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 org.jikesrvm.compilers.opt.driver.CompilerPhase;
016import org.jikesrvm.compilers.opt.ir.Binary;
017import org.jikesrvm.compilers.opt.ir.GuardCarrier;
018import org.jikesrvm.compilers.opt.ir.GuardResultCarrier;
019import org.jikesrvm.compilers.opt.ir.Move;
020import org.jikesrvm.compilers.opt.ir.NullCheck;
021import org.jikesrvm.compilers.opt.ir.BasicBlock;
022import org.jikesrvm.compilers.opt.ir.IR;
023import org.jikesrvm.compilers.opt.ir.Instruction;
024import org.jikesrvm.compilers.opt.ir.Operator;
025import org.jikesrvm.compilers.opt.ir.operand.MemoryOperand;
026import org.jikesrvm.compilers.opt.ir.operand.Operand;
027
028import static org.jikesrvm.compilers.opt.ir.Operators.GUARD_COMBINE;
029import static org.jikesrvm.compilers.opt.ir.Operators.GUARD_MOVE;
030import static org.jikesrvm.compilers.opt.ir.Operators.NULL_CHECK;
031
032/**
033 * This module performs two tasks:
034 * <ul>
035 *   <li> (1) When possible, it folds null checks into the first load/store
036 *            that is being guarded by the null check
037 *   <li> (2) It removes all validation registers from the IR
038 * </ul>
039 *
040 * <p> Doing (1) more or less implies either (a) doing (2) or
041 * (b) making large changes to the MIR operator set such that
042 * all load/stores produce validation results.
043 * Although this would be possible, it would not be a trivial change.
044 * So, until we have an urgent need to preserve guard operands all
045 * the way through the MIR, we'll take the easy way out.
046 */
047public class NullCheckCombining extends CompilerPhase {
048
049  /**
050   * Return this instance of this phase. This phase contains no
051   * per-compilation instance fields.
052   * @param ir not used
053   * @return this
054   */
055  @Override
056  public CompilerPhase newExecution(IR ir) {
057    return this;
058  }
059
060  @Override
061  public final String getName() {
062    return "NullCheckCombining";
063  }
064
065  /**
066   * Perform nullcheck combining and validation register removal.
067   *
068   * @param ir the IR to transform
069   */
070  @Override
071  public void perform(IR ir) {
072    for (BasicBlock bb = ir.firstBasicBlockInCodeOrder(); bb != null; bb = bb.nextBasicBlockInCodeOrder()) {
073      if (!bb.isEmpty()) {
074        Instruction lastInstr = bb.lastInstruction();
075
076        boolean combined;
077        boolean remaining;
078        // (1) Combine null checks in bb into the first load/store in
079        // bb they guard.
080        // Restrict this to respect PEI ordering.
081        // Only do locally, since we don't understand control flow here.
082        // We could be more aggressive about moving PEIs past stores
083        // by determining which stores actually update global or
084        // handler-visible state.
085        do {
086          combined = remaining = false;
087          Instruction activeNullCheck = null;
088          Operand activeGuard = null;
089          for (Instruction instr = bb.firstRealInstruction(),
090              nextInstr = null; instr != lastInstr; instr = nextInstr) {
091            nextInstr = instr.nextInstructionInCodeOrder();
092            Operator op = instr.operator();
093            if (op == GUARD_MOVE) {
094              if (activeGuard != null && Move.getVal(instr).similar(activeGuard)) {
095                activeGuard = Move.getResult(instr);
096              }
097            } else if (op == GUARD_COMBINE) {
098              if (activeGuard != null &&
099                  (Binary.getVal1(instr) == activeGuard || Binary.getVal2(instr) == activeGuard)) {
100                activeGuard = null;
101              }
102            } else if (op == NULL_CHECK) {
103              remaining |= (activeGuard == null);
104              activeGuard = NullCheck.getGuardResult(instr);
105              activeNullCheck = instr;
106            } else if (isExplicitStore(instr, op)) {
107              if (instr.isPEI()) {
108                // can't reorder PEI's
109                // NOTE: don't mark remaining, since we'd hit the same problem instr again.
110                activeGuard = null;
111              } else {
112                if (activeGuard != null && canFold(instr, activeGuard, true)) {
113                  instr.markAsPEI();
114                  activeNullCheck.remove();
115                  activeGuard = null;
116                  combined = true;
117                }
118                remaining |= (activeGuard == null);
119                activeGuard = null;   // don't attempt to move PEI past a store; could do better.
120              }
121            } else if (isExplicitLoad(instr, op)) {
122              if (activeGuard != null && canFold(instr, activeGuard, false)) {
123                instr.markAsPEI();
124                activeNullCheck.remove();
125                activeGuard = null;
126                combined = true;
127              } else if (instr.isPEI()) {
128                // can't reorder PEI's
129                // NOTE: don't mark remaining, since we'd hit the same problem instr again.
130                activeGuard = null;
131              }
132            } else {
133              if (op.isImplicitStore() || op.isPEI()) {
134                // NOTE: don't mark remaining, since we'd hit the same problem instr again.
135                activeGuard = null; // don't reorder PEI's; be conservative about stores.
136              }
137            }
138          }
139        } while (combined & remaining);
140
141        // (2) Blow away all validation registers in bb.
142        for (Instruction instr = bb.firstRealInstruction(), nextInstr = null; instr != lastInstr; instr = nextInstr) {
143          nextInstr = instr.nextInstructionInCodeOrder();
144          Operator op = instr.operator();
145          if (op == GUARD_MOVE || op == GUARD_COMBINE) {
146            instr.remove();
147          } else {
148            if (GuardResultCarrier.conforms(op)) {
149              GuardResultCarrier.setGuardResult(instr, null);
150            }
151            if (GuardCarrier.conforms(op)) {
152              GuardCarrier.setGuard(instr, null);
153            }
154          }
155        }
156      }
157    }
158  }
159
160  private boolean isExplicitStore(Instruction s, Operator op) {
161    if (op.isExplicitStore()) return true;
162    for (int i = 0, n = s.getNumberOfDefs(); i < n; i++) {
163      if (s.getOperand(i) instanceof MemoryOperand) return true;
164    }
165    return false;
166  }
167
168  private boolean isExplicitLoad(Instruction s, Operator op) {
169    if (op.isExplicitLoad()) return true;
170    int numOps = s.getNumberOfOperands();
171    int numUses = s.getNumberOfUses();
172    for (int i = numOps - numUses; i < numOps; i++) {
173      if (s.getOperand(i) instanceof MemoryOperand) {
174        return true;
175      }
176    }
177    return false;
178  }
179
180  private boolean canFold(Instruction s, Operand activeGuard, boolean isStore) {
181    if (GuardCarrier.conforms(s) && GuardCarrier.hasGuard(s) && activeGuard.similar(GuardCarrier.getGuard(s))) {
182      return true;
183    }
184    for (int i = 0, n = s.getNumberOfOperands(); i < n; i++) {
185      Operand op = s.getOperand(i);
186      if (op instanceof MemoryOperand) {
187        MemoryOperand memOp = (MemoryOperand) op;
188        if (activeGuard.similar(memOp.guard)) {
189          return true;
190        }
191      }
192    }
193    return false;
194  }
195}
196
197
198