[LV][NFC] Improve complexity of fixing users of reductions

[michaelmaitland]

Summary

The original loop is O(MxN) since is_contained iterates over
all incoming values. This change makes it so only the phis
which use the value as an incoming value are iterated over so
it is now O(M).

This patch is analogous to D146999.

[michaelmaitland]

@fhahn Was there a reason why we did not use VPLiveOut in D147471? An alternative to this patch would be to take the same approach as D147471.

[ABataev]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

4105

auto *Phi

4107

if (auto *UPhi = dyn_cast<PHINode>(U); UPhi && UPhi->getParent() == LoopExitBlock)

[michaelmaitland]

Use auto and dyn_cast

[michaelmaitland]

Use BCBlockPhi instead of PhiR

[fhahn]

There are quite a few tests filing in the perecommit CI. Could you rebase & double check if the current version works as expected?

[fhahn]

Marking as changed requested as per previous comment.

[michaelmaitland]

I am going to abandon this revision. This case is not the same as in fixFixedOrderReccurence since we do not have the LiveOut->phis() function here to check whether the LoopExistInst is contained in incoming values in an O(1) fashion.

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

void InnerLoopVectorizer::fixReduction(VPReductionPHIRecipe *PhiR,
   }
 
   // Now, we need to fix the users of the reduction variable
   // inside and outside of the scalar remainder loop.
 
   // We know that the loop is in LCSSA form. We need to update the PHI nodes
   // in the exit blocks.  See comment on analogous loop in
   // fixFixedOrderRecurrence for a more complete explaination of the logic.
-  if (!Cost->requiresScalarEpilogue(VF))
-    for (PHINode &LCSSAPhi : LoopExitBlock->phis())
-      if (llvm::is_contained(LCSSAPhi.incoming_values(), LoopExitInst)) {
-        LCSSAPhi.addIncoming(ReducedPartRdx, LoopMiddleBlock);
-        State.Plan->removeLiveOut(&LCSSAPhi);
-      }
+  if (!Cost->requiresScalarEpilogue(VF)) {
+    SmallPtrSet<PHINode *, 2> ToFix;
+    PHINode *Phi = cast<PHINode>(PhiR->getUnderlyingValue());
+    for (User *U : Phi->users())
+      if (isa<PHINode>(U) && cast<Instruction>(U)->getParent() == LoopExitBlock)
+        ToFix.insert(cast<PHINode>(U));
+    for (PHINode *LCSSAPhi : ToFix) {
+      LCSSAPhi->addIncoming(ReducedPartRdx, LoopMiddleBlock);
+      State.Plan->removeLiveOut(LCSSAPhi);
+    }
 
   // Fix the scalar loop reduction variable with the incoming reduction sum
   // from the vector body and from the backedge value.
   int IncomingEdgeBlockIdx =
       OrigPhi->getBasicBlockIndex(OrigLoop->getLoopLatch());
   assert(IncomingEdgeBlockIdx >= 0 && "Invalid block index");
   // Pick the other block.
   int SelfEdgeBlockIdx = (IncomingEdgeBlockIdx ? 0 : 1);