brintos / llvm-project-archived public Read only

1//===- VPlanRecipes.cpp - Implementations for VPlan recipes ---------------===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8///9/// \file10/// This file contains implementations for different VPlan recipes.11///12//===----------------------------------------------------------------------===//13 14#include "LoopVectorizationPlanner.h"15#include "VPlan.h"16#include "VPlanAnalysis.h"17#include "VPlanHelpers.h"18#include "VPlanPatternMatch.h"19#include "VPlanUtils.h"20#include "llvm/ADT/STLExtras.h"21#include "llvm/ADT/SmallVector.h"22#include "llvm/ADT/Twine.h"23#include "llvm/Analysis/AssumptionCache.h"24#include "llvm/Analysis/IVDescriptors.h"25#include "llvm/Analysis/LoopInfo.h"26#include "llvm/IR/BasicBlock.h"27#include "llvm/IR/IRBuilder.h"28#include "llvm/IR/Instruction.h"29#include "llvm/IR/Instructions.h"30#include "llvm/IR/Intrinsics.h"31#include "llvm/IR/Type.h"32#include "llvm/IR/Value.h"33#include "llvm/Support/Casting.h"34#include "llvm/Support/CommandLine.h"35#include "llvm/Support/Debug.h"36#include "llvm/Support/raw_ostream.h"37#include "llvm/Transforms/Utils/BasicBlockUtils.h"38#include "llvm/Transforms/Utils/LoopUtils.h"39#include <cassert>40 41using namespace llvm;42using namespace llvm::VPlanPatternMatch;43 44using VectorParts = SmallVector<Value *, 2>;45 46#define LV_NAME "loop-vectorize"47#define DEBUG_TYPE LV_NAME48 49bool VPRecipeBase::mayWriteToMemory() const {50  switch (getVPDefID()) {51  case VPExpressionSC:52    return cast<VPExpressionRecipe>(this)->mayReadOrWriteMemory();53  case VPInstructionSC: {54    auto *VPI = cast<VPInstruction>(this);55    // Loads read from memory but don't write to memory.56    if (VPI->getOpcode() == Instruction::Load)57      return false;58    return VPI->opcodeMayReadOrWriteFromMemory();59  }60  case VPInterleaveEVLSC:61  case VPInterleaveSC:62    return cast<VPInterleaveBase>(this)->getNumStoreOperands() > 0;63  case VPWidenStoreEVLSC:64  case VPWidenStoreSC:65    return true;66  case VPReplicateSC:67    return cast<Instruction>(getVPSingleValue()->getUnderlyingValue())68        ->mayWriteToMemory();69  case VPWidenCallSC:70    return !cast<VPWidenCallRecipe>(this)71                ->getCalledScalarFunction()72                ->onlyReadsMemory();73  case VPWidenIntrinsicSC:74    return cast<VPWidenIntrinsicRecipe>(this)->mayWriteToMemory();75  case VPCanonicalIVPHISC:76  case VPBranchOnMaskSC:77  case VPDerivedIVSC:78  case VPFirstOrderRecurrencePHISC:79  case VPReductionPHISC:80  case VPScalarIVStepsSC:81  case VPPredInstPHISC:82    return false;83  case VPBlendSC:84  case VPReductionEVLSC:85  case VPReductionSC:86  case VPVectorPointerSC:87  case VPWidenCanonicalIVSC:88  case VPWidenCastSC:89  case VPWidenGEPSC:90  case VPWidenIntOrFpInductionSC:91  case VPWidenLoadEVLSC:92  case VPWidenLoadSC:93  case VPWidenPHISC:94  case VPWidenPointerInductionSC:95  case VPWidenSC:96  case VPWidenSelectSC: {97    const Instruction *I =98        dyn_cast_or_null<Instruction>(getVPSingleValue()->getUnderlyingValue());99    (void)I;100    assert((!I || !I->mayWriteToMemory()) &&101           "underlying instruction may write to memory");102    return false;103  }104  default:105    return true;106  }107}108 109bool VPRecipeBase::mayReadFromMemory() const {110  switch (getVPDefID()) {111  case VPExpressionSC:112    return cast<VPExpressionRecipe>(this)->mayReadOrWriteMemory();113  case VPInstructionSC:114    return cast<VPInstruction>(this)->opcodeMayReadOrWriteFromMemory();115  case VPWidenLoadEVLSC:116  case VPWidenLoadSC:117    return true;118  case VPReplicateSC:119    return cast<Instruction>(getVPSingleValue()->getUnderlyingValue())120        ->mayReadFromMemory();121  case VPWidenCallSC:122    return !cast<VPWidenCallRecipe>(this)123                ->getCalledScalarFunction()124                ->onlyWritesMemory();125  case VPWidenIntrinsicSC:126    return cast<VPWidenIntrinsicRecipe>(this)->mayReadFromMemory();127  case VPBranchOnMaskSC:128  case VPDerivedIVSC:129  case VPFirstOrderRecurrencePHISC:130  case VPPredInstPHISC:131  case VPScalarIVStepsSC:132  case VPWidenStoreEVLSC:133  case VPWidenStoreSC:134    return false;135  case VPBlendSC:136  case VPReductionEVLSC:137  case VPReductionSC:138  case VPVectorPointerSC:139  case VPWidenCanonicalIVSC:140  case VPWidenCastSC:141  case VPWidenGEPSC:142  case VPWidenIntOrFpInductionSC:143  case VPWidenPHISC:144  case VPWidenPointerInductionSC:145  case VPWidenSC:146  case VPWidenSelectSC: {147    const Instruction *I =148        dyn_cast_or_null<Instruction>(getVPSingleValue()->getUnderlyingValue());149    (void)I;150    assert((!I || !I->mayReadFromMemory()) &&151           "underlying instruction may read from memory");152    return false;153  }154  default:155    // FIXME: Return false if the recipe represents an interleaved store.156    return true;157  }158}159 160bool VPRecipeBase::mayHaveSideEffects() const {161  switch (getVPDefID()) {162  case VPExpressionSC:163    return cast<VPExpressionRecipe>(this)->mayHaveSideEffects();164  case VPDerivedIVSC:165  case VPFirstOrderRecurrencePHISC:166  case VPPredInstPHISC:167  case VPVectorEndPointerSC:168    return false;169  case VPInstructionSC: {170    auto *VPI = cast<VPInstruction>(this);171    return mayWriteToMemory() ||172           VPI->getOpcode() == VPInstruction::BranchOnCount ||173           VPI->getOpcode() == VPInstruction::BranchOnCond;174  }175  case VPWidenCallSC: {176    Function *Fn = cast<VPWidenCallRecipe>(this)->getCalledScalarFunction();177    return mayWriteToMemory() || !Fn->doesNotThrow() || !Fn->willReturn();178  }179  case VPWidenIntrinsicSC:180    return cast<VPWidenIntrinsicRecipe>(this)->mayHaveSideEffects();181  case VPBlendSC:182  case VPReductionEVLSC:183  case VPReductionSC:184  case VPScalarIVStepsSC:185  case VPVectorPointerSC:186  case VPWidenCanonicalIVSC:187  case VPWidenCastSC:188  case VPWidenGEPSC:189  case VPWidenIntOrFpInductionSC:190  case VPWidenPHISC:191  case VPWidenPointerInductionSC:192  case VPWidenSC:193  case VPWidenSelectSC: {194    const Instruction *I =195        dyn_cast_or_null<Instruction>(getVPSingleValue()->getUnderlyingValue());196    (void)I;197    assert((!I || !I->mayHaveSideEffects()) &&198           "underlying instruction has side-effects");199    return false;200  }201  case VPInterleaveEVLSC:202  case VPInterleaveSC:203    return mayWriteToMemory();204  case VPWidenLoadEVLSC:205  case VPWidenLoadSC:206  case VPWidenStoreEVLSC:207  case VPWidenStoreSC:208    assert(209        cast<VPWidenMemoryRecipe>(this)->getIngredient().mayHaveSideEffects() ==210            mayWriteToMemory() &&211        "mayHaveSideffects result for ingredient differs from this "212        "implementation");213    return mayWriteToMemory();214  case VPReplicateSC: {215    auto *R = cast<VPReplicateRecipe>(this);216    return R->getUnderlyingInstr()->mayHaveSideEffects();217  }218  default:219    return true;220  }221}222 223void VPRecipeBase::insertBefore(VPRecipeBase *InsertPos) {224  assert(!Parent && "Recipe already in some VPBasicBlock");225  assert(InsertPos->getParent() &&226         "Insertion position not in any VPBasicBlock");227  InsertPos->getParent()->insert(this, InsertPos->getIterator());228}229 230void VPRecipeBase::insertBefore(VPBasicBlock &BB,231                                iplist<VPRecipeBase>::iterator I) {232  assert(!Parent && "Recipe already in some VPBasicBlock");233  assert(I == BB.end() || I->getParent() == &BB);234  BB.insert(this, I);235}236 237void VPRecipeBase::insertAfter(VPRecipeBase *InsertPos) {238  assert(!Parent && "Recipe already in some VPBasicBlock");239  assert(InsertPos->getParent() &&240         "Insertion position not in any VPBasicBlock");241  InsertPos->getParent()->insert(this, std::next(InsertPos->getIterator()));242}243 244void VPRecipeBase::removeFromParent() {245  assert(getParent() && "Recipe not in any VPBasicBlock");246  getParent()->getRecipeList().remove(getIterator());247  Parent = nullptr;248}249 250iplist<VPRecipeBase>::iterator VPRecipeBase::eraseFromParent() {251  assert(getParent() && "Recipe not in any VPBasicBlock");252  return getParent()->getRecipeList().erase(getIterator());253}254 255void VPRecipeBase::moveAfter(VPRecipeBase *InsertPos) {256  removeFromParent();257  insertAfter(InsertPos);258}259 260void VPRecipeBase::moveBefore(VPBasicBlock &BB,261                              iplist<VPRecipeBase>::iterator I) {262  removeFromParent();263  insertBefore(BB, I);264}265 266InstructionCost VPRecipeBase::cost(ElementCount VF, VPCostContext &Ctx) {267  // Get the underlying instruction for the recipe, if there is one. It is used268  // to269  //   * decide if cost computation should be skipped for this recipe,270  //   * apply forced target instruction cost.271  Instruction *UI = nullptr;272  if (auto *S = dyn_cast<VPSingleDefRecipe>(this))273    UI = dyn_cast_or_null<Instruction>(S->getUnderlyingValue());274  else if (auto *IG = dyn_cast<VPInterleaveBase>(this))275    UI = IG->getInsertPos();276  else if (auto *WidenMem = dyn_cast<VPWidenMemoryRecipe>(this))277    UI = &WidenMem->getIngredient();278 279  InstructionCost RecipeCost;280  if (UI && Ctx.skipCostComputation(UI, VF.isVector())) {281    RecipeCost = 0;282  } else {283    RecipeCost = computeCost(VF, Ctx);284    RecipeCost = computeCost(VF, Ctx);285    if (ForceTargetInstructionCost.getNumOccurrences() > 0 &&286        RecipeCost.isValid()) {287      if (UI)288        RecipeCost = InstructionCost(ForceTargetInstructionCost);289      else290        RecipeCost = InstructionCost(0);291    }292  }293 294  LLVM_DEBUG({295    dbgs() << "Cost of " << RecipeCost << " for VF " << VF << ": ";296    dump();297  });298  return RecipeCost;299}300 301InstructionCost VPRecipeBase::computeCost(ElementCount VF,302                                          VPCostContext &Ctx) const {303  llvm_unreachable("subclasses should implement computeCost");304}305 306bool VPRecipeBase::isPhi() const {307  return (getVPDefID() >= VPFirstPHISC && getVPDefID() <= VPLastPHISC) ||308         isa<VPPhi, VPIRPhi>(this);309}310 311bool VPRecipeBase::isScalarCast() const {312  auto *VPI = dyn_cast<VPInstruction>(this);313  return VPI && Instruction::isCast(VPI->getOpcode());314}315 316void VPIRFlags::intersectFlags(const VPIRFlags &Other) {317  assert(OpType == Other.OpType && "OpType must match");318  switch (OpType) {319  case OperationType::OverflowingBinOp:320    WrapFlags.HasNUW &= Other.WrapFlags.HasNUW;321    WrapFlags.HasNSW &= Other.WrapFlags.HasNSW;322    break;323  case OperationType::Trunc:324    TruncFlags.HasNUW &= Other.TruncFlags.HasNUW;325    TruncFlags.HasNSW &= Other.TruncFlags.HasNSW;326    break;327  case OperationType::DisjointOp:328    DisjointFlags.IsDisjoint &= Other.DisjointFlags.IsDisjoint;329    break;330  case OperationType::PossiblyExactOp:331    ExactFlags.IsExact &= Other.ExactFlags.IsExact;332    break;333  case OperationType::GEPOp:334    GEPFlags &= Other.GEPFlags;335    break;336  case OperationType::FPMathOp:337  case OperationType::FCmp:338    assert((OpType != OperationType::FCmp ||339            FCmpFlags.Pred == Other.FCmpFlags.Pred) &&340           "Cannot drop CmpPredicate");341    getFMFsRef().NoNaNs &= Other.getFMFsRef().NoNaNs;342    getFMFsRef().NoInfs &= Other.getFMFsRef().NoInfs;343    break;344  case OperationType::NonNegOp:345    NonNegFlags.NonNeg &= Other.NonNegFlags.NonNeg;346    break;347  case OperationType::Cmp:348    assert(CmpPredicate == Other.CmpPredicate && "Cannot drop CmpPredicate");349    break;350  case OperationType::Other:351    assert(AllFlags == Other.AllFlags && "Cannot drop other flags");352    break;353  }354}355 356FastMathFlags VPIRFlags::getFastMathFlags() const {357  assert((OpType == OperationType::FPMathOp || OpType == OperationType::FCmp) &&358         "recipe doesn't have fast math flags");359  const FastMathFlagsTy &F = getFMFsRef();360  FastMathFlags Res;361  Res.setAllowReassoc(F.AllowReassoc);362  Res.setNoNaNs(F.NoNaNs);363  Res.setNoInfs(F.NoInfs);364  Res.setNoSignedZeros(F.NoSignedZeros);365  Res.setAllowReciprocal(F.AllowReciprocal);366  Res.setAllowContract(F.AllowContract);367  Res.setApproxFunc(F.ApproxFunc);368  return Res;369}370 371#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)372void VPSingleDefRecipe::dump() const { VPDef::dump(); }373 374void VPRecipeBase::print(raw_ostream &O, const Twine &Indent,375                         VPSlotTracker &SlotTracker) const {376  printRecipe(O, Indent, SlotTracker);377  if (auto DL = getDebugLoc()) {378    O << ", !dbg ";379    DL.print(O);380  }381}382#endif383 384template <unsigned PartOpIdx>385VPValue *386VPUnrollPartAccessor<PartOpIdx>::getUnrollPartOperand(const VPUser &U) const {387  if (U.getNumOperands() == PartOpIdx + 1)388    return U.getOperand(PartOpIdx);389  return nullptr;390}391 392template <unsigned PartOpIdx>393unsigned VPUnrollPartAccessor<PartOpIdx>::getUnrollPart(const VPUser &U) const {394  if (auto *UnrollPartOp = getUnrollPartOperand(U))395    return cast<ConstantInt>(UnrollPartOp->getLiveInIRValue())->getZExtValue();396  return 0;397}398 399namespace llvm {400template class VPUnrollPartAccessor<1>;401template class VPUnrollPartAccessor<2>;402template class VPUnrollPartAccessor<3>;403}404 405VPInstruction::VPInstruction(unsigned Opcode, ArrayRef<VPValue *> Operands,406                             const VPIRFlags &Flags, const VPIRMetadata &MD,407                             DebugLoc DL, const Twine &Name)408    : VPRecipeWithIRFlags(VPDef::VPInstructionSC, Operands, Flags, DL),409      VPIRMetadata(MD), Opcode(Opcode), Name(Name.str()) {410  assert(flagsValidForOpcode(getOpcode()) &&411         "Set flags not supported for the provided opcode");412  assert((getNumOperandsForOpcode(Opcode) == -1u ||413          getNumOperandsForOpcode(Opcode) == getNumOperands()) &&414         "number of operands does not match opcode");415}416 417#ifndef NDEBUG418unsigned VPInstruction::getNumOperandsForOpcode(unsigned Opcode) {419  if (Instruction::isUnaryOp(Opcode) || Instruction::isCast(Opcode))420    return 1;421 422  if (Instruction::isBinaryOp(Opcode))423    return 2;424 425  switch (Opcode) {426  case VPInstruction::StepVector:427  case VPInstruction::VScale:428    return 0;429  case Instruction::Alloca:430  case Instruction::ExtractValue:431  case Instruction::Freeze:432  case Instruction::Load:433  case VPInstruction::BranchOnCond:434  case VPInstruction::Broadcast:435  case VPInstruction::BuildStructVector:436  case VPInstruction::BuildVector:437  case VPInstruction::CalculateTripCountMinusVF:438  case VPInstruction::CanonicalIVIncrementForPart:439  case VPInstruction::ExplicitVectorLength:440  case VPInstruction::ExtractLastElement:441  case VPInstruction::ExtractLastLanePerPart:442  case VPInstruction::ExtractPenultimateElement:443  case VPInstruction::Not:444  case VPInstruction::ResumeForEpilogue:445  case VPInstruction::Unpack:446    return 1;447  case Instruction::ICmp:448  case Instruction::FCmp:449  case Instruction::ExtractElement:450  case Instruction::Store:451  case VPInstruction::BranchOnCount:452  case VPInstruction::ComputeReductionResult:453  case VPInstruction::ExtractLane:454  case VPInstruction::FirstOrderRecurrenceSplice:455  case VPInstruction::LogicalAnd:456  case VPInstruction::PtrAdd:457  case VPInstruction::WidePtrAdd:458  case VPInstruction::WideIVStep:459    return 2;460  case Instruction::Select:461  case VPInstruction::ActiveLaneMask:462  case VPInstruction::ComputeAnyOfResult:463  case VPInstruction::ReductionStartVector:464    return 3;465  case VPInstruction::ComputeFindIVResult:466    return 4;467  case Instruction::Call:468  case Instruction::GetElementPtr:469  case Instruction::PHI:470  case Instruction::Switch:471  case VPInstruction::AnyOf:472  case VPInstruction::FirstActiveLane:473  case VPInstruction::LastActiveLane:474  case VPInstruction::SLPLoad:475  case VPInstruction::SLPStore:476    // Cannot determine the number of operands from the opcode.477    return -1u;478  }479  llvm_unreachable("all cases should be handled above");480}481#endif482 483bool VPInstruction::doesGeneratePerAllLanes() const {484  return Opcode == VPInstruction::PtrAdd && !vputils::onlyFirstLaneUsed(this);485}486 487bool VPInstruction::canGenerateScalarForFirstLane() const {488  if (Instruction::isBinaryOp(getOpcode()) || Instruction::isCast(getOpcode()))489    return true;490  if (isSingleScalar() || isVectorToScalar())491    return true;492  switch (Opcode) {493  case Instruction::Freeze:494  case Instruction::ICmp:495  case Instruction::PHI:496  case Instruction::Select:497  case VPInstruction::BranchOnCond:498  case VPInstruction::BranchOnCount:499  case VPInstruction::CalculateTripCountMinusVF:500  case VPInstruction::CanonicalIVIncrementForPart:501  case VPInstruction::PtrAdd:502  case VPInstruction::ExplicitVectorLength:503  case VPInstruction::AnyOf:504  case VPInstruction::Not:505    return true;506  default:507    return false;508  }509}510 511/// Create a conditional branch using \p Cond branching to the successors of \p512/// VPBB. Note that the first successor is always forward (i.e. not created yet)513/// while the second successor may already have been created (if it is a header514/// block and VPBB is a latch).515static BranchInst *createCondBranch(Value *Cond, VPBasicBlock *VPBB,516                                    VPTransformState &State) {517  // Replace the temporary unreachable terminator with a new conditional518  // branch, hooking it up to backward destination (header) for latch blocks519  // now, and to forward destination(s) later when they are created.520  // Second successor may be backwards - iff it is already in VPBB2IRBB.521  VPBasicBlock *SecondVPSucc = cast<VPBasicBlock>(VPBB->getSuccessors()[1]);522  BasicBlock *SecondIRSucc = State.CFG.VPBB2IRBB.lookup(SecondVPSucc);523  BasicBlock *IRBB = State.CFG.VPBB2IRBB[VPBB];524  BranchInst *CondBr = State.Builder.CreateCondBr(Cond, IRBB, SecondIRSucc);525  // First successor is always forward, reset it to nullptr526  CondBr->setSuccessor(0, nullptr);527  IRBB->getTerminator()->eraseFromParent();528  return CondBr;529}530 531Value *VPInstruction::generate(VPTransformState &State) {532  IRBuilderBase &Builder = State.Builder;533 534  if (Instruction::isBinaryOp(getOpcode())) {535    bool OnlyFirstLaneUsed = vputils::onlyFirstLaneUsed(this);536    Value *A = State.get(getOperand(0), OnlyFirstLaneUsed);537    Value *B = State.get(getOperand(1), OnlyFirstLaneUsed);538    auto *Res =539        Builder.CreateBinOp((Instruction::BinaryOps)getOpcode(), A, B, Name);540    if (auto *I = dyn_cast<Instruction>(Res))541      applyFlags(*I);542    return Res;543  }544 545  switch (getOpcode()) {546  case VPInstruction::Not: {547    bool OnlyFirstLaneUsed = vputils::onlyFirstLaneUsed(this);548    Value *A = State.get(getOperand(0), OnlyFirstLaneUsed);549    return Builder.CreateNot(A, Name);550  }551  case Instruction::ExtractElement: {552    assert(State.VF.isVector() && "Only extract elements from vectors");553    if (getOperand(1)->isLiveIn()) {554      unsigned IdxToExtract =555          cast<ConstantInt>(getOperand(1)->getLiveInIRValue())->getZExtValue();556      return State.get(getOperand(0), VPLane(IdxToExtract));557    }558    Value *Vec = State.get(getOperand(0));559    Value *Idx = State.get(getOperand(1), /*IsScalar=*/true);560    return Builder.CreateExtractElement(Vec, Idx, Name);561  }562  case Instruction::Freeze: {563    Value *Op = State.get(getOperand(0), vputils::onlyFirstLaneUsed(this));564    return Builder.CreateFreeze(Op, Name);565  }566  case Instruction::FCmp:567  case Instruction::ICmp: {568    bool OnlyFirstLaneUsed = vputils::onlyFirstLaneUsed(this);569    Value *A = State.get(getOperand(0), OnlyFirstLaneUsed);570    Value *B = State.get(getOperand(1), OnlyFirstLaneUsed);571    return Builder.CreateCmp(getPredicate(), A, B, Name);572  }573  case Instruction::PHI: {574    llvm_unreachable("should be handled by VPPhi::execute");575  }576  case Instruction::Select: {577    bool OnlyFirstLaneUsed = vputils::onlyFirstLaneUsed(this);578    Value *Cond =579        State.get(getOperand(0),580                  OnlyFirstLaneUsed || vputils::isSingleScalar(getOperand(0)));581    Value *Op1 = State.get(getOperand(1), OnlyFirstLaneUsed);582    Value *Op2 = State.get(getOperand(2), OnlyFirstLaneUsed);583    return Builder.CreateSelect(Cond, Op1, Op2, Name);584  }585  case VPInstruction::ActiveLaneMask: {586    // Get first lane of vector induction variable.587    Value *VIVElem0 = State.get(getOperand(0), VPLane(0));588    // Get the original loop tripcount.589    Value *ScalarTC = State.get(getOperand(1), VPLane(0));590 591    // If this part of the active lane mask is scalar, generate the CMP directly592    // to avoid unnecessary extracts.593    if (State.VF.isScalar())594      return Builder.CreateCmp(CmpInst::Predicate::ICMP_ULT, VIVElem0, ScalarTC,595                               Name);596 597    ElementCount EC = State.VF.multiplyCoefficientBy(598        cast<ConstantInt>(getOperand(2)->getLiveInIRValue())->getZExtValue());599    auto *PredTy = VectorType::get(Builder.getInt1Ty(), EC);600    return Builder.CreateIntrinsic(Intrinsic::get_active_lane_mask,601                                   {PredTy, ScalarTC->getType()},602                                   {VIVElem0, ScalarTC}, nullptr, Name);603  }604  case VPInstruction::FirstOrderRecurrenceSplice: {605    // Generate code to combine the previous and current values in vector v3.606    //607    //   vector.ph:608    //     v_init = vector(..., ..., ..., a[-1])609    //     br vector.body610    //611    //   vector.body612    //     i = phi [0, vector.ph], [i+4, vector.body]613    //     v1 = phi [v_init, vector.ph], [v2, vector.body]614    //     v2 = a[i, i+1, i+2, i+3];615    //     v3 = vector(v1(3), v2(0, 1, 2))616 617    auto *V1 = State.get(getOperand(0));618    if (!V1->getType()->isVectorTy())619      return V1;620    Value *V2 = State.get(getOperand(1));621    return Builder.CreateVectorSplice(V1, V2, -1, Name);622  }623  case VPInstruction::CalculateTripCountMinusVF: {624    unsigned UF = getParent()->getPlan()->getUF();625    Value *ScalarTC = State.get(getOperand(0), VPLane(0));626    Value *Step = createStepForVF(Builder, ScalarTC->getType(), State.VF, UF);627    Value *Sub = Builder.CreateSub(ScalarTC, Step);628    Value *Cmp = Builder.CreateICmp(CmpInst::Predicate::ICMP_UGT, ScalarTC, Step);629    Value *Zero = ConstantInt::getNullValue(ScalarTC->getType());630    return Builder.CreateSelect(Cmp, Sub, Zero);631  }632  case VPInstruction::ExplicitVectorLength: {633    // TODO: Restructure this code with an explicit remainder loop, vsetvli can634    // be outside of the main loop.635    Value *AVL = State.get(getOperand(0), /*IsScalar*/ true);636    // Compute EVL637    assert(AVL->getType()->isIntegerTy() &&638           "Requested vector length should be an integer.");639 640    assert(State.VF.isScalable() && "Expected scalable vector factor.");641    Value *VFArg = Builder.getInt32(State.VF.getKnownMinValue());642 643    Value *EVL = Builder.CreateIntrinsic(644        Builder.getInt32Ty(), Intrinsic::experimental_get_vector_length,645        {AVL, VFArg, Builder.getTrue()});646    return EVL;647  }648  case VPInstruction::CanonicalIVIncrementForPart: {649    unsigned Part = getUnrollPart(*this);650    auto *IV = State.get(getOperand(0), VPLane(0));651    assert(Part != 0 && "Must have a positive part");652    // The canonical IV is incremented by the vectorization factor (num of653    // SIMD elements) times the unroll part.654    Value *Step = createStepForVF(Builder, IV->getType(), State.VF, Part);655    return Builder.CreateAdd(IV, Step, Name, hasNoUnsignedWrap(),656                             hasNoSignedWrap());657  }658  case VPInstruction::BranchOnCond: {659    Value *Cond = State.get(getOperand(0), VPLane(0));660    auto *Br = createCondBranch(Cond, getParent(), State);661    applyMetadata(*Br);662    return Br;663  }664  case VPInstruction::BranchOnCount: {665    // First create the compare.666    Value *IV = State.get(getOperand(0), /*IsScalar*/ true);667    Value *TC = State.get(getOperand(1), /*IsScalar*/ true);668    Value *Cond = Builder.CreateICmpEQ(IV, TC);669    return createCondBranch(Cond, getParent(), State);670  }671  case VPInstruction::Broadcast: {672    return Builder.CreateVectorSplat(673        State.VF, State.get(getOperand(0), /*IsScalar*/ true), "broadcast");674  }675  case VPInstruction::BuildStructVector: {676    // For struct types, we need to build a new 'wide' struct type, where each677    // element is widened, i.e., we create a struct of vectors.678    auto *StructTy =679        cast<StructType>(State.TypeAnalysis.inferScalarType(getOperand(0)));680    Value *Res = PoisonValue::get(toVectorizedTy(StructTy, State.VF));681    for (const auto &[LaneIndex, Op] : enumerate(operands())) {682      for (unsigned FieldIndex = 0; FieldIndex != StructTy->getNumElements();683           FieldIndex++) {684        Value *ScalarValue =685            Builder.CreateExtractValue(State.get(Op, true), FieldIndex);686        Value *VectorValue = Builder.CreateExtractValue(Res, FieldIndex);687        VectorValue =688            Builder.CreateInsertElement(VectorValue, ScalarValue, LaneIndex);689        Res = Builder.CreateInsertValue(Res, VectorValue, FieldIndex);690      }691    }692    return Res;693  }694  case VPInstruction::BuildVector: {695    auto *ScalarTy = State.TypeAnalysis.inferScalarType(getOperand(0));696    auto NumOfElements = ElementCount::getFixed(getNumOperands());697    Value *Res = PoisonValue::get(toVectorizedTy(ScalarTy, NumOfElements));698    for (const auto &[Idx, Op] : enumerate(operands()))699      Res = Builder.CreateInsertElement(Res, State.get(Op, true),700                                        Builder.getInt32(Idx));701    return Res;702  }703  case VPInstruction::ReductionStartVector: {704    if (State.VF.isScalar())705      return State.get(getOperand(0), true);706    IRBuilderBase::FastMathFlagGuard FMFG(Builder);707    Builder.setFastMathFlags(getFastMathFlags());708    // If this start vector is scaled then it should produce a vector with fewer709    // elements than the VF.710    ElementCount VF = State.VF.divideCoefficientBy(711        cast<ConstantInt>(getOperand(2)->getLiveInIRValue())->getZExtValue());712    auto *Iden = Builder.CreateVectorSplat(VF, State.get(getOperand(1), true));713    return Builder.CreateInsertElement(Iden, State.get(getOperand(0), true),714                                       Builder.getInt32(0));715  }716  case VPInstruction::ComputeAnyOfResult: {717    // FIXME: The cross-recipe dependency on VPReductionPHIRecipe is temporary718    // and will be removed by breaking up the recipe further.719    auto *PhiR = cast<VPReductionPHIRecipe>(getOperand(0));720    auto *OrigPhi = cast<PHINode>(PhiR->getUnderlyingValue());721    Value *ReducedPartRdx = State.get(getOperand(2));722    for (unsigned Idx = 3; Idx < getNumOperands(); ++Idx)723      ReducedPartRdx =724          Builder.CreateBinOp(Instruction::Or, State.get(getOperand(Idx)),725                              ReducedPartRdx, "bin.rdx");726    return createAnyOfReduction(Builder, ReducedPartRdx,727                                State.get(getOperand(1), VPLane(0)), OrigPhi);728  }729  case VPInstruction::ComputeFindIVResult: {730    // FIXME: The cross-recipe dependency on VPReductionPHIRecipe is temporary731    // and will be removed by breaking up the recipe further.732    auto *PhiR = cast<VPReductionPHIRecipe>(getOperand(0));733    // Get its reduction variable descriptor.734    RecurKind RK = PhiR->getRecurrenceKind();735    assert(RecurrenceDescriptor::isFindIVRecurrenceKind(RK) &&736           "Unexpected reduction kind");737    assert(!PhiR->isInLoop() &&738           "In-loop FindLastIV reduction is not supported yet");739 740    // The recipe's operands are the reduction phi, the start value, the741    // sentinel value, followed by one operand for each part of the reduction.742    unsigned UF = getNumOperands() - 3;743    Value *ReducedPartRdx = State.get(getOperand(3));744    RecurKind MinMaxKind;745    bool IsSigned = RecurrenceDescriptor::isSignedRecurrenceKind(RK);746    if (RecurrenceDescriptor::isFindLastIVRecurrenceKind(RK))747      MinMaxKind = IsSigned ? RecurKind::SMax : RecurKind::UMax;748    else749      MinMaxKind = IsSigned ? RecurKind::SMin : RecurKind::UMin;750    for (unsigned Part = 1; Part < UF; ++Part)751      ReducedPartRdx = createMinMaxOp(Builder, MinMaxKind, ReducedPartRdx,752                                      State.get(getOperand(3 + Part)));753 754    Value *Start = State.get(getOperand(1), true);755    Value *Sentinel = getOperand(2)->getLiveInIRValue();756    return createFindLastIVReduction(Builder, ReducedPartRdx, RK, Start,757                                     Sentinel);758  }759  case VPInstruction::ComputeReductionResult: {760    // FIXME: The cross-recipe dependency on VPReductionPHIRecipe is temporary761    // and will be removed by breaking up the recipe further.762    auto *PhiR = cast<VPReductionPHIRecipe>(getOperand(0));763    // Get its reduction variable descriptor.764 765    RecurKind RK = PhiR->getRecurrenceKind();766    assert(!RecurrenceDescriptor::isFindIVRecurrenceKind(RK) &&767           "should be handled by ComputeFindIVResult");768 769    // The recipe's operands are the reduction phi, followed by one operand for770    // each part of the reduction.771    unsigned UF = getNumOperands() - 1;772    VectorParts RdxParts(UF);773    for (unsigned Part = 0; Part < UF; ++Part)774      RdxParts[Part] = State.get(getOperand(1 + Part), PhiR->isInLoop());775 776    IRBuilderBase::FastMathFlagGuard FMFG(Builder);777    if (hasFastMathFlags())778      Builder.setFastMathFlags(getFastMathFlags());779 780    // Reduce all of the unrolled parts into a single vector.781    Value *ReducedPartRdx = RdxParts[0];782    if (PhiR->isOrdered()) {783      ReducedPartRdx = RdxParts[UF - 1];784    } else {785      // Floating-point operations should have some FMF to enable the reduction.786      for (unsigned Part = 1; Part < UF; ++Part) {787        Value *RdxPart = RdxParts[Part];788        if (RecurrenceDescriptor::isMinMaxRecurrenceKind(RK))789          ReducedPartRdx = createMinMaxOp(Builder, RK, ReducedPartRdx, RdxPart);790        else {791          // For sub-recurrences, each UF's reduction variable is already792          // negative, we need to do: reduce.add(-acc_uf0 + -acc_uf1)793          Instruction::BinaryOps Opcode =794              RK == RecurKind::Sub795                  ? Instruction::Add796                  : (Instruction::BinaryOps)RecurrenceDescriptor::getOpcode(RK);797          ReducedPartRdx =798              Builder.CreateBinOp(Opcode, RdxPart, ReducedPartRdx, "bin.rdx");799        }800      }801    }802 803    // Create the reduction after the loop. Note that inloop reductions create804    // the target reduction in the loop using a Reduction recipe.805    if (State.VF.isVector() && !PhiR->isInLoop()) {806      // TODO: Support in-order reductions based on the recurrence descriptor.807      // All ops in the reduction inherit fast-math-flags from the recurrence808      // descriptor.809      ReducedPartRdx = createSimpleReduction(Builder, ReducedPartRdx, RK);810    }811 812    return ReducedPartRdx;813  }814  case VPInstruction::ExtractLastLanePerPart:815  case VPInstruction::ExtractLastElement:816  case VPInstruction::ExtractPenultimateElement: {817    unsigned Offset =818        getOpcode() == VPInstruction::ExtractPenultimateElement ? 2 : 1;819    Value *Res;820    if (State.VF.isVector()) {821      assert(Offset <= State.VF.getKnownMinValue() &&822             "invalid offset to extract from");823      // Extract lane VF - Offset from the operand.824      Res = State.get(getOperand(0), VPLane::getLaneFromEnd(State.VF, Offset));825    } else {826      assert(Offset <= 1 && "invalid offset to extract from");827      Res = State.get(getOperand(0));828    }829    if (isa<ExtractElementInst>(Res))830      Res->setName(Name);831    return Res;832  }833  case VPInstruction::LogicalAnd: {834    Value *A = State.get(getOperand(0));835    Value *B = State.get(getOperand(1));836    return Builder.CreateLogicalAnd(A, B, Name);837  }838  case VPInstruction::PtrAdd: {839    assert(vputils::onlyFirstLaneUsed(this) &&840           "can only generate first lane for PtrAdd");841    Value *Ptr = State.get(getOperand(0), VPLane(0));842    Value *Addend = State.get(getOperand(1), VPLane(0));843    return Builder.CreatePtrAdd(Ptr, Addend, Name, getGEPNoWrapFlags());844  }845  case VPInstruction::WidePtrAdd: {846    Value *Ptr =847        State.get(getOperand(0), vputils::isSingleScalar(getOperand(0)));848    Value *Addend = State.get(getOperand(1));849    return Builder.CreatePtrAdd(Ptr, Addend, Name, getGEPNoWrapFlags());850  }851  case VPInstruction::AnyOf: {852    Value *Res = Builder.CreateFreeze(State.get(getOperand(0)));853    for (VPValue *Op : drop_begin(operands()))854      Res = Builder.CreateOr(Res, Builder.CreateFreeze(State.get(Op)));855    return State.VF.isScalar() ? Res : Builder.CreateOrReduce(Res);856  }857  case VPInstruction::ExtractLane: {858    Value *LaneToExtract = State.get(getOperand(0), true);859    Type *IdxTy = State.TypeAnalysis.inferScalarType(getOperand(0));860    Value *Res = nullptr;861    Value *RuntimeVF = getRuntimeVF(Builder, IdxTy, State.VF);862 863    for (unsigned Idx = 1; Idx != getNumOperands(); ++Idx) {864      Value *VectorStart =865          Builder.CreateMul(RuntimeVF, ConstantInt::get(IdxTy, Idx - 1));866      Value *VectorIdx = Idx == 1867                             ? LaneToExtract868                             : Builder.CreateSub(LaneToExtract, VectorStart);869      Value *Ext = State.VF.isScalar()870                       ? State.get(getOperand(Idx))871                       : Builder.CreateExtractElement(872                             State.get(getOperand(Idx)), VectorIdx);873      if (Res) {874        Value *Cmp = Builder.CreateICmpUGE(LaneToExtract, VectorStart);875        Res = Builder.CreateSelect(Cmp, Ext, Res);876      } else {877        Res = Ext;878      }879    }880    return Res;881  }882  case VPInstruction::FirstActiveLane: {883    if (getNumOperands() == 1) {884      Value *Mask = State.get(getOperand(0));885      return Builder.CreateCountTrailingZeroElems(Builder.getInt64Ty(), Mask,886                                                  /*ZeroIsPoison=*/false, Name);887    }888    // If there are multiple operands, create a chain of selects to pick the889    // first operand with an active lane and add the number of lanes of the890    // preceding operands.891    Value *RuntimeVF = getRuntimeVF(Builder, Builder.getInt64Ty(), State.VF);892    unsigned LastOpIdx = getNumOperands() - 1;893    Value *Res = nullptr;894    for (int Idx = LastOpIdx; Idx >= 0; --Idx) {895      Value *TrailingZeros =896          State.VF.isScalar()897              ? Builder.CreateZExt(898                    Builder.CreateICmpEQ(State.get(getOperand(Idx)),899                                         Builder.getFalse()),900                    Builder.getInt64Ty())901              : Builder.CreateCountTrailingZeroElems(902                    Builder.getInt64Ty(), State.get(getOperand(Idx)),903                    /*ZeroIsPoison=*/false, Name);904      Value *Current = Builder.CreateAdd(905          Builder.CreateMul(RuntimeVF, Builder.getInt64(Idx)), TrailingZeros);906      if (Res) {907        Value *Cmp = Builder.CreateICmpNE(TrailingZeros, RuntimeVF);908        Res = Builder.CreateSelect(Cmp, Current, Res);909      } else {910        Res = Current;911      }912    }913 914    return Res;915  }916  case VPInstruction::ResumeForEpilogue:917    return State.get(getOperand(0), true);918  default:919    llvm_unreachable("Unsupported opcode for instruction");920  }921}922 923InstructionCost VPRecipeWithIRFlags::getCostForRecipeWithOpcode(924    unsigned Opcode, ElementCount VF, VPCostContext &Ctx) const {925  Type *ScalarTy = Ctx.Types.inferScalarType(this);926  Type *ResultTy = VF.isVector() ? toVectorTy(ScalarTy, VF) : ScalarTy;927  switch (Opcode) {928  case Instruction::FNeg:929    return Ctx.TTI.getArithmeticInstrCost(Opcode, ResultTy, Ctx.CostKind);930  case Instruction::UDiv:931  case Instruction::SDiv:932  case Instruction::SRem:933  case Instruction::URem:934  case Instruction::Add:935  case Instruction::FAdd:936  case Instruction::Sub:937  case Instruction::FSub:938  case Instruction::Mul:939  case Instruction::FMul:940  case Instruction::FDiv:941  case Instruction::FRem:942  case Instruction::Shl:943  case Instruction::LShr:944  case Instruction::AShr:945  case Instruction::And:946  case Instruction::Or:947  case Instruction::Xor: {948    TargetTransformInfo::OperandValueInfo RHSInfo = {949        TargetTransformInfo::OK_AnyValue, TargetTransformInfo::OP_None};950 951    if (VF.isVector()) {952      // Certain instructions can be cheaper to vectorize if they have a953      // constant second vector operand. One example of this are shifts on x86.954      VPValue *RHS = getOperand(1);955      RHSInfo = Ctx.getOperandInfo(RHS);956 957      if (RHSInfo.Kind == TargetTransformInfo::OK_AnyValue &&958          getOperand(1)->isDefinedOutsideLoopRegions())959        RHSInfo.Kind = TargetTransformInfo::OK_UniformValue;960    }961 962    Instruction *CtxI = dyn_cast_or_null<Instruction>(getUnderlyingValue());963    SmallVector<const Value *, 4> Operands;964    if (CtxI)965      Operands.append(CtxI->value_op_begin(), CtxI->value_op_end());966    return Ctx.TTI.getArithmeticInstrCost(967        Opcode, ResultTy, Ctx.CostKind,968        {TargetTransformInfo::OK_AnyValue, TargetTransformInfo::OP_None},969        RHSInfo, Operands, CtxI, &Ctx.TLI);970  }971  case Instruction::Freeze:972    // This opcode is unknown. Assume that it is the same as 'mul'.973    return Ctx.TTI.getArithmeticInstrCost(Instruction::Mul, ResultTy,974                                          Ctx.CostKind);975  case Instruction::ExtractValue:976    return Ctx.TTI.getInsertExtractValueCost(Instruction::ExtractValue,977                                             Ctx.CostKind);978  case Instruction::ICmp:979  case Instruction::FCmp: {980    Type *ScalarOpTy = Ctx.Types.inferScalarType(getOperand(0));981    Type *OpTy = VF.isVector() ? toVectorTy(ScalarOpTy, VF) : ScalarOpTy;982    Instruction *CtxI = dyn_cast_or_null<Instruction>(getUnderlyingValue());983    return Ctx.TTI.getCmpSelInstrCost(984        Opcode, OpTy, CmpInst::makeCmpResultType(OpTy), getPredicate(),985        Ctx.CostKind, {TTI::OK_AnyValue, TTI::OP_None},986        {TTI::OK_AnyValue, TTI::OP_None}, CtxI);987  }988  }989  llvm_unreachable("called for unsupported opcode");990}991 992InstructionCost VPInstruction::computeCost(ElementCount VF,993                                           VPCostContext &Ctx) const {994  if (Instruction::isBinaryOp(getOpcode())) {995    if (!getUnderlyingValue() && getOpcode() != Instruction::FMul) {996      // TODO: Compute cost for VPInstructions without underlying values once997      // the legacy cost model has been retired.998      return 0;999    }1000 1001    assert(!doesGeneratePerAllLanes() &&1002           "Should only generate a vector value or single scalar, not scalars "1003           "for all lanes.");1004    return getCostForRecipeWithOpcode(1005        getOpcode(),1006        vputils::onlyFirstLaneUsed(this) ? ElementCount::getFixed(1) : VF, Ctx);1007  }1008 1009  switch (getOpcode()) {1010  case Instruction::Select: {1011    // TODO: It may be possible to improve this by analyzing where the1012    // condition operand comes from.1013    CmpInst::Predicate Pred = CmpInst::BAD_ICMP_PREDICATE;1014    auto *CondTy = Ctx.Types.inferScalarType(getOperand(0));1015    auto *VecTy = Ctx.Types.inferScalarType(getOperand(1));1016    if (!vputils::onlyFirstLaneUsed(this)) {1017      CondTy = toVectorTy(CondTy, VF);1018      VecTy = toVectorTy(VecTy, VF);1019    }1020    return Ctx.TTI.getCmpSelInstrCost(Instruction::Select, VecTy, CondTy, Pred,1021                                      Ctx.CostKind);1022  }1023  case Instruction::ExtractElement:1024  case VPInstruction::ExtractLane: {1025    if (VF.isScalar()) {1026      // ExtractLane with VF=1 takes care of handling extracting across multiple1027      // parts.1028      return 0;1029    }1030 1031    // Add on the cost of extracting the element.1032    auto *VecTy = toVectorTy(Ctx.Types.inferScalarType(getOperand(0)), VF);1033    return Ctx.TTI.getVectorInstrCost(Instruction::ExtractElement, VecTy,1034                                      Ctx.CostKind);1035  }1036  case VPInstruction::AnyOf: {1037    auto *VecTy = toVectorTy(Ctx.Types.inferScalarType(this), VF);1038    return Ctx.TTI.getArithmeticReductionCost(1039        Instruction::Or, cast<VectorType>(VecTy), std::nullopt, Ctx.CostKind);1040  }1041  case VPInstruction::FirstActiveLane: {1042    Type *ScalarTy = Ctx.Types.inferScalarType(getOperand(0));1043    if (VF.isScalar())1044      return Ctx.TTI.getCmpSelInstrCost(Instruction::ICmp, ScalarTy,1045                                        CmpInst::makeCmpResultType(ScalarTy),1046                                        CmpInst::ICMP_EQ, Ctx.CostKind);1047    // Calculate the cost of determining the lane index.1048    auto *PredTy = toVectorTy(ScalarTy, VF);1049    IntrinsicCostAttributes Attrs(Intrinsic::experimental_cttz_elts,1050                                  Type::getInt64Ty(Ctx.LLVMCtx),1051                                  {PredTy, Type::getInt1Ty(Ctx.LLVMCtx)});1052    return Ctx.TTI.getIntrinsicInstrCost(Attrs, Ctx.CostKind);1053  }1054  case VPInstruction::LastActiveLane: {1055    Type *ScalarTy = Ctx.Types.inferScalarType(getOperand(0));1056    if (VF.isScalar())1057      return Ctx.TTI.getCmpSelInstrCost(Instruction::ICmp, ScalarTy,1058                                        CmpInst::makeCmpResultType(ScalarTy),1059                                        CmpInst::ICMP_EQ, Ctx.CostKind);1060    // Calculate the cost of determining the lane index: NOT + cttz_elts + SUB.1061    auto *PredTy = toVectorTy(ScalarTy, VF);1062    IntrinsicCostAttributes Attrs(Intrinsic::experimental_cttz_elts,1063                                  Type::getInt64Ty(Ctx.LLVMCtx),1064                                  {PredTy, Type::getInt1Ty(Ctx.LLVMCtx)});1065    InstructionCost Cost = Ctx.TTI.getIntrinsicInstrCost(Attrs, Ctx.CostKind);1066    // Add cost of NOT operation on the predicate.1067    Cost += Ctx.TTI.getArithmeticInstrCost(1068        Instruction::Xor, PredTy, Ctx.CostKind,1069        {TargetTransformInfo::OK_AnyValue, TargetTransformInfo::OP_None},1070        {TargetTransformInfo::OK_UniformConstantValue,1071         TargetTransformInfo::OP_None});1072    // Add cost of SUB operation on the index.1073    Cost += Ctx.TTI.getArithmeticInstrCost(1074        Instruction::Sub, Type::getInt64Ty(Ctx.LLVMCtx), Ctx.CostKind);1075    return Cost;1076  }1077  case VPInstruction::FirstOrderRecurrenceSplice: {1078    assert(VF.isVector() && "Scalar FirstOrderRecurrenceSplice?");1079    SmallVector<int> Mask(VF.getKnownMinValue());1080    std::iota(Mask.begin(), Mask.end(), VF.getKnownMinValue() - 1);1081    Type *VectorTy = toVectorTy(Ctx.Types.inferScalarType(this), VF);1082 1083    return Ctx.TTI.getShuffleCost(TargetTransformInfo::SK_Splice,1084                                  cast<VectorType>(VectorTy),1085                                  cast<VectorType>(VectorTy), Mask,1086                                  Ctx.CostKind, VF.getKnownMinValue() - 1);1087  }1088  case VPInstruction::ActiveLaneMask: {1089    Type *ArgTy = Ctx.Types.inferScalarType(getOperand(0));1090    unsigned Multiplier =1091        cast<ConstantInt>(getOperand(2)->getLiveInIRValue())->getZExtValue();1092    Type *RetTy = toVectorTy(Type::getInt1Ty(Ctx.LLVMCtx), VF * Multiplier);1093    IntrinsicCostAttributes Attrs(Intrinsic::get_active_lane_mask, RetTy,1094                                  {ArgTy, ArgTy});1095    return Ctx.TTI.getIntrinsicInstrCost(Attrs, Ctx.CostKind);1096  }1097  case VPInstruction::ExplicitVectorLength: {1098    Type *Arg0Ty = Ctx.Types.inferScalarType(getOperand(0));1099    Type *I32Ty = Type::getInt32Ty(Ctx.LLVMCtx);1100    Type *I1Ty = Type::getInt1Ty(Ctx.LLVMCtx);1101    IntrinsicCostAttributes Attrs(Intrinsic::experimental_get_vector_length,1102                                  I32Ty, {Arg0Ty, I32Ty, I1Ty});1103    return Ctx.TTI.getIntrinsicInstrCost(Attrs, Ctx.CostKind);1104  }1105  case VPInstruction::ExtractLastElement: {1106    // Add on the cost of extracting the element.1107    auto *VecTy = toVectorTy(Ctx.Types.inferScalarType(getOperand(0)), VF);1108    return Ctx.TTI.getIndexedVectorInstrCostFromEnd(Instruction::ExtractElement,1109                                                    VecTy, Ctx.CostKind, 0);1110  }1111  case VPInstruction::ExtractPenultimateElement:1112    if (VF == ElementCount::getScalable(1))1113      return InstructionCost::getInvalid();1114    [[fallthrough]];1115  default:1116    // TODO: Compute cost other VPInstructions once the legacy cost model has1117    // been retired.1118    assert(!getUnderlyingValue() &&1119           "unexpected VPInstruction witht underlying value");1120    return 0;1121  }1122}1123 1124bool VPInstruction::isVectorToScalar() const {1125  return getOpcode() == VPInstruction::ExtractLastElement ||1126         getOpcode() == VPInstruction::ExtractLastLanePerPart ||1127         getOpcode() == VPInstruction::ExtractPenultimateElement ||1128         getOpcode() == Instruction::ExtractElement ||1129         getOpcode() == VPInstruction::ExtractLane ||1130         getOpcode() == VPInstruction::FirstActiveLane ||1131         getOpcode() == VPInstruction::LastActiveLane ||1132         getOpcode() == VPInstruction::ComputeAnyOfResult ||1133         getOpcode() == VPInstruction::ComputeFindIVResult ||1134         getOpcode() == VPInstruction::ComputeReductionResult ||1135         getOpcode() == VPInstruction::AnyOf;1136}1137 1138bool VPInstruction::isSingleScalar() const {1139  switch (getOpcode()) {1140  case Instruction::PHI:1141  case VPInstruction::ExplicitVectorLength:1142  case VPInstruction::ResumeForEpilogue:1143  case VPInstruction::VScale:1144    return true;1145  default:1146    return isScalarCast();1147  }1148}1149 1150void VPInstruction::execute(VPTransformState &State) {1151  assert(!State.Lane && "VPInstruction executing an Lane");1152  IRBuilderBase::FastMathFlagGuard FMFGuard(State.Builder);1153  assert(flagsValidForOpcode(getOpcode()) &&1154         "Set flags not supported for the provided opcode");1155  if (hasFastMathFlags())1156    State.Builder.setFastMathFlags(getFastMathFlags());1157  Value *GeneratedValue = generate(State);1158  if (!hasResult())1159    return;1160  assert(GeneratedValue && "generate must produce a value");1161  bool GeneratesPerFirstLaneOnly = canGenerateScalarForFirstLane() &&1162                                   (vputils::onlyFirstLaneUsed(this) ||1163                                    isVectorToScalar() || isSingleScalar());1164  assert((((GeneratedValue->getType()->isVectorTy() ||1165            GeneratedValue->getType()->isStructTy()) ==1166           !GeneratesPerFirstLaneOnly) ||1167          State.VF.isScalar()) &&1168         "scalar value but not only first lane defined");1169  State.set(this, GeneratedValue,1170            /*IsScalar*/ GeneratesPerFirstLaneOnly);1171}1172 1173bool VPInstruction::opcodeMayReadOrWriteFromMemory() const {1174  if (Instruction::isBinaryOp(getOpcode()) || Instruction::isCast(getOpcode()))1175    return false;1176  switch (getOpcode()) {1177  case Instruction::GetElementPtr:1178  case Instruction::ExtractElement:1179  case Instruction::Freeze:1180  case Instruction::FCmp:1181  case Instruction::ICmp:1182  case Instruction::Select:1183  case Instruction::PHI:1184  case VPInstruction::AnyOf:1185  case VPInstruction::BranchOnCond:1186  case VPInstruction::BranchOnCount:1187  case VPInstruction::Broadcast:1188  case VPInstruction::BuildStructVector:1189  case VPInstruction::BuildVector:1190  case VPInstruction::CalculateTripCountMinusVF:1191  case VPInstruction::CanonicalIVIncrementForPart:1192  case VPInstruction::ExtractLane:1193  case VPInstruction::ExtractLastElement:1194  case VPInstruction::ExtractLastLanePerPart:1195  case VPInstruction::ExtractPenultimateElement:1196  case VPInstruction::ActiveLaneMask:1197  case VPInstruction::ExplicitVectorLength:1198  case VPInstruction::FirstActiveLane:1199  case VPInstruction::LastActiveLane:1200  case VPInstruction::FirstOrderRecurrenceSplice:1201  case VPInstruction::LogicalAnd:1202  case VPInstruction::Not:1203  case VPInstruction::PtrAdd:1204  case VPInstruction::WideIVStep:1205  case VPInstruction::WidePtrAdd:1206  case VPInstruction::StepVector:1207  case VPInstruction::ReductionStartVector:1208  case VPInstruction::VScale:1209  case VPInstruction::Unpack:1210    return false;1211  default:1212    return true;1213  }1214}1215 1216bool VPInstruction::usesFirstLaneOnly(const VPValue *Op) const {1217  assert(is_contained(operands(), Op) && "Op must be an operand of the recipe");1218  if (Instruction::isBinaryOp(getOpcode()) || Instruction::isCast(getOpcode()))1219    return vputils::onlyFirstLaneUsed(this);1220 1221  switch (getOpcode()) {1222  default:1223    return false;1224  case Instruction::ExtractElement:1225    return Op == getOperand(1);1226  case Instruction::PHI:1227    return true;1228  case Instruction::FCmp:1229  case Instruction::ICmp:1230  case Instruction::Select:1231  case Instruction::Or:1232  case Instruction::Freeze:1233  case VPInstruction::Not:1234    // TODO: Cover additional opcodes.1235    return vputils::onlyFirstLaneUsed(this);1236  case VPInstruction::ActiveLaneMask:1237  case VPInstruction::ExplicitVectorLength:1238  case VPInstruction::CalculateTripCountMinusVF:1239  case VPInstruction::CanonicalIVIncrementForPart:1240  case VPInstruction::BranchOnCount:1241  case VPInstruction::BranchOnCond:1242  case VPInstruction::Broadcast:1243  case VPInstruction::ReductionStartVector:1244    return true;1245  case VPInstruction::BuildStructVector:1246  case VPInstruction::BuildVector:1247    // Before replicating by VF, Build(Struct)Vector uses all lanes of the1248    // operand, after replicating its operands only the first lane is used.1249    // Before replicating, it will have only a single operand.1250    return getNumOperands() > 1;1251  case VPInstruction::PtrAdd:1252    return Op == getOperand(0) || vputils::onlyFirstLaneUsed(this);1253  case VPInstruction::WidePtrAdd:1254    // WidePtrAdd supports scalar and vector base addresses.1255    return false;1256  case VPInstruction::ComputeAnyOfResult:1257  case VPInstruction::ComputeFindIVResult:1258    return Op == getOperand(1);1259  case VPInstruction::ExtractLane:1260    return Op == getOperand(0);1261  };1262  llvm_unreachable("switch should return");1263}1264 1265bool VPInstruction::usesFirstPartOnly(const VPValue *Op) const {1266  assert(is_contained(operands(), Op) && "Op must be an operand of the recipe");1267  if (Instruction::isBinaryOp(getOpcode()))1268    return vputils::onlyFirstPartUsed(this);1269 1270  switch (getOpcode()) {1271  default:1272    return false;1273  case Instruction::FCmp:1274  case Instruction::ICmp:1275  case Instruction::Select:1276    return vputils::onlyFirstPartUsed(this);1277  case VPInstruction::BranchOnCount:1278  case VPInstruction::BranchOnCond:1279  case VPInstruction::CanonicalIVIncrementForPart:1280    return true;1281  };1282  llvm_unreachable("switch should return");1283}1284 1285#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)1286void VPInstruction::dump() const {1287  VPSlotTracker SlotTracker(getParent()->getPlan());1288  printRecipe(dbgs(), "", SlotTracker);1289}1290 1291void VPInstruction::printRecipe(raw_ostream &O, const Twine &Indent,1292                                VPSlotTracker &SlotTracker) const {1293  O << Indent << "EMIT" << (isSingleScalar() ? "-SCALAR" : "") << " ";1294 1295  if (hasResult()) {1296    printAsOperand(O, SlotTracker);1297    O << " = ";1298  }1299 1300  switch (getOpcode()) {1301  case VPInstruction::Not:1302    O << "not";1303    break;1304  case VPInstruction::SLPLoad:1305    O << "combined load";1306    break;1307  case VPInstruction::SLPStore:1308    O << "combined store";1309    break;1310  case VPInstruction::ActiveLaneMask:1311    O << "active lane mask";1312    break;1313  case VPInstruction::ExplicitVectorLength:1314    O << "EXPLICIT-VECTOR-LENGTH";1315    break;1316  case VPInstruction::FirstOrderRecurrenceSplice:1317    O << "first-order splice";1318    break;1319  case VPInstruction::BranchOnCond:1320    O << "branch-on-cond";1321    break;1322  case VPInstruction::CalculateTripCountMinusVF:1323    O << "TC > VF ? TC - VF : 0";1324    break;1325  case VPInstruction::CanonicalIVIncrementForPart:1326    O << "VF * Part +";1327    break;1328  case VPInstruction::BranchOnCount:1329    O << "branch-on-count";1330    break;1331  case VPInstruction::Broadcast:1332    O << "broadcast";1333    break;1334  case VPInstruction::BuildStructVector:1335    O << "buildstructvector";1336    break;1337  case VPInstruction::BuildVector:1338    O << "buildvector";1339    break;1340  case VPInstruction::ExtractLane:1341    O << "extract-lane";1342    break;1343  case VPInstruction::ExtractLastElement:1344    O << "extract-last-element";1345    break;1346  case VPInstruction::ExtractLastLanePerPart:1347    O << "extract-last-lane-per-part";1348    break;1349  case VPInstruction::ExtractPenultimateElement:1350    O << "extract-penultimate-element";1351    break;1352  case VPInstruction::ComputeAnyOfResult:1353    O << "compute-anyof-result";1354    break;1355  case VPInstruction::ComputeFindIVResult:1356    O << "compute-find-iv-result";1357    break;1358  case VPInstruction::ComputeReductionResult:1359    O << "compute-reduction-result";1360    break;1361  case VPInstruction::LogicalAnd:1362    O << "logical-and";1363    break;1364  case VPInstruction::PtrAdd:1365    O << "ptradd";1366    break;1367  case VPInstruction::WidePtrAdd:1368    O << "wide-ptradd";1369    break;1370  case VPInstruction::AnyOf:1371    O << "any-of";1372    break;1373  case VPInstruction::FirstActiveLane:1374    O << "first-active-lane";1375    break;1376  case VPInstruction::LastActiveLane:1377    O << "last-active-lane";1378    break;1379  case VPInstruction::ReductionStartVector:1380    O << "reduction-start-vector";1381    break;1382  case VPInstruction::ResumeForEpilogue:1383    O << "resume-for-epilogue";1384    break;1385  case VPInstruction::Unpack:1386    O << "unpack";1387    break;1388  default:1389    O << Instruction::getOpcodeName(getOpcode());1390  }1391 1392  printFlags(O);1393  printOperands(O, SlotTracker);1394}1395#endif1396 1397void VPInstructionWithType::execute(VPTransformState &State) {1398  State.setDebugLocFrom(getDebugLoc());1399  if (isScalarCast()) {1400    Value *Op = State.get(getOperand(0), VPLane(0));1401    Value *Cast = State.Builder.CreateCast(Instruction::CastOps(getOpcode()),1402                                           Op, ResultTy);1403    State.set(this, Cast, VPLane(0));1404    return;1405  }1406  switch (getOpcode()) {1407  case VPInstruction::StepVector: {1408    Value *StepVector =1409        State.Builder.CreateStepVector(VectorType::get(ResultTy, State.VF));1410    State.set(this, StepVector);1411    break;1412  }1413  case VPInstruction::VScale: {1414    Value *VScale = State.Builder.CreateVScale(ResultTy);1415    State.set(this, VScale, true);1416    break;1417  }1418 1419  default:1420    llvm_unreachable("opcode not implemented yet");1421  }1422}1423 1424#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)1425void VPInstructionWithType::printRecipe(raw_ostream &O, const Twine &Indent,1426                                        VPSlotTracker &SlotTracker) const {1427  O << Indent << "EMIT" << (isSingleScalar() ? "-SCALAR" : "") << " ";1428  printAsOperand(O, SlotTracker);1429  O << " = ";1430 1431  switch (getOpcode()) {1432  case VPInstruction::WideIVStep:1433    O << "wide-iv-step ";1434    printOperands(O, SlotTracker);1435    break;1436  case VPInstruction::StepVector:1437    O << "step-vector " << *ResultTy;1438    break;1439  case VPInstruction::VScale:1440    O << "vscale " << *ResultTy;1441    break;1442  default:1443    assert(Instruction::isCast(getOpcode()) && "unhandled opcode");1444    O << Instruction::getOpcodeName(getOpcode()) << " ";1445    printOperands(O, SlotTracker);1446    O << " to " << *ResultTy;1447  }1448}1449#endif1450 1451void VPPhi::execute(VPTransformState &State) {1452  State.setDebugLocFrom(getDebugLoc());1453  PHINode *NewPhi = State.Builder.CreatePHI(1454      State.TypeAnalysis.inferScalarType(this), 2, getName());1455  unsigned NumIncoming = getNumIncoming();1456  if (getParent() != getParent()->getPlan()->getScalarPreheader()) {1457    // TODO: Fixup all incoming values of header phis once recipes defining them1458    // are introduced.1459    NumIncoming = 1;1460  }1461  for (unsigned Idx = 0; Idx != NumIncoming; ++Idx) {1462    Value *IncV = State.get(getIncomingValue(Idx), VPLane(0));1463    BasicBlock *PredBB = State.CFG.VPBB2IRBB.at(getIncomingBlock(Idx));1464    NewPhi->addIncoming(IncV, PredBB);1465  }1466  State.set(this, NewPhi, VPLane(0));1467}1468 1469#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)1470void VPPhi::printRecipe(raw_ostream &O, const Twine &Indent,1471                        VPSlotTracker &SlotTracker) const {1472  O << Indent << "EMIT" << (isSingleScalar() ? "-SCALAR" : "") << " ";1473  printAsOperand(O, SlotTracker);1474  O << " = phi ";1475  printPhiOperands(O, SlotTracker);1476}1477#endif1478 1479VPIRInstruction *VPIRInstruction ::create(Instruction &I) {1480  if (auto *Phi = dyn_cast<PHINode>(&I))1481    return new VPIRPhi(*Phi);1482  return new VPIRInstruction(I);1483}1484 1485void VPIRInstruction::execute(VPTransformState &State) {1486  assert(!isa<VPIRPhi>(this) && getNumOperands() == 0 &&1487         "PHINodes must be handled by VPIRPhi");1488  // Advance the insert point after the wrapped IR instruction. This allows1489  // interleaving VPIRInstructions and other recipes.1490  State.Builder.SetInsertPoint(I.getParent(), std::next(I.getIterator()));1491}1492 1493InstructionCost VPIRInstruction::computeCost(ElementCount VF,1494                                             VPCostContext &Ctx) const {1495  // The recipe wraps an existing IR instruction on the border of VPlan's scope,1496  // hence it does not contribute to the cost-modeling for the VPlan.1497  return 0;1498}1499 1500void VPIRInstruction::extractLastLaneOfFirstOperand(VPBuilder &Builder) {1501  assert(isa<PHINode>(getInstruction()) &&1502         "can only update exiting operands to phi nodes");1503  assert(getNumOperands() > 0 && "must have at least one operand");1504  VPValue *Exiting = getOperand(0);1505  if (Exiting->isLiveIn())1506    return;1507 1508  Exiting = Builder.createNaryOp(VPInstruction::ExtractLastElement, {Exiting});1509  setOperand(0, Exiting);1510}1511 1512#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)1513void VPIRInstruction::printRecipe(raw_ostream &O, const Twine &Indent,1514                                  VPSlotTracker &SlotTracker) const {1515  O << Indent << "IR " << I;1516}1517#endif1518 1519void VPIRPhi::execute(VPTransformState &State) {1520  PHINode *Phi = &getIRPhi();1521  for (const auto &[Idx, Op] : enumerate(operands())) {1522    VPValue *ExitValue = Op;1523    auto Lane = vputils::isSingleScalar(ExitValue)1524                    ? VPLane::getFirstLane()1525                    : VPLane::getLastLaneForVF(State.VF);1526    VPBlockBase *Pred = getParent()->getPredecessors()[Idx];1527    auto *PredVPBB = Pred->getExitingBasicBlock();1528    BasicBlock *PredBB = State.CFG.VPBB2IRBB[PredVPBB];1529    // Set insertion point in PredBB in case an extract needs to be generated.1530    // TODO: Model extracts explicitly.1531    State.Builder.SetInsertPoint(PredBB, PredBB->getFirstNonPHIIt());1532    Value *V = State.get(ExitValue, VPLane(Lane));1533    // If there is no existing block for PredBB in the phi, add a new incoming1534    // value. Otherwise update the existing incoming value for PredBB.1535    if (Phi->getBasicBlockIndex(PredBB) == -1)1536      Phi->addIncoming(V, PredBB);1537    else1538      Phi->setIncomingValueForBlock(PredBB, V);1539  }1540 1541  // Advance the insert point after the wrapped IR instruction. This allows1542  // interleaving VPIRInstructions and other recipes.1543  State.Builder.SetInsertPoint(Phi->getParent(), std::next(Phi->getIterator()));1544}1545 1546void VPPhiAccessors::removeIncomingValueFor(VPBlockBase *IncomingBlock) const {1547  VPRecipeBase *R = const_cast<VPRecipeBase *>(getAsRecipe());1548  assert(R->getNumOperands() == R->getParent()->getNumPredecessors() &&1549         "Number of phi operands must match number of predecessors");1550  unsigned Position = R->getParent()->getIndexForPredecessor(IncomingBlock);1551  R->removeOperand(Position);1552}1553 1554#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)1555void VPPhiAccessors::printPhiOperands(raw_ostream &O,1556                                      VPSlotTracker &SlotTracker) const {1557  interleaveComma(enumerate(getAsRecipe()->operands()), O,1558                  [this, &O, &SlotTracker](auto Op) {1559                    O << "[ ";1560                    Op.value()->printAsOperand(O, SlotTracker);1561                    O << ", ";1562                    getIncomingBlock(Op.index())->printAsOperand(O);1563                    O << " ]";1564                  });1565}1566#endif1567 1568#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)1569void VPIRPhi::printRecipe(raw_ostream &O, const Twine &Indent,1570                          VPSlotTracker &SlotTracker) const {1571  VPIRInstruction::printRecipe(O, Indent, SlotTracker);1572 1573  if (getNumOperands() != 0) {1574    O << " (extra operand" << (getNumOperands() > 1 ? "s" : "") << ": ";1575    interleaveComma(incoming_values_and_blocks(), O,1576                    [&O, &SlotTracker](auto Op) {1577                      std::get<0>(Op)->printAsOperand(O, SlotTracker);1578                      O << " from ";1579                      std::get<1>(Op)->printAsOperand(O);1580                    });1581    O << ")";1582  }1583}1584#endif1585 1586void VPIRMetadata::applyMetadata(Instruction &I) const {1587  for (const auto &[Kind, Node] : Metadata)1588    I.setMetadata(Kind, Node);1589}1590 1591void VPIRMetadata::intersect(const VPIRMetadata &Other) {1592  SmallVector<std::pair<unsigned, MDNode *>> MetadataIntersection;1593  for (const auto &[KindA, MDA] : Metadata) {1594    for (const auto &[KindB, MDB] : Other.Metadata) {1595      if (KindA == KindB && MDA == MDB) {1596        MetadataIntersection.emplace_back(KindA, MDA);1597        break;1598      }1599    }1600  }1601  Metadata = std::move(MetadataIntersection);1602}1603 1604void VPWidenCallRecipe::execute(VPTransformState &State) {1605  assert(State.VF.isVector() && "not widening");1606  assert(Variant != nullptr && "Can't create vector function.");1607 1608  FunctionType *VFTy = Variant->getFunctionType();1609  // Add return type if intrinsic is overloaded on it.1610  SmallVector<Value *, 4> Args;1611  for (const auto &I : enumerate(args())) {1612    Value *Arg;1613    // Some vectorized function variants may also take a scalar argument,1614    // e.g. linear parameters for pointers. This needs to be the scalar value1615    // from the start of the respective part when interleaving.1616    if (!VFTy->getParamType(I.index())->isVectorTy())1617      Arg = State.get(I.value(), VPLane(0));1618    else1619      Arg = State.get(I.value(), usesFirstLaneOnly(I.value()));1620    Args.push_back(Arg);1621  }1622 1623  auto *CI = cast_or_null<CallInst>(getUnderlyingValue());1624  SmallVector<OperandBundleDef, 1> OpBundles;1625  if (CI)1626    CI->getOperandBundlesAsDefs(OpBundles);1627 1628  CallInst *V = State.Builder.CreateCall(Variant, Args, OpBundles);1629  applyFlags(*V);1630  applyMetadata(*V);1631  V->setCallingConv(Variant->getCallingConv());1632 1633  if (!V->getType()->isVoidTy())1634    State.set(this, V);1635}1636 1637InstructionCost VPWidenCallRecipe::computeCost(ElementCount VF,1638                                               VPCostContext &Ctx) const {1639  return Ctx.TTI.getCallInstrCost(nullptr, Variant->getReturnType(),1640                                  Variant->getFunctionType()->params(),1641                                  Ctx.CostKind);1642}1643 1644#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)1645void VPWidenCallRecipe::printRecipe(raw_ostream &O, const Twine &Indent,1646                                    VPSlotTracker &SlotTracker) const {1647  O << Indent << "WIDEN-CALL ";1648 1649  Function *CalledFn = getCalledScalarFunction();1650  if (CalledFn->getReturnType()->isVoidTy())1651    O << "void ";1652  else {1653    printAsOperand(O, SlotTracker);1654    O << " = ";1655  }1656 1657  O << "call";1658  printFlags(O);1659  O << " @" << CalledFn->getName() << "(";1660  interleaveComma(args(), O, [&O, &SlotTracker](VPValue *Op) {1661    Op->printAsOperand(O, SlotTracker);1662  });1663  O << ")";1664 1665  O << " (using library function";1666  if (Variant->hasName())1667    O << ": " << Variant->getName();1668  O << ")";1669}1670#endif1671 1672void VPWidenIntrinsicRecipe::execute(VPTransformState &State) {1673  assert(State.VF.isVector() && "not widening");1674 1675  SmallVector<Type *, 2> TysForDecl;1676  // Add return type if intrinsic is overloaded on it.1677  if (isVectorIntrinsicWithOverloadTypeAtArg(VectorIntrinsicID, -1, State.TTI))1678    TysForDecl.push_back(VectorType::get(getResultType(), State.VF));1679  SmallVector<Value *, 4> Args;1680  for (const auto &I : enumerate(operands())) {1681    // Some intrinsics have a scalar argument - don't replace it with a1682    // vector.1683    Value *Arg;1684    if (isVectorIntrinsicWithScalarOpAtArg(VectorIntrinsicID, I.index(),1685                                           State.TTI))1686      Arg = State.get(I.value(), VPLane(0));1687    else1688      Arg = State.get(I.value(), usesFirstLaneOnly(I.value()));1689    if (isVectorIntrinsicWithOverloadTypeAtArg(VectorIntrinsicID, I.index(),1690                                               State.TTI))1691      TysForDecl.push_back(Arg->getType());1692    Args.push_back(Arg);1693  }1694 1695  // Use vector version of the intrinsic.1696  Module *M = State.Builder.GetInsertBlock()->getModule();1697  Function *VectorF =1698      Intrinsic::getOrInsertDeclaration(M, VectorIntrinsicID, TysForDecl);1699  assert(VectorF &&1700         "Can't retrieve vector intrinsic or vector-predication intrinsics.");1701 1702  auto *CI = cast_or_null<CallInst>(getUnderlyingValue());1703  SmallVector<OperandBundleDef, 1> OpBundles;1704  if (CI)1705    CI->getOperandBundlesAsDefs(OpBundles);1706 1707  CallInst *V = State.Builder.CreateCall(VectorF, Args, OpBundles);1708 1709  applyFlags(*V);1710  applyMetadata(*V);1711 1712  if (!V->getType()->isVoidTy())1713    State.set(this, V);1714}1715 1716/// Compute the cost for the intrinsic \p ID with \p Operands, produced by \p R.1717static InstructionCost getCostForIntrinsics(Intrinsic::ID ID,1718                                            ArrayRef<const VPValue *> Operands,1719                                            const VPRecipeWithIRFlags &R,1720                                            ElementCount VF,1721                                            VPCostContext &Ctx) {1722  // Some backends analyze intrinsic arguments to determine cost. Use the1723  // underlying value for the operand if it has one. Otherwise try to use the1724  // operand of the underlying call instruction, if there is one. Otherwise1725  // clear Arguments.1726  // TODO: Rework TTI interface to be independent of concrete IR values.1727  SmallVector<const Value *> Arguments;1728  for (const auto &[Idx, Op] : enumerate(Operands)) {1729    auto *V = Op->getUnderlyingValue();1730    if (!V) {1731      if (auto *UI = dyn_cast_or_null<CallBase>(R.getUnderlyingValue())) {1732        Arguments.push_back(UI->getArgOperand(Idx));1733        continue;1734      }1735      Arguments.clear();1736      break;1737    }1738    Arguments.push_back(V);1739  }1740 1741  Type *ScalarRetTy = Ctx.Types.inferScalarType(&R);1742  Type *RetTy = VF.isVector() ? toVectorizedTy(ScalarRetTy, VF) : ScalarRetTy;1743  SmallVector<Type *> ParamTys;1744  for (const VPValue *Op : Operands) {1745    ParamTys.push_back(VF.isVector()1746                           ? toVectorTy(Ctx.Types.inferScalarType(Op), VF)1747                           : Ctx.Types.inferScalarType(Op));1748  }1749 1750  // TODO: Rework TTI interface to avoid reliance on underlying IntrinsicInst.1751  FastMathFlags FMF =1752      R.hasFastMathFlags() ? R.getFastMathFlags() : FastMathFlags();1753  IntrinsicCostAttributes CostAttrs(1754      ID, RetTy, Arguments, ParamTys, FMF,1755      dyn_cast_or_null<IntrinsicInst>(R.getUnderlyingValue()),1756      InstructionCost::getInvalid(), &Ctx.TLI);1757  return Ctx.TTI.getIntrinsicInstrCost(CostAttrs, Ctx.CostKind);1758}1759 1760InstructionCost VPWidenIntrinsicRecipe::computeCost(ElementCount VF,1761                                                    VPCostContext &Ctx) const {1762  SmallVector<const VPValue *> ArgOps(operands());1763  return getCostForIntrinsics(VectorIntrinsicID, ArgOps, *this, VF, Ctx);1764}1765 1766StringRef VPWidenIntrinsicRecipe::getIntrinsicName() const {1767  return Intrinsic::getBaseName(VectorIntrinsicID);1768}1769 1770bool VPWidenIntrinsicRecipe::usesFirstLaneOnly(const VPValue *Op) const {1771  assert(is_contained(operands(), Op) && "Op must be an operand of the recipe");1772  return all_of(enumerate(operands()), [this, &Op](const auto &X) {1773    auto [Idx, V] = X;1774    return V != Op || isVectorIntrinsicWithScalarOpAtArg(getVectorIntrinsicID(),1775                                                         Idx, nullptr);1776  });1777}1778 1779#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)1780void VPWidenIntrinsicRecipe::printRecipe(raw_ostream &O, const Twine &Indent,1781                                         VPSlotTracker &SlotTracker) const {1782  O << Indent << "WIDEN-INTRINSIC ";1783  if (ResultTy->isVoidTy()) {1784    O << "void ";1785  } else {1786    printAsOperand(O, SlotTracker);1787    O << " = ";1788  }1789 1790  O << "call";1791  printFlags(O);1792  O << getIntrinsicName() << "(";1793 1794  interleaveComma(operands(), O, [&O, &SlotTracker](VPValue *Op) {1795    Op->printAsOperand(O, SlotTracker);1796  });1797  O << ")";1798}1799#endif1800 1801void VPHistogramRecipe::execute(VPTransformState &State) {1802  IRBuilderBase &Builder = State.Builder;1803 1804  Value *Address = State.get(getOperand(0));1805  Value *IncAmt = State.get(getOperand(1), /*IsScalar=*/true);1806  VectorType *VTy = cast<VectorType>(Address->getType());1807 1808  // The histogram intrinsic requires a mask even if the recipe doesn't;1809  // if the mask operand was omitted then all lanes should be executed and1810  // we just need to synthesize an all-true mask.1811  Value *Mask = nullptr;1812  if (VPValue *VPMask = getMask())1813    Mask = State.get(VPMask);1814  else1815    Mask =1816        Builder.CreateVectorSplat(VTy->getElementCount(), Builder.getInt1(1));1817 1818  // If this is a subtract, we want to invert the increment amount. We may1819  // add a separate intrinsic in future, but for now we'll try this.1820  if (Opcode == Instruction::Sub)1821    IncAmt = Builder.CreateNeg(IncAmt);1822  else1823    assert(Opcode == Instruction::Add && "only add or sub supported for now");1824 1825  State.Builder.CreateIntrinsic(Intrinsic::experimental_vector_histogram_add,1826                                {VTy, IncAmt->getType()},1827                                {Address, IncAmt, Mask});1828}1829 1830InstructionCost VPHistogramRecipe::computeCost(ElementCount VF,1831                                               VPCostContext &Ctx) const {1832  // FIXME: Take the gather and scatter into account as well. For now we're1833  //        generating the same cost as the fallback path, but we'll likely1834  //        need to create a new TTI method for determining the cost, including1835  //        whether we can use base + vec-of-smaller-indices or just1836  //        vec-of-pointers.1837  assert(VF.isVector() && "Invalid VF for histogram cost");1838  Type *AddressTy = Ctx.Types.inferScalarType(getOperand(0));1839  VPValue *IncAmt = getOperand(1);1840  Type *IncTy = Ctx.Types.inferScalarType(IncAmt);1841  VectorType *VTy = VectorType::get(IncTy, VF);1842 1843  // Assume that a non-constant update value (or a constant != 1) requires1844  // a multiply, and add that into the cost.1845  InstructionCost MulCost =1846      Ctx.TTI.getArithmeticInstrCost(Instruction::Mul, VTy, Ctx.CostKind);1847  if (IncAmt->isLiveIn()) {1848    ConstantInt *CI = dyn_cast<ConstantInt>(IncAmt->getLiveInIRValue());1849 1850    if (CI && CI->getZExtValue() == 1)1851      MulCost = TTI::TCC_Free;1852  }1853 1854  // Find the cost of the histogram operation itself.1855  Type *PtrTy = VectorType::get(AddressTy, VF);1856  Type *MaskTy = VectorType::get(Type::getInt1Ty(Ctx.LLVMCtx), VF);1857  IntrinsicCostAttributes ICA(Intrinsic::experimental_vector_histogram_add,1858                              Type::getVoidTy(Ctx.LLVMCtx),1859                              {PtrTy, IncTy, MaskTy});1860 1861  // Add the costs together with the add/sub operation.1862  return Ctx.TTI.getIntrinsicInstrCost(ICA, Ctx.CostKind) + MulCost +1863         Ctx.TTI.getArithmeticInstrCost(Opcode, VTy, Ctx.CostKind);1864}1865 1866#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)1867void VPHistogramRecipe::printRecipe(raw_ostream &O, const Twine &Indent,1868                                    VPSlotTracker &SlotTracker) const {1869  O << Indent << "WIDEN-HISTOGRAM buckets: ";1870  getOperand(0)->printAsOperand(O, SlotTracker);1871 1872  if (Opcode == Instruction::Sub)1873    O << ", dec: ";1874  else {1875    assert(Opcode == Instruction::Add);1876    O << ", inc: ";1877  }1878  getOperand(1)->printAsOperand(O, SlotTracker);1879 1880  if (VPValue *Mask = getMask()) {1881    O << ", mask: ";1882    Mask->printAsOperand(O, SlotTracker);1883  }1884}1885 1886void VPWidenSelectRecipe::printRecipe(raw_ostream &O, const Twine &Indent,1887                                      VPSlotTracker &SlotTracker) const {1888  O << Indent << "WIDEN-SELECT ";1889  printAsOperand(O, SlotTracker);1890  O << " = select ";1891  printFlags(O);1892  getOperand(0)->printAsOperand(O, SlotTracker);1893  O << ", ";1894  getOperand(1)->printAsOperand(O, SlotTracker);1895  O << ", ";1896  getOperand(2)->printAsOperand(O, SlotTracker);1897  O << (vputils::isSingleScalar(getCond()) ? " (condition is single-scalar)"1898                                           : "");1899}1900#endif1901 1902void VPWidenSelectRecipe::execute(VPTransformState &State) {1903  Value *Cond = State.get(getCond(), vputils::isSingleScalar(getCond()));1904 1905  Value *Op0 = State.get(getOperand(1));1906  Value *Op1 = State.get(getOperand(2));1907  Value *Sel = State.Builder.CreateSelect(Cond, Op0, Op1);1908  State.set(this, Sel);1909  if (auto *I = dyn_cast<Instruction>(Sel)) {1910    if (isa<FPMathOperator>(I))1911      applyFlags(*I);1912    applyMetadata(*I);1913  }1914}1915 1916InstructionCost VPWidenSelectRecipe::computeCost(ElementCount VF,1917                                                 VPCostContext &Ctx) const {1918  SelectInst *SI = cast<SelectInst>(getUnderlyingValue());1919  bool ScalarCond = getOperand(0)->isDefinedOutsideLoopRegions();1920  Type *ScalarTy = Ctx.Types.inferScalarType(this);1921  Type *VectorTy = toVectorTy(Ctx.Types.inferScalarType(this), VF);1922 1923  VPValue *Op0, *Op1;1924  if (!ScalarCond && ScalarTy->getScalarSizeInBits() == 1 &&1925      (match(this, m_LogicalAnd(m_VPValue(Op0), m_VPValue(Op1))) ||1926       match(this, m_LogicalOr(m_VPValue(Op0), m_VPValue(Op1))))) {1927    // select x, y, false --> x & y1928    // select x, true, y --> x | y1929    const auto [Op1VK, Op1VP] = Ctx.getOperandInfo(Op0);1930    const auto [Op2VK, Op2VP] = Ctx.getOperandInfo(Op1);1931 1932    SmallVector<const Value *, 2> Operands;1933    if (all_of(operands(),1934               [](VPValue *Op) { return Op->getUnderlyingValue(); }))1935      Operands.append(SI->op_begin(), SI->op_end());1936    bool IsLogicalOr = match(this, m_LogicalOr(m_VPValue(Op0), m_VPValue(Op1)));1937    return Ctx.TTI.getArithmeticInstrCost(1938        IsLogicalOr ? Instruction::Or : Instruction::And, VectorTy,1939        Ctx.CostKind, {Op1VK, Op1VP}, {Op2VK, Op2VP}, Operands, SI);1940  }1941 1942  Type *CondTy = Ctx.Types.inferScalarType(getOperand(0));1943  if (!ScalarCond)1944    CondTy = VectorType::get(CondTy, VF);1945 1946  CmpInst::Predicate Pred = CmpInst::BAD_ICMP_PREDICATE;1947  if (auto *Cmp = dyn_cast<CmpInst>(SI->getCondition()))1948    Pred = Cmp->getPredicate();1949  return Ctx.TTI.getCmpSelInstrCost(1950      Instruction::Select, VectorTy, CondTy, Pred, Ctx.CostKind,1951      {TTI::OK_AnyValue, TTI::OP_None}, {TTI::OK_AnyValue, TTI::OP_None}, SI);1952}1953 1954VPIRFlags::FastMathFlagsTy::FastMathFlagsTy(const FastMathFlags &FMF) {1955  AllowReassoc = FMF.allowReassoc();1956  NoNaNs = FMF.noNaNs();1957  NoInfs = FMF.noInfs();1958  NoSignedZeros = FMF.noSignedZeros();1959  AllowReciprocal = FMF.allowReciprocal();1960  AllowContract = FMF.allowContract();1961  ApproxFunc = FMF.approxFunc();1962}1963 1964#if !defined(NDEBUG)1965bool VPIRFlags::flagsValidForOpcode(unsigned Opcode) const {1966  switch (OpType) {1967  case OperationType::OverflowingBinOp:1968    return Opcode == Instruction::Add || Opcode == Instruction::Sub ||1969           Opcode == Instruction::Mul || Opcode == Instruction::Shl ||1970           Opcode == VPInstruction::VPInstruction::CanonicalIVIncrementForPart;1971  case OperationType::Trunc:1972    return Opcode == Instruction::Trunc;1973  case OperationType::DisjointOp:1974    return Opcode == Instruction::Or;1975  case OperationType::PossiblyExactOp:1976    return Opcode == Instruction::AShr || Opcode == Instruction::LShr ||1977           Opcode == Instruction::UDiv || Opcode == Instruction::SDiv;1978  case OperationType::GEPOp:1979    return Opcode == Instruction::GetElementPtr ||1980           Opcode == VPInstruction::PtrAdd ||1981           Opcode == VPInstruction::WidePtrAdd;1982  case OperationType::FPMathOp:1983    return Opcode == Instruction::Call || Opcode == Instruction::FAdd ||1984           Opcode == Instruction::FMul || Opcode == Instruction::FSub ||1985           Opcode == Instruction::FNeg || Opcode == Instruction::FDiv ||1986           Opcode == Instruction::FRem || Opcode == Instruction::FPExt ||1987           Opcode == Instruction::FPTrunc || Opcode == Instruction::Select ||1988           Opcode == VPInstruction::WideIVStep ||1989           Opcode == VPInstruction::ReductionStartVector ||1990           Opcode == VPInstruction::ComputeReductionResult;1991  case OperationType::FCmp:1992    return Opcode == Instruction::FCmp;1993  case OperationType::NonNegOp:1994    return Opcode == Instruction::ZExt || Opcode == Instruction::UIToFP;1995  case OperationType::Cmp:1996    return Opcode == Instruction::FCmp || Opcode == Instruction::ICmp;1997  case OperationType::Other:1998    return true;1999  }2000  llvm_unreachable("Unknown OperationType enum");2001}2002#endif2003 2004#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)2005void VPIRFlags::printFlags(raw_ostream &O) const {2006  switch (OpType) {2007  case OperationType::Cmp:2008    O << " " << CmpInst::getPredicateName(getPredicate());2009    break;2010  case OperationType::FCmp:2011    O << " " << CmpInst::getPredicateName(getPredicate());2012    getFastMathFlags().print(O);2013    break;2014  case OperationType::DisjointOp:2015    if (DisjointFlags.IsDisjoint)2016      O << " disjoint";2017    break;2018  case OperationType::PossiblyExactOp:2019    if (ExactFlags.IsExact)2020      O << " exact";2021    break;2022  case OperationType::OverflowingBinOp:2023    if (WrapFlags.HasNUW)2024      O << " nuw";2025    if (WrapFlags.HasNSW)2026      O << " nsw";2027    break;2028  case OperationType::Trunc:2029    if (TruncFlags.HasNUW)2030      O << " nuw";2031    if (TruncFlags.HasNSW)2032      O << " nsw";2033    break;2034  case OperationType::FPMathOp:2035    getFastMathFlags().print(O);2036    break;2037  case OperationType::GEPOp:2038    if (GEPFlags.isInBounds())2039      O << " inbounds";2040    else if (GEPFlags.hasNoUnsignedSignedWrap())2041      O << " nusw";2042    if (GEPFlags.hasNoUnsignedWrap())2043      O << " nuw";2044    break;2045  case OperationType::NonNegOp:2046    if (NonNegFlags.NonNeg)2047      O << " nneg";2048    break;2049  case OperationType::Other:2050    break;2051  }2052  O << " ";2053}2054#endif2055 2056void VPWidenRecipe::execute(VPTransformState &State) {2057  auto &Builder = State.Builder;2058  switch (Opcode) {2059  case Instruction::Call:2060  case Instruction::Br:2061  case Instruction::PHI:2062  case Instruction::GetElementPtr:2063  case Instruction::Select:2064    llvm_unreachable("This instruction is handled by a different recipe.");2065  case Instruction::UDiv:2066  case Instruction::SDiv:2067  case Instruction::SRem:2068  case Instruction::URem:2069  case Instruction::Add:2070  case Instruction::FAdd:2071  case Instruction::Sub:2072  case Instruction::FSub:2073  case Instruction::FNeg:2074  case Instruction::Mul:2075  case Instruction::FMul:2076  case Instruction::FDiv:2077  case Instruction::FRem:2078  case Instruction::Shl:2079  case Instruction::LShr:2080  case Instruction::AShr:2081  case Instruction::And:2082  case Instruction::Or:2083  case Instruction::Xor: {2084    // Just widen unops and binops.2085    SmallVector<Value *, 2> Ops;2086    for (VPValue *VPOp : operands())2087      Ops.push_back(State.get(VPOp));2088 2089    Value *V = Builder.CreateNAryOp(Opcode, Ops);2090 2091    if (auto *VecOp = dyn_cast<Instruction>(V)) {2092      applyFlags(*VecOp);2093      applyMetadata(*VecOp);2094    }2095 2096    // Use this vector value for all users of the original instruction.2097    State.set(this, V);2098    break;2099  }2100  case Instruction::ExtractValue: {2101    assert(getNumOperands() == 2 && "expected single level extractvalue");2102    Value *Op = State.get(getOperand(0));2103    auto *CI = cast<ConstantInt>(getOperand(1)->getLiveInIRValue());2104    Value *Extract = Builder.CreateExtractValue(Op, CI->getZExtValue());2105    State.set(this, Extract);2106    break;2107  }2108  case Instruction::Freeze: {2109    Value *Op = State.get(getOperand(0));2110    Value *Freeze = Builder.CreateFreeze(Op);2111    State.set(this, Freeze);2112    break;2113  }2114  case Instruction::ICmp:2115  case Instruction::FCmp: {2116    // Widen compares. Generate vector compares.2117    bool FCmp = Opcode == Instruction::FCmp;2118    Value *A = State.get(getOperand(0));2119    Value *B = State.get(getOperand(1));2120    Value *C = nullptr;2121    if (FCmp) {2122      C = Builder.CreateFCmp(getPredicate(), A, B);2123    } else {2124      C = Builder.CreateICmp(getPredicate(), A, B);2125    }2126    if (auto *I = dyn_cast<Instruction>(C)) {2127      applyFlags(*I);2128      applyMetadata(*I);2129    }2130    State.set(this, C);2131    break;2132  }2133  default:2134    // This instruction is not vectorized by simple widening.2135    LLVM_DEBUG(dbgs() << "LV: Found an unhandled opcode : "2136                      << Instruction::getOpcodeName(Opcode));2137    llvm_unreachable("Unhandled instruction!");2138  } // end of switch.2139 2140#if !defined(NDEBUG)2141  // Verify that VPlan type inference results agree with the type of the2142  // generated values.2143  assert(VectorType::get(State.TypeAnalysis.inferScalarType(this), State.VF) ==2144             State.get(this)->getType() &&2145         "inferred type and type from generated instructions do not match");2146#endif2147}2148 2149InstructionCost VPWidenRecipe::computeCost(ElementCount VF,2150                                           VPCostContext &Ctx) const {2151  switch (Opcode) {2152  case Instruction::UDiv:2153  case Instruction::SDiv:2154  case Instruction::SRem:2155  case Instruction::URem:2156    // If the div/rem operation isn't safe to speculate and requires2157    // predication, then the only way we can even create a vplan is to insert2158    // a select on the second input operand to ensure we use the value of 12159    // for the inactive lanes. The select will be costed separately.2160  case Instruction::FNeg:2161  case Instruction::Add:2162  case Instruction::FAdd:2163  case Instruction::Sub:2164  case Instruction::FSub:2165  case Instruction::Mul:2166  case Instruction::FMul:2167  case Instruction::FDiv:2168  case Instruction::FRem:2169  case Instruction::Shl:2170  case Instruction::LShr:2171  case Instruction::AShr:2172  case Instruction::And:2173  case Instruction::Or:2174  case Instruction::Xor:2175  case Instruction::Freeze:2176  case Instruction::ExtractValue:2177  case Instruction::ICmp:2178  case Instruction::FCmp:2179    return getCostForRecipeWithOpcode(getOpcode(), VF, Ctx);2180  default:2181    llvm_unreachable("Unsupported opcode for instruction");2182  }2183}2184 2185#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)2186void VPWidenRecipe::printRecipe(raw_ostream &O, const Twine &Indent,2187                                VPSlotTracker &SlotTracker) const {2188  O << Indent << "WIDEN ";2189  printAsOperand(O, SlotTracker);2190  O << " = " << Instruction::getOpcodeName(Opcode);2191  printFlags(O);2192  printOperands(O, SlotTracker);2193}2194#endif2195 2196void VPWidenCastRecipe::execute(VPTransformState &State) {2197  auto &Builder = State.Builder;2198  /// Vectorize casts.2199  assert(State.VF.isVector() && "Not vectorizing?");2200  Type *DestTy = VectorType::get(getResultType(), State.VF);2201  VPValue *Op = getOperand(0);2202  Value *A = State.get(Op);2203  Value *Cast = Builder.CreateCast(Instruction::CastOps(Opcode), A, DestTy);2204  State.set(this, Cast);2205  if (auto *CastOp = dyn_cast<Instruction>(Cast)) {2206    applyFlags(*CastOp);2207    applyMetadata(*CastOp);2208  }2209}2210 2211InstructionCost VPWidenCastRecipe::computeCost(ElementCount VF,2212                                               VPCostContext &Ctx) const {2213  // TODO: In some cases, VPWidenCastRecipes are created but not considered in2214  // the legacy cost model, including truncates/extends when evaluating a2215  // reduction in a smaller type.2216  if (!getUnderlyingValue())2217    return 0;2218  // Computes the CastContextHint from a recipes that may access memory.2219  auto ComputeCCH = [&](const VPRecipeBase *R) -> TTI::CastContextHint {2220    if (VF.isScalar())2221      return TTI::CastContextHint::Normal;2222    if (isa<VPInterleaveBase>(R))2223      return TTI::CastContextHint::Interleave;2224    if (const auto *ReplicateRecipe = dyn_cast<VPReplicateRecipe>(R))2225      return ReplicateRecipe->isPredicated() ? TTI::CastContextHint::Masked2226                                             : TTI::CastContextHint::Normal;2227    const auto *WidenMemoryRecipe = dyn_cast<VPWidenMemoryRecipe>(R);2228    if (WidenMemoryRecipe == nullptr)2229      return TTI::CastContextHint::None;2230    if (!WidenMemoryRecipe->isConsecutive())2231      return TTI::CastContextHint::GatherScatter;2232    if (WidenMemoryRecipe->isReverse())2233      return TTI::CastContextHint::Reversed;2234    if (WidenMemoryRecipe->isMasked())2235      return TTI::CastContextHint::Masked;2236    return TTI::CastContextHint::Normal;2237  };2238 2239  VPValue *Operand = getOperand(0);2240  TTI::CastContextHint CCH = TTI::CastContextHint::None;2241  // For Trunc/FPTrunc, get the context from the only user.2242  if ((Opcode == Instruction::Trunc || Opcode == Instruction::FPTrunc) &&2243      !hasMoreThanOneUniqueUser() && getNumUsers() > 0) {2244    if (auto *StoreRecipe = dyn_cast<VPRecipeBase>(*user_begin()))2245      CCH = ComputeCCH(StoreRecipe);2246  }2247  // For Z/Sext, get the context from the operand.2248  else if (Opcode == Instruction::ZExt || Opcode == Instruction::SExt ||2249           Opcode == Instruction::FPExt) {2250    if (Operand->isLiveIn())2251      CCH = TTI::CastContextHint::Normal;2252    else if (Operand->getDefiningRecipe())2253      CCH = ComputeCCH(Operand->getDefiningRecipe());2254  }2255 2256  auto *SrcTy =2257      cast<VectorType>(toVectorTy(Ctx.Types.inferScalarType(Operand), VF));2258  auto *DestTy = cast<VectorType>(toVectorTy(getResultType(), VF));2259  // Arm TTI will use the underlying instruction to determine the cost.2260  return Ctx.TTI.getCastInstrCost(2261      Opcode, DestTy, SrcTy, CCH, Ctx.CostKind,2262      dyn_cast_if_present<Instruction>(getUnderlyingValue()));2263}2264 2265#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)2266void VPWidenCastRecipe::printRecipe(raw_ostream &O, const Twine &Indent,2267                                    VPSlotTracker &SlotTracker) const {2268  O << Indent << "WIDEN-CAST ";2269  printAsOperand(O, SlotTracker);2270  O << " = " << Instruction::getOpcodeName(Opcode);2271  printFlags(O);2272  printOperands(O, SlotTracker);2273  O << " to " << *getResultType();2274}2275#endif2276 2277InstructionCost VPHeaderPHIRecipe::computeCost(ElementCount VF,2278                                               VPCostContext &Ctx) const {2279  return Ctx.TTI.getCFInstrCost(Instruction::PHI, Ctx.CostKind);2280}2281 2282/// A helper function that returns an integer or floating-point constant with2283/// value C.2284static Constant *getSignedIntOrFpConstant(Type *Ty, int64_t C) {2285  return Ty->isIntegerTy() ? ConstantInt::getSigned(Ty, C)2286                           : ConstantFP::get(Ty, C);2287}2288 2289#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)2290void VPWidenIntOrFpInductionRecipe::printRecipe(2291    raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const {2292  O << Indent;2293  printAsOperand(O, SlotTracker);2294  O << " = WIDEN-INDUCTION";2295  printFlags(O);2296  O << " ";2297  printOperands(O, SlotTracker);2298 2299  if (auto *TI = getTruncInst())2300    O << " (truncated to " << *TI->getType() << ")";2301}2302#endif2303 2304bool VPWidenIntOrFpInductionRecipe::isCanonical() const {2305  // The step may be defined by a recipe in the preheader (e.g. if it requires2306  // SCEV expansion), but for the canonical induction the step is required to be2307  // 1, which is represented as live-in.2308  if (getStepValue()->getDefiningRecipe())2309    return false;2310  auto *StepC = dyn_cast<ConstantInt>(getStepValue()->getLiveInIRValue());2311  auto *StartC = dyn_cast<ConstantInt>(getStartValue()->getLiveInIRValue());2312  return StartC && StartC->isZero() && StepC && StepC->isOne() &&2313         getScalarType() == getRegion()->getCanonicalIVType();2314}2315 2316#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)2317void VPDerivedIVRecipe::printRecipe(raw_ostream &O, const Twine &Indent,2318                                    VPSlotTracker &SlotTracker) const {2319  O << Indent;2320  printAsOperand(O, SlotTracker);2321  O << " = DERIVED-IV ";2322  getStartValue()->printAsOperand(O, SlotTracker);2323  O << " + ";2324  getOperand(1)->printAsOperand(O, SlotTracker);2325  O << " * ";2326  getStepValue()->printAsOperand(O, SlotTracker);2327}2328#endif2329 2330void VPScalarIVStepsRecipe::execute(VPTransformState &State) {2331  // Fast-math-flags propagate from the original induction instruction.2332  IRBuilder<>::FastMathFlagGuard FMFG(State.Builder);2333  if (hasFastMathFlags())2334    State.Builder.setFastMathFlags(getFastMathFlags());2335 2336  /// Compute scalar induction steps. \p ScalarIV is the scalar induction2337  /// variable on which to base the steps, \p Step is the size of the step.2338 2339  Value *BaseIV = State.get(getOperand(0), VPLane(0));2340  Value *Step = State.get(getStepValue(), VPLane(0));2341  IRBuilderBase &Builder = State.Builder;2342 2343  // Ensure step has the same type as that of scalar IV.2344  Type *BaseIVTy = BaseIV->getType()->getScalarType();2345  assert(BaseIVTy == Step->getType() && "Types of BaseIV and Step must match!");2346 2347  // We build scalar steps for both integer and floating-point induction2348  // variables. Here, we determine the kind of arithmetic we will perform.2349  Instruction::BinaryOps AddOp;2350  Instruction::BinaryOps MulOp;2351  if (BaseIVTy->isIntegerTy()) {2352    AddOp = Instruction::Add;2353    MulOp = Instruction::Mul;2354  } else {2355    AddOp = InductionOpcode;2356    MulOp = Instruction::FMul;2357  }2358 2359  // Determine the number of scalars we need to generate for each unroll2360  // iteration.2361  bool FirstLaneOnly = vputils::onlyFirstLaneUsed(this);2362  // Compute the scalar steps and save the results in State.2363  Type *IntStepTy =2364      IntegerType::get(BaseIVTy->getContext(), BaseIVTy->getScalarSizeInBits());2365 2366  unsigned StartLane = 0;2367  unsigned EndLane = FirstLaneOnly ? 1 : State.VF.getKnownMinValue();2368  if (State.Lane) {2369    StartLane = State.Lane->getKnownLane();2370    EndLane = StartLane + 1;2371  }2372  Value *StartIdx0;2373  if (getUnrollPart(*this) == 0)2374    StartIdx0 = ConstantInt::get(IntStepTy, 0);2375  else {2376    StartIdx0 = State.get(getOperand(2), true);2377    if (getUnrollPart(*this) != 1) {2378      StartIdx0 =2379          Builder.CreateMul(StartIdx0, ConstantInt::get(StartIdx0->getType(),2380                                                        getUnrollPart(*this)));2381    }2382    StartIdx0 = Builder.CreateSExtOrTrunc(StartIdx0, IntStepTy);2383  }2384 2385  if (BaseIVTy->isFloatingPointTy())2386    StartIdx0 = Builder.CreateSIToFP(StartIdx0, BaseIVTy);2387 2388  for (unsigned Lane = StartLane; Lane < EndLane; ++Lane) {2389    Value *StartIdx = Builder.CreateBinOp(2390        AddOp, StartIdx0, getSignedIntOrFpConstant(BaseIVTy, Lane));2391    // The step returned by `createStepForVF` is a runtime-evaluated value2392    // when VF is scalable. Otherwise, it should be folded into a Constant.2393    assert((State.VF.isScalable() || isa<Constant>(StartIdx)) &&2394           "Expected StartIdx to be folded to a constant when VF is not "2395           "scalable");2396    auto *Mul = Builder.CreateBinOp(MulOp, StartIdx, Step);2397    auto *Add = Builder.CreateBinOp(AddOp, BaseIV, Mul);2398    State.set(this, Add, VPLane(Lane));2399  }2400}2401 2402#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)2403void VPScalarIVStepsRecipe::printRecipe(raw_ostream &O, const Twine &Indent,2404                                        VPSlotTracker &SlotTracker) const {2405  O << Indent;2406  printAsOperand(O, SlotTracker);2407  O << " = SCALAR-STEPS ";2408  printOperands(O, SlotTracker);2409}2410#endif2411 2412bool VPWidenGEPRecipe::usesFirstLaneOnly(const VPValue *Op) const {2413  assert(is_contained(operands(), Op) && "Op must be an operand of the recipe");2414  return vputils::isSingleScalar(Op);2415}2416 2417void VPWidenGEPRecipe::execute(VPTransformState &State) {2418  assert(State.VF.isVector() && "not widening");2419  // Construct a vector GEP by widening the operands of the scalar GEP as2420  // necessary. We mark the vector GEP 'inbounds' if appropriate. A GEP2421  // results in a vector of pointers when at least one operand of the GEP2422  // is vector-typed. Thus, to keep the representation compact, we only use2423  // vector-typed operands for loop-varying values.2424 2425  assert(2426      any_of(operands(),2427             [](VPValue *Op) { return !Op->isDefinedOutsideLoopRegions(); }) &&2428      "Expected at least one loop-variant operand");2429 2430  // If the GEP has at least one loop-varying operand, we are sure to2431  // produce a vector of pointers unless VF is scalar.2432  // The pointer operand of the new GEP. If it's loop-invariant, we2433  // won't broadcast it.2434  auto *Ptr = State.get(getOperand(0), isPointerLoopInvariant());2435 2436  // Collect all the indices for the new GEP. If any index is2437  // loop-invariant, we won't broadcast it.2438  SmallVector<Value *, 4> Indices;2439  for (unsigned I = 1, E = getNumOperands(); I < E; I++) {2440    VPValue *Operand = getOperand(I);2441    Indices.push_back(State.get(Operand, isIndexLoopInvariant(I - 1)));2442  }2443 2444  // Create the new GEP. Note that this GEP may be a scalar if VF == 1,2445  // but it should be a vector, otherwise.2446  auto *NewGEP = State.Builder.CreateGEP(getSourceElementType(), Ptr, Indices,2447                                         "", getGEPNoWrapFlags());2448  assert((State.VF.isScalar() || NewGEP->getType()->isVectorTy()) &&2449         "NewGEP is not a pointer vector");2450  State.set(this, NewGEP);2451}2452 2453#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)2454void VPWidenGEPRecipe::printRecipe(raw_ostream &O, const Twine &Indent,2455                                   VPSlotTracker &SlotTracker) const {2456  O << Indent << "WIDEN-GEP ";2457  O << (isPointerLoopInvariant() ? "Inv" : "Var");2458  for (size_t I = 0; I < getNumOperands() - 1; ++I)2459    O << "[" << (isIndexLoopInvariant(I) ? "Inv" : "Var") << "]";2460 2461  O << " ";2462  printAsOperand(O, SlotTracker);2463  O << " = getelementptr";2464  printFlags(O);2465  printOperands(O, SlotTracker);2466}2467#endif2468 2469void VPVectorEndPointerRecipe::execute(VPTransformState &State) {2470  auto &Builder = State.Builder;2471  unsigned CurrentPart = getUnrollPart(*this);2472  const DataLayout &DL = Builder.GetInsertBlock()->getDataLayout();2473  Type *IndexTy = DL.getIndexType(State.TypeAnalysis.inferScalarType(this));2474 2475  // The wide store needs to start at the last vector element.2476  Value *RunTimeVF = State.get(getVFValue(), VPLane(0));2477  if (IndexTy != RunTimeVF->getType())2478    RunTimeVF = Builder.CreateZExtOrTrunc(RunTimeVF, IndexTy);2479  // NumElt = Stride * CurrentPart * RunTimeVF2480  Value *NumElt = Builder.CreateMul(2481      ConstantInt::get(IndexTy, Stride * (int64_t)CurrentPart), RunTimeVF);2482  // LastLane = Stride * (RunTimeVF - 1)2483  Value *LastLane = Builder.CreateSub(RunTimeVF, ConstantInt::get(IndexTy, 1));2484  if (Stride != 1)2485    LastLane = Builder.CreateMul(ConstantInt::get(IndexTy, Stride), LastLane);2486  Value *Ptr = State.get(getOperand(0), VPLane(0));2487  Value *ResultPtr =2488      Builder.CreateGEP(IndexedTy, Ptr, NumElt, "", getGEPNoWrapFlags());2489  ResultPtr = Builder.CreateGEP(IndexedTy, ResultPtr, LastLane, "",2490                                getGEPNoWrapFlags());2491 2492  State.set(this, ResultPtr, /*IsScalar*/ true);2493}2494 2495#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)2496void VPVectorEndPointerRecipe::printRecipe(raw_ostream &O, const Twine &Indent,2497                                           VPSlotTracker &SlotTracker) const {2498  O << Indent;2499  printAsOperand(O, SlotTracker);2500  O << " = vector-end-pointer";2501  printFlags(O);2502  printOperands(O, SlotTracker);2503}2504#endif2505 2506void VPVectorPointerRecipe::execute(VPTransformState &State) {2507  auto &Builder = State.Builder;2508  unsigned CurrentPart = getUnrollPart(*this);2509  const DataLayout &DL = Builder.GetInsertBlock()->getDataLayout();2510  Type *IndexTy = DL.getIndexType(State.TypeAnalysis.inferScalarType(this));2511  Value *Ptr = State.get(getOperand(0), VPLane(0));2512 2513  Value *Increment = createStepForVF(Builder, IndexTy, State.VF, CurrentPart);2514  Value *ResultPtr = Builder.CreateGEP(getSourceElementType(), Ptr, Increment,2515                                       "", getGEPNoWrapFlags());2516 2517  State.set(this, ResultPtr, /*IsScalar*/ true);2518}2519 2520#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)2521void VPVectorPointerRecipe::printRecipe(raw_ostream &O, const Twine &Indent,2522                                        VPSlotTracker &SlotTracker) const {2523  O << Indent;2524  printAsOperand(O, SlotTracker);2525  O << " = vector-pointer ";2526  printFlags(O);2527  printOperands(O, SlotTracker);2528}2529#endif2530 2531InstructionCost VPBlendRecipe::computeCost(ElementCount VF,2532                                           VPCostContext &Ctx) const {2533  // Handle cases where only the first lane is used the same way as the legacy2534  // cost model.2535  if (vputils::onlyFirstLaneUsed(this))2536    return Ctx.TTI.getCFInstrCost(Instruction::PHI, Ctx.CostKind);2537 2538  Type *ResultTy = toVectorTy(Ctx.Types.inferScalarType(this), VF);2539  Type *CmpTy = toVectorTy(Type::getInt1Ty(Ctx.Types.getContext()), VF);2540  return (getNumIncomingValues() - 1) *2541         Ctx.TTI.getCmpSelInstrCost(Instruction::Select, ResultTy, CmpTy,2542                                    CmpInst::BAD_ICMP_PREDICATE, Ctx.CostKind);2543}2544 2545#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)2546void VPBlendRecipe::printRecipe(raw_ostream &O, const Twine &Indent,2547                                VPSlotTracker &SlotTracker) const {2548  O << Indent << "BLEND ";2549  printAsOperand(O, SlotTracker);2550  O << " =";2551  if (getNumIncomingValues() == 1) {2552    // Not a User of any mask: not really blending, this is a2553    // single-predecessor phi.2554    O << " ";2555    getIncomingValue(0)->printAsOperand(O, SlotTracker);2556  } else {2557    for (unsigned I = 0, E = getNumIncomingValues(); I < E; ++I) {2558      O << " ";2559      getIncomingValue(I)->printAsOperand(O, SlotTracker);2560      if (I == 0)2561        continue;2562      O << "/";2563      getMask(I)->printAsOperand(O, SlotTracker);2564    }2565  }2566}2567#endif2568 2569void VPReductionRecipe::execute(VPTransformState &State) {2570  assert(!State.Lane && "Reduction being replicated.");2571  RecurKind Kind = getRecurrenceKind();2572  assert(!RecurrenceDescriptor::isAnyOfRecurrenceKind(Kind) &&2573         "In-loop AnyOf reductions aren't currently supported");2574  // Propagate the fast-math flags carried by the underlying instruction.2575  IRBuilderBase::FastMathFlagGuard FMFGuard(State.Builder);2576  State.Builder.setFastMathFlags(getFastMathFlags());2577  Value *NewVecOp = State.get(getVecOp());2578  if (VPValue *Cond = getCondOp()) {2579    Value *NewCond = State.get(Cond, State.VF.isScalar());2580    VectorType *VecTy = dyn_cast<VectorType>(NewVecOp->getType());2581    Type *ElementTy = VecTy ? VecTy->getElementType() : NewVecOp->getType();2582 2583    Value *Start = getRecurrenceIdentity(Kind, ElementTy, getFastMathFlags());2584    if (State.VF.isVector())2585      Start = State.Builder.CreateVectorSplat(VecTy->getElementCount(), Start);2586 2587    Value *Select = State.Builder.CreateSelect(NewCond, NewVecOp, Start);2588    NewVecOp = Select;2589  }2590  Value *NewRed;2591  Value *NextInChain;2592  if (isOrdered()) {2593    Value *PrevInChain = State.get(getChainOp(), /*IsScalar*/ true);2594    if (State.VF.isVector())2595      NewRed =2596          createOrderedReduction(State.Builder, Kind, NewVecOp, PrevInChain);2597    else2598      NewRed = State.Builder.CreateBinOp(2599          (Instruction::BinaryOps)RecurrenceDescriptor::getOpcode(Kind),2600          PrevInChain, NewVecOp);2601    PrevInChain = NewRed;2602    NextInChain = NewRed;2603  } else if (isPartialReduction()) {2604    assert(Kind == RecurKind::Add && "Unexpected partial reduction kind");2605    Value *PrevInChain = State.get(getChainOp(), /*IsScalar*/ false);2606    NewRed = State.Builder.CreateIntrinsic(2607        PrevInChain->getType(), Intrinsic::vector_partial_reduce_add,2608        {PrevInChain, NewVecOp}, nullptr, "partial.reduce");2609    PrevInChain = NewRed;2610    NextInChain = NewRed;2611  } else {2612    assert(isInLoop() &&2613           "The reduction must either be ordered, partial or in-loop");2614    Value *PrevInChain = State.get(getChainOp(), /*IsScalar*/ true);2615    NewRed = createSimpleReduction(State.Builder, NewVecOp, Kind);2616    if (RecurrenceDescriptor::isMinMaxRecurrenceKind(Kind))2617      NextInChain = createMinMaxOp(State.Builder, Kind, NewRed, PrevInChain);2618    else2619      NextInChain = State.Builder.CreateBinOp(2620          (Instruction::BinaryOps)RecurrenceDescriptor::getOpcode(Kind),2621          PrevInChain, NewRed);2622  }2623  State.set(this, NextInChain, /*IsScalar*/ !isPartialReduction());2624}2625 2626void VPReductionEVLRecipe::execute(VPTransformState &State) {2627  assert(!State.Lane && "Reduction being replicated.");2628 2629  auto &Builder = State.Builder;2630  // Propagate the fast-math flags carried by the underlying instruction.2631  IRBuilderBase::FastMathFlagGuard FMFGuard(Builder);2632  Builder.setFastMathFlags(getFastMathFlags());2633 2634  RecurKind Kind = getRecurrenceKind();2635  Value *Prev = State.get(getChainOp(), /*IsScalar*/ true);2636  Value *VecOp = State.get(getVecOp());2637  Value *EVL = State.get(getEVL(), VPLane(0));2638 2639  Value *Mask;2640  if (VPValue *CondOp = getCondOp())2641    Mask = State.get(CondOp);2642  else2643    Mask = Builder.CreateVectorSplat(State.VF, Builder.getTrue());2644 2645  Value *NewRed;2646  if (isOrdered()) {2647    NewRed = createOrderedReduction(Builder, Kind, VecOp, Prev, Mask, EVL);2648  } else {2649    NewRed = createSimpleReduction(Builder, VecOp, Kind, Mask, EVL);2650    if (RecurrenceDescriptor::isMinMaxRecurrenceKind(Kind))2651      NewRed = createMinMaxOp(Builder, Kind, NewRed, Prev);2652    else2653      NewRed = Builder.CreateBinOp(2654          (Instruction::BinaryOps)RecurrenceDescriptor::getOpcode(Kind), NewRed,2655          Prev);2656  }2657  State.set(this, NewRed, /*IsScalar*/ true);2658}2659 2660InstructionCost VPReductionRecipe::computeCost(ElementCount VF,2661                                               VPCostContext &Ctx) const {2662  RecurKind RdxKind = getRecurrenceKind();2663  Type *ElementTy = Ctx.Types.inferScalarType(this);2664  auto *VectorTy = cast<VectorType>(toVectorTy(ElementTy, VF));2665  unsigned Opcode = RecurrenceDescriptor::getOpcode(RdxKind);2666  FastMathFlags FMFs = getFastMathFlags();2667  std::optional<FastMathFlags> OptionalFMF =2668      ElementTy->isFloatingPointTy() ? std::make_optional(FMFs) : std::nullopt;2669 2670  if (isPartialReduction()) {2671    InstructionCost CondCost = 0;2672    if (isConditional()) {2673      CmpInst::Predicate Pred = CmpInst::BAD_ICMP_PREDICATE;2674      auto *CondTy = cast<VectorType>(2675          toVectorTy(Ctx.Types.inferScalarType(getCondOp()), VF));2676      CondCost = Ctx.TTI.getCmpSelInstrCost(Instruction::Select, VectorTy,2677                                            CondTy, Pred, Ctx.CostKind);2678    }2679    return CondCost + Ctx.TTI.getPartialReductionCost(2680                          Opcode, ElementTy, ElementTy, ElementTy, VF,2681                          TargetTransformInfo::PR_None,2682                          TargetTransformInfo::PR_None, std::nullopt,2683                          Ctx.CostKind);2684  }2685 2686  // TODO: Support any-of reductions.2687  assert(2688      (!RecurrenceDescriptor::isAnyOfRecurrenceKind(RdxKind) ||2689       ForceTargetInstructionCost.getNumOccurrences() > 0) &&2690      "Any-of reduction not implemented in VPlan-based cost model currently.");2691 2692  // Note that TTI should model the cost of moving result to the scalar register2693  // and the BinOp cost in the getMinMaxReductionCost().2694  if (RecurrenceDescriptor::isMinMaxRecurrenceKind(RdxKind)) {2695    Intrinsic::ID Id = getMinMaxReductionIntrinsicOp(RdxKind);2696    return Ctx.TTI.getMinMaxReductionCost(Id, VectorTy, FMFs, Ctx.CostKind);2697  }2698 2699  // Note that TTI should model the cost of moving result to the scalar register2700  // and the BinOp cost in the getArithmeticReductionCost().2701  return Ctx.TTI.getArithmeticReductionCost(Opcode, VectorTy, OptionalFMF,2702                                            Ctx.CostKind);2703}2704 2705VPExpressionRecipe::VPExpressionRecipe(2706    ExpressionTypes ExpressionType,2707    ArrayRef<VPSingleDefRecipe *> ExpressionRecipes)2708    : VPSingleDefRecipe(VPDef::VPExpressionSC, {}, {}),2709      ExpressionRecipes(ExpressionRecipes), ExpressionType(ExpressionType) {2710  assert(!ExpressionRecipes.empty() && "Nothing to combine?");2711  assert(2712      none_of(ExpressionRecipes,2713              [](VPSingleDefRecipe *R) { return R->mayHaveSideEffects(); }) &&2714      "expression cannot contain recipes with side-effects");2715 2716  // Maintain a copy of the expression recipes as a set of users.2717  SmallPtrSet<VPUser *, 4> ExpressionRecipesAsSetOfUsers;2718  for (auto *R : ExpressionRecipes)2719    ExpressionRecipesAsSetOfUsers.insert(R);2720 2721  // Recipes in the expression, except the last one, must only be used by2722  // (other) recipes inside the expression. If there are other users, external2723  // to the expression, use a clone of the recipe for external users.2724  for (VPSingleDefRecipe *R : reverse(ExpressionRecipes)) {2725    if (R != ExpressionRecipes.back() &&2726        any_of(R->users(), [&ExpressionRecipesAsSetOfUsers](VPUser *U) {2727          return !ExpressionRecipesAsSetOfUsers.contains(U);2728        })) {2729      // There are users outside of the expression. Clone the recipe and use the2730      // clone those external users.2731      VPSingleDefRecipe *CopyForExtUsers = R->clone();2732      R->replaceUsesWithIf(CopyForExtUsers, [&ExpressionRecipesAsSetOfUsers](2733                                                VPUser &U, unsigned) {2734        return !ExpressionRecipesAsSetOfUsers.contains(&U);2735      });2736      CopyForExtUsers->insertBefore(R);2737    }2738    if (R->getParent())2739      R->removeFromParent();2740  }2741 2742  // Internalize all external operands to the expression recipes. To do so,2743  // create new temporary VPValues for all operands defined by a recipe outside2744  // the expression. The original operands are added as operands of the2745  // VPExpressionRecipe itself.2746  for (auto *R : ExpressionRecipes) {2747    for (const auto &[Idx, Op] : enumerate(R->operands())) {2748      auto *Def = Op->getDefiningRecipe();2749      if (Def && ExpressionRecipesAsSetOfUsers.contains(Def))2750        continue;2751      addOperand(Op);2752      LiveInPlaceholders.push_back(new VPValue());2753    }2754  }2755 2756  // Replace each external operand with the first one created for it in2757  // LiveInPlaceholders.2758  for (auto *R : ExpressionRecipes)2759    for (auto const &[LiveIn, Tmp] : zip(operands(), LiveInPlaceholders))2760      R->replaceUsesOfWith(LiveIn, Tmp);2761}2762 2763void VPExpressionRecipe::decompose() {2764  for (auto *R : ExpressionRecipes)2765    // Since the list could contain duplicates, make sure the recipe hasn't2766    // already been inserted.2767    if (!R->getParent())2768      R->insertBefore(this);2769 2770  for (const auto &[Idx, Op] : enumerate(operands()))2771    LiveInPlaceholders[Idx]->replaceAllUsesWith(Op);2772 2773  replaceAllUsesWith(ExpressionRecipes.back());2774  ExpressionRecipes.clear();2775}2776 2777InstructionCost VPExpressionRecipe::computeCost(ElementCount VF,2778                                                VPCostContext &Ctx) const {2779  Type *RedTy = Ctx.Types.inferScalarType(this);2780  auto *SrcVecTy = cast<VectorType>(2781      toVectorTy(Ctx.Types.inferScalarType(getOperand(0)), VF));2782  assert(RedTy->isIntegerTy() &&2783         "VPExpressionRecipe only supports integer types currently.");2784  unsigned Opcode = RecurrenceDescriptor::getOpcode(2785      cast<VPReductionRecipe>(ExpressionRecipes.back())->getRecurrenceKind());2786  switch (ExpressionType) {2787  case ExpressionTypes::ExtendedReduction: {2788    unsigned Opcode = RecurrenceDescriptor::getOpcode(2789        cast<VPReductionRecipe>(ExpressionRecipes[1])->getRecurrenceKind());2790    auto *ExtR = cast<VPWidenCastRecipe>(ExpressionRecipes[0]);2791 2792    return cast<VPReductionRecipe>(ExpressionRecipes.back())2793                   ->isPartialReduction()2794               ? Ctx.TTI.getPartialReductionCost(2795                     Opcode, Ctx.Types.inferScalarType(getOperand(0)), nullptr,2796                     RedTy, VF,2797                     TargetTransformInfo::getPartialReductionExtendKind(2798                         ExtR->getOpcode()),2799                     TargetTransformInfo::PR_None, std::nullopt, Ctx.CostKind)2800               : Ctx.TTI.getExtendedReductionCost(2801                     Opcode, ExtR->getOpcode() == Instruction::ZExt, RedTy,2802                     SrcVecTy, std::nullopt, Ctx.CostKind);2803  }2804  case ExpressionTypes::MulAccReduction:2805    return Ctx.TTI.getMulAccReductionCost(false, Opcode, RedTy, SrcVecTy,2806                                          Ctx.CostKind);2807 2808  case ExpressionTypes::ExtNegatedMulAccReduction:2809    assert(Opcode == Instruction::Add && "Unexpected opcode");2810    Opcode = Instruction::Sub;2811    [[fallthrough]];2812  case ExpressionTypes::ExtMulAccReduction: {2813    auto *RedR = cast<VPReductionRecipe>(ExpressionRecipes.back());2814    if (RedR->isPartialReduction()) {2815      auto *Ext0R = cast<VPWidenCastRecipe>(ExpressionRecipes[0]);2816      auto *Ext1R = cast<VPWidenCastRecipe>(ExpressionRecipes[1]);2817      auto *Mul = cast<VPWidenRecipe>(ExpressionRecipes[2]);2818      return Ctx.TTI.getPartialReductionCost(2819          Opcode, Ctx.Types.inferScalarType(getOperand(0)),2820          Ctx.Types.inferScalarType(getOperand(1)), RedTy, VF,2821          TargetTransformInfo::getPartialReductionExtendKind(2822              Ext0R->getOpcode()),2823          TargetTransformInfo::getPartialReductionExtendKind(2824              Ext1R->getOpcode()),2825          Mul->getOpcode(), Ctx.CostKind);2826    }2827    return Ctx.TTI.getMulAccReductionCost(2828        cast<VPWidenCastRecipe>(ExpressionRecipes.front())->getOpcode() ==2829            Instruction::ZExt,2830        Opcode, RedTy, SrcVecTy, Ctx.CostKind);2831  }2832  }2833  llvm_unreachable("Unknown VPExpressionRecipe::ExpressionTypes enum");2834}2835 2836bool VPExpressionRecipe::mayReadOrWriteMemory() const {2837  return any_of(ExpressionRecipes, [](VPSingleDefRecipe *R) {2838    return R->mayReadFromMemory() || R->mayWriteToMemory();2839  });2840}2841 2842bool VPExpressionRecipe::mayHaveSideEffects() const {2843  assert(2844      none_of(ExpressionRecipes,2845              [](VPSingleDefRecipe *R) { return R->mayHaveSideEffects(); }) &&2846      "expression cannot contain recipes with side-effects");2847  return false;2848}2849 2850bool VPExpressionRecipe::isSingleScalar() const {2851  // Cannot use vputils::isSingleScalar(), because all external operands2852  // of the expression will be live-ins while bundled.2853  auto *RR = dyn_cast<VPReductionRecipe>(ExpressionRecipes.back());2854  return RR && !RR->isPartialReduction();2855}2856 2857#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)2858 2859void VPExpressionRecipe::printRecipe(raw_ostream &O, const Twine &Indent,2860                                     VPSlotTracker &SlotTracker) const {2861  O << Indent << "EXPRESSION ";2862  printAsOperand(O, SlotTracker);2863  O << " = ";2864  auto *Red = cast<VPReductionRecipe>(ExpressionRecipes.back());2865  unsigned Opcode = RecurrenceDescriptor::getOpcode(Red->getRecurrenceKind());2866 2867  switch (ExpressionType) {2868  case ExpressionTypes::ExtendedReduction: {2869    getOperand(1)->printAsOperand(O, SlotTracker);2870    O << " + " << (Red->isPartialReduction() ? "partial." : "") << "reduce.";2871    O << Instruction::getOpcodeName(Opcode) << " (";2872    getOperand(0)->printAsOperand(O, SlotTracker);2873    Red->printFlags(O);2874 2875    auto *Ext0 = cast<VPWidenCastRecipe>(ExpressionRecipes[0]);2876    O << Instruction::getOpcodeName(Ext0->getOpcode()) << " to "2877      << *Ext0->getResultType();2878    if (Red->isConditional()) {2879      O << ", ";2880      Red->getCondOp()->printAsOperand(O, SlotTracker);2881    }2882    O << ")";2883    break;2884  }2885  case ExpressionTypes::ExtNegatedMulAccReduction: {2886    getOperand(getNumOperands() - 1)->printAsOperand(O, SlotTracker);2887    O << " + " << (Red->isPartialReduction() ? "partial." : "") << "reduce.";2888    O << Instruction::getOpcodeName(2889             RecurrenceDescriptor::getOpcode(Red->getRecurrenceKind()))2890      << " (sub (0, mul";2891    auto *Mul = cast<VPWidenRecipe>(ExpressionRecipes[2]);2892    Mul->printFlags(O);2893    O << "(";2894    getOperand(0)->printAsOperand(O, SlotTracker);2895    auto *Ext0 = cast<VPWidenCastRecipe>(ExpressionRecipes[0]);2896    O << " " << Instruction::getOpcodeName(Ext0->getOpcode()) << " to "2897      << *Ext0->getResultType() << "), (";2898    getOperand(1)->printAsOperand(O, SlotTracker);2899    auto *Ext1 = cast<VPWidenCastRecipe>(ExpressionRecipes[1]);2900    O << " " << Instruction::getOpcodeName(Ext1->getOpcode()) << " to "2901      << *Ext1->getResultType() << ")";2902    if (Red->isConditional()) {2903      O << ", ";2904      Red->getCondOp()->printAsOperand(O, SlotTracker);2905    }2906    O << "))";2907    break;2908  }2909  case ExpressionTypes::MulAccReduction:2910  case ExpressionTypes::ExtMulAccReduction: {2911    getOperand(getNumOperands() - 1)->printAsOperand(O, SlotTracker);2912    O << " + " << (Red->isPartialReduction() ? "partial." : "") << "reduce.";2913    O << Instruction::getOpcodeName(2914             RecurrenceDescriptor::getOpcode(Red->getRecurrenceKind()))2915      << " (";2916    O << "mul";2917    bool IsExtended = ExpressionType == ExpressionTypes::ExtMulAccReduction;2918    auto *Mul = cast<VPWidenRecipe>(IsExtended ? ExpressionRecipes[2]2919                                               : ExpressionRecipes[0]);2920    Mul->printFlags(O);2921    if (IsExtended)2922      O << "(";2923    getOperand(0)->printAsOperand(O, SlotTracker);2924    if (IsExtended) {2925      auto *Ext0 = cast<VPWidenCastRecipe>(ExpressionRecipes[0]);2926      O << " " << Instruction::getOpcodeName(Ext0->getOpcode()) << " to "2927        << *Ext0->getResultType() << "), (";2928    } else {2929      O << ", ";2930    }2931    getOperand(1)->printAsOperand(O, SlotTracker);2932    if (IsExtended) {2933      auto *Ext1 = cast<VPWidenCastRecipe>(ExpressionRecipes[1]);2934      O << " " << Instruction::getOpcodeName(Ext1->getOpcode()) << " to "2935        << *Ext1->getResultType() << ")";2936    }2937    if (Red->isConditional()) {2938      O << ", ";2939      Red->getCondOp()->printAsOperand(O, SlotTracker);2940    }2941    O << ")";2942    break;2943  }2944  }2945}2946 2947void VPReductionRecipe::printRecipe(raw_ostream &O, const Twine &Indent,2948                                    VPSlotTracker &SlotTracker) const {2949  if (isPartialReduction())2950    O << Indent << "PARTIAL-REDUCE ";2951  else2952    O << Indent << "REDUCE ";2953  printAsOperand(O, SlotTracker);2954  O << " = ";2955  getChainOp()->printAsOperand(O, SlotTracker);2956  O << " +";2957  printFlags(O);2958  O << " reduce."2959    << Instruction::getOpcodeName(2960           RecurrenceDescriptor::getOpcode(getRecurrenceKind()))2961    << " (";2962  getVecOp()->printAsOperand(O, SlotTracker);2963  if (isConditional()) {2964    O << ", ";2965    getCondOp()->printAsOperand(O, SlotTracker);2966  }2967  O << ")";2968}2969 2970void VPReductionEVLRecipe::printRecipe(raw_ostream &O, const Twine &Indent,2971                                       VPSlotTracker &SlotTracker) const {2972  O << Indent << "REDUCE ";2973  printAsOperand(O, SlotTracker);2974  O << " = ";2975  getChainOp()->printAsOperand(O, SlotTracker);2976  O << " +";2977  printFlags(O);2978  O << " vp.reduce."2979    << Instruction::getOpcodeName(2980           RecurrenceDescriptor::getOpcode(getRecurrenceKind()))2981    << " (";2982  getVecOp()->printAsOperand(O, SlotTracker);2983  O << ", ";2984  getEVL()->printAsOperand(O, SlotTracker);2985  if (isConditional()) {2986    O << ", ";2987    getCondOp()->printAsOperand(O, SlotTracker);2988  }2989  O << ")";2990}2991 2992#endif2993 2994/// A helper function to scalarize a single Instruction in the innermost loop.2995/// Generates a sequence of scalar instances for lane \p Lane. Uses the VPValue2996/// operands from \p RepRecipe instead of \p Instr's operands.2997static void scalarizeInstruction(const Instruction *Instr,2998                                 VPReplicateRecipe *RepRecipe,2999                                 const VPLane &Lane, VPTransformState &State) {3000  assert((!Instr->getType()->isAggregateType() ||3001          canVectorizeTy(Instr->getType())) &&3002         "Expected vectorizable or non-aggregate type.");3003 3004  // Does this instruction return a value ?3005  bool IsVoidRetTy = Instr->getType()->isVoidTy();3006 3007  Instruction *Cloned = Instr->clone();3008  if (!IsVoidRetTy) {3009    Cloned->setName(Instr->getName() + ".cloned");3010    Type *ResultTy = State.TypeAnalysis.inferScalarType(RepRecipe);3011    // The operands of the replicate recipe may have been narrowed, resulting in3012    // a narrower result type. Update the type of the cloned instruction to the3013    // correct type.3014    if (ResultTy != Cloned->getType())3015      Cloned->mutateType(ResultTy);3016  }3017 3018  RepRecipe->applyFlags(*Cloned);3019  RepRecipe->applyMetadata(*Cloned);3020 3021  if (RepRecipe->hasPredicate())3022    cast<CmpInst>(Cloned)->setPredicate(RepRecipe->getPredicate());3023 3024  if (auto DL = RepRecipe->getDebugLoc())3025    State.setDebugLocFrom(DL);3026 3027  // Replace the operands of the cloned instructions with their scalar3028  // equivalents in the new loop.3029  for (const auto &I : enumerate(RepRecipe->operands())) {3030    auto InputLane = Lane;3031    VPValue *Operand = I.value();3032    if (vputils::isSingleScalar(Operand))3033      InputLane = VPLane::getFirstLane();3034    Cloned->setOperand(I.index(), State.get(Operand, InputLane));3035  }3036 3037  // Place the cloned scalar in the new loop.3038  State.Builder.Insert(Cloned);3039 3040  State.set(RepRecipe, Cloned, Lane);3041 3042  // If we just cloned a new assumption, add it the assumption cache.3043  if (auto *II = dyn_cast<AssumeInst>(Cloned))3044    State.AC->registerAssumption(II);3045 3046  assert(3047      (RepRecipe->getRegion() ||3048       !RepRecipe->getParent()->getPlan()->getVectorLoopRegion() ||3049       all_of(RepRecipe->operands(),3050              [](VPValue *Op) { return Op->isDefinedOutsideLoopRegions(); })) &&3051      "Expected a recipe is either within a region or all of its operands "3052      "are defined outside the vectorized region.");3053}3054 3055void VPReplicateRecipe::execute(VPTransformState &State) {3056  Instruction *UI = getUnderlyingInstr();3057 3058  if (!State.Lane) {3059    assert(IsSingleScalar && "VPReplicateRecipes outside replicate regions "3060                             "must have already been unrolled");3061    scalarizeInstruction(UI, this, VPLane(0), State);3062    return;3063  }3064 3065  assert((State.VF.isScalar() || !isSingleScalar()) &&3066         "uniform recipe shouldn't be predicated");3067  assert(!State.VF.isScalable() && "Can't scalarize a scalable vector");3068  scalarizeInstruction(UI, this, *State.Lane, State);3069  // Insert scalar instance packing it into a vector.3070  if (State.VF.isVector() && shouldPack()) {3071    Value *WideValue =3072        State.Lane->isFirstLane()3073            ? PoisonValue::get(toVectorizedTy(UI->getType(), State.VF))3074            : State.get(this);3075    State.set(this, State.packScalarIntoVectorizedValue(this, WideValue,3076                                                        *State.Lane));3077  }3078}3079 3080bool VPReplicateRecipe::shouldPack() const {3081  // Find if the recipe is used by a widened recipe via an intervening3082  // VPPredInstPHIRecipe. In this case, also pack the scalar values in a vector.3083  return any_of(users(), [](const VPUser *U) {3084    if (auto *PredR = dyn_cast<VPPredInstPHIRecipe>(U))3085      return !vputils::onlyScalarValuesUsed(PredR);3086    return false;3087  });3088}3089 3090/// Returns a SCEV expression for \p Ptr if it is a pointer computation for3091/// which the legacy cost model computes a SCEV expression when computing the3092/// address cost. Computing SCEVs for VPValues is incomplete and returns3093/// SCEVCouldNotCompute in cases the legacy cost model can compute SCEVs. In3094/// those cases we fall back to the legacy cost model. Otherwise return nullptr.3095static const SCEV *getAddressAccessSCEV(const VPValue *Ptr, ScalarEvolution &SE,3096                                        const Loop *L) {3097  auto *PtrR = Ptr->getDefiningRecipe();3098  if (!PtrR || !((isa<VPReplicateRecipe>(Ptr) &&3099                  cast<VPReplicateRecipe>(Ptr)->getOpcode() ==3100                      Instruction::GetElementPtr) ||3101                 isa<VPWidenGEPRecipe>(Ptr) ||3102                 match(Ptr, m_GetElementPtr(m_VPValue(), m_VPValue()))))3103    return nullptr;3104 3105  // We are looking for a GEP where all indices are either loop invariant or3106  // inductions.3107  for (VPValue *Opd : drop_begin(PtrR->operands())) {3108    if (!Opd->isDefinedOutsideLoopRegions() &&3109        !isa<VPScalarIVStepsRecipe, VPWidenIntOrFpInductionRecipe>(Opd))3110      return nullptr;3111  }3112 3113  return vputils::getSCEVExprForVPValue(Ptr, SE, L);3114}3115 3116/// Returns true if \p V is used as part of the address of another load or3117/// store.3118static bool isUsedByLoadStoreAddress(const VPUser *V) {3119  SmallPtrSet<const VPUser *, 4> Seen;3120  SmallVector<const VPUser *> WorkList = {V};3121 3122  while (!WorkList.empty()) {3123    auto *Cur = dyn_cast<VPSingleDefRecipe>(WorkList.pop_back_val());3124    if (!Cur || !Seen.insert(Cur).second)3125      continue;3126 3127    auto *Blend = dyn_cast<VPBlendRecipe>(Cur);3128    // Skip blends that use V only through a compare by checking if any incoming3129    // value was already visited.3130    if (Blend && none_of(seq<unsigned>(0, Blend->getNumIncomingValues()),3131                         [&](unsigned I) {3132                           return Seen.contains(3133                               Blend->getIncomingValue(I)->getDefiningRecipe());3134                         }))3135      continue;3136 3137    for (VPUser *U : Cur->users()) {3138      if (auto *InterleaveR = dyn_cast<VPInterleaveBase>(U))3139        if (InterleaveR->getAddr() == Cur)3140          return true;3141      if (auto *RepR = dyn_cast<VPReplicateRecipe>(U)) {3142        if (RepR->getOpcode() == Instruction::Load &&3143            RepR->getOperand(0) == Cur)3144          return true;3145        if (RepR->getOpcode() == Instruction::Store &&3146            RepR->getOperand(1) == Cur)3147          return true;3148      }3149      if (auto *MemR = dyn_cast<VPWidenMemoryRecipe>(U)) {3150        if (MemR->getAddr() == Cur && MemR->isConsecutive())3151          return true;3152      }3153    }3154 3155    // The legacy cost model only supports scalarization loads/stores with phi3156    // addresses, if the phi is directly used as load/store address. Don't3157    // traverse further for Blends.3158    if (Blend)3159      continue;3160 3161    append_range(WorkList, Cur->users());3162  }3163  return false;3164}3165 3166InstructionCost VPReplicateRecipe::computeCost(ElementCount VF,3167                                               VPCostContext &Ctx) const {3168  Instruction *UI = cast<Instruction>(getUnderlyingValue());3169  // VPReplicateRecipe may be cloned as part of an existing VPlan-to-VPlan3170  // transform, avoid computing their cost multiple times for now.3171  Ctx.SkipCostComputation.insert(UI);3172 3173  if (VF.isScalable() && !isSingleScalar())3174    return InstructionCost::getInvalid();3175 3176  switch (UI->getOpcode()) {3177  case Instruction::GetElementPtr:3178    // We mark this instruction as zero-cost because the cost of GEPs in3179    // vectorized code depends on whether the corresponding memory instruction3180    // is scalarized or not. Therefore, we handle GEPs with the memory3181    // instruction cost.3182    return 0;3183  case Instruction::Call: {3184    auto *CalledFn =3185        cast<Function>(getOperand(getNumOperands() - 1)->getLiveInIRValue());3186 3187    SmallVector<const VPValue *> ArgOps(drop_end(operands()));3188    SmallVector<Type *, 4> Tys;3189    for (const VPValue *ArgOp : ArgOps)3190      Tys.push_back(Ctx.Types.inferScalarType(ArgOp));3191 3192    if (CalledFn->isIntrinsic())3193      // Various pseudo-intrinsics with costs of 0 are scalarized instead of3194      // vectorized via VPWidenIntrinsicRecipe. Return 0 for them early.3195      switch (CalledFn->getIntrinsicID()) {3196      case Intrinsic::assume:3197      case Intrinsic::lifetime_end:3198      case Intrinsic::lifetime_start:3199      case Intrinsic::sideeffect:3200      case Intrinsic::pseudoprobe:3201      case Intrinsic::experimental_noalias_scope_decl: {3202        assert(getCostForIntrinsics(CalledFn->getIntrinsicID(), ArgOps, *this,3203                                    ElementCount::getFixed(1), Ctx) == 0 &&3204               "scalarizing intrinsic should be free");3205        return InstructionCost(0);3206      }3207      default:3208        break;3209      }3210 3211    Type *ResultTy = Ctx.Types.inferScalarType(this);3212    InstructionCost ScalarCallCost =3213        Ctx.TTI.getCallInstrCost(CalledFn, ResultTy, Tys, Ctx.CostKind);3214    if (isSingleScalar()) {3215      if (CalledFn->isIntrinsic())3216        ScalarCallCost = std::min(3217            ScalarCallCost,3218            getCostForIntrinsics(CalledFn->getIntrinsicID(), ArgOps, *this,3219                                 ElementCount::getFixed(1), Ctx));3220      return ScalarCallCost;3221    }3222 3223    return ScalarCallCost * VF.getFixedValue() +3224           Ctx.getScalarizationOverhead(ResultTy, ArgOps, VF);3225  }3226  case Instruction::Add:3227  case Instruction::Sub:3228  case Instruction::FAdd:3229  case Instruction::FSub:3230  case Instruction::Mul:3231  case Instruction::FMul:3232  case Instruction::FDiv:3233  case Instruction::FRem:3234  case Instruction::Shl:3235  case Instruction::LShr:3236  case Instruction::AShr:3237  case Instruction::And:3238  case Instruction::Or:3239  case Instruction::Xor:3240  case Instruction::ICmp:3241  case Instruction::FCmp:3242    return getCostForRecipeWithOpcode(getOpcode(), ElementCount::getFixed(1),3243                                      Ctx) *3244           (isSingleScalar() ? 1 : VF.getFixedValue());3245  case Instruction::SDiv:3246  case Instruction::UDiv:3247  case Instruction::SRem:3248  case Instruction::URem: {3249    InstructionCost ScalarCost =3250        getCostForRecipeWithOpcode(getOpcode(), ElementCount::getFixed(1), Ctx);3251    if (isSingleScalar())3252      return ScalarCost;3253 3254    ScalarCost = ScalarCost * VF.getFixedValue() +3255                 Ctx.getScalarizationOverhead(Ctx.Types.inferScalarType(this),3256                                              to_vector(operands()), VF);3257    // If the recipe is not predicated (i.e. not in a replicate region), return3258    // the scalar cost. Otherwise handle predicated cost.3259    if (!getRegion()->isReplicator())3260      return ScalarCost;3261 3262    // Account for the phi nodes that we will create.3263    ScalarCost += VF.getFixedValue() *3264                  Ctx.TTI.getCFInstrCost(Instruction::PHI, Ctx.CostKind);3265    // Scale the cost by the probability of executing the predicated blocks.3266    // This assumes the predicated block for each vector lane is equally3267    // likely.3268    ScalarCost /= Ctx.getPredBlockCostDivisor(UI->getParent());3269    return ScalarCost;3270  }3271  case Instruction::Load:3272  case Instruction::Store: {3273    // TODO: See getMemInstScalarizationCost for how to handle replicating and3274    // predicated cases.3275    const VPRegionBlock *ParentRegion = getRegion();3276    if (ParentRegion && ParentRegion->isReplicator())3277      break;3278 3279    bool IsLoad = UI->getOpcode() == Instruction::Load;3280    const VPValue *PtrOp = getOperand(!IsLoad);3281    const SCEV *PtrSCEV = getAddressAccessSCEV(PtrOp, Ctx.SE, Ctx.L);3282    if (isa_and_nonnull<SCEVCouldNotCompute>(PtrSCEV))3283      break;3284 3285    Type *ValTy = Ctx.Types.inferScalarType(IsLoad ? this : getOperand(0));3286    Type *ScalarPtrTy = Ctx.Types.inferScalarType(PtrOp);3287    const Align Alignment = getLoadStoreAlignment(UI);3288    unsigned AS = cast<PointerType>(ScalarPtrTy)->getAddressSpace();3289    TTI::OperandValueInfo OpInfo = TTI::getOperandInfo(UI->getOperand(0));3290    InstructionCost ScalarMemOpCost = Ctx.TTI.getMemoryOpCost(3291        UI->getOpcode(), ValTy, Alignment, AS, Ctx.CostKind, OpInfo);3292 3293    Type *PtrTy = isSingleScalar() ? ScalarPtrTy : toVectorTy(ScalarPtrTy, VF);3294    bool PreferVectorizedAddressing = Ctx.TTI.prefersVectorizedAddressing();3295    bool UsedByLoadStoreAddress =3296        !PreferVectorizedAddressing && isUsedByLoadStoreAddress(this);3297    InstructionCost ScalarCost =3298        ScalarMemOpCost + Ctx.TTI.getAddressComputationCost(3299                              PtrTy, UsedByLoadStoreAddress ? nullptr : &Ctx.SE,3300                              PtrSCEV, Ctx.CostKind);3301    if (isSingleScalar())3302      return ScalarCost;3303 3304    SmallVector<const VPValue *> OpsToScalarize;3305    Type *ResultTy = Type::getVoidTy(PtrTy->getContext());3306    // Set ResultTy and OpsToScalarize, if scalarization is needed. Currently we3307    // don't assign scalarization overhead in general, if the target prefers3308    // vectorized addressing or the loaded value is used as part of an address3309    // of another load or store.3310    if (!UsedByLoadStoreAddress) {3311      bool EfficientVectorLoadStore =3312          Ctx.TTI.supportsEfficientVectorElementLoadStore();3313      if (!(IsLoad && !PreferVectorizedAddressing) &&3314          !(!IsLoad && EfficientVectorLoadStore))3315        append_range(OpsToScalarize, operands());3316 3317      if (!EfficientVectorLoadStore)3318        ResultTy = Ctx.Types.inferScalarType(this);3319    }3320 3321    return (ScalarCost * VF.getFixedValue()) +3322           Ctx.getScalarizationOverhead(ResultTy, OpsToScalarize, VF, true);3323  }3324  }3325 3326  return Ctx.getLegacyCost(UI, VF);3327}3328 3329#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)3330void VPReplicateRecipe::printRecipe(raw_ostream &O, const Twine &Indent,3331                                    VPSlotTracker &SlotTracker) const {3332  O << Indent << (IsSingleScalar ? "CLONE " : "REPLICATE ");3333 3334  if (!getUnderlyingInstr()->getType()->isVoidTy()) {3335    printAsOperand(O, SlotTracker);3336    O << " = ";3337  }3338  if (auto *CB = dyn_cast<CallBase>(getUnderlyingInstr())) {3339    O << "call";3340    printFlags(O);3341    O << "@" << CB->getCalledFunction()->getName() << "(";3342    interleaveComma(make_range(op_begin(), op_begin() + (getNumOperands() - 1)),3343                    O, [&O, &SlotTracker](VPValue *Op) {3344                      Op->printAsOperand(O, SlotTracker);3345                    });3346    O << ")";3347  } else {3348    O << Instruction::getOpcodeName(getUnderlyingInstr()->getOpcode());3349    printFlags(O);3350    printOperands(O, SlotTracker);3351  }3352 3353  if (shouldPack())3354    O << " (S->V)";3355}3356#endif3357 3358void VPBranchOnMaskRecipe::execute(VPTransformState &State) {3359  assert(State.Lane && "Branch on Mask works only on single instance.");3360 3361  VPValue *BlockInMask = getOperand(0);3362  Value *ConditionBit = State.get(BlockInMask, *State.Lane);3363 3364  // Replace the temporary unreachable terminator with a new conditional branch,3365  // whose two destinations will be set later when they are created.3366  auto *CurrentTerminator = State.CFG.PrevBB->getTerminator();3367  assert(isa<UnreachableInst>(CurrentTerminator) &&3368         "Expected to replace unreachable terminator with conditional branch.");3369  auto CondBr =3370      State.Builder.CreateCondBr(ConditionBit, State.CFG.PrevBB, nullptr);3371  CondBr->setSuccessor(0, nullptr);3372  CurrentTerminator->eraseFromParent();3373}3374 3375InstructionCost VPBranchOnMaskRecipe::computeCost(ElementCount VF,3376                                                  VPCostContext &Ctx) const {3377  // The legacy cost model doesn't assign costs to branches for individual3378  // replicate regions. Match the current behavior in the VPlan cost model for3379  // now.3380  return 0;3381}3382 3383void VPPredInstPHIRecipe::execute(VPTransformState &State) {3384  assert(State.Lane && "Predicated instruction PHI works per instance.");3385  Instruction *ScalarPredInst =3386      cast<Instruction>(State.get(getOperand(0), *State.Lane));3387  BasicBlock *PredicatedBB = ScalarPredInst->getParent();3388  BasicBlock *PredicatingBB = PredicatedBB->getSinglePredecessor();3389  assert(PredicatingBB && "Predicated block has no single predecessor.");3390  assert(isa<VPReplicateRecipe>(getOperand(0)) &&3391         "operand must be VPReplicateRecipe");3392 3393  // By current pack/unpack logic we need to generate only a single phi node: if3394  // a vector value for the predicated instruction exists at this point it means3395  // the instruction has vector users only, and a phi for the vector value is3396  // needed. In this case the recipe of the predicated instruction is marked to3397  // also do that packing, thereby "hoisting" the insert-element sequence.3398  // Otherwise, a phi node for the scalar value is needed.3399  if (State.hasVectorValue(getOperand(0))) {3400    auto *VecI = cast<Instruction>(State.get(getOperand(0)));3401    assert((isa<InsertElementInst, InsertValueInst>(VecI)) &&3402           "Packed operands must generate an insertelement or insertvalue");3403 3404    // If VectorI is a struct, it will be a sequence like:3405    // %1       = insertvalue %unmodified, %x, 03406    // %2       = insertvalue %1, %y, 13407    // %VectorI = insertvalue %2, %z, 23408    // To get the unmodified vector we need to look through the chain.3409    if (auto *StructTy = dyn_cast<StructType>(VecI->getType()))3410      for (unsigned I = 0; I < StructTy->getNumContainedTypes() - 1; I++)3411        VecI = cast<InsertValueInst>(VecI->getOperand(0));3412 3413    PHINode *VPhi = State.Builder.CreatePHI(VecI->getType(), 2);3414    VPhi->addIncoming(VecI->getOperand(0), PredicatingBB); // Unmodified vector.3415    VPhi->addIncoming(VecI, PredicatedBB); // New vector with inserted element.3416    if (State.hasVectorValue(this))3417      State.reset(this, VPhi);3418    else3419      State.set(this, VPhi);3420    // NOTE: Currently we need to update the value of the operand, so the next3421    // predicated iteration inserts its generated value in the correct vector.3422    State.reset(getOperand(0), VPhi);3423  } else {3424    if (vputils::onlyFirstLaneUsed(this) && !State.Lane->isFirstLane())3425      return;3426 3427    Type *PredInstType = State.TypeAnalysis.inferScalarType(getOperand(0));3428    PHINode *Phi = State.Builder.CreatePHI(PredInstType, 2);3429    Phi->addIncoming(PoisonValue::get(ScalarPredInst->getType()),3430                     PredicatingBB);3431    Phi->addIncoming(ScalarPredInst, PredicatedBB);3432    if (State.hasScalarValue(this, *State.Lane))3433      State.reset(this, Phi, *State.Lane);3434    else3435      State.set(this, Phi, *State.Lane);3436    // NOTE: Currently we need to update the value of the operand, so the next3437    // predicated iteration inserts its generated value in the correct vector.3438    State.reset(getOperand(0), Phi, *State.Lane);3439  }3440}3441 3442#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)3443void VPPredInstPHIRecipe::printRecipe(raw_ostream &O, const Twine &Indent,3444                                      VPSlotTracker &SlotTracker) const {3445  O << Indent << "PHI-PREDICATED-INSTRUCTION ";3446  printAsOperand(O, SlotTracker);3447  O << " = ";3448  printOperands(O, SlotTracker);3449}3450#endif3451 3452InstructionCost VPWidenMemoryRecipe::computeCost(ElementCount VF,3453                                                 VPCostContext &Ctx) const {3454  Type *Ty = toVectorTy(getLoadStoreType(&Ingredient), VF);3455  unsigned AS = cast<PointerType>(Ctx.Types.inferScalarType(getAddr()))3456                    ->getAddressSpace();3457  unsigned Opcode = isa<VPWidenLoadRecipe, VPWidenLoadEVLRecipe>(this)3458                        ? Instruction::Load3459                        : Instruction::Store;3460 3461  if (!Consecutive) {3462    // TODO: Using the original IR may not be accurate.3463    // Currently, ARM will use the underlying IR to calculate gather/scatter3464    // instruction cost.3465    assert(!Reverse &&3466           "Inconsecutive memory access should not have the order.");3467 3468    const Value *Ptr = getLoadStorePointerOperand(&Ingredient);3469    Type *PtrTy = Ptr->getType();3470 3471    // If the address value is uniform across all lanes, then the address can be3472    // calculated with scalar type and broadcast.3473    if (!vputils::isSingleScalar(getAddr()))3474      PtrTy = toVectorTy(PtrTy, VF);3475 3476    unsigned IID = isa<VPWidenLoadRecipe>(this)      ? Intrinsic::masked_gather3477                   : isa<VPWidenStoreRecipe>(this)   ? Intrinsic::masked_scatter3478                   : isa<VPWidenLoadEVLRecipe>(this) ? Intrinsic::vp_gather3479                                                     : Intrinsic::vp_scatter;3480    return Ctx.TTI.getAddressComputationCost(PtrTy, nullptr, nullptr,3481                                             Ctx.CostKind) +3482           Ctx.TTI.getMemIntrinsicInstrCost(3483               MemIntrinsicCostAttributes(IID, Ty, Ptr, IsMasked, Alignment,3484                                          &Ingredient),3485               Ctx.CostKind);3486  }3487 3488  InstructionCost Cost = 0;3489  if (IsMasked) {3490    unsigned IID = isa<VPWidenLoadRecipe>(this) ? Intrinsic::masked_load3491                                                : Intrinsic::masked_store;3492    Cost += Ctx.TTI.getMemIntrinsicInstrCost(3493        MemIntrinsicCostAttributes(IID, Ty, Alignment, AS), Ctx.CostKind);3494  } else {3495    TTI::OperandValueInfo OpInfo = Ctx.getOperandInfo(3496        isa<VPWidenLoadRecipe, VPWidenLoadEVLRecipe>(this) ? getOperand(0)3497                                                           : getOperand(1));3498    Cost += Ctx.TTI.getMemoryOpCost(Opcode, Ty, Alignment, AS, Ctx.CostKind,3499                                    OpInfo, &Ingredient);3500  }3501  if (!Reverse)3502    return Cost;3503 3504  return Cost += Ctx.TTI.getShuffleCost(3505             TargetTransformInfo::SK_Reverse, cast<VectorType>(Ty),3506             cast<VectorType>(Ty), {}, Ctx.CostKind, 0);3507}3508 3509void VPWidenLoadRecipe::execute(VPTransformState &State) {3510  Type *ScalarDataTy = getLoadStoreType(&Ingredient);3511  auto *DataTy = VectorType::get(ScalarDataTy, State.VF);3512  bool CreateGather = !isConsecutive();3513 3514  auto &Builder = State.Builder;3515  Value *Mask = nullptr;3516  if (auto *VPMask = getMask()) {3517    // Mask reversal is only needed for non-all-one (null) masks, as reverse3518    // of a null all-one mask is a null mask.3519    Mask = State.get(VPMask);3520    if (isReverse())3521      Mask = Builder.CreateVectorReverse(Mask, "reverse");3522  }3523 3524  Value *Addr = State.get(getAddr(), /*IsScalar*/ !CreateGather);3525  Value *NewLI;3526  if (CreateGather) {3527    NewLI = Builder.CreateMaskedGather(DataTy, Addr, Alignment, Mask, nullptr,3528                                       "wide.masked.gather");3529  } else if (Mask) {3530    NewLI =3531        Builder.CreateMaskedLoad(DataTy, Addr, Alignment, Mask,3532                                 PoisonValue::get(DataTy), "wide.masked.load");3533  } else {3534    NewLI = Builder.CreateAlignedLoad(DataTy, Addr, Alignment, "wide.load");3535  }3536  applyMetadata(*cast<Instruction>(NewLI));3537  if (Reverse)3538    NewLI = Builder.CreateVectorReverse(NewLI, "reverse");3539  State.set(this, NewLI);3540}3541 3542#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)3543void VPWidenLoadRecipe::printRecipe(raw_ostream &O, const Twine &Indent,3544                                    VPSlotTracker &SlotTracker) const {3545  O << Indent << "WIDEN ";3546  printAsOperand(O, SlotTracker);3547  O << " = load ";3548  printOperands(O, SlotTracker);3549}3550#endif3551 3552/// Use all-true mask for reverse rather than actual mask, as it avoids a3553/// dependence w/o affecting the result.3554static Instruction *createReverseEVL(IRBuilderBase &Builder, Value *Operand,3555                                     Value *EVL, const Twine &Name) {3556  VectorType *ValTy = cast<VectorType>(Operand->getType());3557  Value *AllTrueMask =3558      Builder.CreateVectorSplat(ValTy->getElementCount(), Builder.getTrue());3559  return Builder.CreateIntrinsic(ValTy, Intrinsic::experimental_vp_reverse,3560                                 {Operand, AllTrueMask, EVL}, nullptr, Name);3561}3562 3563void VPWidenLoadEVLRecipe::execute(VPTransformState &State) {3564  Type *ScalarDataTy = getLoadStoreType(&Ingredient);3565  auto *DataTy = VectorType::get(ScalarDataTy, State.VF);3566  bool CreateGather = !isConsecutive();3567 3568  auto &Builder = State.Builder;3569  CallInst *NewLI;3570  Value *EVL = State.get(getEVL(), VPLane(0));3571  Value *Addr = State.get(getAddr(), !CreateGather);3572  Value *Mask = nullptr;3573  if (VPValue *VPMask = getMask()) {3574    Mask = State.get(VPMask);3575    if (isReverse())3576      Mask = createReverseEVL(Builder, Mask, EVL, "vp.reverse.mask");3577  } else {3578    Mask = Builder.CreateVectorSplat(State.VF, Builder.getTrue());3579  }3580 3581  if (CreateGather) {3582    NewLI =3583        Builder.CreateIntrinsic(DataTy, Intrinsic::vp_gather, {Addr, Mask, EVL},3584                                nullptr, "wide.masked.gather");3585  } else {3586    NewLI = Builder.CreateIntrinsic(DataTy, Intrinsic::vp_load,3587                                    {Addr, Mask, EVL}, nullptr, "vp.op.load");3588  }3589  NewLI->addParamAttr(3590      0, Attribute::getWithAlignment(NewLI->getContext(), Alignment));3591  applyMetadata(*NewLI);3592  Instruction *Res = NewLI;3593  if (isReverse())3594    Res = createReverseEVL(Builder, Res, EVL, "vp.reverse");3595  State.set(this, Res);3596}3597 3598InstructionCost VPWidenLoadEVLRecipe::computeCost(ElementCount VF,3599                                                  VPCostContext &Ctx) const {3600  if (!Consecutive || IsMasked)3601    return VPWidenMemoryRecipe::computeCost(VF, Ctx);3602 3603  // We need to use the getMemIntrinsicInstrCost() instead of getMemoryOpCost()3604  // here because the EVL recipes using EVL to replace the tail mask. But in the3605  // legacy model, it will always calculate the cost of mask.3606  // TODO: Using getMemoryOpCost() instead of getMemIntrinsicInstrCost  when we3607  // don't need to compare to the legacy cost model.3608  Type *Ty = toVectorTy(getLoadStoreType(&Ingredient), VF);3609  unsigned AS = cast<PointerType>(Ctx.Types.inferScalarType(getAddr()))3610                    ->getAddressSpace();3611  // FIXME: getMaskedMemoryOpCost assumes masked_* intrinsics.3612  // After migrating to getMemIntrinsicInstrCost, switch this to vp_load.3613  InstructionCost Cost = Ctx.TTI.getMemIntrinsicInstrCost(3614      MemIntrinsicCostAttributes(Intrinsic::masked_load, Ty, Alignment, AS),3615      Ctx.CostKind);3616  if (!Reverse)3617    return Cost;3618 3619  return Cost + Ctx.TTI.getShuffleCost(3620                    TargetTransformInfo::SK_Reverse, cast<VectorType>(Ty),3621                    cast<VectorType>(Ty), {}, Ctx.CostKind, 0);3622}3623 3624#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)3625void VPWidenLoadEVLRecipe::printRecipe(raw_ostream &O, const Twine &Indent,3626                                       VPSlotTracker &SlotTracker) const {3627  O << Indent << "WIDEN ";3628  printAsOperand(O, SlotTracker);3629  O << " = vp.load ";3630  printOperands(O, SlotTracker);3631}3632#endif3633 3634void VPWidenStoreRecipe::execute(VPTransformState &State) {3635  VPValue *StoredVPValue = getStoredValue();3636  bool CreateScatter = !isConsecutive();3637 3638  auto &Builder = State.Builder;3639 3640  Value *Mask = nullptr;3641  if (auto *VPMask = getMask()) {3642    // Mask reversal is only needed for non-all-one (null) masks, as reverse3643    // of a null all-one mask is a null mask.3644    Mask = State.get(VPMask);3645    if (isReverse())3646      Mask = Builder.CreateVectorReverse(Mask, "reverse");3647  }3648 3649  Value *StoredVal = State.get(StoredVPValue);3650  if (isReverse()) {3651    // If we store to reverse consecutive memory locations, then we need3652    // to reverse the order of elements in the stored value.3653    StoredVal = Builder.CreateVectorReverse(StoredVal, "reverse");3654    // We don't want to update the value in the map as it might be used in3655    // another expression. So don't call resetVectorValue(StoredVal).3656  }3657  Value *Addr = State.get(getAddr(), /*IsScalar*/ !CreateScatter);3658  Instruction *NewSI = nullptr;3659  if (CreateScatter)3660    NewSI = Builder.CreateMaskedScatter(StoredVal, Addr, Alignment, Mask);3661  else if (Mask)3662    NewSI = Builder.CreateMaskedStore(StoredVal, Addr, Alignment, Mask);3663  else3664    NewSI = Builder.CreateAlignedStore(StoredVal, Addr, Alignment);3665  applyMetadata(*NewSI);3666}3667 3668#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)3669void VPWidenStoreRecipe::printRecipe(raw_ostream &O, const Twine &Indent,3670                                     VPSlotTracker &SlotTracker) const {3671  O << Indent << "WIDEN store ";3672  printOperands(O, SlotTracker);3673}3674#endif3675 3676void VPWidenStoreEVLRecipe::execute(VPTransformState &State) {3677  VPValue *StoredValue = getStoredValue();3678  bool CreateScatter = !isConsecutive();3679 3680  auto &Builder = State.Builder;3681 3682  CallInst *NewSI = nullptr;3683  Value *StoredVal = State.get(StoredValue);3684  Value *EVL = State.get(getEVL(), VPLane(0));3685  if (isReverse())3686    StoredVal = createReverseEVL(Builder, StoredVal, EVL, "vp.reverse");3687  Value *Mask = nullptr;3688  if (VPValue *VPMask = getMask()) {3689    Mask = State.get(VPMask);3690    if (isReverse())3691      Mask = createReverseEVL(Builder, Mask, EVL, "vp.reverse.mask");3692  } else {3693    Mask = Builder.CreateVectorSplat(State.VF, Builder.getTrue());3694  }3695  Value *Addr = State.get(getAddr(), !CreateScatter);3696  if (CreateScatter) {3697    NewSI = Builder.CreateIntrinsic(Type::getVoidTy(EVL->getContext()),3698                                    Intrinsic::vp_scatter,3699                                    {StoredVal, Addr, Mask, EVL});3700  } else {3701    NewSI = Builder.CreateIntrinsic(Type::getVoidTy(EVL->getContext()),3702                                    Intrinsic::vp_store,3703                                    {StoredVal, Addr, Mask, EVL});3704  }3705  NewSI->addParamAttr(3706      1, Attribute::getWithAlignment(NewSI->getContext(), Alignment));3707  applyMetadata(*NewSI);3708}3709 3710InstructionCost VPWidenStoreEVLRecipe::computeCost(ElementCount VF,3711                                                   VPCostContext &Ctx) const {3712  if (!Consecutive || IsMasked)3713    return VPWidenMemoryRecipe::computeCost(VF, Ctx);3714 3715  // We need to use the getMemIntrinsicInstrCost() instead of getMemoryOpCost()3716  // here because the EVL recipes using EVL to replace the tail mask. But in the3717  // legacy model, it will always calculate the cost of mask.3718  // TODO: Using getMemoryOpCost() instead of getMemIntrinsicInstrCost when we3719  // don't need to compare to the legacy cost model.3720  Type *Ty = toVectorTy(getLoadStoreType(&Ingredient), VF);3721  unsigned AS = cast<PointerType>(Ctx.Types.inferScalarType(getAddr()))3722                    ->getAddressSpace();3723  // FIXME: getMaskedMemoryOpCost assumes masked_* intrinsics.3724  // After migrating to getMemIntrinsicInstrCost, switch this to vp_store.3725  InstructionCost Cost = Ctx.TTI.getMemIntrinsicInstrCost(3726      MemIntrinsicCostAttributes(Intrinsic::masked_store, Ty, Alignment, AS),3727      Ctx.CostKind);3728  if (!Reverse)3729    return Cost;3730 3731  return Cost + Ctx.TTI.getShuffleCost(3732                    TargetTransformInfo::SK_Reverse, cast<VectorType>(Ty),3733                    cast<VectorType>(Ty), {}, Ctx.CostKind, 0);3734}3735 3736#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)3737void VPWidenStoreEVLRecipe::printRecipe(raw_ostream &O, const Twine &Indent,3738                                        VPSlotTracker &SlotTracker) const {3739  O << Indent << "WIDEN vp.store ";3740  printOperands(O, SlotTracker);3741}3742#endif3743 3744static Value *createBitOrPointerCast(IRBuilderBase &Builder, Value *V,3745                                     VectorType *DstVTy, const DataLayout &DL) {3746  // Verify that V is a vector type with same number of elements as DstVTy.3747  auto VF = DstVTy->getElementCount();3748  auto *SrcVecTy = cast<VectorType>(V->getType());3749  assert(VF == SrcVecTy->getElementCount() && "Vector dimensions do not match");3750  Type *SrcElemTy = SrcVecTy->getElementType();3751  Type *DstElemTy = DstVTy->getElementType();3752  assert((DL.getTypeSizeInBits(SrcElemTy) == DL.getTypeSizeInBits(DstElemTy)) &&3753         "Vector elements must have same size");3754 3755  // Do a direct cast if element types are castable.3756  if (CastInst::isBitOrNoopPointerCastable(SrcElemTy, DstElemTy, DL)) {3757    return Builder.CreateBitOrPointerCast(V, DstVTy);3758  }3759  // V cannot be directly casted to desired vector type.3760  // May happen when V is a floating point vector but DstVTy is a vector of3761  // pointers or vice-versa. Handle this using a two-step bitcast using an3762  // intermediate Integer type for the bitcast i.e. Ptr <-> Int <-> Float.3763  assert((DstElemTy->isPointerTy() != SrcElemTy->isPointerTy()) &&3764         "Only one type should be a pointer type");3765  assert((DstElemTy->isFloatingPointTy() != SrcElemTy->isFloatingPointTy()) &&3766         "Only one type should be a floating point type");3767  Type *IntTy =3768      IntegerType::getIntNTy(V->getContext(), DL.getTypeSizeInBits(SrcElemTy));3769  auto *VecIntTy = VectorType::get(IntTy, VF);3770  Value *CastVal = Builder.CreateBitOrPointerCast(V, VecIntTy);3771  return Builder.CreateBitOrPointerCast(CastVal, DstVTy);3772}3773 3774/// Return a vector containing interleaved elements from multiple3775/// smaller input vectors.3776static Value *interleaveVectors(IRBuilderBase &Builder, ArrayRef<Value *> Vals,3777                                const Twine &Name) {3778  unsigned Factor = Vals.size();3779  assert(Factor > 1 && "Tried to interleave invalid number of vectors");3780 3781  VectorType *VecTy = cast<VectorType>(Vals[0]->getType());3782#ifndef NDEBUG3783  for (Value *Val : Vals)3784    assert(Val->getType() == VecTy && "Tried to interleave mismatched types");3785#endif3786 3787  // Scalable vectors cannot use arbitrary shufflevectors (only splats), so3788  // must use intrinsics to interleave.3789  if (VecTy->isScalableTy()) {3790    assert(Factor <= 8 && "Unsupported interleave factor for scalable vectors");3791    return Builder.CreateVectorInterleave(Vals, Name);3792  }3793 3794  // Fixed length. Start by concatenating all vectors into a wide vector.3795  Value *WideVec = concatenateVectors(Builder, Vals);3796 3797  // Interleave the elements into the wide vector.3798  const unsigned NumElts = VecTy->getElementCount().getFixedValue();3799  return Builder.CreateShuffleVector(3800      WideVec, createInterleaveMask(NumElts, Factor), Name);3801}3802 3803// Try to vectorize the interleave group that \p Instr belongs to.3804//3805// E.g. Translate following interleaved load group (factor = 3):3806//   for (i = 0; i < N; i+=3) {3807//     R = Pic[i];             // Member of index 03808//     G = Pic[i+1];           // Member of index 13809//     B = Pic[i+2];           // Member of index 23810//     ... // do something to R, G, B3811//   }3812// To:3813//   %wide.vec = load <12 x i32>                       ; Read 4 tuples of R,G,B3814//   %R.vec = shuffle %wide.vec, poison, <0, 3, 6, 9>   ; R elements3815//   %G.vec = shuffle %wide.vec, poison, <1, 4, 7, 10>  ; G elements3816//   %B.vec = shuffle %wide.vec, poison, <2, 5, 8, 11>  ; B elements3817//3818// Or translate following interleaved store group (factor = 3):3819//   for (i = 0; i < N; i+=3) {3820//     ... do something to R, G, B3821//     Pic[i]   = R;           // Member of index 03822//     Pic[i+1] = G;           // Member of index 13823//     Pic[i+2] = B;           // Member of index 23824//   }3825// To:3826//   %R_G.vec = shuffle %R.vec, %G.vec, <0, 1, 2, ..., 7>3827//   %B_U.vec = shuffle %B.vec, poison, <0, 1, 2, 3, u, u, u, u>3828//   %interleaved.vec = shuffle %R_G.vec, %B_U.vec,3829//        <0, 4, 8, 1, 5, 9, 2, 6, 10, 3, 7, 11>    ; Interleave R,G,B elements3830//   store <12 x i32> %interleaved.vec              ; Write 4 tuples of R,G,B3831void VPInterleaveRecipe::execute(VPTransformState &State) {3832  assert(!State.Lane && "Interleave group being replicated.");3833  assert((!needsMaskForGaps() || !State.VF.isScalable()) &&3834         "Masking gaps for scalable vectors is not yet supported.");3835  const InterleaveGroup<Instruction> *Group = getInterleaveGroup();3836  Instruction *Instr = Group->getInsertPos();3837 3838  // Prepare for the vector type of the interleaved load/store.3839  Type *ScalarTy = getLoadStoreType(Instr);3840  unsigned InterleaveFactor = Group->getFactor();3841  auto *VecTy = VectorType::get(ScalarTy, State.VF * InterleaveFactor);3842 3843  VPValue *BlockInMask = getMask();3844  VPValue *Addr = getAddr();3845  Value *ResAddr = State.get(Addr, VPLane(0));3846 3847  auto CreateGroupMask = [&BlockInMask, &State,3848                          &InterleaveFactor](Value *MaskForGaps) -> Value * {3849    if (State.VF.isScalable()) {3850      assert(!MaskForGaps && "Interleaved groups with gaps are not supported.");3851      assert(InterleaveFactor <= 8 &&3852             "Unsupported deinterleave factor for scalable vectors");3853      auto *ResBlockInMask = State.get(BlockInMask);3854      SmallVector<Value *> Ops(InterleaveFactor, ResBlockInMask);3855      return interleaveVectors(State.Builder, Ops, "interleaved.mask");3856    }3857 3858    if (!BlockInMask)3859      return MaskForGaps;3860 3861    Value *ResBlockInMask = State.get(BlockInMask);3862    Value *ShuffledMask = State.Builder.CreateShuffleVector(3863        ResBlockInMask,3864        createReplicatedMask(InterleaveFactor, State.VF.getFixedValue()),3865        "interleaved.mask");3866    return MaskForGaps ? State.Builder.CreateBinOp(Instruction::And,3867                                                   ShuffledMask, MaskForGaps)3868                       : ShuffledMask;3869  };3870 3871  const DataLayout &DL = Instr->getDataLayout();3872  // Vectorize the interleaved load group.3873  if (isa<LoadInst>(Instr)) {3874    Value *MaskForGaps = nullptr;3875    if (needsMaskForGaps()) {3876      MaskForGaps =3877          createBitMaskForGaps(State.Builder, State.VF.getFixedValue(), *Group);3878      assert(MaskForGaps && "Mask for Gaps is required but it is null");3879    }3880 3881    Instruction *NewLoad;3882    if (BlockInMask || MaskForGaps) {3883      Value *GroupMask = CreateGroupMask(MaskForGaps);3884      Value *PoisonVec = PoisonValue::get(VecTy);3885      NewLoad = State.Builder.CreateMaskedLoad(VecTy, ResAddr,3886                                               Group->getAlign(), GroupMask,3887                                               PoisonVec, "wide.masked.vec");3888    } else3889      NewLoad = State.Builder.CreateAlignedLoad(VecTy, ResAddr,3890                                                Group->getAlign(), "wide.vec");3891    applyMetadata(*NewLoad);3892    // TODO: Also manage existing metadata using VPIRMetadata.3893    Group->addMetadata(NewLoad);3894 3895    ArrayRef<VPValue *> VPDefs = definedValues();3896    if (VecTy->isScalableTy()) {3897      // Scalable vectors cannot use arbitrary shufflevectors (only splats),3898      // so must use intrinsics to deinterleave.3899      assert(InterleaveFactor <= 8 &&3900             "Unsupported deinterleave factor for scalable vectors");3901      NewLoad = State.Builder.CreateIntrinsic(3902          Intrinsic::getDeinterleaveIntrinsicID(InterleaveFactor),3903          NewLoad->getType(), NewLoad,3904          /*FMFSource=*/nullptr, "strided.vec");3905    }3906 3907    auto CreateStridedVector = [&InterleaveFactor, &State,3908                                &NewLoad](unsigned Index) -> Value * {3909      assert(Index < InterleaveFactor && "Illegal group index");3910      if (State.VF.isScalable())3911        return State.Builder.CreateExtractValue(NewLoad, Index);3912 3913      // For fixed length VF, use shuffle to extract the sub-vectors from the3914      // wide load.3915      auto StrideMask =3916          createStrideMask(Index, InterleaveFactor, State.VF.getFixedValue());3917      return State.Builder.CreateShuffleVector(NewLoad, StrideMask,3918                                               "strided.vec");3919    };3920 3921    for (unsigned I = 0, J = 0; I < InterleaveFactor; ++I) {3922      Instruction *Member = Group->getMember(I);3923 3924      // Skip the gaps in the group.3925      if (!Member)3926        continue;3927 3928      Value *StridedVec = CreateStridedVector(I);3929 3930      // If this member has different type, cast the result type.3931      if (Member->getType() != ScalarTy) {3932        VectorType *OtherVTy = VectorType::get(Member->getType(), State.VF);3933        StridedVec =3934            createBitOrPointerCast(State.Builder, StridedVec, OtherVTy, DL);3935      }3936 3937      if (Group->isReverse())3938        StridedVec = State.Builder.CreateVectorReverse(StridedVec, "reverse");3939 3940      State.set(VPDefs[J], StridedVec);3941      ++J;3942    }3943    return;3944  }3945 3946  // The sub vector type for current instruction.3947  auto *SubVT = VectorType::get(ScalarTy, State.VF);3948 3949  // Vectorize the interleaved store group.3950  Value *MaskForGaps =3951      createBitMaskForGaps(State.Builder, State.VF.getKnownMinValue(), *Group);3952  assert(((MaskForGaps != nullptr) == needsMaskForGaps()) &&3953         "Mismatch between NeedsMaskForGaps and MaskForGaps");3954  ArrayRef<VPValue *> StoredValues = getStoredValues();3955  // Collect the stored vector from each member.3956  SmallVector<Value *, 4> StoredVecs;3957  unsigned StoredIdx = 0;3958  for (unsigned i = 0; i < InterleaveFactor; i++) {3959    assert((Group->getMember(i) || MaskForGaps) &&3960           "Fail to get a member from an interleaved store group");3961    Instruction *Member = Group->getMember(i);3962 3963    // Skip the gaps in the group.3964    if (!Member) {3965      Value *Undef = PoisonValue::get(SubVT);3966      StoredVecs.push_back(Undef);3967      continue;3968    }3969 3970    Value *StoredVec = State.get(StoredValues[StoredIdx]);3971    ++StoredIdx;3972 3973    if (Group->isReverse())3974      StoredVec = State.Builder.CreateVectorReverse(StoredVec, "reverse");3975 3976    // If this member has different type, cast it to a unified type.3977 3978    if (StoredVec->getType() != SubVT)3979      StoredVec = createBitOrPointerCast(State.Builder, StoredVec, SubVT, DL);3980 3981    StoredVecs.push_back(StoredVec);3982  }3983 3984  // Interleave all the smaller vectors into one wider vector.3985  Value *IVec = interleaveVectors(State.Builder, StoredVecs, "interleaved.vec");3986  Instruction *NewStoreInstr;3987  if (BlockInMask || MaskForGaps) {3988    Value *GroupMask = CreateGroupMask(MaskForGaps);3989    NewStoreInstr = State.Builder.CreateMaskedStore(3990        IVec, ResAddr, Group->getAlign(), GroupMask);3991  } else3992    NewStoreInstr =3993        State.Builder.CreateAlignedStore(IVec, ResAddr, Group->getAlign());3994 3995  applyMetadata(*NewStoreInstr);3996  // TODO: Also manage existing metadata using VPIRMetadata.3997  Group->addMetadata(NewStoreInstr);3998}3999 4000#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)4001void VPInterleaveRecipe::printRecipe(raw_ostream &O, const Twine &Indent,4002                                     VPSlotTracker &SlotTracker) const {4003  const InterleaveGroup<Instruction> *IG = getInterleaveGroup();4004  O << Indent << "INTERLEAVE-GROUP with factor " << IG->getFactor() << " at ";4005  IG->getInsertPos()->printAsOperand(O, false);4006  O << ", ";4007  getAddr()->printAsOperand(O, SlotTracker);4008  VPValue *Mask = getMask();4009  if (Mask) {4010    O << ", ";4011    Mask->printAsOperand(O, SlotTracker);4012  }4013 4014  unsigned OpIdx = 0;4015  for (unsigned i = 0; i < IG->getFactor(); ++i) {4016    if (!IG->getMember(i))4017      continue;4018    if (getNumStoreOperands() > 0) {4019      O << "\n" << Indent << "  store ";4020      getOperand(1 + OpIdx)->printAsOperand(O, SlotTracker);4021      O << " to index " << i;4022    } else {4023      O << "\n" << Indent << "  ";4024      getVPValue(OpIdx)->printAsOperand(O, SlotTracker);4025      O << " = load from index " << i;4026    }4027    ++OpIdx;4028  }4029}4030#endif4031 4032void VPInterleaveEVLRecipe::execute(VPTransformState &State) {4033  assert(!State.Lane && "Interleave group being replicated.");4034  assert(State.VF.isScalable() &&4035         "Only support scalable VF for EVL tail-folding.");4036  assert(!needsMaskForGaps() &&4037         "Masking gaps for scalable vectors is not yet supported.");4038  const InterleaveGroup<Instruction> *Group = getInterleaveGroup();4039  Instruction *Instr = Group->getInsertPos();4040 4041  // Prepare for the vector type of the interleaved load/store.4042  Type *ScalarTy = getLoadStoreType(Instr);4043  unsigned InterleaveFactor = Group->getFactor();4044  assert(InterleaveFactor <= 8 &&4045         "Unsupported deinterleave/interleave factor for scalable vectors");4046  ElementCount WideVF = State.VF * InterleaveFactor;4047  auto *VecTy = VectorType::get(ScalarTy, WideVF);4048 4049  VPValue *Addr = getAddr();4050  Value *ResAddr = State.get(Addr, VPLane(0));4051  Value *EVL = State.get(getEVL(), VPLane(0));4052  Value *InterleaveEVL = State.Builder.CreateMul(4053      EVL, ConstantInt::get(EVL->getType(), InterleaveFactor), "interleave.evl",4054      /* NUW= */ true, /* NSW= */ true);4055  LLVMContext &Ctx = State.Builder.getContext();4056 4057  Value *GroupMask = nullptr;4058  if (VPValue *BlockInMask = getMask()) {4059    SmallVector<Value *> Ops(InterleaveFactor, State.get(BlockInMask));4060    GroupMask = interleaveVectors(State.Builder, Ops, "interleaved.mask");4061  } else {4062    GroupMask =4063        State.Builder.CreateVectorSplat(WideVF, State.Builder.getTrue());4064  }4065 4066  // Vectorize the interleaved load group.4067  if (isa<LoadInst>(Instr)) {4068    CallInst *NewLoad = State.Builder.CreateIntrinsic(4069        VecTy, Intrinsic::vp_load, {ResAddr, GroupMask, InterleaveEVL}, nullptr,4070        "wide.vp.load");4071    NewLoad->addParamAttr(0,4072                          Attribute::getWithAlignment(Ctx, Group->getAlign()));4073 4074    applyMetadata(*NewLoad);4075    // TODO: Also manage existing metadata using VPIRMetadata.4076    Group->addMetadata(NewLoad);4077 4078    // Scalable vectors cannot use arbitrary shufflevectors (only splats),4079    // so must use intrinsics to deinterleave.4080    NewLoad = State.Builder.CreateIntrinsic(4081        Intrinsic::getDeinterleaveIntrinsicID(InterleaveFactor),4082        NewLoad->getType(), NewLoad,4083        /*FMFSource=*/nullptr, "strided.vec");4084 4085    const DataLayout &DL = Instr->getDataLayout();4086    for (unsigned I = 0, J = 0; I < InterleaveFactor; ++I) {4087      Instruction *Member = Group->getMember(I);4088      // Skip the gaps in the group.4089      if (!Member)4090        continue;4091 4092      Value *StridedVec = State.Builder.CreateExtractValue(NewLoad, I);4093      // If this member has different type, cast the result type.4094      if (Member->getType() != ScalarTy) {4095        VectorType *OtherVTy = VectorType::get(Member->getType(), State.VF);4096        StridedVec =4097            createBitOrPointerCast(State.Builder, StridedVec, OtherVTy, DL);4098      }4099 4100      State.set(getVPValue(J), StridedVec);4101      ++J;4102    }4103    return;4104  } // End for interleaved load.4105 4106  // The sub vector type for current instruction.4107  auto *SubVT = VectorType::get(ScalarTy, State.VF);4108  // Vectorize the interleaved store group.4109  ArrayRef<VPValue *> StoredValues = getStoredValues();4110  // Collect the stored vector from each member.4111  SmallVector<Value *, 4> StoredVecs;4112  const DataLayout &DL = Instr->getDataLayout();4113  for (unsigned I = 0, StoredIdx = 0; I < InterleaveFactor; I++) {4114    Instruction *Member = Group->getMember(I);4115    // Skip the gaps in the group.4116    if (!Member) {4117      StoredVecs.push_back(PoisonValue::get(SubVT));4118      continue;4119    }4120 4121    Value *StoredVec = State.get(StoredValues[StoredIdx]);4122    // If this member has different type, cast it to a unified type.4123    if (StoredVec->getType() != SubVT)4124      StoredVec = createBitOrPointerCast(State.Builder, StoredVec, SubVT, DL);4125 4126    StoredVecs.push_back(StoredVec);4127    ++StoredIdx;4128  }4129 4130  // Interleave all the smaller vectors into one wider vector.4131  Value *IVec = interleaveVectors(State.Builder, StoredVecs, "interleaved.vec");4132  CallInst *NewStore =4133      State.Builder.CreateIntrinsic(Type::getVoidTy(Ctx), Intrinsic::vp_store,4134                                    {IVec, ResAddr, GroupMask, InterleaveEVL});4135  NewStore->addParamAttr(1,4136                         Attribute::getWithAlignment(Ctx, Group->getAlign()));4137 4138  applyMetadata(*NewStore);4139  // TODO: Also manage existing metadata using VPIRMetadata.4140  Group->addMetadata(NewStore);4141}4142 4143#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)4144void VPInterleaveEVLRecipe::printRecipe(raw_ostream &O, const Twine &Indent,4145                                        VPSlotTracker &SlotTracker) const {4146  const InterleaveGroup<Instruction> *IG = getInterleaveGroup();4147  O << Indent << "INTERLEAVE-GROUP with factor " << IG->getFactor() << " at ";4148  IG->getInsertPos()->printAsOperand(O, false);4149  O << ", ";4150  getAddr()->printAsOperand(O, SlotTracker);4151  O << ", ";4152  getEVL()->printAsOperand(O, SlotTracker);4153  if (VPValue *Mask = getMask()) {4154    O << ", ";4155    Mask->printAsOperand(O, SlotTracker);4156  }4157 4158  unsigned OpIdx = 0;4159  for (unsigned i = 0; i < IG->getFactor(); ++i) {4160    if (!IG->getMember(i))4161      continue;4162    if (getNumStoreOperands() > 0) {4163      O << "\n" << Indent << "  vp.store ";4164      getOperand(2 + OpIdx)->printAsOperand(O, SlotTracker);4165      O << " to index " << i;4166    } else {4167      O << "\n" << Indent << "  ";4168      getVPValue(OpIdx)->printAsOperand(O, SlotTracker);4169      O << " = vp.load from index " << i;4170    }4171    ++OpIdx;4172  }4173}4174#endif4175 4176InstructionCost VPInterleaveBase::computeCost(ElementCount VF,4177                                              VPCostContext &Ctx) const {4178  Instruction *InsertPos = getInsertPos();4179  // Find the VPValue index of the interleave group. We need to skip gaps.4180  unsigned InsertPosIdx = 0;4181  for (unsigned Idx = 0; IG->getFactor(); ++Idx)4182    if (auto *Member = IG->getMember(Idx)) {4183      if (Member == InsertPos)4184        break;4185      InsertPosIdx++;4186    }4187  Type *ValTy = Ctx.Types.inferScalarType(4188      getNumDefinedValues() > 0 ? getVPValue(InsertPosIdx)4189                                : getStoredValues()[InsertPosIdx]);4190  auto *VectorTy = cast<VectorType>(toVectorTy(ValTy, VF));4191  unsigned AS = cast<PointerType>(Ctx.Types.inferScalarType(getAddr()))4192                    ->getAddressSpace();4193 4194  unsigned InterleaveFactor = IG->getFactor();4195  auto *WideVecTy = VectorType::get(ValTy, VF * InterleaveFactor);4196 4197  // Holds the indices of existing members in the interleaved group.4198  SmallVector<unsigned, 4> Indices;4199  for (unsigned IF = 0; IF < InterleaveFactor; IF++)4200    if (IG->getMember(IF))4201      Indices.push_back(IF);4202 4203  // Calculate the cost of the whole interleaved group.4204  InstructionCost Cost = Ctx.TTI.getInterleavedMemoryOpCost(4205      InsertPos->getOpcode(), WideVecTy, IG->getFactor(), Indices,4206      IG->getAlign(), AS, Ctx.CostKind, getMask(), NeedsMaskForGaps);4207 4208  if (!IG->isReverse())4209    return Cost;4210 4211  return Cost + IG->getNumMembers() *4212                    Ctx.TTI.getShuffleCost(TargetTransformInfo::SK_Reverse,4213                                           VectorTy, VectorTy, {}, Ctx.CostKind,4214                                           0);4215}4216 4217#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)4218void VPCanonicalIVPHIRecipe::printRecipe(raw_ostream &O, const Twine &Indent,4219                                         VPSlotTracker &SlotTracker) const {4220  O << Indent << "EMIT ";4221  printAsOperand(O, SlotTracker);4222  O << " = CANONICAL-INDUCTION ";4223  printOperands(O, SlotTracker);4224}4225#endif4226 4227bool VPWidenPointerInductionRecipe::onlyScalarsGenerated(bool IsScalable) {4228  return vputils::onlyScalarValuesUsed(this) &&4229         (!IsScalable || vputils::onlyFirstLaneUsed(this));4230}4231 4232#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)4233void VPWidenPointerInductionRecipe::printRecipe(4234    raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const {4235  assert((getNumOperands() == 3 || getNumOperands() == 5) &&4236         "unexpected number of operands");4237  O << Indent << "EMIT ";4238  printAsOperand(O, SlotTracker);4239  O << " = WIDEN-POINTER-INDUCTION ";4240  getStartValue()->printAsOperand(O, SlotTracker);4241  O << ", ";4242  getStepValue()->printAsOperand(O, SlotTracker);4243  O << ", ";4244  getOperand(2)->printAsOperand(O, SlotTracker);4245  if (getNumOperands() == 5) {4246    O << ", ";4247    getOperand(3)->printAsOperand(O, SlotTracker);4248    O << ", ";4249    getOperand(4)->printAsOperand(O, SlotTracker);4250  }4251}4252 4253void VPExpandSCEVRecipe::printRecipe(raw_ostream &O, const Twine &Indent,4254                                     VPSlotTracker &SlotTracker) const {4255  O << Indent << "EMIT ";4256  printAsOperand(O, SlotTracker);4257  O << " = EXPAND SCEV " << *Expr;4258}4259#endif4260 4261void VPWidenCanonicalIVRecipe::execute(VPTransformState &State) {4262  Value *CanonicalIV = State.get(getOperand(0), /*IsScalar*/ true);4263  Type *STy = CanonicalIV->getType();4264  IRBuilder<> Builder(State.CFG.PrevBB->getTerminator());4265  ElementCount VF = State.VF;4266  Value *VStart = VF.isScalar()4267                      ? CanonicalIV4268                      : Builder.CreateVectorSplat(VF, CanonicalIV, "broadcast");4269  Value *VStep = createStepForVF(Builder, STy, VF, getUnrollPart(*this));4270  if (VF.isVector()) {4271    VStep = Builder.CreateVectorSplat(VF, VStep);4272    VStep =4273        Builder.CreateAdd(VStep, Builder.CreateStepVector(VStep->getType()));4274  }4275  Value *CanonicalVectorIV = Builder.CreateAdd(VStart, VStep, "vec.iv");4276  State.set(this, CanonicalVectorIV);4277}4278 4279#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)4280void VPWidenCanonicalIVRecipe::printRecipe(raw_ostream &O, const Twine &Indent,4281                                           VPSlotTracker &SlotTracker) const {4282  O << Indent << "EMIT ";4283  printAsOperand(O, SlotTracker);4284  O << " = WIDEN-CANONICAL-INDUCTION ";4285  printOperands(O, SlotTracker);4286}4287#endif4288 4289void VPFirstOrderRecurrencePHIRecipe::execute(VPTransformState &State) {4290  auto &Builder = State.Builder;4291  // Create a vector from the initial value.4292  auto *VectorInit = getStartValue()->getLiveInIRValue();4293 4294  Type *VecTy = State.VF.isScalar()4295                    ? VectorInit->getType()4296                    : VectorType::get(VectorInit->getType(), State.VF);4297 4298  BasicBlock *VectorPH =4299      State.CFG.VPBB2IRBB.at(getParent()->getCFGPredecessor(0));4300  if (State.VF.isVector()) {4301    auto *IdxTy = Builder.getInt32Ty();4302    auto *One = ConstantInt::get(IdxTy, 1);4303    IRBuilder<>::InsertPointGuard Guard(Builder);4304    Builder.SetInsertPoint(VectorPH->getTerminator());4305    auto *RuntimeVF = getRuntimeVF(Builder, IdxTy, State.VF);4306    auto *LastIdx = Builder.CreateSub(RuntimeVF, One);4307    VectorInit = Builder.CreateInsertElement(4308        PoisonValue::get(VecTy), VectorInit, LastIdx, "vector.recur.init");4309  }4310 4311  // Create a phi node for the new recurrence.4312  PHINode *Phi = PHINode::Create(VecTy, 2, "vector.recur");4313  Phi->insertBefore(State.CFG.PrevBB->getFirstInsertionPt());4314  Phi->addIncoming(VectorInit, VectorPH);4315  State.set(this, Phi);4316}4317 4318InstructionCost4319VPFirstOrderRecurrencePHIRecipe::computeCost(ElementCount VF,4320                                             VPCostContext &Ctx) const {4321  if (VF.isScalar())4322    return Ctx.TTI.getCFInstrCost(Instruction::PHI, Ctx.CostKind);4323 4324  return 0;4325}4326 4327#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)4328void VPFirstOrderRecurrencePHIRecipe::printRecipe(4329    raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const {4330  O << Indent << "FIRST-ORDER-RECURRENCE-PHI ";4331  printAsOperand(O, SlotTracker);4332  O << " = phi ";4333  printOperands(O, SlotTracker);4334}4335#endif4336 4337void VPReductionPHIRecipe::execute(VPTransformState &State) {4338  // Reductions do not have to start at zero. They can start with4339  // any loop invariant values.4340  VPValue *StartVPV = getStartValue();4341 4342  // In order to support recurrences we need to be able to vectorize Phi nodes.4343  // Phi nodes have cycles, so we need to vectorize them in two stages. This is4344  // stage #1: We create a new vector PHI node with no incoming edges. We'll use4345  // this value when we vectorize all of the instructions that use the PHI.4346  BasicBlock *VectorPH =4347      State.CFG.VPBB2IRBB.at(getParent()->getCFGPredecessor(0));4348  bool ScalarPHI = State.VF.isScalar() || isInLoop();4349  Value *StartV = State.get(StartVPV, ScalarPHI);4350  Type *VecTy = StartV->getType();4351 4352  BasicBlock *HeaderBB = State.CFG.PrevBB;4353  assert(State.CurrentParentLoop->getHeader() == HeaderBB &&4354         "recipe must be in the vector loop header");4355  auto *Phi = PHINode::Create(VecTy, 2, "vec.phi");4356  Phi->insertBefore(HeaderBB->getFirstInsertionPt());4357  State.set(this, Phi, isInLoop());4358 4359  Phi->addIncoming(StartV, VectorPH);4360}4361 4362#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)4363void VPReductionPHIRecipe::printRecipe(raw_ostream &O, const Twine &Indent,4364                                       VPSlotTracker &SlotTracker) const {4365  O << Indent << "WIDEN-REDUCTION-PHI ";4366 4367  printAsOperand(O, SlotTracker);4368  O << " = phi ";4369  printOperands(O, SlotTracker);4370  if (getVFScaleFactor() > 1)4371    O << " (VF scaled by 1/" << getVFScaleFactor() << ")";4372}4373#endif4374 4375void VPWidenPHIRecipe::execute(VPTransformState &State) {4376  Value *Op0 = State.get(getOperand(0));4377  Type *VecTy = Op0->getType();4378  Instruction *VecPhi = State.Builder.CreatePHI(VecTy, 2, Name);4379  State.set(this, VecPhi);4380}4381 4382#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)4383void VPWidenPHIRecipe::printRecipe(raw_ostream &O, const Twine &Indent,4384                                   VPSlotTracker &SlotTracker) const {4385  O << Indent << "WIDEN-PHI ";4386 4387  printAsOperand(O, SlotTracker);4388  O << " = phi ";4389  printPhiOperands(O, SlotTracker);4390}4391#endif4392 4393// TODO: It would be good to use the existing VPWidenPHIRecipe instead and4394// remove VPActiveLaneMaskPHIRecipe.4395void VPActiveLaneMaskPHIRecipe::execute(VPTransformState &State) {4396  BasicBlock *VectorPH =4397      State.CFG.VPBB2IRBB.at(getParent()->getCFGPredecessor(0));4398  Value *StartMask = State.get(getOperand(0));4399  PHINode *Phi =4400      State.Builder.CreatePHI(StartMask->getType(), 2, "active.lane.mask");4401  Phi->addIncoming(StartMask, VectorPH);4402  State.set(this, Phi);4403}4404 4405#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)4406void VPActiveLaneMaskPHIRecipe::printRecipe(raw_ostream &O, const Twine &Indent,4407                                            VPSlotTracker &SlotTracker) const {4408  O << Indent << "ACTIVE-LANE-MASK-PHI ";4409 4410  printAsOperand(O, SlotTracker);4411  O << " = phi ";4412  printOperands(O, SlotTracker);4413}4414#endif4415 4416#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)4417void VPEVLBasedIVPHIRecipe::printRecipe(raw_ostream &O, const Twine &Indent,4418                                        VPSlotTracker &SlotTracker) const {4419  O << Indent << "EXPLICIT-VECTOR-LENGTH-BASED-IV-PHI ";4420 4421  printAsOperand(O, SlotTracker);4422  O << " = phi ";4423  printOperands(O, SlotTracker);4424}4425#endif4426