Initial import of l3c

[snipe.git] / codegen / igraph.sml

diff --git a/codegen/igraph.sml b/codegen/igraph.sml
index 9fe50a00ff23ee8360a8b819c63b94d53fce0f2b..30b17eee61acdde8942671491542182cb7e17200 100644 (file)
--- a/codegen/igraph.sml
+++ b/codegen/igraph.sml
@@ -1,4 +1,4 @@
-(* L2 compiler
+(* L3 compiler
  * interference graph generator
  * Takes a list of interfering temps and generates the interference graph
  * Author: Chris Lu <czl@andrew.cmu.edu>
@@ -6,66 +6,109 @@
 
 signature IGRAPH =
 sig
-  type interferences = x86.oper list list
-  type graph = (Temp.temp * x86.oper list) list
-  val gengraph : interferences -> graph
+  structure OperSet : ORD_SET
+    where type Key.ord_key = x86.oper
+  structure LiveMap : ORD_MAP
+    where type Key.ord_key = int
+  structure TempMap : ORD_MAP
+    where type Key.ord_key = Temp.temp
+      
+  type predicates = Liveness.predicates
+  type livenesses = Liveness.livenesses
+  type graph = OperSet.set TempMap.map
+  val gengraph : predicates * livenesses -> graph * Temp.temp list
 end
 
 structure Igraph :> IGRAPH =
 struct
-  type interferences = x86.oper list list
-  type graph = (Temp.temp * x86.oper list) list
+  structure OperSet = Liveness.OperSet
+  structure LiveMap = Liveness.LiveMap
+
+  structure TempSet = BinarySetFn (
+    struct
+      type ord_key = Temp.temp
+      val compare = Temp.compare
+    end
+  )
+
+  structure TempMap = SplayMapFn (
+    struct
+      type ord_key = Temp.temp
+      val compare = Temp.compare
+    end)
+  
+  type predicates = Liveness.predicates
+  type livenesses = Liveness.livenesses
+  type graph = OperSet.set TempMap.map
+  
   structure X = x86
   
-  (* val canonicalize : graph -> graph
-   * canonicalize a => puts a in the canonical form by eliminating repeat nodes and edges
-   * does so by sorting them first, then eliminating consecutive temps
-   *)
-  fun canonicalize orig =
+  fun add_temp_interfere g (t, oper) =
     let
-      val sorig = ListMergeSort.sort (fn ((a,_),(b,_)) => X.cmpoper (a,b) = LESS) orig
-      fun merge ((x, xl)::(y, yl)::rl) = (if X.opereq (x,y) then merge ((x, List.revAppend(yl,xl))::rl) else (x, xl) :: merge ((y, yl)::rl))
-        | merge (a::nil) = [a]
-        | merge nil = nil
-      val ml = merge sorig
-      fun uniq l =
-        let
-          val sl = ListMergeSort.sort (fn (a,b) => X.cmpoper (a,b) = LESS) l
-          fun merge' (x::y::rl) = (if X.opereq (x,y) then merge' (x::rl) else x :: merge' (y::rl))
-            | merge' (x::nil) = [x]
-            | merge' nil = nil
-        in
-          merge' sl
-        end
+      val set = (valOf (TempMap.find (g, t))) handle Option => OperSet.empty
     in
-      List.map (fn (a, x) => (a, uniq x)) ml
+      TempMap.insert (g, t, OperSet.union (set, OperSet.singleton oper))
+    end
+  
+  fun add_interfere g (o1, o2) =
+    let
+      val g = case o1
+        of (X.TEMP t) => add_temp_interfere g (t, o2)
+         | _ => g
+    in
+      case o2
+        of (X.TEMP t) => add_temp_interfere g (t, o1)
+         | _ => g
     end
 
-  (* val proc_one : Temp.temp list * graph -> graph
-   * helper function to convert a list of interfering registers to a graph
-   *)
-  fun proc_one x =
-        List.map
-          (fn item1 => (item1, (List.filter (fn item2 => not (X.opereq(item1, item2))) x)))
-          x
+  fun alltemps preds =
+    LiveMap.foldr
+      (fn (ps, ts) => List.foldr
+        (fn (Liveness.DEF(X.TEMP t), ts') => TempSet.add (ts', t)
+          | (Liveness.USE(X.TEMP t), ts') => TempSet.add (ts', t)
+          | (_, ts') => ts')
+        ts
+        ps
+      )
+      TempSet.empty
+      preds
 
   (* val gengraph : interferences -> graph
    * generates the interference graph from a list of interfering temps
    * by creating separate interference graphs for each line, concatenating them,
    * and putting them in canonical form
    *)
-  fun gengraph x =
-    let
-      val igraph' = canonicalize (List.concat (List.map proc_one x))
-    in
-      foldr
-        (fn ((a,l),b) => case a
-          of X.REG(_) => b
-           | X.TEMP(t) => (t,l)::b 
-           | _ => raise ErrorMsg.InternalError "Non-live register type found in igraph"
+  fun gengraph (preds, lives) : graph * Temp.temp list =
+    (LiveMap.foldri
+      (fn (ln, predlist, map) =>
+        let
+          val ismove = Liveness.ismove predlist
+        in
+          List.foldr
+            (fn (oper, map) =>
+              List.foldr
+                (fn (ln', map) =>
+                  let
+                    val liveat = valOf (LiveMap.find (lives, ln'))
+                    val liveat =
+                      if not ismove
+                      then liveat
+                      else OperSet.difference
+                             (liveat,
+                              OperSet.addList (OperSet.empty, Liveness.uses predlist))
+                  in
+                    OperSet.foldr
+                      (fn (oper', map) => add_interfere map (oper, oper'))
+                      map
+                      liveat
+                  end)
+                map
+                (Liveness.succs predlist))
+            map
+            (Liveness.defs predlist)
+        end
         )
-        nil
-        igraph'
-    end
-
+      TempMap.empty
+      preds,
+      TempSet.listItems (alltemps preds))
 end