llvm dev - Aug 2016 - RFC: We should stop merging allocas in the inliner

The existing lifetime start/end is not very well defined (by spec, or by
code) in what it means, so you could have nested lifetime markers if you
wanted.   If you made the spec well-defined, they would be meaningful (for
loops, etc).

There are a number of open bugs/complaints about lifetime markers and the
fact that the scope is not well defined (the spec says "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'.)

"Before" is not a well-defined term :)  (the end code says after,
which has
similar problems)

Trivial case:

Two block loop consists, lifetime maker at beginning

A
|  ^
|    \
|    |
|   |
v /
B

Lifetime marker is at top of A.

Is B before A? (if not, are we using dominates as the definition of
"before", because B is a predecessor of A)
Does the answer change if i put a jump to B somewhere above A?
If we use dominates, and i put a jump there, i can make A and B dominator
tree siblings.  Is the pointer now invalid? :)

etc

I suspect what is really wanted is "i want lifetime markers to specify that
this thing has single-iteration scope, function scope, or SESE/SEME region
scope"  (or something).



On Mon, Aug 1, 2016 at 8:36 AM, David Blaikie via llvm-dev <
llvm-dev at lists.llvm.org> wrote:
> Would we want to wrap any of the allocas we do import while inlining in
> extra lifetime markers? (not sure if nested lifetime markers are
> supported/meaningful - maybe just in the case where there are no lifetime
> markers already?) So that non-Clang IR clients still get stack reuse for
> inlined stack slots?
>
> On Sun, Jul 31, 2016 at 9:48 PM Chandler Carruth via llvm-dev <
> llvm-dev at lists.llvm.org> wrote:
>
>> Chris added alloca merging in the inliner a looooong time ago, 2009.
The
>> reason he added it was because at the time we didn't do stack
coloring and
>> without it we had serious stack size problems in LLVM.
>>
>> Since then, a few rather important things have changed:
>> - We have reasonably powerful stack coloring support in the backend
based
>> on lifetime markers
>> - Clang (the primary frontend I'm aware of that hit issues with
this) is
>> now emitting lifetime markers for essentially everything
>> - Clang even has front-end based -O0 stack reuse tricks
>> - AliasAnalysis has become even more important (extended to codegen
time
>> etc) and relies heavily on distinguishing between allocas.
>> - We have lots of tools like the sanitizers that directly reason about
>> allocas to catch bugs in user programs.
>>
>> The first two changes pretty much completely obviate the need for
alloca
>> merging as far as I'm aware, and the second two changes make the
>> information loss caused by this practice, IMO, really bad.
>>
>> Even if there are problems exposed by turning off alloca merging in the
>> inliner, they are almost certainly deficiencies in stack coloring,
Clang,
>> or other parts of the optimizer that we should fix rather than continue
to
>> ignore.
>>
>> Thoughts? The code changes are easy and mechanical. My plan would be:
>> 1) Add a flag to turn this off.
>> 2) Run benchmarks with flag to make sure things are actually working.
>> 3) Change default for the flag, make sure chaos doesn't ensue.
>> 4) Delete the (quite substantial) complexity associated with this and
the
>> flag.
>> 5) Profit!
>>
>> -Chandler
>> _______________________________________________
>> 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/20160801/59328287/attachment.html>

On Mon, Aug 1, 2016 at 8:58 AM, Daniel Berlin via llvm-dev <
llvm-dev at lists.llvm.org> wrote:
> The existing lifetime start/end is not very well defined (by spec, or by
> code) in what it means, so you could have nested lifetime markers if you
> wanted.   If you made the spec well-defined, they would be meaningful (for
> loops, etc).
>
> There are a number of open bugs/complaints about lifetime markers and the
> fact that the scope is not well defined (the spec says "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'.)
>
> "Before" is not a well-defined term :)  (the end code says after,
which
> has similar problems)
>
> Trivial case:
>
> Two block loop consists, lifetime maker at beginning
>
> A
> |  ^
> |    \
> |    |
> |   |
> v /
> B
>
> Lifetime marker is at top of A.
>
> Is B before A? (if not, are we using dominates as the definition of
> "before", because B is a predecessor of A)
> Does the answer change if i put a jump to B somewhere above A?
> If we use dominates, and i put a jump there, i can make A and B dominator
> tree siblings.  Is the pointer now invalid? :)
>
> etc
>
> I suspect what is really wanted is "i want lifetime markers to specify
> that this thing has single-iteration scope, function scope, or SESE/SEME
> region scope"  (or something).
>

Also having lifetime.start marker seems unnecessary and it makes live range
analysis less precise actually.  One local var can have one single end
marker and multiple implicit start markers (first uses). The end marker
should post-dominate all uses. Having one start marker is like defining a
least common dominator for all the implicit starts which make the resulting
live range strictly 'larger' than necessary.

David




>
>
>
> On Mon, Aug 1, 2016 at 8:36 AM, David Blaikie via llvm-dev <
> llvm-dev at lists.llvm.org> wrote:
>
>> Would we want to wrap any of the allocas we do import while inlining in
>> extra lifetime markers? (not sure if nested lifetime markers are
>> supported/meaningful - maybe just in the case where there are no
lifetime
>> markers already?) So that non-Clang IR clients still get stack reuse
for
>> inlined stack slots?
>>
>
>> On Sun, Jul 31, 2016 at 9:48 PM Chandler Carruth via llvm-dev <
>> llvm-dev at lists.llvm.org> wrote:
>>
>>> Chris added alloca merging in the inliner a looooong time ago,
2009. The
>>> reason he added it was because at the time we didn't do stack
coloring and
>>> without it we had serious stack size problems in LLVM.
>>>
>>> Since then, a few rather important things have changed:
>>> - We have reasonably powerful stack coloring support in the backend
>>> based on lifetime markers
>>> - Clang (the primary frontend I'm aware of that hit issues with
this) is
>>> now emitting lifetime markers for essentially everything
>>> - Clang even has front-end based -O0 stack reuse tricks
>>> - AliasAnalysis has become even more important (extended to codegen
time
>>> etc) and relies heavily on distinguishing between allocas.
>>> - We have lots of tools like the sanitizers that directly reason
about
>>> allocas to catch bugs in user programs.
>>>
>>> The first two changes pretty much completely obviate the need for
alloca
>>> merging as far as I'm aware, and the second two changes make
the
>>> information loss caused by this practice, IMO, really bad.
>>>
>>> Even if there are problems exposed by turning off alloca merging in
the
>>> inliner, they are almost certainly deficiencies in stack coloring,
Clang,
>>> or other parts of the optimizer that we should fix rather than
continue to
>>> ignore.
>>>
>>> Thoughts? The code changes are easy and mechanical. My plan would
be:
>>> 1) Add a flag to turn this off.
>>> 2) Run benchmarks with flag to make sure things are actually
working.
>>> 3) Change default for the flag, make sure chaos doesn't ensue.
>>> 4) Delete the (quite substantial) complexity associated with this
and
>>> the flag.
>>> 5) Profit!
>>>
>>> -Chandler
>>> _______________________________________________
>>> 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
>>
>>
>
> _______________________________________________
> 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/20160801/e6a63cc6/attachment.html>

On Mon, Aug 1, 2016 at 10:12 AM, Xinliang David Li <xinliangli at
gmail.com>
wrote:
>
> On Mon, Aug 1, 2016 at 8:58 AM, Daniel Berlin via llvm-dev <
> llvm-dev at lists.llvm.org> wrote:
>
>> The existing lifetime start/end is not very well defined (by spec, or
by
>> code) in what it means, so you could have nested lifetime markers if
you
>> wanted.   If you made the spec well-defined, they would be meaningful
(for
>> loops, etc).
>>
>> There are a number of open bugs/complaints about lifetime markers and
the
>> fact that the scope is not well defined (the spec says "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'.)
>>
>> "Before" is not a well-defined term :)  (the end code says
after, which
>> has similar problems)
>>
>> Trivial case:
>>
>> Two block loop consists, lifetime maker at beginning
>>
>> A
>> |  ^
>> |    \
>> |    |
>> |   |
>> v /
>> B
>>
>> Lifetime marker is at top of A.
>>
>> Is B before A? (if not, are we using dominates as the definition of
>> "before", because B is a predecessor of A)
>> Does the answer change if i put a jump to B somewhere above A?
>> If we use dominates, and i put a jump there, i can make A and B
dominator
>> tree siblings.  Is the pointer now invalid? :)
>>
>> etc
>>
>> I suspect what is really wanted is "i want lifetime markers to
specify
>> that this thing has single-iteration scope, function scope, or
SESE/SEME
>> region scope"  (or something).
>>
>
>
> Also having lifetime.start marker seems unnecessary and it makes live
> range analysis less precise actually.  One local var can have one single
> end marker and multiple implicit start markers (first uses).
>
The original goal, AFAIK, of lifetime start/end was to say "the frontend
put the alloca/etc here, but that's not really where the lifetime starts,
so please ignore anything between the thing you think is the start and the
real start".

Extend this to structures, where parts of a structure may get used but
other parts still dead for a while.

> The end marker should post-dominate all uses. Having one start marker is
> like defining a least common dominator for all the implicit starts which
> make the resulting live range strictly 'larger' than necessary.
>
Yes, it is possible to track and compute more precise ranges than the
lifetime start markers give you, *assuming* the actual placement of
variables in the IR is accurate to the original block scope (IE nothing
generates uninitialized loads to start), and you compute the ranges before
anything messes that up (IE moves the uses up) :).

Right now, i believe the lifetime start markers are what block things from
moving those loads up, because they just get deleted as undefined :)

In any case, i think this is going to derail chandler's question if we
continue on this thread and not a new one :)

--Dan
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160801/8f8ebeea/attachment.html>