Home My Page Projects Code Snippets Project Openings SML/NJ
Summary Activity Forums Tracker Lists Tasks Docs Surveys News SCM Files

SCM Repository

[smlnj] Diff of /sml/trunk/src/MLRISC/ra/liveness.sml
ViewVC logotype

Diff of /sml/trunk/src/MLRISC/ra/liveness.sml

Parent Directory Parent Directory | Revision Log Revision Log | View Patch Patch

revision 908, Fri Aug 24 17:36:41 2001 UTC revision 909, Fri Aug 24 17:48:53 2001 UTC
# Line 6  Line 6 
6    
7  (** liveness.sml - computes live variables **)  (** liveness.sml - computes live variables **)
8    
9    
10  (* I've moved the parameters of the functor to the function arguments  (* I've moved the parameters of the functor to the function arguments
11   * so that it is more flexible.   * so that it is more flexible.
12   *   *
13   * -- Allen 4/28/00   * -- Allen 4/28/00
14   *)   *)
15    
16    (* TODO: The liveness module should take a
17     *  C.cellset list IntHashTable.hash_table
18     *)
19    
20  signature LIVENESS = sig  signature LIVENESS = sig
21    
22    structure F : FLOWGRAPH    structure CFG : CONTROL_FLOW_GRAPH
23    structure I : INSTRUCTIONS  
24    structure C : CELLS    type live_in_table = CellsBasis.SortedCells.sorted_cells IntHashTable.hash_table
25      sharing F.I = I  
26      sharing I.C = C    val liveness : {
27              defUse : CFG.I.instruction
28    val liveness :                          -> (CellsBasis.cell list * CellsBasis.cell list),
29        { defUse     : I.instruction -> CellsBasis.cell list * CellsBasis.cell list,            getCell    : CellsBasis.CellSet.cellset -> CellsBasis.cell list
30          updateCell : C.cellset * CellsBasis.cell list -> C.cellset,          } -> CFG.cfg
31          getCell    : C.cellset -> CellsBasis.cell list,              -> live_in_table
32          blocks     : F.block list  
       } -> F.block list  
33  end  end
34    
35    
36  functor Liveness(Flowgraph : FLOWGRAPH) : LIVENESS =  functor Liveness(Flowgraph : CONTROL_FLOW_GRAPH) : LIVENESS = struct
37  struct    structure CFG = Flowgraph
38      structure I   = CFG.I
39    structure F  = Flowgraph    structure SC  = CellsBasis.SortedCells
40    structure I  = F.I    structure CS  = CellsBasis.CellSet
41    structure C  = I.C    structure HT  = IntHashTable
42    structure SC = CellsBasis.SortedCells (* CellsBasis.SortedCells *)    structure G   = Graph
43    
44      type live_in_table = SC.sorted_cells HT.hash_table
45    
46    fun error msg = MLRiscErrorMsg.error("Liveness",msg)    fun error msg = MLRiscErrorMsg.error("Liveness",msg)
47    
48      val NotFound = General.Fail("Liveness: Not Found")            (* exception *)
49    
50    fun prList(l,msg:string) = let    fun prList(l,msg:string) = let
51        fun pr([]) = print "\n"        fun pr([]) = print "\n"
52          | pr(x::xs) = (print(Int.toString x ^ " "); pr xs)          | pr(x::xs) = (print(Int.toString x ^ " "); pr xs)
53      in print msg; pr l      in print msg; pr l
54      end      end
55    
56    fun liveness{defUse,getCell,updateCell,blocks} = let    fun liveness {defUse,getCell} = let
57        val getCell = SC.uniq o getCell        val getCell = SC.uniq o getCell
58        fun codeBlocks [] = []  
59          | codeBlocks((blk as F.BBLOCK _)::blks) = blk::codeBlocks blks      fun dataflow (cfg as G.GRAPH graph) = let
60          | codeBlocks(_::blks) = codeBlocks blks        val blocks = #nodes graph ()
61          val nNodes = #order graph ()
62        fun dataflow blkArr = let  
63            val M                                    = Array.length blkArr        val liveIn : SC.sorted_cells  HT.hash_table = HT.mkTable(nNodes, NotFound)
64            val useArr : SC.sorted_cells Array.array = Array.array(M,SC.empty)        val liveOut : SC.sorted_cells HT.hash_table = HT.mkTable(nNodes, NotFound)
65            val defArr : SC.sorted_cells Array.array = Array.array(M,SC.empty)        val uses : SC.sorted_cells HT.hash_table = HT.mkTable(nNodes, NotFound)
66          val defs : SC.sorted_cells HT.hash_table = HT.mkTable(nNodes, NotFound)
67            fun init ~1 = ()  
68              | init n  = let        (* compute block aggregate definition use. *)
69                  val F.BBLOCK{blknum,insns,liveIn,...} = Array.sub(blkArr,n)        fun initDefUse(nid, CFG.BLOCK{insns, ...}) = let
70                  fun defuse(insn::insns,def,use) = let                  fun defuse(insn::insns,def,use) = let
71                        val (d,u) = defUse insn                        val (d,u) = defUse insn
72                        val u' = SC.difference(SC.uniq u,def)                        val u' = SC.difference(SC.uniq u,def)
73                        val use' = SC.union(u', use)                        val use' = SC.union(u', use)
74                        val d' = SC.difference(SC.uniq d,use')                        val d' = SC.difference(SC.uniq d,use')
75                      in              in defuse(insns, SC.union(d',def), use')
                       defuse(insns, SC.union(d',def), use')  
76                      end                      end
77                    | defuse([],def,use) =                    | defuse([],def,use) =
78                        (Array.update(useArr,blknum,use);                (HT.insert uses (nid, use);  HT.insert defs (nid, def))
                        Array.update(defArr,blknum,def))  
79                in                in
80                    defuse(rev(!insns),SC.empty,SC.empty);          defuse(rev(!insns), SC.empty, SC.empty)
81                    liveIn := updateCell(!liveIn,[]);        end
82                    init(n-1)  
83                end        (* gather the liveOut information *)
84          fun initLiveOut(nid, CFG.BLOCK{annotations, ...}) =
85            fun outB(F.BBLOCK{succ=ref [], ...}) = false          (case #get CFG.LIVEOUT (!annotations)
86              | outB(F.BBLOCK{succ=ref [(F.EXIT _,_)], ...}) = false            of NONE => HT.insert liveOut (nid, SC.empty)
87              | outB(F.BBLOCK{succ, liveOut,...}) = let             | SOME cs => HT.insert liveOut (nid, getCell cs)
88                  fun inSuccs([], acc) = acc          (*esac*))
89                    | inSuccs((F.EXIT _,_)::sl, acc) = inSuccs(sl, acc)  
90                    | inSuccs((F.BBLOCK{blknum,liveIn,...},_)::sl, acc) =  
91                        inSuccs(sl, SC.union(getCell(!liveIn), acc))        fun initLiveIn () =
92                  val liveout = inSuccs(!succ, SC.empty)          #forall_nodes graph (fn (nid, _) => HT.insert liveIn (nid, SC.empty))
93                  val change = SC.notEq(getCell(!liveOut),liveout)  
94                in liveOut:= updateCell(!liveOut,SC.return liveout); change        fun init() = (
95                end              #forall_nodes graph initDefUse;
96              | outB _ = error "liveness.dataflow.outB"              #forall_nodes graph initLiveOut;
97                initLiveIn())
98            fun inB(F.BBLOCK{blknum,liveIn,liveOut,...}) = let  
99                val use    = Array.sub(useArr,blknum)        fun inB(nid) = let
100                val def    = Array.sub(defArr,blknum)          val use = HT.lookup uses nid
101                val livein = SC.union(use, SC.difference(getCell(!liveOut),def))          val def = HT.lookup defs nid
102                val change = SC.notEq(getCell(!liveIn),livein)          val liveOut = HT.lookup liveOut nid
103            val livein = SC.union(use, SC.difference(liveOut, def))
104            val changed = SC.notEq(HT.lookup liveIn nid, livein)
105          in
106            HT.insert liveIn (nid, livein); changed
107          end
108    
109    
110          fun outB(nid, CFG.BLOCK{annotations, ...}) = let
111            fun inSucc([], acc) = acc
112              | inSucc(nid::ns, acc) =
113                 inSucc(ns, SC.union(HT.lookup liveIn nid, acc))
114            val oldLiveOut = HT.lookup liveOut nid
115            val newLiveOut = inSucc(#succ graph nid, SC.empty)
116              in              in
117                liveIn := updateCell(!liveIn, SC.return livein); change          HT.insert liveOut (nid, newLiveOut);
118            SC.notEq(oldLiveOut, newLiveOut)
119              end              end
             | inB _ = error "liveness.dataflow.inB"  
120    
121            fun bottomup() = let            fun bottomup() = let
122                val visited = Array.array(M,false)            val visitedTbl : bool HT.hash_table = HT.mkTable(nNodes, NotFound)
123                fun visit(n, changed) = let            fun isVisited nid =
124                (case HT.find visitedTbl nid of NONE => false | _ => true)
125              fun visit(nid, changed) = let
126                    fun visitSucc([],changed') = changed'                    fun visitSucc([],changed') = changed'
127                      | visitSucc((F.EXIT _,_)::ns, changed') =                | visitSucc(nid::ns, changed') = let
128                         visitSucc(ns, changed')                    val CFG.BLOCK{kind, ...} = #node_info graph nid
129                      | visitSucc((F.BBLOCK{blknum=n, ...},_)::ns,changed') =                  in case kind
130                         if Array.sub(visited,n) then visitSucc(ns,changed')                      of CFG.STOP => visitSucc(ns, changed')
131                         else visitSucc(ns,visit(n,changed'))                       | CFG.NORMAL =>
132                            if isVisited nid then visitSucc(ns, changed')
133                    val block as(F.BBLOCK{succ,...}) = Array.sub(blkArr, n)                          else visitSucc(ns, visit(nid, changed'))
134                    val _ = Array.update(visited,n,true)                  end
135    
136                    val changed' = visitSucc(!succ,changed);              val _ = HT.insert visitedTbl (nid, true)
137                    val change1 = outB block  
138                    val change2 = inB block              val changed' = visitSucc(#succ graph nid, changed);
139                val block = #node_info graph nid
140                val change1 = outB(nid, block)
141                val change2 = inB(nid)
142                  in                  in
143                    changed' orelse change1 orelse change2                    changed' orelse change1 orelse change2
144                  end                  end
145                fun visitAll(n,last,changed) =  
146                    if n=last then changed            fun forall([], changed) = changed
147                    else if Array.sub(visited,n) then visitAll(n+1,last,changed)              | forall((nid,block)::rest, changed) =
148                         else visitAll(n+1,last,visit(n,changed))                 if isVisited(nid) then forall(rest, changed)
149                   else forall(rest, visit(nid, changed))
150              in              in
151                visitAll(0,M,false)            forall(blocks, false)
152              end              end
153    
154            fun repeat n = if bottomup() then repeat(n+1) else (n+1)            fun repeat n = if bottomup() then repeat(n+1) else (n+1)
155    
156          in          in
157              init (M-1); repeat 0        init(); repeat 0; liveIn
158          end          end
159      in  
160          dataflow (Array.fromList (codeBlocks blocks));    in dataflow
         blocks  
161      end      end
162  end  end
163    

Legend:
Removed from v.908  
changed lines
  Added in v.909

root@smlnj-gforge.cs.uchicago.edu
ViewVC Help
Powered by ViewVC 1.0.0