codegen/igraph.sml

   1 (* L3 compiler
   2  * interference graph generator
   3  * Takes a list of interfering temps and generates the interference graph
   4  * Author: Chris Lu <czl@andrew.cmu.edu>
   5  *)
   6
   7 signature IGRAPH =
   8 sig
   9   structure OperSet : ORD_SET
  10     where type Key.ord_key = x86.basicop
  11   structure LiveMap : ORD_MAP
  12     where type Key.ord_key = int
  13   structure TempMap : ORD_MAP
  14     where type Key.ord_key = Temp.temp
  15
  16   type predicates = Liveness.predicates
  17   type livenesses = Liveness.livenesses
  18   type graph = OperSet.set TempMap.map
  19   val gengraph : predicates * livenesses -> graph * Temp.temp list
  20 end
  21
  22 structure Igraph :> IGRAPH =
  23 struct
  24   structure OperSet = Liveness.OperSet
  25   structure LiveMap = Liveness.LiveMap
  26
  27   structure TempSet = BinarySetFn (
  28     struct
  29       type ord_key = Temp.temp
  30       val compare = Temp.compare
  31     end
  32   )
  33
  34   structure TempMap = SplayMapFn (
  35     struct
  36       type ord_key = Temp.temp
  37       val compare = Temp.compare
  38     end)
  39
  40   type predicates = Liveness.predicates
  41   type livenesses = Liveness.livenesses
  42   type graph = OperSet.set TempMap.map
  43
  44   structure X = x86
  45
  46   fun add_temp_interfere g (t, oper) =
  47     let
  48       val set = (valOf (TempMap.find (g, t))) handle Option => OperSet.empty
  49     in
  50       TempMap.insert (g, t, OperSet.union (set, OperSet.singleton oper))
  51     end
  52
  53   fun add_interfere g (o1, o2) =
  54     let
  55       val g = case o1
  56         of (X.TEMP t) => add_temp_interfere g (t, o2)
  57          | _ => g
  58     in
  59       case o2
  60         of (X.TEMP t) => add_temp_interfere g (t, o1)
  61          | _ => g
  62     end
  63
  64   fun alltemps preds =
  65     LiveMap.foldr
  66       (fn (ps, ts) => List.foldr
  67         (fn (Liveness.DEF(X.TEMP t), ts') => TempSet.add (ts', t)
  68           | (Liveness.USE(X.TEMP t), ts') => TempSet.add (ts', t)
  69           | (_, ts') => ts')
  70         ts
  71         ps
  72       )
  73       TempSet.empty
  74       preds
  75
  76   (* val gengraph : interferences -> graph
  77    * generates the interference graph from a list of interfering temps
  78    * by creating separate interference graphs for each line, concatenating them,
  79    * and putting them in canonical form
  80    *)
  81   fun gengraph (preds, lives) : graph * Temp.temp list =
  82     (LiveMap.foldri
  83       (fn (ln, predlist, map) =>
  84         let
  85           val ismove = Liveness.ismove predlist
  86         in
  87           List.foldr
  88             (fn (oper, map) =>
  89               List.foldr
  90                 (fn (ln', map) =>
  91                   let
  92                     val liveat = valOf (LiveMap.find (lives, ln'))
  93                     val liveat =
  94                       if not ismove
  95                       then liveat
  96                       else OperSet.difference
  97                              (liveat,
  98                               OperSet.addList (OperSet.empty, Liveness.uses predlist))
  99                   in
 100                     OperSet.foldr
 101                       (fn (oper', map) => add_interfere map (oper, oper'))
 102                       map
 103                       liveat
 104                   end)
 105                 map
 106                 (Liveness.succs predlist))
 107             map
 108             (Liveness.defs predlist)
 109         end
 110         )
 111       TempMap.empty
 112       preds,
 113       TempSet.listItems (alltemps preds))
 114 end