SaberCondAllocator.h

Go to the documentation of this file.

//===- SaberCondAllocator.h -- Path condition manipulation---------------------//
//
//                     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/>.
//
//===----------------------------------------------------------------------===//
 
/*
 * PathAllocator.h
 *
 *  Created on: Apr 3, 2014
 *      Author: Yulei Sui
 */
 
#ifndef PATHALLOCATOR_H_
#define PATHALLOCATOR_H_
 
#include "SVFIR/SVFModule.h"
#include "SVFIR/SVFValue.h"
#include "Util/WorkList.h"
#include "Graphs/SVFG.h"
#include "Util/Z3Expr.h"
 
 
namespace SVF
{
 
class SaberCondAllocator
{
 
public:
 
    typedef Z3Expr Condition;   
    typedef Map<u32_t, const ICFGNode*> IndexToTermInstMap; 
    typedef Map<u32_t,Condition> CondPosMap;        
    typedef Map<const SVFBasicBlock*, CondPosMap > BBCondMap;   
    typedef Set<const SVFBasicBlock*> BasicBlockSet;
    typedef Map<const SVFFunction*,  BasicBlockSet> FunToExitBBsMap;  
    typedef Map<const SVFBasicBlock*, Condition> BBToCondMap;   
    typedef FIFOWorkList<const SVFBasicBlock*> CFWorkList;  
    typedef Map<const SVFGNode*, Set<const SVFGNode*>> SVFGNodeToSVFGNodeSetMap;
 
 
    SaberCondAllocator();
 
    virtual ~SaberCondAllocator()
    {
    }
 
    inline std::string getMemUsage()
    {
        u32_t vmrss, vmsize;
        if (SVFUtil::getMemoryUsageKB(&vmrss, &vmsize))
            return std::to_string(vmsize) + "KB";
        else
            return "cannot read memory usage";
    }
    inline u32_t getCondNum()
    {
        return totalCondNum;
    }
 
 
    inline Condition condAnd(const Condition& lhs, const Condition& rhs)
    {
        return Condition::AND(lhs,rhs);
    }
    inline Condition condOr(const Condition& lhs, const Condition& rhs)
    {
        return Condition::OR(lhs,rhs);
    }
    inline Condition condNeg(const Condition& cond)
    {
        return Condition::NEG(cond);
    }
    inline Condition getTrueCond() const
    {
        return Condition::getTrueCond();
    }
    inline Condition getFalseCond() const
    {
        return Condition::getFalseCond();
    }
    inline NodeBS exactCondElem(const Condition& cond)
    {
        NodeBS elems;
        extractSubConds(cond, elems);
        return elems;
    }
 
    inline std::string dumpCond(const Condition& cond) const
    {
        return Condition::dumpStr(cond);
    }
 
    Condition newCond(const ICFGNode* inst);
 
    void allocate(const SVFModule* module);
 
    //{@
    inline const ICFGNode* getCondInst(u32_t id) const
    {
        IndexToTermInstMap::const_iterator it = idToTermInstMap.find(id);
        assert(it != idToTermInstMap.end() && "this should be a fresh condition");
        return it->second;
    }
 
    inline void setCondInst(const Condition &condition, const ICFGNode* inst)
    {
        assert(idToTermInstMap.find(condition.id()) == idToTermInstMap.end() && "this should be a fresh condition");
        idToTermInstMap[condition.id()] = inst;
    }
 
    bool isNegCond(u32_t id) const
    {
        return negConds.test(id);
    }
 
    inline bool postDominate(const SVFBasicBlock* bbKey, const SVFBasicBlock* bbValue) const
    {
        const SVFFunction*  keyFunc = bbKey->getParent();
        const SVFFunction*  valueFunc = bbValue->getParent();
        bool funcEq = (keyFunc == valueFunc);
        (void)funcEq; // Suppress warning of unused variable under release build
        assert(funcEq && "two basicblocks should be in the same function!");
        return keyFunc->postDominate(bbKey,bbValue);
    }
 
    inline bool dominate(const SVFBasicBlock* bbKey, const SVFBasicBlock* bbValue) const
    {
        const SVFFunction*  keyFunc = bbKey->getParent();
        const SVFFunction*  valueFunc = bbValue->getParent();
        bool funcEq = (keyFunc == valueFunc);
        (void)funcEq; // Suppress warning of unused variable under release build
        assert(funcEq && "two basicblocks should be in the same function!");
        return keyFunc->dominate(bbKey,bbValue);
    }
 
 
    virtual Condition ComputeIntraVFGGuard(const SVFBasicBlock* src, const SVFBasicBlock* dst);
    virtual Condition ComputeInterCallVFGGuard(const SVFBasicBlock* src, const SVFBasicBlock* dst, const SVFBasicBlock* callBB);
    virtual Condition ComputeInterRetVFGGuard(const SVFBasicBlock* src, const SVFBasicBlock* dst, const SVFBasicBlock* retBB);
 
    virtual Condition getPHIComplementCond(const SVFBasicBlock* BB1, const SVFBasicBlock* BB2, const SVFBasicBlock* BB0);
 
    inline void clearCFCond()
    {
        bbToCondMap.clear();
    }
    inline void setCurEvalSVFGNode(const SVFGNode* node)
    {
        curEvalSVFGNode = node;
    }
    inline const SVFGNode* getCurEvalSVFGNode() const
    {
        return curEvalSVFGNode;
    }
 
    void printPathCond();
 
    bool isSatisfiable(const Condition& condition);
 
    inline bool isAllPathReachable(Condition& condition)
    {
        return isEquivalentBranchCond(condition, Condition::getTrueCond());
    }
 
    bool isEquivalentBranchCond(const Condition &lhs, const Condition &rhs) const;
 
    inline ICFG* getICFG() const
    {
        return PAG::getPAG()->getICFG();
    }
 
 
    inline bool setCFCond(const SVFBasicBlock* bb, const Condition& cond)
    {
        BBToCondMap::iterator it = bbToCondMap.find(bb);
        // until a fixed-point is reached (condition is not changed)
        if(it!=bbToCondMap.end() && isEquivalentBranchCond(it->second, cond))
            return false;
 
        bbToCondMap[bb] = cond;
        return true;
    }
    inline Condition getCFCond(const SVFBasicBlock* bb) const
    {
        BBToCondMap::const_iterator it = bbToCondMap.find(bb);
        if(it==bbToCondMap.end())
        {
            return getFalseCond();
        }
        return it->second;
    }
 
 
    inline void setNegCondInst(const Condition &condition, const ICFGNode* inst)
    {
        setCondInst(condition, inst);
        negConds.set(condition.id());
    }
 
    SVFGNodeToSVFGNodeSetMap & getRemovedSUVFEdges()
    {
        return removedSUVFEdges;
    }
 
private:
 
    virtual void allocateForBB(const SVFBasicBlock& bb);
 
 
    void setBranchCond(const SVFBasicBlock* bb, const SVFBasicBlock* succ, const Condition& cond);
    Condition getBranchCond(const SVFBasicBlock*  bb, const SVFBasicBlock* succ) const;
    Condition getEvalBrCond(const SVFBasicBlock*  bb, const SVFBasicBlock* succ);
 
    Condition evaluateBranchCond(const SVFBasicBlock*  bb, const SVFBasicBlock* succ) ;
    Condition evaluateLoopExitBranch(const SVFBasicBlock*  bb, const SVFBasicBlock* succ);
    Condition evaluateTestNullLikeExpr(const BranchStmt* branchStmt, const SVFBasicBlock* succ);
    Condition evaluateProgExit(const BranchStmt* branchStmt, const SVFBasicBlock* succ);
    void collectBBCallingProgExit(const SVFBasicBlock& bb);
    bool isBBCallsProgExit(const SVFBasicBlock* bb);
 
 
    bool isEQCmp(const CmpStmt* cmp) const;
    bool isNECmp(const CmpStmt* cmp) const;
    bool isTestNullExpr(const ICFGNode* test) const;
    bool isTestNotNullExpr(const ICFGNode* test) const;
    bool isTestContainsNullAndTheValue(const CmpStmt* cmp) const;
 
    void destroy()
    {
 
    }
 
    void extractSubConds(const Condition &condition, NodeBS &support) const;
 
 
    FunToExitBBsMap funToExitBBsMap;        
    BBToCondMap bbToCondMap;                
    const SVFGNode* curEvalSVFGNode{};          
    IndexToTermInstMap idToTermInstMap;     
    NodeBS negConds;                        
    std::vector<Condition> conditionVec;          
    static u32_t totalCondNum; 
    SVFGNodeToSVFGNodeSetMap removedSUVFEdges;
 
protected:
    BBCondMap bbConds;                      
 
};
 
} // End namespace SVF
 
#endif /* PATHALLOCATOR_H_ */