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 */
013package org.jikesrvm.compilers.opt.driver;
014
015import java.util.ArrayList;
016
017import org.jikesrvm.VM;
018import org.jikesrvm.adaptive.recompilation.instrumentation.InsertInstructionCounters;
019import org.jikesrvm.adaptive.recompilation.instrumentation.InsertMethodInvocationCounter;
020import org.jikesrvm.adaptive.recompilation.instrumentation.InsertYieldpointCounters;
021import org.jikesrvm.adaptive.recompilation.instrumentation.InstrumentationSamplingFramework;
022import org.jikesrvm.adaptive.recompilation.instrumentation.LowerInstrumentation;
023import org.jikesrvm.compilers.opt.AdjustBranchProbabilities;
024import org.jikesrvm.compilers.opt.FieldAnalysis;
025import org.jikesrvm.compilers.opt.LocalCSE;
026import org.jikesrvm.compilers.opt.LocalCastOptimization;
027import org.jikesrvm.compilers.opt.LocalConstantProp;
028import org.jikesrvm.compilers.opt.LocalCopyProp;
029import org.jikesrvm.compilers.opt.OptOptions;
030import org.jikesrvm.compilers.opt.Simple;
031import org.jikesrvm.compilers.opt.bc2ir.ConvertBCtoHIR;
032import org.jikesrvm.compilers.opt.bc2ir.OsrPointConstructor;
033import org.jikesrvm.compilers.opt.controlflow.BranchOptimizations;
034import org.jikesrvm.compilers.opt.controlflow.BuildLST;
035import org.jikesrvm.compilers.opt.controlflow.CFGTransformations;
036import org.jikesrvm.compilers.opt.controlflow.DominanceFrontier;
037import org.jikesrvm.compilers.opt.controlflow.DominatorsPhase;
038import org.jikesrvm.compilers.opt.controlflow.EstimateBlockFrequencies;
039import org.jikesrvm.compilers.opt.controlflow.LoopUnrolling;
040import org.jikesrvm.compilers.opt.controlflow.ReorderingPhase;
041import org.jikesrvm.compilers.opt.controlflow.StaticSplitting;
042import org.jikesrvm.compilers.opt.controlflow.TailRecursionElimination;
043import org.jikesrvm.compilers.opt.controlflow.YieldPoints;
044import org.jikesrvm.compilers.opt.escape.EscapeTransformations;
045import org.jikesrvm.compilers.opt.hir2lir.ConvertHIRtoLIR;
046import org.jikesrvm.compilers.opt.hir2lir.ExpandRuntimeServices;
047import org.jikesrvm.compilers.opt.ir.IR;
048import org.jikesrvm.compilers.opt.regalloc.CoalesceMoves;
049import org.jikesrvm.compilers.opt.ssa.GCP;
050import org.jikesrvm.compilers.opt.ssa.LeaveSSA;
051import org.jikesrvm.compilers.opt.ssa.LiveRangeSplitting;
052import org.jikesrvm.compilers.opt.ssa.LoadElimination;
053import org.jikesrvm.compilers.opt.ssa.LoopVersioning;
054import org.jikesrvm.compilers.opt.ssa.PiNodes;
055import org.jikesrvm.compilers.opt.ssa.RedundantBranchElimination;
056import org.jikesrvm.compilers.opt.ssa.SSATuneUp;
057import org.jikesrvm.osr.AdjustBCIndexes;
058
059/**
060 * This class specifies the order in which CompilerPhases are
061 * executed during the HIR and LIR phase of the opt compilation of a method.
062 * <p>
063 * The order of the compiler phases for MIR is handled separately for each
064 * architecture by the respective MIROptimizationPlanner.
065 */
066public 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    if (VM.BuildForIA32) {
161      org.jikesrvm.compilers.opt.driver.ia32.MIROptimizationPlanner.intializeMasterPlan(temp);
162    } else {
163      if (VM.VerifyAssertions) VM._assert(VM.BuildForPowerPC);
164      org.jikesrvm.compilers.opt.driver.ppc.MIROptimizationPlanner.intializeMasterPlan(temp);
165    }
166    masterPlan = toArray(temp);
167  }
168
169  /**
170   * Convert the ArrayList to an array of elements.
171   * @param planElementList the array list to convert, must be non-{@code null}
172   * @return list as array
173   */
174  private static OptimizationPlanElement[] toArray(ArrayList<OptimizationPlanElement> planElementList) {
175    OptimizationPlanElement[] p = new OptimizationPlanElement[planElementList.size()];
176    planElementList.toArray(p);
177    return p;
178  }
179
180  /**
181   * This method defines the optimization plan elements required to
182   * generate HIR from bytecodes.
183   *
184   * @param p the plan under construction
185   */
186  private static void BC2HIR(ArrayList<OptimizationPlanElement> p) {
187    composeComponents(p, "Convert Bytecodes to HIR", new Object[]{
188        // Generate HIR from bytecodes
189        new ConvertBCtoHIR(),
190
191        new AdjustBCIndexes(), new OsrPointConstructor(),
192
193        // Always do initial wave of peephole branch optimizations
194        new BranchOptimizations(0, true, false),
195
196        // ir now contains well formed HIR. Optionally do a verification pass.
197        new CompilerPhase() {
198          @Override
199          public String getName() {
200            return "HIR Verification";
201          }
202          @Override
203          public void perform(IR ir) {
204            if (IR.SANITY_CHECK) {
205              ir.verify("Initial HIR", true);
206            }
207          }
208          @Override
209          public CompilerPhase newExecution(IR ir) {
210            return this;
211          }
212        },
213
214        // Adjust static branch probabilities to account for infrequent blocks
215        new AdjustBranchProbabilities(),
216
217        // Optional printing of initial HIR
218        // Do this after branch optimization, since without merging
219        // FallThroughOuts, the IR is quite ugly.
220        new IRPrinter("Initial HIR") {
221          @Override
222          public boolean shouldPerform(OptOptions options) {
223            return options.PRINT_HIGH;
224          }
225        }});
226  }
227
228  /**
229   * This method defines the optimization plan elements that
230   * are to be performed on the HIR.
231   *
232   * @param p the plan under construction
233   */
234  private static void HIROptimizations(ArrayList<OptimizationPlanElement> p) {
235    // Various large-scale CFG transformations.
236    // Do these very early in the pipe so that all HIR opts can benefit.
237    composeComponents(p, "CFG Transformations", new Object[]{
238        // tail recursion elimination
239        new TailRecursionElimination(),
240        // Estimate block frequencies if doing any of
241        // static splitting, cfg transformations, or loop unrolling.
242        // Assumption: none of these are active at O0.
243        new OptimizationPlanCompositeElement("Basic Block Frequency Estimation",
244                                                 new Object[]{new BuildLST(), new EstimateBlockFrequencies()}) {
245          @Override
246          public boolean shouldPerform(OptOptions options) {
247            return options.getOptLevel() >= 1;
248          }
249        },
250        // CFG splitting
251        new StaticSplitting(),
252        // restructure loops
253        new CFGTransformations(),
254        // Loop unrolling
255        new LoopUnrolling(), new BranchOptimizations(1, true, true),});
256
257    // Use the LST to insert yieldpoints and estimate
258    // basic block frequency from branch probabilities
259    composeComponents(p,
260                      "CFG Structural Analysis",
261                      new Object[]{new BuildLST(), new YieldPoints(), new EstimateBlockFrequencies()});
262
263    // Simple flow-insensitive optimizations
264    addComponent(p, new Simple(1, true, true, false, false));
265
266    // Simple escape analysis and related transformations
267    addComponent(p, new EscapeTransformations());
268
269    // Perform peephole branch optimizations to clean-up before SSA stuff
270    addComponent(p, new BranchOptimizations(1, true, true));
271
272    // SSA meta-phase
273    SSAinHIR(p);
274
275    // Perform local copy propagation for a factored basic block.
276    addComponent(p, new LocalCopyProp());
277    // Perform local constant propagation for a factored basic block.
278    addComponent(p, new LocalConstantProp());
279    // Perform local common-subexpression elimination for a
280    // factored basic block.
281    addComponent(p, new LocalCSE(true));
282    // Flow-insensitive field analysis
283    addComponent(p, new FieldAnalysis());
284    if (VM.BuildForAdaptiveSystem) {
285      // Insert counter on each method prologue
286      // Insert yieldpoint counters
287      addComponent(p, new InsertYieldpointCounters());
288      // Insert counter on each HIR instruction
289      addComponent(p, new InsertInstructionCounters());
290      // Insert method invocation counters
291      addComponent(p, new InsertMethodInvocationCounter());
292    }
293  }
294
295  /**
296   * This method defines the optimization plan elements that
297   * are to be performed with SSA form on HIR.
298   *
299   * @param p the plan under construction
300   */
301  private static void SSAinHIR(ArrayList<OptimizationPlanElement> p) {
302    composeComponents(p, "SSA", new Object[]{
303        // Use the LST to estimate basic block frequency from branch probabilities
304        new OptimizationPlanCompositeElement("Basic Block Frequency Estimation",
305                                                 new Object[]{new BuildLST(), new EstimateBlockFrequencies()}) {
306          @Override
307          public boolean shouldPerform(OptOptions options) {
308            return options.getOptLevel() >= 3;
309          }
310        },
311
312        new OptimizationPlanCompositeElement("HIR SSA transformations", new Object[]{
313            // Local copy propagation
314            new LocalCopyProp(),
315            // Local constant propagation
316            new LocalConstantProp(),
317            // Insert PI Nodes
318            new PiNodes(true),
319            // branch optimization
320            new BranchOptimizations(3, true, true),
321            // Compute dominators
322            new DominatorsPhase(true),
323            // compute dominance frontier
324            new DominanceFrontier(),
325            // load elimination
326            new LoadElimination(1),
327            // load elimination
328            new LoadElimination(2),
329            // load elimination
330            new LoadElimination(3),
331            // load elimination
332            new LoadElimination(4),
333            // load elimination
334            new LoadElimination(5),
335            // eliminate redundant conditional branches
336            new RedundantBranchElimination(),
337            // path sensitive constant propagation
338            new SSATuneUp(),
339            // clean up Pi Nodes
340            new PiNodes(false),
341            // Simple SSA optimizations,
342            new SSATuneUp(),
343            // Global Code Placement,
344            new GCP(),
345            // Loop versioning
346            new LoopVersioning(),
347            // Leave SSA
348            new LeaveSSA()}) {
349          @Override
350          public boolean shouldPerform(OptOptions options) {
351            return options.getOptLevel() >= 3;
352          }
353        },
354        // Coalesce moves
355        new CoalesceMoves(),
356
357        // SSA reveals new opportunites for the following
358        new OptimizationPlanCompositeElement("Post SSA cleanup",
359                                                 new Object[]{new LocalCopyProp(),
360                                                              new LocalConstantProp(),
361                                                              new Simple(3, true, true, false, false),
362                                                              new EscapeTransformations(),
363                                                              new BranchOptimizations(3, true, true)}) {
364          @Override
365          public boolean shouldPerform(OptOptions options) {
366            return options.getOptLevel() >= 3;
367          }
368        }});
369  }
370
371  /**
372   * This method defines the optimization plan elements that
373   * are to be performed with SSA form on LIR.
374   *
375   * @param p the plan under construction
376   */
377  private static void SSAinLIR(ArrayList<OptimizationPlanElement> p) {
378    composeComponents(p, "SSA", new Object[]{
379        // Use the LST to estimate basic block frequency from branch probabilities
380        new OptimizationPlanCompositeElement("Basic Block Frequency Estimation",
381                                                 new Object[]{new BuildLST(), new EstimateBlockFrequencies()}) {
382          @Override
383          public boolean shouldPerform(OptOptions options) {
384            return options.getOptLevel() >= 3;
385          }
386        },
387
388        new OptimizationPlanCompositeElement("LIR SSA transformations", new Object[]{
389            // restructure loops
390            new CFGTransformations(),
391            // Compute dominators
392            new DominatorsPhase(true),
393            // compute dominance frontier
394            new DominanceFrontier(),
395            // Global Code Placement,
396            new GCP(),
397            // Leave SSA
398            new LeaveSSA()}) {
399          @Override
400          public boolean shouldPerform(OptOptions options) {
401            return options.getOptLevel() >= 3;
402          }
403        },
404        // Live range splitting
405        new LiveRangeSplitting(),
406
407        // Coalesce moves
408        new CoalesceMoves(),
409
410        // SSA reveals new opportunites for the following
411        new OptimizationPlanCompositeElement("Post SSA cleanup",
412                                                 new Object[]{new LocalCopyProp(),
413                                                              new LocalConstantProp(),
414                                                              new Simple(3, true, true, false, false),
415                                                              new BranchOptimizations(3, true, true)}) {
416          @Override
417          public boolean shouldPerform(OptOptions options) {
418            return options.getOptLevel() >= 3;
419          }
420        }});
421  }
422
423  /**
424   * This method defines the optimization plan elements that
425   * are to be performed to lower HIR to LIR.
426   *
427   * @param p the plan under construction
428   */
429  private static void HIR2LIR(ArrayList<OptimizationPlanElement> p) {
430    composeComponents(p, "Convert HIR to LIR", new Object[]{
431        // Optional printing of final HIR
432        new IRPrinter("Final HIR") {
433          @Override
434          public boolean shouldPerform(OptOptions options) {
435            return options.PRINT_FINAL_HIR;
436          }
437        },
438
439        // Inlining "runtime service" methods
440        new ExpandRuntimeServices(),
441        // Peephole branch optimizations
442        new BranchOptimizations(1, true, true),
443        // Local optimizations of checkcasts
444        new LocalCastOptimization(),
445        // Massive operator expansion
446        new ConvertHIRtoLIR(),
447        // Peephole branch optimizations
448        new BranchOptimizations(0, true, true),
449        // Adjust static branch probabilites to account for infrequent blocks
450        // introduced by the inlining of runtime services.
451        new AdjustBranchProbabilities(),
452        // Optional printing of initial LIR
453        new IRPrinter("Initial LIR") {
454          @Override
455          public boolean shouldPerform(OptOptions options) {
456            return options.PRINT_LOW;
457          }
458        }});
459  }
460
461  /**
462   * This method defines the optimization plan elements that
463   * are to be performed on the LIR.
464   *
465   * @param p the plan under construction
466   */
467  private static void LIROptimizations(ArrayList<OptimizationPlanElement> p) {
468    // SSA meta-phase
469    SSAinLIR(p);
470    // Perform local copy propagation for a factored basic block.
471    addComponent(p, new LocalCopyProp());
472    // Perform local constant propagation for a factored basic block.
473    addComponent(p, new LocalConstantProp());
474    // Perform local common-subexpression elimination for a factored basic block.
475    addComponent(p, new LocalCSE(false));
476    // Simple flow-insensitive optimizations
477    addComponent(p, new Simple(0, false, false, false, VM.BuildForIA32));
478
479    // Use the LST to estimate basic block frequency
480    addComponent(p,
481                 new OptimizationPlanCompositeElement("Basic Block Frequency Estimation",
482                                                          new Object[]{new BuildLST(),
483                                                                       new EstimateBlockFrequencies()}));
484
485    // Perform basic block reordering
486    addComponent(p, new ReorderingPhase());
487    // Perform peephole branch optimizations
488    addComponent(p, new BranchOptimizations(0, false, true));
489
490    if (VM.BuildForAdaptiveSystem) {
491      // Arnold & Ryder instrumentation sampling framework
492      addComponent(p, new InstrumentationSamplingFramework());
493
494      // Convert high level place holder instructions into actual instrumentation
495      addComponent(p, new LowerInstrumentation());
496    }
497  }
498
499  // Helper functions for constructing the masterPlan.
500  protected static void addComponent(ArrayList<OptimizationPlanElement> p, CompilerPhase e) {
501    addComponent(p, new OptimizationPlanAtomicElement(e));
502  }
503
504  protected static void addComponent(ArrayList<OptimizationPlanElement> p, OptimizationPlanElement e) {
505    p.add(e);
506  }
507
508  /**
509   * Add a set of optimization plan elements to a vector.
510   * @param p    the vector to add to
511   * @param name the name for this composition
512   * @param es   the array of composed elements
513   */
514  protected static void composeComponents(ArrayList<OptimizationPlanElement> p, String name, Object[] es) {
515    p.add(OptimizationPlanCompositeElement.compose(name, es));
516  }
517}