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 579 - (view) (download)

1 : monnier 467 (*
2 :     * Performs simple local optimizations.
3 :     *)
4 : george 555 functor MLTreeSimplifier
5 :     (structure T : MLTREE
6 :     (* Extension *)
7 :     val sext : T.rewriter -> T.sext -> T.sext
8 :     val rext : T.rewriter -> T.rext -> T.rext
9 :     val fext : T.rewriter -> T.fext -> T.fext
10 :     val ccext : T.rewriter -> T.ccext -> T.ccext
11 :     ) : MLTREE_SIMPLIFIER =
12 : monnier 467 struct
13 :    
14 : george 545 structure T = T
15 :     structure W = Word32
16 :     structure I = Int32
17 :     structure LE = T.LabelExp
18 : george 555 structure R = MLTreeRewrite
19 :     (structure T = T
20 :     val sext = sext and rext = rext and fext = fext and ccext = ccext
21 :     )
22 : monnier 467
23 : george 555 type simplifier = T.rewriter
24 : george 545
25 : monnier 467 datatype const = CONST of W.word | NONCONST
26 :     datatype cond = TRUE | FALSE | UNKNOWN
27 :    
28 :     val NOP = T.COPY(32,[],[])
29 :     val ALWAYS_TRUE = T.CMP(32, T.EQ, T.LI 0, T.LI 0)
30 :     val ALWAYS_FALSE = T.CMP(32, T.NE, T.LI 0, T.LI 0)
31 :    
32 :     val zero = 0w0 : W.word
33 :     val one = 0w1 : W.word
34 :    
35 :     exception Precison
36 :    
37 : george 555 fun simplify {addressWidth} =
38 : george 545 let
39 : monnier 467 (* Get constant value *)
40 :     fun valOf(T.LI i) = CONST(W.fromInt i)
41 :     | valOf(T.LI32 w) = CONST w
42 :     | valOf(T.MARK(e,_)) = valOf e
43 :     | valOf e = NONCONST
44 :    
45 :     fun bits(ty,w) =
46 :     let val mask = W.<<(0w1,Word.fromInt ty)-0w1
47 :     in if mask = zero then raise Precison
48 :     else W.andb(w,mask)
49 :     end
50 :    
51 :     fun isSigned(ty,w) =
52 :     let val signBit = W.<<(0w1,Word.fromInt(ty-1))
53 :     in W.andb(signBit,w) <> 0w0 end
54 :    
55 :     fun extend(ty,false,w) = w
56 :     | extend(ty,true,w) =
57 :     let val signBit = W.<<(0w1,Word.fromInt(ty-1))
58 :     in if W.andb(signBit,w) <> 0w0 then
59 :     let val shift = Word.fromInt(W.wordSize-ty)
60 :     in W.~>>(W.<<(w, shift), shift) end
61 :     else w
62 :     end
63 :    
64 :     fun compute (signed, f) (e,ty,a,b) =
65 :     case (valOf a, valOf b) of
66 :     (CONST a, CONST b) =>
67 :     (let val a = bits(ty,a)
68 :     val b = bits(ty,b)
69 :     val w = extend(ty,signed,bits(ty,f(a,b)))
70 :     in T.LI(W.toIntX w) handle _ => T.LI32 w end
71 :     handle _ => e
72 :     )
73 :     | _ => e
74 :    
75 :     fun computeUnary (signed, f) (e,ty,a) =
76 :     case (valOf a) of
77 :     (CONST a) =>
78 :     (let val a = bits(ty,a)
79 :     val w = extend(ty,signed,bits(ty,f(a)))
80 :     in T.LI(W.toIntX w) handle _ => T.LI32 w end
81 :     handle _ => e
82 :     )
83 :     | _ => e
84 :    
85 :     fun computeTrap f (e,ty,a,b) =
86 :     case (a,b) of
87 :     (T.LI a, T.LI b) =>
88 :     (let val x = f(a,b)
89 :     val range = Word.toInt(Word.<<(0w1,Word.fromInt ty))
90 :     in if x >= range orelse x < ~range then e
91 :     else T.LI x
92 :     end handle _ => e
93 :     )
94 :     | _ => e
95 :    
96 : george 545 fun sll x = compute (false,fn (a,b) => W.<<(a,Word.fromInt(W.toIntX(b)))) x
97 :     fun srl x = compute (false,fn (a,b) => W.>>(a,Word.fromInt(W.toIntX(b)))) x
98 :     fun sra x = compute (true,fn (a,b) => W.~>>(a,Word.fromInt(W.toIntX(b)))) x
99 :     fun andb x = compute (false,W.andb) x
100 :     fun orb x = compute (false,W.orb) x
101 :     fun xorb x = compute (false,W.xorb) x
102 :     fun notb x = computeUnary (false,W.notb) x
103 :     fun add x = compute (true,W.+) x
104 :     fun addt x = computeTrap (Int.+) x
105 :     fun sub x = compute (true,W.-) x
106 :     fun subt x = computeTrap (Int.-) x
107 :     fun muls x = compute (true,W.* ) x
108 :     fun mulu x = compute (false,W.* ) x
109 :     fun mult x = computeTrap (Int.* ) x
110 :     fun divs x = compute (true,W.div) x
111 :     fun divu x = compute (false,W.div) x
112 :     fun divt x = computeTrap (Int.div) x
113 :     fun rems x = compute (true,W.mod) x
114 :     fun remu x = compute (false,W.mod) x
115 :     fun remt x = computeTrap (Int.mod) x
116 : monnier 467
117 :     (* Evaluate an integer comparison *)
118 :     fun cmp (signed,rel) (ty,a,b) =
119 :     let val a = bits(ty,a)
120 :     val b = bits(ty,b)
121 :     in if signed then
122 :     (case (isSigned(ty, a),isSigned(ty, b)) of
123 :     (false, false) => rel(a,b)
124 :     | (false, true) => rel(one,zero)
125 :     | (true, false) => rel(zero,one)
126 :     | (true, true) => rel(b,a)
127 :     )
128 :     else rel(a,b)
129 :     end
130 :    
131 : george 545 fun gt x = cmp (true,W.>) x
132 :     fun lt x = cmp (true,W.<) x
133 :     fun ge x = cmp (true,W.>=) x
134 :     fun le x = cmp (true,W.<=) x
135 :     fun gtu x = cmp (false,W.>) x
136 :     fun ltu x = cmp (false,W.<) x
137 :     fun geu x = cmp (false,W.>=) x
138 :     fun leu x = cmp (false,W.<=) x
139 : monnier 467
140 :     (* Evaluate a comparison *)
141 :     fun evalcc(T.CMP(ty,cond,a,b)) =
142 :     (case (cond,valOf a,valOf b) of
143 :     (T.EQ,CONST i,CONST j) => if i = j then TRUE else FALSE
144 :     | (T.NE,CONST i,CONST j) => if i <> j then TRUE else FALSE
145 :     | (T.GT,CONST i,CONST j) => if gt(ty,i,j) then TRUE else FALSE
146 :     | (T.LT,CONST i,CONST j) => if lt(ty,i,j) then TRUE else FALSE
147 :     | (T.GE,CONST i,CONST j) => if ge(ty,j,i) then TRUE else FALSE
148 :     | (T.LE,CONST i,CONST j) => if le(ty,j,i) then TRUE else FALSE
149 :     | (T.GTU,CONST i,CONST j) => if gtu(ty,i,j) then TRUE else FALSE
150 :     | (T.LTU,CONST i,CONST j) => if ltu(ty,i,j) then TRUE else FALSE
151 :     | (T.GEU,CONST i,CONST j) => if geu(ty,i,j) then TRUE else FALSE
152 :     | (T.LEU,CONST i,CONST j) => if leu(ty,i,j) then TRUE else FALSE
153 :     | (T.GEU,_,CONST 0w0) => TRUE
154 :     | (T.GTU,CONST 0w0,_) => FALSE
155 :     | (T.LTU,_,CONST 0w0) => FALSE
156 :     | (T.LEU,CONST 0w0,_) => TRUE
157 :     | _ => UNKNOWN
158 :     )
159 :     | evalcc(T.CCMARK(e,_)) = evalcc e
160 :     | evalcc _ = UNKNOWN
161 :    
162 : george 545 fun sim ==> e =
163 :     let
164 : monnier 467 (* algebraic simplification and constant folding *)
165 :     fun ADD(e,f,ty,a,(T.LI 0 | T.LI32 0w0)) = a
166 :     | ADD(e,f,ty,(T.LI 0 | T.LI32 0w0),a) = a
167 : george 545 | ADD(e,f,ty,a,b) =
168 :     if ty = addressWidth then
169 :     (case (a, b) of
170 :     (T.LABEL le, T.LI n) => T.LABEL(LE.PLUS(le,LE.INT n))
171 :     | (T.LI n, T.LABEL le) => T.LABEL(LE.PLUS(le,LE.INT n))
172 :     | (T.LABEL le, T.LABEL le') => T.LABEL(LE.PLUS(le,le'))
173 :     | _ => f(e,ty,a,b)
174 :     ) else f(e,ty,a,b)
175 : monnier 467 fun SUB(e,f,ty,a,(T.LI 0 | T.LI32 0w0)) = a
176 : george 545 | SUB(e,f,ty,a,b) =
177 :     if ty = addressWidth then
178 :     (case (a, b) of
179 :     (T.LABEL le, T.LI n) => T.LABEL(LE.MINUS(le,LE.INT n))
180 :     | (T.LI n, T.LABEL le) => T.LABEL(LE.MINUS(LE.INT n,le))
181 :     | (T.LABEL le, T.LABEL le') => T.LABEL(LE.MINUS(le,le'))
182 :     | _ => f(e,ty,a,b)
183 :     ) else f(e,ty,a,b)
184 : monnier 467 fun MUL(e,f,ty,a,b as (T.LI 0 | T.LI32 0w0)) = b
185 :     | MUL(e,f,ty,a as (T.LI 0 | T.LI32 0w0),b) = a
186 :     | MUL(e,f,ty,a,(T.LI 1 | T.LI32 0w1)) = a
187 :     | MUL(e,f,ty,(T.LI 1 | T.LI32 0w1),b) = b
188 :     | MUL(e,f,ty,a,b) = f(e,ty,a,b)
189 :     fun DIV(e,f,ty,a,(T.LI 1 | T.LI32 0w1)) = a
190 :     | DIV(e,f,ty,a,b) = f(e,ty,a,b)
191 :     fun REM(e,f,ty,a,b) = f(e,ty,a,b)
192 :     fun ANDB(e,ty,a,b as (T.LI 0 | T.LI32 0w0)) = b
193 :     | ANDB(e,ty,a as (T.LI 0 | T.LI32 0w0),b) = a
194 :     | ANDB(e,ty,a,b) = andb(e,ty,a,b)
195 :     fun ORB(e,ty,a,(T.LI 0 | T.LI32 0w0)) = a
196 :     | ORB(e,ty,(T.LI 0 | T.LI32 0w0),b) = b
197 :     | ORB(e,ty,a,b) = orb(e,ty,a,b)
198 :     fun XORB(e,ty,a,(T.LI 0 | T.LI32 0w0)) = a
199 :     | XORB(e,ty,(T.LI 0 | T.LI32 0w0),b) = b
200 :     | XORB(e,ty,a,b) = xorb(e,ty,a,b)
201 :     fun NOTB(e,ty,a) = notb(e,ty,a)
202 :     fun SHIFT(e,f,ty,a,(T.LI 0 | T.LI32 0w0)) = a
203 :     | SHIFT(e,f,ty,a as (T.LI 0 | T.LI32 0w0),b) = a
204 :     | SHIFT(e,f,ty,a,b) = f(e,ty,a,b)
205 : george 555 fun identity_ext(8,T.SIGN_EXTEND,T.LI n) = ~128 <= n andalso n <= 127
206 :     | identity_ext(16,T.SIGN_EXTEND,T.LI n) = ~32768 <= n andalso n <= 32767
207 :     | identity_ext(ty,T.SIGN_EXTEND,T.LI n) = ty >= 32
208 :     | identity_ext(8,T.SIGN_EXTEND,T.LI32 n) = n <= 0w127
209 :     | identity_ext(16,T.SIGN_EXTEND,T.LI32 n) = n <= 0w32767
210 :     | identity_ext(ty,T.SIGN_EXTEND,T.LI32 n) = ty >= 32
211 :     | identity_ext(8,T.ZERO_EXTEND,T.LI n) = 0 <= n andalso n <= 255
212 :     | identity_ext(16,T.ZERO_EXTEND,T.LI n) = 0 <= n andalso n <= 65535
213 :     | identity_ext(ty,T.ZERO_EXTEND,T.LI n) = n >= 0 andalso ty >= 32
214 :     | identity_ext(8,T.ZERO_EXTEND,T.LI32 n) = n <= 0w255
215 :     | identity_ext(16,T.ZERO_EXTEND,T.LI32 n) = n <= 0w65535
216 :     | identity_ext(ty,T.ZERO_EXTEND,T.LI32 n) = ty >= 32
217 :     | identity_ext _ = false
218 :    
219 : monnier 467 in (* perform algebraic simplification and constant folding *)
220 :     case e of
221 :     T.ADD(ty,a,b) => ADD(e,add,ty,a,b)
222 :     | T.SUB(ty,(T.LI 0 | T.LI32 0w0),T.SUB(ty',(T.LI 0 | T.LI32 0w0), a)) =>
223 :     if ty = ty' then a else e
224 :     | T.SUB(ty,a,b) => SUB(e,sub,ty,a,b)
225 :     | T.MULS(ty,a,b) => MUL(e,muls,ty,a,b)
226 :     | T.DIVS(ty,a,b) => DIV(e,divs,ty,a,b)
227 :     | T.REMS(ty,a,b) => REM(e,rems,ty,a,b)
228 :     | T.MULU(ty,a,b) => MUL(e,mulu,ty,a,b)
229 :     | T.DIVU(ty,a,b) => DIV(e,divu,ty,a,b)
230 :     | T.REMU(ty,a,b) => REM(e,remu,ty,a,b)
231 :    
232 :     | T.ADDT(ty,a,b) => ADD(e,addt,ty,a,b)
233 :     | T.SUBT(ty,a,b) => SUB(e,subt,ty,a,b)
234 :     | T.MULT(ty,a,b) => MUL(e,mult,ty,a,b)
235 :     | T.DIVT(ty,a,b) => DIV(e,divt,ty,a,b)
236 :     | T.REMT(ty,a,b) => REM(e,remt,ty,a,b)
237 :    
238 :     | T.ANDB(ty,T.NOTB(ty',a),T.NOTB(ty'',b)) =>
239 :     if ty = ty' andalso ty' = ty'' then T.NOTB(ty,T.ORB(ty,a,b)) else e
240 :     | T.ANDB(ty,a,b) => ANDB(e,ty,a,b)
241 :     | T.ORB(ty,T.NOTB(ty',a),T.NOTB(ty'',b)) =>
242 :     if ty = ty' andalso ty' = ty'' then T.NOTB(ty,T.ANDB(ty,a,b)) else e
243 :     | T.ORB(ty,a,b) => ORB(e,ty,a,b)
244 :     | T.XORB(ty,T.NOTB(ty',a),T.NOTB(ty'',b)) =>
245 :     if ty = ty' andalso ty' = ty'' then T.NOTB(ty,T.XORB(ty,a,b)) else e
246 :     | T.XORB(ty,a,b) => XORB(e,ty,a,b)
247 :     | T.NOTB(ty,T.NOTB(ty',a)) => if ty = ty' then a else e
248 :     | T.NOTB(ty,a) => NOTB(e,ty,a)
249 :     | T.SRA(ty,a,b) => SHIFT(e,sra,ty,a,b)
250 :     | T.SRL(ty,a,b) => SHIFT(e,srl,ty,a,b)
251 :     | T.SLL(ty,a,b) => SHIFT(e,sll,ty,a,b)
252 :    
253 : george 555 | T.CVTI2I(_,_,_,e as (T.LI 0 | T.LI32 0w0)) => e
254 :     | cvt as T.CVTI2I(ty,ext,_,e) =>
255 :     if identity_ext(ty,ext,e) then e else cvt
256 : monnier 467
257 :     | T.COND(ty,cc,a,b) =>
258 :     (case evalcc cc of TRUE => a | FALSE => b | UNKNOWN => e)
259 :     | e => e
260 :     end
261 :    
262 : george 545 and simStm ==> (s as T.IF(ctrl,cc,s1,s2)) = (* dead code elimination *)
263 :     (case evalcc cc of
264 :     TRUE => s1
265 :     | FALSE => s2
266 :     | UNKNOWN => s
267 :     )
268 :     | simStm ==> s = s
269 : monnier 467
270 : george 545 and simF ==> (exp as T.FNEG(ty,T.FNEG(ty',e))) = if ty = ty' then e else exp
271 :     | simF ==> exp = exp
272 : monnier 467
273 : george 545 and simCC ==> (exp as T.CMP _) =
274 :     (case evalcc exp of
275 :     TRUE => ALWAYS_TRUE | FALSE => ALWAYS_FALSE | UNKNOWN => exp
276 :     )
277 :     | simCC ==> exp = exp
278 : monnier 467
279 : george 555 in R.rewrite {rexp=sim,fexp=simF,ccexp=simCC,stm=simStm} end
280 : monnier 467 end

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