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

Alina Sbirlea via llvm-dev llvm-dev at lists.llvm.org
Thu Aug 1 11:45:45 PDT 2019

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,

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>

More information about the llvm-dev mailing list