ROSE  0.10.5.0
BasicBlock.h
1 #ifndef ROSE_Partitioner2_BasicBlock_H
2 #define ROSE_Partitioner2_BasicBlock_H
3 
4 #include <rosePublicConfig.h>
5 #ifdef ROSE_BUILD_BINARY_ANALYSIS_SUPPORT
6 
7 #include <Partitioner2/BasicTypes.h>
8 #include <Partitioner2/DataBlock.h>
9 #include <Partitioner2/Semantics.h>
10 #include <SourceLocation.h>
11 
12 #include <Sawyer/Attribute.h>
13 #include <Sawyer/Cached.h>
14 #include <Sawyer/Map.h>
15 #include <Sawyer/Optional.h>
16 #include <Sawyer/SharedPointer.h>
17 #include <Sawyer/Synchronization.h>
18 
19 #include <boost/serialization/access.hpp>
20 #include <boost/serialization/base_object.hpp>
21 #include <boost/serialization/set.hpp>
22 #include <boost/serialization/string.hpp>
23 #include <boost/serialization/vector.hpp>
24 
25 namespace Rose {
26 namespace BinaryAnalysis {
27 namespace Partitioner2 {
28 
30 
32 // BasicBlockSemantics
34 
40 public:
48 
54 
60 
66 
72 
74  bool wasDropped;
75 
76 public:
79  : usingDispatcher(false), wasDropped(false) {}
80 
85  bool isSemanticsDropped() const {
86  return dispatcher && !initialState;
87  }
88 
93  bool isSemanticsError() const {
94  return dispatcher && initialState && !usingDispatcher;
95  }
96 
103  return usingDispatcher && operators ? operators->currentState() : BaseSemantics::StatePtr();
104  }
105 };
106 
108 // BasicBlock
110 
133 public:
136 
138  class Successor {
139  private:
140  Semantics::SValuePtr expr_;
141  EdgeType type_;
142  Confidence confidence_;
143 
144 #ifdef ROSE_HAVE_BOOST_SERIALIZATION_LIB
145  private:
146  friend class boost::serialization::access;
147 
148  template<class S>
149  void serialize(S &s, const unsigned /*version*/) {
150  s & BOOST_SERIALIZATION_NVP(expr_);
151  s & BOOST_SERIALIZATION_NVP(type_);
152  s & BOOST_SERIALIZATION_NVP(confidence_);
153  }
154 #endif
155 
156  public: // "protected" fails for boost-1.58.
157  // intentionally undocumented; needed for serialization
158  Successor()
159  : type_(E_USER_DEFINED), confidence_(ASSUMED) {}
160 
161  public:
163  : expr_(expr), type_(type), confidence_(confidence) {}
164 
166  const Semantics::SValuePtr& expr() const { return expr_; }
167 
169  EdgeType type() const { return type_; }
170  void type(EdgeType t) { type_ = t; }
171 
175  Confidence confidence() const { return confidence_; }
176  void confidence(Confidence c) { confidence_ = c; }
178  };
179 
181  typedef std::vector<Successor> Successors;
182 
183 private:
184  mutable SAWYER_THREAD_TRAITS::Mutex mutex_;
185 
186  bool isFrozen_; // True when the object becomes read-only
187  rose_addr_t startVa_; // Starting address, perhaps redundant with insns_[0]->p_address
188  std::string comment_; // Mutli-line plain-text comment
189  std::vector<SgAsmInstruction*> insns_; // Instructions in the order they're executed
190  BasicBlockSemantics semantics_; // All semantics-related information
191  std::vector<DataBlock::Ptr> dblocks_; // Data blocks owned by this basic block, sorted
192  SourceLocation sourceLocation_; // Optional location of basic block in source code
193 
194  // When a basic block gets lots of instructions some operations become slow due to the linear nature of the instruction
195  // list. Therefore, we also keep a mapping from instruction address to position in the list. The mapping is only used when
196  // the bigBlock size is reached.
197  static const size_t bigBlock_ = 200;
199  InsnAddrMap insnAddrMap_; // maps instruction address to index in insns_ vector
200 
201  // The following members are caches either because their value is seldom needed and expensive to compute, or because
202  // the value is best computed at a higher layer than a single basic block (e.g., in the partitioner) yet it makes the
203  // most sense to store it here. Make sure clearCache() resets these to initial values.
204  Sawyer::Cached<Successors> successors_; // control flow successors out of final instruction
205  Sawyer::Cached<std::set<rose_addr_t> > ghostSuccessors_;// non-followed successors from opaque predicates, all insns
206  Sawyer::Cached<bool> isFunctionCall_; // is this block semantically a function call?
207  Sawyer::Cached<bool> isFunctionReturn_; // is this block semantically a return from the function?
208  Sawyer::Cached<bool> mayReturn_; // a function return is reachable from this basic block in the CFG
209  Sawyer::Cached<bool> popsStack_; // basic block has a net popping effect
210 
211  void clearCacheNS() const {
212  successors_.clear();
213  ghostSuccessors_.clear();
214  isFunctionCall_.clear();
215  isFunctionReturn_.clear();
216  mayReturn_.clear();
217  popsStack_.clear();
218  }
219 
220 public:
221  void copyCache(const BasicBlock::Ptr &other) {
222  ASSERT_not_null(other);
223  SAWYER_THREAD_TRAITS::LockGuard2 lock(mutex_, other->mutex_);
224  successors_ = other->successors_;
225  ghostSuccessors_ = other->ghostSuccessors_;
226  isFunctionCall_ = other->isFunctionCall_;
227  isFunctionReturn_ = other->isFunctionReturn_;
228  mayReturn_ = other->mayReturn_;
229  popsStack_ = other->popsStack_;
230  }
231 
232 
234  // Serialization
236 #ifdef ROSE_HAVE_BOOST_SERIALIZATION_LIB
237 private:
238  friend class boost::serialization::access;
239 
240  template<class S>
241  void serialize(S &s, const unsigned version) {
242  //s & boost::serialization::base_object<Sawyer::Attribute::Storage<> >(*this); -- not saved
243  s & BOOST_SERIALIZATION_NVP(isFrozen_);
244  s & BOOST_SERIALIZATION_NVP(startVa_);
245  s & BOOST_SERIALIZATION_NVP(comment_);
246  s & BOOST_SERIALIZATION_NVP(insns_);
247  s & boost::serialization::make_nvp("dispatcher_", semantics_.dispatcher);
248  s & boost::serialization::make_nvp("operators_", semantics_.operators);
249  s & boost::serialization::make_nvp("initialState_", semantics_.initialState);
250  s & boost::serialization::make_nvp("usingDispatcher_", semantics_.usingDispatcher);
251  s & boost::serialization::make_nvp("optionalPenultimateState_", semantics_.optionalPenultimateState);
252  s & BOOST_SERIALIZATION_NVP(dblocks_);
253  s & BOOST_SERIALIZATION_NVP(insnAddrMap_);
254  s & BOOST_SERIALIZATION_NVP(successors_);
255  s & BOOST_SERIALIZATION_NVP(ghostSuccessors_);
256  s & BOOST_SERIALIZATION_NVP(isFunctionCall_);
257  s & BOOST_SERIALIZATION_NVP(isFunctionReturn_);
258  s & BOOST_SERIALIZATION_NVP(mayReturn_);
259  if (version >= 1)
260  s & BOOST_SERIALIZATION_NVP(popsStack_);
261  if (version >= 2)
262  s & BOOST_SERIALIZATION_NVP(sourceLocation_);
263  }
264 #endif
265 
266 
268  // Constructors
270 protected:
271  BasicBlock() // needed for serialization
272  : isFrozen_(false), startVa_(0) {}
273 
274  // use instance() instead
275  BasicBlock(rose_addr_t startVa, const Partitioner &partitioner)
276  : isFrozen_(false), startVa_(startVa) {
277  semantics_.usingDispatcher = true;
278  init(partitioner);
279  }
280 
281 public:
287  static Ptr instance(rose_addr_t startVa, const Partitioner &partitioner) {
288  return Ptr(new BasicBlock(startVa, partitioner));
289  }
290 
296  virtual Ptr create(rose_addr_t startVa, const Partitioner &partitioner) const {
297  return instance(startVa, partitioner);
298  }
299 
301  // Cache
303 public:
307  void clearCache() {
308  SAWYER_THREAD_TRAITS::LockGuard lock(mutex_);
309  clearCacheNS();
310  }
311 
313  // Status
315 public:
321  bool isFrozen() const {
322  SAWYER_THREAD_TRAITS::LockGuard lock(mutex_);
323  return isFrozen_;
324  }
325 
333  const std::string& comment() const { return comment_; }
334  void comment(const std::string &s) { comment_ = s; }
340  const SourceLocation& sourceLocation() const { return sourceLocation_; }
341  void sourceLocation(const SourceLocation &loc) { sourceLocation_ = loc; }
345  // Instructions
348 public:
356  rose_addr_t address() const {
357  SAWYER_THREAD_TRAITS::LockGuard lock(mutex_);
358  return startVa_;
359  }
360 
368 
375  rose_addr_t fallthroughVa() const;
376 
380  size_t nInstructions() const {
381  SAWYER_THREAD_TRAITS::LockGuard lock(mutex_);
382  return insns_.size();
383  }
384 
392  bool isEmpty() const {
393  SAWYER_THREAD_TRAITS::LockGuard lock(mutex_);
394  return insns_.empty();
395  }
396 
403  SgAsmInstruction* instructionExists(rose_addr_t startVa) const;
404 
412 
420  const std::vector<SgAsmInstruction*>& instructions() const { return insns_; }
421 
440  void append(const Partitioner&, SgAsmInstruction*);
441 
448  void pop();
449 
456  std::set<rose_addr_t> explicitConstants() const;
457 
458 
460  // Static data blocks
462 public:
466  size_t nDataBlocks() const {
467  SAWYER_THREAD_TRAITS::LockGuard lock(mutex_);
468  return dblocks_.size();
469  }
470 
477 
485 
494  bool insertDataBlock(const DataBlock::Ptr&);
495 
504 
510  const std::vector<DataBlock::Ptr>& dataBlocks() const { return dblocks_; }
511 
512 
514  // Semantics
516 public:
524 
532  void dropSemantics(const Partitioner&);
533 
542 
543 
544 
546  // Control flow
548 public:
559  const Sawyer::Cached<Successors>& successors() const { return successors_; }
560  void successors(const Successors&);
573  const Sawyer::Cached<std::set<rose_addr_t> >& ghostSuccessors() const { return ghostSuccessors_; }
574 
586  void insertSuccessor(rose_addr_t va, size_t nBits, EdgeType type=E_NORMAL, Confidence confidence=ASSUMED);
592  void clearSuccessors();
593 
594 
596  // Cached properties computed elsewhere
598 public:
607  const Sawyer::Cached<bool>& isFunctionCall() const { return isFunctionCall_; }
608 
616  const Sawyer::Cached<bool>& isFunctionReturn() const { return isFunctionReturn_; }
617 
624  const Sawyer::Cached<bool>& mayReturn() const { return mayReturn_; }
625 
631  const Sawyer::Cached<bool>& popsStack() const { return popsStack_; }
632 
633 
635  // Output
637 public:
641  std::string printableName() const;
642 
643 
645  // Private members for the partitioner
647 private:
648  friend class Partitioner;
649  void init(const Partitioner&);
650  void freeze() { isFrozen_ = true; semantics_.optionalPenultimateState = Sawyer::Nothing(); }
651  void thaw() { isFrozen_ = false; }
652  BasicBlockSemantics undropSemanticsNS(const Partitioner&);
653 
654  // Find an equivalent data block and replace it with the specified data block, or insert the specified data block.
655  void replaceOrInsertDataBlock(const DataBlock::Ptr&);
656 };
657 
658 } // namespace
659 } // namespace
660 } // namespace
661 
662 // Class versions must be at global scope
663 BOOST_CLASS_VERSION(Rose::BinaryAnalysis::Partitioner2::BasicBlock, 2);
664 
665 #endif
666 #endif
EdgeType type() const
Type of successor.
Definition: BasicBlock.h:169
boost::shared_ptr< RiscOperators > RiscOperatorsPtr
Shared-ownership pointer to a RISC operators object.
const std::string & comment() const
Comment.
Definition: BasicBlock.h:333
Information about a source location.
static Ptr instance(rose_addr_t startVa, const Partitioner &partitioner)
Static allocating constructor.
Definition: BasicBlock.h:287
void pop()
Undo the latest append.
const Sawyer::Cached< std::set< rose_addr_t > > & ghostSuccessors() const
Ghost successors.
Definition: BasicBlock.h:573
Confidence confidence() const
Confidence level of this successor.
Definition: BasicBlock.h:175
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:466
void dropSemantics(const Partitioner &)
Drops semantic information.
EdgeType
Partitioner control flow edge types.
Definition: BasicTypes.h:55
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:334
bool wasDropped
Whether the semantics had been dropped and reconstructed.
Definition: BasicBlock.h:74
bool usingDispatcher
Whether semantic state is up-to-date.
Definition: BasicBlock.h:65
BaseSemantics::StatePtr finalState() const
Return the final semantic state.
Definition: BasicBlock.h:102
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:35
boost::shared_ptr< State > StatePtr
Shared-ownership pointer to a semantic state.
BaseSemantics::RiscOperatorsPtr operators
Risc operators.
Definition: BasicBlock.h:53
Information related to instruction semantics.
Definition: BasicBlock.h:39
void clearCache()
Clear all cached data.
Definition: BasicBlock.h:307
Main namespace for the ROSE library.
Sawyer::Optional< BaseSemantics::StatePtr > optionalPenultimateState
The state just prior to executing the final instruction.
Definition: BasicBlock.h:71
rose_addr_t address() const
Get the address for a basic block.
Definition: BasicBlock.h:356
BasicBlockSemantics()
Construct an empty semantics object.
Definition: BasicBlock.h:78
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:631
AddressIntervalSet dataAddresses() const
Addresses that are part of static data.
The value is an assumption without any proof.
Definition: BasicTypes.h:80
bool isSemanticsDropped() const
Determines whether semantics have been dropped.
Definition: BasicBlock.h:85
const Sawyer::Cached< bool > & isFunctionCall() const
Is a function call?
Definition: BasicBlock.h:607
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:79
const Semantics::SValuePtr & expr() const
Symbolic expression for the successor address.
Definition: BasicBlock.h:166
bool isSemanticsError() const
Determines whether a semantics error was encountered.
Definition: BasicBlock.h:93
const SourceLocation & sourceLocation() const
Optional location in source code.
Definition: BasicBlock.h:340
void clearSuccessors()
Clear all successor information.
bool isEmpty() const
Return true if this basic block has no instructions.
Definition: BasicBlock.h:392
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:616
Normal control flow edge, nothing special.
Definition: BasicTypes.h:56
void confidence(Confidence c)
Confidence level of this successor.
Definition: BasicBlock.h:176
bool isFrozen() const
Determine if basic block is read-only.
Definition: BasicBlock.h:321
BasicBlockSemantics undropSemantics(const Partitioner &)
Undrop semantics.
void sourceLocation(const SourceLocation &loc)
Optional location in source code.
Definition: BasicBlock.h:341
void clear() const
Remove cached value.
Definition: Cached.h:69
Sawyer::SharedPointer< BasicBlock > Ptr
Shared pointer to a basic block.
Definition: BasicBlock.h:135
const std::vector< DataBlock::Ptr > & dataBlocks() const
Data blocks owned.
Definition: BasicBlock.h:510
Base class for reference counted objects.
Definition: SharedObject.h:64
BaseSemantics::DispatcherPtr dispatcher
How instructions are dispatched.
Definition: BasicBlock.h:47
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:380
BaseSemantics::StatePtr initialState
Initial state for semantics.
Definition: BasicBlock.h:59
API and storage for attributes.
Definition: Attribute.h:208
const Sawyer::Cached< Successors > & successors() const
Control flow successors.
Definition: BasicBlock.h:559
Represents no value.
Definition: Optional.h:32
virtual Ptr create(rose_addr_t startVa, const Partitioner &partitioner) const
Virtual constructor.
Definition: BasicBlock.h:296
const std::vector< SgAsmInstruction * > & instructions() const
Get the instructions for this block.
Definition: BasicBlock.h:420
Partitions instructions into basic blocks and functions.
Definition: Partitioner.h:321
AddressIntervalSet insnAddresses() const
Get all instruction addresses.
const Sawyer::Cached< bool > & mayReturn() const
May-return property.
Definition: BasicBlock.h:624
std::set< rose_addr_t > explicitConstants() const
Set of explicit constants.
std::vector< Successor > Successors
All successors in no particular order.
Definition: BasicBlock.h:181
rose_addr_t fallthroughVa() const
Get the address after the end of the final instruction.