#include <TypeBasedHeapCloning.h>

Inheritance diagram for SVF::TypeBasedHeapCloning:

Public Member Functions
virtual	~TypeBasedHeapCloning ()

Static Public Member Functions
static const MDNode *	getRawCTirMetadata (const Value *)
	Returns raw ctir metadata of a Value. Returns null if it doesn't exist. More...

Protected Member Functions
	TypeBasedHeapCloning (BVDataPTAImpl *pta)
	Constructor. pta is the pointer analysis using this object (i.e. that which is extending). More...

virtual void	backPropagate (NodeID clone)=0

void	setDCHG (DCHGraph *dchg)
	DCHG must be set by extending class once the DCHG is available. More...

void	setPAG (PAG *pag)
	PAG must be set by extending class once the PAG is available. More...

bool	isBlkObjOrConstantObj (NodeID o) const

bool	isBase (const DIType a, const DIType b) const

bool	isClone (NodeID o) const
	Returns true if o is a clone. More...

void	setType (NodeID o, const DIType *t)
	Sets the type (in objToType) of o. More...

const DIType *	getType (NodeID o) const
	Returns the type (from objToType) of o. Asserts existence. More...

void	setAllocationSite (NodeID o, NodeID site)
	Sets the allocation site (in objToAllocation) of o. More...

NodeID	getAllocationSite (NodeID o) const
	Returns the allocation site (from objToAllocation) of o. Asserts existence. More...

const NodeBS	getObjsWithClones (void)
	Returns objects that have clones (any key in objToClones). More...

void	addClone (NodeID o, NodeID c)
	Add a clone c to object o. More...

const NodeBS &	getClones (NodeID o)
	Returns all the clones of o. More...

void	setOriginalObj (NodeID c, NodeID o)

NodeID	getOriginalObj (NodeID c) const
	Returns the original object c is cloned from. If c is not a clone, returns itself. More...

PointsTo &	getFilterSet (NodeID loc)
	Returns the filter set of a location. Not const; could create empty PointsTo. More...

void	addGepToObj (NodeID gep, NodeID base, unsigned offset)
	Associates gep with base (through objToGeps and memObjToGeps). More...

const NodeBS &	getGepObjsFromMemObj (const MemObj *memObj, unsigned offset)

const NodeBS &	getGepObjs (NodeID base)

const NodeBS	getGepObjClones (NodeID base, unsigned offset)

bool	init (NodeID loc, NodeID p, const DIType *tildet, bool reuse, bool gep=false)

NodeID	cloneObject (NodeID o, const DIType *type, bool reuse)

NodeID	addCloneDummyObjNode (const MemObj *mem)
	Add clone dummy object node to PAG. More...

NodeID	addCloneGepObjNode (const MemObj *mem, const LocationSet &l)
	Add clone GEP object node to PAG. More...

NodeID	addCloneFIObjNode (const MemObj *mem)
	Add clone FI object node to PAG. More...

const DIType *	getTypeFromCTirMetadata (const Value *)

void	validateTBHCTests (SVFModule *svfMod)

void	dumpStats (void)
	Dump some statistics we tracked. More...

Protected Attributes
DCHGraph *	dchg = nullptr

Static Protected Attributes
static const DIType *	undefType = nullptr
	The undefined type (•); void. More...

static const std::string	derefFnName = "deref"
	deref function for TBHC alias tests. More...

static const std::string	mangledDerefFnName = "_Z5derefv"
	deref function (mangled) for TBHC alias tests. More...

Private Member Functions
bool	isGep (const PAGNode *n) const
	Test whether object is a GEP object. For convenience. More...

Private Attributes
BVDataPTAImpl *	pta
	PTA extending this class. More...

PAG *	ppag = nullptr
	PAG the PTA uses. Just a shortcut for getPAG(). More...

Map< NodeID, const DIType * >	objToType
	Object -> its type. More...

Map< NodeID, NodeID >	objToAllocation

Map< NodeID, NodeBS >	objToClones
	(Original) object -> set of its clones. More...

Map< NodeID, NodeID >	cloneToOriginalObj
	(Clone) object -> original object (opposite of objToclones). More...

Map< NodeID, PointsTo >	locToFilterSet
	Maps nodes (a location like a PAG node or SVFG node) to their filter set. More...

Map< NodeID, NodeBS >	objToGeps
	Maps objects to the GEP nodes beneath them. More...

Map< const MemObj *, Map< unsigned, NodeBS > >	memObjToGeps
	Maps memory objects to their GEP objects. (memobj -> (fieldidx -> geps)) More...

unsigned	numInit = 0

unsigned	numTBWU = 0

unsigned	numTBSSU = 0

unsigned	numTBSU = 0

unsigned	numReuse = 0

unsigned	numAgg = 0

unsigned	numSGInit = 0

unsigned	numSGTBWU = 0

unsigned	numSGTBSSU = 0

unsigned	numSGTBSU = 0

unsigned	numSGReuse = 0

unsigned	numSGAgg = 0

Detailed Description

Definition at line 21 of file TypeBasedHeapCloning.h.

Constructor & Destructor Documentation

◆ ~TypeBasedHeapCloning()

virtual SVF::TypeBasedHeapCloning::~TypeBasedHeapCloning ( )

inlinevirtual

Definition at line 27 of file TypeBasedHeapCloning.h.

27 { };

◆ TypeBasedHeapCloning()

TypeBasedHeapCloning::TypeBasedHeapCloning ( BVDataPTAImpl * pta )

protected

Constructor. pta is the pointer analysis using this object (i.e. that which is extending).

Definition at line 21 of file TypeBasedHeapCloning.cpp.

 {
     this->pta = pta;
 }

Member Function Documentation

◆ addClone()

void TypeBasedHeapCloning::addClone	(	NodeID	o,
		NodeID	c
	)

protected

Add a clone c to object o.

Definition at line 86 of file TypeBasedHeapCloning.cpp.

 {
     objToClones[o].set(c);
 }

◆ addCloneDummyObjNode()

NodeID TypeBasedHeapCloning::addCloneDummyObjNode ( const MemObj * mem )

inlineprotected

Add clone dummy object node to PAG.

Definition at line 501 of file TypeBasedHeapCloning.cpp.

 {
     NodeID id = NodeIDAllocator::get()->allocateObjectId();
     return ppag->addObjNode(nullptr, new CloneDummyObjPN(id, mem), id);
 }

◆ addCloneFIObjNode()

NodeID TypeBasedHeapCloning::addCloneFIObjNode ( const MemObj * mem )

inlineprotected

Add clone FI object node to PAG.

Definition at line 513 of file TypeBasedHeapCloning.cpp.

 {
     NodeID id = NodeIDAllocator::get()->allocateObjectId();
     return ppag->addObjNode(mem->getRefVal(), new CloneFIObjPN(mem->getRefVal(), id, mem), id);
 }

◆ addCloneGepObjNode()

NodeID TypeBasedHeapCloning::addCloneGepObjNode	(	const MemObj *	mem,
		const LocationSet &	l
	)

inlineprotected

Add clone GEP object node to PAG.

Definition at line 507 of file TypeBasedHeapCloning.cpp.

 {
     NodeID id = NodeIDAllocator::get()->allocateObjectId();
     return ppag->addObjNode(mem->getRefVal(), new CloneGepObjPN(mem, id, l), id);
 }

◆ addGepToObj()

void TypeBasedHeapCloning::addGepToObj	(	NodeID	gep,
		NodeID	base,
		unsigned	offset
	)

protected

Associates gep with base (through objToGeps and memObjToGeps).

Definition at line 118 of file TypeBasedHeapCloning.cpp.

 {
     objToGeps[base].set(gep);
     const PAGNode *baseNode = ppag->getPAGNode(base);
     assert(baseNode && "TBHC: given bad base node?");
     const ObjPN *baseObj = SVFUtil::dyn_cast<ObjPN>(baseNode);
     assert(baseObj && "TBHC: non-object given for base?");
     // We can use the base or the gep mem. obj.; should be identical.
     const MemObj *baseMemObj = baseObj->getMemObj();
 
     objToGeps[base].set(gep);
     memObjToGeps[baseMemObj][offset].set(gep);
 }

◆ backPropagate()

virtual void SVF::TypeBasedHeapCloning::backPropagate ( NodeID clone )

protectedpure virtual

Required by user. Handles back-propagation of newly created clone after all metadata has been set. Used by cloneObject.

Implemented in SVF::FlowSensitiveTBHC.

◆ cloneObject()

NodeID TypeBasedHeapCloning::cloneObject	(	NodeID	o,
		const DIType *	type,
		bool	reuse
	)

protected

Returns a clone of o with type type. reuse indicates whether we are cloning as a result of reuse.

Definition at line 411 of file TypeBasedHeapCloning.cpp.

 {
     NodeID clone;
     const PAGNode *obj = ppag->getPAGNode(o);
     if (const GepObjPN *gepObj = SVFUtil::dyn_cast<GepObjPN>(obj))
     {
         const NodeBS &clones = getGepObjClones(gepObj->getBaseNode(), gepObj->getLocationSet().getOffset());
         // TODO: a bit of repetition.
         for (NodeID clone : clones)
         {
             if (getType(clone) == type)
             {
                 return clone;
             }
         }
 
         clone = addCloneGepObjNode(gepObj->getMemObj(), gepObj->getLocationSet());
 
         // The base needs to know about the new clone.
         addGepToObj(clone, gepObj->getBaseNode(), gepObj->getLocationSet().getOffset());
 
         addClone(o, clone);
         addClone(getOriginalObj(o), clone);
         // The only instance of original object of a Gep object being retrieved is for
         // IN sets and gepToSVFGRetriever in FSTBHC, so we don't care that clone comes
         // from o (we can get that by checking the base and offset).
         setOriginalObj(clone, getOriginalObj(o));
         CloneGepObjPN *cloneGepObj = SVFUtil::dyn_cast<CloneGepObjPN>(ppag->getPAGNode(clone));
         cloneGepObj->setBaseNode(gepObj->getBaseNode());
     }
     else if (SVFUtil::isa<FIObjPN>(obj) || SVFUtil::isa<DummyObjPN>(obj))
     {
         o = getOriginalObj(o);
         // Check there isn't an appropriate clone already.
         const NodeBS &clones = getClones(o);
         for (NodeID clone : clones)
         {
             if (getType(clone) == type)
             {
                 return clone;
             }
         }
 
         if (const FIObjPN *fiObj = SVFUtil::dyn_cast<FIObjPN>(obj))
         {
             clone = addCloneFIObjNode(fiObj->getMemObj());
         }
         else
         {
             const DummyObjPN *dummyObj = SVFUtil::dyn_cast<DummyObjPN>(obj);
             clone = addCloneDummyObjNode(dummyObj->getMemObj());
         }
         // We checked above that it's an FIObj or a DummyObj.
 
         // Tracking object<->clone mappings.
         addClone(o, clone);
         setOriginalObj(clone, o);
     }
     else
     {
         assert(false && "FSTBHC: trying to clone unhandled object");
     }
 
     // Clone's metadata. This can be shared between Geps/otherwise.
     setType(clone, type);
     setAllocationSite(clone, getAllocationSite(o));
 
     backPropagate(clone);
 
     return clone;
 }

◆ dumpStats()

void TypeBasedHeapCloning::dumpStats ( void )

protected

Dump some statistics we tracked.

Definition at line 731 of file TypeBasedHeapCloning.cpp.

 {
     std::string indent = "";
     SVFUtil::outs() << "@@@@@@@@@ TBHC STATISTICS @@@@@@@@@\n";
     indent = "  ";
 
     // Print clones with their types.
     SVFUtil::outs() << indent << "=== Original objects to clones ===\n";
     indent = "    ";
     unsigned totalClones = 0;
     const NodeBS objs = getObjsWithClones();
     for (NodeID o : objs)
     {
         const NodeBS &clones = getClones(o);
         if (clones.count() == 0) continue;
 
         totalClones += clones.count();
         SVFUtil::outs() << indent
                         << "  " << o << " : "
                         << "(" << clones.count() << ")"
                         << "[ ";
         bool first = true;
         for (NodeID c : clones)
         {
             if (!first)
             {
                 SVFUtil::outs() << ", ";
             }
 
             SVFUtil::outs() << c
                             << "{"
                             << dchg->diTypeToStr(getType(c))
                             << "}";
             first = false;
         }
 
         SVFUtil::outs() << " ]\n";
     }
 
     indent = "  ";
     SVFUtil::outs() << indent
                     << "Total: " << ppag->getObjectNodeNum() + ppag->getFieldObjNodeNum() + totalClones
                     << " (" << totalClones << " clones)\n";
     SVFUtil::outs() << indent << "==================================\n";
 
     SVFUtil::outs() << indent << "INITIALISE : " << numInit  << "\n";
     SVFUtil::outs() << indent << "TBWU       : " << numTBWU  << "\n";
     SVFUtil::outs() << indent << "TBSSU      : " << numTBSSU << "\n";
     SVFUtil::outs() << indent << "TBSU       : " << numTBSU  << "\n";
     SVFUtil::outs() << indent << "REUSE      : " << numReuse << "\n";
     SVFUtil::outs() << indent << "AGG CASE   : " << numAgg   << "\n";
 
     SVFUtil::outs() << "\n";
     SVFUtil::outs() << indent << "STACK/GLOBAL OBJECTS\n";
     indent = "    ";
     SVFUtil::outs() << indent << "INITIALISE : " << numSGInit  << "\n";
     SVFUtil::outs() << indent << "TBWU       : " << numSGTBWU  << "\n";
     SVFUtil::outs() << indent << "TBSSU      : " << numSGTBSSU << "\n";
     SVFUtil::outs() << indent << "TBSU       : " << numSGTBSU  << "\n";
     SVFUtil::outs() << indent << "REUSE      : " << numSGReuse << "\n";
     SVFUtil::outs() << indent << "AGG CASE   : " << numSGAgg   << "\n";
 
     SVFUtil::outs() << "@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@\n";
 }

◆ getAllocationSite()

NodeID TypeBasedHeapCloning::getAllocationSite ( NodeID o ) const

protected

Returns the allocation site (from objToAllocation) of o. Asserts existence.

Definition at line 69 of file TypeBasedHeapCloning.cpp.

 {
     assert(objToAllocation.find(o) != objToAllocation.end() && "TBHC: object has no allocation site?");
     return objToAllocation.at(o);
 }

◆ getClones()

const NodeBS & TypeBasedHeapCloning::getClones ( NodeID o )

protected

Returns all the clones of o.

Definition at line 91 of file TypeBasedHeapCloning.cpp.

 {
     return objToClones[o];
 }

◆ getFilterSet()

PointsTo & TypeBasedHeapCloning::getFilterSet ( NodeID loc )

protected

Returns the filter set of a location. Not const; could create empty PointsTo.

Definition at line 113 of file TypeBasedHeapCloning.cpp.

 {
     return locToFilterSet[loc];
 }

◆ getGepObjClones()

const NodeBS TypeBasedHeapCloning::getGepObjClones	(	NodeID	base,
		unsigned	offset
	)

protected

Returns the GEP object node(s) of base for ls. This may include clones. If there are no GEP objects, then getGepObjNode is called on the PAG (through base's getGepObjNode) which will create one.

Definition at line 142 of file TypeBasedHeapCloning.cpp.

 {
     assert(dchg && "TBHC: DCHG not set!");
     // Set of GEP objects we will return.
     NodeBS geps;
 
     PAGNode *node = ppag->getPAGNode(base);
     assert(node && "TBHC: base object node does not exist.");
     ObjPN *baseNode = SVFUtil::dyn_cast<ObjPN>(node);
     assert(baseNode && "TBHC: base \"object\" node is not an object.");
 
     // totalOffset is the offset from the real base (i.e. base of base),
     // offset is the offset into base, whether it is a field itself or not.
     unsigned totalOffset = offset;
     if (const GepObjPN *baseGep = SVFUtil::dyn_cast<GepObjPN>(baseNode))
     {
         totalOffset += baseGep->getLocationSet().getOffset();
     }
 
     const DIType *baseType = getType(base);
 
     // First field? Just return the whole object; same thing.
     // For arrays, we want things to work as normal because an array *object* is more
     // like a pointer than a struct object.
     if (offset == 0 && baseType->getTag() != dwarf::DW_TAG_array_type)
     {
         // The base object is the 0 gep object.
         addGepToObj(base, base, 0);
         geps.set(base);
         return geps;
     }
 
     if (baseNode->getMemObj()->isFieldInsensitive())
     {
         // If it's field-insensitive, the base represents everything.
         geps.set(base);
         return geps;
     }
 
     // Caching on offset would improve performance but it seems minimal.
     const NodeBS &gepObjs = getGepObjs(base);
     for (NodeID gep : gepObjs)
     {
         PAGNode *node = ppag->getPAGNode(gep);
         assert(node && "TBHC: expected gep node doesn't exist.");
         assert((SVFUtil::isa<GepObjPN>(node) || SVFUtil::isa<FIObjPN>(node))
                && "TBHC: expected a GEP or FI object.");
 
         if (GepObjPN *gepNode = SVFUtil::dyn_cast<GepObjPN>(node))
         {
             if (gepNode->getLocationSet().getOffset() == totalOffset)
             {
                 geps.set(gep);
             }
         }
         else
         {
             // Definitely a FIObj (asserted), but we don't want to add it if
             // the object is field-sensitive because in that case it actually
             // represents the 0th field, not the whole object.
             if (baseNode->getMemObj()->isFieldInsensitive())
             {
                 geps.set(gep);
             }
         }
     }
 
     if (geps.empty())
     {
         // No gep node has even be created, so create one.
         NodeID newGep;
         LocationSet newLS;
         // fldIdx is what is returned by getOffset.
         newLS.setFldIdx(totalOffset);
 
         if (isClone(base))
         {
             // Don't use ppag->getGepObjNode because base and it's original object
             // have the same memory object which is the key PAG uses.
             newGep = addCloneGepObjNode(baseNode->getMemObj(), newLS);
         }
         else
         {
             newGep = ppag->getGepObjNode(base, newLS);
         }
 
         if (GepObjPN *gep = SVFUtil::dyn_cast<GepObjPN>(ppag->getPAGNode(newGep)))
         {
             gep->setBaseNode(base);
         }
 
         addGepToObj(newGep, base, totalOffset);
         const DIType *newGepType = nullptr;
         if (baseType->getTag() == dwarf::DW_TAG_array_type || baseType->getTag() == dwarf::DW_TAG_pointer_type)
         {
             if (const DICompositeType *arrayType = SVFUtil::dyn_cast<DICompositeType>(baseType))
             {
                 // Array access.
                 newGepType = arrayType->getBaseType();
             }
             else if (const DIDerivedType *ptrType = SVFUtil::dyn_cast<DIDerivedType>(baseType))
             {
                 // Pointer access.
                 newGepType = ptrType->getBaseType();
             }
             assert(newGepType && "TBHC: newGepType is neither DIComposite nor DIDerived");
 
             // Get the canonical type because we got the type from the DIType infrastructure directly.
             newGepType = dchg->getCanonicalType(newGepType);
         }
         else
         {
             // Must be a struct/class.
             // Don't use totalOffset because we're operating on the Gep object which is our parent
             // (i.e. field of some base, not the base itself).
             newGepType = dchg->getFieldType(getType(base), offset);
         }
 
         setType(newGep, newGepType);
         // We call the object created in the non-TBHC analysis the original object.
         setOriginalObj(newGep, ppag->getGepObjNode(baseNode->getMemObj(), offset));
         setAllocationSite(newGep, 0);
 
         geps.set(newGep);
     }
 
     return geps;
 }

◆ getGepObjs()

const NodeBS & TypeBasedHeapCloning::getGepObjs ( NodeID base )

protected

Returns all gep objects under an object. Not const; could create empty set.

Definition at line 137 of file TypeBasedHeapCloning.cpp.

 {
     return objToGeps[base];
 }

◆ getGepObjsFromMemObj()

const NodeBS & TypeBasedHeapCloning::getGepObjsFromMemObj	(	const MemObj *	memObj,
		unsigned	offset
	)

protected

Returns all gep objects at a particular offset for memory object. Not const; could create empty set.

Definition at line 132 of file TypeBasedHeapCloning.cpp.

 {
     return memObjToGeps[memObj][offset];
 }

◆ getObjsWithClones()

const NodeBS TypeBasedHeapCloning::getObjsWithClones ( void )

protected

Returns objects that have clones (any key in objToClones).

Definition at line 75 of file TypeBasedHeapCloning.cpp.

 {
     NodeBS objs;
     for (std::pair<NodeID, NodeBS> oc : objToClones)
     {
         objs.set(oc.first);
     }
 
     return objs;
 }

◆ getOriginalObj()

NodeID TypeBasedHeapCloning::getOriginalObj ( NodeID c ) const

protected

Returns the original object c is cloned from. If c is not a clone, returns itself.

Definition at line 101 of file TypeBasedHeapCloning.cpp.

 {
     if (isClone(c))
     {
         assert(cloneToOriginalObj.find(c) != cloneToOriginalObj.end()
                && "TBHC: original object not set for clone?");
         return cloneToOriginalObj.at(c);
     }
 
     return c;
 }

◆ getRawCTirMetadata()

const MDNode * TypeBasedHeapCloning::getRawCTirMetadata ( const Value * v )

static

Returns raw ctir metadata of a Value. Returns null if it doesn't exist.

Definition at line 483 of file TypeBasedHeapCloning.cpp.

 {
     assert(v != nullptr && "TBHC: trying to get metadata from nullptr!");
 
     const MDNode *mdNode = nullptr;
     if (const Instruction *inst = SVFUtil::dyn_cast<Instruction>(v))
     {
         mdNode = inst->getMetadata(cppUtil::ctir::derefMDName);
     }
     else if (const GlobalObject *go = SVFUtil::dyn_cast<GlobalObject>(v))
     {
         mdNode = go->getMetadata(cppUtil::ctir::derefMDName);
     }
 
     // Will be nullptr if metadata isn't there.
     return mdNode;
 }

◆ getType()

const DIType * TypeBasedHeapCloning::getType ( NodeID o ) const

protected

Returns the type (from objToType) of o. Asserts existence.

Definition at line 58 of file TypeBasedHeapCloning.cpp.

 {
     assert(objToType.find(o) != objToType.end() && "TBHC: object has no type?");
     return objToType.at(o);
 }

◆ getTypeFromCTirMetadata()

const DIType * TypeBasedHeapCloning::getTypeFromCTirMetadata ( const Value * v )

protected

Returns the ctir type attached to the value, nullptr if non-existant. Not static because it needs the DCHG to return the canonical type. Not static because we need dchg's getCanonicalType.

Definition at line 519 of file TypeBasedHeapCloning.cpp.

 {
     assert(v != nullptr && "TBHC: trying to get type from nullptr!");
 
     const MDNode *mdNode = getRawCTirMetadata(v);
     if (mdNode == nullptr)
     {
         return nullptr;
     }
 
     const DIType *type = SVFUtil::dyn_cast<DIType>(mdNode);
     if (type == nullptr)
     {
         SVFUtil::errs() << "TBHC: bad ctir metadata type\n";
         return nullptr;
     }
 
     return dchg->getCanonicalType(type);
 }

◆ init()

bool TypeBasedHeapCloning::init	(	NodeID	loc,
		NodeID	p,
		const DIType *	tildet,
		bool	reuse,
		bool	gep = `false`
	)

protected

Initialise the pointees of p at loc (which is type tildet *). reuse indicates whether reuse is a possibility for this initialisation. Returns whether p changed.

Definition at line 271 of file TypeBasedHeapCloning.cpp.

 {
     assert(dchg && "TBHC: DCHG not set!");
     bool changed = false;
 
     const PointsTo &pPt = pta->getPts(p);
     // The points-to set we will populate in the loop to fill pPt.
     PointsTo pNewPt;
 
     PointsTo &filterSet = getFilterSet(loc);
     for (NodeID o : pPt)
     {
         // If it's been filtered before, it'll be filtered again.
         if (filterSet.test(o)) continue;
 
         PAGNode *obj = ppag->getPAGNode(o);
         assert(obj && "TBHC: pointee object does not exist in PAG?");
         const DIType *tp = getType(o);  // tp is t'
 
         // When an object is field-insensitive, we can't filter on any of the fields' types.
         // i.e. a pointer of the field type can safely access an object of the base/struct
         // type if that object is field-insensitive.
         bool fieldInsensitive = false;
         std::vector<const DIType *> fieldTypes;
         if (ObjPN *obj = SVFUtil::dyn_cast<ObjPN>(ppag->getPAGNode(o)))
         {
             fieldInsensitive = obj->getMemObj()->isFieldInsensitive();
             if (tp != nullptr && (tp->getTag() == dwarf::DW_TAG_structure_type
                                   || tp->getTag() == dwarf::DW_TAG_class_type))
             {
                 fieldTypes = dchg->getFieldTypes(tp);
             }
         }
 
         const Set<const DIType *> &aggs = dchg->isAgg(tp)
                                              ? dchg->getAggs(tp) : Set<const DIType *>();
 
         NodeID prop;
         bool filter = false;
         if (tp == undefType)
         {
             // o is uninitialised.
             // GEP objects should never be uninitialised; type assigned at creation.
             assert(!isGep(obj) && "TBHC: GEP object is untyped!");
             prop = cloneObject(o, tildet, false);
             ++numInit;
             if (!pta->isHeapMemObj(o) && !SVFUtil::isa<DummyObjPN>(obj)) ++numSGInit;
         }
         else if (fieldInsensitive && tp && dchg->isFieldOf(tildet, tp))
         {
             // Field-insensitive object but the instruction is operating on a field.
             prop = o;
             ++numTBWU;
             if (!pta->isHeapMemObj(o) && !SVFUtil::isa<DummyObjPN>(obj)) ++numSGTBWU;
         }
         else if (gep && aggs.find(tildet) != aggs.end())
         {
             // SVF treats two consecutive GEPs as children to the same load/store.
             // Special case for aggregates.
             // SVF will transform (for example)
             //    `1: s = get struct element X from array a; 2: f = get field of struct Y from s;`
             // to `1: s = get struct element X from array a; 2: f = get field of struct Y from a;`
             // so we want the second instruction to be operating on an object of type
             // 'Struct S', not 'Array of S'.
             prop = cloneObject(o, tildet, false);
             ++numAgg;
             if (!pta->isHeapMemObj(o) && !SVFUtil::isa<DummyObjPN>(obj)) ++numSGAgg;
         }
         else if (isBase(tp, tildet) && tp != tildet
                  && (reuse || dchg->isFirstField(tp, tildet) || (!reuse && pta->isHeapMemObj(o))))
         {
             // Downcast.
             // One of three conditions:
             //  - !reuse && heap: because downcasts should not happen to stack/globals.
             //  - isFirstField because ^ can happen because when we take the field of a
             //    struct that is a struct, we get its first field, then it may downcast
             //    back to the struct at another GEP.
             //    TODO: this can probably be solved more cleanly.
             //  - reuse: because it can happen to stack/heap objects.
             prop = cloneObject(o, tildet, reuse);
             ++numTBSSU;
             if (!pta->isHeapMemObj(o) && !SVFUtil::isa<DummyObjPN>(obj)) ++numSGTBSSU;
         }
         else if (isBase(tildet, tp))
         {
             // Upcast.
             prop = o;
             ++numTBWU;
             if (!pta->isHeapMemObj(o) && !SVFUtil::isa<DummyObjPN>(obj)) ++numSGTBWU;
         }
         else if (tildet != tp && reuse)
         {
             // Reuse.
             prop = cloneObject(o, tildet, true);
             ++numReuse;
             if (!pta->isHeapMemObj(o) && !SVFUtil::isa<DummyObjPN>(obj)) ++numSGReuse;
         }
         else
         {
             // Some spurious objects will be filtered.
             filter = true;
             prop = o;
             ++numTBSU;
             if (!pta->isHeapMemObj(o) && !SVFUtil::isa<DummyObjPN>(obj)) ++numSGTBSU;
         }
 
         if (prop != o)
         {
             // If we cloned, we want to keep o in p's PTS but filter it (ignore it later).
             pNewPt.set(o);
             filterSet.set(o);
             // TODO: hack, sound but imprecise and unclean.
             // In the aggs case there is a difference between it being good for
             // arrays and structs. For now, just propagate both the clone and the original
             // object till a cleaner solution is found.
             if (gep && aggs.find(tildet) != aggs.end())
             {
                 filterSet.reset(o);
             }
         }
 
         pNewPt.set(prop);
 
         if (filter)
         {
             filterSet.set(o);
         }
     }
 
     if (pPt != pNewPt)
     {
         // Seems fast enough to perform in the naive way.
         pta->clearFullPts(p);
         pta->unionPts(p, pNewPt);
         changed = true;
     }
 
     return changed;
 }

◆ isBase()

bool TypeBasedHeapCloning::isBase	(	const DIType *	a,
		const DIType *	b
	)		const

protected

Wrapper around DCHGraph::isBase. Purpose is to keep our conditions clean by only passing two parameters like the rules.

Definition at line 42 of file TypeBasedHeapCloning.cpp.

 {
     assert(dchg && "TBHC: DCHG not set!");
     return dchg->isBase(a, b, true);
 }

◆ isBlkObjOrConstantObj()

bool TypeBasedHeapCloning::isBlkObjOrConstantObj ( NodeID o ) const

protected

Check if an object is a black hole obj or a constant object. Required since other implementations obviously do not account for clones.

Definition at line 36 of file TypeBasedHeapCloning.cpp.

 {
     if (isClone(o)) o = cloneToOriginalObj.at(o);
     return SVFUtil::isa<ObjPN>(ppag->getPAGNode(o)) && ppag->isBlkObjOrConstantObj(o);
 }

◆ isClone()

bool TypeBasedHeapCloning::isClone ( NodeID o ) const

protected

Returns true if o is a clone.

Definition at line 48 of file TypeBasedHeapCloning.cpp.

 {
     return cloneToOriginalObj.find(o) != cloneToOriginalObj.end();
 }

◆ isGep()

bool TypeBasedHeapCloning::isGep ( const PAGNode * n ) const

private

Test whether object is a GEP object. For convenience.

Definition at line 539 of file TypeBasedHeapCloning.cpp.

 {
     assert(n != nullptr && "TBHC: testing if null is a GEP object!");
     return SVFUtil::isa<GepObjPN>(n);
 }

◆ setAllocationSite()

void TypeBasedHeapCloning::setAllocationSite	(	NodeID	o,
		NodeID	site
	)

protected

Sets the allocation site (in objToAllocation) of o.

Definition at line 64 of file TypeBasedHeapCloning.cpp.

 {
     objToAllocation.insert({o, site});
 }

◆ setDCHG()

void TypeBasedHeapCloning::setDCHG ( DCHGraph * dchg )

protected

DCHG must be set by extending class once the DCHG is available.

Definition at line 26 of file TypeBasedHeapCloning.cpp.

 {
     this->dchg = dchg;
 }

◆ setOriginalObj()

void TypeBasedHeapCloning::setOriginalObj	(	NodeID	c,
		NodeID	o
	)

protected

Definition at line 96 of file TypeBasedHeapCloning.cpp.

 {
     cloneToOriginalObj.insert({c, o});
 }

◆ setPAG()

void TypeBasedHeapCloning::setPAG ( PAG * pag )

protected

PAG must be set by extending class once the PAG is available.

Definition at line 31 of file TypeBasedHeapCloning.cpp.

 {
     ppag = pag;
 }

◆ setType()

void TypeBasedHeapCloning::setType	(	NodeID	o,
		const DIType *	t
	)

protected

Sets the type (in objToType) of o.

Definition at line 53 of file TypeBasedHeapCloning.cpp.

 {
     objToType.insert({o, t});
 }

◆ validateTBHCTests()

void TypeBasedHeapCloning::validateTBHCTests ( SVFModule * svfMod )

protected

Runs tests on MAYALIAS, NOALIAS, etc. built from TBHC_MAYALIAS, TBHC_NOALIAS, etc. macros. TBHC_XALIAS macros produce: call XALIAS(...) %1 = load ... ... n = load p store ... n-1, ...* n !ctir !t1 call deref() n+1 = load ... ... n+n = load q store ... n+n-1, ...* n+n !ctir !t2 call deref() We want to test the points-to sets of n and n+n after filtering with !t1 and !t2 respectively.

Definition at line 562 of file TypeBasedHeapCloning.cpp.

 {
     const LLVMModuleSet *llvmModuleSet = LLVMModuleSet::getLLVMModuleSet();
     for (u32_t i = 0; i < llvmModuleSet->getModuleNum(); ++i)
     {
         const PAG::CallSiteSet &callSites = ppag->getCallSiteSet();
         for (const CallBlockNode *cbn : callSites)
         {
             const CallSite &cs = SVFUtil::getLLVMCallSite(cbn->getCallSite());
             const Function *fn = cs.getCalledFunction();
             if (fn == nullptr || !isAliasTestFunction(fn->getName().str()))
             {
                 continue;
             }
 
             // We have a test call,
             // We want the store which stores to the pointer in question (i.e. operand of the
             // store is the pointer, and the store itself is the dereference).
             const StoreInst *ps = nullptr, *qs = nullptr;
             // Check: currInst is a deref call, so p/q is prevInst.
 
             // Find p.
             const Instruction *prevInst = nullptr;
             const Instruction *currInst = cs.getInstruction();
             do
             {
                 if (const CallInst *ci = SVFUtil::dyn_cast<CallInst>(currInst))
                 {
                     std::string calledFnName = ci->getCalledFunction()->getName().str();
                     if (calledFnName == derefFnName || calledFnName == mangledDerefFnName)
                     {
                         const StoreInst *si = SVFUtil::dyn_cast<StoreInst>(prevInst);
                         assert(si && "TBHC: validation macro not producing stores?");
                         ps = si;
                         break;
                     }
                 }
 
                 prevInst = currInst;
                 currInst = currInst->getNextNonDebugInstruction();
             }
             while (currInst != nullptr);
 
             // Repeat for q.
             while (currInst != nullptr)
             {
                 // while loop, not do-while, because we need to the next instruction (current
                 // instruction is the first deref()).
                 prevInst = currInst;
                 currInst = currInst->getNextNonDebugInstruction();
 
                 if (const CallInst *ci = SVFUtil::dyn_cast<CallInst>(currInst))
                 {
                     std::string calledFnName = ci->getCalledFunction()->getName().str();
                     if (calledFnName == derefFnName || calledFnName == mangledDerefFnName)
                     {
                         const StoreInst *si = SVFUtil::dyn_cast<StoreInst>(prevInst);
                         assert(si && "TBHC: validation macro not producing stores?");
                         qs = si;
                         break;
                     }
                 }
             }
 
             assert(ps != nullptr && qs != nullptr && "TBHC: malformed alias test?");
             NodeID p = ppag->getValueNode(ps->getPointerOperand()),
                    q = ppag->getValueNode(qs->getPointerOperand());
             const DIType *pt = getTypeFromCTirMetadata(ps), *qt = getTypeFromCTirMetadata(qs);
 
             // Now filter both points-to sets according to the type of the value.
             const PointsTo &pPts = pta->getPts(p), &qPts = pta->getPts(q);
             PointsTo pPtsFiltered, qPtsFiltered;
             for (NodeID o : pPts)
             {
                 if (getType(o) != undefType && isBase(pt, getType(o)))
                 {
                     pPtsFiltered.set(o);
                 }
             }
 
             for (NodeID o : qPts)
             {
                 if (getType(o) != undefType && isBase(qt, getType(o)))
                 {
                     qPtsFiltered.set(o);
                 }
             }
 
             BVDataPTAImpl *bvpta = SVFUtil::dyn_cast<BVDataPTAImpl>(pta);
             assert(bvpta && "TBHC: need a BVDataPTAImpl for TBHC alias testing.");
             AliasResult res = bvpta->alias(pPtsFiltered, qPtsFiltered);
 
             bool passed = false;
             std::string testName = "";
             if (fn->getName() == PointerAnalysis::aliasTestMayAlias
                     || fn->getName() == PointerAnalysis::aliasTestMayAliasMangled)
             {
                 passed = res == llvm::MayAlias || res == llvm::MustAlias;
                 testName = PointerAnalysis::aliasTestMayAlias;
             }
             else if (fn->getName() == PointerAnalysis::aliasTestNoAlias
                      || fn->getName() == PointerAnalysis::aliasTestNoAliasMangled)
             {
                 passed = res == llvm::NoAlias;
                 testName = PointerAnalysis::aliasTestNoAlias;
             }
             else if (fn->getName() == PointerAnalysis::aliasTestMustAlias
                      || fn->getName() == PointerAnalysis::aliasTestMustAliasMangled)
             {
                 passed = res == llvm::MustAlias || res == llvm::MayAlias;
                 testName = PointerAnalysis::aliasTestMustAlias;
             }
             else if (fn->getName() == PointerAnalysis::aliasTestPartialAlias
                      || fn->getName() == PointerAnalysis::aliasTestPartialAliasMangled)
             {
                 passed = res == llvm::MayAlias || res == llvm::PartialAlias;
                 testName = PointerAnalysis::aliasTestPartialAlias;
             }
             else if (fn->getName() == PointerAnalysis::aliasTestFailMayAlias
                      || fn->getName() == PointerAnalysis::aliasTestFailMayAliasMangled)
             {
                 passed = res != llvm::MayAlias && res != llvm::MustAlias && res != llvm::PartialAlias;
                 testName = PointerAnalysis::aliasTestFailMayAlias;
             }
             else if (fn->getName() == PointerAnalysis::aliasTestFailNoAlias
                      || fn->getName() == PointerAnalysis::aliasTestFailNoAliasMangled)
             {
                 passed = res != llvm::NoAlias;
                 testName = PointerAnalysis::aliasTestFailNoAlias;
             }
 
             SVFUtil::outs() << "[" << pta->PTAName() << "] Checking " << testName << "\n";
             raw_ostream &msgStream = passed ? SVFUtil::outs() : SVFUtil::errs();
             msgStream << (passed ? SVFUtil::sucMsg("\t SUCCESS") : SVFUtil::errMsg("\t FAILURE"))
                       << " : " << testName
                       << " check <id:" << p << ", id:" << q << "> "
                       << "at (" << SVFUtil::getSourceLoc(cs.getInstruction()) << ")\n";
             if (!passed)
                 assert(false && "test case failed!");
 
             if (pPtsFiltered.empty())
             {
                 msgStream << SVFUtil::wrnMsg("\t WARNING")
                           << " : pts(" << p << ") is empty\n";
             }
 
             if (qPtsFiltered.empty())
             {
                 msgStream << SVFUtil::wrnMsg("\t WARNING")
                           << " : pts(" << q << ") is empty\n";
             }
 
             if (testName == PointerAnalysis::aliasTestMustAlias)
             {
                 msgStream << SVFUtil::wrnMsg("\t WARNING")
                           << " : MUSTALIAS tests are actually MAYALIAS tests\n";
             }
 
             if (testName == PointerAnalysis::aliasTestPartialAlias)
             {
                 msgStream << SVFUtil::wrnMsg("\t WARNING")
                           << " : PARTIALALIAS tests are actually MAYALIAS tests\n";
             }
 
             msgStream.flush();
         }
     }
 }

Member Data Documentation

◆ cloneToOriginalObj

Map<NodeID, NodeID> SVF::TypeBasedHeapCloning::cloneToOriginalObj

private

(Clone) object -> original object (opposite of objToclones).

Definition at line 160 of file TypeBasedHeapCloning.h.

◆ dchg

DCHGraph* SVF::TypeBasedHeapCloning::dchg = nullptr

protected

Class hierarchy graph built from debug information. Required, CHG from IR is insufficient.

Definition at line 47 of file TypeBasedHeapCloning.h.

◆ derefFnName

const std::string TypeBasedHeapCloning::derefFnName = "deref"

staticprotected

deref function for TBHC alias tests.

Definition at line 34 of file TypeBasedHeapCloning.h.

◆ locToFilterSet

Map<NodeID, PointsTo> SVF::TypeBasedHeapCloning::locToFilterSet

private

Maps nodes (a location like a PAG node or SVFG node) to their filter set.

Definition at line 162 of file TypeBasedHeapCloning.h.

◆ mangledDerefFnName

const std::string TypeBasedHeapCloning::mangledDerefFnName = "_Z5derefv"

staticprotected

deref function (mangled) for TBHC alias tests.

Definition at line 36 of file TypeBasedHeapCloning.h.

◆ memObjToGeps

Map<const MemObj *, Map<unsigned, NodeBS> > SVF::TypeBasedHeapCloning::memObjToGeps

private

Maps memory objects to their GEP objects. (memobj -> (fieldidx -> geps))

Definition at line 166 of file TypeBasedHeapCloning.h.

◆ numAgg

unsigned SVF::TypeBasedHeapCloning::numAgg = 0

private

Definition at line 177 of file TypeBasedHeapCloning.h.

◆ numInit

unsigned SVF::TypeBasedHeapCloning::numInit = 0

private

Definition at line 172 of file TypeBasedHeapCloning.h.

◆ numReuse

unsigned SVF::TypeBasedHeapCloning::numReuse = 0

private

Definition at line 176 of file TypeBasedHeapCloning.h.

◆ numSGAgg

unsigned SVF::TypeBasedHeapCloning::numSGAgg = 0

private

Definition at line 185 of file TypeBasedHeapCloning.h.

◆ numSGInit

unsigned SVF::TypeBasedHeapCloning::numSGInit = 0

private

Definition at line 180 of file TypeBasedHeapCloning.h.

◆ numSGReuse

unsigned SVF::TypeBasedHeapCloning::numSGReuse = 0

private

Definition at line 184 of file TypeBasedHeapCloning.h.

◆ numSGTBSSU

unsigned SVF::TypeBasedHeapCloning::numSGTBSSU = 0

private

Definition at line 182 of file TypeBasedHeapCloning.h.

◆ numSGTBSU

unsigned SVF::TypeBasedHeapCloning::numSGTBSU = 0

private

Definition at line 183 of file TypeBasedHeapCloning.h.

◆ numSGTBWU

unsigned SVF::TypeBasedHeapCloning::numSGTBWU = 0

private

Definition at line 181 of file TypeBasedHeapCloning.h.

◆ numTBSSU

unsigned SVF::TypeBasedHeapCloning::numTBSSU = 0

private

Definition at line 174 of file TypeBasedHeapCloning.h.

◆ numTBSU

unsigned SVF::TypeBasedHeapCloning::numTBSU = 0

private

Definition at line 175 of file TypeBasedHeapCloning.h.

◆ numTBWU

unsigned SVF::TypeBasedHeapCloning::numTBWU = 0

private

Definition at line 173 of file TypeBasedHeapCloning.h.

◆ objToAllocation

Map<NodeID, NodeID> SVF::TypeBasedHeapCloning::objToAllocation

private

Object -> allocation site. The value NodeID depends on the pointer analysis (could be an SVFG node or PAG node for example).

Definition at line 156 of file TypeBasedHeapCloning.h.

◆ objToClones

Map<NodeID, NodeBS> SVF::TypeBasedHeapCloning::objToClones

private

(Original) object -> set of its clones.

Definition at line 158 of file TypeBasedHeapCloning.h.

◆ objToGeps

Map<NodeID, NodeBS> SVF::TypeBasedHeapCloning::objToGeps

private

Maps objects to the GEP nodes beneath them.

Definition at line 164 of file TypeBasedHeapCloning.h.

◆ objToType

Map<NodeID, const DIType *> SVF::TypeBasedHeapCloning::objToType

private

Object -> its type.

Definition at line 152 of file TypeBasedHeapCloning.h.

◆ ppag

PAG* SVF::TypeBasedHeapCloning::ppag = nullptr

private

PAG the PTA uses. Just a shortcut for getPAG().

Definition at line 149 of file TypeBasedHeapCloning.h.

◆ pta

BVDataPTAImpl* SVF::TypeBasedHeapCloning::pta

private

PTA extending this class.

Definition at line 147 of file TypeBasedHeapCloning.h.

◆ undefType

const DIType * TypeBasedHeapCloning::undefType = nullptr

staticprotected

The undefined type (•); void.

Definition at line 27 of file TypeBasedHeapCloning.h.

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

/home/runner/work/SVF-1/SVF-1/include/Util/TypeBasedHeapCloning.h
/home/runner/work/SVF-1/SVF-1/lib/Util/TypeBasedHeapCloning.cpp

Public Member Functions

Static Public Member Functions

Protected Member Functions

Protected Attributes

Static Protected Attributes

Private Member Functions

Private Attributes

Detailed Description

Constructor & Destructor Documentation

◆ ~TypeBasedHeapCloning()

◆ TypeBasedHeapCloning()

Member Function Documentation

◆ addClone()

◆ addCloneDummyObjNode()

◆ addCloneFIObjNode()

◆ addCloneGepObjNode()

◆ addGepToObj()

◆ backPropagate()

◆ cloneObject()

◆ dumpStats()

◆ getAllocationSite()

◆ getClones()

◆ getFilterSet()

◆ getGepObjClones()

◆ getGepObjs()

◆ getGepObjsFromMemObj()

◆ getObjsWithClones()

◆ getOriginalObj()

◆ getRawCTirMetadata()

◆ getType()

◆ getTypeFromCTirMetadata()

◆ init()

◆ isBase()

◆ isBlkObjOrConstantObj()

◆ isClone()

◆ isGep()

◆ setAllocationSite()

◆ setDCHG()

◆ setOriginalObj()

◆ setPAG()

◆ setType()

◆ validateTBHCTests()

Member Data Documentation

◆ cloneToOriginalObj

◆ dchg

◆ derefFnName

◆ locToFilterSet

◆ mangledDerefFnName

◆ memObjToGeps

◆ numAgg

◆ numInit

◆ numReuse

◆ numSGAgg

◆ numSGInit

◆ numSGReuse

◆ numSGTBSSU

◆ numSGTBSU

◆ numSGTBWU

◆ numTBSSU

◆ numTBSU

◆ numTBWU

◆ objToAllocation

◆ objToClones

◆ objToGeps

◆ objToType

◆ ppag

◆ pta

◆ undefType