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