Loop invariant operations
for (i = 0; i < n; i++) {
A[i] = m + n;
}
to (loop invariant code motion)
t = m + n;
for (i = 0; i < n; i++) {
A[i] = t;
}
Partial Redundancy Elimination (aka lazy code motion)
Subsumes
The idea is that there should be no redundant computation on any path --- this includes paths that include multiple loop iterations. Notice that CSE can be thought of as "redundancy elimination" (without "partial") because we remove redundancy only if it was present on all paths. The consideration of paths that include loop iterations provides LICM for free.
┌───────┐
│ BB1 │
└───┬───┘
┌───┴───┐
▼ ▼
┌───────┐ ┌───────┐
│ BB2 │ │ BB3 │
│a=b+c │ │b=7 │
└───┬───┘ └───┬───┘
│ │
└───┬─────┘
▼
┌───────────┐
│ BB4 │
│ d=b+c │
└───────────┘
can be changed to
BB1->BB2
BB1->BB3
BB2->BB4
BB3->BB4
BB2: t = b + c
a = t
BB3: b = 7
t = b + c
BB3: d = t
┌───────┐
│ BB1 │
└───┬───┘
┌───┴───┐
▼ ▼
┌───────┐ ┌───────┐
│ BB2 │ │ BB3 │
│t=b+c │ │b=7 │
│a=t │ │t=b+c │
└───┬───┘ └───┬───┘
│ │
└───┬─────┘
▼
┌───────────┐
│ BB4 │
│ d=t │
└───────────┘
Can we place calculations of b+c such that no path re-executes the same expression? Algorithm based on PLDI92 paper by Knoop et. al. on "Lazy code motion"
┌───────┐
│ BB1 │
│c = a+b│
└───┬───┘
┌──────────┴───────────────┐
│ │
│ ▼
│ ┌───────┐
│ │ BB2 │
│ │ a=10 │
│ └───┬───┘
│ ┌─────────────────────┴───┐
│ │ ▼
│ │ exit
▼ ▼
┌───────┐
│ BB3 │
│d = a+b│
└───────┘
We cannot move a+b to BB2 (or we add redundant computation on the exit path), and cannot keep it at BB3 (as it is redundant on BB1->BB3 path). We need to add a new basic block.
┌───────┐
│ BB1 │
│t = a+b│
│c = t │
└───┬───┘
┌──────────┴───────────────┐
│ │
│ ▼
│ ┌───────┐
│ │ BB2 │
│ │ a=10 │
│ └───┬───┘
│ ┌───────┐ │
│ ┌───│newBB │─────────┴───┐
│ │ │t=a+b │ ▼
│ │ └───────┘ exit
│ │
▼ ▼
┌───────┐
│ BB3 │
│d = t │
└───────┘
Algorithm Prelims:
Algorithm Overview:
Example1:
┌───────────────┐
│ BB1 │
│ (entry) │
└───────┬───────┘
┌─────────┼─────────┐
│ │ │
▼ ▼ ▼
┌────────┐ ┌────────┐ ┌────────┐
│ BB2 │ │ BB3 │ │ BB4 │
│x=a+b │ │ │ │a = 10 │
└───┬────┘ └───┬────┘ └───┬────┘
│ │ │
│ │ ▼
│ │ ┌────────┐
│ │ │ BB6 │
│ │ │z=a+b │
│ │ └────────┘
│ │
└────┬─────┘
▼
┌────────┐
│ BB5 │
│y=a+b │
└────────┘
change to
┌───────────────┐
│ BB1 │
│ (entry) │
└───────┬───────┘
┌─────────┼─────────┐
│ │ │
▼ ▼ ▼
┌────────┐ ┌────────┐ ┌────────┐
│ BB2 │ │ BB3 │ │ BB4 │
│x=a+b │ │t=a+b │ │a = 10 │
└───┬────┘ └───┬────┘ └───┬────┘
│ │ │
│ │ ▼
│ │ ┌────────┐
│ │ │ BB6 │
│ │ │t=a+b │
│ │ │z=t │
│ │ └────────┘
│ │
└────┬─────┘
▼
┌────────┐
│ BB5 │
│y=t │
└────────┘
Notice that we put t = a+b where a+b is "needed", i.e., it is needed on all paths in future.
Also, note that for now, we are adding copies even when they were not necessarily required, e.g., z=t, we
will clean up later.
Example 2
┌───────────┐
│ BB1 │
│ (entry) │
└─────┬─────┘
│
▼
┌───────────┐
┌──►│ BB2 │
│ │ x = a + b │
│ └─────┬─────┘
│ │
│ ▼
│ ┌───────────┐
└───│ BB3 │
└─────┬─────┘
│
▼
┌────┐
│BB4 │
└────┘
change to
┌───────────┐
│ BB1 │
│ t = a + b │
└─────┬─────┘
│
▼
┌───────────┐
┌──►│ BB2 │
│ │ x = t │
│ └─────┬─────┘
│ │
│ ▼
│ ┌───────────┐
└───│ BB3 │
└─────┬─────┘
│
▼
┌────┐
│BB4 │
└────┘
Again, t=a+b is "needed" on all paths in future
Example 3
┌─────────┐
│ BB1 │
│ x = a+b │
└────┬────┘
│
▼
┌─────────┐
│ BB2 │
└────┬────┘
│
▼
┌─────────┐
┌─►│ BB3 │
│ └────┬────┘
│ │
│ ▼
│ ┌─────────┐
│ │ BB4 │
│ │ y=a+b │
│ └───┬─┬───┘
│ │ │
│ │ └──────┐
│ ▼ ▼
│ ┌────┐ ┌─────────┐
│ │BB5 │ │ BB6 │
│ └─┬──┘ │ a = 10 │
│ │ └────┬────┘
│ │ │
└─────┴─────────┘
to BB3
change to
┌─────────┐
│ BB1 │
│ t = a+b │
│ x = t │
└────┬────┘
│
▼
┌─────────┐
│ BB2 │
└────┬────┘
│
▼
┌─────────┐
┌─────►┌─►│ BB3 │
│ │ └────┬────┘
│ │ │
│ │ ▼
│ │ ┌─────────┐
│ │ │ BB4 │
│ │ │ y=t │
│ │ └───┬─┬───┘
│ │ │ │
│ │ │ └──────┐
│ │ ▼ ▼
│ │ ┌────┐ ┌─────────┐
│ │ │BB5 │ │ BB6 │
│ │ └─┬──┘ │ a = 10 │
│ │ │ └────┬────┘
│ │ │ │
│ └───────┘ │
│ ┌───────┐ │
└────────│ newBB │───────┘
│ t=a+b │
└───────┘
Example 4 (not all redundancy can be eliminated)
┌─────────┐
│ BB1 │
│ x = a+b │
└────┬────┘
│
▼
┌─────────┐
│ BB2 │
└────┬────┘
│
▼
┌─────────┐ ┌───────────┐
┌─►│ BB3 │───────────►│ BB6 │
│ └────┬────┘ │ a = 10 │
│ │ └┬─────┬────┘
│ ▼ │ │
│ ┌─────────┐ │ ▼
│ │ BB4 │ │ ┌──────┐
│ └────┬────┘ │ │ exit │
│ │ │ └──────┘
│ ▼ │
│ ┌─────────┐ │
│ │ BB5 │ │
│ │ y = a+b │ │
│ └────┬────┘ │
│ │ │
└───────┘──────────────────┘
change to
┌─────────┐
│ BB1 │
│ t = a+b │
│ x = t │
└────┬────┘
│
▼
┌─────────┐
│ BB2 │
└────┬────┘
│
▼
┌─────────┐ ┌───────────┐
┌─►│ BB3 │───────────►│ BB6 │
│ └────┬────┘ │ a = 10 │
│ │ └┬─────┬────┘
│ ▼ │ │
│ ┌─────────┐ │ ▼
│ │ BB4 │ │ ┌──────┐
│ └────┬────┘ │ │ exit │
│ │ │ └──────┘
│ ▼ ▼
│ ┌─────────┐ ┌─────────┐
│ │ BB5 │ │ newBB │
│ │ y = t │ │ t = a+b │
│ └────┬────┘ └────┬────┘
│ │ │
└───────┘──────────────────┘
There is some redundancy in the transformed code which is unavoidable. Notice that the path from newBB->BB3->BB6->exit computes a+b even though it was not required.
The other option is (which our algorithm will produce):
┌─────────┐
│ BB1 │
│ t = a+b │
│ x = t │
└────┬────┘
│
▼
┌─────────┐
│ BB2 │
└────┬────┘
│
▼
┌─────────┐ ┌───────────┐
┌─►│ BB3 │───────────►│ BB6 │
│ └────┬────┘ │ a = 10 │
│ │ └┬─────┬────┘
│ ▼ │ │
│ ┌─────────┐ │ ▼
│ │ BB4 │ │ ┌──────┐
│ └────┬────┘ │ │ exit │
│ │ │ └──────┘
│ ▼ │
│ ┌─────────┐ │
│ │ BB5 │ │
│ │ t = a+b │ │
│ │ y = t │ │
│ └────┬────┘ │
│ │ │
└───────┘──────────────────┘
This avoids redundancy on the BB6->BB3->BB6->exit path, but now a+b is computed twice on the path B2->B3->B4->B5 (this is the solution that our analysis will yield).
Which expressions are needed (i.e., are required to be available) on all outgoing paths?
Data-flow analysis
{a+b} for x=a+b). Ekill is the set of expressions killed by this expression, e.g., all expressions containing x are killed by x=a+b.Proposal 1:
Example 5
┌─────────┐
│ BB1 │
│ x = a+b │
└────┬────┘
│
▼
┌─────────┐
│ BB2 │
└────┬────┘
│
▼
┌─────────┐
│ BB3 │
└───┬─┬───┘
│ │
yes │ │ no
│ └─────────┐
▼ ▼
┌─────────┐ ┌──────┐
│ BB4 │ │ exit │
│ y = a+b │ └──────┘
└─────────┘
Now, a+b is needed at BB4 entry but not needed at BB3 exit. Yet computing t=a+b on the edge BB3->BB4 is redundant because the expression a+b is already available (or not missing) at BB4.
p if its value has not been "computed" by any basic block along SOME path reaching p. Will solve the redundancy problem with the first example.
Is it true that the missing expressions analysis is the complement of the available expressions analysis? i.e., missing = all - available?
Place the expression at the earliest point we need it and is missing
x+y \in earliest[b], at beginning of b, create a new variable t, such that t=x+y, and replace every original x+y by t.t. The temporary's "live range" (or the number of basic blocks in which it is live) is thus artificially inflated. We would like to ensure that the live range is as small as possible, so that the interference with other pseudo-registers is minimized (e.g., fewer edges in the register-interference graph. See examples 6 and 7 below.Some examples where Proposal 2 will cause register pressure:
Example 6
┌─────────┐
│ BB1 │
└───┬─┬─┬─┘
│ │ │
┌───────┘ │ └───────┐
▼ ▼ ▼
┌────────┐ ┌────────┐ ┌────────┐
│ BB2 │ │ BB3 │ │ BB4 │
└───┬────┘ └───┬────┘ │ a = 10 │
│ │ └────────┘
│ │
└────┬─────┘
▼
┌─────────┐
│ BB5 │
│ y = a+b │
└─────────┘
Here, the frontier occurs at the end of BB1 but that is too early to compute t=a+b as we will take up an extra register for a long time unnecessarily!
Example 7 (a more convincing example of why you should not compute a value too early)
┌─────────┐
│ BB1 │
└────┬─┬──┘
│ │
┌────┘ └────┐
▼ ▼
┌────────┐ ┌────────┐
│ BB2 │ │ BB3 │
└───┬────┘ │a = b+c │
│ └───┬────┘
▼ │
┌────────┐ ▼
┌─►│ BB4 │ ┌────────┐
│ └──┬──┬──┘ │ BB7 │
│ │ │ └───┬────┘
│ │ │ │
│ │ └──► BB5 ──┘
│ │ │
│ │ ▼
└─────┘ ┌─────────┐
│ BB6 │
│ y = b+c │
└─────────┘
The frontier is at the beginning of BB1 but that would eat-up a register for the entire duration of the BB2-BB4 loop which seems too wasteful.
Example 8 (another convincing example of why you should not compute a value too early)
┌───────────┐
│ BB1 │
│ │
└─────┬─────┘
│
▼
┌───────────┐
┌──►│ BB2 │
│ │ │
│ └─────┬─────┘
│ │
│ ▼
│ ┌───────────┐
└───│ BB3 │
└─────┬─────┘
▼
┌───────────┐
│ BB4 │
└─────┬─────┘
▼
┌───────────┐
┌──►│ BB5 │
│ │ x = a+b │
│ └─────┬─────┘
│ │
│ ▼
│ ┌───────────┐
└───│ BB6 │
└─────┬─────┘
│
▼
┌────┐
│BB7 │
└────┘
The frontier (needed and missing) is at the beginning of BB1 but that would eat-up a register for the entire duration of the BB2-BB4 loop which seems too wasteful.
e is postponed at a program point p if:
p, we have "computed" e but not used it subsequently.p, we have seen the earliest placement of e but not a subsequent use.
┌─────────┐
│ BB1 │
└────┬─┬──┘
│ │
┌────┘ └────┐
▼ ▼
┌────────┐ ┌────────┐
│ BB2 │ │ BB3 │
└───┬────┘ │a = b+c │
│ └───┬────┘
▼ │
┌────────┐ ▼
┌─►│ BB4 │ ┌────────┐
│ └──┬──┬──┘ │ BB7 │
│ │ │ └───┬────┘
│ │ │ │
│ │ └──► BB5 ──┘
│ │ │
│ │ ▼
└─────┘ ┌─────────┐
│ BB6 │
│ y = b+c │
└─────────┘
Here, b+c is postponed at the beginning of BB3 and on the edge BB5->BB6.
latest[b] = (earliest[b] \union postponed.in[b]) \intersection (EUse \union ExprsForWhichSomeSuccessorIsNotPostponedOrEarliest)Consider example 8:
┌───────────┐
│ BB1 │
│ │
└─────┬─────┘
│
▼
┌───────────┐
┌──►│ BB2 │
│ │ │
│ └─────┬─────┘
│ │
│ ▼
│ ┌───────────┐
└───│ BB3 │
└─────┬─────┘
▼
┌───────────┐
│ BB4 │
│ t = a + b │
└─────┬─────┘
▼
┌───────────┐
┌──►│ BB5 │
│ │ x = t │ # notice that (a+b) is not postponed here, loop paths like BB1->2->3->4->5->6 use the expression (after computing it at earliest)
│ └─────┬─────┘
│ │
│ ▼
│ ┌───────────┐
└───│ BB6 │
└─────┬─────┘
│
▼
┌────┐
│BB7 │
└────┘
┌─────────┐
│ BB1 │
│ x = a+b │
└────┬────┘
│
▼
┌─────────┐
│ BB2 │
└────┬────┘
│
▼
┌─────────┐
│ BB3 │
└─────────┘
No need to generate temporaries in this case. But our algorithm will. Do a liveness analysis to see
if the expression is used later (without an intervening latest as a latest indicates
recomputation).
x+y \in (latest[b] \intersect used.out[b]):
b: add new t=x+yx+y by t only if:
x+y \in (EUse \intersect \not(latest[b] \insersect \not(used.out[b])))latest[b] and not in used.out[b], this use of the expression does not need to be (and has not been) replaced by t, so let it be as it is.