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
 [smlnj] / sml / trunk / src / MLRISC / mltree / mltree-simplify.sml

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

revision 476, Wed Nov 10 22:59:58 1999 UTC revision 545, Thu Feb 24 13:56:44 2000 UTC
# Line 7  Line 7
7     structure T = T     structure T = T
8     structure W = Word32     structure W = Word32
9     structure I = Int32     structure I = Int32
10       structure LE = T.LabelExp
11       structure R  = MLTreeRewrite(T)
12
13       type ('s,'r,'f,'c) simplifier = ('s,'r,'f,'c) R.rewriters
14
15     datatype const = CONST of W.word | NONCONST     datatype const = CONST of W.word | NONCONST
16     datatype cond  = TRUE | FALSE | UNKNOWN     datatype cond  = TRUE | FALSE | UNKNOWN
# Line 20  Line 24
24
25     exception Precison     exception Precison
26
27       fun simplify {addressWidth} ext =
28       let
29        (* Get constant value *)        (* Get constant value *)
30     fun valOf(T.LI i) = CONST(W.fromInt i)     fun valOf(T.LI i) = CONST(W.fromInt i)
31       | valOf(T.LI32 w) = CONST w       | valOf(T.LI32 w) = CONST w
# Line 77  Line 83
83           )           )
84         | _ => e         | _ => e
85
86     val sll  = compute (false,fn (a,b) => W.<<(a,Word.fromInt(W.toIntX(b))))     fun sll x = compute (false,fn (a,b) => W.<<(a,Word.fromInt(W.toIntX(b)))) x
87     val srl  = compute (false,fn (a,b) => W.>>(a,Word.fromInt(W.toIntX(b))))     fun srl x = compute (false,fn (a,b) => W.>>(a,Word.fromInt(W.toIntX(b)))) x
88     val sra  = compute (true,fn (a,b) => W.~>>(a,Word.fromInt(W.toIntX(b))))     fun sra x = compute (true,fn (a,b) => W.~>>(a,Word.fromInt(W.toIntX(b)))) x
89     val andb = compute (false,W.andb)     fun andb x = compute (false,W.andb) x
90     val orb  = compute (false,W.orb)     fun orb  x = compute (false,W.orb) x
91     val xorb = compute (false,W.xorb)     fun xorb x = compute (false,W.xorb) x
92     val notb = computeUnary (false,W.notb)     fun notb x = computeUnary (false,W.notb) x
93     val add  = compute (true,W.+)     fun add  x = compute (true,W.+) x
94     val addt = computeTrap (Int.+)     fun addt x = computeTrap (Int.+) x
95     val sub  = compute (true,W.-)     fun sub  x = compute (true,W.-) x
96     val subt = computeTrap (Int.-)     fun subt x = computeTrap (Int.-) x
97     val muls = compute (true,W.* )     fun muls x = compute (true,W.* ) x
98     val mulu = compute (false,W.* )     fun mulu x = compute (false,W.* ) x
99     val mult = computeTrap (Int.* )     fun mult x = computeTrap (Int.* ) x
100     val divs = compute (true,W.div)     fun divs x = compute (true,W.div) x
101     val divu = compute (false,W.div)     fun divu x = compute (false,W.div) x
102     val divt = computeTrap (Int.div)     fun divt x = computeTrap (Int.div) x
103     val rems = compute (true,W.mod)     fun rems x = compute (true,W.mod) x
104     val remu = compute (false,W.mod)     fun remu x = compute (false,W.mod) x
105     val remt = computeTrap (Int.mod)     fun remt x = computeTrap (Int.mod) x
106
107        (* Evaluate an integer comparison *)        (* Evaluate an integer comparison *)
108     fun cmp (signed,rel) (ty,a,b) =     fun cmp (signed,rel) (ty,a,b) =
# Line 112  Line 118
118         else rel(a,b)         else rel(a,b)
119     end     end
120
121     val gt  = cmp (true,W.>)     fun gt  x = cmp (true,W.>) x
122     val lt  = cmp (true,W.<)     fun lt  x = cmp (true,W.<) x
123     val ge  = cmp (true,W.>=)     fun ge  x = cmp (true,W.>=) x
124     val le  = cmp (true,W.<=)     fun le  x = cmp (true,W.<=) x
125     val gtu = cmp (false,W.>)     fun gtu x = cmp (false,W.>) x
126     val ltu = cmp (false,W.<)     fun ltu x = cmp (false,W.<) x
127     val geu = cmp (false,W.>=)     fun geu x = cmp (false,W.>=) x
128     val leu = cmp (false,W.<=)     fun leu x = cmp (false,W.<=) x
129
130        (* Evaluate a comparison *)        (* Evaluate a comparison *)
131     fun evalcc(T.CMP(ty,cond,a,b)) =     fun evalcc(T.CMP(ty,cond,a,b)) =
# Line 143  Line 149
149       | evalcc(T.CCMARK(e,_)) = evalcc e       | evalcc(T.CCMARK(e,_)) = evalcc e
150       | evalcc _ = UNKNOWN       | evalcc _ = UNKNOWN
151
152     fun sim e =     fun sim ==> e =
153     let (* traverse and simplify *)     let
val e =
case e of
| T.SUB(ty,a,b)  => T.SUB(ty, sim a, sim b)
| T.MULS(ty,a,b) => T.MULS(ty, sim a, sim b)
| T.DIVS(ty,a,b) => T.DIVS(ty, sim a, sim b)
| T.REMS(ty,a,b) => T.REMS(ty, sim a, sim b)
| T.MULU(ty,a,b) => T.MULU(ty, sim a, sim b)
| T.DIVU(ty,a,b) => T.DIVU(ty, sim a, sim b)
| T.REMU(ty,a,b) => T.REMU(ty, sim a, sim b)
| T.SUBT(ty,a,b) => T.SUBT(ty, sim a, sim b)
| T.MULT(ty,a,b) => T.MULT(ty, sim a, sim b)
| T.DIVT(ty,a,b) => T.DIVT(ty, sim a, sim b)
| T.REMT(ty,a,b) => T.REMT(ty, sim a, sim b)
| T.ANDB(ty,a,b) => T.ANDB(ty, sim a, sim b)
| T.ORB(ty,a,b)  => T.ORB(ty, sim a, sim b)
| T.XORB(ty,a,b) => T.XORB(ty, sim a, sim b)
| T.NOTB(ty,a)   => T.NOTB(ty, sim a)
| T.SRA(ty,a,b)  => T.SRA(ty, sim a, sim b)
| T.SRL(ty,a,b)  => T.SRL(ty, sim a, sim b)
| T.SLL(ty,a,b)  => T.SLL(ty, sim a, sim b)
| T.CVTI2I(ty,ext,ty',a) => T.CVTI2I(ty,ext,ty',sim a)
| T.CVTF2I(ty,round,fty,a) => T.CVTF2I(ty,round,fty,simF a)
| T.COND(ty,cc,a,b) => T.COND(ty, simCC cc, sim a, sim b)
| T.SEQ(stm,e) => T.SEQ(simStm stm, sim e)
| T.EXT(ty, rext, es) => T.EXT(ty, rext, map sim es)
| T.MARK(e,an) => T.MARK(sim e, an)
| e => e

154       (* algebraic simplification and constant folding *)       (* algebraic simplification and constant folding *)
155        fun ADD(e,f,ty,a,(T.LI 0 | T.LI32 0w0)) = a        fun ADD(e,f,ty,a,(T.LI 0 | T.LI32 0w0)) = a
156          | ADD(e,f,ty,(T.LI 0 | T.LI32 0w0),a) = a          | ADD(e,f,ty,(T.LI 0 | T.LI32 0w0),a) = a
158                if ty = addressWidth then
159                (case (a, b) of
160                  (T.LABEL le, T.LI n) => T.LABEL(LE.PLUS(le,LE.INT n))
161                | (T.LI n, T.LABEL le) => T.LABEL(LE.PLUS(le,LE.INT n))
162                | (T.LABEL le, T.LABEL le') => T.LABEL(LE.PLUS(le,le'))
163                | _ => f(e,ty,a,b)
164                ) else f(e,ty,a,b)
165        fun SUB(e,f,ty,a,(T.LI 0 | T.LI32 0w0)) = a        fun SUB(e,f,ty,a,(T.LI 0 | T.LI32 0w0)) = a
166          | SUB(e,f,ty,a,b) = f(e,ty,a,b)          | SUB(e,f,ty,a,b) =
167                if ty = addressWidth then
168                (case (a, b) of
169                  (T.LABEL le, T.LI n) => T.LABEL(LE.MINUS(le,LE.INT n))
170                | (T.LI n, T.LABEL le) => T.LABEL(LE.MINUS(LE.INT n,le))
171                | (T.LABEL le, T.LABEL le') => T.LABEL(LE.MINUS(le,le'))
172                | _ => f(e,ty,a,b)
173                ) else f(e,ty,a,b)
174        fun MUL(e,f,ty,a,b as (T.LI 0 | T.LI32 0w0)) = b        fun MUL(e,f,ty,a,b as (T.LI 0 | T.LI32 0w0)) = b
175          | MUL(e,f,ty,a as (T.LI 0 | T.LI32 0w0),b) = a          | MUL(e,f,ty,a as (T.LI 0 | T.LI32 0w0),b) = a
176          | MUL(e,f,ty,a,(T.LI 1 | T.LI32 0w1)) = a          | MUL(e,f,ty,a,(T.LI 1 | T.LI32 0w1)) = a
# Line 205  Line 193
193        fun SHIFT(e,f,ty,a,(T.LI 0 | T.LI32 0w0)) = a        fun SHIFT(e,f,ty,a,(T.LI 0 | T.LI32 0w0)) = a
194          | SHIFT(e,f,ty,a as (T.LI 0 | T.LI32 0w0),b) = a          | SHIFT(e,f,ty,a as (T.LI 0 | T.LI32 0w0),b) = a
195          | SHIFT(e,f,ty,a,b) = f(e,ty,a,b)          | SHIFT(e,f,ty,a,b) = f(e,ty,a,b)
196        fun CVTI2I(e,ty,ext,ty',a) = e        fun SX(e,ty,ty',a) = e
197          fun ZX(e,ty,ty',a) = e
198     in (* perform algebraic simplification and constant folding *)     in (* perform algebraic simplification and constant folding *)
199        case e of        case e of
# Line 240  Line 229
229        | T.SRL(ty,a,b)  => SHIFT(e,srl,ty,a,b)        | T.SRL(ty,a,b)  => SHIFT(e,srl,ty,a,b)
230        | T.SLL(ty,a,b)  => SHIFT(e,sll,ty,a,b)        | T.SLL(ty,a,b)  => SHIFT(e,sll,ty,a,b)
231
232        | T.CVTI2I(ty,ext,ty',a) => CVTI2I(e,ty,ext,ty',a)        | T.CVTI2I(ty,T.SIGN_EXTEND,ty',a) => SX(e,ty,ty',a)
233          | T.CVTI2I(ty,T.ZERO_EXTEND,ty',a) => ZX(e,ty,ty',a)
234
235        | T.COND(ty,cc,a,b) =>        | T.COND(ty,cc,a,b) =>
236            (case evalcc cc of TRUE => a | FALSE => b | UNKNOWN => e)            (case evalcc cc of TRUE => a | FALSE => b | UNKNOWN => e)
237        | e => e        | e => e
238     end     end
239
240     and simStm s =     and simStm ==> (s as T.IF(ctrl,cc,s1,s2)) = (* dead code elimination *)
let val s =
case s of
T.MV(ty,dst,e) => T.MV(ty,dst,sim e)
| T.CCMV(dst,cc) => T.CCMV(dst,simCC cc)
| T.FMV(fty,dst,e) => T.FMV(fty,dst,simF e)
| T.JMP(e,labs) => T.JMP(sim e,labs)
| T.CALL(e,defs,uses,mem) => T.CALL(sim e,defs,uses,mem)
| T.STORE(ty,a,b,mem) => T.STORE(ty,sim a,sim b,mem)
| T.STORE_UNALIGNED(ty,a,b,mem) =>
T.STORE_UNALIGNED(ty,sim a,sim b,mem)
| T.FSTORE(fty,a,b,mem) => T.FSTORE(fty,sim a,simF b,mem)
| T.FSTORE_UNALIGNED(fty,a,b,mem) =>
T.FSTORE_UNALIGNED(fty,sim a,simF b,mem)
| T.BCC(cond,cc,lab) => T.BCC(cond,simCC cc,lab)
| T.FBCC(fcond,cc,lab) => T.FBCC(fcond,simCC cc,lab)
| T.ANNOTATION(s,an) => T.ANNOTATION(simStm s,an)
| s => s
in case s of
T.BCC(cond,cc,lab) => (* dead code elimination *)
241                  (case evalcc cc of                  (case evalcc cc of
242                     TRUE => T.JMP(T.LABEL(LabelExp.LABEL lab),[lab])             TRUE => s1
243                   | FALSE => NOP           | FALSE => s2
244                   | UNKNOWN => s                   | UNKNOWN => s
245                  )                  )
246            | s => s       | simStm ==> s = s
end
247
248     and simF e =     and simF ==> (exp as T.FNEG(ty,T.FNEG(ty',e))) = if ty = ty' then e else exp
249         let val exp = case e of       | simF ==> exp = exp
| T.FSUB(fty,a,b) => T.FSUB(fty,simF a,simF b)
| T.FMUL(fty,a,b) => T.FMUL(fty,simF a,simF b)
| T.FDIV(fty,a,b) => T.FDIV(fty,simF a,simF b)
| T.FABS(fty,a)   => T.FABS(fty,simF a)
| T.FNEG(fty,a)   => T.FNEG(fty,simF a)
| T.FSQRT(fty,a)  => T.FSQRT(fty,simF a)
| T.CVTI2F(fty,ext,ty,e) => T.CVTI2F(fty,ext,ty,sim e)
| T.CVTF2F(fty,round,fty',e) => T.CVTF2F(fty,round,fty',simF e)
| T.FSEQ(s,e) => T.FSEQ(simStm s,simF e)
| T.FEXT(fty,fext,es) => T.FEXT(fty,fext,map simF es)
| T.FMARK(e,an) => T.FMARK(simF e,an)
| e => e
in case exp of
T.FNEG(ty,T.FNEG(ty',e)) => if ty = ty' then e else exp
| exp => exp
end
250
251    and simCC e =     and simCC ==> (exp as T.CMP _) =
252        let val e = case e of         (case evalcc exp of
253              T.CMP(ty,cond,a,b) => T.CMP(ty,cond,sim a,sim b)           TRUE => ALWAYS_TRUE | FALSE => ALWAYS_FALSE | UNKNOWN => exp
| T.FCMP(fty,fcond,a,b) => T.FCMP(fty,fcond,simF a,simF b)
| T.CCMARK(e,an) => T.CCMARK(simCC e,an)
| e => e
in  case e of
T.CMP _ =>
(case evalcc e of
TRUE => ALWAYS_TRUE | FALSE => ALWAYS_FALSE | UNKNOWN => e
254                 )                 )
255            | e => e       | simCC ==> exp = exp
end
256
257     val simplify = simStm     in R.rewrite ext {rexp=sim,fexp=simF,ccexp=simCC,stm=simStm} end
val simplifyRexp = sim
val simplifyFexp = simF
val simplifyCCexp = simCC
258  end  end

Legend:
 Removed from v.476 changed lines Added in v.545