org.jikesrvm.compilers.opt.controlflow
Class BranchOptimizations

java.lang.Object
  org.jikesrvm.compilers.opt.driver.CompilerPhase
      org.jikesrvm.compilers.opt.controlflow.BranchOptimizationDriver
          org.jikesrvm.compilers.opt.controlflow.BranchOptimizations

public final class BranchOptimizations
extends BranchOptimizationDriver

Perform simple peephole optimizations for branches.

ABS

private static final Atom ABS

Name of abs method used as a special case in conditional moves

mayReorderCode

private final boolean mayReorderCode

Is branch optimizations allowed to change the code order to create fallthrough edges (and thus merge basic blocks)? After we run code reordering, we disallow this transformation to avoid destroying the desired code order.

mayDuplicateCondBranches

private final boolean mayDuplicateCondBranches

Are we allowed to duplication conditional branches? Restricted until backedge yieldpoints are inserted to avoid creating irreducible control flow by duplicating a conditional branch in a loop header into a block outside the loop, thus creating two loop entry blocks.

BranchOptimizations

public BranchOptimizations(int level,
                           boolean mayReorderCode,
                           boolean mayDuplicateCondBranches)

Parameters:

level - the minimum optimization level at which the branch optimizations should be performed.

mayReorderCode - are we allowed to change the code order?

mayDuplicateCondBranches - are we allowed to duplicate conditional branches?

BranchOptimizations

public BranchOptimizations(int level,
                           boolean mayReorderCode,
                           boolean mayDuplicateCondBranches,
                           boolean simplify)

Parameters:

level - the minimum optimization level at which the branch optimizations should be performed.

mayReorderCode - are we allowed to change the code order?

mayDuplicateCondBranches - are we allowed to duplicate conditional branches?

simplify - simplify prior to optimizing?

optimizeBranchInstruction

protected boolean optimizeBranchInstruction(IR ir,
                                            Instruction s,
                                            BasicBlock bb)

This method actually does the work of attempting to peephole optimize a branch instruction. See Muchnick ~p.590

Specified by:

optimizeBranchInstruction in class BranchOptimizationDriver

Parameters:

ir - the containing IR

s - the branch instruction to optimize

bb - the containing basic block

Returns:

true if an optimization was applied, false otherwise

processGoto

private boolean processGoto(IR ir,
                            Instruction g,
                            BasicBlock bb)

Perform optimizations for a Goto.

Patterns:

    1)      GOTO A       replaced by  GOTO B
         A: GOTO B

    2)      GOTO A       replaced by  IF .. GOTO B
         A: IF .. GOTO B              GOTO C
         C: ...
    3)   GOTO next instruction eliminated
    4)      GOTO A       replaced by  GOTO B
         A: LABEL
            BBEND
         B:
    5)   GOTO BBn where BBn has exactly one in edge
         - move BBn immediately after the GOTO in the code order,
           so that pattern 3) will create a fallthrough
 

 
 Precondition: Goto.conforms(g)


Parameters:
ir - governing IR
g - the instruction to optimize
bb - the basic block holding g
Returns:
true if made a transformation

processConditionalBranch

private boolean processConditionalBranch(IR ir,
                                         Instruction cb,
                                         BasicBlock bb)

Perform optimizations for a conditional branch.

 1)   IF .. GOTO A          replaced by  IF .. GOTO B
      ...
   A: GOTO B
 2)   conditional branch to next instruction eliminated
 3)   IF (condition) GOTO A  replaced by  IF (!condition) GOTO B
      GOTO B                           A: ...
   A: ...
 4) special case to generate Boolean compare opcode
 5) special case to generate conditional move sequence
 6)   IF .. GOTO A       replaced by  IF .. GOTO B
   A: LABEL
      BBEND
   B:
 7)  fallthrough to a goto: replicate goto to enable other optimizations.
 

Precondition: IfCmp.conforms(cb)

Parameters:

ir - the governing IR

cb - the instruction to optimize

bb - the basic block holding if

Returns:

true iff made a transformation

processInlineGuard

private boolean processInlineGuard(IR ir,
                                   Instruction cb,
                                   BasicBlock bb)

Perform optimizations for an inline guard.

Precondition: InlineGuard.conforms(cb)

Parameters:

ir - the governing IR

cb - the instruction to optimize

bb - the basic block holding if

Returns:

true iff made a transformation

processTwoTargetConditionalBranch

private boolean processTwoTargetConditionalBranch(IR ir,
                                                  Instruction cb,
                                                  BasicBlock bb)

Perform optimizations for a two way conditional branch.

Precondition: IfCmp2.conforms(cb)

Parameters:

ir - the governing IR

cb - the instruction to optimize

bb - the basic block holding if

Returns:

true iff made a transformation

isFlipCandidate

private boolean isFlipCandidate(Instruction cb,
                                Instruction target)

Is a conditional branch a candidate to be flipped? See comment 3) of processConditionalBranch

Precondition: IfCmp.conforms(cb)

Parameters:

cb - the conditional branch instruction

target - the target instruction (real instruction) of the conditional branch

Returns:

boolean result

flipConditionalBranch

private void flipConditionalBranch(Instruction cb)

Flip a conditional branch and remove the trailing goto. See comment 3) of processConditionalBranch

Precondition isFlipCandidate(cb)

Parameters:

cb - the conditional branch instruction

booleanCompareHelper

private void booleanCompareHelper(Instruction cb,
                                  RegisterOperand res,
                                  Operand val1,
                                  Operand val2,
                                  ConditionOperand cond)

Generate a boolean operation opcode

 1) IF br != 0 THEN x=1 ELSE x=0       replaced by INT_MOVE x=br
    IF br == 0 THEN x=0 ELSE x=1
 2) IF br == 0 THEN x=1 ELSE x=0       replaced by BOOLEAN_NOT x=br
    IF br != 0 THEN x=0 ELSE x=1
 3) IF v1 ~ v2 THEN x=1 ELSE x=0       replaced by BOOLEAN_CMP x=v1,v2,~
 

Parameters:

cb - conditional branch instruction

res - the operand for result

val1 - value being compared

val2 - value being compared with

cond - comparison condition

generateCondMove

private boolean generateCondMove(IR ir,
                                 BasicBlock bb,
                                 Instruction cb)

Attempt to generate a straight-line sequence using conditional move instructions, to replace a diamond control flow structure.

Suppose we have the following code, where e{n} is an expression:

 if (a op b) {
   x = e2;
   y = e3;
 } else {
   z = e4;
   x = e5;
 }
 

We would transform this to:

 t1 = a;
 t2 = b;
 t3 = e2;
 t4 = e3;
 t5 = e4;
 t6 = e5;
 COND MOVE [if (t1 op t2) x := t3 else x := t6 ];
 COND MOVE [if (t1 op t2) y := t4 else y := y];
 COND MOVE [if (t1 op t2) z := z  else z := t5];
 

Note that we rely on other optimizations (eg. copy propagation) to clean up some of this unnecessary mess.

Note that in this example, we've increased the shortest path by 2 expression evaluations, 2 moves, and 3 cond moves, but eliminated one conditional branch.

We apply a cost heuristic to guide this transformation: We will eliminate a conditional branch iff it increases the shortest path by no more than 'k' operations. Currently, we count each instruction (alu, move, or cond move) as 1 evaluation. The parameter k is specified by OPT\_Options.COND_MOVE_CUTOFF.

In the example above, since we've increased the shortest path by 6 instructions, we will only perform the transformation if k >= 7.

TODO items

• consider smarter cost heuristics
• enhance downstream code generation to avoid redundant evaluation of condition codes.

Parameters:

ir - governing IR

bb - basic block of cb

cb - conditional branch instruction

Returns:

true if the transformation succeeds, false otherwise

fpConditionOK

private boolean fpConditionOK(ConditionOperand c)

Is a specified condition operand 'safe' to transfer into an FCMP instruction?

hasFloatingPointDef

private static boolean hasFloatingPointDef(BasicBlock bb,
                                           boolean invert)

Do any of the instructions in a basic block define a floating-point register?

Parameters:

bb - basic block to search

invert - invert the sense of the search

hasLongDef

private boolean hasLongDef(BasicBlock bb)

Do any of the instructions in a basic block define a long register?

hasCMTaboo

private boolean hasCMTaboo(BasicBlock bb)

Do any of the instructions in a basic block preclude eliminating the basic block with conditional moves?

evaluateCost

private int evaluateCost(BasicBlock bb)

Evaluate the cost of a basic block, in number of real instructions.

copyAndMapInstructions

private Instruction[] copyAndMapInstructions(BasicBlock bb,
                                             HashMap<Instruction,Instruction> map)

For each real non-branch instruction s in bb,

• Copy s to s', and store s' in the returned array
• Insert the function s->s' in the map

rewriteWithTemporaries

private void rewriteWithTemporaries(Instruction[] set,
                                    IR ir)

For each in a set of instructions, rewrite every def to use a new temporary register. If a rewritten def is subsequently used, then use the new temporary register instead.

insertBefore

private void insertBefore(Instruction[] list,
                          Instruction s)

Insert each instruction in a list before instruction s

doCondMove

private void doCondMove(IR ir,
                        Diamond diamond,
                        Instruction cb)

Perform the transformation to replace conditional branch with a sequence using conditional moves.

Parameters:

ir - governing IR

diamond - the IR diamond structure to replace

cb - conditional branch instruction at the head of the diamond

generateBooleanCompare

private boolean generateBooleanCompare(IR ir,
                                       BasicBlock bb,
                                       Instruction cb,
                                       BasicBlock tb)

Attempt to generate a boolean compare opcode from a conditional branch.

 1)   IF .. GOTO A          replaced by  BOOLEAN_CMP x=..
      x = 0
      GOTO B
   A: x = 1
   B: ...
 

Precondition: IfCmp.conforms(cb)

Parameters:

ir - governing IR

bb - basic block of cb

cb - conditional branch instruction

Returns:

true if the transformation succeeds, false otherwise