scale.score.trans
Class LICM

java.lang.Object
  scale.score.trans.Optimization
      scale.score.trans.LICM

public class LICM
extends Optimization

This transformation moves CFG nodes to the outer-most basic block in which they may be executed correctly.

$Id: LICM.java,v 1.79 2007-02-28 18:00:36 burrill Exp $

Copyright 2008 by the Scale Compiler Group,
Department of Computer Science
University of Massachusetts,
Amherst MA. 01003, USA
All Rights Reserved.

Using the SSA use-def links, CFG nodes are moved into the outer-most basic block in which their dependencies are available. In order to preserve the program semantics, only CFG nodes containing stores into temporary variables are moved.

The algorithm does a depth first visit to all the CFG nodes. The nodes in each basic block are numbered with the basic blocks number. The basic block number starts at 0 and is incremented each time a new basic block is encountered. Because the CFG is in SSA form, we know that the definition for every dependency has already been encountered when we reach any particular CFG node. (We exclude Phi functions.) Consequently, we can simply compare the current basic block number to the basic block number of the defining CFG node for every dependency. If it is different, then the CFG node is moved to the end of the basic block with the highest number containing the definition of a dependency that is at the same or higher loop nesting depth. This results in loop invariant code being moved out of loops and still preserves the SSA form of the CFG.

This optimization will also convert a divide to a multiply by the reciprocal if the divisor is loop invariant, the operands are floating point, and the user has allowed operations with floating point operands to be re-arranged. The calculation of the reciprocal is moved out of the loop.

It is possible, though unlikely, for a transformation to reduce register pressure. If the expression references more than one variable that are referenced nowhere else in the scope of the moved expression, register pressure will be reduced. If there is more than one variable that is referenced in other expressions, register pressure will increase.

A transformation is legal if:

• the expression is an optimization candidate,
• the expression does not contain a function call,
• the expression does not reference a global variable,
• the expression is not va_arg(), and
• the expression is loop invariant.

It is beneficial if:

• the cost of evaluating the expression is greater than minimumExecutionCost,
• the expression is not the add of an address and a constant, and
• the size of the loop is less than a heuristic based upon the number of uses of the expression and maxLoopSize.

Field Summary

static boolean	classTrace True if traces are to be performed.
static int	maxLoopSize Maximum loop size allowed for a single use of a loop invariant expression.
static boolean	useHeuristics If true, use heuristics that prune the cases where the optimization is applied.

Fields inherited from class scale.score.trans.Optimization

dChanged, fpReorder, hasDummyAliases, IN_SSA, minimumExecutionCost, NA_SSA, NO_SSA, rChanged, scribble, signedIntsWrapOnOverflow, trace, un, unsafe, unsignedIntsWrapOnOverflow, VALID_SSA

Constructor Summary

LICM(Scribble scribble)
Move the LOOP INVARIANT nodes of the CFG.

Method Summary

static int	funnyLoops() Return the number of non-standard loop structures encountered.
static int	movedExprs() Return the number of expressions moved.
static int	movedNAExprs() Return the number of expressions moved.
static int	newCFGNodes() Return the number of new nodes created.
void	perform() Perform LoopHeaderChord Invariant Code Motion.
static int	reusedExpr() Return the number of expressions re-used.

Methods inherited from class scale.score.trans.Optimization

assertTrace, assertTrace, assertTrace, assertTrace, assertTrace, genTemp, insertStores, requiresSSA, setTrace, sort

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

classTrace

public static boolean classTrace

True if traces are to be performed.

useHeuristics

public static boolean useHeuristics

If true, use heuristics that prune the cases where the optimization is applied.

maxLoopSize

public static int maxLoopSize

Maximum loop size allowed for a single use of a loop invariant expression.

Constructor Detail

LICM

public LICM(Scribble scribble)

Move the LOOP INVARIANT nodes of the CFG.

Parameters:

scribble - the CFG

Method Detail

movedExprs

public static int movedExprs()

Return the number of expressions moved.

movedNAExprs

public static int movedNAExprs()

Return the number of expressions moved.

funnyLoops

public static int funnyLoops()

Return the number of non-standard loop structures encountered.

reusedExpr

public static int reusedExpr()

Return the number of expressions re-used.

newCFGNodes

public static int newCFGNodes()

Return the number of new nodes created.

perform

public void perform()

Perform LoopHeaderChord Invariant Code Motion. This modifies the CFG by moving loop invariant expressions out of the loop. The value of the expression is saved in a temporary and that temporary is used inside of the loop. Some expressions are only moved if they are used in the inner-most loop so that register pressure is not un-duly increased.

Specified by:

perform in class Optimization