AccessPath.cpp

Go to the documentation of this file.

//===- AccessPath.cpp -- Location set for modeling abstract memory object----//
//
//                     SVF: Static Value-Flow Analysis
//
// Copyright (C) <2013->  <Yulei Sui>
//
 
// This program is free software: you can redistribute it and/or modify
// it under the terms of the GNU Affero General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
 
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU Affero General Public License for more details.
 
// You should have received a copy of the GNU Affero General Public License
// along with this program.  If not, see <http://www.gnu.org/licenses/>.
//
//===----------------------------------------------------------------------===//
 
/*
 * @file: AccessPath.cpp
 * @author: yesen
 * @date: 26 Sep 2014
 *
 * LICENSE
 *
 */
 
#include "Util/Options.h"
#include "MemoryModel/AccessPath.h"
#include "Util/SVFUtil.h"
 
using namespace SVF;
using namespace SVFUtil;
 
bool AccessPath::addOffsetVarAndGepTypePair(const SVFVar* var, const SVFType* gepIterType)
{
    idxOperandPairs.emplace_back(var, gepIterType);
    return true;
}
 
bool AccessPath::isConstantOffset() const
{
    for(auto it : idxOperandPairs)
    {
        if(SVFUtil::isa<ConstIntValVar>(it.first) == false)
            return false;
    }
    return true;
}
 
u32_t AccessPath::getElementNum(const SVFType* type) const
{
    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();
    }
}
 
 
// e.g. idxOperandVar: i32 2  idxOperandType: %struct.Student = type { i32, [i8 x 12], i32 }
//  we accumulate field 0 (i32) byte size (4 Bytes), and field 1 ([i8x12]) byte size (12 Bytes)
//  then the return byte offset is 16 Bytes.
u32_t AccessPath::getStructFieldOffset(const SVFVar* idxOperandVar, const SVFStructType* idxOperandType) const
{
    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();
    }
}
 
APOffset AccessPath::computeConstantByteOffset() const
{
    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 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;
}
 
 
// struct inner{ int rollNumber; float percentage;};
// struct Student { struct inner rollNumber; char studentName[10][3];}
// char x = studentRecord[1].studentName[3][2];
 
APOffset AccessPath::computeConstantOffset() const
{
 
    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<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;
}
NodeBS AccessPath::computeAllLocations() const
{
    NodeBS result;
    result.set(getConstantStructFldIdx());
    return result;
}
 
AccessPath AccessPath::operator+(const AccessPath& rhs) const
{
    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;
}
 
bool AccessPath::operator< (const AccessPath& rhs) const
{
    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;
        }
    }
}
 
SVF::AccessPath::LSRelation AccessPath::checkRelation(const AccessPath& LHS, const AccessPath& RHS)
{
    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;
    }
}
 
std::string AccessPath::dump() const
{
    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();
}