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 /MLRISC/trunk/Glue/mlrisc-ssa-optimizer.sml
ViewVC logotype

Annotation of /MLRISC/trunk/Glue/mlrisc-ssa-optimizer.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 2126 - (view) (download)

1 : monnier 409 (*
2 :     * SSA optimizer for doing experiments
3 :     *)
4 :    
5 : george 545 functor SSAOptimizer
6 : monnier 409 (structure Asm : INSTRUCTION_EMITTER
7 : monnier 429 structure MLTreeComp : MLTREECOMP
8 : monnier 409 structure F : FLOWGRAPH
9 :     structure P : INSN_PROPERTIES
10 :     structure SP : SSA_PROPERTIES
11 : george 545 structure OperandTable : OPERAND_TABLE
12 :     structure GCTypeSys : GC_TYPE_SYSTEM
13 : monnier 409 structure FreqProps : FREQUENCY_PROPERTIES
14 : george 545 sharing P.I = SP.I = Asm.I = F.I = OperandTable.I =
15 :     FreqProps.I = MLTreeComp.I
16 : monnier 429 sharing F.P = Asm.P = MLTreeComp.T.PseudoOp
17 :     sharing MLTreeComp.T.Constant = F.I.Constant
18 : george 545 sharing SP.RTL = GCTypeSys.RTL
19 :     type sext and rext and fext and ccext
20 : monnier 429 val callgc : { id : int,
21 : george 545 msg : string,
22 : monnier 498 gcLabel : Label.label,
23 :     returnLabel : Label.label,
24 : george 545 roots : (P.I.C.cell * GCTypeSys.GC.gctype) list,
25 :     stream : (sext,rext,fext,ccext) MLTreeComp.mltreeStream
26 : monnier 429 } -> unit
27 : monnier 409 ) : SSA_OPTIMIZER =
28 :     struct
29 :    
30 :     structure F = F
31 :     structure I = F.I
32 :    
33 : monnier 429 val view_IR = MLRiscControl.getFlag "view-IR"
34 :     val verbose = MLRiscControl.getFlag "verbose"
35 :     val min_blocks = MLRiscControl.getInt "min-blocks"
36 : monnier 409
37 :     fun error msg = MLRiscErrorMsg.error("SSAOptimizer",msg)
38 :    
39 : george 545 structure GraphViewer = GraphViewer(AllDisplays)
40 : monnier 409
41 : george 545 structure FormatInsn = FormatInstruction(Asm)
42 : monnier 409
43 : george 545 structure CFG = ControlFlowGraph
44 : monnier 409 (structure I = I
45 :     structure P = F.P
46 :     structure GraphImpl = DirectedGraph
47 :     structure Asm = Asm
48 :     )
49 :    
50 : george 545 structure Util = CFGUtil
51 : monnier 409 (structure CFG = CFG
52 : monnier 429 structure P = P
53 : monnier 409 )
54 :    
55 : george 545 structure CFG2Cluster = CFG2Cluster
56 : monnier 429 (structure CFG = CFG
57 :     structure F = F
58 :     )
59 :    
60 : george 545 structure Cluster2CFG = Cluster2CFG
61 : monnier 429 (structure CFG = CFG
62 :     structure Util = Util
63 :     structure F = F
64 :     structure P = P
65 : monnier 409 )
66 :    
67 : george 545 structure Dom = DominatorTree(DirectedGraph)
68 : monnier 409
69 : george 545 structure CDG = ControlDependenceGraph
70 : monnier 409 (structure Dom = Dom
71 :     structure GraphImpl = DirectedGraph
72 :     )
73 :    
74 : george 545 structure Loop = LoopStructure
75 : monnier 409 (structure Dom = Dom
76 :     structure GraphImpl = DirectedGraph
77 :     )
78 :    
79 : george 545 structure IR = MLRISC_IR
80 : monnier 409 (structure CFG = CFG
81 :     structure CDG = CDG
82 :     structure Loop = Loop
83 :     structure GraphViewer = GraphViewer
84 :     structure Util = Util
85 :     )
86 :    
87 : george 545 structure Guess = StaticBranchPrediction
88 :     (structure IR = IR
89 :     structure Props = P
90 :     structure FreqProps = FreqProps
91 :     val loopMultiplier=10
92 :     )
93 : monnier 409
94 : george 545 structure Liveness = LivenessAnalysis(CFG)
95 : monnier 409
96 : george 545 structure SSA = SSA
97 : monnier 409 (structure CFG = CFG
98 :     structure Dom = Dom
99 :     structure SP = SP
100 : george 545 structure Props= P
101 : monnier 409 structure RTL = SP.RTL
102 :     structure FormatInsn = FormatInsn
103 :     structure GraphImpl = DirectedGraph
104 : george 545 structure GCMap = GCTypeSys.GCMap
105 : monnier 409 )
106 :    
107 : george 545 structure CFG2SSA = CFG2SSA
108 : monnier 409 (structure SSA = SSA
109 :     structure Liveness = Liveness
110 :     )
111 :    
112 : george 545 structure Reshape = ReshapeBranches(structure IR = IR
113 :     structure P = P)
114 :     structure BranchChaining = BranchChaining(structure IR = IR
115 :     structure P = P)
116 : monnier 409
117 : george 545 structure InsertPreheaders = InsertPreheaders(structure IR = IR
118 :     structure P = P)
119 : monnier 409
120 : george 545 structure SSADCE = SSADeadCodeElim(SSA)
121 : monnier 409
122 : george 545 structure CF = SSAConstantFolding(SSA)
123 : monnier 409
124 : george 545 structure GVN = SSAGlobalValueNumbering(CF)
125 : monnier 409
126 : george 545 structure CCP = SSACondConstProp(CF)
127 : monnier 409
128 : george 545 structure SSAGVN = SSAGVN(structure GVN = GVN
129 :     val leaveBehindCopy = false
130 :     val foldGlobalConstants = true)
131 : monnier 409
132 : george 545 structure SSAGVNL = SSAGVN(structure GVN = GVN
133 :     val leaveBehindCopy = false
134 :     val foldGlobalConstants = false)
135 : monnier 409
136 : george 545 structure SSAGVN' = SSAGVN(structure GVN = GVN
137 :     val leaveBehindCopy = false
138 :     val foldGlobalConstants = true)
139 : monnier 409
140 : george 545 structure SSACCP = SSACCP(CCP)
141 : monnier 409
142 : george 545 structure SSAGCM = SSAGlobalCodeMotion(SSA)
143 :     (* structure SSAGCM2 = SSAGlobalCodeMotion2(SSA) *)
144 :     (* structure Depressurize = SSADepressurize(SSA)*)
145 :    
146 :     structure SSALiveness = SSALiveness(SSA)
147 :    
148 :     structure SSA2CFG = SSA2CFG
149 : monnier 409 (structure SSA = SSA
150 :     structure Liveness = SSALiveness
151 : george 545 structure Props = P
152 : monnier 409 structure Util = Util
153 :     )
154 :    
155 : george 545 structure GCInvariants = GCInvariants
156 : monnier 429 (structure IR = IR
157 :     structure Props = P
158 : george 545 structure RTLProps = SP.RTLProps
159 :     structure OperandTable = OperandTable
160 :     structure TypeSys = GCTypeSys
161 : monnier 429 )
162 :    
163 : george 545 structure SSAGCInvariants = SSAGCInvariants
164 :     (structure SSA = SSA
165 :     structure TypeSys = GCTypeSys
166 :     )
167 :    
168 : monnier 429 structure GCGen = GCGen
169 :     (structure MLTreeComp = MLTreeComp
170 :     structure IR = IR
171 : george 545 structure GCMap = GCTypeSys.GCMap
172 : monnier 429 structure InsnProps = P
173 :     )
174 :    
175 : monnier 409 fun view phase ir = if !view_IR then IR.view phase ir else ()
176 :    
177 :     fun optimize cluster =
178 :     let datatype rep = IR of IR.IR
179 :     | CLUSTER of F.cluster
180 :     | SSA of SSA.ssa
181 : monnier 429 fun doPhase "cluster->cfg" (CLUSTER c) = IR(Cluster2CFG.cluster2cfg c)
182 : monnier 409 | doPhase "cfg->cluster" (IR cfg) =
183 :     CLUSTER(CFG2Cluster.cfg2cluster{cfg=cfg,relayout=false})
184 : george 545 | doPhase "guess" (r as IR ir) = (Guess.run ir; r)
185 :     | doPhase "reshape" (r as IR ir) = (Reshape.run ir; r)
186 :     | doPhase "branch-chaining" (r as IR ir) = (BranchChaining.run ir; r)
187 : monnier 409 | doPhase "insert-preheaders" (r as IR ir) =
188 : george 545 (InsertPreheaders.run ir; r)
189 : monnier 409 | doPhase "split-critical-edges" (r as IR ir) =
190 :     (Util.splitAllCriticalEdges ir; r)
191 :     | doPhase "view-cfg" (r as IR ir) = (view "cfg" ir; r)
192 :     | doPhase "view-dom" (r as IR ir) = (view "dom" ir; r)
193 :     | doPhase "view-doms" (r as IR ir) = (view "doms" ir; r)
194 :     | doPhase "view-cdg" (r as IR ir) = (view "cdg" ir; r)
195 :     | doPhase "view-loop" (r as IR ir) = (view "loop" ir; r)
196 :     | doPhase "view-ssacfg" (r as SSA ssa) =
197 :     (if !view_IR then GraphViewer.view (SSA.viewAsCFG ssa) else (); r)
198 :     | doPhase "view-ssa" (r as SSA ssa) =
199 :     (if !view_IR then GraphViewer.view (SSA.viewAsSSA ssa) else (); r)
200 :     | doPhase "cfg->ssa" (IR ir) = SSA(CFG2SSA.buildSSA(ir,IR.dom ir))
201 :     | doPhase "ssa-dce" (SSA ssa) = SSA(SSADCE.optimize ssa)
202 :     | doPhase "ssa-gvn" (SSA ssa) = SSA(SSAGVN.optimize ssa)
203 :     | doPhase "ssa-gvnl" (SSA ssa) = SSA(SSAGVNL.optimize ssa)
204 :     | doPhase "ssa-gvn'" (SSA ssa) = SSA(SSAGVN'.optimize ssa)
205 :     | doPhase "ssa-gcm" (SSA ssa) = SSA(SSAGCM.optimize ssa)
206 : george 545 | doPhase "ssa-ccp" (SSA ssa) = SSA(SSACCP.optimize ssa)
207 :     | doPhase "ssa-gc-invariants" (SSA ssa) =
208 :     SSA(SSAGCInvariants.optimize ssa)
209 : monnier 409 (* | doPhase "ssa-gcm2" (SSA ssa) = SSA(SSAGCM2.optimize ssa) *)
210 : george 545 (* | doPhase "ssa-dep" (SSA ssa) = SSA(Depressurize.optimize ssa)*)
211 : monnier 409 | doPhase "gvn" (r as SSA ssa) =
212 :     (GVN.computeValueNumbers ssa; r)
213 :     | doPhase "ssa->cfg" (SSA ssa) = IR(SSA2CFG.buildCFG ssa)
214 : george 545 | doPhase "gc-invariants" (r as IR ir) = (GCInvariants.run ir; r)
215 : monnier 429 | doPhase "gc-gen" (r as IR ir) =
216 :     (GCGen.gcGen{callgc=callgc} ir; r)
217 : monnier 409 | doPhase phase _ = error(phase)
218 : monnier 429
219 : monnier 409 fun doPhases [] (CLUSTER c) = c
220 :     | doPhases [] _ = error "cluster needed"
221 :     | doPhases (phase::phases) ir =
222 :     let fun pr msg = TextIO.output(TextIO.stdErr,msg)
223 :     val _ = if !verbose then pr("[ start "^phase^"]") else ();
224 :     val timer = Timer.startCPUTimer()
225 :     val ir = doPhase phase ir handle e =>
226 :     (print("[ "^phase^": uncaught exception: "
227 :     ^exnName e^" ]\n"); raise e)
228 :     val {gc,sys,usr} = Timer.checkCPUTimer timer
229 :     val _ = if !verbose then
230 :     pr("[ end "^phase^" usr="^Time.toString usr^
231 :     " sys="^Time.toString sys^
232 :     " gc="^Time.toString gc^"]\n") else ();
233 :     in doPhases phases ir end
234 :    
235 :     val F.CLUSTER{blocks,...} = cluster
236 :     fun isAllGC([],gc,n) = (gc,n)
237 :     | isAllGC(F.BBLOCK{succ,pred,...}::bs,gc,n) =
238 :     isAllGC(bs,gc andalso (case (!succ,!pred) of
239 :     ([_],[_]) => true | _ => false),n+1)
240 :     | isAllGC(_::bs,gc,n) = isAllGC(bs,gc,n)
241 :     in case isAllGC(blocks,true,0) of
242 :     (true,_) => cluster
243 :     | (false,n) =>
244 :     if n >= !min_blocks then
245 : monnier 429 doPhases (!MLRiscControl.mlrisc_phases) (CLUSTER cluster)
246 : monnier 409 else
247 :     cluster
248 :     end
249 :    
250 : monnier 429 fun codegen cluster =
251 :     if !MLRiscControl.mlrisc then optimize cluster else cluster
252 : monnier 409
253 :     end

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