scale.score.trans
Class CP

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

public class CP
extends Optimization

Perform copy propagation optimization on a Scribble graph.

$Id: CP.java,v 1.70 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.

The algorithm is from .....

When a right argument to an assignment statement is propagated to the places where the left argument is used, the original assignment is no longer needed. However, since the CFG is in SSA form, removing this assignment at this time causes a problem that results in poorer code being generated. Removing the assignment often results in code of the form

   var_3 = var_1;
 ...
   var_1 = var_3;
 

These statments are never removed. The reason this happens is that by removing the assignment, the lifetime of the variable is not terminated prior to the assignment. Thus, the coalescing of variables, that is performed when leaving SSA form, can not change this code to

   var = var;
 ...
   var = var;
 

As a result, the logic to remove useless copies does not remove these unneeded assignments. If the original assignment is left in, then coalescing works, the useless assignments are removed, and dead variable elimination gets rid of the original assignment.

Register pressure is usually increased because the live range of a variable is increased. This tends to outweight the advantage of eliminating the references to the other variable.

A transformation is legal if:

the left-hand-side of the assignment is a variable,

• the variable is not global or static,
• the variable's address is not taken,
• the variable is volatile,
• the variable has hidden aliases, and

the right-hand-side is an expression in which all variables referenced are

• not global or static,
• do not have their addresses taken,
• not volatile, and
• do not have hidden aliases.

It is beneficial if the right-hand-side is

• a variable or
• an addition or subtraction expression whose right operand is a constant and whose left operand is a variable.

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

CP(Scribble scribble)

Method Summary

static int	aliasInhibited() Return the number of times an alias inhibited a copy propagation.
void	perform() Perform the actual copy propagation.
static int	propagations() Return the number of times copy propagation was performed.

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.

Constructor Detail

CP

public CP(Scribble scribble)

Parameters:

scribble - is the Scribble graph to be transformd by copy propagation

Method Detail

aliasInhibited

public static int aliasInhibited()

Return the number of times an alias inhibited a copy propagation.

propagations

public static int propagations()

Return the number of times copy propagation was performed.

perform

public void perform()

Perform the actual copy propagation.

Specified by:

perform in class Optimization