Rough explanation of Control-Flow Graph navigation algorithm

Question

Wondering at a high level how you are supposed to go about navigating a Control-Flow Graph (CFG) to perform operations such as dead code elimination. This diagram shows a dead-code elimination problem, how to figure out these variables are related to each other.

Wondering how you go about iterating through the CFG to find things like:

1. Variables that need to be eliminated (dead code)
2. Variables that need to be divided into SSA form
3. Loops that can be merged perhaps.
4. Reordering the nodes perhaps.
5. Other things.

Don't need to know the exact solutions to these problems, just basically trying to get a rough sense of what it takes to figure out the relationship and meaning among the nodes (or blocks of nodes) of the CFG, so I can look further. If I were to do this naively I would, for each node, traverse the graph again to find relationships to it, which seems like it's suboptimal / the wrong approach. For example, finding the reachable definitions seems like, for each variable, you would check every other variable in the program, creating a highly connected graph. Once you make these connections, then you have to actually do something with the data, so that's even more processing. This seems like a lot of memory/traversing, so wondering if this is the right track.

Answer 1

I think you're asking about Data-flow analysis.

Before SSA, we would use bit vectors, where each bit in the bit vector represents a variable in the method being compiled (could be a program variable or an actual or virtual cpu register). We'd use a pair of bit vectors, one for defs and one for uses, and such bit vectors would be conceptually attached to every instruction; though in practice, we would generally only store such bit vectors at the beginning and at the end of each basic block.

These bit vectors are initially computed by traversing each basic block: going forwards through the block, the reaching definition at the end of the basic block has a bit set for each variable that is set(def'd) in the basic block, and, by going backward through the block, the upwards exposed uses at the beginning of the basic block has a bit set for each variable that is used within the basic block.  During the backward traversal, a def masks a use of the same variable, so only variables that are used and not so masked make it into that bit vector stored for the beginning of the block.

Then the bit vectors for the basic blocks are propagated throughout method being compiled (e.g. the other basic blocks) by traversing the control flow graph, merging information until no changes (the merge functions are fixed points, meaning they converge).  If we recognize particular control flow constructs (while loop, if then, etc...), we can stop merging before the final iteration, in which no changes occur.

In usage, once the data flow for the method has been computed, optimization like dead code can performed.  This optimization might start at the end of a basic block, starting with the uses bit vectors and walking backwards.  Traversing backwards, a copy of the uses bit vector could be modified as per each instruction so as to have instruction level information.

Dead code (in terms of variables assigned but not used) is then detected by knowing that, at a particular def, that variable is not in the use set.  The instruction computing that def can be eliminated.  The data flow needs to be updated as a result, and it is common then to find more instructions (earlier, ones that were computing values for the eliminated instruction to use) that are now dead as well.

SSA — by introducing a new version of a variable (e.g. each time it is assigned) and thus tracking versions of variables instead of just variables — allows some of the collected data flow information to apply to the whole method, instead of varying by location in the code as before SSA.