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

5 files changed, 174 insertions, 15 deletions

diff --git a/Analysis/GRConstants.cpp b/Analysis/GRConstants.cpp
index c1200917d9..78d7b39cd9 100644
--- a/Analysis/GRConstants.cpp
+++ b/Analysis/GRConstants.cpp
@@ -169,7 +169,7 @@ public:
   
   /// 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 @@ public:
   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 @@ public:
   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 @@ public:
   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 @@ GRConstants::SetValue(StateTy St, const LValue& LV, const RValue& V) {
   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 @@ void GRConstants::ProcessBranch(Stmt* Condition, Stmt* Term,
     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 @@ void GRConstants::ProcessBranch(Stmt* Condition, Stmt* Term,
 
   // 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 @@ void GRConstants::ProcessBranch(Stmt* Condition, Stmt* Term,
   // 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 @@ void GRConstants::VisitDeclStmt(DeclStmt* DS, GRConstants::NodeTy* Pred,
     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 @@ void GRConstants::VisitBinaryOperator(BinaryOperator* B,
           Dst.Add(N2);
           break;
           
-        // Arithmetic opreators.
+        // Arithmetic operators.
           
         case BinaryOperator::Add: {
           const NonLValue& R1 = cast<NonLValue>(V1);
@@ -660,6 +779,14 @@ void GRConstants::Visit(Stmt* S, GRConstants::NodeTy* Pred,
 
   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 @@ void GRConstants::Visit(Stmt* S, GRConstants::NodeTy* Pred,
       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;
diff --git a/Analysis/GREngine.cpp b/Analysis/GREngine.cpp
index 8e86d08daa..e3b238aebe 100644
--- a/Analysis/GREngine.cpp
+++ b/Analysis/GREngine.cpp
@@ -155,6 +155,18 @@ void GREngineImpl::HandleBlockExit(CFGBlock * B, ExplodedNodeImpl* Pred) {
         assert(false && "Analysis for this terminator not implemented.");
         break;
         
+      case Stmt::ConditionalOperatorClass:
+        HandleBranch(cast<ConditionalOperator>(Term)->getCond(), Term, B, Pred);
+        break;
+        
+      case Stmt::ChooseExprClass:
+        HandleBranch(cast<ChooseExpr>(Term)->getCond(), Term, B, Pred);
+        break;
+        
+      case Stmt::BinaryOperatorClass: // '&&' and '||'
+        HandleBranch(cast<BinaryOperator>(Term)->getLHS(), Term, B, Pred);
+        break;
+        
       case Stmt::IfStmtClass:
         HandleBranch(cast<IfStmt>(Term)->getCond(), Term, B, Pred);
         break;
@@ -180,7 +192,7 @@ void GREngineImpl::HandleBlockExit(CFGBlock * B, ExplodedNodeImpl* Pred) {
   }
 }
 
-void GREngineImpl::HandleBranch(Stmt* Cond, Stmt* Term, CFGBlock * B,
+void GREngineImpl::HandleBranch(Expr* Cond, Stmt* Term, CFGBlock * B,
                                 ExplodedNodeImpl* Pred) {
   assert (B->succ_size() == 2);
 
diff --git a/Analysis/ValueState.cpp b/Analysis/ValueState.cpp
index de286ae8cb..f323fd4f90 100644
--- a/Analysis/ValueState.cpp
+++ b/Analysis/ValueState.cpp
@@ -16,7 +16,7 @@ RValue ValueStateManager::GetValue(const StateTy& St, const LValue& LV) {
   return InvalidValue();
 }
 
-RValue ValueStateManager::GetValue(const StateTy& St, Stmt* S) {
+RValue ValueStateManager::GetValue(const StateTy& St, Stmt* S, bool* hasVal) {
   for (;;) {
     switch (S->getStmtClass()) {
         
@@ -73,7 +73,14 @@ RValue ValueStateManager::GetValue(const StateTy& St, Stmt* S) {
   
   StateTy::TreeTy* T = St.SlimFind(S);
   
-  return T ? T->getValue().second : InvalidValue();
+  if (T) {
+    if (hasVal) *hasVal = true;
+    return T->getValue().second;
+  }
+  else {
+    if (hasVal) *hasVal = false;
+    return InvalidValue();
+  }
 }
 
 LValue ValueStateManager::GetLValue(const StateTy& St, Stmt* S) {
diff --git a/Analysis/ValueState.h b/Analysis/ValueState.h
index 2af3585b0f..ccbc6dd3c8 100644
--- a/Analysis/ValueState.h
+++ b/Analysis/ValueState.h
@@ -153,8 +153,9 @@ public:
   StateTy SetValue(StateTy St, Stmt* S, bool isBlkExpr, const RValue& V);
   StateTy SetValue(StateTy St, const LValue& LV, const RValue& V);
 
-  RValue GetValue(const StateTy& St, Stmt* S);
+  RValue GetValue(const StateTy& St, Stmt* S, bool* hasVal = NULL);
   RValue GetValue(const StateTy& St, const LValue& LV);
+    
   LValue GetLValue(const StateTy& St, Stmt* S);
   
   StateTy Remove(StateTy St, ValueKey K);
diff --git a/include/clang/Analysis/PathSensitive/GREngine.h b/include/clang/Analysis/PathSensitive/GREngine.h
index cb3366e3c0..157d283d5a 100644
--- a/include/clang/Analysis/PathSensitive/GREngine.h
+++ b/include/clang/Analysis/PathSensitive/GREngine.h
@@ -62,14 +62,14 @@ protected:
   void HandlePostStmt(const PostStmt& S, CFGBlock* B,
                       unsigned StmtIdx, ExplodedNodeImpl *Pred);
   
-  void HandleBranch(Stmt* Cond, Stmt* Term, CFGBlock* B,
+  void HandleBranch(Expr* Cond, Stmt* Term, CFGBlock* B,
                     ExplodedNodeImpl* Pred);  
   
   virtual void* ProcessEOP(CFGBlock* Blk, void* State) = 0;  
 
   virtual void  ProcessStmt(Stmt* S, GRStmtNodeBuilderImpl& Builder) = 0;
 
-  virtual void  ProcessBranch(Stmt* Condition, Stmt* Terminator,
+  virtual void  ProcessBranch(Expr* Condition, Stmt* Terminator,
                               GRBranchNodeBuilderImpl& Builder) = 0;
 
 
@@ -255,7 +255,7 @@ protected:
   }
 
 
-  virtual void ProcessBranch(Stmt* Condition, Stmt* Terminator,
+  virtual void ProcessBranch(Expr* Condition, Stmt* Terminator,
                              GRBranchNodeBuilderImpl& BuilderImpl) {
     GRBranchNodeBuilder<CHECKER> Builder(BuilderImpl);
     Checker->ProcessBranch(Condition, Terminator, Builder);