edu.uci.eecs.doc.clepsydra.tree
Class TreeAnalysisStrategy

java.lang.Object
  edu.uci.eecs.doc.clepsydra.tree.TreeAnalysisStrategy

All Implemented Interfaces:

AnalysisStrategy

public class TreeAnalysisStrategy
extends Object
implements AnalysisStrategy

This analysis strategy computes the WCET by recursively descending the control flow tree and summing the timing of each node. When a branch is encountered, the maximum branch is used as the timing.

Author:

Trevor Harmon

Constructor Summary

TreeAnalysisStrategy(InstructionTimingStrategy instructionTimings, LoopBoundStrategy loopBounds, MethodCacheStrategy methodCache)
Creates a new TreeAnalysisStrategy object.

Method Summary

int	getWCET(Node node) Computes an upper bound on the WCET of the given node.
int	getWCET(Tree tree, Graph graph) Computes an upper bound on the WCET of the given method.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

TreeAnalysisStrategy

public TreeAnalysisStrategy(InstructionTimingStrategy instructionTimings,
                            LoopBoundStrategy loopBounds,
                            MethodCacheStrategy methodCache)

Creates a new TreeAnalysisStrategy object.

Parameters:

instructionTimings - a model of the temporal properties of the target CPU

loopBounds - a strategy for computing the upper bound on loops

methodCache - a strategy for modeling the method cache

Method Detail

getWCET

public int getWCET(Tree tree,
                   Graph graph)
            throws UnknownTimingException,
                   UnknownLoopBoundException

Computes an upper bound on the WCET of the given method.

Specified by:

getWCET in interface AnalysisStrategy

Parameters:

tree - the control flow tree of the method

graph - this parameter is ignored

Returns:

the WCET in CPU cycles

Throws:

UnknownTimingException - if the method contains an instruction whose timing is unknown

UnknownLoopBoundException - if the method contains a loop whose upper bound cannot be determined

getWCET

public int getWCET(Node node)
            throws UnknownTimingException,
                   UnknownLoopBoundException

Computes an upper bound on the WCET of the given node. The WCET value includes nodes in sub-scopes of the given node but not subsequent nodes in the same scope (lexical level). For example, if the method looks like this:

 if (i > 10)
 {
     b = true;
     i >>= 8;
     j++;
 }
 

And the supplied node is i >>= 8, then the resulting WCET would include only i >>= 8. If, however, the supplied node is the if statement, then the resulting WCET would include the i > 10 condition as well as the entire body of the if statement.

Parameters:

node - the node whose WCET is to be computed

Returns:

the WCET in CPU cycles

Throws:

UnknownTimingException - if the node contains an instruction whose timing is unknown

UnknownLoopBoundException - if the node contains a loop whose upper bound cannot be determined