CSC362 2004S, Class 39: Liveness Analysis (was Register Allocation)
Admin:
* Questions on the project?
* How do we know where to start your variables after your constants? Assume slots for true and false. Start your constants at memory location 2. Globals will follow constats.
* Can we please do nested procedures? No.
* Recursive procedures? Yes.
* What do we have to do with arrays? The obvious. Permit array elemenets on the left side of assignments and as parameters. Permit array elements in expressions.
* Thursday: Lab time for class.
* Some of today's stuff is in last Friday's outline.
* Wednesday: EBA on bioinformatics at 4:15
Overview:
* Liveness Analysis
* Review
* Characteristics of key sets
* Example
* Computing key sets
* Functions and procedures
* Register allocation
* Goals
* Spilling
* Detour: NP Completeness
* A Heuristic for graph coloring
* Coalescing
* A revised heuristic
/Liveness Analysis, Reviewed/
* Determining what temporaries/variables are in use at any time in the program
* Useful for assigning large numbers of temporaries to limited number registers.
* Useful for determining whether variables are likely to be initialized before being used.
* Lets us identify unneeded statements: If we assign to a variable/temp and no longer use it afterwards, we need not do the assignment.
* Question: What is the lifespan of a variable? From the time it is defined to the time it is used.
* Claim: To analyze liveness, it helps to pay attention to the following for each "statement",s :
* in(s): The variables live immediately before s executes
* out(s): The variables live immediately after s executes
* used(s): The variables used in the computation of s
* defined(s): The variables changed in the computation of s
* succ(s): All statements that may immediately follow s in some execution of the program
* pred(s): All statements that may immediately precede s in some execution of the program
* Reflective questions:
* Why could an assembly language statement ever have more than one successor?
* Conditional jumps can jump to many different places (or, more simply, to one place or fall through to the next)
* Why could an assembly language statement ever have more than one predecessor?
* Something could be the destination of many jump statements (or of a jump and a "fall through")
/Relationships Between Sets/
for all t in succ(s)
anything in in(t) is in out(s)
in(t) is a subset of out(s)
Followup question: Can in(t) be a strict subset of out(s)? Yes. When s has multiple successors.
Given a statement s, what can we say about in(s), used(s), defined(s), and out(s)?
used(s) is a subset of in(s)
out(s) - defined(s) is a subset of in(s)
in(s) = used(s) union (out(s) - defined(s))
/Example/
USE DEF SUCC PRED IN OUT
s0: a := 0; {} {a} {s1} {?} {c,q} {c,q}
s1: b := 1; {} {b} {s2} {s0} {c,q} {b,c,q}
s2: a := b + c; {b,c} {a} {s3} {s1} {b,c,q} {a,b,q}
s3: b := a + b; {a,b} {b} {?} {s2} {a,b,q} {a,b,q}
So ... we say that we take a "minimal" in and out that meet the criteria above.
/Computing Sets, Revisited/
Observation: Needs for variables propagate backwards. Use this as the
basis of computation
Initialize:
for each statement, s, in(s) = used(s), out(s) = {}
Main work:
repeat
for each statement s,
in(s) = in(s) union out(s) - defined(s)
for each t in pred(s)
out(t) = out(t) union in(s)
until no more changes are made
/Function and Procedure Calls/
f(a,b,c) <- What is used, what is defined? It depends on the definition of f.
You need to figure that out for f and use that info.
Safest: Assume nothing is defined and everything is used.
function f(x,y,z) {
return x+y;
}
procedure f(var x: integer; y,z: integer)
begin
x := y + z;
end;
procedure f(var x: integer; y, z: integer)
begin
end;
/Goals of Register Allocation/
/Detour: NP Completeness/
/A Heuristic for Graph Coloring/
/An Example/
Can we four-color the following graph?
(A,B), (A,F), (A,G), (B,C), (B,D), (B,E), (B,K), (B,M),
(C,M), (D,J), (D,K), (D,M), (E,F), (E,J), (E,M), (F,J),
(F,M), (G,H), (G,I), (G,J), (G,K), (H,I), (H,J), (J,K),
(J,L), (L,M)