ROSE  0.9.9.109
Utility.h
1 #ifndef ROSE_Partitioner2_Utility_H
2 #define ROSE_Partitioner2_Utility_H
3 
4 #include <Partitioner2/AddressUsageMap.h>
5 #include <Partitioner2/BasicBlock.h>
6 #include <Partitioner2/ControlFlowGraph.h>
7 #include <Partitioner2/DataBlock.h>
8 #include <Partitioner2/Function.h>
9 
10 #include "Diagnostics.h"
11 
12 #include <algorithm>
13 #include <ostream>
14 
15 namespace Rose {
16 namespace BinaryAnalysis {
17 namespace Partitioner2 {
18 
19 extern Sawyer::Message::Facility mlog;
20 void initDiagnostics();
21 
22 bool sortBasicBlocksByAddress(const BasicBlock::Ptr&, const BasicBlock::Ptr&);
23 bool sortDataBlocks(const DataBlock::Ptr&, const DataBlock::Ptr&);
24 bool sortFunctionsByAddress(const Function::Ptr&, const Function::Ptr&);
25 bool sortFunctionNodesByAddress(const SgAsmFunction*, const SgAsmFunction*);
26 bool sortByExpression(const BasicBlock::Successor&, const BasicBlock::Successor&);
27 bool sortVerticesByAddress(const ControlFlowGraph::ConstVertexIterator&, const ControlFlowGraph::ConstVertexIterator&);
28 bool sortEdgesBySrc(const ControlFlowGraph::ConstEdgeIterator&, const ControlFlowGraph::ConstEdgeIterator&);
29 bool sortEdgesByDst(const ControlFlowGraph::ConstEdgeIterator&, const ControlFlowGraph::ConstEdgeIterator&);
30 bool sortBlocksForAst(SgAsmBlock*, SgAsmBlock*);
31 bool sortInstructionsByAddress(SgAsmInstruction*, SgAsmInstruction*);
32 
33 template<class Container, class Comparator>
34 static bool
35 isSorted(const Container &container, Comparator sorted, bool distinct=true) {
36  typename Container::const_iterator current = container.begin();
37  if (current!=container.end()) {
38  typename Container::const_iterator next = current;
39  while (++next != container.end()) {
40  if ((distinct && !sorted(*current, *next)) || sorted(*next, *current))
41  return false;
42  ++current;
43  }
44  }
45  return true;
46 }
47 
48 template<class Container, class Value, class Comparator>
49 typename Container::const_iterator
50 lowerBound(const Container &container, const Value &item, Comparator cmp) {
51  return std::lower_bound(container.begin(), container.end(), item, cmp);
52 }
53 template<class Container, class Value, class Comparator>
54 typename Container::iterator
55 lowerBound(Container &container, const Value &item, Comparator cmp) {
56  return std::lower_bound(container.begin(), container.end(), item, cmp);
57 }
58 
59 // Return true if two container elements are equal according to the sorting comparator
60 template<class Value, class Comparator>
61 bool
62 equalUnique(const Value &a, const Value &b, Comparator cmp) {
63  return !cmp(a, b) && !cmp(b, a); // equal iff neither one is less than the other
64 }
65 
66 // Insert an item into a sorted container if it doesn't exist yet in the container. Returns true iff inserted.
67 template<class Container, class Value, class Comparator>
68 bool
69 insertUnique(Container &container, const Value &item, Comparator cmp) {
70  ASSERT_require(!ROSE_PARTITIONER_EXPENSIVE_CHECKS || isSorted(container, cmp, true)); // unique, sorted items
71  typename Container::iterator lb = lowerBound(container, item, cmp);
72  if (lb==container.end() || !equalUnique(*lb, item, cmp)) {
73  container.insert(lb, item);
74  ASSERT_require(!ROSE_PARTITIONER_EXPENSIVE_CHECKS || isSorted(container, cmp, true));
75  return true;
76  }
77  return false;
78 }
79 
80 // Erase an item from a sorted container if it doesn't exist yet in the container. Returns true iff erased.
81 template<class Container, class Value, class Comparator>
82 bool
83 eraseUnique(Container &container, const Value &item, Comparator cmp) {
84  ASSERT_require(!ROSE_PARTITIONER_EXPENSIVE_CHECKS || isSorted(container, cmp, true)); // unique, sorted items
85  typename Container::iterator lb = lowerBound(container, item, cmp);
86  if (lb!=container.end() && equalUnique(*lb, item, cmp)) {
87  container.erase(lb);
88  return true;
89  }
90  return false;
91 }
92 
93 // Check existence of an item in a sorted container. Returns true iff the item exists.
94 template<class Container, class Value, class Comparator>
95 bool
96 existsUnique(const Container &container, const Value &item, Comparator cmp) {
97  if (item==NULL)
98  return false;
99  ASSERT_require(!ROSE_PARTITIONER_EXPENSIVE_CHECKS || isSorted(container, cmp, true)); // unique, sorted items
100  typename Container::const_iterator lb = lowerBound(container, item, cmp);
101  if (lb==container.end() || cmp(*lb, item) || cmp(item, *lb))
102  return false;
103  return true;
104 }
105 
106 // Retrieve an item from a sorted container
107 template<class Container, class Value, class Comparator>
109 getUnique(const Container &container, const Value &item, Comparator cmp) {
110  if (item==NULL)
111  return Sawyer::Nothing();
112  ASSERT_require(!ROSE_PARTITIONER_EXPENSIVE_CHECKS || isSorted(container, cmp, true)); // unique, sorted items
113  typename Container::const_iterator lb = lowerBound(container, item, cmp);
114  if (lb==container.end() || cmp(*lb, item) || cmp(item, *lb))
115  return Sawyer::Nothing();
116  return *lb;
117 }
118 
119 template<class Container, class Comparator>
120 bool
121 isSupersetUnique(const Container &sup, const Container &sub, Comparator lessThan) {
122  ASSERT_require(!ROSE_PARTITIONER_EXPENSIVE_CHECKS || isSorted(sup, lessThan, true)); // unique, sorted items
123  ASSERT_require(!ROSE_PARTITIONER_EXPENSIVE_CHECKS || isSorted(sub, lessThan, true)); // unique, sorted items
124  typename Container::const_iterator isup = sup.begin(), isub = sub.begin();
125  while (isup != sup.end() && isub != sub.end()) {
126  while (isup != sup.end() && lessThan(*isup, *isub))
127  ++isup;
128  if (isup == sup.end() || lessThan(*isub, *isup))
129  return false;
130  ++isup, ++isub;
131  }
132  return isub == sub.end();
133 }
134 
135 std::ostream& operator<<(std::ostream&, const AddressUser&);
136 std::ostream& operator<<(std::ostream&, const AddressUsers&);
137 std::ostream& operator<<(std::ostream&, const AddressUsageMap&);
138 std::ostream& operator<<(std::ostream&, const ControlFlowGraph::Vertex&);
139 std::ostream& operator<<(std::ostream&, const ControlFlowGraph::Edge&);
140 
152 protected:
155  : Sawyer::CommandLine::ValueParser(valueSaver) {}
156 public:
159 
160  static Ptr instance() {
161  return Ptr(new AddressIntervalParser);
162  }
163 
164  static Ptr instance(const Sawyer::CommandLine::ValueSaver::Ptr &valueSaver) {
165  return Ptr(new AddressIntervalParser(valueSaver));
166  }
167 
168  static std::string docString();
169 
170 private:
171  virtual Sawyer::CommandLine::ParsedValue operator()(const char *input, const char **rest,
172  const Sawyer::CommandLine::Location &loc) ROSE_OVERRIDE;
173 };
174 
175 AddressIntervalParser::Ptr addressIntervalParser(AddressInterval &storage);
176 AddressIntervalParser::Ptr addressIntervalParser(std::vector<AddressInterval> &storage);
177 AddressIntervalParser::Ptr addressIntervalParser();
178 
180 class Trigger {
181 public:
182  typedef AddressInterval SizeInterval; // okay to use 64-bit integers for the counters
183  struct Settings {
184  SizeInterval when; // when to trigger based on nCalls_
185  Settings(): when(0) {}
186  };
187 private:
188  size_t nCalls_; // number of times called
189  Settings settings_;
190 public:
192  Trigger(): nCalls_(0) {}
193 
195  explicit Trigger(const Settings &settings): nCalls_(0), settings_(settings) {}
196 
198  Trigger(size_t nSkip, size_t nTimes): nCalls_(0) {
199  settings_.when = nTimes ? SizeInterval::baseSize(nSkip, nTimes) : SizeInterval();
200  }
201 
203  static Trigger once() { return Trigger(0, 1); }
204 
206  static Trigger always() { return Trigger(0, size_t(-1)); }
207 
209  static Trigger never() { return Trigger(); }
210 
212  bool isArmed() const { return !settings_.when.isEmpty() && nCalls_<=settings_.when.greatest(); }
213 
215  bool shouldTrigger() { return settings_.when.isContaining(nCalls_++); }
216 
218  size_t nCalls() const { return nCalls_; }
219 
221  void reset() { nCalls_ = 0; }
222 
224  static Sawyer::CommandLine::SwitchGroup switches(Settings&);
225 
227  static std::string docString();
228 };
229 
231 size_t serialNumber();
232 
233 
234 
235 } // namespace
236 } // namespace
237 } // namespace
238 
239 #endif
Instruction basic block.
const ValueSaver::Ptr valueSaver() const
Property: functor responsible for saving a parsed value in user storage.
Definition: CommandLine.h:719
bool isEmpty() const
True if interval is empty.
Definition: Interval.h:197
Trigger(const Settings &settings)
Armed for triggering when number of calls falls within when.
Definition: Utility.h:195
Base class for machine instructions.
Collection of streams.
Definition: Message.h:1579
Sawyer::SharedPointer< DataBlock > Ptr
Shared pointer to a data block.
Definition: DataBlock.h:22
A collection of related switch declarations.
Definition: CommandLine.h:2488
Represents a synthesized function.
size_t nCalls() const
Number of times called.
Definition: Utility.h:218
bool isContaining(const Interval &other) const
Containment predicate.
Definition: Interval.h:216
Main namespace for the ROSE library.
Sawyer::SharedPointer< AddressIntervalParser > Ptr
Shared-ownership pointer to an AddressIntervalParser.
Definition: Utility.h:158
static Interval baseSize(rose_addr_t lo, rose_addr_t size)
Construct an interval from one endpoint and a size.
Definition: Interval.h:161
size_t serialNumber()
Return the next serial number.
Information about a parsed switch value.
Definition: CommandLine.h:483
Trigger based on number of times called.
Definition: Utility.h:180
static std::string docString()
Documentation for command-line switches.
bool isArmed() const
True if trigger is armed.
Definition: Utility.h:212
Trigger()
Trigger armed for single call.
Definition: Utility.h:192
Sawyer::SharedPointer< BasicBlock > Ptr
Shared pointer to a basic block.
Definition: BasicBlock.h:37
static Sawyer::CommandLine::SwitchGroup switches(Settings &)
Command-line switches to initialize settings.
Position within a command-line.
Definition: CommandLine.h:213
Base class parsing a value from input.
Definition: CommandLine.h:677
Represents no value.
Definition: Optional.h:32
T greatest() const
Returns upper limit.
Definition: Interval.h:191
static Trigger always()
Armed to always trigger.
Definition: Utility.h:206
static Trigger never()
Armed to never trigger.
Definition: Utility.h:209
FunctionPtr Ptr
Shared-ownership pointer for function.
Definition: Function.h:48
bool shouldTrigger()
Increment calls and return true if triggering.
Definition: Utility.h:215
static Trigger once()
Armed for one call.
Definition: Utility.h:203
void reset()
Reset number of calls to zero.
Definition: Utility.h:221
Trigger(size_t nSkip, size_t nTimes)
Armed for triggering after nSkip calls but not more than nTimes times.
Definition: Utility.h:198