Consumed analysis: improve loop handling. The prior version of the analysis

marked all variables as "unknown" at the start of a loop.  The new version
keeps the initial state of variables unchanged, but issues a warning if the
state at the end of the loop is different from the state at the beginning.
This patch will eventually be replaced with a more precise analysis.

Initial patch by chris.wailes@gmail.com.  Reviewed and edited by
delesley@google.com.

llvm-svn: 192314

2 files changed, 146 insertions, 36 deletions

diff --git a/clang/lib/Analysis/Consumed.cpp b/clang/lib/Analysis/Consumed.cpp
index ee8dd77ff63..d291f627d02 100644
--- a/clang/lib/Analysis/Consumed.cpp
+++ b/clang/lib/Analysis/Consumed.cpp
@@ -31,18 +31,15 @@
 #include "llvm/Support/Compiler.h"
 #include "llvm/Support/raw_ostream.h"
 
+// TODO: Use information from tests in while-loop conditional.
 // TODO: Add notes about the actual and expected state for 
 // TODO: Correctly identify unreachable blocks when chaining boolean operators.
 // TODO: Adjust the parser and AttributesList class to support lists of
 //       identifiers.
 // TODO: Warn about unreachable code.
 // TODO: Switch to using a bitmap to track unreachable blocks.
-// TODO: Mark variables as Unknown going into while- or for-loops only if they
-//       are referenced inside that block. (Deferred)
 // TODO: Handle variable definitions, e.g. bool valid = x.isValid();
 //       if (valid) ...; (Deferred)
-// TODO: Add a method(s) to identify which method calls perform what state
-//       transitions. (Deferred)
 // TODO: Take notes on state transitions to provide better warning messages.
 //       (Deferred)
 // TODO: Test nested conditionals: A) Checking the same value multiple times,
@@ -54,6 +51,27 @@ using namespace consumed;
 // Key method definition
 ConsumedWarningsHandlerBase::~ConsumedWarningsHandlerBase() {}
 
+static SourceLocation getWarningLocForLoopExit(const CFGBlock *ExitBlock) {
+  // Find the source location of the last statement in the block, if the block
+  // is not empty.
+  if (const Stmt *StmtNode = ExitBlock->getTerminator()) {
+    return StmtNode->getLocStart();
+  } else {
+    for (CFGBlock::const_reverse_iterator BI = ExitBlock->rbegin(),
+         BE = ExitBlock->rend(); BI != BE; ++BI) {
+      // FIXME: Handle other CFGElement kinds.
+      if (Optional<CFGStmt> CS = BI->getAs<CFGStmt>())
+        return CS->getStmt()->getLocStart();
+    }
+  }
+  
+  // The block is empty, and has a single predecessor. Use its exit location.
+  assert(ExitBlock->pred_size() == 1 && *ExitBlock->pred_begin() &&
+         ExitBlock->succ_size() != 0);
+    
+  return getWarningLocForLoopExit(*ExitBlock->pred_begin());
+}
+
 static ConsumedState invertConsumedUnconsumed(ConsumedState State) {
   switch (State) {
   case CS_Unconsumed:
@@ -897,11 +915,26 @@ void splitVarStateForIfBinOp(const PropagationInfo &PInfo,
   }
 }
 
+bool ConsumedBlockInfo::allBackEdgesVisited(const CFGBlock *CurrBlock,
+                                            const CFGBlock *TargetBlock) {
+  
+  assert(CurrBlock && "Block pointer must not be NULL");
+  assert(TargetBlock && "TargetBlock pointer must not be NULL");
+  
+  unsigned int CurrBlockOrder = VisitOrder[CurrBlock->getBlockID()];
+  for (CFGBlock::const_pred_iterator PI = TargetBlock->pred_begin(),
+       PE = TargetBlock->pred_end(); PI != PE; ++PI) {
+    if (*PI && CurrBlockOrder < VisitOrder[(*PI)->getBlockID()] )
+      return false;
+  }
+  return true;
+}
+
 void ConsumedBlockInfo::addInfo(const CFGBlock *Block,
                                 ConsumedStateMap *StateMap,
                                 bool &AlreadyOwned) {
   
-  if (VisitedBlocks.alreadySet(Block)) return;
+  assert(Block && "Block pointer must not be NULL");
   
   ConsumedStateMap *Entry = StateMapsArray[Block->getBlockID()];
     
@@ -920,10 +953,7 @@ void ConsumedBlockInfo::addInfo(const CFGBlock *Block,
 void ConsumedBlockInfo::addInfo(const CFGBlock *Block,
                                 ConsumedStateMap *StateMap) {
   
-  if (VisitedBlocks.alreadySet(Block)) {
-    delete StateMap;
-    return;
-  }
+  assert(Block != NULL && "Block pointer must not be NULL");
   
   ConsumedStateMap *Entry = StateMapsArray[Block->getBlockID()];
     
@@ -936,15 +966,56 @@ void ConsumedBlockInfo::addInfo(const CFGBlock *Block,
   }
 }
 
-ConsumedStateMap* ConsumedBlockInfo::getInfo(const CFGBlock *Block) {
+ConsumedStateMap* ConsumedBlockInfo::borrowInfo(const CFGBlock *Block) {
+  assert(Block && "Block pointer must not be NULL");
+  assert(StateMapsArray[Block->getBlockID()] && "Block has no block info");
+  
   return StateMapsArray[Block->getBlockID()];
 }
 
-void ConsumedBlockInfo::markVisited(const CFGBlock *Block) {
-  VisitedBlocks.insert(Block);
+void ConsumedBlockInfo::discardInfo(const CFGBlock *Block) {
+  unsigned int BlockID = Block->getBlockID();
+  delete StateMapsArray[BlockID];
+  StateMapsArray[BlockID] = NULL;
+}
+
+ConsumedStateMap* ConsumedBlockInfo::getInfo(const CFGBlock *Block) {
+  assert(Block && "Block pointer must not be NULL");
+  
+  ConsumedStateMap *StateMap = StateMapsArray[Block->getBlockID()];
+  if (isBackEdgeTarget(Block)) {
+    return new ConsumedStateMap(*StateMap);
+  } else {
+    StateMapsArray[Block->getBlockID()] = NULL;
+    return StateMap;
+  }
+}
+
+bool ConsumedBlockInfo::isBackEdge(const CFGBlock *From, const CFGBlock *To) {
+  assert(From && "From block must not be NULL");
+  assert(To   && "From block must not be NULL");
+  
+  return VisitOrder[From->getBlockID()] > VisitOrder[To->getBlockID()];
+}
+
+bool ConsumedBlockInfo::isBackEdgeTarget(const CFGBlock *Block) {
+  assert(Block != NULL && "Block pointer must not be NULL");
+  
+  // Anything with less than two predecessors can't be the target of a back
+  // edge.
+  if (Block->pred_size() < 2)
+    return false;
+  
+  unsigned int BlockVisitOrder = VisitOrder[Block->getBlockID()];
+  for (CFGBlock::const_pred_iterator PI = Block->pred_begin(),
+       PE = Block->pred_end(); PI != PE; ++PI) {
+    if (*PI && BlockVisitOrder < VisitOrder[(*PI)->getBlockID()])
+      return true;
+  }
+  return false;
 }
 
-ConsumedState ConsumedStateMap::getState(const VarDecl *Var) {
+ConsumedState ConsumedStateMap::getState(const VarDecl *Var) const {
   MapType::const_iterator Entry = Map.find(Var);
   
   if (Entry != Map.end()) {
@@ -963,8 +1034,8 @@ void ConsumedStateMap::intersect(const ConsumedStateMap *Other) {
     return;
   }
   
-  for (MapType::const_iterator DMI = Other->Map.begin(),
-       DME = Other->Map.end(); DMI != DME; ++DMI) {
+  for (MapType::const_iterator DMI = Other->Map.begin(), DME = Other->Map.end();
+       DMI != DME; ++DMI) {
     
     LocalState = this->getState(DMI->first);
     
@@ -976,19 +1047,34 @@ void ConsumedStateMap::intersect(const ConsumedStateMap *Other) {
   }
 }
 
+void ConsumedStateMap::intersectAtLoopHead(const CFGBlock *LoopHead,
+  const CFGBlock *LoopBack, const ConsumedStateMap *LoopBackStates,
+  ConsumedWarningsHandlerBase &WarningsHandler) {
+  
+  ConsumedState LocalState;
+  SourceLocation BlameLoc = getWarningLocForLoopExit(LoopBack);
+  
+  for (MapType::const_iterator DMI = LoopBackStates->Map.begin(),
+       DME = LoopBackStates->Map.end(); DMI != DME; ++DMI) {
+    
+    LocalState = this->getState(DMI->first);
+    
+    if (LocalState == CS_None)
+      continue;
+    
+    if (LocalState != DMI->second) {
+      Map[DMI->first] = CS_Unknown;
+      WarningsHandler.warnLoopStateMismatch(
+        BlameLoc, DMI->first->getNameAsString());
+    }
+  }
+}
+
 void ConsumedStateMap::markUnreachable() {
   this->Reachable = false;
   Map.clear();
 }
 
-void ConsumedStateMap::makeUnknown() {
-  for (MapType::const_iterator DMI = Map.begin(), DME = Map.end(); DMI != DME;
-       ++DMI) {
-    
-    Map[DMI->first] = CS_Unknown;
-  }
-}
-
 void ConsumedStateMap::setState(const VarDecl *Var, ConsumedState State) {
   Map[Var] = State;
 }
@@ -997,6 +1083,17 @@ void ConsumedStateMap::remove(const VarDecl *Var) {
   Map.erase(Var);
 }
 
+bool ConsumedStateMap::operator!=(const ConsumedStateMap *Other) const {
+  for (MapType::const_iterator DMI = Other->Map.begin(), DME = Other->Map.end();
+       DMI != DME; ++DMI) {
+    
+    if (this->getState(DMI->first) != DMI->second)
+      return true;
+  }
+  
+  return false;
+}
+
 void ConsumedAnalyzer::determineExpectedReturnState(AnalysisDeclContext &AC,
                                                     const FunctionDecl *D) {
   QualType ReturnType;
@@ -1126,10 +1223,11 @@ void ConsumedAnalyzer::run(AnalysisDeclContext &AC) {
     return;
   
   determineExpectedReturnState(AC, D);
-  
-  BlockInfo = ConsumedBlockInfo(CFGraph);
-  
+
   PostOrderCFGView *SortedGraph = AC.getAnalysis<PostOrderCFGView>();
+  // AC.getCFG()->viewCFG(LangOptions());
+  
+  BlockInfo = ConsumedBlockInfo(CFGraph->getNumBlockIDs(), SortedGraph);
   
   CurrStates = new ConsumedStateMap();
   ConsumedStmtVisitor Visitor(AC, *this, CurrStates);
@@ -1145,7 +1243,6 @@ void ConsumedAnalyzer::run(AnalysisDeclContext &AC) {
        E = SortedGraph->end(); I != E; ++I) {
     
     const CFGBlock *CurrBlock = *I;
-    BlockInfo.markVisited(CurrBlock);
     
     if (CurrStates == NULL)
       CurrStates = BlockInfo.getInfo(CurrBlock);
@@ -1181,27 +1278,33 @@ void ConsumedAnalyzer::run(AnalysisDeclContext &AC) {
     if (!splitState(CurrBlock, Visitor)) {
       CurrStates->setSource(NULL);
       
-      if (CurrBlock->succ_size() > 1) {
-        CurrStates->makeUnknown();
+      if (CurrBlock->succ_size() > 1 ||
+          (CurrBlock->succ_size() == 1 &&
+           (*CurrBlock->succ_begin())->pred_size() > 1)) {
         
         bool OwnershipTaken = false;
         
         for (CFGBlock::const_succ_iterator SI = CurrBlock->succ_begin(),
              SE = CurrBlock->succ_end(); SI != SE; ++SI) {
           
-          if (*SI) BlockInfo.addInfo(*SI, CurrStates, OwnershipTaken);
+          if (*SI == NULL) continue;
+          
+          if (BlockInfo.isBackEdge(CurrBlock, *SI)) {
+            BlockInfo.borrowInfo(*SI)->intersectAtLoopHead(*SI, CurrBlock,
+                                                           CurrStates,
+                                                           WarningsHandler);
+            
+            if (BlockInfo.allBackEdgesVisited(*SI, CurrBlock))
+              BlockInfo.discardInfo(*SI);
+          } else {
+            BlockInfo.addInfo(*SI, CurrStates, OwnershipTaken);
+          }
         }
         
         if (!OwnershipTaken)
           delete CurrStates;
         
         CurrStates = NULL;
-        
-      } else if (CurrBlock->succ_size() == 1 &&
-                 (*CurrBlock->succ_begin())->pred_size() > 1) {
-        
-        BlockInfo.addInfo(*CurrBlock->succ_begin(), CurrStates);
-        CurrStates = NULL;
       }
     }
   } // End of block iterator.
diff --git a/clang/lib/Sema/AnalysisBasedWarnings.cpp b/clang/lib/Sema/AnalysisBasedWarnings.cpp
index a206acd7f23..53e53b28f4c 100644
--- a/clang/lib/Sema/AnalysisBasedWarnings.cpp
+++ b/clang/lib/Sema/AnalysisBasedWarnings.cpp
@@ -1477,6 +1477,13 @@ public:
     }
   }
   
+  void warnLoopStateMismatch(SourceLocation Loc, StringRef VariableName) {
+    PartialDiagnosticAt Warning(Loc, S.PDiag(diag::warn_loop_state_mismatch) <<
+      VariableName);
+    
+    Warnings.push_back(DelayedDiag(Warning, OptionalNotes()));
+  }
+  
   void warnReturnTypestateForUnconsumableType(SourceLocation Loc,
                                               StringRef TypeName) {
     PartialDiagnosticAt Warning(Loc, S.PDiag(