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-exp.sml
ViewVC logotype

Annotation of /sml/trunk/src/MLRISC/SSA/ssa-exp.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 221 - (view) (download)

1 : monnier 221 structure SSAExp : SSA_EXP =
2 :     struct
3 :    
4 :     infix &&
5 :    
6 :     fun x && y = Word.andb(Word.fromInt x,Word.fromInt y) <> 0w0
7 :    
8 :     fun error msg = MLRiscErrorMsg.impossible("SSAExp."^msg)
9 :    
10 :     datatype cond = LT | LTU | LE | LEU | EQ | NE | GE | GEU | GT | GTU
11 :     | VC | VS | SETCC
12 :     datatype fcond = ? | !<=> | == | ?= | !<> | !?>= | < | ?< | !>= | !?> |
13 :     <= | ?<= | !> | !?<= | > | ?> | !<= | !?< | >= | ?>= |
14 :     !< | !?= | <> | != | !? | <=> | SETFCC
15 :    
16 :     (* supported types *)
17 :     datatype ty = I8 | U8 | I16 | U16 | I32 | U32 | I64 | U64 | F | D
18 :    
19 :     (* arithmetic operations *)
20 :     datatype binop = ADD | SUB | MUL | DIV | MOD
21 :     | ADDT | SUBT | MULT | DIVT | MODT
22 :     | ANDB | ORB | XORB | SRA | SRL | SLL
23 :     | CMP of cond | FCMP of fcond | SET of cond
24 :     | TRAP of cond
25 :    
26 :     datatype unary = ABS | NEG | NOT | NOTB | SQRT | CVT of ty
27 :     | CC of cond | FCC of fcond
28 :    
29 :     datatype exp =
30 :     LI
31 :     | ID of int
32 :     | XFER
33 :     | COPY
34 :     | PC
35 :     | BINOP of binop * ty * exp * exp
36 :     | UNARY of unary * ty * exp
37 :     | LOAD of ty * exp (* addr *)
38 :     | STORE of ty * exp * exp (* data addr *)
39 :     | INIT of ty * exp * exp (* data addr *)
40 :     | DEALLOC of exp
41 :     | JMP of exp
42 :     | BRANCH of exp
43 :     | RET
44 :     | CALL of exp
45 :     | NOP
46 :     | PAR of exp list
47 :     | PHI of int
48 :     | PINNED of exp
49 :     | MISC of {hash:int, arity:int, name:string, attribs:int} ref
50 :    
51 :     val A_TRAPPING = 0x1
52 :     val A_PINNED = 0x2
53 :     val A_MUTATOR = 0x4
54 :     val A_LOOKER = 0x8
55 :     val A_PURE = 0x10
56 :    
57 :     fun tyToString ty =
58 :     case ty of
59 :     I8 => "8"
60 :     | U8 => "u8"
61 :     | I16 => "16"
62 :     | U16 => "u16"
63 :     | I32 => ""
64 :     | U32 => "u"
65 :     | I64 => "64"
66 :     | U64 => "u64"
67 :     | F => "f"
68 :     | D => "d"
69 :    
70 :     fun condToString cond =
71 :     case cond of
72 :     LT => "<"
73 :     | LTU => "<u"
74 :     | LE => "<="
75 :     | LEU => "<=u"
76 :     | EQ => "="
77 :     | NE => "!="
78 :     | GE => ">="
79 :     | GEU => ">=u"
80 :     | GT => ">"
81 :     | GTU => ">=u"
82 :     | VC => "vc"
83 :     | VS => "vs"
84 :     | SETCC => "cc"
85 :    
86 :     fun fcondToString c =
87 :     case c of
88 :     ? => "?"
89 :     | !<=> => "!<=>"
90 :     | == => "=="
91 :     | ?= => "?="
92 :     | !<> => "!<>"
93 :     | !?>= => "!?>="
94 :     | op < => "<"
95 :     | ?< => "?<"
96 :     | !>= => "!>="
97 :     | !?> => "!?>"
98 :     | op <= => "<="
99 :     | ?<= => "?<="
100 :     | !> => "!>"
101 :     | !?<= => "!?<="
102 :     | op > => ">"
103 :     | ?> => "?>"
104 :     | !<= => "!<="
105 :     | !?< => "!?<"
106 :     | op >= => ">="
107 :     | ?>= => "?>="
108 :     | !< => "!<"
109 :     | !?= => "!?="
110 :     | op <> => "<>"
111 :     | != => "!="
112 :     | !? => "!?"
113 :     | <=> => "<=>"
114 :     | SETFCC => "fcc"
115 :    
116 :     fun binopToString a =
117 :     case a of
118 :     ADD => "add"
119 :     | SUB => "sub"
120 :     | MUL => "mul"
121 :     | DIV => "div"
122 :     | MOD => "mod"
123 :     | ADDT => "addt"
124 :     | SUBT => "subt"
125 :     | MULT => "mult"
126 :     | DIVT => "divt"
127 :     | MODT => "modt"
128 :     | ANDB => "andb"
129 :     | ORB => "orb"
130 :     | XORB => "xorb"
131 :     | SRA => "sra"
132 :     | SRL => "srl"
133 :     | SLL => "sll"
134 :     | CMP c => "cmp"^condToString c
135 :     | FCMP c => "fcmp"^fcondToString c
136 :     | SET c => "set"^condToString c
137 :     | TRAP c => "trap"^condToString c
138 :    
139 :     fun unaryToString a =
140 :     case a of
141 :     ABS => "abs"
142 :     | NEG => "neg"
143 :     | NOT => "not"
144 :     | NOTB => "notb"
145 :     | SQRT => "sqrt"
146 :     | CVT ty => "cvt"^tyToString ty
147 :     | CC cc => condToString cc
148 :     | FCC cc => fcondToString cc
149 :    
150 :     fun list (l,sep,r) f es =
151 :     l^List.foldr (fn (x,"") => f x | (x,s) => f x^sep^s) "" es^r
152 :    
153 :     fun toString args =
154 :     let fun paren e = "("^exp e^")"
155 :     and exps es = list ("(",",",")") exp es
156 :     and seqs es = exps es
157 :     and arg i = List.nth(args,i) handle Subscript => "?"
158 :     and allArgs() = list ("(",",",")") (fn x => x) args
159 :     and argn n = list ("(",",",")") (fn x => x) (List.take(args,n))
160 :     and exp e =
161 :     case e of
162 :     LI => "li("^arg 0^")"
163 :     | XFER => "xfer("^arg 0^")"
164 :     | COPY => "copy"^allArgs()
165 :     | PC => "pc"
166 :     | ID i => (List.nth(args,i) handle Subscript => "?")
167 :     | BINOP(a,t,x,y) => binopToString a^tyToString t^exps[x,y]
168 :     | UNARY(a,t,x) => unaryToString a^tyToString t^paren x
169 :     | LOAD(t,a) => "load"^tyToString t^paren a
170 :     | STORE(t,x,a) => "store"^tyToString t^exps[x,a]
171 :     | INIT(t,x,a) => "init"^tyToString t^exps[x,a]
172 :     | DEALLOC e => "dealloc"^paren e
173 :     | JMP e => "jmp"^paren e
174 :     | BRANCH e => "branch"^paren e
175 :     | RET => "ret"
176 :     | CALL e => "call"^allArgs()
177 :     | NOP => "nop"
178 :     | PAR es => seqs es
179 :     | PHI b => "phi["^Int.toString b^"]"
180 :     | PINNED e => exp e
181 :     | MISC(ref{name,arity,...}) => name^argn arity
182 :     in exp
183 :     end
184 :    
185 :     fun hashTy ty =
186 :     case ty of
187 :     I8 => 12
188 :     | U8 => 15
189 :     | I16 => 58
190 :     | U16 => 919
191 :     | I32 => 123
192 :     | U32 => 1651
193 :     | I64 => 889
194 :     | U64 => 321
195 :     | F => 789
196 :     | D => 2368
197 :    
198 :     fun hashCond cond =
199 :     case cond of
200 :     LT => 0
201 :     | LTU => 64
202 :     | LE => 128
203 :     | LEU => 192
204 :     | EQ => 256
205 :     | NE => 512
206 :     | GE => 1024
207 :     | GEU => 2048
208 :     | GT => 3172
209 :     | GTU => 4096
210 :     | VC => 3455
211 :     | VS => 24515
212 :     | SETCC => 1312
213 :    
214 :     fun hashFcond fcond =
215 :     case fcond of
216 :     ? => 1
217 :     | !<=> => 2
218 :     | == => 3
219 :     | ?= => 123
220 :     | !<> => 12412
221 :     | !?>= => 5837
222 :     | op < => 35
223 :     | ?< => 1234
224 :     | !>= => 125534
225 :     | !?> => 12385
226 :     | op <= => 857349
227 :     | ?<= => 683
228 :     | !> => 1245
229 :     | !?<= => 124984
230 :     | op > => 1234
231 :     | ?> => 132584
232 :     | !<= => 12837
233 :     | !?< => 75738
234 :     | op >= => 234
235 :     | ?>= => 881
236 :     | !< => 91
237 :     | !?= => 483
238 :     | op <> => 54738
239 :     | != => 1234
240 :     | !? => 4638
241 :     | <=> => 56483
242 :     | SETFCC => 123145
243 :    
244 :     fun hashBinop a =
245 :     case a of
246 :     ADD => 1341
247 :     | SUB => 142515
248 :     | MUL => 131
249 :     | DIV => 514
250 :     | MOD => 15151
251 :     | ADDT => 41341
252 :     | SUBT => 4142515
253 :     | MULT => 4131
254 :     | DIVT => 4514
255 :     | MODT => 415151
256 :     | ANDB => 1351
257 :     | ORB => 591
258 :     | XORB => 4980
259 :     | SRA => 8591
260 :     | SRL => 17541
261 :     | SLL => 3128
262 :     | CMP(c) => 5000 + hashCond c
263 :     | FCMP(c) => 6000 + hashFcond c
264 :     | SET(c) => 7000 + hashCond c
265 :     | TRAP(c)=> 8000 + hashCond c
266 :    
267 :     fun hashUnary a =
268 :     case a of
269 :     ABS => 12434
270 :     | NEG => 49
271 :     | NOT => 4414
272 :     | NOTB => 245
273 :     | SQRT => 3445
274 :     | CVT _ => 123
275 :     | CC cc => 145134 + hashCond cc
276 :     | FCC cc => 5155 + hashFcond cc
277 :    
278 :     fun hash e =
279 :     case e of
280 :     LI => 0
281 :     | XFER => 500
282 :     | COPY => 1000
283 :     | PC => 1500
284 :     | ID i => 2000 + i
285 :     | BINOP(a,t,x,y) => 3000 + hashBinop a + hashTy t + hash x + hash y
286 :     | UNARY(a,t,x) => 4000 + hashUnary a + hashTy t + hash x
287 :     | LOAD(t,a) => 8000 + hashTy t + hash a
288 :     | STORE(t,x,a) => 9000 + hashTy t + hash x + hash a
289 :     | INIT(t,x,a) => 9500 + hashTy t + hash x + hash a
290 :     | DEALLOC e => 32000 + hash e
291 :     | JMP e => 10000 + hash e
292 :     | BRANCH e => 22000 + hash e
293 :     | RET => 13000
294 :     | CALL e => 14000 + hash e
295 :     | NOP => 16000
296 :     | PAR es => 17000 + hashExps es
297 :     | PHI b => 18000 + b
298 :     | PINNED e => hash e
299 :     | MISC(ref{hash,...}) => hash
300 :    
301 :     and hashExps [] = 0
302 :     | hashExps (e::es) = hash e + hashExps es
303 :    
304 :     fun revCond cond =
305 :     case cond of
306 :     LT => GE
307 :     | LTU => GEU
308 :     | LE => GT
309 :     | LEU => GTU
310 :     | EQ => NE
311 :     | NE => EQ
312 :     | GE => LT
313 :     | GEU => LTU
314 :     | GT => LE
315 :     | GTU => LEU
316 :     | _ => error "revCond"
317 :    
318 :     fun revFcond ? = !?
319 :     | revFcond !<=> = <=>
320 :     | revFcond == = !=
321 :     | revFcond ?= = !?=
322 :     | revFcond !<> = op <>
323 :     | revFcond !?>= = ?>=
324 :     | revFcond op < = !<
325 :     | revFcond ?< = !?<
326 :     | revFcond !>= = op >=
327 :     | revFcond !?> = ?>
328 :     | revFcond op <= = !<=
329 :     | revFcond ?<= = !?<=
330 :     | revFcond !> = op >
331 :     | revFcond !?<= = ?<=
332 :     | revFcond op > = !>
333 :     | revFcond ?> = !?>
334 :     | revFcond !<= = op <=
335 :     | revFcond !?< = ?<
336 :     | revFcond op >= = !>=
337 :     | revFcond ?>= = !?>=
338 :     | revFcond !< = op <
339 :     | revFcond !?= = ?=
340 :     | revFcond op <> = !<>
341 :     | revFcond != = ==
342 :     | revFcond !? = ?
343 :     | revFcond <=> = !<=>
344 :     | revFcond _ = error "revFcond"
345 :    
346 :     fun isCommutative(BINOP(a,_,_,_)) = isCommutativeBinop a
347 :     | isCommutative(BRANCH e) = isCommutative e
348 :     | isCommutative _ = false
349 :    
350 :     and isCommutativeBinop(ADD | MUL | ANDB | ORB | XORB | ADDT | MULT) = true
351 :     | isCommutativeBinop(CMP(EQ | NE)) = true
352 :     | isCommutativeBinop(SET(EQ | NE)) = true
353 :     | isCommutativeBinop(TRAP(EQ | NE)) = true
354 :     | isCommutativeBinop(FCMP(== | !=)) = true
355 :     | isCommutativeBinop _ = false
356 :    
357 :     fun isTrapping(BINOP(a,_,_,_)) = isTrappingBinop a
358 :     | isTrapping(MISC(ref{attribs,...})) = attribs && A_TRAPPING
359 :     | isTrapping(CALL _) = true
360 :     | isTrapping _ = false
361 :     and isTrappingBinop(ADDT | SUBT | MULT | DIVT | MODT | TRAP _) = true
362 :     | isTrappingBinop _ = false
363 :    
364 :     fun isPinned(JMP _) = true
365 :     | isPinned(XFER) = true
366 :     | isPinned(BRANCH _) = true
367 :     | isPinned(CALL _) = true
368 :     | isPinned(RET) = true
369 :     | isPinned(STORE _) = true
370 :     | isPinned(INIT _) = true
371 :     | isPinned(DEALLOC _) = true
372 :     | isPinned(BINOP(a,_,x,y)) = isPinned x orelse isPinned y
373 :     | isPinned(UNARY(_,_,x)) = isPinned x
374 :     | isPinned(PAR es) = List.exists isPinned es
375 :     | isPinned(MISC(ref{attribs,...})) = attribs && A_PINNED
376 :     | isPinned(PINNED _) = true
377 :     | isPinned _ = false
378 :    
379 :     fun isMutator(LI) = false
380 :     | isMutator(ID _) = false
381 :     | isMutator(XFER) = false
382 :     | isMutator(COPY) = false
383 :     | isMutator(PC) = false
384 :     | isMutator(BINOP(_,_,x,y)) = isMutator x orelse isMutator y
385 :     | isMutator(UNARY(_,_,x)) = isMutator x
386 :     | isMutator(LOAD(_,e)) = isMutator e
387 :     | isMutator(STORE(_,x,y)) = true
388 :     | isMutator(INIT(_,x,y)) = true
389 :     | isMutator(DEALLOC _) = true
390 :     | isMutator(JMP x) = isMutator x
391 :     | isMutator(BRANCH x) = isMutator x
392 :     | isMutator(RET) = false
393 :     | isMutator(CALL _) = true
394 :     | isMutator(NOP) = false
395 :     | isMutator(PAR es) = List.exists isMutator es
396 :     | isMutator(PHI _) = false
397 :     | isMutator(PINNED e) = isMutator e
398 :     | isMutator(MISC(ref{attribs,...})) = attribs && A_MUTATOR
399 :    
400 :     fun isLooker(LI) = false
401 :     | isLooker(ID _) = false
402 :     | isLooker(XFER) = false
403 :     | isLooker(COPY) = false
404 :     | isLooker(PC) = false
405 :     | isLooker(BINOP(_,_,x,y)) = isLooker x orelse isLooker y
406 :     | isLooker(UNARY(_,_,x)) = isLooker x
407 :     | isLooker(LOAD(_,e)) = true
408 :     | isLooker(STORE(_,x,y)) = isLooker x orelse isLooker y
409 :     | isLooker(INIT(_,x,y)) = isLooker x orelse isLooker y
410 :     | isLooker(DEALLOC x) = isLooker x
411 :     | isLooker(JMP x) = isLooker x
412 :     | isLooker(BRANCH x) = isLooker x
413 :     | isLooker(RET) = false
414 :     | isLooker(CALL _) = true
415 :     | isLooker(NOP) = false
416 :     | isLooker(PAR es) = List.exists isLooker es
417 :     | isLooker(PHI _) = false
418 :     | isLooker(PINNED e) = isLooker e
419 :     | isLooker(MISC(ref{attribs,...})) = attribs && A_LOOKER
420 :    
421 :     fun isPure(LI) = true
422 :     | isPure(ID _) = true
423 :     | isPure(XFER) = true
424 :     | isPure(COPY) = true
425 :     | isPure(PC) = true
426 :     | isPure(BINOP(_,_,x,y)) = isPure x andalso isPure y
427 :     | isPure(UNARY(_,_,x)) = isPure x
428 :     | isPure(LOAD(_,e)) = false
429 :     | isPure(STORE(_,x,y)) = false
430 :     | isPure(INIT(_,x,y)) = false
431 :     | isPure(DEALLOC _) = false
432 :     | isPure(JMP x) = isPure x
433 :     | isPure(BRANCH x) = isPure x
434 :     | isPure(RET) = true
435 :     | isPure(CALL _) = false
436 :     | isPure(NOP) = true
437 :     | isPure(PAR es) = List.all isPure es
438 :     | isPure(PHI _) = true
439 :     | isPure(PINNED e) = isPure e
440 :     | isPure(MISC(ref{attribs,...})) = attribs && A_PURE
441 :    
442 :     fun can'tMoveDown(BRANCH _) = true
443 :     | can'tMoveDown(JMP _) = true
444 :     | can'tMoveDown(RET) = true
445 :     | can'tMoveDown(CALL _) = true
446 :     | can'tMoveDown(STORE _) = true
447 :     | can'tMoveDown(INIT _) = true
448 :     | can'tMoveDown(DEALLOC _) = true
449 :     | can'tMoveDown(LOAD _) = true
450 :     | can'tMoveDown(BINOP(a,_,_,_)) = isTrappingBinop a
451 :     | can'tMoveDown(MISC(ref{attribs,...})) = attribs && A_TRAPPING
452 :     | can'tMoveDown(PINNED _) = true
453 :     | can'tMoveDown _ = false
454 :    
455 :     fun can'tMoveUp(BRANCH _) = true
456 :     | can'tMoveUp(JMP _) = true
457 :     | can'tMoveUp(RET) = true
458 :     | can'tMoveUp(CALL _) = true
459 :     | can'tMoveUp(STORE _) = true
460 :     | can'tMoveUp(INIT _) = true
461 :     | can'tMoveUp(DEALLOC _) = true
462 :     (* | can'tMoveUp(LOAD _) = true *)
463 :     | can'tMoveUp(BINOP(a,_,_,_)) = isTrappingBinop a
464 :     | can'tMoveUp(MISC(ref{attribs,...})) = attribs && A_TRAPPING
465 :     | can'tMoveUp(PINNED _) = true
466 :     | can'tMoveUp _ = false
467 :    
468 :     val newHash = ref 123
469 :    
470 :     fun misc{name,arity,attribs} =
471 :     MISC(ref{name=name,arity=arity,hash= !newHash,attribs=attribs})
472 :     before newHash := !newHash + 89
473 :    
474 :     end
475 :    
476 :     (*
477 :     * $Log: ssa-exp.sml,v $
478 :     * Revision 1.1.1.1 1998/11/16 21:47:05 george
479 :     * Version 110.10
480 :     *
481 :     *)

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