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