[CFG] Add LoopExit information to CFG

This patch introduces a new CFG element CFGLoopExit that indicate when a loop
ends. It does not deal with returnStmts yet (left it as a TODO).
It hidden behind a new analyzer-config flag called cfg-loopexit (false by
default).
Test cases added.

The main purpose of this patch right know is to make loop unrolling and loop
widening easier and more efficient. However, this information can be useful for
future improvements in the StaticAnalyzer core too.

Differential Revision: https://reviews.llvm.org/D35668

llvm-svn: 311235

1 files changed, 24 insertions, 0 deletions

diff --git a/clang/lib/Analysis/CFG.cpp b/clang/lib/Analysis/CFG.cpp
index 6a77455edee..c47a917bef6 100644
--- a/clang/lib/Analysis/CFG.cpp
+++ b/clang/lib/Analysis/CFG.cpp
@@ -602,6 +602,7 @@ private:
     return Visit(S, AddStmtChoice::AlwaysAdd);
   }
   CFGBlock *addInitializer(CXXCtorInitializer *I);
+  void addLoopExit(const Stmt *LoopStmt);
   void addAutomaticObjDtors(LocalScope::const_iterator B,
                             LocalScope::const_iterator E, Stmt *S);
   void addLifetimeEnds(LocalScope::const_iterator B,
@@ -652,6 +653,10 @@ private:
     B->appendLifetimeEnds(VD, S, cfg->getBumpVectorContext());
   }
 
+  void appendLoopExit(CFGBlock *B, const Stmt *LoopStmt) {
+    B->appendLoopExit(LoopStmt, cfg->getBumpVectorContext());
+  }
+
   void appendDeleteDtor(CFGBlock *B, CXXRecordDecl *RD, CXXDeleteExpr *DE) {
     B->appendDeleteDtor(RD, DE, cfg->getBumpVectorContext());
   }
@@ -1253,6 +1258,16 @@ static QualType getReferenceInitTemporaryType(ASTContext &Context,
   return Init->getType();
 }
 
+
+// TODO: Support adding LoopExit element to the CFG in case where the loop is
+// ended by ReturnStmt, GotoStmt or ThrowExpr.
+void CFGBuilder::addLoopExit(const Stmt *LoopStmt){
+  if(!BuildOpts.AddLoopExit)
+    return;
+  autoCreateBlock();
+  appendLoopExit(Block, LoopStmt);
+}
+
 void CFGBuilder::addAutomaticObjHandling(LocalScope::const_iterator B,
                                          LocalScope::const_iterator E,
                                          Stmt *S) {
@@ -2543,6 +2558,8 @@ CFGBlock *CFGBuilder::VisitForStmt(ForStmt *F) {
 
   addAutomaticObjHandling(ScopePos, save_scope_pos.get(), F);
 
+  addLoopExit(F);
+
   // "for" is a control-flow statement.  Thus we stop processing the current
   // block.
   if (Block) {
@@ -2882,6 +2899,7 @@ CFGBlock *CFGBuilder::VisitWhileStmt(WhileStmt *W) {
     addLocalScopeForVarDecl(VD);
     addAutomaticObjHandling(ScopePos, LoopBeginScopePos, W);
   }
+  addLoopExit(W);
 
   // "while" is a control-flow statement.  Thus we stop processing the current
   // block.
@@ -3045,6 +3063,8 @@ CFGBlock *CFGBuilder::VisitCXXThrowExpr(CXXThrowExpr *T) {
 CFGBlock *CFGBuilder::VisitDoStmt(DoStmt *D) {
   CFGBlock *LoopSuccessor = nullptr;
 
+  addLoopExit(D);
+
   // "do...while" is a control-flow statement.  Thus we stop processing the
   // current block.
   if (Block) {
@@ -4025,6 +4045,7 @@ CFGImplicitDtor::getDestructorDecl(ASTContext &astContext) const {
     case CFGElement::Statement:
     case CFGElement::Initializer:
     case CFGElement::NewAllocator:
+    case CFGElement::LoopExit:
     case CFGElement::LifetimeEnds:
       llvm_unreachable("getDestructorDecl should only be used with "
                        "ImplicitDtors");
@@ -4442,6 +4463,9 @@ static void print_elem(raw_ostream &OS, StmtPrinterHelper &Helper,
 
     OS << " (Lifetime ends)\n";
 
+  } else if (Optional<CFGLoopExit> LE = E.getAs<CFGLoopExit>()) {
+    const Stmt *LoopStmt = LE->getLoopStmt();
+    OS << LoopStmt->getStmtClassName() << " (LoopExit)\n";
   } else if (Optional<CFGNewAllocator> NE = E.getAs<CFGNewAllocator>()) {
     OS << "CFGNewAllocator(";
     if (const CXXNewExpr *AllocExpr = NE->getAllocatorExpr())