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; 016 017import org.jikesrvm.VM; 018import org.jikesrvm.compilers.opt.driver.CompilerPhase; 019import org.jikesrvm.compilers.opt.ir.IfCmp; 020import org.jikesrvm.compilers.opt.ir.Move; 021import org.jikesrvm.compilers.opt.ir.NullCheck; 022import org.jikesrvm.compilers.opt.ir.BasicBlock; 023import org.jikesrvm.compilers.opt.ir.IR; 024import org.jikesrvm.compilers.opt.ir.IRTools; 025import org.jikesrvm.compilers.opt.ir.Instruction; 026import static org.jikesrvm.compilers.opt.ir.Operators.BBEND; 027import static org.jikesrvm.compilers.opt.ir.Operators.CHECKCAST; 028import static org.jikesrvm.compilers.opt.ir.Operators.CHECKCAST_NOTNULL; 029import static org.jikesrvm.compilers.opt.ir.Operators.GOTO; 030import static org.jikesrvm.compilers.opt.ir.Operators.NULL_CHECK; 031import static org.jikesrvm.compilers.opt.ir.Operators.REF_IFCMP; 032import static org.jikesrvm.compilers.opt.ir.Operators.REF_MOVE; 033import org.jikesrvm.compilers.opt.ir.Register; 034import org.jikesrvm.compilers.opt.ir.TypeCheck; 035import org.jikesrvm.compilers.opt.ir.operand.NullConstantOperand; 036import 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 */ 053public 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 * @return {@code true} if and only if a type check was moved 142 */ 143 private boolean pushTypeCheckBelowIf(Instruction s, IR ir) { 144 if (s.operator() == CHECKCAST) { 145 Register r = TypeCheck.getRef(s).asRegister().getRegister(); 146 Instruction n = s.nextInstructionInCodeOrder(); 147 /* find moves of the checked value, so that we can also 148 optimize cases where the checked value is moved before 149 it is used 150 */ 151 while (n.operator() == REF_MOVE && 152 Move.getVal(n) instanceof RegisterOperand && 153 Move.getVal(n).asRegister().getRegister() == r) { 154 r = Move.getResult(n).asRegister().getRegister(); 155 n = n.nextInstructionInCodeOrder(); 156 } 157 if (n.operator() == REF_IFCMP && 158 IfCmp.getVal2(n) instanceof NullConstantOperand && 159 IfCmp.getVal1(n) instanceof RegisterOperand && 160 r == IfCmp.getVal1(n).asRegister().getRegister()) { 161 BasicBlock newBlock, patchBlock; 162 BasicBlock myBlock = n.getBasicBlock(); 163 Instruction after = n.nextInstructionInCodeOrder(); 164 if (IfCmp.getCond(n).isEQUAL()) 165 /* We fall through on non-NULL values, so the 166 checkcast must be on the not-taken path 167 from the branch. There are 3 cases: 168 1. n is the last instruction in its basic block, 169 in which case control falls through to the next 170 block in code order. This case is if the 171 instruction after n is a BBEND 172 */ { 173 if (after.operator() == BBEND) { 174 patchBlock = myBlock.nextBasicBlockInCodeOrder(); 175 } else if (after.operator() == GOTO) { 176 /* 2. n is followed by an unconditional goto. In 177 this case control jumps to the target of the 178 goto. 179 */ 180 patchBlock = after.getBranchTarget(); 181 } else if (after.operator() == REF_IFCMP) { 182 /* 3. n is followed by another conditional branch. In 183 this case, we will split the basic block to make 184 n the last instruction in the block, and then 185 we have the fall through case again. 186 */ 187 patchBlock = myBlock.splitNodeAt(n, ir); 188 myBlock.insertOut(patchBlock); 189 ir.cfg.linkInCodeOrder(myBlock, patchBlock); 190 } else { 191 /* this is a bad thing */ 192 return false; 193 } 194 } else 195 /* We branch on not-NULL values, so the checkcast 196 must be spliced in before the branch target 197 */ { 198 patchBlock = n.getBranchTarget(); 199 } 200 /* add block between branch and appropriate successor */ 201 202 newBlock = IRTools.makeBlockOnEdge(myBlock, patchBlock, ir); 203 204 /* put check in new block */ 205 s.remove(); 206 TypeCheck.mutate(s, 207 CHECKCAST_NOTNULL, 208 TypeCheck.getClearResult(s), 209 TypeCheck.getClearRef(s), 210 TypeCheck.getClearType(s), 211 IfCmp.getGuardResult(n).copyRO()); 212 newBlock.prependInstruction(s); 213 return true; 214 } 215 } 216 return false; 217 } 218}