[analyzer] Rework support for CFGScopeBegin, CFGScopeEnd, CFGLifetime elements

[tomasz-kaminski-sonarsource]

Summary

This patch reworks generation for the CFGScopeBegin, CFGScopeEnd,
and CFGLiftimeEnd, in a way that they are now compatible with each
other and CFGAutomaticObjDtor. All of the above elements are now
generated by a single code path, that conditionally inserts elements if
they are requested.

In addition, the handling of goto statements is improved.
The goto statement may leave multiple scopes (and trigger destruction
and lifetime end for the affected variables) and enter multiple scopes,
for example:

{
  int s1;
  {
    int s2;
    goto label; // leaves s1, s2, and enters t1 t1
  }
}
{
  int t1;
  {
    int t2;
label:
  }
}

This is performed by first determining the shared parent scope of the
source and destination. And then emitting elements for exiting each
scope between the source and the parent, and entering each scope
between the parent and destination. All such elements are appended
to the source block, as one label may be reached from multiple scopes.

Finally, the approach for handling backward jumps is changed. When
connecting a source block to a destination block that requires the
insertion of additional elements, we put this element into a new block,
which is then linked between the source and the destination block.
For example:

{
  int t;
label:
  // Destination block referred to as 'DB'
}
{
  // Source block referred to as 'SB'
  Obj s;
  goto label;
}

The jump between SB with terminator T: goto and DB should be
coupled with the following CFG elements:

CFGAutomaticObjDtor(s)
CFGLifetimeEnd(s)
CFGScopeEnd(s)
CFGScopeBegin(t)

To handle such situations, we create a new link (LB) that is linked as
the predecessor of DB, to which we transfer the terminator (goto
statement) of SB. Then LB is handled in the same manner as the
source block in the case of forward jumps.
This produces CFG that looks like this:

SB -> LB (T: goto) -> DB

Finally, the resulting block is linked as the successor of SB. Such an
approach uses existing handling of the noreturn destructors.
As a reminder, for each destructor of an automatic object that is
marked as noreturn, a new noreturn block (marked NBn) is
created, at the destructor is inserted at the end of it.
To illustrate, given two noreturn destructors, we will have:

SB -> NB1 (noreturn)
NB2 (noreturn)
LB (T:goto) -> DB

[steakhal]

I'd appreciate some review on this, given that a lot of you would be affected by the changes of CFG.
By changes I mean, fixes for goto statements, properly calling destructors and stuff.

It's already in production for our CSA fork, and the results look good.

In two weeks we plan to land this unless anyone objects.

[ymandel]

In D153273#4471672, @steakhal wrote:

I'd appreciate some review on this, given that a lot of you would be affected by the changes of CFG.
By changes I mean, fixes for goto statements, properly calling destructors and stuff.

It's already in production for our CSA fork, and the results look good.

In two weeks we plan to land this unless anyone objects.

Thanks! We're planning to take a look in the next few days.

[ymandel]

clang/lib/Analysis/CFG.cpp

772

Consider adding comments describing these methods, either here or at the function definitions.

1840

if LocalScopeEndMarkers isn't supposed to change inside the body of the loop, then consider making this call once
for (std::size_t idx = 1, N = LocalScopeEndMarkers.size(); idx < N; ...

1903–1905

1920–1927

Remove extra braces?

[tomasz-kaminski-sonarsource]

Apply review suggestion and replaced make_scope_exit with SaveAndRestore that was already used
in file.

[steakhal]

clang/lib/Analysis/CFG.cpp

1840–1847

How about using a "pairwise" range here?
I believe, we don't have that just yet, but we can use zip instead.

1892–1894

We could use llvm::make_range(B, E) here, I believe.

1898–1900

Ranges here too.

1934–1936

Probably, we could also use a llvm::make_range(DstPos, BasePos) here, but I'm not sure if that's more readable or not.

[tomasz-kaminski-sonarsource]

clang/lib/Analysis/CFG.cpp

1934–1936

We need to call iterator member function I here, so we cannot replace it with the range.

[tomasz-kaminski-sonarsource]

Switched to ranges when applicable.

[xazax.hun]

clang/test/Analysis/lifetime-cfg-output.cpp

760

Would it be possible to add the variable name to the lifetime ends dumps? It would make interpreting these tests somewhat easier. (It is OK as a separate/follow-up patch.)

clang/test/Analysis/nonreturn-destructors-cfg-output.cpp

99

B3 and B5 look almost identical. Do we need both? If not, would there be a way to deduplicate?

[tomasz-kaminski-sonarsource]

clang/test/Analysis/lifetime-cfg-output.cpp

760

I think that would indeed be helpful. We could do the same for the destructors:

[B3.3].~A() (Implicit destructor)

But to be explicit, I do not have any idea when I would be able to work on it.

[tomasz-kaminski-sonarsource]

clang/test/Analysis/nonreturn-destructors-cfg-output.cpp

99

B2 is created when we visit the statement in reverse order. This includes all statement until we reach goto. So if the code would look like:

{
  A a;
  goto label;
  int b;
    foo();
}
label:
   foo();

Then B2 will include two calls to foo and lifetime of int b. The B5 only includes destructor of a that happens after goto.

So the similarly here only happens by accident, or in other words is by product of the code. In this case any deduplication mechanism for blocks will need to be content based, and I haven't seen anything like that happening in the code.

[xazax.hun]

Thanks! Looks good to me.

clang/include/clang/Analysis/CFG.h

void appendNewAllocator(CXXNewExpr *NE,
     Elements.push_back(CFGNewAllocator(NE), C);
   }
 
   void appendScopeBegin(const VarDecl *VD, const Stmt *S,
                         BumpVectorContext &C) {
     Elements.push_back(CFGScopeBegin(VD, S), C);
   }
 
-  void prependScopeBegin(const VarDecl *VD, const Stmt *S,
-                         BumpVectorContext &C) {
-    Elements.insert(Elements.rbegin(), 1, CFGScopeBegin(VD, S), C);
-  }
-
   void appendScopeEnd(const VarDecl *VD, const Stmt *S, BumpVectorContext &C) {
     Elements.push_back(CFGScopeEnd(VD, S), C);
   }
 
-  void prependScopeEnd(const VarDecl *VD, const Stmt *S, BumpVectorContext &C) {
-    Elements.insert(Elements.rbegin(), 1, CFGScopeEnd(VD, S), C);
-  }
-
   void appendBaseDtor(const CXXBaseSpecifier *BS, BumpVectorContext &C) {
     Elements.push_back(CFGBaseDtor(BS), C);
   }
 
   void appendMemberDtor(FieldDecl *FD, BumpVectorContext &C) {
     Elements.push_back(CFGMemberDtor(FD), C);
   }
 
public:
 
   void appendLoopExit(const Stmt *LoopStmt, BumpVectorContext &C) {
     Elements.push_back(CFGLoopExit(LoopStmt), 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,
-      BumpVectorContext &C) {
-    return iterator(Elements.insert(I.base(), Cnt,
-                                    CFGAutomaticObjDtor(nullptr, nullptr), C));
-  }
-  iterator insertAutomaticObjDtor(iterator I, VarDecl *VD, Stmt *S) {
-    *I = CFGAutomaticObjDtor(VD, S);
-    return ++I;
-  }
-
-  // Scope leaving must be performed 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 beginLifetimeEndsInsert(iterator I, size_t Cnt,
-                                   BumpVectorContext &C) {
-    return iterator(
-        Elements.insert(I.base(), Cnt, CFGLifetimeEnds(nullptr, nullptr), C));
-  }
-  iterator insertLifetimeEnds(iterator I, VarDecl *VD, Stmt *S) {
-    *I = CFGLifetimeEnds(VD, S);
-    return ++I;
-  }
-
-  // Scope leaving must be performed 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 beginScopeEndInsert(iterator I, size_t Cnt, BumpVectorContext &C) {
-    return iterator(
-        Elements.insert(I.base(), Cnt, CFGScopeEnd(nullptr, nullptr), C));
-  }
-  iterator insertScopeEnd(iterator I, VarDecl *VD, Stmt *S) {
-    *I = CFGScopeEnd(VD, S);
-    return ++I;
-  }
 };
 
 /// CFGCallback defines methods that should be called when a logical
 /// operator error is found when building the CFG.
 class CFGCallback {
 public:
   CFGCallback() = default;
   virtual ~CFGCallback() = default;

clang/lib/Analysis/CFG.cpp

public:
 
     explicit operator bool() const {
       return *this != const_iterator();
     }
 
     int distance(const_iterator L);
     const_iterator shared_parent(const_iterator L);
     bool pointsToFirstDeclaredVar() { return VarIter == 1; }
+    bool inSameLocalScope(const_iterator rhs) { return Scope == rhs.Scope; }
   };
 
 private:
   BumpVectorContext ctx;
 
   /// Automatic variables in order of declaration.
   AutomaticVarsTy Vars;
 

 }
 
 /// Calculates the closest parent of this iterator
 /// that is in a scope reachable through the parents of L.
 /// I.e. when using 'goto' from this to L, the lifetime of all variables
 /// between this and shared_parent(L) end.
 LocalScope::const_iterator
 LocalScope::const_iterator::shared_parent(LocalScope::const_iterator L) {
-  llvm::SmallPtrSet<const LocalScope *, 4> ScopesOfL;
+  // one of iterators is not valid (we are not in scope), so common
+  // parent is const_iterator() (i.e. sentinel).
+  if ((*this == const_iterator()) || (L == const_iterator())) {
+    return const_iterator();
+  }
+
+  const_iterator F = *this;
+  if (F.inSameLocalScope(L)) {
+    // Iterators are in the same scope, get common subset of variables.
+    F.VarIter = std::min(F.VarIter, L.VarIter);
+    return F;
+  }
+
+  llvm::SmallDenseMap<const LocalScope *, unsigned, 4> ScopesOfL;
   while (true) {
-    ScopesOfL.insert(L.Scope);
+    ScopesOfL.try_emplace(L.Scope, L.VarIter);
     if (L == const_iterator())
       break;
     L = L.Scope->Prev;
   }
 
-  const_iterator F = *this;
   while (true) {
-    if (ScopesOfL.count(F.Scope))
+    if (auto LIt = ScopesOfL.find(F.Scope); LIt != ScopesOfL.end()) {
+      // Get common subset of variables in given scope
+      F.VarIter = std::min(F.VarIter, LIt->getSecond());
       return F;
+    }
     assert(F != const_iterator() &&
            "L iterator is not reachable from F iterator.");
     F = F.Scope->Prev;
   }
 }
 
 namespace {
 
class CFGBuilder {
   LabelSetTy AddressTakenLabels;
 
   // Information about the currently visited C++ object construction site.
   // This is set in the construction trigger and read when the constructor
   // or a function that returns an object by value is being visited.
   llvm::DenseMap<Expr *, const ConstructionContextLayer *>
       ConstructionContextMap;
 
-  using DeclsWithEndedScopeSetTy = llvm::SmallSetVector<VarDecl *, 16>;
-  DeclsWithEndedScopeSetTy DeclsWithEndedScope;
-
   bool badCFG = false;
   const CFG::BuildOptions &BuildOpts;
 
   // State to track for building switch statements.
   bool switchExclusivelyCovered = false;
   Expr::EvalResult *switchCond = nullptr;
 
   CFG::BuildOptions::ForcedBlkExprs::value_type *cachedEntry = nullptr;
private:
   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,
+  void addAutomaticObjHandling(LocalScope::const_iterator B,
                                LocalScope::const_iterator E, Stmt *S);
-  void addLifetimeEnds(LocalScope::const_iterator B,
+  void addAutomaticObjDestruction(LocalScope::const_iterator B,
                                   LocalScope::const_iterator E, Stmt *S);
-  void addAutomaticObjHandling(LocalScope::const_iterator B,
-                               LocalScope::const_iterator E, Stmt *S);
+  void addScopeExitHandling(LocalScope::const_iterator B,
   void addImplicitDtorsForDestructor(const CXXDestructorDecl *DD);
-  void addScopesEnd(LocalScope::const_iterator B, LocalScope::const_iterator E,
+  void addScopeChangesHandling(LocalScope::const_iterator SrcPos,
+                               LocalScope::const_iterator DstPos,
                                Stmt *S);
-
-  void getDeclsWithEndedScope(LocalScope::const_iterator B,
-                              LocalScope::const_iterator E, Stmt *S);
+  CFGBlock *createScopeChangesHandlingBlock(LocalScope::const_iterator SrcPos,
+                                            CFGBlock *SrcBlk,
+                                            LocalScope::const_iterator DstPost,
+                                            CFGBlock *DstBlk);
 
   // Local scopes creation.
   LocalScope* createOrReuseLocalScope(LocalScope* Scope);
 
   void addLocalScopeForStmt(Stmt *S);
   LocalScope* addLocalScopeForDeclStmt(DeclStmt *DS,
                                        LocalScope* Scope = nullptr);
   LocalScope* addLocalScopeForVarDecl(VarDecl *VD, LocalScope* Scope = nullptr);
private:
   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());
   }
 
-  void prependAutomaticObjDtorsWithTerminator(CFGBlock *Blk,
-      LocalScope::const_iterator B, LocalScope::const_iterator E);
-
-  void prependAutomaticObjLifetimeWithTerminator(CFGBlock *Blk,
-                                                 LocalScope::const_iterator B,
-                                                 LocalScope::const_iterator E);
-
-  const VarDecl *
-  prependAutomaticObjScopeEndWithTerminator(CFGBlock *Blk,
-                                            LocalScope::const_iterator B,
-                                            LocalScope::const_iterator E);
-
   void addSuccessor(CFGBlock *B, CFGBlock *S, bool IsReachable = true) {
     B->addSuccessor(CFGBlock::AdjacentBlock(S, IsReachable),
                     cfg->getBumpVectorContext());
   }
 
   /// Add a reachable successor to a block, with the alternate variant that is
   /// unreachable.
   void addSuccessor(CFGBlock *B, CFGBlock *ReachableBlock, CFGBlock *AltBlock) {
     B->addSuccessor(CFGBlock::AdjacentBlock(ReachableBlock, AltBlock),
                     cfg->getBumpVectorContext());
   }
 
   void appendScopeBegin(CFGBlock *B, const VarDecl *VD, const Stmt *S) {
     if (BuildOpts.AddScopes)
       B->appendScopeBegin(VD, S, cfg->getBumpVectorContext());
   }
 
-  void prependScopeBegin(CFGBlock *B, const VarDecl *VD, const Stmt *S) {
-    if (BuildOpts.AddScopes)
-      B->prependScopeBegin(VD, S, cfg->getBumpVectorContext());
-  }
-
   void appendScopeEnd(CFGBlock *B, const VarDecl *VD, const Stmt *S) {
     if (BuildOpts.AddScopes)
       B->appendScopeEnd(VD, S, cfg->getBumpVectorContext());
   }
 
-  void prependScopeEnd(CFGBlock *B, const VarDecl *VD, const Stmt *S) {
-    if (BuildOpts.AddScopes)
-      B->prependScopeEnd(VD, S, cfg->getBumpVectorContext());
-  }
-
   /// Find a relational comparison with an expression evaluating to a
   /// boolean and a constant other than 0 and 1.
   /// e.g. if ((x < y) == 10)
   TryResult checkIncorrectRelationalOperator(const BinaryOperator *B) {
     const Expr *LHSExpr = B->getLHS()->IgnoreParens();
     const Expr *RHSExpr = B->getRHS()->IgnoreParens();
 
     const IntegerLiteral *IntLiteral = dyn_cast<IntegerLiteral>(LHSExpr);

 void CFGBuilder::cleanupConstructionContext(Expr *E) {
   assert(BuildOpts.AddRichCXXConstructors &&
          "We should not be managing construction contexts!");
   assert(ConstructionContextMap.count(E) &&
          "Cannot exit construction context without the context!");
   ConstructionContextMap.erase(E);
 }
 
-
 /// BuildCFG - Constructs a CFG from an AST (a Stmt*).  The AST can represent an
 ///  arbitrary statement.  Examples include a single expression or a function
 ///  body (compound statement).  The ownership of the returned CFG is
 ///  transferred to the caller.  If CFG construction fails, this method returns
 ///  NULL.
 std::unique_ptr<CFG> CFGBuilder::buildCFG(const Decl *D, Stmt *Statement) {
   assert(cfg.get());
   if (!Statement)
     return nullptr;
 
   // Create an empty block that will serve as the exit block for the CFG.  Since
   // this is the first block added to the CFG, it will be implicitly registered
   // as the exit block.
   Succ = createBlock();
   assert(Succ == &cfg->getExit());
   Block = nullptr;  // the EXIT block is empty.  Create all other blocks lazily.
 
-  assert(!(BuildOpts.AddImplicitDtors && BuildOpts.AddLifetime) &&
-         "AddImplicitDtors and AddLifetime cannot be used at the same time");
-
   if (BuildOpts.AddImplicitDtors)
     if (const CXXDestructorDecl *DD = dyn_cast_or_null<CXXDestructorDecl>(D))
       addImplicitDtorsForDestructor(DD);
 
   // Visit the statements and create the CFG.
   CFGBlock *B = addStmt(Statement);
 
   if (badCFG)
for (BackpatchBlocksTy::iterator I = BackpatchBlocks.begin(),
     CFGBlock *B = I->block;
     if (auto *G = dyn_cast<GotoStmt>(B->getTerminator())) {
       LabelMapTy::iterator LI = LabelMap.find(G->getLabel());
       // If there is no target for the goto, then we are looking at an
       // incomplete AST.  Handle this by not registering a successor.
       if (LI == LabelMap.end())
         continue;
       JumpTarget JT = LI->second;
-      prependAutomaticObjLifetimeWithTerminator(B, I->scopePosition,
-                                                JT.scopePosition);
-      prependAutomaticObjDtorsWithTerminator(B, I->scopePosition,
-                                             JT.scopePosition);
-      const VarDecl *VD = prependAutomaticObjScopeEndWithTerminator(
-          B, I->scopePosition, JT.scopePosition);
-      appendScopeBegin(JT.block, VD, G);
-      addSuccessor(B, JT.block);
-    };
-    if (auto *G = dyn_cast<GCCAsmStmt>(B->getTerminator())) {
+
+      CFGBlock *SuccBlk = createScopeChangesHandlingBlock(
+          I->scopePosition, B, JT.scopePosition, JT.block);
+      addSuccessor(B, SuccBlk);
+    } else if (auto *G = dyn_cast<GCCAsmStmt>(B->getTerminator())) {
       CFGBlock *Successor  = (I+1)->block;
       for (auto *L : G->labels()) {
         LabelMapTy::iterator LI = LabelMap.find(L->getLabel());
         // If there is no target for the goto, then we are looking at an
         // incomplete AST.  Handle this by not registering a successor.
         if (LI == LabelMap.end())
           continue;
         JumpTarget JT = LI->second;

 // ended by ReturnStmt, GotoStmt or ThrowExpr.
 void CFGBuilder::addLoopExit(const Stmt *LoopStmt){
   if(!BuildOpts.AddLoopExit)
     return;
   autoCreateBlock();
   appendLoopExit(Block, LoopStmt);
 }
 
-void CFGBuilder::getDeclsWithEndedScope(LocalScope::const_iterator B,
-                                        LocalScope::const_iterator E, Stmt *S) {
-  if (!BuildOpts.AddScopes)
+/// Adds the CFG elements for leaving the scope of automatic objects in
+/// range [B, E). This include following:
+///   * AutomaticObjectDtor for variables with non-trivial destructor
+///   * LifetimeEnds for all variables
+///   * ScopeEnd for each scope left
+void CFGBuilder::addAutomaticObjHandling(LocalScope::const_iterator B,
+                                         LocalScope::const_iterator E,
+                                         Stmt *S) {
+  if (!BuildOpts.AddScopes && !BuildOpts.AddImplicitDtors &&
+      !BuildOpts.AddLifetime)
     return;
 
   if (B == E)
     return;
 
-  // To go from B to E, one first goes up the scopes from B to P
-  // then sideways in one scope from P to P' and then down
-  // the scopes from P' to E.
-  // The lifetime of all objects between B and P end.
-  LocalScope::const_iterator P = B.shared_parent(E);
-  int Dist = B.distance(P);
-  if (Dist <= 0)
+  // Not leaving the scope, only need to handle destruction and lifetime
+  if (B.inSameLocalScope(E)) {
+    addAutomaticObjDestruction(B, E, S);
     return;
+  }
 
-  for (LocalScope::const_iterator I = B; I != P; ++I)
-    if (I.pointsToFirstDeclaredVar())
-      DeclsWithEndedScope.insert(*I);
+  // Extract information about all local scopes that are left
+  SmallVector<LocalScope::const_iterator, 10> LocalScopeEndMarkers;
+  LocalScopeEndMarkers.push_back(B);
+  for (LocalScope::const_iterator I = B; I != E; ++I) {
+    if (!I.inSameLocalScope(LocalScopeEndMarkers.back()))
+      LocalScopeEndMarkers.push_back(I);
   }
+  LocalScopeEndMarkers.push_back(E);
 
-void CFGBuilder::addAutomaticObjHandling(LocalScope::const_iterator B,
-                                         LocalScope::const_iterator E,
-                                         Stmt *S) {
-  getDeclsWithEndedScope(B, E, S);
-  if (BuildOpts.AddScopes)
-    addScopesEnd(B, E, S);
-  if (BuildOpts.AddImplicitDtors)
-    addAutomaticObjDtors(B, E, S);
-  if (BuildOpts.AddLifetime)
-    addLifetimeEnds(B, E, S);
+  // We need to leave the scope in reverse order, so we reverse the end
+  // markers
+  std::reverse(LocalScopeEndMarkers.begin(), LocalScopeEndMarkers.end());
+  auto Pairwise =
+      llvm::zip(LocalScopeEndMarkers, llvm::drop_begin(LocalScopeEndMarkers));
+  for (auto [E, B] : Pairwise) {
+    if (!B.inSameLocalScope(E))
+      addScopeExitHandling(B, E, S);
+    addAutomaticObjDestruction(B, E, S);
+  }
 }
 
-/// Add to current block automatic objects that leave the scope.
-void CFGBuilder::addLifetimeEnds(LocalScope::const_iterator B,
-                                 LocalScope::const_iterator E, Stmt *S) {
-  if (!BuildOpts.AddLifetime)
+/// Add CFG elements corresponding to call destructor and end of lifetime
+/// of all automatic variables with non-trivial destructor in range [B, E).
+/// This include AutomaticObjectDtor and LifetimeEnds elements.
+void CFGBuilder::addAutomaticObjDestruction(LocalScope::const_iterator B,
+                                            LocalScope::const_iterator E,
+                                            Stmt *S) {
+  if (!BuildOpts.AddImplicitDtors && !BuildOpts.AddLifetime)
     return;
 
   if (B == E)
     return;
 
-  // To go from B to E, one first goes up the scopes from B to P
-  // then sideways in one scope from P to P' and then down
-  // the scopes from P' to E.
-  // The lifetime of all objects between B and P end.
-  LocalScope::const_iterator P = B.shared_parent(E);
-  int dist = B.distance(P);
-  if (dist <= 0)
-    return;
-
-  // We need to perform the scope leaving in reverse order
-  SmallVector<VarDecl *, 10> DeclsTrivial;
   SmallVector<VarDecl *, 10> DeclsNonTrivial;
-  DeclsTrivial.reserve(dist);
-  DeclsNonTrivial.reserve(dist);
+  DeclsNonTrivial.reserve(B.distance(E));
 
-  for (LocalScope::const_iterator I = B; I != P; ++I)
-    if (hasTrivialDestructor(*I))
-      DeclsTrivial.push_back(*I);
-    else
-      DeclsNonTrivial.push_back(*I);
+  for (VarDecl* D : llvm::make_range(B, E))
+    if (!hasTrivialDestructor(D))
+      DeclsNonTrivial.push_back(D);
+
+  for (VarDecl *VD : llvm::reverse(DeclsNonTrivial)) {
+    if (BuildOpts.AddImplicitDtors) {
+      // If this destructor is marked as a no-return destructor, we need to
+      // create a new block for the destructor which does not have as a
+      // successor anything built thus far: control won't flow out of this
+      // block.
+      QualType Ty = VD->getType();
+      if (Ty->isReferenceType())
+        Ty = getReferenceInitTemporaryType(VD->getInit());
+      Ty = Context->getBaseElementType(Ty);
+
+      if (Ty->getAsCXXRecordDecl()->isAnyDestructorNoReturn())
+        Block = createNoReturnBlock();
+    }
 
     autoCreateBlock();
-  // object with trivial destructor end their lifetime last (when storage
-  // duration ends)
-  for (VarDecl *VD : llvm::reverse(DeclsTrivial))
-    appendLifetimeEnds(Block, VD, S);
 
-  for (VarDecl *VD : llvm::reverse(DeclsNonTrivial))
+    // Add LifetimeEnd after automatic obj with non-trivial destructors,
+    // as they end their lifetime when the destructor returns. For trivial
+    // objects, we end lifetime with scope end.
+    if (BuildOpts.AddLifetime)
       appendLifetimeEnds(Block, VD, S);
+    if (BuildOpts.AddImplicitDtors)
+      appendAutomaticObjDtor(Block, VD, S);
+  }
 }
 
-/// Add to current block markers for ending scopes.
-void CFGBuilder::addScopesEnd(LocalScope::const_iterator B,
+/// Add CFG elements corresponding to leaving a scope.
+/// Assumes that range [B, E) corresponds to single scope.
+/// This add following elements:
+///   * LifetimeEnds for all variables with non-trivial destructor
+///   * ScopeEnd for each scope left
+void CFGBuilder::addScopeExitHandling(LocalScope::const_iterator B,
                                       LocalScope::const_iterator E, Stmt *S) {
-  // If implicit destructors are enabled, we'll add scope ends in
-  // addAutomaticObjDtors.
-  if (BuildOpts.AddImplicitDtors)
+  assert(!B.inSameLocalScope(E));
+  if (!BuildOpts.AddLifetime && !BuildOpts.AddScopes)
     return;
 
+  if (BuildOpts.AddScopes) {
     autoCreateBlock();
-
-  for (VarDecl *VD : llvm::reverse(DeclsWithEndedScope))
-    appendScopeEnd(Block, VD, S);
+    appendScopeEnd(Block, B.getFirstVarInScope(), S);
   }
 
-/// addAutomaticObjDtors - Add to current block automatic objects destructors
-/// for objects in range of local scope positions. Use S as trigger statement
-/// for destructors.
-void CFGBuilder::addAutomaticObjDtors(LocalScope::const_iterator B,
-                                      LocalScope::const_iterator E, Stmt *S) {
-  if (!BuildOpts.AddImplicitDtors)
+  if (!BuildOpts.AddLifetime)
     return;
 
-  if (B == E)
+  // We need to perform the scope leaving in reverse order
+  SmallVector<VarDecl *, 10> DeclsTrivial;
+  DeclsTrivial.reserve(B.distance(E));
+
+  // Objects with trivial destructor ends their lifetime when their storage
+  // is destroyed, for automatic variables, this happens when the end of the
+  // scope is added.
+  for (VarDecl* D : llvm::make_range(B, E))
+    if (hasTrivialDestructor(D))
+      DeclsTrivial.push_back(D);
+
+  if (DeclsTrivial.empty())
     return;
 
-  // We need to append the destructors in reverse order, but any one of them
-  // may be a no-return destructor which changes the CFG. As a result, buffer
-  // this sequence up and replay them in reverse order when appending onto the
-  // CFGBlock(s).
-  SmallVector<VarDecl*, 10> Decls;
-  Decls.reserve(B.distance(E));
-  for (LocalScope::const_iterator I = B; I != E; ++I)
-    Decls.push_back(*I);
-
-  for (VarDecl *VD : llvm::reverse(Decls)) {
-    if (hasTrivialDestructor(VD)) {
-      // If AddScopes is enabled and *I is a first variable in a scope, add a
-      // ScopeEnd marker in a Block.
-      if (BuildOpts.AddScopes && DeclsWithEndedScope.count(VD)) {
-        autoCreateBlock();
-        appendScopeEnd(Block, VD, S);
-      }
-      continue;
-    }
-    // If this destructor is marked as a no-return destructor, we need to
-    // create a new block for the destructor which does not have as a successor
-    // anything built thus far: control won't flow out of this block.
-    QualType Ty = VD->getType();
-    if (Ty->isReferenceType()) {
-      Ty = getReferenceInitTemporaryType(VD->getInit());
-    }
-    Ty = Context->getBaseElementType(Ty);
+  for (VarDecl *VD : llvm::reverse(DeclsTrivial))
+    appendLifetimeEnds(Block, VD, S);
+
+/// addScopeChangesHandling - appends information about destruction, lifetime
+/// and cfgScopeEnd for variables in the scope that was left by the jump, and
+/// appends cfgScopeBegin for all scopes that where entered.
+/// We insert the cfgScopeBegin at the end of the jump node, as depending on
+/// the sourceBlock, each goto, may enter different amount of scopes.
+void CFGBuilder::addScopeChangesHandling(LocalScope::const_iterator SrcPos,
+                                         LocalScope::const_iterator DstPos,
+                                         Stmt *S) {
+  assert(Block && "Source block should be always crated");
+  if (!BuildOpts.AddImplicitDtors && !BuildOpts.AddLifetime &&
+      !BuildOpts.AddScopes) {
+    return;
 
-    if (Ty->getAsCXXRecordDecl()->isAnyDestructorNoReturn())
-      Block = createNoReturnBlock();
-    else
-      autoCreateBlock();
+  if (SrcPos == DstPos)
+    return;
 
-    // Add ScopeEnd just after automatic obj destructor.
-    if (BuildOpts.AddScopes && DeclsWithEndedScope.count(VD))
-      appendScopeEnd(Block, VD, S);
-    appendAutomaticObjDtor(Block, VD, S);
+  // Get common scope, the jump leaves all scopes [SrcPos, BasePos), and
+  // enter all scopes between [DstPos, BasePos)
+  LocalScope::const_iterator BasePos = SrcPos.shared_parent(DstPos);
+
+  // Append scope begins for scopes entered by goto
+  if (BuildOpts.AddScopes && !DstPos.inSameLocalScope(BasePos)) {
+    for (LocalScope::const_iterator I = DstPos; I != BasePos; ++I)
+      if (I.pointsToFirstDeclaredVar())
+        appendScopeBegin(Block, *I, S);
   }
+
+  // Append scopeEnds, destructor and lifetime with the terminator for
+  // block left by goto.
+  addAutomaticObjHandling(SrcPos, BasePos, S);
+}
+
+/// createScopeChangesHandlingBlock - Creates a block with cfgElements
+/// corresponding to changing the scope from the source scope of the GotoStmt,
+/// to destination scope. Add destructor, lifetime and cfgScopeEnd
+/// CFGElements to newly created CFGBlock, that will have the CFG terminator
+/// transferred.
+CFGBlock *CFGBuilder::createScopeChangesHandlingBlock(
+    LocalScope::const_iterator SrcPos, CFGBlock *SrcBlk,
+    LocalScope::const_iterator DstPos, CFGBlock *DstBlk) {
+  if (SrcPos == DstPos)
+    return DstBlk;
+
+  if (!BuildOpts.AddImplicitDtors && !BuildOpts.AddLifetime &&
+      (!BuildOpts.AddScopes || SrcPos.inSameLocalScope(DstPos)))
+    return DstBlk;
+
+  // We will update CFBBuilder when creating new block, restore the
+  // previous state at exit.
+  SaveAndRestore save_Block(Block), save_Succ(Succ);
+
+  // Create a new block, and transfer terminator
+  Block = createBlock(false);
+  Block->setTerminator(SrcBlk->getTerminator());
+  SrcBlk->setTerminator(CFGTerminator());
+  addSuccessor(Block, DstBlk);
+
+  // Fill the created Block with the required elements.
+  addScopeChangesHandling(SrcPos, DstPos, Block->getTerminatorStmt());
+
+  assert(Block && "There should be at least one scope changing Block");
+  return Block;
 }
 
 /// addImplicitDtorsForDestructor - Add implicit destructors generated for
 /// base and member objects in destructor.
 void CFGBuilder::addImplicitDtorsForDestructor(const CXXDestructorDecl *DD) {
   assert(BuildOpts.AddImplicitDtors &&
          "Can be called only when dtors should be added");
   const CXXRecordDecl *RD = DD->getParent();
bool CFGBuilder::hasTrivialDestructor(VarDecl *VD) {
   return true;
 }
 
 /// addLocalScopeForVarDecl - Add LocalScope for variable declaration. It will
 /// create add scope for automatic objects and temporary objects bound to
 /// const reference. Will reuse Scope if not NULL.
 LocalScope* CFGBuilder::addLocalScopeForVarDecl(VarDecl *VD,
                                                 LocalScope* Scope) {
-  assert(!(BuildOpts.AddImplicitDtors && BuildOpts.AddLifetime) &&
-         "AddImplicitDtors and AddLifetime cannot be used at the same time");
   if (!BuildOpts.AddImplicitDtors && !BuildOpts.AddLifetime &&
       !BuildOpts.AddScopes)
     return Scope;
 
   // Check if variable is local.
   if (!VD->hasLocalStorage())
     return Scope;
 
-  if (BuildOpts.AddImplicitDtors) {
-    if (!hasTrivialDestructor(VD) || BuildOpts.AddScopes) {
-      // Add the variable to scope
-      Scope = createOrReuseLocalScope(Scope);
-      Scope->addVar(VD);
-      ScopePos = Scope->begin();
-    }
+  if (!BuildOpts.AddLifetime && !BuildOpts.AddScopes &&
+      hasTrivialDestructor(VD)) {
+    assert(BuildOpts.AddImplicitDtors);
     return Scope;
   }
 
-  assert(BuildOpts.AddLifetime);
   // Add the variable to scope
   Scope = createOrReuseLocalScope(Scope);
   Scope->addVar(VD);
   ScopePos = Scope->begin();
   return Scope;
 }
 
 /// addLocalScopeAndDtors - For given statement add local scope for it and
 /// add destructors that will cleanup the scope. Will reuse Scope if not NULL.
 void CFGBuilder::addLocalScopeAndDtors(Stmt *S) {
   LocalScope::const_iterator scopeBeginPos = ScopePos;
   addLocalScopeForStmt(S);
   addAutomaticObjHandling(ScopePos, scopeBeginPos, S);
 }
 
-/// prependAutomaticObjDtorsWithTerminator - Prepend destructor CFGElements for
-/// variables with automatic storage duration to CFGBlock's elements vector.
-/// Elements will be prepended to physical beginning of the vector which
-/// happens to be logical end. Use blocks terminator as statement that specifies
-/// destructors call site.
-/// FIXME: This mechanism for adding automatic destructors doesn't handle
-/// no-return destructors properly.
-void CFGBuilder::prependAutomaticObjDtorsWithTerminator(CFGBlock *Blk,
-    LocalScope::const_iterator B, LocalScope::const_iterator E) {
-  if (!BuildOpts.AddImplicitDtors)
-    return;
-  BumpVectorContext &C = cfg->getBumpVectorContext();
-  CFGBlock::iterator InsertPos
-    = Blk->beginAutomaticObjDtorsInsert(Blk->end(), B.distance(E), C);
-  for (LocalScope::const_iterator I = B; I != E; ++I)
-    InsertPos = Blk->insertAutomaticObjDtor(InsertPos, *I,
-                                            Blk->getTerminatorStmt());
-}
-
-/// prependAutomaticObjLifetimeWithTerminator - Prepend lifetime CFGElements for
-/// variables with automatic storage duration to CFGBlock's elements vector.
-/// Elements will be prepended to physical beginning of the vector which
-/// happens to be logical end. Use blocks terminator as statement that specifies
-/// where lifetime ends.
-void CFGBuilder::prependAutomaticObjLifetimeWithTerminator(
-    CFGBlock *Blk, LocalScope::const_iterator B, LocalScope::const_iterator E) {
-  if (!BuildOpts.AddLifetime)
-    return;
-  BumpVectorContext &C = cfg->getBumpVectorContext();
-  CFGBlock::iterator InsertPos =
-      Blk->beginLifetimeEndsInsert(Blk->end(), B.distance(E), C);
-  for (LocalScope::const_iterator I = B; I != E; ++I) {
-    InsertPos =
-        Blk->insertLifetimeEnds(InsertPos, *I, Blk->getTerminatorStmt());
-  }
-}
-
-/// prependAutomaticObjScopeEndWithTerminator - Prepend scope end CFGElements for
-/// variables with automatic storage duration to CFGBlock's elements vector.
-/// Elements will be prepended to physical beginning of the vector which
-/// happens to be logical end. Use blocks terminator as statement that specifies
-/// where scope ends.
-const VarDecl *
-CFGBuilder::prependAutomaticObjScopeEndWithTerminator(
-    CFGBlock *Blk, LocalScope::const_iterator B, LocalScope::const_iterator E) {
-  if (!BuildOpts.AddScopes)
-    return nullptr;
-  BumpVectorContext &C = cfg->getBumpVectorContext();
-  CFGBlock::iterator InsertPos =
-      Blk->beginScopeEndInsert(Blk->end(), 1, C);
-  LocalScope::const_iterator PlaceToInsert = B;
-  for (LocalScope::const_iterator I = B; I != E; ++I)
-    PlaceToInsert = I;
-  Blk->insertScopeEnd(InsertPos, *PlaceToInsert, Blk->getTerminatorStmt());
-  return *PlaceToInsert;
-}
-
 /// Visit - Walk the subtree of a statement and add extra
 ///   blocks for ternary operators, &&, and ||.  We also process "," and
 ///   DeclStmts (which may contain nested control-flow).
 CFGBlock *CFGBuilder::Visit(Stmt * S, AddStmtChoice asc,
                             bool ExternallyDestructed) {
   if (!S) {
     badCFG = true;
     return nullptr;
CFGBlock *CFGBuilder::VisitGotoStmt(GotoStmt *G) {
   // If we already know the mapping to the label block add the successor now.
   LabelMapTy::iterator I = LabelMap.find(G->getLabel());
 
   if (I == LabelMap.end())
     // We will need to backpatch this block later.
     BackpatchBlocks.push_back(JumpSource(Block, ScopePos));
   else {
     JumpTarget JT = I->second;
-    addAutomaticObjHandling(ScopePos, JT.scopePosition, G);
     addSuccessor(Block, JT.block);
+    addScopeChangesHandling(ScopePos, JT.scopePosition, G);
   }
 
   return Block;
 }
 
 CFGBlock *CFGBuilder::VisitGCCAsmStmt(GCCAsmStmt *G, AddStmtChoice asc) {
   // Goto is a control-flow statement.  Thus we stop processing the current
   // block and create a new one.

clang/test/Analysis/auto-obj-dtors-cfg-output.cpp

 // CHECK-NEXT:   Preds (2): B1 B2
 void test_return() {
   A a;
   A b;
   if (UV) return;
   A c;
 }
 
-// CHECK:      [B8 (ENTRY)]
+// CHECK:      [B9 (ENTRY)]
 // CHECK-NEXT:   Succs (1): B7
 // CHECK:      [B1]
 // CHECK:       l1:
 // WARNINGS-NEXT:   1:  (CXXConstructExpr, A)
 // ANALYZER-NEXT:   1:  (CXXConstructExpr, [B1.2], A)
 // CHECK-NEXT:   2: A c;
 // CHECK-NEXT:   3: [B1.2].~A() (Implicit destructor)
 // CHECK-NEXT:   4: [B6.2].~A() (Implicit destructor)

 // CHECK-NEXT:   Succs (1): B1
 // CHECK:      [B4]
 // CHECK-NEXT:   1: UV
 // CHECK-NEXT:   2: [B4.1] (ImplicitCastExpr, LValueToRValue, _Bool)
 // CHECK-NEXT:   T: if [B4.2]
 // CHECK-NEXT:   Preds (1): B6
 // CHECK-NEXT:   Succs (2): B3 B2
 // CHECK:      [B5]
-// CHECK-NEXT:   1: [B6.4].~A() (Implicit destructor)
-// CHECK-NEXT:   2: [B6.2].~A() (Implicit destructor)
-// CHECK-NEXT:   T: goto l0;
 // CHECK:        Preds (1): B6
-// CHECK-NEXT:   Succs (1): B6
+// CHECK-NEXT:   Succs (1): B8
 // CHECK:      [B6]
 // CHECK:       l0:
 // WARNINGS-NEXT:   1:  (CXXConstructExpr, A)
 // ANALYZER-NEXT:   1:  (CXXConstructExpr, [B6.2], A)
 // CHECK-NEXT:   2: A b;
 // WARNINGS-NEXT:   3:  (CXXConstructExpr, A)
 // ANALYZER-NEXT:   3:  (CXXConstructExpr, [B6.4], A)
 // CHECK-NEXT:   4: A a;
 // CHECK-NEXT:   5: UV
 // CHECK-NEXT:   6: [B6.5] (ImplicitCastExpr, LValueToRValue, _Bool)
 // CHECK-NEXT:   T: if [B6.6]
-// CHECK-NEXT:   Preds (2): B7 B5
+// CHECK-NEXT:   Preds (2): B7 B8
 // CHECK-NEXT:   Succs (2): B5 B4
 // CHECK:      [B7]
 // WARNINGS-NEXT:   1:  (CXXConstructExpr, A)
 // ANALYZER-NEXT:   1:  (CXXConstructExpr, [B7.2], A)
 // CHECK-NEXT:   2: A a;
-// CHECK-NEXT:   Preds (1): B8
+// CHECK-NEXT:   Preds (1): B9
+// CHECK-NEXT:   Succs (1): B6
+// CHECK:      [B8]
+// CHECK-NEXT:   1: [B6.4].~A() (Implicit destructor)
+// CHECK-NEXT:   2: [B6.2].~A() (Implicit destructor)
+// CHECK-NEXT:   T: goto l0;
+// CHECK-NEXT:   Preds (1): B5
 // CHECK-NEXT:   Succs (1): B6
 // CHECK:      [B0 (EXIT)]
 // CHECK-NEXT:   Preds (1): B1
 void test_goto() {
   A a;
 l0:
   A b;
   { A a;

clang/test/Analysis/lifetime-cfg-output.cpp

a:
     k = 1;
   }
 }
 
 struct B {
   ~B();
 };
 
-// CHECK:       [B4 (ENTRY)]
+// CHECK:       [B5 (ENTRY)]
 // CHECK-NEXT:    Succs (1): B3
 // CHECK:       [B1]
 // CHECK-NEXT:    1: i
 // CHECK-NEXT:    2: [B1.1]++
-// CHECK-NEXT:    3: [B2.2] (Lifetime ends)
-// CHECK-NEXT:    4: [B3.1] (Lifetime ends)
+// CHECK-NEXT:    3: [B2.4] (Lifetime ends)
+// CHECK-NEXT:    4: [B2.2] (Lifetime ends)
+// CHECK-NEXT:    5: [B3.1] (Lifetime ends)
 // CHECK-NEXT:    Succs (1): B0
 // CHECK:       [B2]
 // CHECK-NEXT:   label:
 // CHECK-NEXT:    1:  (CXXConstructExpr, B)
-// CHECK-NEXT:    2: B b;
-// CHECK-NEXT:    3: [B2.2] (Lifetime ends)
-// CHECK-NEXT:    T: goto label;
-// CHECK-NEXT:    Preds (2): B3 B2
-// CHECK-NEXT:    Succs (1): B2
+// CHECK-NEXT:    2: B b1;
+// CHECK-NEXT:    3:  (CXXConstructExpr, B)
+// CHECK-NEXT:    4: B b2;
+// CHECK-NEXT:    Preds (2): B3 B4
+// CHECK-NEXT:    Succs (1): B4
 // CHECK:       [B3]
 // CHECK-NEXT:    1: int i;
-// CHECK-NEXT:    Preds (1): B4
+// CHECK-NEXT:    Preds (1): B5
+// CHECK-NEXT:    Succs (1): B2
+// CHECK:       [B4]
+// CHECK-NEXT:    1: [B2.4] (Lifetime ends)
+// CHECK-NEXT:    2: [B2.2] (Lifetime ends)
+// CHECK-NEXT:    T: goto label;
+// CHECK-NEXT:    Preds (1): B2
 // CHECK-NEXT:    Succs (1): B2
 // CHECK:       [B0 (EXIT)]
 // CHECK-NEXT:    Preds (1): B1
 int backpatched_goto() {
   int i;
 label:
-  B b;
+  B b1;
+  B b2;
   goto label;
   i++;
 }

clang/test/Analysis/no-exit-cfg.c

 // RUN: %clang_analyze_cc1 -analyzer-checker=core,alpha.core -verify %s
+// RUN: %clang_analyze_cc1 -analyzer-checker=core,alpha.core -analyzer-config cfg-scopes=true -verify %s
 // expected-no-diagnostics
 
 // This is a test case for the issue reported in PR 2819:
 //  http://llvm.org/bugs/show_bug.cgi?id=2819
 // The flow-sensitive dataflow solver should work even when no block in
 // the CFG reaches the exit block.
 
 int g(int x);

clang/test/Analysis/nonreturn-destructors-cfg-output.cpp

+// RUN: %clang_analyze_cc1 -std=c++11 -fcxx-exceptions -fexceptions -analyzer-checker=debug.DumpCFG -analyzer-config cfg-rich-constructors=true,cfg-implicit-dtors=true,cfg-lifetime=true,cfg-scopes=true %s > %t 2>&1
+// RUN: FileCheck --input-file=%t -check-prefixes=CHECK %s
+
+class A {
+public:
+  int x;
+  [[noreturn]] ~A();
+};
+
+void foo();
+extern const bool UV;
+
+// CHECK:       [B3 (ENTRY)]
+// CHECK-NEXT:    Succs (1): B2
+//
+// CHECK:       [B1]
+// CHECK-NEXT:    1: CFGScopeEnd(a)
+// CHECK-NEXT:    2: foo
+// CHECK-NEXT:    3: [B1.2] (ImplicitCastExpr, FunctionToPointerDecay, void (*)(void))
+// CHECK-NEXT:    4: [B1.3]()
+// CHECK-NEXT:    Succs (1): B0
+//
+// CHECK:       [B2 (NORETURN)]
+// CHECK-NEXT:    1: CFGScopeBegin(a)
+// CHECK-NEXT:    2:  (CXXConstructExpr, [B2.3], A)
+// CHECK-NEXT:    3: A a;
+// CHECK-NEXT:    4: [B2.3].~A() (Implicit destructor)
+// CHECK-NEXT:    5: [B2.3] (Lifetime ends)
+// CHECK-NEXT:    Preds (1): B3
+// CHECK-NEXT:    Succs (1): B0
+//
+// CHECK:       [B0 (EXIT)]
+// CHECK-NEXT:    Preds (2): B1 B2
+void test_single_decl() {
+  {
+    A a;
+  }
+  foo();
+}
+
+// CHECK:       [B6 (ENTRY)]
+// CHECK-NEXT:    Succs (1): B5
+//
+// CHECK:       [B1]
+// CHECK-NEXT:   label:
+// CHECK-NEXT:    1: foo
+// CHECK-NEXT:    2: [B1.1] (ImplicitCastExpr, FunctionToPointerDecay, void (*)(void))
+// CHECK-NEXT:    3: [B1.2]()
+// CHECK-NEXT:    Preds (4): B2 B3(Unreachable) B4 B5(Unreachable)
+// CHECK-NEXT:    Succs (1): B0
+//
+// CHECK:       [B2]
+// CHECK-NEXT:    1: CFGScopeEnd(a)
+// CHECK-NEXT:    Succs (1): B1
+//
+// CHECK:       [B3 (NORETURN)]
+// CHECK-NEXT:    1: [B5.3].~A() (Implicit destructor)
+// CHECK-NEXT:    2: [B5.3] (Lifetime ends)
+// CHECK-NEXT:    Succs (1): B0
+//
+// CHECK:       [B4]
+// CHECK-NEXT:    1: CFGScopeEnd(a)
+// CHECK-NEXT:    T: goto label;
+// CHECK-NEXT:    Succs (1): B1
+//
+// CHECK:       [B5 (NORETURN)]
+// CHECK-NEXT:    1: CFGScopeBegin(a)
+// CHECK-NEXT:    2:  (CXXConstructExpr, [B5.3], A)
+// CHECK-NEXT:    3: A a;
+// CHECK-NEXT:    4: [B5.3].~A() (Implicit destructor)
+// CHECK-NEXT:    5: [B5.3] (Lifetime ends)
+// CHECK-NEXT:    Preds (1): B6
+// CHECK-NEXT:    Succs (1): B0
+//
+// CHECK:       [B0 (EXIT)]
+// CHECK-NEXT:    Preds (3): B1 B3 B5
+void test_forward_goto() {
+  {
+    A a;
+    goto label;
+  }
+label:
+  foo();
+}
+
+
+// The blocks B3 and B5, are inserted during backpatching goto stmt, to handle
+// scope changes.
+// CHECK:       [B6 (ENTRY)]
+// CHECK-NEXT:    Succs (1): B3
+//
+// CHECK:       [B1]
+// CHECK-NEXT:    1: CFGScopeEnd(a)
+// CHECK-NEXT:    2: foo
+// CHECK-NEXT:    3: [B1.2] (ImplicitCastExpr, FunctionToPointerDecay, void (*)(void))
+// CHECK-NEXT:    4: [B1.3]()
+// CHECK-NEXT:    Succs (1): B0
+//
+// CHECK:       [B2 (NORETURN)]
+// CHECK-NEXT:    1: [B3.3].~A() (Implicit destructor)
+// CHECK-NEXT:    2: [B3.3] (Lifetime ends)
+// CHECK-NEXT:    Succs (1): B0
+//
+// CHECK:       [B3]
+// CHECK-NEXT:   label:
+// CHECK-NEXT:    1: CFGScopeBegin(a)
+// CHECK-NEXT:    2:  (CXXConstructExpr, [B3.3], A)
+// CHECK-NEXT:    3: A a;
+// CHECK-NEXT:    Preds (3): B4 B5(Unreachable) B6
+// CHECK-NEXT:    Succs (1): B5
+//
+// CHECK:       [B4]
+// CHECK-NEXT:    1: CFGScopeEnd(a)
+// CHECK-NEXT:    T: goto label;
+// CHECK-NEXT:    Succs (1): B3
+//
+// CHECK:       [B5 (NORETURN)]
+// CHECK-NEXT:    1: [B3.3].~A() (Implicit destructor)
+// CHECK-NEXT:    2: [B3.3] (Lifetime ends)
+// CHECK-NEXT:    Preds (1): B3
+// CHECK-NEXT:    Succs (1): B0
+//
+// CHECK:       [B0 (EXIT)]
+// CHECK-NEXT:    Preds (3): B1 B2 B5
+void test_backward_goto() {
+label:
+  {
+    A a;
+    goto label;
+  }
+  foo();
+}

clang/test/Analysis/scopes-cfg-output.cpp

for (A b; A c = b; ) {
     if (UV) break;
     if (UV) continue;
     if (UV) return;
     A e;
   }
   A f;
 }
 
-// CHECK:      [B8 (ENTRY)]
+// CHECK:      [B9 (ENTRY)]
 // CHECK-NEXT:   Succs (1): B7
 // CHECK:      [B1]
 // CHECK-NEXT:  l1:
 // CHECK-NEXT:   1:  (CXXConstructExpr, [B1.2], A)
 // CHECK-NEXT:   2: A c;
 // CHECK-NEXT:   3: [B1.2].~A() (Implicit destructor)
-// CHECK-NEXT:   4: [B6.5].~A() (Implicit destructor)
-// CHECK-NEXT:   5: [B6.3].~A() (Implicit destructor)
+// CHECK-NEXT:   4: [B6.4].~A() (Implicit destructor)
+// CHECK-NEXT:   5: [B6.2].~A() (Implicit destructor)
 // CHECK-NEXT:   6: [B7.3].~A() (Implicit destructor)
 // CHECK-NEXT:   7: CFGScopeEnd(a)
 // CHECK-NEXT:   Preds (2): B2 B3
 // CHECK-NEXT:   Succs (1): B0
 // CHECK:      [B2]
 // CHECK-NEXT:   1:  (CXXConstructExpr, [B2.2], A)
-// CHECK-NEXT:   2: A b;
+// CHECK-NEXT:   2: A nb;
 // CHECK-NEXT:   3: [B2.2].~A() (Implicit destructor)
-// CHECK-NEXT:   4: [B6.8].~A() (Implicit destructor)
-// CHECK-NEXT:   5: CFGScopeEnd(a)
+// CHECK-NEXT:   4: [B6.7].~A() (Implicit destructor)
+// CHECK-NEXT:   5: CFGScopeEnd(na)
 // CHECK-NEXT:   Preds (1): B4
 // CHECK-NEXT:   Succs (1): B1
 // CHECK:      [B3]
-// CHECK-NEXT:   1: [B6.8].~A() (Implicit destructor)
-// CHECK-NEXT:   2: CFGScopeEnd(a)
+// CHECK-NEXT:   1: [B6.7].~A() (Implicit destructor)
+// CHECK-NEXT:   2: CFGScopeEnd(na)
 // CHECK-NEXT:   T: goto l1;
 // CHECK-NEXT:   Preds (1): B4
 // CHECK-NEXT:   Succs (1): B1
 // CHECK:      [B4]
 // CHECK-NEXT:   1: UV
 // CHECK-NEXT:   2: [B4.1] (ImplicitCastExpr, LValueToRValue, _Bool)
 // CHECK-NEXT:   T: if [B4.2]
 // CHECK-NEXT:   Preds (1): B6
 // CHECK-NEXT:   Succs (2): B3 B2
 // CHECK:      [B5]
-// CHECK-NEXT:   1: [B6.8].~A() (Implicit destructor)
-// CHECK-NEXT:   2: [B6.5].~A() (Implicit destructor)
-// CHECK-NEXT:   3: [B6.3].~A() (Implicit destructor)
-// CHECK-NEXT:   4: CFGScopeEnd(cb)
-// CHECK-NEXT:   T: goto l0;
 // CHECK-NEXT:   Preds (1): B6
-// CHECK-NEXT:   Succs (1): B6
+// CHECK-NEXT:   Succs (1): B8
 // CHECK:      [B6]
 // CHECK-NEXT:  l0:
-// CHECK-NEXT:   1: CFGScopeBegin(cb)
-// CHECK-NEXT:   2:  (CXXConstructExpr, [B6.3], A)
-// CHECK-NEXT:   3: A cb;
-// CHECK-NEXT:   4:  (CXXConstructExpr, [B6.5], A)
-// CHECK-NEXT:   5: A b;
-// CHECK-NEXT:   6: CFGScopeBegin(a)
-// CHECK-NEXT:   7:  (CXXConstructExpr, [B6.8], A)
-// CHECK-NEXT:   8: A a;
-// CHECK-NEXT:   9: UV
-// CHECK-NEXT:  10: [B6.9] (ImplicitCastExpr, LValueToRValue, _Bool)
-// CHECK-NEXT:   T: if [B6.10]
-// CHECK-NEXT:   Preds (2): B7 B5
+// CHECK-NEXT:   1:  (CXXConstructExpr, [B6.2], A)
+// CHECK-NEXT:   2: A cb;
+// CHECK-NEXT:   3:  (CXXConstructExpr, [B6.4], A)
+// CHECK-NEXT:   4: A b;
+// CHECK-NEXT:   5: CFGScopeBegin(na)
+// CHECK-NEXT:   6:  (CXXConstructExpr, [B6.7], A)
+// CHECK-NEXT:   7: A na;
+// CHECK-NEXT:   8: UV
+// CHECK-NEXT:   9: [B6.8] (ImplicitCastExpr, LValueToRValue, _Bool)
+// CHECK-NEXT:   T: if [B6.9]
+// CHECK-NEXT:   Preds (2): B7 B8
 // CHECK-NEXT:   Succs (2): B5 B4
 // CHECK:      [B7]
 // CHECK-NEXT:   1: CFGScopeBegin(a)
 // CHECK-NEXT:   2:  (CXXConstructExpr, [B7.3], A)
 // CHECK-NEXT:   3: A a;
-// CHECK-NEXT:   Preds (1): B8
+// CHECK-NEXT:   Preds (1): B9
+// CHECK-NEXT:   Succs (1): B6
+// CHECK:      [B8]
+// CHECK-NEXT:   1: [B6.7].~A() (Implicit destructor)
+// CHECK-NEXT:   2: CFGScopeEnd(na)
+// CHECK-NEXT:   3: [B6.4].~A() (Implicit destructor)
+// CHECK-NEXT:   4: [B6.2].~A() (Implicit destructor)
+// CHECK-NEXT:   T: goto l0;
+// CHECK-NEXT:   Preds (1): B5
 // CHECK-NEXT:   Succs (1): B6
 // CHECK:      [B0 (EXIT)]
 // CHECK-NEXT:   Preds (1): B1
 void test_goto() {
   A a;
 l0:
   A cb;
   A b;
-  { A a;
+  { A na;
     if (UV) goto l0;
     if (UV) goto l1;
-    A b;
+    A nb;
   }
 l1:
   A c;
 }
 
 // CHECK:      [B7 (ENTRY)]
 // CHECK-NEXT:   Succs (1): B6
 // CHECK:      [B1]
default:
       y = 3;
     }
     {
       int z = 5;
       break; // break from loop
     }
   }
 }
+
+// CHECK:       [B4 (ENTRY)]
+// CHECK-NEXT:    Succs (1): B3
+// CHECK:       [B1]
+// CHECK-NEXT:   label:
+// CHECK-NEXT:    1: CFGScopeEnd(n2t)
+// CHECK-NEXT:    2: CFGScopeEnd(n1t)
+// CHECK-NEXT:    3: [B3.3].~A() (Implicit destructor)
+// CHECK-NEXT:    4: CFGScopeEnd(a)
+// CHECK-NEXT:    Preds (2): B2 B3
+// CHECK-NEXT:    Succs (1): B0
+// CHECK:       [B2]
+// CHECK-NEXT:    1: [B3.9].~A() (Implicit destructor)
+// CHECK-NEXT:    2: CFGScopeEnd(n2s)
+// CHECK-NEXT:    3: [B3.6].~A() (Implicit destructor)
+// CHECK-NEXT:    4: CFGScopeEnd(n1s)
+// CHECK-NEXT:    5: CFGScopeBegin(n1t)
+// CHECK-NEXT:    6: int n1t;
+// CHECK-NEXT:    7: CFGScopeBegin(n2t)
+// CHECK-NEXT:    8: int n2t;
+// CHECK-NEXT:    Succs (1): B1
+// CHECK:       [B3]
+// CHECK-NEXT:    1: CFGScopeBegin(a)
+// CHECK-NEXT:    2:  (CXXConstructExpr, [B3.3], A)
+// CHECK-NEXT:    3: A a;
+// CHECK-NEXT:    4: CFGScopeBegin(n1s)
+// CHECK-NEXT:    5:  (CXXConstructExpr, [B3.6], A)
+// CHECK-NEXT:    6: A n1s;
+// CHECK-NEXT:    7: CFGScopeBegin(n2s)
+// CHECK-NEXT:    8:  (CXXConstructExpr, [B3.9], A)
+// CHECK-NEXT:    9: A n2s;
+// CHECK-NEXT:   10: [B3.9].~A() (Implicit destructor)
+// CHECK-NEXT:   11: CFGScopeEnd(n2s)
+// CHECK-NEXT:   12: [B3.6].~A() (Implicit destructor)
+// CHECK-NEXT:   13: CFGScopeEnd(n1s)
+// CHECK-NEXT:   14: CFGScopeBegin(n1t)
+// CHECK-NEXT:   15: CFGScopeBegin(n2t)
+// CHECK-NEXT:    T: goto label;
+// CHECK-NEXT:    Preds (1): B4
+// CHECK-NEXT:    Succs (1): B1
+// CHECK:       [B0 (EXIT)]
+// CHECK-NEXT:    Preds (1): B1
+void test_goto_multiple_scopes() {
+  A a;
+  {
+    A n1s;
+    {
+      A n2s;
+      goto label;
+    }
+  }
+  {
+    int n1t;
+    {
+      int n2t;
+label:
+    }
+  }
+}
+
+// CHECK:       [B5 (ENTRY)]
+// CHECK-NEXT:    Succs (1): B3
+// CHECK:       [B1]
+// CHECK-NEXT:    1: [B2.8].~A() (Implicit destructor)
+// CHECK-NEXT:    2: CFGScopeEnd(n2s)
+// CHECK-NEXT:    3: [B2.5].~A() (Implicit destructor)
+// CHECK-NEXT:    4: CFGScopeEnd(n1s)
+// CHECK-NEXT:    5: [B3.3].~A() (Implicit destructor)
+// CHECK-NEXT:    6: CFGScopeEnd(a)
+// CHECK-NEXT:    Succs (1): B0
+// CHECK:       [B2]
+// CHECK-NEXT:   label:
+// CHECK-NEXT:    1: CFGScopeEnd(n2t)
+// CHECK-NEXT:    2: CFGScopeEnd(n1t)
+// CHECK-NEXT:    3: CFGScopeBegin(n1s)
+// CHECK-NEXT:    4:  (CXXConstructExpr, [B2.5], A)
+// CHECK-NEXT:    5: A n1s;
+// CHECK-NEXT:    6: CFGScopeBegin(n2s)
+// CHECK-NEXT:    7:  (CXXConstructExpr, [B2.8], A)
+// CHECK-NEXT:    8: A n2s;
+// CHECK-NEXT:    Preds (2): B3 B4
+// CHECK-NEXT:    Succs (1): B4
+// CHECK:       [B3]
+// CHECK-NEXT:    1: CFGScopeBegin(a)
+// CHECK-NEXT:    2:  (CXXConstructExpr, [B3.3], A)
+// CHECK-NEXT:    3: A a;
+// CHECK-NEXT:    4: CFGScopeBegin(n1t)
+// CHECK-NEXT:    5: int n1t;
+// CHECK-NEXT:    6: CFGScopeBegin(n2t)
+// CHECK-NEXT:    7: int n2t;
+// CHECK-NEXT:    Preds (1): B5
+// CHECK-NEXT:    Succs (1): B2
+// CHECK:       [B4]
+// CHECK-NEXT:    1: [B2.8].~A() (Implicit destructor)
+// CHECK-NEXT:    2: CFGScopeEnd(n2s)
+// CHECK-NEXT:    3: [B2.5].~A() (Implicit destructor)
+// CHECK-NEXT:    4: CFGScopeEnd(n1s)
+// CHECK-NEXT:    5: CFGScopeBegin(n1t)
+// CHECK-NEXT:    6: CFGScopeBegin(n2t)
+// CHECK-NEXT:    T: goto label;
+// CHECK-NEXT:    Preds (1): B2
+// CHECK-NEXT:    Succs (1): B2
+// CHECK:       [B0 (EXIT)]
+// CHECK-NEXT:    Preds (1): B1
+void test_backpatched_goto_multiple_scopes() {
+  A a;
+  {
+    int n1t;
+    {
+      int n2t;
+label:
+    }
+  }
+{
+  A n1s;
+  {
+    A n2s;
+    goto label;
+  }
+}
+}
+
+// CHECK:       [B8 (ENTRY)]
+// CHECK-NEXT:    Succs (1): B7
+// CHECK:       [B1]
+// CHECK-NEXT:   label:
+// CHECK-NEXT:    1: CFGScopeEnd(n2t)
+// CHECK-NEXT:    2: CFGScopeEnd(n1t)
+// CHECK-NEXT:    Preds (4): B2 B3 B4 B6
+// CHECK-NEXT:    Succs (1): B0
+// CHECK:       [B2]
+// CHECK-NEXT:    T: goto label;
+// CHECK-NEXT:    Preds (1): B3
+// CHECK-NEXT:    Succs (1): B1
+// CHECK:       [B3]
+// CHECK-NEXT:    1: CFGScopeBegin(n2t)
+// CHECK-NEXT:    2: int n2t;
+// CHECK-NEXT:    3: UV
+// CHECK-NEXT:    4: [B3.3] (ImplicitCastExpr, LValueToRValue, _Bool)
+// CHECK-NEXT:    T: if [B3.4]
+// CHECK-NEXT:    Preds (1): B5
+// CHECK-NEXT:    Succs (2): B2 B1
+// CHECK:       [B4]
+// CHECK-NEXT:    1: CFGScopeBegin(n2t)
+// CHECK-NEXT:    T: goto label;
+// CHECK-NEXT:    Preds (1): B5
+// CHECK-NEXT:    Succs (1): B1
+// CHECK:       [B5]
+// CHECK-NEXT:    1: CFGScopeBegin(n1t)
+// CHECK-NEXT:    2: int n1t;
+// CHECK-NEXT:    3: UV
+// CHECK-NEXT:    4: [B5.3] (ImplicitCastExpr, LValueToRValue, _Bool)
+// CHECK-NEXT:    T: if [B5.4]
+// CHECK-NEXT:    Preds (1): B7
+// CHECK-NEXT:    Succs (2): B4 B3
+// CHECK:       [B6]
+// CHECK-NEXT:    1: CFGScopeBegin(n1t)
+// CHECK-NEXT:    2: CFGScopeBegin(n2t)
+// CHECK-NEXT:    T: goto label;
+// CHECK-NEXT:    Preds (1): B7
+// CHECK-NEXT:    Succs (1): B1
+// CHECK:       [B7]
+// CHECK-NEXT:    1: UV
+// CHECK-NEXT:    2: [B7.1] (ImplicitCastExpr, LValueToRValue, _Bool)
+// CHECK-NEXT:    T: if [B7.2]
+// CHECK-NEXT:    Preds (1): B8
+// CHECK-NEXT:    Succs (2): B6 B5
+// CHECK:       [B0 (EXIT)]
+// CHECK-NEXT:    Preds (1): B1
+void test_multiple_goto_entering_scopes() {
+  if (UV) goto label;
+  {
+    int n1t;
+    if (UV) goto label;
+    {
+      int n2t;
+      if (UV) goto label;
+label:
+    }
+  }
+}