Page MenuHomePhabricator

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

Authored by ahatanak on Dec 12 2016, 9:47 AM.

Details

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;
}

Diff Detail

Event Timeline

ahatanak updated this revision to Diff 81099.Dec 12 2016, 9:47 AM
ahatanak retitled this revision from to [CodeGen] Move lifetime.start of a variable when goto jumps back past its declaration.
ahatanak updated this object.
ahatanak added reviewers: rjmccall, rsmith.
ahatanak added a subscriber: cfe-commits.

Add cfe-commits.

majnemer added inline comments.
lib/CodeGen/CodeGenFunction.h
656

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

ahatanak updated this revision to Diff 81284.Dec 13 2016, 12:37 PM

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

ahatanak updated this revision to Diff 82142.Dec 20 2016, 1:28 PM

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 edited edge metadata.Dec 20 2016, 2:28 PM

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
350

Addr and Size are recoverable from this.

ahatanak updated this revision to Diff 82279.Dec 21 2016, 3:06 PM
ahatanak edited edge metadata.
ahatanak marked an inline comment as done.

Remove Addr and Size from CallLifetimeEnd.

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.

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.

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 updated this revision to Diff 82421.Dec 23 2016, 2:03 PM

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);
}

}

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
913

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 added inline comments.Jan 3 2017, 7:52 AM
lib/CodeGen/CGDecl.cpp
913

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 added inline comments.Jan 3 2017, 8:14 AM
lib/CodeGen/CGDecl.cpp
913

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 added inline comments.Jan 3 2017, 8:38 AM
lib/CodeGen/CGDecl.cpp
913

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

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 updated this revision to Diff 83680.Jan 9 2017, 1:41 PM

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.

}

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.

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 updated this revision to Diff 84434.Jan 13 2017, 11:07 PM

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 added inline comments.Jan 23 2017, 12:16 PM
lib/CodeGen/CodeGenFunction.h
217

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

236

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

ahatanak added inline comments.Jan 24 2017, 1:34 PM
lib/CodeGen/CodeGenFunction.h
217

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

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 added inline comments.Jan 24 2017, 1:49 PM
lib/CodeGen/CodeGenFunction.h
217

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 added inline comments.Jan 24 2017, 2:05 PM
lib/CodeGen/CodeGenFunction.h
217

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

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

ahatanak updated this revision to Diff 85643.Jan 24 2017, 3:22 PM
ahatanak marked an inline comment as done.

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 accepted this revision.Jan 24 2017, 4:25 PM

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
1027

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

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

This revision is now accepted and ready to land.Jan 24 2017, 4:25 PM
ahatanak updated this revision to Diff 85774.Jan 25 2017, 10:26 AM
ahatanak marked 2 inline comments as done.

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.

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.

This revision was automatically updated to reflect the committed changes.