[CodeGen] Don't emit lifetime intrinsics for some local variables

Summary:
Current generation of lifetime intrinsics does not handle cases like:

```
  {
    char x;
  l1:
    bar(&x, 1);
  }
  goto l1;

```
We will get code like this:

```
  %x = alloca i8, align 1
  call void @llvm.lifetime.start(i64 1, i8* nonnull %x)
  br label %l1
l1:
  %call = call i32 @bar(i8* nonnull %x, i32 1)
  call void @llvm.lifetime.end(i64 1, i8* nonnull %x)
  br label %l1
```

So the second time bar was called for x which is marked as dead.
Lifetime markers here are misleading so it's better to remove them at all.
This type of bypasses are rare, e.g. code detects just 8 functions building
clang (2329 targets).

PR28267

Reviewers: eugenis

Subscribers: beanz, mgorny, cfe-commits

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

llvm-svn: 285176

1 files changed, 168 insertions, 0 deletions

diff --git a/clang/lib/CodeGen/VarBypassDetector.cpp b/clang/lib/CodeGen/VarBypassDetector.cpp
new file mode 100644
index 00000000000..cfb93d6a9fc
--- /dev/null
+++ b/clang/lib/CodeGen/VarBypassDetector.cpp
@@ -0,0 +1,168 @@
+//===--- VarBypassDetector.h - Bypass jumps detector --------------*- C++ -*-=//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "VarBypassDetector.h"
+
+#include "clang/AST/Decl.h"
+#include "clang/AST/Expr.h"
+#include "clang/AST/Stmt.h"
+
+using namespace clang;
+using namespace CodeGen;
+
+/// Clear the object and pre-process for the given statement, usually function
+/// body statement.
+void VarBypassDetector::Init(const Stmt *Body) {
+  FromScopes.clear();
+  ToScopes.clear();
+  Bypasses.clear();
+  Scopes = {{~0U, nullptr}};
+  unsigned ParentScope = 0;
+  AlwaysBypassed = !BuildScopeInformation(Body, ParentScope);
+  if (!AlwaysBypassed)
+    Detect();
+}
+
+/// Build scope information for a declaration that is part of a DeclStmt.
+/// Returns false if we failed to build scope information and can't tell for
+/// which vars are being bypassed.
+bool VarBypassDetector::BuildScopeInformation(const Decl *D,
+                                              unsigned &ParentScope) {
+  const VarDecl *VD = dyn_cast<VarDecl>(D);
+  if (VD && VD->hasLocalStorage()) {
+    Scopes.push_back({ParentScope, VD});
+    ParentScope = Scopes.size() - 1;
+  }
+
+  if (const VarDecl *VD = dyn_cast<VarDecl>(D))
+    if (const Expr *Init = VD->getInit())
+      return BuildScopeInformation(Init, ParentScope);
+
+  return true;
+}
+
+/// Walk through the statements, adding any labels or gotos to
+/// LabelAndGotoScopes and recursively walking the AST as needed.
+/// Returns false if we failed to build scope information and can't tell for
+/// which vars are being bypassed.
+bool VarBypassDetector::BuildScopeInformation(const Stmt *S,
+                                              unsigned &origParentScope) {
+  // If this is a statement, rather than an expression, scopes within it don't
+  // propagate out into the enclosing scope. Otherwise we have to worry about
+  // block literals, which have the lifetime of their enclosing statement.
+  unsigned independentParentScope = origParentScope;
+  unsigned &ParentScope =
+      ((isa<Expr>(S) && !isa<StmtExpr>(S)) ? origParentScope
+                                           : independentParentScope);
+
+  unsigned StmtsToSkip = 0u;
+
+  switch (S->getStmtClass()) {
+  case Stmt::IndirectGotoStmtClass:
+    return false;
+
+  case Stmt::SwitchStmtClass:
+    if (const Stmt *Init = cast<SwitchStmt>(S)->getInit()) {
+      if (!BuildScopeInformation(Init, ParentScope))
+        return false;
+      ++StmtsToSkip;
+    }
+    if (const VarDecl *Var = cast<SwitchStmt>(S)->getConditionVariable()) {
+      if (!BuildScopeInformation(Var, ParentScope))
+        return false;
+      ++StmtsToSkip;
+    }
+  // Fall through
+
+  case Stmt::GotoStmtClass:
+    FromScopes.push_back({S, ParentScope});
+    break;
+
+  case Stmt::DeclStmtClass: {
+    const DeclStmt *DS = cast<DeclStmt>(S);
+    for (auto *I : DS->decls())
+      if (!BuildScopeInformation(I, origParentScope))
+        return false;
+    return true;
+  }
+
+  case Stmt::CaseStmtClass:
+  case Stmt::DefaultStmtClass:
+  case Stmt::LabelStmtClass:
+    llvm_unreachable("the loop bellow handles labels and cases");
+    break;
+
+  default:
+    break;
+  }
+
+  for (const Stmt *SubStmt : S->children()) {
+    if (!SubStmt)
+      continue;
+    if (StmtsToSkip) {
+      --StmtsToSkip;
+      continue;
+    }
+
+    // Cases, labels, and defaults aren't "scope parents".  It's also
+    // important to handle these iteratively instead of recursively in
+    // order to avoid blowing out the stack.
+    while (true) {
+      const Stmt *Next;
+      if (const SwitchCase *SC = dyn_cast<SwitchCase>(SubStmt))
+        Next = SC->getSubStmt();
+      else if (const LabelStmt *LS = dyn_cast<LabelStmt>(SubStmt))
+        Next = LS->getSubStmt();
+      else
+        break;
+
+      ToScopes[SubStmt] = ParentScope;
+      SubStmt = Next;
+    }
+
+    // Recursively walk the AST.
+    if (!BuildScopeInformation(SubStmt, ParentScope))
+      return false;
+  }
+  return true;
+}
+
+/// Checks each jump and stores each variable declaration they bypass.
+void VarBypassDetector::Detect() {
+  for (const auto &S : FromScopes) {
+    const Stmt *St = S.first;
+    unsigned from = S.second;
+    if (const GotoStmt *GS = dyn_cast<GotoStmt>(St)) {
+      if (const LabelStmt *LS = GS->getLabel()->getStmt())
+        Detect(from, ToScopes[LS]);
+    } else if (const SwitchStmt *SS = dyn_cast<SwitchStmt>(St)) {
+      for (const SwitchCase *SC = SS->getSwitchCaseList(); SC;
+           SC = SC->getNextSwitchCase()) {
+        Detect(from, ToScopes[SC]);
+      }
+    } else {
+      llvm_unreachable("goto or switch was expected");
+    }
+  }
+}
+
+/// Checks the jump and stores each variable declaration it bypasses.
+void VarBypassDetector::Detect(unsigned From, unsigned To) {
+  while (From != To) {
+    if (From < To) {
+      assert(Scopes[To].first < To);
+      const auto &ScopeTo = Scopes[To];
+      To = ScopeTo.first;
+      Bypasses.insert(ScopeTo.second);
+    } else {
+      assert(Scopes[From].first < From);
+      From = Scopes[From].first;
+    }
+  }
+}