Mentor: David Malcolm | Organization: GNU Compiler Collection

Summary

The goal of my project for GSoC'26 was to improve C++ support in the -fanalyzer. When the project was proposed, several features needed to be implemented in order to be able to support large sets of C++ programs, and one of the targets that provided the most improvement was adding support for polymorphism.

The project ended up implementing exception subclass matching, virtual function devirtualization and modeling dynamic_cast. These additions let the analyzer reason about polymorphic C++ by tracking exceptions through class hierarchies, analyzing the real callee of a virtual dispatch, and catching bugs like dereferencing the result of a failed dynamic_cast.

Since much of the standard library uses dynamic_cast or virtual methods in some form (and many common methods throw exceptions), adding support for these features is an important pre-requisite towards bigger goals like analyzing and modeling std::vector and other containers, checking iterators for invalidation, and analyzing std::variant or std::unique_ptr.

Background

As a general overview, GCC’s static analyzer does coverage-guided symbolic execution over gimple-SSA IR (which is GCC’s Intermediate Representation used for performing optimizing transformations, and all frontends are lowered to it before being lowered to assembly). It builds a graph of the user’s code (called the supergraph) and then explores it with a worklist, building an exploded graph whose nodes are <program point, state> pairs.

Since it is doing static analysis, it never performs any transformation on the input IR. Instead, it just walks paths and emits warnings when a path reaches a “bad” state, with the goal of providing users with useful diagnostics about bugs or vulnerabilities in their code (i.e. use-after-free, double-close, memory leaks, etc).

The state at each node includes a region_model, which is a representation of memory where a store records bindings from region instances (a variable, a field, a heap allocation) to svalue instances (a constant, an initial value, a pointer, the result of a binop). Values can be pointers to regions, which means the full region representation is graph-like.

The region model also includes:

  • a constraint_manager, which records what’s known about relationships between values.
  • dynamic extents, mapping dynamically-allocated regions to svalues (their capacities).

In practice, when the model can’t determine something it chooses to be conservative, and where it can’t model a construct at all it stops exploring that path. Note that, from a formal standpoint, the analyzer is neither sound nor complete.

It’s also important to note that the analyzer was written with the goal of being able to support various frontends and eventually supporting LTO (which is why it works on top of gimple-SSA IR), but each language it wants to support invariably needs many specific constructs to be modeled in order to provide useful diagnostics.

Before this project, the C++ constructs whose behaviour depends on an object’s runtime type were handled conservatively as unknown functions (like virtual calls, catch matching and dynamic_cast), so each encounter with these constructs would result in imprecise modeling of state. That meant most of a C++ program past the first virtual call or past a catch clause couldn’t be analyzed meaningfully, which doesn’t allow for very useful analysis.

Luckily, all of these missing features touch on the same general problem, and the analyzer already has the infrastructure it needs to solve it. To see why, it is useful to look at what the compiler actually emits for a polymorphic object.

How to find the runtime type of a polymorphic object

If a class has virtual methods, every object of that class carries a vptr, which is a hidden pointer member to a table of function pointers called the vtable:

struct A { int a; virtual void v (); };
struct B : A { int b; };

Representation of a given instance of a B object and its vtable:

                              The vtable:
                              +-----------------------+
                              |     0 (top_offset)    |
         The B object:        +-----------------------+
b_ptr --> +----------+        | ptr to typeinfo for B |
          |  vptr    |------> +-----------------------+
          +----------+        |         A::v()        |
          |    a     |        +-----------------------+
          +----------+
          |    b     |
          +----------+

Note that the vptr doesn’t point at the start of the vtable, but at the first function slot, with top_offset and the typeinfo pointer sitting above it at negative offsets.

The important detail here is that the vtable which a B object’s vptr points to belongs to B, not to A, and not to whatever the static type of the pointer we’re holding happens to be. Each constructor that is called when creating a polymorphic object writes the vptr for the class it is constructing, so by the time the most-derived constructor finishes, the vptr is the runtime type of the object.

The concept of a most-derived object is important when talking about polymorphism, and for understanding the rules of dynamic_cast later. A most-derived object is an object that isn’t a subobject of anything else (it is the complete object). For example, if we use the types defined in the above example and have:

B b {};
A* a = &b;

When we are talking about a, the most-derived object it points into is still b, and its most-derived type is B. The A we hold a pointer to is only a subobject of it, and the static type of the pointer says nothing about how far the real object extends. When an object isn’t a subobject of anything it is trivially its own most-derived object.

Another case to consider is that, under multiple inheritance, an object ends up with more than one vptr:

struct A { int a; virtual void v (); };
struct B { int b; virtual void w (); };
struct C : A, B { int c; };

Representation of a given instance of a C object and its vtable:

                               The vtable:
                               +-----------------------+
                               |     0 (top_offset)    |
          The C object:        +-----------------------+
c_ptr --> +-----------+        | ptr to typeinfo for C |
          |   vptr    |------> +-----------------------+
          +-----------+        |         A::v()        |
          |     a     |        +-----------------------+
          +-----------+        |   -16 (top_offset)    |
          | (padding) |        +-----------------------+
          +-----------+        | ptr to typeinfo for C |
          |   vptr    |------> +-----------------------+
          +-----------+        |         B::w()        |
          |     b     |        +-----------------------+
          +-----------+
          |     c     |
          +-----------+

Both of them point into the same vtable object, just at different top_offset11top_offset is the distance from this subobject back to the start of the most-derived object, which is 0 for the A subobject at the top and -16 for the B subobject (the A subobject is a vptr plus an int, padded up to the vptr’s alignment of 8). It’s what __dynamic_cast uses to find the most-derived object given only a pointer to a base subobject. values. This is what makes type substitution work: passing a C* to a method expecting a B* adjusts the pointer by 8 bytes, and the callee finds a B subobject there with C’s vptr, which lets us identify what the original most-derived type for our object was.

In practice this means the pair (vtable decl + byte offset into it) carries two pieces of information at once which we care about: the vtable’s owner is the most-derived type of the object, and the offset identifies which subobject’s vptr was read.

How dynamic_cast works

A downcast or crosscast with dynamic_cast<T*>(p) generally can’t be resolved statically, since the whole point of dynamic_cast is that the most-derived type isn’t known at the cast site. So the frontend lowers it to a library call:

void *__dynamic_cast (const void *__src_ptr,
                      const __class_type_info *__src_type,
                      const __class_type_info *__dst_type,
                      ptrdiff_t __src2dst);

__src2dst22 Each __src2dst value has a different meaning:
>= 0: the source type is a unique public non-virtual base of the target, sitting at this offset (dst_ptr + src2dst == src_ptr);
-1: no hint, the relationship is unspecified;
-2: the source type is not a public base of the target;
-3: the source type is a public base of the target more than once, but never a virtual base. is a hint the frontend computes from the static types, describing how the source relates to the target. The runtime uses it to shortcut its search, since a non-negative value lets the walk check a candidate target by adding the offset and comparing against the source pointer.

A call to __dynamic_cast might look like this:

d = __cxxabiv1::__dynamic_cast (b, &_ZTI4Base, &_ZTI7Derived, 8);

At runtime, libstdc++’s __dynamic_cast reads the vptr out of the source pointer and steps back into the vtable prefix, i.e. the header sitting at negative offsets. This prefix gives it the offset from this subobject to the start of the complete object and the __class_type_info of that complete object. From there it walks the class hierarchy in a single traversal, looking for the source subobject and for every subobject of the target type, accumulating along the way which of src, dst and the whole object are publicly reachable from which. Once the walk returns, those flags are tested in sequence to decide if the rules in [expr.dynamic.cast]/9 were satisfied.

It’s also useful to go over the rules specified in the C++ standard, as the analyzer has to implement them in order to correctly evaluate dynamic_cast calls. Effectively, these rules act as 2 distinct searches:

/9.1 (the downcast): does src point to a public base subobject of a target object, and is that the only target object derived from the subobject src points to? The search starts at the source subobject, so we expect the hierarchy to look like SrcType -> ... -> DstType -> ... -> MDType, and the path from the target down to the source must be public.

/9.2 (the crosscast): otherwise, does src point to a public base subobject of the most-derived object, and is the target an unambiguous public base of it? This search starts at the most-derived object (MDType -> ... -> DstType). This means the target it finds can be on a branch of the hierarchy which isn’t from the source.

If neither succeeds, /9.3 says the runtime check failed, and the result is a null pointer (or a std::bad_cast when casting to references).

Both clauses require that the found target is both unique and publicly reachable. Note that these two requirements are orthogonal, since a second target found through a private path is still a duplicate and makes the cast ambiguous. This means the search has to ignore access specifiers while checking for ambiguity, and needs to track accessibility separately.

How the analyzer implements it

Putting both of the earlier concepts together, __dynamic_cast needs the most-derived type at runtime, and has to go through considerable work to obtain it, like checking typeinfo subclasses, doing hierarchy walks, and adding various checks to bail out early wherever possible.

However, unlike libstdc++, the analyzer isn’t called during the runtime (it runs right before optimizations, after each frontend has lowered to gimple-SSA IR). More importantly, it has already analyzed past constructor calls, which means the store mechanism binds the object’s vptr field to the _ZTV* decl like it would for any other write. The vptr ends up stored as a binop_svalue over a region_svalue and a constant:

cluster for: c
  _vptr.C: (&_ZTV1C + (long unsigned int)16)

This means the dynamic type is already sitting in the model, and no feature needs to go through the effort of modelling this type separately or adding any dynamic-type tracking. It is, then, enough for both of the features that depend on the runtime type to recover the decl and the offset from that binding:

  • for a virtual call, the vtable decl and the vptr offset, together with OBJ_TYPE_REF_TOKEN, index the vtable initializer and give the concrete callee;
  • for dynamic_cast, the vtable’s owner is the most-derived type and the offset identifies which subobject’s vptr was read. Then, [expr.dynamic.cast]/9 can be run over the BINFOs at analysis time, yielding either a pointer to a subobject or a null.

Finally, catch matching doesn’t rely on the machinery above, since the thrown type is known statically at the throw site and no vptr is involved. It is, however, still the same kind of question about the class hierarchy (is the handler type a base of the thrown type, publicly and unambiguously reachable). Since the frontend already knows how to answer this, the analyzer queries it to decide if a handler matches or not the thrown type.

Most of the work performed here is reading back information the analyzer already had access to from its core infrastructure and modeling it explicitly with C++ semantics, while also deciding when it needs to be conservative about what it can derive in each case.

Technical details and implemented work

Exception subclass matching - PR analyzer/119697

exception_matches_type_p previously only treated an exception as caught when the handler type and the exception type were identical, so a handler for a base class never matched a thrown derived class.

Since the analyzer is made with the goal of supporting various languages, we can’t just implement C++ exception handling rules directly. Even if we did, this would have to be done again for each frontend the analyzer wanted to support.
Given that, an exception_matches_type_p langhook that each frontend can implement was added, returning whether a handler of one type catches an exception of another per the analyzed language’s rules. The default returns false, keeping the behaviour for frontends without exception support, and the C++ frontend implements it with handler_match_for_exception_type.
This keeps the analyzer language-agnostic while correctly analyzing [except.handle] cases like ambiguous bases, private bases, cv-qualification, pointer conversions and nullptr.

It should be noted that since there is a single global lang_hooks instance, only one frontend’s rules are available for the whole analysis regardless of which translation unit a given catch came from. This means the implementation doesn’t handle LTO when compiling mixed C and C++.

Virtual function devirtualization - PR analyzer/97114

Virtual calls appear in GIMPLE as OBJ_TYPE_REF calls, which were not previously handled, so every one of them resulted in an unresolved call.

get_fndecl_for_call now handles them. It reads the value bound to the object’s vptr field, and if that value has the form &vtable_decl + constant, the vtable decl and offset are recovered and passed to gimple_get_virt_method_for_vtable together with OBJ_TYPE_REF_TOKEN (the slot index) to look up the concrete fndecl in the vtable initializer, which is then resolved through ultimate_alias_target. Finding a conjured vptr or a non-constant offset means the dynamic type is unknown and the call stays unresolved.

can_throw_p was also extended to resolve through function_symbol(), so thunks are followed to the function underneath, and to then check TREE_NOTHROW on the result. This means noexcept is read off the resolved override rather than off whatever wrapper happened to sit in the vtable slot. Thunks show up here because a vtable slot is only a function pointer, with nowhere to record that this needs adjusting by a fixed offset first, so under multiple inheritance the adjustment has to be a real function that fixes the pointer and jumps to the override.

The implementation does not enumerate possible subtypes, so when the most-derived type isn’t known it won’t check whether each candidate override could throw or leak. Thunk fixed_offset is also not applied before binding this, so the interprocedural multiple-inheritance case is still imprecise, which is likely fixable by applying the offset at bind time. This was left as follow-up.

Note that none of what was implemented here is really C++-specific, since it only deals with OBJ_TYPE_REF and the GIMPLE representation of vtables, so this work is applicable to other frontends that support virtual calls.

dynamic_cast modeling - PR analyzer/110578

dynamic_cast lowers to a call to __cxxabiv1::__dynamic_cast, so this adds a known_function for it.
The runtime check of [expr.dynamic.cast]/9 is evaluated statically when the dynamic type is known, yielding either a pointer to the target subobject or a null pointer, and otherwise the LHS is left conjured. This makes bugs like dereferencing the result of a failed cast visible.
The reference form doesn’t need any extra handling, since the frontend emits the null check and the __cxa_bad_cast call itself, thus from this known_function’s perspective, modeling the null result is enough to get [expr.dynamic.cast]/10 (although std::bad_cast still needs to be specifically modeled with its own known_function).

The dynamic type comes from the same vptr binding used for devirtualization, so get_vtable_from_obj was factored out of get_fndecl_for_virtual_call. The vtable’s DECL_CONTEXT gives the most-derived type, and the offset identifies which subobject’s vptr was read. The source and target class types are recovered from the &_ZTI* typeinfo arguments since the C++ frontend adds them to the TREE_TYPE of the tinfo decl’s DECL_NAME. The __src2dst hint is ignored, since it only exists to let the runtime prune its search. The analyzer walks the BINFOs directly so it never needs the hint, and using it would make the implementation more complex for marginal benefit.

Both clauses of /9 are implemented as a BINFO search over the most-derived type’s hierarchy, tracking per-path accessibility. Some things need to be considered during the BINFO search:

  • ambiguity ignores access specifiers, so a second match down a private path still counts as a duplicate;
  • morally-virtual matches of the same type under different virtual ancestors are distinct subobjects, so matches are deduplicated by BINFO_OFFSET rather than by type;
  • with shared primary-base vtables the binfo owning a vptr value may be an enclosing type, so the source subobject is found by descending the primary chain at relative offset 0.

The result is built as a concrete offset_region relative to the operand’s base region, so it aliases the frontend’s own field accesses to the same bytes, which for e.g., lets us prove that c->m == 50 after the cast rather than just knowing that the cast didn’t fail.

known_function_manager::get_match previously only matched functions at global scope, and now also matches namespace __cxxabiv1 (added in a separate helper patch).

Since __dynamic_cast is an ordinary function that can also be called directly, none of the shapes above can be assumed when analyzing code. The handler sets the LHS to its defaults before doing anything else, so bailing-out leaves a conjured result. The same applies when the most-derived type simply isn’t known, which is the common case for a Base * coming out of an unknown function.

Various tests were added to cover all the possible cases of each clause and the various unique type hierarchy scenarios that might arise with dynamic_cast.

Bugs/PRs resolved

Upstream review of these patches can be found here:

Notes from this project are maintained on the GCC Wiki at StaticAnalyzer/C++.
Status reports throughout the project can be seen here.
Additionally, my GCC commits can be seen here.

For further information on the inner workings of GCC’s -fanalyzer, it is useful to read the analyzer internal documentation.
For people interested in using GCC’s analyzer, see the user facing documentation.

Moyang Wang’s Vtable Notes are also a good resource to read more about the layout of GCC’s vtables and other internal details.

What’s left

I was able to implement all of the items I had planned for the project, and also ended up contributing dynamic_cast support since I finished my project early (ironically, it ended up taking longer than both of the items I had initially set out to do).

A couple details were left as out of scope throughout the project, and they are left here as possible things to work on:

  • Applying thunk fixed_offset before binding this, to fix the interprocedural multiple-inheritance case.
  • Exception matching with LTO / mixed-language compilation.

Conclusion

Thanks to David Malcolm for mentoring and reviewing my patches, and to the gcc-patches reviewers. David was very helpful throughout the entire project and I really appreciate the time he set out to review and guide my project.

GSoC'26 helped me get more comfortable with new areas of GCC, and has helped solidify my ability to do various work around the codebase and the project itself, from the wiki to the mailing lists. It was also a good opportunity to learn more about static analysis academically, but also learn how it is handled in a project like GCC where the goal is finding bugs while developers are compiling their projects, rather than to offer an academic and formal implementation of a static analyzer. David also recommended some good books that have been quite useful in learning more about the field, and I hope to continue studying and learning more about static analysis.

I was happy to have the opportunity to contribute in a more structured manner to GCC and interact more with the community through GSoC'26, and I’ll definitely continue doing work for the static analyzer and other areas in GCC in the future.