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

SCM Repository

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

Annotation of /MLRISC/trunk/ra/liveness.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 2126 - (view) (download)

1 : monnier 245 (* liveness.sml
2 :     *
3 :     * COPYRIGHT (c) 1996 Bell Laboratories.
4 :     *
5 :     *)
6 :    
7 :     (** liveness.sml - computes live variables **)
8 :    
9 : george 909
10 : leunga 641 (* I've moved the parameters of the functor to the function arguments
11 :     * so that it is more flexible.
12 :     *
13 :     * -- Allen 4/28/00
14 :     *)
15 :    
16 : george 909 (* TODO: The liveness module should take a
17 :     * C.cellset list IntHashTable.hash_table
18 :     *)
19 :    
20 : monnier 245 signature LIVENESS = sig
21 :    
22 : george 909 structure CFG : CONTROL_FLOW_GRAPH
23 : monnier 245
24 : jhr 924 type liveness_table =
25 :     CellsBasis.SortedCells.sorted_cells IntHashTable.hash_table
26 : george 909
27 : blume 1259 type du = CellsBasis.cell list * CellsBasis.cell list
28 :    
29 :     (* one def/use step (given defUse function, take du after instruction
30 :     * to du before instruction *)
31 :     val duStep : (CFG.I.instruction -> du) ->
32 :     CFG.I.instruction * du -> du
33 :    
34 :     (* one step for liveness (on a per-instruction basis) *)
35 :     val liveStep : (CFG.I.instruction -> du) ->
36 :     CFG.I.instruction * CellsBasis.SortedCells.sorted_cells ->
37 :     CellsBasis.SortedCells.sorted_cells
38 :    
39 : george 909 val liveness : {
40 : blume 1259 defUse : CFG.I.instruction -> du,
41 : george 909 getCell : CellsBasis.CellSet.cellset -> CellsBasis.cell list
42 :     } -> CFG.cfg
43 : jhr 924 -> {liveIn : liveness_table,
44 :     liveOut : liveness_table
45 :     }
46 : george 909
47 : monnier 245 end
48 :    
49 :    
50 : george 909 functor Liveness(Flowgraph : CONTROL_FLOW_GRAPH) : LIVENESS = struct
51 :     structure CFG = Flowgraph
52 :     structure I = CFG.I
53 :     structure SC = CellsBasis.SortedCells
54 :     structure CS = CellsBasis.CellSet
55 :     structure HT = IntHashTable
56 :     structure G = Graph
57 : monnier 245
58 : jhr 924 type liveness_table = SC.sorted_cells HT.hash_table
59 : monnier 245
60 : blume 1259 type du = CellsBasis.cell list * CellsBasis.cell list
61 :    
62 : monnier 411 fun error msg = MLRiscErrorMsg.error("Liveness",msg)
63 : monnier 245
64 : george 909 val NotFound = General.Fail("Liveness: Not Found") (* exception *)
65 :    
66 : monnier 245 fun prList(l,msg:string) = let
67 :     fun pr([]) = print "\n"
68 : leunga 744 | pr(x::xs) = (print(Int.toString x ^ " "); pr xs)
69 : monnier 245 in print msg; pr l
70 :     end
71 :    
72 : blume 1259 fun duStep defUse (insn, (def, use)) = let
73 :     val (d, u) = defUse insn
74 :     val d0 = SC.uniq d
75 :     val def' = SC.union (d0, def)
76 :     val use' = SC.union (SC.uniq u, SC.difference (use, d0))
77 :     in
78 :     (def', use')
79 :     end
80 :    
81 :     fun liveStep defUse (insn, liveout) = let
82 :     val (d, u) = defUse insn
83 :     in
84 :     SC.union (SC.uniq u, SC.difference (liveout, SC.uniq d))
85 :     end
86 :    
87 : george 909 fun liveness {defUse,getCell} = let
88 :     val getCell = SC.uniq o getCell
89 : monnier 245
90 : george 909 fun dataflow (cfg as G.GRAPH graph) = let
91 :     val blocks = #nodes graph ()
92 :     val nNodes = #order graph ()
93 : monnier 245
94 : george 909 val liveIn : SC.sorted_cells HT.hash_table = HT.mkTable(nNodes, NotFound)
95 :     val liveOut : SC.sorted_cells HT.hash_table = HT.mkTable(nNodes, NotFound)
96 :     val uses : SC.sorted_cells HT.hash_table = HT.mkTable(nNodes, NotFound)
97 :     val defs : SC.sorted_cells HT.hash_table = HT.mkTable(nNodes, NotFound)
98 : monnier 245
99 : george 909 (* compute block aggregate definition use. *)
100 :     fun initDefUse(nid, CFG.BLOCK{insns, ...}) = let
101 : blume 1259 val (def, use) = foldl (duStep defUse) (SC.empty, SC.empty) (!insns)
102 : george 909 in
103 : blume 1259 HT.insert uses (nid, use);
104 :     HT.insert defs (nid, def)
105 : george 909 end
106 : monnier 245
107 : george 909 (* gather the liveOut information *)
108 :     fun initLiveOut(nid, CFG.BLOCK{annotations, ...}) =
109 :     (case #get CFG.LIVEOUT (!annotations)
110 :     of NONE => HT.insert liveOut (nid, SC.empty)
111 :     | SOME cs => HT.insert liveOut (nid, getCell cs)
112 :     (*esac*))
113 : monnier 245
114 :    
115 : george 909 fun initLiveIn () =
116 :     #forall_nodes graph (fn (nid, _) => HT.insert liveIn (nid, SC.empty))
117 : monnier 245
118 : george 909 fun init() = (
119 :     #forall_nodes graph initDefUse;
120 :     #forall_nodes graph initLiveOut;
121 :     initLiveIn())
122 : monnier 245
123 : george 909 fun inB(nid) = let
124 :     val use = HT.lookup uses nid
125 :     val def = HT.lookup defs nid
126 :     val liveOut = HT.lookup liveOut nid
127 :     val livein = SC.union(use, SC.difference(liveOut, def))
128 :     val changed = SC.notEq(HT.lookup liveIn nid, livein)
129 :     in
130 :     HT.insert liveIn (nid, livein); changed
131 :     end
132 :    
133 :    
134 :     fun outB(nid, CFG.BLOCK{annotations, ...}) = let
135 :     fun inSucc([], acc) = acc
136 :     | inSucc(nid::ns, acc) =
137 :     inSucc(ns, SC.union(HT.lookup liveIn nid, acc))
138 :     val oldLiveOut = HT.lookup liveOut nid
139 :     val newLiveOut = inSucc(#succ graph nid, SC.empty)
140 :     in
141 :     HT.insert liveOut (nid, newLiveOut);
142 :     SC.notEq(oldLiveOut, newLiveOut)
143 :     end
144 :    
145 :     fun bottomup() = let
146 :     val visitedTbl : bool HT.hash_table = HT.mkTable(nNodes, NotFound)
147 :     fun isVisited nid =
148 :     (case HT.find visitedTbl nid of NONE => false | _ => true)
149 :     fun visit(nid, changed) = let
150 :     fun visitSucc([], changed') = changed'
151 :     | visitSucc(nid::ns, changed') = let
152 :     val CFG.BLOCK{kind, ...} = #node_info graph nid
153 :     in case kind
154 :     of CFG.STOP => visitSucc(ns, changed')
155 :     | CFG.NORMAL =>
156 :     if isVisited nid then visitSucc(ns, changed')
157 :     else visitSucc(ns, visit(nid, changed'))
158 : george 984 | _ => error "visit.visitSucc"
159 : george 909 end
160 :    
161 :     val _ = HT.insert visitedTbl (nid, true)
162 :    
163 :     val changed' = visitSucc(#succ graph nid, changed);
164 :     val block = #node_info graph nid
165 :     val change1 = outB(nid, block)
166 :     val change2 = inB(nid)
167 :     in
168 :     changed' orelse change1 orelse change2
169 :     end
170 :    
171 :     fun forall([], changed) = changed
172 :     | forall((nid,block)::rest, changed) =
173 :     if isVisited(nid) then forall(rest, changed)
174 :     else forall(rest, visit(nid, changed))
175 :     in
176 :     forall(blocks, false)
177 :     end
178 :    
179 :     fun repeat n = if bottomup() then repeat(n+1) else (n+1)
180 :    
181 : monnier 245 in
182 : jhr 924 init(); repeat 0; {liveIn=liveIn, liveOut=liveOut}
183 : george 909 end
184 :    
185 :     in dataflow
186 :     end
187 : monnier 245 end
188 :    

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