Home My Page Projects Code Snippets Project Openings SML/NJ
Summary Activity Forums Tracker Lists Tasks Docs Surveys News SCM Files

SCM Repository

[smlnj] Diff of /sml/trunk/src/MLRISC/mltree/mltree-simplify.sml
ViewVC logotype

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

Parent Directory Parent Directory | Revision Log Revision Log | View Patch Patch

revision 590, Sat Apr 1 02:24:08 2000 UTC revision 591, Mon Apr 3 01:19:20 2000 UTC
# Line 34  Line 34 
34    
35     exception Precison     exception Precison
36    
37     fun simplify {addressWidth} =     (*
38     let      * Constant folding code
39        *
40        * This should be rewritten to take advantage of IntInf.
41        *)
42    
43        (* Get constant value *)        (* Get constant value *)
44     fun valOf(T.LI i) = CONST(W.fromInt i)     fun valOf(T.LI i) = CONST(W.fromInt i)
45       | valOf(T.LI32 w) = CONST w       | valOf(T.LI32 w) = CONST w
# Line 93  Line 97 
97           )           )
98         | _ => e         | _ => e
99    
100     fun sll x = compute (false,fn (a,b) => W.<<(a,Word.fromInt(W.toIntX(b)))) x     val sll = compute (false,fn (a,b) => W.<<(a,Word.fromInt(W.toIntX(b))))
101     fun srl x = compute (false,fn (a,b) => W.>>(a,Word.fromInt(W.toIntX(b)))) x     val srl = compute (false,fn (a,b) => W.>>(a,Word.fromInt(W.toIntX(b))))
102     fun sra x = compute (true,fn (a,b) => W.~>>(a,Word.fromInt(W.toIntX(b)))) x     val sra = compute (true,fn (a,b) => W.~>>(a,Word.fromInt(W.toIntX(b))))
103     fun andb x = compute (false,W.andb) x     val andb = compute (false,W.andb)
104     fun orb  x = compute (false,W.orb) x     val orb  = compute (false,W.orb)
105     fun xorb x = compute (false,W.xorb) x     val xorb = compute (false,W.xorb)
106     fun notb x = computeUnary (false,W.notb) x     val notb = computeUnary (false,W.notb)
107     fun add  x = compute (true,W.+) x     val add  = compute (true,W.+)
108     fun addt x = computeTrap (Int.+) x     val addt = computeTrap (Int.+)
109     fun sub  x = compute (true,W.-) x     val sub  = compute (true,W.-)
110     fun subt x = computeTrap (Int.-) x     val subt = computeTrap (Int.-)
111     fun muls x = compute (true,W.* ) x     val muls = compute (true,W.* )
112     fun mulu x = compute (false,W.* ) x     val mulu = compute (false,W.* )
113     fun mult x = computeTrap (Int.* ) x     val mult = computeTrap (Int.* )
114     fun divs x = compute (true,W.div) x     val divs = compute (true,W.div)
115     fun divu x = compute (false,W.div) x     val divu = compute (false,W.div)
116     fun divt x = computeTrap (Int.div) x     val divt = computeTrap (Int.div)
117     fun rems x = compute (true,W.mod) x     val rems = compute (true,W.mod)
118     fun remu x = compute (false,W.mod) x     val remu = compute (false,W.mod)
119     fun remt x = computeTrap (Int.mod) x     val remt = computeTrap (Int.mod)
120    
121        (* Evaluate an integer comparison *)        (* Evaluate an integer comparison *)
122     fun cmp (signed,rel) (ty,a,b) =     fun cmp (signed,rel) (ty,a,b) =
# Line 128  Line 132 
132         else rel(a,b)         else rel(a,b)
133     end     end
134    
135     fun gt  x = cmp (true,W.>) x     val gt  = cmp (true,W.>)
136     fun lt  x = cmp (true,W.<) x     val lt  = cmp (true,W.<)
137     fun ge  x = cmp (true,W.>=) x     val ge  = cmp (true,W.>=)
138     fun le  x = cmp (true,W.<=) x     val le  = cmp (true,W.<=)
139     fun gtu x = cmp (false,W.>) x     val gtu = cmp (false,W.>)
140     fun ltu x = cmp (false,W.<) x     val ltu = cmp (false,W.<)
141     fun geu x = cmp (false,W.>=) x     val geu = cmp (false,W.>=)
142     fun leu x = cmp (false,W.<=) x     val leu = cmp (false,W.<=)
143    
144        (* Evaluate a comparison *)        (* Evaluate a comparison *)
145     fun evalcc(T.CMP(ty,cond,a,b)) =     fun evalcc(T.CMP(ty,cond,a,b)) =
# Line 159  Line 163 
163       | evalcc(T.CCMARK(e,_)) = evalcc e       | evalcc(T.CCMARK(e,_)) = evalcc e
164       | evalcc _ = UNKNOWN       | evalcc _ = UNKNOWN
165    
166     fun sim ==> e =     (*
167        *  The main algebraic simplifier
168        *)
169    
170       exception NotFoldable
171    
172       fun simplify {addressWidth, signedAddress} =
173       let
174    
175       fun sim ==> exp =
176     let     let
177       (* algebraic simplification and constant folding *)  
178        fun ADD(e,f,ty,a,(T.LI 0 | T.LI32 0w0)) = a        fun isConstant(T.LI _) = true
179          | ADD(e,f,ty,(T.LI 0 | T.LI32 0w0),a) = a          | isConstant(T.LABEL _) = true
180          | ADD(e,f,ty,a,b) =          | isConstant(T.CONST _) = true
181            | isConstant(T.LI32 _) = true
182            | isConstant _ = false
183    
184          (*
185           * Fold in abstract constant
186           *)
187          fun foldConst(h, f, ty, a, b) =
188              if ty = addressWidth then              if ty = addressWidth then
189              (case (a, b) of        let fun g(T.LABEL le) = le
190                (T.LABEL le, T.LI n) => T.LABEL(LE.PLUS(le,LE.INT n))              | g(T.LI n) = LE.INT n
191              | (T.LI n, T.LABEL le) => T.LABEL(LE.PLUS(le,LE.INT n))              | g(T.CONST c) = LE.CONST c
192              | (T.LABEL le, T.LABEL le') => T.LABEL(LE.PLUS(le,le'))              | g(T.LI32 n) = LE.INT(W.toIntX n)
193              | _ => f(e,ty,a,b)              | g _ = raise NotFoldable
194              ) else f(e,ty,a,b)        in  T.LABEL(h(g a, g b)) handle _ => f(exp, ty, a, b) end
195        fun SUB(e,f,ty,a,(T.LI 0 | T.LI32 0w0)) = a        else f(exp, ty, a, b)
196          | SUB(e,f,ty,a,b) =  
197          fun foldConst2(h, f, ty, a, b) =
198              if ty = addressWidth then              if ty = addressWidth then
199              (case (a, b) of        let fun g(T.LABEL le) = le
200                (T.LABEL le, T.LI n) => T.LABEL(LE.MINUS(le,LE.INT n))              | g(T.LI n) = LE.INT n
201              | (T.LI n, T.LABEL le) => T.LABEL(LE.MINUS(LE.INT n,le))              | g(T.CONST c) = LE.CONST c
202              | (T.LABEL le, T.LABEL le') => T.LABEL(LE.MINUS(le,le'))              | g(T.LI32 n) = LE.INT(W.toIntX n)
203              | _ => f(e,ty,a,b)              | g _ = raise NotFoldable
204              ) else f(e,ty,a,b)            fun g'(T.LI n) = Word.fromInt n
205        fun MUL(e,f,ty,a,b as (T.LI 0 | T.LI32 0w0)) = b              | g'(T.LI32 w) = Word.fromLargeWord w
206          | MUL(e,f,ty,a as (T.LI 0 | T.LI32 0w0),b) = a              | g' _ = raise NotFoldable
207          | MUL(e,f,ty,a,(T.LI 1 | T.LI32 0w1)) = a        in  T.LABEL(h(g a, g' b)) handle _ => f(exp, ty, a, b) end
208          | MUL(e,f,ty,(T.LI 1 | T.LI32 0w1),b) = b        else f(exp, ty, a, b)
209          | MUL(e,f,ty,a,b) = f(e,ty,a,b)  
210        fun DIV(e,f,ty,a,(T.LI 1 | T.LI32 0w1)) = a  
211          | DIV(e,f,ty,a,b) = f(e,ty,a,b)        (* algebraic simplification and constant folding rules
212        fun REM(e,f,ty,a,b) = f(e,ty,a,b)         * for various operators
213        fun ANDB(e,ty,a,b as (T.LI 0 | T.LI32 0w0)) = b         *)
214          | ANDB(e,ty,a as (T.LI 0 | T.LI32 0w0),b) = a        fun ADD(f,fold,ty,a,(T.LI 0 | T.LI32 0w0)) = a
215          | ANDB(e,ty,a,b) = andb(e,ty,a,b)          | ADD(f,fold,ty,(T.LI 0 | T.LI32 0w0),a) = a
216        fun ORB(e,ty,a,(T.LI 0 | T.LI32 0w0)) = a          | ADD(f,fold,ty,a,b) =
217          | ORB(e,ty,(T.LI 0 | T.LI32 0w0),b) = b              if fold then foldConst(LE.PLUS, f, ty, a, b) else f(exp,ty,a,b)
218          | ORB(e,ty,a,b) = orb(e,ty,a,b)  
219        fun XORB(e,ty,a,(T.LI 0 | T.LI32 0w0)) = a        fun SUB(f,fold,ty,a,(T.LI 0 | T.LI32 0w0)) = a
220          | XORB(e,ty,(T.LI 0 | T.LI32 0w0),b) = b          | SUB(f,fold,ty,a,b) =
221          | XORB(e,ty,a,b) = xorb(e,ty,a,b)              if fold then foldConst(LE.MINUS, f, ty, a, b) else f(exp,ty,a,b)
222        fun NOTB(e,ty,a) = notb(e,ty,a)  
223        fun SHIFT(e,f,ty,a,(T.LI 0 | T.LI32 0w0)) = a        fun MUL(f,fold,ty,a,b as (T.LI 0 | T.LI32 0w0)) = b
224          | SHIFT(e,f,ty,a as (T.LI 0 | T.LI32 0w0),b) = a          | MUL(f,fold,ty,a as (T.LI 0 | T.LI32 0w0),b) = a
225          | SHIFT(e,f,ty,a,b) = f(e,ty,a,b)          | MUL(f,fold,ty,a,(T.LI 1 | T.LI32 0w1)) = a
226            | MUL(f,fold,ty,(T.LI 1 | T.LI32 0w1),b) = b
227            | MUL(f,fold,ty,a,b) =
228                if fold then foldConst(LE.MULT, f, ty, a, b) else f(exp,ty,a,b)
229    
230          fun DIV(f,fold,ty,a,(T.LI 1 | T.LI32 0w1)) = a
231            | DIV(f,fold,ty,a,b) =
232                if fold then foldConst(LE.DIV, f, ty, a, b) else f(exp,ty,a,b)
233    
234          fun REM(f,ty,a,b) = f(exp,ty,a,b)
235    
236          fun SHIFT(f,fold,g,ty,a,(T.LI 0 | T.LI32 0w0)) = a
237            | SHIFT(f,fold,g,ty,a as (T.LI 0 | T.LI32 0w0),b) = a
238            | SHIFT(f,fold,g,ty,a,b) =
239                if fold then foldConst2(g, f, ty, a, b) else f(exp,ty,a,b)
240    
241        fun identity_ext(8,T.SIGN_EXTEND,T.LI n) = ~128 <= n andalso n <= 127        fun identity_ext(8,T.SIGN_EXTEND,T.LI n) = ~128 <= n andalso n <= 127
242          | identity_ext(16,T.SIGN_EXTEND,T.LI n) = ~32768 <= n andalso n <= 32767          | identity_ext(16,T.SIGN_EXTEND,T.LI n) = ~32768 <= n andalso n <= 32767
243          | identity_ext(ty,T.SIGN_EXTEND,T.LI n) = ty >= 32          | identity_ext(ty,T.SIGN_EXTEND,T.LI n) = ty >= 32
# Line 217  Line 253 
253          | identity_ext _ = false          | identity_ext _ = false
254    
255     in (* perform algebraic simplification and constant folding *)     in (* perform algebraic simplification and constant folding *)
256        case e of        case exp of
257          T.ADD(ty,a,b)  => ADD(e,add,ty,a,b)          T.ADD(ty,a,b) => ADD(add,true,ty,a,b)
258        | T.SUB(ty,(T.LI 0 | T.LI32 0w0),T.SUB(ty',(T.LI 0 | T.LI32 0w0), a)) =>        | T.SUB(ty,(T.LI 0 | T.LI32 0w0),T.SUB(ty',(T.LI 0 | T.LI32 0w0), a)) =>
259              if ty = ty' then a else e              if ty = ty' then a else exp
260        | T.SUB(ty,a,b)  => SUB(e,sub,ty,a,b)        | T.SUB(ty,a,b) => SUB(sub,true,ty,a,b)
       | T.MULS(ty,a,b) => MUL(e,muls,ty,a,b)  
       | T.DIVS(ty,a,b) => DIV(e,divs,ty,a,b)  
       | T.REMS(ty,a,b) => REM(e,rems,ty,a,b)  
       | T.MULU(ty,a,b) => MUL(e,mulu,ty,a,b)  
       | T.DIVU(ty,a,b) => DIV(e,divu,ty,a,b)  
       | T.REMU(ty,a,b) => REM(e,remu,ty,a,b)  
   
       | T.ADDT(ty,a,b) => ADD(e,addt,ty,a,b)  
       | T.SUBT(ty,a,b) => SUB(e,subt,ty,a,b)  
       | T.MULT(ty,a,b) => MUL(e,mult,ty,a,b)  
       | T.DIVT(ty,a,b) => DIV(e,divt,ty,a,b)  
       | T.REMT(ty,a,b) => REM(e,remt,ty,a,b)  
261    
262          | T.MULS(ty,a,b) => MUL(muls,signedAddress,ty,a,b)
263          | T.DIVS(ty,a,b) => DIV(divs,signedAddress,ty,a,b)
264          | T.REMS(ty,a,b) => REM(rems,ty,a,b)
265    
266          | T.MULU(ty,a,b) => MUL(mulu,not signedAddress,ty,a,b)
267          | T.DIVU(ty,a,b) => DIV(divu,not signedAddress,ty,a,b)
268          | T.REMU(ty,a,b) => REM(remu,ty,a,b)
269    
270          | T.ADDT(ty,a,b) => ADD(addt,true,ty,a,b)
271          | T.SUBT(ty,a,b) => SUB(subt,true,ty,a,b)
272    
273          | T.MULT(ty,a,b) => MUL(mult,false,ty,a,b)
274          | T.DIVT(ty,a,b) => DIV(divt,false,ty,a,b)
275          | T.REMT(ty,a,b) => REM(remt,ty,a,b)
276    
277          | T.ANDB(_,_,b as (T.LI 0 | T.LI32 0w0)) => b
278          | T.ANDB(_,a as (T.LI 0 | T.LI32 0w0),_) => a
279        | T.ANDB(ty,T.NOTB(ty',a),T.NOTB(ty'',b)) =>        | T.ANDB(ty,T.NOTB(ty',a),T.NOTB(ty'',b)) =>
280           if ty = ty' andalso ty' = ty'' then T.NOTB(ty,T.ORB(ty,a,b)) else e           if ty = ty' andalso ty' = ty'' then T.NOTB(ty,T.ORB(ty,a,b)) else exp
281        | T.ANDB(ty,a,b) => ANDB(e,ty,a,b)        | T.ANDB(ty,a,b) => foldConst2(LE.AND,andb,ty,a,b)
282    
283          | T.ORB(_,a,(T.LI 0 | T.LI32 0w0)) => a
284          | T.ORB(_,(T.LI 0 | T.LI32 0w0),b) => b
285        | T.ORB(ty,T.NOTB(ty',a),T.NOTB(ty'',b)) =>        | T.ORB(ty,T.NOTB(ty',a),T.NOTB(ty'',b)) =>
286            if ty = ty' andalso ty' = ty'' then T.NOTB(ty,T.ANDB(ty,a,b)) else e            if ty = ty' andalso ty' = ty'' then T.NOTB(ty,T.ANDB(ty,a,b)) else exp
287        | T.ORB(ty,a,b)  => ORB(e,ty,a,b)        | T.ORB(ty,a,b) => foldConst2(LE.OR,orb,ty,a,b)
288    
289          | T.XORB(ty,a,(T.LI 0 | T.LI32 0w0)) => a
290          | T.XORB(ty,(T.LI 0 | T.LI32 0w0),b) => b
291        | T.XORB(ty,T.NOTB(ty',a),T.NOTB(ty'',b)) =>        | T.XORB(ty,T.NOTB(ty',a),T.NOTB(ty'',b)) =>
292            if ty = ty' andalso ty' = ty'' then T.NOTB(ty,T.XORB(ty,a,b)) else e            if ty = ty' andalso ty' = ty''
293        | T.XORB(ty,a,b) => XORB(e,ty,a,b)            then T.NOTB(ty,T.XORB(ty,a,b)) else exp
294        | T.NOTB(ty,T.NOTB(ty',a)) => if ty = ty' then a else e        | T.XORB(ty,a,b) => xorb(exp,ty,a,b)
295        | T.NOTB(ty,a)   => NOTB(e,ty,a)  
296        | T.SRA(ty,a,b)  => SHIFT(e,sra,ty,a,b)        | T.NOTB(ty,T.NOTB(ty',a)) => if ty = ty' then a else exp
297        | T.SRL(ty,a,b)  => SHIFT(e,srl,ty,a,b)        | T.NOTB(ty,a)   => notb(exp,ty,a)
298        | T.SLL(ty,a,b)  => SHIFT(e,sll,ty,a,b)  
299          | T.SRA(ty,a,b)  => SHIFT(sra,signedAddress,LE.RSHIFT,ty,a,b)
300          | T.SRL(ty,a,b)  => SHIFT(srl,not signedAddress,LE.RSHIFT,ty,a,b)
301          | T.SLL(ty,a,b)  => SHIFT(sll,true,LE.LSHIFT,ty,a,b)
302    
303        | T.CVTI2I(_,_,_,e as (T.LI 0 | T.LI32 0w0)) => e        | T.CVTI2I(_,_,_,e as (T.LI 0 | T.LI32 0w0)) => e
304        | cvt as T.CVTI2I(ty,ext,_,e) =>        | cvt as T.CVTI2I(ty,ext,_,e) =>
305             if identity_ext(ty,ext,e) then e else cvt             if identity_ext(ty,ext,e) then e else cvt
306    
307        | T.COND(ty,cc,a,b) =>        | T.COND(ty,cc,a,b) =>
308            (case evalcc cc of TRUE => a | FALSE => b | UNKNOWN => e)            (case evalcc cc of TRUE => a | FALSE => b | UNKNOWN => exp)
309        | e => e        | exp => exp
310     end     end
311    
312     and simStm ==> (s as T.IF(ctrl,cc,s1,s2)) = (* dead code elimination *)     and simStm ==> (s as T.IF(ctrl,cc,s1,s2)) = (* dead code elimination *)

Legend:
Removed from v.590  
changed lines
  Added in v.591

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