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;
014
015import java.util.Enumeration;
016import java.util.HashMap;
017import java.util.HashSet;
018import java.util.Map;
019
020import org.jikesrvm.VM;
021import org.jikesrvm.compilers.opt.driver.CompilerPhase;
022import org.jikesrvm.compilers.opt.ir.BasicBlock;
023import org.jikesrvm.compilers.opt.ir.IR;
024import org.jikesrvm.compilers.opt.ir.Instruction;
025import org.jikesrvm.compilers.opt.ir.Move;
026import org.jikesrvm.compilers.opt.ir.Register;
027import org.jikesrvm.compilers.opt.ir.operand.Operand;
028import org.jikesrvm.compilers.opt.ir.operand.RegisterOperand;
029
030/**
031 * Perform local copy propagation for a factored basic block.
032 * Orthogonal to the copy propagation performed in Simple
033 * since here we use flow-sensitive analysis within a basic block.
034 * <p>
035 * TODO: factor out common functionality in the various local propagation
036 * phases?
037 */
038public class LocalCopyProp extends CompilerPhase {
039
040  @Override
041  public final boolean shouldPerform(OptOptions options) {
042    return options.LOCAL_COPY_PROP;
043  }
044
045  @Override
046  public final String getName() {
047    return "Local CopyProp";
048  }
049
050  @Override
051  public void reportAdditionalStats() {
052    VM.sysWrite("  ");
053    VM.sysWrite(container.counter1 / container.counter2 * 100, 2);
054    VM.sysWrite("% Infrequent BBs");
055  }
056
057  /**
058   * Return this instance of this phase. This phase contains no
059   * per-compilation instance fields.
060   * @param ir not used
061   * @return this
062   */
063  @Override
064  public CompilerPhase newExecution(IR ir) {
065    return this;
066  }
067
068  /**
069   * Perform local constant propagation for a method.
070   *
071   * @param ir the IR to optimize
072   */
073  @Override
074  public void perform(IR ir) {
075    HashMap<Register, Operand> info = new HashMap<Register, Operand>();
076    for (BasicBlock bb = ir.firstBasicBlockInCodeOrder(); bb != null; bb = bb.nextBasicBlockInCodeOrder()) {
077      if (bb.isEmpty()) continue;
078      container.counter2++;
079      if (bb.getInfrequent()) {
080        container.counter1++;
081        if (ir.options.FREQ_FOCUS_EFFORT) continue;
082      }
083      // iterate over all instructions in the basic block
084      for (Instruction s = bb.firstRealInstruction(),
085          sentinel = bb.lastInstruction(); s != sentinel; s = s.nextInstructionInCodeOrder()) {
086
087        if (!info.isEmpty()) {
088          // PROPAGATE COPIES
089          int numUses = s.getNumberOfPureUses();
090          if (numUses > 0) {
091            boolean didSomething = false;
092            for (Enumeration<Operand> e = s.getUses(); e.hasMoreElements();) {
093              Operand use = e.nextElement();
094              if (use instanceof RegisterOperand) {
095                RegisterOperand rUse = (RegisterOperand) use;
096                Operand value = info.get(rUse.getRegister());
097                if (value != null) {
098                  didSomething = true;
099                  value = value.copy();
100                  if (value instanceof RegisterOperand) {
101                    // preserve program point specific typing!
102                    ((RegisterOperand) value).copyTypeFrom(rUse);
103                  }
104                  s.replaceOperand(use, value);
105                }
106              }
107            }
108            if (didSomething) {
109              Simplifier.simplify(ir.IRStage == IR.HIR, ir.regpool, ir.options, s);
110            }
111          }
112          // KILL
113          boolean killPhysicals = s.isTSPoint() || s.operator().implicitDefs != 0;
114          // kill any physical registers
115          // TODO: use a better data structure for efficiency.
116          // I'm being lazy for now in the name of avoiding
117          // premature optimization.
118          if (killPhysicals) {
119            HashSet<Register> toRemove = new HashSet<Register>();
120            for (Map.Entry<Register, Operand> entry : info.entrySet()) {
121              Register eR = entry.getValue().asRegister().getRegister();
122              if (killPhysicals && eR.isPhysical()) {
123                // delay the removal to avoid ConcurrentModification with iterator.
124                toRemove.add(entry.getKey());
125              }
126            }
127            // Now perform the removals.
128            for (final Register aToRemove : toRemove) {
129              info.remove(aToRemove);
130            }
131          }
132
133          for (Enumeration<Operand> e = s.getDefs(); e.hasMoreElements();) {
134            Operand def = e.nextElement();
135            if (def != null && def.isRegister()) {
136              Register r = def.asRegister().getRegister();
137              info.remove(r);
138              // also must kill any registers mapped to r
139              // TODO: use a better data structure for efficiency.
140              // I'm being lazy for now in the name of avoiding
141              // premature optimization.
142              HashSet<Register> toRemove = new HashSet<Register>();
143              for (Map.Entry<Register, Operand> entry : info.entrySet()) {
144                Register eR = ((RegisterOperand) entry.getValue()).getRegister();
145                if (eR == r) {
146                  // delay the removal to avoid ConcurrentModification
147                  // with iterator.
148                  toRemove.add(entry.getKey());
149                }
150              }
151              // Now perform the removals.
152              for (final Register register : toRemove) {
153                info.remove(register);
154              }
155            }
156          }
157        }
158        // GEN
159        if (Move.conforms(s)) {
160          Operand val = Move.getVal(s);
161          if (val.isRegister()) {
162            RegisterOperand rhs = val.asRegister();
163            if (!rhs.getRegister().isPhysical()) {
164              RegisterOperand lhs = Move.getResult(s);
165              /* Only gen if the move instruction does not represent a Magic <==> non-Magic coercion */
166              if (lhs.getType().isReferenceType() == rhs.getType().isReferenceType()) {
167                info.put(lhs.getRegister(), val);
168              }
169            }
170          }
171        }
172      }
173      info.clear();
174    }
175  }
176}