Removal of unused labels, basic live intervals

1 files changed, 115 insertions, 1 deletions

diff --git a/emit.fun b/emit.fun
index 05e84f0..6e21556 100644
--- a/emit.fun
+++ b/emit.fun
@@ -120,10 +120,122 @@ functor Emit(I: IL) = struct
     D.appi f P.iniLayouts
   end
 
+  fun getVarsForAlloc vregs =
+  let
+    fun loop idx acc =
+      if idx = D.length vregs then
+        rev acc
+      else
+        let
+          val { t, ... } = D.get vregs idx
+        in
+          if t = I.RtReg then
+            loop (idx + 1) (idx :: acc)
+          else
+            loop (idx + 1) acc
+        end
+  in
+    loop 0 []
+  end
+
+  fun extendEnd (iStart, iEnd) ops labels =
+  let
+    fun loop idx iEnd =
+      if idx = D.length ops then
+        iEnd
+      else
+        let
+          val ins = D.get ops idx
+        in
+          case ins of
+            SOME (I.IrJmp lid) | SOME (I.IrJz (_, lid)) |
+            SOME (I.IrJnz (_, lid)) =>
+            let
+              val ldest = valOf $ D.get labels lid
+
+              val iEnd =
+                if ldest > iStart andalso ldest < iEnd then
+                  idx
+                else
+                  iEnd
+            in
+              loop (idx + 1) iEnd
+            end
+          | _ => loop (idx + 1) iEnd
+        end
+  in
+    loop iEnd iEnd
+  end
+
+  fun computeIntLocal (s, e) ops labels =
+  let
+    val e = extendEnd (s, e) ops labels
+  in
+    (s, e)
+  end
+
+  fun getBasicInt [] _ = raise Unreachable
+    | getBasicInt defs [] = (List.last defs, hd defs + 1)
+    | getBasicInt defs use =
+    let
+      val (firstDef, lastDef) = (List.last defs, hd defs)
+      val (firstUse, lastUse) = (List.last use, hd use)
+
+      val first = if firstDef < firstUse then firstDef else firstUse - 1
+      val last = if lastDef < lastUse then lastUse else lastDef + 1
+    in
+      (first, last)
+    end
+
+  fun computeInt (I.Fi { vregs, ops, localBound, labels, ... }) var =
+  let
+    val { defs, use, ... } = D.get vregs var
+    val (iStart, iEnd) = getBasicInt defs use
+
+    val (iStart, iEnd) =
+      if var < localBound then
+        computeIntLocal (iStart, iEnd) ops labels
+      else
+        (iStart, iEnd)
+  in
+    (var, iStart, iEnd)
+  end
+
+  fun computeInts (F as I.Fi { vregs, ... }) vars =
+    List.map (computeInt F) vars
+
+  fun printInts ints =
+  let
+    val () = printfn `"\nintervals:\n" %
+    fun p (id, s, e) = printfn `"id: %" I id `" {" I s `", " I e `"}" %
+  in
+    List.app p ints
+  end
+
+
+  fun regAlloc (F as I.Fi { vregs, labels, ... }) =
+  let
+    val varsForAlloc = getVarsForAlloc vregs
+    val () = printfn `"for alloc: " Plist i varsForAlloc (", ", true, 0) %
+
+    val intervals = computeInts F varsForAlloc
+
+    val () = printInts intervals
+  in
+    raise Unimplemented
+  end
+
+  fun emitFunc (F as I.Fi { vregs, ... }) =
+  let
+    val () = regAlloc F vregs
+  in
+    raise Unimplemented
+  end
+
   fun openFile fname = file := SOME (TextIO.openOut fname)
 
   fun emit fname
-    (I.Ctx { globSyms, extSyms, objsZI, objs, strlits, ... }) =
+    (I.Ctx { globSyms, extSyms, objsZI, objs, strlits, funcInfos, ... }) =
   let
     val () = openFile fname
 
@@ -134,6 +246,8 @@ functor Emit(I: IL) = struct
     val () = handleData objs
     val () = handleStrlits strlits
     val () = handleLocalIniLayouts ()
+
+    val () = List.app emitFunc funcInfos
   in
     ()
   end