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

On Thu, Aug 4, 2016 at 9:56 AM Mehdi Amini via llvm-dev <
llvm-dev at lists.llvm.org> wrote:
>
> On Aug 4, 2016, at 9:48 AM, Chandler Carruth via llvm-dev <
> llvm-dev at lists.llvm.org> wrote:
>
> 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.
>
>
> Are these “clang tricks” some indications of weaknesses in LLVM on this
> aspect?
>
Depends on how you look at it. They're only enabled at O0. It's
essentially
the lowest compile time cost way to re-use stack space in *highly*
repeatative functions (like where you have macros stamping out 1000s of
temporary std::string objects). Clang just keeps a freelist around of
allocas and re-uses them.

We could always turn on some form of stack coloring at O0, but when we
looked at it that would have been much harder to have match the compile
time profile, and also harder to make survive debug info etc.

Within Clang there are somewhat more obvious repeated patterns that we can
target for re-use.

At least, this is my memory from the discussion with Richard Smith when he
implemented this. =] He may want to provide more details or correct my
memory of things.

>
> —
> Mehdi
>
> _______________________________________________
> 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/20160804/31a028bb/attachment-0001.html>

> On Aug 4, 2016, at 10:00 AM, Chandler Carruth <chandlerc at
gmail.com> wrote:
> 
> On Thu, Aug 4, 2016 at 9:56 AM Mehdi Amini via llvm-dev <llvm-dev at
lists.llvm.org <mailto:llvm-dev at lists.llvm.org>> wrote:
> 
>> On Aug 4, 2016, at 9:48 AM, Chandler Carruth via llvm-dev <llvm-dev
at lists.llvm.org <mailto:llvm-dev at lists.llvm.org>> wrote:
>> 
>> On Thu, Aug 4, 2016 at 9:44 AM Joerg Sonnenberger via llvm-dev
<llvm-dev at lists.llvm.org <mailto: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.
> 
> Are these “clang tricks” some indications of weaknesses in LLVM on this
aspect?
> 
> Depends on how you look at it. They're only enabled at O0.
Oh right, I missed that part. That’s fine then.

— 
Mehdi

> It's essentially the lowest compile time cost way to re-use stack space
in *highly* repeatative functions (like where you have macros stamping out 1000s
of temporary std::string objects). Clang just keeps a freelist around of allocas
and re-uses them.
> 
> We could always turn on some form of stack coloring at O0, but when we
looked at it that would have been much harder to have match the compile time
profile, and also harder to make survive debug info etc.
> 
> Within Clang there are somewhat more obvious repeated patterns that we can
target for re-use.
> 
> At least, this is my memory from the discussion with Richard Smith when he
implemented this. =] He may want to provide more details or correct my memory of
things.
>  
> 
> — 
> Mehdi
> 
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org>
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
<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/20160804/091801b3/attachment.html>

So, tho story doesn't end here.

Fun thing. Clang at -O0, despite going to hackish lengths to re-use stack
space in the frontend, explicitly disables the insertion of lifetime
markers in the *always inliner* that runs at -O0. See r151430 to Clang
which adds this.

However, that commit has ... very little information. Fortunately, it was
paired with a change to LLVM in r151429 where the plumbing for this was
added to the always inliner. In that commit, it was mentioned that the
lifetime markers caused a, like, 100x slowdown in compile time. While Eric
and Chad explained this as largely having to do with disabling fast-isel
and doing more expensive selection-dag, given the number of bugs we've hit
in the stack coloring I suspect that may also have played a part in the
slowdown.

While I hope that we no longer have this kind of compile time penalty, at
least the following need to happen to finally move on from this chapter of
the inliner:

1) We need to re-enable lifetime intrinsics in the always inliner (and
potentially disable alloca merging) to make sure they aren't crippling
compile time any more.

2) See how bad the stack frame size regressions from nuking the alloca
merging are in -O0 since that is the configuration where this is actually
still doing something.

3) If the regressions in #2 are bad, do some work to turn on stack coloring
(at least in a limited form) at -O0. I have no idea what is required here
sadly. =/ This is not a part of the backend I know well.


I'm not going to have time to run with this in the very short term, but if
anyone else is interested, I'm happy to provide pointers or advice.

On Thu, Aug 4, 2016 at 10:03 AM Mehdi Amini via llvm-dev <
llvm-dev at lists.llvm.org> wrote:
> On Aug 4, 2016, at 10:00 AM, Chandler Carruth <chandlerc at
gmail.com> wrote:
>
> On Thu, Aug 4, 2016 at 9:56 AM Mehdi Amini via llvm-dev <
> llvm-dev at lists.llvm.org> wrote:
>
>>
>> On Aug 4, 2016, at 9:48 AM, Chandler Carruth via llvm-dev <
>> llvm-dev at lists.llvm.org> wrote:
>>
>> 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.
>>
>>
>> Are these “clang tricks” some indications of weaknesses in LLVM on this
>> aspect?
>>
>
> Depends on how you look at it. They're only enabled at O0.
>
>
> Oh right, I missed that part. That’s fine then.
>
> —
> Mehdi
>
>
> It's essentially the lowest compile time cost way to re-use stack space
in
> *highly* repeatative functions (like where you have macros stamping out
> 1000s of temporary std::string objects). Clang just keeps a freelist around
> of allocas and re-uses them.
>
> We could always turn on some form of stack coloring at O0, but when we
> looked at it that would have been much harder to have match the compile
> time profile, and also harder to make survive debug info etc.
>
> Within Clang there are somewhat more obvious repeated patterns that we can
> target for re-use.
>
> At least, this is my memory from the discussion with Richard Smith when he
> implemented this. =] He may want to provide more details or correct my
> memory of things.
>
>
>>
>> —
>> Mehdi
>>
>> _______________________________________________
>> 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/20160809/215f2fa3/attachment.html>