(:C L are the caching and laziness specifications, i.e.
C \in {cache, cache1, replicate, unchecked}
L \in {eager, lazy, looplazy}
Call the information computed by these rules Kconst(p) for program
point p.
keepConst() :C L: Out = In + {(x1,C,L), .. (xn,C,L)}
unkeepConst() :C L: Out = In - {(x1,C,L), .. (xn,C,L)}
other: Out = In
The "+" denotes set union, with the constraint that for each variable
x, at most one element (x,C,L) can be in any set. Making different
annotations for the same variable ((x,C,L) , (x,C',L') where (C,L) !=
(C',L')) is not allowed and flagged as an error.
At Merge M:
define S = {s | s = In(p), p a predecessor of the merge} = {s1, .. , sn}
(S is a set of sets)
Out = In(p) for some predecessor p iff |S|= 1 (i.e. all
incoming Kconst sets are identical)
otherwise:
split the CFG at M into n=|S| copies. In copy i M has
exactly those predecessors p of the original CFG for which Kconst(P) =
si, i.e those that have identical Kconst sets. Continue propagation of
keepConst annotations for these CFGs. [Guaranteed to terminate as
splitting creates a merge where all incoming Kconst sets are
identical. This will be repeated until no more merges with different
incoming Kconst sets are around.]
Example:
assume the following Kconst sets of 5 predecessors:
{x,y} {x,y,z} {x,z} {x,y} {}
S = {{}, {x,y}, {x,z}, {x,y,z}}
|S| = 4
4 copies of the CFG will be created. The duplication an be
done locally by creating |S| copies of all the merge block M and
remerging the |S| copies back into all the successor blocks of M.
{x,y} {x,y} {} {x,z} {x,y,z}
| | | | |
v v v v v
----------------------------------
M
----------------------------------
/ \
/ \
S1 S2
will be transformed to:
| | | | |
v v v v v
---------- --------
| M1 | | M2 | M3 M4
--------- edges from M3 and M4 not shown
| \_ / \
| \/ \
v / \ v
S1 <____ / \------>S2
If different sets do then merge at the successors a new splitting will
be done when visiting these successors duplicating the graph more as
necessary.
L({(x1,C1,L1), .. (xn, Cn, Ln)}) = min(L1, .. Ln) where min is the
minimum of the following order: lazy < looplazy < eager
C({(x1,C1,L1), .. (xn, Cn, Ln)}) = min(C1, .. Cn)
where min is the minimum of the following order:
replicate < cache < cache1 < unchecked
At Merge M:
Out = + In(p) \intersect RTC(M)
The intersection with the set of runtime constants at the merge point
assures that the isConst annotation is only propagated for variables
that are still runtime constants after the merge.
In the previous section we have computed annotations for dynamic merge points based on the programmer annotations for the variables. From these (dynamic) merge point annotations we compute which dynamic branches are treated lazily.
1. All dynamic merges annotated as looplazy are changed to
eager iff they are not loop head merges
lazy iff they are loop head merges
2. For each dynamic merge M annotated lazy:
compute the earliest post-dominating edges E of M and mark them
as lazy
3. For each dynamic branch D:
If any outgoing edge of D is marked lazy mark D as a lazy
otherwise as eager
When edge E post-dominates edge E' (or node p) we are sure that when
we follow edge E we are guaranteed to traverse E' (pass thru p) later.
[An vertex v' post-dominates a vertex v in a graph G iff v dominates v' in G' where G' is obtained from G by reversing the edges. The dominates-relation for edges is obtained by introducing a new vertex v12 for each edge (v1,v2) and replacing it in the graph with edges (v1,v) and (v, v2). An edge (v1,v2) dominates (v3,v4) iff in the new graph v12 dominates v34.
d1?
l/ \
d2? B1
/ \ | /
B2 B3 d3?
\ / l/ \______>
-----
M:
If M is annotated as lazy the left edge of d1 and d3 each the earliest
edges that post-dominate M and hence are annotated as lazy. d1 and d3
will be stitched lazily, d2 eagerly.
isConst(x1, .. xn:C)
KeyOut = KeyIn if C == unchecked or x \in RTC
KeyIn U {x1, .., xn} otherwise
keepConst(x1, .. xn:C) L
KeyOut = KeyIn if (C == unchecked) or C ==
replicate) or x \in RTC
KeyIn U {x1, .., xn} otherwise
unkeepConst(x1, .. xn)
KeyOut = KeyIn - {x1, .. xn}
Others:
KeyOut = KeyIn \intersect RTC
The latter rule accounts for implicit ends of isConst where a variable
loses its constancy. This preserves the invariant that at any given
point a variable can only be part of the context (cache key) if it is
also a runtime constant.
A possible optimization is to remove a variable v from the key set as
soon as
This will require to keep the DAG of derivations of rtcs to check that
{x| v => x} \intersect RTC = {} (v => x denotes that variable v was
used to derive that x is a rtc).
C(p0) = set of variables annotated as constant in the isConst() {} region annotation.
Each flow function is modified (f(ins) denotes the previously used
flow function for instruction ins):
Cflow [[ins]] cs = f(ins) U Kconst(p) i.e. the set of variables to be
kept constant at the program point are always considered constant at
point p.
isConst(x) is treated as a pseudo-instruction with the following flow
function:
Cflow [[isConst(x)]] cs = cs U {x}
Mconstant(cs1, cs2) = cs1 U cs2 if cn1 and cn2 are mutually exclusive
(static merge)
(cs1 \intersection cs2) U Kconst(p) otherwise
i.e. static merges (based on the unmodified reachability analysis) are
treated in the same way as before. For dynamic merges all inferred
constants based on variables annotated to be kept constant are
forgotten, only the variables in Kconst(p) are considered constant on
Example:
Assume the programmer has annotated keepConst(x,y)
(SSA form)
if (d) ; d dynamic condition
t1 = x * y
{x, y, t1} set of constants
else
t2 = x + y
{x, y, t2} set of constants
M:
At M the merge is a dynamic merge, hence the rule is:
({x, y, t1 } \intersect {x, y, t2}) U {x,y}
= {x, y}
For the loop unrolling example in the paper this works out as follows:
keepConst(p)
p1 = 1st
-->M: {p1,p3}
| p2 = Phi(p1,p3)
| t = (p2 != NULL)
|
| t?
| | \---------->
| |
| ...
| p3 = p2->next
| |
| |
-------
M is a non-static merge. For loop unrolling this loop head merge was
therefore marked as a constant merge to be able to derive the loop
induction variable as run time constant. Using the keepConst
annotation for variable p (the induction variable) achieves the same
effect here, by unioning in {p} at M again.
Hence, no special marking for the loop head merge as a constant merge
is necessary, it is sufficient to use keepConst on the variable "along
which" the loop is to be unrolled.
Multi-way loop unrolling is achieved in the same way by annotating the induction variable along which to unroll. Example:
pc = 0
keepConst(pc)
while (1) {
M:
op = codes[pc]
switch(op) {
case ADD:
...
pc++
break
case BRANCH:
if (testreg)
pc = codes[pc+1]
else
pc = codes[pc+2]
break
...
}
}
The keepConst(pc) annotation will keep pc constant at the merge point
M and hence in all cases of the switch, which in turn will allow
codes[pc+1] to be derived as a constant.