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