ROSE  0.9.10.69
Classes | Public Types | Public Member Functions | List of all members
Sawyer::Container::Trace< T, IndexTag > Class Template Reference

Description

template<class T, class IndexTag = TraceMapIndexTag>
class Sawyer::Container::Trace< T, IndexTag >

Records and replays traces.

This class is able to record a trace and replay it later. A trace is an ordered list of labels of type T, where a label can be any type whose members have an ordering relationship (integers, strings, pointers, certain kinds of iterators, etc.). Some examples where a Trace could be used:

Of course, a container traversal or DFA execution could also be replayed by re-traversing or re-executing, but that's not always convenient due to data modification during the traversal, the size of the associated data, or the runtime expense. Furthermore, a Trace can also answer queries like how often a label was visited, what transitions are most common, and so on.

Although a trace can be stored simply as an ordered list of labels, doing so is not always the most efficient. A Trace compresses a trace by observing that many kinds of traces tend to be "bursty". That is, the successor of each visit to label A is likely to be the same as the successor of the previous visit to A. See burstiness. The higher the burstiness the more compression is possible.

In order to compress a trace and to later obtain information on a per-label basis, the Trace needs to be able to form an index of the labels. The second template argument, IndexTag, is a tag that selects an index type from the TraceIndexTraits. Sawyer provides the following tags, but users can create additional tags and their own index types. TraceMapIndexTag is the default and uses an std::map to store labels; TraceVectorIndexTag causes an std::vector to be used instead and is suitable for a dense set of low-numbered labels.

Example: recording a program execution trace for a control flow graph

This example records a program execution trace (ET) over a control flow graph (CFG). An ET is the ordered list of machine instruction addresses executed by a program when it runs, and a CFG is a graph whose vertices are all known instruction addresses and whose edges represent possible execution flow from one instruction to another. Non-branching instructions have only one outgoing edge, and most branches have two outgoing edges (indirect branches have more). For simplicity, we assume that the CFG is complete and is computed prior to obtaining the trace. The important thing to know is that execution traces tend to be bursty: non-branching instructions always have the same successor, and branching instructions (especially those controlling loops) tend to branch one way more often than the other.

using namespace Sawyer;
using namespace Sawyer::Container;
class Instruction { ... } // some user-defined type
class CfgEdge { ... } // some user-defined type
class Program { ... } // some user-define type
Program program("a.out"); // user-defined: starts a program in a debugger
typedef Graph<Instruction, CfgEdge, unsigned> Cfg; // instructions indexed by their unsigned address
typedef Trace<size_t, TraceVectorIndexTag> Trace; // labels are sequential CFG vertex IDs, so a vector is appropriate
Cfg cfg;
Trace trace;
while (program.isRunning()) {
unsigned address = program.executionAddress();
Cfg::ConstVertexIterator vertex = cfg.findVertexKey(address); // O(log) or O(1) depending on index type
trace.append(vertex->id()); // O(1)
program.singleStep();
}

Later, we can replay the trace without the expense of running the program again:

trace.traverse([&cfg](size_t vertexId) {
Cfg::ConstVertexIterator vertex = cfg.findVertex(vertexId); // O(1)
const Instruction &insn = vertex->value();
std::cout <<"executed " <<insn.toString() <<"\n";
return true; // continue traversal
});

If we know the address of a branch instruction (such as for an "if" statement in a higher level language), we can query some properties such as burstiness to decide whether speculative execution would be beneficial here:

unsigned branchAddress = ...;
if (trace.exists(branchAddress)) { // branch was executed at least once?
if (trace.burstiness(branchAddress) >= 2.0) {
// loosely speaking, the branch predicate is not random; 2.0 is arbitrary
}
}

Definition at line 258 of file Trace.h.

#include <Trace.h>

Classes

struct  Successor
 Compressed next-label list. More...
 

Public Types

typedef T Label
 Label type. More...
 
typedef std::vector< SuccessorSuccessors
 Successors for a label. More...
 

Public Member Functions

 Trace ()
 Default constructor. More...
 
void clear ()
 Clears the recorded trace. More...
 
void reserve (size_t n)
 Reserve space in the label index. More...
 
bool isEmpty () const
 Determines if a trace is empty. More...
 
bool exists (const Label &label) const
 Determines if a label is present in a trace. More...
 
size_t nLabels () const
 Number of distinct labels. More...
 
void append (const Label &label)
 Append a label to a trace. More...
 
template<class Visitor >
void traverse (Visitor &visitor) const
 Traversal of the trace labels. More...
 
void print (std::ostream &out, const std::string &separator=", ") const
 Print as sequence. More...
 
void dump (std::ostream &out) const
 Low-level debugging information. More...
 
std::vector< LabeltoVector () const
 Convert a trace into a vector. More...
 
std::set< LabelsuccessorSet (const Label &label) const
 Set of labels which are successors for the specified label. More...
 
double burstiness () const
 The burstiness of a trace. More...
 
const Successorssuccessors (const Label &label) const
 Ordered successors for a label. More...
 
size_t size () const
 Total length of a trace, or the number of times a label appears in a trace. More...
 
size_t size (const Label &label) const
 Total length of a trace, or the number of times a label appears in a trace. More...
 
double burstiness (const Label &label) const
 The burstiness of a label. More...
 

Member Typedef Documentation

template<class T , class IndexTag = TraceMapIndexTag>
typedef T Sawyer::Container::Trace< T, IndexTag >::Label

Label type.

Labels must have an ordering defined by a less-than operator.

Definition at line 263 of file Trace.h.

template<class T , class IndexTag = TraceMapIndexTag>
typedef std::vector<Successor> Sawyer::Container::Trace< T, IndexTag >::Successors

Successors for a label.

Definition at line 277 of file Trace.h.

Constructor & Destructor Documentation

template<class T , class IndexTag = TraceMapIndexTag>
Sawyer::Container::Trace< T, IndexTag >::Trace ( )
inline

Default constructor.

Definition at line 294 of file Trace.h.

Member Function Documentation

template<class T , class IndexTag = TraceMapIndexTag>
void Sawyer::Container::Trace< T, IndexTag >::clear ( )
inline

Clears the recorded trace.

This Trace is reset to its default-constructed state.

Definition at line 299 of file Trace.h.

template<class T , class IndexTag = TraceMapIndexTag>
void Sawyer::Container::Trace< T, IndexTag >::reserve ( size_t  n)
inline

Reserve space in the label index.

This is a hint to reserve space for n distinct labels in the label index. The index need not honor this request.

Definition at line 308 of file Trace.h.

template<class T , class IndexTag = TraceMapIndexTag>
bool Sawyer::Container::Trace< T, IndexTag >::isEmpty ( ) const
inline

Determines if a trace is empty.

Returns true if and only if a trace contains no labels.

Time complexity: constant.

Definition at line 317 of file Trace.h.

Referenced by Sawyer::Container::Trace< T, IndexTag >::append(), Sawyer::Container::Trace< T, IndexTag >::dump(), Sawyer::Container::Trace< T, IndexTag >::exists(), and Sawyer::Container::Trace< T, IndexTag >::traverse().

template<class T , class IndexTag = TraceMapIndexTag>
bool Sawyer::Container::Trace< T, IndexTag >::exists ( const Label label) const
inline

Determines if a label is present in a trace.

Returns true if and only if the specified label occurs in the trace.

Time complexity: depends on the label indexing scheme, but probably constant for labels that can be used as array indexes and logorithmic for labels that are map lookup keys.

Definition at line 327 of file Trace.h.

References Sawyer::Container::Trace< T, IndexTag >::isEmpty().

Referenced by Sawyer::Container::Trace< T, IndexTag >::append().

template<class T , class IndexTag = TraceMapIndexTag>
size_t Sawyer::Container::Trace< T, IndexTag >::size ( void  ) const
inline

Total length of a trace, or the number of times a label appears in a trace.

Time complexity: constant.

Definition at line 336 of file Trace.h.

Referenced by Sawyer::Container::Trace< T, IndexTag >::burstiness().

template<class T , class IndexTag = TraceMapIndexTag>
size_t Sawyer::Container::Trace< T, IndexTag >::size ( const Label label) const
inline

Total length of a trace, or the number of times a label appears in a trace.

Time complexity: constant.

Definition at line 339 of file Trace.h.

References Sawyer::Container::Trace< T, IndexTag >::successors().

template<class T , class IndexTag = TraceMapIndexTag>
size_t Sawyer::Container::Trace< T, IndexTag >::nLabels ( ) const
inline

Number of distinct labels.

This is the number of unique labels that appear in the trace.

Time complexity: constant.

Definition at line 350 of file Trace.h.

template<class T , class IndexTag = TraceMapIndexTag>
void Sawyer::Container::Trace< T, IndexTag >::append ( const Label label)
inline

Append a label to a trace.

Time complexity: amortized constant if labels are array indexes, amortized logirithmic if labels are map keys.

Definition at line 357 of file Trace.h.

References Sawyer::Container::Trace< T, IndexTag >::exists(), Sawyer::Container::Trace< T, IndexTag >::isEmpty(), and Sawyer::Container::Trace< T, IndexTag >::successors().

template<class T , class IndexTag = TraceMapIndexTag>
template<class Visitor >
void Sawyer::Container::Trace< T, IndexTag >::traverse ( Visitor &  visitor) const
inline

Traversal of the trace labels.

The visitor functor takes one argument: the label being visited, and should return true if the traversal should continue or false if it should be terminated.

Time complexity: initialization time is proportional to the number of distinct labels in the trace. Advancing from one label to the next is constant time.

Definition at line 386 of file Trace.h.

References Sawyer::Container::Trace< T, IndexTag >::Successor::end, Sawyer::Container::Trace< T, IndexTag >::isEmpty(), Sawyer::Container::Trace< T, IndexTag >::Successor::next, and Sawyer::Container::Trace< T, IndexTag >::successors().

Referenced by Sawyer::Container::Trace< T, IndexTag >::print(), and Sawyer::Container::Trace< T, IndexTag >::toVector().

template<class T , class IndexTag = TraceMapIndexTag>
void Sawyer::Container::Trace< T, IndexTag >::print ( std::ostream &  out,
const std::string &  separator = ", " 
) const
inline

Print as sequence.

Emits the trace to the specified output stream with each element separated by the separator.

Definition at line 436 of file Trace.h.

References Sawyer::Container::Trace< T, IndexTag >::traverse().

template<class T , class IndexTag = TraceMapIndexTag>
void Sawyer::Container::Trace< T, IndexTag >::dump ( std::ostream &  out) const
inline

Low-level debugging information.

This method is intended for debugging. It prints the storage representation of this trace. The output format is not defined.

Definition at line 445 of file Trace.h.

References Sawyer::Container::Trace< T, IndexTag >::Successor::end, Sawyer::Container::Trace< T, IndexTag >::isEmpty(), Sawyer::Container::Trace< T, IndexTag >::Successor::next, and Sawyer::Container::Trace< T, IndexTag >::successors().

template<class T , class IndexTag = TraceMapIndexTag>
std::vector<Label> Sawyer::Container::Trace< T, IndexTag >::toVector ( ) const
inline

Convert a trace into a vector.

Converts a trace into a vector of labels. Consider using traverse instead since it's more efficient.

Definition at line 477 of file Trace.h.

References Sawyer::Container::Trace< T, IndexTag >::traverse().

template<class T , class IndexTag = TraceMapIndexTag>
std::set<Label> Sawyer::Container::Trace< T, IndexTag >::successorSet ( const Label label) const
inline

Set of labels which are successors for the specified label.

Time complexity: The set must be constructed by traversing successor sequence. The length of the successor sequence is the number of maximal subsequences where the members of a subsequence are all the same. Insertion of each label into the set has logarithmic time.

Definition at line 488 of file Trace.h.

References Sawyer::Container::Trace< T, IndexTag >::Successor::next.

Referenced by Sawyer::Container::Trace< T, IndexTag >::burstiness().

template<class T , class IndexTag = TraceMapIndexTag>
double Sawyer::Container::Trace< T, IndexTag >::burstiness ( const Label label) const
inline

The burstiness of a label.

Loosely speaking, the "burstiness" of a label is a measure of how often successive occurrences of the label transition to the same successor and is a floating point value between zero and one, inclusive. Specifically, the burstiness of a label is the number of distinct labels divided by the number of maximal subsequences of the successor sequence where a subsequence's members are all the same label.

For example, if the the entire trace is [5, 5, 5, 4, 5, 5] then the successors of label 5 are the sequence [5, 5, 4, 5] and the maximal subsequences of one label are [5, 5], [4], and [5]. The burstiness of 5 is therefore 2/3 since there are two distinct labels, {4, 5}, and three maximal successor subsequences.

Some properties: A label with only one distinct successor, will have a burstiness of 1.0 no matter how many times the label appears in the trace. A label with N distinct successors will have a burstiness of 1.0 if it visits the first distinct successor, then the second, then the third (in any order) without any interleaving. A label that interleaves its successors as much as possible will have a burstiness of approximately 1/N where N is the number of distinct successors.

If label has no successors then zero is returned. This is distinguishable from other cases since normal return values will always be positive.

Time complexity: O(n) where n is the number of maximal subsequences of the successors where all members of a subsequence are equal. Time to look up the label depends on the label index type.

Definition at line 519 of file Trace.h.

References Sawyer::Container::Trace< T, IndexTag >::size(), and Sawyer::Container::Trace< T, IndexTag >::successorSet().

template<class T , class IndexTag = TraceMapIndexTag>
double Sawyer::Container::Trace< T, IndexTag >::burstiness ( ) const
inline

The burstiness of a trace.

The burstiness of a trace is the average burstiness of its labels.

Definition at line 529 of file Trace.h.

References Sawyer::Container::Trace< T, IndexTag >::size(), and Sawyer::CommandLine::sum().

template<class T , class IndexTag = TraceMapIndexTag>
const Successors& Sawyer::Container::Trace< T, IndexTag >::successors ( const Label label) const
inline

Ordered successors for a label.

Given a label, return a vector that describes the ordered successors for this label. The return value is a list whose members are pairs consisting of an integer visit sequence number and a label. For instance, if label A was visited 10 times and the successors were, in order, [B, B, B, B, B, C, C, B, B, D] then the return value will be the list of pairs [(5,B), (7,C), (9,B), (10,D)].

Time complexity: Depends on the label index type. If the TraceVectorIndexTag was specified then this method executes in constant time.

Definition at line 550 of file Trace.h.

Referenced by Sawyer::Container::Trace< T, IndexTag >::append(), Sawyer::Container::Trace< T, IndexTag >::dump(), Sawyer::Container::Trace< T, IndexTag >::size(), and Sawyer::Container::Trace< T, IndexTag >::traverse().


The documentation for this class was generated from the following file: