The RepoMetadataGeneration and RepoPruning Passes

Two passes — called RepoMetadataGeneration and RepoPruning — are added to the LLVM pass pipeline. They enable the compiler to avoid the code generation phases for functions and global variables whose definitions already have binary representations in the repository. These new passes belong to the ModulePass class and are placed as early as possible in the pass pipeline, and thus avoid wasteful work in the later phases of the compiler.

The RepoMetadataGeneration Pass

This pass loops over all of the functions and variables in the input module. If the function or variable is defined in the input module and will be emitted to the output file, a cryptographic hash digest is calculated to identify it. The digest is attached to the function or variable as TicketNode metadata, which includes the digest, linkage type, visibility type and pruned status. The pruned field will be used by the RepoPruning pass and will be set to true when the function or variable is pruned.

The hash calculation for functions and variables must consider all aspects of the IR definition and its environment that affects the final generated code. The environment includes the target triple, the data layout for the module’s target platform, and the collection of enabled LLVM passes.

Hash Calculation

Functions

The function hash calculation needs to consider the following:

• The function attributes (including those for its return type and formal arguments).
• Whether the function takes a variable number of arguments.
• The calling convention. Calling conventions may differ in where parameters, return values and return addresses are placed (in registers, on the call stack, a mix of both, or in other memory structures). If the function has input parameters, and the function return type is not void, then the calling conventions need to be considered.
• The function return type.
• The type and number of formal arguments.
• The function body. We do a control-flow-graph ordered walk since the actual ordering of the basic blocks in the linked list is immaterial. Our walk starts at the entry block for the function, then visits the next block from each terminator in order; as an artefact, this also means that unreachable blocks are ignored. When hashing each instruction, the opcode, return type, operand types, operand values, and any other factors affecting the operation must be considered.

The function name doesn’t need to be considered in the hash calculation.

Global Variables

The global variable hash calculation needs to consider the following:

• The variable type.
• Whether the variable is a constant.
• The thread local mode.
• The alignment.
• The GlobalVariable::UnnamedAddr type.
• The initial value (if present) or the the default initializer.

Contributions

A global object (GO) is either a function or a global variable. The Contributions of a GO (X) are those GOs (Y) which transitively reference X and where a potential optimisation to either X or any of Y may invalidate both. For example, if a function test() calls a function setto() and setto() modifies a global variable g, test()’s hash will contribute to g’s hash.

For example, if there is a file named test.c:

int g = 0;
void setto (int * const p, int v) { *p = v; }
void test (void) { setto (&g, 2); }

When test() is modified to void test (void) { setto (&g, 3); }, both test()’s and g’s hashes need to change since setto() potentially changes g’s value. The GOs’ contributions are:

GO	Contributions
g	test
setto	empty
test	empty

Dependencies

The Dependencies of an object are those objects which it transitively references but are not Contributions. For the above example, if the function test() calls setto() and g is an input parameter of setto, test()’s hash will depend on setto () and g. When setto() is modified, test()’s hash needs to change if setto() is potentially inlined.

For the above example, The GOs’ contributions and dependencies are:

GO	Dependencies	Contributions
g	empty	test
setto	empty	empty
test	g, setto	empty

Final Hash Value

A GO’s hash transitively includes the hashes of the set of global objects on which it depends. It is calculated by accumulating its initial digest, the digest of all its dependencies and contributions. The initial digest is the hash of an object itself (a function or global variable) without consideration for any references to other objects. The names of the GO’s dependencies must also be accumulated in the GO’s initial hash.

For example, if there are two files (a.c and b.c):

a.c:

extern int quz();
extern int a;
static int a_foo () {
    return quz() + a;
}
int a_bar () {
    return a_foo();
}

b.c:

extern int quz();
extern int a;
static int b_foo () {
    return quz() + a;
}
int b_bar () {
    return b_foo();
}

The functions a_foo() and b_foo() have references to the same fragment in the repository since they have the same hash. Comparing the definitions of a_bar() and b_bar(), the only difference is the call: the callee’s name is different. If we only accumulate the hash of the dependents, the a_bar() and b_bar() hashes will match, incorrectly identifying them as having the same body. The a_bar() fragment has an external fixup to a_foo (a symbol defined with internal linkage by the ticket corresponding to the a.c file). The b_bar() fragment also has an external fixup to b_foo (a symbol defined with internal linkage by the b.c. ticket). The names of the GO’s dependents must also be accumulated in the GO’s hash.

For the above example, the GOs’ final hashes are:

Hʹ(g) = H(g) + H(test)
Hʹ(setto) = H(setto)
Hʹ(test) = H(test) + H(g) + H(setto)

Notation:

• Hʹ(x) is the “final” hash of x
• H(x) is the “initial” hash of x
• ‘+’ means concatenation of two hashes.

The RepoPruning Pass

The RepoPruning pass removes unchanged GOs whose definitions already have binary representations in the repository. If a GO is pruned, it is changed from a definition to a declaration to avoid the later phases of the compiling process. At the same time, TicketNode metadata is added for all of the fragment's dependents.

The following example explains the GO’s dependent list.

test.ll:

target triple = "x86_64-pc-linux-gnu"

@.input_str = private unnamed_addr constant [7 x i8] c"hello\0A\00", align 1

declare i32 @printf(i8* nocapture readonly, ...)

define void @test() align 2 {
entry:
  %call = call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([7 x i8], [7 x i8]* @.input_str, i32 0, i32 0))
  ret void
}

Optimised IR can be generated using the following command:

$ rm clang.db
$ opt -O3 -S test.ll -mtriple x64_64-pc-linux-gnu-repo -o test.opt.ll

The RepoMetadataGeneration pass creates the TicketNode metadata for each GO. The optimised IR code is given below:

target triple = "x64_64-pc-linux-gnu-repo"

@str = private unnamed_addr constant [6 x i8] c"hello\00"

define void @test() local_unnamed_addr align 2 !repo_ticket !0 {
entry:
  %puts = tail call i32 @puts(i8* getelementptr inbounds ([6 x i8], [6 x i8]* @str, i64 0, i64 0))
  ret void
}

declare i32 @puts(i8* nocapture readonly) local_unnamed_addr

!repo.tickets = !{!0, !1}

!0 = !TicketNode(name: "test", digest: [16 x i8] c"l1uX\9Fr\90o\B4\D8\F9\184\A3\9E\AA", linkage: external, pruned: false)
!1 = !TicketNode(name: ".input_str", digest: [16 x i8] c"\B4\82v\D2\94k\8A5\A9\BD\E4P\DB\EB\BA\D4", linkage: private, pruned: false)

The test() function’s fragment has an external fixup to a symbol str which is a global variable generated by the optimizer. This new global variable doesn’t have TicketNode metadata since this is opimization occurs after the RepoMetadataGeneration pass. The MC-repo backend will create a ticket member for the symbol str, save it to the repository, and add it to the fragment's dependents. When the function test is pruned, the TicketNode metadata must include test() itself and its dependent symbol str.