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/mltree/mltree-rtl.sml
ViewVC logotype

Annotation of /sml/trunk/src/MLRISC/mltree/mltree-rtl.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 775 - (view) (download)

1 : leunga 591 (*
2 :     * Basic RTLs and query functions on these RTLs
3 :     *
4 :     * -- Allen
5 :     *)
6 : leunga 744 functor MLTreeRTL
7 :     (structure Util : MLTREE_UTILS
8 :     structure Rewrite : MLTREE_REWRITE
9 :     structure Fold : MLTREE_FOLD
10 :     sharing Util.T = Rewrite.T = Fold.T
11 :     ) : MLTREE_RTL =
12 : leunga 591 struct
13 : leunga 744
14 :     structure T = Util.T
15 :     structure Util = Util
16 :     structure Rewrite = Rewrite
17 :     structure Fold = Fold
18 :     structure W = Word
19 :     structure C = CellsBasis
20 : leunga 591
21 :     fun error msg = MLRiscErrorMsg.error("MLTreeRTL",msg)
22 :    
23 : leunga 744 datatype pos = IN of int | OUT of int | IO of int * int
24 :     datatype arity = ZERO | ONE | MANY
25 : leunga 591
26 : leunga 744 val itow = Word.fromInt
27 :     infix ||
28 :     val op || = W.orb
29 : leunga 591
30 : leunga 744 type ty = T.ty
31 :     type rtl = T.stm
32 :     type exp = T.rexp
33 :     type cond = T.ccexp
34 :     type var = T.var
35 : leunga 591 type hasher = T.hasher
36 :     type equality = T.equality
37 :     type printer = T.printer
38 :    
39 :    
40 : leunga 601 val hashRTL = Util.hashStm
41 :     val eqRTL = Util.eqStm
42 :     val showRTL = Util.show
43 :     val rtlToString = Util.stmToString
44 :     val expToString = Util.rexpToString
45 : leunga 591
46 : leunga 744 (*-----------------------------------------------------------------------
47 : leunga 606 * Attributes
48 : leunga 744 *-----------------------------------------------------------------------*)
49 : leunga 606 val A_TRAPPING = W.<<(0w1,0w1) (* may cause traps *)
50 :     val A_PINNED = W.<<(0w1,0w2) (* cannot be moved *)
51 :     val A_SIDEEFFECT = W.<<(0w1,0w3) (* has side effect *)
52 : leunga 591 val A_MUTATOR = W.<<(0w1,0w4)
53 :     val A_LOOKER = W.<<(0w1,0w5)
54 : leunga 606 val A_BRANCH = W.<<(0w1,0w6) (* conditional branch *)
55 :     val A_JUMP = W.<<(0w1,0w7) (* has control flow *)
56 : leunga 591 val A_PURE = 0wx0
57 : leunga 744 fun isOn(a,flag) = Word.andb(a,flag) <> 0w0
58 : leunga 591
59 : leunga 744 (*-----------------------------------------------------------------------
60 : leunga 591 * Create new RTL operators
61 : leunga 744 *-----------------------------------------------------------------------*)
62 : leunga 591 val hashCnt = ref 0w0
63 :     fun newHash() = let val h = !hashCnt in hashCnt := h + 0w124127; h end
64 : leunga 744 fun newOp{name,attribs} = {name=name,attribs=ref attribs,hash=newHash()}
65 : leunga 591
66 : leunga 744 (*-----------------------------------------------------------------------
67 : leunga 591 * Reduce a RTL to compiled internal form
68 : leunga 744 *-----------------------------------------------------------------------*)
69 : leunga 591 fun reduce rtl =
70 : leunga 744 let
71 :     in rtl
72 : leunga 591 end
73 :    
74 : leunga 744 (*-----------------------------------------------------------------------
75 : leunga 606 * Collect attributes
76 : leunga 744 *-----------------------------------------------------------------------*)
77 : leunga 606 fun attribsOf rtl =
78 :     let fun stm(T.STORE _,a) = a || (A_SIDEEFFECT || A_MUTATOR)
79 :     | stm(T.JMP _, a) = a || (A_JUMP || A_SIDEEFFECT)
80 :     | stm(T.IF _, a) = a || (A_BRANCH || A_JUMP || A_SIDEEFFECT)
81 :     | stm(T.RET _, a) = a || (A_JUMP || A_SIDEEFFECT)
82 :     | stm(T.CALL _, a) = a || A_SIDEEFFECT
83 : leunga 744 | stm(T.ASSIGN(_,T.$(_,C.MEM,addr),value),a) =
84 :     a || (A_SIDEEFFECT || A_MUTATOR)
85 : leunga 606 | stm(_, a) = a
86 :     fun rexp(T.ADDT _,a) = a || A_TRAPPING
87 :     | rexp(T.SUBT _,a) = a || A_TRAPPING
88 :     | rexp(T.MULT _,a) = a || A_TRAPPING
89 :     | rexp(T.DIVT _,a) = a || A_TRAPPING
90 :     | rexp(T.REMT _,a) = a || A_TRAPPING
91 :     | rexp(T.LOAD _,a) = a || A_LOOKER
92 : leunga 744 | rexp(T.$(_,C.MEM,_),a) = a || A_LOOKER
93 : leunga 606 | rexp(_, a) = a
94 :     fun fexp(_, a) = a
95 :     fun ccexp(_, a) = a
96 :     in #stm (Fold.fold{stm=stm,rexp=rexp, fexp=fexp, ccexp=ccexp}) rtl
97 : leunga 591 end
98 :    
99 : leunga 744
100 :     (*-----------------------------------------------------------------------
101 :     * Create a uniq RTL
102 :     *-----------------------------------------------------------------------*)
103 :     fun new(rtl) =
104 :     let val rtl = reduce rtl
105 :     val attribs = attribsOf(rtl, A_PURE)
106 :     val rtl =
107 :     case rtl of
108 :     T.COPY _ => rtl
109 :     | _ => T.RTL{e=rtl,hash=newHash(),attribs=ref attribs}
110 :     in rtl
111 :     end
112 :    
113 :     val COPY = T.COPY(0,[],[])
114 :     val JMP = new(T.JMP(T.PARAM 0,[]))
115 :    
116 :    
117 : leunga 695 fun pin(x as T.RTL{attribs, ...}) =
118 :     (attribs := (!attribs || A_PINNED); x)
119 : leunga 657 | pin _ = error "pin"
120 :    
121 : leunga 744 (*-----------------------------------------------------------------------
122 :     * Type queries
123 :     *-----------------------------------------------------------------------*)
124 :     fun hasSideEffect(T.RTL{attribs, ...}) = isOn(!attribs, A_SIDEEFFECT)
125 :     | hasSideEffect _ = false
126 :     fun isConditionalBranch(T.RTL{attribs, ...}) = isOn(!attribs,A_BRANCH)
127 :     | isConditionalBranch _ = false
128 :     fun isJump(T.RTL{attribs, ...}) = isOn(!attribs,A_JUMP)
129 :     | isJump(T.JMP _) = true
130 :     | isJump _ = false
131 :     fun isLooker(T.RTL{attribs, ...}) = isOn(!attribs,A_LOOKER)
132 :     | isLooker _ = false
133 : leunga 624
134 : leunga 744 (*-----------------------------------------------------------------------
135 :     * Def/use queries
136 :     *-----------------------------------------------------------------------*)
137 :     fun defUse rtl =
138 :     let fun contains x = List.exists(fn y => Util.eqRexp(x,y))
139 :     fun diff(A,B) = List.filter (fn z => not(contains z B)) A
140 :     fun uniq([], l) = rev l
141 :     | uniq(x::xs, l) = if contains x l then uniq(xs,l) else uniq(xs,x::l)
142 :    
143 :     fun stm(T.ASSIGN(_,x, y), d, u) =
144 :     let val (d, u) = lhs(x, d, u)
145 :     in rhs(y, d, u) end
146 :     | stm(T.COPY _, d, u) = (d, u) (* XXX *)
147 :     | stm(T.RET _, d, u) = (d, u)
148 :     | stm(T.RTL{e, ...}, d, u) = stm(e, d, u)
149 :     | stm(T.JMP(e,_), d, u) = rhs(e, d, u)
150 :     | stm(T.IF(x,y,z), d, u) =
151 :     let val (d, u) = cond(x, d, u)
152 :     val (d1, u) = stm(y, [], u)
153 :     val (d2, u) = stm(z, [], u)
154 :     val u1 = diff(d1,d2)
155 :     val u2 = diff(d2,d1)
156 :     in (d @ d1 @ d2, u @ u1 @ u2)
157 :     end
158 :     | stm(T.SEQ rtls, d, u) = stms(rtls, d, u)
159 :     | stm(T.CALL{funct,...}, d, u) = rhs(funct, d, u)
160 :     | stm(rtl, d, u) = error("defUse.stm: "^rtlToString rtl)
161 :    
162 :     and stms([], d, u) = (d, u)
163 :     | stms(s::ss, d, u) = let val (d, u) = stm(s, d, u)
164 :     in stms(ss, d, u) end
165 :    
166 :     and rhs(T.LI _, d, u) = (d, u)
167 :     | rhs(x as T.ARG _, d, u) = (d, x::u)
168 :     | rhs(x as T.PARAM _, d, u) = (d, x::u)
169 :     | rhs(T.ADD(_,x,y), d, u) = binOp(x, y, d, u)
170 :     | rhs(T.SUB(_,x,y), d, u) = binOp(x, y, d, u)
171 :     | rhs(T.MULS(_,x,y), d, u) = binOp(x, y, d, u)
172 :     | rhs(T.MULU(_,x,y), d, u) = binOp(x, y, d, u)
173 :     | rhs(T.DIVS(_,x,y), d, u) = binOp(x, y, d, u)
174 :     | rhs(T.DIVU(_,x,y), d, u) = binOp(x, y, d, u)
175 :     | rhs(T.QUOTS(_,x,y), d, u) = binOp(x, y, d, u)
176 :     | rhs(T.REMS(_,x,y), d, u) = binOp(x, y, d, u)
177 :     | rhs(T.REMU(_,x,y), d, u) = binOp(x, y, d, u)
178 :     | rhs(T.ADDT(_,x,y), d, u) = binOp(x, y, d, u)
179 :     | rhs(T.SUBT(_,x,y), d, u) = binOp(x, y, d, u)
180 :     | rhs(T.MULT(_,x,y), d, u) = binOp(x, y, d, u)
181 :     | rhs(T.DIVT(_,x,y), d, u) = binOp(x, y, d, u)
182 :     | rhs(T.REMT(_,x,y), d, u) = binOp(x, y, d, u)
183 :     | rhs(T.SLL(_,x,y), d, u) = binOp(x, y, d, u)
184 :     | rhs(T.SRL(_,x,y), d, u) = binOp(x, y, d, u)
185 :     | rhs(T.SRA(_,x,y), d, u) = binOp(x, y, d, u)
186 :     | rhs(T.ANDB(_,x,y), d, u) = binOp(x, y, d, u)
187 :     | rhs(T.ORB(_,x,y), d, u) = binOp(x, y, d, u)
188 :     | rhs(T.XORB(_,x,y), d, u) = binOp(x, y, d, u)
189 :     | rhs(T.EQVB(_,x,y), d, u) = binOp(x, y, d, u)
190 :     | rhs(T.NEG(_,x), d, u) = rhs(x, d, u)
191 :     | rhs(T.NEGT(_,x), d, u) = rhs(x, d, u)
192 :     | rhs(T.NOTB(_,x), d, u) = rhs(x, d, u)
193 :     | rhs(T.SX(_,_,x), d, u) = rhs(x, d, u)
194 :     | rhs(T.ZX(_,_,x), d, u) = rhs(x, d, u)
195 :     | rhs(x as T.$(_,_,T.ARG _), d, u) = (d, x::u)
196 :     | rhs(x as T.$(_,_,T.PARAM _), d, u) = (d, x::u)
197 :     | rhs(x as T.$(_,_,e), d, u) = rhs(e, d, x::u)
198 :     | rhs(T.CVTF2I(_,_,_,x), d, u) = fexp(x, d, u)
199 :     | rhs(T.OP(_,_,es), d, u) = rexps(es, d, u)
200 :     | rhs(T.COND(_,x,y,z), d, u) =
201 :     let val (d, u) = cond(x, d, u)
202 :     in binOp(y, z, d, u) end
203 :     | rhs(T.BITSLICE(_,_,e), d, u) = rhs(e, d, u)
204 :     | rhs(T.???, d, u) = (d, u)
205 :     | rhs(e, d, u) = error("defUse.rhs: "^Util.rexpToString e)
206 :    
207 :     and binOp(x, y, d, u) =
208 :     let val (d, u) = rhs(x, d, u)
209 :     in rhs(y, d, u) end
210 :    
211 :     and rexps([], d, u) = (d, u)
212 :     | rexps(e::es, d, u) =
213 :     let val (d, u) = rhs(e, d, u)
214 :     in rexps(es, d, u) end
215 :    
216 :     and lhs(x as T.$(_,_,T.ARG _), d, u) = (x::d, u)
217 :     | lhs(x as T.$(_,_,T.PARAM _), d, u) = (x::d, u)
218 :     | lhs(x as T.$(_,_,addr), d, u) = rhs(addr, x::d, u)
219 :     | lhs(x as T.ARG _, d, u) = (x::d, u)
220 :     | lhs(x as T.PARAM _, d, u) = (x::d, u)
221 :     | lhs(T.???, d, u) = (d, u)
222 :     | lhs(e, d, u) = error("defUse.lhs: "^Util.rexpToString e)
223 :    
224 :     and fexp(T.FADD(_, x, y), d, u) = fbinOp(x, y, d, u)
225 :     | fexp(T.FSUB(_, x, y), d, u) = fbinOp(x, y, d, u)
226 :     | fexp(T.FMUL(_, x, y), d, u) = fbinOp(x, y, d, u)
227 :     | fexp(T.FDIV(_, x, y), d, u) = fbinOp(x, y, d, u)
228 :     | fexp(T.FCOPYSIGN(_, x, y), d, u) = fbinOp(x, y, d, u)
229 :     | fexp(T.FCOND(_, x, y, z), d, u) =
230 :     let val (d, u) = cond(x, d, u)
231 :     in fbinOp(y, z, d, u) end
232 :     | fexp(T.FSQRT(_, x), d, u) = fexp(x, d, u)
233 :     | fexp(T.FABS(_, x), d, u) = fexp(x, d, u)
234 :     | fexp(T.FNEG(_, x), d, u) = fexp(x, d, u)
235 :     | fexp(T.CVTI2F(_, _, x), d, u) = rhs(x, d, u)
236 :     | fexp(e, d, u) = error("defUse.fexp: "^Util.fexpToString e)
237 :    
238 :     and fbinOp(x, y, d, u) =
239 :     let val (d, u) = fexp(x, d, u)
240 :     in fexp(y, d, u) end
241 :    
242 :     and cond(T.CMP(_,_,x,y), d, u) = binOp(x, y, d, u)
243 :     | cond(T.FCMP(_,_,x,y), d, u) = fbinOp(x, y, d, u)
244 :     | cond(T.TRUE, d, u) = (d, u)
245 :     | cond(T.FALSE, d, u) = (d, u)
246 :     | cond(T.NOT x, d, u) = cond(x, d, u)
247 :     | cond(T.AND(x, y), d, u) = cond2(x, y, d, u)
248 :     | cond(T.OR(x, y), d, u) = cond2(x, y, d, u)
249 :     | cond(T.XOR(x, y), d, u) = cond2(x, y, d, u)
250 :     | cond(T.EQV(x, y), d, u) = cond2(x, y, d, u)
251 :     | cond(e, d, u) = error("defUse.cond: "^Util.ccexpToString e)
252 :    
253 :     and cond2(x, y, d, u) =
254 :     let val (d, u) = cond(x, d, u)
255 :     in cond(y, d, u) end
256 :    
257 :     val (d, u) = stm(rtl, [], [])
258 :    
259 :     in (uniq(d, []), uniq(u, []))
260 :     end
261 :    
262 :     (*-----------------------------------------------------------------------
263 :     * Giving definitions and uses. Find out the naming constraints.
264 :     *-----------------------------------------------------------------------*)
265 :     fun namingConstraints(defs, uses) =
266 :     let fun collectFixed((x as T.$(_,_,T.LI r))::xs, fixed, rest) =
267 : leunga 775 collectFixed(xs, (x, IntInf.toInt r)::fixed, rest)
268 : leunga 744 | collectFixed(x::xs, fixed, rest) =
269 :     collectFixed(xs, fixed, x::rest)
270 :     | collectFixed([], fixed, rest) = (fixed, rest)
271 :     val (fixedUses, otherUses) = collectFixed(uses, [], [])
272 :     val (fixedDefs, otherDefs) = collectFixed(defs, [], [])
273 :     val fixed =
274 :     List.filter
275 :     (fn x => List.exists (fn y => Util.eqRexp(x,y)) otherUses)
276 :     otherDefs
277 :     in {fixedUses=fixedUses,
278 :     fixedDefs=fixedDefs,
279 :     twoAddress=fixed
280 :     }
281 :     end
282 :    
283 :     (*-----------------------------------------------------------------------
284 :     * Assign positions to each argument
285 :     *-----------------------------------------------------------------------*)
286 :     fun argPos rtl =
287 :     let val (defs, uses) = defUse rtl
288 :     fun pos([], i, ds) = ds
289 :     | pos(d::defs, i, ds) = pos(defs, i+1, (d,i)::ds)
290 :     val ds = pos(defs, 0, [])
291 :     val us = pos(uses, 0, [])
292 :     in (ds, us)
293 :     end
294 :    
295 :     exception NotAnArgument
296 :    
297 :     fun argOf rtl =
298 :     let val (defs, uses) = argPos rtl
299 :     fun find(this,(x as (T.$(_,_,T.ARG(_,_,name)),_))::xs) =
300 :     if this = name then SOME x else find(this, xs)
301 :     | find(this,(x as (T.ARG(_,_,name),_))::xs) =
302 :     if this = name then SOME x else find(this, xs)
303 :     | find(this,_::xs) = find(this, xs)
304 :     | find(this,[]) = NONE
305 :     fun lookup name =
306 :     case (find(name,defs), find(name,uses)) of
307 :     (SOME(x,i),SOME(_,j)) => (x,IO(i,j))
308 :     | (SOME(x, i), NONE) => (x,OUT i)
309 :     | (NONE, SOME(x, i)) => (x,IN i)
310 :     | (NONE, NONE) => raise NotAnArgument
311 :     in lookup
312 :     end
313 :    
314 :     (*-----------------------------------------------------------------------
315 :     * Return the arity of an argument
316 :     *-----------------------------------------------------------------------*)
317 :     fun arity(T.ARG _) = MANY
318 :     | arity(T.$(_,C.MEM,_)) = MANY
319 :     | arity(T.$(_,_,_)) = ONE
320 :     | arity _ = raise NotAnArgument
321 :    
322 :     fun nonConstArity(T.ARG _) = MANY
323 :     | nonConstArity(T.$(_,C.MEM,_)) = MANY
324 :     | nonConstArity(T.$(_,_,_)) = ONE
325 :     | nonConstArity _ = raise NotAnArgument
326 :    
327 :     (*-----------------------------------------------------------------------
328 :     * Code motion queries
329 :     *-----------------------------------------------------------------------*)
330 : leunga 624 fun can'tMoveUp(T.RTL{attribs, ...}) =
331 : leunga 695 isOn(!attribs, A_SIDEEFFECT || A_TRAPPING || A_PINNED)
332 : leunga 624 | can'tMoveUp(T.PHI _) = true
333 : leunga 775 | can'tMoveUp(T.SOURCE) = true
334 :     | can'tMoveUp(T.SINK) = true
335 : leunga 624 | can'tMoveUp _ = false
336 :    
337 :     fun can'tMoveDown(T.PHI _) = true
338 : leunga 775 | can'tMoveDown(T.SOURCE) = true
339 :     | can'tMoveDown(T.SINK) = true
340 : leunga 624 | can'tMoveDown(T.RTL{attribs, ...}) =
341 : leunga 695 isOn(!attribs, A_SIDEEFFECT || A_BRANCH || A_JUMP || A_TRAPPING ||
342 : leunga 657 A_PINNED ||
343 :     A_LOOKER (* can be avoided with pure loads! XXX *))
344 : leunga 744 | can'tMoveDown rtl = error("can'tMoveDown: "^rtlToString rtl)
345 : leunga 624
346 : leunga 657 fun pinned(T.RTL{attribs, ...}) =
347 : leunga 695 isOn(!attribs, A_SIDEEFFECT || A_TRAPPING || A_PINNED)
348 : leunga 657 | pinned(T.PHI _) = true
349 : leunga 775 | pinned(T.SOURCE) = true
350 :     | pinned(T.SINK) = true
351 : leunga 657 | pinned _ = false
352 : leunga 606 fun can'tBeRemoved(T.RTL{attribs, ...}) =
353 : leunga 695 isOn(!attribs, A_SIDEEFFECT || A_BRANCH || A_JUMP)
354 : leunga 775 | can'tBeRemoved(T.SOURCE) = true
355 :     | can'tBeRemoved(T.SINK) = true
356 : leunga 606 | can'tBeRemoved _ = false
357 : leunga 744
358 : leunga 591 end

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