scale.score.trans
Class URJ

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

public class URJ
extends Optimization

This class performs unroll & jam.

$Id: URJ.java,v 1.123 2007-10-29 13:42:27 burrill Exp $

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

For each loop, we first try to flatten it. If that fails, we next try to unroll it as a for-loop. If that fails, we try to unroll it as a while-loop. If that fails, we give up. The following is the decision tree for this process. By flattening, we mean unrolling the loop by its known iteration count, removing the exit test, and removing the back edge of the loop.

For target architectures that have instruction blocks of fixed size (e.g., Trips), an attempt is made to unroll or flatten so that the blocks are filled.

Field Summary

static boolean	classTrace True if traces are to be performed.
static int	defaultMinUnrollFactor Controls the number of times a loop is unrolled.
static boolean	doPropagation Do back propagation of induction variables after unrolling.
static boolean	inhibitFlattenLoops If true, inhibits loop flattening.
static boolean	inhibitForLoops If true, inhibits for-loop unrolling.
static boolean	inhibitWhileLoops If true, inhibits while-loop unrolling.
static int	maxLoopBlocks The maximum size, in "blocks", of an unrolled or flattened loop when using instruction estimates.
static int	maxLoopCFGNodes The maximum size, in CFG nodes, of an unrolled or flattened loop.
static double	minLoopHeaderExecRatio If path profiling is used, this is the minimum execution ratio that a loop header needs in order for its loop to be unrolled.
static int	minNewAvgTripCount If path profiling is used and the exact loop iteration is not known, this is the minimum allowed trip count of the unrolled loop.
static boolean	peel True if loop peeling is to be performed.
static boolean	useHeuristics If true, use heuristics that prune the cases where the optimization is applied.
static boolean	useInstCountEstimates If true, use estimated instruction counts instead of node counts.

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

URJ(Scribble scribble)

Method Summary

static int	flattened() Return the number of loops that were flattened.
java.lang.String	getUnrollLoopKindString(int loopKind) Convert the unroll status to a string for display.
static int	newCFGNodes() Return the number of new nodes created.
void	perform() Perform the optimization.
int	requiresSSA() Return whether this optimization requires that the CFG be in SSA form.
static int	unrolled() Return the number of for loops that were unrolled.
static int	unrolledWhile() Return the number of while loops that were unrolled.

Methods inherited from class scale.score.trans.Optimization

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

Methods inherited from class java.lang.Object

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

Field Detail

doPropagation

public static boolean doPropagation

Do back propagation of induction variables after unrolling.

maxLoopCFGNodes

public static int maxLoopCFGNodes

The maximum size, in CFG nodes, of an unrolled or flattened loop. Default is 256.

maxLoopBlocks

public static int maxLoopBlocks

The maximum size, in "blocks", of an unrolled or flattened loop when using instruction estimates. Default is 4.

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.

useInstCountEstimates

public static boolean useInstCountEstimates

If true, use estimated instruction counts instead of node counts. Instruction count estimates are not accurate for all target architectures. Instead of using maxLoopCFGNodes, the value of maxLoopBlocks×Machine.getMaxBlockSize() is used determine the maximum loop size.

peel

public static boolean peel

True if loop peeling is to be performed.

defaultMinUnrollFactor

public static int defaultMinUnrollFactor

Controls the number of times a loop is unrolled. This is the default number of times to unroll a loop when the loop iteration count is unknown. This value must be greater than 1.

inhibitWhileLoops

public static boolean inhibitWhileLoops

If true, inhibits while-loop unrolling.

inhibitForLoops

public static boolean inhibitForLoops

If true, inhibits for-loop unrolling.

inhibitFlattenLoops

public static boolean inhibitFlattenLoops

If true, inhibits loop flattening.

minLoopHeaderExecRatio

public static double minLoopHeaderExecRatio

If path profiling is used, this is the minimum execution ratio that a loop header needs in order for its loop to be unrolled. The execution ratio is the ratio of the execution frequency of a loop header to the flow (using the unit metric) of the entire program.

minNewAvgTripCount

public static int minNewAvgTripCount

If path profiling is used and the exact loop iteration is not known, this is the minimum allowed trip count of the unrolled loop.

Constructor Detail

URJ

public URJ(Scribble scribble)

Method Detail

unrolled

public static int unrolled()

Return the number of for loops that were unrolled.

unrolledWhile

public static int unrolledWhile()

Return the number of while loops that were unrolled.

flattened

public static int flattened()

Return the number of loops that were flattened.

newCFGNodes

public static int newCFGNodes()

Return the number of new nodes created.

perform

public void perform()

Description copied from class: Optimization

Perform the optimization. Each optimization must specify

• if the CFG is left in valid SSA form
• if the dominance information is still valid
• if the variable reference information is still valid

after it completes. The Scribble class provides methods that may be used to sepcify this information.

Specified by:

perform in class Optimization

requiresSSA

public int requiresSSA()

Return whether this optimization requires that the CFG be in SSA form. It returns either

NO_SSA

the CFG must not be in SSA form,

IN_SSA

the CFG must be in SSA form,

VALID_SSA

the CFG must be in valid SSA form, or

NA_SSA

the CFG does not need to be in valid SSA form.

Overrides:

requiresSSA in class Optimization

getUnrollLoopKindString

public java.lang.String getUnrollLoopKindString(int loopKind)

Convert the unroll status to a string for display.