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

Hi @all,

I hit a problem with Polly-generated code which llvm.org/PR32251 . The
problem is how @llvm.lifetime.start is placed after Polly transformed
the code. Basically Polly transformed

    llvm.lifetime.start(&var)
    [...]
    llvm.lifetime.end(&var)

into

    if (c) {
      llvm.lifetime.start(&var)
    }
    [...]
    llvm.lifetime.end(&var)


now the llvm.lifetime.end is not dominated by the corresponding
llvm.lifetime.start. As far as I understand the documentation [1] this
is a valid construction, meaning that the value of var is only
undefined before some point when c is true. I don't expect the
compiler to exploit this.

However, this miscompiles since r270559 ("Rework/enhance stack
coloring data flow analysis", https://reviews.llvm.org/D18827)

I modified Polly's code generator to produce

    if (c) {
      llvm.lifetime.start(&var)
    } else {
      llvm.lifetime.start(&var)
    }
    [...]
    llvm.lifetime.end(&var)

and it does not miscompile anymore. However, Polly is currently is not
able to compute the lifetime in the general case.

Question: Is this a bug in the stack coloring algorithm or should this
be fixed in Polly?


Side question: Are there any invalid combinations of
llvm.lifetime.start/end such as

    llvm.lifetime.end(&var)
    llvm.lifetime.start(&var)

(my interpretation would be that var is always dead)? With invalid I
mean that the compiler does not need to handle this case.

Regards,
Michael

[1] http://llvm.org/docs/LangRef.html#llvm-lifetime-start-intrinsic

Hello Michael,

Perhaps you could share a little more detail about your test case and the
specific failure mode. Without seeing the uses of the variable, it's hard
to tell how the new algorithm is going to behave.

More specifically, when you say "miscompiles", I assume that this
means
that StackColoring has overlapped two variables whose lifetimes are on fact
not disjoint after all?

The pattern you describe (where the lifetime start doesn't strictly
dominate the lifetime end) is referred to in the current stack coloring
source code as a "degenerate" lifetime; there is code that
specifically
looks for such cases and treats them more conservatively than well-formed
lifetimes (this is described in the "Implementation Notes" comment in
the
source starting around line 90). The key question however is where the uses
of the variable are relative to the lifetime start/end markers.

For your side question (are there invalid ways to use lifetime start/end),
I don't think I really have a good answer there. What I have seen on my own
is that lifetime start/end markers tend to start out in more
reasonable/sane configurations, but then can be perturbed / rearranged
during optimization, resulting in orderings that don't always make sense
(such as the case you cite). My feeling is that this is OK, and that the
stack coloring code should be able to tolerate that sort of perturbation.

Thanks, Than


On Wed, Mar 29, 2017 at 7:39 AM, Michael Kruse <llvmdev at meinersbur.de>
wrote:
> Hi @all,
>
> I hit a problem with Polly-generated code which llvm.org/PR32251 . The
> problem is how @llvm.lifetime.start is placed after Polly transformed
> the code. Basically Polly transformed
>
>     llvm.lifetime.start(&var)
>     [...]
>     llvm.lifetime.end(&var)
>
> into
>
>     if (c) {
>       llvm.lifetime.start(&var)
>     }
>     [...]
>     llvm.lifetime.end(&var)
>
>
> now the llvm.lifetime.end is not dominated by the corresponding
> llvm.lifetime.start. As far as I understand the documentation [1] this
> is a valid construction, meaning that the value of var is only
> undefined before some point when c is true. I don't expect the
> compiler to exploit this.
>
> However, this miscompiles since r270559 ("Rework/enhance stack
> coloring data flow analysis", https://reviews.llvm.org/D18827)
>
> I modified Polly's code generator to produce
>
>     if (c) {
>       llvm.lifetime.start(&var)
>     } else {
>       llvm.lifetime.start(&var)
>     }
>     [...]
>     llvm.lifetime.end(&var)
>
> and it does not miscompile anymore. However, Polly is currently is not
> able to compute the lifetime in the general case.
>
> Question: Is this a bug in the stack coloring algorithm or should this
> be fixed in Polly?
>
>
> Side question: Are there any invalid combinations of
> llvm.lifetime.start/end such as
>
>     llvm.lifetime.end(&var)
>     llvm.lifetime.start(&var)
>
> (my interpretation would be that var is always dead)? With invalid I
> mean that the compiler does not need to handle this case.
>
> Regards,
> Michael
>
> [1] http://llvm.org/docs/LangRef.html#llvm-lifetime-start-intrinsic
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170329/1724d00b/attachment.html>

2017-03-29 14:19 GMT+02:00 Than McIntosh <thanm at
google.com>:
> Hello Michael,
>
> Perhaps you could share a little more detail about your test case and the
> specific failure mode. Without seeing the uses of the variable, it's
hard to
> tell how the new algorithm is going to behave.
The test case that fails as mentioned in llvm.org/PR32251 is SPEC
CPU's 2006 444.namd (version 1.1). In its main function there are
several structs on the stack and annotated with lifetime markers.
Polly does the previously mentioned transformation on one of those
markers (which is not intended).

Because the SPEC2006 is proprietary, I am not sure that I can share
any code on the public mailing list. If I can convince you to look
into it, I can send you source and the IR Polly is generating.

> More specifically, when you say "miscompiles", I assume that this
means that
> StackColoring has overlapped two variables whose lifetimes are on fact not
> disjoint after all?
I diagnosed a miscompile because test-suite found that the program's
output defers from the reference output. I did not look specifically
what it does wrong. It did not miscompile before r270559 (git bisect).

> The pattern you describe (where the lifetime start doesn't strictly
dominate
> the lifetime end) is referred to in the current stack coloring source code
> as a "degenerate" lifetime; there is code that specifically looks
for such
> cases and treats them more conservatively than well-formed lifetimes (this
> is described in the "Implementation Notes" comment in the source
starting
> around line 90). The key question however is where the uses of the variable
> are relative to the lifetime start/end markers.
I only overflew https://reviews.llvm.org/D18827 to find whether that
case is mentioned, but couldn't find something.

The degenerate case described moves the computation of the pointer
before the LIFETIME_START marker, but the markers themselves are still
(post-)dominating each other. As not being familiar with the code,
this does not seem to be equivalent to my case.

> For your side question (are there invalid ways to use lifetime start/end),
I
> don't think I really have a good answer there. What I have seen on my
own is
> that lifetime start/end markers tend to start out in more reasonable/sane
> configurations, but then can be perturbed / rearranged during optimization,
> resulting in orderings that don't always make sense (such as the case
you
> cite). My feeling is that this is OK, and that the stack coloring code
> should be able to tolerate that sort of perturbation.
Thanks for your thoughts.

Michael

I think lifetime start / end are poorly specified and need to be replaced.
However, I've said that a lot, I haven't done anything about it myself,
and
people are probably tired of hearing me say it by now.

I think Polly's transform is valid and this is a bug in stack coloring.
Stack coloring needs to be able to cope with unmatched lifetime intrinsics.

On Wed, Mar 29, 2017 at 4:39 AM, Michael Kruse via llvm-dev <
llvm-dev at lists.llvm.org> wrote:
> Hi @all,
>
> I hit a problem with Polly-generated code which llvm.org/PR32251 . The
> problem is how @llvm.lifetime.start is placed after Polly transformed
> the code. Basically Polly transformed
>
>     llvm.lifetime.start(&var)
>     [...]
>     llvm.lifetime.end(&var)
>
> into
>
>     if (c) {
>       llvm.lifetime.start(&var)
>     }
>     [...]
>     llvm.lifetime.end(&var)
>
>
> now the llvm.lifetime.end is not dominated by the corresponding
> llvm.lifetime.start. As far as I understand the documentation [1] this
> is a valid construction, meaning that the value of var is only
> undefined before some point when c is true. I don't expect the
> compiler to exploit this.
>
> However, this miscompiles since r270559 ("Rework/enhance stack
> coloring data flow analysis", https://reviews.llvm.org/D18827)
>
> I modified Polly's code generator to produce
>
>     if (c) {
>       llvm.lifetime.start(&var)
>     } else {
>       llvm.lifetime.start(&var)
>     }
>     [...]
>     llvm.lifetime.end(&var)
>
> and it does not miscompile anymore. However, Polly is currently is not
> able to compute the lifetime in the general case.
>
> Question: Is this a bug in the stack coloring algorithm or should this
> be fixed in Polly?
>
>
> Side question: Are there any invalid combinations of
> llvm.lifetime.start/end such as
>
>     llvm.lifetime.end(&var)
>     llvm.lifetime.start(&var)
>
> (my interpretation would be that var is always dead)? With invalid I
> mean that the compiler does not need to handle this case.
>
> Regards,
> Michael
>
> [1] http://llvm.org/docs/LangRef.html#llvm-lifetime-start-intrinsic
> _______________________________________________
> 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/20170329/d858f5af/attachment.html>

I've updated the bug with my analysis.

Than


On Wed, Mar 29, 2017 at 12:39 PM, Reid Kleckner via llvm-dev <
llvm-dev at lists.llvm.org> wrote:
> I think lifetime start / end are poorly specified and need to be replaced.
> However, I've said that a lot, I haven't done anything about it
myself, and
> people are probably tired of hearing me say it by now.
>
> I think Polly's transform is valid and this is a bug in stack coloring.
> Stack coloring needs to be able to cope with unmatched lifetime intrinsics.
>
> On Wed, Mar 29, 2017 at 4:39 AM, Michael Kruse via llvm-dev <
> llvm-dev at lists.llvm.org> wrote:
>
>> Hi @all,
>>
>> I hit a problem with Polly-generated code which llvm.org/PR32251 . The
>> problem is how @llvm.lifetime.start is placed after Polly transformed
>> the code. Basically Polly transformed
>>
>>     llvm.lifetime.start(&var)
>>     [...]
>>     llvm.lifetime.end(&var)
>>
>> into
>>
>>     if (c) {
>>       llvm.lifetime.start(&var)
>>     }
>>     [...]
>>     llvm.lifetime.end(&var)
>>
>>
>> now the llvm.lifetime.end is not dominated by the corresponding
>> llvm.lifetime.start. As far as I understand the documentation [1] this
>> is a valid construction, meaning that the value of var is only
>> undefined before some point when c is true. I don't expect the
>> compiler to exploit this.
>>
>> However, this miscompiles since r270559 ("Rework/enhance stack
>> coloring data flow analysis", https://reviews.llvm.org/D18827)
>>
>> I modified Polly's code generator to produce
>>
>>     if (c) {
>>       llvm.lifetime.start(&var)
>>     } else {
>>       llvm.lifetime.start(&var)
>>     }
>>     [...]
>>     llvm.lifetime.end(&var)
>>
>> and it does not miscompile anymore. However, Polly is currently is not
>> able to compute the lifetime in the general case.
>>
>> Question: Is this a bug in the stack coloring algorithm or should this
>> be fixed in Polly?
>>
>>
>> Side question: Are there any invalid combinations of
>> llvm.lifetime.start/end such as
>>
>>     llvm.lifetime.end(&var)
>>     llvm.lifetime.start(&var)
>>
>> (my interpretation would be that var is always dead)? With invalid I
>> mean that the compiler does not need to handle this case.
>>
>> Regards,
>> Michael
>>
>> [1] http://llvm.org/docs/LangRef.html#llvm-lifetime-start-intrinsic
>> _______________________________________________
>> LLVM Developers mailing list
>> llvm-dev at lists.llvm.org
>> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>>
>
>
> _______________________________________________
> 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/20170330/ddc7ab42/attachment.html>

On Wed, Mar 29, 2017 at 4:39 AM, Michael Kruse via llvm-dev <
llvm-dev at lists.llvm.org> wrote:
> Hi @all,
>
> I hit a problem with Polly-generated code which llvm.org/PR32251 . The
> problem is how @llvm.lifetime.start is placed after Polly transformed
> the code. Basically Polly transformed
>
>     llvm.lifetime.start(&var)
>     [...]
>     llvm.lifetime.end(&var)
>
> into
>
>     if (c) {
>       llvm.lifetime.start(&var)
>     }
>     [...]
>     llvm.lifetime.end(&var)
>
>
> now the llvm.lifetime.end is not dominated by the corresponding
> llvm.lifetime.start.


Which is not sensible but valid.

It's not sensible in the sense that it's not clear what
"before" means in
the documentation. There are several reasonable interpretations.
IE if the path through C is never taken, does that mean the lifetime never
starts?


The only sensible approach i know of is that every path to a lifetime end
must hit a lifetime.start or the lifetime is  UB along that path.
That would outlaw the above :P

You could also go with the scope of lifetime.end is formed by the members
of the post-dominance frontier, etc, and remove lifetime.start.

As far as I understand the documentation [1] this
> is a valid construction, meaning that the value of var is only
> undefined before some point when c is true. I don't expect the
> compiler to exploit this.
>
i do not believe it can be correct in all cases without correct dominance
and post-dominance info.


>
> However, this miscompiles since r270559 ("Rework/enhance stack
> coloring data flow analysis", https://reviews.llvm.org/D18827)
>
> I modified Polly's code generator to produce
>
>     if (c) {
>       llvm.lifetime.start(&var)
>     } else {
>       llvm.lifetime.start(&var)
>     }
>     [...]
>     llvm.lifetime.end(&var)
>
> and it does not miscompile anymore. However, Polly is currently is not
> able to compute the lifetime in the general case.
>
Of course, nothing is.
But they are also metadata, so you could just drop them if you wanted.

>
> Question: Is this a bug in the stack coloring algorithm or should this
> be fixed in Polly?
>
It's a bug in the semantics of lifetime.start/lifetime.end
 :)
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170330/d3e0d4cb/attachment.html>

I'm with Reid on this one.
Even the current specification is so underspecified as to mean pretty much
anything you like :)
But also like reid, i feel like this pops up every few months and we just
hatchet job it until we get something working again, and since i'm not
going to change that anytime soon,  so ...


On Wed, Mar 29, 2017 at 9:39 AM, Reid Kleckner via llvm-dev <
llvm-dev at lists.llvm.org> wrote:
> I think lifetime start / end are poorly specified and need to be replaced.
> However, I've said that a lot, I haven't done anything about it
myself, and
> people are probably tired of hearing me say it by now.
>
> I think Polly's transform is valid and this is a bug in stack coloring.
> Stack coloring needs to be able to cope with unmatched lifetime intrinsics.
>
> On Wed, Mar 29, 2017 at 4:39 AM, Michael Kruse via llvm-dev <
> llvm-dev at lists.llvm.org> wrote:
>
>> Hi @all,
>>
>> I hit a problem with Polly-generated code which llvm.org/PR32251 . The
>> problem is how @llvm.lifetime.start is placed after Polly transformed
>> the code. Basically Polly transformed
>>
>>     llvm.lifetime.start(&var)
>>     [...]
>>     llvm.lifetime.end(&var)
>>
>> into
>>
>>     if (c) {
>>       llvm.lifetime.start(&var)
>>     }
>>     [...]
>>     llvm.lifetime.end(&var)
>>
>>
>> now the llvm.lifetime.end is not dominated by the corresponding
>> llvm.lifetime.start. As far as I understand the documentation [1] this
>> is a valid construction, meaning that the value of var is only
>> undefined before some point when c is true. I don't expect the
>> compiler to exploit this.
>>
>> However, this miscompiles since r270559 ("Rework/enhance stack
>> coloring data flow analysis", https://reviews.llvm.org/D18827)
>>
>> I modified Polly's code generator to produce
>>
>>     if (c) {
>>       llvm.lifetime.start(&var)
>>     } else {
>>       llvm.lifetime.start(&var)
>>     }
>>     [...]
>>     llvm.lifetime.end(&var)
>>
>> and it does not miscompile anymore. However, Polly is currently is not
>> able to compute the lifetime in the general case.
>>
>> Question: Is this a bug in the stack coloring algorithm or should this
>> be fixed in Polly?
>>
>>
>> Side question: Are there any invalid combinations of
>> llvm.lifetime.start/end such as
>>
>>     llvm.lifetime.end(&var)
>>     llvm.lifetime.start(&var)
>>
>> (my interpretation would be that var is always dead)? With invalid I
>> mean that the compiler does not need to handle this case.
>>
>> Regards,
>> Michael
>>
>> [1] http://llvm.org/docs/LangRef.html#llvm-lifetime-start-intrinsic
>> _______________________________________________
>> LLVM Developers mailing list
>> llvm-dev at lists.llvm.org
>> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>>
>
>
> _______________________________________________
> 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/20170330/f8ef72cd/attachment-0001.html>

2017-03-31 0:19 GMT+02:00 Daniel Berlin <dberlin at
dberlin.org>:
>> I modified Polly's code generator to produce
>>
>>     if (c) {
>>       llvm.lifetime.start(&var)
>>     } else {
>>       llvm.lifetime.start(&var)
>>     }
>>     [...]
>>     llvm.lifetime.end(&var)
>>
>> and it does not miscompile anymore. However, Polly is currently is not
>> able to compute the lifetime in the general case.
>
>
> Of course, nothing is.
> But they are also metadata, so you could just drop them if you wanted.
This is actually exactly what Polly did, but only in the optimized
side of the loop versioning. The original code version is not touched,
which keeps the llvm.lifetime.start in it.

So of the bug is on Polly's side, I would "fix" it by deleting all
lifetime markers also in the original code.

Michael