[llvm-dev] Well-formed @llvm.lifetime.start and @llvm.lifetime.end intrinsics

[Michael Kruse via llvm-dev]

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...@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev

[Than McIntosh via llvm-dev]

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

[Michael Kruse via llvm-dev]

2017-03-29 14:19 GMT+02:00 Than McIntosh <th...@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

[Than McIntosh via llvm-dev]

OK, thanks for the additional info.

Sure, if you can send me a runnable test case, I can spend some time in the debugger to learn more about how things are going wrong. It seems unlikely that I would be able to identify the issue just looking at IR dumps or source code, though.

Cheers, Than

[Reid Kleckner via llvm-dev]

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.

[Than McIntosh via llvm-dev]

I've updated the bug with my analysis.

Than

[Daniel Berlin via llvm-dev]

On Wed, Mar 29, 2017 at 4:39 AM, Michael Kruse via llvm-dev <llvm...@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

 :)

[Daniel Berlin via llvm-dev]

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 ...

[Michael Kruse via llvm-dev]

2017-03-31 0:19 GMT+02:00 Daniel Berlin <dbe...@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

[Daniel Berlin via llvm-dev]

On Thu, Mar 30, 2017 at 3:45 PM, Michael Kruse <llv...@meinersbur.de> wrote:

2017-03-31 0:19 GMT+02:00 Daniel Berlin <dbe...@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.

I'm curious, btw, what made it think the above is legal.

The intrinsics are marked as touching memory, having side effects, etc.

Do you guys specially ignore them or something?

[Daniel Berlin via llvm-dev]

(in particular, those things keep LICM from moving them)

[Michael Kruse via llvm-dev]

2017-03-31 0:54 GMT+02:00 Daniel Berlin <dbe...@dberlin.org>:
> I'm curious, btw, what made it think the above is legal.
> The intrinsics are marked as touching memory, having side effects, etc.

The precedes my involvement with Polly.

Polly has a list of intrinsics that can be safely ignored, e.g.
llvm.dbg.value/llvm.gbg.declare. The lifetime markers are also in this
list. Ignored intrinsic are ... well ... ignored when generating the
optimized code.

[Daniel Berlin via llvm-dev]

Interesting.

They are marked this way specifically to prevent things from moving them this way, and it blocks other optimization. So if we are ignoring it to move them, it seems either "they shouldn't be moved", or "we shouldn't  mark them" :P

Thinking harder about this.

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.

[Reid Kleckner via llvm-dev]

It's useful to think about lifetime.start/end as being equivalent to a memset of undef. They effectively clobber what was there and reinitialize it with "nothing". If you transform lifetime.start in a way that would be incorrect if it were storing undef, then that transform is incorrect.

[Daniel Berlin via llvm-dev]

Sure, and you definitely can't transform an unconditional store to a conditional one unless the uses are guarded by the same condition, or you can prove it already had that value (in which case, the memset would also be dead) :)

ie

memset(a, 0)

use a

can't be transformed to

if (c)

  memset(a, 0)

use a

So again, if polly is making a lifetime.start conditional when the use is not conditional, that's a bug in polly, regardless of the bug in stack coloring's ability to handle it.

[David Majnemer via llvm-dev]

Hmm. This doesn't jive with my understanding of how things worked.

I see the lifetime intrinsics as something which _can_ be made conditional on arbitrary control flow. I can build a consistent view of them because I also believe the lifetime intrinsics can only make sense when they are paired together.

Another way of thinking about it is that a store of undef can be used to make an earlier store dead but it can also be safely removed or even be made conditional on arbitrary control flow. There is no non-UB way of detecting that such a store remains or was eliminated.

[Daniel Berlin via llvm-dev]

On Thu, Mar 30, 2017 at 11:42 PM, David Majnemer <david.m...@gmail.com> wrote:

Hmm. This doesn't jive with my understanding of how things worked.

 

 

I see the lifetime intrinsics as something which _can_ be made conditional on arbitrary control flow.

That seems very wrong.

The whole purpose of them was because the middle end *does not know* more than the frontend about the lifetime starting and ending of memory objects

They were not supposed to float.

Much like assume, they were meant to be tethered in place.

Otherwise, they are literally pointless :)

·IE in such a world, we should not be stopping licm, etc, from moving them, and we should stop letting them block optimization by being marked as side-effecting.

Whatever happens to them, happens.

Further, if i can make them conditional on arbitrary control flow, i can cause all the lifetime starts to die, easily, again, something we are specifically marking them as side-effecting to avoid.

ie 

lifetime.start

->

if (dead condition)

 lifetime.start

->

nothing

Now they are all unpaired :)

So maybe you meant something other than arbitrary control flow?

I can probably do worse than this depending on how arbitrary you want (IE shove them into loops in ways that more things are dead than were before)

I can build a consistent view of them because I also believe the lifetime intrinsics can only make sense when they are paired together.

That is also not what our langref says.

It does not require pairing:

For example, for lifetime start:
"This intrinsic indicates that before this point in the code, the value of the memory pointed to by ptr is dead. This means that it is known to never be used and has an undefined value. A load from the pointer that precedes this intrinsic can be replaced with 'undef'."

Ignoring "before this point in the code" (which is the argument we have in the first paragraph), nothing about this requires it be paired.

It would be perfectly reasonable in this definition to have lifetime starts without ends, for things that begin life in the middle of the function but extend past it.

Or to say that after a function call, lifetime of memory object has ended (without it ever starting).

Now, i don't claim these are *good* semantics, but if we want to change them, we should change them, not just do something different than we document :)

(in any case, i believe we are rehashing the fact that we all think these intrinsics are in need of some serious rework to clear up semantics, etc)

[Michael Kruse via llvm-dev]

2017-03-31 1:16 GMT+02:00 Daniel Berlin <dbe...@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?

[Daniel Berlin via llvm-dev]

On Fri, Mar 31, 2017 at 4:05 AM, Michael Kruse <llv...@meinersbur.de> wrote:

2017-03-31 1:16 GMT+02:00 Daniel Berlin <dbe...@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.

 

Michael

[Michael Kruse via llvm-dev]

2017-03-31 3:38 GMT+02:00 Daniel Berlin <dbe...@dberlin.org>:
> Sure, and you definitely can't transform an unconditional store to a
> conditional one unless the uses are guarded by the same condition, or you
> can prove it already had that value (in which case, the memset would also be
> dead) :)
>
> ie
> memset(a, 0)
> use a
>
> can't be transformed to
> if (c)
> memset(a, 0)
> use a
>
> So again, if polly is making a lifetime.start conditional when the use is
> not conditional, that's a bug in polly, regardless of the bug in stack
> coloring's ability to handle it.

InstCombine transforms memset(a,1) to a single StoreInst, but keeps
the memset if the size argument is zero. A StoreInst can be optimized
away, e.g. by DeadStoreElimination. I wonder, are the semantics of
memset(a, 0) different than "do nothing"?

Where is the chain of transformations

memset(&a, '0', sizeof a);
if (c)
a = 1;

=>

if (c) {
memset(&a, '0', sizeof a);
a = 1;
} else
memset(&a, '0', sizeof a);

=>

if (c) {
memset(&a, '0', sizeof a);
a = 1;
} else
memset(&a, '0', sizeof a);

=>

if (c) {
a = 0;
a = 1;
} else
memset(&a, '0', sizeof a);

=>

if (c)
a = 1;
else
memset(&a, '0', sizeof a);

=>
if (c)
a = 0;
if (!c)
memset(&a, '0', sizeof a);

not legal?

[Michael Kruse via llvm-dev]

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.

[Than McIntosh via llvm-dev]

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

[Michael Kruse via llvm-dev]

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.

[Daniel Berlin via llvm-dev]

On Fri, Mar 31, 2017 at 4:48 AM, Michael Kruse <llv...@meinersbur.de> wrote:

2017-03-31 3:38 GMT+02:00 Daniel Berlin <dbe...@dberlin.org>:
> Sure, and you definitely can't transform an unconditional store to a
> conditional one unless the uses are guarded by the same condition, or you
> can prove it already had that value (in which case, the memset would also be
> dead) :)
>
> ie
> memset(a, 0)
> use a
>
> can't be transformed to
> if (c)
>   memset(a, 0)
> use a
>
> So again, if polly is making a lifetime.start conditional when the use is
> not conditional, that's a bug in polly, regardless of the bug in stack
> coloring's ability to handle it.

InstCombine transforms memset(a,1) to a single StoreInst, but keeps
the memset if the size argument is zero. A StoreInst can be optimized
away, e.g. by DeadStoreElimination. I wonder, are the semantics of
memset(a, 0) different than "do nothing"?

Yes, they are, because the value of a could be "not zero" :)

to whit:

if (load a == 50)
  memset (a, 0)

if (load a == 0)

   do something

If *a starts out as 50, this memset makes it do something.

This is completely legal assuming no further use of a in the if(a) block

But lifetime.start is *not* a memset, and as mentioned, it was specifically built to be not moved.

As also mentioned, i think these are crappy semantics, but that's the ones we built ATM :)

 

Michael

[Daniel Berlin via llvm-dev]

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.

[Daniel Berlin via llvm-dev]

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.

[Michael Kruse via llvm-dev]

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

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.