Parts of this blog post are written with the help of Google Gemini. The parts written with Gemini's help will be indicated.
In the last blog post (https://gist.github.com/CharlieQiu2017/aa8374cea7b0033e2e2fcd7cd797c4fd) we looked at the C front-end of GCC. A summary is as follows:
- The front-end parses the input file (called a "translation unit" or "compilation unit") and constructs data structures called "trees."
- The front-end calls various interfaces to pass the trees to the middle-end.
For each function definition it calls
cgraph_node::finalize_function()(ingcc/cgraphunit.cc). For each variable or function declaration it callsrest_of_decl_compilation()(ingcc/passes.cc). For each struct and enum definition it callsrest_of_type_compilation()(ingcc/passes.cc). - After the front-end finishes its task,
compile_file()(ingcc/toplev.cc) callssymbol_table::finalize_compilation_unit()(ingcc/cgraphunit.cc) to initiate the middle-end and the back-end.
One of the first actions done by finalize_compilation_unit() is to "gimplify" the function definitions.
In detail: the GCC middle-end uses a static single-assignment (SSA) intermediate representation called GIMPLE
that is similar to the LLVM IR (https://llvm.org/docs/LangRef.html).
However, the front-ends do not directly generate GIMPLE representations.
Instead, they generate "GENERIC" trees and the middle-end "gimplifies" them into GIMPLE.
In this blog post, we take a look at the code related to this part of GCC.
The actions done by finalize_compilation_unit() are:
-
It calls
finalize_size_functions()ingcc/stor-layout.cc. This function emits so-called "size functions" which are functions that compute the storage size of a complex type dynamically. Values of such types have storage sizes that depend on the value of some field within the type. In C and C++ there are no such types, and we may ignore this function. However, the Ada front-end uses this feature extensively: https://gcc.gnu.org/onlinedocs/gnat_rm/Size-of-Variant-Record-Objects.html. -
It calls
handle_alias_pairs()to process alias symbols. -
It calls
analyze_functions(). This is where the heavy work of call graph analysis and gimplification occur. -
The two functions
handle_alias_pairs()andanalyze_functions()are called again. See below on why the code does this. -
It calls
compile()to run the optimization passes. This part is beyond the scope of this blog post.
In C and C++ it is possible to define aliases of symbols, which are symbols that reference the same target. There are several ways to do this.
The oldest way is to use #pragma weak sym1 = sym2 which declares sym1 as a weak alias of sym2.
See https://gcc.gnu.org/onlinedocs/gcc/Weak-Pragmas.html.
This pragma is handled by maybe_apply_pragma_weak() in gcc/c-family/c-pragma.cc,
which calls assemble_alias() in gcc/varasm.cc.
Another way is to declare the alias target as an attribute. The GCC documentation (https://gcc.gnu.org/onlinedocs/gcc/Common-Function-Attributes.html) shows the following example:
void __f () { /* Do something. */; }
void f () __attribute__ ((weak, alias ("__f")));In this example, f is a weak alias for __f.
The alias attribute is handled by the handle_alias_ifunc_attribute() in gcc/c-family/c-attribs.cc.
However, this function merely generates the tree node for representing the attribute.
Later, rest_of_decl_compilation() will read the alias attribute and call assemble_alias().
The GCC compiler may internally generate aliases of symbols. This is used extensively within the C++ front-end.
To understand the current structure of finalize_compilation_unit() we need to dive into the history of GCC.
In 2009 the following bug report (https://gcc.gnu.org/bugzilla/show_bug.cgi?id=41257) was filed against GCC, then at version 4.5.0:
The following valid code snippet is rejected on trunk when compiled with "-O"
(on x86_64-unknown-linux-gnu):
==================================
struct A
{
virtual void foo();
virtual ~A();
int i;
};
struct B : virtual A {};
struct C : B
{
virtual void foo();
};
void bar()
{
C().foo();
}
==================================
bug.cc:11:1: error: '*.LTHUNK0' aliased to undefined symbol '_ZN1CD1Ev'
To understand this testcase we need some knowledge of the ABI of C++ (https://itanium-cxx-abi.github.io/cxx-abi/abi.html).
Here, struct A is a polymorphic class because it declares two virtual functions (foo and the destructor).
Therefore struct A requires a vtable.
The vtable structure of each type can be dumped with the flag -fdump-lang-class:
Vtable for A
A::_ZTV1A: 5 entries
0 (int (*)(...))0 # Top offset
8 (int (*)(...))(& _ZTI1A) # Typeinfo of A
16 (int (*)(...))A::foo # Virtual function pointers
24 (int (*)(...))A::~A
32 (int (*)(...))A::~A
For an introduction to vtables, see https://nimrod.blog/posts/what-does-cpp-object-layout-look-like/
and https://stackoverflow.com/questions/6258559/what-is-the-vtt-for-a-class.
The first entry is the "offset to top."
The second entry points to the typeinfo of struct A.
The remaining entries are virtual function pointers.
Regarding why there are two destructors of A, see https://stackoverflow.com/questions/44558119/why-do-i-have-two-destructor-implementations-in-my-assembly-output.
Now struct B introduces some complexity into the picture because it declares struct A as a virtual base class.
Virtual inheritance was originally introduced to resolve some difficulties arising from diamond inheritance.
Virtual bases of the same class are only instantiated once, regardless the number of times the class is inherited.
The reason virtual bases are tricky is that, it is no longer straightforward to convert a pointer of a derived class to a pointer of a virtual base. The virtual base is no longer an internal part of the derived class, so we need additional entries in the vtable to record the offset of the virtual bases.
The vtable of struct B is as follows:
Vtable for B
B::_ZTV1B: 12 entries
0 8 # Vbase offset
8 (int (*)(...))0 # Top offset
16 (int (*)(...))(& _ZTI1B) # Typeinfo of B
24 (int (*)(...))B::~B # Virtual function pointers
32 (int (*)(...))B::~B
40 18446744073709551608 # Vcall offset of B::~B
48 0 # Vcall offset of A::foo
56 (int (*)(...))-8 # Top offset
64 (int (*)(...))(& _ZTI1B) # Typeinfo of B
72 (int (*)(...))A::foo # Virtual function pointers
80 (int (*)(...))B::_ZTv0_n32_N1BD1Ev # Thunk functions
88 (int (*)(...))B::_ZTv0_n32_N1BD0Ev
At offset 0 we have a new entry called the Vbase offset,
which records the offset of the data members of struct A from the beginning of an object of struct B.
To convert a pointer of B to a pointer of A, the program reads the Vbase offset from the vtable,
and adds the offset to the pointer.
If we convert a pointer of struct B to a pointer of struct A, and then call delete on the pointer,
the specs require that the destructor of B be called.
Notice that we cannot pass the pointer directly to B::~B(),
because B::~B() expects a pointer of struct B, which is different from a pointer of struct A.
To fix this discrepancy, the compiler introduces entries called "thunk functions" and "Vcall offsets" into the vtable.
The purpose of the thunk function is to adjust the pointer before passing it to the derived class virtual functions.
The Vcall offset informs the thunk function how to adjust the pointer.
Here we see that the Vcall offset of B::~B() is 18446744073709551608,
which is actually the unsigned representation of -8.
This means before calling B::~B() we need to subtract 8 from the pointer address,
which corresponds to converting a pointer of struct A to a pointer of struct B.
Now if we read the assembly output of g++ we will see:
.set .LTHUNK2,_ZN1CD1Ev
.align 2
.weak _ZTv0_n32_N1CD1Ev
.type _ZTv0_n32_N1CD1Ev, %function
_ZTv0_n32_N1CD1Ev:
ldr x12, [x0]
ldr x13, [x12, -32]
add x0, x0, x13
b .LTHUNK2
.size _ZTv0_n32_N1CD1Ev, .-_ZTv0_n32_N1CD1Ev
The compiler creates an alias called .LTHUNK2 to B::~B().
Subsequently, the thunk function uses the symbol .LTHUNK2, not the mangled name of B::~B().
As to why GCC creates this alias, my understanding is that while B::~B() is a public symbol, the alias symbol is local,
so that in position-independent code (PIC) the jump does not need to go through the global offset table.
Gemini agrees with my analysis here.
See https://gcc.gnu.org/legacy-ml/gcc-patches/2003-06/msg02603.html which introduced the thunk alias.
See also https://gcc.gnu.org/pipermail/gcc-patches/2004-April/135822.html which disables this optimization for certain targets.
We now return to the bug report PR41257.
If we compile bug.cc with optimizations enabled,
then g++ will inline the constructors and destructors of struct C inside bar().
Thus there is no need to emit code for C::~C() and its thunk functions separately,
and the middle-end removes them as dead-code.
However, it fails to remove the alias-pair declaration, so the .set directive remains in the assembly code,
resulting in the assembler complaining about an undefined symbol.
The initial response to PR41257 (https://gcc.gnu.org/cgit/gcc/commit/?id=5f1a9ebbc159cb2cad9605777f92e0c73f4cee76) was to emit thunk functions before performing callgraph analysis. We first look at the version before the patch:
/* Before initial response to PR41257 */
void
cgraph_finalize_compilation_unit (void)
{
/* Do not skip analyzing the functions if there were errors, we
miss diagnostics for following functions otherwise. */
finalize_size_functions ();
finish_aliases_1 ();
if (!quiet_flag)
{
fprintf (stderr, "\nAnalyzing compilation unit\n");
fflush (stderr);
}
timevar_push (TV_CGRAPH);
cgraph_analyze_functions ();
timevar_pop (TV_CGRAPH);
cgraph_optimize ();
}The purpose of finish_aliases_1() is to inform the callgraph analyzer that the alias targets are needed.
However, at this point the thunk aliases are not created yet.
They are created when cgraph_analyze_functions() calls cgraph_emit_thunks().
As mentioned in the bug report thread, the thunks are emitted but the target functions are removed as dead code,
resulting in the observed error.
/* Initial response to PR41257 */
void
cgraph_finalize_compilation_unit (void)
{
/* Do not skip analyzing the functions if there were errors, we
miss diagnostics for following functions otherwise. */
/* Emit size functions we didn't inline. */
finalize_size_functions ();
/* Emit thunks, if needed. */
if (lang_hooks.callgraph.emit_associated_thunks)
cgraph_emit_thunks ();
/* Call functions declared with the "constructor" or "destructor"
attribute. */
cgraph_build_cdtor_fns ();
if (!quiet_flag)
{
fprintf (stderr, "\nAnalyzing compilation unit\n");
fflush (stderr);
}
/* Mark alias targets necessary and emit diagnostics. */
finish_aliases_1 ();
/* Gimplify and lower all functions. */
timevar_push (TV_CGRAPH);
cgraph_analyze_functions ();
timevar_pop (TV_CGRAPH);
cgraph_optimize ();
}Here we emit the thunk functions before analyzing the call graph, so the alias targets will not be removed as dead code. However, it was soon found that this sometimes results in more thunk functions than necessary, leading to link errors. The next response was to analyze the callgraph twice:
/* Second response to PR41257 */
void
cgraph_finalize_compilation_unit (void)
{
timevar_push (TV_CGRAPH);
/* Do not skip analyzing the functions if there were errors, we
miss diagnostics for following functions otherwise. */
/* Emit size functions we didn't inline. */
finalize_size_functions ();
/* Call functions declared with the "constructor" or "destructor"
attribute. */
cgraph_build_cdtor_fns ();
/* Mark alias targets necessary and emit diagnostics. */
finish_aliases_1 ();
if (!quiet_flag)
{
fprintf (stderr, "\nAnalyzing compilation unit\n");
fflush (stderr);
}
/* Gimplify and lower all functions, compute reachability and
remove unreachable nodes. */
cgraph_analyze_functions ();
/* Emit thunks for reachable nodes, if needed. */
if (lang_hooks.callgraph.emit_associated_thunks)
cgraph_emit_thunks ();
/* Mark alias targets necessary and emit diagnostics. */
finish_aliases_1 ();
/* Gimplify and lower thunks. */
cgraph_analyze_functions ();
/* Finally drive the pass manager. */
cgraph_optimize ();
timevar_pop (TV_CGRAPH);
}We first do one pass of callgraph analysis.
If a target function is determined to be unreachable, its thunk functions will not be emitted.
Otherwise we emit the thunks, and we call finish_aliases_1() again to ensure the targets will not be removed later.
Finally we call cgraph_analyze_functions() again to gimplify the thunk functions.
This is why analyze_functions() is called twice in the current finalize_compilation_unit() function.
The next update to finalize_compilation_unit() came from Jan Hubicka
(https://gcc.gnu.org/pipermail/gcc-patches/2009-November/274293.html).
This patch adds aliases and thunks as first-class objects into the middle-end.
Now the middle-end recognizes that certain functions from the front-end are thunks,
and the front-end no longer needs to do hacks around assemble_alias().
This patch also removed the emit_associated_thunks hook,
but did not comment on whether it is still necessary to call cgraph_analyze_functions() twice.
Consequently, the finalize_compilation_unit() function almost took its current shape.
Currently, the thunks and aliases created by the C++ front-end are handled as follows.
In gcc/cgraph.cc there are two interfaces called create_alias() and create_same_body_alias().
The latter interface is a thin wrapper over the former one,
with the added feature that calling cgraph_node::get(alias) transparently returns cgraph_node::get(target).
These functions are used by the C++ front-end to create local aliases of virtual functions.
The aliases declared via pragmas and attributes still go through assemble_alias().
They are pushed into a vector called alias_pairs.
The purpose of handle_alias_pairs() is to walk through this vector, and call create_alias() for these aliases.
Thunk functions (which are not aliases, as they contain additional code to adjust the this pointer)
are recorded in the symbol table using special structures called struct thunk_info.
In gcc/cgraph.cc there is a function create_thunk() for adding entries of thunk_info.
The create_thunk() function does not emit the GIMPLE representation of thunk functions.
The actual code is emitted by expand_thunk() in gcc/symtab-thunks.cc.
Within the C++ front-end, the file gcc/cp/method.cc contains three functions
make_thunk(), finish_thunk(), and use_thunk().
The first two functions are used to create a tree node that represents a thunk function,
but does not register it with the symbol table.
When the front-end determines that a thunk function needs to be emitted, it calls use_thunk(),
which performs final processing on the thunk tree node and calls create_thunk().
The analyze_functions() procedure performs the following operations:
- It processes certain attributes declared on functions and variables (see
process_function_and_variable_attributes()). - It "gimplifies" each function (convert the GENERIC representation into GIMPLE).
This is done in two steps: first it calls
gimplify_function_tree(), then it runs several "lowering" passes on the GIMPLE tree. - It computes a "call graph," and eliminates dead code based on the call graph.
- For C++ programs it also computes a type inheritance graph which will be used by the devirtualization pass.
The main part of analyze_functions() is an iterated loop over the symbol table.
For each symbol, the function first checks whether it must be kept (by calling node->needed_p()).
If so, it is considered a "root" vertex of the call graph, and it is queued for analysis by calling enqueue_node().
The gimplification step occurs within cnode->analyze(),
which will also populate the direct and indirect (polymorphic) callee lists of the symbol node.
Then analyze_functions() will add all the direct callees to the analysis queue.
If both optimization and devirtualization are enabled, then analyze_functions() will also go through
the indirect callee list and call walk_polymorphic_call_targets() upon the elements.
The walk_polymorphic_call_targets() function will identify all possible targets of
a polymorphic call and queue them for analysis.
I believe that having walk_polymorphic_call_targets() call enqueue_node() is mostly redundant.
Gemini agrees that this call is redundant in the majority of cases.
However, there are some edge cases related to inline.
Suppose that I declare a virtual function, and supply an inline implementation of the virtual function:
class A {
virtual void fun ();
};
inline void A::fun () {
return;
}
int main () {
A a;
a::fun ();
}Suppose that devirtualization is disabled.
Then the inline version of A::fun() may be ignored, because it is not exported and not directly called within the file.
However, if devirtualization is enabled, then the devirt pass may convert a::fun() into a direct call to the inline version.
Consequently, the inline version of A::fun() must be analyzed and compiled.
As you can see, analyzing a call graph vertex may lead to more vertices being queued for analysis.
Hence the loop in analyze_functions() is iterated until the call graph stabilizes.
We are now ready to dive into cgraph_node::analyze().
The source code is actually very short and clear.
If the function is a thunk, we call expand_thunk() which directly generates the GIMPLE tree.
If the function is an alias, we resolve the alias.
If the function is a multi-version dispatcher (this is related to GNU_IFUNC),
then we call a target-specific hook to generate the dispatcher body.
After these special cases, we call gimplify_function_tree()
and then execute_pass_list (cfun, g->get_passes ()->all_lowering_passes).
The basic data structure for GIMPLE trees is struct gimple, defined in gcc/gimple.h.
Like GENERIC trees, each instance of struct gimple begins with a tree code,
and the GIMPLE tree codes are defined in gcc/gimple.def.
Both gimple_seq and gimple_seq_node are defined to be struct gimple *.
A gimple_seq is a linked list of GIMPLE tree nodes.
The comments in gcc/gimple.h say:
/* [ WORD 4-5 ]
Linked lists of gimple statements. The next pointers form
a NULL terminated list, the prev pointers are a cyclic list.
A gimple statement is hence also a double-ended list of
statements, with the pointer itself being the first element,
and the prev pointer being the last. */
The GIMPLE tree immediately after gimplify_function_tree() can be dumped with -fdump-tree-gimple.
Alternatively, GIMPLE trees can be printed in GDB using the functions provided in gcc/gimple-pretty-print.cc.
Example:
int fun (int a, int b) { return a + b; }After gimplification, we get:
{
int D.3484;
D.3484 = a + b;
return D.3484;
}
After gimplification, there are 13 "lowering" passes that convert GIMPLE into a fully SSA form.
Passes whose name begins with * are those that do not have their own dump files.
These passes usually only perform internal analysis and do not modify the function tree.
Around half of the passes can be ignored.
*warn_unused_result(gcc/tree-cfg.cc)*diagnose_omp_blocks(OpenMP)*diagnose_tm_blocks(Transactional Memory)omp_oacc_kernels_decompose(OpenMP)omplower(OpenMP)lower(gcc/gimple-low.cc)tmlower(Transactional Memory)ehopt(Exception Handling,gcc/tree-eh.cc)eh(Exception Handling,gcc/tree-eh.cc)coro-lower-builtins(Coroutines,gcc/coroutine-passes.cc)cfg(gcc/tree-cfg.cc)*warn_function_return(gcc/tree-cfg.cc)coro-early-expand-ifns(Coroutines,gcc/coroutine-passes.cc)ompexp(OpenMP)*build_cgraph_edges(gcc/cgraphbuild.cc)
Clearly the most importaant step is lower. It is explained as follows in gcc/gimple-low.cc:
/* The differences between High GIMPLE and Low GIMPLE are the
following:
1- Lexical scopes are removed (i.e., GIMPLE_BIND disappears).
2- GIMPLE_TRY and GIMPLE_CATCH are converted to abnormal control
flow and exception regions are built as an on-the-side region
hierarchy (See tree-eh.cc:lower_eh_constructs).
3- Multiple identical return statements are grouped into a single
return and gotos to the unique return site. */