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 java.util.Enumeration;
020
021 import org.jikesrvm.VM;
022 import org.jikesrvm.compilers.opt.OptOptions;
023 import org.jikesrvm.compilers.opt.controlflow.DominatorTree;
024 import org.jikesrvm.compilers.opt.driver.CompilerPhase;
025 import org.jikesrvm.compilers.opt.driver.OptimizationPlanAtomicElement;
026 import org.jikesrvm.compilers.opt.driver.OptimizationPlanCompositeElement;
027 import org.jikesrvm.compilers.opt.driver.OptimizationPlanElement;
028 import org.jikesrvm.compilers.opt.ir.BasicBlock;
029 import org.jikesrvm.compilers.opt.ir.Goto;
030 import org.jikesrvm.compilers.opt.ir.IR;
031 import org.jikesrvm.compilers.opt.ir.IfCmp;
032 import org.jikesrvm.compilers.opt.ir.InlineGuard;
033 import org.jikesrvm.compilers.opt.ir.Instruction;
034 import 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 */
063 public 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() { return "RBE Transform"; }
113
114 @Override
115 public boolean printingEnabled(OptOptions options, boolean before) {
116 return false && DEBUG;
117 }
118
119 /**
120 * Return this instance of this phase. This phase contains
121 * no per-compilation instance fields.
122 * @param ir not used
123 * @return this
124 */
125 @Override
126 public CompilerPhase newExecution(IR ir) {
127 return this;
128 }
129
130 /**
131 * Transform to eliminate redundant branches passed on
132 * GVNs and dominator information.
133 *
134 * @param ir The IR on which to apply the phase
135 */
136 @Override
137 public void perform(IR ir) {
138 // (1) Remove redundant conditional branches and locally fix the PHIs
139 GlobalValueNumberState gvns = ir.HIRInfo.valueNumbers;
140 DominatorTree dt = ir.HIRInfo.dominatorTree;
141 for (Enumeration<BasicBlock> bbs = ir.getBasicBlocks(); bbs.hasMoreElements();) {
142 BasicBlock candBB = bbs.nextElement();
143 Instruction candTest = candBB.firstBranchInstruction();
144 if (candTest == null) continue;
145 if (!(IfCmp.conforms(candTest) || InlineGuard.conforms(candTest))) continue;
146 GVCongruenceClass cc = gvns.congruenceClass(candTest);
147 if (cc.size() > 1) {
148 for (ValueGraphVertex vertex : cc) {
149 Instruction poss = (Instruction) vertex.getName();
150 if (poss != candTest) {
151 BasicBlock notTaken = getNotTakenBlock(poss);
152 BasicBlock taken = poss.getBranchTarget();
153 if (taken == notTaken) continue; // both go to same block, so we don't know anything!
154 if (notTaken.hasOneIn() && dt.dominates(notTaken, candBB)) {
155 if (DEBUG) VM.sysWrite(candTest + " is dominated by not-taken branch of " + poss + "\n");
156 removeCondBranch(candBB, candTest, ir, poss);
157 cc.removeVertex(gvns.valueGraph.getVertex(candTest));
158 break;
159 }
160 if (taken.hasOneIn() && dt.dominates(taken, candBB)) {
161 if (DEBUG) VM.sysWrite(candTest + " is dominated by taken branch of " + poss + "\n");
162 takeCondBranch(candBB, candTest, ir);
163 cc.removeVertex(gvns.valueGraph.getVertex(candTest));
164 break;
165 }
166 }
167 }
168 }
169 }
170 // (2) perform a Depth-first search of the control flow graph,
171 // and remove any nodes we have made unreachable
172 removeUnreachableCode(ir);
173 }
174
175 /**
176 * Remove unreachable code
177 *
178 * @param ir the IR to optimize
179 */
180 private void removeUnreachableCode(IR ir) {
181 boolean removedCode = false;
182 BasicBlock entry = ir.cfg.entry();
183 ir.cfg.clearDFS();
184 entry.sortDFS();
185 for (BasicBlock node = entry; node != null;) {
186 // save it now before removeFromCFGAndCodeOrder nulls it out!!!
187 BasicBlock nextNode = (BasicBlock) node.getNext();
188 if (!node.dfsVisited()) {
189 for (Enumeration<BasicBlock> e = node.getOut(); e.hasMoreElements();) {
190 BasicBlock target = e.nextElement();
191 if (target != node && !target.isExit() && target.dfsVisited()) {
192 SSA.purgeBlockFromPHIs(node, target);
193 }
194 }
195 ir.cfg.removeFromCFGAndCodeOrder(node);
196 removedCode = true;
197 }
198 node = nextNode;
199 }
200 if (removedCode) {
201 ir.cfg.compactNodeNumbering();
202 ir.HIRInfo.dominatorTree = null;
203 ir.HIRInfo.dominatorsAreComputed = false;
204 }
205 }
206
207 /**
208 * Return the basic block that s's block will goto if s is not taken.
209 */
210 private BasicBlock getNotTakenBlock(Instruction s) {
211 s = s.nextInstructionInCodeOrder();
212 if (Goto.conforms(s)) return s.getBranchTarget();
213 if (VM.VerifyAssertions) VM._assert(s.operator() == BBEND);
214 return s.getBasicBlock().nextBasicBlockInCodeOrder();
215 }
216
217 /**
218 * Remove cb from source, updating PHI nodes to maintain SSA form.
219 *
220 * @param source basic block containing cb
221 * @param cb conditional branch to remove
222 * @param ir containing IR
223 * @param di branch that dominates cb
224 */
225 private void removeCondBranch(BasicBlock source, Instruction cb, IR ir, Instruction di) {
226 if (DEBUG) VM.sysWrite("Eliminating definitely not-taken branch " + cb + "\n");
227 if (IfCmp.conforms(cb) && IfCmp.hasGuardResult(cb)) {
228 cb.insertBefore(Move.create(GUARD_MOVE, IfCmp.getGuardResult(cb), IfCmp.getGuardResult(di).copy()));
229 }
230 BasicBlock deadBB = cb.getBranchTarget();
231 cb.remove();
232 source.recomputeNormalOut(ir);
233 if (!source.pointsOut(deadBB)) {
234 // there is no longer an edge from source to target;
235 // update any PHIs in target to reflect this.
236 SSA.purgeBlockFromPHIs(source, deadBB);
237 }
238 }
239
240 /**
241 * Transform cb into a GOTO, updating PHI nodes to maintain SSA form.
242 */
243 private void takeCondBranch(BasicBlock source, Instruction cb, IR ir) {
244 if (DEBUG) VM.sysWrite("Eliminating definitely taken branch " + cb + "\n");
245 BasicBlock deadBB = source.nextBasicBlockInCodeOrder();
246 Instruction next = cb.nextInstructionInCodeOrder();
247 if (Goto.conforms(next)) {
248 deadBB = next.getBranchTarget();
249 next.remove();
250 }
251 Goto.mutate(cb, GOTO, cb.getBranchTarget().makeJumpTarget());
252 source.recomputeNormalOut(ir);
253 if (!source.pointsOut(deadBB)) {
254 // there is no longer an edge from source to target;
255 // update any PHIs in target to reflect this.
256 SSA.purgeBlockFromPHIs(source, deadBB);
257 }
258 }
259 }
260 }