Add loop pass insertion point EP_LateLoopOptimizations

[kparzysz]

Summary

Add an extension point allowing late loop optimization passes.

[kparzysz]

Actually, an extension point would not work, since extensions need to be added from outside of the PassManagerBuilder. There would have to be another way to collect them and add them to the pipeline.

[kparzysz]

This is the simplest way to insert the pass. This is very close to what we actually do. We'd need something like this, which would allow inserting target-specific passes from within the builder.

[efriedma]

If we wanted to allow targets to add target-specific extensions, we could add a function to TargetMachine which takes a PassManagerBuilder, and make clang call it. And it's easy enough to add extension points if we need them.

That said, I'm not sure that's really relevant for your particular use-case; the transformation presented here is basically target-independent. The only issue is that there isn't a target-independent equivalent to hexagon_M4_pmpyw (but equivalent instructions do exist on many targets; x86 has PCLMULQDQ, ARM has VMULL.P64, etc.).

[kparzysz]

In D28694#645883, @efriedma wrote:

If we wanted to allow targets to add target-specific extensions, we could add a function to TargetMachine which takes a PassManagerBuilder, and make clang call it. And it's easy enough to add extension points if we need them.

That's actually a good point!

That said, I'm not sure that's really relevant for your particular use-case; the transformation presented here is basically target-independent. The only issue is that there isn't a target-independent equivalent to hexagon_M4_pmpyw (but equivalent instructions do exist on many targets; x86 has PCLMULQDQ, ARM has VMULL.P64, etc.).

True, but there is other stuff in that file as well that only applies to Hexagon. Plus posting of this patch was motivated by a post on llvm-dev asking about this exact thing (i.e. target-specific loop idioms).

[mehdi_amini]

I assume you just posted the patch as a straw man to go with the llvm-dev discussion or is it something you intend to push forward?

include/llvm/Transforms/IPO/PassManagerBuilder.h

119 ↗

(On Diff #84383)

Does not seems something we want in the PMBuilder.

[kparzysz]

In D28694#646276, @mehdi_amini wrote:

I assume you just posted the patch as a straw man to go with the llvm-dev discussion or is it something you intend to push forward?

Both. We have a need for this and there is now someone else interested in this kind of capability. Hal wanted to see a use case, and I think this fits the bill.

[kparzysz]

include/llvm/Transforms/IPO/PassManagerBuilder.h

119 ↗

(On Diff #84383)

I plan to go forward with Eli's suggestion. This was put here just to get this to compile and pass tests.

[kparzysz]

Implement Eli's suggestion: add a TM hook to insert target-specific loop idiom recognition passes.

[mehdi_amini]

lib/Transforms/IPO/PassManagerBuilder.cpp

320 ↗

(On Diff #84557)

This extension point could get its own separate patch.

It seems very targeted, if the only point is to have TargetSpecific loop idiom recognition, then why aren't some TTI implemented and used in LoopIdiomPass?

[hfinkel]

lib/Transforms/IPO/PassManagerBuilder.cpp

320 ↗

(On Diff #84557)

I thought about suggesting this, but didn't because:

a. It is not clear what from the existing loop idiom recognition pass could be reused
b. The target-specific logic might want access to other analyses, and that would be awkward if it is just a TTI callback.

What do you think?

[mehdi_amini]

lib/Transforms/IPO/PassManagerBuilder.cpp

320 ↗

(On Diff #84557)

These are good points!

It is not clear what from the existing loop idiom recognition pass could be reused

Main point here: the insertion point in the pipeline :)

The target-specific logic might want access to other analyses, and that would be awkward if it is just a TTI callback.

No sure what you mean by "awkward" with a TTI needing analysis, but that would definitely be a problem if the TTI would want an analysis that is not generic or not currently available in LoopIdiom.

The reason I think discussing this extension point in its own revision is because I think we usually have "generic" and "coarse grain" extension points (do we have another case of specific hook like that?).
I'm cautious about it because adding such hooks makes it harder to evolve/maintain the pipeline (ultimately what when we'll have a hook before/after every single pass?).

[mehdi_amini]

include/llvm/Transforms/IPO/PassManagerBuilder.h

106 ↗

(On Diff #84557)

Side note, but somehow related to the "too specific" aspect I mentioned, I'd call it EP_BeforeLoopIdiom and I'd describe it:

/// This extension point allows adding passes before loop-idiom 
/// recognition passes. It can be used for example  by a target to
/// add a specific loop-idiom recognition passes.

[kparzysz]

lib/Transforms/IPO/PassManagerBuilder.cpp

320 ↗

(On Diff #84557)

I'm cautious about it because adding such hooks makes it harder to evolve/maintain the pipeline (ultimately what when we'll have a hook before/after every single pass?).

That's an understandable concern, but I think that this particular case is warranted, since it is not uncommon for targets to have their optimized versions of certain loop-based operations. It can be either via target-specific runtime libraries, or directly via hardware instructions.
Since this insertion point is shared with that of the target-independent loop idiom recognizer, the implementations would also share the same ways of handling the code. That would make it easier to move code from a target-specific version to the target-independent pass, or conversely, to take a target-independent code and adopt it for the needs of a given target.

[kparzysz]

include/llvm/Transforms/IPO/PassManagerBuilder.h

106 ↗

(On Diff #84557)

That could certainly be done.

[kparzysz]

Extracted the implementation of the new insertion point, with the previous comments reflected.

[chandlerc]

Sorry I didn't notice this waiting on me, and thanks for the gentle prod Krzysztof! My two cents inline.

lib/Transforms/IPO/PassManagerBuilder.cpp

320 ↗

(On Diff #84557)

I think this extension point makes sense, and I wouldn't even tie it to the loop idiom recognition but instead to the position in the loop pipeline.

Specifically, I'd add a "late loop canonicalization and simplification" extension point. I would put it after the normal loop idiom but before loop deletion. I think documenting it as "the last thing in the loop pipeline before deletion" makes sense. You can talk about the fact that this is where you should extend the pipeline with loop transformations that tend to *remove loops entirely*.

You should also make it really clear that these need to be *loop passes* and are run in a pipeline across each loop in the nest. And ideally get some assert failure in the extension mechanism that enforces this. Having this accidentally add a function pass will really dramatically change the loop pipeline by partitioning deletion from the rest.

And as Mehdi said, I would land this as its own patch, and then to the TargetMachine patch separately.

And just to clarify, I would be very concerned about a TTI callback for the reasons Krzysztof mentioned... Especially the needing another analysis. I just think it'll get awkward fast and injecting passes is pretty clean and testable.

tools/opt/opt.cpp

292–301 ↗

(On Diff #84578)

If we go this way, I worry we're just bugging for a third...

What about instead you call a method on TargetMachine with the builder that can add any extensions it wants. Then all of this gets sunk into the TM. You can subsume both early-as-possible and the late-loop extensions into this one API. Does that make sense to others?

[kparzysz]

tools/opt/opt.cpp

292–301 ↗

(On Diff #84578)

It makes sense to me. There is already a review for doing that (by someone else): D28336.

[kparzysz]

Isolated the extension point alone in this patch.

[kparzysz]

I think we have reached a consensus here. Could someone approve if there are no further concerns?

[hfinkel]

In D28694#656194, @kparzysz wrote:

I think we have reached a consensus here. Could someone approve if there are no further concerns?

LGTM.

llvm/trunk/include/llvm/Transforms/IPO/PassManagerBuilder.h

enum ExtensionPointTy {
     /// inserted after the inlining pass.
     EP_EnabledOnOptLevel0,
 
     /// EP_Peephole - This extension point allows adding passes that perform
     /// peephole optimizations similar to the instruction combiner. These passes
     /// will be inserted after each instance of the instruction combiner pass.
     EP_Peephole,
 
+    /// EP_LateLoopOptimizations - This extension point allows adding late loop
+    /// canonicalization and simplification passes. This is the last point in
+    /// the loop optimization pipeline before loop deletion. Each pass added
+    /// here must be an instance of LoopPass.
+    /// This is the place to add passes that can remove loops, such as target-
+    /// specific loop idiom recognition.
+    EP_LateLoopOptimizations,
+
     /// EP_CGSCCOptimizerLate - This extension point allows adding CallGraphSCC
     /// passes at the end of the main CallGraphSCC passes and before any
     /// function simplification passes run by CGPassManager.
     EP_CGSCCOptimizerLate,
   };
 
   /// The Optimization Level - Specify the basic optimization level.
   ///    0 = -O0, 1 = -O1, 2 = -O2, 3 = -O3

llvm/trunk/lib/Transforms/IPO/PassManagerBuilder.cpp

void PassManagerBuilder::addFunctionSimplificationPasses(
   // Rotate Loop - disable header duplication at -Oz
   MPM.add(createLoopRotatePass(SizeLevel == 2 ? 0 : -1));
   MPM.add(createLICMPass());                  // Hoist loop invariants
   MPM.add(createLoopUnswitchPass(SizeLevel || OptLevel < 3));
   MPM.add(createCFGSimplificationPass());
   addInstructionCombiningPass(MPM);
   MPM.add(createIndVarSimplifyPass());        // Canonicalize indvars
   MPM.add(createLoopIdiomPass());             // Recognize idioms like memset.
+  addExtensionsToPM(EP_LateLoopOptimizations, MPM);
   MPM.add(createLoopDeletionPass());          // Delete dead loops
+
   if (EnableLoopInterchange) {
     MPM.add(createLoopInterchangePass()); // Interchange loops
     MPM.add(createCFGSimplificationPass());
   }
   if (!DisableUnrollLoops)
     MPM.add(createSimpleLoopUnrollPass());    // Unroll small loops
   addExtensionsToPM(EP_LoopOptimizerEnd, MPM);