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.ssa;
014
015import org.jikesrvm.compilers.opt.OptOptions;
016import org.jikesrvm.compilers.opt.driver.CompilerPhase;
017import org.jikesrvm.compilers.opt.driver.OptimizationPlanAtomicElement;
018import org.jikesrvm.compilers.opt.driver.OptimizationPlanCompositeElement;
019import org.jikesrvm.compilers.opt.driver.OptimizationPlanElement;
020import org.jikesrvm.compilers.opt.ir.IR;
021import org.jikesrvm.compilers.opt.ir.Instruction;
022import org.jikesrvm.compilers.opt.ir.operand.Operand;
023import org.jikesrvm.compilers.opt.ir.operand.RegisterOperand;
024
025/**
026 * Global code placement comes in two flavours. The first is loop
027 * invariant code motion (LICM), the second is global common sub
028 * expression elimination (GCSE).<p>
029 *
030 * LICM is applied to HIR and LIR, GCSE only to LIR and before
031 * LICM.<p>
032 *
033 * Both algorithms run on SSA and use the dominator tree to determine
034 * positions for operations. That's why these operations are called
035 * code placement instead of code motion. <p>
036 *
037 * There is no code yet to deal with partial redundancies.
038 */
039public final class GCP extends OptimizationPlanCompositeElement {
040
041  /**
042   * Makes sure we are in SSA and have global value numbers at hand.
043   * Then execute the transformations.
044   */
045  public GCP() {
046    super("Global Code Placement", new OptimizationPlanElement[]{
047        // 1. Set up IR state to control SSA translation as needed
048        new OptimizationPlanAtomicElement(new GCPPreparation()),
049        // 2. Get the desired SSA form
050        new OptimizationPlanAtomicElement(new EnterSSA()),
051        // 3. Perform global CSE
052        new OptimizationPlanAtomicElement(new GlobalCSE()),
053        // 4. Repair SSA
054        new OptimizationPlanAtomicElement(new EnterSSA()),
055        // 5. Perform Loop Invariant Code Motion
056        new OptimizationPlanAtomicElement(new LICM()),
057        // 6. Finalize GCP
058        new OptimizationPlanAtomicElement(new GCPFinalization())});
059  }
060
061  /**
062   * Redefine shouldPerform so that none of the subphases will occur
063   * unless we pass through this test.
064   */
065  @Override
066  public boolean shouldPerform(OptOptions options) {
067    if (options.getOptLevel() < 2) {
068      return false;
069    }
070    return options.SSA_GCP || options.SSA_GCSE;
071  }
072
073  static boolean tooBig(IR ir) {
074    boolean res = false;
075    if (ir.getMaxBasicBlockNumber() > 1000) {
076      //VM.sysWrite (ir.method.toString() + " is too large\n");
077      res = true;
078    }
079    return res;
080  }
081
082  /**
083   * This class sets up the IR state prior to entering SSA for GCP
084   */
085  private static class GCPPreparation extends CompilerPhase {
086    /**
087     * Return this instance of this phase. This phase contains no
088     * per-compilation instance fields.
089     * @param ir not used
090     * @return this
091     */
092    @Override
093    public CompilerPhase newExecution(IR ir) {
094      return this;
095    }
096
097    /**
098     * Should this phase perform?
099     * <p>
100     * @return <code>true</code> if SSA-based global code placement
101     *  or SSA-based global common subexpression elimination are
102     *  enabled
103     */
104    @Override
105    public final boolean shouldPerform(OptOptions options) {
106      return options.SSA_GCP || options.SSA_GCSE;
107    }
108
109    /**
110     * Return the name of the phase
111     */
112    @Override
113    public final String getName() {
114      return "GCP Preparation";
115    }
116
117    @Override
118    public final void perform(IR ir) {
119      boolean dont = false;
120      //VM.sysWrite("> " + ir.method + "\n");
121
122      if (ir.hasReachableExceptionHandlers()) {
123        //VM.sysWrite("has exceptionhandlers\n");
124        dont = true;
125      }
126      if (GCP.tooBig(ir)) {
127        dont = true;
128      }
129      if (dont) {
130        ir.options.SSA = false;
131        return;
132      }
133      ir.desiredSSAOptions = new SSAOptions();
134      // register in the IR the SSA properties we need for GCP
135      if (ir.IRStage == IR.LIR) {
136        ir.desiredSSAOptions.setScalarsOnly(true);
137        ir.desiredSSAOptions.setBackwards(false);
138        ir.desiredSSAOptions.setInsertUsePhis(false);
139        ir.desiredSSAOptions.setInsertPEIDeps(false);
140        ir.desiredSSAOptions.setHeapTypes(null);
141      } else {
142        // HIR options
143        ir.desiredSSAOptions.setScalarsOnly(false);
144        ir.desiredSSAOptions.setBackwards(true);
145        ir.desiredSSAOptions.setInsertUsePhis(true);
146        ir.desiredSSAOptions.setInsertPEIDeps(!ir.options.SSA_LICM_IGNORE_PEI);
147        ir.desiredSSAOptions.setHeapTypes(null);
148      }
149    }
150  }
151
152  /**
153   * This class sets up the IR state prior to entering SSA for GCP
154   */
155  private static class GCPFinalization extends CompilerPhase {
156    /**
157     * Return this instance of this phase. This phase contains no
158     * per-compilation instance fields.
159     * @param ir not used
160     * @return this
161     */
162    @Override
163    public CompilerPhase newExecution(IR ir) {
164      return this;
165    }
166
167    /**
168     * Should this phase perform?
169     * <p>
170     * Perform only if global code placement
171     * or global common subexpression elimination are performed.
172     */
173    @Override
174    public final boolean shouldPerform(OptOptions options) {
175      return options.SSA_GCP || options.SSA_GCSE;
176    }
177
178    /**
179     * Return the name of the phase
180     */
181    @Override
182    public final String getName() {
183      return "GCP Finalization";
184    }
185
186    @Override
187    public final void perform(IR ir) {
188      ir.options.SSA = true;
189      //VM.sysWrite("< " + ir.method + "\n");
190      // register in the IR the SSA properties GCP preserves
191      if (!GCP.tooBig(ir) && !ir.hasReachableExceptionHandlers() && ir.actualSSAOptions != null) {
192        if (ir.IRStage == IR.LIR) {
193          ir.actualSSAOptions.setScalarsOnly(true);
194          ir.actualSSAOptions.setBackwards(false);
195          ir.actualSSAOptions.setInsertUsePhis(false);
196          ir.actualSSAOptions.setInsertPEIDeps(false);
197          ir.actualSSAOptions.setHeapTypes(null);
198        } else {
199          // HIR options
200          ir.actualSSAOptions.setScalarsOnly(false);
201          ir.actualSSAOptions.setBackwards(true);
202          ir.actualSSAOptions.setInsertUsePhis(true);
203          ir.actualSSAOptions.setInsertPEIDeps(true);
204          ir.actualSSAOptions.setHeapTypes(null);
205        }
206      }
207    }
208  }
209
210  public static boolean usesOrDefsPhysicalRegisterOrAddressType(Instruction inst) {
211
212    for (int i = inst.getNumberOfOperands() - 1; i >= 0; --i) {
213      Operand op = inst.getOperand(i);
214      if (op instanceof RegisterOperand) {
215        if (op.asRegister().getType().isWordLikeType() || op.asRegister().getRegister().isPhysical()) {
216          return true;
217        }
218      }
219    }
220    return false;
221  }
222}