CSC362 2004S, Class 38: Miscellaneous (was Liveness Analysis)

Admin
* I am so very glad that Davis and Cassie and Paul and Nate and that skateboard guy and Oge and John and Daniel and Anantaand Shihan and Patricia and Arjun and a slightly late Ben made it to class
* Free pizza!
* Picnic moved
  * Who will move tables?
* Questions on the project
  * Yes, you need to build a new PAL object for each instruction.
* Questions on the final
  * What format?  Open book, Open computer; Both theory and practice
  * How do we prepare?  Talk to your group about common "hard problems"; Reread or read the book; Pretend you are only allowed to bring one page of notes; Come to the review session
  * Can the seniors take it early so that they may celebrate being seniors for a longer period of time?  Yes
  * Do you intend to pass all of the seniors, even if they don't deserve to pass because they walk out on convo?  Yes
  * Is that fair?  Define fair
  * Will you grade the final?  I intend to.  However, the best laid schemes of mice and men gang aft aglay and lea' us not but grief and pain for promised joy.
  
* Jokes about yesterday's convo

Overview:
* Background: Difference between PAL and "real" assembly language
* Context: Why consider liveness.
* The basics of liveness analysis.
* Some theoretical issues .
* Some practical issues.
* Some examples.

What would we have to worry about as we translated from PAL to "real" assembly language
* In PAL, there are an arbitrarily large number of "temporaries"; In real machines, there are a fixed number of registers
* In real machines, addresses are usually of bytes, in PAL, we deal with "cells" which hold an integer
* PAL builds trees of instructions sequences, regular assembly has a single instruction sequence
* Stack and heap size limits are going to be different (and accessed in different ways)
* Read and Write are going to have to be translated to a long sequence of instructions (or, more likely, a subroutine)
* If we are dealing with language interoperatiblity, we need to use the standard stack frame
* PAL instructions are very general: Usually you are limited in how you address memory and how many parameters

From temporaries to registers
* Attempt to map each temporary to a register
* When is it "safe" to put two temporaries in one register?  If they're not "in scope" (live) at the same time
* Build a graph.  Each temporary corresponds to a node in the graph.  There is an edge between two nodes if the corresponding temporaries are "alive" at the same time.  Could solve as a partitioning problem.  Could solve as graph coloring (or minimal graph coloring).  

Observation: In order to convert register allocation to graph coloring, we need to know about lifetimes of variables
* New problem: How to compute lifetimes
  * useful for graph coloring
  * useful for optimization
	a := b + c
	{ a no longer used }
	ADD b c -> a
	{ a no longer used }
  	MOV location-of-result TMP # as result of translation printf(x)
* Applicable at many levels
  * Individual statements in high level langauge
  * Individual statements in low level langauge
  * Blocks of statements

* Strategy: Look at characteristics of statements:
  * used(s) : The set of variables used in the statement
  * defined(s) : The set of variables defined in the statement
  * in(s) : The set of variables alive before s
  * out(s) : The set of variables alive after s