GlobalVarReplacement

Overview

Package

Class

Tree

Deprecated

Index

Help

PREV CLASS NEXT CLASS

FRAMES NO FRAMES

SUMMARY: NESTED | FIELD | CONSTR | METHOD

DETAIL: FIELD | CONSTR | METHOD

scale.score.trans
Class GlobalVarReplacement

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

public class GlobalVarReplacement
extends Optimization
extends Optimization

This class replaces references to global variables with references to local variables.

$Id: GlobalVarReplacement.java,v 1.62 2007-10-04 19:58:35 burrill Exp $

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

An attempt is made to put the first load of the global variable outside of the loop. This optimization must be performed outside of SSA form because

it does not use the use-def information, and
it is too hard to add the use-def links and phi functions if it is in SSA form.

In the following algorithm the relation "dominated by" means those nodes in the iterative dominance domain. The iterative dominance domain terminates at calls to subroutines.

 For each global variable g
   Obtain set uses of the uses of g
   Pushd CFG start node on stack wl
   While set uses is not empty
     firstNode = null
     insertNode = null
     while stack wl is not empty
       sNode = pop(wl)
       push children of sNode on wl
       if sNode is a loop header and all exits of the loop are dominated by sNode
         insert = sNode
       if sNode is in set uses
         firstNode = sNode
     end while stack wl
     if firstNode == null
       exit while set uses
     if insertNode == null
       insertNode = firstNode
     else if firstNode is not dominated by the loop header insertNode
       insert = first
     Insert a load of the global variable into a temporary variable before insertNode
     Replace references to g in firstNode with references to the temporary
     Change all references to g in the nodes specified by uses
            that are dominated by firstNode
     remove firstNode from set uses
     Change all defs of g in the nodes specified by defs that
             are dominated by firstNode to def
        both the temporary and the global variable
   End while set uses
 End for each global variable g

Register pressure is always increased because a new variable is introduced that has a live range that is always greater than the live range of the reference to the gloabl variable it represents.

A transformation is legal if:

the variable is a global (or static),
the variable is not volatile,
the variable has no hidden aliases, and
the variable's address is not taken.

It is beneficial if:

the variable has more than one reference, and
the live range of the surrogate variable would not be too great.

The heuristic used to determine if the live range would be too great divides the number of nodes dominated by the def of the surrogate variable by the number of references and compares that to a constant value. This constant is 60 unless the variable is floating point and the target architecture does not have non-volatile floating point registers. In this case the value of 30 is used.

Field Summary
`static boolean`	`classTrace` True if traces are to be performed.
`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
`GlobalVarReplacement(Scribble scribble)`

Method Summary
`static int`	`newCFGNodes()` Return the number of new nodes created.
`static int`	`outOfLoops()` Return the current number of loads placed outside of loops.
`void`	`perform()` Perform the optimization.
`static int`	`replacedLoads()` Return the current number of array loads replaced.
`int`	`requiresSSA()` Specify that this optimization requires that the CFG NOT be in SSA form.

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

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.

Constructor Detail