[CFG] Add LoopExit information to CFG

[szepet]

Summary

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.

[szepet]

Adding new block when the loop successor is the ExitBlock.
Test cases updated.

[szepet]

Updated test cases to fit on trunk.

[szepet]

Accidentally left debug print removed.

[szepet]

Wrong diff updated last time, fixed it.

[NoQ]

CFG construction tests seem to have accidentally disappeared from the recent revisions.

lib/StaticAnalyzer/Core/PathDiagnostic.cpp

581–583

Can these two actually be call sites, ever? If we don't intend that, maybe give them their own llvm_unreachable with a different comment?

[szepet]

Test file re-added.
CFGElement::LoopExit and LifetimeEnds separated into their own caseStmt.

[szepet]

lib/StaticAnalyzer/Core/PathDiagnostic.cpp

581–583

Not sure about the comment string so if you have a better idea or just don't like this one, please let me know!

[dcoughlin]

This is incomplete, but seems like it is moving in the direction of where we want to ultimately end up. I have some minor comments inline, but otherwise this seems reasonable. I think it is very important to document the new element clearly and indicate that it is currently incomplete and intended only for consumption by the static analyzer.

include/clang/Analysis/CFG.h

173

Can you add a comment indicating that this is only produced when the cfg-loopexit analyzer config flag is true and also say that it is only produced when building the CFG for the static analyzer. This way other consumers of the CFG will know they don't need to handle it.

It would also be good to document that a loop exit element can be reached even when the loop body was never entered. Please add a test for while (false) { ... }.

750

Can you add a comment explaining that S should be a looping statement and also change the name from S to something more evocative. This will make it more clear how the method is intended to be called.

lib/Analysis/CFG.cpp

605

The '*' here doesn't match the style of the surrounding code.

656

Can you rename 'S' to something more evocative ('LoopStmt', perhaps).

1263

You should also mention 'throw' and 'goto'. Do you handle 'break' correctly? If so, please add tests. If not, add it to this list of unhandled constructs in this comment.

And (super nit) add a space before "TODO".

[szepet]

Updates based on comments.

[dcoughlin]

Looks good to me me. Thanks!

include/clang/Analysis/AnalysisContext.h

class AnalysisDeclContextManager {
   bool SynthesizeBodies;
 
 public:
   AnalysisDeclContextManager(bool useUnoptimizedCFG = false,
                              bool addImplicitDtors = false,
                              bool addInitializers = false,
                              bool addTemporaryDtors = false,
                              bool addLifetime = false,
+                             bool addLoopExit = false,
                              bool synthesizeBodies = false,
                              bool addStaticInitBranches = false,
                              bool addCXXNewAllocator = true,
                              CodeInjector* injector = nullptr);
 
   ~AnalysisDeclContextManager();
 
   AnalysisDeclContext *getContext(const Decl *D);

include/clang/Analysis/CFG.h

 class CFGElement {
 public:
   enum Kind {
     // main kind
     Statement,
     Initializer,
     NewAllocator,
     LifetimeEnds,
+    LoopExit,
     // dtor kind
     AutomaticObjectDtor,
     DeleteDtor,
     BaseDtor,
     MemberDtor,
     TemporaryDtor,
     DTOR_BEGIN = AutomaticObjectDtor,
     DTOR_END = TemporaryDtor

 private:
   friend class CFGElement;
   CFGNewAllocator() {}
   static bool isKind(const CFGElement &elem) {
     return elem.getKind() == NewAllocator;
   }
 };
 
+/// Represents the point where a loop ends.
+class CFGLoopExit : public CFGElement {
+public:
+    explicit CFGLoopExit(const Stmt *stmt)
+            : CFGElement(LoopExit, stmt) {}
+
+    const Stmt *getLoopStmt() const {
+      return static_cast<Stmt *>(Data1.getPointer());
+    }
+
+private:
+    friend class CFGElement;
+    CFGLoopExit() {}
+    static bool isKind(const CFGElement &elem) {
+      return elem.getKind() == LoopExit;
+    }
+};
+
 /// Represents the point where the lifetime of an automatic object ends
 class CFGLifetimeEnds : public CFGElement {
 public:
   explicit CFGLifetimeEnds(const VarDecl *var, const Stmt *stmt)
       : CFGElement(LifetimeEnds, var, stmt) {}
 
   const VarDecl *getVarDecl() const {
     return static_cast<VarDecl *>(Data1.getPointer());
public:
   void appendAutomaticObjDtor(VarDecl *VD, Stmt *S, BumpVectorContext &C) {
     Elements.push_back(CFGAutomaticObjDtor(VD, S), C);
   }
 
   void appendLifetimeEnds(VarDecl *VD, Stmt *S, BumpVectorContext &C) {
     Elements.push_back(CFGLifetimeEnds(VD, S), C);
   }
 
+  void appendLoopExit(const Stmt *S, BumpVectorContext &C) {
+    Elements.push_back(CFGLoopExit(S), C);
+  }
+
   void appendDeleteDtor(CXXRecordDecl *RD, CXXDeleteExpr *DE, BumpVectorContext &C) {
     Elements.push_back(CFGDeleteDtor(RD, DE), C);
   }
 
   // Destructors must be inserted in reversed order. So insertion is in two
   // steps. First we prepare space for some number of elements, then we insert
   // the elements beginning at the last position in prepared space.
   iterator beginAutomaticObjDtorsInsert(iterator I, size_t Cnt,
public:
     typedef llvm::DenseMap<const Stmt *, const CFGBlock*> ForcedBlkExprs;
     ForcedBlkExprs **forcedBlkExprs;
     CFGCallback *Observer;
     bool PruneTriviallyFalseEdges;
     bool AddEHEdges;
     bool AddInitializers;
     bool AddImplicitDtors;
     bool AddLifetime;
+    bool AddLoopExit;
     bool AddTemporaryDtors;
     bool AddStaticInitBranches;
     bool AddCXXNewAllocator;
     bool AddCXXDefaultInitExprInCtors;
 
     bool alwaysAdd(const Stmt *stmt) const {
       return alwaysAddMask[stmt->getStmtClass()];
     }
 
     BuildOptions &setAlwaysAdd(Stmt::StmtClass stmtClass, bool val = true) {
       alwaysAddMask[stmtClass] = val;
       return *this;
     }
 
     BuildOptions &setAllAlwaysAdd() {
       alwaysAddMask.set();
       return *this;
     }
 
     BuildOptions()
       : forcedBlkExprs(nullptr), Observer(nullptr),
         PruneTriviallyFalseEdges(true),
         AddEHEdges(false),
         AddInitializers(false), AddImplicitDtors(false),
-        AddLifetime(false),
+        AddLifetime(false), AddLoopExit(false),
         AddTemporaryDtors(false), AddStaticInitBranches(false),
         AddCXXNewAllocator(false), AddCXXDefaultInitExprInCtors(false) {}
   };
 
   /// buildCFG - Builds a CFG from an AST.
   static std::unique_ptr<CFG> buildCFG(const Decl *D, Stmt *AST, ASTContext *C,
                                        const BuildOptions &BO);
 

include/clang/StaticAnalyzer/Core/AnalyzerOptions.h

private:
   Optional<bool> IncludeImplicitDtorsInCFG;
 
   /// \sa includeTemporaryDtorsInCFG
   Optional<bool> IncludeTemporaryDtorsInCFG;
 
   /// \sa IncludeLifetimeInCFG
   Optional<bool> IncludeLifetimeInCFG;
 
+  /// \sa IncludeLoopExitInCFG
+  Optional<bool> IncludeLoopExitInCFG;
+
   /// \sa mayInlineCXXStandardLibrary
   Optional<bool> InlineCXXStandardLibrary;
   
   /// \sa mayInlineTemplateFunctions
   Optional<bool> InlineTemplateFunctions;
 
   /// \sa mayInlineCXXAllocator
   Optional<bool> InlineCXXAllocator;
public:
 
   /// Returns whether or not end-of-lifetime information should be included in
   /// the CFG.
   ///
   /// This is controlled by the 'cfg-lifetime' config option, which accepts
   /// the values "true" and "false".
   bool includeLifetimeInCFG();
 
+  /// Returns whether or not the end of the loop information should be included
+  /// in the CFG.
+  ///
+  /// This is controlled by the 'cfg-loopexit' config option, which accepts
+  /// the values "true" and "false".
+  bool includeLoopExitInCFG();
+
   /// Returns whether or not C++ standard library functions may be considered
   /// for inlining.
   ///
   /// This is controlled by the 'c++-stdlib-inlining' config option, which
   /// accepts the values "true" and "false".
   bool mayInlineCXXStandardLibrary();
 
   /// Returns whether or not templated functions may be considered for inlining.

lib/Analysis/AnalysisDeclContext.cpp

: Manager(Mgr),
   cfgBuildOptions.forcedBlkExprs = &forcedBlkExprs;
 }
 
 AnalysisDeclContextManager::AnalysisDeclContextManager(bool useUnoptimizedCFG,
                                                        bool addImplicitDtors,
                                                        bool addInitializers,
                                                        bool addTemporaryDtors,
                                                        bool addLifetime,
+                                                       bool addLoopExit,
                                                        bool synthesizeBodies,
                                                        bool addStaticInitBranch,
                                                        bool addCXXNewAllocator,
                                                        CodeInjector *injector)
   : Injector(injector), SynthesizeBodies(synthesizeBodies)
 {
   cfgBuildOptions.PruneTriviallyFalseEdges = !useUnoptimizedCFG;
   cfgBuildOptions.AddImplicitDtors = addImplicitDtors;
   cfgBuildOptions.AddInitializers = addInitializers;
   cfgBuildOptions.AddTemporaryDtors = addTemporaryDtors;
   cfgBuildOptions.AddLifetime = addLifetime;
+  cfgBuildOptions.AddLoopExit = addLoopExit;
   cfgBuildOptions.AddStaticInitBranches = addStaticInitBranch;
   cfgBuildOptions.AddCXXNewAllocator = addCXXNewAllocator;
 }
 
 void AnalysisDeclContextManager::clear() { Contexts.clear(); }
 
 static BodyFarm &getBodyFarm(ASTContext &C, CodeInjector *injector = nullptr) {
   static BodyFarm *BF = new BodyFarm(C, injector);

lib/Analysis/CFG.cpp

private:
   void autoCreateBlock() { if (!Block) Block = createBlock(); }
   CFGBlock *createBlock(bool add_successor = true);
   CFGBlock *createNoReturnBlock();
 
   CFGBlock *addStmt(Stmt *S) {
     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,
                        LocalScope::const_iterator E, Stmt *S);
   void addAutomaticObjHandling(LocalScope::const_iterator B,
                                LocalScope::const_iterator E, Stmt *S);
   void addImplicitDtorsForDestructor(const CXXDestructorDecl *DD);
 
private:
   void appendAutomaticObjDtor(CFGBlock *B, VarDecl *VD, Stmt *S) {
     B->appendAutomaticObjDtor(VD, S, cfg->getBumpVectorContext());
   }
 
   void appendLifetimeEnds(CFGBlock *B, VarDecl *VD, Stmt *S) {
     B->appendLifetimeEnds(VD, S, cfg->getBumpVectorContext());
   }
 
+  void appendLoopExit(CFGBlock *B, const Stmt *S) {
+    B->appendLoopExit(S, cfg->getBumpVectorContext());
+  }
+
   void appendDeleteDtor(CFGBlock *B, CXXRecordDecl *RD, CXXDeleteExpr *DE) {
     B->appendDeleteDtor(RD, DE, cfg->getBumpVectorContext());
   }
 
   void prependAutomaticObjDtorsWithTerminator(CFGBlock *Blk,
       LocalScope::const_iterator B, LocalScope::const_iterator E);
 
   void prependAutomaticObjLifetimeWithTerminator(CFGBlock *Blk,
while (true) {
     }
     
     break;
   }
 
   return Init->getType();
 }
 
+
+//TODO: Support adding LoopExit element to the CFG in case where the loop is
+// ended by ReturnStmt.
+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) {
   if (BuildOpts.AddImplicitDtors)
     addAutomaticObjDtors(B, E, S);
   if (BuildOpts.AddLifetime)
     addLifetimeEnds(B, E, S);
 }
CFGBlock *CFGBuilder::VisitForStmt(ForStmt *F) {
   LocalScope::const_iterator LoopBeginScopePos = ScopePos;
 
   if (VarDecl *VD = F->getConditionVariable())
     addLocalScopeForVarDecl(VD);
   LocalScope::const_iterator ContinueScopePos = ScopePos;
 
   addAutomaticObjHandling(ScopePos, save_scope_pos.get(), F);
 
+  addLoopExit(F);
+
   // "for" is a control-flow statement.  Thus we stop processing the current
   // block.
   if (Block) {
     if (badCFG)
       return nullptr;
     LoopSuccessor = Block;
   } else
     LoopSuccessor = Succ;
CFGBlock *CFGBuilder::VisitWhileStmt(WhileStmt *W) {
 
   // Create local scope for possible condition variable.
   // Store scope position for continue statement.
   LocalScope::const_iterator LoopBeginScopePos = ScopePos;
   if (VarDecl *VD = W->getConditionVariable()) {
     addLocalScopeForVarDecl(VD);
     addAutomaticObjHandling(ScopePos, LoopBeginScopePos, W);
   }
+  addLoopExit(W);
 
   // "while" is a control-flow statement.  Thus we stop processing the current
   // block.
   if (Block) {
     if (badCFG)
       return nullptr;
     LoopSuccessor = Block;
     Block = nullptr;
CFGBlock *CFGBuilder::VisitCXXThrowExpr(CXXThrowExpr *T) {
   // Add the statement to the block.  This may create new blocks if S contains
   // control-flow (short-circuit operations).
   return VisitStmt(T, AddStmtChoice::AlwaysAdd);
 }
 
 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) {
     if (badCFG)
       return nullptr;
     LoopSuccessor = Block;
   } else
     LoopSuccessor = Succ;

 }
 
 const CXXDestructorDecl *
 CFGImplicitDtor::getDestructorDecl(ASTContext &astContext) const {
   switch (getKind()) {
     case CFGElement::Statement:
     case CFGElement::Initializer:
     case CFGElement::NewAllocator:
+    case CFGElement::LoopExit:
     case CFGElement::LifetimeEnds:
       llvm_unreachable("getDestructorDecl should only be used with "
                        "ImplicitDtors");
     case CFGElement::AutomaticObjectDtor: {
       const VarDecl *var = castAs<CFGAutomaticObjDtor>().getVarDecl();
       QualType ty = var->getType();
 
       // FIXME: See CFGBuilder::addLocalScopeForVarDecl.
if (Optional<CFGStmt> CS = E.getAs<CFGStmt>()) {
     OS << " (Implicit destructor)\n";
 
   } else if (Optional<CFGLifetimeEnds> DE = E.getAs<CFGLifetimeEnds>()) {
     const VarDecl *VD = DE->getVarDecl();
     Helper.handleDecl(VD, OS);
 
     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())
       AllocExpr->getType().print(OS, PrintingPolicy(Helper.getLangOpts()));
     OS << ")\n";
   } else if (Optional<CFGDeleteDtor> DE = E.getAs<CFGDeleteDtor>()) {
     const CXXRecordDecl *RD = DE->getCXXRecordDecl();
     if (!RD)

lib/StaticAnalyzer/Core/AnalysisManager.cpp

AnalysisManager::AnalysisManager(ASTContext &ctx, DiagnosticsEngine &diags,
                                  ConstraintManagerCreator constraintmgr,
                                  CheckerManager *checkerMgr,
                                  AnalyzerOptions &Options,
                                  CodeInjector *injector)
   : AnaCtxMgr(Options.UnoptimizedCFG,
               Options.includeImplicitDtorsInCFG(),
               /*AddInitializers=*/true,
               Options.includeTemporaryDtorsInCFG(),
-        Options.includeLifetimeInCFG(),
+              Options.includeLifetimeInCFG(),
+              Options.includeLoopExitInCFG(),
               Options.shouldSynthesizeBodies(),
               Options.shouldConditionalizeStaticInitializers(),
               /*addCXXNewAllocator=*/true,
               injector),
     Ctx(ctx),
     Diags(diags),
     LangOpts(lang),
     PathConsumers(PDC),

lib/StaticAnalyzer/Core/AnalyzerOptions.cpp

return getBooleanOption(IncludeImplicitDtorsInCFG,
                           /* Default = */ true);
 }
 
 bool AnalyzerOptions::includeLifetimeInCFG() {
   return getBooleanOption(IncludeLifetimeInCFG, "cfg-lifetime",
                           /* Default = */ false);
 }
 
+bool AnalyzerOptions::includeLoopExitInCFG() {
+  return getBooleanOption(IncludeLoopExitInCFG, "cfg-loopexit",
+          /* Default = */ false);
+}
+
 bool AnalyzerOptions::mayInlineCXXStandardLibrary() {
   return getBooleanOption(InlineCXXStandardLibrary,
                           "c++-stdlib-inlining",
                           /*Default=*/true);
 }
 
 bool AnalyzerOptions::mayInlineTemplateFunctions() {
   return getBooleanOption(InlineTemplateFunctions,

lib/StaticAnalyzer/Core/ExprEngine.cpp

switch (E.getKind()) {
     case CFGElement::AutomaticObjectDtor:
     case CFGElement::DeleteDtor:
     case CFGElement::BaseDtor:
     case CFGElement::MemberDtor:
     case CFGElement::TemporaryDtor:
       ProcessImplicitDtor(E.castAs<CFGImplicitDtor>(), Pred);
       return;
     case CFGElement::LifetimeEnds:
+    case CFGElement::LoopExit:
       return;
   }
 }
 
 static bool shouldRemoveDeadBindings(AnalysisManager &AMgr,
                                      const CFGStmt S,
                                      const ExplodedNode *Pred,
                                      const LocationContext *LC) {

lib/StaticAnalyzer/Core/PathDiagnostic.cpp

getLocationForCaller(const StackFrameContext *SFC,
   case CFGElement::MemberDtor: {
     const AnalysisDeclContext *CallerInfo = CallerCtx->getAnalysisDeclContext();
     if (const Stmt *CallerBody = CallerInfo->getBody())
       return PathDiagnosticLocation::createEnd(CallerBody, SM, CallerCtx);
     return PathDiagnosticLocation::create(CallerInfo->getDecl(), SM);
   }
   case CFGElement::TemporaryDtor:
   case CFGElement::NewAllocator:
   case CFGElement::LifetimeEnds:
+  case CFGElement::LoopExit:
     llvm_unreachable("not yet implemented!");
   }
 
   llvm_unreachable("Unknown CFGElement kind");
 }
 
 PathDiagnosticLocation
 PathDiagnosticLocation::createBegin(const Decl *D,
                                     const SourceManager &SM) {

test/Analysis/analyzer-config.c

 // RUN: %clang_analyze_cc1 -triple x86_64-apple-darwin10 %s -o /dev/null -analyzer-checker=core,osx.cocoa,debug.ConfigDumper -analyzer-max-loop 34 > %t 2>&1
 // RUN: FileCheck --input-file=%t %s
 
 void bar() {}
 void foo() {
   // Call bar 33 times so max-times-inline-large is met and
   // min-blocks-for-inline-large is checked
   for (int i = 0; i < 34; ++i) {
     bar();
   }
 }
 
 // CHECK: [config]
 // CHECK-NEXT: cfg-conditional-static-initializers = true
 // CHECK-NEXT: cfg-implicit-dtors = true
 // CHECK-NEXT: cfg-lifetime = false
+// CHECK-NEXT: cfg-loopexit = false
 // CHECK-NEXT: cfg-temporary-dtors = false
 // CHECK-NEXT: faux-bodies = true
 // CHECK-NEXT: graph-trim-interval = 1000
 // CHECK-NEXT: inline-lambdas = true
 // CHECK-NEXT: ipa = dynamic-bifurcate
 // CHECK-NEXT: ipa-always-inline-size = 3
 // CHECK-NEXT: leak-diagnostics-reference-allocation = false
 // CHECK-NEXT: max-inlinable-size = 100
 // CHECK-NEXT: max-nodes = 225000
 // CHECK-NEXT: max-times-inline-large = 32
 // CHECK-NEXT: min-cfg-size-treat-functions-as-large = 14
 // CHECK-NEXT: mode = deep
 // CHECK-NEXT: region-store-small-struct-limit = 2
 // CHECK-NEXT: unroll-loops = false
 // CHECK-NEXT: widen-loops = false
 // CHECK-NEXT: [stats]
-// CHECK-NEXT: num-entries = 18
+// CHECK-NEXT: num-entries = 19

test/Analysis/analyzer-config.cpp

 // CHECK-NEXT: c++-container-inlining = false
 // CHECK-NEXT: c++-inlining = destructors
 // CHECK-NEXT: c++-shared_ptr-inlining = false
 // CHECK-NEXT: c++-stdlib-inlining = true
 // CHECK-NEXT: c++-template-inlining = true
 // CHECK-NEXT: cfg-conditional-static-initializers = true
 // CHECK-NEXT: cfg-implicit-dtors = true
 // CHECK-NEXT: cfg-lifetime = false
+// CHECK-NEXT: cfg-loopexit = false
 // CHECK-NEXT: cfg-temporary-dtors = false
 // CHECK-NEXT: faux-bodies = true
 // CHECK-NEXT: graph-trim-interval = 1000
 // CHECK-NEXT: inline-lambdas = true
 // CHECK-NEXT: ipa = dynamic-bifurcate
 // CHECK-NEXT: ipa-always-inline-size = 3
 // CHECK-NEXT: leak-diagnostics-reference-allocation = false
 // CHECK-NEXT: max-inlinable-size = 100
 // CHECK-NEXT: max-nodes = 225000
 // CHECK-NEXT: max-times-inline-large = 32
 // CHECK-NEXT: min-cfg-size-treat-functions-as-large = 14
 // CHECK-NEXT: mode = deep
 // CHECK-NEXT: region-store-small-struct-limit = 2
 // CHECK-NEXT: unroll-loops = false
 // CHECK-NEXT: widen-loops = false
 // CHECK-NEXT: [stats]
-// CHECK-NEXT: num-entries = 23
+// CHECK-NEXT: num-entries = 24