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

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

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

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.

I’ve updated the bug with my analysis.

Than

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 :stuck_out_tongue:

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
:slight_smile:

I’m with Reid on this one.
Even the current specification is so underspecified as to mean pretty much anything you like :slight_smile:

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 …

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

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?

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

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.

Michael

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” :stuck_out_tongue:

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.

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.

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) :slight_smile:

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.

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.

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 :slight_smile:
·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 :slight_smile:

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 :slight_smile:

(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)

If it is legal for a frontend to generate it, why is it not legal for
a transformation?

Michael

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

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