001 /*
002 * This file is part of the Jikes RVM project (http://jikesrvm.org).
003 *
004 * This file is licensed to You under the Eclipse Public License (EPL);
005 * You may not use this file except in compliance with the License. You
006 * may obtain a copy of the License at
007 *
008 * http://www.opensource.org/licenses/eclipse-1.0.php
009 *
010 * See the COPYRIGHT.txt file distributed with this work for information
011 * regarding copyright ownership.
012 */
013 package org.jikesrvm.compilers.opt.driver;
014
015 import java.util.ArrayList;
016
017 import org.jikesrvm.VM;
018 import org.jikesrvm.ArchitectureSpecificOpt.MIROptimizationPlanner;
019 import org.jikesrvm.adaptive.recompilation.instrumentation.InsertInstructionCounters;
020 import org.jikesrvm.adaptive.recompilation.instrumentation.InsertMethodInvocationCounter;
021 import org.jikesrvm.adaptive.recompilation.instrumentation.InsertYieldpointCounters;
022 import org.jikesrvm.adaptive.recompilation.instrumentation.InstrumentationSamplingFramework;
023 import org.jikesrvm.adaptive.recompilation.instrumentation.LowerInstrumentation;
024 import org.jikesrvm.compilers.opt.AdjustBranchProbabilities;
025 import org.jikesrvm.compilers.opt.FieldAnalysis;
026 import org.jikesrvm.compilers.opt.LocalCSE;
027 import org.jikesrvm.compilers.opt.LocalCastOptimization;
028 import org.jikesrvm.compilers.opt.LocalConstantProp;
029 import org.jikesrvm.compilers.opt.LocalCopyProp;
030 import org.jikesrvm.compilers.opt.OptOptions;
031 import org.jikesrvm.compilers.opt.Simple;
032 import org.jikesrvm.compilers.opt.bc2ir.ConvertBCtoHIR;
033 import org.jikesrvm.compilers.opt.bc2ir.OsrPointConstructor;
034 import org.jikesrvm.compilers.opt.controlflow.BranchOptimizations;
035 import org.jikesrvm.compilers.opt.controlflow.BuildLST;
036 import org.jikesrvm.compilers.opt.controlflow.CFGTransformations;
037 import org.jikesrvm.compilers.opt.controlflow.DominanceFrontier;
038 import org.jikesrvm.compilers.opt.controlflow.DominatorsPhase;
039 import org.jikesrvm.compilers.opt.controlflow.EstimateBlockFrequencies;
040 import org.jikesrvm.compilers.opt.controlflow.LoopUnrolling;
041 import org.jikesrvm.compilers.opt.controlflow.ReorderingPhase;
042 import org.jikesrvm.compilers.opt.controlflow.StaticSplitting;
043 import org.jikesrvm.compilers.opt.controlflow.TailRecursionElimination;
044 import org.jikesrvm.compilers.opt.controlflow.YieldPoints;
045 import org.jikesrvm.compilers.opt.escape.EscapeTransformations;
046 import org.jikesrvm.compilers.opt.hir2lir.ConvertHIRtoLIR;
047 import org.jikesrvm.compilers.opt.hir2lir.ExpandRuntimeServices;
048 import org.jikesrvm.compilers.opt.ir.IR;
049 import org.jikesrvm.compilers.opt.regalloc.CoalesceMoves;
050 import org.jikesrvm.compilers.opt.ssa.GCP;
051 import org.jikesrvm.compilers.opt.ssa.LeaveSSA;
052 import org.jikesrvm.compilers.opt.ssa.LiveRangeSplitting;
053 import org.jikesrvm.compilers.opt.ssa.LoadElimination;
054 import org.jikesrvm.compilers.opt.ssa.LoopVersioning;
055 import org.jikesrvm.compilers.opt.ssa.PiNodes;
056 import org.jikesrvm.compilers.opt.ssa.RedundantBranchElimination;
057 import org.jikesrvm.compilers.opt.ssa.SSATuneUp;
058 import org.jikesrvm.osr.AdjustBCIndexes;
059
060 /**
061 * This class specifies the order in which CompilerPhases are
062 * executed during the HIR and LIR phase of the opt compilation of a method.
063 *
064 * @see MIROptimizationPlanner
065 */
066 public class OptimizationPlanner {
067
068 /**
069 * The master optimization plan.
070 * All plans that are actually executed should be subsets of this plan
071 * constructed by calling createOptimizationPlan.
072 */
073 private static OptimizationPlanElement[] masterPlan;
074
075 /**
076 * Generate a report of time spent in various phases of the opt compiler.
077 * <p> NB: This method may be called in a context where classloading and/or
078 * GC cannot be allowed.
079 * Therefore we must use primitive sysWrites for output and avoid string
080 * appends and other allocations.
081 *
082 * @param explain Should an explanation of the metrics be generated?
083 */
084 public static void generateOptimizingCompilerSubsystemReport(boolean explain) {
085 if (!VM.MeasureCompilationPhases) {
086 return;
087 }
088
089 VM.sysWrite("\t\tOptimizing Compiler SubSystem\n");
090 VM.sysWrite("\tPhase\t\t\t\t\tTime\n");
091 VM.sysWrite("\t\t\t\t\t (ms) (%ofTotal)\n");
092 double total = 0.0;
093
094 for (OptimizationPlanElement element : masterPlan) {
095 total += element.elapsedTime();
096 }
097
098 for (OptimizationPlanElement element : masterPlan) {
099 element.reportStats(8, 40, total);
100 }
101
102 VM.sysWrite("\n\tTOTAL COMPILATION TIME\t\t");
103 int t = (int) total, places = t;
104 if (places == 0) {
105 places = 1;
106 }
107 while (places < 1000000) { // Right-align 't'
108 VM.sysWrite(" ");
109 places *= 10;
110 }
111 VM.sysWrite(t);
112 VM.sysWrite("\n");
113 }
114
115 /**
116 * Using the passed options create an optimization plan
117 * by selecting a subset of the elements in the masterPlan.
118 *
119 * @param options the Options to use
120 * @return an OptimizationPlanElement[] selected from
121 * the masterPlan based on options.
122 */
123 public static OptimizationPlanElement[] createOptimizationPlan(OptOptions options) {
124 if (masterPlan == null) {
125 initializeMasterPlan();
126 }
127
128 ArrayList<OptimizationPlanElement> temp = new ArrayList<OptimizationPlanElement>();
129 for (OptimizationPlanElement element : masterPlan) {
130 if (element.shouldPerform(options)) {
131 temp.add(element);
132 }
133 }
134 if (VM.writingBootImage) {
135 masterPlan = null; // avoid problems with classes not being in bootimage.
136 }
137 return toArray(temp);
138 }
139
140 /**
141 * This method is called to initialize all phases to support
142 * measuring compilation.
143 */
144 public static void initializeMeasureCompilation() {
145 for (OptimizationPlanElement element : masterPlan) {
146 element.initializeForMeasureCompilation();
147 }
148 }
149
150 /**
151 * Initialize the "master plan", which holds all optimization elements
152 * that will normally execute.
153 */
154 private static void initializeMasterPlan() {
155 ArrayList<OptimizationPlanElement> temp = new ArrayList<OptimizationPlanElement>();
156 BC2HIR(temp);
157 HIROptimizations(temp);
158 HIR2LIR(temp);
159 LIROptimizations(temp);
160 MIROptimizationPlanner.intializeMasterPlan(temp);
161 masterPlan = toArray(temp);
162 }
163
164 /**
165 * Convert the ArrayList to an array of elements.
166 * @param planElementList the array list to convert, must be non-{@code null}
167 * @return list as array
168 */
169 private static OptimizationPlanElement[] toArray(ArrayList<OptimizationPlanElement> planElementList) {
170 OptimizationPlanElement[] p = new OptimizationPlanElement[planElementList.size()];
171 planElementList.toArray(p);
172 return p;
173 }
174
175 /**
176 * This method defines the optimization plan elements required to
177 * generate HIR from bytecodes.
178 *
179 * @param p the plan under construction
180 */
181 private static void BC2HIR(ArrayList<OptimizationPlanElement> p) {
182 composeComponents(p, "Convert Bytecodes to HIR", new Object[]{
183 // Generate HIR from bytecodes
184 new ConvertBCtoHIR(),
185
186 new AdjustBCIndexes(), new OsrPointConstructor(),
187
188 // Always do initial wave of peephole branch optimizations
189 new BranchOptimizations(0, true, false),
190
191 // ir now contains well formed HIR. Optionally do a verification pass.
192 new CompilerPhase() {
193 @Override
194 public String getName() {
195 return "HIR Verification";
196 }
197 @Override
198 public void perform(IR ir) {
199 if (IR.SANITY_CHECK) {
200 ir.verify("Initial HIR", true);
201 }
202 }
203 @Override
204 public CompilerPhase newExecution(IR ir) {
205 return this;
206 }
207 },
208
209 // Adjust static branch probabilities to account for infrequent blocks
210 new AdjustBranchProbabilities(),
211
212 // Optional printing of initial HIR
213 // Do this after branch optimization, since without merging
214 // FallThroughOuts, the IR is quite ugly.
215 new IRPrinter("Initial HIR") {
216 @Override
217 public boolean shouldPerform(OptOptions options) {
218 return options.PRINT_HIGH;
219 }
220 }});
221 }
222
223 /**
224 * This method defines the optimization plan elements that
225 * are to be performed on the HIR.
226 *
227 * @param p the plan under construction
228 */
229 private static void HIROptimizations(ArrayList<OptimizationPlanElement> p) {
230 // Various large-scale CFG transformations.
231 // Do these very early in the pipe so that all HIR opts can benefit.
232 composeComponents(p, "CFG Transformations", new Object[]{
233 // tail recursion elimination
234 new TailRecursionElimination(),
235 // Estimate block frequencies if doing any of
236 // static splitting, cfg transformations, or loop unrolling.
237 // Assumption: none of these are active at O0.
238 new OptimizationPlanCompositeElement("Basic Block Frequency Estimation",
239 new Object[]{new BuildLST(), new EstimateBlockFrequencies()}) {
240 @Override
241 public boolean shouldPerform(OptOptions options) {
242 return options.getOptLevel() >= 1;
243 }
244 },
245 // CFG splitting
246 new StaticSplitting(),
247 // restructure loops
248 new CFGTransformations(),
249 // Loop unrolling
250 new LoopUnrolling(), new BranchOptimizations(1, true, true),});
251
252 // Use the LST to insert yieldpoints and estimate
253 // basic block frequency from branch probabilities
254 composeComponents(p,
255 "CFG Structural Analysis",
256 new Object[]{new BuildLST(), new YieldPoints(), new EstimateBlockFrequencies()});
257
258 // Simple flow-insensitive optimizations
259 addComponent(p, new Simple(1, true, true, false, false));
260
261 // Simple escape analysis and related transformations
262 addComponent(p, new EscapeTransformations());
263
264 // Perform peephole branch optimizations to clean-up before SSA stuff
265 addComponent(p, new BranchOptimizations(1, true, true));
266
267 // SSA meta-phase
268 SSAinHIR(p);
269
270 // Perform local copy propagation for a factored basic block.
271 addComponent(p, new LocalCopyProp());
272 // Perform local constant propagation for a factored basic block.
273 addComponent(p, new LocalConstantProp());
274 // Perform local common-subexpression elimination for a
275 // factored basic block.
276 addComponent(p, new LocalCSE(true));
277 // Flow-insensitive field analysis
278 addComponent(p, new FieldAnalysis());
279 if (VM.BuildForAdaptiveSystem) {
280 // Insert counter on each method prologue
281 // Insert yieldpoint counters
282 addComponent(p, new InsertYieldpointCounters());
283 // Insert counter on each HIR instruction
284 addComponent(p, new InsertInstructionCounters());
285 // Insert method invocation counters
286 addComponent(p, new InsertMethodInvocationCounter());
287 }
288 }
289
290 /**
291 * This method defines the optimization plan elements that
292 * are to be performed with SSA form on HIR.
293 *
294 * @param p the plan under construction
295 */
296 private static void SSAinHIR(ArrayList<OptimizationPlanElement> p) {
297 composeComponents(p, "SSA", new Object[]{
298 // Use the LST to estimate basic block frequency from branch probabilities
299 new OptimizationPlanCompositeElement("Basic Block Frequency Estimation",
300 new Object[]{new BuildLST(), new EstimateBlockFrequencies()}) {
301 @Override
302 public boolean shouldPerform(OptOptions options) {
303 return options.getOptLevel() >= 3;
304 }
305 },
306
307 new OptimizationPlanCompositeElement("HIR SSA transformations", new Object[]{
308 // Local copy propagation
309 new LocalCopyProp(),
310 // Local constant propagation
311 new LocalConstantProp(),
312 // Insert PI Nodes
313 new PiNodes(true),
314 // branch optimization
315 new BranchOptimizations(3, true, true),
316 // Compute dominators
317 new DominatorsPhase(true),
318 // compute dominance frontier
319 new DominanceFrontier(),
320 // load elimination
321 new LoadElimination(1),
322 // load elimination
323 new LoadElimination(2),
324 // load elimination
325 new LoadElimination(3),
326 // load elimination
327 new LoadElimination(4),
328 // load elimination
329 new LoadElimination(5),
330 // eliminate redundant conditional branches
331 new RedundantBranchElimination(),
332 // path sensitive constant propagation
333 new SSATuneUp(),
334 // clean up Pi Nodes
335 new PiNodes(false),
336 // Simple SSA optimizations,
337 new SSATuneUp(),
338 // Global Code Placement,
339 new GCP(),
340 // Loop versioning
341 new LoopVersioning(),
342 // Leave SSA
343 new LeaveSSA()}) {
344 @Override
345 public boolean shouldPerform(OptOptions options) {
346 return options.getOptLevel() >= 3;
347 }
348 },
349 // Coalesce moves
350 new CoalesceMoves(),
351
352 // SSA reveals new opportunites for the following
353 new OptimizationPlanCompositeElement("Post SSA cleanup",
354 new Object[]{new LocalCopyProp(),
355 new LocalConstantProp(),
356 new Simple(3, true, true, false, false),
357 new EscapeTransformations(),
358 new BranchOptimizations(3, true, true)}) {
359 @Override
360 public boolean shouldPerform(OptOptions options) {
361 return options.getOptLevel() >= 3;
362 }
363 }});
364 }
365
366 /**
367 * This method defines the optimization plan elements that
368 * are to be performed with SSA form on LIR.
369 *
370 * @param p the plan under construction
371 */
372 private static void SSAinLIR(ArrayList<OptimizationPlanElement> p) {
373 composeComponents(p, "SSA", new Object[]{
374 // Use the LST to estimate basic block frequency from branch probabilities
375 new OptimizationPlanCompositeElement("Basic Block Frequency Estimation",
376 new Object[]{new BuildLST(), new EstimateBlockFrequencies()}) {
377 @Override
378 public boolean shouldPerform(OptOptions options) {
379 return options.getOptLevel() >= 3;
380 }
381 },
382
383 new OptimizationPlanCompositeElement("LIR SSA transformations", new Object[]{
384 // restructure loops
385 new CFGTransformations(),
386 // Compute dominators
387 new DominatorsPhase(true),
388 // compute dominance frontier
389 new DominanceFrontier(),
390 // Global Code Placement,
391 new GCP(),
392 // Leave SSA
393 new LeaveSSA()}) {
394 @Override
395 public boolean shouldPerform(OptOptions options) {
396 return options.getOptLevel() >= 3;
397 }
398 },
399 // Live range splitting
400 new LiveRangeSplitting(),
401
402 // Coalesce moves
403 new CoalesceMoves(),
404
405 // SSA reveals new opportunites for the following
406 new OptimizationPlanCompositeElement("Post SSA cleanup",
407 new Object[]{new LocalCopyProp(),
408 new LocalConstantProp(),
409 new Simple(3, true, true, false, false),
410 new BranchOptimizations(3, true, true)}) {
411 @Override
412 public boolean shouldPerform(OptOptions options) {
413 return options.getOptLevel() >= 3;
414 }
415 }});
416 }
417
418 /**
419 * This method defines the optimization plan elements that
420 * are to be performed to lower HIR to LIR.
421 *
422 * @param p the plan under construction
423 */
424 private static void HIR2LIR(ArrayList<OptimizationPlanElement> p) {
425 composeComponents(p, "Convert HIR to LIR", new Object[]{
426 // Optional printing of final HIR
427 new IRPrinter("Final HIR") {
428 @Override
429 public boolean shouldPerform(OptOptions options) {
430 return options.PRINT_FINAL_HIR;
431 }
432 },
433
434 // Inlining "runtime service" methods
435 new ExpandRuntimeServices(),
436 // Peephole branch optimizations
437 new BranchOptimizations(1, true, true),
438 // Local optimizations of checkcasts
439 new LocalCastOptimization(),
440 // Massive operator expansion
441 new ConvertHIRtoLIR(),
442 // Peephole branch optimizations
443 new BranchOptimizations(0, true, true),
444 // Adjust static branch probabilites to account for infrequent blocks
445 // introduced by the inlining of runtime services.
446 new AdjustBranchProbabilities(),
447 // Optional printing of initial LIR
448 new IRPrinter("Initial LIR") {
449 @Override
450 public boolean shouldPerform(OptOptions options) {
451 return options.PRINT_LOW;
452 }
453 }});
454 }
455
456 /**
457 * This method defines the optimization plan elements that
458 * are to be performed on the LIR.
459 *
460 * @param p the plan under construction
461 */
462 private static void LIROptimizations(ArrayList<OptimizationPlanElement> p) {
463 // SSA meta-phase
464 SSAinLIR(p);
465 // Perform local copy propagation for a factored basic block.
466 addComponent(p, new LocalCopyProp());
467 // Perform local constant propagation for a factored basic block.
468 addComponent(p, new LocalConstantProp());
469 // Perform local common-subexpression elimination for a factored basic block.
470 addComponent(p, new LocalCSE(false));
471 // Simple flow-insensitive optimizations
472 addComponent(p, new Simple(0, false, false, false, VM.BuildForIA32));
473
474 // Use the LST to estimate basic block frequency
475 addComponent(p,
476 new OptimizationPlanCompositeElement("Basic Block Frequency Estimation",
477 new Object[]{new BuildLST(),
478 new EstimateBlockFrequencies()}));
479
480 // Perform basic block reordering
481 addComponent(p, new ReorderingPhase());
482 // Perform peephole branch optimizations
483 addComponent(p, new BranchOptimizations(0, false, true));
484
485 if (VM.BuildForAdaptiveSystem) {
486 // Arnold & Ryder instrumentation sampling framework
487 addComponent(p, new InstrumentationSamplingFramework());
488
489 // Convert high level place holder instructions into actual instrumentation
490 addComponent(p, new LowerInstrumentation());
491 }
492 }
493
494 // Helper functions for constructing the masterPlan.
495 protected static void addComponent(ArrayList<OptimizationPlanElement> p, CompilerPhase e) {
496 addComponent(p, new OptimizationPlanAtomicElement(e));
497 }
498
499 /**
500 * Add an optimization plan element to a vector.
501 */
502 protected static void addComponent(ArrayList<OptimizationPlanElement> p, OptimizationPlanElement e) {
503 p.add(e);
504 }
505
506 /**
507 * Add a set of optimization plan elements to a vector.
508 * @param p the vector to add to
509 * @param name the name for this composition
510 * @param es the array of composed elements
511 */
512 protected static void composeComponents(ArrayList<OptimizationPlanElement> p, String name, Object[] es) {
513 p.add(OptimizationPlanCompositeElement.compose(name, es));
514 }
515 }