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