[LV] Do not try to sink dead instructions.

[fhahn]

Summary

Dead instructions do not need to be sunk. Currently we try and record
the recipies for them, but there are no recipes emitted for them and
there's nothing to sink. They can be removed from SinkAfter while
marking them for recording.

Fixes PR44634.

[fhahn]

Update test checks

[merge_guards_bot]

Unit tests: fail. 62194 tests passed, 1 failed and 815 were skipped.

failed: LLVM.Transforms/LoopVectorize/first-order-recurrence.ll

clang-tidy: pass.

clang-format: pass.

Build artifacts: diff.json, clang-tidy.txt, clang-format.patch, CMakeCache.txt, console-log.txt, test-results.xml

Pre-merge checks is in beta. Report issue. Please join beta or enable it for your project.

[merge_guards_bot]

Unit tests: pass. 62195 tests passed, 0 failed and 815 were skipped.

clang-tidy: pass.

clang-format: pass.

Build artifacts: diff.json, clang-tidy.txt, clang-format.patch, CMakeCache.txt, console-log.txt, test-results.xml

Pre-merge checks is in beta. Report issue. Please join beta or enable it for your project.

[gilr]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

7172

How about cleaning sink-after once, immediately after calling collectTriviallyDeadInstrucions()?

7174

DeadInstructions.count()?

7201

Independently, this belongs in collectTriviallyDeadInstructions(), right?

7233

DeadInstructions.count()?

[fhahn]

Address comments.

[fhahn]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

7172

Done, I've moved it to the caller.

7174

I am never sure which version is really preferable. I think find() makes it a bit more explicit. But I can change it to count if that's preferred, as there can be no duplicate keys in dense maps

7201

I am not sure if it makes sense to put them there. As indicated in the comment, we really should handle them properly. They are not really dead, it's more that dropping them is the easiest way to handle them legally and adding them to DeadInstructions is the quickest way to not add them to the plan.

It should be initialized in the caller though I think. I'll put that up as a follow-up change.

7233

I can update it, if preferred.

[merge_guards_bot]

Unit tests: pass. 62198 tests passed, 0 failed and 815 were skipped.

clang-tidy: pass.

clang-format: pass.

Build artifacts: diff.json, clang-tidy.txt, clang-format.patch, CMakeCache.txt, console-log.txt, test-results.xml

Pre-merge checks is in beta. Report issue. Please join beta or enable it for your project.

[gilr]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

7135

How about:

for (auto *Dead : DeadInstructions)
  SinkAfter.erase(Dead);

Would also facilitate filtering dead instructions from other maps if needed.

[fhahn]

Iterate over DeadInstructions instead.

[merge_guards_bot]

Unit tests: pass. 62222 tests passed, 0 failed and 816 were skipped.

clang-tidy: pass.

clang-format: fail. Please format your changes with clang-format by running git-clang-format HEAD^ or applying this patch.

Build artifacts: diff.json, clang-tidy.txt, clang-format.patch, CMakeCache.txt, console-log.txt, test-results.xml

Pre-merge checks is in beta. Report issue. Please join beta or enable it for your project.

[gilr]

LGTM!

[fhahn]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

7201

I've pushed a commit moving this to the caller https://reviews.llvm.org/rGd1f849a284d9

llvm/lib/Transforms/Vectorize/LoopVectorizationPlanner.h

 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
   /// exclusive, possibly decreasing \p Range.End.
   VPlanPtr buildVPlan(VFRange &Range);
 
   /// Build a VPlan using VPRecipes according to the information gather by
   /// Legal. This method is only used for the legacy inner loop vectorizer.
-  VPlanPtr
-  buildVPlanWithVPRecipes(VFRange &Range, SmallPtrSetImpl<Value *> &NeedDef,
-                          SmallPtrSetImpl<Instruction *> &DeadInstructions);
+  VPlanPtr buildVPlanWithVPRecipes(
+      VFRange &Range, SmallPtrSetImpl<Value *> &NeedDef,
+      SmallPtrSetImpl<Instruction *> &DeadInstructions,
+      const DenseMap<Instruction *, Instruction *> &SinkAfter);
 
   /// 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. This method creates VPlans using VPRecipes.
   void buildVPlansWithVPRecipes(unsigned MinVF, unsigned MaxVF);
 };
 
 } // namespace llvm
 
 #endif // LLVM_TRANSFORMS_VECTORIZE_LOOPVECTORIZATIONPLANNER_H

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

void LoopVectorizationPlanner::buildVPlansWithVPRecipes(unsigned MinVF,
   // 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);
 
+  DenseMap<Instruction *, Instruction *> &SinkAfter = Legal->getSinkAfter();
+  // Dead instructions do not need sinking. Remove them from SinkAfter.
+  for (auto &Entry : make_early_inc_range(SinkAfter)) {
+    if (DeadInstructions.find(Entry.first) != DeadInstructions.end())
+      SinkAfter.erase(Entry.first);
+  }
+
   for (unsigned VF = MinVF; VF < MaxVF + 1;) {
     VFRange SubRange = {VF, MaxVF + 1};
-    VPlans.push_back(
-        buildVPlanWithVPRecipes(SubRange, NeedDef, DeadInstructions));
+    VPlans.push_back(buildVPlanWithVPRecipes(SubRange, NeedDef,
+                                             DeadInstructions, SinkAfter));
     VF = SubRange.End;
   }
 }
 
 VPlanPtr LoopVectorizationPlanner::buildVPlanWithVPRecipes(
     VFRange &Range, SmallPtrSetImpl<Value *> &NeedDef,
-    SmallPtrSetImpl<Instruction *> &DeadInstructions) {
+    SmallPtrSetImpl<Instruction *> &DeadInstructions,
+    const DenseMap<Instruction *, Instruction *> &SinkAfter) {
 
   // Hold a mapping from predicated instructions to their recipes, in order to
   // fix their AlsoPack behavior if a user is determined to replicate and use a
   // scalar instead of vector value.
   DenseMap<Instruction *, VPReplicateRecipe *> PredInst2Recipe;
 
-  DenseMap<Instruction *, Instruction *> &SinkAfter = Legal->getSinkAfter();
-
   SmallPtrSet<const InterleaveGroup<Instruction> *, 1> InterleaveGroups;
 
   VPRecipeBuilder RecipeBuilder(OrigLoop, TLI, Legal, CM, Builder);
 
   // ---------------------------------------------------------------------------
   // Pre-construction: record ingredients whose recipes we'll need to further
   // process after constructing the initial VPlan.
   // ---------------------------------------------------------------------------
 
   // Mark instructions we'll need to sink later and their targets as
   // ingredients whose recipe we'll need to record.
   for (auto &Entry : SinkAfter) {
     RecipeBuilder.recordRecipeOf(Entry.first);
     RecipeBuilder.recordRecipeOf(Entry.second);
   }
 
   // For each interleave group which is relevant for this (possibly trimmed)
   // Range, add it to the set of groups to be later applied to the VPlan and add
   // placeholders for its members' Recipes which we'll be replacing with a
   // single VPInterleaveRecipe.
   for (InterleaveGroup<Instruction> *IG : IAI.getInterleaveGroups()) {
     auto applyIG = [IG, this](unsigned VF) -> bool {
       return (VF >= 2 && // Query is illegal for VF == 1
               CM.getWideningDecision(IG->getInsertPos(), VF) ==
                   LoopVectorizationCostModel::CM_Interleave);
VPlanPtr LoopVectorizationPlanner::buildVPlanWithVPRecipes(
   // Build initial VPlan: Scan the body of the loop in a topological order to
   // visit each basic block after having visited its predecessor basic blocks.
   // ---------------------------------------------------------------------------
 
   // 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.
   auto &ConditionalAssumes = Legal->getConditionalAssumes();
   DeadInstructions.insert(ConditionalAssumes.begin(), ConditionalAssumes.end());
 
   // Create a dummy pre-entry VPBasicBlock to start building the VPlan.
   VPBasicBlock *VPBB = new VPBasicBlock("Pre-Entry");
   auto Plan = std::make_unique<VPlan>(VPBB);
 
   // Represent values that will have defs inside VPlan.
   for (Value *V : NeedDef)
for (BasicBlock *BB : make_range(DFS.beginRPO(), DFS.endRPO())) {
 
     // Introduce each ingredient into VPlan.
     for (Instruction &I : BB->instructionsWithoutDebug()) {
       Instruction *Instr = &I;
 
       // First filter out irrelevant instructions, to ensure no recipes are
       // built for them.
       if (isa<BranchInst>(Instr) ||
           DeadInstructions.find(Instr) != DeadInstructions.end())
         continue;
 
       if (RecipeBuilder.tryToCreateRecipe(Instr, Range, Plan, VPBB))
         continue;
 
       // Otherwise, if all widening options failed, Instruction is to be
       // replicated. This may create a successor for VPBB.
       VPBasicBlock *NextVPBB = RecipeBuilder.handleReplication(

llvm/test/Transforms/LoopVectorize/first-order-recurrence.ll

cond.end:                                         ; preds = %for.body4, %cond.true
   %indvars.iv.next = add nuw nsw i32 %indvars.iv, 1
   %cmp5 = icmp slt i32 %indvars.iv.next, %tc
   %exitcond = icmp eq i32 %indvars.iv.next, %x
   br i1 %exitcond, label %for.end12.loopexit, label %for.body4
 
 for.end12.loopexit:                               ; preds = %cond.end
   ret void
 }
+
+; Dead instructions, like the exit condition are not part of the actual VPlan
+; and do not need to be sunk. PR44634.
+define void @sink_dead_inst() {
+; SINK-AFTER-LABEL: define void @sink_dead_inst(
+; SINK-AFTER-LABEL: vector.body:                                      ; preds = %vector.body, %vector.ph
+; SINK-AFTER-NEXT:    %index = phi i32 [ 0, %vector.ph ], [ %index.next, %vector.body ]
+; SINK-AFTER-NEXT:    %vec.ind = phi <4 x i16> [ <i16 -27, i16 -26, i16 -25, i16 -24>, %vector.ph ], [ %vec.ind.next, %vector.body ]
+; SINK-AFTER-NEXT:    %vector.recur = phi <4 x i16> [ <i16 undef, i16 undef, i16 undef, i16 0>, %vector.ph ], [ %3, %vector.body ]
+; SINK-AFTER-NEXT:    %vector.recur2 = phi <4 x i32> [ <i32 undef, i32 undef, i32 undef, i32 -27>, %vector.ph ], [ %1, %vector.body ]
+; SINK-AFTER-NEXT:    %0 = add <4 x i16> %vec.ind, <i16 1, i16 1, i16 1, i16 1>
+; SINK-AFTER-NEXT:    %1 = zext <4 x i16> %0 to <4 x i32>
+; SINK-AFTER-NEXT:    %2 = shufflevector <4 x i32> %vector.recur2, <4 x i32> %1, <4 x i32> <i32 3, i32 4, i32 5, i32 6>
+; SINK-AFTER-NEXT:    %3 = add <4 x i16> %0, <i16 5, i16 5, i16 5, i16 5>
+; SINK-AFTER-NEXT:    %4 = shufflevector <4 x i16> %vector.recur, <4 x i16> %3, <4 x i32> <i32 3, i32 4, i32 5, i32 6>
+; SINK-AFTER-NEXT:    %5 = sub <4 x i16> %4, <i16 10, i16 10, i16 10, i16 10>
+; SINK-AFTER-NEXT:    %index.next = add i32 %index, 4
+; SINK-AFTER-NEXT:    %vec.ind.next = add <4 x i16> %vec.ind, <i16 4, i16 4, i16 4, i16 4>
+; SINK-AFTER-NEXT:    %6 = icmp eq i32 %index.next, 40
+; SINK-AFTER-NEXT:    br i1 %6, label %middle.block, label %vector.body, !llvm.loop !43
+;
+entry:
+  br label %for.cond
+
+for.cond:
+  %iv = phi i16 [ -27, %entry ], [ %iv.next, %for.cond ]
+  %rec.1 = phi i16 [ 0, %entry ], [ %rec.1.prev, %for.cond ]
+  %rec.2 = phi i32 [ -27, %entry ], [ %rec.2.prev, %for.cond ]
+  %use.rec.1 = sub i16 %rec.1, 10
+  %cmp = icmp eq i32 %rec.2, 15
+  %iv.next = add i16 %iv, 1
+  %rec.2.prev = zext i16 %iv.next to i32
+  %rec.1.prev = add i16 %iv.next, 5
+  br i1 %cmp, label %for.end, label %for.cond
+
+for.end:
+  ret void
+}