Implemented initial transfer function support for '&&', '||', '?', and
__builtin_choose.
git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@46731 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/Analysis/GRConstants.cpp b/Analysis/GRConstants.cpp
index c120091..78d7b39 100644
--- a/Analysis/GRConstants.cpp
+++ b/Analysis/GRConstants.cpp
@@ -169,7 +169,7 @@
/// ProcessBranch - Called by GREngine. Used to generate successor
/// nodes by processing the 'effects' of a branch condition.
- void ProcessBranch(Stmt* Condition, Stmt* Term, BranchNodeBuilder& builder);
+ void ProcessBranch(Expr* Condition, Stmt* Term, BranchNodeBuilder& builder);
/// RemoveDeadBindings - Return a new state that is the same as 'M' except
/// that all subexpression mappings are removed and that any
@@ -188,7 +188,11 @@
inline RValue GetValue(const StateTy& St, Stmt* S) {
return StateMgr.GetValue(St, S);
}
-
+
+ inline RValue GetValue(const StateTy& St, Stmt* S, bool& hasVal) {
+ return StateMgr.GetValue(St, S, &hasVal);
+ }
+
inline RValue GetValue(const StateTy& St, const Stmt* S) {
return GetValue(St, const_cast<Stmt*>(S));
}
@@ -200,6 +204,10 @@
inline LValue GetLValue(const StateTy& St, Stmt* S) {
return StateMgr.GetLValue(St, S);
}
+
+ inline NonLValue GetRValueConstant(uint64_t X, Expr* E) {
+ return NonLValue::GetValue(ValMgr, X, E->getType(), E->getLocStart());
+ }
/// Assume - Create new state by assuming that a given expression
/// is true or false.
@@ -230,7 +238,14 @@
void VisitBinaryOperator(BinaryOperator* B, NodeTy* Pred, NodeSet& Dst);
/// VisitDeclStmt - Transfer function logic for DeclStmts.
- void VisitDeclStmt(DeclStmt* DS, NodeTy* Pred, NodeSet& Dst);
+ void VisitDeclStmt(DeclStmt* DS, NodeTy* Pred, NodeSet& Dst);
+
+ /// VisitGuardedExpr - Transfer function logic for ?, __builtin_choose
+ void VisitGuardedExpr(Stmt* S, Stmt* LHS, Stmt* RHS,
+ NodeTy* Pred, NodeSet& Dst);
+
+ /// VisitLogicalExpr - Transfer function logic for '&&', '||'
+ void VisitLogicalExpr(BinaryOperator* B, NodeTy* Pred, NodeSet& Dst);
};
} // end anonymous namespace
@@ -269,7 +284,7 @@
return StateMgr.SetValue(St, LV, V);
}
-void GRConstants::ProcessBranch(Stmt* Condition, Stmt* Term,
+void GRConstants::ProcessBranch(Expr* Condition, Stmt* Term,
BranchNodeBuilder& builder) {
StateTy PrevState = builder.getState();
@@ -279,6 +294,37 @@
if (I.getKey().isSubExpr())
PrevState = StateMgr.Remove(PrevState, I.getKey());
+ // Remove terminator-specific bindings.
+ switch (Term->getStmtClass()) {
+ default: break;
+
+ case Stmt::BinaryOperatorClass: { // '&&', '||'
+ BinaryOperator* B = cast<BinaryOperator>(Term);
+ // FIXME: Liveness analysis should probably remove these automatically.
+ // Verify later when we converge to an 'optimization' stage.
+ PrevState = StateMgr.Remove(PrevState, B->getRHS());
+ break;
+ }
+
+ case Stmt::ConditionalOperatorClass: { // '?' operator
+ ConditionalOperator* C = cast<ConditionalOperator>(Term);
+ // FIXME: Liveness analysis should probably remove these automatically.
+ // Verify later when we converge to an 'optimization' stage.
+ if (Expr* L = C->getLHS()) PrevState = StateMgr.Remove(PrevState, L);
+ PrevState = StateMgr.Remove(PrevState, C->getRHS());
+ break;
+ }
+
+ case Stmt::ChooseExprClass: { // __builtin_choose_expr
+ ChooseExpr* C = cast<ChooseExpr>(Term);
+ // FIXME: Liveness analysis should probably remove these automatically.
+ // Verify later when we converge to an 'optimization' stage.
+ PrevState = StateMgr.Remove(PrevState, C->getRHS());
+ PrevState = StateMgr.Remove(PrevState, C->getRHS());
+ break;
+ }
+ }
+
RValue V = GetValue(PrevState, Condition);
switch (V.getBaseKind()) {
@@ -305,9 +351,11 @@
// Process the true branch.
bool isFeasible = true;
+
StateTy St = Assume(PrevState, V, true, isFeasible);
- if (isFeasible) builder.generateNode(St, true);
+ if (isFeasible)
+ builder.generateNode(St, true);
else {
builder.markInfeasible(true);
isFeasible = true;
@@ -316,11 +364,70 @@
// Process the false branch.
St = Assume(PrevState, V, false, isFeasible);
- if (isFeasible) builder.generateNode(St, false);
- else builder.markInfeasible(false);
-
+ if (isFeasible)
+ builder.generateNode(St, false);
+ else
+ builder.markInfeasible(false);
}
+
+void GRConstants::VisitLogicalExpr(BinaryOperator* B, NodeTy* Pred,
+ NodeSet& Dst) {
+
+ bool hasR2;
+ StateTy PrevState = Pred->getState();
+
+ RValue R1 = GetValue(PrevState, B->getLHS());
+ RValue R2 = GetValue(PrevState, B->getRHS(), hasR2);
+
+ if (isa<InvalidValue>(R1) &&
+ (isa<InvalidValue>(R2) ||
+ isa<UninitializedValue>(R2))) {
+
+ Nodify(Dst, B, Pred, SetValue(PrevState, B, R2));
+ return;
+ }
+ else if (isa<UninitializedValue>(R1)) {
+ Nodify(Dst, B, Pred, SetValue(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, SetValue(PrevState, B, GetRValueConstant(0U, B)));
+ return;
+ }
+ }
+ 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, SetValue(PrevState, B, GetRValueConstant(1U, B)));
+ return;
+ }
+ }
+
+ // 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, SetValue(PrevState, B, GetRValueConstant(1U, B)));
+
+ St = Assume(PrevState, R2, false, isFeasible);
+
+ if (isFeasible)
+ Nodify(Dst, B, Pred, SetValue(PrevState, B, GetRValueConstant(0U, B)));
+}
+
+
+
void GRConstants::ProcessStmt(Stmt* S, StmtNodeBuilder& builder) {
Builder = &builder;
@@ -416,6 +523,18 @@
Dst.Add(Pred);
}
+
+void GRConstants::VisitGuardedExpr(Stmt* S, Stmt* LHS, Stmt* RHS,
+ NodeTy* Pred, NodeSet& Dst) {
+
+ StateTy St = Pred->getState();
+
+ RValue R = GetValue(St, LHS);
+ if (isa<InvalidValue>(R)) R = GetValue(St, RHS);
+
+ Nodify(Dst, S, Pred, SetValue(St, S, R));
+}
+
void GRConstants::VisitUnaryOperator(UnaryOperator* U,
GRConstants::NodeTy* Pred,
GRConstants::NodeSet& Dst) {
@@ -531,7 +650,7 @@
Dst.Add(N2);
break;
- // Arithmetic opreators.
+ // Arithmetic operators.
case BinaryOperator::Add: {
const NonLValue& R1 = cast<NonLValue>(V1);
@@ -660,6 +779,14 @@
switch (S->getStmtClass()) {
case Stmt::BinaryOperatorClass:
+
+ if (cast<BinaryOperator>(S)->isLogicalOp()) {
+ VisitLogicalExpr(cast<BinaryOperator>(S), Pred, Dst);
+ break;
+ }
+
+ // Fall-through.
+
case Stmt::CompoundAssignOperatorClass:
VisitBinaryOperator(cast<BinaryOperator>(S), Pred, Dst);
break;
@@ -684,6 +811,18 @@
break;
}
+ case Stmt::ConditionalOperatorClass: { // '?' operator
+ ConditionalOperator* C = cast<ConditionalOperator>(S);
+ VisitGuardedExpr(S, C->getLHS(), C->getRHS(), Pred, Dst);
+ break;
+ }
+
+ case Stmt::ChooseExprClass: { // __builtin_choose_expr
+ ChooseExpr* C = cast<ChooseExpr>(S);
+ VisitGuardedExpr(S, C->getLHS(), C->getRHS(), Pred, Dst);
+ break;
+ }
+
case Stmt::DeclStmtClass:
VisitDeclStmt(cast<DeclStmt>(S), Pred, Dst);
break;