[LV] Avoid emitting trivially dead instructions

[mssimpso]

Summary

Some instructions from the original loop, when vectorized, can become trivially dead. This happens because of the way we structure the new loop. For example, we create new induction variables and induction variable "steps" in the new loop. Thus, when we go to vectorize the original induction variable update, it may no longer be needed due to the instructions we've already created. This patch prevents us from creating these redundant instructions. This reduces code size before simplification and allows greater flexibility in code generation since we have fewer unnecessary instruction uses.

[mkuper]

I assume the motivation is that we don't want to run adce after the vectorizer, and "regular" dce doesn't catch this because of loop-carried dependencies?

[mssimpso]

In D25631#570826, @mkuper wrote:

I assume the motivation is that we don't want to run adce after the vectorizer, and "regular" dce doesn't catch this because of loop-carried dependencies?

No, this is mostly motivated by the sinking patch I submitted. These trivially dead instructions can create uses of scalar instructions that can potentially be sunk into predicated blocks. They prevent sinking because if we were to move the scalars, their definitions would no longer dominate the uses, even though the uses should later be deleted.

[gilr]

lib/Transforms/Vectorize/LoopVectorize.cpp

4241

Perhaps replace the double-negation with "... if all its users except the induction variable are dead"?

4246

The "|| U == Cmp" test seems to kill the update whether or not Cmp is dead. Per the above comment I think you meant here "|| DeadInstructions.count(U)", right?

[mssimpso]

lib/Transforms/Vectorize/LoopVectorize.cpp

4241

That's much better. Thanks!

4246

Yes, nice catch! I'll update the patch.

[mssimpso]

Addressed Gil's comments. Thanks!

[mkuper]

LGTM with a nit about naming.

lib/Transforms/Vectorize/LoopVectorize.cpp

4243

Ind/Induction combined with the two "autos" is confusing. Maybe make the type of Ind explicit (or call it IndPhi?)?

[mssimpso]

lib/Transforms/Vectorize/LoopVectorize.cpp

4243

I'll make the type explicit. Thanks Michael!

[gilr]

LGTM

lib/Transforms/Vectorize/LoopVectorize.cpp

protected:
   /// that were defined inside the loop. Here we fix the 'undef case'.
   /// See PR14725.
   void fixLCSSAPHIs();
 
   /// Predicate conditional instructions that require predication on their
   /// respective conditions.
   void predicateInstructions();
 
+  /// Collect the instructions from the original loop that would be trivially
+  /// dead in the vectorized loop if generated.
+  void collectTriviallyDeadInstructions();
+
   /// Shrinks vector element sizes to the smallest bitwidth they can be legally
   /// represented as.
   void truncateToMinimalBitwidths();
 
   /// A helper function that computes the predicate of the block BB, assuming
   /// that the header block of the loop is set to True. It returns the *entry*
   /// mask for the block BB.
   VectorParts createBlockInMask(BasicBlock *BB);
protected:
   /// The legality analysis.
   LoopVectorizationLegality *Legal;
 
   /// The profitablity analysis.
   LoopVectorizationCostModel *Cost;
 
   // Record whether runtime checks are added.
   bool AddedSafetyChecks;
+
+  // Holds instructions from the original loop whose counterparts in the
+  // vectorized loop would be trivially dead if generated. 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;
 };
 
 class InnerLoopUnroller : public InnerLoopVectorizer {
 public:
   InnerLoopUnroller(Loop *OrigLoop, PredicatedScalarEvolution &PSE,
                     LoopInfo *LI, DominatorTree *DT,
                     const TargetLibraryInfo *TLI,
                     const TargetTransformInfo *TTI, AssumptionCache *AC,
void InnerLoopVectorizer::vectorizeLoop() {
   // Phi nodes have cycles, so we need to vectorize them in two stages. First,
   // we create a new vector PHI node with no incoming edges. We use this value
   // when we vectorize all of the instructions that use the PHI. Next, after
   // all of the instructions in the block are complete we add the new incoming
   // edges to the PHI. At this point all of the instructions in the basic block
   // are vectorized, so we can use them to construct the PHI.
   PhiVector PHIsToFix;
 
+  // Collect instructions from the original loop that will become trivially
+  // dead in the vectorized loop. We don't need to vectorize these
+  // instructions.
+  collectTriviallyDeadInstructions();
+
   // Scan the loop in a topological order to ensure that defs are vectorized
   // before users.
   LoopBlocksDFS DFS(OrigLoop);
   DFS.perform(LI);
 
   // Vectorize all of the blocks in the original loop.
   for (BasicBlock *BB : make_range(DFS.beginRPO(), DFS.endRPO()))
     vectorizeBlockInLoop(BB, &PHIsToFix);
for (Instruction &LEI : *LoopExitBlock) {
     if (!LCSSAPhi)
       break;
     if (LCSSAPhi->getNumIncomingValues() == 1)
       LCSSAPhi->addIncoming(UndefValue::get(LCSSAPhi->getType()),
                             LoopMiddleBlock);
   }
 }
 
+void InnerLoopVectorizer::collectTriviallyDeadInstructions() {
+  BasicBlock *Latch = OrigLoop->getLoopLatch();
+
+  // We create new control-flow for the vectorized loop, so the original
+  // condition will be dead after vectorization if it's only used by the
+  // branch.
+  auto *Cmp = dyn_cast<Instruction>(Latch->getTerminator()->getOperand(0));
+  if (Cmp && Cmp->hasOneUse())
+    DeadInstructions.insert(Cmp);
+
+  // 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.
+  for (auto &Induction : *Legal->getInductionVars()) {
+    auto *Ind = Induction.first;
+    auto *IndUpdate = cast<Instruction>(Ind->getIncomingValueForBlock(Latch));
+    if (all_of(IndUpdate->users(), [&](User *U) -> bool {
+          return U == Ind || DeadInstructions.count(cast<Instruction>(U));
+        }))
+      DeadInstructions.insert(IndUpdate);
+  }
+}
+
 void InnerLoopVectorizer::predicateInstructions() {
 
   // For each instruction I marked for predication on value C, split I into its
   // own basic block to form an if-then construct over C.
   // Since I may be fed by extractelement and/or be feeding an insertelement
   // generated during scalarization we try to move such instructions into the
   // predicated basic block as well. For the insertelement this also means that
   // the PHI will be created for the resulting vector rather than for the
static bool mayDivideByZero(Instruction &I) {
   auto *CInt = dyn_cast<ConstantInt>(Divisor);
   return !CInt || CInt->isZero();
 }
 
 void InnerLoopVectorizer::vectorizeBlockInLoop(BasicBlock *BB, PhiVector *PV) {
   // For each instruction in the old loop.
   for (Instruction &I : *BB) {
 
+    // If the instruction will become trivially dead when vectorized, we don't
+    // need to generate it.
+    if (DeadInstructions.count(&I))
+      continue;
+
     // Scalarize instructions that should remain scalar after vectorization.
     if (!(isa<BranchInst>(&I) || isa<PHINode>(&I) ||
           isa<DbgInfoIntrinsic>(&I)) &&
         Legal->isScalarAfterVectorization(&I)) {
       scalarizeInstruction(&I);
       continue;
     }
 

test/Transforms/LoopVectorize/dead_instructions.ll

+; RUN: opt < %s -force-vector-width=2 -force-vector-interleave=2 -loop-vectorize -S | FileCheck %s
+
+target datalayout = "e-m:e-i64:64-i128:128-n32:64-S128"
+
+; CHECK-LABEL: @dead_instructions_01
+;
+; This test ensures that we don't generate trivially dead instructions prior to
+; instruction simplification. We don't need to generate instructions
+; corresponding to the original induction variable update or branch condition,
+; since we rewrite the loop structure.
+;
+; CHECK:     vector.body:
+; CHECK:       %index = phi i64 [ 0, %vector.ph ], [ %index.next, %vector.body ]
+; CHECK:       %[[I0:.+]] = add i64 %index, 0
+; CHECK:       %[[I2:.+]] = add i64 %index, 2
+; CHECK:       getelementptr inbounds i64, i64* %a, i64 %[[I0]]
+; CHECK:       getelementptr inbounds i64, i64* %a, i64 %[[I2]]
+; CHECK-NOT:   add nuw nsw i64 %[[I0]], 1
+; CHECK-NOT:   add nuw nsw i64 %[[I2]], 1
+; CHECK-NOT:   icmp slt i64 {{.*}}, %n
+; CHECK:       %index.next = add i64 %index, 4
+; CHECK:       %[[CMP:.+]] = icmp eq i64 %index.next, %n.vec
+; CHECK:       br i1 %[[CMP]], label %middle.block, label %vector.body
+;
+define i64 @dead_instructions_01(i64 *%a, i64 %n) {
+entry:
+  br label %for.body
+
+for.body:
+  %i = phi i64 [ %i.next, %for.body ], [ 0, %entry ]
+  %r = phi i64 [ %tmp2, %for.body ], [ 0, %entry ]
+  %tmp0 = getelementptr inbounds i64, i64* %a, i64 %i
+  %tmp1 = load i64, i64* %tmp0, align 8
+  %tmp2 = add i64 %tmp1, %r
+  %i.next = add nuw nsw i64 %i, 1
+  %cond = icmp slt i64 %i.next, %n
+  br i1 %cond, label %for.body, label %for.end
+
+for.end:
+  %tmp3  = phi i64 [ %tmp2, %for.body ]
+  ret i64 %tmp3
+}