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

[Alina Sbirlea via llvm-dev]

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>