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    }