ROSE  0.9.11.56
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 
28 // BasicBlockSemantics
30 
36 public:
44 
50 
56 
62 
68 
70  bool wasDropped;
71 
72 public:
75  : usingDispatcher(false), wasDropped(false) {}
76 
81  bool isSemanticsDropped() const {
82  return dispatcher && !initialState;
83  }
84 
89  bool isSemanticsError() const {
90  return dispatcher && initialState && !usingDispatcher;
91  }
92 
99  return usingDispatcher && operators ? operators->currentState() : BaseSemantics::StatePtr();
100  }
101 };
102 
104 // BasicBlock
106 
129 public:
132 
134  class Successor {
135  private:
136  Semantics::SValuePtr expr_;
137  EdgeType type_;
138  Confidence confidence_;
139 
140 #ifdef ROSE_HAVE_BOOST_SERIALIZATION_LIB
141  private:
142  friend class boost::serialization::access;
143 
144  template<class S>
145  void serialize(S &s, const unsigned /*version*/) {
146  s & BOOST_SERIALIZATION_NVP(expr_);
147  s & BOOST_SERIALIZATION_NVP(type_);
148  s & BOOST_SERIALIZATION_NVP(confidence_);
149  }
150 #endif
151 
152  public: // "protected" fails for boost-1.58.
153  // intentionally undocumented; needed for serialization
154  Successor()
155  : type_(E_USER_DEFINED), confidence_(ASSUMED) {}
156 
157  public:
159  : expr_(expr), type_(type), confidence_(confidence) {}
160 
162  const Semantics::SValuePtr& expr() const { return expr_; }
163 
165  EdgeType type() const { return type_; }
166  void type(EdgeType t) { type_ = t; }
167 
171  Confidence confidence() const { return confidence_; }
172  void confidence(Confidence c) { confidence_ = c; }
174  };
175 
177  typedef std::vector<Successor> Successors;
178 
179 private:
180  mutable SAWYER_THREAD_TRAITS::Mutex mutex_;
181 
182  bool isFrozen_; // True when the object becomes read-only
183  rose_addr_t startVa_; // Starting address, perhaps redundant with insns_[0]->p_address
184  std::string comment_; // Mutli-line plain-text comment
185  std::vector<SgAsmInstruction*> insns_; // Instructions in the order they're executed
186  BasicBlockSemantics semantics_; // All semantics-related information
187  std::vector<DataBlock::Ptr> dblocks_; // Data blocks owned by this basic block, sorted
188 
189  // When a basic block gets lots of instructions some operations become slow due to the linear nature of the instruction
190  // list. Therefore, we also keep a mapping from instruction address to position in the list. The mapping is only used when
191  // the bigBlock size is reached.
192  static const size_t bigBlock_ = 200;
194  InsnAddrMap insnAddrMap_; // maps instruction address to index in insns_ vector
195 
196  // The following members are caches either because their value is seldom needed and expensive to compute, or because
197  // the value is best computed at a higher layer than a single basic block (e.g., in the partitioner) yet it makes the
198  // most sense to store it here. Make sure clearCache() resets these to initial values.
199  Sawyer::Cached<Successors> successors_; // control flow successors out of final instruction
200  Sawyer::Cached<std::set<rose_addr_t> > ghostSuccessors_;// non-followed successors from opaque predicates, all insns
201  Sawyer::Cached<bool> isFunctionCall_; // is this block semantically a function call?
202  Sawyer::Cached<bool> isFunctionReturn_; // is this block semantically a return from the function?
203  Sawyer::Cached<bool> mayReturn_; // a function return is reachable from this basic block in the CFG
204  Sawyer::Cached<bool> popsStack_; // basic block has a net popping effect
205 
206  void clearCacheNS() const {
207  successors_.clear();
208  ghostSuccessors_.clear();
209  isFunctionCall_.clear();
210  isFunctionReturn_.clear();
211  mayReturn_.clear();
212  popsStack_.clear();
213  }
214 
215 public:
216  void copyCache(const BasicBlock::Ptr &other) {
217  ASSERT_not_null(other);
218  SAWYER_THREAD_TRAITS::LockGuard2 lock(mutex_, other->mutex_);
219  successors_ = other->successors_;
220  ghostSuccessors_ = other->ghostSuccessors_;
221  isFunctionCall_ = other->isFunctionCall_;
222  isFunctionReturn_ = other->isFunctionReturn_;
223  mayReturn_ = other->mayReturn_;
224  popsStack_ = other->popsStack_;
225  }
226 
227 
229  // Serialization
231 #ifdef ROSE_HAVE_BOOST_SERIALIZATION_LIB
232 private:
233  friend class boost::serialization::access;
234 
235  template<class S>
236  void serialize(S &s, const unsigned version) {
237  //s & boost::serialization::base_object<Sawyer::Attribute::Storage<> >(*this); -- not saved
238  s & BOOST_SERIALIZATION_NVP(isFrozen_);
239  s & BOOST_SERIALIZATION_NVP(startVa_);
240  s & BOOST_SERIALIZATION_NVP(comment_);
241  s & BOOST_SERIALIZATION_NVP(insns_);
242  s & boost::serialization::make_nvp("dispatcher_", semantics_.dispatcher);
243  s & boost::serialization::make_nvp("operators_", semantics_.operators);
244  s & boost::serialization::make_nvp("initialState_", semantics_.initialState);
245  s & boost::serialization::make_nvp("usingDispatcher_", semantics_.usingDispatcher);
246  s & boost::serialization::make_nvp("optionalPenultimateState_", semantics_.optionalPenultimateState);
247  s & BOOST_SERIALIZATION_NVP(dblocks_);
248  s & BOOST_SERIALIZATION_NVP(insnAddrMap_);
249  s & BOOST_SERIALIZATION_NVP(successors_);
250  s & BOOST_SERIALIZATION_NVP(ghostSuccessors_);
251  s & BOOST_SERIALIZATION_NVP(isFunctionCall_);
252  s & BOOST_SERIALIZATION_NVP(isFunctionReturn_);
253  s & BOOST_SERIALIZATION_NVP(mayReturn_);
254  if (version >= 1)
255  s & BOOST_SERIALIZATION_NVP(popsStack_);
256  }
257 #endif
258 
259 
261  // Constructors
263 protected:
264  BasicBlock() // needed for serialization
265  : isFrozen_(false), startVa_(0) {}
266 
267  // use instance() instead
268  BasicBlock(rose_addr_t startVa, const Partitioner &partitioner)
269  : isFrozen_(false), startVa_(startVa) {
270  semantics_.usingDispatcher = true;
271  init(partitioner);
272  }
273 
274 public:
280  static Ptr instance(rose_addr_t startVa, const Partitioner &partitioner) {
281  return Ptr(new BasicBlock(startVa, partitioner));
282  }
283 
289  virtual Ptr create(rose_addr_t startVa, const Partitioner &partitioner) const {
290  return instance(startVa, partitioner);
291  }
292 
294  // Cache
296 public:
300  void clearCache() {
301  SAWYER_THREAD_TRAITS::LockGuard lock(mutex_);
302  clearCacheNS();
303  }
304 
306  // Status
308 public:
314  bool isFrozen() const {
315  SAWYER_THREAD_TRAITS::LockGuard lock(mutex_);
316  return isFrozen_;
317  }
318 
326  const std::string& comment() const { return comment_; }
327  void comment(const std::string &s) { comment_ = s; }
331  // Instructions
334 public:
342  rose_addr_t address() const {
343  SAWYER_THREAD_TRAITS::LockGuard lock(mutex_);
344  return startVa_;
345  }
346 
354 
361  rose_addr_t fallthroughVa() const;
362 
366  size_t nInstructions() const {
367  SAWYER_THREAD_TRAITS::LockGuard lock(mutex_);
368  return insns_.size();
369  }
370 
378  bool isEmpty() const {
379  SAWYER_THREAD_TRAITS::LockGuard lock(mutex_);
380  return insns_.empty();
381  }
382 
389  SgAsmInstruction* instructionExists(rose_addr_t startVa) const;
390 
398 
406  const std::vector<SgAsmInstruction*>& instructions() const { return insns_; }
407 
426  void append(const Partitioner&, SgAsmInstruction*);
427 
434  void pop();
435 
442  std::set<rose_addr_t> explicitConstants() const;
443 
444 
446  // Static data blocks
448 public:
452  size_t nDataBlocks() const {
453  SAWYER_THREAD_TRAITS::LockGuard lock(mutex_);
454  return dblocks_.size();
455  }
456 
463 
471 
480  bool insertDataBlock(const DataBlock::Ptr&);
481 
490 
496  const std::vector<DataBlock::Ptr>& dataBlocks() const { return dblocks_; }
497 
498 
500  // Semantics
502 public:
510 
518  void dropSemantics(const Partitioner&);
519 
528 
529 
530 
532  // Control flow
534 public:
545  const Sawyer::Cached<Successors>& successors() const { return successors_; }
546  void successors(const Successors&);
559  const Sawyer::Cached<std::set<rose_addr_t> >& ghostSuccessors() const { return ghostSuccessors_; }
560 
572  void insertSuccessor(rose_addr_t va, size_t nBits, EdgeType type=E_NORMAL, Confidence confidence=ASSUMED);
578  void clearSuccessors();
579 
580 
582  // Cached properties computed elsewhere
584 public:
593  const Sawyer::Cached<bool>& isFunctionCall() const { return isFunctionCall_; }
594 
602  const Sawyer::Cached<bool>& isFunctionReturn() const { return isFunctionReturn_; }
603 
610  const Sawyer::Cached<bool>& mayReturn() const { return mayReturn_; }
611 
617  const Sawyer::Cached<bool>& popsStack() const { return popsStack_; }
618 
619 
621  // Output
623 public:
627  std::string printableName() const;
628 
629 
631  // Private members for the partitioner
633 private:
634  friend class Partitioner;
635  void init(const Partitioner&);
636  void freeze() { isFrozen_ = true; semantics_.optionalPenultimateState = Sawyer::Nothing(); }
637  void thaw() { isFrozen_ = false; }
638  BasicBlockSemantics undropSemanticsNS(const Partitioner&);
639 
640  // Find an equivalent data block and replace it with the specified data block, or insert the specified data block.
641  void replaceOrInsertDataBlock(const DataBlock::Ptr&);
642 };
643 
644 } // namespace
645 } // namespace
646 } // namespace
647 
648 // Class versions must be at global scope
649 BOOST_CLASS_VERSION(Rose::BinaryAnalysis::Partitioner2::BasicBlock, 1);
650 
651 #endif
EdgeType type() const
Type of successor.
Definition: BasicBlock.h:165
const std::string & comment() const
Comment.
Definition: BasicBlock.h:326
static Ptr instance(rose_addr_t startVa, const Partitioner &partitioner)
Static allocating constructor.
Definition: BasicBlock.h:280
void pop()
Undo the latest append.
const Sawyer::Cached< std::set< rose_addr_t > > & ghostSuccessors() const
Ghost successors.
Definition: BasicBlock.h:559
Confidence confidence() const
Confidence level of this successor.
Definition: BasicBlock.h:171
DataBlock::Ptr dataBlockExists(const DataBlock::Ptr &) const
Determine if this basic block contains the specified data block or equivalent data block...
size_t nDataBlocks() const
Get the number of data blocks owned.
Definition: BasicBlock.h:452
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:327
bool wasDropped
Whether the semantics had been dropped and reconstructed.
Definition: BasicBlock.h:70
bool usingDispatcher
Whether semantic state is up-to-date.
Definition: BasicBlock.h:61
BaseSemantics::StatePtr finalState() const
Return the final semantic state.
Definition: BasicBlock.h:98
void append(const Partitioner &, SgAsmInstruction *)
Append an instruction to a basic block.
Sawyer::SharedPointer< DataBlock > Ptr
Shared pointer to a data block.
Definition: DataBlock.h:31
BaseSemantics::RiscOperatorsPtr operators
Risc operators.
Definition: BasicBlock.h:49
Information related to instruction semantics.
Definition: BasicBlock.h:35
void clearCache()
Clear all cached data.
Definition: BasicBlock.h:300
Main namespace for the ROSE library.
Sawyer::Optional< BaseSemantics::StatePtr > optionalPenultimateState
The state just prior to executing the final instruction.
Definition: BasicBlock.h:67
rose_addr_t address() const
Get the address for a basic block.
Definition: BasicBlock.h:342
BasicBlockSemantics()
Construct an empty semantics object.
Definition: BasicBlock.h:74
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:617
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:81
const Sawyer::Cached< bool > & isFunctionCall() const
Is a function call?
Definition: BasicBlock.h:593
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:162
bool isSemanticsError() const
Determines whether a semantics error was encountered.
Definition: BasicBlock.h:89
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:378
DataBlock::Ptr eraseDataBlock(const DataBlock::Ptr &)
Remove specified or equivalent data block from this basic block.
BasicBlockSemantics semantics() const
Return information about semantics.
const Sawyer::Cached< bool > & isFunctionReturn() const
Is a function return?
Definition: BasicBlock.h:602
Normal control flow edge, nothing special.
Definition: BasicTypes.h:51
void confidence(Confidence c)
Confidence level of this successor.
Definition: BasicBlock.h:172
bool isFrozen() const
Determine if basic block is read-only.
Definition: BasicBlock.h:314
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:131
const std::vector< DataBlock::Ptr > & dataBlocks() const
Data blocks owned.
Definition: BasicBlock.h:496
Base class for reference counted objects.
Definition: SharedObject.h:64
BaseSemantics::DispatcherPtr dispatcher
How instructions are dispatched.
Definition: BasicBlock.h:43
bool insertDataBlock(const DataBlock::Ptr &)
Make this basic block own the specified data block or equivalent data block.
size_t nInstructions() const
Get the number of instructions in this block.
Definition: BasicBlock.h:366
BaseSemantics::StatePtr initialState
Initial state for semantics.
Definition: BasicBlock.h:55
API and storage for attributes.
Definition: Attribute.h:208
const Sawyer::Cached< Successors > & successors() const
Control flow successors.
Definition: BasicBlock.h:545
Represents no value.
Definition: Optional.h:32
virtual Ptr create(rose_addr_t startVa, const Partitioner &partitioner) const
Virtual constructor.
Definition: BasicBlock.h:289
const std::vector< SgAsmInstruction * > & instructions() const
Get the instructions for this block.
Definition: BasicBlock.h:406
Partitions instructions into basic blocks and functions.
Definition: Partitioner.h:317
AddressIntervalSet insnAddresses() const
Get all instruction addresses.
const Sawyer::Cached< bool > & mayReturn() const
May-return property.
Definition: BasicBlock.h:610
std::set< rose_addr_t > explicitConstants() const
Set of explicit constants.
std::vector< Successor > Successors
All successors in no particular order.
Definition: BasicBlock.h:177
rose_addr_t fallthroughVa() const
Get the address after the end of the final instruction.