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-simplify.sml
ViewVC logotype

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

Parent Directory Parent Directory | Revision Log Revision Log


Revision 475 - (view) (download)
Original Path: sml/branches/SMLNJ/src/MLRISC/mltree/mltree-simplify.sml

1 : monnier 467 (*
2 :     * Performs simple local optimizations.
3 :     *)
4 :     functor MLTreeSimplifier(T : MLTREE) : MLTREE_SIMPLIFIER =
5 :     struct
6 :    
7 :     structure T = T
8 :     structure W = Word32
9 :     structure I = Int32
10 :    
11 :     datatype const = CONST of W.word | NONCONST
12 :     datatype cond = TRUE | FALSE | UNKNOWN
13 :    
14 :     val NOP = T.COPY(32,[],[])
15 :     val ALWAYS_TRUE = T.CMP(32, T.EQ, T.LI 0, T.LI 0)
16 :     val ALWAYS_FALSE = T.CMP(32, T.NE, T.LI 0, T.LI 0)
17 :    
18 :     val zero = 0w0 : W.word
19 :     val one = 0w1 : W.word
20 :    
21 :     exception Precison
22 :    
23 :     (* Get constant value *)
24 :     fun valOf(T.LI i) = CONST(W.fromInt i)
25 :     | valOf(T.LI32 w) = CONST w
26 :     | valOf(T.MARK(e,_)) = valOf e
27 :     | valOf e = NONCONST
28 :    
29 :     fun bits(ty,w) =
30 :     let val mask = W.<<(0w1,Word.fromInt ty)-0w1
31 :     in if mask = zero then raise Precison
32 :     else W.andb(w,mask)
33 :     end
34 :    
35 :     fun isSigned(ty,w) =
36 :     let val signBit = W.<<(0w1,Word.fromInt(ty-1))
37 :     in W.andb(signBit,w) <> 0w0 end
38 :    
39 :     fun extend(ty,false,w) = w
40 :     | extend(ty,true,w) =
41 :     let val signBit = W.<<(0w1,Word.fromInt(ty-1))
42 :     in if W.andb(signBit,w) <> 0w0 then
43 :     let val shift = Word.fromInt(W.wordSize-ty)
44 :     in W.~>>(W.<<(w, shift), shift) end
45 :     else w
46 :     end
47 :    
48 :     fun compute (signed, f) (e,ty,a,b) =
49 :     case (valOf a, valOf b) of
50 :     (CONST a, CONST b) =>
51 :     (let val a = bits(ty,a)
52 :     val b = bits(ty,b)
53 :     val w = extend(ty,signed,bits(ty,f(a,b)))
54 :     in T.LI(W.toIntX w) handle _ => T.LI32 w end
55 :     handle _ => e
56 :     )
57 :     | _ => e
58 :    
59 :     fun computeUnary (signed, f) (e,ty,a) =
60 :     case (valOf a) of
61 :     (CONST a) =>
62 :     (let val a = bits(ty,a)
63 :     val w = extend(ty,signed,bits(ty,f(a)))
64 :     in T.LI(W.toIntX w) handle _ => T.LI32 w end
65 :     handle _ => e
66 :     )
67 :     | _ => e
68 :    
69 :     fun computeTrap f (e,ty,a,b) =
70 :     case (a,b) of
71 :     (T.LI a, T.LI b) =>
72 :     (let val x = f(a,b)
73 :     val range = Word.toInt(Word.<<(0w1,Word.fromInt ty))
74 :     in if x >= range orelse x < ~range then e
75 :     else T.LI x
76 :     end handle _ => e
77 :     )
78 :     | _ => e
79 :    
80 :     val sll = compute (false,fn (a,b) => W.<<(a,Word.fromInt(W.toIntX(b))))
81 :     val srl = compute (false,fn (a,b) => W.>>(a,Word.fromInt(W.toIntX(b))))
82 :     val sra = compute (true,fn (a,b) => W.~>>(a,Word.fromInt(W.toIntX(b))))
83 :     val andb = compute (false,W.andb)
84 :     val orb = compute (false,W.orb)
85 :     val xorb = compute (false,W.xorb)
86 :     val notb = computeUnary (false,W.notb)
87 :     val add = compute (true,W.+)
88 :     val addt = computeTrap (Int.+)
89 :     val sub = compute (true,W.-)
90 :     val subt = computeTrap (Int.-)
91 :     val muls = compute (true,W.* )
92 :     val mulu = compute (false,W.* )
93 :     val mult = computeTrap (Int.* )
94 :     val divs = compute (true,W.div)
95 :     val divu = compute (false,W.div)
96 :     val divt = computeTrap (Int.div)
97 :     val rems = compute (true,W.mod)
98 :     val remu = compute (false,W.mod)
99 :     val remt = computeTrap (Int.mod)
100 :    
101 :     (* Evaluate an integer comparison *)
102 :     fun cmp (signed,rel) (ty,a,b) =
103 :     let val a = bits(ty,a)
104 :     val b = bits(ty,b)
105 :     in if signed then
106 :     (case (isSigned(ty, a),isSigned(ty, b)) of
107 :     (false, false) => rel(a,b)
108 :     | (false, true) => rel(one,zero)
109 :     | (true, false) => rel(zero,one)
110 :     | (true, true) => rel(b,a)
111 :     )
112 :     else rel(a,b)
113 :     end
114 :    
115 :     val gt = cmp (true,W.>)
116 :     val lt = cmp (true,W.<)
117 :     val ge = cmp (true,W.>=)
118 :     val le = cmp (true,W.<=)
119 :     val gtu = cmp (false,W.>)
120 :     val ltu = cmp (false,W.<)
121 :     val geu = cmp (false,W.>=)
122 :     val leu = cmp (false,W.<=)
123 :    
124 :     (* Evaluate a comparison *)
125 :     fun evalcc(T.CMP(ty,cond,a,b)) =
126 :     (case (cond,valOf a,valOf b) of
127 :     (T.EQ,CONST i,CONST j) => if i = j then TRUE else FALSE
128 :     | (T.NE,CONST i,CONST j) => if i <> j then TRUE else FALSE
129 :     | (T.GT,CONST i,CONST j) => if gt(ty,i,j) then TRUE else FALSE
130 :     | (T.LT,CONST i,CONST j) => if lt(ty,i,j) then TRUE else FALSE
131 :     | (T.GE,CONST i,CONST j) => if ge(ty,j,i) then TRUE else FALSE
132 :     | (T.LE,CONST i,CONST j) => if le(ty,j,i) then TRUE else FALSE
133 :     | (T.GTU,CONST i,CONST j) => if gtu(ty,i,j) then TRUE else FALSE
134 :     | (T.LTU,CONST i,CONST j) => if ltu(ty,i,j) then TRUE else FALSE
135 :     | (T.GEU,CONST i,CONST j) => if geu(ty,i,j) then TRUE else FALSE
136 :     | (T.LEU,CONST i,CONST j) => if leu(ty,i,j) then TRUE else FALSE
137 :     | (T.GEU,_,CONST 0w0) => TRUE
138 :     | (T.GTU,CONST 0w0,_) => FALSE
139 :     | (T.LTU,_,CONST 0w0) => FALSE
140 :     | (T.LEU,CONST 0w0,_) => TRUE
141 :     | _ => UNKNOWN
142 :     )
143 :     | evalcc(T.CCMARK(e,_)) = evalcc e
144 :     | evalcc _ = UNKNOWN
145 :    
146 :     fun sim e =
147 :     let (* traverse and simplify *)
148 :     val e =
149 :     case e of
150 :     T.ADD(ty,a,b) => T.ADD(ty, sim a, sim b)
151 :     | T.SUB(ty,a,b) => T.SUB(ty, sim a, sim b)
152 :     | T.MULS(ty,a,b) => T.MULS(ty, sim a, sim b)
153 :     | T.DIVS(ty,a,b) => T.DIVS(ty, sim a, sim b)
154 :     | T.REMS(ty,a,b) => T.REMS(ty, sim a, sim b)
155 :     | T.MULU(ty,a,b) => T.MULU(ty, sim a, sim b)
156 :     | T.DIVU(ty,a,b) => T.DIVU(ty, sim a, sim b)
157 :     | T.REMU(ty,a,b) => T.REMU(ty, sim a, sim b)
158 :     | T.ADDT(ty,a,b) => T.ADDT(ty, sim a, sim b)
159 :     | T.SUBT(ty,a,b) => T.SUBT(ty, sim a, sim b)
160 :     | T.MULT(ty,a,b) => T.MULT(ty, sim a, sim b)
161 :     | T.DIVT(ty,a,b) => T.DIVT(ty, sim a, sim b)
162 :     | T.REMT(ty,a,b) => T.REMT(ty, sim a, sim b)
163 :     | T.ANDB(ty,a,b) => T.ANDB(ty, sim a, sim b)
164 :     | T.ORB(ty,a,b) => T.ORB(ty, sim a, sim b)
165 :     | T.XORB(ty,a,b) => T.XORB(ty, sim a, sim b)
166 :     | T.NOTB(ty,a) => T.NOTB(ty, sim a)
167 :     | T.SRA(ty,a,b) => T.SRA(ty, sim a, sim b)
168 :     | T.SRL(ty,a,b) => T.SRL(ty, sim a, sim b)
169 :     | T.SLL(ty,a,b) => T.SLL(ty, sim a, sim b)
170 : monnier 475 | T.CVTI2I(ty,ext,ty',a) => T.CVTI2I(ty,ext,ty',sim a)
171 :     | T.CVTF2I(ty,round,fty,a) => T.CVTF2I(ty,round,fty,simF a)
172 : monnier 467 | T.COND(ty,cc,a,b) => T.COND(ty, simCC cc, sim a, sim b)
173 :     | T.LOAD(ty,a,mem) => T.LOAD(ty, sim a, mem)
174 :     | T.LOAD_UNALIGNED(ty,a,mem) => T.LOAD_UNALIGNED(ty, sim a, mem)
175 :     | T.SEQ(stm,e) => T.SEQ(simStm stm, sim e)
176 : monnier 475 | T.EXT(ty, rext, es) => T.EXT(ty, rext, map sim es)
177 : monnier 467 | T.MARK(e,an) => T.MARK(sim e, an)
178 :     | e => e
179 :    
180 :     (* algebraic simplification and constant folding *)
181 :     fun ADD(e,f,ty,a,(T.LI 0 | T.LI32 0w0)) = a
182 :     | ADD(e,f,ty,(T.LI 0 | T.LI32 0w0),a) = a
183 :     | ADD(e,f,ty,a,b) = f(e,ty,a,b)
184 :     fun SUB(e,f,ty,a,(T.LI 0 | T.LI32 0w0)) = a
185 :     | SUB(e,f,ty,a,b) = f(e,ty,a,b)
186 :     fun MUL(e,f,ty,a,b as (T.LI 0 | T.LI32 0w0)) = b
187 :     | MUL(e,f,ty,a as (T.LI 0 | T.LI32 0w0),b) = a
188 :     | MUL(e,f,ty,a,(T.LI 1 | T.LI32 0w1)) = a
189 :     | MUL(e,f,ty,(T.LI 1 | T.LI32 0w1),b) = b
190 :     | MUL(e,f,ty,a,b) = f(e,ty,a,b)
191 :     fun DIV(e,f,ty,a,(T.LI 1 | T.LI32 0w1)) = a
192 :     | DIV(e,f,ty,(T.LI 1 | T.LI32 0w1),b) = b
193 :     | DIV(e,f,ty,a,b) = f(e,ty,a,b)
194 :     fun REM(e,f,ty,a,b) = f(e,ty,a,b)
195 :     fun ANDB(e,ty,a,b as (T.LI 0 | T.LI32 0w0)) = b
196 :     | ANDB(e,ty,a as (T.LI 0 | T.LI32 0w0),b) = a
197 :     | ANDB(e,ty,a,b) = andb(e,ty,a,b)
198 :     fun ORB(e,ty,a,(T.LI 0 | T.LI32 0w0)) = a
199 :     | ORB(e,ty,(T.LI 0 | T.LI32 0w0),b) = b
200 :     | ORB(e,ty,a,b) = orb(e,ty,a,b)
201 :     fun XORB(e,ty,a,(T.LI 0 | T.LI32 0w0)) = a
202 :     | XORB(e,ty,(T.LI 0 | T.LI32 0w0),b) = b
203 :     | XORB(e,ty,a,b) = xorb(e,ty,a,b)
204 :     fun NOTB(e,ty,a) = notb(e,ty,a)
205 :     fun SHIFT(e,f,ty,a,(T.LI 0 | T.LI32 0w0)) = a
206 :     | SHIFT(e,f,ty,a as (T.LI 0 | T.LI32 0w0),b) = a
207 :     | SHIFT(e,f,ty,a,b) = f(e,ty,a,b)
208 : monnier 475 fun CVTI2I(e,ty,ext,ty',a) = e
209 : monnier 467 in (* perform algebraic simplification and constant folding *)
210 :     case e of
211 :     T.ADD(ty,a,b) => ADD(e,add,ty,a,b)
212 :     | T.SUB(ty,(T.LI 0 | T.LI32 0w0),T.SUB(ty',(T.LI 0 | T.LI32 0w0), a)) =>
213 :     if ty = ty' then a else e
214 :     | T.SUB(ty,a,b) => SUB(e,sub,ty,a,b)
215 :     | T.MULS(ty,a,b) => MUL(e,muls,ty,a,b)
216 :     | T.DIVS(ty,a,b) => DIV(e,divs,ty,a,b)
217 :     | T.REMS(ty,a,b) => REM(e,rems,ty,a,b)
218 :     | T.MULU(ty,a,b) => MUL(e,mulu,ty,a,b)
219 :     | T.DIVU(ty,a,b) => DIV(e,divu,ty,a,b)
220 :     | T.REMU(ty,a,b) => REM(e,remu,ty,a,b)
221 :    
222 :     | T.ADDT(ty,a,b) => ADD(e,addt,ty,a,b)
223 :     | T.SUBT(ty,a,b) => SUB(e,subt,ty,a,b)
224 :     | T.MULT(ty,a,b) => MUL(e,mult,ty,a,b)
225 :     | T.DIVT(ty,a,b) => DIV(e,divt,ty,a,b)
226 :     | T.REMT(ty,a,b) => REM(e,remt,ty,a,b)
227 :    
228 :     | T.ANDB(ty,T.NOTB(ty',a),T.NOTB(ty'',b)) =>
229 :     if ty = ty' andalso ty' = ty'' then T.NOTB(ty,T.ORB(ty,a,b)) else e
230 :     | T.ANDB(ty,a,b) => ANDB(e,ty,a,b)
231 :     | T.ORB(ty,T.NOTB(ty',a),T.NOTB(ty'',b)) =>
232 :     if ty = ty' andalso ty' = ty'' then T.NOTB(ty,T.ANDB(ty,a,b)) else e
233 :     | T.ORB(ty,a,b) => ORB(e,ty,a,b)
234 :     | T.XORB(ty,T.NOTB(ty',a),T.NOTB(ty'',b)) =>
235 :     if ty = ty' andalso ty' = ty'' then T.NOTB(ty,T.XORB(ty,a,b)) else e
236 :     | T.XORB(ty,a,b) => XORB(e,ty,a,b)
237 :     | T.NOTB(ty,T.NOTB(ty',a)) => if ty = ty' then a else e
238 :     | T.NOTB(ty,a) => NOTB(e,ty,a)
239 :     | T.SRA(ty,a,b) => SHIFT(e,sra,ty,a,b)
240 :     | T.SRL(ty,a,b) => SHIFT(e,srl,ty,a,b)
241 :     | T.SLL(ty,a,b) => SHIFT(e,sll,ty,a,b)
242 :    
243 : monnier 475 | T.CVTI2I(ty,ext,ty',a) => CVTI2I(e,ty,ext,ty',a)
244 : monnier 467
245 :     | T.COND(ty,cc,a,b) =>
246 :     (case evalcc cc of TRUE => a | FALSE => b | UNKNOWN => e)
247 :     | e => e
248 :     end
249 :    
250 :     and simStm s =
251 :     let val s =
252 :     case s of
253 :     T.MV(ty,dst,e) => T.MV(ty,dst,sim e)
254 :     | T.CCMV(dst,cc) => T.CCMV(dst,simCC cc)
255 :     | T.FMV(fty,dst,e) => T.FMV(fty,dst,simF e)
256 :     | T.JMP(e,labs) => T.JMP(sim e,labs)
257 :     | T.CALL(e,defs,uses,mem) => T.CALL(sim e,defs,uses,mem)
258 :     | T.STORE(ty,a,b,mem) => T.STORE(ty,sim a,sim b,mem)
259 :     | T.STORE_UNALIGNED(ty,a,b,mem) =>
260 :     T.STORE_UNALIGNED(ty,sim a,sim b,mem)
261 :     | T.FSTORE(fty,a,b,mem) => T.FSTORE(fty,sim a,simF b,mem)
262 :     | T.FSTORE_UNALIGNED(fty,a,b,mem) =>
263 :     T.FSTORE_UNALIGNED(fty,sim a,simF b,mem)
264 :     | T.BCC(cond,cc,lab) => T.BCC(cond,simCC cc,lab)
265 :     | T.FBCC(fcond,cc,lab) => T.FBCC(fcond,simCC cc,lab)
266 :     | T.ANNOTATION(s,an) => T.ANNOTATION(simStm s,an)
267 :     | s => s
268 :     in case s of
269 :     T.BCC(cond,cc,lab) => (* dead code elimination *)
270 :     (case evalcc cc of
271 :     TRUE => T.JMP(T.LABEL(LabelExp.LABEL lab),[lab])
272 :     | FALSE => NOP
273 :     | UNKNOWN => s
274 :     )
275 :     | s => s
276 :     end
277 :    
278 :     and simF e =
279 : monnier 475 let val exp = case e of
280 : monnier 467 T.FLOAD(fty,e,mem) => T.FLOAD(fty,sim e,mem)
281 :     | T.FLOAD_UNALIGNED(fty,e,mem) => T.FLOAD_UNALIGNED(fty,sim e,mem)
282 :     | T.FADD(fty,a,b) => T.FADD(fty,simF a,simF b)
283 :     | T.FSUB(fty,a,b) => T.FSUB(fty,simF a,simF b)
284 :     | T.FMUL(fty,a,b) => T.FMUL(fty,simF a,simF b)
285 :     | T.FDIV(fty,a,b) => T.FDIV(fty,simF a,simF b)
286 :     | T.FABS(fty,a) => T.FABS(fty,simF a)
287 :     | T.FNEG(fty,a) => T.FNEG(fty,simF a)
288 :     | T.FSQRT(fty,a) => T.FSQRT(fty,simF a)
289 : monnier 475 | T.CVTI2F(fty,ext,ty,e) => T.CVTI2F(fty,ext,ty,sim e)
290 :     | T.CVTF2F(fty,round,fty',e) => T.CVTF2F(fty,round,fty',simF e)
291 : monnier 467 | T.FSEQ(s,e) => T.FSEQ(simStm s,simF e)
292 : monnier 475 | T.FEXT(fty,fext,es) => T.FEXT(fty,fext,map simF es)
293 : monnier 467 | T.FMARK(e,an) => T.FMARK(simF e,an)
294 :     | e => e
295 : monnier 475 in case exp of
296 :     T.FNEG(ty,T.FNEG(ty',e)) => if ty = ty' then e else exp
297 :     | exp => exp
298 :     end
299 : monnier 467
300 :     and simCC e =
301 :     let val e = case e of
302 :     T.CMP(ty,cond,a,b) => T.CMP(ty,cond,sim a,sim b)
303 :     | T.FCMP(fty,fcond,a,b) => T.FCMP(fty,fcond,simF a,simF b)
304 :     | T.CCMARK(e,an) => T.CCMARK(simCC e,an)
305 :     | e => e
306 :     in case e of
307 :     T.CMP _ =>
308 :     (case evalcc e of
309 :     TRUE => ALWAYS_TRUE | FALSE => ALWAYS_FALSE | UNKNOWN => e
310 :     )
311 :     | e => e
312 :     end
313 :    
314 :     val simplify = simStm
315 :     val simplifyRexp = sim
316 :     val simplifyFexp = simF
317 :     val simplifyCCexp = simCC
318 :     end

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