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 java.util.Enumeration;
016
017 import org.jikesrvm.VM;
018 import org.jikesrvm.compilers.opt.driver.CompilerPhase;
019 import org.jikesrvm.compilers.opt.ir.IfCmp;
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.IRTools;
025 import org.jikesrvm.compilers.opt.ir.Instruction;
026 import static org.jikesrvm.compilers.opt.ir.Operators.BBEND;
027 import static org.jikesrvm.compilers.opt.ir.Operators.CHECKCAST;
028 import static org.jikesrvm.compilers.opt.ir.Operators.CHECKCAST_NOTNULL;
029 import static org.jikesrvm.compilers.opt.ir.Operators.GOTO;
030 import static org.jikesrvm.compilers.opt.ir.Operators.NULL_CHECK;
031 import static org.jikesrvm.compilers.opt.ir.Operators.REF_IFCMP;
032 import static org.jikesrvm.compilers.opt.ir.Operators.REF_MOVE;
033 import org.jikesrvm.compilers.opt.ir.Register;
034 import org.jikesrvm.compilers.opt.ir.TypeCheck;
035 import org.jikesrvm.compilers.opt.ir.operand.NullConstantOperand;
036 import org.jikesrvm.compilers.opt.ir.operand.RegisterOperand;
037
038 /**
039 * Perform simple peephole optimizations to reduce the overhead of
040 * checking casts. This code was inspired by some special cases in
041 * handling checkcast in HIR2LIR, but the actual code is all different.
042 *
043 * <p> There are currently the following optimizations:
044 * <ul>
045 * <li> 1. If a checkcast is just before a nullcheck, invert them and
046 * convert the checkcast into a checkcast_not_null
047 * <li> 2. If a checkcast is followed by a branch based on a null test of
048 * the same variable, then push the cast below the conditional on
049 * the path where the obejct is known not to be null. And convert
050 * it to a checkcast_not_null
051 * </ul>
052 */
053 public final class LocalCastOptimization extends CompilerPhase {
054
055 @Override
056 public String getName() {
057 return "Local Cast Optimizations";
058 }
059
060 @Override
061 public void reportAdditionalStats() {
062 VM.sysWrite(" ");
063 VM.sysWrite(container.counter1 / container.counter2 * 100, 2);
064 VM.sysWrite("% Infrequent BBs");
065 }
066
067 /**
068 * Return this instance of this phase. This phase contains no
069 * per-compilation instance fields.
070 * @param ir not used
071 * @return this
072 */
073 @Override
074 public CompilerPhase newExecution(IR ir) {
075 return this;
076 }
077
078 /**
079 * Main routine: perform the transformation.
080 * @param ir the IR to transform
081 */
082 @Override
083 public void perform(IR ir) {
084 // loop over all basic blocks ...
085 for (Enumeration<BasicBlock> e = ir.getBasicBlocks(); e.hasMoreElements();) {
086 BasicBlock bb = e.nextElement();
087 if (bb.isEmpty()) continue;
088 container.counter2++;
089 if (bb.getInfrequent()) {
090 container.counter1++;
091 if (ir.options.FREQ_FOCUS_EFFORT) continue;
092 }
093 // visit each instruction in the basic block
094 for (Enumeration<Instruction> ie = bb.forwardInstrEnumerator(); ie.hasMoreElements();) {
095 Instruction s = ie.nextElement();
096 if (TypeCheck.conforms(s) && (invertNullAndTypeChecks(s) || pushTypeCheckBelowIf(s, ir))) {
097 // hack: we may have modified the instructions; start over
098 ie = bb.forwardInstrEnumerator();
099 }
100 }
101 }
102 }
103
104 /**
105 * If there's a checkcast followed by a null check, move the checkcast
106 * after the null check, since the null pointer exception must be thrown
107 * anyway.
108 * @param s the potential checkcast instruction
109 * @return true iff the transformation happened
110 */
111 private boolean invertNullAndTypeChecks(Instruction s) {
112 if (s.operator() == CHECKCAST) {
113 Register r = TypeCheck.getRef(s).asRegister().getRegister();
114 Instruction n = s.nextInstructionInCodeOrder();
115 while (n.operator() == REF_MOVE &&
116 Move.getVal(n) instanceof RegisterOperand &&
117 Move.getVal(n).asRegister().getRegister() == r) {
118 r = Move.getResult(n).asRegister().getRegister();
119 n = n.nextInstructionInCodeOrder();
120 }
121 if (n.operator() == NULL_CHECK &&
122 TypeCheck.getRef(s).asRegister().getRegister() == NullCheck.getRef(n).asRegister().getRegister()) {
123 s.remove();
124 TypeCheck.mutate(s,
125 CHECKCAST_NOTNULL,
126 TypeCheck.getClearResult(s),
127 TypeCheck.getClearRef(s),
128 TypeCheck.getClearType(s),
129 NullCheck.getGuardResult(n).copy());
130 n.insertAfter(s);
131 return true;
132 }
133 }
134 return false;
135 }
136
137 /**
138 * Where legal, move a type check below an if instruction.
139 * @param s the potential typecheck instruction
140 * @param ir the governing IR
141 */
142 private boolean pushTypeCheckBelowIf(Instruction s, IR ir) {
143 if (s.operator() == CHECKCAST) {
144 Register r = TypeCheck.getRef(s).asRegister().getRegister();
145 Instruction n = s.nextInstructionInCodeOrder();
146 /* find moves of the checked value, so that we can also
147 optimize cases where the checked value is moved before
148 it is used
149 */
150 while (n.operator() == REF_MOVE &&
151 Move.getVal(n) instanceof RegisterOperand &&
152 Move.getVal(n).asRegister().getRegister() == r) {
153 r = Move.getResult(n).asRegister().getRegister();
154 n = n.nextInstructionInCodeOrder();
155 }
156 if (n.operator() == REF_IFCMP &&
157 IfCmp.getVal2(n) instanceof NullConstantOperand &&
158 IfCmp.getVal1(n) instanceof RegisterOperand &&
159 r == IfCmp.getVal1(n).asRegister().getRegister()) {
160 BasicBlock newBlock, patchBlock;
161 BasicBlock myBlock = n.getBasicBlock();
162 Instruction after = n.nextInstructionInCodeOrder();
163 if (IfCmp.getCond(n).isEQUAL())
164 /* We fall through on non-NULL values, so the
165 checkcast must be on the not-taken path
166 from the branch. There are 3 cases:
167 1. n is the last instruction in its basic block,
168 in which case control falls through to the next
169 block in code order. This case is if the
170 instruction after n is a BBEND
171 */ {
172 if (after.operator() == BBEND) {
173 patchBlock = myBlock.nextBasicBlockInCodeOrder();
174 } else if (after.operator() == GOTO) {
175 /* 2. n is followed by an unconditional goto. In
176 this case control jumps to the target of the
177 goto.
178 */
179 patchBlock = after.getBranchTarget();
180 } else if (after.operator() == REF_IFCMP) {
181 /* 3. n is followed by another conditional branch. In
182 this case, we will split the basic block to make
183 n the last instruction in the block, and then
184 we have the fall through case again.
185 */
186 patchBlock = myBlock.splitNodeAt(n, ir);
187 myBlock.insertOut(patchBlock);
188 ir.cfg.linkInCodeOrder(myBlock, patchBlock);
189 } else {
190 /* this is a bad thing */
191 return false;
192 }
193 } else
194 /* We branch on not-NULL values, so the checkcast
195 must be spliced in before the branch target
196 */ {
197 patchBlock = n.getBranchTarget();
198 }
199 /* add block between branch and appropriate successor */
200
201 newBlock = IRTools.makeBlockOnEdge(myBlock, patchBlock, ir);
202
203 /* put check in new block */
204 s.remove();
205 TypeCheck.mutate(s,
206 CHECKCAST_NOTNULL,
207 TypeCheck.getClearResult(s),
208 TypeCheck.getClearRef(s),
209 TypeCheck.getClearType(s),
210 IfCmp.getGuardResult(n).copyRO());
211 newBlock.prependInstruction(s);
212 return true;
213 }
214 }
215 return false;
216 }
217 }