llvm dev - Nov 2017 - RFC: Replace usage of Alias Set Tracker with MemorySSA in LICM

Hi,

I wanted to give a heads-up that I've been looking into replacing the
AliasSetTracker(AST) with MemorySSA in the Loop Invariant Code Motion
(LICM) pass.
I would love to get feedback on the best way to incrementally push in this
change.

Motivation:
There has been an outstanding issue with using the Alias Set Tracker due to
its expensive construction time (quadratic).
We've had test cases take forever to compile, where the largest time was
spent constructing the AST in LICM.
We've also had to degrade the AST results as a temporary fix to resolve
this (D23432).
The hope is that by using MemorySSA instead, which has linear construction
time, we can avoid this issues and decrease compile times.

Some initial discussion points:
1. As a first step, I'm looking at having MemorySSA as a dependency only
for LICM, in the old pass manager.
2. In the future, MemorySSA may become one of the loop passes that's
readily available for all loops in the new pass manager. This will be a
more extensive change and it may require analyzing the overhead of
preserving MemorySSA by all loop passes.
3. As was pointed out in an earlier thread, MemorySSA could be used to
implement AliasSetTracker. I am not looking into that. I'm looking into
explicitly using MemorySSA, instead of the AliasSetTracker.
If there are issues with this choice, please raise them here.

As this is still work in progress, the feedback received will help shape
how the replacement gets implemented and merged in.

Best,
Alina
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170530/a6ec7757/attachment-0001.html>

On Tue, May 30, 2017 at 10:07 AM, Alina Sbirlea via llvm-dev
<llvm-dev at lists.llvm.org> wrote:
> Hi,
>
> I wanted to give a heads-up that I've been looking into replacing the
> AliasSetTracker(AST) with MemorySSA in the Loop Invariant Code Motion
(LICM)
> pass.
> I would love to get feedback on the best way to incrementally push in this
> change.
>
> Motivation:
> There has been an outstanding issue with using the Alias Set Tracker due to
> its expensive construction time (quadratic).
> We've had test cases take forever to compile, where the largest time
was
> spent constructing the AST in LICM.
> We've also had to degrade the AST results as a temporary fix to resolve
this
> (D23432).
In case you want another example https://bugs.llvm.org//show_bug.cgi?id=30608
(just revert this https://reviews.llvm.org/D25376 and the follow-up to
trigger the O(N^2) behaviour).
> The hope is that by using MemorySSA instead, which has linear construction
> time, we can avoid this issues and decrease compile times.
>
> Some initial discussion points:
> 1. As a first step, I'm looking at having MemorySSA as a dependency
only for
> LICM, in the old pass manager.
> 2. In the future, MemorySSA may become one of the loop passes that's
readily
> available for all loops in the new pass manager. This will be a more
> extensive change and it may require analyzing the overhead of preserving
> MemorySSA by all loop passes.
> 3. As was pointed out in an earlier thread, MemorySSA could be used to
> implement AliasSetTracker. I am not looking into that. I'm looking into
> explicitly using MemorySSA, instead of the AliasSetTracker.
> If there are issues with this choice, please raise them here.
It seems sensible to me starting from MemorySSA as a replacement for
AliasSetTracker in LICM.
There's also an annoying (longstanding) problem in the usage of
AliasSetTracker in LICM that could possibly go away with the switch
(and that would be great, i.e. killing two birds with one stone).
LICM creates an AliasSetTracker state that expects to be cleaned up by
a later run.
If for some reason this doesn't happen (e.g. -opt-bisect-limit=X
breaks in the middle of the loop pipeline) or some other loop pass
removes a loop, you end up with an assertion in `doFinalization()`.
This is a problem at least for the current PM infrastructure (not sure
if/how it manifests in the new PM as there's no `doFinalization()`).

You can trigger it running opt -loop-unroll -licm on the following

define void @patatino() {
entry:
  br label %winky
winky:
  br label %tinky
tinky:
  br i1 true, label %tinky, label %for.end
for.end:
  br i1 false, label %winky, label %if.end
if.end:
  ret void
}

Thanks again for working on this.

-- 
Davide

"There are no solved problems; there are only problems that are more
or less solved" -- Henri Poincare

On 5/30/2017 10:07 AM, Alina Sbirlea via llvm-dev wrote:
> Hi,
>
> I wanted to give a heads-up that I've been looking into replacing the 
> AliasSetTracker(AST) with MemorySSA in the Loop Invariant Code Motion 
> (LICM) pass.
> I would love to get feedback on the best way to incrementally push in 
> this change.
>
> Motivation:
> There has been an outstanding issue with using the Alias Set Tracker 
> due to its expensive construction time (quadratic).
> We've had test cases take forever to compile, where the largest time 
> was spent constructing the AST in LICM.
> We've also had to degrade the AST results as a temporary fix to 
> resolve this (D23432).
> The hope is that by using MemorySSA instead, which has linear 
> construction time, we can avoid this issues and decrease compile times.
>
> Some initial discussion points:
> 1. As a first step, I'm looking at having MemorySSA as a dependency 
> only for LICM, in the old pass manager.
> 2. In the future, MemorySSA may become one of the loop passes that's 
> readily available for all loops in the new pass manager. This will be 
> a more extensive change and it may require analyzing the overhead of 
> preserving MemorySSA by all loop passes.
This works essentially the same way in the legacy pass manager and the 
new pass manager; it's just not as obvious in the legacy pass manager.  
See getLoopAnalysisUsage(), which is basically the set of passes which a 
LoopPass is allowed to use/must preserve to allow loop pass interleaving.

-Eli

-- 
Employee of Qualcomm Innovation Center, Inc.
Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, a Linux
Foundation Collaborative Project

Hi,

I wanted to give an update on this topic, as a heads up for what I'd like
the plan to be going forward.

I would like to split the current patch doing the replacement of Alias Set
Tracker (AST) with MemorySSA (D35741 <https://reviews.llvm.org/D35741>)
into more manageable pieces.
(Note, while the current patch is not the prettiest, it covers all the
final functionality. I will rebase this patch on the intermediate patches
planned below.)

A few reasons for the split:
- Preliminary performance results on pathological test cases show that
building MemorySSA as a dependency without using it in LICM (i.e., build
MemorySSA and also build AST!) leads to prohibitively large compile times,
making this a non-option. No surprise here. Hence the flag to enable
MemorySSA will be:
    -> false (do not build MemorySSA, build Alias Set Tracker)
    -> true (build MemorySSA and use it, do not build Alias Set Tracker)
- Doing sink/hoist in LICM with MemorySSA is straight-forward, while
promotion is difficult to tackle.
- Having loop passes preserve MemorySSA is a necessary long term step.
- Easier to review, of course.

Rough next steps:
- Adding MemorySSA as a dependency, to be *built* under a flag in both new
and legacy pass managers.
- With flag enabled, update MemorySSA in LICM, use it to do sink and hoist,
do not do promotion.
- With flag enabled, do promotion, add MemorySSA sets. This piece can later
be replaced, with a different promotion mechanism.
- Update MemorySSA in LoopUnswitch and LoopRotate
- Update MemorySSA in IndVarsimplify, LoopIdiomRecognize, LoopDeletion

Patches coming up soon, and feedback welcome.

Thanks,
Alina


On Tue, May 30, 2017 at 10:07 AM, Alina Sbirlea <alina.sbirlea at
gmail.com>
wrote:
> Hi,
>
> I wanted to give a heads-up that I've been looking into replacing the
> AliasSetTracker(AST) with MemorySSA in the Loop Invariant Code Motion
> (LICM) pass.
> I would love to get feedback on the best way to incrementally push in this
> change.
>
> Motivation:
> There has been an outstanding issue with using the Alias Set Tracker due
> to its expensive construction time (quadratic).
> We've had test cases take forever to compile, where the largest time
was
> spent constructing the AST in LICM.
> We've also had to degrade the AST results as a temporary fix to resolve
> this (D23432).
> The hope is that by using MemorySSA instead, which has linear construction
> time, we can avoid this issues and decrease compile times.
>
> Some initial discussion points:
> 1. As a first step, I'm looking at having MemorySSA as a dependency
only
> for LICM, in the old pass manager.
> 2. In the future, MemorySSA may become one of the loop passes that's
> readily available for all loops in the new pass manager. This will be a
> more extensive change and it may require analyzing the overhead of
> preserving MemorySSA by all loop passes.
> 3. As was pointed out in an earlier thread, MemorySSA could be used to
> implement AliasSetTracker. I am not looking into that. I'm looking into
> explicitly using MemorySSA, instead of the AliasSetTracker.
> If there are issues with this choice, please raise them here.
>
> As this is still work in progress, the feedback received will help shape
> how the replacement gets implemented and merged in.
>
> Best,
> Alina
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20171120/636f73d4/attachment.html>

Following up on a very old thread, that in time has evolved into:
   "Enable the use of MemorySSA in the LoopPassManager."

There have been discussions over the past couple of years about using
MemorySSA throughout the loop passes, and the verbal consensus was that
this is a good idea. After extensive testing, I'm looking to flip the flag
to enable the use of MemorySSA with: D58311
<https://reviews.llvm.org/D58311>.

I'd very much appreciate it folks took a moment to mention if they have
concerns, suggestions, feedback about this.

Thank you,
Alina



On Mon, Nov 20, 2017 at 1:02 PM Alina Sbirlea via llvm-dev <
llvm-dev at lists.llvm.org> wrote:
> Hi,
>
> I wanted to give an update on this topic, as a heads up for what I'd
like
> the plan to be going forward.
>
> I would like to split the current patch doing the replacement of Alias Set
> Tracker (AST) with MemorySSA (D35741
<https://reviews.llvm.org/D35741>)
> into more manageable pieces.
> (Note, while the current patch is not the prettiest, it covers all the
> final functionality. I will rebase this patch on the intermediate patches
> planned below.)
>
> A few reasons for the split:
> - Preliminary performance results on pathological test cases show that
> building MemorySSA as a dependency without using it in LICM (i.e., build
> MemorySSA and also build AST!) leads to prohibitively large compile times,
> making this a non-option. No surprise here. Hence the flag to enable
> MemorySSA will be:
>     -> false (do not build MemorySSA, build Alias Set Tracker)
>     -> true (build MemorySSA and use it, do not build Alias Set Tracker)
> - Doing sink/hoist in LICM with MemorySSA is straight-forward, while
> promotion is difficult to tackle.
> - Having loop passes preserve MemorySSA is a necessary long term step.
> - Easier to review, of course.
>
> Rough next steps:
> - Adding MemorySSA as a dependency, to be *built* under a flag in both new
> and legacy pass managers.
> - With flag enabled, update MemorySSA in LICM, use it to do sink and
> hoist, do not do promotion.
> - With flag enabled, do promotion, add MemorySSA sets. This piece can
> later be replaced, with a different promotion mechanism.
> - Update MemorySSA in LoopUnswitch and LoopRotate
> - Update MemorySSA in IndVarsimplify, LoopIdiomRecognize, LoopDeletion
>
> Patches coming up soon, and feedback welcome.
>
> Thanks,
> Alina
>
>
> On Tue, May 30, 2017 at 10:07 AM, Alina Sbirlea <alina.sbirlea at
gmail.com>
> wrote:
>
>> Hi,
>>
>> I wanted to give a heads-up that I've been looking into replacing
the
>> AliasSetTracker(AST) with MemorySSA in the Loop Invariant Code Motion
>> (LICM) pass.
>> I would love to get feedback on the best way to incrementally push in
>> this change.
>>
>> Motivation:
>> There has been an outstanding issue with using the Alias Set Tracker
due
>> to its expensive construction time (quadratic).
>> We've had test cases take forever to compile, where the largest
time was
>> spent constructing the AST in LICM.
>> We've also had to degrade the AST results as a temporary fix to
resolve
>> this (D23432).
>> The hope is that by using MemorySSA instead, which has linear
>> construction time, we can avoid this issues and decrease compile times.
>>
>> Some initial discussion points:
>> 1. As a first step, I'm looking at having MemorySSA as a dependency
only
>> for LICM, in the old pass manager.
>> 2. In the future, MemorySSA may become one of the loop passes
that's
>> readily available for all loops in the new pass manager. This will be a
>> more extensive change and it may require analyzing the overhead of
>> preserving MemorySSA by all loop passes.
>> 3. As was pointed out in an earlier thread, MemorySSA could be used to
>> implement AliasSetTracker. I am not looking into that. I'm looking
into
>> explicitly using MemorySSA, instead of the AliasSetTracker.
>> If there are issues with this choice, please raise them here.
>>
>> As this is still work in progress, the feedback received will help
shape
>> how the replacement gets implemented and merged in.
>>
>> Best,
>> Alina
>>
>
> _______________________________________________
> 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/20190801/e07eb702/attachment.html>