ROSE 0.11.145.147
|
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.
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.
Later, we can replay the trace without the expense of running the program again:
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:
#include <Sawyer/Trace.h>
Classes | |
class | ConstIterator |
Forward iterator. More... | |
struct | Successor |
Compressed next-label list. More... | |
Public Types | |
typedef T | Label |
Label type. | |
typedef std::vector< Successor > | Successors |
Successors for a label. | |
Public Member Functions | |
Trace () | |
Default constructor. | |
ConstIterator | begin () const |
Returns a forward iterator pointing to first element of this trace. | |
ConstIterator | end () const |
Returns a forward iterator pointing past the end of this trace. | |
Label | front () const |
Returns the first item in the trace. | |
Label | back () const |
Returns the last item in the trace. | |
void | clear () |
Clears the recorded trace. | |
void | reserve (size_t n) |
Reserve space in the label index. | |
bool | isEmpty () const |
Determines if a trace is empty. | |
bool | exists (const Label &label) const |
Determines if a label is present in a trace. | |
size_t | nLabels () const |
Number of distinct labels. | |
Sawyer::Container::Set< Label > | labels () const |
Set of all labels in the trace. | |
void | append (const Label &label) |
Append a label to a trace. | |
template<class Visitor > | |
void | traverse (Visitor &visitor) const |
Traversal of the trace labels. | |
void | print (std::ostream &out, const std::string &separator=", ") const |
Print as sequence. | |
void | dump (std::ostream &out) const |
Low-level debugging information. | |
std::vector< Label > | toVector () const |
Convert a trace into a vector. | |
std::set< Label > | successorSet (const Label &label) const |
Set of labels which are successors for the specified label. | |
double | burstiness () const |
The burstiness of a trace. | |
const Successors & | successors (const Label &label) const |
Ordered successors for a label. | |
size_t | size () const |
Total length of a trace, or the number of times a label appears in a trace. | |
size_t | size (const Label &label) const |
Total length of a trace, or the number of times a label appears in a trace. | |
double | burstiness (const Label &label) const |
The burstiness of a label. | |
typedef T Sawyer::Container::Trace< T, IndexTag >::Label |
typedef std::vector<Successor> Sawyer::Container::Trace< T, IndexTag >::Successors |
|
inline |
|
inline |
|
inline |
|
inline |
Returns the first item in the trace.
The trace must not be empty. Returns a copy of the item.
Definition at line 394 of file Trace.h.
Referenced by Sawyer::Container::Trace< T, IndexTag >::ConstIterator::ConstIterator().
|
inline |
|
inline |
|
inline |
|
inline |
Determines if a trace is empty.
Returns true if and only if a trace contains no labels.
Time complexity: constant.
Definition at line 426 of file Trace.h.
Referenced by Sawyer::Container::Trace< T, IndexTag >::ConstIterator::ConstIterator(), 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().
|
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 436 of file Trace.h.
References Sawyer::Container::Trace< T, IndexTag >::isEmpty().
Referenced by Sawyer::Container::Trace< T, IndexTag >::append().
|
inline |
Total length of a trace, or the number of times a label appears in a trace.
Time complexity: constant.
Definition at line 445 of file Trace.h.
Referenced by Sawyer::Container::Trace< T, IndexTag >::burstiness(), and Sawyer::Container::Trace< T, IndexTag >::burstiness().
|
inline |
Total length of a trace, or the number of times a label appears in a trace.
Time complexity: constant.
Definition at line 448 of file Trace.h.
References Sawyer::Container::Trace< T, IndexTag >::successors().
|
inline |
|
inline |
Set of all labels in the trace.
This is the set of labels in no particular order.
Definition at line 466 of file Trace.h.
References Sawyer::Container::Set< T, C, A >::insert().
|
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 476 of file Trace.h.
References Sawyer::Container::Trace< T, IndexTag >::exists(), Sawyer::Container::Trace< T, IndexTag >::isEmpty(), and Sawyer::Container::Trace< T, IndexTag >::successors().
Referenced by Rose::BinaryAnalysis::Debugger::Base::trace().
|
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 505 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().
|
inline |
Print as sequence.
Emits the trace to the specified output stream with each element separated by the separator
.
Definition at line 555 of file Trace.h.
References Sawyer::Container::Trace< T, IndexTag >::traverse().
Referenced by Sawyer::Container::operator<<().
|
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 564 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().
|
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 596 of file Trace.h.
References Sawyer::Container::Trace< T, IndexTag >::traverse().
|
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 607 of file Trace.h.
References Sawyer::Container::Trace< T, IndexTag >::Successor::next.
Referenced by Sawyer::Container::Trace< T, IndexTag >::burstiness().
|
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 638 of file Trace.h.
References Sawyer::Container::Trace< T, IndexTag >::size(), and Sawyer::Container::Trace< T, IndexTag >::successorSet().
|
inline |
The burstiness of a trace.
The burstiness of a trace is the average burstiness of its labels.
Definition at line 648 of file Trace.h.
References Sawyer::Container::Trace< T, IndexTag >::burstiness(), and Sawyer::Container::Trace< T, IndexTag >::size().
Referenced by Sawyer::Container::Trace< T, IndexTag >::burstiness().
|
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 669 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().