ROSE  0.9.10.25
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 
14 #include <boost/serialization/access.hpp>
15 #include <boost/serialization/base_object.hpp>
16 #include <boost/serialization/set.hpp>
17 #include <boost/serialization/string.hpp>
18 #include <boost/serialization/vector.hpp>
19 
20 namespace Rose {
21 namespace BinaryAnalysis {
22 namespace Partitioner2 {
23 
25 
43 public:
46 
48  class Successor {
49  private:
51  EdgeType type_;
52  Confidence confidence_;
53 
54 #ifdef ROSE_HAVE_BOOST_SERIALIZATION_LIB
55  private:
56  friend class boost::serialization::access;
57 
58  template<class S>
59  void serialize(S &s, const unsigned /*version*/) {
60  s & BOOST_SERIALIZATION_NVP(expr_);
61  s & BOOST_SERIALIZATION_NVP(type_);
62  s & BOOST_SERIALIZATION_NVP(confidence_);
63  }
64 #endif
65 
66  protected:
67  // intentionally undocumented; needed for serialization
68  Successor()
69  : type_(E_USER_DEFINED), confidence_(ASSUMED) {}
70 
71  public:
73  : expr_(expr), type_(type), confidence_(confidence) {}
74 
76  const Semantics::SValuePtr& expr() const { return expr_; }
77 
79  EdgeType type() const { return type_; }
80  void type(EdgeType t) { type_ = t; }
81 
85  Confidence confidence() const { return confidence_; }
86  void confidence(Confidence c) { confidence_ = c; }
88  };
89 
91  typedef std::vector<Successor> Successors;
92 
93 private:
94  bool isFrozen_; // True when the object becomes read-only
95  rose_addr_t startVa_; // Starting address, perhaps redundant with insns_[0]->p_address
96  std::string comment_; // Mutli-line plain-text comment
97  std::vector<SgAsmInstruction*> insns_; // Instructions in the order they're executed
98  BaseSemantics::DispatcherPtr dispatcher_; // How instructions are dispatched (null if no instructions)
99  BaseSemantics::RiscOperatorsPtr operators_; // Risc operators even if we're not using a dispatcher
100  BaseSemantics::StatePtr initialState_; // Initial state for semantics (null if dropped semantics)
101  bool usingDispatcher_; // True if dispatcher's state is up-to-date for the final instruction
102  Sawyer::Optional<BaseSemantics::StatePtr> optionalPenultimateState_; // One level of undo information
103  std::vector<DataBlock::Ptr> dblocks_; // Data blocks owned by this basic block, sorted
104 
105  // When a basic block gets lots of instructions some operations become slow due to the linear nature of the instruction
106  // list. Therefore, we also keep a mapping from instruction address to position in the list. The mapping is only used when
107  // the bigBlock size is reached.
108  static const size_t bigBlock_ = 200;
110  InsnAddrMap insnAddrMap_; // maps instruction address to index in insns_ vector
111 
112  // The following members are caches either because their value is seldom needed and expensive to compute, or because
113  // the value is best computed at a higher layer than a single basic block (e.g., in the partitioner) yet it makes the
114  // most sense to store it here. Make sure clearCache() resets these to initial values.
115  Sawyer::Cached<Successors> successors_; // control flow successors out of final instruction
116  Sawyer::Cached<std::set<rose_addr_t> > ghostSuccessors_;// non-followed successors from opaque predicates, all insns
117  Sawyer::Cached<bool> isFunctionCall_; // is this block semantically a function call?
118  Sawyer::Cached<bool> isFunctionReturn_; // is this block semantically a return from the function?
119  Sawyer::Cached<bool> mayReturn_; // a function return is reachable from this basic block in the CFG
120 
121  void clearCache() const {
122  successors_.clear();
123  ghostSuccessors_.clear();
124  isFunctionCall_.clear();
125  isFunctionReturn_.clear();
126  mayReturn_.clear();
127  }
128 
129 public:
130  void copyCache(const BasicBlock::Ptr other) {
131  successors_ = other->successors_;
132  ghostSuccessors_ = other->ghostSuccessors_;
133  isFunctionCall_ = other->isFunctionCall_;
134  isFunctionReturn_ = other->isFunctionReturn_;
135  mayReturn_ = other->mayReturn_;
136  }
137 
138 
140  // Serialization
142 #ifdef ROSE_HAVE_BOOST_SERIALIZATION_LIB
143 private:
144  friend class boost::serialization::access;
145 
146  template<class S>
147  void serialize(S &s, const unsigned /*version*/) {
148  //s & boost::serialization::base_object<Sawyer::Attribute::Storage<> >(*this); -- not saved
149  s & BOOST_SERIALIZATION_NVP(isFrozen_);
150  s & BOOST_SERIALIZATION_NVP(startVa_);
151  s & BOOST_SERIALIZATION_NVP(comment_);
152  s & BOOST_SERIALIZATION_NVP(insns_);
153  s & BOOST_SERIALIZATION_NVP(dispatcher_); // FIXME[Robb P Matzke 2016-11-07]
154  s & BOOST_SERIALIZATION_NVP(operators_); // FIXME[Robb P Matzke 2016-11-07]
155  s & BOOST_SERIALIZATION_NVP(initialState_);
156  s & BOOST_SERIALIZATION_NVP(usingDispatcher_);
157  s & BOOST_SERIALIZATION_NVP(optionalPenultimateState_);
158  s & BOOST_SERIALIZATION_NVP(dblocks_);
159  s & BOOST_SERIALIZATION_NVP(insnAddrMap_);
160  s & BOOST_SERIALIZATION_NVP(successors_);
161  s & BOOST_SERIALIZATION_NVP(ghostSuccessors_);
162  s & BOOST_SERIALIZATION_NVP(isFunctionCall_);
163  s & BOOST_SERIALIZATION_NVP(isFunctionReturn_);
164  s & BOOST_SERIALIZATION_NVP(mayReturn_);
165  }
166 #endif
167 
168 
170  // Constructors
172 protected:
173  BasicBlock() // needed for serialization
174  : isFrozen_(false), startVa_(0), usingDispatcher_(false) {}
175 
176  // use instance() instead
177  BasicBlock(rose_addr_t startVa, const Partitioner *partitioner)
178  : isFrozen_(false), startVa_(startVa), usingDispatcher_(true) { init(partitioner); }
179 
180 public:
186  static Ptr instance(rose_addr_t startVa, const Partitioner *partitioner) {
187  return Ptr(new BasicBlock(startVa, partitioner));
188  }
189 
195  virtual Ptr create(rose_addr_t startVa, const Partitioner *partitioner) const {
196  return instance(startVa, partitioner);
197  }
198 
199 
201  // Status
203 public:
207  bool isFrozen() const { return isFrozen_; }
208 
214  const std::string& comment() const { return comment_; }
215  void comment(const std::string &s) { comment_ = s; }
219  // Instructions
222 public:
228  rose_addr_t address() const { return startVa_; }
229 
235 
240  rose_addr_t fallthroughVa() const;
241 
243  size_t nInstructions() const { return insns_.size(); }
244 
250  bool isEmpty() const { return insns_.empty(); }
251 
256  SgAsmInstruction* instructionExists(rose_addr_t startVa) const;
257 
263 
269  const std::vector<SgAsmInstruction*>& instructions() const { return insns_; }
270 
285  void append(SgAsmInstruction*);
286 
291  void pop();
292 
293 
295  // Static data blocks
297 public:
299  size_t nDataBlocks() const { return dblocks_.size(); }
300 
305 
311 
317  bool insertDataBlock(const DataBlock::Ptr&);
318 
322  const std::vector<DataBlock::Ptr> dataBlocks() const { return dblocks_; }
323 
324 
326  // Semantics
328 public:
333  bool isSemanticsDropped() const { return dispatcher_ && !initialState_; }
334 
339  bool isSemanticsError() const { return dispatcher_ && initialState_ && !usingDispatcher_; }
340 
344  const BaseSemantics::StatePtr& initialState() const { return initialState_; }
345 
352 
358  const BaseSemantics::DispatcherPtr& dispatcher() const { return dispatcher_; }
359 
364  void dropSemantics();
365 
370  void undropSemantics();
371 
372 
374  // Control flow
376 public:
385  const Sawyer::Cached<Successors>& successors() const { return successors_; }
386  void successors(const Successors&);
397  const Sawyer::Cached<std::set<rose_addr_t> >& ghostSuccessors() const { return ghostSuccessors_; }
398 
408  void insertSuccessor(rose_addr_t va, size_t nBits, EdgeType type=E_NORMAL, Confidence confidence=ASSUMED);
412  void clearSuccessors();
413 
414 
416  // Cached properties computed elsewhere
418 public:
425  const Sawyer::Cached<bool>& isFunctionCall() const { return isFunctionCall_; }
426 
432  const Sawyer::Cached<bool>& isFunctionReturn() const { return isFunctionReturn_; }
433 
434 // /** Property: Initial stack pointer.
435 // *
436 // * Stack pointer at the entrance to the basic block relative to the stack pointer at the entrance to the basic block's
437 // * function. This property caches the value computed elsewhere. See also, @ref stackDeltaOut and @ref stackDelta.
438 // *
439 // * The @ref stackDeltaInConcrete method is a read-only accessor for the @ref stackDeltaIn property that returns the stack
440 // * delta expression as either a 64-bit signed value or the @ref SgAsmInstruction::INVALID_STACK_DELTA constant.
441 // *
442 // * @{ */
443 // BaseSemantics::SValuePtr stackDeltaIn() const;
444 // void stackDeltaIn(const BaseSemantics::SValuePtr&);
445 // int64_t stackDeltaInConcrete() const;
446 // /** @} */
447 //
448 // /** Property: Final stack pointer.
449 // *
450 // * Stack pointer at the exit of the basic block relative to the stack pointer at the entrance to the basic block's
451 // * function. This property caches the value computed elsewhere. See also, @ref stackDeltaIn and @ref stackDelta.
452 // *
453 // * The @ref stackDeltaOutConcrete method is a read-only accessor for the @ref stackDeltaOut property that returns the
454 // * stack delta expression as either a 64-bit signed value or the @ref SgAsmInstruction::INVALID_STACK_DELTA constant.
455 // *
456 // * @{ */
457 // BaseSemantics::SValuePtr stackDeltaOut() const;
458 // void stackDeltaOut(const BaseSemantics::SValuePtr&);
459 // int64_t stackDeltaOutConcrete() const;
460 // /** @} */
461 //
462 // /** Property: Stack delta.
463 // *
464 // * The stack delta is the difference between the final and initial stack pointers for this basic block if available. There
465 // * are two forms of this function: @ref stackDelta returns a symbolic expression or null, and @ref stackDeltaConcrete
466 // * returns a 64-bit signed value or the @ref SgAsmInstruction::INVALID_STACK_DELTA constant.
467 // *
468 // * The symbolic stack delta is a property that can be queried or set. It is set by the stack pointer analysis. The
469 // * concrete version is a wrapper that returns a numeric value from the symbolic value.
470 // *
471 // * @{ */
472 // BaseSemantics::SValuePtr stackDelta() const;
473 // void stackDelta(const BaseSemantics::SValuePtr&);
474 // int64_t stackDeltaConcrete() const;
475 // /** @} */
476 
481  const Sawyer::Cached<bool>& mayReturn() const { return mayReturn_; }
482 
483 
485  // Output
487 public:
489  std::string printableName() const;
490 
491 
493  // Private members for the partitioner
495 private:
496  friend class Partitioner;
497  void init(const Partitioner*);
498  void freeze() { isFrozen_ = true; optionalPenultimateState_ = Sawyer::Nothing(); }
499  void thaw() { isFrozen_ = false; }
500 };
501 
502 } // namespace
503 } // namespace
504 } // namespace
505 
506 #endif
EdgeType type() const
Type of successor.
Definition: BasicBlock.h:79
const std::string & comment() const
Comment.
Definition: BasicBlock.h:214
const BaseSemantics::StatePtr & initialState() const
Return the initial semantic state.
Definition: BasicBlock.h:344
void pop()
Undo the latest append.
virtual Ptr create(rose_addr_t startVa, const Partitioner *partitioner) const
Virtual constructor.
Definition: BasicBlock.h:195
const Sawyer::Cached< std::set< rose_addr_t > > & ghostSuccessors() const
Ghost successors.
Definition: BasicBlock.h:397
Confidence confidence() const
Confidence level of this successor.
Definition: BasicBlock.h:85
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:299
EdgeType
Partitioner control flow edge types.
Definition: BasicTypes.h:30
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:215
void append(SgAsmInstruction *)
Append an instruction to a basic block.
void dropSemantics()
Drops semantic information.
BaseSemantics::StatePtr finalState()
Return the final semantic state.
Main namespace for the ROSE library.
rose_addr_t address() const
Get the address for a basic block.
Definition: BasicBlock.h:228
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.
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:55
const Sawyer::Cached< bool > & isFunctionCall() const
Is a function call?
Definition: BasicBlock.h:425
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:54
const Semantics::SValuePtr & expr() const
Symbolic expression for the successor address.
Definition: BasicBlock.h:76
static Ptr instance(rose_addr_t startVa, const Partitioner *partitioner)
Static allocating constructor.
Definition: BasicBlock.h:186
boost::shared_ptr< class RiscOperators > RiscOperatorsPtr
Shared-ownership pointer to a RISC operators object.
const std::vector< DataBlock::Ptr > dataBlocks() const
Data blocks owned.
Definition: BasicBlock.h:322
void clearSuccessors()
Clear all successor information.
bool isEmpty() const
Return true if this basic block has no instructions.
Definition: BasicBlock.h:250
const Sawyer::Cached< bool > & isFunctionReturn() const
Is a function return?
Definition: BasicBlock.h:432
Normal control flow edge, nothing special.
Definition: BasicTypes.h:31
void confidence(Confidence c)
Confidence level of this successor.
Definition: BasicBlock.h:86
const BaseSemantics::DispatcherPtr & dispatcher() const
Return the dispatcher that was used for the semantics.
Definition: BasicBlock.h:358
bool isFrozen() const
Determine if basic block is read-only.
Definition: BasicBlock.h:207
void clear() const
Remove cached value.
Definition: Cached.h:69
bool isSemanticsDropped() const
Determines whether semantics have been dropped.
Definition: BasicBlock.h:333
Sawyer::SharedPointer< BasicBlock > Ptr
Shared pointer to a basic block.
Definition: BasicBlock.h:45
Base class for reference counted objects.
Definition: SharedObject.h:22
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:243
API and storage for attributes.
Definition: Attribute.h:208
const Sawyer::Cached< Successors > & successors() const
Control flow successors.
Definition: BasicBlock.h:385
Represents no value.
Definition: Optional.h:32
bool isSemanticsError() const
Determines whether a semantics error was encountered.
Definition: BasicBlock.h:339
const std::vector< SgAsmInstruction * > & instructions() const
Get the instructions for this block.
Definition: BasicBlock.h:269
Partitions instructions into basic blocks and functions.
Definition: Partitioner.h:292
AddressIntervalSet insnAddresses() const
Get all instruction addresses.
const Sawyer::Cached< bool > & mayReturn() const
May-return property.
Definition: BasicBlock.h:481
std::vector< Successor > Successors
All successors in no particular order.
Definition: BasicBlock.h:91
rose_addr_t fallthroughVa() const
Get the address after the end of the final instruction.