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)