SVF::AccessPath Class Reference

#include <AccessPath.h>

Public Types
enum	LSRelation {   NonOverlap , Overlap , Subset , Superset ,   Same }
typedef std::pair< const ValVar *, const SVFType * >	IdxOperandPair
typedef std::vector< IdxOperandPair >	IdxOperandPairs

Public Member Functions
	AccessPath (APOffset o=0, const SVFType *srcTy=nullptr)
	Constructor.
	AccessPath (const AccessPath &ap)
	Copy Constructor.
	~AccessPath ()
AccessPath	operator+ (const AccessPath &rhs) const
	Overload operators.
bool	operator< (const AccessPath &rhs) const
const AccessPath &	operator= (const AccessPath &rhs)
bool	operator== (const AccessPath &rhs) const
APOffset	getConstantStructFldIdx () const
	Get methods.
void	setFldIdx (APOffset idx)
const IdxOperandPairs &	getIdxOperandPairVec () const
const SVFType *	gepSrcPointeeType () const
APOffset	computeConstantByteOffset () const
APOffset	computeConstantOffset () const
	For example,.
u32_t	getElementNum (const SVFType *type) const
	Return element number of a type.
bool	addOffsetVarAndGepTypePair (const ValVar *var, const SVFType *gepIterType)
bool	isConstantOffset () const
	Return TRUE if this is a constant location set.
bool	intersects (const AccessPath &RHS) const
	Return TRUE if we share any location in common with RHS.
u32_t	getStructFieldOffset (const ValVar *idxOperandVar, const SVFStructType *idxOperandType) const
	Return byte offset from the beginning of the structure to the field where it is located for struct type.
std::string	dump () const
	Dump location set.

Protected Member Functions
void	addIdxOperandPair (std::pair< const ValVar *, const SVFType * > pair)

Private Member Functions
LSRelation	checkRelation (const AccessPath &LHS, const AccessPath &RHS)
	Check relations of two location sets.
NodeBS	computeAllLocations () const
	Compute all possible locations according to offset and number-stride pairs.

Private Attributes
APOffset	fldIdx
	Accumulated Constant Offsets.
IdxOperandPairs	idxOperandPairs
	a vector of actual offset in the form of <SVF Var, iterator type>
const SVFType *	gepPointeeType

Friends
class	GraphDBClient

Detailed Description

Definition at line 57 of file AccessPath.h.

Member Typedef Documentation

IdxOperandPair

typedef std::pair<const ValVar*, const SVFType*> SVF::AccessPath::IdxOperandPair

Definition at line 66 of file AccessPath.h.

IdxOperandPairs

typedef std::vector<IdxOperandPair> SVF::AccessPath::IdxOperandPairs

Definition at line 67 of file AccessPath.h.

Member Enumeration Documentation

LSRelation

enum SVF::AccessPath::LSRelation

Enumerator
NonOverlap
Overlap
Subset
Superset
Same

Definition at line 61 of file AccessPath.h.

    {
        NonOverlap, Overlap, Subset, Superset, Same
    };

Constructor & Destructor Documentation

AccessPath() [1/2]

SVF::AccessPath::AccessPath ( APOffset  o = 0, const SVFType *  srcTy = nullptr  )

inline

Constructor.

Definition at line 70 of file AccessPath.h.

: fldIdx(o), gepPointeeType(srcTy) {}

AccessPath() [2/2]

SVF::AccessPath::AccessPath ( const AccessPath &  ap )

inline

Copy Constructor.

Definition at line 73 of file AccessPath.h.

        : fldIdx(ap.fldIdx),
          idxOperandPairs(ap.getIdxOperandPairVec()),
          gepPointeeType(ap.gepSrcPointeeType())
    {
    }

~AccessPath()

SVF::AccessPath::~AccessPath ( )

inline

Definition at line 80 of file AccessPath.h.

{}

Member Function Documentation

addIdxOperandPair()

void SVF::AccessPath::addIdxOperandPair ( std::pair< const ValVar *, const SVFType * >  pair )

inlineprotected

Definition at line 170 of file AccessPath.h.

    {
        idxOperandPairs.push_back(pair);
    }

addOffsetVarAndGepTypePair()

bool AccessPath::addOffsetVarAndGepTypePair	(	const ValVar *	var,
		const SVFType *	gepIterType
	)

Add offset value to vector offsetVarAndGepTypePairs

Definition at line 44 of file AccessPath.cpp.

{
    idxOperandPairs.emplace_back(var, gepIterType);
    return true;
}

checkRelation()

SVF::AccessPath::LSRelation AccessPath::checkRelation ( const AccessPath &  LHS, const AccessPath &  RHS  )

private

Check relations of two location sets.

Definition at line 312 of file AccessPath.cpp.

{
    NodeBS lhsLocations = LHS.computeAllLocations();
    NodeBS rhsLocations = RHS.computeAllLocations();
    if (lhsLocations.intersects(rhsLocations))
    {
        if (lhsLocations == rhsLocations)
            return Same;
        else if (lhsLocations.contains(rhsLocations))
            return Superset;
        else if (rhsLocations.contains(lhsLocations))
            return Subset;
        else
            return Overlap;
    }
    else
    {
        return NonOverlap;
    }
}

computeAllLocations()

NodeBS AccessPath::computeAllLocations ( ) const

private

Compute all possible locations according to offset and number-stride pairs.

Compute all possible locations according to offset and number-stride pairs.

Definition at line 270 of file AccessPath.cpp.

{
    NodeBS result;
    result.set(getConstantStructFldIdx());
    return result;
}

computeConstantByteOffset()

APOffset AccessPath::computeConstantByteOffset

(

)

const

Computes the total constant byte offset of an access path. This function iterates over the offset-variable-type pairs in reverse order, accumulating the total byte offset for constant offsets. For each pair, it retrieves the corresponding SVFValue and determines the type of offset (whether it's an array, pointer, or structure). If the offset corresponds to a structure, it further resolves the actual element type based on the offset value. It then multiplies the offset value by the size of the type to compute the byte offset. This is used to handle composite types where offsets are derived from the type's internal structure, such as arrays or structures with fields of various types and sizes. The function asserts that the access path must have a constant offset, and it is intended to be used when the offset is known to be constant at compile time.

Returns

APOffset representing the computed total constant byte offset. e.g. GepStmt* gep = [i32*4], 2 APOffset byteOffset = gep->accumulateConstantByteOffset(); byteOffset should be 8 since i32 is 4 bytes and index is 2.

Return accumulated constant offset

"value" is the offset variable (must be a constant) "type" is the location where we want to compute offset Given a vector and elem byte size: [(value1,type1), (value2,type2), (value3,type3)], bytesize totalConstByteOffset = ByteOffset(value1,type1) * ByteOffset(value2,type2) + ByteOffset(value3,type3) For a pointer type (e.g., t1 is PointerType), we will retrieve the pointee type and times the offset, i.e., getElementNum(t1) X off1

For example, there is struct DEST{int a, char b[10], int c[5]} (1) c = getelementptr inbounds struct.DEST, struct.DEST* arr, i32 0, i32 2

for (1) offsetVarAndGepTypePairs.size() = 2 i = 0, type: struct.DEST*, PtrType, op = 0 i = 1, type: struct.DEST, StructType, op = 2 for (2) offsetVarAndGepTypePairs.size() = 2 i = 0, type: [10 x i8]*, PtrType, op = 0 i = 1, type: [10 x i8], ArrType, op = 8

if offsetVarAndGepTypePairs[i].second is nullptr, it means GepStmt comes from external API, this GepStmt is assigned in SVFIRExtAPI.cpp at SVFIRBuilder::getBaseTypeAndFlattenedFields ls.addOffsetVarAndGepTypePair()

for (2) i = 1, arrType: [10 x i8], type2 = i8

for (1) i = 0, ptrType: struct.DEST*, type2: struct.DEST for (2) i = 0, ptrType: [10 x i8]*, type2 = [10 x i8]

for (1) structType: struct.DEST structField = 0, flattenIdx = 0, type2: int structField = 1, flattenIdx = 1, type2: char[10] structField = 2, flattenIdx = 11, type2: int[5]

for (2) i = 0, op: 0, type: [10 x i8]*(Ptr), type2: [10 x i8](Arr) i = 1, op: 8, type: [10 x i8](Arr), type2: i8

Definition at line 126 of file AccessPath.cpp.

{
    assert(isConstantOffset() && "not a constant offset");
 
    APOffset totalConstOffset = 0;
    for(int i = idxOperandPairs.size() - 1; i >= 0; i--)
    {
        //  (2) %arrayidx = getelementptr inbounds [10 x i8], [10 x i8]* %b, i64 0, i64 8
        const ValVar* var = idxOperandPairs[i].first;
        const SVFType* type = idxOperandPairs[i].second;
        assert(type && "this GepStmt comes from ExternalAPI cannot call this api");
        const SVFType* type2 = type;
        if (const SVFArrayType* arrType = SVFUtil::dyn_cast<SVFArrayType>(type))
        {
            type2 = arrType->getTypeOfElement();
        }
        else if (SVFUtil::isa<SVFPointerType>(type))
        {
            type2 = gepSrcPointeeType();
        }
 
        const ConstIntValVar* op = SVFUtil::dyn_cast<ConstIntValVar>(var);
        if (const SVFStructType* structType = SVFUtil::dyn_cast<SVFStructType>(type))
        {
            for (u32_t structField = 0; structField < (u32_t)op->getSExtValue(); ++structField)
            {
                u32_t flattenIdx = structType->getTypeInfo()->getFlattenedFieldIdxVec()[structField];
                type2 = structType->getTypeInfo()->getOriginalElemType(flattenIdx);
                totalConstOffset += type2->getByteSize();
            }
        }
        else
        {
            totalConstOffset += op->getSExtValue() * type2->getByteSize();
        }
    }
    totalConstOffset = Options::MaxFieldLimit() > totalConstOffset? totalConstOffset: Options::MaxFieldLimit();
    return totalConstOffset;
}

computeConstantOffset()

APOffset AccessPath::computeConstantOffset

(

)

const

For example,.

Return accumulated constant offset given OffsetVarVec compard to computeConstantByteOffset, it is field offset rather than byte offset e.g. GepStmt* gep = [i32*4], 2 APOffset byteOffset = gep->computeConstantOffset(); byteOffset should be 2 since it is field offset.

Return accumulated constant offset

"value" is the offset variable (must be a constant) "type" is the location where we want to compute offset Given a vector: [(value1,type1), (value2,type2), (value3,type3)] totalConstOffset = flattenOffset(value1,type1) * flattenOffset(value2,type2) + flattenOffset(value3,type3) For a pointer type (e.g., t1 is PointerType), we will retrieve the pointee type and times the offset, i.e., getElementNum(t1) X off1 %5 = getelementptr inbounds struct.Student, struct.Student* %4, i64 1 value1: i64 1 type1: struct.Student* computeConstantOffset = 32 %6 = getelementptr inbounds struct.Student, struct.Student* %5, i32 0, i32 1 value1: i32 0 type1: struct.Student* value2: i32 1 type2: struct.Student = type { struct.inner, [10 x [3 x i8]] } computeConstantOffset = 2 %7 = getelementptr inbounds [10 x [3 x i8]], [10 x [3 x i8]]* %6, i64 0, i64 3 value1: i64 0 type1: [10 x [3 x i8]]* value2: i64 3 type2: [10 x [3 x i8]] computeConstantOffset = 9 %8 = getelementptr inbounds [3 x i8], [3 x i8]* %7, i64 0, i64 2 value1: i64 0 type1: [3 x i8]* value2: i64 2 type2: [3 x i8] computeConstantOffset = 2

Definition at line 214 of file AccessPath.cpp.

{
 
    assert(isConstantOffset() && "not a constant offset");
 
    APOffset totalConstOffset = 0;
    //After the model-const and model-array options are turned on,
    // the gepstmt offset generated by the array on the global
    // node will be saved in getConstantStructFldIdx
    if (idxOperandPairs.size() == 0)
        return getConstantStructFldIdx();
    for(int i = idxOperandPairs.size() - 1; i >= 0; i--)
    {
        const ValVar* var = idxOperandPairs[i].first;
        const SVFType* type = idxOperandPairs[i].second;
        assert(SVFUtil::isa<ConstIntValVar>(var) && "not a constant offset?");
        s64_t constOffset = SVFUtil::dyn_cast<ConstIntValVar>(var)->getSExtValue();
 
        if(type==nullptr)
        {
            totalConstOffset += constOffset;
            continue;
        }
 
        if(SVFUtil::isa<SVFPointerType>(type))
            totalConstOffset += constOffset * getElementNum(gepPointeeType);
        else
        {
            APOffset offset = constOffset;
            if (offset >= 0)
            {
                const std::vector<u32_t>& so = PAG::getPAG()->getTypeInfo(type)->getFlattenedElemIdxVec();
                // if offset is larger than the size of getFlattenedElemIdxVec (overflow)
                // set offset the last index of getFlattenedElemIdxVec to avoid assertion
                if (offset >= (APOffset)so.size())
                {
                    SVFUtil::errs() << "It is an overflow access, hence it is the last idx\n";
                    offset = so.size() - 1;
                }
                else
                {
 
                }
 
                u32_t flattenOffset =
                    PAG::getPAG()->getFlattenedElemIdx(type,
                                                       offset);
                totalConstOffset += flattenOffset;
            }
        }
    }
    return totalConstOffset;
}

dump()

std::string AccessPath::dump

(

)

const

Dump location set.

Definition at line 334 of file AccessPath.cpp.

{
    std::string str;
    std::stringstream rawstr(str);
 
    rawstr << "AccessPath\tField_Index: " << getConstantStructFldIdx();
    rawstr << ",\tNum-Stride: {";
    const IdxOperandPairs& vec = getIdxOperandPairVec();
    IdxOperandPairs::const_iterator it = vec.begin();
    IdxOperandPairs::const_iterator eit = vec.end();
    for (; it != eit; ++it)
    {
        const SVFType* ty = it->second;
        rawstr << " (Svf var: " << it->first->toString() << ", Iter type: " << *ty << ")";
    }
    rawstr << " }\n";
    return rawstr.str();
}

gepSrcPointeeType()

const SVFType * SVF::AccessPath::gepSrcPointeeType ( ) const

inline

Definition at line 114 of file AccessPath.h.

    {
        return gepPointeeType;
    }

getConstantStructFldIdx()

APOffset SVF::AccessPath::getConstantStructFldIdx ( ) const

inline

Get methods.

Definition at line 102 of file AccessPath.h.

    {
        return fldIdx;
    }

getElementNum()

u32_t AccessPath::getElementNum

(

const SVFType *

type

)

const

Return element number of a type.

Return element number of a type (1) StructType or Array, return flattened number elements. (2) Pointer type, return max field limit (3) Non-pointer SingleValueType or Function Type, return 1

Definition at line 65 of file AccessPath.cpp.

{
    if (SVFUtil::isa<SVFArrayType, SVFStructType>(type))
    {
        return PAG::getPAG()->getNumOfFlattenElements(type);
    }
    else if (type->isPointerTy())
    {
        // if type is a pointer, should be like:
        // %2 = getelementptr inbounds i32*, i32** %1, ...
        // where gepSrcPointee is of pointer type (i32*).
        // this can be transformed to:
        // %2 = getelementptr inbounds [N x i32], [N x i32]* %1, ...
        // However, we do not know N without context information. int** implies non-contiguous blocks of memory
        // In this case, we conservatively return max field limit
        return Options::MaxFieldLimit();
    }
    else if (type->isSingleValueType() || SVFUtil::isa<SVFFunctionType>(type))
    {
        return 1;
    }
    else
    {
        SVFUtil::outs() << "GepIter Type" << *type << "\n";
        assert(false && "What other types for this gep?");
        abort();
    }
}

getIdxOperandPairVec()

const IdxOperandPairs & SVF::AccessPath::getIdxOperandPairVec ( ) const

inline

Definition at line 110 of file AccessPath.h.

    {
        return idxOperandPairs;
    }

getStructFieldOffset()

u32_t AccessPath::getStructFieldOffset	(	const ValVar *	idxOperandVar,
		const SVFStructType *	idxOperandType
	)		const

Return byte offset from the beginning of the structure to the field where it is located for struct type.

Return byte offset from the beginning of the structure to the field where it is located for struct type

Definition at line 100 of file AccessPath.cpp.

{
    u32_t structByteOffset = 0;
    if (const ConstIntValVar*op = SVFUtil::dyn_cast<ConstIntValVar>(idxOperandVar))
    {
        for (u32_t structField = 0; structField < (u32_t) op->getSExtValue(); ++structField)
        {
            u32_t flattenIdx = idxOperandType->getTypeInfo()->getFlattenedFieldIdxVec()[structField];
            structByteOffset += idxOperandType->getTypeInfo()->getOriginalElemType(flattenIdx)->getByteSize();
        }
        return structByteOffset;
    }
    else
    {
        assert(false && "struct type can only pair with constant idx");
        abort();
    }
}

intersects()

bool SVF::AccessPath::intersects ( const AccessPath &  RHS ) const

inline

Return TRUE if we share any location in common with RHS.

Definition at line 158 of file AccessPath.h.

    {
        return computeAllLocations().intersects(RHS.computeAllLocations());
    }

isConstantOffset()

bool AccessPath::isConstantOffset

(

)

const

Return TRUE if this is a constant location set.

Return true if all offset values are constants.

Definition at line 51 of file AccessPath.cpp.

{
    for(auto it : idxOperandPairs)
    {
        if(SVFUtil::isa<ConstIntValVar>(it.first) == false)
            return false;
    }
    return true;
}

operator+()

AccessPath AccessPath::operator+

(

const AccessPath &

rhs

)

const

Overload operators.

Definition at line 277 of file AccessPath.cpp.

{
    assert(gepPointeeType == rhs.gepSrcPointeeType() && "source element type not match");
    AccessPath ap(rhs);
    ap.fldIdx += getConstantStructFldIdx();
    for (auto &p : ap.getIdxOperandPairVec())
        ap.addOffsetVarAndGepTypePair(p.first, p.second);
 
    return ap;
}

operator<()

bool AccessPath::operator<

(

const AccessPath &

rhs

)

const

Definition at line 288 of file AccessPath.cpp.

{
    if (fldIdx != rhs.fldIdx)
        return (fldIdx < rhs.fldIdx);
    else
    {
        const IdxOperandPairs& pairVec = getIdxOperandPairVec();
        const IdxOperandPairs& rhsPairVec = rhs.getIdxOperandPairVec();
        if (pairVec.size() != rhsPairVec.size())
            return (pairVec.size() < rhsPairVec.size());
        else
        {
            IdxOperandPairs::const_iterator it = pairVec.begin();
            IdxOperandPairs::const_iterator rhsIt = rhsPairVec.begin();
            for (; it != pairVec.end() && rhsIt != rhsPairVec.end(); ++it, ++rhsIt)
            {
                return (*it) < (*rhsIt);
            }
 
            return false;
        }
    }
}

operator=()

const AccessPath & SVF::AccessPath::operator= ( const AccessPath &  rhs )

inline

Definition at line 86 of file AccessPath.h.

    {
        fldIdx = rhs.fldIdx;
        idxOperandPairs = rhs.getIdxOperandPairVec();
        gepPointeeType = rhs.gepPointeeType;
        return *this;
    }

operator==()

bool SVF::AccessPath::operator== ( const AccessPath &  rhs ) const

inline

Definition at line 93 of file AccessPath.h.

    {
        return this->fldIdx == rhs.fldIdx &&
               this->idxOperandPairs == rhs.idxOperandPairs && this->gepPointeeType == rhs.gepPointeeType;
    }

setFldIdx()

void SVF::AccessPath::setFldIdx ( APOffset  idx )

inline

Definition at line 106 of file AccessPath.h.

    {
        fldIdx = idx;
    }

Friends And Related Symbol Documentation

GraphDBClient

friend class GraphDBClient

friend

Definition at line 59 of file AccessPath.h.

Member Data Documentation

fldIdx

APOffset SVF::AccessPath::fldIdx

private

Accumulated Constant Offsets.

Definition at line 183 of file AccessPath.h.

gepPointeeType

const SVFType* SVF::AccessPath::gepPointeeType

private

Definition at line 185 of file AccessPath.h.

idxOperandPairs

IdxOperandPairs SVF::AccessPath::idxOperandPairs

private

a vector of actual offset in the form of <SVF Var, iterator type>

Definition at line 184 of file AccessPath.h.

---

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

• /home/runner/work/SVF/SVF/svf/include/MemoryModel/AccessPath.h
• /home/runner/work/SVF/SVF/svf/lib/MemoryModel/AccessPath.cpp