[PassManager] Move load/store motion pass after DSE in LTO pipeline.

[fhahn]

Summary

As far as I am aware, the placement of MergedLoadStoreMotion in the
pipeline is not heavily tuned currently. It seems to not matter much if
we do it after DSE in the LTO pipeline (no binary changes for -O3 -flto
on MultiSource/SPEC2000/SPEC2006). Moving it after DSE however has a
major benefit: MemorySSA is constructed by LICM and is consumed by DSE,
so if MergedLoadStoreMotion happens after DSE, we do not need to
preserve MemorySSA in it.

If there are any concerns with this move, I can also update
MergedLoadStoreMotion to preserve MemorySSA.

This patch together with D86651 (preserve MemSSA in MemCpyOpt) and
D86534 (preserve MemSSA in GVN) are the remaining patches to bring down
compile-time for DSE + MemorySSA to the levels outlined in
http://lists.llvm.org/pipermail/llvm-dev/2020-August/144417.html

Once they land, we should be able to start with flipping the switch on
enabling DSE + MmeorySSA.

[xbolva00]

Seems reasonable.

Some pipeline tests should be updated.

[fhahn]

In D86967#2250487, @xbolva00 wrote:

Some pipeline tests should be updated.

Do we have a way to run the LTO pipelines via opt? I am not aware of that and none of the existing tests seem to break with this change, indicating that there seem to be no LTO pipeline tests.

[xbolva00]

cc @tejohnson

[asbirlea]

The idea to have all passes in sequence preserved and use MemorySSA is great. I'm wondering if changing the pass order affects run time (due to potential missed optimizations).
On the other hand, this only affects the LPM, so it may not be as critical due to the plan to switch to the NPM.

The NPM has the passes that take advantage of MSSA combined as DSE+LICM (https://github.com/llvm-mirror/llvm/blob/master/lib/Passes/PassBuilder.cpp#L525) and GVN+MemCpyOpt (https://github.com/llvm-mirror/llvm/blob/master/lib/Passes/PassBuilder.cpp#L504), and GVN+MemCpyOpt+DSE for LTO (https://github.com/llvm-mirror/llvm/blob/master/lib/Passes/PassBuilder.cpp#L1303)
So all cases should be covered by the other "preserve MSSA" patches.

I'll follow up on the llvmdev@ thread regarding testing for the NPM.

[tejohnson]

In D86967#2250685, @xbolva00 wrote:

cc @tejohnson

For the NPM there is a way to invoke the various LTO pass pipelines via opt, and I know there are several tests that do test the pass ordering out of that. For the old PM, though, the only way I could see in opt.cpp to get LTO passes is via the -std-link-opts opt flag, but it doesn't look like any tests actually use that option! Given the upcoming switch to the NPM I'm not sure if it is worth adding a bunch of old PM LTO pipeline tests at this point.

[fhahn]

In D86967#2250810, @asbirlea wrote:

The idea to have all passes in sequence preserved and use MemorySSA is great. I'm wondering if changing the pass order affects run time (due to potential missed optimizations).
On the other hand, this only affects the LPM, so it may not be as critical due to the plan to switch to the NPM.

This patch does not cause any binary changes for -O3 -flto on X86 for MultiSource/SPEC2000/SPEC2006, so it seems like the optimization behavior does not really change for that test set. Looking at the pass, it seems like it is relatively limited in the transformation it applies and should not be impacted a lot by the slight change of placement.

The NPM has the passes that take advantage of MSSA combined as DSE+LICM (https://github.com/llvm-mirror/llvm/blob/master/lib/Passes/PassBuilder.cpp#L525) and GVN+MemCpyOpt (https://github.com/llvm-mirror/llvm/blob/master/lib/Passes/PassBuilder.cpp#L504), and GVN+MemCpyOpt+DSE for LTO (https://github.com/llvm-mirror/llvm/blob/master/lib/Passes/PassBuilder.cpp#L1303)
So all cases should be covered by the other "preserve MSSA" patches.

Yes, for the regular pipeline DSE+LICM are combined with the NPM (same as with LPM). One unfortunate property of the NPM LTO pipeline is that LICM is not run (there's a FIXME), so there is no actual users of MemorySSA close-by, so even though we run GVN+MemCpyOpt+DSE and we could preserve MSSA it won't help much I think, because there is no 'real' consumer at the beginning (with LPM, we run LICM there during LTO).

I'll follow up on the llvmdev@ thread regarding testing for the NPM.

I think the only major difference is that we currently have to construct MSSA only for DSE in the NPM LTO pipeline. That is unfortunate (and will be noticeable in terms of compile-time), but this problem will go away when either NewGVN or LICM is run as it seems expected. from the comments.

In D86967#2250849, @tejohnson wrote:

In D86967#2250685, @xbolva00 wrote:

cc @tejohnson

For the NPM there is a way to invoke the various LTO pass pipelines via opt, and I know there are several tests that do test the pass ordering out of that. For the old PM, though, the only way I could see in opt.cpp to get LTO passes is via the -std-link-opts opt flag, but it doesn't look like any tests actually use that option! Given the upcoming switch to the NPM I'm not sure if it is worth adding a bunch of old PM LTO pipeline tests at this point.

Right, the NPM order does not change. I don't think it's worth adding new options to print the LPM pipelines for a minor change such as this one.

[xbolva00]

. I don't think it's worth adding new options to print the LPM pipelines for a minor change such as this one.

Yeah.

[asbirlea]

Unless there are complaints from others, I think this is good.

[fhahn]

In D86967#2253532, @asbirlea wrote:

Unless there are complaints from others, I think this is good.

Great, thanks! I'll land this now, we can always revert it if there are any concerns or any problems are exposed.

llvm/lib/Transforms/IPO/PassManagerBuilder.cpp

if (OptLevel > 1)
     PM.add(createTailCallEliminationPass());
 
   // Infer attributes on declarations, call sites, arguments, etc.
   PM.add(createPostOrderFunctionAttrsLegacyPass()); // Add nocapture.
   // Run a few AA driven optimizations here and now, to cleanup the code.
   PM.add(createGlobalsAAWrapperPass()); // IP alias analysis.
 
   PM.add(createLICMPass(LicmMssaOptCap, LicmMssaNoAccForPromotionCap));
-  PM.add(createMergedLoadStoreMotionPass()); // Merge ld/st in diamonds.
   PM.add(NewGVN ? createNewGVNPass()
                 : createGVNPass(DisableGVNLoadPRE)); // Remove redundancies.
   PM.add(createMemCpyOptPass());            // Remove dead memcpys.
 
   // Nuke dead stores.
   PM.add(createDeadStoreEliminationPass());
+  PM.add(createMergedLoadStoreMotionPass()); // Merge ld/st in diamonds.
 
   // More loops are countable; try to optimize them.
   PM.add(createIndVarSimplifyPass());
   PM.add(createLoopDeletionPass());
   if (EnableLoopInterchange)
     PM.add(createLoopInterchangePass());
 
   // Unroll small loops