On Wed, Nov 5, 2014 at 11:17 AM, Philip Reames <listmail at philipreames.com> wrote:> > On 11/05/2014 10:54 AM, Reid Kleckner wrote: > > This seems fine to me. The optimizer can (soundly) conclude that %p is >> dead after the "lifetime.end" (for the two instructions), and dead before >> the "lifetime.start" (for the *single* instruction in that basic block, >> *not* for the previous BB). This seems like the proper result for this >> example, am I missing something? >> > > What if I put that in a loop, unroll it once, and prove that the > lifetime.start is unreachable? We would end up with IR like: > > loop: > ... use %p > call void @lifetime.end( %p ) > ... use %p > call void @lifetime.end( %p ) > br i1 %c, label %loop, label %exit > > Are the second uses of %p uses of dead memory? > > It's hard to discuss this without being specific about the starting IR and > transforms. My general response is that either a) such a transform > wouldn't be valid or b) the behaviour of the original program was > undefined. >The starting IR would be something that jumps into the middle of a lifetime region, like the example that Arnaud gave. This was assuming the current state of the world where we haven't added a second lifetime start call prior to the goto branch. Start with something like: void f(int x) { while (x) { goto skip_start; { int y; // lifetime.start skip_start: y = g(); x -= y; // lifetime.end } } } The block containing the lifetime start of y is unreachable and can be deleted. -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20141105/d8004b30/attachment.html>
From: Reid Kleckner [mailto:rnk at google.com]
Sent: 05 November 2014 22:49
To: Philip Reames
Cc: Arnaud De Grandmaison; LLVM Developers Mailing List
Subject: Re: [LLVMdev] lifetime.start/end clarification
On Wed, Nov 5, 2014 at 11:17 AM, Philip Reames <listmail at
philipreames.com> wrote:
On 11/05/2014 10:54 AM, Reid Kleckner wrote:
This seems fine to me. The optimizer can (soundly) conclude that %p is dead
after the "lifetime.end" (for the two instructions), and dead before
the "lifetime.start" (for the *single* instruction in that basic
block, *not* for the previous BB). This seems like the proper result for this
example, am I missing something?
What if I put that in a loop, unroll it once, and prove that the lifetime.start
is unreachable? We would end up with IR like:
loop:
... use %p
call void @lifetime.end( %p )
... use %p
call void @lifetime.end( %p )
br i1 %c, label %loop, label %exit
Are the second uses of %p uses of dead memory?
It's hard to discuss this without being specific about the starting IR and
transforms. My general response is that either a) such a transform wouldn't
be valid or b) the behaviour of the original program was undefined.
The starting IR would be something that jumps into the middle of a lifetime
region, like the example that Arnaud gave. This was assuming the current state
of the world where we haven't added a second lifetime start call prior to
the goto branch.
Start with something like:
void f(int x) {
while (x) {
goto skip_start;
{
int y; // lifetime.start
skip_start:
y = g();
x -= y;
// lifetime.end
}
}
}
The block containing the lifetime start of y is unreachable and can be deleted.
On this example, I think the critical edge to the skip_start label need to get a
lifetime.start inserted (btw, we already insert there a gep to the alloca to
solve a dominator issue), and this makes sense because such an edge also
contains (in essence) the trivial constructors of the scope where the label is.
This looks to me as a hint that when they are used with an alloca,
lifetime.start/end really have to be paired, and that all possible uses of the
alloca should be covered by a [start,end] :
- In the above testcase, when the path from lifetime.end is walked-up the cfg,
it reaches the alloca, and this is weird.
- In my testcase, when the paths from lifetime.start and lifetime.end are
walked-up the cfg, it becomes inconsistent in the entry block: one path will
tell it’s dead, the other it’s alive.
This puts the burden onto clang to generate consistent marker info, which sounds
reasonable after all.
I can probably add some checks to enforce this in llvm, or at least detect such
cases: this will definitely help me to spot candidates for the miscompilation I
observe, which by the way is not caused by unnamed temporaries, but by standard
VarDecl + lifetime markers. I do not know yet where though. It means that we
have a lurking bug today in-tree, and changing the size threshold for marker
insertion is enough to trigger it.
Cheers,
Arnaud
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20141106/181e231b/attachment.html>
On 11/05/2014 01:48 PM, Reid Kleckner wrote:> On Wed, Nov 5, 2014 at 11:17 AM, Philip Reames > <listmail at philipreames.com <mailto:listmail at philipreames.com>> wrote: > > > On 11/05/2014 10:54 AM, Reid Kleckner wrote: >> >> This seems fine to me. The optimizer can (soundly) conclude >> that %p is dead after the "lifetime.end" (for the two >> instructions), and dead before the "lifetime.start" (for the >> *single* instruction in that basic block, *not* for the >> previous BB). This seems like the proper result for this >> example, am I missing something? >> >> >> What if I put that in a loop, unroll it once, and prove that the >> lifetime.start is unreachable? We would end up with IR like: >> >> loop: >> ... use %p >> call void @lifetime.end( %p ) >> ... use %p >> call void @lifetime.end( %p ) >> br i1 %c, label %loop, label %exit >> >> Are the second uses of %p uses of dead memory? > It's hard to discuss this without being specific about the > starting IR and transforms. My general response is that either a) > such a transform wouldn't be valid or b) the behaviour of the > original program was undefined. > > > The starting IR would be something that jumps into the middle of a > lifetime region, like the example that Arnaud gave. This was assuming > the current state of the world where we haven't added a second > lifetime start call prior to the goto branch. > > Start with something like: > > void f(int x) { > while (x) { > goto skip_start; > { > int y; // lifetime.start > skip_start: > y = g(); > x -= y; > // lifetime.end > } > } > } > > The block containing the lifetime start of y is unreachable and can be > deleted.If I'm understanding you right, we'd have something like this: void f(int x) { (space for y reserved, no lifetime start) while (x) { { y = g(); x -= y; // lifetime.end } } } I don't see the problem here. We have a BB (or set of BBs) which contains: { y = g(); x -= y; // lifetime.end(y) } with *two* predecessors. *One* of those predecessors contains the lifetime.end, the other does not. Thus there is a path where the store for y is defined. If I'm interpreting the original code correctly, that's exactly the right semantic. This code is poorly defined if-and-only-if the backedge is taken. To say this differently, the original program had a dynamic trace (before optimization) where two "ends" where not separated by a "start". That's a bug in the frontend. To fix it, the frontend needs a lifetime.start in the source of the goto. (We haven't actually settled the semantics of a sequence of end,start,end. My view is there are reasonable semantics - which I'm using here - for that sequence and important use cases in loops. As the actual documentation says at this point, the lifetime markers would have to be outside the loop. That's just "obviously" silly though.) Philip -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20141105/aa738e5b/attachment.html>
On 11/05/2014 03:08 PM, Arnaud A. de Grandmaison wrote:> > *From:*Reid Kleckner [mailto:rnk at google.com] > *Sent:* 05 November 2014 22:49 > *To:* Philip Reames > *Cc:* Arnaud De Grandmaison; LLVM Developers Mailing List > *Subject:* Re: [LLVMdev] lifetime.start/end clarification > > On Wed, Nov 5, 2014 at 11:17 AM, Philip Reames > <listmail at philipreames.com <mailto:listmail at philipreames.com>> wrote: > > On 11/05/2014 10:54 AM, Reid Kleckner wrote: > > This seems fine to me. The optimizer can (soundly) conclude > that %p is dead after the "lifetime.end" (for the two > instructions), and dead before the "lifetime.start" (for the > *single* instruction in that basic block, *not* for the > previous BB). This seems like the proper result for this > example, am I missing something? > > What if I put that in a loop, unroll it once, and prove that the > lifetime.start is unreachable? We would end up with IR like: > > loop: > > ... use %p > > call void @lifetime.end( %p ) > > ... use %p > > call void @lifetime.end( %p ) > > br i1 %c, label %loop, label %exit > > Are the second uses of %p uses of dead memory? > > It's hard to discuss this without being specific about the starting IR > and transforms. My general response is that either a) such a > transform wouldn't be valid or b) the behaviour of the original > program was undefined. > > The starting IR would be something that jumps into the middle of a > lifetime region, like the example that Arnaud gave. This was assuming > the current state of the world where we haven't added a second > lifetime start call prior to the goto branch. > > Start with something like: > > void f(int x) { > > while (x) { > > goto skip_start; > > { > > int y; // lifetime.start > > skip_start: > > y = g(); > > x -= y; > > // lifetime.end > > } > } > } > > The block containing the lifetime start of y is unreachable and can be > deleted. > > On this example, I think the critical edge to the skip_start label > need to get a lifetime.start inserted (btw, we already insert there a > gep to the alloca to solve a dominator issue), and this makes sense > because such an edge also contains (in essence) the trivial > constructors of the scope where the label is. >Well said. This is exactly the point I've been trying to make.> > This looks to me as a hint that when they are used with an alloca, > lifetime.start/end really have to be paired, and that all possible > uses of the alloca should be covered by a [start,end] : > > - In the above testcase, when the path from lifetime.end is walked-up > the cfg, it reaches the alloca, and this is weird. > > - In my testcase, when the paths from lifetime.start and lifetime.end > are walked-up the cfg, it becomes inconsistent in the entry block: one > path will tell it’s dead, the other it’s alive. > > This puts the burden onto clang to generate consistent marker info, > which sounds reasonable after all. >My analysis is slightly different, but the result is the same. I don't believe that a dynamic trace of {end, use, end} should be well defined. I'm suggesting we extend the current semantics to make the trace {end, start, use, end} meaningful. It's the frontends job to ensure that no dynamic traces of the first type are possible if the second is meant.> > I can probably add some checks to enforce this in llvm, or at least > detect such cases: this will definitely help me to spot candidates for > the miscompilation I observe, which by the way is not caused by > unnamed temporaries, but by standard VarDecl + lifetime markers. I do > not know yet where though. It means that we have a lurking bug today > in-tree, and changing the size threshold for marker insertion is > enough to trigger it. >I agree with this analysis.> > Cheers, > > Arnaud >-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20141105/52315f24/attachment.html>