In thewhile compiler, eight different analyses have been implemented:
1. the Reaching Definitions Analysis 2. the Available Expressions Analysis 3. the Copy Analysis
4. the Very Busy Expressions Analysis 5. the Live Variable Analysis
6. the Strongly Live Variables Analysis 7. the Constant Propagation Analysis 8. the Detection of Signs Analysis
The first five analyses are instances of the Bit Vector Framework (described in Section 2.2.2), thus their transfer function is following the same pattern:
f(λ) = (λ\kill(Bl))∪gen(Bl) whereBl∈blocks(S∗)
The Strongly Live Variables is just an instance of the Distributive Framework, while the last two analysis are only instances of the Monotone Framework.
In the remainder of this section all the parameters of the lattices specifying these eight different analyses will be described.
3.3.1 Reaching Definitions Analysis
The first analysis is the Reaching Definitions analysis. The aim of this analy-sis is to determine for each program point, which assignments may have been made and not overwritten, when program execution reaches this point along some path. In summary, the analysis gives, at each program block entry or exit, for each variable occurring in the program, the (smallest possible) set of labels where the variablemay have obtained its value. The special token ? is used to indicate that the variable may have obtained its value outside the program.
The Reaching Definitions analysis is a forward, over-approximation analysis.
As an instance of the Bit Vector Framework, the parameters of the lattice are:
• P(Var∗ ×(Lab?∗)), the lattice of variables and labels, indicating where a variable is last defined
• a partial ordering⊆and least upper bound operationSthat since it is a may-analysis
• ∅, the least element of the lattice ⊥
• {(x,?)|x∈F V(S∗)}, the extremal valueι of the analysis
• {init(S∗)}, the extremal labelsE
• f low(S∗), the definition of the flowF through the program
• the transition functionf of the Bit Vector Framework
Finally, we need to define the kill and gen functions used in the transition functionfl:
killRD([x:=a]l) = {(x,?)} ∪ {(x, l0)|Bl0 is an assignment toxinS∗} killRD([readx]l) = {(x,?)} ∪ {(x, l0)|Bl0 is an assignment toxinS∗} genRD([x:=a]l) = {(x, l)}
genRD([readx]l) = {(x, l)}
killRD(Bl) = genRD(Bl) = ∅ otherwise
Consider the following program:
[x:=a+b]1; [y:=a*b]2;while [y>a+b]3 do [a:=a+1]4; [x:=a+b]5 od
Figure 3.4: Example program 1
Thanks to the framework defined above, the Reaching Definitions solutions can be computed for the program in Figure3.4:
l RDentry(l) RDexit(l)
1 {(x,?),(y,?),(a,?)} {(x,1),(y,?),(a,?)}
2 {(x,1),(y,?),(a,?)} {(x,1),(y,2),(a,?)}
3 {(x,1),(x,5),(y,2),(a,?),(a,4)} {(x,1),(x,5),(y,2),(a,?),(a,4)}
4 {(x,1),(x,5),(y,2),(a,?),(a,4)} {(x,1),(x,5),(y,2),(a,4)}
5 {(x,1),(x,5),(y,2),(a,4)} {(x,5),(y,2),(a,4)}
3.3.2 Use-Definition and Definition-Use chains
Before looking at other analysis, it is interesting to define two functions, called the Use-Definition chain (often abbreviated ud-chain) and theDefinition-Use chain (abbreviated du-chain). The Use-Definition chain links each use of a vari-able to the different assignments that could have define it, while the Definition-Use chain links an assignment defining a variable to all the potential uses of this
variable.
It is possible to obtain the ud-chain from the results of the Reaching Defini-tions Analysis described in the previous section (RD◦(l) is an abbreviation for RDentry(l)):
UD :Var* ×Lab*→ P(Lab*)
U D(x, l) =
{l0|(x, l0)∈RD◦(l) ifx∈used(Bl)
∅ otherwise
with
used([x:=a]l) =F V(a), used([b]l) =F V(b) used([read x]l) = used([skip]l) = ∅
and FV: AExp→ Var* is a function returning the set of variables occurring in an arithmetic expression.
The du-chain can be computed directly from the ud-chain:
DU :Var*×Lab* → P(Lab*) DU(x, l) ={l0|l∈U D(x, l0)}
3.3.3 Available Expressions Analysis
The aim of the Available Expressions Analysis is to determine for each program point, which expressionsmust have already been computed, and not later mod-ified, on all paths to the program point.
The Available Expressions Analysis is a forward, under-approximation anal-ysis which is an instance of the Bit Vector Framework. The parameters for the lattice are:
• P(AExp*), the lattice of all non-trivial arithmetic expressions occurring in the program
• a partial ordering⊇and least upper bound operationTthat since this is amust-analysis
• AExp*, the least element of the lattice⊥
• ∅, the extremal valueι of the analysis
• {init(S∗)}, the extremal labelsE
• f low(S∗), the definition of the flowF through the program
• the transition functionf of the Bit Vector Framework
We also need the definitions of thekill andgen functions used in the transition functionfl:
killAE([x:=a]l) = {a0 ∈AExp*|x∈F V(a0)}
killAE([readx]l) = {a0 ∈AExp*|x∈F V(a0)}
killAE([b]l) = ∅ killAE([skip]l) = ∅
genAE([x:=a]l) = {a0 ∈AExp(a)|x /∈F V(a0)}
genAE([b]l) = AExp(b) genAE([readx]l) = ∅
genAE([skip]l) = ∅
For example, it is possible to compute the Available Expressions Analysis solu-tions for the program in Figure3.4:
l AEentry(l) AEexit(l)
1 ∅ {a+b}
2 {a+b} {a+b,a*b}
3 {a+b} {a+b}
4 {a+b} ∅
5 ∅ {a+b}
3.3.4 Very Busy Expressions Analysis
An expression isvery busy at the exit from a label if, no matter what path is taken from the label, the expression is always used before any of the variables occurring in it are redefined.
The aim of the Very Busy Expressions Analysis is to determine, for each pro-gram point, which expressions must bevery busy at the exit from the point.
The Very Busy Expressions Analysis is a backward, under-approximation analy-sis, and an instance of the Bit Vector Framework. The parameters of the lattice are:
• P(AExp*), the lattice of all non-trivial arithmetic expressions occurring in the program
• a partial ordering⊇and least upper bound operationTthat since this is amust-analysis
• AExp*, the least element of the lattice ⊥
• ∅, the extremal valueι of the analysis
• f inal(S∗), the extremal labelsE
• f lowR(S∗), the definition of the flowF through the program
• the transition functionf of the Bit Vector Framework
The definitions of thekill and gen functions are:
killV B([x:=a]l) = {a0∈AExp*|x∈F V(a0)}
killV B([readx]l) = {a0∈AExp*|x∈F V(a0)}
killV B([b]l) = ∅ killV B([skip]l) = ∅
genV B([x:=a]l) = AExp(a) genV B([b]l) = AExp(b) genV B([readx]l) = ∅
genV B([skip]l) = ∅
For example, it is possible to compute the Available Expressions Analysis solu-tions for the program in Figure3.4:
l VBentry(l) VBexit(l) 1 {a+b,a*b} {a+b,a*b}
2 {a+b,a*b} {a+b}
3 {a+b} ∅
4 {a+1} {a+b}
5 {a+b} {a+b}
3.3.5 Copy Analysis
The aim of the Copy Analysis is to determine for each program point, which copy statements [x:=y]l still are relevant i.e., neither x nor y have been rede-fined, when control reaches that point.
The Copy Analysis is a forward, under-approximation analysis and an instance of the Bit Vector Framework. The parameters for the lattice are:
• P(Var∗ × Var∗), the lattice of all pairs of variables occurring in the program
• a partial ordering⊇and least upper bound operationT that since this is a must-analysis
• Var∗ ×Var∗, the least element of the lattice⊥
• ∅, the extremal valueι of the analysis
• {init(S∗)}, the extremal labelsE
• f low(S∗), the definition of the flowF through the program
• the transition functionf of the Bit Vector Framework
The definitions of the kill andgen functions used in the transition functionfl are:
killCA([x:=a]l) = {(x, y)|y∈F V(S∗)} ∪ {(y, x)|y∈F V(S∗)}
killCA([readx]l) = {(x, y)|y∈F V(S∗)} ∪ {(y, x)|y∈F V(S∗)}
genCA([x:=a]l) = {(x, y)|a=y∧y∈F V(S∗)}
killCA(Bl) = genCA(Bl) = ∅ otherwise
Consider another example program:
[x:=1]1; [y:=x]2; [z:=y*(-y)]3;write [y]4; [y:=10]5 Figure 3.5: Example program 2
Thanks to the framework defined above, the Copy Analysis solutions can be computed for the program in Figure3.5:
l CAentry(l) CAexit(l)
1 ∅ ∅
2 ∅ {(x,y)}
3 {(x,y)} {(x,y)}
4 {(x,y)} {(x,y)}
5 {(x,y)} ∅
3.3.6 Live Variables Analysis
A variable is live at the exit from a label if there is a path from the label to a use of the variable that does not re-define the variable. The aim of the Live Variables Analysis is to determine for each program point, which variables may be live at the exit from the point. In practice, we are interested in variables that are not live at the exit from a program point.
The Live Variables Analysis is a backward, over-approximation analysis and an instance of the Bit Vector Framework. The parameters for the lattice are:
• P(Var*), the lattice of all variables occurring in the program
• a partial ordering⊆and least upper bound operationSthat since this is amay-analysis
• ∅, the least element of the lattice ⊥
• ∅, the extremal valueι of the analysis
• f inal(S∗), the extremal labelsE
• f lowR(S∗), the definition of the flowF through the program
• the transition functionf of the Bit Vector Framework
The definitions of the kill andgen functions used in the transition functionfl
are:
killLV([x:=a]l) = {x}
killLV([read x]l) = {x}
killLV([b]l) = killLV([skip]l) = ∅
genLV([x:=a]l) = F V(a) genLV([b]l) = F V(b) genLV([readx]l) = ∅
genLV([skip]l) = ∅
For example, it is possible to compute the Live Variables Analysis solutions for the program in Figure3.5: 1 even though its only use is to calculate a new value for a variable that turns out to bedead.
A variable is defined as afaint variable if it isdead or if it is only used to calcu-late new values forfaint variables; otherwise it isstrongly live. In the example xisfaint at the exit from 1.
The aim of the Strongly Live Variables Analysis is to determine which variables may bestrongly liveat the exit from a point. In practice, we are more interested in thefaint variables which can be eliminated.
The Strongly Live Variables Analysis isnot an instance of the Bit Vector Frame-work, but only of the Distributive Framework. All the parameters of the lattice are the same as the ones of the Live Variable Analysis, except the transition functionf. Hence, we have to give its data flow equations:
SLVentry(l) =
(SLVexit(l)\killLV(Bl))∪genLV(Bl) ifkillLV(Bl)⊆SLVexit(l)
SLVexit(l) otherwise
SLVexit(l) = [
SLVentry(l0|(l0, l)∈f lowR(S∗))
We can underline the fact that thekill andgen functions are also the same as those of the Live Variables Analysis
3.3.8 Constant Propagation Analysis
Another analysis which does not belong to the Bit Vector Framework is the Constant Propagation Analysis. The aim of this analysis is to determine, for each program point, whether or not a variable has a constant value whenever the execution reaches that point. This analysis then gives, for each program point, a mapping between the variables and the corresponding information i.e, whether or not the value of the variable is constant, and if so what is the value.
We can see here the complete lattice used for the Constant Propagation Analysis, which is a forward analysis and an instance of the Monotone Framework, though not of the Distributive Framework:
• State\CP = (Var* →Z>)⊥, the lattice which maps variables to values, where >is used to indicate that a variable is not constant and ⊥when we have no information at all.
• λx.>, the extremal valueιof the analysis
• {init(S∗)}, the extremal labelsE
• f low(S∗), the definition of the flowF through the program
• a special partial orderingvdefined by:
∀bσ∈(Var*→Z>)⊥ : ⊥vbσ
∀bσ1,σb2∈Var*→Z> : σb1vbσ2 iff∀x:bσ1(x)vσb2(x) using the partial ordering define onZ>=Z∪ {>}:
∀z∈Z> : zv >
∀z1, z2∈Z : (z1vz2)⇔(z1=z2)
• a least upper bound operation tdefined by:
∀bσ∈(Var*→Z>)⊥ : bσt ⊥=bσ=⊥ tbσ
∀σb1,σb2∈Var*→Z> : ∀x: (σb1tbσ2)(x) =bσ1(x)tσb2(x)
• a special transfer functionflCP defined by:
[x:=a]l: flCP(bσ) =
This transfer function uses the auxiliary function ACP defined below:
ACP(x)
where opda is a function that performs a specific operation on the values given as inputs and compute the result ; if one of the operand is⊥or>, the value returned is>.
It is now possible to compute the Constant Propagation Analysis solutions for the program in Figure3.5:
3.3.9 Detection of Signs Analysis
The last analysis, which does also not belong to the Bit Vector Framework is the Detection of Signs Analysis. The aim of this analysis is to decide whether a variable at a given program point will have a negative value, a positive value, be zero, or combinations of these. The analysis must specify all the signs that a variables might have.
The Detection of Signs Analysis is a forward over-approximation analysis, and an instance of the Monotone Framework:
• State\DS = (Var* →Sign), the lattice which maps variables to a set of signsSign =P({-, 0, +}).
• λx.{−,0,+}, the extremal valueι of the analysis
• {init(S∗)}, the extremal labelsE
• f low(S∗), the definition of the flowF through the program
• a special partial orderingvdefined by:
∀bσ1,σb2∈Var*→Z> : σb1vbσ2 iff∀x:bσ1(x)⊆σb2(x)
• a least upper bound operationtdefined by:
∀σb1,σb2∈Var*→Z> : ∀x: (σb1tσb2)(x) =σb1(x)∪σb2(x)
• a special transfer functionflDS defined by:
[x:=a]l: flDS(σ) =b bσ[x7→ADS(a)
bσ] [reada]l: flDS(σ) =b bσ[x7→ {−,0,+}]
[skip]l: flDS(σ) =b bσ [b]l: flDS(σ) =b bσ
This transfer function uses the auxiliary functionADS defined below:
ADS(x)
where opda : Sign ×Sign → Sign is a function that performs a specific operation on the signs given as inputs and returns the corresponding re-sults ,e.g ifb∗, if{+} and{-} are given as inputs, it will return {-}; if{0, +}and {-}are given as inputs, it will return {-, 0}; etc...
Here are the solutions for the Detection of Signs Analysis, for the program in Figure3.5:
l DOSentry(l) DOSexit(l)
1 {x7→ S−,0,+,y7→ S−,0,+,z7→ S−,0,+,} {x7→ S+,y7→ S−,0,+,z7→ S−,0,+,} 2 {x7→ S+,y7→ S−,0,+,z7→ S−,0,+,} {x7→ S+,y7→ S+,z7→ S−,0,+,} 3 {x7→ S+,y7→ S+,z7→ S−,0,+,} {x7→ S+,y7→ S+,z7→ S−,} 4 {x7→ S+,y7→ S+,z7→ S−,} {x7→ S+,y7→ S+,z7→ S−,} 5 {x7→ S+,y7→ S+,z7→ S−,} {x7→ S+,y7→ S+,z7→ S−,}
whereS−,0,+={−,0,+}, S+={+}, etc...