RFC: Replace usage of Alias Set Tracker with MemorySSA in LICM

Project Infrastructure LLVM Dev List Archives
1

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

2

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 30608 – Super slow to compile simple code (Loop Invariant Code Motion, 3.8: 0.05s, 3.9: 1m+. >1200% slowdown)
(just revert this ⚙ D25376 [InstCombine] Don't unpack arrays that are too large 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.

3

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

4

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

5

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.

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

Thank you,
Alina