Static Value-Flow Analysis
Loading...
Searching...
No Matches
Public Member Functions | Static Public Member Functions | Protected Attributes | Private Member Functions | Private Attributes | List of all members
SVF::DCHGraph Class Reference

Dwarf based CHG. More...

#include <DCHG.h>

Inheritance diagram for SVF::DCHGraph:
SVF::CommonCHGraph SVF::GenericGraph< DCHNode, DCHEdge >

Public Member Functions

 DCHGraph ()
 
virtual ~DCHGraph ()
 
virtual void buildCHG (bool extend)
 
void dump (const std::string &filename)
 
void print (void)
 
virtual bool csHasVFnsBasedonCHA (const CallICFGNode *cs) override
 
virtual const VFunSetgetCSVFsBasedonCHA (const CallICFGNode *cs) override
 
virtual bool csHasVtblsBasedonCHA (CallBase *cs)
 
virtual bool csHasVtblsBasedonCHA (const CallICFGNode *cs) override
 
virtual const VTableSetgetCSVtblsBasedonCHA (const CallICFGNode *cs) override
 
virtual void getVFnsFromVtbls (const CallICFGNode *cs, const VTableSet &vtbls, VFunSet &virtualFunctions) override
 
virtual bool isBase (const DIType *a, const DIType *b, bool firstField)
 
virtual bool isFieldOf (const DIType *f, const DIType *b)
 Returns true if f is a field of b (fields from getFieldTypes).
 
const DITypegetCanonicalType (const DIType *t)
 
const DITypegetFieldType (const DIType *base, unsigned idx)
 Returns the type of field number idx (flattened) in base.
 
const std::vector< const DIType * > & getFieldTypes (const DIType *base)
 Returns a vector of the types of all fields in base.
 
unsigned getNumFields (const DIType *base)
 
const Set< const DIType * > & getAggs (const DIType *base)
 Returns all the aggregates contained (transitively) in base.
 
bool isFirstField (const DIType *f, const DIType *b)
 
- Public Member Functions inherited from SVF::CommonCHGraph
virtual ~CommonCHGraph ()
 
CHGKind getKind (void) const
 
- Public Member Functions inherited from SVF::GenericGraph< DCHNode, DCHEdge >
 GenericGraph ()
 Constructor.
 
virtual ~GenericGraph ()
 Destructor.
 
void destroy ()
 Release memory.
 
iterator begin ()
 Iterators.
 
const_iterator begin () const
 
iterator end ()
 
const_iterator end () const
 
void addGNode (NodeID id, NodeType *node)
 Add a Node.
 
NodeTypegetGNode (NodeID id) const
 Get a node.
 
bool hasGNode (NodeID id) const
 Has a node.
 
void removeGNode (NodeType *node)
 Delete a node.
 
u32_t getTotalNodeNum () const
 Get total number of node/edge.
 
u32_t getTotalEdgeNum () const
 
void incNodeNum ()
 Increase number of node/edge.
 
void incEdgeNum ()
 

Static Public Member Functions

static const DITypestripQualifiers (const DIType *)
 Returns the DIType beneath the qualifiers. Does not strip away "DW_TAG_members".
 
static const DITypestripArray (const DIType *)
 Returns the DIType beneath all qualifiers and arrays.
 
static bool teq (const DIType *t1, const DIType *t2)
 
static std::string diTypeToStr (const DIType *)
 Returns a human-readable version of the DIType.
 
static bool isAgg (const DIType *t)
 
static bool classof (const CommonCHGraph *chg)
 

Protected Attributes

bool extended = false
 Whether this CHG is an extended CHG (first-field). Set by buildCHG.
 
Map< const DIType *, DCHNode * > diTypeToNodeMap
 Maps DITypes to their nodes.
 
Map< const GlobalObjVar *, const DIType * > vtblToTypeMap
 Maps VTables to the DIType associated with them.
 
Map< const DIType *, NodeBSchaMap
 Maps types to all children (i.e. CHA).
 
Map< const DIType *, NodeBSchaFFMap
 Maps types to all children but also considering first field.
 
Map< const DIType *, VTableSetvtblCHAMap
 Maps types to a set with their vtable and all their children's.
 
Map< const CallICFGNode *, VFunSetcsCHAMap
 Maps callsites to a set of potential virtual functions based on CHA.
 
Map< const DIType *, const DIType * > canonicalTypeMap
 Maps types to their canonical type (many-to-one).
 
Set< const DIType * > canonicalTypes
 Set of all possible canonical types (i.e. values of canonicalTypeMap).
 
Map< const DIType *, std::vector< const DIType * > > fieldTypes
 Maps types to their flattened fields' types.
 
Map< const DIType *, Set< const DIType * > > containingAggs
 Maps aggregate types to all the aggregate types it transitively contains.
 
- Protected Attributes inherited from SVF::CommonCHGraph
CHGKind kind
 
- Protected Attributes inherited from SVF::GenericGraph< DCHNode, DCHEdge >
IDToNodeMapTy IDToNodeMap
 node map
 

Private Member Functions

void handleDIBasicType (const DIBasicType *basicType)
 Construction helper to process DIBasicTypes.
 
void handleDICompositeType (const DICompositeType *compositeType)
 Construction helper to process DICompositeTypes.
 
void handleDIDerivedType (const DIDerivedType *derivedType)
 Construction helper to process DIDerivedTypes.
 
void handleDISubroutineType (const DISubroutineType *subroutineType)
 Construction helper to process DISubroutineTypes.
 
void buildVTables ()
 Finds all defined virtual functions and attaches them to nodes.
 
const NodeBScha (const DIType *type, bool firstField)
 Returns a set of all children of type (CHA). Also gradually builds chaMap.
 
void handleTypedef (const DIType *typedefType)
 Attaches the typedef(s) to the base node.
 
void flatten (const DICompositeType *type)
 Populates fieldTypes for type and all its elements.
 
void gatherAggs (const DICompositeType *type)
 Populates containingAggs for type and all its elements.
 
DCHNodegetOrCreateNode (const DIType *type)
 Creates a node from type, or returns it if it exists.
 
const DITypegetCSStaticType (CallBase *cs) const
 Retrieves the metadata associated with a virtual callsite.
 
const DITypegetCSStaticType (const CallICFGNode *cs) const
 
bool hasNode (const DIType *type)
 Checks if a node exists for type.
 
DCHNodegetNode (const DIType *type)
 Returns the node for type (nullptr if it doesn't exist).
 
DCHEdgeaddEdge (const DIType *t1, const DIType *t2, DCHEdge::GEdgeKind et)
 Creates an edge between from t1 to t2.
 
DCHEdgehasEdge (const DIType *t1, const DIType *t2, DCHEdge::GEdgeKind et)
 Returns the edge between t1 and t2 if it exists, returns nullptr otherwise.
 

Private Attributes

NodeID numTypes
 Number of types (nodes) in the graph.
 

Additional Inherited Members

- Public Types inherited from SVF::CommonCHGraph
enum  CHGKind { Standard , DI }
 
- Public Types inherited from SVF::GenericGraph< DCHNode, DCHEdge >
typedef DCHNode NodeType
 
typedef DCHEdge EdgeType
 
typedef OrderedMap< NodeID, NodeType * > IDToNodeMapTy
 NodeID to GenericNode map.
 
typedef IDToNodeMapTy::iterator iterator
 Node Iterators.
 
typedef IDToNodeMapTy::const_iterator const_iterator
 
- Public Attributes inherited from SVF::GenericGraph< DCHNode, DCHEdge >
u32_t edgeNum
 total num of node
 
u32_t nodeNum
 total num of edge
 

Detailed Description

Dwarf based CHG.

Definition at line 206 of file DCHG.h.

Constructor & Destructor Documentation

◆ DCHGraph()

SVF::DCHGraph::DCHGraph ( )
inline

Definition at line 231 of file DCHG.h.

232 :numTypes(0) // vfID(0), buildingCHGTime(0) {
233 {
234 this->kind = DI;
235 }
CHGKind kind
Definition CHG.h:73
NodeID numTypes
Number of types (nodes) in the graph.
Definition DCHG.h:445

◆ ~DCHGraph()

virtual SVF::DCHGraph::~DCHGraph ( )
inlinevirtual

Definition at line 237 of file DCHG.h.

237{ };

Member Function Documentation

◆ addEdge()

DCHEdge * DCHGraph::addEdge ( const DIType t1,
const DIType t2,
DCHEdge::GEdgeKind  et 
)
private

Creates an edge between from t1 to t2.

Definition at line 435 of file DCHG.cpp.

436{
437 DCHNode *src = getOrCreateNode(t1);
438 DCHNode *dst = getOrCreateNode(t2);
439
440 DCHEdge *edge = hasEdge(t1, t2, et);
441 if (edge == nullptr)
442 {
443 // Create a new edge.
444 edge = new DCHEdge(src, dst, et);
445 src->addOutgoingEdge(edge);
446 dst->addIncomingEdge(edge);
447 }
448
449 return edge;
450}
DCHEdge * hasEdge(const DIType *t1, const DIType *t2, DCHEdge::GEdgeKind et)
Returns the edge between t1 and t2 if it exists, returns nullptr otherwise.
Definition DCHG.cpp:452
DCHNode * getOrCreateNode(const DIType *type)
Creates a node from type, or returns it if it exists.
Definition DCHG.cpp:408
bool addIncomingEdge(EdgeType *inEdge)
Add incoming and outgoing edges.
bool addOutgoingEdge(EdgeType *outEdge)
llvm::IRBuilder IRBuilder
Definition BasicTypes.h:74

◆ buildCHG()

void DCHGraph::buildCHG ( bool  extend)
virtual

Builds the CHG from DWARF debug information. extend determines whether to extend the CHG with first field edges.

Definition at line 471 of file DCHG.cpp.

472{
475 for (Module &M : LLVMModuleSet::getLLVMModuleSet()->getLLVMModules())
476 {
477 finder.processModule(M);
478 }
479
480 // Create the void node regardless of whether it appears.
481 getOrCreateNode(nullptr);
482 // Find any char type.
483 const DIType *charType = nullptr;
484 /*
485 * We want void at the top, char as a child, and everything is a child of char:
486 * void
487 * |
488 * char
489 * / | \
490 * x y z
491 */
492
493
494 for (const DIType *type : finder.types())
495 {
496 if (const DIBasicType *basicType = SVFUtil::dyn_cast<DIBasicType>(type))
497 {
498 if (basicType->getEncoding() == dwarf::DW_ATE_unsigned_char
499 || basicType->getEncoding() == dwarf::DW_ATE_signed_char)
500 {
501 charType = type;
502 }
503
505 }
506 else if (const DICompositeType *compositeType = SVFUtil::dyn_cast<DICompositeType>(type))
507 {
509 }
510 else if (const DIDerivedType *derivedType = SVFUtil::dyn_cast<DIDerivedType>(type))
511 {
513 }
514 else if (const DISubroutineType *subroutineType = SVFUtil::dyn_cast<DISubroutineType>(type))
515 {
517 }
518 else
519 {
520 assert(false && "DCHGraph::buildCHG: unexpected DIType.");
521 }
522 }
523
524 buildVTables();
525
526 // Build the void/char/everything else relation.
527 if (extended && charType != nullptr)
528 {
529 // void <-- char
531 // char <-- x, char <-- y, ...
532 for (iterator nodeI = begin(); nodeI != end(); ++nodeI)
533 {
534 // Everything without a parent gets char as a parent.
535 if (nodeI->second->getDIType() != nullptr
536 && nodeI->second->getOutEdges().size() == 0)
537 {
538 addEdge(nodeI->second->getDIType(), charType, DCHEdge::STD_DEF);
539 }
540 }
541 }
542
543 if (Options::PrintDCHG())
544 {
545 print();
546 }
547}
newitem type
Definition cJSON.cpp:2739
@ STD_DEF
Definition DCHG.h:36
void handleDIDerivedType(const DIDerivedType *derivedType)
Construction helper to process DIDerivedTypes.
Definition DCHG.cpp:97
DCHEdge * addEdge(const DIType *t1, const DIType *t2, DCHEdge::GEdgeKind et)
Creates an edge between from t1 to t2.
Definition DCHG.cpp:435
void buildVTables()
Finds all defined virtual functions and attaches them to nodes.
Definition DCHG.cpp:166
void handleDICompositeType(const DICompositeType *compositeType)
Construction helper to process DICompositeTypes.
Definition DCHG.cpp:27
void print(void)
Definition DCHG.cpp:1142
void handleDISubroutineType(const DISubroutineType *subroutineType)
Construction helper to process DISubroutineTypes.
Definition DCHG.cpp:133
void handleDIBasicType(const DIBasicType *basicType)
Construction helper to process DIBasicTypes.
Definition DCHG.cpp:22
bool extended
Whether this CHG is an extended CHG (first-field). Set by buildCHG.
Definition DCHG.h:360
IDToNodeMapTy::iterator iterator
Node Iterators.
static const Option< bool > PrintDCHG
Definition Options.h:179
llvm::DISubroutineType DISubroutineType
Definition BasicTypes.h:240
llvm::DebugInfoFinder DebugInfoFinder
Definition BasicTypes.h:239
llvm::DIDerivedType DIDerivedType
Definition BasicTypes.h:238
llvm::Module Module
Definition BasicTypes.h:84
llvm::DIType DIType
Definition BasicTypes.h:236
llvm::DIBasicType DIBasicType
Definition BasicTypes.h:241
llvm::DICompositeType DICompositeType
Definition BasicTypes.h:237

◆ buildVTables()

void DCHGraph::buildVTables ( )
private

Finds all defined virtual functions and attaches them to nodes.

Definition at line 166 of file DCHG.cpp.

167{
168 for (Module &M : LLVMModuleSet::getLLVMModuleSet()->getLLVMModules())
169 {
170 for (Module::const_global_iterator gvI = M.global_begin(); gvI != M.global_end(); ++gvI)
171 {
172 // Though this will return more than GlobalVariables, we only care about GlobalVariables (for the vtbls).
173 const GlobalVariable *gv = SVFUtil::dyn_cast<const GlobalVariable>(&*gvI);
174 if (gv == nullptr) continue;
175 if (gv->hasMetadata(cppUtil::ctir::vtMDName) && gv->getNumOperands() > 0)
176 {
177 DIType *type = SVFUtil::dyn_cast<DIType>(gv->getMetadata(cppUtil::ctir::vtMDName));
178 assert(type && "DCHG::buildVTables: bad metadata for ctir.vt");
182 SVFUtil::cast<GlobalObjVar>(PAG::getPAG()->getGNode(i));
183 node->setVTable(globalObjVar);
185
187 for (unsigned nthVtbl = 0; nthVtbl < vtbls->getNumOperands(); ++nthVtbl)
188 {
189 const ConstantArray *vtbl = SVFUtil::dyn_cast<ConstantArray>(vtbls->getOperand(nthVtbl));
190 assert(vtbl && "Element of vtbl struct not an array");
191
192 std::vector<const Function* > &vfns = node->getVfnVector(nthVtbl);
193
194 // Iterating over the vtbl, we will run into:
195 // 1. i8* null (don't care for now).
196 // 2. i8* inttoptr ... (don't care for now).
197 // 3. i8* bitcast ... (we only care when a function pointer is being bitcasted).
198 for (unsigned cN = 0; cN < vtbl->getNumOperands(); ++cN)
199 {
200 Constant *c = vtbl->getOperand(cN);
201 if (SVFUtil::isa<ConstantPointerNull>(c))
202 {
203 // Don't care for now.
204 continue;
205 }
206
207 ConstantExpr *ce = SVFUtil::dyn_cast<ConstantExpr>(c);
208 assert(ce && "non-ConstantExpr, non-ConstantPointerNull in vtable?");
209 if (ce->getOpcode() == Instruction::BitCast)
210 {
211 // Could be a GlobalAlias which we don't care about, or a virtual/thunk function.
212 const Function* vfn = SVFUtil::dyn_cast<Function>(ce->getOperand(0));
213 if (vfn != nullptr)
214 {
215 vfns.push_back(vfn);
216 }
217 }
218 }
219 }
220 }
221 }
222 }
223}
const DIType * getCanonicalType(const DIType *t)
Definition DCHG.cpp:724
Map< const GlobalObjVar *, const DIType * > vtblToTypeMap
Maps VTables to the DIType associated with them.
Definition DCHG.h:364
std::vector< const Function * > & getVfnVector(unsigned n)
Return the nth virtual function vector in the vtable.
Definition DCHG.h:179
void setVTable(const GlobalObjVar *vtbl)
Definition DCHG.h:162
NodeType * getGNode(NodeID id) const
Get a node.
static LLVMModuleSet * getLLVMModuleSet()
Definition LLVMModule.h:129
NodeID getObjectNode(const Value *V)
static SVFIR * getPAG(bool buildFromFile=false)
Singleton design here to make sure we only have one instance during any analysis.
Definition SVFIR.h:116
const std::string vtMDName
Definition CppUtil.h:171
const ConstantStruct * getVtblStruct(const GlobalValue *vtbl)
Definition CppUtil.cpp:323
llvm::GlobalVariable GlobalVariable
Definition BasicTypes.h:130
llvm::ConstantStruct ConstantStruct
Definition BasicTypes.h:106
u32_t NodeID
Definition GeneralType.h:56
llvm::ConstantArray ConstantArray
Definition BasicTypes.h:123
llvm::Function Function
Definition BasicTypes.h:85
llvm::Constant Constant
Definition BasicTypes.h:124
llvm::ConstantExpr ConstantExpr
Definition BasicTypes.h:120

◆ cha()

const NodeBS & DCHGraph::cha ( const DIType type,
bool  firstField 
)
private

Returns a set of all children of type (CHA). Also gradually builds chaMap.

Definition at line 225 of file DCHG.cpp.

226{
229
230 // Check if we've already computed.
231 if (cacheMap.find(type) != cacheMap.end())
232 {
233 return cacheMap[type];
234 }
235
237 const DCHNode *node = getOrCreateNode(type);
238 // Consider oneself a child, otherwise the recursion will just come up with nothing.
239 children.set(node->getId());
240 for (const DCHEdge *edge : node->getInEdges())
241 {
242 // Don't care about anything but inheritance, first-field, and standard def. edges.
243 if ( edge->getEdgeKind() != DCHEdge::INHERITANCE
244 && edge->getEdgeKind() != DCHEdge::FIRST_FIELD
245 && edge->getEdgeKind() != DCHEdge::STD_DEF)
246 {
247 continue;
248 }
249
250 // We only care about first-field edges if the flag is on.
251 if (!firstField && edge->getEdgeKind() == DCHEdge::FIRST_FIELD)
252 {
253 continue;
254 }
255
256 const NodeBS &cchildren = cha(edge->getSrcNode()->getDIType(), firstField);
257 // Children's children are my children.
258 for (NodeID cchild : cchildren)
259 {
260 children.set(cchild);
261 }
262 }
263
264 // Cache results.
265 cacheMap.insert({type, children});
266 // Return the permanent object; we're returning a reference.
267 return cacheMap[type];
268}
@ FIRST_FIELD
Definition DCHG.h:35
@ INHERITANCE
Definition DCHG.h:33
const NodeBS & cha(const DIType *type, bool firstField)
Returns a set of all children of type (CHA). Also gradually builds chaMap.
Definition DCHG.cpp:225
Map< const DIType *, NodeBS > chaFFMap
Maps types to all children but also considering first field.
Definition DCHG.h:368
Map< const DIType *, NodeBS > chaMap
Maps types to all children (i.e. CHA).
Definition DCHG.h:366
NodeID getId() const
Get ID.
Definition SVFValue.h:158
iter_range< typename GenericGraphTraits< GraphType >::ChildIteratorType > children(const typename GenericGraphTraits< GraphType >::NodeRef &G)

◆ classof()

static bool SVF::DCHGraph::classof ( const CommonCHGraph chg)
inlinestatic

Definition at line 285 of file DCHG.h.

286 {
287 return chg->getKind() == DI;
288 }

◆ csHasVFnsBasedonCHA()

virtual bool SVF::DCHGraph::csHasVFnsBasedonCHA ( const CallICFGNode cs)
inlineoverridevirtual

Implements SVF::CommonCHGraph.

Definition at line 250 of file DCHG.h.

251 {
252 return csHasVtblsBasedonCHA(cs);
253 }
virtual bool csHasVtblsBasedonCHA(CallBase *cs)
Definition DCHG.h:257

◆ csHasVtblsBasedonCHA() [1/2]

virtual bool SVF::DCHGraph::csHasVtblsBasedonCHA ( CallBase cs)
inlinevirtual

Definition at line 257 of file DCHG.h.

258 {
259 assert(false && "not supported");
261 if (!hasNode(type))
262 {
263 return false;
264 }
265
266 return getNode(type)->getVTable() != nullptr;
267 }
const DIType * getCSStaticType(CallBase *cs) const
Retrieves the metadata associated with a virtual callsite.
Definition DCHG.cpp:426
bool hasNode(const DIType *type)
Checks if a node exists for type.
Definition DCHG.h:420
DCHNode * getNode(const DIType *type)
Returns the node for type (nullptr if it doesn't exist).
Definition DCHG.h:427
const GlobalObjVar * getVTable() const
Definition DCHG.h:167

◆ csHasVtblsBasedonCHA() [2/2]

virtual bool SVF::DCHGraph::csHasVtblsBasedonCHA ( const CallICFGNode cs)
inlineoverridevirtual

Implements SVF::CommonCHGraph.

Definition at line 269 of file DCHG.h.

270 {
271 assert(false && "not supported!");
272 abort();
273 }

◆ diTypeToStr()

std::string DCHGraph::diTypeToStr ( const DIType t)
static

Returns a human-readable version of the DIType.

Definition at line 969 of file DCHG.cpp.

970{
971 std::stringstream ss;
972
973 if (t == nullptr)
974 {
975 return "void";
976 }
977
978 if (const DIBasicType *bt = SVFUtil::dyn_cast<DIBasicType>(t))
979 {
980 ss << bt->getName().str();
981 }
982 else if (const DIDerivedType *dt = SVFUtil::dyn_cast<DIDerivedType>(t))
983 {
984 if (dt->getName() == "__vtbl_ptr_type")
985 {
986 ss << "(vtbl * =) __vtbl_ptr_type";
987 }
988 else if (dt->getTag() == dwarf::DW_TAG_const_type)
989 {
990 ss << "const " << diTypeToStr(dt->getBaseType());
991 }
992 else if (dt->getTag() == dwarf::DW_TAG_volatile_type)
993 {
994 ss << "volatile " << diTypeToStr(dt->getBaseType());
995 }
996 else if (dt->getTag() == dwarf::DW_TAG_restrict_type)
997 {
998 ss << "restrict " << diTypeToStr(dt->getBaseType());
999 }
1000 else if (dt->getTag() == dwarf::DW_TAG_atomic_type)
1001 {
1002 ss << "atomic " << diTypeToStr(dt->getBaseType());
1003 }
1004 else if (dt->getTag() == dwarf::DW_TAG_pointer_type)
1005 {
1006 ss << diTypeToStr(dt->getBaseType()) << " *";
1007 }
1008 else if (dt->getTag() == dwarf::DW_TAG_ptr_to_member_type)
1009 {
1010 ss << diTypeToStr(dt->getBaseType())
1011 << " " << diTypeToStr(SVFUtil::dyn_cast<DIType>(dt->getExtraData())) << "::*";
1012 }
1013 else if (dt->getTag() == dwarf::DW_TAG_reference_type)
1014 {
1015 ss << diTypeToStr(dt->getBaseType()) << " &";
1016 }
1017 else if (dt->getTag() == dwarf::DW_TAG_rvalue_reference_type)
1018 {
1019 ss << diTypeToStr(dt->getBaseType()) << " &&";
1020 }
1021 else if (dt->getTag() == dwarf::DW_TAG_typedef)
1022 {
1023 ss << dt->getName().str() << "->" << diTypeToStr(dt->getBaseType());
1024 }
1025 }
1026 else if (const DICompositeType *ct = SVFUtil::dyn_cast<DICompositeType>(t))
1027 {
1028 if (ct->getTag() == dwarf::DW_TAG_class_type
1029 || ct->getTag() == dwarf::DW_TAG_structure_type
1030 || ct->getTag() == dwarf::DW_TAG_union_type)
1031 {
1032
1033 if (ct->getTag() == dwarf::DW_TAG_class_type)
1034 {
1035 ss << "class";
1036 }
1037 else if (ct->getTag() == dwarf::DW_TAG_structure_type)
1038 {
1039 ss << "struct";
1040 }
1041 else if (ct->getTag() == dwarf::DW_TAG_union_type)
1042 {
1043 ss << "union";
1044 }
1045
1046 ss << ".";
1047
1048 if (ct->getName() != "")
1049 {
1050 ss << ct->getName().str();
1051 }
1052 else
1053 {
1054 // Iterate over the element types.
1055 ss << "{ ";
1056
1057 DINodeArray fields = ct->getElements();
1058 for (unsigned i = 0; i < fields.size(); ++i)
1059 {
1060 // fields[i] gives a type which is DW_TAG_member, we want the member's type (getBaseType).
1061 // It can also give a Subprogram type if the class just had non-virtual functions.
1062 if (const DISubprogram *sp = SVFUtil::dyn_cast<DISubprogram>(fields[i]))
1063 {
1064 ss << sp->getName().str();
1065 }
1066 else if (const DIDerivedType *mt = SVFUtil::dyn_cast<DIDerivedType>(fields[i]))
1067 {
1068 assert(mt->getTag() == dwarf::DW_TAG_member && "DCHG: expected member");
1069 ss << diTypeToStr(mt->getBaseType());
1070 }
1071
1072 if (i != fields.size() - 1)
1073 {
1074 ss << ", ";
1075 }
1076 }
1077
1078 ss << " }";
1079 }
1080 }
1081 else if (ct->getTag() == dwarf::DW_TAG_array_type)
1082 {
1083 ss << diTypeToStr(ct->getBaseType());
1084 DINodeArray sizes = ct->getElements();
1085 for (unsigned i = 0; i < sizes.size(); ++i)
1086 {
1087 DISubrange *sr = SVFUtil::dyn_cast<DISubrange>(sizes[0]);
1088 assert(sr != nullptr && "DCHG: non-subrange as array element?");
1089 int64_t count = -1;
1090 if (const ConstantInt* ci = sr->getCount().dyn_cast<ConstantInt* >())
1091 {
1093 }
1094
1095 ss << "[" << count << "]";
1096 }
1097 }
1098 else if (ct->getTag() == dwarf::DW_TAG_enumeration_type)
1099 {
1100 ss << "enum " << diTypeToStr(ct->getBaseType());
1101 }
1102 else if (ct->getTag() == dwarf::DW_TAG_union_type)
1103 {
1104
1105 }
1106 }
1107 else if (const DISubroutineType *st = SVFUtil::dyn_cast<DISubroutineType>(t))
1108 {
1109 DITypeRefArray types = st->getTypeArray();
1110 // Must have one element at least (the first type).
1111 ss << diTypeToStr(types[0]) << " fn(";
1112 if (types.size() == 1)
1113 {
1114 ss << "void)";
1115 }
1116 else
1117 {
1118 for (unsigned i = 1; i < types.size(); ++i)
1119 {
1120 ss << diTypeToStr(types[i]);
1121 if (i + 1 != types.size())
1122 {
1123 // There's another type.
1124 ss << ", ";
1125 }
1126 }
1127
1128 ss << ")";
1129 }
1130
1131 ss << st->getName().str();
1132 }
1133
1134 return ss.str();
1135}
int count
Definition cJSON.h:216
static std::string diTypeToStr(const DIType *)
Returns a human-readable version of the DIType.
Definition DCHG.cpp:969
std::pair< s64_t, u64_t > getIntegerValue(const ConstantInt *intValue)
Definition LLVMUtil.h:82
llvm::DINodeArray DINodeArray
Definition BasicTypes.h:244
llvm::DISubprogram DISubprogram
Definition BasicTypes.h:113
llvm::DISubrange DISubrange
Definition BasicTypes.h:242
llvm::DITypeRefArray DITypeRefArray
Definition BasicTypes.h:245
llvm::ConstantInt ConstantInt
Definition BasicTypes.h:125

◆ dump()

void SVF::DCHGraph::dump ( const std::string &  filename)
inline

Definition at line 243 of file DCHG.h.

244 {
246 }
static void WriteGraphToFile(SVF::OutStream &O, const std::string &GraphName, const GraphType &GT, bool simple=false)
std::ostream & outs()
Overwrite llvm::outs()
Definition SVFUtil.h:52

◆ flatten()

void DCHGraph::flatten ( const DICompositeType type)
private

Populates fieldTypes for type and all its elements.

Definition at line 270 of file DCHG.cpp.

271{
272 type = SVFUtil::dyn_cast<DICompositeType>(getCanonicalType(type));
273 assert(type && "DCHG::flatten: canon type of struct/class is not struct/class");
274 if (fieldTypes.find(type) != fieldTypes.end())
275 {
276 // Already done (necessary because of the recursion).
277 return;
278 }
279
280 // Create empty vector.
282
283 assert(type != nullptr
284 && (type->getTag() == dwarf::DW_TAG_class_type
285 || type->getTag() == dwarf::DW_TAG_structure_type)
286 && "DCHG::flatten: expected a class/struct");
287
288 // Sort the fields from getElements. Especially a problem for classes; it's all jumbled up.
289 std::vector<const DIDerivedType *> fields;
290 DINodeArray fieldsDINA = type->getElements();
291 for (unsigned i = 0; i < fieldsDINA.size(); ++i)
292 {
293 if (const DIDerivedType *dt = SVFUtil::dyn_cast<DIDerivedType>(fieldsDINA[i]))
294 {
295 // Don't care about subprograms, only member/inheritance.
296 fields.push_back(dt);
297 }
298 }
299
300 // TODO: virtual inheritance is not handled at all!
301 std::sort(fields.begin(), fields.end(),
302 [](const DIDerivedType *&a, const DIDerivedType *&b) -> bool
303 { return a->getOffsetInBits() < b->getOffsetInBits(); });
304
305 for (const DIDerivedType *mt : fields)
306 {
307 assert((mt->getTag() == dwarf::DW_TAG_member || mt->getTag() == dwarf::DW_TAG_inheritance)
308 && "DCHG: expected member/inheritance");
309 // Either we have a class, struct, array, or something not in need of flattening.
310 const DIType *fieldType = mt->getBaseType();
311 if (fieldType->getTag() == dwarf::DW_TAG_structure_type
312 || fieldType->getTag() == dwarf::DW_TAG_class_type)
313 {
314 flatten(SVFUtil::dyn_cast<DICompositeType>(fieldType));
315 for (const DIType *ft : fieldTypes[fieldType])
316 {
317 // ft is already a canonical type because the "root" additions insert
318 // canonical types.
319 fieldTypes[type].push_back(ft);
320 }
321 }
322 else if (fieldType->getTag() == dwarf::DW_TAG_array_type)
323 {
324 const DICompositeType *arrayType = SVFUtil::dyn_cast<DICompositeType>(fieldType);
325 const DIType *baseType = arrayType->getBaseType();
326 if (const DICompositeType *cbt = SVFUtil::dyn_cast<DICompositeType>(baseType))
327 {
328 flatten(cbt);
329 for (const DIType *ft : fieldTypes[cbt])
330 {
331 // ft is already a canonical type like above.
332 fieldTypes[type].push_back(ft);
333 }
334 }
335 else
336 {
338 }
339 }
340 else
341 {
343 }
344 }
345}
cJSON * a
Definition cJSON.cpp:2560
const cJSON *const b
Definition cJSON.h:255
void flatten(const DICompositeType *type)
Populates fieldTypes for type and all its elements.
Definition DCHG.cpp:270
Map< const DIType *, std::vector< const DIType * > > fieldTypes
Maps types to their flattened fields' types.
Definition DCHG.h:378

◆ gatherAggs()

void DCHGraph::gatherAggs ( const DICompositeType type)
private

Populates containingAggs for type and all its elements.

Definition at line 355 of file DCHG.cpp.

356{
358 {
359 return;
360 }
361
362 // Initialise an empty set. We want all aggregates to have a value in
363 // this map, even if empty (e.g. struct has no aggs, only scalars).
365
366 if (type->getTag() == dwarf::DW_TAG_array_type)
367 {
368 const DIType *bt = type->getBaseType();
370
371 if (isAgg(bt))
372 {
373 const DICompositeType *cbt = SVFUtil::dyn_cast<DICompositeType>(bt);
376 // These must be canonical already because of aggs.insert above/below.
380 }
381 }
382 else
383 {
384 DINodeArray fields = type->getElements();
385 for (unsigned i = 0; i < fields.size(); ++i)
386 {
387 // Unwrap the member (could be a subprogram, not type, so guard needed).
388 if (const DIDerivedType *mt = SVFUtil::dyn_cast<DIDerivedType>(fields[i]))
389 {
390 const DIType *ft = mt->getBaseType();
392
393 if (isAgg(ft))
394 {
395 const DICompositeType *cft = SVFUtil::dyn_cast<DICompositeType>(ft);
398 // These must be canonical already because of aggs.insert above.
402 }
403 }
404 }
405 }
406}
static const DIType * stripQualifiers(const DIType *)
Returns the DIType beneath the qualifiers. Does not strip away "DW_TAG_members".
Definition DCHG.cpp:765
void gatherAggs(const DICompositeType *type)
Populates containingAggs for type and all its elements.
Definition DCHG.cpp:355
static bool isAgg(const DIType *t)
Definition DCHG.cpp:347
Map< const DIType *, Set< const DIType * > > containingAggs
Maps aggregate types to all the aggregate types it transitively contains.
Definition DCHG.h:380

◆ getAggs()

const Set< const DIType * > & SVF::DCHGraph::getAggs ( const DIType base)
inline

Returns all the aggregates contained (transitively) in base.

Definition at line 349 of file DCHG.h.

350 {
351 base = getCanonicalType(base);
352 assert(containingAggs.find(base) != containingAggs.end() && "DCHG: aggregates not gathered for base!");
353 return containingAggs[base];
354 }

◆ getCanonicalType()

const DIType * DCHGraph::getCanonicalType ( const DIType t)

Returns the type representing all qualifier-variations of t. This should only matter in the case of DerivedTypes where qualifiers and have qualified base types cause a mess.

Definition at line 724 of file DCHG.cpp.

725{
726 // We want stripped types to be canonical.
727 const DIType *unstrippedT = t;
728 t = stripQualifiers(t);
729
730 // Is there a mapping for the unstripped type? Yes - return it.
732 {
734 }
735
736 // There is no mapping for unstripped type (^), is there one for the stripped
737 // type? Yes - map the unstripped type to the same thing.
738 if (unstrippedT != t)
739 {
740 if (canonicalTypeMap.find(t) != canonicalTypeMap.end())
741 {
744 }
745 }
746
747 // Canonical type for t is not cached, find one for it.
748 for (const DIType *canonType : canonicalTypes)
749 {
750 if (teq(t, canonType))
751 {
752 // Found a canonical type.
754 return canonicalTypeMap[t];
755 }
756 }
757
758 // No canonical type found, so t will be a canonical type.
759 canonicalTypes.insert(t);
760 canonicalTypeMap.insert({t, t});
761
762 return canonicalTypeMap[t];
763}
Map< const DIType *, const DIType * > canonicalTypeMap
Maps types to their canonical type (many-to-one).
Definition DCHG.h:374
static bool teq(const DIType *t1, const DIType *t2)
Definition DCHG.cpp:830
Set< const DIType * > canonicalTypes
Set of all possible canonical types (i.e. values of canonicalTypeMap).
Definition DCHG.h:376

◆ getCSStaticType() [1/2]

const DIType * DCHGraph::getCSStaticType ( CallBase cs) const
private

Retrieves the metadata associated with a virtual callsite.

Definition at line 426 of file DCHG.cpp.

427{
428 MDNode *md = cs->getMetadata(cppUtil::ctir::derefMDName);
429 assert(md != nullptr && "Missing type metadata at virtual callsite");
430 DIType *diType = SVFUtil::dyn_cast<DIType>(md);
431 assert(diType != nullptr && "Incorrect metadata type at virtual callsite");
432 return diType;
433}
const std::string derefMDName
Definition CppUtil.h:168
llvm::MDNode MDNode
Definition BasicTypes.h:112

◆ getCSStaticType() [2/2]

const DIType * SVF::DCHGraph::getCSStaticType ( const CallICFGNode cs) const
inlineprivate

Definition at line 413 of file DCHG.h.

414 {
415 assert(false && "not supported!");
416 abort();
417 }

◆ getCSVFsBasedonCHA()

const VFunSet & DCHGraph::getCSVFsBasedonCHA ( const CallICFGNode cs)
overridevirtual

Implements SVF::CommonCHGraph.

Definition at line 549 of file DCHG.cpp.

550{
551 if (csCHAMap.find(cs) != csCHAMap.end())
552 {
553 return csCHAMap[cs];
554 }
555
559
560 // Cache.
561 csCHAMap.insert({cs, vfns});
562 // Return cached object, not the stack object.
563 return csCHAMap[cs];
564}
Map< const CallICFGNode *, VFunSet > csCHAMap
Maps callsites to a set of potential virtual functions based on CHA.
Definition DCHG.h:372
virtual void getVFnsFromVtbls(const CallICFGNode *cs, const VTableSet &vtbls, VFunSet &virtualFunctions) override
Definition DCHG.cpp:594
virtual const VTableSet & getCSVtblsBasedonCHA(const CallICFGNode *cs) override
Definition DCHG.cpp:566
Set< const GlobalObjVar * > VTableSet
Definition CHG.h:46
Set< const FunObjVar * > VFunSet
Definition CHG.h:47

◆ getCSVtblsBasedonCHA()

const VTableSet & DCHGraph::getCSVtblsBasedonCHA ( const CallICFGNode cs)
overridevirtual

Implements SVF::CommonCHGraph.

Definition at line 566 of file DCHG.cpp.

567{
569 // Check if we've already computed.
570 if (vtblCHAMap.find(type) != vtblCHAMap.end())
571 {
572 return vtblCHAMap[type];
573 }
574
576 const NodeBS &children = cha(type, false);
577 for (NodeID childId : children)
578 {
580 const GlobalObjVar *vtbl = child->getVTable();
581 // TODO: what if it is null?
582 if (vtbl != nullptr)
583 {
584 vtblSet.insert(vtbl);
585 }
586 }
587
588 // Cache.
589 vtblCHAMap.insert({type, vtblSet});
590 // Return cached version - not the stack object.
591 return vtblCHAMap[type];
592}
cJSON * child
Definition cJSON.cpp:2723
Map< const DIType *, VTableSet > vtblCHAMap
Maps types to a set with their vtable and all their children's.
Definition DCHG.h:370

◆ getFieldType()

const DIType * SVF::DCHGraph::getFieldType ( const DIType base,
unsigned  idx 
)
inline

Returns the type of field number idx (flattened) in base.

Definition at line 296 of file DCHG.h.

297 {
298 base = getCanonicalType(base);
299 if (base == nullptr)
300 {
301 // Conservative; the base object is untyped, sadly.
302 return nullptr;
303 }
304
305 // For TBHC this is conservative because the union type is lower in the DCHG
306 // than its fields. TODO: make more precise.
307 if (base->getTag() == dwarf::DW_TAG_union_type)
308 {
309 return base;
310 }
311
312 if (base->getTag() == dwarf::DW_TAG_array_type)
313 {
314 const DICompositeType* cbase =
315 SVFUtil::dyn_cast<DICompositeType>(base);
316 assert(cbase && "DCHG: bad DIComposite case");
317 return cbase->getBaseType();
318 }
319
320 if (!(base->getTag() == dwarf::DW_TAG_class_type ||
321 base->getTag() == dwarf::DW_TAG_structure_type))
322 {
323 return nullptr;
324 }
325
326 assert(fieldTypes.find(base) != fieldTypes.end() && "DCHG: base not flattened!");
327 std::vector<const DIType *> &fields = fieldTypes[base];
328 assert(fields.size() > idx && "DCHG: idx into struct larger than # fields!");
329 return getCanonicalType(fields[idx]);
330 }

◆ getFieldTypes()

const std::vector< const DIType * > & SVF::DCHGraph::getFieldTypes ( const DIType base)
inline

Returns a vector of the types of all fields in base.

Definition at line 333 of file DCHG.h.

334 {
335 base = getCanonicalType(base);
336 assert(fieldTypes.find(base) != fieldTypes.end() && "DCHG: base not flattened!");
337 return fieldTypes[base];
338 }

◆ getNode()

DCHNode * SVF::DCHGraph::getNode ( const DIType type)
inlineprivate

Returns the node for type (nullptr if it doesn't exist).

Definition at line 427 of file DCHG.h.

428 {
430 if (hasNode(type))
431 {
432 return diTypeToNodeMap.at(type);
433 }
434
435 return nullptr;
436 }
Map< const DIType *, DCHNode * > diTypeToNodeMap
Maps DITypes to their nodes.
Definition DCHG.h:362

◆ getNumFields()

unsigned SVF::DCHGraph::getNumFields ( const DIType base)
inline

Definition at line 341 of file DCHG.h.

342 {
343 base = getCanonicalType(base);
344 assert(fieldTypes.find(base) != fieldTypes.end() && "DCHG: base not flattened!");
345 return fieldTypes[base].size();
346 }

◆ getOrCreateNode()

DCHNode * DCHGraph::getOrCreateNode ( const DIType type)
private

Creates a node from type, or returns it if it exists.

Definition at line 408 of file DCHG.cpp.

409{
411
412 // Check, does the node for type exist?
413 if (diTypeToNodeMap[type] != nullptr)
414 {
415 return diTypeToNodeMap[type];
416 }
417
418 DCHNode *node = new DCHNode(type, numTypes++);
419 addGNode(node->getId(), node);
420 diTypeToNodeMap[type] = node;
421 // TODO: handle templates.
422
423 return node;
424}
void addGNode(NodeID id, NodeType *node)
Add a Node.

◆ getVFnsFromVtbls()

void DCHGraph::getVFnsFromVtbls ( const CallICFGNode cs,
const VTableSet vtbls,
VFunSet virtualFunctions 
)
overridevirtual

Implements SVF::CommonCHGraph.

Definition at line 594 of file DCHG.cpp.

595{
596 size_t idx = callsite->getFunIdxInVtable();
597 std::string funName = callsite->getFunNameOfVirtualCall();
598 for (const GlobalObjVar *vtbl : vtbls)
599 {
600 assert(vtblToTypeMap.find(vtbl) != vtblToTypeMap.end() && "floating vtbl");
601 const DIType *type = vtblToTypeMap[vtbl];
602 assert(hasNode(type) && "trying to get vtbl for type not in graph");
603 const DCHNode *node = getNode(type);
604 std::vector<std::vector<const Function* >> allVfns = node->getVfnVectors();
605 for (std::vector<const Function* > vfnV : allVfns)
606 {
607 // We only care about any virtual function corresponding to idx.
608 if (idx >= vfnV.size())
609 {
610 continue;
611 }
612
613 const Function* callee = vfnV[idx];
614 // Practically a copy of that in lib/MemoryModel/CHA.cpp
615 if (callsite->arg_size() == callee->arg_size() || (callsite->isVarArg() && callee->isVarArg()))
616 {
618 std::string calleeName = dname.funcName;
619
620 /*
621 * The compiler will add some special suffix (e.g.,
622 * "[abi:cxx11]") to the end of some virtual function:
623 * In dealII
624 * function: FE_Q<3>::get_name
625 * will be mangled as: _ZNK4FE_QILi3EE8get_nameB5cxx11Ev
626 * after demangling: FE_Q<3>::get_name[abi:cxx11]
627 * The special suffix ("[abi:cxx11]") needs to be removed
628 */
629 const std::string suffix("[abi:cxx11]");
630 size_t suffixPos = calleeName.rfind(suffix);
631 if (suffixPos != std::string::npos)
632 {
633 calleeName.erase(suffixPos, suffix.size());
634 }
635
636 /*
637 * if we can't get the function name of a virtual callsite, all virtual
638 * functions corresponding to idx will be valid
639 */
640 if (funName.size() == 0)
641 {
642 virtualFunctions.insert(LLVMUtil::getFunObjVar(callee->getName().str()));
643 }
644 else if (funName[0] == '~')
645 {
646 /*
647 * if the virtual callsite is calling a destructor, then all
648 * destructors in the ch will be valid
649 * class A { virtual ~A(){} };
650 * class B: public A { virtual ~B(){} };
651 * int main() {
652 * A *a = new B;
653 * delete a; /// the function name of this virtual callsite is ~A()
654 * }
655 */
656 if (calleeName[0] == '~')
657 {
658 virtualFunctions.insert(LLVMUtil::getFunObjVar(callee->getName().str()));
659 }
660 }
661 else
662 {
663 /*
664 * For other virtual function calls, the function name of the callsite
665 * and the function name of the target callee should match exactly
666 */
667 if (funName.compare(calleeName) == 0)
668 {
669 virtualFunctions.insert(LLVMUtil::getFunObjVar(callee->getName().str()));
670 }
671 }
672 }
673 }
674 }
675}
const std::vector< std::vector< const Function * > > & getVfnVectors(void) const
Returns the vector of virtual function vectors.
Definition DCHG.h:173
const FunObjVar * getFunObjVar(const std::string &name)
Definition LLVMUtil.cpp:435
struct DemangledName demangle(const std::string &name)
Definition CppUtil.cpp:195

◆ handleDIBasicType()

void DCHGraph::handleDIBasicType ( const DIBasicType basicType)
private

Construction helper to process DIBasicTypes.

Definition at line 22 of file DCHG.cpp.

23{
25}

◆ handleDICompositeType()

void DCHGraph::handleDICompositeType ( const DICompositeType compositeType)
private

Construction helper to process DICompositeTypes.

Definition at line 27 of file DCHG.cpp.

28{
29 switch (compositeType->getTag())
30 {
31 case dwarf::DW_TAG_array_type:
34 break;
35 case dwarf::DW_TAG_class_type:
36 case dwarf::DW_TAG_structure_type:
38 // If we're extending, we need to add the first-field relation.
39 if (extended)
40 {
41 DINodeArray fields = compositeType->getElements();
42 if (!fields.empty())
43 {
44 // We want the first non-static, non-function member; it may not exist.
45 DIDerivedType *firstMember = nullptr;
46 for (DINode *n : fields)
47 {
48 if (DIDerivedType *fm = SVFUtil::dyn_cast<DIDerivedType>(n))
49 {
50 if (fm->getTag() == dwarf::DW_TAG_member && !fm->isStaticMember())
51 {
53 break;
54 }
55 }
56 }
57
58 if (firstMember != nullptr)
59 {
60 // firstMember is a DW_TAG_member, we want the base type beneath it.
62 }
63 }
64 }
65
68
69 break;
70 case dwarf::DW_TAG_union_type:
72 // All fields are first fields.
73 if (extended)
74 {
75 DINodeArray fields = compositeType->getElements();
76 for (DINode *field : fields)
77 {
78 // fields[0] gives a type which is DW_TAG_member, we want the member's type (getBaseType).
79 DIDerivedType *firstMember = SVFUtil::dyn_cast<DIDerivedType>(field);
80 assert(firstMember != nullptr && "DCHG: expected member type");
82 }
83 }
84
85 // flatten(compositeType);
87
88 break;
89 case dwarf::DW_TAG_enumeration_type:
91 break;
92 default:
93 assert(false && "DCHGraph::buildCHG: unexpected CompositeType tag.");
94 }
95}
cJSON * n
Definition cJSON.cpp:2558
llvm::DINode DINode
Definition BasicTypes.h:243

◆ handleDIDerivedType()

void DCHGraph::handleDIDerivedType ( const DIDerivedType derivedType)
private

Construction helper to process DIDerivedTypes.

Definition at line 97 of file DCHG.cpp.

98{
99 switch (derivedType->getTag())
100 {
101 case dwarf::DW_TAG_inheritance:
102 {
103 assert(SVFUtil::isa<DIType>(derivedType->getScope()) && "inheriting from non-type?");
104 DCHEdge *edge = addEdge(SVFUtil::dyn_cast<DIType>(derivedType->getScope()),
105 derivedType->getBaseType(), DCHEdge::INHERITANCE);
106 // If the offset does not exist (for primary base), getConstantFieldIdx should return 0.
107 edge->setOffset(derivedType->getOffsetInBits());
108 break;
109 }
110 case dwarf::DW_TAG_member:
111 case dwarf::DW_TAG_friend:
112 // Don't care.
113 break;
114 case dwarf::DW_TAG_typedef:
116 break;
117 case dwarf::DW_TAG_pointer_type:
118 case dwarf::DW_TAG_ptr_to_member_type:
119 case dwarf::DW_TAG_reference_type:
120 case dwarf::DW_TAG_rvalue_reference_type:
122 break;
123 case dwarf::DW_TAG_const_type:
124 case dwarf::DW_TAG_atomic_type:
125 case dwarf::DW_TAG_volatile_type:
126 case dwarf::DW_TAG_restrict_type:
127 break;
128 default:
129 assert(false && "DCHGraph::buildCHG: unexpected DerivedType tag.");
130 }
131}
void handleTypedef(const DIType *typedefType)
Attaches the typedef(s) to the base node.
Definition DCHG.cpp:138

◆ handleDISubroutineType()

void DCHGraph::handleDISubroutineType ( const DISubroutineType subroutineType)
private

Construction helper to process DISubroutineTypes.

Definition at line 133 of file DCHG.cpp.

◆ handleTypedef()

void DCHGraph::handleTypedef ( const DIType typedefType)
private

Attaches the typedef(s) to the base node.

Definition at line 138 of file DCHG.cpp.

139{
140 assert(typedefType && typedefType->getTag() == dwarf::DW_TAG_typedef);
141
142 // Need to gather them in a set first because we don't know the base type till
143 // we get to the bottom of the (potentially many) typedefs.
144 std::vector<const DIDerivedType *> typedefs;
145 // Check for nullptr because you can typedef void.
146 while (typedefType != nullptr && typedefType->getTag() == dwarf::DW_TAG_typedef)
147 {
148 const DIDerivedType *typedefDerivedType = SVFUtil::dyn_cast<DIDerivedType>(typedefType);
149 // The typedef itself.
150 typedefs.push_back(typedefDerivedType);
151
152 // Next in the typedef line.
153 typedefType = typedefDerivedType->getBaseType();
154 }
155
156 const DIType *baseType = typedefType;
158
159 for (const DIDerivedType *tdef : typedefs)
160 {
161 // Base type needs to hold its typedefs.
162 baseTypeNode->addTypedef(tdef);
163 }
164}

◆ hasEdge()

DCHEdge * DCHGraph::hasEdge ( const DIType t1,
const DIType t2,
DCHEdge::GEdgeKind  et 
)
private

Returns the edge between t1 and t2 if it exists, returns nullptr otherwise.

Definition at line 452 of file DCHG.cpp.

453{
454 DCHNode *src = getOrCreateNode(t1);
455 DCHNode *dst = getOrCreateNode(t2);
456
457 for (DCHEdge *edge : src->getOutEdges())
458 {
459 DCHNode *node = edge->getDstNode();
460 DCHEdge::GEdgeKind edgeType = edge->getEdgeKind();
461 if (node == dst && edgeType == et)
462 {
463 assert(SVFUtil::isa<DCHEdge>(edge) && "Non-DCHEdge in DCHNode edge set.");
464 return edge;
465 }
466 }
467
468 return nullptr;
469}

◆ hasNode()

bool SVF::DCHGraph::hasNode ( const DIType type)
inlineprivate

Checks if a node exists for type.

Definition at line 420 of file DCHG.h.

421 {
423 return diTypeToNodeMap.find(type) != diTypeToNodeMap.end();
424 }

◆ isAgg()

bool DCHGraph::isAgg ( const DIType t)
static

Definition at line 347 of file DCHG.cpp.

348{
349 if (t == nullptr) return false;
350 return t->getTag() == dwarf::DW_TAG_array_type
351 || t->getTag() == dwarf::DW_TAG_structure_type
352 || t->getTag() == dwarf::DW_TAG_class_type;
353}

◆ isBase()

bool DCHGraph::isBase ( const DIType a,
const DIType b,
bool  firstField 
)
virtual

Returns true if a is a transitive base of b. firstField determines whether to consider first-field edges.

Definition at line 677 of file DCHG.cpp.

678{
681 assert(hasNode(a) && hasNode(b) && "DCHG: isBase query for non-existent node!");
682 const DCHNode *bNode = getNode(b);
683
684 const NodeBS &aChildren = cha(a, firstField);
685 return aChildren.test(bNode->getId());
686}

◆ isFieldOf()

bool DCHGraph::isFieldOf ( const DIType f,
const DIType b 
)
virtual

Returns true if f is a field of b (fields from getFieldTypes).

Definition at line 688 of file DCHG.cpp.

689{
690 assert(f && b && "DCHG::isFieldOf: given nullptr!");
691
694 if (f == b) return true;
695
696 if (b->getTag() == dwarf::DW_TAG_array_type || b->getTag() == dwarf::DW_TAG_pointer_type)
697 {
698 const DIType *baseType = nullptr;
699 if (const DICompositeType *arrayType = SVFUtil::dyn_cast<DICompositeType>(b))
700 {
701 baseType = arrayType->getBaseType();
702 }
703 else if (const DIDerivedType *ptrType = SVFUtil::dyn_cast<DIDerivedType>(b))
704 {
705 baseType = ptrType->getBaseType();
706 }
707 assert(baseType && "DCHG::isFieldOf: baseType is neither DIComposite nor DIDerived!");
708
710 return f == baseType || (baseType != nullptr && isFieldOf(f, baseType));
711 }
712 else if (b->getTag() == dwarf::DW_TAG_class_type
713 || b->getTag() == dwarf::DW_TAG_structure_type)
714 {
715 const std::vector<const DIType *> &fields = getFieldTypes(b);
716 return std::find(fields.begin(), fields.end(), f) != fields.end();
717 }
718 else
719 {
720 return false;
721 }
722}
const std::vector< const DIType * > & getFieldTypes(const DIType *base)
Returns a vector of the types of all fields in base.
Definition DCHG.h:333
virtual bool isFieldOf(const DIType *f, const DIType *b)
Returns true if f is a field of b (fields from getFieldTypes).
Definition DCHG.cpp:688

◆ isFirstField()

bool DCHGraph::isFirstField ( const DIType f,
const DIType b 
)

Definition at line 942 of file DCHG.cpp.

943{
944 // TODO: some improvements.
945 // - cha should be changed to accept which edge types to use,
946 // then we can call cha(..., DCHEdge::FIRST_FIELD).
947 // - If not ^, this could benefit from caching.
950
951 if (f == b) return true;
952
953 const DCHNode *node = getNode(f);
954 assert(node && "DCHG::isFirstField: node not found");
955 // Consider oneself a child, otherwise the recursion will just come up with nothing.
956 for (const DCHEdge *edge : node->getInEdges())
957 {
958 // Only care about first-field edges.
959 if (edge->getEdgeKind() == DCHEdge::FIRST_FIELD)
960 {
961 if (edge->getSrcNode()->getDIType() == b) return true;
962 if (isFirstField(edge->getSrcNode()->getDIType(), b)) return true;
963 }
964 }
965
966 return false;
967}
bool isFirstField(const DIType *f, const DIType *b)
Definition DCHG.cpp:942

◆ print()

void DCHGraph::print ( void  )

Definition at line 1142 of file DCHG.cpp.

1143{
1144 static const std::string line = "-------------------------------------\n";
1145 static const std::string thickLine = "=====================================\n";
1146 static const size_t singleIndent = 2;
1147
1148 size_t currIndent = 0;
1150 unsigned numStructs = 0;
1151 unsigned largestStruct = 0;
1152 NodeSet nodes;
1153 for (DCHGraph::const_iterator it = begin(); it != end(); ++it)
1154 {
1155 nodes.insert(it->first);
1156 }
1157
1158 for (NodeID id : nodes)
1159 {
1160 if (*nodes.begin() != id)
1161 {
1162 SVFUtil::outs() << line;
1163 }
1164
1165 const DCHNode *node = getGNode(id);
1166
1167 SVFUtil::outs() << indent(currIndent) << id << ": " << diTypeToStr(node->getDIType()) << " [" << node->getDIType() << "]" << "\n";
1168 if (node->getDIType() != nullptr
1169 && (node->getDIType()->getTag() == dwarf::DW_TAG_class_type
1170 ||
1171 node->getDIType()->getTag() == dwarf::DW_TAG_structure_type))
1172 {
1173 ++numStructs;
1174 unsigned numFields = getFieldTypes(node->getDIType()).size();
1176 }
1177
1179 SVFUtil::outs() << indent(currIndent) << "Virtual functions\n";
1181 const std::vector<std::vector<const Function* >> &vfnVectors = node->getVfnVectors();
1182 for (unsigned i = 0; i < vfnVectors.size(); ++i)
1183 {
1184 SVFUtil::outs() << indent(currIndent) << "[ vtable #" << i << " ]\n";
1186 for (unsigned j = 0; j < vfnVectors[i].size(); ++j)
1187 {
1188 struct cppUtil::DemangledName dname = cppUtil::demangle(vfnVectors[i][j]->getName().str());
1189 SVFUtil::outs() << indent(currIndent) << "[" << j << "] "
1190 << dname.className << "::" << dname.funcName << "\n";
1191 }
1192
1194 }
1195
1196 // Nothing was printed.
1197 if (vfnVectors.size() == 0)
1198 {
1199 SVFUtil::outs() << indent(currIndent) << "(none)\n";
1200 }
1201
1203
1204 SVFUtil::outs() << indent(currIndent) << "Bases\n";
1206 for (const DCHEdge *edge : node->getOutEdges())
1207 {
1208 std::string arrow;
1209 if (edge->getEdgeKind() == DCHEdge::INHERITANCE)
1210 {
1211 arrow = "--inheritance-->";
1212 }
1213 else if (edge->getEdgeKind() == DCHEdge::FIRST_FIELD)
1214 {
1215 arrow = "--first-field-->";
1216 }
1217 else if (edge->getEdgeKind() == DCHEdge::INSTANCE)
1218 {
1219 arrow = "---instance---->";
1220 }
1221 else if (edge->getEdgeKind() == DCHEdge::STD_DEF)
1222 {
1223 arrow = "---standard---->";
1224 }
1225 else
1226 {
1227 arrow = "----unknown---->";
1228 }
1229
1230 SVFUtil::outs() << indent(currIndent) << "[ " << diTypeToStr(node->getDIType()) << " ] "
1231 << arrow << " [ " << diTypeToStr(edge->getDstNode()->getDIType()) << " ]\n";
1232 }
1233
1234 if (node->getOutEdges().size() == 0)
1235 {
1236 SVFUtil::outs() << indent(currIndent) << "(none)\n";
1237 }
1238
1240
1241 SVFUtil::outs() << indent(currIndent) << "Typedefs\n";
1242
1244
1245 const Set<const DIDerivedType *> &typedefs = node->getTypedefs();
1246 for (const DIDerivedType *tdef : typedefs)
1247 {
1248 std::string typedefName = "void";
1249 if (tdef != nullptr)
1250 {
1251 typedefName = tdef->getName().str();
1252 }
1253
1254 SVFUtil::outs() << indent(currIndent) << typedefName << "\n";
1255 }
1256
1257 if (typedefs.size() == 0)
1258 {
1259 SVFUtil::outs() << indent(currIndent) << "(none)\n";
1260 }
1261
1263
1265 }
1266
1268
1269 SVFUtil::outs() << "Other stats\n";
1270 SVFUtil::outs() << line;
1271 SVFUtil::outs() << "# Canonical types : " << canonicalTypes.size() << "\n";
1272 SVFUtil::outs() << "# structs : " << numStructs << "\n";
1273 SVFUtil::outs() << "Largest struct : " << largestStruct << " fields\n";
1275
1276 SVFUtil::outs().flush();
1277}
static std::string indent(size_t n)
Definition DCHG.cpp:1137
@ INSTANCE
Definition DCHG.h:34
const DIType * getDIType(void) const
Definition DCHG.h:94
const Set< const DIDerivedType * > & getTypedefs(void) const
Definition DCHG.h:157
IDToNodeMapTy::const_iterator const_iterator
const GEdgeSetTy & getOutEdges() const
Set< NodeID > NodeSet
iter_range< typename GenericGraphTraits< GraphType >::nodes_iterator > nodes(const GraphType &G)

◆ stripArray()

const DIType * DCHGraph::stripArray ( const DIType t)
static

Returns the DIType beneath all qualifiers and arrays.

Definition at line 818 of file DCHG.cpp.

819{
820 t = stripQualifiers(t);
821 if (t->getTag() == dwarf::DW_TAG_array_type)
822 {
823 const DICompositeType *at = SVFUtil::dyn_cast<DICompositeType>(t);
824 return stripArray(at->getBaseType());
825 }
826
827 return t;
828}
static const DIType * stripArray(const DIType *)
Returns the DIType beneath all qualifiers and arrays.
Definition DCHG.cpp:818

◆ stripQualifiers()

const DIType * DCHGraph::stripQualifiers ( const DIType t)
static

Returns the DIType beneath the qualifiers. Does not strip away "DW_TAG_members".

Definition at line 765 of file DCHG.cpp.

766{
767 while (true)
768 {
769 // nullptr means void.
770 if (t == nullptr
771 || SVFUtil::isa<DIBasicType>(t)
772 || SVFUtil::isa<DISubroutineType>(t))
773 {
774 break;
775 }
776
777 unsigned tag = t->getTag();
778 // Verbose for clarity.
779 if ( tag == dwarf::DW_TAG_const_type
780 || tag == dwarf::DW_TAG_atomic_type
781 || tag == dwarf::DW_TAG_volatile_type
782 || tag == dwarf::DW_TAG_restrict_type
783 || tag == dwarf::DW_TAG_typedef)
784 {
785 // Qualifier - get underlying type.
786 const DIDerivedType *dt = SVFUtil::dyn_cast<DIDerivedType>(t);
787 assert(t && "DCHG: expected DerivedType");
788 t = dt->getBaseType();
789 }
790 else if ( tag == dwarf::DW_TAG_array_type
791 || tag == dwarf::DW_TAG_class_type
792 || tag == dwarf::DW_TAG_structure_type
793 || tag == dwarf::DW_TAG_union_type
794 || tag == dwarf::DW_TAG_enumeration_type
795 || tag == dwarf::DW_TAG_member
796 || tag == dwarf::DW_TAG_pointer_type
797 || tag == dwarf::DW_TAG_ptr_to_member_type
798 || tag == dwarf::DW_TAG_reference_type
799 || tag == dwarf::DW_TAG_rvalue_reference_type)
800 {
801 // Hit a non-qualifier.
802 break;
803 }
804 else if ( tag == dwarf::DW_TAG_inheritance
805 || tag == dwarf::DW_TAG_friend)
806 {
807 assert(false && "DCHG: unexpected tag when stripping qualifiers");
808 }
809 else
810 {
811 assert(false && "DCHG: unhandled tag when stripping qualifiers");
812 }
813 }
814
815 return t;
816}

◆ teq()

bool DCHGraph::teq ( const DIType t1,
const DIType t2 
)
static

Returns true if t1 and t2 are equivalent, ignoring qualifiers. For equality... Tags always need to be equal. DIBasicType: shallow pointer equality. DIDerivedType: base types (teq). DICompositeType: shallow pointer equality. DISubroutineType: shallow pointer equality.

Definition at line 830 of file DCHG.cpp.

831{
834
835 if (t1 == t2)
836 {
837 // Trivial case. Handles SubRoutineTypes too.
838 return true;
839 }
840
841 if (t1 == nullptr || t2 == nullptr)
842 {
843 // Since t1 != t2 and one of them is null, it is
844 // impossible for them to be equal.
845 return false;
846 }
847
848 // Check if we need base type comparisons.
849 if (SVFUtil::isa<DIBasicType>(t1) && SVFUtil::isa<DIBasicType>(t2))
850 {
851 const DIBasicType *b1 = SVFUtil::dyn_cast<DIBasicType>(t1);
852 const DIBasicType *b2 = SVFUtil::dyn_cast<DIBasicType>(t2);
853
854 unsigned enc1 = b1->getEncoding();
855 unsigned enc2 = b2->getEncoding();
856 bool okayEnc = ((enc1 == dwarf::DW_ATE_signed || enc1 == dwarf::DW_ATE_unsigned || enc1 == dwarf::DW_ATE_boolean)
857 && (enc2 == dwarf::DW_ATE_signed || enc2 == dwarf::DW_ATE_unsigned || enc2 == dwarf::DW_ATE_boolean))
858 ||
859 (enc1 == dwarf::DW_ATE_float && enc2 == dwarf::DW_ATE_float)
860 ||
861 ((enc1 == dwarf::DW_ATE_signed_char || enc1 == dwarf::DW_ATE_unsigned_char)
862 &&
863 (enc2 == dwarf::DW_ATE_signed_char || enc2 == dwarf::DW_ATE_unsigned_char));
864
865 if (!okayEnc) return false;
866 // Now we have split integers, floats, and chars, ignoring signedness.
867
868 return t1->getSizeInBits() == t2->getSizeInBits()
869 && t1->getAlignInBits() == t2->getAlignInBits();
870 }
871
872 // Check, do we need to compare base types?
873 // This makes pointers, references, and arrays equivalent.
874 // Will handle member types.
875 if ((SVFUtil::isa<DIDerivedType>(t1) || t1->getTag() == dwarf::DW_TAG_array_type)
876 && (SVFUtil::isa<DIDerivedType>(t2) || t2->getTag() == dwarf::DW_TAG_array_type))
877 {
878 const DIType *base1, *base2;
879
880 // Set base1.
881 if (const DIDerivedType *d1 = SVFUtil::dyn_cast<DIDerivedType>(t1))
882 {
883 base1 = d1->getBaseType();
884 }
885 else
886 {
887 const DICompositeType *c1 = SVFUtil::dyn_cast<DICompositeType>(t1);
888 assert(c1 && "teq: bad cast for array type");
889 base1 = c1->getBaseType();
890 }
891
892 // Set base2.
893 if (const DIDerivedType *d2 = SVFUtil::dyn_cast<DIDerivedType>(t2))
894 {
895 base2 = d2->getBaseType();
896 }
897 else
898 {
899 const DICompositeType *c2 = SVFUtil::dyn_cast<DICompositeType>(t2);
900 assert(c2 && "teq: bad cast for array type");
901 base2 = c2->getBaseType();
902 }
903
904 // For ptr-to-member, there is some imprecision (but soundness) in
905 // that we don't check the class type.
906 return teq(base1, base2);
907 }
908
909 if (SVFUtil::isa<DICompositeType>(t1) && SVFUtil::isa<DICompositeType>(t2))
910 {
911 const DICompositeType *ct1 = SVFUtil::dyn_cast<DICompositeType>(t1);
912 const DICompositeType *ct2 = SVFUtil::dyn_cast<DICompositeType>(t2);
913
914 if (ct1->getTag() != ct2->getTag()) return false;
915
916 // Treat all enums the same.
917 if (ct1->getTag() == dwarf::DW_TAG_enumeration_type)
918 {
919 return true;
920 }
921
922 // C++ classes? Check mangled name.
923 if (ct1->getTag() == dwarf::DW_TAG_class_type)
924 {
925 return ct1->getIdentifier() == ct2->getIdentifier();
926 }
927
928 // Either union or struct, simply test all fields are equal.
929 // Seems like it is enough to check it was defined in the same place.
930 // The elements sometimes differ but are referring to the same fields.
931 return ct1->getName() == ct2->getName()
932 && ct1->getFile() == ct2->getFile()
933 && ct1->getLine() == ct2->getLine();
934 }
935
936 // They were not equal base types (discounting signedness), nor were they
937 // "equal" pointers/references/arrays, nor were they the structurally equivalent,
938 // nor were they completely equal.
939 return false;
940}

Member Data Documentation

◆ canonicalTypeMap

Map<const DIType*, const DIType*> SVF::DCHGraph::canonicalTypeMap
protected

Maps types to their canonical type (many-to-one).

Definition at line 374 of file DCHG.h.

◆ canonicalTypes

Set<const DIType*> SVF::DCHGraph::canonicalTypes
protected

Set of all possible canonical types (i.e. values of canonicalTypeMap).

Definition at line 376 of file DCHG.h.

◆ chaFFMap

Map<const DIType*, NodeBS> SVF::DCHGraph::chaFFMap
protected

Maps types to all children but also considering first field.

Definition at line 368 of file DCHG.h.

◆ chaMap

Map<const DIType*, NodeBS> SVF::DCHGraph::chaMap
protected

Maps types to all children (i.e. CHA).

Definition at line 366 of file DCHG.h.

◆ containingAggs

Map<const DIType*, Set<const DIType*> > SVF::DCHGraph::containingAggs
protected

Maps aggregate types to all the aggregate types it transitively contains.

Definition at line 380 of file DCHG.h.

◆ csCHAMap

Map<const CallICFGNode*, VFunSet> SVF::DCHGraph::csCHAMap
protected

Maps callsites to a set of potential virtual functions based on CHA.

Definition at line 372 of file DCHG.h.

◆ diTypeToNodeMap

Map<const DIType*, DCHNode*> SVF::DCHGraph::diTypeToNodeMap
protected

Maps DITypes to their nodes.

Definition at line 362 of file DCHG.h.

◆ extended

bool SVF::DCHGraph::extended = false
protected

Whether this CHG is an extended CHG (first-field). Set by buildCHG.

Definition at line 360 of file DCHG.h.

◆ fieldTypes

Map<const DIType*, std::vector<const DIType*> > SVF::DCHGraph::fieldTypes
protected

Maps types to their flattened fields' types.

Definition at line 378 of file DCHG.h.

◆ numTypes

NodeID SVF::DCHGraph::numTypes
private

Number of types (nodes) in the graph.

Definition at line 445 of file DCHG.h.

◆ vtblCHAMap

Map<const DIType*, VTableSet> SVF::DCHGraph::vtblCHAMap
protected

Maps types to a set with their vtable and all their children's.

Definition at line 370 of file DCHG.h.

◆ vtblToTypeMap

Map<const GlobalObjVar*, const DIType*> SVF::DCHGraph::vtblToTypeMap
protected

Maps VTables to the DIType associated with them.

Definition at line 364 of file DCHG.h.


The documentation for this class was generated from the following files: