Major cleanup of the transfer function logic for '&&', '||', and '?'. We
now store in the state essentially which branch we took. This removes
a bunch of bogus assumptions (and likely bugs), reduces the complexity of
the implementation, and facilitates more optimizations.
git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@47613 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/Analysis/GRExprEngine.cpp b/Analysis/GRExprEngine.cpp
index cc1e899..4479ecf 100644
--- a/Analysis/GRExprEngine.cpp
+++ b/Analysis/GRExprEngine.cpp
@@ -66,6 +66,60 @@
return StateMgr.SetRVal(St, LV, RV);
}
+GRExprEngine::StateTy
+GRExprEngine::MarkBranch(StateTy St, Stmt* Terminator, bool branchTaken) {
+
+ switch (Terminator->getStmtClass()) {
+ default:
+ return St;
+
+ case Stmt::BinaryOperatorClass: { // '&&' and '||'
+
+ BinaryOperator* B = cast<BinaryOperator>(Terminator);
+ BinaryOperator::Opcode Op = B->getOpcode();
+
+ assert (Op == BinaryOperator::LAnd || Op == BinaryOperator::LOr);
+
+ // For &&, if we take the true branch, then the value of the whole
+ // expression is that of the RHS expression.
+ //
+ // For ||, if we take the false branch, then the value of the whole
+ // expression is that of the RHS expression.
+
+ Expr* Ex = (Op == BinaryOperator::LAnd && branchTaken) ||
+ (Op == BinaryOperator::LOr && !branchTaken)
+ ? B->getRHS() : B->getLHS();
+
+ return SetBlkExprRVal(St, B, UninitializedVal(Ex));
+ }
+
+ case Stmt::ConditionalOperatorClass: { // ?:
+
+ ConditionalOperator* C = cast<ConditionalOperator>(Terminator);
+
+ // For ?, if branchTaken == true then the value is either the LHS or
+ // the condition itself. (GNU extension).
+
+ Expr* Ex;
+
+ if (branchTaken)
+ Ex = C->getLHS() ? C->getLHS() : C->getCond();
+ else
+ Ex = C->getRHS();
+
+ return SetBlkExprRVal(St, C, UninitializedVal(Ex));
+ }
+
+ case Stmt::ChooseExprClass: { // ?:
+
+ ChooseExpr* C = cast<ChooseExpr>(Terminator);
+
+ Expr* Ex = branchTaken ? C->getLHS() : C->getRHS();
+ return SetBlkExprRVal(St, C, UninitializedVal(Ex));
+ }
+ }
+}
+
void GRExprEngine::ProcessBranch(Expr* Condition, Stmt* Term,
BranchNodeBuilder& builder) {
@@ -126,7 +180,7 @@
StateTy St = Assume(PrevState, V, true, isFeasible);
if (isFeasible)
- builder.generateNode(St, true);
+ builder.generateNode(MarkBranch(St, Term, true), true);
else
builder.markInfeasible(true);
}
@@ -146,7 +200,7 @@
StateTy St = Assume(PrevState, V, false, isFeasible);
if (isFeasible)
- builder.generateNode(St, false);
+ builder.generateNode(MarkBranch(St, Term, false), false);
else
builder.markInfeasible(false);
}
@@ -295,59 +349,54 @@
void GRExprEngine::VisitLogicalExpr(BinaryOperator* B, NodeTy* Pred,
NodeSet& Dst) {
-
- bool hasR2;
- StateTy PrevState = Pred->getState();
-
- RVal R1 = GetRVal(PrevState, B->getLHS());
- RVal R2 = GetRVal(PrevState, B->getRHS(), hasR2);
- if (hasR2) {
- if (R2.isUnknownOrUninit()) {
- Nodify(Dst, B, Pred, SetRVal(PrevState, B, R2));
- return;
- }
- }
- else if (R1.isUnknownOrUninit()) {
- Nodify(Dst, B, Pred, SetRVal(PrevState, B, R1));
- return;
- }
-
- // R1 is an expression that can evaluate to either 'true' or 'false'.
- if (B->getOpcode() == BinaryOperator::LAnd) {
- // hasR2 == 'false' means that LHS evaluated to 'false' and that
- // we short-circuited, leading to a value of '0' for the '&&' expression.
- if (hasR2 == false) {
- Nodify(Dst, B, Pred, SetRVal(PrevState, B, MakeConstantVal(0U, B)));
- return;
- }
+ assert (B->getOpcode() == BinaryOperator::LAnd ||
+ B->getOpcode() == BinaryOperator::LOr);
+
+ assert (B == CurrentStmt && getCFG().isBlkExpr(B));
+
+ StateTy St = Pred->getState();
+ RVal X = GetBlkExprRVal(St, B);
+
+ assert (X.isUninit());
+
+ Expr* Ex = (Expr*) cast<UninitializedVal>(X).getData();
+
+ assert (Ex);
+
+ if (Ex == B->getRHS()) {
+
+ X = GetBlkExprRVal(St, Ex);
+
+ // We took the RHS. Because the value of the '&&' or '||' expression must
+ // evaluate to 0 or 1, we must assume the value of the RHS evaluates to 0
+ // or 1. Alternatively, we could take a lazy approach, and calculate this
+ // value later when necessary. We don't have the machinery in place for
+ // this right now, and since most logical expressions are used for branches,
+ // the payoff is not likely to be large. Instead, we do eager evaluation.
+
+ bool isFeasible = false;
+ StateTy NewState = Assume(St, X, true, isFeasible);
+
+ if (isFeasible)
+ Nodify(Dst, B, Pred, SetBlkExprRVal(NewState, B, MakeConstantVal(1U, B)));
+
+ isFeasible = false;
+ NewState = Assume(St, X, false, isFeasible);
+
+ if (isFeasible)
+ Nodify(Dst, B, Pred, SetBlkExprRVal(NewState, B, MakeConstantVal(0U, B)));
}
else {
- assert (B->getOpcode() == BinaryOperator::LOr);
- // hasR2 == 'false' means that the LHS evaluate to 'true' and that
- // we short-circuited, leading to a value of '1' for the '||' expression.
- if (hasR2 == false) {
- Nodify(Dst, B, Pred, SetRVal(PrevState, B, MakeConstantVal(1U, B)));
- return;
- }
+ // We took the LHS expression. Depending on whether we are '&&' or
+ // '||' we know what the value of the expression is via properties of
+ // the short-circuiting.
+
+ X = MakeConstantVal( B->getOpcode() == BinaryOperator::LAnd ? 0U : 1U, B);
+ Nodify(Dst, B, Pred, SetBlkExprRVal(St, B, X));
}
-
- // If we reach here we did not short-circuit. Assume R2 == true and
- // R2 == false.
-
- bool isFeasible;
- StateTy St = Assume(PrevState, R2, true, isFeasible);
-
- if (isFeasible)
- Nodify(Dst, B, Pred, SetRVal(PrevState, B, MakeConstantVal(1U, B)));
-
- St = Assume(PrevState, R2, false, isFeasible);
-
- if (isFeasible)
- Nodify(Dst, B, Pred, SetRVal(PrevState, B, MakeConstantVal(0U, B)));
}
-
-
+
void GRExprEngine::ProcessStmt(Stmt* S, StmtNodeBuilder& builder) {
@@ -538,12 +587,19 @@
void GRExprEngine::VisitGuardedExpr(Expr* Ex, Expr* L, Expr* R,
NodeTy* Pred, NodeSet& Dst) {
+ assert (Ex == CurrentStmt && getCFG().isBlkExpr(Ex));
+
StateTy St = Pred->getState();
+ RVal X = GetBlkExprRVal(St, Ex);
- RVal V = GetRVal(St, L);
- if (isa<UnknownVal>(V)) V = GetRVal(St, R);
+ assert (X.isUninit());
- Nodify(Dst, Ex, Pred, SetRVal(St, Ex, V));
+ Expr* SE = (Expr*) cast<UninitializedVal>(X).getData();
+
+ assert (SE);
+
+ X = GetBlkExprRVal(St, SE);
+ Nodify(Dst, Ex, Pred, SetBlkExprRVal(St, Ex, X));
}
/// VisitSizeOfAlignOfTypeExpr - Transfer function for sizeof(type).
diff --git a/Analysis/ValueState.cpp b/Analysis/ValueState.cpp
index 03b2996..ab208ff 100644
--- a/Analysis/ValueState.cpp
+++ b/Analysis/ValueState.cpp
@@ -69,10 +69,14 @@
MarkedSymbols.insert(*SI);
}
}
- else
+ else {
+ RVal X = I.getData();
+
+ if (X.isUninit() && cast<UninitializedVal>(X).getData())
+ continue;
+
NewSt.BlockExprBindings = Remove(NewSt, BlkExpr);
-
- continue;
+ }
}
// Iterate over the variable bindings.
@@ -209,7 +213,7 @@
return getPersistentState(NewSt);
}
-RVal ValueStateManager::GetRVal(ValueState St, Expr* E, bool* hasVal) {
+RVal ValueStateManager::GetRVal(ValueState St, Expr* E) {
for (;;) {
@@ -322,21 +326,15 @@
ValueState::ExprBindingsTy::TreeTy* T = St->SubExprBindings.SlimFind(E);
- if (T) {
- if (hasVal) *hasVal = true;
- return T->getValue().second;
- }
+ return T ? T->getValue().second : GetBlkExprRVal(St, E);
+}
+
+RVal ValueStateManager::GetBlkExprRVal(ValueState St, Expr* E) {
- T = St->BlockExprBindings.SlimFind(E);
-
- if (T) {
- if (hasVal) *hasVal = true;
- return T->getValue().second;
- }
- else {
- if (hasVal) *hasVal = false;
- return UnknownVal();
- }
+ assert (!isa<ParenExpr>(E));
+
+ ValueState::ExprBindingsTy::TreeTy* T = St->BlockExprBindings.SlimFind(E);
+ return T ? T->getValue().second : UnknownVal();
}
RVal ValueStateManager::GetLVal(ValueState St, Expr* E) {
diff --git a/Analysis/ValueState.h b/Analysis/ValueState.h
index 424b832..3e00122 100644
--- a/Analysis/ValueState.h
+++ b/Analysis/ValueState.h
@@ -60,11 +60,11 @@
void operator=(const ValueStateImpl& R) const;
public:
- vstate::ExprBindingsTy SubExprBindings;
- vstate::ExprBindingsTy BlockExprBindings;
- vstate::VarBindingsTy VarBindings;
- vstate::ConstNotEqTy ConstNotEq;
- vstate::ConstEqTy ConstEq;
+ vstate::ExprBindingsTy SubExprBindings;
+ vstate::ExprBindingsTy BlockExprBindings;
+ vstate::VarBindingsTy VarBindings;
+ vstate::ConstNotEqTy ConstNotEq;
+ vstate::ConstEqTy ConstEq;
/// This ctor is used when creating the first ValueStateImpl object.
ValueStateImpl(vstate::ExprBindingsTy EB, vstate::VarBindingsTy VB,
@@ -258,10 +258,12 @@
ValueState SetRVal(ValueState St, Expr* E, bool isBlkExpr, RVal V);
ValueState SetRVal(ValueState St, LVal LV, RVal V);
- RVal GetRVal(ValueState St, Expr* E, bool* hasVal = NULL);
- RVal GetRVal(ValueState St, const LVal& LV, QualType T = QualType());
+ RVal GetRVal(ValueState St, Expr* E);
+ RVal GetRVal(ValueState St, const LVal& LV, QualType T = QualType());
RVal GetLVal(ValueState St, Expr* E);
+ RVal GetBlkExprRVal(ValueState St, Expr* Ex);
+
ValueState getPersistentState(const ValueStateImpl& Impl);
ValueState AddEQ(ValueState St, SymbolID sym, const llvm::APSInt& V);