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 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.ADD(ty,a,b)  => T.ADD(ty, sim a, sim b)  
          | 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.ADDT(ty,a,b) => T.ADDT(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.LOAD(ty,a,mem) => T.LOAD(ty, sim a, mem)  
          | T.LOAD_UNALIGNED(ty,a,mem) => T.LOAD_UNALIGNED(ty, sim a, mem)  
          | 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
157          | ADD(e,f,ty,a,b) = f(e,ty,a,b)          | ADD(e,f,ty,a,b) =
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
200          T.ADD(ty,a,b)  => ADD(e,add,ty,a,b)          T.ADD(ty,a,b)  => ADD(e,add,ty,a,b)
# 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.FLOAD(fty,e,mem) => T.FLOAD(fty,sim e,mem)  
            | T.FLOAD_UNALIGNED(fty,e,mem) => T.FLOAD_UNALIGNED(fty,sim e,mem)  
            | T.FADD(fty,a,b) => T.FADD(fty,simF a,simF b)  
            | 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

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