llvm dev - Mar 2017 - Well-formed @llvm.lifetime.start and @llvm.lifetime.end intrinsics

2017-03-31 15:00 GMT+02:00 Than McIntosh <thanm at
google.com>:
> Hi all,
>
> Just to clarify: the code I'm seeing in the stack coloring dumps is a
little
> different from what is being discussed in previous spots in this thread.
The
> example that Michael cited earlier on was
>
>     if (c) {
>       llvm.lifetime.start(&var)
>     }
>     [...]
>     llvm.lifetime.end(&var)
>
> however what I'm seeing is:
>
>     entry block:
>     [...]
>     if (c) {           // conditional branch terminating entry block
>       llvm.lifetime.start(&var)
>       [...]
>       exit(..);        // this is a no-return-call
>     }
>     [...]
>     llvm.lifetime.end(&var)
>
> In the first example there is a path from the lifetime start op to uses of
> the variable. In the second example (which is what I see when I look at the
> stack coloring dumps) there is no such path.
>
> Looking at the code in clang (e.g. CodeGenFunction::EmitAutoVarAlloca) it
is
> pretty clear to me that when the lifetime marker is first manufactured, it
> is placed into the entry block. I don't know enough about how Polly
operates
> to understand why it is migrating the lifetime in question down into the
> block containing the exit... but it seems to me that this is really the
crux
> of the problem.
Thank you for the clarification. I indeed did not consider that the
exit/unreachable makes a difference.

This is what happens in Polly:

  llvm.lifetime.start(&var)
  if (c) {
    call void @_z10exit_usagepkc
    unreachable // because exit_usage is no-return
  }

- Optimistically assume that no functions are executed or control flow
ends in an unreachable. It can determine the condition c1 for when no
such thing ever appears (in which case c1 is just "true")
- Version the old code and the new code:

if (c1) {
  // optimized code without lifetime markers
  ...
} else {
 // Orginal code, not modified by Polly
  llvm.lifetime.start(&var);
  if (c) {
    call void @_z10exit_usagepkc
    unreachable // because exit_usage is no-return
  }
}

In this case c happens to be equal to c1, in which case I guess some
pass removes the inner inner conditional because it is always true.

How do you think code versioning in general should handle this? I
looked into LoopVersioning.cpp (used by LLVM's vectorizer), but could
not see how it handles this situation. Maybe it is not affected
because lifetime markers usually do not cross loop bounds.

Michael

On Fri, Mar 31, 2017 at 6:22 AM, Michael Kruse <llvmdev at meinersbur.de>
wrote:
> 2017-03-31 15:00 GMT+02:00 Than McIntosh <thanm at google.com>:
> > Hi all,
> >
> > Just to clarify: the code I'm seeing in the stack coloring dumps
is a
> little
> > different from what is being discussed in previous spots in this
thread.
> The
> > example that Michael cited earlier on was
> >
> >     if (c) {
> >       llvm.lifetime.start(&var)
> >     }
> >     [...]
> >     llvm.lifetime.end(&var)
> >
> > however what I'm seeing is:
> >
> >     entry block:
> >     [...]
> >     if (c) {           // conditional branch terminating entry block
> >       llvm.lifetime.start(&var)
> >       [...]
> >       exit(..);        // this is a no-return-call
> >     }
> >     [...]
> >     llvm.lifetime.end(&var)
> >
> > In the first example there is a path from the lifetime start op to
uses
> of
> > the variable. In the second example (which is what I see when I look
at
> the
> > stack coloring dumps) there is no such path.
> >
> > Looking at the code in clang (e.g. CodeGenFunction::EmitAutoVarAlloca)
> it is
> > pretty clear to me that when the lifetime marker is first
manufactured,
> it
> > is placed into the entry block. I don't know enough about how
Polly
> operates
> > to understand why it is migrating the lifetime in question down into
the
> > block containing the exit... but it seems to me that this is really
the
> crux
> > of the problem.
>
> Thank you for the clarification. I indeed did not consider that the
> exit/unreachable makes a difference.
>
> This is what happens in Polly:
>
>   llvm.lifetime.start(&var)
>   if (c) {
>     call void @_z10exit_usagepkc
>     unreachable // because exit_usage is no-return
>   }
>
> - Optimistically assume that no functions are executed or control flow
> ends in an unreachable. It can determine the condition c1 for when no
> such thing ever appears (in which case c1 is just "true")
> - Version the old code and the new code:
>
> if (c1) {
>   // optimized code without lifetime markers
>   ...
> } else {
>  // Orginal code, not modified by Polly
>   llvm.lifetime.start(&var);
>   if (c) {
>     call void @_z10exit_usagepkc
>     unreachable // because exit_usage is no-return
>   }
> }
>
>
> In this case c happens to be equal to c1, in which case I guess some
> pass removes the inner inner conditional because it is always true.
>
> How do you think code versioning in general should handle this?

Assuming you don't want to drop them:

If you are only duplicating code structurally, and not moving it past any
statements, and assuming we fix the semantics:
When you start, the lifetime starts for a pointer should jointly (IE
considered as a set) dominate the lifetime ends.
The lifetime ends for a pointer should jointly post-dominate each lifetime
start.

Thus, when duplicating, you would copy into program points to make that
true. That is if you want to try to remain optimal.
Trivially, you can always just hoist lifetime.start and sink lifetime.end
until the above is true again.
Note;
You may not move a lifetime.start past a memory using statement unless you
can prove the memory using statement is noalias the lifetime'd pointer.

otherwise, trivially:

int *a;
int *b;
intptr_t c;

lifetime.start(a)
c = inttoptr (a)
b = ptrtoint(c)
load b

->
c = inttoptr (a)
b = ptrtoint(c)
load b
lifetime.start(a)

->
GVN or something smart will prove a == b, and replace them.

load a
lifetime.start(a)

whoops






I
> looked into LoopVersioning.cpp (used by LLVM's vectorizer), but could
> not see how it handles this situation. Maybe it is not affected
> because lifetime markers usually do not cross loop bounds.
>
Yes, the other things won't do this because lifetime.start is
side-effecting so they won't move it.

Note: MemorySSA also ignores the side-effects of lifetime.start, but we
expect clients to handle it.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170331/5fab568c/attachment.html>

2017-03-31 19:32 GMT+02:00 Daniel Berlin <dberlin at
dberlin.org>:
>
>
> On Fri, Mar 31, 2017 at 6:22 AM, Michael Kruse <llvmdev at
meinersbur.de>
> wrote:
>>
>> 2017-03-31 15:00 GMT+02:00 Than McIntosh <thanm at google.com>:
>> > Hi all,
>> >
>> > Just to clarify: the code I'm seeing in the stack coloring
dumps is a
>> > little
>> > different from what is being discussed in previous spots in this
thread.
>> > The
>> > example that Michael cited earlier on was
>> >
>> >     if (c) {
>> >       llvm.lifetime.start(&var)
>> >     }
>> >     [...]
>> >     llvm.lifetime.end(&var)
>> >
>> > however what I'm seeing is:
>> >
>> >     entry block:
>> >     [...]
>> >     if (c) {           // conditional branch terminating entry
block
>> >       llvm.lifetime.start(&var)
>> >       [...]
>> >       exit(..);        // this is a no-return-call
>> >     }
>> >     [...]
>> >     llvm.lifetime.end(&var)
>> >
>> > In the first example there is a path from the lifetime start op to
uses
>> > of
>> > the variable. In the second example (which is what I see when I
look at
>> > the
>> > stack coloring dumps) there is no such path.
>> >
>> > Looking at the code in clang (e.g.
CodeGenFunction::EmitAutoVarAlloca)
>> > it is
>> > pretty clear to me that when the lifetime marker is first
manufactured,
>> > it
>> > is placed into the entry block. I don't know enough about how
Polly
>> > operates
>> > to understand why it is migrating the lifetime in question down
into the
>> > block containing the exit... but it seems to me that this is
really the
>> > crux
>> > of the problem.
>>
>> Thank you for the clarification. I indeed did not consider that the
>> exit/unreachable makes a difference.
>>
>> This is what happens in Polly:
>>
>>   llvm.lifetime.start(&var)
>>   if (c) {
>>     call void @_z10exit_usagepkc
>>     unreachable // because exit_usage is no-return
>>   }
>>
>> - Optimistically assume that no functions are executed or control flow
>> ends in an unreachable. It can determine the condition c1 for when no
>> such thing ever appears (in which case c1 is just "true")
>> - Version the old code and the new code:
>>
>> if (c1) {
>>   // optimized code without lifetime markers
>>   ...
>> } else {
>>  // Orginal code, not modified by Polly
>>   llvm.lifetime.start(&var);
>>   if (c) {
>>     call void @_z10exit_usagepkc
>>     unreachable // because exit_usage is no-return
>>   }
>> }
>>
>
>>
>> In this case c happens to be equal to c1, in which case I guess some
>> pass removes the inner inner conditional because it is always true.
Small correction: c == !c1.

>>
>> How do you think code versioning in general should handle this?
>
>
> Assuming you don't want to drop them:
>
> If you are only duplicating code structurally, and not moving it past any
> statements, and assuming we fix the semantics:
> When you start, the lifetime starts for a pointer should jointly (IE
> considered as a set) dominate the lifetime ends.
> The lifetime ends for a pointer should jointly post-dominate each lifetime
> start.
This would be great to be mentioned at
http://llvm.org/docs/LangRef.html#llvm-lifetime-start-intrinsic
>
> Thus, when duplicating, you would copy into program points to make that
> true. That is if you want to try to remain optimal.
> Trivially, you can always just hoist lifetime.start and sink lifetime.end
> until the above is true again.
> Note;
> You may not move a lifetime.start past a memory using statement unless you
> can prove the memory using statement is noalias the lifetime'd pointer.
>
> otherwise, trivially:
>
> int *a;
> int *b;
> intptr_t c;
>
> lifetime.start(a)
> c = inttoptr (a)
> b = ptrtoint(c)
> load b
>
> ->
> c = inttoptr (a)
> b = ptrtoint(c)
> load b
> lifetime.start(a)
>
> ->
> GVN or something smart will prove a == b, and replace them.
>
> load a
> lifetime.start(a)
>
> whoops
I try to summarize: One can move lifetime.start arbitrarily up into
dominators, even if crossing instructions affecting the memory pointed
to, but only downwards if anything in-between touching memory
noaliases it.

Thanks for your suggestions.

Michael