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/SSA/ssa-const-folding.sml
ViewVC logotype

Annotation of /sml/trunk/src/MLRISC/SSA/ssa-const-folding.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 227 - (view) (download)
Original Path: sml/branches/SMLNJ/src/MLRISC/SSA/ssa-const-folding.sml

1 : monnier 221 functor SSAConstantFoldingFn(SSA : SSA) : SSA_CONSTANT_FOLDING =
2 :     struct
3 :    
4 :     structure SSA = SSA
5 :     structure SP = SSA.SP
6 :     structure E = SSAExp
7 :     structure G = Graph
8 :    
9 :     type valnum = int
10 :    
11 :     val bot = ~98765432
12 :     val top = ~10000000
13 :     val volatile = ~12345678 (* this value is not equal to itself! *)
14 :     val zero = ~1
15 :     val one = ~2
16 :    
17 :     fun error msg = MLRiscErrorMsg.impossible("SSAConstantFolding."^msg)
18 :    
19 :     fun hashOp(opcode,rs) =
20 :     let fun sum([],h) = h
21 :     | sum(r::rs,h) = sum(rs,h+r)
22 :     in sum(rs,E.hash opcode) end
23 :    
24 :     (*
25 :     * For everything except
26 :     *)
27 :     fun equalOp((op1 : E.exp,rs1 : int list),(op2 : E.exp,rs2 : int list)) =
28 :     op1 = op2 andalso
29 :     let fun eqList(a::b,c::d) =
30 :     a <> ~12345678 andalso a = c andalso eqList(b,d)
31 :     | eqList([],[]) = true
32 :     | eqList(_,_) = false
33 :     in eqList(rs1,rs2) end
34 :    
35 :     fun word i = word i
36 :     fun orb(i,j) = Word.toInt(Word.orb(word i,word j))
37 :     fun andb(i,j) = Word.toInt(Word.andb(word i,word j))
38 :     fun xorb(i,j) = Word.toInt(Word.xorb(word i,word j))
39 :     fun notb i = Word.toInt(Word.notb(word i))
40 :     fun sll(i,j) = Word.toInt(Word.<<(word i,word j))
41 :     fun srl(i,j) = Word.toInt(Word.>>(word i,word j))
42 :     fun sra(i,j) = Word.toInt(Word.~>>(word i,word j))
43 :    
44 :     fun cmp(E.EQ,i,j) = if i = j then ~2 else ~1
45 :     | cmp(E.NE,i,j) = if i <> j then ~2 else ~1
46 :     | cmp(E.LT,i,j) = if i < j then ~2 else ~1
47 :     | cmp(E.LE,i,j) = if i <= j then ~2 else ~1
48 :     | cmp(E.GT,i,j) = if i > j then ~2 else ~1
49 :     | cmp(E.GE,i,j) = if i >= j then ~2 else ~1
50 :     | cmp(E.LTU,i,j) = if word i < word j then ~2 else ~1
51 :     | cmp(E.LEU,i,j) = if word i <= word j then ~2 else ~1
52 :     | cmp(E.GTU,i,j) = if word i > word j then ~2 else ~1
53 :     | cmp(E.GEU,i,j) = if word i >= word j then ~2 else ~1
54 :     | cmp(E.SETCC,_,_) = error "cmp"
55 :    
56 :     fun hashTable (n,exn) =
57 :     HashTable.create{== = equalOp,hash=hashOp,size=n,exn=exn}
58 :    
59 :     val LT = E.BINOP(E.CMP E.LT,E.I32,E.ID 0,E.ID 1)
60 :     val LE = E.BINOP(E.CMP E.LE,E.I32,E.ID 0,E.ID 1)
61 :     val LTU = E.BINOP(E.CMP E.LTU,E.I32,E.ID 0,E.ID 1)
62 :     val LEU = E.BINOP(E.CMP E.LEU,E.I32,E.ID 0,E.ID 1)
63 :     (*
64 :     * Compute the value number
65 :     *)
66 :     fun constantFolding (SSA as G.GRAPH ssa) lookup =
67 :     let val const = SSA.const SSA
68 :     val immed = SSA.immed SSA
69 :    
70 :     fun process(e as E.UNARY(opcode,E.I32,E.ID 0),xs as [x],w) =
71 :     if x < 0 then unary(e,opcode,xs,x,w)
72 :     else lookup(e,xs,w)
73 :     | process(e as E.BINOP(opcode,E.I32,E.ID 0,E.ID 1),xs as [x,y],w) =
74 :     binop(e,opcode,xs,x,y,w)
75 :     | process(E.LI,[a],_) = a
76 :     | process(E.COPY,[a],_) = a
77 :     | process(e as E.PHI _,xs,w) =
78 :     let fun uniq([],x) = x
79 :     | uniq(v::vs,~10000000) = uniq(vs,v)
80 :     | uniq(v::vs,x) = if x = v then uniq(vs,x)
81 :     else lookup(e,xs,w)
82 :     in uniq(xs,~10000000)
83 :     end
84 :     | process(e,xs,w) = lookup(e,xs,w)
85 :    
86 :     (* constant folding for unary operators *)
87 :     and unary(e,opcode,xs,x,w) =
88 :     case (opcode,const x) of
89 :     (E.NEG,SP.IMMED i) => immed(~i)
90 :     | (E.NOT,SP.IMMED i) => immed(if i = ~1 then ~2 else ~1)
91 :     | (E.NOTB,SP.IMMED i) => immed(notb i)
92 :     | (E.ABS,SP.IMMED i) => immed(if i < 0 then ~i else i)
93 :     | _ => lookup(e,xs,w)
94 :    
95 :     (* constant folding for binary operators *)
96 :     and binop(e,opcode,xs,x,y,w) =
97 :     if x < 0 andalso y < 0 then
98 :     (case (const x,const y) of
99 :     (SP.IMMED i, SP.IMMED j) =>
100 :     ((case opcode of
101 :     (E.ADD | E.ADDT) => immed(i + j)
102 :     | (E.SUB | E.SUBT) => immed(i - j)
103 :     | (E.MUL | E.MULT) => immed(i * j)
104 :     | (E.DIV | E.DIVT) => immed(i div j)
105 :     | (E.MOD | E.MODT) => immed(i mod j)
106 :     | E.ANDB => immed(andb(i,j))
107 :     | E.ORB => immed(orb(i,j))
108 :     | E.XORB => immed(xorb(i,j))
109 :     | E.SRA => immed(sra(i,j))
110 :     | E.SRL => immed(srl(i,j))
111 :     | E.SLL => immed(sll(i,j))
112 :     | E.CMP E.SETCC => simplify(e,opcode,xs,x,y,w)
113 :     | E.CMP cc => immed(cmp(cc,i,j))
114 :     | _ => simplify(e,opcode,xs,x,y,w)
115 :     ) handle (Div | Overflow) => simplify(e,opcode,xs,x,y,w))
116 :     | _ => simplify(e,opcode,xs,x,y,w)
117 :     )
118 :     else simplify(e,opcode,xs,x,y,w)
119 :    
120 :     (* algebraic simplification *)
121 :     and simplify(e,binop,xs,x,y,w) =
122 :     (case (binop,x,y) of
123 :     ((E.ADD|E.ADDT|E.ORB),~1,y) => y
124 :     | ((E.ADD|E.ADDT|E.ORB|E.SUB|E.SUBT),x,~1) => x
125 :     | ((E.SUB|E.SUBT),x,y) => if x = y then ~1 else lookup(e,xs,w)
126 :     | ((E.MUL|E.MULT|E.ANDB|E.DIV|E.DIVT|E.MOD|E.MODT),~1,_) => ~1
127 :     | ((E.MUL|E.MULT|E.ANDB),x,~1) => ~1
128 :     | ((E.MUL|E.MULT),~2,y) => y
129 :     | ((E.MUL|E.MULT|E.DIV|E.DIVT),x,~2) => y
130 :     | (E.CMP E.EQ,x,y) => if x = y then ~2 else
131 :     normalize(e,binop,xs,x,y,w)
132 :     | (E.CMP E.NE,x,y) => if x = y then ~1 else
133 :     normalize(e,binop,xs,x,y,w)
134 :     | (E.CMP E.GTU,x,~1) => ~2 (* true *)
135 :     | (E.CMP E.LTU,~1,y) => ~1 (* false *)
136 :     | _ => normalize(e,binop,xs,x,y,w)
137 :     )
138 :    
139 :     (*
140 :     * normalize commutative operators
141 :     *)
142 :     and normalize(e,binop,xs,x,y,w) =
143 :     let val (e',xs') =
144 :     case binop of
145 :     (E.ADD | E.ADDT | E.MUL | E.MULT | E.ANDB | E.ORB | E.XORB
146 :     | E.CMP E.EQ | E.CMP E.NE) =>
147 :     (e,if x < y then xs else [y,x])
148 :     | E.CMP E.GT => (LT,[y,x])
149 :     | E.CMP E.GE => (LE,[y,x])
150 :     | E.CMP E.GTU => (LTU,[y,x])
151 :     | E.CMP E.GEU => (LEU,[y,x])
152 :     | _ => (e,xs)
153 :     in lookup(e',xs',w)
154 :     end
155 :     in process
156 :     end
157 :    
158 :     end
159 :    
160 :     (*
161 : monnier 227 * $Log$
162 : monnier 221 *)

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