PathCondAllocator.h

Go to the documentation of this file.

//===- PathCondAllocator.h -- Path condition manipulation---------------------//
//
//                     SVF: Static Value-Flow Analysis
//
// Copyright (C) <2013-2017>  <Yulei Sui>
//

// This program is free software: you can redistribute it and/or modify
// it under the terms of the GNU 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 General Public License for more details.

// You should have received a copy of the GNU 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 "Util/SVFModule.h"
#include "SVF-FE/DataFlowUtil.h"
#include "Util/Conditions.h"
#include "Util/WorkList.h"

namespace SVF
{

class PathCondAllocator
{

public:
    static u32_t totalCondNum;

    typedef DdNode Condition;
    typedef Map<u32_t,Condition*> CondPosMap;       
    typedef Map<const BasicBlock*, CondPosMap > BBCondMap;  // map bb to a Condition
    typedef Map<const Condition*, const Instruction* > CondToTermInstMap;   // map a condition to its branch instruction
    typedef Set<const BasicBlock*> BasicBlockSet;
    typedef Map<const Function*,  BasicBlockSet> FunToExitBBsMap;  
    typedef Map<const BasicBlock*, Condition*> BBToCondMap; 
    typedef FIFOWorkList<const BasicBlock*> CFWorkList; 

    typedef Map<u32_t,Condition*> IndexToConditionMap;

    PathCondAllocator()
    {
        getBddCondManager();
    }
    virtual ~PathCondAllocator()
    {
        destroy();
    }
    static inline Condition* trueCond()
    {
        return getBddCondManager()->getTrueCond();
    }

    static inline Condition* falseCond()
    {
        return getBddCondManager()->getFalseCond();
    }


    static inline u32_t getMemUsage()
    {
        return getBddCondManager()->getBDDMemUsage();
    }
    static inline u32_t getCondNum()
    {
        return getBddCondManager()->getCondNumber();
    }
    static inline u32_t getMaxLiveCondNumber()
    {
        return getBddCondManager()->getMaxLiveCondNumber();
    }

    void allocate(const SVFModule* module);

    inline const Instruction* getCondInst(const Condition* cond) const
    {
        CondToTermInstMap::const_iterator it = condToInstMap.find(cond);
        assert(it!=condToInstMap.end() && "this should be a fresh condition");
        return it->second;
    }

    inline DominatorTree* getDT(const Function* fun)
    {
        return cfInfoBuilder.getDT(fun);
    }
    inline PostDominatorTree* getPostDT(const Function* fun)
    {
        return cfInfoBuilder.getPostDT(fun);
    }
    inline LoopInfo* getLoopInfo(const Function* f)
    {
        return cfInfoBuilder.getLoopInfo(f);
    }


    inline Condition* condAnd(Condition* lhs, Condition* rhs)
    {
        return bddCondMgr->AND(lhs,rhs);
    }
    inline Condition* condOr(Condition* lhs, Condition* rhs)
    {
        return bddCondMgr->OR(lhs,rhs);
    }
    inline Condition* condNeg(Condition* cond)
    {
        return bddCondMgr->NEG(cond);
    }
    inline Condition* getTrueCond() const
    {
        return bddCondMgr->getTrueCond();
    }
    inline Condition* getFalseCond() const
    {
        return bddCondMgr->getFalseCond();
    }
    inline Condition* getCond(u32_t i) const
    {
        IndexToConditionMap::const_iterator it = indexToDDNodeMap.find(i);
        assert(it!=indexToDDNodeMap.end() && "condition not found!");
        return it->second;
    }
    inline NodeBS exactCondElem(Condition* cond)
    {
        NodeBS elems;
        bddCondMgr->BddSupport(cond,elems);
        return elems;
    }
    inline void markForRelease(Condition* cond)
    {
        bddCondMgr->markForRelease(cond);
    }
    inline void printDbg(Condition* cond)
    {
        bddCondMgr->printDbg(cond);
    }
    inline std::string dumpCond(Condition* cond) const
    {
        return bddCondMgr->dumpStr(cond);
    }


    virtual Condition* ComputeIntraVFGGuard(const BasicBlock* src, const BasicBlock* dst);
    virtual Condition* ComputeInterCallVFGGuard(const BasicBlock* src, const BasicBlock* dst, const BasicBlock* callBB);
    virtual Condition* ComputeInterRetVFGGuard(const BasicBlock* src, const BasicBlock* dst, const BasicBlock* retBB);

    virtual Condition* getPHIComplementCond(const BasicBlock* BB1, const BasicBlock* BB2, const BasicBlock* BB0);

    inline void clearCFCond()
    {
        bbToCondMap.clear();
    }
    inline void setCurEvalVal(const Value* val)
    {
        curEvalVal = val;
    }
    inline const Value* getCurEvalVal() const
    {
        return curEvalVal;
    }

    void printPathCond();

private:

    virtual void allocateForBB(const BasicBlock& bb);


    void setBranchCond(const BasicBlock *bb, const BasicBlock *succ, Condition* cond);
    Condition* getBranchCond(const BasicBlock * bb, const BasicBlock *succ) const;
    inline Condition* getEvalBrCond(const BasicBlock * bb, const BasicBlock *succ)
    {
        if(const Value* val = getCurEvalVal())
            return evaluateBranchCond(bb, succ, val);
        else
            return getBranchCond(bb,succ);
    }

    Condition* evaluateBranchCond(const BasicBlock * bb, const BasicBlock *succ, const Value* val) ;
    Condition* evaluateLoopExitBranch(const BasicBlock * bb, const BasicBlock *succ);
    Condition* evaluateTestNullLikeExpr(const BranchInst* brInst, const BasicBlock *succ, const Value* val);
    Condition* evaluateProgExit(const BranchInst* brInst, const BasicBlock *succ);
    void collectBBCallingProgExit(const BasicBlock& bb);
    bool isBBCallsProgExit(const BasicBlock* bb);


    bool isEQCmp(const CmpInst* cmp) const;
    bool isNECmp(const CmpInst* cmp) const;
    bool isTestNullExpr(const Value* test,const Value* val) const;
    bool isTestNotNullExpr(const Value* test,const Value* val) const;
    bool isTestContainsNullAndTheValue(const CmpInst* cmp, const Value* val) const;



    inline bool setCFCond(const BasicBlock* bb, Condition* cond)
    {
        BBToCondMap::iterator it = bbToCondMap.find(bb);
        if(it!=bbToCondMap.end() && it->second == cond)
            return false;

        bbToCondMap[bb] = cond;
        return true;
    }
    inline Condition* getCFCond(const BasicBlock* bb) const
    {
        BBToCondMap::const_iterator it = bbToCondMap.find(bb);
        if(it==bbToCondMap.end())
        {
            return getFalseCond();
        }
        return it->second;
    }

    inline Condition* createNewCond(u32_t i)
    {
        assert(indexToDDNodeMap.find(i)==indexToDDNodeMap.end() && "This should be fresh index to create new BDD");
        Condition* d = bddCondMgr->Cudd_bdd(i);
        indexToDDNodeMap[i] = d;
        return d;
    }
    inline Condition* newCond(const Instruction* inst)
    {
        Condition* cond = createNewCond(totalCondNum++);
        assert(condToInstMap.find(cond)==condToInstMap.end() && "this should be a fresh condition");
        condToInstMap[cond] = inst;
        return cond;
    }

    static BddCondManager* getBddCondManager()
    {
        if(bddCondMgr==nullptr)
            bddCondMgr = new BddCondManager();
        return bddCondMgr;
    }

    void destroy();

    CondToTermInstMap condToInstMap;        
    PTACFInfoBuilder cfInfoBuilder;         
    FunToExitBBsMap funToExitBBsMap;        
    BBToCondMap bbToCondMap;                
    const Value* curEvalVal;            

protected:
    static BddCondManager* bddCondMgr;      
    BBCondMap bbConds;                      
    IndexToConditionMap indexToDDNodeMap;

};

} // End namespace SVF

#endif /* PATHALLOCATOR_H_ */