ROSE  0.9.11.115
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/DataBlock.h>
7 #include <Partitioner2/Function.h>
8 
9 #include "Diagnostics.h"
10 
11 #include <algorithm>
12 #include <ostream>
13 
14 namespace Rose {
15 namespace BinaryAnalysis {
16 namespace Partitioner2 {
17 
18 extern Sawyer::Message::Facility mlog;
19 void initDiagnostics();
20 
21 bool sortBasicBlocksByAddress(const BasicBlock::Ptr&, const BasicBlock::Ptr&);
22 bool sortDataBlocks(const DataBlock::Ptr&, const DataBlock::Ptr&);
23 bool sortFunctionsByAddress(const Function::Ptr&, const Function::Ptr&);
24 bool sortFunctionNodesByAddress(const SgAsmFunction*, const SgAsmFunction*);
25 bool sortByExpression(const BasicBlock::Successor&, const BasicBlock::Successor&);
26 bool sortBlocksForAst(SgAsmBlock*, SgAsmBlock*);
27 bool sortInstructionsByAddress(SgAsmInstruction*, SgAsmInstruction*);
28 
29 template<class Container, class Comparator>
30 static bool
31 isSorted(const Container &container, Comparator sorted, bool distinct=true) {
32  typename Container::const_iterator current = container.begin();
33  if (current!=container.end()) {
34  typename Container::const_iterator next = current;
35  while (++next != container.end()) {
36  if ((distinct && !sorted(*current, *next)) || sorted(*next, *current))
37  return false;
38  ++current;
39  }
40  }
41  return true;
42 }
43 
44 template<class Container, class Value, class Comparator>
45 typename Container::const_iterator
46 lowerBound(const Container &container, const Value &item, Comparator cmp) {
47  return std::lower_bound(container.begin(), container.end(), item, cmp);
48 }
49 template<class Container, class Value, class Comparator>
50 typename Container::iterator
51 lowerBound(Container &container, const Value &item, Comparator cmp) {
52  return std::lower_bound(container.begin(), container.end(), item, cmp);
53 }
54 
55 // Return true if two container elements are equal according to the sorting comparator
56 template<class Value, class Comparator>
57 bool
58 equalUnique(const Value &a, const Value &b, Comparator cmp) {
59  return !cmp(a, b) && !cmp(b, a); // equal iff neither one is less than the other
60 }
61 
62 // Insert an item into a sorted container if it doesn't exist yet in the container. Returns true iff inserted.
63 template<class Container, class Value, class Comparator>
64 bool
65 insertUnique(Container &container, const Value &item, Comparator cmp) {
66  ASSERT_require(!ROSE_PARTITIONER_EXPENSIVE_CHECKS || isSorted(container, cmp, true)); // unique, sorted items
67  typename Container::iterator lb = lowerBound(container, item, cmp);
68  if (lb==container.end() || !equalUnique(*lb, item, cmp)) {
69  container.insert(lb, item);
70  ASSERT_require(!ROSE_PARTITIONER_EXPENSIVE_CHECKS || isSorted(container, cmp, true));
71  return true;
72  }
73  return false;
74 }
75 
76 // Insert an intem into a sorted continer, replacing any existing item that compares equal to it.
77 template<class Container, class Value, class Comparator>
78 void
79 replaceOrInsert(Container &container, const Value &item, Comparator cmp) {
80  ASSERT_require(!ROSE_PARTITIONER_EXPENSIVE_CHECKS || isSorted(container, cmp, true)); // unique, sorted items
81  typename Container::iterator lb = lowerBound(container, item, cmp);
82  if (lb == container.end() || !equalUnique(*lb, item, cmp)) {
83  container.insert(lb, item);
84  } else {
85  *lb = item;
86  }
87  ASSERT_require(!ROSE_PARTITIONER_EXPENSIVE_CHECKS || isSorted(container, cmp, true));
88 }
89 
90 // Erase an item from a sorted container if it doesn't exist yet in the container. Returns true iff erased.
91 template<class Container, class Value, class Comparator>
92 bool
93 eraseUnique(Container &container, const Value &item, Comparator cmp) {
94  ASSERT_require(!ROSE_PARTITIONER_EXPENSIVE_CHECKS || isSorted(container, cmp, true)); // unique, sorted items
95  typename Container::iterator lb = lowerBound(container, item, cmp);
96  if (lb!=container.end() && equalUnique(*lb, item, cmp)) {
97  container.erase(lb);
98  return true;
99  }
100  return false;
101 }
102 
103 // Check existence of an item in a sorted container. Returns true iff the item exists.
104 template<class Container, class Value, class Comparator>
105 bool
106 existsUnique(const Container &container, const Value &item, Comparator cmp) {
107  if (item==NULL)
108  return false;
109  ASSERT_require(!ROSE_PARTITIONER_EXPENSIVE_CHECKS || isSorted(container, cmp, true)); // unique, sorted items
110  typename Container::const_iterator lb = lowerBound(container, item, cmp);
111  if (lb==container.end() || cmp(*lb, item) || cmp(item, *lb))
112  return false;
113  return true;
114 }
115 
116 // Retrieve an item from a sorted container
117 template<class Container, class Value, class Comparator>
119 getUnique(const Container &container, const Value &item, Comparator cmp) {
120  if (item==NULL)
121  return Sawyer::Nothing();
122  ASSERT_require(!ROSE_PARTITIONER_EXPENSIVE_CHECKS || isSorted(container, cmp, true)); // unique, sorted items
123  typename Container::const_iterator lb = lowerBound(container, item, cmp);
124  if (lb==container.end() || cmp(*lb, item) || cmp(item, *lb))
125  return Sawyer::Nothing();
126  return *lb;
127 }
128 
129 template<class Container, class Comparator>
130 bool
131 isSupersetUnique(const Container &sup, const Container &sub, Comparator lessThan) {
132  ASSERT_require(!ROSE_PARTITIONER_EXPENSIVE_CHECKS || isSorted(sup, lessThan, true)); // unique, sorted items
133  ASSERT_require(!ROSE_PARTITIONER_EXPENSIVE_CHECKS || isSorted(sub, lessThan, true)); // unique, sorted items
134  typename Container::const_iterator isup = sup.begin(), isub = sub.begin();
135  while (isup != sup.end() && isub != sub.end()) {
136  while (isup != sup.end() && lessThan(*isup, *isub))
137  ++isup;
138  if (isup == sup.end() || lessThan(*isub, *isup))
139  return false;
140  ++isup, ++isub;
141  }
142  return isub == sub.end();
143 }
144 
145 std::ostream& operator<<(std::ostream&, const AddressUser&);
146 std::ostream& operator<<(std::ostream&, const AddressUsers&);
147 std::ostream& operator<<(std::ostream&, const AddressUsageMap&);
148 
160 protected:
163  : Sawyer::CommandLine::ValueParser(valueSaver) {}
164 public:
167 
168  static Ptr instance() {
169  return Ptr(new AddressIntervalParser);
170  }
171 
172  static Ptr instance(const Sawyer::CommandLine::ValueSaver::Ptr &valueSaver) {
173  return Ptr(new AddressIntervalParser(valueSaver));
174  }
175 
176  static std::string docString();
177 
182  static AddressInterval parse(const char *input, const char **rest);
183 
190  static AddressInterval parse(const std::string &input);
191 
192 private:
193  virtual Sawyer::CommandLine::ParsedValue operator()(const char *input, const char **rest,
194  const Sawyer::CommandLine::Location &loc) ROSE_OVERRIDE;
195 };
196 
197 AddressIntervalParser::Ptr addressIntervalParser(AddressInterval &storage);
198 AddressIntervalParser::Ptr addressIntervalParser(std::vector<AddressInterval> &storage);
199 AddressIntervalParser::Ptr addressIntervalParser();
200 
202 class Trigger {
203 public:
204  typedef AddressInterval SizeInterval; // okay to use 64-bit integers for the counters
205  struct Settings {
206  SizeInterval when; // when to trigger based on nCalls_
207  Settings(): when(0) {}
208  };
209 private:
210  size_t nCalls_; // number of times called
211  Settings settings_;
212 public:
214  Trigger(): nCalls_(0) {}
215 
217  explicit Trigger(const Settings &settings): nCalls_(0), settings_(settings) {}
218 
220  Trigger(size_t nSkip, size_t nTimes): nCalls_(0) {
221  settings_.when = nTimes ? SizeInterval::baseSize(nSkip, nTimes) : SizeInterval();
222  }
223 
225  static Trigger once() { return Trigger(0, 1); }
226 
228  static Trigger always() { return Trigger(0, size_t(-1)); }
229 
231  static Trigger never() { return Trigger(); }
232 
234  bool isArmed() const { return !settings_.when.isEmpty() && nCalls_<=settings_.when.greatest(); }
235 
237  bool shouldTrigger() { return settings_.when.isContaining(nCalls_++); }
238 
240  size_t nCalls() const { return nCalls_; }
241 
243  void reset() { nCalls_ = 0; }
244 
246  static Sawyer::CommandLine::SwitchGroup switches(Settings&);
247 
249  static std::string docString();
250 };
251 
253 size_t serialNumber();
254 
255 
256 
257 } // namespace
258 } // namespace
259 } // namespace
260 
261 #endif
Instruction basic block.
const ValueSaver::Ptr valueSaver() const
Property: functor responsible for saving a parsed value in user storage.
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:217
Base class for machine instructions.
Sawyer::SharedPointer< DataBlock > Ptr
Shared pointer to a data block.
Definition: DataBlock.h:31
A collection of related switch declarations.
Represents a synthesized function.
size_t nCalls() const
Number of times called.
Definition: Utility.h:240
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:166
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.
Trigger based on number of times called.
Definition: Utility.h:202
static std::string docString()
Documentation for command-line switches.
bool isArmed() const
True if trigger is armed.
Definition: Utility.h:234
Trigger()
Trigger armed for single call.
Definition: Utility.h:214
Sawyer::SharedPointer< BasicBlock > Ptr
Shared pointer to a basic block.
Definition: BasicBlock.h:131
static Sawyer::CommandLine::SwitchGroup switches(Settings &)
Command-line switches to initialize settings.
Position within a command-line.
Base class parsing a value from input.
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:228
static Trigger never()
Armed to never trigger.
Definition: Utility.h:231
FunctionPtr Ptr
Shared-ownership pointer for function.
Definition: Function.h:48
bool shouldTrigger()
Increment calls and return true if triggering.
Definition: Utility.h:237
static Trigger once()
Armed for one call.
Definition: Utility.h:225
void reset()
Reset number of calls to zero.
Definition: Utility.h:243
static AddressInterval parse(const char *input, const char **rest)
Parse an interval from a C string.
Trigger(size_t nSkip, size_t nTimes)
Armed for triggering after nSkip calls but not more than nTimes times.
Definition: Utility.h:220