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 static org.jikesrvm.compilers.opt.ir.Operators.*;
016
017import java.lang.reflect.Constructor;
018import java.util.Enumeration;
019import java.util.HashMap;
020
021import org.jikesrvm.VM;
022import org.jikesrvm.compilers.opt.DefUse;
023import org.jikesrvm.compilers.opt.OptOptions;
024import org.jikesrvm.compilers.opt.Simple;
025import org.jikesrvm.compilers.opt.controlflow.DominatorTree;
026import org.jikesrvm.compilers.opt.controlflow.DominatorTreeNode;
027import org.jikesrvm.compilers.opt.driver.CompilerPhase;
028import org.jikesrvm.compilers.opt.ir.BBend;
029import org.jikesrvm.compilers.opt.ir.BasicBlock;
030import org.jikesrvm.compilers.opt.ir.GuardResultCarrier;
031import org.jikesrvm.compilers.opt.ir.IR;
032import org.jikesrvm.compilers.opt.ir.Instruction;
033import org.jikesrvm.compilers.opt.ir.Register;
034import org.jikesrvm.compilers.opt.ir.ResultCarrier;
035import org.jikesrvm.compilers.opt.ir.operand.RegisterOperand;
036import org.jikesrvm.compilers.opt.util.TreeNode;
037
038/**
039 * This class provides global common sub expression elimination.
040 */
041public final class GlobalCSE extends CompilerPhase {
042
043  /** Output debug messages */
044  public boolean verbose = true;
045  /** Cache of IR being processed by this phase */
046  private IR ir;
047  /** Cache of the value numbers from the IR  */
048  private GlobalValueNumberState valueNumbers;
049  /**
050   * Cache of dominator tree that should be computed prior to this
051   * phase
052   */
053  private DominatorTree dominator;
054  /**
055   * Available expressions. From Muchnick, "an expression
056   * <em>exp</em>is said to be <em>available</em> at the entry to a
057   * basic block if along every control-flow path from the entry block
058   * to this block there is an evaluation of exp that is not
059   * subsequently killed by having one or more of its operands
060   * assigned a new value." Our available expressions are a mapping
061   * from a value number to the first instruction to define it as we
062   * traverse the dominator tree.
063   */
064  private final HashMap<Integer, Instruction> avail;
065
066  /**
067   * Constructor
068   */
069  public GlobalCSE() {
070    avail = new HashMap<Integer, Instruction>();
071  }
072
073  /**
074   * Redefine shouldPerform so that none of the subphases will occur
075   * unless we pass through this test.
076   */
077  @Override
078  public boolean shouldPerform(OptOptions options) {
079    return options.SSA_GCSE;
080  }
081
082  /**
083   * Constructor for this compiler phase
084   */
085  private static final Constructor<CompilerPhase> constructor = getCompilerPhaseConstructor(GlobalCSE.class);
086
087  /**
088   * Get a constructor object for this compiler phase
089   * @return compiler phase constructor
090   */
091  @Override
092  public Constructor<CompilerPhase> getClassConstructor() {
093    return constructor;
094  }
095
096  /**
097   * Returns the name of the phase
098   */
099  @Override
100  public String getName() {
101    return "Global CSE";
102  }
103
104  /**
105   * Perform the GlobalCSE compiler phase
106   */
107  @Override
108  public void perform(IR ir) {
109    // conditions to leave early
110    if (ir.hasReachableExceptionHandlers() || GCP.tooBig(ir)) {
111      return;
112    }
113    // cache useful values
114    verbose = ir.options.DEBUG_GCP;
115    this.ir = ir;
116    dominator = ir.HIRInfo.dominatorTree;
117
118    // perform GVN
119    (new GlobalValueNumber()).perform(ir);
120    valueNumbers = ir.HIRInfo.valueNumbers;
121
122    if (verbose) VM.sysWrite("in GCSE for " + ir.method + "\n");
123
124    // compute DU and perform copy propagation
125    DefUse.computeDU(ir);
126    Simple.copyPropagation(ir);
127    DefUse.computeDU(ir);
128
129    // perform GCSE starting at the entry block
130    globalCSE(ir.firstBasicBlockInCodeOrder());
131
132    if (VM.VerifyAssertions) {
133      boolean isEmpty = avail.isEmpty();
134      if (!isEmpty) {
135        String msg = avail.toString();
136        VM._assert(isEmpty, msg);
137      }
138    }
139    ir.actualSSAOptions.setScalarValid(false);
140  }
141
142  /**
143   * Recursively descend over all blocks dominated by b. For each
144   * instruction in the block, if it defines a GVN then record it in
145   * the available expressions. If the GVN already exists in the
146   * available expressions then eliminate the instruction and change
147   * all uses of the result of the instruction to be uses of the first
148   * instruction to define the result of this expression.
149   * @param b the current block to process
150   */
151  private void globalCSE(BasicBlock b) {
152    Instruction next, inst;
153    // Iterate over instructions in b
154    inst = b.firstInstruction();
155    while (!BBend.conforms(inst)) {
156      next = inst.nextInstructionInCodeOrder();
157      // check instruction is safe for GCSE, {@see shouldCSE}
158      if (!shouldCSE(inst)) {
159        inst = next;
160        continue;
161      }
162      // check the instruction defines a result
163      RegisterOperand result = getResult(inst);
164      if (result == null) {
165        inst = next;
166        continue;
167      }
168      // get the value number for this result. The value number for
169      // the same sub-expression is shared by all results showing they
170      // can be eliminated. If the value number is UNKNOWN the result
171      // is negative.
172      int vn = valueNumbers.getValueNumber(result);
173      if (vn < 0) {
174        inst = next;
175        continue;
176      }
177      // was this the first definition of the value number?
178      Integer Vn = vn;
179      Instruction former = avail.get(Vn);
180      if (former == null) {
181        // first occurance of value number, record it in the available
182        // expressions
183        avail.put(Vn, inst);
184      } else {
185        // this value number has been seen before so we can use the
186        // earlier version
187        // NB instead of trying to repair Heap SSA, we rebuild it
188        // after CSE
189
190        // relink scalar dependencies - make all uses of the current
191        // instructions result use the first definition of the result
192        // by the earlier expression
193        RegisterOperand formerDef = getResult(former);
194        Register reg = result.getRegister();
195        formerDef.getRegister().setSpansBasicBlock();
196        Enumeration<RegisterOperand> uses = DefUse.uses(reg);
197        while (uses.hasMoreElements()) {
198          RegisterOperand use = uses.nextElement();
199          DefUse.transferUse(use, formerDef);
200        }
201        if (verbose) {
202          VM.sysWrite("using      " + former + "\n" + "instead of " + inst + "\n");
203        }
204        // remove the redundant instruction
205        inst.remove();
206      }
207      inst = next;
208    } // end of instruction iteration
209    // Recurse over all blocks that this block dominates
210    Enumeration<TreeNode> e = dominator.getChildren(b);
211    while (e.hasMoreElements()) {
212      DominatorTreeNode n = (DominatorTreeNode) e.nextElement();
213      BasicBlock bl = n.getBlock();
214      // don't process infrequently executed basic blocks
215      if (ir.options.FREQ_FOCUS_EFFORT && bl.getInfrequent()) continue;
216      globalCSE(bl);
217    }
218    // Iterate over instructions in this basic block removing
219    // available expressions that had been created for this block
220    inst = b.firstInstruction();
221    while (!BBend.conforms(inst)) {
222      next = inst.nextInstructionInCodeOrder();
223      if (!shouldCSE(inst)) {
224        inst = next;
225        continue;
226      }
227      RegisterOperand result = getResult(inst);
228      if (result == null) {
229        inst = next;
230        continue;
231      }
232      int vn = valueNumbers.getValueNumber(result);
233      if (vn < 0) {
234        inst = next;
235        continue;
236      }
237      Integer Vn = vn;
238      Instruction former = avail.get(Vn);
239      if (former == inst) {
240        avail.remove(Vn);
241      }
242      inst = next;
243    }
244  }
245
246  private RegisterOperand getResult(Instruction inst) {
247    if (ResultCarrier.conforms(inst)) {
248      return ResultCarrier.getResult(inst);
249    }
250    if (GuardResultCarrier.conforms(inst)) {
251      return GuardResultCarrier.getGuardResult(inst);
252    }
253    return null;
254  }
255
256  private boolean shouldCSE(Instruction inst) {
257
258    if ((inst.isAllocation()) ||
259        inst.isDynamicLinkingPoint() ||
260        inst.isImplicitLoad() ||
261        inst.isImplicitStore() ||
262        inst.getOpcode() >= ARCH_INDEPENDENT_END_opcode) {
263      return false;
264    }
265
266    switch (inst.getOpcode()) {
267      case INT_MOVE_opcode:
268      case LONG_MOVE_opcode:
269      case CHECKCAST_opcode:
270      case CHECKCAST_NOTNULL_opcode:
271      case CHECKCAST_UNRESOLVED_opcode:
272      case MUST_IMPLEMENT_INTERFACE_opcode:
273      case INSTANCEOF_opcode:
274      case INSTANCEOF_NOTNULL_opcode:
275      case INSTANCEOF_UNRESOLVED_opcode:
276      case PI_opcode:
277      case FLOAT_MOVE_opcode:
278      case DOUBLE_MOVE_opcode:
279      case REF_MOVE_opcode:
280      case GUARD_MOVE_opcode:
281      case GUARD_COMBINE_opcode:
282      case TRAP_IF_opcode:
283      case REF_ADD_opcode:
284      case INT_ADD_opcode:
285      case LONG_ADD_opcode:
286      case FLOAT_ADD_opcode:
287      case DOUBLE_ADD_opcode:
288      case REF_SUB_opcode:
289      case INT_SUB_opcode:
290      case LONG_SUB_opcode:
291      case FLOAT_SUB_opcode:
292      case DOUBLE_SUB_opcode:
293      case INT_MUL_opcode:
294      case LONG_MUL_opcode:
295      case FLOAT_MUL_opcode:
296      case DOUBLE_MUL_opcode:
297      case INT_DIV_opcode:
298      case LONG_DIV_opcode:
299      case FLOAT_DIV_opcode:
300      case DOUBLE_DIV_opcode:
301      case INT_REM_opcode:
302      case LONG_REM_opcode:
303      case FLOAT_REM_opcode:
304      case DOUBLE_REM_opcode:
305      case INT_NEG_opcode:
306      case LONG_NEG_opcode:
307      case FLOAT_NEG_opcode:
308      case DOUBLE_NEG_opcode:
309      case REF_SHL_opcode:
310      case INT_SHL_opcode:
311      case LONG_SHL_opcode:
312      case REF_SHR_opcode:
313      case INT_SHR_opcode:
314      case LONG_SHR_opcode:
315      case REF_USHR_opcode:
316      case INT_USHR_opcode:
317      case LONG_USHR_opcode:
318      case REF_AND_opcode:
319      case INT_AND_opcode:
320      case LONG_AND_opcode:
321      case REF_OR_opcode:
322      case INT_OR_opcode:
323      case LONG_OR_opcode:
324      case REF_XOR_opcode:
325      case INT_XOR_opcode:
326      case REF_NOT_opcode:
327      case INT_NOT_opcode:
328      case LONG_NOT_opcode:
329      case LONG_XOR_opcode:
330      case INT_2LONG_opcode:
331      case INT_2FLOAT_opcode:
332      case INT_2DOUBLE_opcode:
333      case INT_2ADDRSigExt_opcode:
334      case INT_2ADDRZerExt_opcode:
335      case LONG_2ADDR_opcode:
336      case ADDR_2INT_opcode:
337      case ADDR_2LONG_opcode:
338      case LONG_2INT_opcode:
339      case LONG_2FLOAT_opcode:
340      case LONG_2DOUBLE_opcode:
341      case FLOAT_2INT_opcode:
342      case FLOAT_2LONG_opcode:
343      case FLOAT_2DOUBLE_opcode:
344      case DOUBLE_2INT_opcode:
345      case DOUBLE_2LONG_opcode:
346      case DOUBLE_2FLOAT_opcode:
347      case INT_2BYTE_opcode:
348      case INT_2USHORT_opcode:
349      case INT_2SHORT_opcode:
350      case LONG_CMP_opcode:
351      case FLOAT_CMPL_opcode:
352      case FLOAT_CMPG_opcode:
353      case DOUBLE_CMPL_opcode:
354      case DOUBLE_CMPG_opcode:
355      case NULL_CHECK_opcode:
356      case BOUNDS_CHECK_opcode:
357      case INT_ZERO_CHECK_opcode:
358      case LONG_ZERO_CHECK_opcode:
359      case OBJARRAY_STORE_CHECK_opcode:
360      case OBJARRAY_STORE_CHECK_NOTNULL_opcode:
361      case BOOLEAN_NOT_opcode:
362      case BOOLEAN_CMP_INT_opcode:
363      case BOOLEAN_CMP_ADDR_opcode:
364      case FLOAT_AS_INT_BITS_opcode:
365      case INT_BITS_AS_FLOAT_opcode:
366      case DOUBLE_AS_LONG_BITS_opcode:
367      case LONG_BITS_AS_DOUBLE_opcode:
368      case ARRAYLENGTH_opcode:
369      case GET_OBJ_TIB_opcode:
370      case GET_CLASS_TIB_opcode:
371      case GET_TYPE_FROM_TIB_opcode:
372      case GET_SUPERCLASS_IDS_FROM_TIB_opcode:
373      case GET_DOES_IMPLEMENT_FROM_TIB_opcode:
374      case GET_ARRAY_ELEMENT_TIB_FROM_TIB_opcode:
375        return !(GCP.usesOrDefsPhysicalRegisterOrAddressType(inst));
376    }
377    return false;
378  }
379}