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/scheduling/buildDDG.sml
ViewVC logotype

Annotation of /sml/trunk/src/MLRISC/scheduling/buildDDG.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 695 - (view) (download)

1 : leunga 695 (*
2 :     * This module builds the data dependence graph for acyclic scheduling.
3 :     *
4 :     * Notes:
5 :     * 1. Special source and sink nodes are added to each basic block.
6 :     * These nodes anchor live-in and live-out values.
7 :     * 2. If a block has a branch, then it is control dependent on the live-in
8 :     * node.
9 :     *
10 :     * -- Allen
11 :     *)
12 :    
13 :     functor SchedulerDDGBuilder
14 :     (structure DDG : SCHEDULER_DDG
15 :     structure CFG : CONTROL_FLOW_GRAPH
16 :     structure RTLProps : RTL_PROPERTIES
17 :     structure InsnProps : INSN_PROPERTIES
18 :     sharing InsnProps.I = RTLProps.I = DDG.I = CFG.I
19 :     ) : SCHEDULER_DDG_BUILDER =
20 :     struct
21 :    
22 :     structure DDG = DDG
23 :     structure CFG = CFG
24 :     structure RTL = RTLProps.RTL
25 :     structure G = Graph
26 :     structure I = CFG.I
27 :     structure C = I.C
28 :     structure SchedProps = DDG.SchedProps
29 :     structure HA = HashArray
30 :     structure A = Array
31 :     structure W8A = Word8Array
32 :     structure SL = SortedList
33 :    
34 :     exception BuildDDG
35 :    
36 :     fun error msg = MLRiscErrorMsg.error("BuildDDG",msg)
37 :    
38 :     val i2s = Int.toString
39 :    
40 :     (* Zero register magic! *)
41 :     val zeroTbl = W8A.array(C.firstPseudo, 0w0)
42 :     val _ = List.app (fn k =>
43 :     case C.zeroReg k of
44 :     SOME r => W8A.update(zeroTbl, r, 0w1)
45 :     | NONE => ()
46 :     ) C.cellkinds
47 :     fun isZero r = W8A.sub(zeroTbl, r) <> 0w0 handle _ => false
48 :    
49 :     exception Nothing
50 :    
51 :     fun buildDDG{cpu_info, cfg, numberOfInstructions, blockIdTbl} =
52 :     let val CFG as G.GRAPH cfg = cfg
53 :     (* The number of nodes <= instructions + livein + liveout per block *)
54 :     val M = numberOfInstructions + #order cfg () * 2
55 :     val DDG as G.GRAPH ddg = DDG.newDDG M
56 :     val globalInfo = DDG.globalInfo DDG
57 :    
58 :     (* Extract instruction properties *)
59 :     val SchedProps.CPU_INFO{defUse, ...} = cpu_info
60 :    
61 :     (* Regmap magic! *)
62 :     val regmap = Intmap.mapInt(CFG.regmap CFG)
63 :     val regmapDefs = map (fn (r,l) => (regmap r,l))
64 :     val regmapUses = map regmap
65 :     fun simplifyCopy(instr, dst, src) =
66 :     let fun loop([], [], dst', src') = (dst', src')
67 :     | loop((d,l)::dst, s::src, dst', src') =
68 :     let val d = regmap d and s = regmap s
69 :     in if d = s then loop(dst, src, dst', src')
70 :     else loop(dst, src, (d,l)::dst', s::src')
71 :     end
72 :     | loop _ = error "simplifyCopy"
73 :     val (dst, src) = loop(dst, src, [], [])
74 :    
75 :     (* add the copy temporary! *)
76 :     val dst = case dst of
77 :     [] => dst
78 :     | _ => case InsnProps.moveTmpR instr of
79 :     SOME r => (regmap r,~1)::dst
80 :     | _ => dst
81 :     in (dst, src)
82 :     end
83 :    
84 :     (* Edge constructors *)
85 :     (* memory *)
86 :     fun m_flow(m,l) = DDG.EDGE{l=l, r=m, d=DDG.MEM_FLOW}
87 :     val m_anti = DDG.EDGE{l= ~1, r= ~1, d=DDG.MEM_ANTI}
88 :     val m_output = DDG.EDGE{l=0, r= ~1, d=DDG.MEM_OUTPUT}
89 :     (* register *)
90 :     fun flow(r,l) = DDG.EDGE{l=l, r=r, d=DDG.FLOW}
91 :     val output = DDG.EDGE{l=0, r= ~1, d=DDG.OUTPUT}
92 :     val anti = DDG.EDGE{l= ~1, r= ~1, d=DDG.ANTI}
93 :     (* control dependence *)
94 :     fun c_flow(r,l) = DDG.EDGE{l=l, r=r, d=DDG.CTRL}
95 :     val c_dep = DDG.EDGE{l= ~1, r= ~1, d=DDG.CTRL}
96 :     val c_output = DDG.EDGE{l=0, r= ~1, d=DDG.CTRL}
97 :     val c_anti = DDG.EDGE{l= ~1, r= ~1, d=DDG.CTRL_ANTI}
98 :    
99 :     (* How to make a new edge *)
100 :     val newEdge = #add_edge ddg
101 :     (* val newEdge = fn (i,j,e) => (print(i2s i^"->"^i2s j^" "^DDG.edgeToString e^"\n"); newEdge(i,j,e)) handle e => raise e *)
102 :    
103 :     (* A table of definitions and uses indexed by block *)
104 :     val defUseTbl = HA.array'(13, fn _ => raise BuildDDG)
105 :    
106 :     (* Create nodes for block b *)
107 :     fun createNodes(id, b, [], ops) = (id, ops)
108 :     | createNodes(id, b, instr::instrs, ops) =
109 :     let val (d, u) = defUse instr
110 :     fun newNode(defs, uses) =
111 :     let val node = DDG.NODE{b=b,instr=instr,defs=defs,uses=uses}
112 :     in #add_node ddg (id, node);
113 :     createNodes(id+1, b, instrs, (id, node)::ops)
114 :     end
115 :     in case InsnProps.instrKind instr of
116 :     InsnProps.IK_COPY =>
117 :     (case simplifyCopy(instr, d, u) of
118 :     ([], []) => createNodes(id, b, instrs, ops)
119 :     | (d, u) => newNode(d, u)
120 :     )
121 :     | _ => newNode(regmapDefs d, regmapUses u)
122 :     end
123 :    
124 :     (* Scan one block; ops are in forward order *)
125 :     fun scanBlock{ops,liveIn=(liveIn,_),defTbl,useTbl} =
126 :     let fun addOutputAndAnti j (r,_) =
127 :     (app (fn i => newEdge(i,j,anti)) (HA.sub(useTbl,r));
128 :     app (fn (i,e) => newEdge(i,j,output)) (HA.sub(defTbl,r))
129 :     )
130 :    
131 :     fun addFlow j r =
132 :     app (fn (i,e) => newEdge(i,j,e)) (HA.sub(defTbl,r))
133 :    
134 :     (* Update def/use *)
135 :     fun addDef i (r,l) =
136 :     if isZero r then ()
137 :     else
138 :     (HA.update(defTbl,r,[(i,flow(r,l))]); HA.update(useTbl,r,[]))
139 :    
140 :     fun addUse i r =
141 :     if isZero r then ()
142 :     else HA.update(useTbl,r,i::HA.sub(useTbl,r))
143 :    
144 :     fun scan [] = ()
145 :     | scan((i,DDG.NODE{instr, defs, uses,...})::rest) =
146 :     let val rtl = RTLProps.rtl instr
147 :     in if RTL.can'tMoveUp rtl then
148 :     newEdge(liveIn, i, c_dep)
149 :     else ();
150 :     app (addOutputAndAnti i) defs;
151 :     app (addFlow i) uses;
152 :     (* update defs/uses *)
153 :     app (addUse i) uses;
154 :     app (addDef i) defs;
155 :     scan rest
156 :     end
157 :     in scan ops
158 :     end
159 :    
160 :    
161 :     val blockId = ref 0
162 :     val nodeId = ref 0
163 :     val blockMap = A.array(#order cfg (), 0)
164 :     val liveInMap = Intmap.new(13, Nothing)
165 :     val liveOutMap = Intmap.new(13, Nothing)
166 :     val specialMap = Intmap.new(32, Nothing)
167 :     val addSpecial = Intmap.add specialMap
168 :     val isSpecial = Intmap.mapWithDefault(specialMap, false)
169 :    
170 :     (* Process a basic block in topological order of the region:
171 :     * 1. create all the nodes in the DDG
172 :     * 2. add the edges
173 :     *)
174 :     fun processBlock(b,b' as CFG.BLOCK{insns,...}) =
175 :     let val bid = !blockId (* block id *)
176 :     val _ = A.update(blockMap, bid, b)
177 :     val _ = A.update(blockIdTbl, b, bid)
178 :     val _ = blockId := bid + 1
179 :    
180 :     fun createNode(instr, defs, uses) =
181 :     let val node = (!nodeId,
182 :     DDG.NODE{instr=instr,b=bid,defs=defs,uses=uses})
183 :     in nodeId := !nodeId + 1;
184 :     #add_node ddg node;
185 :     node
186 :     end
187 :    
188 :     (* Create the nodes *)
189 :     val (newNodeId, ops) = createNodes(!nodeId, bid, !insns, [])
190 :     val _ = nodeId := newNodeId
191 :    
192 :     val revAppend = List.revAppend
193 :    
194 :     val defs = HA.array(13, [])
195 :     val uses = HA.array(13, [])
196 :    
197 :     (* edge Y->X is an internal region edge
198 :     * merge definition and uses from Y => X
199 :     *)
200 :     fun mergeDefUse(Y,X,_) =
201 :     let val {defTbl, useTbl} = HA.sub(defUseTbl, Y)
202 :     in HA.appi (fn (r,es) =>
203 :     HA.update(defs, r, revAppend(es, HA.sub(defs, r))))
204 :     (defTbl, 0, NONE);
205 :     HA.appi (fn (r,is) =>
206 :     HA.update(uses, r, revAppend(is, HA.sub(uses, r))))
207 :     (useTbl, 0, NONE)
208 :     end
209 :    
210 :     fun addCtrlDepEdge(i, j) = newEdge(i,j,c_dep)
211 :    
212 :     (* Add a live-in node for a block that summarizes the
213 :     * values that are coming live-in from side-exits
214 :     *)
215 :     fun addLiveIn X =
216 :     let val entry_edges = #entry_edges cfg X
217 :     val liveIn =
218 :     SL.uniq(foldr (fn ((Y,_,_),S) =>
219 :     let val CFG.BLOCK{annotations,...} = #node_info cfg Y
220 :     in case #get DDG.LIVENESS (!annotations) of
221 :     SOME{liveOut, ...} => revAppend(liveOut,S)
222 :     | NONE => S
223 :     end) [] entry_edges)
224 :     val liveInNode as (i,_) =
225 :     createNode(SchedProps.source,
226 :     map (fn r => (r,~1)) liveIn, [])
227 :     val _ = Intmap.add liveInMap (bid, liveInNode)
228 :     val _ = addSpecial(i, true)
229 :     fun addOutputAndAnti j r =
230 :     (app (fn i => if isSpecial j then ()
231 :     else newEdge(i,j,anti)) (HA.sub(uses,r));
232 :     app (fn (i,e) =>
233 :     if isSpecial i then ()
234 :     else newEdge(i,j,output)) (HA.sub(defs,r))
235 :     )
236 :     in app (addOutputAndAnti i) liveIn;
237 :     app (fn r => HA.update(defs, r,
238 :     (i,DDG.EDGE{l= ~1,r=r,d=DDG.LIVEIN})::HA.sub(defs, r)))
239 :     liveIn;
240 :     liveInNode
241 :     end
242 :    
243 :     val _ = app mergeDefUse (#in_edges cfg b)
244 :     val liveInNode = addLiveIn b
245 :    
246 :     (* Add a live-out node for a block that summarizes the
247 :     * values that are going live-out from side-exits
248 :     *)
249 :     fun addLiveOut X =
250 :     (case #exit_edges cfg X of
251 :     exit_edges =>
252 :     let fun createLiveOutNode(liveOut) =
253 :     let val node as (i, _) =
254 :     createNode(SchedProps.sink, [], liveOut)
255 :     in Intmap.add liveOutMap (bid, node);
256 :     addSpecial(i, true);
257 :     node
258 :     end
259 :     val liveOut =
260 :     if List.exists
261 :     (fn (_,_,CFG.EDGE{k,...}) => k = CFG.EXIT)
262 :     exit_edges
263 :     then
264 :     let val CFG.BLOCK{annotations,...} = #node_info cfg X
265 :     in case #get DDG.LIVENESS (!annotations) of
266 :     SOME{liveOut, ...} => liveOut
267 :     | NONE => error "missing live out"
268 :     end
269 :     else
270 :     SL.uniq(foldr (fn ((_,Y,_),S) =>
271 :     let val CFG.BLOCK{annotations,...} = #node_info cfg Y
272 :     in case #get DDG.LIVENESS (!annotations) of
273 :     SOME{liveIn, ...} => revAppend(liveIn,S)
274 :     | NONE => S
275 :     end) [] exit_edges)
276 :    
277 :     val liveOutNode as (i,_) =
278 :     case !insns of
279 :     [] => createLiveOutNode(liveOut)
280 :     | jmp::_ =>
281 :     case InsnProps.instrKind jmp of
282 :     InsnProps.IK_JUMP =>
283 :     (* add a control dependence edge to the liveIn *)
284 :     let val jmpNode as (j,_) = List.last ops
285 :     in addCtrlDepEdge(#1 liveInNode, j);
286 :     jmpNode
287 :     end
288 :     | _ => createLiveOutNode(liveOut)
289 :     fun addUse i r =
290 :     if isZero r then ()
291 :     else HA.update(uses,r,i::HA.sub(uses,r))
292 :     fun addLiveOut j r =
293 :     app (fn (i,DDG.EDGE{l,r,...}) =>
294 :     newEdge(i,j,DDG.EDGE{l=l,r=r,d=DDG.LIVEOUT}))
295 :     (HA.sub(defs,r))
296 :    
297 :     in app (addLiveOut i) liveOut;
298 :     addLiveOutCtrlDep i;
299 :     app (addUse i) liveOut
300 :     end
301 :     )
302 :    
303 :     (* Add control dependences edges from all the instructions
304 :     * to the live-out node
305 :     *)
306 :     and addLiveOutCtrlDep(j) =
307 :     app (fn node as (i,_) =>
308 :     if i = j then () else addCtrlDepEdge(i,j)
309 :     ) ops
310 :    
311 :     val _ = scanBlock{ops=ops, liveIn=liveInNode,
312 :     defTbl=defs, useTbl=uses};
313 :    
314 :     in addLiveOut b;
315 :     HA.update(defUseTbl, b, {defTbl=defs, useTbl=uses})
316 :     end
317 :    
318 :     (* Build the entire dag *)
319 :     fun buildDag() =
320 :     let val allNodes = #nodes cfg () (* must be in topological order! *)
321 :     in app processBlock allNodes
322 :     end
323 :    
324 :     in buildDag();
325 :     globalInfo :=
326 :     SOME{blockMap=blockMap, liveInMap=liveInMap, liveOutMap=liveOutMap};
327 :     DDG
328 :     end
329 :     end

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