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