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.ssa;
014
015import static org.jikesrvm.compilers.opt.ir.Operators.BBEND;
016import static org.jikesrvm.compilers.opt.ir.Operators.GOTO;
017import static org.jikesrvm.compilers.opt.ir.Operators.GUARD_MOVE;
018
019import java.util.Enumeration;
020
021import org.jikesrvm.VM;
022import org.jikesrvm.compilers.opt.OptOptions;
023import org.jikesrvm.compilers.opt.controlflow.DominatorTree;
024import org.jikesrvm.compilers.opt.driver.CompilerPhase;
025import org.jikesrvm.compilers.opt.driver.OptimizationPlanAtomicElement;
026import org.jikesrvm.compilers.opt.driver.OptimizationPlanCompositeElement;
027import org.jikesrvm.compilers.opt.driver.OptimizationPlanElement;
028import org.jikesrvm.compilers.opt.ir.BasicBlock;
029import org.jikesrvm.compilers.opt.ir.Goto;
030import org.jikesrvm.compilers.opt.ir.IR;
031import org.jikesrvm.compilers.opt.ir.IfCmp;
032import org.jikesrvm.compilers.opt.ir.InlineGuard;
033import org.jikesrvm.compilers.opt.ir.Instruction;
034import org.jikesrvm.compilers.opt.ir.Move;
035
036/**
037 * Redundant branch elimination based on SSA form, global value numbers,
038 * and dominance relationships.
039 * The following are sufficient conditions for a conditional branch cb1
040 * to be eliminated as redundant
041 * <ul>
042 * <li> It is equivalent (has the same value number) as another
043 *      conditional branch cb2
044 * <li> Either (a) the target of the taken branch of cb2 dominates cb1
045 *      and said target block has exactly one in edge or (b)
046 *      the not-taken continuation of cb2 dominates cb1 and
047 *      said continuation block has exactly one in edge.
048 * </ul>
049 * NOTE: the check for exactly one in edge is used to rule out
050 *       situations like the following:
051 * <pre>
052 *      if (C) goto L2              // cb2
053 *      x = x + 1;
054 *  L2: x = x + 1;
055 *      if (C) goto L3.            // cb1
056 * </pre>
057 * Consider redundant branch elimination for cb1.
058 * Here L2 (the target of cb2) dominates cb1, but it
059 * is not correct to eliminate cb1 because it is also
060 * reachable (but not dominated) from the continuation
061 * block of cb2!
062 */
063public final class RedundantBranchElimination extends OptimizationPlanCompositeElement {
064
065  @Override
066  public boolean shouldPerform(OptOptions options) {
067    return options.SSA_REDUNDANT_BRANCH_ELIMINATION;
068  }
069
070  /**
071   * Create this phase element as a composite of other elements
072   */
073  public RedundantBranchElimination() {
074    super("RedundantBranchElimination", new OptimizationPlanElement[]{
075        // Stage 1: Require SSA form
076        new OptimizationPlanAtomicElement(new EnsureSSA()),
077
078        // Stage2: Require GVNs
079        new OptimizationPlanAtomicElement(new GlobalValueNumber()),
080
081        // Stage3: Do the optimization
082        new OptimizationPlanAtomicElement(new RBE()),});
083  }
084
085  private static final class EnsureSSA extends CompilerPhase {
086
087    @Override
088    public String getName() {
089      return "Ensure SSA";
090    }
091
092    public boolean shouldPerform() {
093      return true;
094    }
095
096    @Override
097    public void perform(IR ir) {
098      ir.desiredSSAOptions = new SSAOptions();
099      new EnterSSA().perform(ir);
100    }
101
102    @Override
103    public CompilerPhase newExecution(IR ir) {
104      return this;
105    }
106  }
107
108  private static final class RBE extends CompilerPhase {
109    private static final boolean DEBUG = false;
110
111    @Override
112    public String getName() {
113      return "RBE Transform";
114    }
115
116    @Override
117    public boolean printingEnabled(OptOptions options, boolean before) {
118      return false && DEBUG;
119    }
120
121    /**
122     * Return this instance of this phase. This phase contains
123     * no per-compilation instance fields.
124     * @param ir not used
125     * @return this
126     */
127    @Override
128    public CompilerPhase newExecution(IR ir) {
129      return this;
130    }
131
132    /**
133     * Transform to eliminate redundant branches passed on
134     * GVNs and dominator information.
135     *
136     * @param ir   The IR on which to apply the phase
137     */
138    @Override
139    public void perform(IR ir) {
140      // (1) Remove redundant conditional branches and locally fix the PHIs
141      GlobalValueNumberState gvns = ir.HIRInfo.valueNumbers;
142      DominatorTree dt = ir.HIRInfo.dominatorTree;
143      for (Enumeration<BasicBlock> bbs = ir.getBasicBlocks(); bbs.hasMoreElements();) {
144        BasicBlock candBB = bbs.nextElement();
145        Instruction candTest = candBB.firstBranchInstruction();
146        if (candTest == null) continue;
147        if (!(IfCmp.conforms(candTest) || InlineGuard.conforms(candTest))) continue;
148        GVCongruenceClass cc = gvns.congruenceClass(candTest);
149        if (cc.size() > 1) {
150          for (ValueGraphVertex vertex : cc) {
151            Instruction poss = (Instruction) vertex.getName();
152            if (poss != candTest) {
153              BasicBlock notTaken = getNotTakenBlock(poss);
154              BasicBlock taken = poss.getBranchTarget();
155              if (taken == notTaken) continue; // both go to same block, so we don't know anything!
156              if (notTaken.hasOneIn() && dt.dominates(notTaken, candBB)) {
157                if (DEBUG) VM.sysWrite(candTest + " is dominated by not-taken branch of " + poss + "\n");
158                removeCondBranch(candBB, candTest, ir, poss);
159                cc.removeVertex(gvns.valueGraph.getVertex(candTest));
160                break;
161              }
162              if (taken.hasOneIn() && dt.dominates(taken, candBB)) {
163                if (DEBUG) VM.sysWrite(candTest + " is dominated by taken branch of " + poss + "\n");
164                takeCondBranch(candBB, candTest, ir);
165                cc.removeVertex(gvns.valueGraph.getVertex(candTest));
166                break;
167              }
168            }
169          }
170        }
171      }
172      // (2) perform a Depth-first search of the control flow graph,
173      //     and remove any nodes we have made unreachable
174      removeUnreachableCode(ir);
175    }
176
177    /**
178     * Remove unreachable code
179     *
180     * @param ir the IR to optimize
181     */
182    private void removeUnreachableCode(IR ir) {
183      boolean removedCode = false;
184      BasicBlock entry = ir.cfg.entry();
185      ir.cfg.clearDFS();
186      entry.sortDFS();
187      for (BasicBlock node = entry; node != null;) {
188        // save it now before removeFromCFGAndCodeOrder nulls it out!!!
189        BasicBlock nextNode = (BasicBlock) node.getNext();
190        if (!node.dfsVisited()) {
191          for (Enumeration<BasicBlock> e = node.getOut(); e.hasMoreElements();) {
192            BasicBlock target = e.nextElement();
193            if (target != node && !target.isExit() && target.dfsVisited()) {
194              SSA.purgeBlockFromPHIs(node, target);
195            }
196          }
197          ir.cfg.removeFromCFGAndCodeOrder(node);
198          removedCode = true;
199        }
200        node = nextNode;
201      }
202      if (removedCode) {
203        ir.cfg.compactNodeNumbering();
204        ir.HIRInfo.dominatorTree = null;
205        ir.HIRInfo.dominatorsAreComputed = false;
206      }
207    }
208
209    /**
210     * @param s an instruction instruction
211     * @return the basic block that s's block will goto if s is not taken.
212     */
213    private BasicBlock getNotTakenBlock(Instruction s) {
214      s = s.nextInstructionInCodeOrder();
215      if (Goto.conforms(s)) return s.getBranchTarget();
216      if (VM.VerifyAssertions) VM._assert(s.operator() == BBEND);
217      return s.getBasicBlock().nextBasicBlockInCodeOrder();
218    }
219
220    /**
221     * Remove cb from source, updating PHI nodes to maintain SSA form.
222     *
223     * @param source basic block containing cb
224     * @param cb conditional branch to remove
225     * @param ir containing IR
226     * @param di branch that dominates cb
227     */
228    private void removeCondBranch(BasicBlock source, Instruction cb, IR ir, Instruction di) {
229      if (DEBUG) VM.sysWrite("Eliminating definitely not-taken branch " + cb + "\n");
230      if (IfCmp.conforms(cb) && IfCmp.hasGuardResult(cb)) {
231        cb.insertBefore(Move.create(GUARD_MOVE, IfCmp.getGuardResult(cb), IfCmp.getGuardResult(di).copy()));
232      }
233      BasicBlock deadBB = cb.getBranchTarget();
234      cb.remove();
235      source.recomputeNormalOut(ir);
236      if (!source.pointsOut(deadBB)) {
237        // there is no longer an edge from source to target;
238        // update any PHIs in target to reflect this.
239        SSA.purgeBlockFromPHIs(source, deadBB);
240      }
241    }
242
243    /**
244     * Transforms a conditional branch into a GOTO, updating PHI nodes
245     *  to maintain SSA form.
246     *
247     * @param source the basic block that contains the branch instruction
248     * @param cb the conditional branch to transform
249     * @param ir the governing IR, in SSA form
250     */
251    private void takeCondBranch(BasicBlock source, Instruction cb, IR ir) {
252      if (DEBUG) VM.sysWrite("Eliminating definitely taken branch " + cb + "\n");
253      BasicBlock deadBB = source.nextBasicBlockInCodeOrder();
254      Instruction next = cb.nextInstructionInCodeOrder();
255      if (Goto.conforms(next)) {
256        deadBB = next.getBranchTarget();
257        next.remove();
258      }
259      Goto.mutate(cb, GOTO, cb.getBranchTarget().makeJumpTarget());
260      source.recomputeNormalOut(ir);
261      if (!source.pointsOut(deadBB)) {
262        // there is no longer an edge from source to target;
263        // update any PHIs in target to reflect this.
264        SSA.purgeBlockFromPHIs(source, deadBB);
265      }
266    }
267  }
268}