LoopTools

java.lang.Object
- cetus.analysis.LoopTools

```
public class LoopTools
extends java.lang.Object
```
Provides tools for querying information related to For Loop objects

Method Summary

Methods
Modifier and Type	Method and Description
`static void`	`addLoopName(Program program)` Adds a unique loop name to each for loop.
`static java.util.LinkedList<Loop>`	`calculateInnerLoopNest(Loop enclosing_loop)` Calculate the nest of loops enclosed within the given loop
`static java.util.LinkedList<Loop>`	`calculateLoopNest(Loop loop)` Calculate the loop nest of this loop
`static boolean`	`checkDataDependenceEligibility(Loop loop)` Checks the eligibility of a certain loop for data dependence testing Eligibility checks can be added or removed to increase the scope of dependence testing
`static java.util.Set<Expression>`	`collectScalarDependences(Loop l)` Returns symbols that may cause data dependences with the specified loop.
`static boolean`	`containsBreakStatement(Loop loop)` Check if the loop contains only a break statement modifier
`static boolean`	`containsControlFlowModifier(Loop loop)` Check whether the loop contains control constructs that cause it to terminate before the loop condition is reached.
`static boolean`	`containsControlFlowModifierOtherThanBreakStmt(Loop loop)`
`static boolean`	`containsFunctionCall(Loop loop)` Checks if loop body contains a function call
`static boolean`	`containsLoop(Loop loop)` Check if loop body contains another loop
`static boolean`	`containsOnlyParallelizableCall(Loop loop)` Check if the loop contains a function call that can be tested for data dependences/that can be eventually parallelized
`static java.util.List<Loop>`	`extractOutermostDependenceTestEligibleLoops(Traversable t)`
`static java.util.LinkedList<Loop>`	`getCommonNest(Loop loop1, Loop loop2)` Get common enclosing loops for loop1 and loop2
`static Expression`	`getIncrementExpression(Loop loop)` Get the expression that represents the actual increment value for the loop.
`static Expression`	`getIndexVariable(Loop loop)` Get loop index variable, if loop is canonical
`static Symbol`	`getLoopIndexSymbol(Loop loop)` Get symbol of loop index, index variable is identified from step expression for loop
`static java.lang.String`	`getLoopName(Statement loop)` Returns the loop name inserted by Cetus.
`static Expression`	`getLowerBoundExpression(Loop loop)` Returns a simplified lower bound expression for the loop
`static Loop`	`getOutermostLoop(Loop loop)` Get the outermost loop for the nest that surrounds the input loop
`static long`	`getReuseDistance(Loop loop, ArrayAccess e1, ArrayAccess e2)` A simple implementation based on the Euclidean GCD algorithm to calculate the distance in terms of loop iterations between subscripts of dependent arrays.
`static Expression`	`getUpperBoundExpression(Loop loop)` Returns a simplified upper bound expression for the loop
`static boolean`	`isCanonical(Loop loop)` Check if loop is canonical, FORTRAN DO Loop format
`static boolean`	`isIncrementConstant(Loop loop)` Get loop increment expression and check if it is an integer constant
`static boolean`	`isIncrementEligible(Loop loop)` Returns true if the loop increment is an integer constant value.
`static boolean`	`isIndexInvariant(Loop loop, Identifier id)` Check if the index variable is defined within the loop body
`static boolean`	`isInnermostLoop(Loop loop)` Checks whether this loop contains any inner loops
`static boolean`	`isLoopInvariant(Loop loop, Expression e)` Check if the given expression is loop invariant
`static boolean`	`isLowerBoundConstant(Loop loop)` Check if the lower bound expression is an integer constant
`static boolean`	`isOutermostLoop(Loop loop)` Checks whether this loop is enclosed by any outer loops
`static boolean`	`isPerfectNest(Loop loop)` Check if this loop and inner loops form a perfect nest
`static boolean`	`isPrivate(Symbol s, Loop l)` Check if the input symbol is marked as private to the loop by the Privatization pass.
`static boolean`	`isReduction(Symbol s, Loop l)` Check if the input symbol is marked as reduction for the loop by the Reduction pass.
`static boolean`	`isUpperBoundConstant(Loop loop)` Check if loop upper bound is an integer constant
`static Expression`	`replaceSymbolicLowerBound(Loop loop)` Replaces symbolic values in loop lower bound with information obtained from range analysis.
`static Expression`	`replaceSymbolicLowerBound(Loop loop, RangeDomain loop_rd)` Replaces symbolic values in loop lower bound with information obtained from range analysis.
`static Expression`	`replaceSymbolicUpperBound(Loop loop)` Replaces symbolic values in loop upper bound with information obtained from range analysis.
`static Expression`	`replaceSymbolicUpperBound(Loop loop, RangeDomain loop_rd)` Replaces symbolic values in loop upper bound with information obtained from range analysis.
`static boolean`	`scalarDependencePossible(Loop l)` Check for scalars that are not privatizable or reduction variables
`static java.lang.String`	`toControlString(Loop loop)` Returns the control structure of the specified loop in string.

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

- Method Detail
  - getIncrementExpression
```
public static Expression getIncrementExpression(Loop loop)
```
    Get the expression that represents the actual increment value for the loop. This might be an integer constant or a symbolic value.
  - isIncrementConstant
```
public static boolean isIncrementConstant(Loop loop)
```
    Get loop increment expression and check if it is an integer constant
  - getIndexVariable
```
public static Expression getIndexVariable(Loop loop)
```
    Get loop index variable, if loop is canonical
  - getLowerBoundExpression
```
public static Expression getLowerBoundExpression(Loop loop)
```
    Returns a simplified lower bound expression for the loop
  - isLowerBoundConstant
```
public static boolean isLowerBoundConstant(Loop loop)
```
    Check if the lower bound expression is an integer constant
    
    Parameters:
    loop -
    
    Returns:
    true if it is, false otherwise.
  - getUpperBoundExpression
```
public static Expression getUpperBoundExpression(Loop loop)
```
    Returns a simplified upper bound expression for the loop
    
    Parameters:
    loop -
    
    Returns:
    the upper bound of the loop.
  - isUpperBoundConstant
```
public static boolean isUpperBoundConstant(Loop loop)
```
    Check if loop upper bound is an integer constant
  - calculateLoopNest
```
public static java.util.LinkedList<Loop> calculateLoopNest(Loop loop)
```
    Calculate the loop nest of this loop
  - getCommonNest
```
public static java.util.LinkedList<Loop> getCommonNest(Loop loop1,
                                       Loop loop2)
```
    Get common enclosing loops for loop1 and loop2
  - isCanonical
```
public static boolean isCanonical(Loop loop)
```
    Check if loop is canonical, FORTRAN DO Loop format
  - containsFunctionCall
```
public static boolean containsFunctionCall(Loop loop)
```
    Checks if loop body contains a function call
  - containsOnlyParallelizableCall
```
public static boolean containsOnlyParallelizableCall(Loop loop)
```
    Check if the loop contains a function call that can be tested for data dependences/that can be eventually parallelized
  - isPerfectNest
```
public static boolean isPerfectNest(Loop loop)
```
    Check if this loop and inner loops form a perfect nest
  - containsLoop
```
public static boolean containsLoop(Loop loop)
```
    Check if loop body contains another loop
  - isIndexInvariant
```
public static boolean isIndexInvariant(Loop loop,
                       Identifier id)
```
    Check if the index variable is defined within the loop body
  - isLoopInvariant
```
public static boolean isLoopInvariant(Loop loop,
                      Expression e)
```
    Check if the given expression is loop invariant
  - collectScalarDependences
```
public static java.util.Set<Expression> collectScalarDependences(Loop l)
```
    Returns symbols that may cause data dependences with the specified loop.
    
    Parameters:
    l - the loop to be analyzed.
    
    Returns:
    the set of involved symbols.
  - scalarDependencePossible
```
public static boolean scalarDependencePossible(Loop l)
```
    Check for scalars that are not privatizable or reduction variables
  - isInnermostLoop
```
public static boolean isInnermostLoop(Loop loop)
```
    Checks whether this loop contains any inner loops
  - isOutermostLoop
```
public static boolean isOutermostLoop(Loop loop)
```
    Checks whether this loop is enclosed by any outer loops
  - getOutermostLoop
```
public static Loop getOutermostLoop(Loop loop)
```
    Get the outermost loop for the nest that surrounds the input loop
  - containsControlFlowModifier
```
public static boolean containsControlFlowModifier(Loop loop)
```
    Check whether the loop contains control constructs that cause it to terminate before the loop condition is reached. Check only at one nesting level, no need to check for control flow constructs in nested loops
  - containsBreakStatement
```
public static boolean containsBreakStatement(Loop loop)
```
    Check if the loop contains only a break statement modifier
  - containsControlFlowModifierOtherThanBreakStmt
```
public static boolean containsControlFlowModifierOtherThanBreakStmt(Loop loop)
```
  - calculateInnerLoopNest
```
public static java.util.LinkedList<Loop> calculateInnerLoopNest(Loop enclosing_loop)
```
    Calculate the nest of loops enclosed within the given loop
  - getLoopName
```
public static java.lang.String getLoopName(Statement loop)
```
    Returns the loop name inserted by Cetus.
    
    Parameters:
    loop - the loop.
    
    Returns:
    the loop name if one exists, null otherwise.
  - addLoopName
```
public static void addLoopName(Program program)
```
    Adds a unique loop name to each for loop.
    
    Parameters:
    program - the input program.
  - isPrivate
```
public static boolean isPrivate(Symbol s,
                Loop l)
```
    Check if the input symbol is marked as private to the loop by the Privatization pass. ArrayPrivatization MUST be run before using this test.
    
    Parameters:
    s - the symbol which needs to be checked as private to loop or not
    l - the loop with respect to which private property needs to be checked
    
    Returns:
    true if private, else false
  - isReduction
```
public static boolean isReduction(Symbol s,
                  Loop l)
```
    Check if the input symbol is marked as reduction for the loop by the Reduction pass. Reduction Analysis MUST be run before using this test
    
    Parameters:
    s - the symbol which needs to be checked as reduction variable or not
    l - the loop with respect to which reduction property needs to be checked
    
    Returns:
    true if reduction variable, else false
  - checkDataDependenceEligibility
```
public static boolean checkDataDependenceEligibility(Loop loop)
```
    Checks the eligibility of a certain loop for data dependence testing Eligibility checks can be added or removed to increase the scope of dependence testing
    
    Parameters:
    loop -
    
    Returns:
    true if the loop is formed well enough to be eligible.
  - isIncrementEligible
```
public static boolean isIncrementEligible(Loop loop)
```
    Returns true if the loop increment is an integer constant value. If symbolic, uses range information to determine if it is an integer constant value or not
    
    Parameters:
    loop - the loop whose increment needs to be checked
    
    Returns:
    true if increment is an integer constant value
  - getLoopIndexSymbol
```
public static Symbol getLoopIndexSymbol(Loop loop)
```
    Get symbol of loop index, index variable is identified from step expression for loop
    
    Returns:
    Symbol for the loop index variable
  - replaceSymbolicLowerBound
```
public static Expression replaceSymbolicLowerBound(Loop loop,
                                   RangeDomain loop_rd)
```
    Replaces symbolic values in loop lower bound with information obtained from range analysis. If symbolic bound has a constant value, that value is the new lower bound. In case of a range expression, the lowerbound of the range is conservatively used as the lowerbound for the loop. If the symbolic value has an indeterminate value, the minimum possible value for Long is assigned to the lower bound
    
    Parameters:
    loop - the loop whose symbolic lower bound is to be replaced
    loop_rd - the range domain representing ranges for all vars in the loop statement
    
    Returns:
    the expression for the new lowerbound with constant value
  - replaceSymbolicLowerBound
```
public static Expression replaceSymbolicLowerBound(Loop loop)
```
    Replaces symbolic values in loop lower bound with information obtained from range analysis. If symbolic bound has a constant value, that value is the new lower bound. In case of a range expression, the lowerbound of the range is conservatively used as the lowerbound for the loop. If the symbolic value has an indeterminate value, the minimum possible value for Long is assigned to the lower bound
    
    Parameters:
    loop - the loop whose symbolic lower bound is to be replaced
    
    Returns:
    the expression for the new lowerbound with constant value
  - replaceSymbolicUpperBound
```
public static Expression replaceSymbolicUpperBound(Loop loop,
                                   RangeDomain loop_rd)
```
    Replaces symbolic values in loop upper bound with information obtained from range analysis. If symbolic bound has a constant value, that value is the new upper bound. In case of a range expression, the upperbound of the range is conservatively used as the upperbound for the loop. If the symbolic value has an indeterminate value, the maximum possible value for Long is assigned to the upper bound
    
    Parameters:
    loop - the loop whose symbolic upper bound is to be replaced
    loop_rd - the range domain representing ranges for all vars in the loop statement
    
    Returns:
    the expression for the new upperbound with constant value
  - replaceSymbolicUpperBound
```
public static Expression replaceSymbolicUpperBound(Loop loop)
```
    Replaces symbolic values in loop upper bound with information obtained from range analysis. If symbolic bound has a constant value, that value is the new upper bound. In case of a range expression, the upperbound of the range is conservatively used as the upperbound for the loop. If the symbolic value has an indeterminate value, the maximum possible value for Long is assigned to the upper bound
    
    Parameters:
    loop - the loop whose symbolic upper bound is to be replaced
    
    Returns:
    the expression for the new upperbound with constant value
  - extractOutermostDependenceTestEligibleLoops
```
public static java.util.List<Loop> extractOutermostDependenceTestEligibleLoops(Traversable t)
```
  - getReuseDistance
```
public static long getReuseDistance(Loop loop,
                    ArrayAccess e1,
                    ArrayAccess e2)
```
    A simple implementation based on the Euclidean GCD algorithm to calculate the distance in terms of loop iterations between subscripts of dependent arrays. Only handles single index variable subscripts that are affine expressions of that single loop index variable. Does not handle coupled subscripts
    
    Parameters:
    loop - the loop w.r.t which distance needs to be calculated
    e1 - array access that is one end of the dependence
    e2 - array access that is at the other end of the dependence
  - toControlString
```
public static java.lang.String toControlString(Loop loop)
```
    Returns the control structure of the specified loop in string.
    
    Parameters:
    loop - the given loop.
    
    Returns:
    the string for the control structure.

Class LoopTools

Method Summary

Methods inherited from class java.lang.Object

Method Detail

getIncrementExpression

isIncrementConstant

getIndexVariable

getLowerBoundExpression

isLowerBoundConstant

getUpperBoundExpression

isUpperBoundConstant

calculateLoopNest

getCommonNest

isCanonical

containsFunctionCall

containsOnlyParallelizableCall

isPerfectNest

containsLoop

isIndexInvariant

isLoopInvariant

collectScalarDependences

scalarDependencePossible

isInnermostLoop

isOutermostLoop

getOutermostLoop

containsControlFlowModifier

containsBreakStatement

containsControlFlowModifierOtherThanBreakStmt

calculateInnerLoopNest

getLoopName

addLoopName

isPrivate

isReduction

checkDataDependenceEligibility

isIncrementEligible

getLoopIndexSymbol

replaceSymbolicLowerBound

replaceSymbolicLowerBound

replaceSymbolicUpperBound

replaceSymbolicUpperBound

extractOutermostDependenceTestEligibleLoops

getReuseDistance

toControlString