scale.score.trans
Class TreeHeight

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

public class TreeHeight
extends Optimization

Perform expression tree height reduction on a Scribble graph.

$Id: TreeHeight.java,v 1.25 2007-02-28 18:00:38 burrill Exp $

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

The tree height reduction optimization attempts to improve the performance of individual expressions by allowing more operations to be performed in parallel. For eample, consider the expression (a + (b + (c + d))). Using this order of precedence, the three addition operations must be performed sequentially. If the expression is transformed to ((a + b) + (c + d)) then two of the additons may be performed simultaneously. This will benefit superscalar architectures.

In this example, the two expressions are equivalent. However, on a digital computer using floating point operations, these two expressions may result in two different values because floating point addition is not associative.

Note also that to calculate the value of the first expression requires only five registers. One is used to hold the sum and the others hold the values of the variables. Six registers are required for the second expression as a partial sum must be kept while the other partial sum is calculated. (The number of registers required actually depends on which variables have been allocated to registers.) The net result is an increase in register pressure.

A transformation is legal if:

• the operator is binary-associative,
• the operands are scalars,
• the operands are integers or the user has allowed operations with floating point operands to be re-arranged, and
• the expression has four or more leaves.

It is beneficial if it is legal.

Field Summary

static boolean	classTrace True if traces are to be performed.
static boolean	doHuffman Use Huffman coding weight balancing.
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

TreeHeight(Scribble scribble)

Method Summary

void	perform() Find and reduce the height of expression trees
int	requiresSSA() Return whether this optimization requires that the CFG be in SSA form.
static int	treesReduced() Return the number of expression trees found

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.

doHuffman

public static boolean doHuffman

Use Huffman coding weight balancing.

Constructor Detail

TreeHeight

public TreeHeight(Scribble scribble)

Parameters:

scribble - is the CFG transformed by tree height reduction

Method Detail

treesReduced

public static int treesReduced()

Return the number of expression trees found

perform

public void perform()

Find and reduce the height of expression trees

Specified by:

perform in class Optimization

requiresSSA

public int requiresSSA()

Return whether this optimization requires that the CFG be in SSA form. It returns either

NO_SSA

the CFG must not be in SSA form,

IN_SSA

the CFG must be in SSA form,

VALID_SSA

the CFG must be in valid SSA form, or

NA_SSA

the CFG does not need to be in valid SSA form.

Overrides:

requiresSSA in class Optimization