[llvm-dev] RFC: Replace usage of Alias Set Tracker with MemorySSA in LICM

[Davide Italiano via llvm-dev]

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