Control Flow Graph (CFG)

LLVM builds a CFG for a given function, and this CFG is available when your function pass is running. Let us call it LLVM CFG. The function void initializeForwardMap(Function * func) in 231DFA.h also builds a CFG of the given function func for forward analyses. Let us call it DFA CFG. Analyses based on 231DFA.h should work on DFA CFGs. DFA CFGs are slightly different from what we have seen during lectures.

First, any instruction may have more than one incoming data flows, as is shown below

So the first step of any flow function should be joining the incoming data flows.
Second, in the lecture PHI nodes are used to synthesize values from different paths in an SSA representation. In LLVM IR, the phi instructions serve a similar functionality. However, because the phi instruction is an IR instruction and any IR instruction can return at most one value, if multiple values need to be synthesized there will be a number of phi instructions at the beginning of a basic block. I.e. in the LLVM CFG, an IR basic block may start with a number of consecutive phi instructions. In the DFA CFG, the first phi instruction connects to the first non-phi instruction in the same basic block directly, bypassing all the other phi instructions. Below is an example to illustrate these two kinds of CFG for the same code:

There are k phi instructions at the start of the basic block C. In the LLVM CFG, these phi instructions are connected sequentially. In the DFA CFG, phi 1 has an outgoing edge connecting to the first non-phi instruction %res = add %a, %b directly. When encountering a phi instruction, the flow function should process the series of phi instructions together (effectively a PHI node from the lecture) rather than process each phi instruction individually. This means that the flow function needs to look at the LLVM CFG to iterate through all the later phi instructions at the beginning of the same basic block until the first non-phi instruction.

Lattice

This analysis operates on LLVM IR, so we only care about the reaching definitions of LLVM IR variables. Note that LLVM IR is in Single Static Assignment (SSA) form, so every LLVM IR variable has exactly one definion. Also, because any LLVM IR instruction that can define a variable (i.e. has a non-void return type), can only define one variable at a time, there is a one-to-one mapping between LLVM IR variables and IR instructions that can define variables. For example, below is an add IR instruction:

%result = add i32 4, %var

%result is the variable defined by this add instruction. None of any other instructions can redefine %result. This means that we can use the index of this add instruction to represent this definition of %result. Since a definition can be represented by the index of the defining instruction, unlike the reaching analysis taught in class, the domain D for this analysis is Powerset(S) where S is a set of the indices of all the instructions in the function. The bottom is the empty set. The top is S. ⊑ is ⊆ ("is subset of").

Flow Function

This analysis works at the LLVM IR level, so operations that the flow functions process are IR instructions. The flow functions are specified below. You need to implement them in flowfunction in your subclass of DataFlowAnalysis. There are three categories of IR instructions:

First Category: IR instructions that return a value (defines a variable)

where index is the index of the IR instruction, which corresponds to the variable <result> being defined.

Second Category: IR instructions that do not return a value

Third Category: phi instructions

where indices is the set of all the indices of the phi instructions.

For the reaching definition analysis, you only need to consider the following IR instructions:

1. All the instructions under binary operations;
2. All the instructions under binary bitwise operations;
3. br;
4. switch;
5. alloca;
6. load;
7. store;
8. getelementptr;
9. icmp;
10. fcmp;
11. phi;
12. select.

Every instruction above falls into one of the three categories. If an instruction has multiple outgoing edges, all edges have the same information. Any other IR instructions that are not mentioned above should be treated as IR instructions that do not return a value (the second categories above).