scale.score.trans
Class ValNum

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

public class ValNum
extends Optimization

Global value numbering optimization.

$Id: ValNum.java,v 1.100 2007-10-04 19:58:38 burrill Exp $

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

Global value numbering based on the dominator-based value numbering technique by Preston Briggs et al, "Value Numbering", Software -- Practice and Experience, 1990.

Global value numbering is essentially a common subexpression. elimination algorithm. It attempts to find multiple occurrences of the same expression and replace the subsequent ones with a reference to a new variable whose value is obtained from the first occrrence and are dominated by the first occurrence.

If the first occurrence of the expression is assigned to a variable, this optimization will attempt to use that variable as the replacement variable.

It is possible, though unlikely, for a transformation to reduce register pressure. If the expression references more than one variable that are referenced nowhere else in the scope of the def of the replacement variable, register pressure will be reduced. If there is more than one variable that is referenced in other expressions, register pressure will increase.

A transformation is legal if:

• all the variables in the the expression
  • are not global or static,
  • do not have their addresses taken,
  • are not volatile,
  • do not have hidden aliases, and
• the expression does not have side effects.

It is beneficial if:

• none of the variables in the the expression are floating point or the architecture has non-volatile floating point registers,
• the expression is not a simple add or subtract of an integer constant,
• the expression is not a constant that can be easily generated, and
• there is more than one occurrence of the expression,

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

ValNum(Scribble scribble)

Method Summary

static int	deadCFGNodes() Return the number of dead nodes removed.
static int	newCFGNodes() Return the number of new nodes added.
void	perform() Go through dominance tree to do value numbering.
static int	propagations() Return the number of expressions removed.

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

ValNum

public ValNum(Scribble scribble)

Method Detail

deadCFGNodes

public static int deadCFGNodes()

Return the number of dead nodes removed.

newCFGNodes

public static int newCFGNodes()

Return the number of new nodes added.

propagations

public static int propagations()

Return the number of expressions removed.

perform

public void perform()

Go through dominance tree to do value numbering. Basicly we use the SSA name as the value number. For example in

    a1 = b1 + c1
 

the value number of b1+c1 is a1. An exception ocurrs when the left hand side has alias varibles. In this case, we create a new variable `for the right hand expression.

Specified by:

perform in class Optimization