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 org.jikesrvm.compilers.opt.ir.MIR_Branch;
016 import org.jikesrvm.compilers.opt.ir.MIR_CondBranch;
017 import org.jikesrvm.compilers.opt.ir.MIR_CondBranch2;
018 import org.jikesrvm.compilers.opt.ir.BasicBlock;
019 import org.jikesrvm.compilers.opt.ir.IR;
020 import org.jikesrvm.compilers.opt.ir.Instruction;
021 import org.jikesrvm.compilers.opt.ir.Operators;
022 import org.jikesrvm.compilers.opt.ir.operand.BranchOperand;
023
024 import static org.jikesrvm.compilers.opt.ir.Operators.BBEND;
025
026 /**
027 * Perform simple peephole optimizations for MIR branches.
028 */
029 public final class MIRBranchOptimizations extends BranchOptimizationDriver {
030
031 /**
032 * @param level the minimum optimization level at which the branch
033 * optimizations should be performed.
034 */
035 public MIRBranchOptimizations(int level) {
036 super(level);
037 }
038
039 /**
040 * This method actually does the work of attempting to
041 * peephole optimize a branch instruction.
042 * See Muchnick ~p.590
043 * @param ir the containing IR
044 * @param s the branch instruction to optimize
045 * @param bb the containing basic block
046 * @return true if an optimization was applied, false otherwise
047 */
048 protected boolean optimizeBranchInstruction(IR ir, Instruction s, BasicBlock bb) {
049 if (MIR_Branch.conforms(s)) {
050 return processGoto(ir, s, bb);
051 } else if (MIR_CondBranch.conforms(s)) {
052 return processCondBranch(ir, s, bb);
053 } else if (MIR_CondBranch2.conforms(s)) {
054 return processTwoTargetConditionalBranch(ir, s, bb);
055 } else {
056 return false;
057 }
058 }
059
060 /**
061 * Perform optimizations for an unconditonal branch.
062 *
063 * <p> Patterns:
064 * <pre>
065 * 1) GOTO A replaced by GOTO B
066 * A: GOTO B
067 *
068 * 2) GOTO next instruction eliminated
069 * 3) GOTO A replaced by GOTO B
070 * A: LABEL
071 * BBEND
072 * B:
073 * <pre>
074 *
075 * <p> Precondition: MIR_Branch.conforms(g)
076 *
077 * @param ir governing IR
078 * @param g the instruction to optimize
079 * @param bb the basic block holding g
080 * @return true if made a transformation
081 */
082 private boolean processGoto(IR ir, Instruction g, BasicBlock bb) {
083 BasicBlock targetBlock = g.getBranchTarget();
084 Instruction targetLabel = targetBlock.firstInstruction();
085 // get the first real instruction at the g target
086 // NOTE: this instruction is not necessarily in targetBlock,
087 // iff targetBlock has no real instructions
088 Instruction targetInst = firstRealInstructionFollowing(targetLabel);
089 if (targetInst == null || targetInst == g) {
090 return false;
091 }
092 Instruction nextLabel = firstLabelFollowing(g);
093 if (targetLabel == nextLabel) {
094 // found a GOTO to the next instruction. just remove it.
095 g.remove();
096 return true;
097 }
098 if (MIR_Branch.conforms(targetInst)) {
099 // unconditional branch to unconditional branch.
100 // replace g with goto to targetInst's target
101 Instruction target2 = firstRealInstructionFollowing(targetInst.getBranchTarget().firstInstruction());
102 if (target2 == targetInst) {
103 // Avoid an infinite recursion in the following bizarre scenario:
104 // g: goto L
105 // ...
106 // L: goto L
107 // This happens in jByteMark.EmFloatPnt.denormalize() due to a while(true) {}
108 return false;
109 }
110 BranchOperand top = (BranchOperand) MIR_Branch.getTarget(targetInst).copy();
111 MIR_Branch.setTarget(g, top);
112 bb.recomputeNormalOut(ir); // fix the CFG
113 return true;
114 }
115 if (targetBlock.isEmpty()) {
116 // GOTO an empty block. Change target to the next block.
117 BasicBlock nextBlock = targetBlock.getFallThroughBlock();
118 MIR_Branch.setTarget(g, nextBlock.makeJumpTarget());
119 bb.recomputeNormalOut(ir); // fix the CFG
120 return true;
121 }
122 return false;
123 }
124
125 /**
126 * Perform optimizations for a conditional branch.
127 *
128 * <pre>
129 * 1) IF .. GOTO A replaced by IF .. GOTO B
130 * ...
131 * A: GOTO B
132 * 2) conditional branch to next instruction eliminated
133 * 3) IF (condition) GOTO A replaced by IF (!condition) GOTO B
134 * GOTO B A: ...
135 * A: ...
136 * 4) IF .. GOTO A replaced by IF .. GOTO B
137 * A: LABEL
138 * BBEND
139 * B:
140 * 5) fallthrough to a goto: replicate goto to enable other optimizations.
141 * </pre>
142 *
143 * <p> Precondition: MIR_CondBranch.conforms(cb)
144 *
145 * @param ir the governing IR
146 * @param cb the instruction to optimize
147 * @param bb the basic block holding if
148 * @return true iff made a transformation
149 */
150 private boolean processCondBranch(IR ir, Instruction cb, BasicBlock bb) {
151 BasicBlock targetBlock = cb.getBranchTarget();
152 Instruction targetLabel = targetBlock.firstInstruction();
153 // get the first real instruction at the branch target
154 // NOTE: this instruction is not necessarily in targetBlock,
155 // iff targetBlock has no real instructions
156 Instruction targetInst = firstRealInstructionFollowing(targetLabel);
157 if (targetInst == null || targetInst == cb) {
158 return false;
159 }
160 boolean endsBlock = cb.nextInstructionInCodeOrder().operator() == BBEND;
161 if (endsBlock) {
162 Instruction nextLabel = firstLabelFollowing(cb);
163 if (targetLabel == nextLabel) {
164 // found a conditional branch to the next instruction. just remove it.
165 cb.remove();
166 return true;
167 }
168 Instruction nextI = firstRealInstructionFollowing(nextLabel);
169 if (nextI != null && MIR_Branch.conforms(nextI)) {
170 // replicate Goto
171 cb.insertAfter(nextI.copyWithoutLinks());
172 bb.recomputeNormalOut(ir); // fix the CFG
173 return true;
174 }
175 }
176 if (MIR_Branch.conforms(targetInst)) {
177 // conditional branch to unconditional branch.
178 // change conditional branch target to latter's target
179 Instruction target2 = firstRealInstructionFollowing(targetInst.getBranchTarget().firstInstruction());
180 if (target2 == targetInst) {
181 // Avoid an infinite recursion in the following scenario:
182 // g: if (...) goto L
183 // ...
184 // L: goto L
185 // This happens in GCUtil in some systems due to a while(true) {}
186 return false;
187 }
188 MIR_CondBranch.setTarget(cb, (BranchOperand) (MIR_Branch.getTarget(targetInst).copy()));
189 bb.recomputeNormalOut(ir); // fix the CFG
190 return true;
191 }
192 if (targetBlock.isEmpty()) {
193 // branch to an empty block. Change target to the next block.
194 BasicBlock nextBlock = targetBlock.getFallThroughBlock();
195 BranchOperand newTarget = nextBlock.makeJumpTarget();
196 MIR_CondBranch.setTarget(cb, newTarget);
197 bb.recomputeNormalOut(ir); // fix the CFG
198 return true;
199 }
200 if (isFlipCandidate(cb, targetInst)) {
201 flipConditionalBranch(cb);
202 bb.recomputeNormalOut(ir); // fix the CFG
203 return true;
204 }
205 return false;
206 }
207
208 /**
209 * Perform optimizations for a two way conditional branch.
210 *
211 * <pre>
212 * 1) IF .. GOTO A replaced by IF .. GOTO B
213 * ...
214 * A: GOTO B
215 * 2) conditional branch to next instruction eliminated
216 * 3) IF .. GOTO A replaced by IF .. GOTO B
217 * A: LABEL
218 * BBEND
219 * B:
220 * 4) fallthrough to a goto: replicate goto to enable other optimizations.
221 * </pre>
222 *
223 * <p> Precondition: MIR_CondBranch2.conforms(cb)
224 *
225 * @param ir the governing IR
226 * @param cb the instruction to optimize
227 * @param bb the basic block holding if
228 * @return true iff made a transformation
229 */
230 private boolean processTwoTargetConditionalBranch(IR ir, Instruction cb, BasicBlock bb) {
231 // First condition/target
232 Instruction target1Label = MIR_CondBranch2.getTarget1(cb).target;
233 Instruction target1Inst = firstRealInstructionFollowing(target1Label);
234 Instruction nextLabel = firstLabelFollowing(cb);
235 boolean endsBlock = cb.nextInstructionInCodeOrder().operator() == BBEND;
236 if (target1Inst != null && target1Inst != cb) {
237 if (MIR_Branch.conforms(target1Inst)) {
238 // conditional branch to unconditional branch.
239 // change conditional branch target to latter's target
240 MIR_CondBranch2.setTarget1(cb, MIR_Branch.getTarget(target1Inst));
241 bb.recomputeNormalOut(ir); // fix CFG
242 return true;
243 }
244 BasicBlock target1Block = target1Label.getBasicBlock();
245 if (target1Block.isEmpty()) {
246 // branch to an empty block. Change target to the next block.
247 BasicBlock nextBlock = target1Block.getFallThroughBlock();
248 MIR_CondBranch2.setTarget1(cb, nextBlock.makeJumpTarget());
249 bb.recomputeNormalOut(ir); // fix the CFG
250 return true;
251 }
252 }
253
254 // Second condition/target
255 Instruction target2Label = MIR_CondBranch2.getTarget2(cb).target;
256 Instruction target2Inst = firstRealInstructionFollowing(target2Label);
257 if (target2Inst != null && target2Inst != cb) {
258 if (MIR_Branch.conforms(target2Inst)) {
259 // conditional branch to unconditional branch.
260 // change conditional branch target to latter's target
261 MIR_CondBranch2.setTarget2(cb, MIR_Branch.getTarget(target2Inst));
262 bb.recomputeNormalOut(ir); // fix CFG
263 return true;
264 }
265 if ((target2Label == nextLabel) && endsBlock) {
266 // found a conditional branch to the next instruction.
267 // Reduce to MIR_BranchCond
268 Operators.helper.mutateMIRCondBranch(cb);
269 return true;
270 }
271 BasicBlock target2Block = target2Label.getBasicBlock();
272 if (target2Block.isEmpty()) {
273 // branch to an empty block. Change target to the next block.
274 BasicBlock nextBlock = target2Block.getFallThroughBlock();
275 MIR_CondBranch2.setTarget2(cb, nextBlock.makeJumpTarget());
276 bb.recomputeNormalOut(ir); // fix the CFG
277 return true;
278 }
279 }
280
281 // if fall through to a goto; replicate the goto
282 if (endsBlock) {
283 Instruction nextI = firstRealInstructionFollowing(nextLabel);
284 if (nextI != null && MIR_Branch.conforms(nextI)) {
285 // replicate unconditional branch
286 cb.insertAfter(nextI.copyWithoutLinks());
287 bb.recomputeNormalOut(ir); // fix the CFG
288 return true;
289 }
290 }
291
292 return false;
293 }
294
295 /**
296 * Is a conditional branch a candidate to be flipped?
297 * See comment 3) of processCondBranch
298 *
299 * <p> Precondition: MIR_CondBranch.conforms(cb)
300 *
301 * @param cb the conditional branch instruction
302 * @param target the target instruction (real instruction) of the conditional
303 * branch
304 * @return boolean result
305 */
306 private boolean isFlipCandidate(Instruction cb, Instruction target) {
307 // condition 1: is next instruction a GOTO?
308 Instruction next = cb.nextInstructionInCodeOrder();
309 if (!MIR_Branch.conforms(next)) {
310 return false;
311 }
312 // condition 2: is the target of the conditional branch the
313 // next instruction after the GOTO?
314 next = firstRealInstructionFollowing(next);
315 if (next != target) {
316 return false;
317 }
318 // got this far. It's a candidate.
319 return true;
320 }
321
322 /**
323 * Flip a conditional branch and remove the trailing goto.
324 * See comment 3) of processCondBranch
325 *
326 * <p> Precondition isFlipCandidate(cb)
327 * @param cb the conditional branch instruction
328 */
329 private void flipConditionalBranch(Instruction cb) {
330 // get the trailing GOTO instruction
331 Instruction g = cb.nextInstructionInCodeOrder();
332 BranchOperand gTarget = MIR_Branch.getTarget(g);
333 // now flip the test and set the new target
334 MIR_CondBranch.setCond(cb, MIR_CondBranch.getCond(cb).flipCode());
335 MIR_CondBranch.setTarget(cb, gTarget);
336 // Remove the trailing GOTO instruction
337 g.remove();
338 }
339 }