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 /sml/trunk/src/MLRISC/SSA/mlrisc-cfg2ssa.sml
ViewVC logotype

Annotation of /sml/trunk/src/MLRISC/SSA/mlrisc-cfg2ssa.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 228 - (view) (download)

1 : monnier 221 (*
2 :     * This module constructs an SSA graph from a CFG.
3 :     * It can use either pruned or semi-pruned SSA form.
4 :     * The latter is probably faster to construct but may consume more space.
5 :     *)
6 :    
7 :     functor CFG2SSAFn
8 :     (structure SSA : SSA
9 :     structure Liveness : LIVENESS_ANALYSIS
10 :     sharing SSA.CFG = Liveness.CFG
11 :     ) : CFG2SSA =
12 :     struct
13 :    
14 :     structure SSA = SSA
15 :     structure CFG = SSA.CFG
16 :     structure I = SSA.I
17 :     structure SP = SSA.SP
18 :     structure E = SSAExp
19 :     structure C = I.C
20 :     structure G = Graph
21 :     structure A = Array
22 :     structure R = RegSet
23 :     structure DA = DynamicArray
24 :     structure SSA' = StaticSingleAssignmentFormFn(SSA.Dom)
25 :     structure CP = SSACopiesFn(SP)
26 :    
27 :     fun error msg = MLRiscErrorMsg.impossible("CFG2SSA."^msg)
28 :    
29 :     (*
30 :     * Construct an SSA graph from a CFG and dominator tree
31 :     *)
32 :     fun buildSSA {copyPropagation,keepName,semiPruned}
33 :     (CFG as G.GRAPH cfg,computeDom) =
34 :     let val Dom as G.GRAPH dom = computeDom CFG
35 :     val SSA as G.GRAPH ssa = SSA.newSSA(CFG,computeDom)
36 :    
37 :     val N = #capacity cfg ()
38 :     val ENTRY = hd(#entries cfg ())
39 :     val EXIT = hd(#exits cfg ())
40 :     val getLiveness = Liveness.getLiveness CFG
41 :     val updateCellClass = SSA.updateCellClass SSA
42 :     val DU = A.array(N,[])
43 :     val mustDef = SP.mustDef
44 :    
45 :     (*
46 :     * Is the definition pinned
47 :     *)
48 :     fun isPinnedDef r = List.exists (fn r' => r = r') mustDef
49 :    
50 :     (*
51 :     * Check for initial and terminal blocks
52 :     *)
53 :     fun isInitial b = List.exists(fn (i,_,_) => i=ENTRY) (#in_edges cfg b)
54 :     fun isTerminal b = List.exists(fn (_,j,_) => j=EXIT) (#out_edges cfg b)
55 :    
56 :     (*
57 :     * v is in localLiveIn iff a use of v in some block is not defined
58 :     * in the same block
59 :     *)
60 :     val localLiveIn = BitSet.create(if semiPruned then C.maxCell() else 1)
61 :    
62 :     (*
63 :     * Extracts the registers
64 :     *)
65 :     fun getRegs(SP.REG(r,c)::du,regs) = getRegs(du,r::regs)
66 :     | getRegs(SP.FIX(r,c)::du,regs) = getRegs(du,r::regs)
67 :     | getRegs(SP.MEM r::du,regs) = getRegs(du,r::regs)
68 :     | getRegs(SP.OPN _::du,regs) = getRegs(du,regs)
69 :     | getRegs([],regs) = regs
70 :    
71 :     (*
72 :     * Initialization. Compute the DU array and the
73 :     * localLiveIn set.
74 :     *)
75 :     fun initialize() =
76 :     let fun getLiveOut(_,block) =
77 :     R.fromList(C.cellsetToRegs(CFG.regmap CFG,CFG.liveOut block))
78 :     val getOperands = SP.operands{regmap = CFG.reglookup CFG,
79 :     immed = SSA.immed SSA,
80 :     label = SSA.label SSA,
81 :     operand = SSA.operand SSA
82 :     }
83 :     fun defUse(b,b' as CFG.BLOCK{insns,...}) =
84 :     let fun getRegs([],regs) = regs
85 :     | getRegs(SP.REG(r,c)::du,regs) =
86 :     (updateCellClass(r,c); getRegs(du,r::regs))
87 :     | getRegs(SP.FIX(r,c)::du,regs) =
88 :     (updateCellClass(r,c); getRegs(du,r::regs))
89 :     | getRegs(SP.MEM r::du,regs) =
90 :     (updateCellClass(r,C.MEM); getRegs(du,r::regs))
91 :     | getRegs(SP.OPN _::du,regs) = getRegs(du,regs)
92 :     fun scan([],du,def,use) = (du,def,use)
93 :     | scan(insn::insns,du,def,use) =
94 :     let val (d,u) = getOperands insn
95 :     val d' = R.fromList(getRegs(d,[]))
96 :     val u' = R.fromList(getRegs(u,[]))
97 :     val use = R.+(R.-(use,d'),u')
98 :     val def = R.-(R.+(def,d'),u')
99 :     in scan(insns,(d,u)::du,def,use)
100 :     end
101 :     val liveOut = getLiveOut(b,b')
102 :     val (du,def,use) = scan(!insns,[],R.empty,liveOut)
103 :     in A.update(DU,b,du);
104 :     if semiPruned then
105 :     R.app (fn r => BitSet.set(localLiveIn,r)) use else ();
106 :     (def,use)
107 :     end
108 :     in Liveness.liveness{cfg=CFG,defUse=defUse,liveOut=getLiveOut}
109 :     end
110 :    
111 :     (*
112 :     * Is variable v considered live at block b?
113 :     *)
114 :     fun isLiveSemiPruned(v,b) = BitSet.contains(localLiveIn,v)
115 :     fun isLivePruned(v,b) =
116 :     let val (liveIn,_) = getLiveness b
117 :     in R.contains(liveIn,v) end
118 :    
119 :     (*
120 :     * Return the relevant definitions in a block
121 :     *)
122 :     fun getDefsPruned(b,_) =
123 :     let val defs = foldr (fn ((d,_),l) => getRegs(d,l)) [] (A.sub(DU,b))
124 :     val (_,liveOut) = getLiveness b
125 :     in (* List.filter
126 :     (fn r => BitSet.contains(localLiveIn,r)) (R.sort defs) *)
127 :     R.toList(R.*(R.fromList defs,liveOut))
128 :     end
129 :    
130 :     fun getDefsSemiPruned(b,_) =
131 :     let val defs = foldr (fn ((d,_),l) => getRegs(d,l)) [] (A.sub(DU,b))
132 :     in List.filter
133 :     (fn r => BitSet.contains(localLiveIn,r)) (R.sort defs)
134 :     end
135 :    
136 :     (*
137 :     * Add edges to the SSA graph
138 :     *)
139 :     fun addEdges(n,uses) =
140 :     app (fn r => if r >= 0 then #add_edge ssa (r,n,r)
141 :     else ()) uses
142 :    
143 :     fun addEdges'(n,uses) =
144 :     app (fn SP.REG(r,_) => #add_edge ssa (r,n,r)
145 :     | SP.FIX(r,_) => #add_edge ssa (r,n,r)
146 :     | SP.MEM r => #add_edge ssa (r,n,r)
147 :     | SP.OPN _ => ()) uses
148 :    
149 :     (*
150 :     * Insert phi nodes into a basic block
151 :     *)
152 :     fun insertPhi{block,in_edges,phis=[]} = ()
153 :     | insertPhi{block=(_,CFG.BLOCK{kind=CFG.STOP,...}),...} = ()
154 :     | insertPhi{block=(b,_),in_edges,phis} =
155 :     let val preds = map (fn (j,_,_) => j) in_edges
156 :     fun addPhi(t',t,s) =
157 :     (#add_node ssa(t,SSA.PHI{preds=preds,t'=t',t=t,s=s,b=b});
158 :     addEdges(t,s))
159 :     in app addPhi phis
160 :     end
161 :    
162 :     fun getval(SP.OPN v) = v
163 :     | getval(SP.REG(r,_)) = r
164 :     | getval(SP.MEM r) = r
165 :     | getval(SP.FIX(r,_)) = r
166 :     val getvals = map getval
167 :    
168 :     (*
169 :     * Rename a block
170 :     *)
171 :     fun renameStmt _ (_,CFG.BLOCK{kind=CFG.START,...}) = ()
172 :     | renameStmt _ (_,CFG.BLOCK{kind=CFG.STOP,...}) = ()
173 :     | renameStmt {rename,copy} (b,CFG.BLOCK{insns,...}) =
174 :     let fun addOp(e,i,defs,uses,pos) =
175 :     let val {defs,uses} = rename{defs=defs,uses=uses}
176 :     val n = (case defs of
177 :     r :: _ => r
178 :     | [] => C.newReg())
179 :     val n' = SSA.OP{e=e,i=i,t=defs,s=uses,b=b,p=pos}
180 :     in #add_node ssa (n,n');
181 :     addEdges(n,uses)
182 :     end
183 :     fun scan(i::insns,pos,(d,u)::DU) =
184 :     let val defs = getvals d
185 :     val uses = getvals u
186 :     val e = SP.exp i
187 :     val e = if List.exists isPinnedDef defs then
188 :     E.PINNED e else e
189 :     in case (e,copyPropagation) of
190 :     (E.COPY,true) => copy{dst=defs,src=uses}
191 :     | (E.COPY,false) =>
192 :     let val (defs,uses) = CP.simplifyCopy'(defs,uses)
193 :     in case defs of
194 :     [] => ()
195 :     | _ => addOp(e,i,defs,uses,pos)
196 :     end
197 :     (* must be last if it is a control flow op *)
198 :     | ((E.BRANCH _ | E.JMP _ | E.RET),_) =>
199 :     addOp(e,i,defs,uses,12345678)
200 :     | _ => addOp(e,i,defs,uses,pos)
201 :     ;
202 :     scan(insns,pos+1,DU)
203 :     end
204 :     | scan _ = ()
205 :    
206 :     (*
207 :     * Insert a source node into the ssa graph
208 :     *)
209 :     fun addSource() =
210 :     let val (liveIn,_) = getLiveness b
211 :     val defs' = R.toList liveIn
212 :     val {defs,...} = rename{defs=defs',uses=[]}
213 :     val n = (case defs of
214 :     r :: _ => r
215 :     | [] => C.newReg())
216 :     in #add_node ssa (n,SSA.SOURCE{t=defs,t'=defs',b=b});
217 :     #set_entries ssa (n:: #entries ssa ())
218 :     end
219 :    
220 :     (*
221 :     * Insert a sink node into the ssa graph
222 :     *)
223 :     fun addSink() =
224 :     let val (_,liveOut) = getLiveness b
225 :     val uses' = R.toList liveOut
226 :     val {uses,...} = rename{defs=[],uses=uses'}
227 :     val n = C.newReg()
228 :     in #add_node ssa (n,SSA.SINK{s=uses,s'=uses',b=b});
229 :     addEdges(n,uses);
230 :     #set_exits ssa (n :: #exits ssa ())
231 :     end
232 :    
233 :     in if isInitial(b) then addSource() else ();
234 :     scan(rev(!insns),0,A.sub(DU,b));
235 :     if isTerminal(b) then addSink() else ()
236 :     end
237 :    
238 :     (*
239 :     * Compute the SSA graph
240 :     *)
241 :     fun computeSSA() =
242 :     SSA'.compute_ssa Dom
243 :     { max_var = C.maxCell(),
244 :     defs = if semiPruned then getDefsSemiPruned
245 :     else getDefsPruned,
246 :     is_live = if semiPruned then isLiveSemiPruned
247 :     else isLivePruned,
248 :     rename_var = SSA.newRenamedVar
249 :     (if keepName then SOME(A.array(C.maxCell(),0))
250 :     else NONE) SSA,
251 :     rename_stmt = renameStmt,
252 :     insert_phi = insertPhi
253 :     }
254 :    
255 :     (*
256 :     * Fix up the uninitialized node
257 :     *)
258 :     fun fixupUninit() =
259 :     let val defSite = SSA.defSite SSA
260 :     fun fixUp i =
261 :     case #node_info ssa i of
262 :     SSA.SOURCE{b,...} =>
263 :     if b = ENTRY then fixUninit(i,b)
264 :     else ()
265 :     | _ => ()
266 :     and fixUninit(uninit,b) =
267 :     let val regs = ref []
268 :     fun add(r,_,_) =
269 :     if defSite r = uninit then regs := r :: !regs else ()
270 :     val _ = #forall_edges ssa add
271 :     val regs = R.sort(!regs)
272 :     in #add_node ssa (uninit,SSA.SOURCE{b=b,t=regs,t'=regs})
273 :     end
274 :     in app fixUp (#entries ssa ())
275 :     end
276 :    
277 :     in initialize();
278 :     computeSSA();
279 :     fixupUninit();
280 :     SSA
281 :     end
282 :    
283 :     end
284 :    
285 :     (*
286 : monnier 227 * $Log$
287 : monnier 221 *)

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