Author: labath Date: Fri Aug 23 02:19:22 2013 New Revision: 189090 URL: http://llvm.org/viewvc/llvm-project?rev=189090&view=rev Log: [analyzer] Refactor conditional expression evaluating code
Summary: Instead of digging through the ExplodedGraph, to figure out which edge brought us here, I compute the value of conditional expression by looking at the sub-expression values. To do this, I needed to change the liveness algorithm a bit -- now, the full conditional expression also depends on all atomic sub-expressions, not only the outermost ones. Reviewers: jordan_rose CC: cfe-commits Differential Revision: http://llvm-reviews.chandlerc.com/D1340 Modified: cfe/trunk/lib/Analysis/LiveVariables.cpp cfe/trunk/lib/StaticAnalyzer/Core/ExprEngine.cpp cfe/trunk/lib/StaticAnalyzer/Core/ExprEngineC.cpp cfe/trunk/test/Analysis/logical-ops.c Modified: cfe/trunk/lib/Analysis/LiveVariables.cpp URL: http://llvm.org/viewvc/llvm-project/cfe/trunk/lib/Analysis/LiveVariables.cpp?rev=189090&r1=189089&r2=189090&view=diff ============================================================================== --- cfe/trunk/lib/Analysis/LiveVariables.cpp (original) +++ cfe/trunk/lib/Analysis/LiveVariables.cpp Fri Aug 23 02:19:22 2013 @@ -212,6 +212,8 @@ class TransferFunctions : public StmtVis LiveVariables::LivenessValues &val; LiveVariables::Observer *observer; const CFGBlock *currentBlock; + + void markLogicalExprLeaves(const Expr *E); public: TransferFunctions(LiveVariablesImpl &im, LiveVariables::LivenessValues &Val, @@ -368,9 +370,25 @@ void TransferFunctions::VisitBinaryOpera if (observer) observer->observerKill(DR); } + } else if (B->isLogicalOp()) { + // Leaf expressions in the logical operator tree are live until we reach the + // outermost logical operator. Static analyzer relies on this behaviour. + markLogicalExprLeaves(B->getLHS()->IgnoreParens()); + markLogicalExprLeaves(B->getRHS()->IgnoreParens()); } } +void TransferFunctions::markLogicalExprLeaves(const Expr *E) { + const BinaryOperator *B = dyn_cast<BinaryOperator>(E); + if (!B || !B->isLogicalOp()) { + val.liveStmts = LV.SSetFact.add(val.liveStmts, E); + return; + } + + markLogicalExprLeaves(B->getLHS()->IgnoreParens()); + markLogicalExprLeaves(B->getRHS()->IgnoreParens()); +} + void TransferFunctions::VisitBlockExpr(BlockExpr *BE) { AnalysisDeclContext::referenced_decls_iterator I, E; llvm::tie(I, E) = Modified: cfe/trunk/lib/StaticAnalyzer/Core/ExprEngine.cpp URL: http://llvm.org/viewvc/llvm-project/cfe/trunk/lib/StaticAnalyzer/Core/ExprEngine.cpp?rev=189090&r1=189089&r2=189090&view=diff ============================================================================== --- cfe/trunk/lib/StaticAnalyzer/Core/ExprEngine.cpp (original) +++ cfe/trunk/lib/StaticAnalyzer/Core/ExprEngine.cpp Fri Aug 23 02:19:22 2013 @@ -1343,12 +1343,24 @@ void ExprEngine::processBranch(const Stm return; } + SValBuilder &SVB = Pred->getState()->getStateManager().getSValBuilder(); + SVal TrueVal = SVB.makeTruthVal(true); + SVal FalseVal = SVB.makeTruthVal(false); // Resolve the condition in the precense of nested '||' and '&&'. if (const Expr *Ex = dyn_cast<Expr>(Condition)) Condition = Ex->IgnoreParens(); - Condition = ResolveCondition(Condition, BldCtx.getBlock()); + + // Cast truth values to the correct type. + if (const Expr *Ex = dyn_cast<Expr>(Condition)) { + TrueVal = SVB.evalCast(TrueVal, Ex->getType(), + getContext().getLogicalOperationType()); + FalseVal = SVB.evalCast(FalseVal, Ex->getType(), + getContext().getLogicalOperationType()); + } + + PrettyStackTraceLoc CrashInfo(getContext().getSourceManager(), Condition->getLocStart(), "Error evaluating branch"); @@ -1391,31 +1403,37 @@ void ExprEngine::processBranch(const Stm } } + ProgramStateRef StTrue, StFalse; + // If the condition is still unknown, give up. if (X.isUnknownOrUndef()) { - builder.generateNode(PrevState, true, PredI); - builder.generateNode(PrevState, false, PredI); + + StTrue = PrevState->BindExpr(Condition, BldCtx.LC, TrueVal); + StFalse = PrevState->BindExpr(Condition, BldCtx.LC, FalseVal); + + builder.generateNode(StTrue, true, PredI); + builder.generateNode(StFalse, false, PredI); continue; } DefinedSVal V = X.castAs<DefinedSVal>(); - - ProgramStateRef StTrue, StFalse; tie(StTrue, StFalse) = PrevState->assume(V); // Process the true branch. if (builder.isFeasible(true)) { - if (StTrue) + if (StTrue) { + StTrue = StTrue->BindExpr(Condition, BldCtx.LC, TrueVal); builder.generateNode(StTrue, true, PredI); - else + } else builder.markInfeasible(true); } // Process the false branch. if (builder.isFeasible(false)) { - if (StFalse) + if (StFalse) { + StFalse = StFalse->BindExpr(Condition, BldCtx.LC, FalseVal); builder.generateNode(StFalse, false, PredI); - else + } else builder.markInfeasible(false); } } Modified: cfe/trunk/lib/StaticAnalyzer/Core/ExprEngineC.cpp URL: http://llvm.org/viewvc/llvm-project/cfe/trunk/lib/StaticAnalyzer/Core/ExprEngineC.cpp?rev=189090&r1=189089&r2=189090&view=diff ============================================================================== --- cfe/trunk/lib/StaticAnalyzer/Core/ExprEngineC.cpp (original) +++ cfe/trunk/lib/StaticAnalyzer/Core/ExprEngineC.cpp Fri Aug 23 02:19:22 2013 @@ -501,6 +501,33 @@ void ExprEngine::VisitDeclStmt(const Dec } } +static ProgramStateRef evaluateLogicalExpression(const Expr *E, + const LocationContext *LC, + ProgramStateRef State) { + SVal X = State->getSVal(E, LC); + if (! X.isUnknown()) + return State; + + const BinaryOperator *B = dyn_cast<BinaryOperator>(E->IgnoreParens()); + if (!B || (B->getOpcode() != BO_LAnd && B->getOpcode() != BO_LOr)) + return State; + + State = evaluateLogicalExpression(B->getLHS(), LC, State); + X = State->getSVal(B->getLHS(), LC); + QualType XType = B->getLHS()->getType(); + + assert(X.isConstant()); + if (!X.isZeroConstant() == (B->getOpcode() == BO_LAnd)) { + // LHS not sufficient, we need to check RHS as well + State = evaluateLogicalExpression(B->getRHS(), LC, State); + X = State->getSVal(B->getRHS(), LC); + XType = B->getRHS()->getType(); + } + + SValBuilder &SVB = State->getStateManager().getSValBuilder(); + return State->BindExpr(E, LC, SVB.evalCast(X, B->getType(), XType)); +} + void ExprEngine::VisitLogicalExpr(const BinaryOperator* B, ExplodedNode *Pred, ExplodedNodeSet &Dst) { assert(B->getOpcode() == BO_LAnd || @@ -509,64 +536,25 @@ void ExprEngine::VisitLogicalExpr(const StmtNodeBuilder Bldr(Pred, Dst, *currBldrCtx); ProgramStateRef state = Pred->getState(); - ExplodedNode *N = Pred; - while (!N->getLocation().getAs<BlockEntrance>()) { - ProgramPoint P = N->getLocation(); - assert(P.getAs<PreStmt>()|| P.getAs<PreStmtPurgeDeadSymbols>()); - (void) P; - assert(N->pred_size() == 1); - N = *N->pred_begin(); - } - assert(N->pred_size() == 1); - N = *N->pred_begin(); - BlockEdge BE = N->getLocation().castAs<BlockEdge>(); - SVal X; - - // Determine the value of the expression by introspecting how we - // got this location in the CFG. This requires looking at the previous - // block we were in and what kind of control-flow transfer was involved. - const CFGBlock *SrcBlock = BE.getSrc(); - // The only terminator (if there is one) that makes sense is a logical op. - CFGTerminator T = SrcBlock->getTerminator(); - if (const BinaryOperator *Term = cast_or_null<BinaryOperator>(T.getStmt())) { - (void) Term; - assert(Term->isLogicalOp()); - assert(SrcBlock->succ_size() == 2); - // Did we take the true or false branch? - unsigned constant = (*SrcBlock->succ_begin() == BE.getDst()) ? 1 : 0; - X = svalBuilder.makeIntVal(constant, B->getType()); - } - else { - // If there is no terminator, by construction the last statement - // in SrcBlock is the value of the enclosing expression. - // However, we still need to constrain that value to be 0 or 1. - assert(!SrcBlock->empty()); - CFGStmt Elem = SrcBlock->rbegin()->castAs<CFGStmt>(); - const Expr *RHS = cast<Expr>(Elem.getStmt()); - SVal RHSVal = N->getState()->getSVal(RHS, Pred->getLocationContext()); + state = evaluateLogicalExpression(B, Pred->getLocationContext(), state); + SVal X = state->getSVal(B, Pred->getLocationContext()); - if (RHSVal.isUndef()) { - X = RHSVal; + if (!X.isUndef()) { + DefinedOrUnknownSVal DefinedRHS = X.castAs<DefinedOrUnknownSVal>(); + ProgramStateRef StTrue, StFalse; + llvm::tie(StTrue, StFalse) = state->assume(DefinedRHS); + if (StTrue) { + if (!StFalse) { + // The value is known to be true. + X = getSValBuilder().makeIntVal(1, B->getType()); + } // else The truth value of X is unknown, just leave it as it is. } else { - DefinedOrUnknownSVal DefinedRHS = RHSVal.castAs<DefinedOrUnknownSVal>(); - ProgramStateRef StTrue, StFalse; - llvm::tie(StTrue, StFalse) = N->getState()->assume(DefinedRHS); - if (StTrue) { - if (StFalse) { - // We can't constrain the value to 0 or 1. - // The best we can do is a cast. - X = getSValBuilder().evalCast(RHSVal, B->getType(), RHS->getType()); - } else { - // The value is known to be true. - X = getSValBuilder().makeIntVal(1, B->getType()); - } - } else { - // The value is known to be false. - assert(StFalse && "Infeasible path!"); - X = getSValBuilder().makeIntVal(0, B->getType()); - } + // The value is known to be false. + assert(StFalse && "Infeasible path!"); + X = getSValBuilder().makeIntVal(0, B->getType()); } } + Bldr.generateNode(B, Pred, state->BindExpr(B, Pred->getLocationContext(), X)); } Modified: cfe/trunk/test/Analysis/logical-ops.c URL: http://llvm.org/viewvc/llvm-project/cfe/trunk/test/Analysis/logical-ops.c?rev=189090&r1=189089&r2=189090&view=diff ============================================================================== --- cfe/trunk/test/Analysis/logical-ops.c (original) +++ cfe/trunk/test/Analysis/logical-ops.c Fri Aug 23 02:19:22 2013 @@ -25,3 +25,15 @@ int testTypeIsInt(int i, void *p) { return 1; return 0; } + +// These crashed the analyzer at some point. +int between(char *x) { + extern char start[]; + extern char end[]; + return x >= start && x < end; +} + +int undef(void) {} // expected-warning{{control reaches end of non-void function}} +void useUndef(void) { 0 || undef(); } + +void testPointer(void) { (void) (1 && testPointer && 0); } _______________________________________________ cfe-commits mailing list [email protected] http://lists.cs.uiuc.edu/mailman/listinfo/cfe-commits
