[SLPVectorizer] Use InstructionsState to record AltOpcode

[RKSimon]

Summary

This is part of a move towards generalizing the alternate opcode mechanism and not just supporting (F)Add/(F)Sub counterparts.

The patch embeds the AltOpcode in the InstructionsState instead of calling getAltOpcode so often.

I'm hoping to eventually remove all uses of getAltOpcode and handle alternate opcode selection entirely within getSameOpcode, that will require us to use InstructionsState throughout the BoUpSLP call hierarchy (similar to some of the changes in D28907), which I will begin in future patches.

[dtemirbulatov]

looks good for me.

[ABataev]

LG except with a nit.

lib/Transforms/Vectorize/SLPVectorizer.cpp

355 ↗

(On Diff #152054)

s/IsAltShuffle/isAltShuffle/g

llvm/trunk/lib/Transforms/Vectorize/SLPVectorizer.cpp

if (sameOpcodeOrAlt(OpInstOpcode, getAltOpcode(OpInstOpcode), IOpcode))
     return Op;
   return OpValue;
 }
 
 namespace {
 
 /// Main data required for vectorization of instructions.
 struct InstructionsState {
-  /// The very first instruction in the list with the main opcode.
-  Value *OpValue = nullptr;
-
-  /// The main opcode for the list of instructions.
-  unsigned Opcode = 0;
-
-  /// Some of the instructions in the list have alternate opcodes.
-  bool IsAltShuffle = false;
-
-  InstructionsState() = default;
-  InstructionsState(Value *OpValue, unsigned Opcode, bool IsAltShuffle)
-      : OpValue(OpValue), Opcode(Opcode), IsAltShuffle(IsAltShuffle) {}
-};
-
-} // end anonymous namespace
+  /// The very first instruction in the list with the main opcode.
+  Value *OpValue = nullptr;
+
+  /// The main/alternate opcodes for the list of instructions.
+  unsigned Opcode = 0;
+  unsigned AltOpcode = 0;
+
+  /// Some of the instructions in the list have alternate opcodes.
+  bool isAltShuffle() const { return Opcode != AltOpcode; }
+
+  InstructionsState() = default;
+  InstructionsState(Value *OpValue, unsigned Opcode, unsigned AltOpcode)
+      : OpValue(OpValue), Opcode(Opcode), AltOpcode(AltOpcode) {}
+};
+
+} // end anonymous namespace
 
 /// \returns analysis of the Instructions in \p VL described in
 /// InstructionsState, the Opcode that we suppose the whole list 
 /// could be vectorized even if its structure is diverse.
 static InstructionsState getSameOpcode(ArrayRef<Value *> VL) {
   // Make sure these are all Instructions.
   if (llvm::any_of(VL, [](Value *V) { return !isa<Instruction>(V); }))
-    return InstructionsState(VL[0], 0, false);
+    return InstructionsState(VL[0], 0, 0);
 
   unsigned Opcode = cast<Instruction>(VL[0])->getOpcode();
+  unsigned AltOpcode = Opcode;
   bool HasAltOpcodes = llvm::any_of(VL, [Opcode](Value *V) {
     return Opcode != cast<Instruction>(V)->getOpcode();
   });
 
   // Check for an alternate opcode pattern.
   if (HasAltOpcodes) {
-    unsigned AltOpcode = getAltOpcode(Opcode);
+    AltOpcode = getAltOpcode(Opcode);
     for (int Cnt = 0, E = VL.size(); Cnt < E; Cnt++) {
       unsigned InstOpcode = cast<Instruction>(VL[Cnt])->getOpcode();
       if (!sameOpcodeOrAlt(Opcode, AltOpcode, InstOpcode))
-        return InstructionsState(VL[0], 0, false);
+        return InstructionsState(VL[0], 0, 0);
     }
   }
 
-  return InstructionsState(VL[0], Opcode, HasAltOpcodes);
+  return InstructionsState(VL[0], Opcode, AltOpcode);
 }
 
 /// \returns true if all of the values in \p VL have the same type or false
 /// otherwise.
 static bool allSameType(ArrayRef<Value *> VL) {
   Type *Ty = VL[0]->getType();
   for (int i = 1, e = VL.size(); i < e; i++)
     if (VL[i]->getType() != Ty)
void BoUpSLP::buildTree_rec(ArrayRef<Value *> VL, unsigned Depth,
 
   if (!BS.tryScheduleBundle(VL, this, VL0)) {
     LLVM_DEBUG(dbgs() << "SLP: We are not able to schedule this bundle!\n");
     assert((!BS.getScheduleData(VL0) ||
             !BS.getScheduleData(VL0)->isPartOfBundle()) &&
            "tryScheduleBundle should cancelScheduling on failure");
     newTreeEntry(VL, false, UserTreeIdx, ReuseShuffleIndicies);
     return;
-  }
-  LLVM_DEBUG(dbgs() << "SLP: We are able to schedule this bundle.\n");
-
-  unsigned ShuffleOrOp = S.IsAltShuffle ?
-                (unsigned) Instruction::ShuffleVector : S.Opcode;
-  switch (ShuffleOrOp) {
-    case Instruction::PHI: {
+  }
+  LLVM_DEBUG(dbgs() << "SLP: We are able to schedule this bundle.\n");
+
+  unsigned ShuffleOrOp = S.isAltShuffle() ?
+                (unsigned) Instruction::ShuffleVector : S.Opcode;
+  switch (ShuffleOrOp) {
+    case Instruction::PHI: {
       PHINode *PH = dyn_cast<PHINode>(VL0);
 
       // Check for terminator values (e.g. invoke).
       for (unsigned j = 0; j < VL.size(); ++j)
         for (unsigned i = 0, e = PH->getNumIncomingValues(); i < e; ++i) {
           TerminatorInst *Term = dyn_cast<TerminatorInst>(
               cast<PHINode>(VL[j])->getIncomingValueForBlock(PH->getIncomingBlock(i)));
           if (Term) {
case Instruction::Call: {
         for (Value *j : VL) {
           CallInst *CI2 = dyn_cast<CallInst>(j);
           Operands.push_back(CI2->getArgOperand(i));
         }
         buildTree_rec(Operands, Depth + 1, UserTreeIdx);
       }
       return;
     }
-    case Instruction::ShuffleVector:
-      // If this is not an alternate sequence of opcode like add-sub
-      // then do not vectorize this instruction.
-      if (!S.IsAltShuffle) {
-        BS.cancelScheduling(VL, VL0);
-        newTreeEntry(VL, false, UserTreeIdx, ReuseShuffleIndicies);
-        LLVM_DEBUG(dbgs() << "SLP: ShuffleVector are not vectorized.\n");
+    case Instruction::ShuffleVector:
+      // If this is not an alternate sequence of opcode like add-sub
+      // then do not vectorize this instruction.
+      if (!S.isAltShuffle()) {
+        BS.cancelScheduling(VL, VL0);
+        newTreeEntry(VL, false, UserTreeIdx, ReuseShuffleIndicies);
+        LLVM_DEBUG(dbgs() << "SLP: ShuffleVector are not vectorized.\n");
         return;
       }
       newTreeEntry(VL, true, UserTreeIdx, ReuseShuffleIndicies);
       LLVM_DEBUG(dbgs() << "SLP: added a ShuffleVector op.\n");
 
-      // Reorder operands if reordering would enable vectorization.
-      if (isa<BinaryOperator>(VL0)) {
-        ValueList Left, Right;
-        unsigned AltOpcode = getAltOpcode(S.Opcode);
-        reorderAltShuffleOperands(S.Opcode, AltOpcode, VL, Left, Right);
-        buildTree_rec(Left, Depth + 1, UserTreeIdx);
-        buildTree_rec(Right, Depth + 1, UserTreeIdx);
-        return;
+      // Reorder operands if reordering would enable vectorization.
+      if (isa<BinaryOperator>(VL0)) {
+        ValueList Left, Right;
+        reorderAltShuffleOperands(S.Opcode, S.AltOpcode, VL, Left, Right);
+        buildTree_rec(Left, Depth + 1, UserTreeIdx);
+        buildTree_rec(Right, Depth + 1, UserTreeIdx);
+        return;
       }
 
       for (unsigned i = 0, e = VL0->getNumOperands(); i < e; ++i) {
         ValueList Operands;
         // Prepare the operand vector.
         for (Value *j : VL)
           Operands.push_back(cast<Instruction>(j)->getOperand(i));
 
if (getSameOpcode(VL).Opcode == Instruction::ExtractElement &&
                                             IO->getZExtValue());
           }
         }
         return ReuseShuffleCost + Cost;
       }
     }
     return ReuseShuffleCost + getGatherCost(VL);
   }
-  InstructionsState S = getSameOpcode(VL);
-  assert(S.Opcode && allSameType(VL) && allSameBlock(VL) && "Invalid VL");
-  Instruction *VL0 = cast<Instruction>(S.OpValue);
-  unsigned ShuffleOrOp = S.IsAltShuffle ?
-               (unsigned) Instruction::ShuffleVector : S.Opcode;
-  switch (ShuffleOrOp) {
-    case Instruction::PHI:
+  InstructionsState S = getSameOpcode(VL);
+  assert(S.Opcode && allSameType(VL) && allSameBlock(VL) && "Invalid VL");
+  Instruction *VL0 = cast<Instruction>(S.OpValue);
+  unsigned ShuffleOrOp = S.isAltShuffle() ?
+               (unsigned) Instruction::ShuffleVector : S.Opcode;
+  switch (ShuffleOrOp) {
+    case Instruction::PHI:
       return 0;
 
     case Instruction::ExtractValue:
     case Instruction::ExtractElement:
       if (NeedToShuffleReuses) {
         unsigned Idx = 0;
         for (unsigned I : E->ReuseShuffleIndices) {
           if (ShuffleOrOp == Instruction::ExtractElement) {
if (NeedToShuffleReuses) {
       V = Builder.CreateShuffleVector(V, UndefValue::get(VecTy),
                                       E->ReuseShuffleIndices, "shuffle");
       if (auto *I = dyn_cast<Instruction>(V)) {
         GatherSeq.insert(I);
         CSEBlocks.insert(I->getParent());
       }
     }
     E->VectorizedValue = V;
-    return V;
-  }
-
-  unsigned ShuffleOrOp = S.IsAltShuffle ?
-           (unsigned) Instruction::ShuffleVector : S.Opcode;
-  switch (ShuffleOrOp) {
-    case Instruction::PHI: {
+    return V;
+  }
+
+  unsigned ShuffleOrOp = S.isAltShuffle() ?
+           (unsigned) Instruction::ShuffleVector : S.Opcode;
+  switch (ShuffleOrOp) {
+    case Instruction::PHI: {
       PHINode *PH = dyn_cast<PHINode>(VL0);
       Builder.SetInsertPoint(PH->getParent()->getFirstNonPHI());
       Builder.SetCurrentDebugLocation(PH->getDebugLoc());
       PHINode *NewPhi = Builder.CreatePHI(VecTy, PH->getNumIncomingValues());
       Value *V = NewPhi;
       if (NeedToShuffleReuses) {
         V = Builder.CreateShuffleVector(V, UndefValue::get(VecTy),
                                         E->ReuseShuffleIndices, "shuffle");
case Instruction::Call: {
         V = Builder.CreateShuffleVector(V, UndefValue::get(VecTy),
                                         E->ReuseShuffleIndices, "shuffle");
       }
       E->VectorizedValue = V;
       ++NumVectorInstructions;
       return V;
     }
     case Instruction::ShuffleVector: {
-      ValueList LHSVL, RHSVL;
-      assert(Instruction::isBinaryOp(S.Opcode) &&
-             "Invalid Shuffle Vector Operand");
-      unsigned AltOpcode = getAltOpcode(S.Opcode);
-      reorderAltShuffleOperands(S.Opcode, AltOpcode, E->Scalars, LHSVL, RHSVL);
-      setInsertPointAfterBundle(E->Scalars, VL0);
-
-      Value *LHS = vectorizeTree(LHSVL);
+      ValueList LHSVL, RHSVL;
+      assert(Instruction::isBinaryOp(S.Opcode) &&
+             "Invalid Shuffle Vector Operand");
+      reorderAltShuffleOperands(S.Opcode, S.AltOpcode, E->Scalars, LHSVL,
+                                RHSVL);
+      setInsertPointAfterBundle(E->Scalars, VL0);
+
+      Value *LHS = vectorizeTree(LHSVL);
       Value *RHS = vectorizeTree(RHSVL);
 
       if (E->VectorizedValue) {
         LLVM_DEBUG(dbgs() << "SLP: Diamond merged for " << *VL0 << ".\n");
         return E->VectorizedValue;
       }
 
       // Create a vector of LHS op1 RHS
       Value *V0 = Builder.CreateBinOp(
           static_cast<Instruction::BinaryOps>(S.Opcode), LHS, RHS);
-
-      // Create a vector of LHS op2 RHS
-      Value *V1 = Builder.CreateBinOp(
-          static_cast<Instruction::BinaryOps>(AltOpcode), LHS, RHS);
-
-      // Create shuffle to take alternate operations from the vector.
-      // Also, gather up odd and even scalar ops to propagate IR flags to
+
+      // Create a vector of LHS op2 RHS
+      Value *V1 = Builder.CreateBinOp(
+          static_cast<Instruction::BinaryOps>(S.AltOpcode), LHS, RHS);
+
+      // Create shuffle to take alternate operations from the vector.
+      // Also, gather up odd and even scalar ops to propagate IR flags to
       // each vector operation.
       ValueList OpScalars, AltScalars;
       unsigned e = E->Scalars.size();
       SmallVector<Constant *, 8> Mask(e);
       for (unsigned i = 0; i < e; ++i) {
         auto *OpInst = cast<Instruction>(E->Scalars[i]);
         unsigned InstOpcode = OpInst->getOpcode();
-        assert(sameOpcodeOrAlt(S.Opcode, AltOpcode, InstOpcode) &&
+        assert(sameOpcodeOrAlt(S.Opcode, S.AltOpcode, InstOpcode) &&
                "Unexpected main/alternate opcode");
-        if (InstOpcode == AltOpcode) {
+        if (InstOpcode == S.AltOpcode) {
           Mask[i] = Builder.getInt32(e + i);
           AltScalars.push_back(E->Scalars[i]);
         } else {
           Mask[i] = Builder.getInt32(i);
           OpScalars.push_back(E->Scalars[i]);
         }
       }