#include <AccessPath.h>

Public Types
enum	LSRelation { NonOverlap , Overlap , Subset , Superset , Same }

typedef std::pair< const SVFVar , 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 SVFVar 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 SVFVar 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.

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	SymbolTableInfo

class	SVFIRWriter

class	SVFIRReader

Detailed Description

Definition at line 52 of file AccessPath.h.

Member Typedef Documentation

◆ IdxOperandPair

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

Definition at line 64 of file AccessPath.h.

◆ IdxOperandPairs

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

Definition at line 65 of file AccessPath.h.

Member Enumeration Documentation

◆ LSRelation

enum SVF::AccessPath::LSRelation

Enumerator
NonOverlap
Overlap
Subset
Superset
Same

Definition at line 59 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 68 of file AccessPath.h.

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

SVF::AccessPath::gepPointeeType

const SVFType * gepPointeeType

Definition AccessPath.h:177

SVF::AccessPath::fldIdx

APOffset fldIdx

Accumulated Constant Offsets.

Definition AccessPath.h:175

SVF::IRBuilder

llvm::IRBuilder IRBuilder

Definition BasicTypes.h:74

◆ AccessPath() [2/2]

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

inline

Copy Constructor.

Definition at line 71 of file AccessPath.h.

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

◆ ~AccessPath()

SVF::AccessPath::~AccessPath ( )

inline

Definition at line 78 of file AccessPath.h.

78{}

Member Function Documentation

◆ addOffsetVarAndGepTypePair()

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

Add offset value to vector offsetVarAndGepTypePairs

Definition at line 42 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 310 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.

Definition at line 268 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 124 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 SVFVar* 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 ConstantIntValVar* op = SVFUtil::dyn_cast<ConstantIntValVar>(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 212 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 SVFVar* var = idxOperandPairs[i].first;
        const SVFType* type = idxOperandPairs[i].second;
        assert(SVFUtil::isa<ConstantIntValVar>(var) && "not a constant offset?");
        s64_t constOffset = SVFUtil::dyn_cast<ConstantIntValVar>(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 = SymbolTableInfo::SymbolInfo()->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 =
                    SymbolTableInfo::SymbolInfo()->getFlattenedElemIdx(type,
                            offset);
                totalConstOffset += flattenOffset;
            }
        }
    }
    return totalConstOffset;
}

◆ dump()

std::string AccessPath::dump ( ) const

Dump location set.

Definition at line 332 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 112 of file AccessPath.h.

    {
        return gepPointeeType;
    }

◆ getConstantStructFldIdx()

APOffset SVF::AccessPath::getConstantStructFldIdx ( ) const

inline

Get methods.

Definition at line 100 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 63 of file AccessPath.cpp.

{
    if (SVFUtil::isa<SVFArrayType, SVFStructType>(type))
    {
        return SymbolTableInfo::SymbolInfo()->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 108 of file AccessPath.h.

    {
        return idxOperandPairs;
    }

◆ getStructFieldOffset()

u32_t AccessPath::getStructFieldOffset	(	const SVFVar *	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 98 of file AccessPath.cpp.

{
    u32_t structByteOffset = 0;
    if (const ConstantIntValVar *op = SVFUtil::dyn_cast<ConstantIntValVar>(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 156 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 49 of file AccessPath.cpp.

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

◆ operator+()

AccessPath AccessPath::operator+ ( const AccessPath & rhs ) const

Overload operators.

Definition at line 275 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 286 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 84 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 91 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 104 of file AccessPath.h.

    {
        fldIdx = idx;
    }

Friends And Related Symbol Documentation

◆ SVFIRReader

friend class SVFIRReader

friend

Definition at line 56 of file AccessPath.h.

◆ SVFIRWriter

friend class SVFIRWriter

friend

Definition at line 55 of file AccessPath.h.

◆ SymbolTableInfo

friend class SymbolTableInfo

friend

Definition at line 54 of file AccessPath.h.

Member Data Documentation

◆ fldIdx

APOffset SVF::AccessPath::fldIdx

private

Accumulated Constant Offsets.

Definition at line 175 of file AccessPath.h.

◆ gepPointeeType

const SVFType* SVF::AccessPath::gepPointeeType

private

Definition at line 177 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 176 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

Public Types

Public Member Functions

Private Member Functions

Private Attributes

Friends

Detailed Description

Member Typedef Documentation

◆ IdxOperandPair

◆ IdxOperandPairs

Member Enumeration Documentation

◆ LSRelation

Constructor & Destructor Documentation

◆ AccessPath() [1/2]

◆ AccessPath() [2/2]

◆ ~AccessPath()

Member Function Documentation

◆ addOffsetVarAndGepTypePair()

◆ checkRelation()

◆ computeAllLocations()

◆ computeConstantByteOffset()

◆ computeConstantOffset()

◆ dump()

◆ gepSrcPointeeType()

◆ getConstantStructFldIdx()

◆ getElementNum()

◆ getIdxOperandPairVec()

◆ getStructFieldOffset()

◆ intersects()

◆ isConstantOffset()

◆ operator+()

◆ operator<()

◆ operator=()

◆ operator==()

◆ setFldIdx()

Friends And Related Symbol Documentation

◆ SVFIRReader

◆ SVFIRWriter

◆ SymbolTableInfo

Member Data Documentation

◆ fldIdx

◆ gepPointeeType

◆ idxOperandPairs