llvm/lib/Transforms/Vectorize/VPlanUtils.h

//===- VPlanUtils.h - VPlan-related utilities -------------------*- C++ -*-===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//

#ifndef LLVM_TRANSFORMS_VECTORIZE_VPLANUTILS_H
#define LLVM_TRANSFORMS_VECTORIZE_VPLANUTILS_H

#include "VPlan.h"
#include "llvm/Support/BlockFrequency.h"
#include "llvm/Support/BranchProbability.h"
#include "llvm/Support/Compiler.h"

namespace llvm {
class DominatorTree;
class MemoryLocation;
class ScalarEvolution;
class SCEV;
class PredicatedScalarEvolution;
} // namespace llvm

namespace llvm {

namespace vputils {
/// Returns true if only the first lane of \p Def is used.
bool onlyFirstLaneUsed(const VPValue *Def);

/// Returns true if only the first part of \p Def is used.
bool onlyFirstPartUsed(const VPValue *Def);

/// Returns true if only scalar values of \p Def are used by all users.
bool onlyScalarValuesUsed(const VPValue *Def);

/// Get or create a VPValue that corresponds to the expansion of \p Expr. If \p
/// Expr is a SCEVConstant or SCEVUnknown, return a VPValue wrapping the live-in
/// value. Otherwise return a VPExpandSCEVRecipe to expand \p Expr. If \p Plan's
/// pre-header already contains a recipe expanding \p Expr, return it. If not,
/// create a new one.
VPValue *getOrCreateVPValueForSCEVExpr(VPlan &Plan, const SCEV *Expr);

/// Return the SCEV expression for \p V. Returns SCEVCouldNotCompute if no
/// SCEV expression could be constructed.
LLVM_ABI_FOR_TEST const SCEV *
getSCEVExprForVPValue(const VPValue *V, PredicatedScalarEvolution &PSE,
                      const Loop *L = nullptr);

/// If the pointer operand \p Addr of a memory access is an affine AddRec
/// w.r.t. \p L with a constant stride, return the stride in units of
/// \p AccessTy. Otherwise return std::nullopt.
std::optional<int64_t> getConstantStride(VPValue *Addr, Type *AccessTy,
                                         PredicatedScalarEvolution &PSE,
                                         const Loop *L);

/// Returns true if \p Addr is an address SCEV that can be passed to
/// TTI::getAddressComputationCost, i.e. the address SCEV is loop invariant, an
/// affine AddRec (i.e. induction ), or an add expression of such operands or a
/// sign-extended AddRec.
bool isAddressSCEVForCost(const SCEV *Addr, ScalarEvolution &SE, const Loop *L);

/// Returns true if \p VPV is a single scalar, either because it produces the
/// same value for all lanes or only has its first lane used.
bool isSingleScalar(const VPValue *VPV);

/// Checks if \p V is uniform across all VF lanes and UF parts. It is considered
/// as such if it is either loop invariant (defined outside the vector region)
/// or its operands are known to be uniform across all VFs and UFs (e.g.
/// VPDerivedIV or the canonical IV).
LLVM_ABI_FOR_TEST bool isUniformAcrossVFsAndUFs(const VPValue *V);

/// Return true if \p V is elementwise, i.e. none of the lanes are permuted.
bool isElementwise(const VPValue *V);

/// Returns true if \p R produces scalar values for all VF lanes.
bool doesGeneratePerAllLanes(const VPRecipeBase *R);

/// Returns the header block of the first, top-level loop, or null if none
/// exist.
VPBasicBlock *getFirstLoopHeader(VPlan &Plan, VPDominatorTree &VPDT);

/// Get the VF scaling factor applied to the recipe's output, if the recipe has
/// one.
unsigned getVFScaleFactor(VPRecipeBase *R);

/// Return true if we do not know how to (mechanically) hoist or sink \p R.
/// When sinking, passing \p Sinking = true ensures that assumes aren't sunk.
/// Returns true for recipes that access memory.
bool cannotHoistOrSinkRecipe(const VPRecipeBase &R, bool Sinking = false);

/// Return the intrinsic ID underlying a call.
template <typename Ty> Intrinsic::ID getIntrinsicID(const Ty *R) {
  if (const auto *Intr = dyn_cast<VPWidenIntrinsicRecipe>(R))
    return Intr->getVectorIntrinsicID();
  if (const auto *Call = dyn_cast<VPWidenCallRecipe>(R))
    return Call->getCalledScalarFunction()->getIntrinsicID();

  auto GetCalleeIntrinsic = [&](VPValue *CalleeOp) -> Intrinsic::ID {
    if (!isa<VPIRValue>(CalleeOp))
      return Intrinsic::not_intrinsic;
    auto *F = cast<Function>(CalleeOp->getLiveInIRValue());
    return F->getIntrinsicID();
  };
  if (const auto *Rep = dyn_cast<VPReplicateRecipe>(R))
    if (Rep->getOpcode() == Instruction::Call)
      // The callee is the last operand, excluding the mask if predicated.
      return GetCalleeIntrinsic(
          Rep->getOperand(Rep->getNumOperandsWithoutMask() - 1));
  if (const auto *VPI = dyn_cast<VPInstruction>(R)) {
    if (VPI->getOpcode() == Instruction::Call)
      // The callee is the last operand, excluding the mask if masked.
      return GetCalleeIntrinsic(
          VPI->getOperand(VPI->getNumOperandsWithoutMask() - 1));
    if (VPI->getOpcode() == VPInstruction::Intrinsic) {
      return cast<VPConstantInt>(VPI->getOperand(VPI->getNumOperands() - 1))
          ->getZExtValue();
    }
  }
  return Intrinsic::not_intrinsic;
}

/// Return the instruction opcode for the recipe defining \p V or 0 for
/// unsupported recipes and VPValues not defined by a recipe.
unsigned getOpcode(const VPValue *V);

/// Get the instruction opcode or intrinsic ID for the recipe defining \p V.
/// Returns an optional pair, where the first element indicates whether it is an
/// intrinsic ID.
std::optional<std::pair<bool, unsigned>>
getOpcodeOrIntrinsicID(const VPValue *V);

/// Return a MemoryLocation for \p R with noalias metadata populated from
/// \p R, if the recipe is supported and std::nullopt otherwise. The pointer of
/// the location is conservatively set to nullptr.
std::optional<MemoryLocation> getMemoryLocation(const VPRecipeBase &R);

/// Extracts and returns NoWrap flags from \p PhiR and fast-math flags from \p
/// ID.
VPIRFlags getFlagsForInduction(const InductionDescriptor &ID,
                               const VPPhi *PhiR);

/// Search \p Start's users for a recipe satisfying \p Pred, looking through
/// recipes with definitions.
template <typename PredT>
inline VPRecipeBase *findRecipe(VPValue *Start, PredT Pred) {
  SetVector<VPValue *> Worklist;
  Worklist.insert(Start);
  for (unsigned I = 0; I != Worklist.size(); ++I) {
    VPValue *Cur = Worklist[I];
    auto *R = Cur->getDefiningRecipe();
    if (!R)
      continue;
    if (Pred(R))
      return R;
    for (VPUser *U : Cur->users()) {
      for (VPValue *V : cast<VPRecipeBase>(U)->definedValues())
        Worklist.insert(V);
    }
  }
  return nullptr;
}

/// Find the canonical IV increment of \p Plan's vector loop region. Returns
/// nullptr if not found.
VPInstruction *findCanonicalIVIncrement(VPlan &Plan);

/// Returns the GEP nowrap flags for \p Ptr, looking through pointer casts
/// mirroring Value::stripPointerCasts.
GEPNoWrapFlags getGEPFlagsForPtr(VPValue *Ptr);

/// Returns true if \p V is used as part of the address of another load or
/// store.
bool isUsedByLoadStoreAddress(const VPValue *V);

/// Find the ComputeReductionResult recipe for \p PhiR, looking through selects
/// inserted for predicated reductions or tail folding.
VPInstruction *findComputeReductionResult(VPReductionPHIRecipe *PhiR);

/// Finds the incoming alias-mask within the vector preheader.
VPValue *findIncomingAliasMask(const VPlan &Plan);

/// Returns the (early exiting block, exit block) pairs of \p Plan, i.e. all
/// edges to an exit block that do not come from \p MiddleVPBB.
SmallVector<std::pair<VPBasicBlock *, VPIRBasicBlock *>>
getEarlyExits(const VPlan &Plan, const VPBlockBase *MiddleVPBB);

/// Create a scalar-iv-steps recipe over \p Plan's canonical IV for an
/// induction of \p Kind with \p InductionOpcode / \p FPBinOp, start value \p
/// StartV and step \p Step, truncated to \p TruncI's type if \p TruncI is
/// non-null, inserting recipes via \p Builder.
VPScalarIVStepsRecipe *createScalarIVSteps(
    VPlan &Plan, InductionDescriptor::InductionKind Kind,
    Instruction::BinaryOps InductionOpcode, FPMathOperator *FPBinOp,
    Instruction *TruncI, VPValue *StartV, VPValue *Step, DebugLoc DL,
    VPBuilder &Builder, const VPIRFlags::WrapFlagsTy &Flags = {});

/// Scalarize a VPWidenPointerInductionRecipe by replacing it with a PtrAdd
/// (IndStart, ScalarIVSteps (0, Step)). This is used when the recipe only
/// generates scalar values.
VPValue *scalarizeVPWidenPointerInduction(VPWidenPointerInductionRecipe *PtrIV,
                                          VPlan &Plan, VPBuilder &Builder);

/// Returns true if \p R is dead, i.e. none of its defined values are used and
/// it has no side effects (with the exception of conditional assumes, which are
/// considered dead as their conditions may be flattened).
bool isDeadRecipe(VPRecipeBase &R);

/// Recursively delete \p V and any of its operands that become dead.
void recursivelyDeleteDeadRecipes(VPValue *V);

/// Collect all users of \p V, looking through recipes that define other values.
SmallVector<VPUser *> collectUsersRecursively(VPValue *V);

/// Try to fold \p R using InstSimplifyFolder. Will succeed and return a
/// non-nullptr VPValue for a handled opcode or intrinsic ID if corresponding \p
/// Operands are foldable live-ins.
VPIRValue *tryToFoldLiveIns(VPSingleDefRecipe &R, ArrayRef<VPValue *> Operands,
                            const DataLayout &DL);

/// Insert phis to reconstruct SSA for a single value starting from \p VPBB. \p
/// Defs is a map of definitions at specific blocks. Returns the
/// reconstructed value at VPBB. Use if the CFG has been modified such that a
/// def no longer dominates all its uses. Every block leading to VPBB must be
/// reachable from the entry and the plan must be plain-CFG (not contain any
/// regions).
LLVM_ABI_FOR_TEST VPValue *
reconstructSSA(VPBasicBlock *VPBB, DenseMap<VPBasicBlock *, VPValue *> &Defs);

/// Returns \p Freq as a BranchProbability, relative to the full mass.
BranchProbability getExecutionProbability(BlockFrequency Freq);

/// Computes for each block in \p Blocks, which must be in reverse post-order,
/// the frequency with which it executes relative to the first (header) block,
/// and whether that frequency was composed using any estimated branch weights.
/// The frequency of a block is the sum over its incoming edges, or std::nullopt
/// if any edge on a path reaching it lacks branch weights. Edges to blocks
/// outside \p Blocks are ignored.
DenseMap<const VPBasicBlock *, std::optional<VPExecutionFrequency>>
computeExecutionFrequencies(ArrayRef<VPBasicBlock *> Blocks);

namespace detail {

/// Template-independent implementation for pullOutPermutations.
void pullOutPermutationsImpl(
    VPlan &Plan, function_ref<VPValue *(VPValue *Op)> Perm,
    function_ref<VPSingleDefRecipe *(VPSingleDefRecipe *X)> Build);
} // namespace detail

/// Removes the permutation pattern \p Perm from any elementwise operations
/// in the plan, by constructing a new permutation via \p Build.
/// e.g. binop(perm(x), perm(y)) -> perm(binop(x,y)).
template <typename Match_t, typename Builder>
void pullOutPermutations(VPlan &Plan, Match_t Perm, Builder Build) {
  // Convert matcher to function returing the matched VPValue.
  auto MatchPerm = [&Perm](VPValue *Op) -> VPValue * {
    VPValue *X;
    return match(Op, Perm(X)) ? X : nullptr;
  };
  detail::pullOutPermutationsImpl(Plan, MatchPerm, Build);
}

} // namespace vputils

/// Lightweight SCEV-to-VPlan expander. Converts SCEV expressions into
/// VPInstructions and live-ins. SCEVAddRecExprs are wrapped in a
/// VPExpandSCEVRecipe to be expanded to IR later.
class VPSCEVExpander {
  VPBuilder &Builder;
  ScalarEvolution &SE;
  DebugLoc DL;

  /// When true, nested SCEVUDivExprs are expanded so that they cannot divide by
  /// zero, matching SCEVExpander's SafeUDivMode.
  bool SafeUDivMode = false;

  /// Try to find a loop-invariant IR value in the plan's entry block whose
  /// SCEV matches \p S. Returns the corresponding live-in VPValue, or nullptr
  /// if none is found.
  VPValue *tryToReuseIRValue(const SCEV *S);

public:
  VPSCEVExpander(VPBuilder &Builder, ScalarEvolution &SE, DebugLoc DL)
      : Builder(Builder), SE(SE), DL(DL) {}

  /// Expand \p S into recipes and live-ins using the builder.
  VPValue *expand(const SCEV *S);
};
//===----------------------------------------------------------------------===//
// Utilities for modifying predecessors and successors of VPlan blocks.
//===----------------------------------------------------------------------===//

/// Class that provides utilities for VPBlockBases in VPlan.
class VPBlockUtils {
public:
  VPBlockUtils() = delete;

  /// Insert disconnected VPBlockBase \p NewBlock after \p BlockPtr. Add \p
  /// NewBlock as successor of \p BlockPtr and \p BlockPtr as predecessor of \p
  /// NewBlock, and propagate \p BlockPtr parent to \p NewBlock. \p BlockPtr's
  /// successors are moved from \p BlockPtr to \p NewBlock. \p NewBlock must
  /// have neither successors nor predecessors.
  static void insertBlockAfter(VPBlockBase *NewBlock, VPBlockBase *BlockPtr) {
    assert(!NewBlock->hasSuccessors() && !NewBlock->hasPredecessors() &&
           "Can't insert new block with predecessors or successors.");
    NewBlock->setParent(BlockPtr->getParent());
    transferSuccessors(BlockPtr, NewBlock);
    connectBlocks(BlockPtr, NewBlock);
  }

  /// Insert disconnected block \p NewBlock before \p Blockptr. First
  /// disconnects all predecessors of \p BlockPtr and connects them to \p
  /// NewBlock. Add \p NewBlock as predecessor of \p BlockPtr and \p BlockPtr as
  /// successor of \p NewBlock.
  static void insertBlockBefore(VPBlockBase *NewBlock, VPBlockBase *BlockPtr) {
    assert(!NewBlock->hasSuccessors() && !NewBlock->hasPredecessors() &&
           "Can't insert new block with predecessors or successors.");
    NewBlock->setParent(BlockPtr->getParent());
    for (VPBlockBase *Pred : to_vector(BlockPtr->predecessors()))
      replaceSuccessor(Pred, BlockPtr, NewBlock);
    connectBlocks(NewBlock, BlockPtr);
  }

  /// Insert disconnected VPBlockBases \p IfTrue and \p IfFalse after \p
  /// BlockPtr. Add \p IfTrue and \p IfFalse as succesors of \p BlockPtr and \p
  /// BlockPtr as predecessor of \p IfTrue and \p IfFalse. Propagate \p BlockPtr
  /// parent to \p IfTrue and \p IfFalse. \p BlockPtr must have no successors
  /// and \p IfTrue and \p IfFalse must have neither successors nor
  /// predecessors.
  static void insertTwoBlocksAfter(VPBlockBase *IfTrue, VPBlockBase *IfFalse,
                                   VPBlockBase *BlockPtr) {
    assert(!IfTrue->hasSuccessors() && "Can't insert IfTrue with successors.");
    assert(!IfFalse->hasSuccessors() &&
           "Can't insert IfFalse with successors.");
    BlockPtr->setTwoSuccessors(IfTrue, IfFalse);
    IfTrue->setPredecessors({BlockPtr});
    IfFalse->setPredecessors({BlockPtr});
    IfTrue->setParent(BlockPtr->getParent());
    IfFalse->setParent(BlockPtr->getParent());
  }

  /// Connect VPBlockBases \p From and \p To bi-directionally. If \p PredIdx is
  /// -1, append \p From to the predecessors of \p To, otherwise set \p To's
  /// predecessor at \p PredIdx to \p From. If \p SuccIdx is -1, append \p To to
  /// the successors of \p From, otherwise set \p From's successor at \p SuccIdx
  /// to \p To. Both VPBlockBases must have the same parent, which can be null.
  /// Both VPBlockBases can be already connected to other VPBlockBases.
  static void connectBlocks(VPBlockBase *From, VPBlockBase *To,
                            unsigned PredIdx = -1u, unsigned SuccIdx = -1u) {
    assert((From->getParent() == To->getParent()) &&
           "Can't connect two block with different parents");

    if (SuccIdx == -1u)
      From->appendSuccessor(To);
    else
      From->getSuccessors()[SuccIdx] = To;

    if (PredIdx == -1u)
      To->appendPredecessor(From);
    else
      To->getPredecessors()[PredIdx] = From;
  }

  /// Disconnect VPBlockBases \p From and \p To bi-directionally. Remove \p To
  /// from the successors of \p From and \p From from the predecessors of \p To.
  static void disconnectBlocks(VPBlockBase *From, VPBlockBase *To) {
    assert(To && "Successor to disconnect is null.");
    From->removeSuccessor(To);
    To->removePredecessor(From);
  }

  /// Redirect the edge from \p From to \p OldSucc to \p NewSucc, keeping \p
  /// From's successor order. \p From is removed from \p OldSucc's predecessors
  /// and appended to \p NewSucc's.
  static void replaceSuccessor(VPBlockBase *From, VPBlockBase *OldSucc,
                               VPBlockBase *NewSucc) {
    From->replaceSuccessor(OldSucc, NewSucc);
    OldSucc->removePredecessor(From);
    NewSucc->appendPredecessor(From);
  }

  /// Reassociate all the blocks connected to \p Old so that they now point to
  /// \p New.
  static void reassociateBlocks(VPBlockBase *Old, VPBlockBase *New) {
    auto Preds = to_vector(Old->getPredecessors());
    auto Succs = to_vector(Old->getSuccessors());
    for (auto *Pred : Preds)
      Pred->replaceSuccessor(Old, New);
    for (auto *Succ : Succs)
      Succ->replacePredecessor(Old, New);
    New->setPredecessors(Old->getPredecessors());
    New->setSuccessors(Old->getSuccessors());
    Old->clearPredecessors();
    Old->clearSuccessors();
  }

  /// Transfer successors from \p Old to \p New. \p New must have no successors.
  static void transferSuccessors(VPBlockBase *Old, VPBlockBase *New) {
    for (auto *Succ : Old->getSuccessors())
      Succ->replacePredecessor(Old, New);
    New->setSuccessors(Old->getSuccessors());
    Old->clearSuccessors();
  }

  /// Clone the CFG for all nodes reachable from \p Entry, including cloning
  /// the blocks and their recipes. Operands of cloned recipes will NOT be
  /// updated. Remapping of operands must be done separately. Returns a pair
  /// with the new entry and exiting blocks of the cloned region. If \p Entry
  /// isn't part of a region, return nullptr for the exiting block.
  static std::pair<VPBlockBase *, VPBlockBase *> cloneFrom(VPBlockBase *Entry);

  /// Return an iterator range over \p Range which only includes \p BlockTy
  /// blocks. The accesses are casted to \p BlockTy.
  template <typename BlockTy, typename T> static auto blocksOnly(T &&Range) {
    return make_isa_range<BlockTy>(std::forward<T>(Range));
  }

  /// Return an iterator range over \p Range with each block cast to \p
  /// BlockTy. Unlike blocksOnly, all blocks in \p Range must be of type
  /// \p BlockTy.
  template <typename BlockTy, typename T> static auto blocksAs(T &&Range) {
    // Create BaseTy with correct const-ness based on BlockTy.
    using BaseTy = std::conditional_t<std::is_const<BlockTy>::value,
                                      const VPBlockBase, VPBlockBase>;
    return map_range(
        Range, [](BaseTy *Block) -> BlockTy * { return cast<BlockTy>(Block); });
  }

  /// Returns the blocks between \p FirstBB and \p LastBB, where FirstBB
  /// to LastBB forms a single-sucessor chain.
  static SmallVector<VPBasicBlock *>
  blocksInSingleSuccessorChainBetween(VPBasicBlock *FirstBB,
                                      VPBasicBlock *LastBB);

  /// Inserts \p BlockPtr on the edge between \p From and \p To. That is, update
  /// \p From's successor to \p To to point to \p BlockPtr and \p To's
  /// predecessor from \p From to \p BlockPtr. \p From and \p To are added to \p
  /// BlockPtr's predecessors and successors respectively. There must be a
  /// single edge between \p From and \p To.
  static void insertOnEdge(VPBlockBase *From, VPBlockBase *To,
                           VPBlockBase *BlockPtr) {
    unsigned SuccIdx = From->getIndexForSuccessor(To);
    unsigned PredIx = To->getIndexForPredecessor(From);
    VPBlockUtils::connectBlocks(From, BlockPtr, -1, SuccIdx);
    VPBlockUtils::connectBlocks(BlockPtr, To, PredIx, -1);
  }

  /// Returns true if \p VPB is a loop header, based on regions or \p VPDT in
  /// their absence.
  static bool isHeader(const VPBlockBase *VPB, const VPDominatorTree &VPDT);

  /// Returns true if \p VPB is a loop latch, using isHeader().
  static bool isLatch(const VPBlockBase *VPB, const VPDominatorTree &VPDT);

  /// Returns the header and latch of the outermost loop of \p Plan in plain
  /// CFG form (before regions are formed).
  static std::pair<VPBasicBlock *, VPBasicBlock *>
  getPlainCFGHeaderAndLatch(const VPlan &Plan);

  /// Returns the middle block of \p Plan in plain CFG form (before regions
  /// are formed).
  static VPBasicBlock *getPlainCFGMiddleBlock(const VPlan &Plan);
};

} // namespace llvm

#endif