Index: include/clang/Analysis/CFG.h =================================================================== --- include/clang/Analysis/CFG.h +++ include/clang/Analysis/CFG.h @@ -59,6 +59,7 @@ Initializer, NewAllocator, LifetimeEnds, + LoopEntrance, LoopExit, // dtor kind AutomaticObjectDtor, @@ -175,6 +176,32 @@ } }; +/// Represents the point where a loop begins. This element is encountered right +/// before the first loop element. This element is is only produced when +/// building the CFG for the static analyzer and hidden behind the +/// 'cfg-loopexit' analyzer config flag. +/// In case of a ForStmt which contains an InitStmt it is placed directly before +/// the CFGStmts of the initialization (in the same block). In case of a +/// WhileStmt/DoStmt/ForStmt without InitStmt it appears at the end of the +/// previous block (before the loop). However, if we step in to the loop via a +/// gotoStmt then the CFGLoopEntrance is the last element of the goto terminated +/// block. +class CFGLoopEntrance : public CFGElement { +public: + explicit CFGLoopEntrance(const Stmt *stmt) : CFGElement(LoopEntrance, stmt) {} + + const Stmt *getLoopStmt() const { + return static_cast(Data1.getPointer()); + } + +private: + friend class CFGElement; + CFGLoopEntrance() {} + static bool isKind(const CFGElement &elem) { + return elem.getKind() == LoopEntrance; + } +}; + /// Represents the point where a loop ends. /// This element is is only produced when building the CFG for the static /// analyzer and hidden behind the 'cfg-loopexit' analyzer config flag. It is @@ -786,6 +813,10 @@ Elements.push_back(CFGLoopExit(LoopStmt), C); } + void appendLoopEntrance(const Stmt *LoopStmt, BumpVectorContext &C) { + Elements.push_back(CFGLoopEntrance(LoopStmt), C); + } + void appendDeleteDtor(CXXRecordDecl *RD, CXXDeleteExpr *DE, BumpVectorContext &C) { Elements.push_back(CFGDeleteDtor(RD, DE), C); } Index: lib/Analysis/CFG.cpp =================================================================== --- lib/Analysis/CFG.cpp +++ lib/Analysis/CFG.cpp @@ -655,6 +655,8 @@ CFGBlock *addInitializer(CXXCtorInitializer *I); void addLoopExit(const Stmt *LoopStmt); void addLoopExit(const Stmt *FromStmt, const Stmt *ToStmt); + void addLoopEntrance(const Stmt *LoopStmt); + void addLoopEntrance(const Stmt *FromStmt, const Stmt *ToStmt); void addAutomaticObjDtors(LocalScope::const_iterator B, LocalScope::const_iterator E, Stmt *S); @@ -717,6 +719,10 @@ B->appendLoopExit(LoopStmt, cfg->getBumpVectorContext()); } + void appendLoopEntrance(CFGBlock *B, const Stmt *LoopStmt) { + B->appendLoopEntrance(LoopStmt, cfg->getBumpVectorContext()); + } + void appendDeleteDtor(CFGBlock *B, CXXRecordDecl *RD, CXXDeleteExpr *DE) { B->appendDeleteDtor(RD, DE, cfg->getBumpVectorContext()); } @@ -1356,6 +1362,24 @@ return LoopStmts; } +void CFGBuilder::addLoopEntrance(const Stmt *FromStmt, const Stmt *ToStmt) { + if (!BuildOpts.AddLoopExit) + return; + + llvm::SmallSetVector FromLoopStmts = + collectContainingLoops(FromStmt, *Context); + + llvm::SmallSetVector ToLoopStmts = + collectContainingLoops(ToStmt, *Context); + + ToLoopStmts.set_subtract(FromLoopStmts); + for (llvm::SmallSetVector::reverse_iterator + I = ToLoopStmts.rbegin(), + E = ToLoopStmts.rend(); + I != E; ++I) + appendLoopEntrance(Block, *I); +} + void CFGBuilder::addLoopExit(const Stmt *FromStmt, const Stmt *ToStmt) { if (!BuildOpts.AddLoopExit) return; @@ -1374,6 +1398,13 @@ appendLoopExit(Block, *I); } +void CFGBuilder::addLoopEntrance(const Stmt *LoopStmt) { + if (!BuildOpts.AddLoopExit) + return; + autoCreateBlock(); + appendLoopEntrance(Block, LoopStmt); +} + void CFGBuilder::addAutomaticObjHandling(LocalScope::const_iterator B, LocalScope::const_iterator E, Stmt *S) { @@ -2762,6 +2793,7 @@ addSuccessor(Block, JT.block); } addLoopExit(G, G->getLabel()->getStmt()); + addLoopEntrance(G, G->getLabel()->getStmt()); return Block; } @@ -2917,7 +2949,7 @@ // Link up the loop-back block to the entry condition block. addSuccessor(TransitionBlock, EntryConditionBlock); - + // The condition block is the implicit successor for any code above the loop. Succ = EntryConditionBlock; @@ -2925,14 +2957,17 @@ // statements. This block can also contain statements that precede the loop. if (Stmt *I = F->getInit()) { Block = createBlock(); - return addStmt(I); + CFGBlock *InitBlock = addStmt(I); + addLoopEntrance(F); + return InitBlock; } // There is no loop initialization. We are thus basically a while loop. // NULL out Block to force lazy block construction. Block = nullptr; Succ = EntryConditionBlock; - return EntryConditionBlock; + addLoopEntrance(F); + return (Block ? Block : Succ); } CFGBlock *CFGBuilder::VisitMemberExpr(MemberExpr *M, AddStmtChoice asc) { @@ -3236,7 +3271,8 @@ // Return the condition block, which is the dominating block for the loop. Succ = EntryConditionBlock; - return EntryConditionBlock; + addLoopEntrance(W); + return (Block ? Block : Succ); } CFGBlock *CFGBuilder::VisitObjCAtCatchStmt(ObjCAtCatchStmt *S) { @@ -3385,7 +3421,8 @@ // Return the loop body, which is the dominating block for the loop. Succ = BodyBlock; - return BodyBlock; + addLoopEntrance(D); + return (Block ? Block : Succ); } CFGBlock *CFGBuilder::VisitContinueStmt(ContinueStmt *C) { @@ -4266,6 +4303,7 @@ case CFGElement::Initializer: case CFGElement::NewAllocator: case CFGElement::LoopExit: + case CFGElement::LoopEntrance: case CFGElement::LifetimeEnds: llvm_unreachable("getDestructorDecl should only be used with " "ImplicitDtors"); @@ -4679,6 +4717,9 @@ Helper.handleDecl(VD, OS); OS << " (Lifetime ends)\n"; + } else if (Optional LE = E.getAs()) { + const Stmt *LoopStmt = LE->getLoopStmt(); + OS << LoopStmt->getStmtClassName() << " (LoopEntrance)\n"; } else if (Optional LE = E.getAs()) { const Stmt *LoopStmt = LE->getLoopStmt(); OS << LoopStmt->getStmtClassName() << " (LoopExit)\n"; Index: lib/StaticAnalyzer/Core/PathDiagnostic.cpp =================================================================== --- lib/StaticAnalyzer/Core/PathDiagnostic.cpp +++ lib/StaticAnalyzer/Core/PathDiagnostic.cpp @@ -581,6 +581,7 @@ llvm_unreachable("not yet implemented!"); case CFGElement::LifetimeEnds: case CFGElement::LoopExit: + case CFGElement::LoopEntrance: llvm_unreachable("CFGElement kind should not be on callsite!"); } Index: test/Analysis/loopexit-cfg-output.cpp =================================================================== --- test/Analysis/loopexit-cfg-output.cpp +++ test/Analysis/loopexit-cfg-output.cpp @@ -32,8 +32,9 @@ // CHECK-NEXT: Succs (2): B3 B1 // CHECK: [B5] -// CHECK-NEXT: 1: 0 -// CHECK-NEXT: 2: int i = 0; +// CHECK-NEXT: 1: ForStmt (LoopEntrance) +// CHECK-NEXT: 2: 0 +// CHECK-NEXT: 3: int i = 0; // CHECK-NEXT: Preds (1): B6 // CHECK-NEXT: Succs (1): B4 @@ -46,8 +47,8 @@ return; } -// CHECK: [B4 (ENTRY)] -// CHECK-NEXT: Succs (1): B3 +// CHECK: [B5 (ENTRY)] +// CHECK-NEXT: Succs (1): B4 // CHECK: [B1] // CHECK-NEXT: 1: ForStmt (LoopExit) @@ -62,6 +63,11 @@ // CHECK-NEXT: Preds (2): B2 B4 // CHECK-NEXT: Succs (2): B2 NULL +// CHECK: [B4] +// CHECK-NEXT: 1: ForStmt (LoopEntrance) +// CHECK-NEXT: Preds (1): B5 +// CHECK-NEXT: Succs (1): B3 + // CHECK: [B0 (EXIT)] // CHECK-NEXT: Preds (1): B1 void check_forloop2() { @@ -69,8 +75,8 @@ ; } -// CHECK: [B5 (ENTRY)] -// CHECK-NEXT: Succs (1): B4 +// CHECK: [B6 (ENTRY)] +// CHECK-NEXT: Succs (1): B5 // CHECK: [B1] // CHECK-NEXT: 1: WhileStmt (LoopExit) @@ -91,6 +97,11 @@ // CHECK-NEXT: Preds (2): B2 B5 // CHECK-NEXT: Succs (2): B3 NULL +// CHECK: [B5] +// CHECK-NEXT: 1: WhileStmt (LoopEntrance) +// CHECK-NEXT: Preds (1): B6 +// CHECK-NEXT: Succs (1): B4 + // CHECK: [B0 (EXIT)] // CHECK-NEXT: Preds (1): B1 void check_while1() { @@ -125,6 +136,7 @@ // CHECK: [B4] // CHECK-NEXT: 1: int l; +// CHECK-NEXT: 2: WhileStmt (LoopEntrance) // CHECK-NEXT: Preds (1): B5 // CHECK-NEXT: Succs (1): B3 @@ -138,8 +150,8 @@ return; } -// CHECK: [B4 (ENTRY)] -// CHECK-NEXT: Succs (1): B3 +// CHECK: [B5 (ENTRY)] +// CHECK-NEXT: Succs (1): B4 // CHECK: [B1] // CHECK-NEXT: 1: WhileStmt (LoopExit) @@ -155,6 +167,11 @@ // CHECK-NEXT: Preds (2): B2 B4 // CHECK-NEXT: Succs (2): NULL B1 +// CHECK: [B4] +// CHECK-NEXT: 1: WhileStmt (LoopEntrance) +// CHECK-NEXT: Preds (1): B5 +// CHECK-NEXT: Succs (1): B3 + // CHECK: [B0 (EXIT)] // CHECK-NEXT: Preds (1): B1 void check_while3() { @@ -163,8 +180,8 @@ } } -// CHECK: [B4 (ENTRY)] -// CHECK-NEXT: Succs (1): B2 +// CHECK: [B5 (ENTRY)] +// CHECK-NEXT: Succs (1): B4 // CHECK: [B1] // CHECK-NEXT: 1: DoStmt (LoopExit) @@ -180,6 +197,11 @@ // CHECK: [B3] // CHECK-NEXT: Succs (1): B2 +// CHECK: [B4] +// CHECK-NEXT: 1: DoStmt (LoopEntrance) +// CHECK-NEXT: Preds (1): B5 +// CHECK-NEXT: Succs (1): B2 + // CHECK: [B0 (EXIT)] // CHECK-NEXT: Preds (1): B1 void check_dowhile1() { @@ -221,6 +243,7 @@ // CHECK: [B5] // CHECK-NEXT: 1: 2 // CHECK-NEXT: 2: int j = 2; +// CHECK-NEXT: 3: DoStmt (LoopEntrance) // CHECK-NEXT: Preds (1): B6 // CHECK-NEXT: Succs (1): B3 @@ -274,8 +297,9 @@ // CHECK-NEXT: Succs (2): B5 B3 // CHECK: [B7] -// CHECK-NEXT: 1: 1 -// CHECK-NEXT: 2: int j = 1; +// CHECK-NEXT: 1: ForStmt (LoopEntrance) +// CHECK-NEXT: 2: 1 +// CHECK-NEXT: 3: int j = 1; // CHECK-NEXT: Preds (1): B8 // CHECK-NEXT: Succs (1): B6 @@ -292,6 +316,7 @@ // CHECK-NEXT: 1: 40 // CHECK-NEXT: 2: -[B9.1] // CHECK-NEXT: 3: int i = -40; +// CHECK-NEXT: 4: WhileStmt (LoopEntrance) // CHECK-NEXT: Preds (1): B10 // CHECK-NEXT: Succs (1): B8 @@ -305,19 +330,19 @@ } } -// CHECK: [B9 (ENTRY)] -// CHECK-NEXT: Succs (1): B8 +// CHECK: [B10 (ENTRY)] +// CHECK-NEXT: Succs (1): B9 // CHECK: [B1] // CHECK-NEXT: 1: ForStmt (LoopExit) -// CHECK-NEXT: Preds (1): B7 +// CHECK-NEXT: Preds (1): B8 // CHECK-NEXT: Succs (1): B0 // CHECK: [B2] // CHECK-NEXT: 1: j // CHECK-NEXT: 2: [B2.1]++ // CHECK-NEXT: Preds (1): B3 -// CHECK-NEXT: Succs (1): B7 +// CHECK-NEXT: Succs (1): B8 // CHECK: [B3] // CHECK-NEXT: 1: DoStmt (LoopExit) @@ -346,22 +371,28 @@ // CHECK-NEXT: Succs (1): B5 // CHECK: [B7] +// CHECK-NEXT: 1: DoStmt (LoopEntrance) +// CHECK-NEXT: Preds (1): B8 +// CHECK-NEXT: Succs (1): B5 + +// CHECK: [B8] // CHECK-NEXT: 1: j -// CHECK-NEXT: 2: [B7.1] (ImplicitCastExpr, LValueToRValue, int) +// CHECK-NEXT: 2: [B8.1] (ImplicitCastExpr, LValueToRValue, int) // CHECK-NEXT: 3: 6 -// CHECK-NEXT: 4: [B7.2] < [B7.3] -// CHECK-NEXT: T: for (...; [B7.4]; ...) -// CHECK-NEXT: Preds (2): B2 B8 -// CHECK-NEXT: Succs (2): B5 B1 +// CHECK-NEXT: 4: [B8.2] < [B8.3] +// CHECK-NEXT: T: for (...; [B8.4]; ...) +// CHECK-NEXT: Preds (2): B2 B9 +// CHECK-NEXT: Succs (2): B7 B1 -// CHECK: [B8] +// CHECK: [B9] // CHECK-NEXT: 1: 40 -// CHECK-NEXT: 2: -[B8.1] +// CHECK-NEXT: 2: -[B9.1] // CHECK-NEXT: 3: int i = -40; -// CHECK-NEXT: 4: 1 -// CHECK-NEXT: 5: int j = 1; -// CHECK-NEXT: Preds (1): B9 -// CHECK-NEXT: Succs (1): B7 +// CHECK-NEXT: 4: ForStmt (LoopEntrance) +// CHECK-NEXT: 5: 1 +// CHECK-NEXT: 6: int j = 1; +// CHECK-NEXT: Preds (1): B10 +// CHECK-NEXT: Succs (1): B8 // CHECK: [B0 (EXIT)] // CHECK-NEXT: Preds (1): B1 @@ -418,6 +449,7 @@ // CHECK-NEXT: 1: ForStmt (LoopExit) // CHECK-NEXT: 2: 1 // CHECK-NEXT: 3: int i = 1; +// CHECK-NEXT: 4: WhileStmt (LoopEntrance) // CHECK-NEXT: Preds (2): B8 B10 // CHECK-NEXT: Succs (1): B5 @@ -451,8 +483,9 @@ // CHECK-NEXT: Succs (2): B9 B6 // CHECK: [B11] -// CHECK-NEXT: 1: 2 -// CHECK-NEXT: 2: int i = 2; +// CHECK-NEXT: 1: ForStmt (LoopEntrance) +// CHECK-NEXT: 2: 2 +// CHECK-NEXT: 3: int i = 2; // CHECK-NEXT: Preds (1): B12 // CHECK-NEXT: Succs (1): B10 @@ -527,6 +560,7 @@ // CHECK: [B8] // CHECK-NEXT: 1: 1 // CHECK-NEXT: 2: int j = 1; +// CHECK-NEXT: 3: WhileStmt (LoopEntrance) // CHECK-NEXT: Preds (1): B9 // CHECK-NEXT: Succs (1): B7 @@ -541,8 +575,9 @@ // CHECK: [B10] // CHECK-NEXT: lab: -// CHECK-NEXT: 1: 0 -// CHECK-NEXT: 2: int i = 0; +// CHECK-NEXT: 1: ForStmt (LoopEntrance) +// CHECK-NEXT: 2: 0 +// CHECK-NEXT: 3: int i = 0; // CHECK-NEXT: Preds (2): B5 B11 // CHECK-NEXT: Succs (1): B9 @@ -613,6 +648,7 @@ // CHECK-NEXT: lab: // CHECK-NEXT: 1: 1 // CHECK-NEXT: 2: int j = 1; +// CHECK-NEXT: 3: WhileStmt (LoopEntrance) // CHECK-NEXT: Preds (2): B9 B5 // CHECK-NEXT: Succs (1): B7 @@ -626,8 +662,9 @@ // CHECK-NEXT: Succs (2): B8 B1 // CHECK: [B10] -// CHECK-NEXT: 1: 0 -// CHECK-NEXT: 2: int i = 0; +// CHECK-NEXT: 1: ForStmt (LoopEntrance) +// CHECK-NEXT: 2: 0 +// CHECK-NEXT: 3: int i = 0; // CHECK-NEXT: Preds (1): B11 // CHECK-NEXT: Succs (1): B9 @@ -646,20 +683,20 @@ return; } -// CHECK: [B10 (ENTRY)] -// CHECK-NEXT: Succs (1): B9 +// CHECK: [B11 (ENTRY)] +// CHECK-NEXT: Succs (1): B10 // CHECK: [B1] // CHECK-NEXT: 1: ForStmt (LoopExit) // CHECK-NEXT: 2: return; -// CHECK-NEXT: Preds (1): B8 +// CHECK-NEXT: Preds (1): B9 // CHECK-NEXT: Succs (1): B0 // CHECK: [B2] // CHECK-NEXT: 1: i // CHECK-NEXT: 2: [B2.1]++ // CHECK-NEXT: Preds (1): B3 -// CHECK-NEXT: Succs (1): B8 +// CHECK-NEXT: Succs (1): B9 // CHECK: [B3] // CHECK-NEXT: 1: WhileStmt (LoopExit) @@ -675,7 +712,7 @@ // CHECK-NEXT: 1: 2 // CHECK-NEXT: 2: j // CHECK-NEXT: 3: [B5.2] = [B5.1] -// CHECK-NEXT: Preds (2): B6 B7 +// CHECK-NEXT: Preds (2): B6 B8 // CHECK-NEXT: Succs (1): B4 // CHECK: [B6] @@ -684,30 +721,36 @@ // CHECK-NEXT: 3: 12 // CHECK-NEXT: 4: [B6.2] < [B6.3] // CHECK-NEXT: T: while [B6.4] -// CHECK-NEXT: Preds (1): B4 +// CHECK-NEXT: Preds (2): B4 B7 // CHECK-NEXT: Succs (2): B5 B3 // CHECK: [B7] +// CHECK-NEXT: 1: WhileStmt (LoopEntrance) +// CHECK-NEXT: Succs (1): B6 + +// CHECK: [B8] // CHECK-NEXT: 1: 1 // CHECK-NEXT: 2: int j = 1; +// CHECK-NEXT: 3: WhileStmt (LoopEntrance) // CHECK-NEXT: T: goto lab; -// CHECK-NEXT: Preds (1): B8 +// CHECK-NEXT: Preds (1): B9 // CHECK-NEXT: Succs (1): B5 -// CHECK: [B8] +// CHECK: [B9] // CHECK-NEXT: 1: i -// CHECK-NEXT: 2: [B8.1] (ImplicitCastExpr, LValueToRValue, int) +// CHECK-NEXT: 2: [B9.1] (ImplicitCastExpr, LValueToRValue, int) // CHECK-NEXT: 3: 10 -// CHECK-NEXT: 4: [B8.2] < [B8.3] -// CHECK-NEXT: T: for (...; [B8.4]; ...) -// CHECK-NEXT: Preds (2): B2 B9 -// CHECK-NEXT: Succs (2): B7 B1 +// CHECK-NEXT: 4: [B9.2] < [B9.3] +// CHECK-NEXT: T: for (...; [B9.4]; ...) +// CHECK-NEXT: Preds (2): B2 B10 +// CHECK-NEXT: Succs (2): B8 B1 -// CHECK: [B9] -// CHECK-NEXT: 1: 0 -// CHECK-NEXT: 2: int i = 0; -// CHECK-NEXT: Preds (1): B10 -// CHECK-NEXT: Succs (1): B8 +// CHECK: [B10] +// CHECK-NEXT: 1: ForStmt (LoopEntrance) +// CHECK-NEXT: 2: 0 +// CHECK-NEXT: 3: int i = 0; +// CHECK-NEXT: Preds (1): B11 +// CHECK-NEXT: Succs (1): B9 // CHECK: [B0 (EXIT)] // CHECK-NEXT: Preds (1): B1 @@ -778,6 +821,7 @@ // CHECK: [B8] // CHECK-NEXT: 1: 1 // CHECK-NEXT: 2: int j = 1; +// CHECK-NEXT: 3: WhileStmt (LoopEntrance) // CHECK-NEXT: Preds (1): B9 // CHECK-NEXT: Succs (1): B7 @@ -791,8 +835,9 @@ // CHECK-NEXT: Succs (2): B8 B1 // CHECK: [B10] -// CHECK-NEXT: 1: 0 -// CHECK-NEXT: 2: int i = 0; +// CHECK-NEXT: 1: ForStmt (LoopEntrance) +// CHECK-NEXT: 2: 0 +// CHECK-NEXT: 3: int i = 0; // CHECK-NEXT: Preds (1): B11 // CHECK-NEXT: Succs (1): B9 @@ -854,6 +899,7 @@ // CHECK: [B7] // CHECK-NEXT: 1: 1 // CHECK-NEXT: 2: int j = 1; +// CHECK-NEXT: 3: WhileStmt (LoopEntrance) // CHECK-NEXT: Preds (1): B8 // CHECK-NEXT: Succs (1): B6 @@ -867,8 +913,9 @@ // CHECK-NEXT: Succs (2): B7 B1 // CHECK: [B9] -// CHECK-NEXT: 1: 0 -// CHECK-NEXT: 2: int i = 0; +// CHECK-NEXT: 1: ForStmt (LoopEntrance) +// CHECK-NEXT: 2: 0 +// CHECK-NEXT: 3: int i = 0; // CHECK-NEXT: Preds (1): B10 // CHECK-NEXT: Succs (1): B8