ROSE 0.11.145.147
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#include <Rose/BinaryAnalysis/Partitioner2/BasicTypes.h>
6
7#include <Rose/BinaryAnalysis/Partitioner2/Semantics.h>
8#include <Rose/SourceLocation.h>
9
10#include <Sawyer/Attribute.h>
11#include <Sawyer/Cached.h>
12#include <Sawyer/Map.h>
13#include <Sawyer/Optional.h>
14#include <Sawyer/SharedPointer.h>
15#include <Sawyer/Synchronization.h>
16
17#ifdef ROSE_HAVE_BOOST_SERIALIZATION_LIB
18#include <boost/serialization/access.hpp>
19#endif
20
21namespace Rose {
22namespace BinaryAnalysis {
23namespace Partitioner2 {
24
26
28// BasicBlockSemantics
30
102
105private:
107 EdgeType type_;
108 Confidence confidence_;
109
110#ifdef ROSE_HAVE_BOOST_SERIALIZATION_LIB
111private:
112 friend class boost::serialization::access;
113 template<class S> void serialize(S &s, const unsigned /*version*/);
114#endif
115
116public: // "protected" fails for boost-1.58.
117 // intentionally undocumented; needed for serialization
119 : type_(E_USER_DEFINED), confidence_(ASSUMED) {}
120
121public:
123 : expr_(expr), type_(type), confidence_(confidence) {}
124
126 const Semantics::SValuePtr& expr() const { return expr_; }
127
129 EdgeType type() const { return type_; }
130 void type(EdgeType t) { type_ = t; }
131
135 Confidence confidence() const { return confidence_; }
136 void confidence(Confidence c) { confidence_ = c; }
138};
139
141// BasicBlock
143
166public:
169
172
175
176private:
177 mutable SAWYER_THREAD_TRAITS::Mutex mutex_;
178
179 bool isFrozen_; // True when the object becomes read-only
180 rose_addr_t startVa_; // Starting address, perhaps redundant with insns_[0]->p_address
181 std::string comment_; // Mutli-line plain-text comment
182 std::vector<SgAsmInstruction*> insns_; // Instructions in the order they're executed
183 BasicBlockSemantics semantics_; // All semantics-related information
184 std::vector<DataBlockPtr> dblocks_; // Data blocks owned by this basic block, sorted
185 SourceLocation sourceLocation_; // Optional location of basic block in source code
186
187 // When a basic block gets lots of instructions some operations become slow due to the linear nature of the instruction
188 // list. Therefore, we also keep a mapping from instruction address to position in the list. The mapping is only used when
189 // the bigBlock size is reached.
190 static const size_t bigBlock_ = 200;
192 InsnAddrMap insnAddrMap_; // maps instruction address to index in insns_ vector
193
194 // The following members are caches either because their value is seldom needed and expensive to compute, or because
195 // the value is best computed at a higher layer than a single basic block (e.g., in the partitioner) yet it makes the
196 // most sense to store it here. Make sure clearCache() resets these to initial values.
197 Sawyer::Cached<Successors> successors_; // control flow successors out of final instruction
198 Sawyer::Cached<std::set<rose_addr_t> > ghostSuccessors_;// non-followed successors from opaque predicates, all insns
199 Sawyer::Cached<bool> isFunctionCall_; // is this block semantically a function call?
200 Sawyer::Cached<bool> isFunctionReturn_; // is this block semantically a return from the function?
201 Sawyer::Cached<bool> mayReturn_; // a function return is reachable from this basic block in the CFG
202 Sawyer::Cached<bool> popsStack_; // basic block has a net popping effect
203 void clearCacheNS() const;
204public:
205 void copyCache(const BasicBlockPtr &other);
206
207
209 // Serialization
211#ifdef ROSE_HAVE_BOOST_SERIALIZATION_LIB
212private:
213 friend class boost::serialization::access;
214 template<class S> void serializeCommon(S&, const unsigned version);
215 template<class S> void save(S&, const unsigned version) const;
216 template<class S> void load(S&, const unsigned version);
217 BOOST_SERIALIZATION_SPLIT_MEMBER();
218#endif
219
220
222 // Constructors
224protected:
225 BasicBlock(); // needed for serialization
226
227 // use instance() instead
228 BasicBlock(rose_addr_t startVa, const PartitionerConstPtr&);
229public:
230 ~BasicBlock();
231
232public:
238 static Ptr instance(rose_addr_t startVa, const PartitionerConstPtr &partitioner) {
239 return Ptr(new BasicBlock(startVa, partitioner));
240 }
241
247 virtual Ptr create(rose_addr_t startVa, const PartitionerConstPtr &partitioner) const {
248 return instance(startVa, partitioner);
249 }
250
252 // Cache
254public:
258 void clearCache() {
259 SAWYER_THREAD_TRAITS::LockGuard lock(mutex_);
260 clearCacheNS();
261 }
262
264 // Status
266public:
272 bool isFrozen() const {
273 SAWYER_THREAD_TRAITS::LockGuard lock(mutex_);
274 return isFrozen_;
275 }
276
284 const std::string& comment() const { return comment_; }
285 void comment(const std::string &s) { comment_ = s; }
291 const SourceLocation& sourceLocation() const { return sourceLocation_; }
292 void sourceLocation(const SourceLocation &loc) { sourceLocation_ = loc; }
297 // Instructions
299public:
307 rose_addr_t address() const {
308 SAWYER_THREAD_TRAITS::LockGuard lock(mutex_);
309 return startVa_;
310 }
311
319
326 rose_addr_t fallthroughVa() const;
327
331 size_t nInstructions() const {
332 SAWYER_THREAD_TRAITS::LockGuard lock(mutex_);
333 return insns_.size();
334 }
335
343 bool isEmpty() const {
344 SAWYER_THREAD_TRAITS::LockGuard lock(mutex_);
345 return insns_.empty();
346 }
347
354 SgAsmInstruction* instructionExists(rose_addr_t startVa) const;
355
363
381 const std::vector<SgAsmInstruction*>& instructions() const { return insns_; }
382
401
408 void pop();
409
416 std::set<rose_addr_t> explicitConstants() const;
417
418
420 // Static data blocks
422public:
426 size_t nDataBlocks() const;
427
434
442
452
461
467 const std::vector<DataBlockPtr>& dataBlocks() const { return dblocks_; }
468
469
471 // Semantics
473public:
481
490
499
500
501
503 // Control flow
505public:
516 const Sawyer::Cached<Successors>& successors() const { return successors_; }
517 void successors(const Successors&);
530 const Sawyer::Cached<std::set<rose_addr_t> >& ghostSuccessors() const { return ghostSuccessors_; }
531
543 void insertSuccessor(rose_addr_t va, size_t nBits, EdgeType type=E_NORMAL, Confidence confidence=ASSUMED);
550
551
553 // Cached properties computed elsewhere
555public:
564 const Sawyer::Cached<bool>& isFunctionCall() const { return isFunctionCall_; }
565 void isFunctionCall(bool flag) const { isFunctionCall_.set(flag); }
566
574 const Sawyer::Cached<bool>& isFunctionReturn() const { return isFunctionReturn_; }
575 void isFunctionReturn(bool flag) const { isFunctionReturn_.set(flag); }
576
583 const Sawyer::Cached<bool>& mayReturn() const { return mayReturn_; }
584 void mayReturn(bool flag) const { mayReturn_.set(flag); }
585
591 const Sawyer::Cached<bool>& popsStack() const { return popsStack_; }
592 void popsStack(bool flag) const { popsStack_.set(flag); }
593
594
596 // Output
598public:
602 std::string printableName() const;
603
604
606 // Private members for the partitioner
608private:
609 friend class Partitioner;
610 void init(const PartitionerConstPtr&);
611 void freeze() { isFrozen_ = true; semantics_.optionalPenultimateState = Sawyer::Nothing(); }
612 void thaw() { isFrozen_ = false; }
613 BasicBlockSemantics undropSemanticsNS(const PartitionerConstPtr&);
614
615 // Find an equivalent data block and replace it with the specified data block, or insert the specified data block.
616 void replaceOrInsertDataBlock(const DataBlockPtr&);
617};
618
619} // namespace
620} // namespace
621} // namespace
622
623#endif
624#endif
Information related to instruction semantics.
Definition BasicBlock.h:35
BaseSemantics::DispatcherPtr dispatcher
How instructions are dispatched.
Definition BasicBlock.h:43
bool wasDropped
Whether the semantics had been dropped and reconstructed.
Definition BasicBlock.h:70
BasicBlockSemantics()
Construct an empty semantics object.
Definition BasicBlock.h:74
bool usingDispatcher
Whether semantic state is up-to-date.
Definition BasicBlock.h:61
BaseSemantics::StatePtr initialState
Initial state for semantics.
Definition BasicBlock.h:55
bool isSemanticsDropped() const
Determines whether semantics have been dropped.
Definition BasicBlock.h:81
bool isSemanticsError() const
Determines whether a semantics error was encountered.
Definition BasicBlock.h:89
Sawyer::Optional< BaseSemantics::StatePtr > optionalPenultimateState
The state just prior to executing the final instruction.
Definition BasicBlock.h:67
BaseSemantics::RiscOperatorsPtr operators
Risc operators.
Definition BasicBlock.h:49
BaseSemantics::StatePtr finalState() const
Return the final semantic state.
Definition BasicBlock.h:98
const Semantics::SValuePtr & expr() const
Symbolic expression for the successor address.
Definition BasicBlock.h:126
void confidence(Confidence c)
Confidence level of this successor.
Definition BasicBlock.h:136
Confidence confidence() const
Confidence level of this successor.
Definition BasicBlock.h:135
BasicBlockSemantics semantics() const
Return information about semantics.
const Sawyer::Cached< bool > & popsStack() const
Pops stack property.
Definition BasicBlock.h:591
void clearCache()
Clear all cached data.
Definition BasicBlock.h:258
Sawyer::Optional< size_t > instructionIndex(SgAsmInstruction *) const
Position of an instruction.
const Sawyer::Cached< bool > & isFunctionCall() const
Is a function call?
Definition BasicBlock.h:564
const std::vector< DataBlockPtr > & dataBlocks() const
Data blocks owned.
Definition BasicBlock.h:467
AddressIntervalSet insnAddresses() const
Get all instruction addresses.
void successors(const Successors &)
Control flow successors.
SgAsmInstruction * instructionExists(rose_addr_t startVa) const
Determine if this basic block contains an instruction at a specific address.
const Sawyer::Cached< std::set< rose_addr_t > > & ghostSuccessors() const
Ghost successors.
Definition BasicBlock.h:530
void insertSuccessor(const BaseSemantics::SValuePtr &, EdgeType type=E_NORMAL, Confidence confidence=ASSUMED)
Insert a new successor.
void insertSuccessor(rose_addr_t va, size_t nBits, EdgeType type=E_NORMAL, Confidence confidence=ASSUMED)
Insert a new successor.
std::string printableName() const
A printable name for this basic block.
size_t nDataBlocks() const
Get the number of data blocks owned.
bool isEmpty() const
Return true if this basic block has no instructions.
Definition BasicBlock.h:343
Sawyer::Optional< size_t > instructionIndex(rose_addr_t) const
Position of an instruction.
void sourceLocation(const SourceLocation &loc)
Optional location in source code.
Definition BasicBlock.h:292
rose_addr_t fallthroughVa() const
Get the address after the end of the final instruction.
Sawyer::Optional< size_t > instructionExists(SgAsmInstruction *) const
Determines if this basic block contains the specified instruction.
static Ptr instance(rose_addr_t startVa, const PartitionerConstPtr &partitioner)
Static allocating constructor.
Definition BasicBlock.h:238
DataBlockPtr eraseDataBlock(const DataBlockPtr &)
Remove specified or equivalent data block from this basic block.
bool insertDataBlock(const DataBlockPtr &)
Make this basic block own the specified data block or equivalent data block.
void comment(const std::string &s)
Comment.
Definition BasicBlock.h:285
rose_addr_t address() const
Get the address for a basic block.
Definition BasicBlock.h:307
void clearSuccessors()
Clear all successor information.
void dropSemantics(const PartitionerConstPtr &)
Drops semantic information.
const SourceLocation & sourceLocation() const
Optional location in source code.
Definition BasicBlock.h:291
BasicBlockSuccessors Successors
All successors in no particular order.
Definition BasicBlock.h:174
Sawyer::SharedPointer< BasicBlock > Ptr
Shared pointer to a basic block.
Definition BasicBlock.h:168
void append(const PartitionerConstPtr &, SgAsmInstruction *)
Append an instruction to a basic block.
const Sawyer::Cached< bool > & isFunctionReturn() const
Is a function return?
Definition BasicBlock.h:574
virtual Ptr create(rose_addr_t startVa, const PartitionerConstPtr &partitioner) const
Virtual constructor.
Definition BasicBlock.h:247
std::set< rose_addr_t > explicitConstants() const
Set of explicit constants.
size_t nInstructions() const
Get the number of instructions in this block.
Definition BasicBlock.h:331
const Sawyer::Cached< Successors > & successors() const
Control flow successors.
Definition BasicBlock.h:516
DataBlockPtr dataBlockExists(const DataBlockPtr &) const
Determine if this basic block contains the specified data block or equivalent data block.
const std::vector< SgAsmInstruction * > & instructions() const
Get the instructions for this block.
Definition BasicBlock.h:381
bool isFrozen() const
Determine if basic block is read-only.
Definition BasicBlock.h:272
BasicBlockSemantics undropSemantics(const PartitionerConstPtr &)
Undrop semantics.
const Sawyer::Cached< bool > & mayReturn() const
May-return property.
Definition BasicBlock.h:583
AddressIntervalSet dataAddresses() const
Addresses that are part of static data.
const std::string & comment() const
Comment.
Definition BasicBlock.h:284
Partitions instructions into basic blocks and functions.
Information about a source location.
API and storage for attributes.
Definition Attribute.h:215
Implements cache data members.
Definition Cached.h:40
void set(const Value &x) const
Assign a new value.
Definition Cached.h:134
Container associating values with keys.
Definition Sawyer/Map.h:72
Represents no value.
Definition Optional.h:36
Holds a value or nothing.
Definition Optional.h:56
Base class for reference counted objects.
Reference-counting intrusive smart pointer.
Base class for machine instructions.
boost::shared_ptr< RiscOperators > RiscOperatorsPtr
Shared-ownership pointer to a RISC operators object.
boost::shared_ptr< Dispatcher > DispatcherPtr
Shared-ownership pointer to a semantics instruction dispatcher.
Sawyer::SharedPointer< const Partitioner > PartitionerConstPtr
Shared-ownership pointer for Partitioner.
std::vector< BasicBlockSuccessor > BasicBlockSuccessors
All successors in no particular order.
@ E_NORMAL
Normal control flow edge, nothing special.
@ ASSUMED
The value is an assumption without any proof.
Sawyer::SharedPointer< DataBlock > DataBlockPtr
Shared-ownership pointer for DataBlock.
The ROSE library.