[VPlan][WIP] VMULH via VPRecipeBase

[dmgreen]

Summary

This is not ready for review yet.

It is meant mostly as an illustration to show how combining and replacing VPlan recipes might work. It sits on top of the cost model changes from D89322 as we need a way to cost the instruction in the vplan, not the instructions in the original loop.

The patch:

• Adds a adjustVPlanForVectorPatterns to transform VPlans to other vector patterns.
• Adds tryCombineToMulh to match trunc(lsr(mul(ext, ext)), BW)) and convert it to a VPInstruction::vmulh node in the vplan graph.
• It adds some simple vp_ pattern matchers.
• Adds simple cost modelling for the new mulh vector instructions.

It passes the llvm lit tests, but I have run no further testing on it.

[dmgreen]

I rebase and have take out some of the VPValue/VPRecipe changes, leaving the basic idea for vmulh codegen here. Still not intended for review as many details have not been filled out.

llvm/lib/Transforms/Vectorize/LoopVectorizationPlanner.h

private:
   void buildVPlansWithVPRecipes(unsigned MinVF, unsigned MaxVF);
 
   /// Adjust the recipes for any inloop reductions. The chain of instructions
   /// leading from the loop exit instr to the phi need to be converted to
   /// reductions, with one operand being vector and the other being the scalar
   /// reduction chain.
   void adjustRecipesForInLoopReductions(VPlanPtr &Plan,
                                         VPRecipeBuilder &RecipeBuilder);
+  bool adjustVPlanForVectorPatterns(VPlanPtr &Plan,
+                                    VPRecipeBuilder &RecipeBuilder);
 };
 
 } // namespace llvm
 
 #endif // LLVM_TRANSFORMS_VECTORIZE_LOOPVECTORIZATIONPLANNER_H

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Transforms/Vectorize/LoopVectorize.h"
 #include "LoopVectorizationPlanner.h"
 #include "VPRecipeBuilder.h"
 #include "VPlan.h"
 #include "VPlanHCFGBuilder.h"
+#include "VPlanPatternMatch.h"
 #include "VPlanPredicator.h"
 #include "VPlanTransforms.h"
 #include "llvm/ADT/APInt.h"
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/DenseMapInfo.h"
 #include "llvm/ADT/Hashing.h"
 #include "llvm/ADT/MapVector.h"
for (unsigned i = 0; i < IG->getFactor(); ++i)
           Plan->removeVPValueFor(Member);
           OriginalV->replaceAllUsesWith(Plan->getOrAddVPValue(Member));
         }
         RecipeBuilder.getRecipe(Member)->eraseFromParent();
       }
   }
 
   // Adjust the recipes for any inloop reductions.
-  if (Range.Start > 1)
+  if (Range.Start > 1) {
     adjustRecipesForInLoopReductions(Plan, RecipeBuilder);
+    adjustVPlanForVectorPatterns(Plan, RecipeBuilder);
+  }
 
   // Finally, if tail is folded by masking, introduce selects between the phi
   // and the live-out instruction of each reduction, at the end of the latch.
   if (CM.foldTailByMasking() && !Legal->getReductionVars().empty()) {
     Builder.setInsertPoint(VPBB);
     auto *Cond = RecipeBuilder.createBlockInMask(OrigLoop->getHeader(), Plan);
     for (auto &Reduction : Legal->getReductionVars()) {
       if (CM.isInLoopReduction(Reduction.first))
for (Instruction *R : ReductionOperations) {
                "Expected to replace a VPWidenSC");
         CompareRecipe->eraseFromParent();
       }
       Chain = R;
     }
   }
 }
 
+static bool tryCombineToMulh(VPBasicBlock::reverse_iterator &It, VPlanPtr &Plan,
+                             VPRecipeBuilder &RecipeBuilder) {
+  VPWidenRecipe *RV = dyn_cast<VPWidenRecipe>(&*It);
+  if (!RV)
+    return false;
+
+  // trunc(lsr(mul(ext, ext)), BW)) -> mulhs/mulhu
+  Type *Ty = RV->getType();
+  unsigned BW = Ty->getScalarSizeInBits();
+
+  VPValue *Mul;
+  // TODOD: Start at shift. create ext(trunc())
+  // TODOD: One use checks?
+  if (!match(RV, vp_Trunc(vp_LShr(vp_Value(Mul), vp_SpecificInt(BW)))))
+    return false;
+
+  VPValue *A, *B;
+  unsigned Opcode = 0;
+  if (match(Mul, vp_Mul(vp_SExt(vp_Value(A)), vp_SExt(vp_Value(B)))))
+    Opcode = VPInstruction::Mulhs;
+  else if (match(Mul, vp_Mul(vp_ZExt(vp_Value(A)), vp_ZExt(vp_Value(B)))))
+    Opcode = VPInstruction::Mulhu;
+  else
+    return false;
+
+  unsigned MulBW = Mul->getType()->getScalarSizeInBits();
+  if (MulBW > BW * 2)
+    return false;
+
+  if (A->getType() != Ty || B->getType() != Ty) // TODOD: Generalize
+    return false;
+
+  auto *Mulh = new VPInstruction(Opcode, Ty, {A, B});
+  RV->getParent()->insert(Mulh, RV->getIterator());
+  RV->replaceAllUsesWith(Mulh);
+  RV->recursivelyDeleteUnusedRecipes();
+  It = Mulh->getReverseIterator();
+  return true;
+}
+
+bool LoopVectorizationPlanner::adjustVPlanForVectorPatterns(
+    VPlanPtr &Plan, VPRecipeBuilder &RecipeBuilder) {
+  LLVM_DEBUG(dbgs() << "Current plan: " << *Plan << "\n");
+  bool Changed = false;
+  for (VPBlockBase *Block : depth_first(Plan->getEntry())) {
+    if (auto *BB = dyn_cast<VPBasicBlock>(Block)) {
+      for (VPBasicBlock::reverse_iterator It = BB->rbegin(), E = BB->rend();
+           It != E; ++It) {
+        if (true /*TODOD: TTI->hasVectorPattern(Mulh)*/)
+          Changed |= tryCombineToMulh(It, Plan, RecipeBuilder);
+      }
+    }
+  }
+
+  return Changed;
+}
+
 Value* LoopVectorizationPlanner::VPCallbackILV::
 getOrCreateVectorValues(Value *V, unsigned Part) {
       return ILV.getOrCreateVectorValue(V, Part);
 }
 
 Value *LoopVectorizationPlanner::VPCallbackILV::getOrCreateScalarValue(
     Value *V, const VPIteration &Instance) {
   return ILV.getOrCreateScalarValue(V, Instance);
VectorizationCostTy VPInstruction::cost(ElementCount VF, VPCostContext &Ctx) {
   case VPInstruction::ActiveLaneMask: {
     ArrayRef<Type *> Ops;
     IntrinsicCostAttributes CostAttrs(Intrinsic::get_active_lane_mask,
                                       getVectorType(VF), Ops);
     return {Ctx.CM.TTI.getIntrinsicInstrCost(
                 CostAttrs, TargetTransformInfo::TCK_RecipThroughput),
             false};
   }
+  case VPInstruction::Mulhs:
+  case VPInstruction::Mulhu: {
+    // TODOD: return TTI.getVectorInstrCost(getOpcode(), getVectorType(VF));
+    return {1, false};
+  }
   default:
     llvm_unreachable("Unsupported opcode for VPInstruction::cost");
   }
 }
 
 // Determine how to lower the scalar epilogue, which depends on 1) optimising
 // for minimum code-size, 2) predicate compiler options, 3) loop hints forcing
 // predication, and 4) a TTI hook that analyses whether the loop is suitable

llvm/lib/Transforms/Vectorize/VPlan.h

public:
   /// Returns the underlying instruction if this recipe has one or nullptr
   /// otherwise.
   Instruction *getUnderlyingInstr() {
     return cast_or_null<Instruction>(getUnderlyingValue());
   }
   const Instruction *getUnderlyingInstr() const {
     return cast_or_null<Instruction>(getUnderlyingValue());
   }
+
+  void recursivelyDeleteUnusedRecipes();
+
+  static inline bool classof(const VPValue *V) {
+    return V->getVPValueID() >= VPBlendSC;
+  }
 };
 
 /// This is a concrete Recipe that models a single VPlan-level instruction.
 /// While as any Recipe it may generate a sequence of IR instructions when
 /// executed, these instructions would always form a single-def expression as
 /// the VPInstruction is also a single def-use vertex.
 class VPInstruction : public VPRecipeBase {
   friend class VPlanSlp;
 
 public:
   /// VPlan opcodes, extending LLVM IR with idiomatics instructions.
   enum {
     Not = Instruction::OtherOpsEnd + 1,
     ICmpULE,
     SLPLoad,
     SLPStore,
     ActiveLaneMask,
+    Mulhs,
+    Mulhu,
   };
 
 private:
   typedef unsigned char OpcodeTy;
   OpcodeTy Opcode;
 
   Type *ScalarType;
 
public:
   /// Produce widened copies of all Ingredients.
   void execute(VPTransformState &State) override;
 
   VectorizationCostTy cost(ElementCount VF, VPCostContext &Ctx) override;
 
   /// Print the recipe.
   void print(raw_ostream &O, const Twine &Indent,
              VPSlotTracker &SlotTracker) const override;
+
+  unsigned getOpcode() const { return getUnderlyingInstr()->getOpcode(); }
 };
 
 /// A recipe for widening Call instructions.
 class VPWidenCallRecipe : public VPRecipeBase {
 public:
   template <typename IterT>
   VPWidenCallRecipe(CallInst &I, iterator_range<IterT> CallArguments)
       : VPRecipeBase(VPWidenCallSC, &I, CallArguments) {}

llvm/lib/Transforms/Vectorize/VPlan.cpp

void VPRecipeBase::removeFromParent() {
   Parent = nullptr;
 }
 
 iplist<VPRecipeBase>::iterator VPRecipeBase::eraseFromParent() {
   assert(getParent() && "Recipe not in any VPBasicBlock");
   return getParent()->getRecipeList().erase(getIterator());
 }
 
+void VPRecipeBase::recursivelyDeleteUnusedRecipes() {
+  if (getNumUsers() == 0 /* && isSafeToRemove()*/) {
+    for (auto *Op : operands()) {
+      Op->removeUser(*this);
+      if (VPRecipeBase *R = dyn_cast<VPRecipeBase>(Op))
+        R->recursivelyDeleteUnusedRecipes();
+    }
+    clearOperands();
+    eraseFromParent();
+  }
+}
+
 void VPRecipeBase::moveAfter(VPRecipeBase *InsertPos) {
   removeFromParent();
   insertAfter(InsertPos);
 }
 
 void VPInstruction::generateInstruction(VPTransformState &State,
                                         unsigned Part) {
   IRBuilder<> &Builder = State.Builder;
case VPInstruction::ActiveLaneMask: {
     auto *Int1Ty = Type::getInt1Ty(Builder.getContext());
     auto *PredTy = FixedVectorType::get(Int1Ty, State.VF.getKnownMinValue());
     Instruction *Call = Builder.CreateIntrinsic(
         Intrinsic::get_active_lane_mask, {PredTy, ScalarTC->getType()},
         {VIVElem0, ScalarTC}, nullptr, "active.lane.mask");
     State.set(this, Call, Part);
     break;
   }
+  case VPInstruction::Mulhs:
+  case VPInstruction::Mulhu: {
+    Value *A = State.get(getOperand(0), Part);
+    Value *B = State.get(getOperand(1), Part);
+
+    auto Ty = cast<VectorType>(A->getType());
+    unsigned BW = Ty->getScalarSizeInBits();
+    auto *WidenTy = VectorType::getExtendedElementVectorType(Ty);
+
+    auto *ExtA = getOpcode() == VPInstruction::Mulhs
+                     ? Builder.CreateSExt(A, WidenTy)
+                     : Builder.CreateZExt(A, WidenTy);
+    auto *ExtB = getOpcode() == VPInstruction::Mulhs
+                     ? Builder.CreateSExt(B, WidenTy)
+                     : Builder.CreateZExt(B, WidenTy);
+    auto *Mul = Builder.CreateMul(ExtA, ExtB);
+    auto *Shift = Builder.CreateLShr(
+        Mul, ConstantDataVector::getSplat(
+                 State.VF.getKnownMinValue(),
+                 ConstantInt::get(WidenTy->getElementType(), BW)));
+    auto *Trunc = Builder.CreateTrunc(Shift, Ty);
+
+    State.set(this, Trunc, Part);
+    break;
+  }
   default:
     llvm_unreachable("Unsupported opcode for instruction");
   }
 }
 
 void VPInstruction::execute(VPTransformState &State) {
   assert(!State.Instance && "VPInstruction executing an Instance");
   for (unsigned Part = 0; Part < State.UF; ++Part)
case VPInstruction::SLPLoad:
     O << "combined load";
     break;
   case VPInstruction::SLPStore:
     O << "combined store";
     break;
   case VPInstruction::ActiveLaneMask:
     O << "active lane mask";
     break;
+  case VPInstruction::Mulhs:
+    O << "mulhs";
+    break;
+  case VPInstruction::Mulhu:
+    O << "mulhu";
+    break;
 
   default:
     O << Instruction::getOpcodeName(getOpcode());
   }
 
   for (const VPValue *Operand : operands()) {
     O << " ";
     Operand->printAsOperand(O, SlotTracker);

llvm/lib/Transforms/Vectorize/VPlanPatternMatch.h

+//===- VPlanPatternMatch.h - Pattern matchers for vplan recipes -*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+/// \file
+/// This file contains a number of vplan pattern matchers, similar to and
+/// working on top of the the generic IR pattern matches from IR/PatternMatch.h.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_TRANSFORMS_VECTORIZE_VPLANPATTERNMATCHER_H
+#define LLVM_TRANSFORMS_VECTORIZE_VPLANPATTERNMATCHER_H
+
+#include "VPlan.h"
+#include "VPlanValue.h"
+#include "llvm/IR/Instruction.h"
+#include <llvm/IR/PatternMatch.h>
+
+using namespace llvm;
+using namespace llvm::PatternMatch;
+
+template <typename LHS_t, typename RHS_t, unsigned Opcode>
+struct VPBinaryOp_match {
+  LHS_t L;
+  RHS_t R;
+
+  VPBinaryOp_match(const LHS_t &LHS, const RHS_t &RHS) : L(LHS), R(RHS) {}
+
+  template <typename OpTy> bool match(OpTy *V) {
+    const VPWidenRecipe *VW = dyn_cast<VPWidenRecipe>(V);
+    if (VW && VW->getOpcode() == Opcode)
+      return L.match(VW->getOperand(0)) && R.match(VW->getOperand(1));
+    // TODOD: VPInstruction?
+    return false;
+  }
+};
+template <typename LHS, typename RHS>
+inline VPBinaryOp_match<LHS, RHS, Instruction::Mul> vp_Mul(const LHS &L,
+                                                           const RHS &R) {
+  return VPBinaryOp_match<LHS, RHS, Instruction::Mul>(L, R);
+}
+template <typename LHS, typename RHS>
+inline VPBinaryOp_match<LHS, RHS, Instruction::LShr> vp_LShr(const LHS &L,
+                                                             const RHS &R) {
+  return VPBinaryOp_match<LHS, RHS, Instruction::LShr>(L, R);
+}
+
+template <typename LHS_t, unsigned Opcode> struct VPUnaryOp_match {
+  LHS_t L;
+
+  VPUnaryOp_match(const LHS_t &LHS) : L(LHS) {}
+
+  template <typename OpTy> bool match(OpTy *V) {
+    const VPWidenRecipe *VW = dyn_cast<VPWidenRecipe>(V);
+    if (VW && VW->getOpcode() == Opcode)
+      return L.match(VW->getOperand(0));
+    return false;
+  }
+};
+template <typename LHS>
+inline VPUnaryOp_match<LHS, Instruction::Trunc> vp_Trunc(const LHS &L) {
+  return VPUnaryOp_match<LHS, Instruction::Trunc>(L);
+}
+template <typename LHS>
+inline VPUnaryOp_match<LHS, Instruction::SExt> vp_SExt(const LHS &L) {
+  return VPUnaryOp_match<LHS, Instruction::SExt>(L);
+}
+template <typename LHS>
+inline VPUnaryOp_match<LHS, Instruction::ZExt> vp_ZExt(const LHS &L) {
+  return VPUnaryOp_match<LHS, Instruction::ZExt>(L);
+}
+
+inline bind_ty<VPValue> vp_Value(VPValue *&V) { return V; }
+inline bind_ty<const VPValue> vp_Value(const VPValue *&V) { return V; }
+
+struct VPspecific_intval {
+  APInt Val;
+
+  VPspecific_intval(APInt V) : Val(std::move(V)) {}
+
+  template <typename ITy> bool match(ITy *V) {
+    const auto *C = V->getConstantValue();
+    if (const auto *CI = dyn_cast_or_null<ConstantInt>(C))
+      return CI && APInt::isSameValue(CI->getValue(), Val);
+    return false;
+  }
+};
+inline VPspecific_intval vp_SpecificInt(uint64_t V) {
+  return VPspecific_intval(APInt(64, V));
+}
+
+#endif // LLVM_TRANSFORMS_VECTORIZE_VPLANPATTERNMATCHER_H

llvm/lib/Transforms/Vectorize/VPlanValue.h

public:
   VPValue(const VPValue &) = delete;
   VPValue &operator=(const VPValue &) = delete;
 
   /// \return an ID for the concrete type of this object.
   /// This is used to implement the classof checks. This should not be used
   /// for any other purpose, as the values may change as LLVM evolves.
   unsigned getVPValueID() const { return SubclassID; }
 
+  // FIXME: We need to do something about types.
+  Type *getType() {
+    if (UnderlyingVal)
+      return UnderlyingVal->getType();
+    return nullptr;
+  }
+
   void printAsOperand(raw_ostream &OS, VPSlotTracker &Tracker) const;
   void print(raw_ostream &OS, VPSlotTracker &Tracker) const;
 
   /// Dump the value to stderr (for debugging).
   void dump() const;
 
   unsigned getNumUsers() const { return Users.size(); }
   void addUser(VPUser &User) { Users.push_back(&User); }
bool hasMoreThanOneUniqueUser() {
     // Check if all users match the first user.
     auto Current = std::next(user_begin());
     while (Current != user_end() && *user_begin() == *Current)
       Current++;
     return Current != user_end();
   }
 
   void replaceAllUsesWith(VPValue *New);
+
+  const Constant *getConstantValue() const {
+    if (SubclassID == VPValueSC)
+      return dyn_cast<ConstantInt>(getUnderlyingValue());
+    return nullptr;
+  }
 };
 
 typedef DenseMap<Value *, VPValue *> Value2VPValueTy;
 typedef DenseMap<VPValue *, Value *> VPValue2ValueTy;
 
 raw_ostream &operator<<(raw_ostream &OS, const VPValue &V);
 
 /// This class augments VPValue with operands which provide the inverse def-use
 /// edges from VPValue's users to their defs.
 class VPUser : public VPValue {
   SmallVector<VPValue *, 2> Operands;
 
+protected:
+  void clearOperands() { Operands.clear(); }
+
 public:
   VPUser(const unsigned char SC, Value *UV = nullptr) : VPValue(SC, UV) {}
   VPUser(const unsigned char SC, Value *UV, ArrayRef<VPValue *> Operands)
       : VPValue(SC, UV) {
     for (VPValue *Operand : Operands)
       addOperand(Operand);
   }
   VPUser(const unsigned char SC, Value *UV,