lecture-plan.txt

Lecture 1
================================================================================

Administration stuff

Compiler and course organization

Abstract syntax trees, R_0


Lecture 2: Compiling Integers, Arithmetic, and Let
================================================================================

S-Expressions

  quote

  comma

Pattern Matching

  match

Recursion

  The HTDP recipe, grammar => recursive function
  arith?

Interpreter for R_0

The R_1 Language

  let expressions, overshadowing variables
  evaluation order is left to right

The x86-64 Language

   program is a sequence of instructions, they are stored in memory
   arguments: 
     integer immediate values
     registers
     memory (map addresses to 64-bit value)
       stack and frame layout (Fig. 2.6)

   x86-64 version of
     (+ 10 32)      Fig 2.4
   and
     (+ 52 (- 10))  Fig 2.5

Compiler Correctness Diagram (p. 17)

Compiler Plan
  Differences:
  * instruction format, 2-arguments
  * nesting expressions versus simple instruction arguments
  * variables vs. registers
  * multiple variables with the same name vs. unique names
    of registers and memory locations

  Gordian Knot between instruction selection and register allocation.
  Cut by doing optimistic instruction selection.

  Plan:

  R_1
  |  uniquify
  V
  R_1
  |  flatten (emphasize this one, e.g. (+ (- 5) (- 10)) )
  V
  C_0
  |  select-instructions
  V
  x86*
  |  assign-homes
  V
  x86*
  |  patch-instructions
  V
  x86


Lecture 3: Register Allocation
================================================================================

Liveness Analysis

Build Interference Graph

Graph Coloring


Lecture 4: Register Allocation cont'd, Booleans & Control Flow
================================================================================

Review Reg. Allocation

    (let ([a 1])
      (let ([b 2])
	(let ([f b])
	  (let ([e (+ a b)])
	   (let ([d f])
	      d)))))
        

After instruction selection:

    (program (a b f e d)
      (movq (int 1) (var a))
      (movq (int 2) (var b))
      (movq (var b) (var f))
      (movq (var a) (var e))
      (addq (var b) (var e))
      (movq (var f) (var d))
      (movq (var d) (reg rax)))

Liveness analysis

    (program (a b f e d)
      (movq (int 1) (var a))	(set 'a)
      (movq (int 2) (var b))	(set 'a 'b)
      (movq (var b) (var f))	(set 'a 'b 'f)
      (movq (var a) (var e))	(set 'b 'f 'e)
      (addq (var b) (var e))	(set 'f)
      (movq (var f) (var d))	(set 'd)
      (movq (var d) (reg rax)))	(set)

Interference graph

    a---b   d
    |   |
    |   |
    f---e

    Graph coloring
    0 rbx
    1 rcx
    2 rdx

    a  0
    b  1
    f  1
    e  0
    d  0

    (program 16
      (movq (int 1) (reg rbx))
      (movq (int 42) (reg rcx))
      (movq (reg rcx) (reg rcx))   <-- delete b -> f
      (movq (reg rbx) (reg rbx))   <-- delete a --> e
      (addq (reg rcx) (reg rbx))
      (movq (reg rcx) (reg rbx))
      (movq (reg rbx) (reg rax)))


Patch Instructions

    (program 16
      (movq (int 1) (reg rbx))
      (movq (int 42) (reg rcx))
      (addq (reg rcx) (reg rbx))
      (movq (reg rcx) (reg rbx))
      (movq (reg rbx) (reg rax)))

Move Biasing

    Move Graph:

     a---e

     b---f---d

    With move biasing, we color d with 1 (rcx) to match f.

    (program 16
      (movq (int 1) (reg rbx))
      (movq (int 42) (reg rcx))
      (addq (reg rcx) (reg rbx))
      (movq (reg rcx) (reg rcx))    <--- delete f -> d
      (movq (reg rcx) (reg rax)))

    (program 16
      (movq (int 1) (reg rbx))
      (movq (int 42) (reg rcx))
      (addq (reg rcx) (reg rbx))
      (movq (reg rcx) (reg rax)))

Booleans & Control Flow

  exp ::= ... | (not exp) | (and exp exp) | (eq? exp exp) 
        | #f | #f | (if exp exp exp)
  R_2 ::= (program exp)

  interpreter R_2
    'if' expects a boolean
    'and' does short circuiting
    'eq?' works on integers and on booleans (but not mixed)

  type checking
    types classify values: Integer, Boolean
    goal: predict the type of value that an expression will produce
    goal: reject programs that will error due to type mismatches
    notice similarity between the interpreter and the type checker
    Type checking is an "abstract interpretation"

Lecture 5: Booleans & Control Flow cont'd
================================================================================

  Questions about register allocation?

  flattening from R_2 to C_1:
    arg ::= ... | #t | #f 
    exp ::= ... | (not arg) | (eq? arg arg)
    stmt ::= ... | (if arg stmt* stmt*)
    C_1 ::= (program (var*) stmt+)

    * (if exp exp exp)

    * (and exp exp)

  select-instructions

    * (assign lhs (eq? arg1 arg2))

      cmpq s1, s2
        puts the result in a special EFLAGS register
      sete d
        puts 0 or 1 into the destination based on the EFLAGS
        caveat: destination must be a byte-sized register such as 'al'
          that is part of larger register 'rax'
      movzbq s, d
        move from byte-sized register to 64-bit register
  	filling the rest with 0's
    
    * keep 'if' statements

  liveness analysis

    * What about (if cnd thn-ss els-ss)?

      * talk about conservative approximation
      * store the life-after sets for the thn and els branches
        (if cnd thn-ss thn-lives els-ss els-lives)

    * how to deal with byte-sized registers like 'al'?

  patch-instructions

    * recurse through 'if'
    * new instructions (may not require changes)

  lower-conditionals

    * more x86 instructions
      * je label
         jump to the label if the EFLAGS register is 'equal'
         otherwise fall through to the next instruction
      * jmp label
         jump to label unconditionally

    * (if cnd thn-ss els-ss)
      ==>
      (cmpq (int 0) cnd)
      (je elselabel)
      thn-ss
      (jmp endlabel)
      (label elselabel)
      els-ss
      (label endlabel)
      
  Walk through example translation from book

Lecture 6: Optimizing Control Flow
================================================================================

Redundancy in conditions:

(program
  (if (eq? (read) 1) 42 0))
⇓ flatten
(program (t.1 t.2 if.1)
  (assign t.1 (read))
  (assign t.2 (eq? t.1 1))   ←
  (if (eq? #t t.2)           ←
    ((assign if.1 42))
    ((assign if.1 0))) 
  (return if.1))

Would be better as:

(program (t.1 t.2 if.1)
  (assign t.1 (read))
  (if (eq? t.1 1)           ←
    ((assign if.1 42))
    ((assign if.1 0))) 
  (return if.1))

Our optimization should be as general as possible.  So we should try
to get good results in somewhat more complicated situations.

(program
  (if (let ([x 1])
        (not (eq? 2 x))) 
   42
   777))
⇓ 
(program (x.1 t.1 if.1)
  (assign x.1 1)
  (assign t.1 (read))
  (if (eq? x.1 t.1)
    ((assign if.1 42))
    ((assign if.1 777))) 
  (return if.1))


How should we recognize such situations and generate the code?

What pass should we change or add?

  Use a helper function inside flatten to help with 'if'.
  Recurse over the condition.

  (if cnd thn els)
     flatten thn ⇒ new-thn thn-ss
     flatten els ⇒ new-els els-ss

  flatten-if cnd new-thn thn-ss new-els els-ss
  cases:
    #t, #f
    (let ([x e]) body)
    (not ,cnd2)
    (if cnd2 thn2 els2)
	==>
	(if cnd2
	  (if thn2 thn els)
	  (if els2 thn els)
	but that would duplicate code.
	If we changed to an IR for CFGs
        L1: thn
        L2: els
        (if cnd2
          (if thn2 (jmp L1) (jmp L2))
          (if els2 (jmp L1) (jmp L2)))

	instead, let's do the simple approach:
        flatten cnd => new-cnd cnd-ss
        tmp, 
        cnd-ss
        (if (eq? #t new-cnd)
           (thn-ss (assign tmp new-thn))
           (els-ss (assign tmp new-els)))

    (and e1 e2)
      same as for 'if'


Aside: implementing 'not' is less straightforward than we thought.
Recommend using xorq.

  
Tuples, Heap Allocation, and Garbage Collection
-----------------------------------------------

Syntax:

type ::= Integer | Boolean | (Vector type+)
exp ::= ... | (vector exp+) | (vector-ref exp exp) | (vector-set! exp exp exp)
R3 ::= (program exp)

Example:

(let ([v (vector 10 #f)])
  (+ (vector-ref v 0)
     (if (vector-ref v 1)
         0
         (let ([_ (vector-set! v 0 32)])
           (vector-ref v 0)))))

Interpreter
   introduce interp-op

Talk about heap allocation

Updating the passes: (without GC)

  * type checking: straightforward
  * uniquify and flatten: nothing to do
  * select-instructions
    (assign lhs (vector es ...))
    ==>
    allocate a chunk of memory
    fill it in with es, need new kind of arg: (offset ,addr ,bytes) 

    (assign lhs (vector-ref vec i))
    ==>
    (movq (offset new-vec (* i 8)) new-lhs)

    (assign lhs (vector-set! vec i arg)
    ==>
    (movq new-arg (offset new-vec (* i 8)))

  * liveness, assign-homes, print-x86
    update to handle (offset ,addr ,bytes)


Lecture 7: Garbage Collection
================================================================================

Tuples (vectors) are represented by a pointer to a continguous chunk
of memory.

Def. A chunk is *garbage* if it is not reachable by the running
program by any path of pointer traversals.

Def. A *live* chunk is reachable by the running program by a pointer
traversal path.

A garbage collector preserves live chunks and deallocates garbage.
Thus, the program will never traverse a dangling pointer into a
deallocated chucnk.

Comment on the connection between garbage collection and type safety.

When does garbage collection happen? Typically during some calls to
the allocation routine.

Basic parts of a GC:
1. Garbage detection
2. Reclaiming garbage for reuse

Garbage detection starts at the *root set*:
* pointers on the stack
* pointers in registers

Reclaimed objects are typically put on a "free list" 
that is used for allocation.

Reference Counting
------------------
Each chunk keeps a count of how many pointers to it exist.

The count goes up and down during allocation, assignment, and
during reclamation.

When the count reaches zero, reclaim the chunk and decrement
the count for chunks pointed to by this one. This can trigger
a cascade of reclaimations, e.g., for an entire list or tree.

An *incremental* GC only does a fixed amount of work during each
allocation. This property is important for programs with timing
constraints, such as real-time systems.

Reference counting can be made entirely incremental by cutting off the
reclaimation, instead putting chunks with zero count on a to-reclaim
list.

Problems:
* cycles
* efficiency
but recent research overcomes these problems
"Taking Off the Gloves with Reference Counting Immix"
by Shahriyar et al.

Tracing GC's
------------

* Mark and Sweep
   1. Garbage detection: "mark" all reachable chunks via DFS or BFS
   2. Reclaiming garbage for reuse: "sweep" all of memory, reclaiming
      the chunks that were not marked.
   Problems:
   * fragmentation
   * cost is proportional to the size of the heap
   * bad locality of reference

* Mark-Compact
   Moves the marked objects so they are contiguous, often
     by sliding them down to the next object.
   Allocation is just a pointer bump.

* Copying Collectors
   Divide the heap into two (or more) semispaces.
   Allocation bumps a pointer in one of the spaces.
   If there is no room left, stop and copy.

   Copy all live chunks to the tospace, updating
   the pointers in them to point to the new locations.

   Cheney Algorithm:
   * Implements BFS
   * Queue stored in the tospace, between alloc pointer and
     a "scan" pointer.
   * Chunks in the queue may have stale pointers.
   * Copied objects have forwarding pointers.


Lecture: GC Q&A and Functions
================================================================================


Question:

This code is at the end of the garbage collection code in racket:

(movq (global-value free_ptr) (var t.2))
(addq (int 16) (global-value free_ptr))
(movq (int 131) (offset (var t.2) 0))

At the point where 131 is, I believe this is the tag at the front of
the array.  I've seen examples of it having 3, 131, and 160.  Is there
an explanation somewhere that I missed that tells us how to calculate
the tag in-context?