ROSE  0.11.109.0
Partitioner2/Utility.h
1 #ifndef ROSE_BinaryAnalysis_Partitioner2_Utility_H
2 #define ROSE_BinaryAnalysis_Partitioner2_Utility_H
3 #include <featureTests.h>
4 #ifdef ROSE_ENABLE_BINARY_ANALYSIS
5 
6 #include <Rose/BinaryAnalysis/Partitioner2/AddressUsageMap.h>
7 #include <Rose/BinaryAnalysis/Partitioner2/BasicBlock.h>
8 #include <Rose/BinaryAnalysis/Partitioner2/DataBlock.h>
9 #include <Rose/BinaryAnalysis/Partitioner2/Function.h>
10 #include <Rose/CommandLine/IntervalParser.h>
11 
12 #include <Rose/Diagnostics.h>
13 
14 #include <algorithm>
15 #include <ostream>
16 
17 namespace Rose {
18 namespace BinaryAnalysis {
19 namespace Partitioner2 {
20 
22 void initDiagnostics();
23 
24 bool sortBasicBlocksByAddress(const BasicBlock::Ptr&, const BasicBlock::Ptr&);
25 bool sortDataBlocks(const DataBlock::Ptr&, const DataBlock::Ptr&);
26 bool sortFunctionsByAddress(const Function::Ptr&, const Function::Ptr&);
27 bool sortFunctionNodesByAddress(const SgAsmFunction*, const SgAsmFunction*);
28 bool sortByExpression(const BasicBlock::Successor&, const BasicBlock::Successor&);
29 bool sortBlocksForAst(SgAsmBlock*, SgAsmBlock*);
30 bool sortInstructionsByAddress(SgAsmInstruction*, SgAsmInstruction*);
31 
32 template<class Container, class Comparator>
33 static bool
34 isSorted(const Container &container, Comparator sorted, bool distinct=true) {
35  typename Container::const_iterator current = container.begin();
36  if (current!=container.end()) {
37  typename Container::const_iterator next = current;
38  while (++next != container.end()) {
39  if ((distinct && !sorted(*current, *next)) || sorted(*next, *current))
40  return false;
41  ++current;
42  }
43  }
44  return true;
45 }
46 
47 template<class Container, class Value, class Comparator>
48 typename Container::const_iterator
49 lowerBound(const Container &container, const Value &item, Comparator cmp) {
50  return std::lower_bound(container.begin(), container.end(), item, cmp);
51 }
52 template<class Container, class Value, class Comparator>
53 typename Container::iterator
54 lowerBound(Container &container, const Value &item, Comparator cmp) {
55  return std::lower_bound(container.begin(), container.end(), item, cmp);
56 }
57 
58 // Return true if two container elements are equal according to the sorting comparator
59 template<class Value, class Comparator>
60 bool
61 equalUnique(const Value &a, const Value &b, Comparator cmp) {
62  return !cmp(a, b) && !cmp(b, a); // equal iff neither one is less than the other
63 }
64 
65 // Insert an item into a sorted container if it doesn't exist yet in the container. Returns true iff inserted.
66 template<class Container, class Value, class Comparator>
67 bool
68 insertUnique(Container &container, const Value &item, Comparator cmp) {
69  ASSERT_require(!ROSE_PARTITIONER_EXPENSIVE_CHECKS || isSorted(container, cmp, true)); // unique, sorted items
70  typename Container::iterator lb = lowerBound(container, item, cmp);
71  if (lb==container.end() || !equalUnique(*lb, item, cmp)) {
72  container.insert(lb, item);
73  ASSERT_require(!ROSE_PARTITIONER_EXPENSIVE_CHECKS || isSorted(container, cmp, true));
74  return true;
75  }
76  return false;
77 }
78 
79 // Insert an intem into a sorted continer, replacing any existing item that compares equal to it.
80 template<class Container, class Value, class Comparator>
81 void
82 replaceOrInsert(Container &container, const Value &item, Comparator cmp) {
83  ASSERT_require(!ROSE_PARTITIONER_EXPENSIVE_CHECKS || isSorted(container, cmp, true)); // unique, sorted items
84  typename Container::iterator lb = lowerBound(container, item, cmp);
85  if (lb == container.end() || !equalUnique(*lb, item, cmp)) {
86  container.insert(lb, item);
87  } else {
88  *lb = item;
89  }
90  ASSERT_require(!ROSE_PARTITIONER_EXPENSIVE_CHECKS || isSorted(container, cmp, true));
91 }
92 
93 // Erase an item from a sorted container if it doesn't exist yet in the container. Returns true iff erased.
94 template<class Container, class Value, class Comparator>
95 bool
96 eraseUnique(Container &container, const Value &item, Comparator cmp) {
97  ASSERT_require(!ROSE_PARTITIONER_EXPENSIVE_CHECKS || isSorted(container, cmp, true)); // unique, sorted items
98  typename Container::iterator lb = lowerBound(container, item, cmp);
99  if (lb!=container.end() && equalUnique(*lb, item, cmp)) {
100  container.erase(lb);
101  return true;
102  }
103  return false;
104 }
105 
106 // Check existence of an item in a sorted container. Returns true iff the item exists.
107 template<class Container, class Value, class Comparator>
108 bool
109 existsUnique(const Container &container, const Value &item, Comparator cmp) {
110  if (item==NULL)
111  return false;
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 false;
116  return true;
117 }
118 
119 // Retrieve an item from a sorted container
120 template<class Container, class Value, class Comparator>
122 getUnique(const Container &container, const Value &item, Comparator cmp) {
123  if (item==NULL)
124  return Sawyer::Nothing();
125  ASSERT_require(!ROSE_PARTITIONER_EXPENSIVE_CHECKS || isSorted(container, cmp, true)); // unique, sorted items
126  typename Container::const_iterator lb = lowerBound(container, item, cmp);
127  if (lb==container.end() || cmp(*lb, item) || cmp(item, *lb))
128  return Sawyer::Nothing();
129  return *lb;
130 }
131 
132 // Find an existing item if possible and return the item. If not found, insert the item and return false.
133 template<class Container, class Value, class Comparator>
135 getOrInsertUnique(Container &container, const Value &item, Comparator cmp) {
136  ASSERT_require(!ROSE_PARTITIONER_EXPENSIVE_CHECKS || isSorted(container, cmp, true)); // unique, sorted items
137  typename Container::iterator lb = lowerBound(container, item, cmp);
138  if (lb != container.end() && equalUnique(*lb, item, cmp)) {
139  return *lb;
140  } else {
141  container.insert(lb, item);
142  ASSERT_require(!ROSE_PARTITIONER_EXPENSIVE_CHECKS || isSorted(container, cmp, true));
143  return Sawyer::Nothing();
144  }
145 }
146 
147 template<class Container, class Comparator>
148 bool
149 isSupersetUnique(const Container &sup, const Container &sub, Comparator lessThan) {
150  ASSERT_require(!ROSE_PARTITIONER_EXPENSIVE_CHECKS || isSorted(sup, lessThan, true)); // unique, sorted items
151  ASSERT_require(!ROSE_PARTITIONER_EXPENSIVE_CHECKS || isSorted(sub, lessThan, true)); // unique, sorted items
152  typename Container::const_iterator isup = sup.begin(), isub = sub.begin();
153  while (isup != sup.end() && isub != sub.end()) {
154  while (isup != sup.end() && lessThan(*isup, *isub))
155  ++isup;
156  if (isup == sup.end() || lessThan(*isub, *isup))
157  return false;
158  ++isup, ++isub;
159  }
160  return isub == sub.end();
161 }
162 
163 std::ostream& operator<<(std::ostream&, const AddressUser&);
164 std::ostream& operator<<(std::ostream&, const AddressUsers&);
165 std::ostream& operator<<(std::ostream&, const AddressUsageMap&);
166 
179 
180 protected:
183  : Super(valueSaver) {}
184 public:
187 
189  static Ptr instance() {
190  return Ptr(new AddressIntervalParser);
191  }
192 
195  return Ptr(new AddressIntervalParser(valueSaver));
196  }
197 
199  static std::string docString();
200 };
201 
202 AddressIntervalParser::Ptr addressIntervalParser(AddressInterval &storage);
203 AddressIntervalParser::Ptr addressIntervalParser(std::vector<AddressInterval> &storage);
204 AddressIntervalParser::Ptr addressIntervalParser(AddressIntervalSet &storage);
205 AddressIntervalParser::Ptr addressIntervalParser();
206 
208 class Trigger {
209 public:
210  typedef AddressInterval SizeInterval; // okay to use 64-bit integers for the counters
211  struct Settings {
212  SizeInterval when; // when to trigger based on nCalls_
213  Settings(): when(0) {}
214  };
215 private:
216  size_t nCalls_; // number of times called
217  Settings settings_;
218 public:
220  Trigger(): nCalls_(0) {}
221 
223  explicit Trigger(const Settings &settings): nCalls_(0), settings_(settings) {}
224 
226  Trigger(size_t nSkip, size_t nTimes): nCalls_(0) {
227  settings_.when = nTimes ? SizeInterval::baseSize(nSkip, nTimes) : SizeInterval();
228  }
229 
231  static Trigger once() { return Trigger(0, 1); }
232 
234  static Trigger always() { return Trigger(0, size_t(-1)); }
235 
237  static Trigger never() { return Trigger(); }
238 
240  bool isArmed() const { return !settings_.when.isEmpty() && nCalls_<=settings_.when.greatest(); }
241 
243  bool shouldTrigger() { return settings_.when.contains(nCalls_++); }
244 
246  size_t nCalls() const { return nCalls_; }
247 
249  void reset() { nCalls_ = 0; }
250 
252  static Sawyer::CommandLine::SwitchGroup switches(Settings&);
253 
255  static std::string docString();
256 };
257 
259 size_t serialNumber();
260 
261 
262 
263 } // namespace
264 } // namespace
265 } // namespace
266 
267 #endif
268 #endif
Instruction basic block.
const ValueSaver::Ptr valueSaver() const
Property: functor responsible for saving a parsed value in user storage.
static Ptr instance()
Default allocating constructor.
bool isEmpty() const
True if interval is empty.
Definition: Interval.h:219
Trigger(const Settings &settings)
Armed for triggering when number of calls falls within when.
Base class for machine instructions.
Collection of streams.
Definition: Message.h:1606
Sawyer::SharedPointer< AddressIntervalParser > Ptr
Shared-ownership pointer to an AddressIntervalParser.
ROSE_DLL_API Sawyer::Message::Facility mlog
Diagnostic facility for the ROSE library as a whole.
Sawyer::SharedPointer< DataBlock > Ptr
Shared pointer to a data block.
Definition: DataBlock.h:34
A collection of related switch declarations.
Represents a synthesized function.
size_t nCalls() const
Number of times called.
Main namespace for the ROSE library.
static Interval baseSize(rose_addr_t lo, rose_addr_t size)
Construct an interval from one endpoint and a size.
Definition: Interval.h:162
bool contains(const Interval &other) const
Containment predicate.
Definition: Interval.h:246
size_t serialNumber()
Return the next serial number.
Trigger based on number of times called.
static std::string docString()
Documentation for command-line switches.
bool isArmed() const
True if trigger is armed.
Trigger()
Trigger armed for single call.
static Ptr instance(const Sawyer::CommandLine::ValueSaver::Ptr &valueSaver)
Allocating constructor.
Sawyer::SharedPointer< BasicBlock > Ptr
Shared pointer to a basic block.
Definition: BasicBlock.h:134
void initDiagnostics()
Initialize diagnostics.
static Sawyer::CommandLine::SwitchGroup switches(Settings &)
Command-line switches to initialize settings.
static std::string docString()
Runtime documentation.
Represents no value.
Definition: Optional.h:32
T greatest() const
Returns upper limit.
Definition: Interval.h:213
static Trigger always()
Armed to always trigger.
static Trigger never()
Armed to never trigger.
FunctionPtr Ptr
Shared-ownership pointer for function.
Definition: Function.h:51
bool shouldTrigger()
Increment calls and return true if triggering.
static Trigger once()
Armed for one call.
void reset()
Reset number of calls to zero.
Trigger(size_t nSkip, size_t nTimes)
Armed for triggering after nSkip calls but not more than nTimes times.