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

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

Parent Directory Parent Directory | Revision Log Revision Log


Revision 695 - (view) (download)

1 : leunga 695 (*
2 :     * Partial redundancy elimination.
3 :     * This is my own algorithm.
4 :     *
5 :     * -- Allen (leunga@cs.nyu.edu)
6 :     *)
7 :     functor SSAPRE(SSA : SSA) : SSA_OPTIMIZATION =
8 :     struct
9 :     structure SSA = SSA
10 :     structure SP = SSA.SP
11 :     structure RTL = SSA.RTL
12 :     structure Dom = SSA.Dom
13 :     structure T = RTL.T
14 :     structure G = Graph
15 :     structure A = Array
16 :    
17 :     type flowgraph = SSA.ssa
18 :    
19 :     fun error msg = MLRiscErrorMsg.error("SSAPRE",msg)
20 :    
21 :     val preRemoved = MLRiscControl.getCounter "ssa-partial-redundancy-removed"
22 :    
23 :     val name = "Partial Redundancy Elimination"
24 :    
25 :     (*
26 :     * Redundancy elimination is driven by frequency.
27 :     * Given:
28 :     *
29 :     * t <- phi(t1, t2, ..., tn)
30 :     * ...
31 :     * v <- f(t)
32 :     *
33 :     * f(t) is partially redundant if it is cheaper to transform it
34 :     * into:
35 :     *
36 :     * v1 <- f(v1)
37 :     * v2 <- f(v2)
38 :     * ...
39 :     * vn <- f(vn)
40 :     *
41 :     * v <- phi(v1, v2, ..., vn)
42 :     * t <- phi(t1, t2, ..., tn)
43 :     *)
44 :    
45 :     fun run(SSA as G.GRAPH ssa) =
46 :     let val Dom as G.GRAPH dom = SSA.dom SSA
47 :    
48 :     val dominates = Dom.dominates Dom
49 :     val levels = Dom.levelsMap Dom
50 :    
51 :     val defSite = SSA.defSite SSA
52 :     val block = SSA.block SSA
53 :     val uses = SSA.uses SSA
54 :     val defs = SSA.defs SSA
55 :     val rtl = SSA.rtl SSA
56 :     val freqTbl = SSA.freqTbl SSA
57 :    
58 :     val showOp = SSA.showOp SSA
59 :     val showVal = SSA.showVal SSA
60 :    
61 :     fun process i =
62 :     case rtl i of
63 :     T.PHI{preds, ...} => hoistAllUses(i,preds)
64 :     | _ => ()
65 :    
66 :     (* hoist uses of phi-node i *)
67 :     and hoistAllUses(i,preds) =
68 :     let val [t] = defs i
69 :     val uses_i = uses i
70 :    
71 :     (* find partially redundant phi nodes *)
72 :     in if List.exists (fn v => v = t) uses_i then
73 :     print("PRE "^showOp i^"\n") else ()
74 :     end
75 :    
76 :     in SSA.forallNodes SSA process;
77 :     SSA
78 :     end
79 :    
80 :     end

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