BranchOptimizations (Jikes RVM API)

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.

Field Summary

Fields
Modifier and Type	Field and Description
`private static Atom`	`ABS` Name of abs method used as a special case in conditional moves
`private boolean`	`mayDuplicateCondBranches` Are we allowed to duplication conditional branches?
`private boolean`	`mayReorderCode` Is branch optimizations allowed to change the code order to create fallthrough edges (and thus merge basic blocks)?

Fields inherited from class org.jikesrvm.compilers.opt.driver.CompilerPhase
container

Constructor Summary

Constructors
Constructor and Description
`BranchOptimizations(int level, boolean mayReorderCode, boolean mayDuplicateCondBranches)`
`BranchOptimizations(int level, boolean mayReorderCode, boolean mayDuplicateCondBranches, boolean simplify)`

Method Summary

All Methods Static Methods Instance Methods Concrete Methods
Modifier and Type	Method and Description
`private void`	`booleanCompareHelper(Instruction cb, RegisterOperand res, Operand val1, Operand val2, ConditionOperand cond)` Generate a boolean operation opcode 1) IF br !
`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
`private void`	`doCondMove(IR ir, Diamond diamond, Instruction cb)` Perform the transformation to replace conditional branch with a sequence using conditional moves.
`private int`	`evaluateCost(BasicBlock bb)` Evaluates the cost of a basic block, in number of real instructions excluding branches.
`private void`	`flipConditionalBranch(Instruction cb)` Flip a conditional branch and remove the trailing goto.
`private boolean`	`fpConditionOK(ConditionOperand c)` Is a specified condition operand 'safe' to transfer into an FCMP instruction?
`private boolean`	`generateBooleanCompare(IR ir, BasicBlock bb, Instruction cb, BasicBlock tb)` Attempt to generate a boolean compare opcode from a conditional branch.
`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.
`private boolean`	`hasCMTaboo(BasicBlock bb)` Do any of the instructions in a basic block preclude eliminating the basic block with conditional moves?
`private static boolean`	`hasFloatingPointDef(BasicBlock bb, boolean invert)` Do any of the instructions in a basic block define a floating-point register?
`private boolean`	`hasLongDef(BasicBlock bb)` Do any of the instructions in a basic block define a long register?
`private void`	`insertBefore(Instruction[] list, Instruction s)` Inserts each instruction in a list before another instruction.
`private boolean`	`isFlipCandidate(Instruction cb, Instruction target)` Is a conditional branch a candidate to be flipped?
`protected boolean`	`optimizeBranchInstruction(IR ir, Instruction s, BasicBlock bb)` This method actually does the work of attempting to peephole optimize a branch instruction.
`private boolean`	`processConditionalBranch(IR ir, Instruction cb, BasicBlock bb)` Perform optimizations for a conditional branch.
`private boolean`	`processGoto(IR ir, Instruction g, BasicBlock bb)` Perform optimizations for a Goto.
`private boolean`	`processInlineGuard(IR ir, Instruction cb, BasicBlock bb)` Perform optimizations for an inline guard.
`private boolean`	`processTwoTargetConditionalBranch(IR ir, Instruction cb, BasicBlock bb)` Perform optimizations for a two way conditional branch.
`private void`	`rewriteWithTemporaries(Instruction[] set, IR ir)` For each in a set of instructions, rewrite every def to use a new temporary register.

Methods inherited from class org.jikesrvm.compilers.opt.controlflow.BranchOptimizationDriver
applyPeepholeBranchOpts, firstLabelFollowing, firstRealInstructionFollowing, getName, maximizeBasicBlocks, newExecution, perform, perform, printingEnabled, removeUnreachableCode, shouldPerform

Methods inherited from class org.jikesrvm.compilers.opt.driver.CompilerPhase
dumpIR, dumpIR, getClassConstructor, getCompilerPhaseConstructor, getCompilerPhaseConstructor, performPhase, reportAdditionalStats, setContainer, verify

Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

- Field Detail
  - 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.
- Constructor Detail
  - 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?
- Method Detail
  - 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?
    
    Parameters:
    
    c - operand to check
    
    Returns:
    
    whether the operand is 'safe'
  - 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 - true if and only if the sense of the search should be inverted
    
    Returns:
    
    whether a floating point register (or a non-floating point register) is defined in the block
  - hasLongDef
```
private boolean hasLongDef(BasicBlock bb)
```
    Do any of the instructions in a basic block define a long register?
    
    Parameters:
    
    bb - basic block to search
    
    Returns:
    
    whether an instruction in the block defines 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?
    
    Parameters:
    
    bb - the block to check
    
    Returns:
    
    whether the block must be retained
  - evaluateCost
```
private int evaluateCost(BasicBlock bb)
```
    Evaluates the cost of a basic block, in number of real instructions excluding branches.
    
    Parameters:
    
    bb - the block to evaluate
    
    Returns:
    
    the number of real instruction, excluding branches.
  - 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
    Parameters:
    
    bb - the basic block to process
    
    map - map for instructions (must be empty at the start)
    
    Returns:
    
    the copied instructions (which are not linked into an instruction list)
  - 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.
    
    Parameters:
    
    set - the instructions to rewrite
    
    ir - the IR that will provide the temporary registers
  - insertBefore
```
private void insertBefore(Instruction[] list,
                          Instruction s)
```
    Inserts each instruction in a list before another instruction.
    
    Parameters:
    
    list - the instructions to insert before the other instruction
    
    s - the instruction before which the insertion should be done
  - 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
    
    tb - target block the branch instruction
    
    Returns:
    
    true if and only if the transformation succeeds

Class BranchOptimizations

Field Summary

Fields inherited from class org.jikesrvm.compilers.opt.driver.CompilerPhase

Constructor Summary

Method Summary

Methods inherited from class org.jikesrvm.compilers.opt.controlflow.BranchOptimizationDriver

Methods inherited from class org.jikesrvm.compilers.opt.driver.CompilerPhase

Methods inherited from class java.lang.Object

Field Detail

ABS

mayReorderCode

mayDuplicateCondBranches

Constructor Detail

BranchOptimizations

BranchOptimizations

Method Detail

optimizeBranchInstruction

processGoto

processConditionalBranch

processInlineGuard

processTwoTargetConditionalBranch

isFlipCandidate

flipConditionalBranch

booleanCompareHelper

generateCondMove

fpConditionOK

hasFloatingPointDef

hasLongDef

hasCMTaboo

evaluateCost

copyAndMapInstructions

rewriteWithTemporaries

insertBefore

doCondMove

generateBooleanCompare