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