ROSE  0.9.9.109
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 
35 public:
38 
40  class Successor {
41  private:
43  EdgeType type_;
44  Confidence confidence_;
45 
46 #ifdef ROSE_HAVE_BOOST_SERIALIZATION_LIB
47  private:
48  friend class boost::serialization::access;
49 
50  template<class S>
51  void serialize(S &s, const unsigned version) {
52  s & BOOST_SERIALIZATION_NVP(expr_);
53  s & BOOST_SERIALIZATION_NVP(type_);
54  s & BOOST_SERIALIZATION_NVP(confidence_);
55  }
56 #endif
57 
58  protected:
59  // intentionally undocumented; needed for serialization
60  Successor()
61  : type_(E_USER_DEFINED), confidence_(ASSUMED) {}
62 
63  public:
65  : expr_(expr), type_(type), confidence_(confidence) {}
66 
68  const Semantics::SValuePtr& expr() const { return expr_; }
69 
71  EdgeType type() const { return type_; }
72 
76  Confidence confidence() const { return confidence_; }
77  void confidence(Confidence c) { confidence_ = c; }
79  };
80 
82  typedef std::vector<Successor> Successors;
83 
84 private:
85  bool isFrozen_; // True when the object becomes read-only
86  rose_addr_t startVa_; // Starting address, perhaps redundant with insns_[0]->p_address
87  std::string comment_; // Mutli-line plain-text comment
88  std::vector<SgAsmInstruction*> insns_; // Instructions in the order they're executed
89  BaseSemantics::DispatcherPtr dispatcher_; // How instructions are dispatched (null if no instructions)
90  BaseSemantics::RiscOperatorsPtr operators_; // Risc operators even if we're not using a dispatcher
91  BaseSemantics::StatePtr initialState_; // Initial state for semantics (null if dropped semantics)
92  bool usingDispatcher_; // True if dispatcher's state is up-to-date for the final instruction
93  Sawyer::Optional<BaseSemantics::StatePtr> optionalPenultimateState_; // One level of undo information
94  std::vector<DataBlock::Ptr> dblocks_; // Data blocks owned by this basic block, sorted
95 
96  // When a basic block gets lots of instructions some operations become slow due to the linear nature of the instruction
97  // list. Therefore, we also keep a mapping from instruction address to position in the list. The mapping is only used when
98  // the bigBlock size is reached.
99  static const size_t bigBlock_ = 200;
101  InsnAddrMap insnAddrMap_; // maps instruction address to index in insns_ vector
102 
103  // The following members are caches either because their value is seldom needed and expensive to compute, or because
104  // the value is best computed at a higher layer than a single basic block (e.g., in the partitioner) yet it makes the
105  // most sense to store it here. Make sure clearCache() resets these to initial values.
106  Sawyer::Cached<Successors> successors_; // control flow successors out of final instruction
107  Sawyer::Cached<std::set<rose_addr_t> > ghostSuccessors_;// non-followed successors from opaque predicates, all insns
108  Sawyer::Cached<bool> isFunctionCall_; // is this block semantically a function call?
109  Sawyer::Cached<bool> isFunctionReturn_; // is this block semantically a return from the function?
110  Sawyer::Cached<bool> mayReturn_; // a function return is reachable from this basic block in the CFG
111 
112  void clearCache() const {
113  successors_.clear();
114  ghostSuccessors_.clear();
115  isFunctionCall_.clear();
116  isFunctionReturn_.clear();
117  mayReturn_.clear();
118  }
119 
120 public:
121  void copyCache(const BasicBlock::Ptr other) {
122  successors_ = other->successors_;
123  ghostSuccessors_ = other->ghostSuccessors_;
124  isFunctionCall_ = other->isFunctionCall_;
125  isFunctionReturn_ = other->isFunctionReturn_;
126  mayReturn_ = other->mayReturn_;
127  }
128 
129 
131  // Serialization
133 #ifdef ROSE_HAVE_BOOST_SERIALIZATION_LIB
134 private:
135  friend class boost::serialization::access;
136 
137  template<class S>
138  void serialize(S &s, const unsigned version) {
139  //s & boost::serialization::base_object<Sawyer::Attribute::Storage<> >(*this); -- not saved
140  s & BOOST_SERIALIZATION_NVP(isFrozen_);
141  s & BOOST_SERIALIZATION_NVP(startVa_);
142  s & BOOST_SERIALIZATION_NVP(comment_);
143  s & BOOST_SERIALIZATION_NVP(insns_);
144  s & BOOST_SERIALIZATION_NVP(dispatcher_); // FIXME[Robb P Matzke 2016-11-07]
145  s & BOOST_SERIALIZATION_NVP(operators_); // FIXME[Robb P Matzke 2016-11-07]
146  s & BOOST_SERIALIZATION_NVP(initialState_);
147  s & BOOST_SERIALIZATION_NVP(usingDispatcher_);
148  s & BOOST_SERIALIZATION_NVP(optionalPenultimateState_);
149  s & BOOST_SERIALIZATION_NVP(dblocks_);
150  s & BOOST_SERIALIZATION_NVP(insnAddrMap_);
151  s & BOOST_SERIALIZATION_NVP(successors_);
152  s & BOOST_SERIALIZATION_NVP(ghostSuccessors_);
153  s & BOOST_SERIALIZATION_NVP(isFunctionCall_);
154  s & BOOST_SERIALIZATION_NVP(isFunctionReturn_);
155  s & BOOST_SERIALIZATION_NVP(mayReturn_);
156  }
157 #endif
158 
159 
161  // Constructors
163 protected:
164  BasicBlock() // needed for serialization
165  : isFrozen_(false), startVa_(0), usingDispatcher_(false) {}
166 
167  // use instance() instead
168  BasicBlock(rose_addr_t startVa, const Partitioner *partitioner)
169  : isFrozen_(false), startVa_(startVa), usingDispatcher_(true) { init(partitioner); }
170 
171 public:
177  static Ptr instance(rose_addr_t startVa, const Partitioner *partitioner) {
178  return Ptr(new BasicBlock(startVa, partitioner));
179  }
180 
186  virtual Ptr create(rose_addr_t startVa, const Partitioner *partitioner) const {
187  return instance(startVa, partitioner);
188  }
189 
190 
192  // Status
194 public:
198  bool isFrozen() const { return isFrozen_; }
199 
205  const std::string& comment() const { return comment_; }
206  void comment(const std::string &s) { comment_ = s; }
210  // Instructions
213 public:
219  rose_addr_t address() const { return startVa_; }
220 
226 
231  rose_addr_t fallthroughVa() const;
232 
234  size_t nInstructions() const { return insns_.size(); }
235 
241  bool isEmpty() const { return insns_.empty(); }
242 
247  SgAsmInstruction* instructionExists(rose_addr_t startVa) const;
248 
254 
260  const std::vector<SgAsmInstruction*>& instructions() const { return insns_; }
261 
276  void append(SgAsmInstruction*);
277 
282  void pop();
283 
284 
286  // Static data blocks
288 public:
290  size_t nDataBlocks() const { return dblocks_.size(); }
291 
296 
302 
308  bool insertDataBlock(const DataBlock::Ptr&);
309 
313  const std::vector<DataBlock::Ptr> dataBlocks() const { return dblocks_; }
314 
315 
317  // Semantics
319 public:
324  bool isSemanticsDropped() const { return dispatcher_ && !initialState_; }
325 
330  bool isSemanticsError() const { return dispatcher_ && initialState_ && !usingDispatcher_; }
331 
335  const BaseSemantics::StatePtr& initialState() const { return initialState_; }
336 
343 
349  const BaseSemantics::DispatcherPtr& dispatcher() const { return dispatcher_; }
350 
355  void dropSemantics();
356 
361  void undropSemantics();
362 
363 
365  // Control flow
367 public:
374  const Sawyer::Cached<Successors>& successors() const { return successors_; }
375 
384  const Sawyer::Cached<std::set<rose_addr_t> >& ghostSuccessors() const { return ghostSuccessors_; }
385 
395  void insertSuccessor(rose_addr_t va, size_t nBits, EdgeType type=E_NORMAL, Confidence confidence=ASSUMED);
399  void clearSuccessors();
400 
401 
403  // Cached properties computed elsewhere
405 public:
412  const Sawyer::Cached<bool>& isFunctionCall() const { return isFunctionCall_; }
413 
419  const Sawyer::Cached<bool>& isFunctionReturn() const { return isFunctionReturn_; }
420 
421 // /** Property: Initial stack pointer.
422 // *
423 // * Stack pointer at the entrance to the basic block relative to the stack pointer at the entrance to the basic block's
424 // * function. This property caches the value computed elsewhere. See also, @ref stackDeltaOut and @ref stackDelta.
425 // *
426 // * The @ref stackDeltaInConcrete method is a read-only accessor for the @ref stackDeltaIn property that returns the stack
427 // * delta expression as either a 64-bit signed value or the @ref SgAsmInstruction::INVALID_STACK_DELTA constant.
428 // *
429 // * @{ */
430 // BaseSemantics::SValuePtr stackDeltaIn() const;
431 // void stackDeltaIn(const BaseSemantics::SValuePtr&);
432 // int64_t stackDeltaInConcrete() const;
433 // /** @} */
434 //
435 // /** Property: Final stack pointer.
436 // *
437 // * Stack pointer at the exit of the basic block relative to the stack pointer at the entrance to the basic block's
438 // * function. This property caches the value computed elsewhere. See also, @ref stackDeltaIn and @ref stackDelta.
439 // *
440 // * The @ref stackDeltaOutConcrete method is a read-only accessor for the @ref stackDeltaOut property that returns the
441 // * stack delta expression as either a 64-bit signed value or the @ref SgAsmInstruction::INVALID_STACK_DELTA constant.
442 // *
443 // * @{ */
444 // BaseSemantics::SValuePtr stackDeltaOut() const;
445 // void stackDeltaOut(const BaseSemantics::SValuePtr&);
446 // int64_t stackDeltaOutConcrete() const;
447 // /** @} */
448 //
449 // /** Property: Stack delta.
450 // *
451 // * The stack delta is the difference between the final and initial stack pointers for this basic block if available. There
452 // * are two forms of this function: @ref stackDelta returns a symbolic expression or null, and @ref stackDeltaConcrete
453 // * returns a 64-bit signed value or the @ref SgAsmInstruction::INVALID_STACK_DELTA constant.
454 // *
455 // * The symbolic stack delta is a property that can be queried or set. It is set by the stack pointer analysis. The
456 // * concrete version is a wrapper that returns a numeric value from the symbolic value.
457 // *
458 // * @{ */
459 // BaseSemantics::SValuePtr stackDelta() const;
460 // void stackDelta(const BaseSemantics::SValuePtr&);
461 // int64_t stackDeltaConcrete() const;
462 // /** @} */
463 
468  const Sawyer::Cached<bool>& mayReturn() const { return mayReturn_; }
469 
470 
472  // Output
474 public:
476  std::string printableName() const;
477 
478 
480  // Private members for the partitioner
482 private:
483  friend class Partitioner;
484  void init(const Partitioner*);
485  void freeze() { isFrozen_ = true; optionalPenultimateState_ = Sawyer::Nothing(); }
486  void thaw() { isFrozen_ = false; }
487 };
488 
489 } // namespace
490 } // namespace
491 } // namespace
492 
493 #endif
EdgeType type() const
Type of successor.
Definition: BasicBlock.h:71
const std::string & comment() const
Comment.
Definition: BasicBlock.h:205
const BaseSemantics::StatePtr & initialState() const
Return the initial semantic state.
Definition: BasicBlock.h:335
void pop()
Undo the latest append.
virtual Ptr create(rose_addr_t startVa, const Partitioner *partitioner) const
Virtual constructor.
Definition: BasicBlock.h:186
const Sawyer::Cached< std::set< rose_addr_t > > & ghostSuccessors() const
Ghost successors.
Definition: BasicBlock.h:384
Confidence confidence() const
Confidence level of this successor.
Definition: BasicBlock.h:76
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:290
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:206
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:219
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:412
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:68
static Ptr instance(rose_addr_t startVa, const Partitioner *partitioner)
Static allocating constructor.
Definition: BasicBlock.h:177
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:313
void clearSuccessors()
Clear all successor information.
bool isEmpty() const
Return true if this basic block has no instructions.
Definition: BasicBlock.h:241
const Sawyer::Cached< bool > & isFunctionReturn() const
Is a function return?
Definition: BasicBlock.h:419
Normal control flow edge, nothing special.
Definition: BasicTypes.h:31
void confidence(Confidence c)
Confidence level of this successor.
Definition: BasicBlock.h:77
const BaseSemantics::DispatcherPtr & dispatcher() const
Return the dispatcher that was used for the semantics.
Definition: BasicBlock.h:349
bool isFrozen() const
Determine if basic block is read-only.
Definition: BasicBlock.h:198
void clear() const
Remove cached value.
Definition: Cached.h:69
bool isSemanticsDropped() const
Determines whether semantics have been dropped.
Definition: BasicBlock.h:324
Sawyer::SharedPointer< BasicBlock > Ptr
Shared pointer to a basic block.
Definition: BasicBlock.h:37
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:234
API and storage for attributes.
Definition: Attribute.h:208
const Sawyer::Cached< Successors > & successors() const
Control flow successors.
Definition: BasicBlock.h:374
Represents no value.
Definition: Optional.h:32
bool isSemanticsError() const
Determines whether a semantics error was encountered.
Definition: BasicBlock.h:330
const std::vector< SgAsmInstruction * > & instructions() const
Get the instructions for this block.
Definition: BasicBlock.h:260
Partitions instructions into basic blocks and functions.
Definition: Partitioner.h:289
AddressIntervalSet insnAddresses() const
Get all instruction addresses.
const Sawyer::Cached< bool > & mayReturn() const
May-return property.
Definition: BasicBlock.h:468
std::vector< Successor > Successors
All successors in no particular order.
Definition: BasicBlock.h:82
rose_addr_t fallthroughVa() const
Get the address after the end of the final instruction.