ScalarReplacement

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 ScalarReplacement

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

public class ScalarReplacement
extends Optimization
extends Optimization

This class replaces references to array elements with references to scalar variables. If array elements are set, the CFG is no longer in a completely valid SSA form.

$Id: ScalarReplacement.java,v 1.74 2007-10-18 17:01:10 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 array s
   Sort subscript expressions in control dependence order
   For each subscript expression r1 of s
     For each remaining subscript expression r2
           of s in r1's iterated dominance domain
       If all edges from r1 to r2 have zero distance
         Add edges from r1 to r2 to list of edges
     End for each remaining r2 of s
     Allocate new variable vd
     For each def-use link from r1
       Sort in control dependence order
       Replace first load with a load into vd.
       Replace all remaining loads with a load of vd.
       For each store
         Replace array reference with reference to vd
         Insert a store from vd to the array and record this store.
       End for each store
     End for each def-use link
     For each data dependence edge in list of edges
       Switch on edge type
         case input, flow
           For each def-use link from r2
             Sort in control dependence order
             Replace first load with a load into vd.
             Replace all remaining loads with a load of vd.
             For each store
               Replace array reference with reference to vd
               Insert a store from vd to the array and record this store.
             End each store
           End each def-use link
         End case
         case anti, output
           For each def-use link from r2
             Sort in control dependence order
             For each store
               Replace array reference with reference to vd
               Insert a store from vd to the array and record this store.
             End each store
           End each def-use
         End case
       End switch
     End for each data dependence edge
     For each recorded store s1
       If there exists a straight line control path to another recorded store s2
         remove s1
     End for each recorded store
   End for each r1 of s
 End for each array

Field Summary
`static boolean`	`classTrace` True if traces are to be performed.
`static boolean`	`innerLoopsOnly` If true, data dependence analysis is performed for inner loops only.
`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
`ScalarReplacement(Scribble scribble)`

Method Summary
`static int`	`newCFGNodes()` Return the number of new nodes created.
`void`	`perform()` Perform the optimization.
`static int`	`replacedLoads()` Return the current number of array loads replaced.
`static int`	`replacedStores()` Return the current number of array stores replaced.

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.

innerLoopsOnly

public static boolean innerLoopsOnly

If true, data dependence analysis is performed for inner loops only. For

    do 10 i = 1, N
      do 20 j = 1, M
        ...
        = x(i)
        ...
 20 continue
      do 20 j = 1, M
        ...
        = x(i)
        ...
 30 continue
 10 continue

setting innerLoopsOnly to false will enable scalar replacement to use one scalar variable for both references to x. It may also greatly increase the time that the scalar replacement optimization takes.

Constructor Detail