[LV] Remove collectTriviallyDeadInstructions, already handled by VP DCE.

[fhahn]

Summary

Now that removeDeadRecipes can remove most dead recipes across a whole
VPlan, there is no need to first collect some dead instructions.
Instead removeDeadRecipes can simply clean them up.

Depends D127580.

[Ayal]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

8953

To be close to current state, dead recipes should be removed as early as possible, but they should also clean up after optimizeInductions() and/or sinkScalarOperands() (but not after mergeReplicateRegions())? Can also run it twice, keeping the late version at the end next to removeRedundantExpandSCEVRecipes(), and issuing it early instead of the preparatory collectTriviallyDeadInstructions().

llvm/test/Transforms/LoopVectorize/X86/consecutive-ptr-uniforms.ll

101

Hmm, moving removeDeadRecipes() removed alsoPack or something?

In the case of PR40816, the loads (and phi's they feed) are also redundant and can be discarded, as LV sees through them to figure out the trip count.

llvm/test/Transforms/LoopVectorize/pointer-induction.ll

39

Avoid sinking scalar GEP into first triangle?

Perhaps worth separating the movement of removeDeadRecipes() from the removal of collectTriviallyDeadInstructions() into separate patches, to clarify the origin of these changes.

[fhahn]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

8953

I am not sure we can move it up much, as the interleave group code still accesses values via IR references. In theory we could remove a load that's never used and crash.

llvm/test/Transforms/LoopVectorize/X86/consecutive-ptr-uniforms.ll

101

I think we remove some unnecessary users earlier, hence no need to pack.

We can also remove the unused phis, will do in a late patch.

llvm/test/Transforms/LoopVectorize/pointer-induction.ll

39

I think this change is combination of moving removeDeadRecipes and removing collectTriviallyDeadInstructions, through which we end up avoiding to sink

[Ayal]

llvm/test/Transforms/LoopVectorize/pointer-induction.ll

39

So does it make sense to first only hoist removeDeadRecipes() above mergeReplicateRegions(), and then remove collectTriviallyDeadInstructions in a separate patch, isolating any such effects?

[fhahn]

llvm/test/Transforms/LoopVectorize/pointer-induction.ll

39

I can hoist removeDeadRecipes up separately, but moving it alone won't show any changes in the existing tests unfortunately.

[Ayal]

llvm/test/Transforms/LoopVectorize/pointer-induction.ll

39

I can hoist removeDeadRecipes up separately, but moving it alone won't show any changes in the existing tests unfortunately.

So be it. Is the hoist important?

[fhahn]

Rebase after splitting off removeDeadRecipes movement to D128831.

[fhahn]

llvm/test/Transforms/LoopVectorize/pointer-induction.ll

39

The movement is important to avoid some regressions in some of the tests, due to dead instructions blocking region merging. I managed to construct a test case and split off the movement of removeDeadRecipes to D128831

[Ayal]

Nice clean-up!
Adding a nit for potential further clean-ups.

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

8534

Shall assumes be dropped as a VPlan2VPlan transformation, thereby eliminating DeadInstructions, simplifying sinking after them below, and potentially taking care of the TODO? As separate follow-up patch(es).

llvm/test/Transforms/LoopVectorize/pointer-induction.ll

39

The movement is important to avoid some regressions in some of the tests, due to dead instructions blocking region merging. I managed to construct a test case and split off the movement of removeDeadRecipes to D128831

Excellent!

[fhahn]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

8534

As separate follow-up patch(es).

Yes I am planning on doing this as follow up, the goal is to completely remove DeadInstructions

llvm/lib/Transforms/Vectorize/LoopVectorizationPlanner.h

#endif
   static bool
   getDecisionAndClampRange(const std::function<bool(ElementCount)> &Predicate,
                            VFRange &Range);
 
   /// Check if the number of runtime checks exceeds the threshold.
   bool requiresTooManyRuntimeChecks() const;
 
 protected:
-  /// Collect the instructions from the original loop that would be trivially
-  /// dead in the vectorized loop if generated.
-  void collectTriviallyDeadInstructions(
-      SmallPtrSetImpl<Instruction *> &DeadInstructions);
-
   /// Build VPlans for power-of-2 VF's between \p MinVF and \p MaxVF inclusive,
   /// according to the information gathered by Legal when it checked if it is
   /// legal to vectorize the loop.
   void buildVPlans(ElementCount MinVF, ElementCount MaxVF);
 
 private:
   /// Build a VPlan according to the information gathered by Legal. \return a
   /// VPlan for vectorization factors \p Range.Start and up to \p Range.End

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

void LoopVectorizationPlanner::printPlans(raw_ostream &O) {
   for (const auto &Plan : VPlans)
     if (PrintVPlansInDotFormat)
       Plan->printDOT(O);
     else
       Plan->print(O);
 }
 #endif
 
-void LoopVectorizationPlanner::collectTriviallyDeadInstructions(
-    SmallPtrSetImpl<Instruction *> &DeadInstructions) {
-
-  // We create new control-flow for the vectorized loop, so the original exit
-  // conditions will be dead after vectorization if it's only used by the
-  // terminator
-  SmallVector<BasicBlock*> ExitingBlocks;
-  OrigLoop->getExitingBlocks(ExitingBlocks);
-  for (auto *BB : ExitingBlocks) {
-    auto *Cmp = dyn_cast<Instruction>(BB->getTerminator()->getOperand(0));
-    if (!Cmp || !Cmp->hasOneUse())
-      continue;
-
-    // TODO: we should introduce a getUniqueExitingBlocks on Loop
-    if (!DeadInstructions.insert(Cmp).second)
-      continue;
-
-    // The operands of the icmp is often a dead trunc, used by IndUpdate.
-    // TODO: can recurse through operands in general
-    for (Value *Op : Cmp->operands()) {
-      if (isa<TruncInst>(Op) && Op->hasOneUse())
-          DeadInstructions.insert(cast<Instruction>(Op));
-    }
-  }
-
-  // We create new "steps" for induction variable updates to which the original
-  // induction variables map. An original update instruction will be dead if
-  // all its users except the induction variable are dead.
-  auto *Latch = OrigLoop->getLoopLatch();
-  for (auto &Induction : Legal->getInductionVars()) {
-    PHINode *Ind = Induction.first;
-    auto *IndUpdate = cast<Instruction>(Ind->getIncomingValueForBlock(Latch));
-
-    // If the tail is to be folded by masking, the primary induction variable,
-    // if exists, isn't dead: it will be used for masking. Don't kill it.
-    if (CM.foldTailByMasking() && IndUpdate == Legal->getPrimaryInduction())
-      continue;
-
-    if (llvm::all_of(IndUpdate->users(), [&](User *U) -> bool {
-          return U == Ind || DeadInstructions.count(cast<Instruction>(U));
-        }))
-      DeadInstructions.insert(IndUpdate);
-  }
-}
-
 Value *InnerLoopUnroller::getBroadcastInstrs(Value *V) { return V; }
 
 //===--------------------------------------------------------------------===//
 // EpilogueVectorizerMainLoop
 //===--------------------------------------------------------------------===//
 
 /// This function is partially responsible for generating the control flow
 /// depicted in https://llvm.org/docs/Vectorizers.html#epilogue-vectorization.
VPRecipeBuilder::tryToCreateWidenRecipe(Instruction *Instr,
 
   return toVPRecipeResult(tryToWiden(Instr, Operands));
 }
 
 void LoopVectorizationPlanner::buildVPlansWithVPRecipes(ElementCount MinVF,
                                                         ElementCount MaxVF) {
   assert(OrigLoop->isInnermost() && "Inner loop expected.");
 
-  // Collect instructions from the original loop that will become trivially dead
-  // in the vectorized loop. We don't need to vectorize these instructions. For
-  // example, original induction update instructions can become dead because we
-  // separately emit induction "steps" when generating code for the new loop.
-  // Similarly, we create a new latch condition when setting up the structure
-  // of the new loop, so the old one can become dead.
-  SmallPtrSet<Instruction *, 4> DeadInstructions;
-  collectTriviallyDeadInstructions(DeadInstructions);
-
   // Add assume instructions we need to drop to DeadInstructions, to prevent
   // them from being added to the VPlan.
   // TODO: We only need to drop assumes in blocks that get flattend. If the
   // control flow is preserved, we should keep them.
+  SmallPtrSet<Instruction *, 4> DeadInstructions;
   auto &ConditionalAssumes = Legal->getConditionalAssumes();
   DeadInstructions.insert(ConditionalAssumes.begin(), ConditionalAssumes.end());
 
   MapVector<Instruction *, Instruction *> &SinkAfter = Legal->getSinkAfter();
   // Dead instructions do not need sinking. Remove them from SinkAfter.
   for (Instruction *I : DeadInstructions)
     SinkAfter.erase(I);
 
VPlanPtr LoopVectorizationPlanner::buildVPlanWithVPRecipes(
   }
 
   // From this point onwards, VPlan-to-VPlan transformations may change the plan
   // in ways that accessing values using original IR values is incorrect.
   Plan->disableValue2VPValue();
 
   VPlanTransforms::optimizeInductions(*Plan, *PSE.getSE());
   VPlanTransforms::sinkScalarOperands(*Plan);
-  VPlanTransforms::mergeReplicateRegions(*Plan);
   VPlanTransforms::removeDeadRecipes(*Plan);
+  VPlanTransforms::mergeReplicateRegions(*Plan);
   VPlanTransforms::removeRedundantExpandSCEVRecipes(*Plan);
 
   std::string PlanName;
   raw_string_ostream RSO(PlanName);
   ElementCount VF = Range.Start;
   Plan->addVF(VF);
   RSO << "Initial VPlan for VF={" << VF;
   for (VF *= 2; ElementCount::isKnownLT(VF, Range.End); VF *= 2) {

llvm/test/Transforms/LoopVectorize/X86/consecutive-ptr-uniforms.ll

 ; FORCE-NEXT:    [[TMP2:%.*]] = icmp ule <2 x i32> [[VEC_IND]], <i32 2, i32 2>
 ; FORCE-NEXT:    [[TMP3:%.*]] = extractelement <2 x i1> [[TMP2]], i32 0
 ; FORCE-NEXT:    br i1 [[TMP3]], label [[PRED_LOAD_IF:%.*]], label [[PRED_LOAD_CONTINUE:%.*]]
 ; FORCE:       pred.load.if:
 ; FORCE-NEXT:    [[TMP0:%.*]] = add i32 [[INDEX]], 0
 ; FORCE-NEXT:    store i32 [[TMP0]], i32* @b, align 1
 ; FORCE-NEXT:    [[TMP6:%.*]] = getelementptr inbounds [3 x i32], [3 x i32]* @a, i32 0, i32 [[TMP0]]
 ; FORCE-NEXT:    [[TMP7:%.*]] = load i32, i32* [[TMP6]], align 1
-; FORCE-NEXT:    [[TMP8:%.*]] = insertelement <2 x i32> poison, i32 [[TMP7]], i32 0
 ; FORCE-NEXT:    br label [[PRED_LOAD_CONTINUE]]
 ; FORCE:       pred.load.continue:
-; FORCE-NEXT:    [[TMP9:%.*]] = phi <2 x i32> [ poison, [[VECTOR_BODY]] ], [ [[TMP8]], [[PRED_LOAD_IF]] ]
+; FORCE-NEXT:    [[TMP9:%.*]] = phi i32 [ poison, [[VECTOR_BODY]] ], [ [[TMP7]], [[PRED_LOAD_IF]] ]
 ; FORCE-NEXT:    [[TMP10:%.*]] = extractelement <2 x i1> [[TMP2]], i32 1
 ; FORCE-NEXT:    br i1 [[TMP10]], label [[PRED_LOAD_IF3:%.*]], label [[PRED_LOAD_CONTINUE4]]
 ; FORCE:       pred.load.if1:
 ; FORCE-NEXT:    [[TMP1:%.*]] = add i32 [[INDEX]], 1
 ; FORCE-NEXT:    store i32 [[TMP1]], i32* @b, align 1
 ; FORCE-NEXT:    [[TMP11:%.*]] = getelementptr inbounds [3 x i32], [3 x i32]* @a, i32 0, i32 [[TMP1]]
 ; FORCE-NEXT:    [[TMP12:%.*]] = load i32, i32* [[TMP11]], align 1
-; FORCE-NEXT:    [[TMP13:%.*]] = insertelement <2 x i32> [[TMP9]], i32 [[TMP12]], i32 1
 ; FORCE-NEXT:    br label [[PRED_LOAD_CONTINUE4]]
 ; FORCE:       pred.load.continue2:
-; FORCE-NEXT:    [[TMP14:%.*]] = phi <2 x i32> [ [[TMP9]], [[PRED_LOAD_CONTINUE]] ], [ [[TMP13]], [[PRED_LOAD_IF3]] ]
+; FORCE-NEXT:    [[TMP13:%.*]] = phi i32 [ poison, %pred.load.continue ], [ [[TMP12]], %pred.load.if1 ]
 ; FORCE-NEXT:    [[INDEX_NEXT]] = add i32 [[INDEX]], 2
 ; FORCE-NEXT:    [[VEC_IND_NEXT]] = add <2 x i32> [[VEC_IND]], <i32 2, i32 2>
 ; FORCE-NEXT:    [[TMP15:%.*]] = icmp eq i32 [[INDEX_NEXT]], 4
 ; FORCE-NEXT:    br i1 [[TMP15]], label {{%.*}}, label [[VECTOR_BODY]]
 ;
 @a = internal constant [3 x i32] [i32 7, i32 7, i32 0], align 1
 @b = external global i32, align 1
 

llvm/test/Transforms/LoopVectorize/pointer-induction.ll

 ; CHECK-NEXT:    [[TMP7:%.*]] = bitcast i8* [[TMP6]] to <4 x i8>*
 ; CHECK-NEXT:    [[WIDE_LOAD:%.*]] = load <4 x i8>, <4 x i8>* [[TMP7]], align 1
 ; CHECK-NEXT:    [[REVERSE:%.*]] = shufflevector <4 x i8> [[WIDE_LOAD]], <4 x i8> poison, <4 x i32> <i32 3, i32 2, i32 1, i32 0>
 ; CHECK-NEXT:    [[TMP8:%.*]] = icmp eq <4 x i8> [[REVERSE]], zeroinitializer
 ; CHECK-NEXT:    [[TMP9:%.*]] = xor <4 x i1> [[TMP8]], <i1 true, i1 true, i1 true, i1 true>
 ; CHECK-NEXT:    [[TMP10:%.*]] = extractelement <4 x i1> [[TMP9]], i32 0
 ; CHECK-NEXT:    br i1 [[TMP10]], label [[PRED_STORE_IF:%.*]], label [[PRED_STORE_CONTINUE:%.*]]
 ; CHECK:       pred.store.if:
-; CHECK-NEXT:    [[TMP11:%.*]] = getelementptr inbounds i8, i8* [[NEXT_GEP]], i64 -1
-; CHECK-NEXT:    store i8 95, i8* [[TMP11]], align 1
+; CHECK-NEXT:    store i8 95, i8* [[TMP4]], align 1
 ; CHECK-NEXT:    br label [[PRED_STORE_CONTINUE]]
 ; CHECK:       pred.store.continue:
 ; CHECK-NEXT:    [[TMP12:%.*]] = extractelement <4 x i1> [[TMP9]], i32 1
 ; CHECK-NEXT:    br i1 [[TMP12]], label [[PRED_STORE_IF5:%.*]], label [[PRED_STORE_CONTINUE6:%.*]]
 ; CHECK:       pred.store.if5:
 ; CHECK-NEXT:    [[TMP13:%.*]] = add i64 [[INDEX]], 1
 ; CHECK-NEXT:    [[TMP14:%.*]] = mul i64 [[TMP13]], -1
 ; CHECK-NEXT:    [[NEXT_GEP2:%.*]] = getelementptr i8, i8* null, i64 [[TMP14]]