[VectorCombine] add loop to enable iterative folding

[spatel]

Summary

Given the limited range of potential vector transforms, this is an acceptable way to iterate? If this is or becomes too inefficient, we could use a worklist strategy like instcombine, but that would require altering more code. The motivation comes from PR42174:
https://bugs.llvm.org/show_bug.cgi?id=42174
...although we don't have the underlying scalarization-with-constant-operand fold yet. If we add that transform 1st, it would only scalarize 1 instruction instead of the entire chain of insert-insert-binops.

[nikic]

My only concern here would be whether this can degenerate quadratically. Without particular familiarity with this pass, and looking at example @ins1_ins1_iterate, it seems like this would work by scalarizing one operation on each iteration. Is that right? If so, that seems potentially problematic, as the pass becomes quadratic for longer instruction chains.

[spatel]

In D79799#2038887, @nikic wrote:

My only concern here would be whether this can degenerate quadratically. Without particular familiarity with this pass, and looking at example @ins1_ins1_iterate, it seems like this would work by scalarizing one operation on each iteration. Is that right? If so, that seems potentially problematic, as the pass becomes quadratic for longer instruction chains.

Yes, in the worst case it could become quadratic, and you're seeing the test correctly. I think we could undo the reverse basic-block walk in this patch to make that particular case more efficient.

If I'm seeing it correctly, other iterative passes like SimplifyCFG and CodeGenPrepare allow for quadratic-time possibility too. I'm not sure if there's a theoretical way to draw the line on that, or if we just accept that potential risk (assume that anything this pass will ever do is rare, so it can't be too expensive). As I wrote in the description, I think the alternative is to revise things to be more like InstCombine's user-based worklist. We could also put in a cl::opt flag to bail out and/or assert if we go overboard. Any other suggestions?

[nikic]

In D79799#2039039, @spatel wrote:

In D79799#2038887, @nikic wrote:

My only concern here would be whether this can degenerate quadratically. Without particular familiarity with this pass, and looking at example @ins1_ins1_iterate, it seems like this would work by scalarizing one operation on each iteration. Is that right? If so, that seems potentially problematic, as the pass becomes quadratic for longer instruction chains.

Yes, in the worst case it could become quadratic, and you're seeing the test correctly. I think we could undo the reverse basic-block walk in this patch to make that particular case more efficient.

Speaking of which: If I replace this with a forward walk, then the ins1_ins1_iterate test folds, and there are no other test changes in VectorCombine or PhaseOrdering. If there are cases that benefit from the backwards walk, there doesn't seem to be test coverage for them.

If I'm seeing it correctly, other iterative passes like SimplifyCFG and CodeGenPrepare allow for quadratic-time possibility too. I'm not sure if there's a theoretical way to draw the line on that, or if we just accept that potential risk (assume that anything this pass will ever do is rare, so it can't be too expensive). As I wrote in the description, I think the alternative is to revise things to be more like InstCombine's user-based worklist. We could also put in a cl::opt flag to bail out and/or assert if we go overboard. Any other suggestions?

I agree that this is unlikely to become a problem in practice for this pass, because vector code is uncommon. And you are right that this problem also exists in other passes, though it is probably not always as easy to find actually quadratic cases. Personally I'm fine with your approach here, and we can always pivot to a worklist if necessary. Though per my comment above, it seems like for now just flipping the iteration order might be sufficient.

[spatel]

In D79799#2040145, @nikic wrote:

In D79799#2039039, @spatel wrote:

In D79799#2038887, @nikic wrote:

My only concern here would be whether this can degenerate quadratically. Without particular familiarity with this pass, and looking at example @ins1_ins1_iterate, it seems like this would work by scalarizing one operation on each iteration. Is that right? If so, that seems potentially problematic, as the pass becomes quadratic for longer instruction chains.

Yes, in the worst case it could become quadratic, and you're seeing the test correctly. I think we could undo the reverse basic-block walk in this patch to make that particular case more efficient.

Speaking of which: If I replace this with a forward walk, then the ins1_ins1_iterate test folds, and there are no other test changes in VectorCombine or PhaseOrdering. If there are cases that benefit from the backwards walk, there doesn't seem to be test coverage for them.

If I'm seeing it correctly, other iterative passes like SimplifyCFG and CodeGenPrepare allow for quadratic-time possibility too. I'm not sure if there's a theoretical way to draw the line on that, or if we just accept that potential risk (assume that anything this pass will ever do is rare, so it can't be too expensive). As I wrote in the description, I think the alternative is to revise things to be more like InstCombine's user-based worklist. We could also put in a cl::opt flag to bail out and/or assert if we go overboard. Any other suggestions?

I agree that this is unlikely to become a problem in practice for this pass, because vector code is uncommon. And you are right that this problem also exists in other passes, though it is probably not always as easy to find actually quadratic cases. Personally I'm fine with your approach here, and we can always pivot to a worklist if necessary. Though per my comment above, it seems like for now just flipping the iteration order might be sufficient.

Excellent point. Let's make the small change until we have evidence for the need for a costlier solution:
rG81e9ede3a2db

Over in D79078, we're trying to figure out how to properly deal with the reduction test diffs seen in that commit. I'm not sure what the answer will be.

I'll put this patch on hold for now rather than abandon.

[spatel]

D110171 added a worklist, so this is moot.

llvm/lib/Transforms/Vectorize/VectorCombine.cpp

 /// This is the entry point for all transforms. Pass manager differences are
 /// handled in the callers of this function.
 static bool runImpl(Function &F, const TargetTransformInfo &TTI,
                     const DominatorTree &DT) {
   if (DisableVectorCombine)
     return false;
 
   bool MadeChange = false;
+
+  // Iterate until there are no more changes. Transforms can build on each
+  // other's improvements.
+  bool IterationChange;
+  do {
+    IterationChange = false;
     for (BasicBlock &BB : F) {
       // Ignore unreachable basic blocks.
       if (!DT.isReachableFromEntry(&BB))
         continue;
-    // Do not delete instructions under here and invalidate the iterator.
-    // Walk the block backwards for efficiency. We're matching a chain of
+
+      // Walk the block backwards for efficiency. We are matching a chain of
       // use->defs, so we're more likely to succeed by starting from the bottom.
-    // TODO: It could be more efficient to remove dead instructions
-    //       iteratively in this loop rather than waiting until the end.
       for (Instruction &I : make_range(BB.rbegin(), BB.rend())) {
         if (isa<DbgInfoIntrinsic>(I))
           continue;
-      MadeChange |= foldExtractExtract(I, TTI);
-      MadeChange |= foldBitcastShuf(I, TTI);
-      MadeChange |= scalarizeBinop(I, TTI);
+        IterationChange |= foldExtractExtract(I, TTI);
+        IterationChange |= foldBitcastShuf(I, TTI);
+        IterationChange |= scalarizeBinop(I, TTI);
       }
     }
-
-  // We're done with transforms, so remove dead instructions.
-  if (MadeChange)
+    // Remove dead instructions before iterating.
+    if (IterationChange)
       for (BasicBlock &BB : F)
         SimplifyInstructionsInBlock(&BB);
 
+    // Set overall changed flag.
+    MadeChange |= IterationChange;
+  } while (IterationChange);
+
   return MadeChange;
 }
 
 // Pass manager boilerplate below here.
 
 namespace {
 class VectorCombineLegacyPass : public FunctionPass {
 public:

llvm/test/Transforms/VectorCombine/X86/insert-binop.ll

;
   %i1 = insertelement <2 x i64> undef, i64 %y, i32 1
   %r = xor <2 x i64> %i0, %i1
   ret <2 x i64> %r
 }
 
 define <2 x i64> @ins1_ins1_iterate(i64 %w, i64 %x, i64 %y, i64 %z) {
 ; CHECK-LABEL: @ins1_ins1_iterate(
 ; CHECK-NEXT:    [[S0_SCALAR:%.*]] = sub i64 [[W:%.*]], [[X:%.*]]
-; CHECK-NEXT:    [[S0:%.*]] = insertelement <2 x i64> undef, i64 [[S0_SCALAR]], i64 1
-; CHECK-NEXT:    [[I2:%.*]] = insertelement <2 x i64> undef, i64 [[Y:%.*]], i32 1
-; CHECK-NEXT:    [[S1:%.*]] = or <2 x i64> [[S0]], [[I2]]
-; CHECK-NEXT:    [[I3:%.*]] = insertelement <2 x i64> undef, i64 [[Z:%.*]], i32 1
-; CHECK-NEXT:    [[S2:%.*]] = shl <2 x i64> [[I3]], [[S1]]
+; CHECK-NEXT:    [[S1_SCALAR:%.*]] = or i64 [[S0_SCALAR]], [[Y:%.*]]
+; CHECK-NEXT:    [[S2_SCALAR:%.*]] = shl i64 [[Z:%.*]], [[S1_SCALAR]]
+; CHECK-NEXT:    [[S2:%.*]] = insertelement <2 x i64> undef, i64 [[S2_SCALAR]], i64 1
 ; CHECK-NEXT:    ret <2 x i64> [[S2]]
 ;
   %i0 = insertelement <2 x i64> undef, i64 %w, i64 1
   %i1 = insertelement <2 x i64> undef, i64 %x, i32 1
   %s0 = sub <2 x i64> %i0, %i1
   %i2 = insertelement <2 x i64> undef, i64 %y, i32 1
   %s1 = or <2 x i64> %s0, %i2
   %i3 = insertelement <2 x i64> undef, i64 %z, i32 1