[CodeGen] Move lifetime.start of a variable when goto jumps back past its declaration

[ahatanak]

Summary

This patch attempts to fix the bug discussed here:

http://lists.llvm.org/pipermail/cfe-dev/2016-July/050066.html

This patch fixes the bug by moving the lifetime.start of a variable to the beginning of its lexical scope.

int move_lifetime_start(int a) {
  int *p = 0;
  // This patch moves lifetime.start for "i" to the beginning of the function.
 label1:
  if (p) {
    foo2(*p); // The storage of "i" has to be kept alive when goto jumps to label1.
    return 0;
  }

  int i = 999; // lifetime.start for "i" used to be inserted here.
  if (a != 2) {
    p = &i;
    goto label1;
  }
  return -1;
}

[ahatanak]

Add cfe-commits.

[majnemer]

lib/CodeGen/CodeGenFunction.h

619 ↗

(On Diff #81099)

This can be written as llvm::is_contained(Labels, LD);

[ahatanak]

Address review comment. Use llvm::is_contained instead of std::find.

[ahatanak]

Rebase and improve test cases.

• Add "-mllvm -disable-llvm-optzns" to the RUN line.
• Add a test case that shows lifetime.start of a variable isn't moved to the beginning of its scope when the goto leaves the scope.

[rjmccall]

Wouldn't it be simpler to just record an insertion point for the beginning of the current lexical scope and insert the lifetime.begin there instead of at the current IP?

lib/CodeGen/CodeGenFunction.h

351 ↗

(On Diff #82142)

Addr and Size are recoverable from this.

[ahatanak]

Remove Addr and Size from CallLifetimeEnd.

[ahatanak]

In D27680#628272, @rjmccall wrote:

Wouldn't it be simpler to just record an insertion point for the beginning of the current lexical scope and insert the lifetime.begin there instead of at the current IP?

I'm not sure I understood your comment, but it seems to me that simply moving the lifetime.start intrinsics to the current lexical scope wouldn't work in a case like this:

{ // This is the previous lexical scope.
label1:
  ...
  int a; // We want to move the lifetime.start for "a" to the beginning of this scope (not the current lexical scope), since goto is not leaving its scope.
  ...
  { // This is the current lexical scope.
    int b; // We don't want to move the lifetime.start for "b", since goto is leaving its scope.
    goto label1;
  }
}

Currently, the lifetime.start is inserted at the beginning of the basic block of the lexical scope holding the goto's destination.

Let me know if I misunderstood your comment or you've found a flaw in this approach.

[rjmccall]

In D27680#629182, @ahatanak wrote:

In D27680#628272, @rjmccall wrote:

Wouldn't it be simpler to just record an insertion point for the beginning of the current lexical scope and insert the lifetime.begin there instead of at the current IP?

I'm not sure I understood your comment, but it seems to me that simply moving the lifetime.start intrinsics to the current lexical scope wouldn't work in a case like this:

I'm suggesting that, instead of moving instructions retroactively when you see a goto, you just insert the lifetime.start intrinsics at the start of the current lexical scope when you're emitting the variable. That more exactly models the C language rule, I think, and shouldn't have any significant negative impact on optimization.

[ahatanak]

Ah, good idea. That sounds like a much simpler and less invasive approach. I agree that the performance impact would probably be small, and if it turns out to have a significant impact, we can reduce the number of times we move the lifetime.start (without moving it retroactively) by checking whether a label was seen.

I'll see if I can come with a new patch.

[ahatanak]

When compiling for C, insert lifetime.start at the beginning of the current lexical scope, rather than moving it retroactively when a goto jumps backwards over the variable declaration.

Also, insert lifetime.start at a more precise location, rather than always inserting it at the beginning of a basic block. This enables keeping the live ranges disjoint in some cases. For example, in the following code, the live ranges of a and b would overlap if the lifetime.starts were moved to the beginning of the basic block, but would be disjoint if moved to the beginning of their lexical scopes:

void foo1() {

{
  int a[5];
  foo2(a);
}
{
  int b[5];
  foo2(b);
}

}

[rjmccall]

In D27680#630192, @ahatanak wrote:

Ah, good idea. That sounds like a much simpler and less invasive approach. I agree that the performance impact would probably be small, and if it turns out to have a significant impact, we can reduce the number of times we move the lifetime.start (without moving it retroactively) by checking whether a label was seen.

Oh, good idea, that's a great way to heuristically get the performance back if we decide it's important.

lib/CodeGen/CGDecl.cpp

917 ↗

(On Diff #82421)

BB->begin() is not necessarily a legal place to insert a call. This could happen if e.g. a scope was unconditionally entered after a statement including a ternary expression.

Also, I think lexical scopes don't necessarily have an active basic block upon entry, because their entry can be unreachable. This happens most importantly with e.g. switch statements, but can also happen with goto or simply with unreachable code (which it's still important to not crash on).

[ahatanak]

lib/CodeGen/CGDecl.cpp

917 ↗

(On Diff #82421)

I'm not sure why BB->begin() wouldn't be the right place to insert a call when a scope is entered after a ternary expression. Is it because EmitConditionalOperatorLValue inserts a phi at the beginning of block "cond.end"?

Also, I'm not sure when goto or unreachable code might be mis-compiled. Could you elaborate further on that? I can see now why lifetime.start can be inserted at a wrong location when lowering switch statements because EmitSwitchStmt creates and inserts a SwitchInst before a lexical scope is entered, but I'm not sure about the other two cases you mentioned.

[ahatanak]

lib/CodeGen/CGDecl.cpp

917 ↗

(On Diff #82421)

Also, I realized this patch doesn't always insert lifetime.start at the beginning of the block the variable is associated with. For example, when the following code is compiled, lifetime.start for "i" is inserted after the call to foo2, but it should be inserted before the call (at the beginning of the function):

void foo1(int a) {
  foo2();
  for (int i = 0; i < 10; ++i)
    foo3();
}

I'll fix this in my next patch.

[rjmccall]

lib/CodeGen/CGDecl.cpp

917 ↗

(On Diff #82421)

Yes, my point was about PHIs and any other instruction that might be required to appear at the start of a block.

[ahatanak]

I found another problem with the current patch: it can generate IR that doesn't pass asan's use-after-scope check. For example, IRGen generates the following IR for function move_lifetime_start in lifetime2.c when this patch is applied:

entry:
  %i = alloca i32, align 4
  %0 = bitcast i32* %i to i8*
  call void @llvm.lifetime.start(i64 4, i8* nonnull %0) #3
  %cmp = icmp eq i32 %a, 2
  br label %label1

label1:                                           ; preds = %if.end, %entry
  %p.0 = phi i32* [ null, %entry ], [ %i, %if.end ]
  %tobool = icmp eq i32* %p.0, null
  br i1 %tobool, label %if.end, label %if.then
  ...
if.end:                                           ; preds = %label1
  call void @llvm.lifetime.end(i64 4, i8* nonnull %0) #3
  br i1 %cmp, label %cleanup3.loopexit, label %label1

cleanup3.loopexit:                                ; preds = %if.end
  br label %cleanup3

use-after-scope poisons the memory for "%i" after llvm.lifetime.end and unpoisons it after llvm.lifetime.start, so when the code in block "if.end" jumps back to "label1", it ends up accessing the memory that is still poisoned. I think this can be fixed by making changes in CGCleanup.cpp and moving lifetime.end to block "cleanup3.loopexit", but I'm thinking maybe I should take a different approach.

What if we analyze the AST before IRGen (probably we can do it in VarBypassDetector) and mark those variables whose lifetimes need to be extended and pretend when doing IRGen that those variables are declared at the beginning of their enclosing compound statements? Basically, EmitVarDecl is called for the variables that need extended lifetime before EmitCompoundStmt does IRGen for the body of the compound statement and later when the VarDecl's for those variables are visited, EmitVarDecl returns without doing anything.

I haven't thought through all the details yet, but do you see any problems with this approach?

[ahatanak]

I added an AST analysis pass that is run before IRGen and decides which VarDecls need their lifetimes to be extended or disabled. It only looks at VarDecls which have their addresses taken and are declared after a label is seen. It extends the lifetimes of VarDecls declared in a compound statement if there are backward gotos that don't leave the scope of the compound statement. However, if there are gotos that jump from outside into the compound statement too, it drops all lifetime markers for those VarDecls since emitting lifetime.start at the beginning of the compound statement might break use-after-scope check. For example:

goto label2;

{

// cannot move lifetime.start for "x" to the start of this block since the "goto label2" will
// jump over lifetime.start.
...

label2:

...

label1:

...
int x;
foo1(&x);
goto label1; // backward goto.

}

[rjmccall]

Interesting. That's a pretty heavyweight solution, and you're still missing switches, which have exactly the same "can jump into an arbitrary variable's scope" behavior.

I think maybe an easier solution would be to just remove the begin-lifetime marker completely when there's a label or case statement in its scope. If we want to improve on that, there's already a jump analysis in Sema that could pretty easily be made to mark variables that have jumps into their lifetimes; we would just need to guarantee that that analysis is done.

lib/CodeGen/LifetimeExtend.cpp

11 ↗

(On Diff #83680)

A RecursiveASTVisitor is a rather large thing to instantiate, and we don't need most of its functionality. Stmt already has a children() accessor that returns the range of child statements, which should be sufficient.

[ahatanak]

In D27680#642770, @rjmccall wrote:

Interesting. That's a pretty heavyweight solution, and you're still missing switches, which have exactly the same "can jump into an arbitrary variable's scope" behavior.

In addition to missing the switches, I realized the code in VisitGotoStmt and VisitLabelStmt isn't correct. For example, in function move_lifetime_start in the test case, it wouldn't move the lifetime markers for "i "if label "label1" were enclosed in a block:

{
 label1:
   p = 0;
}
...
  int i = 999;
  if (ac != 2) {
    p = &i;
    goto label1;
  }
...

I fixed both bugs in my local branch.

I think maybe an easier solution would be to just remove the begin-lifetime marker completely when there's a label or case statement in its scope. If we want to improve on that, there's already a jump analysis in Sema that could pretty easily be made to mark variables that have jumps into their lifetimes; we would just need to guarantee that that analysis is done.

I suppose you are suggesting we avoid emitting lifetime begin and end during IRGen if there is a label preceding the variable declaration (I don't think we have to care about case or default statements since we only have to worry about backward jumps), rather than running an analysis pass before IRGen and stretching the lifetime at IRGen time. If it doesn't have a large impact on performance, we can do that, but otherwise we have to come up with another way to fix this bug.

[ahatanak]

Remove lifetime markers completely for variables that are declared after a label was seen in a compound statement

I tested this patch building llvm's test-suite and SPEC benchmarks with -Os. Surprisingly (maybe not so surprising), none of the 3000+ object files changed, so I think removing the markers should be fine at least for now.

[rjmccall]

lib/CodeGen/CodeGenFunction.h

217 ↗

(On Diff #84434)

Shouldn't this be maintained by some existing scoping structure like LexicalScope?

236 ↗

(On Diff #84434)

A label in a nested scope acts like a label in outer scopes, too.

[ahatanak]

lib/CodeGen/CodeGenFunction.h

217 ↗

(On Diff #84434)

I think I need a structure that gets pushed and popped when we enter and exit a compound statement, but I couldn't find one in CodeGenFunction.

Adding a flag to LexicalScope would fail to disable lifetime markers in some cases. For example, in the code below (which I think is valid), the lifetime markers of "i" wouldn't get disabled because a LexicalScope is pushed at the beginning of CodeGenFunction::EmitForStmt:

void foo2(int *);
int c;

void foo1(int n) {
  int *p = 0;

label1:
  foo2(p);
  for (int i = 0; i < n; ++i)
    if (i == 5)
      p = &i;

  if (c)
    goto label1;
}

If we want to avoid introducing new structures to track labels, perhaps we can just check whether a label was seen so far in the current function rather than the current compound statement, but I'm not sure how much impact that would have on performance.

236 ↗

(On Diff #84434)

I think you are suggesting setting all the flags on the stack rather than just the top (or maybe not?), but I'm not sure why that's necessary. Could you elaborate on your comment a little more and show me a simple example when this code would fail to disable lifetime markers when it should?

The boolean flag set to true is propagated to the outer scope's flag when we have completed processing the compound statement and LabelSeenRAII's destructor is called. So, for example, if I enclose label1 in function jump_backward_over_declaration of the test case,
IRGen disables lifetime markers for "i" even though "i" is declared in the outer compound statement of label1.

[ahatanak]

lib/CodeGen/CodeGenFunction.h

217 ↗

(On Diff #84434)

Alternatively, add a flag to LexicalScope that indicates it was created in EmitCompoundStmtWithoutScope. lifetime markers would be disabled if the flag of the enclosing CompoundStmt's LexicalScope were set.

[rjmccall]

lib/CodeGen/CodeGenFunction.h

217 ↗

(On Diff #84434)

The C language rule is not tied specifically to compound statements; it is tied to "blocks". Selection (if/switch) and iteration (for/do/while) statements are also blocks. So the code is not valid because the lifetime of 'i' is tied to the block of the for statement. This is basically what we currently track with LexicalScope.

The C++ language rule is similar but stricter.

236 ↗

(On Diff #84434)

Okay. And since it's not possible to query a non-active scope's flag, this works.

[ahatanak]

To decide whether lifetime markers should be disabled, check whether the current LexicalScope has labels instead of introducing a new structure that keeps track of labels seen in the current compound statement.

[rjmccall]

Thanks. Some minor changes and then LGTM.

I'm currently wondering if a better solution might be to just teach the Bypasses analysis about the C lifetime rule. But we don't need to do that right now.

lib/CodeGen/CGDecl.cpp

1031 ↗

(On Diff #85643)

It's probably appropriate to just rework this entire comment at this point. Suggestion:

If there's a jump into the lifetime of this variable, its lifetime gets broken
up into several regions in IR, which requires more work to handle correctly.
For now, just omit the intrinsics; this is a rare case, and it's better to just be
conservatively correct.  PR28267.

We have to do this in all language modes if there's a jump past the declaration.
We also have to do it in C if there's a jump to an earlier point in the current
block because non-VLA lifetimes begin as soon as the containing block is
entered, not when its variables actually come into scope; suppressing the
lifetime annotations completely in this case is unnecessarily pessimistic, but
again, this is rare.

lib/CodeGen/CodeGenFunction.h

216 ↗

(On Diff #85643)

It seems reasonable to give this a more descriptive name, like hasLabelBeenSeenInCurrentScope().

[ahatanak]

Yes, we can make VarBypassDetector detect variables declared after labels too if we want to put all the logic for disabling lifetime markers in one place.

[rjmccall]

In D27680#656453, @ahatanak wrote:

Yes, we can make VarBypassDetector detect variables declared after labels too if we want to put all the logic for disabling lifetime markers in one place.

Okay. If that's straightforward, that does seem better. But feel free to use this approach first if there's time pressure.

cfe/trunk/lib/CodeGen/CGDecl.cpp

if (NRVO) {
       // the catch parameter starts in the catchpad instruction, and we can't
       // insert code in those basic blocks.
       bool IsMSCatchParam =
           D.isExceptionVariable() && getTarget().getCXXABI().isMicrosoft();
 
       // Emit a lifetime intrinsic if meaningful. There's no point in doing this
       // if we don't have a valid insertion point (?).
       if (HaveInsertPoint() && !IsMSCatchParam) {
-        // goto or switch-case statements can break lifetime into several
-        // regions which need more efforts to handle them correctly. PR28267
-        // This is rare case, but it's better just omit intrinsics than have
-        // them incorrectly placed.
-        if (!Bypasses.IsBypassed(&D)) {
+        // If there's a jump into the lifetime of this variable, its lifetime
+        // gets broken up into several regions in IR, which requires more work
+        // to handle correctly. For now, just omit the intrinsics; this is a
+        // rare case, and it's better to just be conservatively correct.
+        // PR28267.
+        //
+        // We have to do this in all language modes if there's a jump past the
+        // declaration. We also have to do it in C if there's a jump to an
+        // earlier point in the current block because non-VLA lifetimes begin as
+        // soon as the containing block is entered, not when its variables
+        // actually come into scope; suppressing the lifetime annotations
+        // completely in this case is unnecessarily pessimistic, but again, this
+        // is rare.
+        if (!Bypasses.IsBypassed(&D) &&
+            !(!getLangOpts().CPlusPlus && hasLabelBeenSeenInCurrentScope())) {
           uint64_t size = CGM.getDataLayout().getTypeAllocSize(allocaTy);
           emission.SizeForLifetimeMarkers =
               EmitLifetimeStart(size, address.getPointer());
         }
       } else {
         assert(!emission.useLifetimeMarkers());
       }
     }

cfe/trunk/lib/CodeGen/CodeGenFunction.h

public:
 
   /// ReturnBlock - Unified return block.
   JumpDest ReturnBlock;
 
   /// ReturnValue - The temporary alloca to hold the return
   /// value. This is invalid iff the function has no return value.
   Address ReturnValue;
 
+  /// Return true if a label was seen in the current scope.
+  bool hasLabelBeenSeenInCurrentScope() const {
+    if (CurLexicalScope)
+      return CurLexicalScope->hasLabels();
+    return !LabelMap.empty();
+  }
+
   /// AllocaInsertPoint - This is an instruction in the entry block before which
   /// we prefer to insert allocas.
   llvm::AssertingVH<llvm::Instruction> AllocaInsertPt;
 
   /// \brief API for captured statement code generation.
   class CGCapturedStmtInfo {
   public:
     explicit CGCapturedStmtInfo(CapturedRegionKind K = CR_Default)
public:
     void ForceCleanup() {
       CGF.CurLexicalScope = ParentScope;
       RunCleanupsScope::ForceCleanup();
 
       if (!Labels.empty())
         rescopeLabels();
     }
 
+    bool hasLabels() const {
+      return !Labels.empty();
+    }
+
     void rescopeLabels();
   };
 
   typedef llvm::DenseMap<const Decl *, Address> DeclMapTy;
 
   /// \brief The scope used to remap some variables as private in the OpenMP
   /// loop body (or other captured region emitted without outlining), and to
   /// restore old vars back on exit.

cfe/trunk/test/CodeGen/lifetime2.c

-// RUN: %clang -S -emit-llvm -o - -O2 %s | FileCheck %s -check-prefixes=CHECK,O2
-// RUN: %clang -S -emit-llvm -o - -O2 -Xclang -disable-lifetime-markers %s \
+// RUN: %clang_cc1 -S -emit-llvm -o - -O2 -disable-llvm-passes %s | FileCheck %s -check-prefixes=CHECK,O2
+// RUN: %clang_cc1 -S -emit-llvm -o - -O2 -disable-lifetime-markers %s \
 // RUN:       | FileCheck %s -check-prefixes=CHECK,O0
-// RUN: %clang -S -emit-llvm -o - -O0 %s | FileCheck %s -check-prefixes=CHECK,O0
+// RUN: %clang_cc1 -S -emit-llvm -o - -O0 %s | FileCheck %s -check-prefixes=CHECK,O0
 
 extern int bar(char *A, int n);
 
 // CHECK-LABEL: @foo
 // O0-NOT: @llvm.lifetime.start
 int foo (int n) {
   if (n) {
 // O2: @llvm.lifetime.start
     char A[100];
     return bar(A, 1);
   } else {
 // O2: @llvm.lifetime.start
     char A[100];
     return bar(A, 2);
   }
 }
 
 // CHECK-LABEL: @no_goto_bypass
 void no_goto_bypass() {
   // O2: @llvm.lifetime.start(i64 1
   char x;
 l1:
   bar(&x, 1);
-  // O2: @llvm.lifetime.start(i64 5
-  // O2: @llvm.lifetime.end(i64 5
   char y[5];
   bar(y, 5);
   goto l1;
   // Infinite loop
-  // O2-NOT: @llvm.lifetime.end(i64 1
+  // O2-NOT: @llvm.lifetime.end(
 }
 
 // CHECK-LABEL: @goto_bypass
 void goto_bypass() {
   {
     // O2-NOT: @llvm.lifetime.start(i64 1
     // O2-NOT: @llvm.lifetime.end(i64 1
     char x;

 void indirect_jump(int n) {
   char x;
   // O2-NOT: @llvm.lifetime
   void *T[] = {&&L};
   goto *T[n];
 L:
   bar(&x, 1);
 }
+
+// O2-LABEL: define i32 @jump_backward_over_declaration(
+// O2-NOT: call void @llvm.lifetime.{{.*}}(i64 4,
+
+extern void foo2(int p);
+
+int jump_backward_over_declaration(int a) {
+  int *p = 0;
+label1:
+  if (p) {
+    foo2(*p);
+    return 0;
+  }
+
+  int i = 999;
+  if (a != 2) {
+    p = &i;
+    goto label1;
+  }
+  return -1;
+}