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.LABEL;
017
018 import java.util.Enumeration;
019
020 import org.jikesrvm.VM;
021 import org.jikesrvm.compilers.opt.DefUse;
022 import org.jikesrvm.compilers.opt.OptOptions;
023 import org.jikesrvm.compilers.opt.driver.CompilerPhase;
024 import org.jikesrvm.compilers.opt.ir.BasicBlock;
025 import org.jikesrvm.compilers.opt.ir.IR;
026 import org.jikesrvm.compilers.opt.ir.Instruction;
027 import org.jikesrvm.compilers.opt.ir.Trap;
028 import org.jikesrvm.compilers.opt.util.SpaceEffGraphNode;
029
030 /**
031 * IR level independent driver for
032 * simple peephole optimizations of branches.
033 */
034 public abstract class BranchOptimizationDriver extends CompilerPhase {
035
036 /**
037 * Optimization level at which phase should be performed.
038 */
039 private final int level;
040
041 /**
042 * Optimization level at which phase should be performed.
043 */
044 private final boolean simplify;
045
046 /**
047 * @param level the minimum optimization level at which the branch
048 * optimizations should be performed.
049 * @param simplify perform simplification prior to optimization?
050 */
051 BranchOptimizationDriver(int level, boolean simplify) {
052 this.level = level;
053 this.simplify = simplify;
054 }
055
056 /**
057 * @param level the minimum optimization level at which the branch
058 * optimizations should be performed.
059 */
060 BranchOptimizationDriver(int level) {
061 this.level = level;
062 this.simplify = false;
063 }
064
065 /** Interface */
066 @Override
067 public final boolean shouldPerform(OptOptions options) {
068 return options.getOptLevel() >= level;
069 }
070
071 @Override
072 public final String getName() {
073 return "Branch Optimizations";
074 }
075
076 @Override
077 public final boolean printingEnabled(OptOptions options, boolean before) {
078 return false;
079 }
080
081 /**
082 * This phase contains no per-compilation instance fields.
083 */
084 @Override
085 public final CompilerPhase newExecution(IR ir) {
086 return this;
087 }
088
089 /**
090 * Perform peephole branch optimizations.
091 *
092 * @param ir the IR to optimize
093 */
094 @Override
095 public final void perform(IR ir) {
096 perform(ir, true);
097 }
098
099 public final void perform(IR ir, boolean renumber) {
100 if (simplify) {
101 applySimplify(ir);
102 }
103
104 maximizeBasicBlocks(ir);
105 if (VM.BuildForIA32) {
106 // spans-bb information is used for CMOV insertion
107 DefUse.recomputeSpansBasicBlock(ir);
108 }
109 boolean didSomething = false;
110 boolean didSomethingThisTime = true;
111 while (didSomethingThisTime) {
112 didSomething |= applyPeepholeBranchOpts(ir);
113 didSomethingThisTime = removeUnreachableCode(ir);
114 didSomething |= didSomethingThisTime;
115 }
116 if (didSomething) {
117 maximizeBasicBlocks(ir);
118 }
119
120 ir.cfg.compactNodeNumbering();
121
122 if (ir.IRStage < IR.MIR) {
123 ir.pruneExceptionalOut();
124 }
125 }
126
127 /**
128 * Perform branch simplifications.
129 *
130 * @param ir the IR to optimize
131 * @return was something reduced
132 */
133 private static boolean applySimplify(IR ir) {
134 boolean didSomething = false;
135 for (Enumeration<BasicBlock> e = ir.getBasicBlocks(); e.hasMoreElements();) {
136 BasicBlock bb = e.nextElement();
137 didSomething |= BranchSimplifier.simplify(bb, ir);
138 }
139 return didSomething;
140 }
141
142 /**
143 * This pass performs peephole branch optimizations.
144 * See Muchnick ~p.590
145 *
146 * @param ir the IR to optimize
147 */
148 protected boolean applyPeepholeBranchOpts(IR ir) {
149 boolean didSomething = false;
150 for (Enumeration<BasicBlock> e = ir.getBasicBlocks(); e.hasMoreElements();) {
151 BasicBlock bb = e.nextElement();
152 if (!bb.isEmpty()) {
153 for (Enumeration<Instruction> ie = bb.enumerateBranchInstructions(); ie.hasMoreElements();) {
154 Instruction s = ie.nextElement();
155 if (optimizeBranchInstruction(ir, s, bb)) {
156 didSomething = true;
157 // hack: we may have modified the instructions; start over
158 ie = bb.enumerateBranchInstructions();
159 }
160 }
161 }
162 }
163 return didSomething;
164 }
165
166 /**
167 * This method actually does the work of attempting to
168 * peephole optimize a branch instruction.
169 * @param ir the containing IR
170 * @param s the branch instruction to optimize
171 * @param bb the containing basic block
172 * @return true if an optimization was applied, false otherwise
173 */
174 protected abstract boolean optimizeBranchInstruction(IR ir, Instruction s, BasicBlock bb);
175
176 /**
177 * Remove unreachable code
178 *
179 * @param ir the IR to optimize
180 * @return true if did something, false otherwise
181 */
182 protected final boolean removeUnreachableCode(IR ir) {
183 boolean result = false;
184
185 // (1) All code in a basic block after an unconditional
186 // trap instruction is dead.
187 for (Instruction s = ir.firstInstructionInCodeOrder(); s != null; s = s.nextInstructionInCodeOrder()) {
188 if (Trap.conforms(s)) {
189 Instruction p = s.nextInstructionInCodeOrder();
190 if (p.operator() != BBEND) {
191 BasicBlock bb = s.getBasicBlock();
192 do {
193 Instruction q = p;
194 p = p.nextInstructionInCodeOrder();
195 q.remove();
196 } while (p.operator() != BBEND);
197 bb.recomputeNormalOut(ir);
198 result = true;
199 }
200 }
201 }
202
203 // (2) perform a Depth-first search of the control flow graph,
204 // and remove any nodes not reachable from entry.
205 BasicBlock entry = ir.cfg.entry();
206 ir.cfg.clearDFS();
207 entry.sortDFS();
208 for (SpaceEffGraphNode node = entry; node != null;) {
209 // save it now before removeFromCFGAndCodeOrder nulls it out!!!
210 SpaceEffGraphNode nextNode = node.getNext();
211 if (!node.dfsVisited()) {
212 BasicBlock bb = (BasicBlock) node;
213 ir.cfg.removeFromCFGAndCodeOrder(bb);
214 result = true;
215 }
216 node = nextNode;
217 }
218 return result;
219 }
220
221 /**
222 * Merge adjacent basic blocks
223 *
224 * @param ir the IR to optimize
225 */
226 protected final void maximizeBasicBlocks(IR ir) {
227 for (BasicBlock currBB = ir.cfg.firstInCodeOrder(); currBB != null;) {
228 if (currBB.mergeFallThrough(ir)) {
229 // don't advance currBB; it may have a new trivial fallthrough to swallow
230 } else {
231 currBB = currBB.nextBasicBlockInCodeOrder();
232 }
233 }
234 }
235
236 // Helper functions
237
238 /**
239 * Given an instruction s, return the first LABEL instruction
240 * following s.
241 */
242 protected final Instruction firstLabelFollowing(Instruction s) {
243 for (s = s.nextInstructionInCodeOrder(); s != null; s = s.nextInstructionInCodeOrder()) {
244 if (s.operator() == LABEL) {
245 return s;
246 }
247 }
248 return null;
249 }
250
251 /**
252 * Given an instruction s, return the first real (non-label) instruction
253 * following s
254 */
255 protected final Instruction firstRealInstructionFollowing(Instruction s) {
256 for (s = s.nextInstructionInCodeOrder(); s != null; s = s.nextInstructionInCodeOrder()) {
257 if (s.operator() != LABEL && s.operator() != BBEND) {
258 return s;
259 }
260 }
261 return s;
262 }
263 }