add notes

I start to believe that it is possible to simply
reuse the regalloc I wrote.  All the data structures
seem fine.

Here is a list modifications to make for sure:
 - Keep track of the mapping for live in variables
   for each block.
 - Make sure 'loc' (or a new function) returns
   registers for the arguments of base instructions.

Spilling
--------

When we need a register and none are left.  If we
are at the end of a block, simply spill anybody (the
resolving will take care of adding the moves).  If we
are in a block, find somebody to spill and its next
use, if the next use is in the same block, emit reload
code, otherwise, decide to emit the reload at the
end of the cheapest block (this means that we have to
patch some mappings that were already stored).  We let
the resolve handle the insertion of the reload code.

Example:

  +----------------------+
  |                      |
  |                      |
  |   +----+     +----+  |   +----+
 -+-> | b1 | --> | b2 | -+-> | b3 | -->
      +----+     +----+      +----+
        ^                       ^
        Spill x                 First use of x
        (Was in r1)

The cheapest position for reload code is at the
beginning of b3, so we have to modify the mapping
at the end of b1, beginning of b2, and end of b2 to
change it from (x -> r1) to (x -> spill).

Reloading
---------

When a spilled variable is needed in register.  In this
case, we are necessarily inside a block (or at a branch)
because that is the only place we require a variable to
be in register.  Here again we are constrained to insert
the spill code before the next use of the variable, but
more importantly, we must do it before the register
chosen is *in use next*.

1 files changed, 57 insertions, 7 deletions

diff --git a/lo2.ml b/lo2.ml
index 1f8d75a..d96359f 100644
--- a/lo2.ml
+++ b/lo2.ml
@@ -260,8 +260,8 @@ let ircmp a b =
   | IRIns (_,x), IRIns (_,y) -> compare x y
 
 (* An interval specifies a region of the program text (usually where
- * a variable is live. It has two bounds, lo and hi, they are both
- * inclusive.  (We cannot have an empty interval.)
+ * a variable is live. It has two bounds, lo is exclusive and hi is
+ * inclusive.
  *)
 type inter = { lo: iref; hi: iref }
 
@@ -316,11 +316,61 @@ let mkinters (p: iprog) =
   ) ih;
   hp
 
-(*
-let regalloc2 (p: iprog) =
-  let lh = liveness p in
-  let nr = 4 in
-*)
+let regalloc2 ?(nr=4) (p: iprog) =
+  let nbb = Array.length p in
+
+  let _regs = Array.init nr (fun _ -> {busy=[]}) in
+  let _spillh = Heap.create (fun (_,a) (_,b) -> ircmp b a) in
+  let act = Hashtbl.create 101 in (* Active list. *)
+  let _loc_ ir =
+    try Hashtbl.find act ir
+    with Not_found -> LVoid in
+
+  let rp = Array.init nbb (fun i ->
+      { bb_name = p.(i).bb_name
+      ; bb_phis = [| |]
+      ; bb_inss = [| |]
+      ; bb_jmp = `Jmp (-1)
+      }
+    ) in
+  let bb = ref [] in (* Block in construction. *)
+  let _emit l i = bb := {ri_res=l;ri_ins=i} :: !bb in
+
+  for b = 0 to nbb do
+    let bi = p.(b).bb_inss in
+    let bl = Array.length bi in
+
+    (* Entering a block.
+     * Many phi intervals start at the same time.
+     * We need to allocate them registers and store
+     * the allocator state for the resolve phase.
+     *)
+
+    for i = 0 to bl - 1 do
+      let _ir = IRIns (b,i) in
+
+      (* For a regular instruction:
+       *   1. Get locations of arguments.
+       *      Make sure they are in registers.
+       *   2. Free registers of dead variables.
+       *   3. Allocate for the new interval.
+       *   4. Emit the instruction.
+       *)
+
+      ()
+    done;
+
+    (* Leaving a block.
+     * Rewrite the jump.
+     * Store the allocator state for the resolve
+     * phase.
+     *)
+
+    rp.(b).bb_inss <- Array.of_list (List.rev !bb);
+  done;
+
+  rp
+
 
 (* Little test programs. *)
 let pbasic: iprog =