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.IRTools.CPOS;
016 import static org.jikesrvm.compilers.opt.ir.Operators.BBEND;
017 import static org.jikesrvm.compilers.opt.ir.Operators.BOOLEAN_CMP_ADDR;
018 import static org.jikesrvm.compilers.opt.ir.Operators.BOOLEAN_CMP_INT;
019 import static org.jikesrvm.compilers.opt.ir.Operators.BOOLEAN_NOT;
020 import static org.jikesrvm.compilers.opt.ir.Operators.DOUBLE_2FLOAT_opcode;
021 import static org.jikesrvm.compilers.opt.ir.Operators.DOUBLE_ADD_opcode;
022 import static org.jikesrvm.compilers.opt.ir.Operators.DOUBLE_MOVE_opcode;
023 import static org.jikesrvm.compilers.opt.ir.Operators.DOUBLE_MUL_opcode;
024 import static org.jikesrvm.compilers.opt.ir.Operators.DOUBLE_NEG_opcode;
025 import static org.jikesrvm.compilers.opt.ir.Operators.DOUBLE_SUB_opcode;
026 import static org.jikesrvm.compilers.opt.ir.Operators.FLOAT_2DOUBLE_opcode;
027 import static org.jikesrvm.compilers.opt.ir.Operators.FLOAT_ADD_opcode;
028 import static org.jikesrvm.compilers.opt.ir.Operators.FLOAT_MOVE_opcode;
029 import static org.jikesrvm.compilers.opt.ir.Operators.FLOAT_MUL_opcode;
030 import static org.jikesrvm.compilers.opt.ir.Operators.FLOAT_NEG_opcode;
031 import static org.jikesrvm.compilers.opt.ir.Operators.FLOAT_SUB_opcode;
032 import static org.jikesrvm.compilers.opt.ir.Operators.GOTO;
033 import static org.jikesrvm.compilers.opt.ir.Operators.INT_2BYTE_opcode;
034 import static org.jikesrvm.compilers.opt.ir.Operators.INT_2SHORT_opcode;
035 import static org.jikesrvm.compilers.opt.ir.Operators.INT_2USHORT_opcode;
036 import static org.jikesrvm.compilers.opt.ir.Operators.INT_ADD_opcode;
037 import static org.jikesrvm.compilers.opt.ir.Operators.INT_AND_opcode;
038 import static org.jikesrvm.compilers.opt.ir.Operators.INT_IFCMP;
039 import static org.jikesrvm.compilers.opt.ir.Operators.INT_IFCMP2;
040 import static org.jikesrvm.compilers.opt.ir.Operators.INT_MOVE;
041 import static org.jikesrvm.compilers.opt.ir.Operators.INT_MOVE_opcode;
042 import static org.jikesrvm.compilers.opt.ir.Operators.INT_MUL_opcode;
043 import static org.jikesrvm.compilers.opt.ir.Operators.INT_NEG_opcode;
044 import static org.jikesrvm.compilers.opt.ir.Operators.INT_NOT_opcode;
045 import static org.jikesrvm.compilers.opt.ir.Operators.INT_OR_opcode;
046 import static org.jikesrvm.compilers.opt.ir.Operators.INT_SHL_opcode;
047 import static org.jikesrvm.compilers.opt.ir.Operators.INT_SHR_opcode;
048 import static org.jikesrvm.compilers.opt.ir.Operators.INT_SUB_opcode;
049 import static org.jikesrvm.compilers.opt.ir.Operators.INT_USHR_opcode;
050 import static org.jikesrvm.compilers.opt.ir.Operators.INT_XOR_opcode;
051 import static org.jikesrvm.compilers.opt.ir.Operators.REF_ADD_opcode;
052 import static org.jikesrvm.compilers.opt.ir.Operators.REF_AND_opcode;
053 import static org.jikesrvm.compilers.opt.ir.Operators.REF_IFCMP;
054 import static org.jikesrvm.compilers.opt.ir.Operators.REF_MOVE_opcode;
055 import static org.jikesrvm.compilers.opt.ir.Operators.REF_NOT_opcode;
056 import static org.jikesrvm.compilers.opt.ir.Operators.REF_OR_opcode;
057 import static org.jikesrvm.compilers.opt.ir.Operators.REF_SHL_opcode;
058 import static org.jikesrvm.compilers.opt.ir.Operators.REF_SHR_opcode;
059 import static org.jikesrvm.compilers.opt.ir.Operators.REF_SUB_opcode;
060 import static org.jikesrvm.compilers.opt.ir.Operators.REF_USHR_opcode;
061 import static org.jikesrvm.compilers.opt.ir.Operators.REF_XOR_opcode;
062 import static org.jikesrvm.compilers.opt.ir.Operators.RETURN;
063
064 import java.util.Enumeration;
065 import java.util.HashMap;
066 import java.util.HashSet;
067
068 import org.jikesrvm.VM;
069 import org.jikesrvm.classloader.Atom;
070 import org.jikesrvm.classloader.TypeReference;
071 import org.jikesrvm.compilers.opt.OptimizingCompilerException;
072 import org.jikesrvm.compilers.opt.ir.BasicBlock;
073 import org.jikesrvm.compilers.opt.ir.BooleanCmp;
074 import org.jikesrvm.compilers.opt.ir.CondMove;
075 import org.jikesrvm.compilers.opt.ir.Goto;
076 import org.jikesrvm.compilers.opt.ir.IR;
077 import org.jikesrvm.compilers.opt.ir.IRTools;
078 import org.jikesrvm.compilers.opt.ir.IfCmp;
079 import org.jikesrvm.compilers.opt.ir.IfCmp2;
080 import org.jikesrvm.compilers.opt.ir.InlineGuard;
081 import org.jikesrvm.compilers.opt.ir.Instruction;
082 import org.jikesrvm.compilers.opt.ir.Move;
083 import org.jikesrvm.compilers.opt.ir.Operator;
084 import org.jikesrvm.compilers.opt.ir.Register;
085 import org.jikesrvm.compilers.opt.ir.Return;
086 import org.jikesrvm.compilers.opt.ir.Unary;
087 import org.jikesrvm.compilers.opt.ir.operand.BranchOperand;
088 import org.jikesrvm.compilers.opt.ir.operand.BranchProfileOperand;
089 import org.jikesrvm.compilers.opt.ir.operand.ConditionOperand;
090 import org.jikesrvm.compilers.opt.ir.operand.IntConstantOperand;
091 import org.jikesrvm.compilers.opt.ir.operand.Operand;
092 import org.jikesrvm.compilers.opt.ir.operand.RegisterOperand;
093
094 /**
095 * Perform simple peephole optimizations for branches.
096 */
097 public final class BranchOptimizations extends BranchOptimizationDriver {
098
099 /**
100 * Name of abs method used as a special case in conditional moves
101 */
102 private static final Atom ABS = Atom.findOrCreateAsciiAtom("abs");
103
104 /**
105 * Is branch optimizations allowed to change the code order to
106 * create fallthrough edges (and thus merge basic blocks)?
107 * After we run code reordering, we disallow this transformation to avoid
108 * destroying the desired code order.
109 */
110 private final boolean mayReorderCode;
111
112 /**
113 * Are we allowed to duplication conditional branches?
114 * Restricted until backedge yieldpoints are inserted to
115 * avoid creating irreducible control flow by duplicating
116 * a conditional branch in a loop header into a block outside the
117 * loop, thus creating two loop entry blocks.
118 */
119 private final boolean mayDuplicateCondBranches;
120
121 /**
122 * @param level the minimum optimization level at which the branch
123 * optimizations should be performed.
124 * @param mayReorderCode are we allowed to change the code order?
125 * @param mayDuplicateCondBranches are we allowed to duplicate conditional branches?
126 */
127 public BranchOptimizations(int level, boolean mayReorderCode, boolean mayDuplicateCondBranches) {
128 super(level, true);
129 this.mayReorderCode = mayReorderCode;
130 this.mayDuplicateCondBranches = mayDuplicateCondBranches;
131 }
132
133 /**
134 * @param level the minimum optimization level at which the branch
135 * optimizations should be performed.
136 * @param mayReorderCode are we allowed to change the code order?
137 * @param mayDuplicateCondBranches are we allowed to duplicate conditional branches?
138 * @param simplify simplify prior to optimizing?
139 */
140 public BranchOptimizations(int level, boolean mayReorderCode, boolean mayDuplicateCondBranches,
141 boolean simplify) {
142 super(level, simplify);
143 this.mayReorderCode = mayReorderCode;
144 this.mayDuplicateCondBranches = mayDuplicateCondBranches;
145 }
146
147 /**
148 * This method actually does the work of attempting to
149 * peephole optimize a branch instruction.
150 * See Muchnick ~p.590
151 * @param ir the containing IR
152 * @param s the branch instruction to optimize
153 * @param bb the containing basic block
154 * @return {@code true} if an optimization was applied, {@code false} otherwise
155 */
156 @Override
157 protected boolean optimizeBranchInstruction(IR ir, Instruction s, BasicBlock bb) {
158 if (Goto.conforms(s)) {
159 return processGoto(ir, s, bb);
160 } else if (IfCmp.conforms(s)) {
161 return processConditionalBranch(ir, s, bb);
162 } else if (InlineGuard.conforms(s)) {
163 return processInlineGuard(ir, s, bb);
164 } else if (IfCmp2.conforms(s)) {
165 return processTwoTargetConditionalBranch(ir, s, bb);
166 } else {
167 return false;
168 }
169 }
170
171 /**
172 * Perform optimizations for a Goto.
173 *
174 * <p> Patterns:
175 * <pre>
176 * 1) GOTO A replaced by GOTO B
177 * A: GOTO B
178 *
179 * 2) GOTO A replaced by IF .. GOTO B
180 * A: IF .. GOTO B GOTO C
181 * C: ...
182 * 3) GOTO next instruction eliminated
183 * 4) GOTO A replaced by GOTO B
184 * A: LABEL
185 * BBEND
186 * B:
187 * 5) GOTO BBn where BBn has exactly one in edge
188 * - move BBn immediately after the GOTO in the code order,
189 * so that pattern 3) will create a fallthrough
190 * <pre>
191 *
192 * <p> Precondition: Goto.conforms(g)
193 *
194 * @param ir governing IR
195 * @param g the instruction to optimize
196 * @param bb the basic block holding g
197 * @return {@code true} if made a transformation
198 */
199 private boolean processGoto(IR ir, Instruction g, BasicBlock bb) {
200 BasicBlock targetBlock = g.getBranchTarget();
201
202 // don't optimize jumps to a code motion landing pad
203 if (targetBlock.getLandingPad()) return false;
204
205 Instruction targetLabel = targetBlock.firstInstruction();
206 // get the first real instruction at the g target
207 // NOTE: this instruction is not necessarily in targetBlock,
208 // iff targetBlock has no real instructions
209 Instruction targetInst = firstRealInstructionFollowing(targetLabel);
210 if (targetInst == null || targetInst == g) {
211 return false;
212 }
213 Instruction nextLabel = firstLabelFollowing(g);
214 if (targetLabel == nextLabel) {
215 // found a GOTO to the next instruction. just remove it.
216 g.remove();
217 return true;
218 }
219 if (Goto.conforms(targetInst)) {
220 // unconditional branch to unconditional branch.
221 // replace g with goto to targetInst's target
222 Instruction target2 = firstRealInstructionFollowing(targetInst.getBranchTarget().firstInstruction());
223 if (target2 == targetInst) {
224 // Avoid an infinite recursion in the following bizarre scenario:
225 // g: goto L
226 // ...
227 // L: goto L
228 // This happens in jByteMark.EmFloatPnt.denormalize() due to a while(true) {}
229 return false;
230 }
231 Goto.setTarget(g, (BranchOperand) Goto.getTarget(targetInst).copy());
232 bb.recomputeNormalOut(ir); // fix the CFG
233 return true;
234 }
235 if (targetBlock.isEmpty()) {
236 // GOTO an empty basic block. Change target to the
237 // next block.
238 BasicBlock nextBlock = targetBlock.getFallThroughBlock();
239 Goto.setTarget(g, nextBlock.makeJumpTarget());
240 bb.recomputeNormalOut(ir); // fix the CFG
241 return true;
242 }
243 if (mayDuplicateCondBranches && IfCmp.conforms(targetInst)) {
244 // unconditional branch to a conditional branch.
245 // If the Goto is the only branch instruction in its basic block
246 // and the IfCmp is the only non-GOTO branch instruction
247 // in its basic block then replace the goto with a copy of
248 // targetInst and append another GOTO to the not-taken
249 // target of targetInst's block.
250 // We impose these additional restrictions to avoid getting
251 // multiple conditional branches in a single basic block.
252 if (!g.prevInstructionInCodeOrder().isBranch() &&
253 (targetInst.nextInstructionInCodeOrder().operator == BBEND ||
254 targetInst.nextInstructionInCodeOrder().operator == GOTO)) {
255 Instruction copy = targetInst.copyWithoutLinks();
256 g.replace(copy);
257 Instruction newGoto = targetInst.getBasicBlock().getNotTakenNextBlock().makeGOTO();
258 copy.insertAfter(newGoto);
259 bb.recomputeNormalOut(ir); // fix the CFG
260 return true;
261 }
262 }
263
264 // try to create a fallthrough
265 if (mayReorderCode && targetBlock.getNumberOfIn() == 1) {
266 BasicBlock ftBlock = targetBlock.getFallThroughBlock();
267 if (ftBlock != null) {
268 BranchOperand ftTarget = ftBlock.makeJumpTarget();
269 targetBlock.appendInstruction(CPOS(g,Goto.create(GOTO, ftTarget)));
270 }
271
272 ir.cfg.removeFromCodeOrder(targetBlock);
273 ir.cfg.insertAfterInCodeOrder(bb, targetBlock);
274 targetBlock.recomputeNormalOut(ir); // fix the CFG
275 return true;
276 }
277 return false;
278 }
279
280 /**
281 * Perform optimizations for a conditional branch.
282 *
283 * <pre>
284 * 1) IF .. GOTO A replaced by IF .. GOTO B
285 * ...
286 * A: GOTO B
287 * 2) conditional branch to next instruction eliminated
288 * 3) IF (condition) GOTO A replaced by IF (!condition) GOTO B
289 * GOTO B A: ...
290 * A: ...
291 * 4) special case to generate Boolean compare opcode
292 * 5) special case to generate conditional move sequence
293 * 6) IF .. GOTO A replaced by IF .. GOTO B
294 * A: LABEL
295 * BBEND
296 * B:
297 * 7) fallthrough to a goto: replicate goto to enable other optimizations.
298 * </pre>
299 *
300 * <p> Precondition: IfCmp.conforms(cb)
301 *
302 * @param ir the governing IR
303 * @param cb the instruction to optimize
304 * @param bb the basic block holding if
305 * @return {@code true} iff made a transformation
306 */
307 private boolean processConditionalBranch(IR ir, Instruction cb, BasicBlock bb) {
308 BasicBlock targetBlock = cb.getBranchTarget();
309
310 // don't optimize jumps to a code motion landing pad
311 if (targetBlock.getLandingPad()) return false;
312
313 Instruction targetLabel = targetBlock.firstInstruction();
314 // get the first real instruction at the branch target
315 // NOTE: this instruction is not necessarily in targetBlock,
316 // iff targetBlock has no real instructions
317 Instruction targetInst = firstRealInstructionFollowing(targetLabel);
318 if (targetInst == null || targetInst == cb) {
319 return false;
320 }
321 boolean endsBlock = cb.nextInstructionInCodeOrder().operator() == BBEND;
322 if (endsBlock) {
323 Instruction nextLabel = firstLabelFollowing(cb);
324
325 if (targetLabel == nextLabel) {
326 // found a conditional branch to the next instruction. just remove it.
327 cb.remove();
328 return true;
329 }
330 Instruction nextI = firstRealInstructionFollowing(nextLabel);
331 if (nextI != null && Goto.conforms(nextI)) {
332 // Check that the target is not the fall through (the goto itself).
333 // If we add a goto to the next block, it will be removed by
334 // processGoto and we will loop indefinitely.
335 // This can be tripped by (strange) code such as:
336 // if (condition) while (true);
337 BasicBlock gotoTarget = nextI.getBranchTarget();
338 Instruction gotoLabel = gotoTarget.firstInstruction();
339 Instruction gotoInst = firstRealInstructionFollowing(gotoLabel);
340
341 if (gotoInst != nextI) {
342 // replicate Goto
343 cb.insertAfter(nextI.copyWithoutLinks());
344 bb.recomputeNormalOut(ir); // fix the CFG
345 return true;
346 }
347 }
348 }
349 // attempt to generate boolean compare.
350 if (generateBooleanCompare(ir, bb, cb, targetBlock)) {
351 // generateBooleanCompare does all necessary CFG fixup.
352 return true;
353 }
354 // attempt to generate a sequence using conditional moves
355 if (generateCondMove(ir, bb, cb)) {
356 // generateCondMove does all necessary CFG fixup.
357 return true;
358 }
359
360 // do we fall through to a block that has only a goto?
361 BasicBlock fallThrough = bb.getFallThroughBlock();
362 if (fallThrough != null) {
363 Instruction fallThroughInstruction = fallThrough.firstRealInstruction();
364 if ((fallThroughInstruction != null) && Goto.conforms(fallThroughInstruction)) {
365 // copy goto to bb
366 bb.appendInstruction(fallThroughInstruction.copyWithoutLinks());
367 bb.recomputeNormalOut(ir);
368 }
369 }
370
371 if (Goto.conforms(targetInst)) {
372 // conditional branch to unconditional branch.
373 // change conditional branch target to latter's target
374 Instruction target2 = firstRealInstructionFollowing(targetInst.getBranchTarget().firstInstruction());
375 if (target2 == targetInst) {
376 // Avoid an infinite recursion in the following scenario:
377 // g: if (...) goto L
378 // ...
379 // L: goto L
380 // This happens in GCUtil in some systems due to a while(true) {}
381 return false;
382 }
383 IfCmp.setTarget(cb, (BranchOperand) Goto.getTarget(targetInst).copy());
384 bb.recomputeNormalOut(ir); // fix the CFG
385 return true;
386 }
387 if (targetBlock.isEmpty()) {
388 // branch to an empty block. Change target to the next block.
389 BasicBlock nextBlock = targetBlock.getFallThroughBlock();
390 IfCmp.setTarget(cb, nextBlock.makeJumpTarget());
391 bb.recomputeNormalOut(ir); // fix the CFG
392 return true;
393 }
394 if (isFlipCandidate(cb, targetInst)) {
395 flipConditionalBranch(cb);
396 bb.recomputeNormalOut(ir); // fix the CFG
397 return true;
398 }
399 return false;
400 }
401
402 /**
403 * Perform optimizations for an inline guard.
404 *
405 * <p> Precondition: InlineGuard.conforms(cb)
406 *
407 * @param ir the governing IR
408 * @param cb the instruction to optimize
409 * @param bb the basic block holding if
410 * @return {@code true} iff made a transformation
411 */
412 private boolean processInlineGuard(IR ir, Instruction cb, BasicBlock bb) {
413 BasicBlock targetBlock = cb.getBranchTarget();
414 Instruction targetLabel = targetBlock.firstInstruction();
415 // get the first real instruction at the branch target
416 // NOTE: this instruction is not necessarily in targetBlock,
417 // iff targetBlock has no real instructions
418 Instruction targetInst = firstRealInstructionFollowing(targetLabel);
419 if (targetInst == null || targetInst == cb) {
420 return false;
421 }
422 boolean endsBlock = cb.nextInstructionInCodeOrder().operator() == BBEND;
423 if (endsBlock) {
424 Instruction nextLabel = firstLabelFollowing(cb);
425 if (targetLabel == nextLabel) {
426 // found a conditional branch to the next instruction. just remove it.
427 cb.remove();
428 return true;
429 }
430 Instruction nextI = firstRealInstructionFollowing(nextLabel);
431 if (nextI != null && Goto.conforms(nextI)) {
432 // replicate Goto
433 cb.insertAfter(nextI.copyWithoutLinks());
434 bb.recomputeNormalOut(ir); // fix the CFG
435 return true;
436 }
437 }
438 // do we fall through to a block that has only a goto?
439 BasicBlock fallThrough = bb.getFallThroughBlock();
440 if (fallThrough != null) {
441 Instruction fallThroughInstruction = fallThrough.firstRealInstruction();
442 if ((fallThroughInstruction != null) && Goto.conforms(fallThroughInstruction)) {
443 // copy goto to bb
444 bb.appendInstruction(fallThroughInstruction.copyWithoutLinks());
445 bb.recomputeNormalOut(ir);
446 }
447 }
448
449 if (Goto.conforms(targetInst)) {
450 // conditional branch to unconditional branch.
451 // change conditional branch target to latter's target
452 InlineGuard.setTarget(cb, (BranchOperand) Goto.getTarget(targetInst).copy());
453 bb.recomputeNormalOut(ir); // fix the CFG
454 return true;
455 }
456 if (targetBlock.isEmpty()) {
457 // branch to an empty block. Change target to the next block.
458 BasicBlock nextBlock = targetBlock.getFallThroughBlock();
459 InlineGuard.setTarget(cb, nextBlock.makeJumpTarget());
460 bb.recomputeNormalOut(ir); // fix the CFG
461 return true;
462 }
463 return false;
464 }
465
466 /**
467 * Perform optimizations for a two way conditional branch.
468 *
469 * <p> Precondition: IfCmp2.conforms(cb)
470 *
471 * @param ir the governing IR
472 * @param cb the instruction to optimize
473 * @param bb the basic block holding if
474 * @return {@code true} iff made a transformation
475 */
476 private boolean processTwoTargetConditionalBranch(IR ir, Instruction cb, BasicBlock bb) {
477 // First condition/target
478 Instruction target1Label = IfCmp2.getTarget1(cb).target;
479 Instruction target1Inst = firstRealInstructionFollowing(target1Label);
480 Instruction nextLabel = firstLabelFollowing(cb);
481 boolean endsBlock = cb.nextInstructionInCodeOrder().operator() == BBEND;
482 if (target1Inst != null && target1Inst != cb) {
483 if (Goto.conforms(target1Inst)) {
484 // conditional branch to unconditional branch.
485 // change conditional branch target to latter's target
486 IfCmp2.setTarget1(cb, (BranchOperand) Goto.getTarget(target1Inst).copy());
487 bb.recomputeNormalOut(ir); // fix CFG
488 return true;
489 }
490 BasicBlock target1Block = target1Label.getBasicBlock();
491 if (target1Block.isEmpty()) {
492 // branch to an empty block. Change target to the next block.
493 BasicBlock nextBlock = target1Block.getFallThroughBlock();
494 IfCmp2.setTarget1(cb, nextBlock.makeJumpTarget());
495 bb.recomputeNormalOut(ir); // fix the CFG
496 return true;
497 }
498 }
499
500 // Second condition/target
501 Instruction target2Label = IfCmp2.getTarget2(cb).target;
502 Instruction target2Inst = firstRealInstructionFollowing(target2Label);
503 if (target2Inst != null && target2Inst != cb) {
504 if (Goto.conforms(target2Inst)) {
505 // conditional branch to unconditional branch.
506 // change conditional branch target to latter's target
507 IfCmp2.setTarget2(cb, (BranchOperand) Goto.getTarget(target2Inst).copy());
508 bb.recomputeNormalOut(ir); // fix CFG
509 return true;
510 }
511 if ((target2Label == nextLabel) && endsBlock) {
512 // found a conditional branch to the next instruction. Reduce to IfCmp
513 if (VM.VerifyAssertions) VM._assert(cb.operator() == INT_IFCMP2);
514 IfCmp.mutate(cb,
515 INT_IFCMP,
516 IfCmp2.getGuardResult(cb),
517 IfCmp2.getVal1(cb),
518 IfCmp2.getVal2(cb),
519 IfCmp2.getCond1(cb),
520 IfCmp2.getTarget1(cb),
521 IfCmp2.getBranchProfile1(cb));
522 return true;
523 }
524 BasicBlock target2Block = target2Label.getBasicBlock();
525 if (target2Block.isEmpty()) {
526 // branch to an empty block. Change target to the next block.
527 BasicBlock nextBlock = target2Block.getFallThroughBlock();
528 IfCmp2.setTarget2(cb, nextBlock.makeJumpTarget());
529 bb.recomputeNormalOut(ir); // fix the CFG
530 return true;
531 }
532 }
533
534 // if fall through to a goto; replicate the goto
535 if (endsBlock) {
536 Instruction nextI = firstRealInstructionFollowing(nextLabel);
537 if (nextI != null && Goto.conforms(nextI)) {
538 // replicate Goto
539 cb.insertAfter(nextI.copyWithoutLinks());
540 bb.recomputeNormalOut(ir); // fix the CFG
541 return true;
542 }
543 }
544
545 return false;
546 }
547
548 /**
549 * Is a conditional branch a candidate to be flipped?
550 * See comment 3) of processConditionalBranch
551 *
552 * <p> Precondition: IfCmp.conforms(cb)
553 *
554 * @param cb the conditional branch instruction
555 * @param target the target instruction (real instruction) of the conditional
556 * branch
557 * @return boolean result
558 */
559 private boolean isFlipCandidate(Instruction cb, Instruction target) {
560 // condition 1: is next instruction a GOTO?
561 Instruction next = cb.nextInstructionInCodeOrder();
562 if (!Goto.conforms(next)) {
563 return false;
564 }
565 // condition 2: is the target of the conditional branch the
566 // next instruction after the GOTO?
567 next = firstRealInstructionFollowing(next);
568 if (next != target) {
569 return false;
570 }
571 // got this far. It's a candidate.
572 return true;
573 }
574
575 /**
576 * Flip a conditional branch and remove the trailing goto.
577 * See comment 3) of processConditionalBranch
578 *
579 * <p> Precondition isFlipCandidate(cb)
580 * @param cb the conditional branch instruction
581 */
582 private void flipConditionalBranch(Instruction cb) {
583 // get the trailing GOTO instruction
584 Instruction g = cb.nextInstructionInCodeOrder();
585 BranchOperand gTarget = (BranchOperand) (Goto.getTarget(g).copy());
586 // now flip the test and set the new target
587 IfCmp.setCond(cb, IfCmp.getCond(cb).flipCode());
588 IfCmp.setTarget(cb, gTarget);
589
590 // Update the branch probability. It is now the opposite
591 cb.flipBranchProbability();
592 // finally, remove the trailing GOTO instruction
593 g.remove();
594 }
595
596 /**
597 * Generate a boolean operation opcode
598 *
599 * <pre>
600 * 1) IF br != 0 THEN x=1 ELSE x=0 replaced by INT_MOVE x=br
601 * IF br == 0 THEN x=0 ELSE x=1
602 * 2) IF br == 0 THEN x=1 ELSE x=0 replaced by BOOLEAN_NOT x=br
603 * IF br != 0 THEN x=0 ELSE x=1
604 * 3) IF v1 ~ v2 THEN x=1 ELSE x=0 replaced by BOOLEAN_CMP x=v1,v2,~
605 * </pre>
606 *
607 *
608 * @param cb conditional branch instruction
609 * @param res the operand for result
610 * @param val1 value being compared
611 * @param val2 value being compared with
612 * @param cond comparison condition
613 */
614 private void booleanCompareHelper(Instruction cb, RegisterOperand res, Operand val1, Operand val2,
615 ConditionOperand cond) {
616 if ((val1 instanceof RegisterOperand) &&
617 ((RegisterOperand) val1).getType().isBooleanType() &&
618 (val2 instanceof IntConstantOperand)) {
619 int value = ((IntConstantOperand) val2).value;
620 if (VM.VerifyAssertions && (value != 0) && (value != 1)) {
621 throw new OptimizingCompilerException("Invalid boolean value");
622 }
623 int c = cond.evaluate(value, 0);
624 if (c == ConditionOperand.TRUE) {
625 Unary.mutate(cb, BOOLEAN_NOT, res, val1);
626 return;
627 } else if (c == ConditionOperand.FALSE) {
628 Move.mutate(cb, INT_MOVE, res, val1);
629 return;
630 }
631 }
632 BooleanCmp.mutate(cb,
633 (cb.operator() == REF_IFCMP) ? BOOLEAN_CMP_ADDR : BOOLEAN_CMP_INT,
634 res,
635 val1,
636 val2,
637 cond,
638 new BranchProfileOperand());
639 }
640
641 /**
642 * Attempt to generate a straight-line sequence using conditional move
643 * instructions, to replace a diamond control flow structure.
644 *
645 * <p>Suppose we have the following code, where e{n} is an expression:
646 * <pre>
647 * if (a op b) {
648 * x = e2;
649 * y = e3;
650 * } else {
651 * z = e4;
652 * x = e5;
653 * }
654 * </pre>
655 * We would transform this to:
656 * <pre>
657 * t1 = a;
658 * t2 = b;
659 * t3 = e2;
660 * t4 = e3;
661 * t5 = e4;
662 * t6 = e5;
663 * COND MOVE [if (t1 op t2) x := t3 else x := t6 ];
664 * COND MOVE [if (t1 op t2) y := t4 else y := y];
665 * COND MOVE [if (t1 op t2) z := z else z := t5];
666 * </pre>
667 *
668 * <p>Note that we rely on other optimizations (eg. copy propagation) to
669 * clean up some of this unnecessary mess.
670 *
671 * <p>Note that in this example, we've increased the shortest path by 2
672 * expression evaluations, 2 moves, and 3 cond moves, but eliminated one
673 * conditional branch.
674 *
675 * <p>We apply a cost heuristic to guide this transformation:
676 * We will eliminate a conditional branch iff it increases the shortest
677 * path by no more than 'k' operations. Currently, we count each
678 * instruction (alu, move, or cond move) as 1 evaluation.
679 * The parameter k is specified by OPT\_Options.COND_MOVE_CUTOFF.
680 *
681 * <p> In the example above, since we've increased the shortest path by
682 * 6 instructions, we will only perform the transformation if k >= 7.
683 *
684 * <p> TODO items
685 * <ul>
686 * <li> consider smarter cost heuristics
687 * <li> enhance downstream code generation to avoid redundant evaluation
688 * of condition codes.
689 * </ul>
690 *
691 * @param ir governing IR
692 * @param bb basic block of cb
693 * @param cb conditional branch instruction
694 * @return true if the transformation succeeds, false otherwise
695 */
696 private boolean generateCondMove(IR ir, BasicBlock bb, Instruction cb) {
697 final boolean VERBOSE=false;
698 if (!VM.BuildForIA32) return false;
699 if (!IfCmp.conforms(cb)) return false;
700
701 if (VERBOSE) System.out.println("CondMove: Looking to optimize "+cb);
702 // Don't generate CMOVs for branches that can be folded.
703 if (IfCmp.getVal1(cb).isConstant() && IfCmp.getVal2(cb).isConstant()) {
704 if (VERBOSE) System.out.println("CondMove: fail - could be folded");
705 return false;
706 }
707
708 // see if bb is the root of an if-then-else.
709 Diamond diamond = Diamond.buildDiamond(bb);
710 if (diamond == null) {
711 if (VERBOSE) System.out.println("CondMove: fail - no diamond");
712 return false;
713 }
714 BasicBlock taken = diamond.getTaken();
715 BasicBlock notTaken = diamond.getNotTaken();
716
717 // do not perform the transformation if either branch of the diamond
718 // has a taboo instruction (eg., a PEI, store or divide).
719 if (taken != null && hasCMTaboo(taken)) {
720 if (VERBOSE) System.out.println("CondMove: fail - taken branch has taboo instruction");
721 return false;
722 }
723 if (notTaken != null && hasCMTaboo(notTaken)) {
724 if (VERBOSE) System.out.println("CondMove: fail - not taken branch has taboo instruction");
725 return false;
726 }
727
728 ConditionOperand cond = IfCmp.getCond(cb);
729
730 // Do not generate when we don't know the branch probability or
731 // when branch probability is high. CMOVs reduce performance of
732 // the out-of-order engine (Intel Optimization Guide -
733 // Assembly/Compiler Coding Rule 2).
734 // Ignore in the case of an abs() method as we can create tighter
735 // instructions.
736 BranchProfileOperand profile = IfCmp.getBranchProfile(cb);
737 if ((Math.abs(profile.takenProbability - 0.5) >= ir.options.CONTROL_WELL_PREDICTED_CUTOFF) &&
738 !(cb.position != null && cb.position.method.getName() == ABS && cond.isFLOATINGPOINT())) {
739 if (VERBOSE)
740 System.out.println("CondMove: fail - branch could be well predicted by branch predictor: "+
741 profile.takenProbability);
742 return false;
743 }
744
745 // if we must generate FCMP, make sure the condition code is OK
746 if (cond.isFLOATINGPOINT()) {
747 if (!fpConditionOK(cond)) {
748 // Condition not OK, but maybe if we flip the operands
749 if (!fpConditionOK(cond.flipOperands())) {
750 // still not ok so flip operands back
751 cond.flipOperands();
752 // give up or for SSE2 check if this is a floating point compare
753 // controlling just floating point moves
754 if (!VM.BuildForSSE2Full || hasFloatingPointDef(taken, true) || hasFloatingPointDef(notTaken, true)) {
755 if (VERBOSE) System.out.println("CondMove: fail - fp condition not OK: "+cond);
756 return false;
757 }
758 } else {
759 // flip operands
760 Operand val1 = IfCmp.getVal1(cb);
761 Operand val2 = IfCmp.getVal2(cb);
762 IfCmp.setVal1(cb, val2);
763 IfCmp.setVal2(cb, val1);
764 }
765 }
766 }
767
768 if (!cond.isFLOATINGPOINT()) {
769 // Can only generate moves of floating point values for floating point
770 // compares or for unsigned compares in x87
771 if (VM.BuildForSSE2Full || !cond.isUNSIGNED()) {
772 if (hasFloatingPointDef(taken, false) || hasFloatingPointDef(notTaken, false)) {
773 if (VERBOSE)
774 System.out.println("CondMove: fail - not allowed integer condition controlling floating conditional move");
775 return false;
776 }
777 }
778 }
779
780 // For now, do not generate CMOVs for longs.
781 if (hasLongDef(taken) || hasLongDef(notTaken)) {
782 return false;
783 }
784
785 // count the number of expression evaluations in each side of the
786 // diamond
787 int takenCost = 0;
788 int notTakenCost = 0;
789 if (taken != null) takenCost = evaluateCost(taken);
790 if (notTaken != null) notTakenCost = evaluateCost(notTaken);
791
792 // evaluate whether it's profitable.
793 int shortestCost = Math.min(takenCost, notTakenCost);
794 int xformCost = 2 * (takenCost + notTakenCost);
795 int k = ir.options.CONTROL_COND_MOVE_CUTOFF;
796 if (xformCost - shortestCost > k) {
797 if (VERBOSE) System.out.println("CondMove: fail - cost too high");
798 return false;
799 }
800
801 // Perform the transformation!
802 doCondMove(ir, diamond, cb);
803 return true;
804 }
805
806 /**
807 * Is a specified condition operand 'safe' to transfer into an FCMP
808 * instruction?
809 */
810 private boolean fpConditionOK(ConditionOperand c) {
811 // FCOMI sets ZF, PF, and CF as follows:
812 // Compare Results ZF PF CF
813 // left > right 0 0 0
814 // left < right 0 0 1
815 // left == right 1 0 0
816 // UNORDERED 1 1 1
817 switch (c.value) {
818 case ConditionOperand.CMPL_EQUAL:
819 return false; // (ZF == 1) but ordered
820 case ConditionOperand.CMPL_NOT_EQUAL:
821 return false; // (ZF == 0) but unordered
822 case ConditionOperand.CMPG_LESS:
823 return false; // (CF == 1) but ordered
824 case ConditionOperand.CMPG_GREATER_EQUAL:
825 return false; // (CF == 0) but unordered
826 case ConditionOperand.CMPG_LESS_EQUAL:
827 return false; // (CF == 1 || ZF == 1) but ordered
828 case ConditionOperand.CMPG_GREATER:
829 return false; // (CF == 0 && ZF == 0) but unordered
830
831 case ConditionOperand.CMPL_GREATER:
832 return true; // (CF == 0 && ZF == 0) and ordered
833 case ConditionOperand.CMPL_LESS_EQUAL:
834 return true; // (CF == 1 || ZF == 1) and unordered
835 case ConditionOperand.CMPL_GREATER_EQUAL:
836 return true; // (CF == 0) and ordered
837 case ConditionOperand.CMPL_LESS:
838 return true; // (CF == 1) and unordered
839 default:
840 OptimizingCompilerException.UNREACHABLE();
841 return false; // keep jikes happy
842 }
843 }
844
845 /**
846 * Do any of the instructions in a basic block define a floating-point
847 * register?
848 *
849 * @param bb basic block to search
850 * @param invert invert the sense of the search
851 */
852 private static boolean hasFloatingPointDef(BasicBlock bb, boolean invert) {
853 if (bb == null) return false;
854 for (Enumeration<Instruction> e = bb.forwardRealInstrEnumerator(); e.hasMoreElements();) {
855 Instruction s = e.nextElement();
856 for (Enumeration<Operand> d = s.getDefs(); d.hasMoreElements();) {
857 Operand def = d.nextElement();
858 if (def.isRegister()) {
859 if (def.asRegister().getRegister().isFloatingPoint() != invert) return true;
860 }
861 }
862 }
863 return false;
864 }
865
866 /**
867 * Do any of the instructions in a basic block define a long
868 * register?
869 */
870 private boolean hasLongDef(BasicBlock bb) {
871 if (bb == null) return false;
872 for (Enumeration<Instruction> e = bb.forwardRealInstrEnumerator(); e.hasMoreElements();) {
873 Instruction s = e.nextElement();
874 for (Enumeration<Operand> d = s.getDefs(); d.hasMoreElements();) {
875 Operand def = d.nextElement();
876 if (def.isRegister()) {
877 if (def.asRegister().getRegister().isLong()) return true;
878 }
879 }
880 }
881 return false;
882 }
883
884 /**
885 * Do any of the instructions in a basic block preclude eliminating the
886 * basic block with conditional moves?
887 */
888 private boolean hasCMTaboo(BasicBlock bb) {
889
890 if (bb == null) return false;
891
892 // Note: it is taboo to assign more than once to any register in the
893 // block.
894 HashSet<Register> defined = new HashSet<Register>();
895
896 for (Enumeration<Instruction> e = bb.forwardRealInstrEnumerator(); e.hasMoreElements();) {
897 Instruction s = e.nextElement();
898 if (s.isBranch()) continue;
899 // for now, only the following opcodes are legal.
900 switch (s.operator.opcode) {
901 case INT_MOVE_opcode:
902 case REF_MOVE_opcode:
903 case DOUBLE_MOVE_opcode:
904 case FLOAT_MOVE_opcode:
905 case INT_ADD_opcode:
906 case REF_ADD_opcode:
907 case FLOAT_ADD_opcode:
908 case DOUBLE_ADD_opcode:
909 case INT_SUB_opcode:
910 case REF_SUB_opcode:
911 case FLOAT_SUB_opcode:
912 case DOUBLE_SUB_opcode:
913 case INT_MUL_opcode:
914 case FLOAT_MUL_opcode:
915 case DOUBLE_MUL_opcode:
916 case INT_NEG_opcode:
917 case FLOAT_NEG_opcode:
918 case DOUBLE_NEG_opcode:
919 case REF_SHL_opcode:
920 case INT_SHL_opcode:
921 case REF_SHR_opcode:
922 case INT_SHR_opcode:
923 case REF_USHR_opcode:
924 case INT_USHR_opcode:
925 case REF_AND_opcode:
926 case INT_AND_opcode:
927 case REF_OR_opcode:
928 case INT_OR_opcode:
929 case REF_XOR_opcode:
930 case INT_XOR_opcode:
931 case REF_NOT_opcode:
932 case INT_NOT_opcode:
933 case INT_2BYTE_opcode:
934 case INT_2USHORT_opcode:
935 case INT_2SHORT_opcode:
936 case FLOAT_2DOUBLE_opcode:
937 case DOUBLE_2FLOAT_opcode:
938 // these are OK.
939 break;
940 default:
941 return true;
942 }
943
944 // make sure no register is defined more than once in this block.
945 for (Enumeration<Operand> defs = s.getDefs(); defs.hasMoreElements();) {
946 Operand def = defs.nextElement();
947 if (VM.VerifyAssertions) VM._assert(def.isRegister());
948 Register r = def.asRegister().getRegister();
949 if (defined.contains(r)) return true;
950 defined.add(r);
951 }
952 }
953
954 return false;
955 }
956
957 /**
958 * Evaluate the cost of a basic block, in number of real instructions.
959 */
960 private int evaluateCost(BasicBlock bb) {
961 int result = 0;
962 for (Enumeration<Instruction> e = bb.forwardRealInstrEnumerator(); e.hasMoreElements();) {
963 Instruction s = e.nextElement();
964 if (!s.isBranch()) result++;
965 }
966 return result;
967 }
968
969 /**
970 * For each real non-branch instruction s in bb,
971 * <ul>
972 * <li> Copy s to s', and store s' in the returned array
973 * <li> Insert the function s->s' in the map
974 * </ul>
975 */
976 private Instruction[] copyAndMapInstructions(BasicBlock bb, HashMap<Instruction, Instruction> map) {
977 if (bb == null) return new Instruction[0];
978
979 int count = 0;
980 // first count the number of instructions
981 for (Enumeration<Instruction> e = bb.forwardRealInstrEnumerator(); e.hasMoreElements();) {
982 Instruction s = e.nextElement();
983 if (s.isBranch()) continue;
984 count++;
985 }
986 // now copy.
987 Instruction[] result = new Instruction[count];
988 int i = 0;
989 for (Enumeration<Instruction> e = bb.forwardRealInstrEnumerator(); e.hasMoreElements();) {
990 Instruction s = e.nextElement();
991 if (s.isBranch()) continue;
992 Instruction sprime = s.copyWithoutLinks();
993 result[i++] = sprime;
994 map.put(s, sprime);
995 }
996 return result;
997 }
998
999 /**
1000 * For each in a set of instructions, rewrite every def to use a new
1001 * temporary register. If a rewritten def is subsequently used, then
1002 * use the new temporary register instead.
1003 */
1004 private void rewriteWithTemporaries(Instruction[] set, IR ir) {
1005
1006 // Maintain a mapping holding the new name for each register
1007 HashMap<Register, Register> map = new HashMap<Register, Register>();
1008 for (Instruction s : set) {
1009 // rewrite the uses to use the new names
1010 for (Enumeration<Operand> e = s.getUses(); e.hasMoreElements();) {
1011 Operand use = e.nextElement();
1012 if (use != null && use.isRegister()) {
1013 Register r = use.asRegister().getRegister();
1014 Register temp = map.get(r);
1015 if (temp != null) {
1016 use.asRegister().setRegister(temp);
1017 }
1018 }
1019 }
1020
1021 if (VM.VerifyAssertions) VM._assert(s.getNumberOfDefs() == 1);
1022
1023 Operand def = s.getDefs().nextElement();
1024 RegisterOperand rDef = def.asRegister();
1025 RegisterOperand temp = ir.regpool.makeTemp(rDef);
1026 map.put(rDef.getRegister(), temp.getRegister());
1027 s.replaceOperand(def, temp);
1028 }
1029 }
1030
1031 /**
1032 * Insert each instruction in a list before instruction s
1033 */
1034 private void insertBefore(Instruction[] list, Instruction s) {
1035 for (Instruction x : list) {
1036 s.insertBefore(x);
1037 }
1038 }
1039
1040 /**
1041 * Perform the transformation to replace conditional branch with a
1042 * sequence using conditional moves.
1043 *
1044 * @param ir governing IR
1045 * @param diamond the IR diamond structure to replace
1046 * @param cb conditional branch instruction at the head of the diamond
1047 */
1048 private void doCondMove(IR ir, Diamond diamond, Instruction cb) {
1049 BasicBlock taken = diamond.getTaken();
1050 BasicBlock notTaken = diamond.getNotTaken();
1051
1052 // for each non-branch instruction s in the diamond,
1053 // copy s to a new instruction s'
1054 // and store a mapping from s to s'
1055 HashMap<Instruction, Instruction> takenInstructions = new HashMap<Instruction, Instruction>();
1056 Instruction[] takenInstructionList = copyAndMapInstructions(taken, takenInstructions);
1057
1058 HashMap<Instruction, Instruction> notTakenInstructions = new HashMap<Instruction, Instruction>();
1059 Instruction[] notTakenInstructionList = copyAndMapInstructions(notTaken, notTakenInstructions);
1060
1061 // Extract the values and condition from the conditional branch.
1062 Operand val1 = IfCmp.getVal1(cb);
1063 Operand val2 = IfCmp.getVal2(cb);
1064 ConditionOperand cond = IfCmp.getCond(cb);
1065
1066 // Copy val1 and val2 to temporaries, just in case they're defined in
1067 // the diamond. If they're not defined in the diamond, copy prop
1068 // should clean these moves up.
1069 RegisterOperand tempVal1 = ir.regpool.makeTemp(val1);
1070 Operator op = IRTools.getMoveOp(tempVal1.getType());
1071 cb.insertBefore(Move.create(op, tempVal1.copyRO(), val1.copy()));
1072 RegisterOperand tempVal2 = ir.regpool.makeTemp(val2);
1073 op = IRTools.getMoveOp(tempVal2.getType());
1074 cb.insertBefore(Move.create(op, tempVal2.copyRO(), val2.copy()));
1075
1076 // For each instruction in each temporary set, rewrite it to def a new
1077 // temporary, and insert it before the branch.
1078 rewriteWithTemporaries(takenInstructionList, ir);
1079 rewriteWithTemporaries(notTakenInstructionList, ir);
1080 insertBefore(takenInstructionList, cb);
1081 insertBefore(notTakenInstructionList, cb);
1082
1083 // For each register defined in the TAKEN branch, save a mapping to
1084 // the corresponding conditional move.
1085 HashMap<Register, Instruction> takenMap = new HashMap<Register, Instruction>();
1086
1087 // Now insert conditional moves to replace each instruction in the diamond.
1088 // First handle the taken branch.
1089 if (taken != null) {
1090 for (Enumeration<Instruction> e = taken.forwardRealInstrEnumerator(); e.hasMoreElements();) {
1091 Instruction s = e.nextElement();
1092 if (s.isBranch()) continue;
1093 Operand def = s.getDefs().nextElement();
1094 // if the register does not span a basic block, it is a temporary
1095 // that will now be dead
1096 if (def.asRegister().getRegister().spansBasicBlock()) {
1097 Instruction tempS = takenInstructions.get(s);
1098 RegisterOperand temp = (RegisterOperand) tempS.getDefs().nextElement();
1099 op = IRTools.getCondMoveOp(def.asRegister().getType());
1100 Instruction cmov =
1101 CondMove.create(op,
1102 def.asRegister(),
1103 tempVal1.copy(),
1104 tempVal2.copy(),
1105 cond.copy().asCondition(),
1106 temp.copy(),
1107 def.copy());
1108 takenMap.put(def.asRegister().getRegister(), cmov);
1109 cb.insertBefore(cmov);
1110 }
1111 s.remove();
1112 }
1113 }
1114 // For each register defined in the NOT-TAKEN branch, save a mapping to
1115 // the corresponding conditional move.
1116 HashMap<Register, Instruction> notTakenMap = new HashMap<Register, Instruction>();
1117 // Next handle the not taken branch.
1118 if (notTaken != null) {
1119 for (Enumeration<Instruction> e = notTaken.forwardRealInstrEnumerator(); e.hasMoreElements();) {
1120 Instruction s = e.nextElement();
1121 if (s.isBranch()) continue;
1122 Operand def = s.getDefs().nextElement();
1123 // if the register does not span a basic block, it is a temporary
1124 // that will now be dead
1125 if (def.asRegister().getRegister().spansBasicBlock()) {
1126 Instruction tempS = notTakenInstructions.get(s);
1127 RegisterOperand temp = (RegisterOperand) tempS.getDefs().nextElement();
1128
1129 Instruction prevCmov = takenMap.get(def.asRegister().getRegister());
1130 if (prevCmov != null) {
1131 // if this register was also defined in the taken branch, change
1132 // the previous cmov with a different 'False' Value
1133 CondMove.setFalseValue(prevCmov, temp.copy());
1134 notTakenMap.put(def.asRegister().getRegister(), prevCmov);
1135 } else {
1136 // create a new cmov instruction
1137 op = IRTools.getCondMoveOp(def.asRegister().getType());
1138 Instruction cmov =
1139 CondMove.create(op,
1140 def.asRegister(),
1141 tempVal1.copy(),
1142 tempVal2.copy(),
1143 cond.copy().asCondition(),
1144 def.copy(),
1145 temp.copy());
1146 cb.insertBefore(cmov);
1147 notTakenMap.put(def.asRegister().getRegister(), cmov);
1148 }
1149 }
1150 s.remove();
1151 }
1152 }
1153
1154 // Mutate the conditional branch into a GOTO.
1155 BranchOperand target = diamond.getBottom().makeJumpTarget();
1156 Goto.mutate(cb, GOTO, target);
1157
1158 // Delete a potential GOTO after cb.
1159 Instruction next = cb.nextInstructionInCodeOrder();
1160 if (next.operator != BBEND) {
1161 next.remove();
1162 }
1163
1164 // Recompute the CFG.
1165 diamond.getTop().recomputeNormalOut(ir); // fix the CFG
1166 }
1167
1168 /**
1169 * Attempt to generate a boolean compare opcode from a conditional branch.
1170 *
1171 * <pre>
1172 * 1) IF .. GOTO A replaced by BOOLEAN_CMP x=..
1173 * x = 0
1174 * GOTO B
1175 * A: x = 1
1176 * B: ...
1177 * </pre>
1178 *
1179 * <p> Precondition: <code>IfCmp.conforms(<i>cb</i>)</code>
1180 *
1181 *
1182 * @param ir governing IR
1183 * @param bb basic block of cb
1184 * @param cb conditional branch instruction
1185 * @return true if the transformation succeeds, false otherwise
1186 */
1187 private boolean generateBooleanCompare(IR ir, BasicBlock bb, Instruction cb, BasicBlock tb) {
1188
1189 if ((cb.operator() != INT_IFCMP) && (cb.operator() != REF_IFCMP)) {
1190 return false;
1191 }
1192 // make sure this is the last branch in the block
1193 if (cb.nextInstructionInCodeOrder().operator() != BBEND) {
1194 return false;
1195 }
1196 Operand val1 = IfCmp.getVal1(cb);
1197 Operand val2 = IfCmp.getVal2(cb);
1198 ConditionOperand condition = IfCmp.getCond(cb);
1199 // "not taken" path
1200 BasicBlock fb = cb.getBasicBlock().getNotTakenNextBlock();
1201 // make sure it's a diamond
1202 if (tb.getNumberOfNormalOut() != 1) {
1203 return false;
1204 }
1205 if (fb.getNumberOfNormalOut() != 1) {
1206 return false;
1207 }
1208 BasicBlock jb = fb.getNormalOut().nextElement(); // join block
1209 // make sure it's a diamond
1210 if (!tb.pointsOut(jb)) {
1211 return false;
1212 }
1213 Instruction ti = tb.firstRealInstruction();
1214 Instruction fi = fb.firstRealInstruction();
1215 // make sure the instructions in target blocks are either both moves
1216 // or both returns
1217 if (ti == null || fi == null) {
1218 return false;
1219 }
1220 if (ti.operator() != fi.operator()) {
1221 return false;
1222 }
1223 if (ti.operator != RETURN && ti.operator() != INT_MOVE) {
1224 return false;
1225 }
1226 //
1227 // WARNING: This code is currently NOT exercised!
1228 //
1229 if (ti.operator() == RETURN) {
1230 // make sure each of the target blocks contains only one instruction
1231 if (ti != tb.lastRealInstruction()) {
1232 return false;
1233 }
1234 if (fi != fb.lastRealInstruction()) {
1235 return false;
1236 }
1237 Operand tr = Return.getVal(ti);
1238 Operand fr = Return.getVal(fi);
1239 // make sure we're returning constants
1240 if (!(tr instanceof IntConstantOperand) || !(fr instanceof IntConstantOperand)) {
1241 return false;
1242 }
1243 int tv = ((IntConstantOperand) tr).value;
1244 int fv = ((IntConstantOperand) fr).value;
1245 if (!((tv == 1 && fv == 0) || (tv == 1 && fv == 0))) {
1246 return false;
1247 }
1248 RegisterOperand t = ir.regpool.makeTemp(TypeReference.Boolean);
1249 // Cases 1) and 2)
1250 if (tv == 0) {
1251 condition = condition.flipCode();
1252 }
1253 booleanCompareHelper(cb, t, val1.copy(), val2.copy(), condition);
1254 cb.insertAfter(Return.create(RETURN, t.copyD2U()));
1255 } else { // (ti.operator() == INT_MOVE)
1256 // make sure each of the target blocks only does the move
1257 if (ti != tb.lastRealInstruction() && ti.nextInstructionInCodeOrder().operator() != GOTO) {
1258 return false;
1259 }
1260 if (fi != fb.lastRealInstruction() && fi.nextInstructionInCodeOrder().operator() != GOTO) {
1261 return false;
1262 }
1263 RegisterOperand t = Move.getResult(ti);
1264 // make sure both moves are to the same register
1265 if (t.getRegister() != Move.getResult(fi).getRegister()) {
1266 return false;
1267 }
1268 Operand tr = Move.getVal(ti);
1269 Operand fr = Move.getVal(fi);
1270 // make sure we're assigning constants
1271 if (!(tr instanceof IntConstantOperand) || !(fr instanceof IntConstantOperand)) {
1272 return false;
1273 }
1274 int tv = ((IntConstantOperand) tr).value;
1275 int fv = ((IntConstantOperand) fr).value;
1276 if (!((tv == 1 && fv == 0) || (tv == 0 && fv == 1))) {
1277 return false;
1278 }
1279 // Cases 3) and 4)
1280 if (tv == 0) {
1281 condition = condition.flipCode();
1282 }
1283 booleanCompareHelper(cb, t.copyRO(), val1.copy(), val2.copy(), condition);
1284 Instruction next = cb.nextInstructionInCodeOrder();
1285 if (next.operator() == GOTO) {
1286 Goto.setTarget(next, jb.makeJumpTarget());
1287 } else {
1288 cb.insertAfter(jb.makeGOTO());
1289 }
1290 }
1291 // fixup CFG
1292 bb.deleteOut(tb);
1293 bb.deleteOut(fb);
1294 bb.insertOut(jb); // Note: if we processed returns,
1295 // jb is the exit node.
1296 return true;
1297 }
1298 }