ROSE  0.9.9.199
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  void type(EdgeType t) { type_ = t; }
73 
77  Confidence confidence() const { return confidence_; }
78  void confidence(Confidence c) { confidence_ = c; }
80  };
81 
83  typedef std::vector<Successor> Successors;
84 
85 private:
86  bool isFrozen_; // True when the object becomes read-only
87  rose_addr_t startVa_; // Starting address, perhaps redundant with insns_[0]->p_address
88  std::string comment_; // Mutli-line plain-text comment
89  std::vector<SgAsmInstruction*> insns_; // Instructions in the order they're executed
90  BaseSemantics::DispatcherPtr dispatcher_; // How instructions are dispatched (null if no instructions)
91  BaseSemantics::RiscOperatorsPtr operators_; // Risc operators even if we're not using a dispatcher
92  BaseSemantics::StatePtr initialState_; // Initial state for semantics (null if dropped semantics)
93  bool usingDispatcher_; // True if dispatcher's state is up-to-date for the final instruction
94  Sawyer::Optional<BaseSemantics::StatePtr> optionalPenultimateState_; // One level of undo information
95  std::vector<DataBlock::Ptr> dblocks_; // Data blocks owned by this basic block, sorted
96 
97  // When a basic block gets lots of instructions some operations become slow due to the linear nature of the instruction
98  // list. Therefore, we also keep a mapping from instruction address to position in the list. The mapping is only used when
99  // the bigBlock size is reached.
100  static const size_t bigBlock_ = 200;
102  InsnAddrMap insnAddrMap_; // maps instruction address to index in insns_ vector
103 
104  // The following members are caches either because their value is seldom needed and expensive to compute, or because
105  // the value is best computed at a higher layer than a single basic block (e.g., in the partitioner) yet it makes the
106  // most sense to store it here. Make sure clearCache() resets these to initial values.
107  Sawyer::Cached<Successors> successors_; // control flow successors out of final instruction
108  Sawyer::Cached<std::set<rose_addr_t> > ghostSuccessors_;// non-followed successors from opaque predicates, all insns
109  Sawyer::Cached<bool> isFunctionCall_; // is this block semantically a function call?
110  Sawyer::Cached<bool> isFunctionReturn_; // is this block semantically a return from the function?
111  Sawyer::Cached<bool> mayReturn_; // a function return is reachable from this basic block in the CFG
112 
113  void clearCache() const {
114  successors_.clear();
115  ghostSuccessors_.clear();
116  isFunctionCall_.clear();
117  isFunctionReturn_.clear();
118  mayReturn_.clear();
119  }
120 
121 public:
122  void copyCache(const BasicBlock::Ptr other) {
123  successors_ = other->successors_;
124  ghostSuccessors_ = other->ghostSuccessors_;
125  isFunctionCall_ = other->isFunctionCall_;
126  isFunctionReturn_ = other->isFunctionReturn_;
127  mayReturn_ = other->mayReturn_;
128  }
129 
130 
132  // Serialization
134 #ifdef ROSE_HAVE_BOOST_SERIALIZATION_LIB
135 private:
136  friend class boost::serialization::access;
137 
138  template<class S>
139  void serialize(S &s, const unsigned version) {
140  //s & boost::serialization::base_object<Sawyer::Attribute::Storage<> >(*this); -- not saved
141  s & BOOST_SERIALIZATION_NVP(isFrozen_);
142  s & BOOST_SERIALIZATION_NVP(startVa_);
143  s & BOOST_SERIALIZATION_NVP(comment_);
144  s & BOOST_SERIALIZATION_NVP(insns_);
145  s & BOOST_SERIALIZATION_NVP(dispatcher_); // FIXME[Robb P Matzke 2016-11-07]
146  s & BOOST_SERIALIZATION_NVP(operators_); // FIXME[Robb P Matzke 2016-11-07]
147  s & BOOST_SERIALIZATION_NVP(initialState_);
148  s & BOOST_SERIALIZATION_NVP(usingDispatcher_);
149  s & BOOST_SERIALIZATION_NVP(optionalPenultimateState_);
150  s & BOOST_SERIALIZATION_NVP(dblocks_);
151  s & BOOST_SERIALIZATION_NVP(insnAddrMap_);
152  s & BOOST_SERIALIZATION_NVP(successors_);
153  s & BOOST_SERIALIZATION_NVP(ghostSuccessors_);
154  s & BOOST_SERIALIZATION_NVP(isFunctionCall_);
155  s & BOOST_SERIALIZATION_NVP(isFunctionReturn_);
156  s & BOOST_SERIALIZATION_NVP(mayReturn_);
157  }
158 #endif
159 
160 
162  // Constructors
164 protected:
165  BasicBlock() // needed for serialization
166  : isFrozen_(false), startVa_(0), usingDispatcher_(false) {}
167 
168  // use instance() instead
169  BasicBlock(rose_addr_t startVa, const Partitioner *partitioner)
170  : isFrozen_(false), startVa_(startVa), usingDispatcher_(true) { init(partitioner); }
171 
172 public:
178  static Ptr instance(rose_addr_t startVa, const Partitioner *partitioner) {
179  return Ptr(new BasicBlock(startVa, partitioner));
180  }
181 
187  virtual Ptr create(rose_addr_t startVa, const Partitioner *partitioner) const {
188  return instance(startVa, partitioner);
189  }
190 
191 
193  // Status
195 public:
199  bool isFrozen() const { return isFrozen_; }
200 
206  const std::string& comment() const { return comment_; }
207  void comment(const std::string &s) { comment_ = s; }
211  // Instructions
214 public:
220  rose_addr_t address() const { return startVa_; }
221 
227 
232  rose_addr_t fallthroughVa() const;
233 
235  size_t nInstructions() const { return insns_.size(); }
236 
242  bool isEmpty() const { return insns_.empty(); }
243 
248  SgAsmInstruction* instructionExists(rose_addr_t startVa) const;
249 
255 
261  const std::vector<SgAsmInstruction*>& instructions() const { return insns_; }
262 
277  void append(SgAsmInstruction*);
278 
283  void pop();
284 
285 
287  // Static data blocks
289 public:
291  size_t nDataBlocks() const { return dblocks_.size(); }
292 
297 
303 
309  bool insertDataBlock(const DataBlock::Ptr&);
310 
314  const std::vector<DataBlock::Ptr> dataBlocks() const { return dblocks_; }
315 
316 
318  // Semantics
320 public:
325  bool isSemanticsDropped() const { return dispatcher_ && !initialState_; }
326 
331  bool isSemanticsError() const { return dispatcher_ && initialState_ && !usingDispatcher_; }
332 
336  const BaseSemantics::StatePtr& initialState() const { return initialState_; }
337 
344 
350  const BaseSemantics::DispatcherPtr& dispatcher() const { return dispatcher_; }
351 
356  void dropSemantics();
357 
362  void undropSemantics();
363 
364 
366  // Control flow
368 public:
377  const Sawyer::Cached<Successors>& successors() const { return successors_; }
378  void successors(const Successors&);
389  const Sawyer::Cached<std::set<rose_addr_t> >& ghostSuccessors() const { return ghostSuccessors_; }
390 
400  void insertSuccessor(rose_addr_t va, size_t nBits, EdgeType type=E_NORMAL, Confidence confidence=ASSUMED);
404  void clearSuccessors();
405 
406 
408  // Cached properties computed elsewhere
410 public:
417  const Sawyer::Cached<bool>& isFunctionCall() const { return isFunctionCall_; }
418 
424  const Sawyer::Cached<bool>& isFunctionReturn() const { return isFunctionReturn_; }
425 
426 // /** Property: Initial stack pointer.
427 // *
428 // * Stack pointer at the entrance to the basic block relative to the stack pointer at the entrance to the basic block's
429 // * function. This property caches the value computed elsewhere. See also, @ref stackDeltaOut and @ref stackDelta.
430 // *
431 // * The @ref stackDeltaInConcrete method is a read-only accessor for the @ref stackDeltaIn property that returns the stack
432 // * delta expression as either a 64-bit signed value or the @ref SgAsmInstruction::INVALID_STACK_DELTA constant.
433 // *
434 // * @{ */
435 // BaseSemantics::SValuePtr stackDeltaIn() const;
436 // void stackDeltaIn(const BaseSemantics::SValuePtr&);
437 // int64_t stackDeltaInConcrete() const;
438 // /** @} */
439 //
440 // /** Property: Final stack pointer.
441 // *
442 // * Stack pointer at the exit of the basic block relative to the stack pointer at the entrance to the basic block's
443 // * function. This property caches the value computed elsewhere. See also, @ref stackDeltaIn and @ref stackDelta.
444 // *
445 // * The @ref stackDeltaOutConcrete method is a read-only accessor for the @ref stackDeltaOut property that returns the
446 // * stack delta expression as either a 64-bit signed value or the @ref SgAsmInstruction::INVALID_STACK_DELTA constant.
447 // *
448 // * @{ */
449 // BaseSemantics::SValuePtr stackDeltaOut() const;
450 // void stackDeltaOut(const BaseSemantics::SValuePtr&);
451 // int64_t stackDeltaOutConcrete() const;
452 // /** @} */
453 //
454 // /** Property: Stack delta.
455 // *
456 // * The stack delta is the difference between the final and initial stack pointers for this basic block if available. There
457 // * are two forms of this function: @ref stackDelta returns a symbolic expression or null, and @ref stackDeltaConcrete
458 // * returns a 64-bit signed value or the @ref SgAsmInstruction::INVALID_STACK_DELTA constant.
459 // *
460 // * The symbolic stack delta is a property that can be queried or set. It is set by the stack pointer analysis. The
461 // * concrete version is a wrapper that returns a numeric value from the symbolic value.
462 // *
463 // * @{ */
464 // BaseSemantics::SValuePtr stackDelta() const;
465 // void stackDelta(const BaseSemantics::SValuePtr&);
466 // int64_t stackDeltaConcrete() const;
467 // /** @} */
468 
473  const Sawyer::Cached<bool>& mayReturn() const { return mayReturn_; }
474 
475 
477  // Output
479 public:
481  std::string printableName() const;
482 
483 
485  // Private members for the partitioner
487 private:
488  friend class Partitioner;
489  void init(const Partitioner*);
490  void freeze() { isFrozen_ = true; optionalPenultimateState_ = Sawyer::Nothing(); }
491  void thaw() { isFrozen_ = false; }
492 };
493 
494 } // namespace
495 } // namespace
496 } // namespace
497 
498 #endif
EdgeType type() const
Type of successor.
Definition: BasicBlock.h:71
const std::string & comment() const
Comment.
Definition: BasicBlock.h:206
const BaseSemantics::StatePtr & initialState() const
Return the initial semantic state.
Definition: BasicBlock.h:336
void pop()
Undo the latest append.
virtual Ptr create(rose_addr_t startVa, const Partitioner *partitioner) const
Virtual constructor.
Definition: BasicBlock.h:187
const Sawyer::Cached< std::set< rose_addr_t > > & ghostSuccessors() const
Ghost successors.
Definition: BasicBlock.h:389
Confidence confidence() const
Confidence level of this successor.
Definition: BasicBlock.h:77
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:291
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:207
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:220
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:417
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:178
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:314
void clearSuccessors()
Clear all successor information.
bool isEmpty() const
Return true if this basic block has no instructions.
Definition: BasicBlock.h:242
const Sawyer::Cached< bool > & isFunctionReturn() const
Is a function return?
Definition: BasicBlock.h:424
Normal control flow edge, nothing special.
Definition: BasicTypes.h:31
void confidence(Confidence c)
Confidence level of this successor.
Definition: BasicBlock.h:78
const BaseSemantics::DispatcherPtr & dispatcher() const
Return the dispatcher that was used for the semantics.
Definition: BasicBlock.h:350
bool isFrozen() const
Determine if basic block is read-only.
Definition: BasicBlock.h:199
void clear() const
Remove cached value.
Definition: Cached.h:69
bool isSemanticsDropped() const
Determines whether semantics have been dropped.
Definition: BasicBlock.h:325
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:235
API and storage for attributes.
Definition: Attribute.h:208
const Sawyer::Cached< Successors > & successors() const
Control flow successors.
Definition: BasicBlock.h:377
Represents no value.
Definition: Optional.h:32
bool isSemanticsError() const
Determines whether a semantics error was encountered.
Definition: BasicBlock.h:331
const std::vector< SgAsmInstruction * > & instructions() const
Get the instructions for this block.
Definition: BasicBlock.h:261
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:473
std::vector< Successor > Successors
All successors in no particular order.
Definition: BasicBlock.h:83
rose_addr_t fallthroughVa() const
Get the address after the end of the final instruction.