Work Note 7, DM546, Spring 2013

Lecture February 21

• Liveness analysis and register allocation.

Supplementary literature: A note on lattices and fixed points (not part of the curriculum).

Exercises February 27

• Consider code generation templates for the following constructions:
  • for-loops (old Algol/Pascal style): for i:=7 to 42 do SOMETHING.
  • for-loops (C style).
  • loops with break/continue. The loop is as a starting point infinite and starts with the keyword loop without any condition. Inside the body of the loop, break exits the loop and continue starts from the beginning. For both break and continue, this is independent of where in the loop code you are.
  • switch (C) and case (Pascal) constructions.
  • records.
  • arrays.
  • multi-dimensionel arrays; this is different from arrays of arrays. You must find a layout such that you can efficiently compute the address of A[i,j,k], for instance. Thus, it must be different from following three pointers as you would logically do if you used A[i][j][k].
  • conditional expressions in C style: ( exp ? exp : exp ).
• What is the semantics of i:= 7; for i:=i+1 to i+2 do {i:=i+3; print i} according to your template above, i.e., what is printed? What are the reasonable behaviors?
• What should be the behavior of the following three pieces of C-code:
  • x = 3; r = x++ * x++ * x++;
  • x = 3; r = ++x * ++x * ++x;
  • y = 0; r = y++ + 2*y++ + 3*y++ + 4*y++;
  Try it! You might be surprised...
• Are there efficiency reasons to restrict switch/case expressions to be simple types and only use values from a small domain?
• Some programming languages offer lists with random access (A[i]), append (A.append(42)), and insert (A.insert(pos,val)) which inserts val in between the positions pos and pos+1. Can this be implemented efficiently?
• Consider constructions which are typically allocated in the heap, e.g., C structs. How can they give rise to (enormous) vaste of space? How is it possible in principle to check if allocated space is still used and thereby "collect" unused space for reuse?