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.controlflow; 014 015 import static org.jikesrvm.compilers.opt.ir.Operators.BBEND; 016 import static org.jikesrvm.compilers.opt.ir.Operators.CALL_opcode; 017 import static org.jikesrvm.compilers.opt.ir.Operators.GOTO; 018 import static org.jikesrvm.compilers.opt.ir.Operators.IR_PROLOGUE_opcode; 019 import static org.jikesrvm.compilers.opt.ir.Operators.LABEL; 020 import static org.jikesrvm.compilers.opt.ir.Operators.SYSCALL_opcode; 021 import static org.jikesrvm.compilers.opt.ir.Operators.UNINT_BEGIN; 022 import static org.jikesrvm.compilers.opt.ir.Operators.UNINT_END; 023 024 import java.lang.reflect.Constructor; 025 026 import org.jikesrvm.VM; 027 import org.jikesrvm.compilers.opt.OptOptions; 028 import org.jikesrvm.compilers.opt.driver.CompilerPhase; 029 import org.jikesrvm.compilers.opt.ir.BasicBlock; 030 import org.jikesrvm.compilers.opt.ir.Call; 031 import org.jikesrvm.compilers.opt.ir.Goto; 032 import org.jikesrvm.compilers.opt.ir.IR; 033 import org.jikesrvm.compilers.opt.ir.IRTools; 034 import org.jikesrvm.compilers.opt.ir.Instruction; 035 import org.jikesrvm.compilers.opt.ir.Move; 036 import org.jikesrvm.compilers.opt.ir.Prologue; 037 import org.jikesrvm.compilers.opt.ir.Return; 038 import org.jikesrvm.compilers.opt.ir.operand.MethodOperand; 039 import org.jikesrvm.compilers.opt.ir.operand.Operand; 040 import org.jikesrvm.compilers.opt.ir.operand.RegisterOperand; 041 042 /** 043 * Transform tail recursive calls into loops. 044 * <p> 045 * NOTES: 046 * <ul> 047 * <li> This pass does not attempt to optimize all tail calls, just those 048 * that are directly recursive. 049 * <li> Even the small optimization we are doing here destroys the ability 050 * to accurately support stack frame inspection. 051 * <li> This phase assumes that is run before Yieldpoints and thus 052 * does not need to insert a yieldpoint in the newly created loop header. 053 * </ul> 054 */ 055 public final class TailRecursionElimination extends CompilerPhase { 056 057 private static final boolean DEBUG = false; 058 private final BranchOptimizations branchOpts = new BranchOptimizations(-1, true, false); 059 060 /** 061 * Constructor for this compiler phase 062 */ 063 private static final Constructor<CompilerPhase> constructor = 064 getCompilerPhaseConstructor(TailRecursionElimination.class); 065 066 /** 067 * Get a constructor object for this compiler phase 068 * @return compiler phase constructor 069 */ 070 @Override 071 public Constructor<CompilerPhase> getClassConstructor() { 072 return constructor; 073 } 074 075 @Override 076 public boolean shouldPerform(OptOptions options) { 077 return options.getOptLevel() >= 1; 078 } 079 080 @Override 081 public String getName() { return "Tail Recursion Elimination"; } 082 083 @Override 084 public CompilerPhase newExecution(IR ir) { return this; } 085 086 /** 087 * Perform tail recursion elimination. 088 * 089 * @param ir the IR to optimize 090 */ 091 @Override 092 public void perform(IR ir) { 093 BasicBlock target = null; 094 Instruction prologue = null; 095 boolean didSomething = false; 096 097 for (Instruction instr = ir.firstInstructionInCodeOrder(), 098 nextInstr = null; instr != null; instr = nextInstr) { 099 nextInstr = instr.nextInstructionInCodeOrder(); 100 101 switch (instr.getOpcode()) { 102 case IR_PROLOGUE_opcode: 103 prologue = instr; 104 break; 105 case SYSCALL_opcode: 106 case CALL_opcode: 107 if (isTailRecursion(instr, ir)) { 108 if (target == null) { 109 target = prologue.getBasicBlock().splitNodeWithLinksAt(prologue, ir); 110 } 111 if (DEBUG) dumpIR(ir, "Before transformation of " + instr); 112 nextInstr = transform(instr, prologue, target, ir); 113 if (DEBUG) dumpIR(ir, "After transformation of " + instr); 114 didSomething = true; 115 } 116 break; 117 default: 118 break; 119 } 120 } 121 122 if (didSomething) { 123 branchOpts.perform(ir, true); 124 if (DEBUG) dumpIR(ir, "After cleanup"); 125 if (DEBUG) { 126 VM.sysWrite("Eliminated tail calls in " + ir.method + "\n"); 127 } 128 } 129 } 130 131 /** 132 * Is the argument call instruction a tail recursive call? 133 * 134 * @param call the call in question 135 * @param ir the enclosing IR 136 * @return <code>true</code> if call is tail recursive and 137 * <code>false</code> if it is not. 138 */ 139 boolean isTailRecursion(Instruction call, IR ir) { 140 if (!Call.hasMethod(call)) return false; 141 MethodOperand methOp = Call.getMethod(call); 142 if (!methOp.hasPreciseTarget()) return false; 143 if (methOp.getTarget() != ir.method) return false; 144 RegisterOperand result = Call.getResult(call); 145 Instruction s = call.nextInstructionInCodeOrder(); 146 while (true) { 147 if (s.isMove()) { 148 if (Move.getVal(s).similar(result)) { 149 result = Move.getResult(s); 150 if (DEBUG) VM.sysWrite("Updating result to " + result + "\n"); 151 } else { 152 return false; // move of a value that isn't the result blocks us 153 } 154 } else 155 if (s.operator() == LABEL || s.operator() == BBEND || s.operator() == UNINT_BEGIN || s.operator() == UNINT_END) { 156 if (DEBUG) VM.sysWrite("Falling through " + s + "\n"); 157 // skip over housekeeping instructions and follow the code order. 158 } else if (s.operator() == GOTO) { 159 // follow the unconditional branch to its target LABEL 160 s = s.getBranchTarget().firstInstruction(); 161 if (DEBUG) VM.sysWrite("Following goto to " + s + "\n"); 162 } else if (s.isReturn()) { 163 Operand methodResult = Return.getVal(s); 164 if (DEBUG) VM.sysWrite("Found return " + s + "\n"); 165 return methodResult == null || methodResult.similar(result); 166 } else { 167 // any other instruction blocks us 168 return false; 169 } 170 s = s.nextInstructionInCodeOrder(); 171 } 172 } 173 174 /** 175 * Transform the tail recursive call into a loop. 176 * 177 * @param call The recursive call 178 * @param prologue The IR_Prologue instruction 179 * @param target The loop head 180 * @param ir the containing IR 181 */ 182 Instruction transform(Instruction call, Instruction prologue, BasicBlock target, IR ir) { 183 // (1) insert move instructions to assign fresh temporaries 184 // the actuals of the call. 185 int numParams = Call.getNumberOfParams(call); 186 RegisterOperand[] temps = new RegisterOperand[numParams]; 187 for (int i = 0; i < numParams; i++) { 188 Operand actual = Call.getClearParam(call, i); 189 temps[i] = ir.regpool.makeTemp(actual); 190 Instruction move = Move.create(IRTools.getMoveOp(temps[i].getType()), temps[i], actual); 191 move.copyPosition(call); 192 call.insertBefore(move); 193 } 194 195 // (2) insert move instructions to assign the formal parameters 196 // the corresponding fresh temporary 197 for (int i = 0; i < numParams; i++) { 198 RegisterOperand formal = Prologue.getFormal(prologue, i).copyD2D(); 199 Instruction move = Move.create(IRTools.getMoveOp(formal.getType()), formal, temps[i].copyD2U()); 200 move.copyPosition(call); 201 call.insertBefore(move); 202 } 203 204 // (3) Blow away all instructions below the call in the basic block 205 // (should only be moves and other housekeeping instructions 206 // skipped over in isTailRecursion loop above) 207 BasicBlock myBlock = call.getBasicBlock(); 208 Instruction dead = myBlock.lastRealInstruction(); 209 while (dead != call) { 210 dead = dead.remove(); 211 } 212 213 // (4) Insert a goto to jump from the call to the loop head 214 Instruction gotoInstr = Goto.create(GOTO, target.makeJumpTarget()); 215 gotoInstr.copyPosition(call); 216 call.insertAfter(gotoInstr); 217 218 // (5) Remove the call instruction 219 call.remove(); 220 221 // (6) Update the CFG 222 myBlock.deleteNormalOut(); 223 myBlock.insertOut(target); 224 225 return myBlock.lastInstruction(); 226 } 227 }