edu.uci.eecs.doc.clepsydra.cache
Class DualMethodCacheStrategy

java.lang.Object
  edu.uci.eecs.doc.clepsydra.cache.DualMethodCacheStrategy

All Implemented Interfaces:

MethodCacheStrategy

public class DualMethodCacheStrategy
extends Object

Performs simple cache hit analysis based on a dual-method cache configuration. This analysis is conservative and only finds guaranteed hits when a single method is invoked in a loop. The analysis is based on WCET Analysis for a Java Processor by Martin Schoeberl and Rasmus Pedersen.

Author:

Trevor Harmon

Nested Class Summary

Nested classes/interfaces inherited from interface edu.uci.eecs.doc.clepsydra.cache.MethodCacheStrategy

MethodCacheStrategy.HitRatio

Constructor Summary

DualMethodCacheStrategy()

Method Summary

MethodCacheStrategy.HitRatio	getInvokeHitRatio(InvokeInstruction invokeInstruction, Node node, LoopBoundStrategy loopBoundStrategy) Returns the cache hit ratio for the given invoke instruction.
protected int	getIterations(Node node, LoopBoundStrategy loopBoundStrategy) Returns the number of times the node is executed.
boolean	isReturnHit(ReturnStatement returnStatement) Returns true if the given return statement is guaranteed to result in a method cache hit.

Methods inherited from class java.lang.Object

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

Constructor Detail

DualMethodCacheStrategy

public DualMethodCacheStrategy()

Method Detail

getInvokeHitRatio

public MethodCacheStrategy.HitRatio getInvokeHitRatio(InvokeInstruction invokeInstruction,
                                                      Node node,
                                                      LoopBoundStrategy loopBoundStrategy)

Returns the cache hit ratio for the given invoke instruction. For example, if the method is only invoked once by the given block, and it is guaranteed to be in the cache, then the hit ratio would be 1/1. If the method is invoked in a loop that executes 10 times, and the first iteration is a miss and all others are hits, then the hit ratio would be 9/10.

Specified by:

getInvokeHitRatio in interface MethodCacheStrategy

Parameters:

invokeInstruction - a bytecode instruction that invokes a method

node - the node in the control flow tree in which the invoke instruction lives

loopBoundStrategy - if the invocation occurs in a loop, this algorithm is used to determine the maximum number of iterations of the loop

Returns:

a hit ratio object

isReturnHit

public boolean isReturnHit(ReturnStatement returnStatement)

Returns true if the given return statement is guaranteed to result in a method cache hit. (For the dual method cache, return instructions are a guaranteed hit if the method containing the return statement doesn't invoke any other methods.)

Specified by:

isReturnHit in interface MethodCacheStrategy

Parameters:

returnStatement - a control flow node representing a return statement

Returns:

true if the return to the caller is a cache hit; false otherwise

getIterations

protected int getIterations(Node node,
                            LoopBoundStrategy loopBoundStrategy)
                     throws UnknownLoopBoundException

Returns the number of times the node is executed. Examples: Without loops, iterations = 1 In a single loop of bound 10, iterations = 10 In a nested loop with inner bound 10 and outer bound 10, iterations = 100

Throws:

UnknownLoopBoundException