Handle the case when the LHS of the logical operator is undefined
Apparently, this can happen at least when the LHS is a pointer comparison at
the
analyzer cannot tell anything about the pointers in question.
One could argue that it is not a good idea to make up a value for the
expression
in the environment if someone before us deliberately left it as undefined,
since
some checker may rely on this fact. However, one could also say that if
somebody
wanted to check for the undefined value, he could do it immediately after the
expression which produced it (which all current checkers do, I believe). Also,
fact is that the analyzer already had assumed the value to be true or false
anyway, when it picked which branch to follow, so I am now basically recording
that decision.
Hi jordan_rose,
http://llvm-reviews.chandlerc.com/D1340
CHANGE SINCE LAST DIFF
http://llvm-reviews.chandlerc.com/D1340?vs=3316&id=3382#toc
Files:
lib/Analysis/LiveVariables.cpp
lib/StaticAnalyzer/Core/ExprEngine.cpp
lib/StaticAnalyzer/Core/ExprEngineC.cpp
test/Analysis/logical-ops.c
Index: lib/Analysis/LiveVariables.cpp
===================================================================
--- lib/Analysis/LiveVariables.cpp
+++ lib/Analysis/LiveVariables.cpp
@@ -212,6 +212,8 @@
LiveVariables::LivenessValues &val;
LiveVariables::Observer *observer;
const CFGBlock *currentBlock;
+
+ void MarkLogicalOpsLive(const Expr *E);
public:
TransferFunctions(LiveVariablesImpl &im,
LiveVariables::LivenessValues &Val,
@@ -368,9 +370,28 @@
if (observer)
observer->observerKill(DR);
}
+ } else {
+ // All logical sub-operations are live until we reach the outermost
+ // operator. Static analyzer relies on this behaviour.
+ MarkLogicalOpsLive(B);
}
}
+void TransferFunctions::MarkLogicalOpsLive(const Expr *E) {
+ const BinaryOperator *BO = dyn_cast<BinaryOperator>(E);
+ if (!BO || !BO->isLogicalOp())
+ return;
+
+ const Expr *LHS = BO->getLHS()->IgnoreParens();
+ const Expr *RHS = BO->getRHS()->IgnoreParens();
+
+ val.liveStmts = LV.SSetFact.add(val.liveStmts, LHS);
+ val.liveStmts = LV.SSetFact.add(val.liveStmts, RHS);
+
+ MarkLogicalOpsLive(LHS);
+ MarkLogicalOpsLive(RHS);
+}
+
void TransferFunctions::VisitBlockExpr(BlockExpr *BE) {
AnalysisDeclContext::referenced_decls_iterator I, E;
llvm::tie(I, E) =
Index: lib/StaticAnalyzer/Core/ExprEngine.cpp
===================================================================
--- lib/StaticAnalyzer/Core/ExprEngine.cpp
+++ lib/StaticAnalyzer/Core/ExprEngine.cpp
@@ -1391,16 +1391,21 @@
}
}
+ ProgramStateRef StTrue, StFalse;
+
// If the condition is still unknown, give up.
if (X.isUnknownOrUndef()) {
- builder.generateNode(PrevState, true, PredI);
- builder.generateNode(PrevState, false, PredI);
+ SValBuilder &SVB = PrevState->getStateManager().getSValBuilder();
+
+ StTrue = PrevState->BindExpr(Condition, BldCtx.LC, SVB.makeTruthVal(true));
+ StFalse = PrevState->BindExpr(Condition, BldCtx.LC, SVB.makeTruthVal(false));
+
+ 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.
Index: lib/StaticAnalyzer/Core/ExprEngineC.cpp
===================================================================
--- lib/StaticAnalyzer/Core/ExprEngineC.cpp
+++ lib/StaticAnalyzer/Core/ExprEngineC.cpp
@@ -501,72 +501,64 @@
}
}
+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 = cast_or_null<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.isUnknownOrUndef() && "Value should have already been computed.");
+
+ ProgramStateRef StTrue, StFalse;
+ llvm::tie(StTrue, StFalse) = State->assume(X.castAs<DefinedOrUnknownSVal>());
+
+ assert(!StTrue != !StFalse && "Value should be evaluate to true or false.");
+ if(!StFalse == (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 ||
B->getOpcode() == BO_LOr);
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());
-
- if (RHSVal.isUndef()) {
- X = RHSVal;
- } 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());
+ state = EvaluateLogicalExpression(B, Pred->getLocationContext(), state);
+ SVal X = state->getSVal(B, Pred->getLocationContext());
+
+ 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 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));
}
Index: test/Analysis/logical-ops.c
===================================================================
--- test/Analysis/logical-ops.c
+++ test/Analysis/logical-ops.c
@@ -25,3 +25,10 @@
return 1;
return 0;
}
+
+// this used to crash the analyzer
+int between(char *x) {
+ extern char start[];
+ extern char end[];
+ return x >= start && x < end;
+}
_______________________________________________
cfe-commits mailing list
[email protected]
http://lists.cs.uiuc.edu/mailman/listinfo/cfe-commits
