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 public Constructor<CompilerPhase> getClassConstructor() {
071 return constructor;
072 }
073
074 public boolean shouldPerform(OptOptions options) {
075 return options.getOptLevel() >= 1;
076 }
077
078 public String getName() { return "Tail Recursion Elimination"; }
079
080 public CompilerPhase newExecution(IR ir) { return this; }
081
082 /**
083 * Perform tail recursion elimination.
084 *
085 * @param ir the IR to optimize
086 */
087 public void perform(IR ir) {
088 BasicBlock target = null;
089 Instruction prologue = null;
090 boolean didSomething = false;
091
092 for (Instruction instr = ir.firstInstructionInCodeOrder(),
093 nextInstr = null; instr != null; instr = nextInstr) {
094 nextInstr = instr.nextInstructionInCodeOrder();
095
096 switch (instr.getOpcode()) {
097 case IR_PROLOGUE_opcode:
098 prologue = instr;
099 break;
100 case SYSCALL_opcode:
101 case CALL_opcode:
102 if (isTailRecursion(instr, ir)) {
103 if (target == null) {
104 target = prologue.getBasicBlock().splitNodeWithLinksAt(prologue, ir);
105 }
106 if (DEBUG) dumpIR(ir, "Before transformation of " + instr);
107 nextInstr = transform(instr, prologue, target, ir);
108 if (DEBUG) dumpIR(ir, "After transformation of " + instr);
109 didSomething = true;
110 }
111 break;
112 default:
113 break;
114 }
115 }
116
117 if (didSomething) {
118 branchOpts.perform(ir, true);
119 if (DEBUG) dumpIR(ir, "After cleanup");
120 if (DEBUG) {
121 VM.sysWrite("Eliminated tail calls in " + ir.method + "\n");
122 }
123 }
124 }
125
126 /**
127 * Is the argument call instruction a tail recursive call?
128 *
129 * @param call the call in question
130 * @param ir the enclosing IR
131 * @return <code>true</code> if call is tail recursive and
132 * <code>false</code> if it is not.
133 */
134 boolean isTailRecursion(Instruction call, IR ir) {
135 if (!Call.hasMethod(call)) return false;
136 MethodOperand methOp = Call.getMethod(call);
137 if (!methOp.hasPreciseTarget()) return false;
138 if (methOp.getTarget() != ir.method) return false;
139 RegisterOperand result = Call.getResult(call);
140 Instruction s = call.nextInstructionInCodeOrder();
141 while (true) {
142 if (s.isMove()) {
143 if (Move.getVal(s).similar(result)) {
144 result = Move.getResult(s);
145 if (DEBUG) VM.sysWrite("Updating result to " + result + "\n");
146 } else {
147 return false; // move of a value that isn't the result blocks us
148 }
149 } else
150 if (s.operator() == LABEL || s.operator() == BBEND || s.operator() == UNINT_BEGIN || s.operator() == UNINT_END) {
151 if (DEBUG) VM.sysWrite("Falling through " + s + "\n");
152 // skip over housekeeping instructions and follow the code order.
153 } else if (s.operator() == GOTO) {
154 // follow the unconditional branch to its target LABEL
155 s = s.getBranchTarget().firstInstruction();
156 if (DEBUG) VM.sysWrite("Following goto to " + s + "\n");
157 } else if (s.isReturn()) {
158 Operand methodResult = Return.getVal(s);
159 if (DEBUG) VM.sysWrite("Found return " + s + "\n");
160 return methodResult == null || methodResult.similar(result);
161 } else {
162 // any other instruction blocks us
163 return false;
164 }
165 s = s.nextInstructionInCodeOrder();
166 }
167 }
168
169 /**
170 * Transform the tail recursive call into a loop.
171 *
172 * @param call The recursive call
173 * @param prologue The IR_Prologue instruction
174 * @param target The loop head
175 * @param ir the containing IR
176 */
177 Instruction transform(Instruction call, Instruction prologue, BasicBlock target, IR ir) {
178 // (1) insert move instructions to assign fresh temporaries
179 // the actuals of the call.
180 int numParams = Call.getNumberOfParams(call);
181 RegisterOperand[] temps = new RegisterOperand[numParams];
182 for (int i = 0; i < numParams; i++) {
183 Operand actual = Call.getClearParam(call, i);
184 temps[i] = ir.regpool.makeTemp(actual);
185 Instruction move = Move.create(IRTools.getMoveOp(temps[i].getType()), temps[i], actual);
186 move.copyPosition(call);
187 call.insertBefore(move);
188 }
189
190 // (2) insert move instructions to assign the formal parameters
191 // the corresponding fresh temporary
192 for (int i = 0; i < numParams; i++) {
193 RegisterOperand formal = Prologue.getFormal(prologue, i).copyD2D();
194 Instruction move = Move.create(IRTools.getMoveOp(formal.getType()), formal, temps[i].copyD2U());
195 move.copyPosition(call);
196 call.insertBefore(move);
197 }
198
199 // (3) Blow away all instructions below the call in the basic block
200 // (should only be moves and other housekeeping instructions
201 // skipped over in isTailRecursion loop above)
202 BasicBlock myBlock = call.getBasicBlock();
203 Instruction dead = myBlock.lastRealInstruction();
204 while (dead != call) {
205 dead = dead.remove();
206 }
207
208 // (4) Insert a goto to jump from the call to the loop head
209 Instruction gotoInstr = Goto.create(GOTO, target.makeJumpTarget());
210 gotoInstr.copyPosition(call);
211 call.insertAfter(gotoInstr);
212
213 // (5) Remove the call instruction
214 call.remove();
215
216 // (6) Update the CFG
217 myBlock.deleteNormalOut();
218 myBlock.insertOut(target);
219
220 return myBlock.lastInstruction();
221 }
222 }