Initial import of l2c

[snipe.git] / codegen / igraph.sml

diff --git a/codegen/igraph.sml b/codegen/igraph.sml
index b11fd0d006c689bed2dd39101f8081d43882aef5..9fe50a00ff23ee8360a8b819c63b94d53fce0f2b 100644 (file)
--- a/codegen/igraph.sml
+++ b/codegen/igraph.sml
@@ -1,37 +1,37 @@
-(* interference graph generator
- * Gathers tiberium, fires rockets
+(* L2 compiler
+ * interference graph generator
  * Takes a list of interfering temps and generates the interference graph
- * Author: Chris Lu <czl@andrew>
+ * Author: Chris Lu <czl@andrew.cmu.edu>
  *)
 
 signature IGRAPH =
 sig
-  type tiberium = x86.oper list list
-  type rockets = (Temp.temp * x86.oper list) list
-  val gengraph : tiberium -> rockets
+  type interferences = x86.oper list list
+  type graph = (Temp.temp * x86.oper list) list
+  val gengraph : interferences -> graph
 end
 
 structure Igraph :> IGRAPH =
 struct
-  type tiberium = x86.oper list list
-  type rockets = (Temp.temp * x86.oper list) list
+  type interferences = x86.oper list list
+  type graph = (Temp.temp * x86.oper list) list
   structure X = x86
   
-  (* val canonicalize : rockets -> rockets
+  (* 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 =
     let
       val sorig = ListMergeSort.sort (fn ((a,_),(b,_)) => X.cmpoper (a,b) = LESS) orig
-      fun merge ((x, xl)::(y, yl)::rl) = (case X.cmpoper (x,y) of EQUAL => merge ((x, xl @ yl)::rl) | _ => (x, xl) :: merge ((y, yl)::rl))
+      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) = (case X.cmpoper (x,y) of EQUAL => merge' (x::rl) | _ => x :: merge' (y::rl))
+          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
@@ -41,15 +41,15 @@ struct
       List.map (fn (a, x) => (a, uniq x)) ml
     end
 
-  (* val proc_one : Temp.temp list * rockets -> rockets
+  (* 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 => X.cmpoper(item1, item2) <> EQUAL) x)))
+          (fn item1 => (item1, (List.filter (fn item2 => not (X.opereq(item1, item2))) x)))
           x
 
-  (* val gengraph : tiberium -> rockets
+  (* 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
@@ -62,7 +62,7 @@ struct
         (fn ((a,l),b) => case a
           of X.REG(_) => b
            | X.TEMP(t) => (t,l)::b 
-           | _ => raise ErrorMsg.InternalError "I'm a doooodyyyheaadddd"
+           | _ => raise ErrorMsg.InternalError "Non-live register type found in igraph"
         )
         nil
         igraph'