When computing SSA form, we used the concept of dominance frontier to decide where to
place phi-nodes.
Dominance forniter of node X is the set of nodes at which dominance of X ends.
Dominance frontier cannot be used to determine wether allocas are ambiguous in memory
to register promotion.
IN dominator tree each node is either header of a loop or an entrance to an if-else.
Relation between post dominance frontier and CDG.
SRA done before Mem2reg.
Optimization
Mem to register promotion:
Idenify unambiguous allocas. All uses of the alloca should be as the base address of a load
or a store.
Memory to register promotion pseudocode in the lecture doesn’t remove the alloca, but it
could.
Note, the stores must be removed because other passes, notably DCE, can’t easily remove
them. Insert phi-nodes in dominance frontier basic blocks.
Scalar replacement of aggregates:
Idenify unambiguous array. Array is unambiguous if and only if it is referenced with
constant indices.
All uses of the alloca should be as the base address of a getelementptr. SRA does not
promote to a register; rather, we let the memory-toregister
pass do that for us later.
Dead Code Elimination:
In terms of optimization development, we will often leave dead instructions behind
knowing that DCE will clean them up.
But, we can’t do this for instructions that DCE ignores, like stores and branches
Common Subexpression elimination:
explicit redundancy, same opcode, same operand, in a node dominated by instruction.
In the Common Subexpression Elimination (CSE) pass presented in lecture, loads and
stores can be determined
to be redundant only if they occur in the same basic block.
However, this is only a technical limitation of our algorithm not a fundamental limitation
