Index: include/clang/Analysis/AnalysisContext.h =================================================================== --- include/clang/Analysis/AnalysisContext.h +++ include/clang/Analysis/AnalysisContext.h @@ -427,6 +427,7 @@ bool addInitializers = false, bool addTemporaryDtors = false, bool addLifetime = false, + bool addLoopExit = false, bool synthesizeBodies = false, bool addStaticInitBranches = false, bool addCXXNewAllocator = true, Index: include/clang/Analysis/CFG.h =================================================================== --- include/clang/Analysis/CFG.h +++ include/clang/Analysis/CFG.h @@ -59,6 +59,7 @@ Initializer, NewAllocator, LifetimeEnds, + LoopExit, // dtor kind AutomaticObjectDtor, DeleteDtor, @@ -168,6 +169,24 @@ } }; +/// 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(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: @@ -728,6 +747,10 @@ 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); } @@ -794,6 +817,7 @@ bool AddInitializers; bool AddImplicitDtors; bool AddLifetime; + bool AddLoopExit; bool AddTemporaryDtors; bool AddStaticInitBranches; bool AddCXXNewAllocator; @@ -818,7 +842,7 @@ PruneTriviallyFalseEdges(true), AddEHEdges(false), AddInitializers(false), AddImplicitDtors(false), - AddLifetime(false), + AddLifetime(false), AddLoopExit(false), AddTemporaryDtors(false), AddStaticInitBranches(false), AddCXXNewAllocator(false), AddCXXDefaultInitExprInCtors(false) {} }; Index: include/clang/StaticAnalyzer/Core/AnalyzerOptions.h =================================================================== --- include/clang/StaticAnalyzer/Core/AnalyzerOptions.h +++ include/clang/StaticAnalyzer/Core/AnalyzerOptions.h @@ -214,6 +214,9 @@ /// \sa IncludeLifetimeInCFG Optional IncludeLifetimeInCFG; + /// \sa IncludeLoopExitInCFG + Optional IncludeLoopExitInCFG; + /// \sa mayInlineCXXStandardLibrary Optional InlineCXXStandardLibrary; @@ -415,6 +418,13 @@ /// 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. /// Index: lib/Analysis/AnalysisDeclContext.cpp =================================================================== --- lib/Analysis/AnalysisDeclContext.cpp +++ lib/Analysis/AnalysisDeclContext.cpp @@ -68,6 +68,7 @@ bool addInitializers, bool addTemporaryDtors, bool addLifetime, + bool addLoopExit, bool synthesizeBodies, bool addStaticInitBranch, bool addCXXNewAllocator, @@ -79,6 +80,7 @@ cfgBuildOptions.AddInitializers = addInitializers; cfgBuildOptions.AddTemporaryDtors = addTemporaryDtors; cfgBuildOptions.AddLifetime = addLifetime; + cfgBuildOptions.AddLoopExit = addLoopExit; cfgBuildOptions.AddStaticInitBranches = addStaticInitBranch; cfgBuildOptions.AddCXXNewAllocator = addCXXNewAllocator; } Index: lib/Analysis/CFG.cpp =================================================================== --- lib/Analysis/CFG.cpp +++ lib/Analysis/CFG.cpp @@ -602,6 +602,7 @@ return Visit(S, AddStmtChoice::AlwaysAdd); } CFGBlock *addInitializer(CXXCtorInitializer *I); + void addLoopExit(CFGBlock* B, 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 @@ 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()); } @@ -1253,6 +1258,15 @@ return Init->getType(); } + +// TODO: Support adding LoopExit element to the CFG in case where the loop is +// ended by ReturnStmt. +void CFGBuilder::addLoopExit(CFGBlock* B, const Stmt* LoopStmt){ + if(!BuildOpts.AddLoopExit) + return; + appendLoopExit(B, LoopStmt); +} + void CFGBuilder::addAutomaticObjHandling(LocalScope::const_iterator B, LocalScope::const_iterator E, Stmt *S) { @@ -2557,6 +2571,8 @@ SaveAndRestore save_break(BreakJumpTarget); BreakJumpTarget = JumpTarget(LoopSuccessor, ScopePos); + addLoopExit(LoopSuccessor, F); + CFGBlock *BodyBlock = nullptr, *TransitionBlock = nullptr; // Now create the loop body. @@ -2896,6 +2912,8 @@ CFGBlock *BodyBlock = nullptr, *TransitionBlock = nullptr; + addLoopExit(LoopSuccessor, W); + // Process the loop body. { assert(W->getBody()); @@ -3054,6 +3072,8 @@ } else LoopSuccessor = Succ; + addLoopExit(LoopSuccessor,D); + // Because of short-circuit evaluation, the condition of the loop can span // multiple basic blocks. Thus we need the "Entry" and "Exit" blocks that // evaluate the condition. @@ -4025,6 +4045,7 @@ 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 @@ OS << " (Lifetime ends)\n"; + } else if (Optional LE = E.getAs()) { + const Stmt *LoopStmt = LE->getLoopStmt(); + OS << LoopStmt->getStmtClassName() << " (LoopExit)\n"; } else if (Optional NE = E.getAs()) { OS << "CFGNewAllocator("; if (const CXXNewExpr *AllocExpr = NE->getAllocatorExpr()) Index: lib/StaticAnalyzer/Core/AnalysisManager.cpp =================================================================== --- lib/StaticAnalyzer/Core/AnalysisManager.cpp +++ lib/StaticAnalyzer/Core/AnalysisManager.cpp @@ -26,7 +26,8 @@ Options.includeImplicitDtorsInCFG(), /*AddInitializers=*/true, Options.includeTemporaryDtorsInCFG(), - Options.includeLifetimeInCFG(), + Options.includeLifetimeInCFG(), + Options.includeLoopExitInCFG(), Options.shouldSynthesizeBodies(), Options.shouldConditionalizeStaticInitializers(), /*addCXXNewAllocator=*/true, Index: lib/StaticAnalyzer/Core/AnalyzerOptions.cpp =================================================================== --- lib/StaticAnalyzer/Core/AnalyzerOptions.cpp +++ lib/StaticAnalyzer/Core/AnalyzerOptions.cpp @@ -183,6 +183,11 @@ /* Default = */ false); } +bool AnalyzerOptions::includeLoopExitInCFG() { + return getBooleanOption(IncludeLoopExitInCFG, "cfg-loopexit", + /* Default = */ false); +} + bool AnalyzerOptions::mayInlineCXXStandardLibrary() { return getBooleanOption(InlineCXXStandardLibrary, "c++-stdlib-inlining", Index: lib/StaticAnalyzer/Core/ExprEngine.cpp =================================================================== --- lib/StaticAnalyzer/Core/ExprEngine.cpp +++ lib/StaticAnalyzer/Core/ExprEngine.cpp @@ -363,6 +363,7 @@ ProcessImplicitDtor(E.castAs(), Pred); return; case CFGElement::LifetimeEnds: + case CFGElement::LoopExit: return; } } Index: lib/StaticAnalyzer/Core/PathDiagnostic.cpp =================================================================== --- lib/StaticAnalyzer/Core/PathDiagnostic.cpp +++ lib/StaticAnalyzer/Core/PathDiagnostic.cpp @@ -579,6 +579,7 @@ case CFGElement::TemporaryDtor: case CFGElement::NewAllocator: case CFGElement::LifetimeEnds: + case CFGElement::LoopExit: llvm_unreachable("not yet implemented!"); } Index: test/Analysis/analyzer-config.c =================================================================== --- test/Analysis/analyzer-config.c +++ test/Analysis/analyzer-config.c @@ -14,6 +14,7 @@ // 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 @@ -29,4 +30,4 @@ // CHECK-NEXT: region-store-small-struct-limit = 2 // CHECK-NEXT: widen-loops = false // CHECK-NEXT: [stats] -// CHECK-NEXT: num-entries = 17 +// CHECK-NEXT: num-entries = 18 Index: test/Analysis/analyzer-config.cpp =================================================================== --- test/Analysis/analyzer-config.cpp +++ test/Analysis/analyzer-config.cpp @@ -25,6 +25,7 @@ // 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 @@ -40,4 +41,4 @@ // CHECK-NEXT: region-store-small-struct-limit = 2 // CHECK-NEXT: widen-loops = false // CHECK-NEXT: [stats] -// CHECK-NEXT: num-entries = 22 +// CHECK-NEXT: num-entries = 23 Index: test/Analysis/loopexit-cfg-output.cpp =================================================================== --- /dev/null +++ test/Analysis/loopexit-cfg-output.cpp @@ -0,0 +1,177 @@ +// RUN: %clang_cc1 -analyze -analyzer-checker=debug.DumpCFG -analyzer-config cfg-loopexit=true %s > %t 2>&1 +// RUN: FileCheck --input-file=%t %s + +// CHECK: [B5 (ENTRY)] +// CHECK-NEXT: Succs (1): B4 + +// CHECK: [B1] +// CHECK-NEXT: 1: i +// CHECK-NEXT: 2: [B1.1]++ +// CHECK-NEXT: Preds (1): B2 +// CHECK-NEXT: Succs (1): B3 + +// CHECK: [B2] +// CHECK-NEXT: 1: i +// CHECK-NEXT: 2: [B2.1]++ +// CHECK-NEXT: Preds (1): B3 +// CHECK-NEXT: Succs (1): B1 + +// CHECK: [B3] +// CHECK-NEXT: 1: i +// CHECK-NEXT: 2: [B3.1] (ImplicitCastExpr, LValueToRValue, int) +// CHECK-NEXT: 3: 12 +// CHECK-NEXT: 4: [B3.2] < [B3.3] +// CHECK-NEXT: T: for (...; [B3.4]; ...) +// CHECK-NEXT: Preds (2): B1 B4 +// CHECK-NEXT: Succs (2): B2 B0 + +// CHECK: [B4] +// CHECK-NEXT: 1: 0 +// CHECK-NEXT: 2: int i = 0; +// CHECK-NEXT: Preds (1): B5 +// CHECK-NEXT: Succs (1): B3 + +// CHECK: [B0 (EXIT)] +// CHECK-NEXT: 1: ForStmt (LoopExit) +// CHECK-NEXT: Preds (1): B3 +void check_forloop1() { + for (int i = 0; i < 12; i++) { + i++; + } +} + +// CHECK: [B3 (ENTRY)] +// CHECK-NEXT: Succs (1): B2 + +// CHECK: [B1] +// CHECK-NEXT: Preds (1): B2 +// CHECK-NEXT: Succs (1): B2 + +// CHECK: [B2] +// CHECK-NEXT: T: for (; ; ) +// CHECK-NEXT: Preds (2): B1 B3 +// CHECK-NEXT: Succs (2): B1 NULL + +// CHECK: [B0 (EXIT)] +// CHECK-NEXT: 1: ForStmt (LoopExit) +void check_forloop2() { + for (;;) + ; +} + +// CHECK: [B4 (ENTRY)] +// CHECK-NEXT: Succs (1): B3 + +// CHECK: [B1] +// CHECK-NEXT: Preds (1): B2 +// CHECK-NEXT: Succs (1): B3 + +// CHECK: [B2] +// CHECK-NEXT: 1: int i; +// CHECK-NEXT: Preds (1): B3 +// CHECK-NEXT: Succs (1): B1 + +// CHECK: [B3] +// CHECK-NEXT: 1: true +// CHECK-NEXT: T: while [B3.1] +// CHECK-NEXT: Preds (2): B1 B4 +// CHECK-NEXT: Succs (2): B2 NULL + +// CHECK: [B0 (EXIT)] +// CHECK-NEXT: 1: WhileStmt (LoopExit) +void check_while1() { + while (true) { + int i; + } +} + +// CHECK: [B4 (ENTRY)] +// CHECK-NEXT: Succs (1): B3 + +// CHECK: [B1] +// CHECK-NEXT: Preds (1): B2 +// CHECK-NEXT: Succs (1): B2 + +// CHECK: [B2] +// CHECK-NEXT: 1: l +// CHECK-NEXT: 2: [B2.1] (ImplicitCastExpr, LValueToRValue, int) +// CHECK-NEXT: 3: 42 +// CHECK-NEXT: 4: [B2.2] < [B2.3] +// CHECK-NEXT: T: while [B2.4] +// CHECK-NEXT: Preds (2): B1 B3 +// CHECK-NEXT: Succs (2): B1 B0 + +// CHECK: [B3] +// CHECK-NEXT: 1: int l; +// CHECK-NEXT: Preds (1): B4 +// CHECK-NEXT: Succs (1): B2 + +// CHECK: [B0 (EXIT)] +// CHECK-NEXT: 1: WhileStmt (LoopExit) +// CHECK-NEXT: Preds (1): B2 + +void check_while2() { + int l; + while (l < 42) + ; +} + +// CHECK: [B3 (ENTRY)] +// CHECK-NEXT: Succs (1): B1 + +// CHECK: [B1] +// CHECK-NEXT: 1: false +// CHECK-NEXT: T: do ... while [B1.1] +// CHECK-NEXT: Preds (2): B2 B3 +// CHECK-NEXT: Succs (2): NULL B0 + +// CHECK: [B2] +// CHECK-NEXT: Succs (1): B1 + +// CHECK: [B0 (EXIT)] +// CHECK-NEXT: 1: DoStmt (LoopExit) +// CHECK-NEXT: Preds (1): B1 + +void check_dowhile1() { + do { + } while (false); +} + +// CHECK: [B5 (ENTRY)] +// CHECK-NEXT: Succs (1): B4 + +// CHECK: [B1] +// CHECK-NEXT: 1: j +// CHECK-NEXT: 2: [B1.1] (ImplicitCastExpr, LValueToRValue, int) +// CHECK-NEXT: 3: 20 +// CHECK-NEXT: 4: [B1.2] < [B1.3] +// CHECK-NEXT: T: do ... while [B1.4] +// CHECK-NEXT: Preds (1): B2 +// CHECK-NEXT: Succs (2): B3 B0 + +// CHECK: [B2] +// CHECK-NEXT: 1: j +// CHECK-NEXT: 2: 2 +// CHECK-NEXT: 3: [B2.1] += [B2.2] +// CHECK-NEXT: Preds (2): B3 B4 +// CHECK-NEXT: Succs (1): B1 + +// CHECK: [B3] +// CHECK-NEXT: Preds (1): B1 +// CHECK-NEXT: Succs (1): B2 + +// CHECK: [B4] +// CHECK-NEXT: 1: 2 +// CHECK-NEXT: 2: int j = 2; +// CHECK-NEXT: Preds (1): B5 +// CHECK-NEXT: Succs (1): B2 + +// CHECK: [B0 (EXIT)] +// CHECK-NEXT: 1: DoStmt (LoopExit) +// CHECK-NEXT: Preds (1): B1 +void check_dowhile2() { + int j = 2; + do { + j += 2; + } while (j < 20); +}