ROSE  0.9.10.196
BasicBlock.h
1 #ifndef ROSE_Partitioner2_BasicBlock_H
2 #define ROSE_Partitioner2_BasicBlock_H
3 
4 #include <Partitioner2/BasicTypes.h>
5 #include <Partitioner2/DataBlock.h>
6 #include <Partitioner2/Semantics.h>
7 
8 #include <Sawyer/Attribute.h>
9 #include <Sawyer/Cached.h>
10 #include <Sawyer/Map.h>
11 #include <Sawyer/Optional.h>
12 #include <Sawyer/SharedPointer.h>
13 #include <Sawyer/Synchronization.h>
14 
15 #include <boost/serialization/access.hpp>
16 #include <boost/serialization/base_object.hpp>
17 #include <boost/serialization/set.hpp>
18 #include <boost/serialization/string.hpp>
19 #include <boost/serialization/vector.hpp>
20 
21 namespace Rose {
22 namespace BinaryAnalysis {
23 namespace Partitioner2 {
24 
26 
32 public:
40 
46 
52 
58 
64 
66  bool wasDropped;
67 
68 public:
71  : usingDispatcher(false), wasDropped(false) {}
72 
77  bool isSemanticsDropped() const {
78  return dispatcher && !initialState;
79  }
80 
85  bool isSemanticsError() const {
86  return dispatcher && initialState && !usingDispatcher;
87  }
88 
95  return usingDispatcher && operators ? operators->currentState() : BaseSemantics::StatePtr();
96  }
97 };
98 
121 public:
124 
126  class Successor {
127  private:
128  Semantics::SValuePtr expr_;
129  EdgeType type_;
130  Confidence confidence_;
131 
132 #ifdef ROSE_HAVE_BOOST_SERIALIZATION_LIB
133  private:
134  friend class boost::serialization::access;
135 
136  template<class S>
137  void serialize(S &s, const unsigned /*version*/) {
138  s & BOOST_SERIALIZATION_NVP(expr_);
139  s & BOOST_SERIALIZATION_NVP(type_);
140  s & BOOST_SERIALIZATION_NVP(confidence_);
141  }
142 #endif
143 
144  public: // "protected" fails for boost-1.58.
145  // intentionally undocumented; needed for serialization
146  Successor()
147  : type_(E_USER_DEFINED), confidence_(ASSUMED) {}
148 
149  public:
151  : expr_(expr), type_(type), confidence_(confidence) {}
152 
154  const Semantics::SValuePtr& expr() const { return expr_; }
155 
157  EdgeType type() const { return type_; }
158  void type(EdgeType t) { type_ = t; }
159 
163  Confidence confidence() const { return confidence_; }
164  void confidence(Confidence c) { confidence_ = c; }
166  };
167 
169  typedef std::vector<Successor> Successors;
170 
171 private:
172  mutable SAWYER_THREAD_TRAITS::Mutex mutex_;
173 
174  bool isFrozen_; // True when the object becomes read-only
175  rose_addr_t startVa_; // Starting address, perhaps redundant with insns_[0]->p_address
176  std::string comment_; // Mutli-line plain-text comment
177  std::vector<SgAsmInstruction*> insns_; // Instructions in the order they're executed
178  BasicBlockSemantics semantics_; // All semantics-related information
179  std::vector<DataBlock::Ptr> dblocks_; // Data blocks owned by this basic block, sorted
180 
181  // When a basic block gets lots of instructions some operations become slow due to the linear nature of the instruction
182  // list. Therefore, we also keep a mapping from instruction address to position in the list. The mapping is only used when
183  // the bigBlock size is reached.
184  static const size_t bigBlock_ = 200;
186  InsnAddrMap insnAddrMap_; // maps instruction address to index in insns_ vector
187 
188  // The following members are caches either because their value is seldom needed and expensive to compute, or because
189  // the value is best computed at a higher layer than a single basic block (e.g., in the partitioner) yet it makes the
190  // most sense to store it here. Make sure clearCache() resets these to initial values.
191  Sawyer::Cached<Successors> successors_; // control flow successors out of final instruction
192  Sawyer::Cached<std::set<rose_addr_t> > ghostSuccessors_;// non-followed successors from opaque predicates, all insns
193  Sawyer::Cached<bool> isFunctionCall_; // is this block semantically a function call?
194  Sawyer::Cached<bool> isFunctionReturn_; // is this block semantically a return from the function?
195  Sawyer::Cached<bool> mayReturn_; // a function return is reachable from this basic block in the CFG
196  Sawyer::Cached<bool> popsStack_; // basic block has a net popping effect
197 
198  void clearCacheNS() const {
199  successors_.clear();
200  ghostSuccessors_.clear();
201  isFunctionCall_.clear();
202  isFunctionReturn_.clear();
203  mayReturn_.clear();
204  popsStack_.clear();
205  }
206 
207 public:
208  void copyCache(const BasicBlock::Ptr &other) {
209  ASSERT_not_null(other);
210  SAWYER_THREAD_TRAITS::LockGuard2 lock(mutex_, other->mutex_);
211  successors_ = other->successors_;
212  ghostSuccessors_ = other->ghostSuccessors_;
213  isFunctionCall_ = other->isFunctionCall_;
214  isFunctionReturn_ = other->isFunctionReturn_;
215  mayReturn_ = other->mayReturn_;
216  popsStack_ = other->popsStack_;
217  }
218 
219 
221  // Serialization
223 #ifdef ROSE_HAVE_BOOST_SERIALIZATION_LIB
224 private:
225  friend class boost::serialization::access;
226 
227  template<class S>
228  void serialize(S &s, const unsigned version) {
229  //s & boost::serialization::base_object<Sawyer::Attribute::Storage<> >(*this); -- not saved
230  s & BOOST_SERIALIZATION_NVP(isFrozen_);
231  s & BOOST_SERIALIZATION_NVP(startVa_);
232  s & BOOST_SERIALIZATION_NVP(comment_);
233  s & BOOST_SERIALIZATION_NVP(insns_);
234  s & boost::serialization::make_nvp("dispatcher_", semantics_.dispatcher);
235  s & boost::serialization::make_nvp("operators_", semantics_.operators);
236  s & boost::serialization::make_nvp("initialState_", semantics_.initialState);
237  s & boost::serialization::make_nvp("usingDispatcher_", semantics_.usingDispatcher);
238  s & boost::serialization::make_nvp("optionalPenultimateState_", semantics_.optionalPenultimateState);
239  s & BOOST_SERIALIZATION_NVP(dblocks_);
240  s & BOOST_SERIALIZATION_NVP(insnAddrMap_);
241  s & BOOST_SERIALIZATION_NVP(successors_);
242  s & BOOST_SERIALIZATION_NVP(ghostSuccessors_);
243  s & BOOST_SERIALIZATION_NVP(isFunctionCall_);
244  s & BOOST_SERIALIZATION_NVP(isFunctionReturn_);
245  s & BOOST_SERIALIZATION_NVP(mayReturn_);
246  if (version >= 1)
247  s & BOOST_SERIALIZATION_NVP(popsStack_);
248  }
249 #endif
250 
251 
253  // Constructors
255 protected:
256  BasicBlock() // needed for serialization
257  : isFrozen_(false), startVa_(0) {}
258 
259  // use instance() instead
260  BasicBlock(rose_addr_t startVa, const Partitioner &partitioner)
261  : isFrozen_(false), startVa_(startVa) {
262  semantics_.usingDispatcher = true;
263  init(partitioner);
264  }
265 
266 public:
272  static Ptr instance(rose_addr_t startVa, const Partitioner &partitioner) {
273  return Ptr(new BasicBlock(startVa, partitioner));
274  }
275 
281  virtual Ptr create(rose_addr_t startVa, const Partitioner &partitioner) const {
282  return instance(startVa, partitioner);
283  }
284 
286  // Cache
288 public:
292  void clearCache() {
293  SAWYER_THREAD_TRAITS::LockGuard lock(mutex_);
294  clearCacheNS();
295  }
296 
298  // Status
300 public:
306  bool isFrozen() const {
307  SAWYER_THREAD_TRAITS::LockGuard lock(mutex_);
308  return isFrozen_;
309  }
310 
318  const std::string& comment() const { return comment_; }
319  void comment(const std::string &s) { comment_ = s; }
323  // Instructions
326 public:
334  rose_addr_t address() const {
335  SAWYER_THREAD_TRAITS::LockGuard lock(mutex_);
336  return startVa_;
337  }
338 
346 
353  rose_addr_t fallthroughVa() const;
354 
358  size_t nInstructions() const {
359  SAWYER_THREAD_TRAITS::LockGuard lock(mutex_);
360  return insns_.size();
361  }
362 
370  bool isEmpty() const {
371  SAWYER_THREAD_TRAITS::LockGuard lock(mutex_);
372  return insns_.empty();
373  }
374 
381  SgAsmInstruction* instructionExists(rose_addr_t startVa) const;
382 
390 
398  const std::vector<SgAsmInstruction*>& instructions() const { return insns_; }
399 
418  void append(const Partitioner&, SgAsmInstruction*);
419 
426  void pop();
427 
434  std::set<rose_addr_t> explicitConstants() const;
435 
436 
438  // Static data blocks
440 public:
444  size_t nDataBlocks() const {
445  SAWYER_THREAD_TRAITS::LockGuard lock(mutex_);
446  return dblocks_.size();
447  }
448 
455 
463 
471  bool insertDataBlock(const DataBlock::Ptr&);
472 
478  const std::vector<DataBlock::Ptr>& dataBlocks() const { return dblocks_; }
479 
480 
482  // Semantics
484 public:
492 
500  void dropSemantics(const Partitioner&);
501 
510 
511 
512 
514  // Control flow
516 public:
527  const Sawyer::Cached<Successors>& successors() const { return successors_; }
528  void successors(const Successors&);
541  const Sawyer::Cached<std::set<rose_addr_t> >& ghostSuccessors() const { return ghostSuccessors_; }
542 
554  void insertSuccessor(rose_addr_t va, size_t nBits, EdgeType type=E_NORMAL, Confidence confidence=ASSUMED);
560  void clearSuccessors();
561 
562 
564  // Cached properties computed elsewhere
566 public:
575  const Sawyer::Cached<bool>& isFunctionCall() const { return isFunctionCall_; }
576 
584  const Sawyer::Cached<bool>& isFunctionReturn() const { return isFunctionReturn_; }
585 
592  const Sawyer::Cached<bool>& mayReturn() const { return mayReturn_; }
593 
599  const Sawyer::Cached<bool>& popsStack() const { return popsStack_; }
600 
601 
603  // Output
605 public:
609  std::string printableName() const;
610 
611 
613  // Private members for the partitioner
615 private:
616  friend class Partitioner;
617  void init(const Partitioner&);
618  void freeze() { isFrozen_ = true; semantics_.optionalPenultimateState = Sawyer::Nothing(); }
619  void thaw() { isFrozen_ = false; }
620  BasicBlockSemantics undropSemanticsNS(const Partitioner&);
621 };
622 
623 } // namespace
624 } // namespace
625 } // namespace
626 
627 // Class versions must be at global scope
628 BOOST_CLASS_VERSION(Rose::BinaryAnalysis::Partitioner2::BasicBlock, 1);
629 
630 #endif
EdgeType type() const
Type of successor.
Definition: BasicBlock.h:157
const std::string & comment() const
Comment.
Definition: BasicBlock.h:318
static Ptr instance(rose_addr_t startVa, const Partitioner &partitioner)
Static allocating constructor.
Definition: BasicBlock.h:272
void pop()
Undo the latest append.
const Sawyer::Cached< std::set< rose_addr_t > > & ghostSuccessors() const
Ghost successors.
Definition: BasicBlock.h:541
Confidence confidence() const
Confidence level of this successor.
Definition: BasicBlock.h:163
DataBlock::Ptr dataBlockExists(const DataBlock::Ptr &) const
Determine if this basic block contains the specified data block.
size_t nDataBlocks() const
Get the number of data blocks owned.
Definition: BasicBlock.h:444
void dropSemantics(const Partitioner &)
Drops semantic information.
EdgeType
Partitioner control flow edge types.
Definition: BasicTypes.h:50
void insertSuccessor(const BaseSemantics::SValuePtr &, EdgeType type=E_NORMAL, Confidence confidence=ASSUMED)
Insert a new successor.
Base class for machine instructions.
void comment(const std::string &s)
Comment.
Definition: BasicBlock.h:319
bool wasDropped
Whether the semantics had been dropped and reconstructed.
Definition: BasicBlock.h:66
bool usingDispatcher
Whether semantic state is up-to-date.
Definition: BasicBlock.h:57
BaseSemantics::StatePtr finalState() const
Return the final semantic state.
Definition: BasicBlock.h:94
void append(const Partitioner &, SgAsmInstruction *)
Append an instruction to a basic block.
BaseSemantics::RiscOperatorsPtr operators
Risc operators.
Definition: BasicBlock.h:45
Information related to instruction semantics.
Definition: BasicBlock.h:31
void clearCache()
Clear all cached data.
Definition: BasicBlock.h:292
Main namespace for the ROSE library.
Sawyer::Optional< BaseSemantics::StatePtr > optionalPenultimateState
The state just prior to executing the final instruction.
Definition: BasicBlock.h:63
rose_addr_t address() const
Get the address for a basic block.
Definition: BasicBlock.h:334
BasicBlockSemantics()
Construct an empty semantics object.
Definition: BasicBlock.h:70
boost::shared_ptr< class State > StatePtr
Shared-ownership pointer to a semantic state.
boost::shared_ptr< class Dispatcher > DispatcherPtr
Shared-ownership pointer to a semantics instruction dispatcher.
const Sawyer::Cached< bool > & popsStack() const
Pops stack property.
Definition: BasicBlock.h:599
AddressIntervalSet dataAddresses() const
Addresses that are part of static data.
Base classes for instruction semantics.
The value is an assumption without any proof.
Definition: BasicTypes.h:75
bool isSemanticsDropped() const
Determines whether semantics have been dropped.
Definition: BasicBlock.h:77
const Sawyer::Cached< bool > & isFunctionCall() const
Is a function call?
Definition: BasicBlock.h:575
SgAsmInstruction * instructionExists(rose_addr_t startVa) const
Determine if this basic block contains an instruction at a specific address.
std::string printableName() const
A printable name for this basic block.
Confidence
How sure are we of something.
Definition: BasicTypes.h:74
const Semantics::SValuePtr & expr() const
Symbolic expression for the successor address.
Definition: BasicBlock.h:154
bool isSemanticsError() const
Determines whether a semantics error was encountered.
Definition: BasicBlock.h:85
boost::shared_ptr< class RiscOperators > RiscOperatorsPtr
Shared-ownership pointer to a RISC operators object.
void clearSuccessors()
Clear all successor information.
bool isEmpty() const
Return true if this basic block has no instructions.
Definition: BasicBlock.h:370
BasicBlockSemantics semantics() const
Return information about semantics.
const Sawyer::Cached< bool > & isFunctionReturn() const
Is a function return?
Definition: BasicBlock.h:584
Normal control flow edge, nothing special.
Definition: BasicTypes.h:51
void confidence(Confidence c)
Confidence level of this successor.
Definition: BasicBlock.h:164
bool isFrozen() const
Determine if basic block is read-only.
Definition: BasicBlock.h:306
BasicBlockSemantics undropSemantics(const Partitioner &)
Undrop semantics.
void clear() const
Remove cached value.
Definition: Cached.h:69
Sawyer::SharedPointer< BasicBlock > Ptr
Shared pointer to a basic block.
Definition: BasicBlock.h:123
const std::vector< DataBlock::Ptr > & dataBlocks() const
Data blocks owned.
Definition: BasicBlock.h:478
Base class for reference counted objects.
Definition: SharedObject.h:64
BaseSemantics::DispatcherPtr dispatcher
How instructions are dispatched.
Definition: BasicBlock.h:39
bool insertDataBlock(const DataBlock::Ptr &)
Make this basic block own the specified data block.
size_t nInstructions() const
Get the number of instructions in this block.
Definition: BasicBlock.h:358
BaseSemantics::StatePtr initialState
Initial state for semantics.
Definition: BasicBlock.h:51
API and storage for attributes.
Definition: Attribute.h:208
const Sawyer::Cached< Successors > & successors() const
Control flow successors.
Definition: BasicBlock.h:527
Represents no value.
Definition: Optional.h:32
virtual Ptr create(rose_addr_t startVa, const Partitioner &partitioner) const
Virtual constructor.
Definition: BasicBlock.h:281
const std::vector< SgAsmInstruction * > & instructions() const
Get the instructions for this block.
Definition: BasicBlock.h:398
Partitions instructions into basic blocks and functions.
Definition: Partitioner.h:293
AddressIntervalSet insnAddresses() const
Get all instruction addresses.
const Sawyer::Cached< bool > & mayReturn() const
May-return property.
Definition: BasicBlock.h:592
std::set< rose_addr_t > explicitConstants() const
Set of explicit constants.
std::vector< Successor > Successors
All successors in no particular order.
Definition: BasicBlock.h:169
rose_addr_t fallthroughVa() const
Get the address after the end of the final instruction.