Source code

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;
016
017import org.jikesrvm.VM;
018import org.jikesrvm.compilers.opt.ir.BasicBlock;
019import org.jikesrvm.compilers.opt.ir.IR;
020import org.jikesrvm.compilers.opt.ir.Instruction;
021import org.jikesrvm.compilers.opt.ir.operand.BranchOperand;
022
023/**
024 * Perform simple peephole optimizations for MIR branches.
025 */
026public final class MIRBranchOptimizations extends BranchOptimizationDriver {
027
028  /**
029   * @param level the minimum optimization level at which the branch
030   * optimizations should be performed.
031   */
032  public MIRBranchOptimizations(int level) {
033    super(level);
034  }
035
036  private static boolean isMIR_Branch(Instruction x) {
037    if (VM.BuildForIA32) {
038      return org.jikesrvm.compilers.opt.ir.ia32.MIR_Branch.conforms(x);
039    } else {
040      if (VM.VerifyAssertions) VM._assert(VM.BuildForPowerPC);
041      return org.jikesrvm.compilers.opt.ir.ppc.MIR_Branch.conforms(x);
042    }
043  }
044
045  private static boolean isMIR_CondBranch(Instruction x) {
046    if (VM.BuildForIA32) {
047      return org.jikesrvm.compilers.opt.ir.ia32.MIR_CondBranch.conforms(x);
048    } else {
049      if (VM.VerifyAssertions) VM._assert(VM.BuildForPowerPC);
050      return org.jikesrvm.compilers.opt.ir.ppc.MIR_CondBranch.conforms(x);
051    }
052  }
053
054  private static boolean isMIR_CondBranch2(Instruction x) {
055    if (VM.BuildForIA32) {
056      return org.jikesrvm.compilers.opt.ir.ia32.MIR_CondBranch2.conforms(x);
057    } else {
058      if (VM.VerifyAssertions) VM._assert(VM.BuildForPowerPC);
059      return org.jikesrvm.compilers.opt.ir.ppc.MIR_CondBranch2.conforms(x);
060    }
061  }
062
063  private static BranchOperand MIR_Branch_getTarget(Instruction x) {
064    if (VM.BuildForIA32) {
065      return org.jikesrvm.compilers.opt.ir.ia32.MIR_Branch.getTarget(x);
066    } else {
067      if (VM.VerifyAssertions) VM._assert(VM.BuildForPowerPC);
068      return org.jikesrvm.compilers.opt.ir.ppc.MIR_Branch.getTarget(x);
069    }
070  }
071
072  private static void MIR_Branch_setTarget(Instruction x, BranchOperand y) {
073    if (VM.BuildForIA32) {
074      org.jikesrvm.compilers.opt.ir.ia32.MIR_Branch.setTarget(x, y);
075    } else {
076      if (VM.VerifyAssertions) VM._assert(VM.BuildForPowerPC);
077      org.jikesrvm.compilers.opt.ir.ppc.MIR_Branch.setTarget(x, y);
078    }
079  }
080
081  private static void MIR_CondBranch_setTarget(Instruction x, BranchOperand y) {
082    if (VM.BuildForIA32) {
083      org.jikesrvm.compilers.opt.ir.ia32.MIR_CondBranch.setTarget(x, y);
084    } else {
085      if (VM.VerifyAssertions) VM._assert(VM.BuildForPowerPC);
086      org.jikesrvm.compilers.opt.ir.ppc.MIR_CondBranch.setTarget(x, y);
087    }
088  }
089
090  private static BranchOperand MIR_CondBranch2_getTarget1(Instruction x) {
091    if (VM.BuildForIA32) {
092      return org.jikesrvm.compilers.opt.ir.ia32.MIR_CondBranch2.getTarget1(x);
093    } else {
094      if (VM.VerifyAssertions) VM._assert(VM.BuildForPowerPC);
095      return org.jikesrvm.compilers.opt.ir.ppc.MIR_CondBranch2.getTarget1(x);
096    }
097  }
098
099  private static BranchOperand MIR_CondBranch2_getTarget2(Instruction x) {
100    if (VM.BuildForIA32) {
101      return org.jikesrvm.compilers.opt.ir.ia32.MIR_CondBranch2.getTarget2(x);
102    } else {
103      if (VM.VerifyAssertions) VM._assert(VM.BuildForPowerPC);
104      return org.jikesrvm.compilers.opt.ir.ppc.MIR_CondBranch2.getTarget2(x);
105    }
106  }
107
108  private static void MIR_CondBranch2_setTarget1(Instruction x, BranchOperand y) {
109    if (VM.BuildForIA32) {
110      org.jikesrvm.compilers.opt.ir.ia32.MIR_CondBranch2.setTarget1(x, y);
111    } else {
112      if (VM.VerifyAssertions) VM._assert(VM.BuildForPowerPC);
113      org.jikesrvm.compilers.opt.ir.ppc.MIR_CondBranch2.setTarget1(x, y);
114    }
115  }
116
117  private static void MIR_CondBranch2_setTarget2(Instruction x, BranchOperand y) {
118    if (VM.BuildForIA32) {
119      org.jikesrvm.compilers.opt.ir.ia32.MIR_CondBranch2.setTarget2(x, y);
120    } else {
121      if (VM.VerifyAssertions) VM._assert(VM.BuildForPowerPC);
122      org.jikesrvm.compilers.opt.ir.ppc.MIR_CondBranch2.setTarget2(x, y);
123    }
124  }
125
126  /**
127   * This method actually does the work of attempting to
128   * peephole optimize a branch instruction.
129   * See Muchnick ~p.590
130   * @param ir the containing IR
131   * @param s the branch instruction to optimize
132   * @param bb the containing basic block
133   * @return {@code true} if an optimization was applied, {@code false} otherwise
134   */
135  @Override
136  protected boolean optimizeBranchInstruction(IR ir, Instruction s, BasicBlock bb) {
137    if (isMIR_Branch(s)) {
138      return processGoto(ir, s, bb);
139    } else if (isMIR_CondBranch(s)) {
140      return processCondBranch(ir, s, bb);
141    } else if (isMIR_CondBranch2(s)) {
142      return processTwoTargetConditionalBranch(ir, s, bb);
143    } else {
144      return false;
145    }
146  }
147
148  /**
149   * Perform optimizations for an unconditonal branch.
150   *
151   * <p> Patterns:
152   * <pre>
153   *    1)      GOTO A       replaced by  GOTO B
154   *         A: GOTO B
155   *
156   *    2)   GOTO next instruction eliminated
157   *    3)      GOTO A       replaced by  GOTO B
158   *         A: LABEL
159   *            BBEND
160   *         B:
161   * </pre>
162   *
163   * <p> Precondition: MIR_Branch.conforms(g)
164   *
165   * @param ir governing IR
166   * @param g the instruction to optimize
167   * @param bb the basic block holding g
168   * @return {@code true} if made a transformation
169   */
170  private boolean processGoto(IR ir, Instruction g, BasicBlock bb) {
171    BasicBlock targetBlock = g.getBranchTarget();
172    Instruction targetLabel = targetBlock.firstInstruction();
173    // get the first real instruction at the g target
174    // NOTE: this instruction is not necessarily in targetBlock,
175    // iff targetBlock has no real instructions
176    Instruction targetInst = firstRealInstructionFollowing(targetLabel);
177    if (targetInst == null || targetInst == g) {
178      return false;
179    }
180    Instruction nextLabel = firstLabelFollowing(g);
181    if (targetLabel == nextLabel) {
182      // found a GOTO to the next instruction.  just remove it.
183      g.remove();
184      return true;
185    }
186    if (isMIR_Branch(targetInst)) {
187      // unconditional branch to unconditional branch.
188      // replace g with goto to targetInst's target
189      Instruction target2 = firstRealInstructionFollowing(targetInst.getBranchTarget().firstInstruction());
190      if (target2 == targetInst) {
191        // Avoid an infinite recursion in the following bizarre scenario:
192        // g: goto L
193        // ...
194        // L: goto L
195        // This happens in jByteMark.EmFloatPnt.denormalize() due to a while(true) {}
196        return false;
197      }
198      BranchOperand top = (BranchOperand)(MIR_Branch_getTarget(targetInst).copy());
199      MIR_Branch_setTarget(g, top);
200      bb.recomputeNormalOut(ir); // fix the CFG
201      return true;
202    }
203    if (targetBlock.isEmpty()) {
204      // GOTO an empty block.  Change target to the next block.
205      BasicBlock nextBlock = targetBlock.getFallThroughBlock();
206      MIR_Branch_setTarget(g, nextBlock.makeJumpTarget());
207      bb.recomputeNormalOut(ir); // fix the CFG
208      return true;
209    }
210    return false;
211  }
212
213  /**
214   * Perform optimizations for a conditional branch.
215   *
216   * <pre>
217   * 1)   IF .. GOTO A          replaced by  IF .. GOTO B
218   *      ...
219   *   A: GOTO B
220   * 2)   conditional branch to next instruction eliminated
221   * 3)   IF (condition) GOTO A  replaced by  IF (!condition) GOTO B
222   *      GOTO B                           A: ...
223   *   A: ...
224   * 4)   IF .. GOTO A       replaced by  IF .. GOTO B
225   *   A: LABEL
226   *      BBEND
227   *   B:
228   * 5)  fallthrough to a goto: replicate goto to enable other optimizations.
229   * </pre>
230   *
231   * <p> Precondition: MIR_CondBranch.conforms(cb)
232   *
233   * @param ir the governing IR
234   * @param cb the instruction to optimize
235   * @param bb the basic block holding if
236   * @return {@code true} iff made a transformation
237   */
238  private boolean processCondBranch(IR ir, Instruction cb, BasicBlock bb) {
239    BasicBlock targetBlock = cb.getBranchTarget();
240    Instruction targetLabel = targetBlock.firstInstruction();
241    // get the first real instruction at the branch target
242    // NOTE: this instruction is not necessarily in targetBlock,
243    // iff targetBlock has no real instructions
244    Instruction targetInst = firstRealInstructionFollowing(targetLabel);
245    if (targetInst == null || targetInst == cb) {
246      return false;
247    }
248    boolean endsBlock = cb.nextInstructionInCodeOrder().operator() == BBEND;
249    if (endsBlock) {
250      Instruction nextLabel = firstLabelFollowing(cb);
251      if (targetLabel == nextLabel) {
252        // found a conditional branch to the next instruction.  just remove it.
253        cb.remove();
254        return true;
255      }
256      Instruction nextI = firstRealInstructionFollowing(nextLabel);
257      if (nextI != null && isMIR_Branch(nextI)) {
258        // replicate Goto
259        cb.insertAfter(nextI.copyWithoutLinks());
260        bb.recomputeNormalOut(ir); // fix the CFG
261        return true;
262      }
263    }
264    if (isMIR_Branch(targetInst)) {
265      // conditional branch to unconditional branch.
266      // change conditional branch target to latter's target
267      Instruction target2 = firstRealInstructionFollowing(targetInst.getBranchTarget().firstInstruction());
268      if (target2 == targetInst) {
269        // Avoid an infinite recursion in the following scenario:
270        // g: if (...) goto L
271        // ...
272        // L: goto L
273        // This happens in GCUtil in some systems due to a while(true) {}
274        return false;
275      }
276      MIR_CondBranch_setTarget(cb, (BranchOperand)MIR_Branch_getTarget(targetInst).copy());
277      bb.recomputeNormalOut(ir); // fix the CFG
278      return true;
279    }
280    if (targetBlock.isEmpty()) {
281      // branch to an empty block.  Change target to the next block.
282      BasicBlock nextBlock = targetBlock.getFallThroughBlock();
283      BranchOperand newTarget = nextBlock.makeJumpTarget();
284      MIR_CondBranch_setTarget(cb, newTarget);
285      bb.recomputeNormalOut(ir); // fix the CFG
286      return true;
287    }
288    if (isFlipCandidate(cb, targetInst)) {
289      flipConditionalBranch(cb);
290      bb.recomputeNormalOut(ir); // fix the CFG
291      return true;
292    }
293    return false;
294  }
295
296  /**
297   * Perform optimizations for a two way conditional branch.
298   *
299   * <pre>
300   * 1)   IF .. GOTO A          replaced by  IF .. GOTO B
301   *      ...
302   *   A: GOTO B
303   * 2)   conditional branch to next instruction eliminated
304   * 3)   IF .. GOTO A       replaced by  IF .. GOTO B
305   *   A: LABEL
306   *      BBEND
307   *   B:
308   * 4)  fallthrough to a goto: replicate goto to enable other optimizations.
309   * </pre>
310   *
311   * <p> Precondition: MIR_CondBranch2.conforms(cb)
312   *
313   * @param ir the governing IR
314   * @param cb the instruction to optimize
315   * @param bb the basic block holding if
316   * @return {@code true} iff made a transformation
317   */
318  private boolean processTwoTargetConditionalBranch(IR ir, Instruction cb, BasicBlock bb) {
319    // First condition/target
320    Instruction target1Label = MIR_CondBranch2_getTarget1(cb).target;
321    Instruction target1Inst = firstRealInstructionFollowing(target1Label);
322    Instruction nextLabel = firstLabelFollowing(cb);
323    boolean endsBlock = cb.nextInstructionInCodeOrder().operator() == BBEND;
324    if (target1Inst != null && target1Inst != cb) {
325      if (isMIR_Branch(target1Inst)) {
326        // conditional branch to unconditional branch.
327        // change conditional branch target to latter's target
328        MIR_CondBranch2_setTarget1(cb, MIR_Branch_getTarget(target1Inst));
329        bb.recomputeNormalOut(ir); // fix CFG
330        return true;
331      }
332      BasicBlock target1Block = target1Label.getBasicBlock();
333      if (target1Block.isEmpty()) {
334        // branch to an empty block.  Change target to the next block.
335        BasicBlock nextBlock = target1Block.getFallThroughBlock();
336        MIR_CondBranch2_setTarget1(cb, nextBlock.makeJumpTarget());
337        bb.recomputeNormalOut(ir); // fix the CFG
338        return true;
339      }
340    }
341
342    // Second condition/target
343    Instruction target2Label = MIR_CondBranch2_getTarget2(cb).target;
344    Instruction target2Inst = firstRealInstructionFollowing(target2Label);
345    if (target2Inst != null && target2Inst != cb) {
346      if (isMIR_Branch(target2Inst)) {
347        // conditional branch to unconditional branch.
348        // change conditional branch target to latter's target
349        MIR_CondBranch2_setTarget2(cb, MIR_Branch_getTarget(target2Inst));
350        bb.recomputeNormalOut(ir); // fix CFG
351        return true;
352      }
353      if ((target2Label == nextLabel) && endsBlock) {
354        // found a conditional branch to the next instruction.
355        // Reduce to MIR_BranchCond
356        if (VM.BuildForIA32) {
357          org.jikesrvm.compilers.opt.ir.ia32.MIR_CondBranch.mutate(cb,
358              org.jikesrvm.compilers.opt.ir.ia32.ArchOperators.IA32_JCC,
359              org.jikesrvm.compilers.opt.ir.ia32.MIR_CondBranch2.getCond1(cb),
360              org.jikesrvm.compilers.opt.ir.ia32.MIR_CondBranch2.getTarget1(cb),
361              org.jikesrvm.compilers.opt.ir.ia32.MIR_CondBranch2.getBranchProfile1(cb));
362        } else {
363          if (VM.VerifyAssertions) VM._assert(VM.BuildForPowerPC);
364          org.jikesrvm.compilers.opt.ir.ppc.MIR_CondBranch.mutate(cb,
365              org.jikesrvm.compilers.opt.ir.ppc.ArchOperators.PPC_BCOND,
366              org.jikesrvm.compilers.opt.ir.ppc.MIR_CondBranch2.getValue(cb),
367              org.jikesrvm.compilers.opt.ir.ppc.MIR_CondBranch2.getCond1(cb),
368              org.jikesrvm.compilers.opt.ir.ppc.MIR_CondBranch2.getTarget1(cb),
369              org.jikesrvm.compilers.opt.ir.ppc.MIR_CondBranch2.getBranchProfile1(cb));
370        }
371        return true;
372      }
373      BasicBlock target2Block = target2Label.getBasicBlock();
374      if (target2Block.isEmpty()) {
375        // branch to an empty block.  Change target to the next block.
376        BasicBlock nextBlock = target2Block.getFallThroughBlock();
377        MIR_CondBranch2_setTarget2(cb, nextBlock.makeJumpTarget());
378        bb.recomputeNormalOut(ir); // fix the CFG
379        return true;
380      }
381    }
382
383    // if fall through to a goto; replicate the goto
384    if (endsBlock) {
385      Instruction nextI = firstRealInstructionFollowing(nextLabel);
386      if (nextI != null && isMIR_Branch(nextI)) {
387        // replicate unconditional branch
388        cb.insertAfter(nextI.copyWithoutLinks());
389        bb.recomputeNormalOut(ir); // fix the CFG
390        return true;
391      }
392    }
393
394    return false;
395  }
396
397  /**
398   * Is a conditional branch a candidate to be flipped?
399   * See comment 3) of processCondBranch
400   *
401   * <p> Precondition: MIR_CondBranch.conforms(cb)
402   *
403   * @param cb the conditional branch instruction
404   * @param target the target instruction (real instruction) of the conditional
405   *               branch
406   * @return boolean result
407   */
408  private boolean isFlipCandidate(Instruction cb, Instruction target) {
409    // condition 1: is next instruction a GOTO?
410    Instruction next = cb.nextInstructionInCodeOrder();
411    if (!isMIR_Branch(next)) {
412      return false;
413    }
414    // condition 2: is the target of the conditional branch the
415    //  next instruction after the GOTO?
416    next = firstRealInstructionFollowing(next);
417    if (next != target) {
418      return false;
419    }
420    // got this far.  It's a candidate.
421    return true;
422  }
423
424  /**
425   * Flip a conditional branch and remove the trailing goto.
426   * See comment 3) of processCondBranch
427   *
428   * <p> Precondition isFlipCandidate(cb)
429   * @param cb the conditional branch instruction
430   */
431  private void flipConditionalBranch(Instruction cb) {
432    // get the trailing GOTO instruction
433    Instruction g = cb.nextInstructionInCodeOrder();
434    BranchOperand gTarget = MIR_Branch_getTarget(g);
435    // now flip the test and set the new target
436    if (VM.BuildForIA32) {
437      org.jikesrvm.compilers.opt.ir.ia32.MIR_CondBranch.setCond(cb,
438          org.jikesrvm.compilers.opt.ir.ia32.MIR_CondBranch.getCond(cb).flipCode());
439    } else {
440      if (VM.VerifyAssertions) VM._assert(VM.BuildForPowerPC);
441      org.jikesrvm.compilers.opt.ir.ppc.MIR_CondBranch.setCond(cb,
442          org.jikesrvm.compilers.opt.ir.ppc.MIR_CondBranch.getCond(cb).flipCode());
443    }
444    MIR_CondBranch_setTarget(cb, gTarget);
445    // Remove the trailing GOTO instruction
446    g.remove();
447  }
448}