|
Prev: Creating Statements
Data Flow Analysis
So far we have only considered code execution paths without consideration
for what each arithmetic instruction does. We've only been concerned about
branches and compare instructions.
However we have seen in the previous page that we cannot collapse multiple
if statements without collapsing at least some of the instructions between
the branch instructions.
Since registers are not directly accessible by a C program, a good guideline is
to try to remove all register references from instructions. What's left should
be fairly close to the original source file.
But when is it safe to collapse multiple instructions without changing the
behavior of the converted program?
The answer is: when we are sure that there is no loss of data when we
remove an instruction.
Consider the following sequence of instructions:
MOV R1, var_1
R1 = var_1;
CMP R1,#10
if(R1 == 10 ||
L0: JEQ L1
CMP R1,#20
R1 == 20) {
JNE L2
L1: ....
L2:
}
In this sequence we cannot simply collapse the first 2 instructions into a
single "CMP var_1, #10", because the value in R1 is used again in the second CMP
instruction. In this case it is safe to assume that the second CMP instruction
also checks the value of "var_1", so it is safe to convert it to "CMP var_1,
#20". This would lead to the final statement:
if(var_1 == 10 || var_1 == 20) {
}
If the value of register R1 is used at or after the instruction L0, we say that the
register is "alive" at L0.
Instead, if the register is reloaded with another value in a subsequent
instruction, we say that the register is "dead" at L0.
Thus, the "liveness" of a register is an attribute of each instruction.
It's easy to compute the liveness of a register in a basic block. It's more
difficult to compute the lifetime of a register across basic blocks. For example
in the following code:
MOV R2, var_2
...
JEQ L3
...
L4:
MOV R1, var_1
CMP R1,#10
if(var_1 == 10 ||
JEQ L1
CMP R2,#20
var_2 == 20) { // ?
JNE L2
L1: ....
L2:
}
How do we know that R2 still has the value of var_2 at the CMP R2,#20
instruction?
There may be an execution path from another R2 assignment that enters the block
L4, in which case we cannot know what the value of R2 is. Or, there can be
another use of R2 after the compare instruction.
We need to perform a global lifetime analysis on all the basic blocks of the
function, considering how execution flows from block to block, and computing
whether each register is "dead" or "alive" at each instruction.
Data Representation
Liveness information is typically represented as a set of bits per each
instruction. Each bit in the set represents one of the variables we want to
track. Despite the importance of data flow analysis, books on compiler
implementation use different terms to identify the information described in the
liveness sets. Some compute the sets of killed and used variables; others
compute the sets of live and dead variables, although this definition doesn't
say if the variables are live when entering the instruction or when exiting the
instruction.
I think a clearer identification of the liveness information involves computing
the "livein" and "liveout" sets, meaning the set of variables that are alive
before executing the instruction, and those that are alive after executing the
instruction.
Since we are dealing with assembly instructions and we want to track the
liveness information of each register, it makes sense to have a bit set where
each bit represents a CPU register. Here's an example:
Instruction stream LiveIn(i) Set
LiveOut(i) Set Def(i) Set Use(i) Set
R1 = var_2
R1
R1
R2 = R1 + 1
R1
R1? R2 R2
R1
var_2 = R2
R1? R2 R1? R2?
R2
Computing Use and Defs
You can see that the LiveIn and LiveOut sets depend on the information provided
by 2 functions of each instruction. The Def(i) function returns the set of
registers that are "defined" (written) by instruction 'i'; the Use(i) function
returns the set of registers "used" (read) by instruction 'i'. Def(i) and Use(i)
only depend on each instruction. Here is some code that computes Def(i) and Use(i):
ComputeUseDefs()
{
for each instruction i in each block in CFG
i.defs = 0
if i.op == Assign && isRegister(i.dest)
i.defs = BitSet(i.dest.regnum)
i.use = 0
if i.src1 && isRegister(i.src1)
i.use |= BitSet(i.src1.regnum)
if i.src2 && isRegister(i.src2)
i.use |= BitSet(i.src2.regnum)
}
This code assumes that each operand can only be a memory location, a constant or
a register. If an operand can be something more complex, such as an indexed
addressing mode, then we need to consider every single piece referenced by the
addressing mode and set all the relevant bits in the Def(i) and Use(i) sets.
A more robust algorithm, using a tree to represent both source and
destinations operands is as follows:
ComputeUseDefs()
{
for each instruction i in each block in CFG
i.defs = 0
i.use = 0
if i.op == Assign && isRegister(i.result)
i.defs = BitSet(i.result.regnum)
else
i.use |=
getUses(i.result)
i.use |= getUses(i.op1)
i.use |= getUses(i.op2)
}
getUses(Node n)
{
if n == null
return 0
use = getUses(n.op1)
use |= getUses(n.op2)
if n.op == Register
use |= BitSet(n.regnum)
return use
}
We will see in the advanced section that it is not always possible to compute
the Defs(i) and Use(i) sets, in particular for call
instructions when the destination of the call in not known.
Global Lifetime Analysis
Armed with the knowledge of which register is used and defined by each
instruction, we can now compute the liveness information.
The algorithm to compute LiveIn(i) and LiveOut(i) performs several passes
through the control flow graph, computing and propagating the liveness
information to all the other blocks until there is some entry that is changed.
When the computed sets are not changed anymore, it means that we have computed
all the needed information and we can exit the algorithm.
The algorithm works in 3 phases. The first phase computes the liveness
information for each basic block without considering how that basic block is
related to the other basic blocks:
for each b in CFG
b.use = 0
b.defs = 0
b.input = 0
b.output = 0
i = b.lastInstr
do
i.liveout = i.use
i.dead = i.defs &
~i.liveout
b.use = i.liveout | (b.use
& ~i.dead)
b.defs = i.dead | (b.defs
& ~i.liveout)
i = i.prevInstr
while i != null
end for each b
The second phase works on the information in each block by
propagating the liveness information from each block to
all the other blocks in the CFG:
do
changed = false
for each block in CFG
out = b.defs
for each succ
in block.succs
out |= succ.input
in =
block.use | (out & ~block.defs)
if in !=
block.input || out != block.output
changed = true
block.input = in
block.output = out
end for each block
while changed
The third phase adds the information collected from the other blocks
to each instruction present in each block:
for each block in CFG
live = 0
for each succ in block.succs
live |=
succ.input
i = block.lastInstr
do
newlive = i.liveout
| (live & ~i.dead)
i.liveout = live
live = newlive
i = i.prevInstr
while i != null
end for each block
After the algorithm we can use the LiveIn(i) and LiveOut(i) information in our
attempt to eliminate register references and to compress multiple instructions
into complex expressions.
|