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.ssa;
014
015 import static org.jikesrvm.compilers.opt.ir.Operators.PI;
016
017 import java.lang.reflect.Constructor;
018 import java.util.Enumeration;
019
020 import org.jikesrvm.VM;
021 import org.jikesrvm.compilers.opt.OptOptions;
022 import org.jikesrvm.compilers.opt.OptimizingCompilerException;
023 import org.jikesrvm.compilers.opt.driver.CompilerPhase;
024 import org.jikesrvm.compilers.opt.ir.BasicBlock;
025 import org.jikesrvm.compilers.opt.ir.BoundsCheck;
026 import org.jikesrvm.compilers.opt.ir.GuardedUnary;
027 import org.jikesrvm.compilers.opt.ir.IR;
028 import org.jikesrvm.compilers.opt.ir.IRTools;
029 import org.jikesrvm.compilers.opt.ir.IfCmp;
030 import org.jikesrvm.compilers.opt.ir.InlineGuard;
031 import org.jikesrvm.compilers.opt.ir.Instruction;
032 import org.jikesrvm.compilers.opt.ir.Move;
033 import org.jikesrvm.compilers.opt.ir.NullCheck;
034 import org.jikesrvm.compilers.opt.ir.Operator;
035 import org.jikesrvm.compilers.opt.ir.TypeCheck;
036 import org.jikesrvm.compilers.opt.ir.operand.Operand;
037 import org.jikesrvm.compilers.opt.ir.operand.RegisterOperand;
038
039 /**
040 * This pass inserts PI nodes (Effectively copies)
041 * on branch edges, to introduce new names for analysis
042 */
043 public final class PiNodes extends CompilerPhase {
044
045 /**
046 * Should we insert PI nodes for array references after bounds-checks
047 * and null-checks?
048 * <p>TODO: if this is false, then null-check elimination
049 * will be ineffective.
050 * <p>TODO: prove that null-check elimination is
051 * sound before turning this on again.
052 */
053 static final boolean CHECK_REF_PI = false;
054
055 /**
056 * Should we insert (true) or delete (false) PI nodes?
057 */
058 final boolean insertion;
059
060 /**
061 * Are we adding pi nodes for type checks only? This is for GNOSYS
062 * analysis right now.
063 */
064 final boolean typeChecks;
065
066 /**
067 * Should this phase be performed?
068 * Only perform this when we are doing an SSA-based optimization
069 * that can benefit from PI nodes.
070 */
071 @Override
072 public boolean shouldPerform(OptOptions options) {
073 return options.SSA_GLOBAL_BOUNDS_CHECK || typeChecks;
074 }
075
076 /**
077 * Constructor for this compiler phase
078 */
079 private static final Constructor<CompilerPhase> constructor =
080 getCompilerPhaseConstructor(PiNodes.class, new Class[]{Boolean.TYPE, Boolean.TYPE});
081
082 /**
083 * Get a constructor object for this compiler phase
084 * @return compiler phase constructor
085 */
086 @Override
087 public Constructor<CompilerPhase> getClassConstructor() {
088 return constructor;
089 }
090
091 /**
092 * A String representation of this phase
093 * @return a string representation
094 */
095 @Override
096 public String getName() {
097 return "Pi Nodes " + insertion;
098 }
099
100 /**
101 * Should we print the IR either before or after this phase?
102 * @param options controlling compiler options
103 * @param before control for the query
104 */
105 @Override
106 public boolean printingEnabled(OptOptions options, boolean before) {
107 return false;
108 }
109
110 /**
111 * Create the phase.
112 *
113 * @param insert If true, we insert PI nodes, If false, we remove them.
114 */
115 public PiNodes(boolean insert) {
116 this.insertion = insert;
117 this.typeChecks = false;
118 }
119
120 /**
121 * Create the phase.
122 *
123 * @param insert If true, we insert PI nodes, If false, we remove them.
124 * @param typeChecks If true, we insert PI nodes only for type checks.
125 */
126 public PiNodes(boolean insert, boolean typeChecks) {
127 super(new Object[]{insert, typeChecks});
128 this.insertion = insert;
129 this.typeChecks = typeChecks;
130 }
131
132 @Override
133 public void perform(IR ir) {
134 if (insertion) {
135 if (!typeChecks) {
136 insertPiIfNodes(ir);
137 insertPiBcNodes(ir);
138 insertPiNullCheckNodes(ir);
139 } else {
140 insertPiCheckCastNodes(ir);
141 }
142 // invalidate SSA state
143 ir.actualSSAOptions = null;
144 } else {
145 cleanUp(ir);
146 }
147 }
148
149 /**
150 * Insert PI nodes corresponding to compare operations.
151 * Pi-nodes are represented as dummy assignments with a single
152 * argument inserted along each outedge of the conditional.
153 *
154 * @param ir the governing IR
155 */
156 private void insertPiIfNodes(IR ir) {
157 Enumeration<Instruction> e = ir.forwardInstrEnumerator();
158 while(e.hasMoreElements()) {
159 Instruction instr = e.nextElement();
160 // TODO: what other compareops generate useful assertions?
161 if (IfCmp.conforms(instr) || InlineGuard.conforms(instr)) {
162
163 BasicBlock thisbb = instr.getBasicBlock();
164 // only handle the "normal" case
165 if (thisbb.getNumberOfNormalOut() != 2) {
166 continue;
167 }
168 // insert new basic blocks on each edge out of thisbb
169 Enumeration<BasicBlock> outBB = thisbb.getNormalOut();
170 BasicBlock out1 = outBB.nextElement();
171 BasicBlock new1 = IRTools.makeBlockOnEdge(thisbb, out1, ir);
172 BasicBlock out2 = outBB.nextElement();
173 BasicBlock new2 = IRTools.makeBlockOnEdge(thisbb, out2, ir);
174
175 // For these types of IfCmp's, the Pi Node is not actually
176 // needed yet. For now the only functionality needed is the
177 // blocks made on the outgoing edges.
178 if (InlineGuard.conforms(instr)) continue;
179
180 RegisterOperand ifGuard = IfCmp.getGuardResult(instr);
181
182 if (VM.VerifyAssertions) {
183 VM._assert(ifGuard != null);
184 }
185 // get compared variables
186 Operand a = IfCmp.getVal1(instr);
187 Operand b = IfCmp.getVal2(instr);
188 // determine which block is "taken" on the branch
189 BasicBlock takenBlock = IfCmp.getTarget(instr).target.getBasicBlock();
190 boolean new1IsTaken = false;
191 if (takenBlock == new1) {
192 new1IsTaken = true;
193 }
194
195 // insert the PI-node instructions for a and b
196 if (a.isRegister() &&
197 !a.asRegister().getRegister().isPhysical() &&
198 (a.asRegister().getRegister().isInteger() || a.asRegister().getRegister().isAddress())) {
199 // insert pi-nodes only for variables, not constants
200 Instruction s = GuardedUnary.create(PI, (RegisterOperand) a.copy(), a.copy(), null);
201 RegisterOperand sGuard = (RegisterOperand) ifGuard.copy();
202 if (new1IsTaken) {
203 sGuard.setTaken();
204 } else {
205 sGuard.setNotTaken();
206 }
207 GuardedUnary.setGuard(s, sGuard);
208 new1.prependInstruction(s);
209 s = s.copyWithoutLinks();
210 sGuard = (RegisterOperand) ifGuard.copy();
211 if (new1IsTaken) {
212 sGuard.setNotTaken();
213 } else {
214 sGuard.setTaken();
215 }
216 GuardedUnary.setGuard(s, sGuard);
217 new2.prependInstruction(s);
218 }
219 if (b.isRegister() &&
220 !b.asRegister().getRegister().isPhysical() &&
221 (b.asRegister().getRegister().isInteger() || b.asRegister().getRegister().isAddress())) {
222 Instruction s = GuardedUnary.create(PI, (RegisterOperand) b.copy(), b.copy(), null);
223 RegisterOperand sGuard = (RegisterOperand) ifGuard.copy();
224 if (new1IsTaken) {
225 sGuard.setTaken();
226 } else {
227 sGuard.setNotTaken();
228 }
229 GuardedUnary.setGuard(s, sGuard);
230 new1.prependInstruction(s);
231 s = s.copyWithoutLinks();
232 sGuard = (RegisterOperand) ifGuard.copy();
233 if (new1IsTaken) {
234 sGuard.setNotTaken();
235 } else {
236 sGuard.setTaken();
237 }
238 GuardedUnary.setGuard(s, sGuard);
239 new2.prependInstruction(s);
240 }
241 }
242 }
243 }
244
245 /**
246 * Insert Pi nodes for boundchecks.
247 *
248 * <p>Each boundcheck Arr, Index will be followed by
249 * <pre> PI Index, Index </pre>
250 *
251 * @param ir the governing IR
252 */
253 private void insertPiBcNodes(IR ir) {
254 Instruction nextInst = null;
255 // for each instruction in the IR
256 for (Instruction instr = ir.firstInstructionInCodeOrder(); instr != null; instr = nextInst) {
257 // can't use iterator, since we modify instruction stream
258 nextInst = instr.nextInstructionInCodeOrder();
259 if (BoundsCheck.conforms(instr)) {
260 // Create a pi node for the index.
261 Operand index = BoundsCheck.getIndex(instr);
262 // create the instruction and insert it
263 if (index.isRegister() && !index.asRegister().getRegister().isPhysical()) {
264 Instruction s = GuardedUnary.create(PI, (RegisterOperand) index.copy(), index.copy(), null);
265 RegisterOperand sGuard = (RegisterOperand) BoundsCheck.getGuardResult(instr).copy();
266 sGuard.setBoundsCheck();
267 GuardedUnary.setGuard(s, sGuard);
268 instr.insertAfter(s);
269 }
270 if (CHECK_REF_PI) {
271 // Create a pi node for the array.
272 Operand array = BoundsCheck.getRef(instr);
273 // create the instruction and insert it
274 if (array.isRegister() && !array.asRegister().getRegister().isPhysical()) {
275 Instruction s = GuardedUnary.create(PI, (RegisterOperand) array.copy(), array.copy(), null);
276 RegisterOperand sGuard = (RegisterOperand) BoundsCheck.getGuardResult(instr).copy();
277 sGuard.setBoundsCheck();
278 GuardedUnary.setGuard(s, sGuard);
279 instr.insertAfter(s);
280 }
281 }
282 }
283 }
284 }
285
286 /**
287 * Insert Pi nodes for null check operations.
288 *
289 * <p>Each checkcast obj will be followed by
290 * <pre> PI obj, obj </pre>
291 *
292 * @param ir the governing IR
293 */
294 private void insertPiNullCheckNodes(IR ir) {
295 if (!CHECK_REF_PI) return;
296 Instruction nextInst = null;
297 // for each instruction in the IR
298 for (Instruction instr = ir.firstInstructionInCodeOrder(); instr != null; instr = nextInst) {
299 // can't use iterator, since we modify instruction stream
300 nextInst = instr.nextInstructionInCodeOrder();
301 if (NullCheck.conforms(instr)) {
302 // get compared variables
303 Operand obj = NullCheck.getRef(instr);
304 // create the instruction and insert it
305 if (obj.isRegister()) {
306 RegisterOperand lval = (RegisterOperand) obj.copy();
307 Instruction s = GuardedUnary.create(PI, lval, obj.copy(), null);
308 RegisterOperand sGuard = (RegisterOperand) NullCheck.getGuardResult(instr).copy();
309 sGuard.setNullCheck();
310 GuardedUnary.setGuard(s, sGuard);
311 instr.insertAfter(s);
312 }
313 }
314 }
315 }
316
317 /**
318 * Insert Pi nodes for checkcast operations.
319 *
320 * <p>Each checkcast obj will be followed by
321 * <pre> ref_move obj, obj </pre>
322 *
323 * @param ir the governing IR
324 */
325 private void insertPiCheckCastNodes(IR ir) {
326 Instruction nextInst = null;
327 // for each instruction in the IR
328 for (Instruction instr = ir.firstInstructionInCodeOrder(); instr != null; instr = nextInst) {
329 // can't use iterator, since we modify instruction stream
330 nextInst = instr.nextInstructionInCodeOrder();
331 if (TypeCheck.conforms(instr)) {
332 // get compared variables
333 Operand obj = TypeCheck.getRef(instr);
334 // create the instruction and insert it
335 if (obj.isRegister()) {
336 RegisterOperand lval = (RegisterOperand) obj.copy();
337 lval.clearDeclaredType();
338 if (lval.getType().isLoaded() && lval.getType().isClassType() && lval.getType().peekType().asClass().isFinal()) {
339 lval.setPreciseType(TypeCheck.getType(instr).getTypeRef());
340 } else {
341 lval.clearPreciseType();
342 lval.setType(TypeCheck.getType(instr).getTypeRef());
343 }
344 Instruction s = GuardedUnary.create(PI, lval, obj.copy(), null);
345 s.position = instr.position;
346 s.bcIndex = instr.bcIndex;
347 Operand iGuard = TypeCheck.getGuard(instr);
348 if (iGuard != null) {
349 Operand sGuard = iGuard.copy();
350 GuardedUnary.setGuard(s, sGuard);
351 }
352 instr.insertAfter(s);
353 }
354 }
355 }
356 }
357
358 /**
359 * Change all PI nodes to INT_MOVE instructions
360 * <p> Side effect: invalidates SSA state
361 *
362 * @param ir the governing IR
363 */
364 static void cleanUp(IR ir) {
365 for (Enumeration<Instruction> e = ir.forwardInstrEnumerator(); e.hasMoreElements();) {
366 Instruction s = e.nextElement();
367 if (s.operator == PI) {
368 RegisterOperand result = GuardedUnary.getResult(s);
369 Operator mv = IRTools.getMoveOp(result.getType());
370 Operand val = GuardedUnary.getVal(s);
371 Move.mutate(s, mv, result, val);
372 }
373 }
374 // invalidate SSA state
375 ir.actualSSAOptions = null;
376 }
377
378 /**
379 * Get the instruction a Pi node is linked to.
380 * <strong>PRECONDITION: </strong> register lists computed and valid.
381 */
382 public static Instruction getGenerator(Instruction def) {
383 if (def.operator != PI) {
384 throw new OptimizingCompilerException("Not a PI Node!");
385 }
386 Operand g = GuardedUnary.getGuard(def);
387 Instruction link = g.asRegister().getRegister().defList.instruction;
388 return link;
389 }
390
391 /**
392 * Is an instruction a Pi node linked to the <em>not taken</em> edge of
393 * a conditional branch instruction?
394 */
395 public static boolean isNotTakenPi(Instruction def) {
396 if (def.operator != PI) {
397 return false;
398 }
399 Operand g = GuardedUnary.getGuard(def);
400 return g.asRegister().isNotTaken();
401 }
402
403 /**
404 * Is an instruction a Pi node linked to the <em>taken</em> edge of
405 * a conditional branch instruction?
406 */
407 public static boolean isTakenPi(Instruction def) {
408 if (def.operator != PI) {
409 return false;
410 }
411 Operand g = GuardedUnary.getGuard(def);
412 return g.asRegister().isTaken();
413 }
414
415 /**
416 * Is an instruction a Pi node linked to a bounds-check?
417 */
418 public static boolean isBoundsCheckPi(Instruction def) {
419 if (def.operator != PI) {
420 return false;
421 }
422 Operand g = GuardedUnary.getGuard(def);
423 return g.asRegister().isBoundsCheck();
424 }
425
426 /**
427 * Is an instruction a Pi node linked to a null-check?
428 */
429 public static boolean isNullCheckPi(Instruction def) {
430 if (def.operator != PI) {
431 return false;
432 }
433 Operand g = GuardedUnary.getGuard(def);
434 return g.asRegister().isNullCheck();
435 }
436 }