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

2017-03-31 13:46 GMT+02:00 Daniel Berlin <dberlin at
dberlin.org>:
>
>
> On Fri, Mar 31, 2017 at 4:05 AM, Michael Kruse <llvmdev at
meinersbur.de>
> wrote:
>>
>> 2017-03-31 1:16 GMT+02:00 Daniel Berlin <dberlin at dberlin.org>:
>> > if you transformed
>> >
>> > lifetime.start(%p)
>> > use %p
>> > lifetime.end(%p)
>> > into
>> >
>> > if (c)
>> >   lifetime.start(%p)
>> > use %p
>> > lifetime.end(%p)
>> >
>> > That is *definitely* a bug in polly.
>> > Stack coloring should be able to handle it if that is the original
IR
>> > but that is definitely not a legal transform of the
lifetime.start.
>>
>> If it is legal for a frontend to generate it, why is it not legal for
>> a transformation?
>
>
> Errr.
> Because, as mentioned, they are not meant to float.
> They are meant to stay executing under precisely the same conditions the
> frontend gave them.
>
> Also, the set of things for which it is legal for the frontend to do, but
> not you, is infinite.
>
> For example, as mentioned, the frontend may generate:
>
> if (c)
>   memset (a, 0)
> use(a)
>
> But that does not make it legal for you to transform
>
> memset(a, 0)
> use(a)
>
> into
> if (c)
>   memset(a, 0)
> use(a)
>
> unless you can prove a already had the value 0, or that condition c always
> holds.
Because the semantics are different. And you admit yourself that the
transformation can be done if the compiler show that it can do the
transformation if the compiler can show that the value received by
use(a) will be the same.

How I do understand the current the reference manual for
llvm.lifetime.start, the semantics of

llvm.lifetime.start(a)

and

if (c)
  llvm.lifetime.start(a)

are the same if a is not used before that point. According to Than
McIntosh the problem is that StackColoring currently does not
correctly handle the situation.

What I would wish for is that the language reference for lifetime
markers is updated such that it reflects the what StackColoring can
handle, and that the IR verifier fails when the lifetime markes are
not well-formed according to that reference. For instance, we can
define that the end/start marker must (post-)dominate the start/end
marker.

Michael

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.

Thanks, Than


On Fri, Mar 31, 2017 at 8:02 AM, Michael Kruse via llvm-dev <
llvm-dev at lists.llvm.org> wrote:
> 2017-03-31 13:46 GMT+02:00 Daniel Berlin <dberlin at dberlin.org>:
> >
> >
> > On Fri, Mar 31, 2017 at 4:05 AM, Michael Kruse <llvmdev at
meinersbur.de>
> > wrote:
> >>
> >> 2017-03-31 1:16 GMT+02:00 Daniel Berlin <dberlin at
dberlin.org>:
> >> > if you transformed
> >> >
> >> > lifetime.start(%p)
> >> > use %p
> >> > lifetime.end(%p)
> >> > into
> >> >
> >> > if (c)
> >> >   lifetime.start(%p)
> >> > use %p
> >> > lifetime.end(%p)
> >> >
> >> > That is *definitely* a bug in polly.
> >> > Stack coloring should be able to handle it if that is the
original IR
> >> > but that is definitely not a legal transform of the
lifetime.start.
> >>
> >> If it is legal for a frontend to generate it, why is it not legal
for
> >> a transformation?
> >
> >
> > Errr.
> > Because, as mentioned, they are not meant to float.
> > They are meant to stay executing under precisely the same conditions
the
> > frontend gave them.
> >
> > Also, the set of things for which it is legal for the frontend to do,
but
> > not you, is infinite.
> >
> > For example, as mentioned, the frontend may generate:
> >
> > if (c)
> >   memset (a, 0)
> > use(a)
> >
> > But that does not make it legal for you to transform
> >
> > memset(a, 0)
> > use(a)
> >
> > into
> > if (c)
> >   memset(a, 0)
> > use(a)
> >
> > unless you can prove a already had the value 0, or that condition c
> always
> > holds.
>
> Because the semantics are different. And you admit yourself that the
> transformation can be done if the compiler show that it can do the
> transformation if the compiler can show that the value received by
> use(a) will be the same.
>
> How I do understand the current the reference manual for
> llvm.lifetime.start, the semantics of
>
> llvm.lifetime.start(a)
>
> and
>
> if (c)
>   llvm.lifetime.start(a)
>
> are the same if a is not used before that point. According to Than
> McIntosh the problem is that StackColoring currently does not
> correctly handle the situation.
>
> What I would wish for is that the language reference for lifetime
> markers is updated such that it reflects the what StackColoring can
> handle, and that the IR verifier fails when the lifetime markes are
> not well-formed according to that reference. For instance, we can
> define that the end/start marker must (post-)dominate the start/end
> marker.
>
> Michael
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170331/7d5b2a02/attachment.html>

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 5:02 AM, Michael Kruse <llvmdev at meinersbur.de>
wrote:
> 2017-03-31 13:46 GMT+02:00 Daniel Berlin <dberlin at dberlin.org>:
> >
> >
> > On Fri, Mar 31, 2017 at 4:05 AM, Michael Kruse <llvmdev at
meinersbur.de>
> > wrote:
> >>
> >> 2017-03-31 1:16 GMT+02:00 Daniel Berlin <dberlin at
dberlin.org>:
> >> > if you transformed
> >> >
> >> > lifetime.start(%p)
> >> > use %p
> >> > lifetime.end(%p)
> >> > into
> >> >
> >> > if (c)
> >> >   lifetime.start(%p)
> >> > use %p
> >> > lifetime.end(%p)
> >> >
> >> > That is *definitely* a bug in polly.
> >> > Stack coloring should be able to handle it if that is the
original IR
> >> > but that is definitely not a legal transform of the
lifetime.start.
> >>
> >> If it is legal for a frontend to generate it, why is it not legal
for
> >> a transformation?
> >
> >
> > Errr.
> > Because, as mentioned, they are not meant to float.
> > They are meant to stay executing under precisely the same conditions
the
> > frontend gave them.
> >
> > Also, the set of things for which it is legal for the frontend to do,
but
> > not you, is infinite.
> >
> > For example, as mentioned, the frontend may generate:
> >
> > if (c)
> >   memset (a, 0)
> > use(a)
> >
> > But that does not make it legal for you to transform
> >
> > memset(a, 0)
> > use(a)
> >
> > into
> > if (c)
> >   memset(a, 0)
> > use(a)
> >
> > unless you can prove a already had the value 0, or that condition c
> always
> > holds.
>
> Because the semantics are different. And you admit yourself that the
> transformation can be done if the compiler show that it can do the
> transformation if the compiler can show that the value received by
> use(a) will be the same.
>
> How I do understand the current the reference manual for
> llvm.lifetime.start, the semantics of
>
> llvm.lifetime.start(a)
>
> and
>
> if (c)
>   llvm.lifetime.start(a)
>
> are the same if a is not used before that point.

Assuming by before, you mean post-dominance or something, yes, i'd agree.
Yes, *assuming it stays that way* in the IR :)


According to Than
> McIntosh the problem is that StackColoring currently does not
> correctly handle the situation.
>
>
What I would wish for is that the language reference for
lifetime
> markers is updated such that it reflects the what StackColoring can
> handle, and that the IR verifier fails when the lifetime markes are
> not well-formed according to that reference. For instance, we can
> define that the end/start marker must (post-)dominate the start/end
> marker.
>
>
I believe, at this point, most of us wish for someting strong: that we
ripped them out by their tendrils, and replaced them withs ometing with
very well defined and useful semantics that are easy to verify.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170331/a326d34d/attachment.html>