SVF::PathCondAllocator Class Reference

#include <PathCondAllocator.h>

Public Types
typedef DdNode	Condition
typedef Map< u32_t, Condition * >	CondPosMap
	map a branch to its Condition More...
typedef Map< const BasicBlock *, CondPosMap >	BBCondMap
typedef Map< const Condition *, const Instruction *>	CondToTermInstMap
typedef Set< const BasicBlock * >	BasicBlockSet
typedef Map< const Function *, BasicBlockSet >	FunToExitBBsMap
	map a function to all its basic blocks calling program exit More...
typedef Map< const BasicBlock *, Condition * >	BBToCondMap
	map a basic block to its condition during control-flow guard computation More...
typedef FIFOWorkList< const BasicBlock * >	CFWorkList
	worklist for control-flow guard computation More...
typedef Map< u32_t, Condition * >	IndexToConditionMap

Public Member Functions
	PathCondAllocator ()
	Constructor. More...
virtual	~PathCondAllocator ()
	Destructor. More...
void	allocate (const SVFModule *module)
	Perform path allocation. More...
const Instruction *	getCondInst (const Condition *cond) const
	Get llvm conditional expression. More...
DominatorTree *	getDT (const Function *fun)
	Get dominators. More...
PostDominatorTree *	getPostDT (const Function *fun)
	Get Postdominators. More...
LoopInfo *	getLoopInfo (const Function *f)
	Get LoopInfo. More...
void	printPathCond ()
	Print out the path condition information. More...
Condition *	condAnd (Condition *lhs, Condition *rhs)
	Condition operations. More...
Condition *	condOr (Condition *lhs, Condition *rhs)
Condition *	condNeg (Condition *cond)
Condition *	getTrueCond () const
Condition *	getFalseCond () const
Condition *	getCond (u32_t i) const
	Given an index, get its condition. More...
NodeBS	exactCondElem (Condition *cond)
	Iterator every element of the bdd. More...
void	markForRelease (Condition *cond)
	Decrease reference counting for the bdd. More...
void	printDbg (Condition *cond)
	Print debug information for this condition. More...
std::string	dumpCond (Condition *cond) const
virtual Condition *	ComputeIntraVFGGuard (const BasicBlock *src, const BasicBlock *dst)
	Guard Computation for a value-flow (between two basic blocks) More...
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)
void	clearCFCond ()
void	setCurEvalVal (const Value *val)
	Set current value for branch condition evaluation. More...
const Value *	getCurEvalVal () const
	Get current value for branch condition evaluation. More...

Static Public Member Functions
static Condition *	trueCond ()
static Condition *	falseCond ()
static u32_t	getMemUsage ()
	Statistics. More...
static u32_t	getCondNum ()
static u32_t	getMaxLiveCondNumber ()

Static Public Attributes
static u32_t	totalCondNum = 0

Protected Attributes
BBCondMap	bbConds
	map basic block to its successors/predecessors branch conditions More...
IndexToConditionMap	indexToDDNodeMap

Static Protected Attributes
static BddCondManager *	bddCondMgr = nullptr
	bbd manager More...

Private Member Functions
virtual void	allocateForBB (const BasicBlock &bb)
	Allocate path condition for every basic block. More...
Condition *	createNewCond (u32_t i)
	Create new BDD condition. More...
Condition *	newCond (const Instruction *inst)
	Allocate a new condition. More...
void	destroy ()
	Release memory. More...
void	setBranchCond (const BasicBlock *bb, const BasicBlock *succ, Condition *cond)
	Get/Set a branch condition, and its terminator instruction. More...
Condition *	getBranchCond (const BasicBlock *bb, const BasicBlock *succ) const
	Get branch condition. More...
Condition *	getEvalBrCond (const BasicBlock *bb, const BasicBlock *succ)
	Get a condition, evaluate the value for conditions if necessary (e.g., testNull like express) More...
Condition *	evaluateBranchCond (const BasicBlock *bb, const BasicBlock *succ, const Value *val)
	Evaluate branch conditions. More...
Condition *	evaluateLoopExitBranch (const BasicBlock *bb, const BasicBlock *succ)
	Evaluate loop exit branch. More...
Condition *	evaluateTestNullLikeExpr (const BranchInst *brInst, const BasicBlock *succ, const Value *val)
	Return branch condition after evaluating test null like expression. More...
Condition *	evaluateProgExit (const BranchInst *brInst, const BasicBlock *succ)
	Return condition when there is a branch calls program exit. More...
void	collectBBCallingProgExit (const BasicBlock &bb)
	Collect basic block contains program exit function call. More...
bool	isBBCallsProgExit (const BasicBlock *bb)
bool	isEQCmp (const CmpInst *cmp) const
	Evaluate test null/not null like expressions. More...
bool	isNECmp (const CmpInst *cmp) const
	Return true if the predicate of this compare instruction is not equal. More...
bool	isTestNullExpr (const Value *test, const Value *val) const
	Return true if this is a test null expression. More...
bool	isTestNotNullExpr (const Value *test, const Value *val) const
	Return true if this is a test not null expression. More...
bool	isTestContainsNullAndTheValue (const CmpInst *cmp, const Value *val) const
	Return true if two values on the predicate are what we want. More...
bool	setCFCond (const BasicBlock *bb, Condition *cond)
	Get/Set control-flow conditions. More...
Condition *	getCFCond (const BasicBlock *bb) const

Static Private Member Functions
static BddCondManager *	getBddCondManager ()
	Used internally, not supposed to be exposed to other classes. More...

Private Attributes
CondToTermInstMap	condToInstMap
	map a condition to its corresponding llvm instruction More...
PTACFInfoBuilder	cfInfoBuilder
	map a function to its loop info More...
FunToExitBBsMap	funToExitBBsMap
	map a function to all its basic blocks calling program exit More...
BBToCondMap	bbToCondMap
	map a basic block to its path condition starting from root More...
const Value *	curEvalVal
	current llvm value to evaluate branch condition when computing guards More...

Detailed Description

PathCondAllocator allocates conditions for each basic block of a certain CFG.

Definition at line 44 of file PathCondAllocator.h.

Member Typedef Documentation

BasicBlockSet

typedef Set<const BasicBlock*> SVF::PathCondAllocator::BasicBlockSet

Definition at line 54 of file PathCondAllocator.h.

BBCondMap

typedef Map<const BasicBlock*, CondPosMap > SVF::PathCondAllocator::BBCondMap

Definition at line 52 of file PathCondAllocator.h.

BBToCondMap

typedef Map<const BasicBlock*, Condition*> SVF::PathCondAllocator::BBToCondMap

map a basic block to its condition during control-flow guard computation

Definition at line 56 of file PathCondAllocator.h.

CFWorkList

typedef FIFOWorkList<const BasicBlock*> SVF::PathCondAllocator::CFWorkList

worklist for control-flow guard computation

Definition at line 57 of file PathCondAllocator.h.

Condition

typedef DdNode SVF::PathCondAllocator::Condition

Definition at line 50 of file PathCondAllocator.h.

CondPosMap

typedef Map<u32_t,Condition*> SVF::PathCondAllocator::CondPosMap

map a branch to its Condition

Definition at line 51 of file PathCondAllocator.h.

CondToTermInstMap

typedef Map<const Condition*, const Instruction* > SVF::PathCondAllocator::CondToTermInstMap

Definition at line 53 of file PathCondAllocator.h.

FunToExitBBsMap

typedef Map<const Function*, BasicBlockSet> SVF::PathCondAllocator::FunToExitBBsMap

map a function to all its basic blocks calling program exit

Definition at line 55 of file PathCondAllocator.h.

IndexToConditionMap

typedef Map<u32_t,Condition*> SVF::PathCondAllocator::IndexToConditionMap

Definition at line 59 of file PathCondAllocator.h.

Constructor & Destructor Documentation

PathCondAllocator()

SVF::PathCondAllocator::PathCondAllocator ( )

inline

Constructor.

Definition at line 62 of file PathCondAllocator.h.

    {
        getBddCondManager();
    }

~PathCondAllocator()

virtual SVF::PathCondAllocator::~PathCondAllocator ( )

inlinevirtual

Destructor.

Definition at line 67 of file PathCondAllocator.h.

    {
        destroy();
    }

Member Function Documentation

allocate()

void PathCondAllocator::allocate

(

const SVFModule *

M

)

Perform path allocation.

Allocate path condition for each branch

Definition at line 52 of file PathCondAllocator.cpp.

{
    DBOUT(DGENERAL,outs() << pasMsg("path condition allocation starts\n"));

    for (SVFModule::const_iterator fit = M->begin(); fit != M->end(); ++fit)
    {
        const SVFFunction * func = *fit;
        if (!SVFUtil::isExtCall(func))
        {
            // Allocate conditions for a program.
            for (Function::const_iterator bit = func->getLLVMFun()->begin(), ebit = func->getLLVMFun()->end(); bit != ebit; ++bit)
            {
                const BasicBlock & bb = *bit;
                collectBBCallingProgExit(bb);
                allocateForBB(bb);
            }
        }
    }

    if(Options::PrintPathCond)
        printPathCond();

    DBOUT(DGENERAL,outs() << pasMsg("path condition allocation ends\n"));
}

allocateForBB()

void PathCondAllocator::allocateForBB ( const BasicBlock &  bb )

privatevirtual

Allocate path condition for every basic block.

Allocate conditions for a basic block and propagate its condition to its successors.

TODO: handle BranchInst and SwitchInst individually here!!

Definition at line 80 of file PathCondAllocator.cpp.

{

    u32_t succ_number = getBBSuccessorNum(&bb);

    // if successor number greater than 1, allocate new decision variable for successors
    if(succ_number > 1)
    {

        //allocate log2(num_succ) decision variables
        double num = log(succ_number)/log(2);
        u32_t bit_num = (u32_t)ceil(num);
        u32_t succ_index = 0;
        std::vector<Condition*> condVec;
        for(u32_t i = 0 ; i < bit_num; i++)
        {
            condVec.push_back(newCond(bb.getTerminator()));
        }

        // iterate each successor
        for (succ_const_iterator succ_it = succ_begin(&bb);
                succ_it != succ_end(&bb);
                succ_it++, succ_index++)
        {

            const BasicBlock* succ = *succ_it;

            Condition* path_cond = getTrueCond();


            // for each successor decide its bit representation
            // decide whether each bit of succ_index is 1 or 0, if (three successor) succ_index is 000 then use C1^C2^C3
            // if 001 use C1^C2^negC3
            for(u32_t j = 0 ; j < bit_num; j++)
            {
                //test each bit of this successor's index (binary representation)
                u32_t tool = 0x01 << j;
                if(tool & succ_index)
                {
                    path_cond = condAnd(path_cond, condVec.at(j));
                }
                else
                {
                    path_cond = condAnd(path_cond, (condNeg(condVec.at(j))));
                }
            }
            setBranchCond(&bb,succ,path_cond);
        }

    }
}

clearCFCond()

void SVF::PathCondAllocator::clearCFCond ( )

inline

Definition at line 186 of file PathCondAllocator.h.

    {
        bbToCondMap.clear();
    }

collectBBCallingProgExit()

void PathCondAllocator::collectBBCallingProgExit ( const BasicBlock &  bb )

private

Collect basic block contains program exit function call.

Whether this basic block contains program exit function call

Definition at line 359 of file PathCondAllocator.cpp.

{

    for(BasicBlock::const_iterator it = bb.begin(), eit = bb.end(); it!=eit; it++)
    {
        const Instruction* inst = &*it;
        if(SVFUtil::isa<CallInst>(inst) || SVFUtil::isa<InvokeInst>(inst))
            if(SVFUtil::isProgExitCall(inst))
            {
                funToExitBBsMap[bb.getParent()].insert(&bb);
            }
    }
}

ComputeInterCallVFGGuard()

PathCondAllocator::Condition * PathCondAllocator::ComputeInterCallVFGGuard ( const BasicBlock *  srcBB, const BasicBlock *  dstBB, const BasicBlock *  callBB  )

virtual

Compute calling inter-procedural guards between two SVFGNodes (from caller to callee) src –c1–> callBB –true–> funEntryBB –c2–> dst the InterCallVFGGuard is c1 ^ c2

Definition at line 418 of file PathCondAllocator.cpp.

{
    const BasicBlock* funEntryBB = &dstBB->getParent()->getEntryBlock();

    Condition* c1 = ComputeIntraVFGGuard(srcBB,callBB);
    setCFCond(funEntryBB,condOr(getCFCond(funEntryBB),getCFCond(callBB)));
    Condition* c2 = ComputeIntraVFGGuard(funEntryBB,dstBB);
    return condAnd(c1,c2);
}

ComputeInterRetVFGGuard()

PathCondAllocator::Condition * PathCondAllocator::ComputeInterRetVFGGuard ( const BasicBlock *  srcBB, const BasicBlock *  dstBB, const BasicBlock *  retBB  )

virtual

Compute return inter-procedural guards between two SVFGNodes (from callee to caller) src –c1–> funExitBB –true–> retBB –c2–> dst the InterRetVFGGuard is c1 ^ c2

Definition at line 433 of file PathCondAllocator.cpp.

{
    const BasicBlock* funExitBB = getFunExitBB(srcBB->getParent());

    Condition* c1 = ComputeIntraVFGGuard(srcBB,funExitBB);
    setCFCond(retBB,condOr(getCFCond(retBB),getCFCond(funExitBB)));
    Condition* c2 = ComputeIntraVFGGuard(retBB,dstBB);
    return condAnd(c1,c2);
}

ComputeIntraVFGGuard()

PathCondAllocator::Condition * PathCondAllocator::ComputeIntraVFGGuard ( const BasicBlock *  srcBB, const BasicBlock *  dstBB  )

virtual

Guard Computation for a value-flow (between two basic blocks)

Compute intra-procedural guards between two SVFGNodes (inside same function)

if the dstBB is the eligible loop exit of the current basic block we can early terminate the computation

calculate the branch condition if succ post dominate bb, then we get brCond quicker by using postDT note that we assume loop exit always post dominate loop bodys which means loops are approximated only once.

Definition at line 446 of file PathCondAllocator.cpp.

{

    assert(srcBB->getParent() == dstBB->getParent() && "two basic blocks are not in the same function??");

    PostDominatorTree* postDT = getPostDT(srcBB->getParent());
    if(postDT->dominates(dstBB,srcBB))
        return getTrueCond();

    CFWorkList worklist;
    worklist.push(srcBB);
    setCFCond(srcBB,getTrueCond());

    while(!worklist.empty())
    {
        const BasicBlock* bb = worklist.pop();
        Condition* cond = getCFCond(bb);

        if(Condition* loopExitCond = evaluateLoopExitBranch(bb,dstBB))
            return condAnd(cond, loopExitCond);


        for (succ_const_iterator succ_it = succ_begin(bb);
                succ_it != succ_end(bb); succ_it++)
        {
            const BasicBlock* succ = *succ_it;
            Condition* brCond;
            if(postDT->dominates(succ,bb))
                brCond = getTrueCond();
            else
                brCond = getEvalBrCond(bb, succ);

            DBOUT(DSaber, outs() << " bb (" << bb->getName() <<
                  ") --> " << "succ_bb (" << succ->getName() << ") condition: " << brCond << "\n");
            Condition* succPathCond = condAnd(cond, brCond);
            if(setCFCond(succ, condOr(getCFCond(succ), succPathCond)))
                worklist.push(succ);
        }
    }

    DBOUT(DSaber, outs() << " src_bb (" << srcBB->getName() <<
          ") --> " << "dst_bb (" << dstBB->getName() << ") condition: " << getCFCond(dstBB) << "\n");

    return getCFCond(dstBB);
}

condAnd()

Condition* SVF::PathCondAllocator::condAnd ( Condition *  lhs, Condition *  rhs  )

inline

Condition operations.

Definition at line 126 of file PathCondAllocator.h.

    {
        return bddCondMgr->AND(lhs,rhs);
    }

condNeg()

Condition* SVF::PathCondAllocator::condNeg ( Condition *  cond )

inline

Definition at line 134 of file PathCondAllocator.h.

    {
        return bddCondMgr->NEG(cond);
    }

condOr()

Condition* SVF::PathCondAllocator::condOr ( Condition *  lhs, Condition *  rhs  )

inline

Definition at line 130 of file PathCondAllocator.h.

    {
        return bddCondMgr->OR(lhs,rhs);
    }

createNewCond()

Condition* SVF::PathCondAllocator::createNewCond ( u32_t  i )

inlineprivate

Create new BDD condition.

Definition at line 278 of file PathCondAllocator.h.

    {
        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;
    }

destroy()

void PathCondAllocator::destroy ( )

private

Release memory.

Release memory

Definition at line 502 of file PathCondAllocator.cpp.

{
    delete bddCondMgr;
    bddCondMgr = nullptr;
}

dumpCond()

std::string SVF::PathCondAllocator::dumpCond ( Condition *  cond ) const

inline

Definition at line 170 of file PathCondAllocator.h.

    {
        return bddCondMgr->dumpStr(cond);
    }

evaluateBranchCond()

PathCondAllocator::Condition * PathCondAllocator::evaluateBranchCond ( const BasicBlock *  bb, const BasicBlock *  succ, const Value *  val  )

private

Evaluate branch conditions.

Evaluate the branch condtion

(1) Evaluate a branch when it reaches a program exit (2) Evaluate a branch when it is loop exit branch (3) Evaluate a branch when it is a test null like condition

Definition at line 285 of file PathCondAllocator.cpp.

{
    if(getBBSuccessorNum(bb) == 1)
    {
        assert(bb->getTerminator()->getSuccessor(0) == succ && "not the unique successor?");
        return getTrueCond();
    }

    if(const BranchInst* brInst = SVFUtil::dyn_cast<BranchInst>(bb->getTerminator()))
    {
        assert(brInst->getNumSuccessors() == 2 && "not a two successors branch??");
        const BasicBlock* succ1 = brInst->getSuccessor(0);
        const BasicBlock* succ2 = brInst->getSuccessor(1);
        assert((succ1 == succ || succ2 == succ) && "not a successor??");

        Condition* evalLoopExit = evaluateLoopExitBranch(bb,succ);
        if(evalLoopExit)
            return evalLoopExit;

        Condition* evalProgExit = evaluateProgExit(brInst,succ);
        if(evalProgExit)
            return evalProgExit;

        Condition* evalTestNullLike = evaluateTestNullLikeExpr(brInst,succ,val);
        if(evalTestNullLike)
            return evalTestNullLike;

    }
    return getBranchCond(bb, succ);
}

evaluateLoopExitBranch()

PathCondAllocator::Condition * PathCondAllocator::evaluateLoopExitBranch ( const BasicBlock *  bb, const BasicBlock *  dst  )

private

Evaluate loop exit branch.

Evaluate loop exit branch to be true if bb is loop header and succ is the only exit basic block outside the loop (excluding exit bbs which call program exit) for all other case, we conservatively evaluate false for now

exclude exit bb which calls program exit

if the dst dominate all other loop exit bbs, then dst can certainly be reached

Definition at line 245 of file PathCondAllocator.cpp.

{
    const Function* fun = bb->getParent();
    assert(fun==dst->getParent() && "two basic blocks should be in the same function");

    const LoopInfo* loopInfo = getLoopInfo(fun);
    if(loopInfo->isLoopHeader(const_cast<BasicBlock*>(bb)))
    {
        const Loop *loop = loopInfo->getLoopFor(bb);
        SmallBBVector exitbbs;
        Set<BasicBlock*> filteredbbs;
        loop->getExitBlocks(exitbbs);
        while(!exitbbs.empty())
        {
            BasicBlock* eb = exitbbs.pop_back_val();
            if(isBBCallsProgExit(eb) == false)
                filteredbbs.insert(eb);
        }

        bool allPDT = true;
        PostDominatorTree* pdt = getPostDT(fun);
        for(Set<BasicBlock*>::const_iterator it = filteredbbs.begin(), eit = filteredbbs.end(); it!=eit; ++it)
        {
            if(pdt->dominates(dst,*it) == false)
                allPDT =false;
        }

        if(allPDT)
            return getTrueCond();
    }
    return nullptr;
}

evaluateProgExit()

PathCondAllocator::Condition * PathCondAllocator::evaluateProgExit ( const BranchInst *  brInst, const BasicBlock *  succ  )

private

Return condition when there is a branch calls program exit.

Evaluate condition for program exit (e.g., exit(0))

then branch calls program exit

else branch calls program exit

no branch call program exit

Definition at line 201 of file PathCondAllocator.cpp.

{
    const BasicBlock* succ1 = brInst->getSuccessor(0);
    const BasicBlock* succ2 = brInst->getSuccessor(1);

    bool branch1 = isBBCallsProgExit(succ1);
    bool branch2 = isBBCallsProgExit(succ2);

    if(branch1 == true && branch2 == false)
    {
        // succ is then branch
        if(succ1 == succ)
            return getFalseCond();
        // succ is else branch
        else
            return getTrueCond();
    }
    else if(branch1 == false && branch2 == true)
    {
        // succ is else branch
        if(succ2 == succ)
            return getFalseCond();
        // succ is then branch
        else
            return getTrueCond();
    }
    // two branches both call program exit
    else if(branch1 == true && branch2 == true)
    {
        return getFalseCond();
    }
    else
        return nullptr;

}

evaluateTestNullLikeExpr()

PathCondAllocator::Condition * PathCondAllocator::evaluateTestNullLikeExpr ( const BranchInst *  brInst, const BasicBlock *  succ, const Value *  val  )

private

Return branch condition after evaluating test null like expression.

Evaluate null like expression for source-sink related bug detection in SABER

Definition at line 171 of file PathCondAllocator.cpp.

{

    const BasicBlock* succ1 = brInst->getSuccessor(0);

    if(isTestNullExpr(brInst->getCondition(),val))
    {
        // succ is then branch
        if(succ1 == succ)
            return getFalseCond();
        // succ is else branch
        else
            return getTrueCond();
    }
    if(isTestNotNullExpr(brInst->getCondition(),val))
    {
        // succ is then branch
        if(succ1 == succ)
            return getTrueCond();
        // succ is else branch
        else
            return getFalseCond();
    }

    return nullptr;
}

exactCondElem()

NodeBS SVF::PathCondAllocator::exactCondElem ( Condition *  cond )

inline

Iterator every element of the bdd.

Definition at line 154 of file PathCondAllocator.h.

    {
        NodeBS elems;
        bddCondMgr->BddSupport(cond,elems);
        return elems;
    }

falseCond()

static Condition* SVF::PathCondAllocator::falseCond ( )

inlinestatic

Definition at line 76 of file PathCondAllocator.h.

    {
        return getBddCondManager()->getFalseCond();
    }

getBddCondManager()

static BddCondManager* SVF::PathCondAllocator::getBddCondManager ( )

inlinestaticprivate

Used internally, not supposed to be exposed to other classes.

Definition at line 295 of file PathCondAllocator.h.

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

getBranchCond()

PathCondAllocator::Condition * PathCondAllocator::getBranchCond ( const BasicBlock *  bb, const BasicBlock *  succ  ) const

private

Get branch condition.

Get a branch condition

Definition at line 136 of file PathCondAllocator.cpp.

{
    u32_t pos = getBBSuccessorPos(bb,succ);
    if(getBBSuccessorNum(bb) == 1)
        return getTrueCond();
    else
    {
        BBCondMap::const_iterator it = bbConds.find(bb);
        assert(it!=bbConds.end() && "basic block does not have branch and conditions??");
        CondPosMap::const_iterator cit = it->second.find(pos);
        assert(cit!=it->second.end() && "no condition on the branch??");
        return cit->second;
    }
}

getCFCond()

Condition* SVF::PathCondAllocator::getCFCond ( const BasicBlock *  bb ) const

inlineprivate

Definition at line 266 of file PathCondAllocator.h.

    {
        BBToCondMap::const_iterator it = bbToCondMap.find(bb);
        if(it==bbToCondMap.end())
        {
            return getFalseCond();
        }
        return it->second;
    }

getCond()

Condition* SVF::PathCondAllocator::getCond ( u32_t  i ) const

inline

Given an index, get its condition.

Definition at line 147 of file PathCondAllocator.h.

    {
        IndexToConditionMap::const_iterator it = indexToDDNodeMap.find(i);
        assert(it!=indexToDDNodeMap.end() && "condition not found!");
        return it->second;
    }

getCondInst()

const Instruction* SVF::PathCondAllocator::getCondInst ( const Condition *  cond ) const

inline

Get llvm conditional expression.

Definition at line 101 of file PathCondAllocator.h.

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

getCondNum()

static u32_t SVF::PathCondAllocator::getCondNum ( )

inlinestatic

Definition at line 87 of file PathCondAllocator.h.

    {
        return getBddCondManager()->getCondNumber();
    }

getCurEvalVal()

const Value* SVF::PathCondAllocator::getCurEvalVal ( ) const

inline

Get current value for branch condition evaluation.

Definition at line 196 of file PathCondAllocator.h.

    {
        return curEvalVal;
    }

getDT()

DominatorTree* SVF::PathCondAllocator::getDT ( const Function *  fun )

inline

Get dominators.

Definition at line 109 of file PathCondAllocator.h.

    {
        return cfInfoBuilder.getDT(fun);
    }

getEvalBrCond()

Condition* SVF::PathCondAllocator::getEvalBrCond ( const BasicBlock *  bb, const BasicBlock *  succ  )

inlineprivate

Get a condition, evaluate the value for conditions if necessary (e.g., testNull like express)

Definition at line 217 of file PathCondAllocator.h.

    {
        if(const Value* val = getCurEvalVal())
            return evaluateBranchCond(bb, succ, val);
        else
            return getBranchCond(bb,succ);
    }

getFalseCond()

Condition* SVF::PathCondAllocator::getFalseCond ( ) const

inline

Definition at line 142 of file PathCondAllocator.h.

    {
        return bddCondMgr->getFalseCond();
    }

getLoopInfo()

LoopInfo* SVF::PathCondAllocator::getLoopInfo ( const Function *  f )

inline

Get LoopInfo.

Definition at line 119 of file PathCondAllocator.h.

    {
        return cfInfoBuilder.getLoopInfo(f);
    }

getMaxLiveCondNumber()

static u32_t SVF::PathCondAllocator::getMaxLiveCondNumber ( )

inlinestatic

Definition at line 91 of file PathCondAllocator.h.

    {
        return getBddCondManager()->getMaxLiveCondNumber();
    }

getMemUsage()

static u32_t SVF::PathCondAllocator::getMemUsage ( )

inlinestatic

Statistics.

Definition at line 83 of file PathCondAllocator.h.

    {
        return getBddCondManager()->getBDDMemUsage();
    }

getPHIComplementCond()

PathCondAllocator::Condition * PathCondAllocator::getPHIComplementCond ( const BasicBlock *  BB1, const BasicBlock *  BB2, const BasicBlock *  BB0  )

virtual

Get complement condition (from B1 to B0) according to a complementBB (BB2) at a phi e.g., B0: dstBB; B1:incomingBB; B2:complementBB

Get complement phi condition e.g., B0: dstBB; B1:incomingBB; B2:complementBB Assume B0 (phi node) is the successor of both B1 and B2. If B1 dominates B2, and B0 not dominate B2 then condition from B1–>B0 = neg(B1–>B2)^(B1–>B0)

avoid both BB0 and BB1 dominate BB2 (e.g., while loop), then BB2 is not necessaryly a complement BB

Definition at line 398 of file PathCondAllocator.cpp.

{
    assert(BB1 && BB2 && "expect nullptr BB here!");

    DominatorTree* dt = getDT(BB1->getParent());
    if(dt->dominates(BB1,BB2) && !dt->dominates(BB0,BB2))
    {
        Condition* cond =  ComputeIntraVFGGuard(BB1,BB2);
        return condNeg(cond);
    }

    return trueCond();
}

getPostDT()

PostDominatorTree* SVF::PathCondAllocator::getPostDT ( const Function *  fun )

inline

Get Postdominators.

Definition at line 114 of file PathCondAllocator.h.

    {
        return cfInfoBuilder.getPostDT(fun);
    }

getTrueCond()

Condition* SVF::PathCondAllocator::getTrueCond ( ) const

inline

Definition at line 138 of file PathCondAllocator.h.

    {
        return bddCondMgr->getTrueCond();
    }

isBBCallsProgExit()

bool PathCondAllocator::isBBCallsProgExit ( const BasicBlock *  bb )

private

Whether this basic block contains program exit function call

Definition at line 376 of file PathCondAllocator.cpp.

{
    const Function* fun = bb->getParent();
    FunToExitBBsMap::const_iterator it = funToExitBBsMap.find(fun);
    if(it!=funToExitBBsMap.end())
    {
        PostDominatorTree* pdt = getPostDT(fun);
        for(BasicBlockSet::const_iterator bit = it->second.begin(), ebit= it->second.end(); bit!=ebit; bit++)
        {
            if(pdt->dominates(*bit,bb))
                return true;
        }
    }
    return false;
}

isEQCmp()

bool PathCondAllocator::isEQCmp ( const CmpInst *  cmp ) const

private

Evaluate test null/not null like expressions.

Return true if the predicate of this compare instruction is equal

Definition at line 316 of file PathCondAllocator.cpp.

{
    return (cmp->getPredicate() == CmpInst::ICMP_EQ);
}

isNECmp()

bool PathCondAllocator::isNECmp ( const CmpInst *  cmp ) const

private

Return true if the predicate of this compare instruction is not equal.

Definition at line 321 of file PathCondAllocator.cpp.

{
    return (cmp->getPredicate() == CmpInst::ICMP_NE);
}

isTestContainsNullAndTheValue()

bool PathCondAllocator::isTestContainsNullAndTheValue ( const CmpInst *  cmp, const Value *  val  ) const

private

Return true if two values on the predicate are what we want.

Definition at line 344 of file PathCondAllocator.cpp.

{

    const Value* op0 = cmp->getOperand(0);
    const Value* op1 = cmp->getOperand(1);
    if((op0 == val && SVFUtil::isa<ConstantPointerNull>(op1))
            || (op1 == val && SVFUtil::isa<ConstantPointerNull>(op0)) )
        return true;

    return false;
}

isTestNotNullExpr()

bool PathCondAllocator::isTestNotNullExpr ( const Value *  test, const Value *  val  ) const

private

Return true if this is a test not null expression.

Definition at line 335 of file PathCondAllocator.cpp.

{
    if(const CmpInst* cmp = SVFUtil::dyn_cast<CmpInst>(test))
    {
        return isTestContainsNullAndTheValue(cmp,val) && isNECmp(cmp);
    }
    return false;
}

isTestNullExpr()

bool PathCondAllocator::isTestNullExpr ( const Value *  test, const Value *  val  ) const

private

Return true if this is a test null expression.

Definition at line 326 of file PathCondAllocator.cpp.

{
    if(const CmpInst* cmp = SVFUtil::dyn_cast<CmpInst>(test))
    {
        return isTestContainsNullAndTheValue(cmp,val) && isEQCmp(cmp);
    }
    return false;
}

markForRelease()

void SVF::PathCondAllocator::markForRelease ( Condition *  cond )

inline

Decrease reference counting for the bdd.

Definition at line 161 of file PathCondAllocator.h.

    {
        bddCondMgr->markForRelease(cond);
    }

newCond()

Condition* SVF::PathCondAllocator::newCond ( const Instruction *  inst )

inlineprivate

Allocate a new condition.

Definition at line 286 of file PathCondAllocator.h.

    {
        Condition* cond = createNewCond(totalCondNum++);
        assert(condToInstMap.find(cond)==condToInstMap.end() && "this should be a fresh condition");
        condToInstMap[cond] = inst;
        return cond;
    }

printDbg()

void SVF::PathCondAllocator::printDbg ( Condition *  cond )

inline

Print debug information for this condition.

Definition at line 166 of file PathCondAllocator.h.

    {
        bddCondMgr->printDbg(cond);
    }

printPathCond()

void PathCondAllocator::printPathCond

(

)

Print out the path condition information.

Print path conditions

Definition at line 511 of file PathCondAllocator.cpp.

{

    outs() << "print path condition\n";

    for(BBCondMap::const_iterator it = bbConds.begin(), eit = bbConds.end(); it!=eit; ++it)
    {
        const BasicBlock* bb = it->first;
        for(CondPosMap::const_iterator cit = it->second.begin(), ecit = it->second.end(); cit!=ecit; ++cit)
        {
            u32_t i=0;
            for (const BasicBlock *succ: successors(bb))
            {
                if (i == cit->first)
                {
                    Condition* cond = cit->second;
                    outs() << bb->getName() << "-->" << succ->getName() << ":";
                    outs() << dumpCond(cond) << "\n";
                    break;
                }
                i++;
            }
        }
    }
}

setBranchCond()

void PathCondAllocator::setBranchCond ( const BasicBlock *  bb, const BasicBlock *  succ, Condition *  cond  )

private

Get/Set a branch condition, and its terminator instruction.

Set branch condition

Set a branch condition

we only care about basic blocks have more than one successor

FIXME: llvm getNumSuccessors allows duplicated block in the successors, it makes this assertion fail In this case we may waste a condition allocation, because the overwrite of the previous cond

Definition at line 154 of file PathCondAllocator.cpp.

{
    assert(getBBSuccessorNum(bb) > 1 && "not more than one successor??");
    u32_t pos = getBBSuccessorPos(bb,succ);
    CondPosMap& condPosMap = bbConds[bb];

    //assert(condPosMap.find(pos) == condPosMap.end() && "this branch has already been set ");

    condPosMap[pos] = cond;
}

setCFCond()

bool SVF::PathCondAllocator::setCFCond ( const BasicBlock *  bb, Condition *  cond  )

inlineprivate

Get/Set control-flow conditions.

Definition at line 257 of file PathCondAllocator.h.

    {
        BBToCondMap::iterator it = bbToCondMap.find(bb);
        if(it!=bbToCondMap.end() && it->second == cond)
            return false;

        bbToCondMap[bb] = cond;
        return true;
    }

setCurEvalVal()

void SVF::PathCondAllocator::setCurEvalVal ( const Value *  val )

inline

Set current value for branch condition evaluation.

Definition at line 191 of file PathCondAllocator.h.

    {
        curEvalVal = val;
    }

trueCond()

static Condition* SVF::PathCondAllocator::trueCond ( )

inlinestatic

Definition at line 71 of file PathCondAllocator.h.

    {
        return getBddCondManager()->getTrueCond();
    }

Member Data Documentation

bbConds

BBCondMap SVF::PathCondAllocator::bbConds

protected

map basic block to its successors/predecessors branch conditions

Definition at line 313 of file PathCondAllocator.h.

bbToCondMap

BBToCondMap SVF::PathCondAllocator::bbToCondMap

private

map a basic block to its path condition starting from root

Definition at line 308 of file PathCondAllocator.h.

bddCondMgr

BddCondManager * PathCondAllocator::bddCondMgr = nullptr

staticprotected

bbd manager

Definition at line 312 of file PathCondAllocator.h.

cfInfoBuilder

PTACFInfoBuilder SVF::PathCondAllocator::cfInfoBuilder

private

map a function to its loop info

Definition at line 306 of file PathCondAllocator.h.

condToInstMap

CondToTermInstMap SVF::PathCondAllocator::condToInstMap

private

map a condition to its corresponding llvm instruction

Definition at line 305 of file PathCondAllocator.h.

curEvalVal

const Value* SVF::PathCondAllocator::curEvalVal

private

current llvm value to evaluate branch condition when computing guards

Definition at line 309 of file PathCondAllocator.h.

funToExitBBsMap

FunToExitBBsMap SVF::PathCondAllocator::funToExitBBsMap

private

map a function to all its basic blocks calling program exit

Definition at line 307 of file PathCondAllocator.h.

indexToDDNodeMap

IndexToConditionMap SVF::PathCondAllocator::indexToDDNodeMap

protected

Definition at line 314 of file PathCondAllocator.h.

totalCondNum

u32_t PathCondAllocator::totalCondNum = 0

static

Definition at line 48 of file PathCondAllocator.h.

---

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

• /home/runner/work/SVF-1/SVF-1/include/Util/PathCondAllocator.h
• /home/runner/work/SVF-1/SVF-1/lib/Util/PathCondAllocator.cpp