[VPlan][WIP] VMULH via VPRecipeBase (using VPDef).

[fhahn]

Summary

Based on D88152, with small adjustments to use VPDef.

llvm/lib/Transforms/Vectorize/LoopVectorizationPlanner.h

void buildVPlansWithVPRecipes(ElementCount MinVF, ElementCount MaxVF,
                                 VPlan &OriginalPlan);
 
   /// 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 (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, {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);

llvm/lib/Transforms/Vectorize/VPlan.h

if (auto *VPV = toVPValue())
       return cast_or_null<Instruction>(VPV->getUnderlyingValue());
     return nullptr;
   }
   const Instruction *getUnderlyingInstr() const {
     if (auto *VPV = toVPValue())
       return cast_or_null<Instruction>(VPV->getUnderlyingValue());
     return nullptr;
   }
+
+  void recursivelyDeleteUnusedRecipes();
 };
 
 inline bool VPUser::classof(const VPDef *Recipe) {
   return Recipe->getVPDefID() == VPRecipeBase::VPInstructionSC ||
          Recipe->getVPDefID() == VPRecipeBase::VPWidenSC ||
          Recipe->getVPDefID() == VPRecipeBase::VPWidenCallSC ||
          Recipe->getVPDefID() == VPRecipeBase::VPWidenSelectSC ||
          Recipe->getVPDefID() == VPRecipeBase::VPWidenGEPSC ||

 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;
 
   /// Utility method serving execute(): generates a single instance of the
   /// modeled instruction.
public:
   }
 
   /// Produce widened copies of all Ingredients.
   void execute(VPTransformState &State) 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 VPValue {
 
 public:
   template <typename IterT>
   VPWidenCallRecipe(CallInst &I, iterator_range<IterT> CallArguments)

llvm/lib/Transforms/Vectorize/VPlan.cpp

iplist<VPRecipeBase>::iterator VPRecipeBase::eraseFromParent() {
   return getParent()->getRecipeList().erase(getIterator());
 }
 
 void VPRecipeBase::moveAfter(VPRecipeBase *InsertPos) {
   removeFromParent();
   insertAfter(InsertPos);
 }
 
+void VPRecipeBase::recursivelyDeleteUnusedRecipes() {
+  if (all_of(defined_values(), [](VPValue *Def) {
+        return Def->getNumUsers() == 0;
+      }) /* && isSafeToRemove()*/) {
+    for (auto *Op : operands()) {
+      Op->removeUser(*this);
+      if (VPRecipeBase *R = dyn_cast<VPRecipeBase>(Op->getDef()))
+        R->recursivelyDeleteUnusedRecipes();
+    }
+    eraseFromParent();
+  }
+}
+
 void VPInstruction::generateInstruction(VPTransformState &State,
                                         unsigned Part) {
   IRBuilder<> &Builder = State.Builder;
 
   if (Instruction::isBinaryOp(getOpcode())) {
     Value *A = State.get(getOperand(0), Part);
     Value *B = State.get(getOperand(1), Part);
     Value *V = Builder.CreateBinOp((Instruction::BinaryOps)getOpcode(), A, B);

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

bool hasMoreThanOneUniqueUser() {
     while (Current != user_end() && *user_begin() == *Current)
       Current++;
     return Current != user_end();
   }
 
   void replaceAllUsesWith(VPValue *New);
 
   VPDef *getDef() { return Def; }
+
+  // FIXME: We need to do something about types.
+  Type *getType() {
+    if (UnderlyingVal)
+      return UnderlyingVal->getType();
+    return nullptr;
+  }
+
+  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