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

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
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160801/6f898dd7/attachment.html>

On Sun, Jul 31, 2016 at 9:47 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:
>
There is one caveat: stop doing stack merging in inliner will change the
inliner cost analysis which may have affect inlining decisions and
performance in an unexpected way.  For instance, the allocatedSize estimate
won't be as accurate due to double counting.

> 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.
>
The code handling the merging seems to be in an isolated place with <100
lines of code. While I agree this change may be something good to do in
principle -- are there any practical reason for doing this? you mentioned
information loss (aliasing, sanitizer etc) -- are there any real issues
caused by the merging (with tracking bugs)?

David


> 5) Profit!
>
> -Chandler
>
> _______________________________________________
> 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/96c37e7e/attachment.html>

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
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160801/a06376a2/attachment.html>

I want to double check, but I believe it already does exactly that. If not,
yes, we should synthesize lifetime markers just to be safe.

On Mon, Aug 1, 2016, 08:36 David Blaikie <dblaikie at gmail.com> 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
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160801/954fdaac/attachment.html>

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>

I just want to note that there's currently a miscompile in C code with
lifetime markers:
  http://lists.llvm.org/pipermail/cfe-dev/2016-July/050066.html

Depending on how we fix that, we could end up being more pessimistic about when
markers are emitted.  I suggest we fix that before benchmarking this change.
> On 2016-Jul-31, at 21:47, 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

Yeah, this is a reverse variant of the example i posted to david blaikie :)

Assuming y'all are certain this is supposed to do something sensible in C,
outside of "stop emitting lifetime markers in functions with jumps past
variable initialization", getting a conservatively right answer is ...
non-trivial AFAIK.



On Mon, Aug 1, 2016 at 5:51 PM, Duncan P. N. Exon Smith via llvm-dev <
llvm-dev at lists.llvm.org> wrote:
> I just want to note that there's currently a miscompile in C code with
> lifetime markers:
>   http://lists.llvm.org/pipermail/cfe-dev/2016-July/050066.html
>
> Depending on how we fix that, we could end up being more pessimistic about
> when markers are emitted.  I suggest we fix that before benchmarking this
> change.
>
> > On 2016-Jul-31, at 21:47, 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/4812901f/attachment.html>

On Mon, Aug 1, 2016 at 5:51 PM Duncan P. N. Exon Smith via llvm-dev <
llvm-dev at lists.llvm.org> wrote:
> I just want to note that there's currently a miscompile in C code with
> lifetime markers:
>   http://lists.llvm.org/pipermail/cfe-dev/2016-July/050066.html
>
> Depending on how we fix that, we could end up being more pessimistic about
> when markers are emitted.  I suggest we fix that before benchmarking this
> change.
>
That shouldn't impact this change.

The inliner will emit *inlining* based lifetime markers all on its own for
any static allocas that the frontend doesn't annotate. So we could turn off
all lifetime markers in Clang and the merging here should still not be
necessary to get the stack savings.

(And I have now verified that yes, the inliner inserts these markers...)
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160802/60b4d3c6/attachment.html>

> On Jul 31, 2016, at 9:47 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:
I like the principal idea.
> 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.
What does this imply? Just run-time?  I’d like to see stack size data w/ and w/o
the change and  - just in case - an investigation/fix of the outliers. Any
thoughts about compile-time and code size?

You probably also want to collect the data across more than one platform.

> 4) Delete the (quite substantial) complexity associated with this and the
flag.
You might need to allow target specific behavior for some grace
period.
> 5) Profit!
> 
> -Chandler
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev

On Mon, Aug 1, 2016 at 7:23 PM Gerolf Hoflehner via llvm-dev <
llvm-dev at lists.llvm.org> wrote:
>
> > On Jul 31, 2016, at 9:47 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:
>
> I like the principal idea.
> > 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.
>
> What does this imply? Just run-time?  I’d like to see stack size data w/
> and w/o the change and  - just in case - an investigation/fix of the
> outliers.

Sure, I'll do both some benchmarks and also look at some stack sizes.

> Any thoughts about compile-time and code size?
>
I think compile-time regressions are certainly possible with heavier use of
AA and stack coloring, but we'd likely be hitting those through other
patterns than just this one already. It doesn't seem likely this will
really cause much churn there, but certainly if reports come in, we will
have a flag that we can toggle until things are fixed.

>
> You probably also want to collect the data across more than one platform.
>
I'll certainly collect it for the platforms I have access to and such, but
hopefully those interested in other platforms and worried about stack space
can also do some testing. That's why I want to add a flag so its super easy
to check whether this regresses something you care about.

>
>
> > 4) Delete the (quite substantial) complexity associated with this and
> the flag.
> You might need to allow target specific behavior for some grace period.
>
I really don't think this warrants a long grace period much less target
specific behavior.

The goal is simplification. We have lots of infrastructure for a target to
control how stack coloring and layout is done. Honestly, I suspect most of
the stack objects already go down this path. It is only array type allocas
that we even bother with this merging for right now, so I'm not expecting
any dramatic changes.

Clearly, if folks report problems, we'll turn it back on and have to sort
out what happened, but I think we can take a pretty simple approach to get
from here to there...
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160802/65e31f07/attachment.html>

Seeing no big concerns raised with this direction...

On Sun, Jul 31, 2016 at 9:47 PM Chandler Carruth <chandlerc at gmail.com>
wrote:
> 1) Add a flag to turn this off.
>
https://reviews.llvm.org/D23052

Will proceed from there.

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
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160802/005bb562/attachment.html>

> On Aug 2, 2016, at 1:02 AM, Chandler Carruth via llvm-dev <llvm-dev at
lists.llvm.org> wrote:
> 
> Seeing no big concerns raised with this direction…
I don’t think I have seen an answer to the first email from David in this
thread?

— 
Mehd

> 
> On Sun, Jul 31, 2016 at 9:47 PM Chandler Carruth <chandlerc at gmail.com
<mailto:chandlerc at gmail.com>> wrote:
> 1) Add a flag to turn this off.
> 
> https://reviews.llvm.org/D23052 <https://reviews.llvm.org/D23052>
> 
> Will proceed from there.
> 
> 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
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160802/d0bf62ff/attachment.html>

Sorry I missed these comments in my first read through David.

On Mon, Aug 1, 2016 at 1:06 AM Xinliang David Li via llvm-dev <
llvm-dev at lists.llvm.org> wrote:
> On Sun, Jul 31, 2016 at 9:47 PM, Chandler Carruth via llvm-dev <
> llvm-dev at lists.llvm.org> wrote:
>
>> Thoughts? The code changes are easy and mechanical. My plan would be:
>>
>
> There is one caveat: stop doing stack merging in inliner will change the
> inliner cost analysis which may have affect inlining decisions and
> performance in an unexpected way.  For instance, the allocatedSize estimate
> won't be as accurate due to double counting.
>
There is the possibility of this, but I think it is relatively unlikely for
a few reasons.

The first is that I don't think the alloca merging is helping that much
here. Specifically, we only merge certain kinds of allocas and we only
merge them in fairly limited cases. So if the thresholds were very
sensitive to this, I would expect us to have seen these thresholds blocking
things more often than we have.

Also, as you mention, there are two places we might hit this. One is due to
the increased number of alloca instructions causing skew in the inline
cost. I think we should "fix" this by stopping counting *static*
alloca
instructions for the purpose of inline cost estimation. I think this will
be a net win. The alloca instructions are completely synthetic when static.
All of them will be folded into a single stack adjustment that is even
shared with register spills etc. I think we should model them as free.
(Clearly, *dynamic* alloca instructions are different here!) But I don't
think this is likely enough to be urgent to fix. I think we could do both
changes in parallel.

The other limit is the allocated size limit, and I think that is the more
likely issue (it sounds like it was the one you were worried about as
well). This one might be an issue, but I also think we can adjust it pretty
freely. The goal of this limit, from my recollection of when it went in, is
more to avoid run-away stack bloating, and the value of the limit is
somewhat arbitrary. And it only impacts inlining into recursive functions.
So I'm less worried about this in general. If it proves to be a problem in
practice, we can do something about it, and if that happens it would
probably be good to know because we shouldn't be relying on merging to
model this anyways.


>
>> 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.
>>
>
> The code handling the merging seems to be in an isolated place with <100
> lines of code. While I agree this change may be something good to do in
> principle -- are there any practical reason for doing this?
>
Yes, its complexity which is better addressed by another layer. Every piece
of complexity, especially in something like the inliner, makes it harder to
change and reason about. I'm trying to minimize and isolate the complex
parts of the iniliner in preparation to porting it to the new pass manager.
This seemed like low-hanging fruit.

> you mentioned information loss (aliasing, sanitizer etc) -- are there any
> real issues caused by the merging (with tracking bugs)?
>
I don't have any, but I also don't think we should wait for bugs to come
up
to make principled changes to the compiler, especially those that are
simplifying!
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160802/d963c6c4/attachment.html>

FYI, I ran some initial measurements just for sanity on the test-suite on
x86-64:

Total stack frame size: 13362520 -> 13365864 (+0.02%)
Average stack frame size: 581.814 -> 581.96 (+0.02%)
Average compile time: 5.71178 -> 5.67256 (within noise)

Number of functions is exactly the same, so no trivially visible inlining
decision changes.

I've spot checked a few of the functions that had significant change in
stack size. One shows a pattern that isn't too surprising in retrospect:
this change allows us to hoist more code which causes live ranges to expand
and increases spills. Nothing really scary here, and in many ways validates
the core premise -- this does actually remove barriers to the mid-level
optimizer.

I've also found one case where stack coloring appears to just fail for no
reason: "NArchive::N7z::GetStringForSizeValue(unsigned int)" in
7zHandler.cpp has exactly the same sequence of instructions after the
change but 3x larger stack. But this appears to be rare and mostly relating
to functions with already small stack sizes. I've filed PR28821 to track
this.

Anyways, while clearly some stuff will need cleaning up, I don't see
anything really scary jumping out here.

-Chandler

On Tue, Aug 2, 2016 at 1:02 AM Chandler Carruth <chandlerc at gmail.com>
wrote:
> Seeing no big concerns raised with this direction...
>
> On Sun, Jul 31, 2016 at 9:47 PM Chandler Carruth <chandlerc at
gmail.com>
> wrote:
>
>> 1) Add a flag to turn this off.
>>
>
> https://reviews.llvm.org/D23052
>
> Will proceed from there.
>
> 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
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160803/aba2f7ea/attachment-0001.html>

> On Jul 31, 2016, at 9:47 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!
I’m +1 for removing this.  You are exactly right that it was a terrible hack to
work around lack of proper stack coloring.  That said, I think that doing proper
evaluation is key.  Your (downthread) numbers about the testsuite are great!

I assume that the testcases added back in 2009 are handled as well?

-Chris

On Mon, Aug 01, 2016 at 04:47:49AM +0000, Chandler Carruth via llvm-dev
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.
Do we have any way to hunt for stack size regressions? I've been hit by
some serious bugs in this area in GCC in the past and I would prefer to
not repeat that experience with LLVM.

Joerg

On Thu, Aug 4, 2016 at 9:44 AM Joerg Sonnenberger via llvm-dev <
llvm-dev at lists.llvm.org> wrote:
> On Mon, Aug 01, 2016 at 04:47:49AM +0000, Chandler Carruth via llvm-dev
> 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.
>
> Do we have any way to hunt for stack size regressions? I've been hit by
> some serious bugs in this area in GCC in the past and I would prefer to
> not repeat that experience with LLVM.
>
My technique was to log the stack size and build a bunch of code, and then
analyze the logs before and after. It seemed really effective though?

I also have some tests (sadly internal) that check stacksize is under some
bound and those tend to serve is good indicators that something has gone
badly wrong. For example, without the Clang tricks at -O0, we couldn't get
their tests to pass.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160804/f2110fae/attachment.html>