Rietveld Code Review Tool
Help | Bug tracker | Discussion group | Source code | Sign in
(279)

Unified Diff: syzygy/reorder/linear_order_generator.h

Issue 4641092: Revamped linear order generator (Closed) Base URL: http://sawbuck.googlecode.com/svn/trunk/
Patch Set: '' Created 12 years, 9 months ago
Use n/p to move between diff chunks; N/P to move between comments. Please Sign in to add in-line comments.
Jump to:
View side-by-side diff with in-line comments
Download patch
« no previous file with comments | « no previous file | syzygy/reorder/linear_order_generator.cc » ('j') | no next file with comments »
Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
Index: syzygy/reorder/linear_order_generator.h
===================================================================
--- syzygy/reorder/linear_order_generator.h (revision 365)
+++ syzygy/reorder/linear_order_generator.h (working copy)
@@ -17,6 +17,25 @@
// If data ordering is enabled, all data blocks referred to by a code block
// are assumed to have been touched when the code block was executed, and they
// are output in that order.
+//
+// If multiple runs of the instrumented binary are seen in the trace files, each
+// run will be processed independently, and for each unique block, the count of
+// how many runs in which its execution was seen is maintained. Blocks are first
+// sorted by the number of individual runs in which they were seen (decreasing),
+// and then sorted by the order in which they were seen. For the special case
+// of blocks that were only seen in a single run of the binary, these are
Siggi 2011/07/05 14:30:19 Nice. Thanks!
+// separated by run and then sorted by time seen.
+//
+// Consider a trace file that contains 3 runs of an executable. The generated
+// ordering will be as follows:
+//
+// code seen in all 3 runs, code seen in any 2 runs, code seen only in 1st run,
+// code seen only in 2nd run, code seen only in 3rd run
+//
+// In the case where there is a single run of the instrumented binary, the
+// ordering will be a simple ordering of blocks by order of execution, as per
+// our original proof-of-concept ordering.
+
#ifndef SYZYGY_REORDER_LINEAR_ORDER_GENERATOR_H_
#define SYZYGY_REORDER_LINEAR_ORDER_GENERATOR_H_
@@ -30,11 +49,18 @@
public:
typedef Reorderer::UniqueTime UniqueTime;
typedef Reorderer::Order Order;
+ struct BlockCall;
LinearOrderGenerator();
virtual ~LinearOrderGenerator();
// OrderGenerator implementation.
+ virtual bool OnProcessStarted(const Reorderer& reorderer,
+ uint32 process_id,
+ const UniqueTime& time);
+ virtual bool OnProcessEnded(const Reorderer& reorderer,
+ uint32 process_id,
+ const UniqueTime& time);
virtual bool OnCodeBlockEntry(const Reorderer& reorderer,
const BlockGraph::Block* block,
RelativeAddress address,
@@ -45,19 +71,59 @@
Order* order);
private:
- typedef std::map<const BlockGraph::Block*, UniqueTime> BlockCallMap;
+ typedef std::vector<BlockCall> BlockCalls;
+ typedef std::map<size_t, BlockCalls> ProcessGroupBlockCalls;
+ typedef std::map<const BlockGraph::Block*, BlockCall> BlockCallMap;
// Called by OnFunctionEntry to update block_calls_.
- bool TouchBlock(const BlockGraph::Block* block, const UniqueTime& time);
- // Given a code block, touches the data blocks associated with it.
- bool TouchDataBlocks(const Reorderer& reorderer,
- const BlockGraph::Block* code_block,
- const UniqueTime& time);
+ bool TouchBlock(const BlockCall& block_call);
+ // Given a block, inserts the data blocks associated with it into
+ // the ordering. Will recursively traverse data blocks until the given
+ // maximum stack depth (that way, we include data referred to by data).
+ bool InsertDataBlocks(size_t max_recursion_depth,
+ const Reorderer& reorderer,
+ const BlockGraph::Block* block,
+ Order* order);
+
+ // This is called to indicate a process group closure.
+ bool CloseProcessGroup();
+
+ // We assume that processes that co-exist are all part of a single run.
+ // So we divide up block calls per run. This counts the number of currently
+ // active processes, and when it reaches zero it means that we need to
+ // start a new process.
+ size_t active_process_count_;
+
+ // This is for creating unique ids for groups of coexisting processes.
+ // This is incremented every time active_process_count transitions from 0
+ // to 1.
+ size_t next_process_group_id_;
+
+ // Stores the linearized block list per process group.
+ ProcessGroupBlockCalls process_group_calls_;
+
// Stores pointers to blocks, and the first time at which they were accessed.
- BlockCallMap block_calls_;
+ // There is one of these per 'process group'.
+ BlockCallMap block_call_map_;
+
+ // Stores a list of already-inserted data blocks.
+ std::set<const BlockGraph::Block*> data_block_set_;
};
+struct LinearOrderGenerator::BlockCall {
+ const BlockGraph::Block* block;
+ uint32_t process_id;
+ uint32_t thread_id;
+ UniqueTime time;
+
+ BlockCall(const BlockGraph::Block* block, uint32_t process_id,
+ uint32_t thread_id, const UniqueTime& time)
+ : block(block), process_id(process_id), thread_id(thread_id),
+ time(time) {
+ }
+};
+
} // namespace reorder
#endif // SYZYGY_REORDER_LINEAR_ORDER_GENERATOR_H_
« no previous file with comments | « no previous file | syzygy/reorder/linear_order_generator.cc » ('j') | no next file with comments »

Powered by Google App Engine
RSS Feeds Recent Issues | This issue
This is Rietveld f62528b