X-Git-Url: http://git.joshuawise.com/snipe.git/blobdiff_plain/0a24e44d4e9f82f8d3d83de8e58c83c8cf2868b6..5c79bb689ab446551bc7ec4497e6c9b75582837e:/codegen/igraph.sml diff --git a/codegen/igraph.sml b/codegen/igraph.sml index 9fe50a0..7e71043 100644 --- 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 @@ -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.basicop + 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