ROSE  0.11.57.0
BasicBlock.h
1 #ifndef ROSE_BinaryAnalysis_Partitioner2_BasicBlock_H
2 #define ROSE_BinaryAnalysis_Partitioner2_BasicBlock_H
3 #include <featureTests.h>
4 #ifdef ROSE_ENABLE_BINARY_ANALYSIS
5 
6 #include <Rose/BinaryAnalysis/Partitioner2/BasicTypes.h>
7 #include <Rose/BinaryAnalysis/Partitioner2/DataBlock.h>
8 #include <Rose/BinaryAnalysis/Partitioner2/Semantics.h>
9 #include <Rose/SourceLocation.h>
10 
11 #include <Sawyer/Attribute.h>
12 #include <Sawyer/Cached.h>
13 #include <Sawyer/Map.h>
14 #include <Sawyer/Optional.h>
15 #include <Sawyer/SharedPointer.h>
16 #include <Sawyer/Synchronization.h>
17 
18 #include <boost/serialization/access.hpp>
19 #include <boost/serialization/base_object.hpp>
20 #include <boost/serialization/set.hpp>
21 #include <boost/serialization/string.hpp>
22 #include <boost/serialization/vector.hpp>
23 
24 namespace Rose {
25 namespace BinaryAnalysis {
26 namespace Partitioner2 {
27 
29 
31 // BasicBlockSemantics
33 
39 public:
47 
53 
59 
65 
71 
73  bool wasDropped;
74 
75 public:
78  : usingDispatcher(false), wasDropped(false) {}
79 
84  bool isSemanticsDropped() const {
85  return dispatcher && !initialState;
86  }
87 
92  bool isSemanticsError() const {
93  return dispatcher && initialState && !usingDispatcher;
94  }
95 
102  return usingDispatcher && operators ? operators->currentState() : BaseSemantics::StatePtr();
103  }
104 };
105 
107 // BasicBlock
109 
132 public:
135 
137  class Successor {
138  private:
139  Semantics::SValuePtr expr_;
140  EdgeType type_;
141  Confidence confidence_;
142 
143 #ifdef ROSE_HAVE_BOOST_SERIALIZATION_LIB
144  private:
145  friend class boost::serialization::access;
146 
147  template<class S>
148  void serialize(S &s, const unsigned /*version*/) {
149  s & BOOST_SERIALIZATION_NVP(expr_);
150  s & BOOST_SERIALIZATION_NVP(type_);
151  s & BOOST_SERIALIZATION_NVP(confidence_);
152  }
153 #endif
154 
155  public: // "protected" fails for boost-1.58.
156  // intentionally undocumented; needed for serialization
157  Successor()
158  : type_(E_USER_DEFINED), confidence_(ASSUMED) {}
159 
160  public:
162  : expr_(expr), type_(type), confidence_(confidence) {}
163 
165  const Semantics::SValuePtr& expr() const { return expr_; }
166 
168  EdgeType type() const { return type_; }
169  void type(EdgeType t) { type_ = t; }
170 
174  Confidence confidence() const { return confidence_; }
175  void confidence(Confidence c) { confidence_ = c; }
177  };
178 
180  typedef std::vector<Successor> Successors;
181 
182 private:
183  mutable SAWYER_THREAD_TRAITS::Mutex mutex_;
184 
185  bool isFrozen_; // True when the object becomes read-only
186  rose_addr_t startVa_; // Starting address, perhaps redundant with insns_[0]->p_address
187  std::string comment_; // Mutli-line plain-text comment
188  std::vector<SgAsmInstruction*> insns_; // Instructions in the order they're executed
189  BasicBlockSemantics semantics_; // All semantics-related information
190  std::vector<DataBlock::Ptr> dblocks_; // Data blocks owned by this basic block, sorted
191  SourceLocation sourceLocation_; // Optional location of basic block in source code
192 
193  // When a basic block gets lots of instructions some operations become slow due to the linear nature of the instruction
194  // list. Therefore, we also keep a mapping from instruction address to position in the list. The mapping is only used when
195  // the bigBlock size is reached.
196  static const size_t bigBlock_ = 200;
198  InsnAddrMap insnAddrMap_; // maps instruction address to index in insns_ vector
199 
200  // The following members are caches either because their value is seldom needed and expensive to compute, or because
201  // the value is best computed at a higher layer than a single basic block (e.g., in the partitioner) yet it makes the
202  // most sense to store it here. Make sure clearCache() resets these to initial values.
203  Sawyer::Cached<Successors> successors_; // control flow successors out of final instruction
204  Sawyer::Cached<std::set<rose_addr_t> > ghostSuccessors_;// non-followed successors from opaque predicates, all insns
205  Sawyer::Cached<bool> isFunctionCall_; // is this block semantically a function call?
206  Sawyer::Cached<bool> isFunctionReturn_; // is this block semantically a return from the function?
207  Sawyer::Cached<bool> mayReturn_; // a function return is reachable from this basic block in the CFG
208  Sawyer::Cached<bool> popsStack_; // basic block has a net popping effect
209 
210  void clearCacheNS() const {
211  successors_.clear();
212  ghostSuccessors_.clear();
213  isFunctionCall_.clear();
214  isFunctionReturn_.clear();
215  mayReturn_.clear();
216  popsStack_.clear();
217  }
218 
219 public:
220  void copyCache(const BasicBlock::Ptr &other) {
221  ASSERT_not_null(other);
222  SAWYER_THREAD_TRAITS::LockGuard2 lock(mutex_, other->mutex_);
223  successors_ = other->successors_;
224  ghostSuccessors_ = other->ghostSuccessors_;
225  isFunctionCall_ = other->isFunctionCall_;
226  isFunctionReturn_ = other->isFunctionReturn_;
227  mayReturn_ = other->mayReturn_;
228  popsStack_ = other->popsStack_;
229  }
230 
231 
233  // Serialization
235 #ifdef ROSE_HAVE_BOOST_SERIALIZATION_LIB
236 private:
237  friend class boost::serialization::access;
238 
239  template<class S>
240  void serialize(S &s, const unsigned version) {
241  //s & boost::serialization::base_object<Sawyer::Attribute::Storage<> >(*this); -- not saved
242  s & BOOST_SERIALIZATION_NVP(isFrozen_);
243  s & BOOST_SERIALIZATION_NVP(startVa_);
244  s & BOOST_SERIALIZATION_NVP(comment_);
245  s & BOOST_SERIALIZATION_NVP(insns_);
246  s & boost::serialization::make_nvp("dispatcher_", semantics_.dispatcher);
247  s & boost::serialization::make_nvp("operators_", semantics_.operators);
248  s & boost::serialization::make_nvp("initialState_", semantics_.initialState);
249  s & boost::serialization::make_nvp("usingDispatcher_", semantics_.usingDispatcher);
250  s & boost::serialization::make_nvp("optionalPenultimateState_", semantics_.optionalPenultimateState);
251  s & BOOST_SERIALIZATION_NVP(dblocks_);
252  s & BOOST_SERIALIZATION_NVP(insnAddrMap_);
253  s & BOOST_SERIALIZATION_NVP(successors_);
254  s & BOOST_SERIALIZATION_NVP(ghostSuccessors_);
255  s & BOOST_SERIALIZATION_NVP(isFunctionCall_);
256  s & BOOST_SERIALIZATION_NVP(isFunctionReturn_);
257  s & BOOST_SERIALIZATION_NVP(mayReturn_);
258  if (version >= 1)
259  s & BOOST_SERIALIZATION_NVP(popsStack_);
260  if (version >= 2)
261  s & BOOST_SERIALIZATION_NVP(sourceLocation_);
262  }
263 #endif
264 
265 
267  // Constructors
269 protected:
270  BasicBlock() // needed for serialization
271  : isFrozen_(false), startVa_(0) {}
272 
273  // use instance() instead
274  BasicBlock(rose_addr_t startVa, const Partitioner &partitioner)
275  : isFrozen_(false), startVa_(startVa) {
276  semantics_.usingDispatcher = true;
277  init(partitioner);
278  }
279 
280 public:
286  static Ptr instance(rose_addr_t startVa, const Partitioner &partitioner) {
287  return Ptr(new BasicBlock(startVa, partitioner));
288  }
289 
295  virtual Ptr create(rose_addr_t startVa, const Partitioner &partitioner) const {
296  return instance(startVa, partitioner);
297  }
298 
300  // Cache
302 public:
306  void clearCache() {
307  SAWYER_THREAD_TRAITS::LockGuard lock(mutex_);
308  clearCacheNS();
309  }
310 
312  // Status
314 public:
320  bool isFrozen() const {
321  SAWYER_THREAD_TRAITS::LockGuard lock(mutex_);
322  return isFrozen_;
323  }
324 
332  const std::string& comment() const { return comment_; }
333  void comment(const std::string &s) { comment_ = s; }
339  const SourceLocation& sourceLocation() const { return sourceLocation_; }
340  void sourceLocation(const SourceLocation &loc) { sourceLocation_ = loc; }
344  // Instructions
347 public:
355  rose_addr_t address() const {
356  SAWYER_THREAD_TRAITS::LockGuard lock(mutex_);
357  return startVa_;
358  }
359 
367 
374  rose_addr_t fallthroughVa() const;
375 
379  size_t nInstructions() const {
380  SAWYER_THREAD_TRAITS::LockGuard lock(mutex_);
381  return insns_.size();
382  }
383 
391  bool isEmpty() const {
392  SAWYER_THREAD_TRAITS::LockGuard lock(mutex_);
393  return insns_.empty();
394  }
395 
402  SgAsmInstruction* instructionExists(rose_addr_t startVa) const;
403 
411 
419  const std::vector<SgAsmInstruction*>& instructions() const { return insns_; }
420 
439  void append(const Partitioner&, SgAsmInstruction*);
440 
447  void pop();
448 
455  std::set<rose_addr_t> explicitConstants() const;
456 
457 
459  // Static data blocks
461 public:
465  size_t nDataBlocks() const {
466  SAWYER_THREAD_TRAITS::LockGuard lock(mutex_);
467  return dblocks_.size();
468  }
469 
476 
484 
493  bool insertDataBlock(const DataBlock::Ptr&);
494 
503 
509  const std::vector<DataBlock::Ptr>& dataBlocks() const { return dblocks_; }
510 
511 
513  // Semantics
515 public:
523 
531  void dropSemantics(const Partitioner&);
532 
541 
542 
543 
545  // Control flow
547 public:
558  const Sawyer::Cached<Successors>& successors() const { return successors_; }
559  void successors(const Successors&);
572  const Sawyer::Cached<std::set<rose_addr_t> >& ghostSuccessors() const { return ghostSuccessors_; }
573 
585  void insertSuccessor(rose_addr_t va, size_t nBits, EdgeType type=E_NORMAL, Confidence confidence=ASSUMED);
591  void clearSuccessors();
592 
593 
595  // Cached properties computed elsewhere
597 public:
606  const Sawyer::Cached<bool>& isFunctionCall() const { return isFunctionCall_; }
607 
615  const Sawyer::Cached<bool>& isFunctionReturn() const { return isFunctionReturn_; }
616 
623  const Sawyer::Cached<bool>& mayReturn() const { return mayReturn_; }
624 
630  const Sawyer::Cached<bool>& popsStack() const { return popsStack_; }
631 
632 
634  // Output
636 public:
640  std::string printableName() const;
641 
642 
644  // Private members for the partitioner
646 private:
647  friend class Partitioner;
648  void init(const Partitioner&);
649  void freeze() { isFrozen_ = true; semantics_.optionalPenultimateState = Sawyer::Nothing(); }
650  void thaw() { isFrozen_ = false; }
651  BasicBlockSemantics undropSemanticsNS(const Partitioner&);
652 
653  // Find an equivalent data block and replace it with the specified data block, or insert the specified data block.
654  void replaceOrInsertDataBlock(const DataBlock::Ptr&);
655 };
656 
657 } // namespace
658 } // namespace
659 } // namespace
660 
661 // Class versions must be at global scope
662 BOOST_CLASS_VERSION(Rose::BinaryAnalysis::Partitioner2::BasicBlock, 2);
663 
664 #endif
665 #endif
EdgeType type() const
Type of successor.
Definition: BasicBlock.h:168
boost::shared_ptr< RiscOperators > RiscOperatorsPtr
Shared-ownership pointer to a RISC operators object.
const std::string & comment() const
Comment.
Definition: BasicBlock.h:332
Information about a source location.
static Ptr instance(rose_addr_t startVa, const Partitioner &partitioner)
Static allocating constructor.
Definition: BasicBlock.h:286
void pop()
Undo the latest append.
const Sawyer::Cached< std::set< rose_addr_t > > & ghostSuccessors() const
Ghost successors.
Definition: BasicBlock.h:572
Confidence confidence() const
Confidence level of this successor.
Definition: BasicBlock.h:174
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:465
void dropSemantics(const Partitioner &)
Drops semantic information.
EdgeType
Partitioner control flow edge types.
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:333
bool wasDropped
Whether the semantics had been dropped and reconstructed.
Definition: BasicBlock.h:73
bool usingDispatcher
Whether semantic state is up-to-date.
Definition: BasicBlock.h:64
BaseSemantics::StatePtr finalState() const
Return the final semantic state.
Definition: BasicBlock.h:101
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:34
boost::shared_ptr< State > StatePtr
Shared-ownership pointer to a semantic state.
BaseSemantics::RiscOperatorsPtr operators
Risc operators.
Definition: BasicBlock.h:52
Information related to instruction semantics.
Definition: BasicBlock.h:38
void clearCache()
Clear all cached data.
Definition: BasicBlock.h:306
Main namespace for the ROSE library.
A container holding a set of values.
Definition: IntervalSet.h:55
Sawyer::Optional< BaseSemantics::StatePtr > optionalPenultimateState
The state just prior to executing the final instruction.
Definition: BasicBlock.h:70
rose_addr_t address() const
Get the address for a basic block.
Definition: BasicBlock.h:355
BasicBlockSemantics()
Construct an empty semantics object.
Definition: BasicBlock.h:77
boost::shared_ptr< Dispatcher > DispatcherPtr
Shared-ownership pointer to a semantics instruction dispatcher.
const Sawyer::Cached< bool > & popsStack() const
Pops stack property.
Definition: BasicBlock.h:630
AddressIntervalSet dataAddresses() const
Addresses that are part of static data.
Base classes for instruction semantics.
Definition: Dispatcher.h:18
The value is an assumption without any proof.
bool isSemanticsDropped() const
Determines whether semantics have been dropped.
Definition: BasicBlock.h:84
const Sawyer::Cached< bool > & isFunctionCall() const
Is a function call?
Definition: BasicBlock.h:606
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.
const Semantics::SValuePtr & expr() const
Symbolic expression for the successor address.
Definition: BasicBlock.h:165
bool isSemanticsError() const
Determines whether a semantics error was encountered.
Definition: BasicBlock.h:92
const SourceLocation & sourceLocation() const
Optional location in source code.
Definition: BasicBlock.h:339
void clearSuccessors()
Clear all successor information.
bool isEmpty() const
Return true if this basic block has no instructions.
Definition: BasicBlock.h:391
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:615
Normal control flow edge, nothing special.
void confidence(Confidence c)
Confidence level of this successor.
Definition: BasicBlock.h:175
bool isFrozen() const
Determine if basic block is read-only.
Definition: BasicBlock.h:320
BasicBlockSemantics undropSemantics(const Partitioner &)
Undrop semantics.
void sourceLocation(const SourceLocation &loc)
Optional location in source code.
Definition: BasicBlock.h:340
void clear() const
Remove cached value.
Definition: Cached.h:69
Sawyer::SharedPointer< BasicBlock > Ptr
Shared pointer to a basic block.
Definition: BasicBlock.h:134
const std::vector< DataBlock::Ptr > & dataBlocks() const
Data blocks owned.
Definition: BasicBlock.h:509
Base class for reference counted objects.
Definition: SharedObject.h:64
BaseSemantics::DispatcherPtr dispatcher
How instructions are dispatched.
Definition: BasicBlock.h:46
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:379
BaseSemantics::StatePtr initialState
Initial state for semantics.
Definition: BasicBlock.h:58
API and storage for attributes.
Definition: Attribute.h:208
const Sawyer::Cached< Successors > & successors() const
Control flow successors.
Definition: BasicBlock.h:558
Represents no value.
Definition: Optional.h:32
virtual Ptr create(rose_addr_t startVa, const Partitioner &partitioner) const
Virtual constructor.
Definition: BasicBlock.h:295
const std::vector< SgAsmInstruction * > & instructions() const
Get the instructions for this block.
Definition: BasicBlock.h:419
Partitions instructions into basic blocks and functions.
Definition: Partitioner.h:290
AddressIntervalSet insnAddresses() const
Get all instruction addresses.
const Sawyer::Cached< bool > & mayReturn() const
May-return property.
Definition: BasicBlock.h:623
std::set< rose_addr_t > explicitConstants() const
Set of explicit constants.
std::vector< Successor > Successors
All successors in no particular order.
Definition: BasicBlock.h:180
rose_addr_t fallthroughVa() const
Get the address after the end of the final instruction.