251 lines · c
1//===- VPlanUtils.h - VPlan-related utilities -------------------*- C++ -*-===//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#ifndef LLVM_TRANSFORMS_VECTORIZE_VPLANUTILS_H10#define LLVM_TRANSFORMS_VECTORIZE_VPLANUTILS_H11 12#include "VPlan.h"13#include "llvm/Support/Compiler.h"14 15namespace llvm {16class MemoryLocation;17class ScalarEvolution;18class SCEV;19} // namespace llvm20 21namespace llvm {22 23namespace vputils {24/// Returns true if only the first lane of \p Def is used.25bool onlyFirstLaneUsed(const VPValue *Def);26 27/// Returns true if only the first part of \p Def is used.28bool onlyFirstPartUsed(const VPValue *Def);29 30/// Returns true if only scalar values of \p Def are used by all users.31bool onlyScalarValuesUsed(const VPValue *Def);32 33/// Get or create a VPValue that corresponds to the expansion of \p Expr. If \p34/// Expr is a SCEVConstant or SCEVUnknown, return a VPValue wrapping the live-in35/// value. Otherwise return a VPExpandSCEVRecipe to expand \p Expr. If \p Plan's36/// pre-header already contains a recipe expanding \p Expr, return it. If not,37/// create a new one.38VPValue *getOrCreateVPValueForSCEVExpr(VPlan &Plan, const SCEV *Expr);39 40/// Return the SCEV expression for \p V. Returns SCEVCouldNotCompute if no41/// SCEV expression could be constructed.42const SCEV *getSCEVExprForVPValue(const VPValue *V, ScalarEvolution &SE,43 const Loop *L = nullptr);44 45/// Returns true if \p VPV is a single scalar, either because it produces the46/// same value for all lanes or only has its first lane used.47bool isSingleScalar(const VPValue *VPV);48 49/// Return true if \p V is a header mask in \p Plan.50bool isHeaderMask(const VPValue *V, const VPlan &Plan);51 52/// Checks if \p V is uniform across all VF lanes and UF parts. It is considered53/// as such if it is either loop invariant (defined outside the vector region)54/// or its operand is known to be uniform across all VFs and UFs (e.g.55/// VPDerivedIV or VPCanonicalIVPHI).56bool isUniformAcrossVFsAndUFs(VPValue *V);57 58/// Returns the header block of the first, top-level loop, or null if none59/// exist.60VPBasicBlock *getFirstLoopHeader(VPlan &Plan, VPDominatorTree &VPDT);61 62/// Get the VF scaling factor applied to the recipe's output, if the recipe has63/// one.64unsigned getVFScaleFactor(VPRecipeBase *R);65 66/// Returns the VPValue representing the uncountable exit comparison used by67/// AnyOf if the recipes it depends on can be traced back to live-ins and68/// the addresses (in GEP/PtrAdd form) of any (non-masked) load used in69/// generating the values for the comparison. The recipes are stored in70/// \p Recipes, and recipes forming an address for a load are also added to71/// \p GEPs.72LLVM_ABI_FOR_TEST73std::optional<VPValue *>74getRecipesForUncountableExit(VPlan &Plan,75 SmallVectorImpl<VPRecipeBase *> &Recipes,76 SmallVectorImpl<VPRecipeBase *> &GEPs);77 78/// Return a MemoryLocation for \p R with noalias metadata populated from79/// \p R, if the recipe is supported and std::nullopt otherwise. The pointer of80/// the location is conservatively set to nullptr.81std::optional<MemoryLocation> getMemoryLocation(const VPRecipeBase &R);82 83/// Extracts and returns NoWrap and FastMath flags from the induction binop in84/// \p ID.85inline VPIRFlags getFlagsFromIndDesc(const InductionDescriptor &ID) {86 if (ID.getKind() == InductionDescriptor::IK_FpInduction)87 return ID.getInductionBinOp()->getFastMathFlags();88 89 if (auto *OBO = dyn_cast_if_present<OverflowingBinaryOperator>(90 ID.getInductionBinOp()))91 return VPIRFlags::WrapFlagsTy(OBO->hasNoUnsignedWrap(),92 OBO->hasNoSignedWrap());93 94 assert(ID.getKind() == InductionDescriptor::IK_IntInduction &&95 "Expected int induction");96 return VPIRFlags::WrapFlagsTy(false, false);97}98} // namespace vputils99 100//===----------------------------------------------------------------------===//101// Utilities for modifying predecessors and successors of VPlan blocks.102//===----------------------------------------------------------------------===//103 104/// Class that provides utilities for VPBlockBases in VPlan.105class VPBlockUtils {106public:107 VPBlockUtils() = delete;108 109 /// Insert disconnected VPBlockBase \p NewBlock after \p BlockPtr. Add \p110 /// NewBlock as successor of \p BlockPtr and \p BlockPtr as predecessor of \p111 /// NewBlock, and propagate \p BlockPtr parent to \p NewBlock. \p BlockPtr's112 /// successors are moved from \p BlockPtr to \p NewBlock. \p NewBlock must113 /// have neither successors nor predecessors.114 static void insertBlockAfter(VPBlockBase *NewBlock, VPBlockBase *BlockPtr) {115 assert(NewBlock->getSuccessors().empty() &&116 NewBlock->getPredecessors().empty() &&117 "Can't insert new block with predecessors or successors.");118 NewBlock->setParent(BlockPtr->getParent());119 SmallVector<VPBlockBase *> Succs(BlockPtr->successors());120 for (VPBlockBase *Succ : Succs) {121 Succ->replacePredecessor(BlockPtr, NewBlock);122 NewBlock->appendSuccessor(Succ);123 }124 BlockPtr->clearSuccessors();125 connectBlocks(BlockPtr, NewBlock);126 }127 128 /// Insert disconnected block \p NewBlock before \p Blockptr. First129 /// disconnects all predecessors of \p BlockPtr and connects them to \p130 /// NewBlock. Add \p NewBlock as predecessor of \p BlockPtr and \p BlockPtr as131 /// successor of \p NewBlock.132 static void insertBlockBefore(VPBlockBase *NewBlock, VPBlockBase *BlockPtr) {133 assert(NewBlock->getSuccessors().empty() &&134 NewBlock->getPredecessors().empty() &&135 "Can't insert new block with predecessors or successors.");136 NewBlock->setParent(BlockPtr->getParent());137 for (VPBlockBase *Pred : to_vector(BlockPtr->predecessors())) {138 Pred->replaceSuccessor(BlockPtr, NewBlock);139 NewBlock->appendPredecessor(Pred);140 }141 BlockPtr->clearPredecessors();142 connectBlocks(NewBlock, BlockPtr);143 }144 145 /// Insert disconnected VPBlockBases \p IfTrue and \p IfFalse after \p146 /// BlockPtr. Add \p IfTrue and \p IfFalse as succesors of \p BlockPtr and \p147 /// BlockPtr as predecessor of \p IfTrue and \p IfFalse. Propagate \p BlockPtr148 /// parent to \p IfTrue and \p IfFalse. \p BlockPtr must have no successors149 /// and \p IfTrue and \p IfFalse must have neither successors nor150 /// predecessors.151 static void insertTwoBlocksAfter(VPBlockBase *IfTrue, VPBlockBase *IfFalse,152 VPBlockBase *BlockPtr) {153 assert(IfTrue->getSuccessors().empty() &&154 "Can't insert IfTrue with successors.");155 assert(IfFalse->getSuccessors().empty() &&156 "Can't insert IfFalse with successors.");157 BlockPtr->setTwoSuccessors(IfTrue, IfFalse);158 IfTrue->setPredecessors({BlockPtr});159 IfFalse->setPredecessors({BlockPtr});160 IfTrue->setParent(BlockPtr->getParent());161 IfFalse->setParent(BlockPtr->getParent());162 }163 164 /// Connect VPBlockBases \p From and \p To bi-directionally. If \p PredIdx is165 /// -1, append \p From to the predecessors of \p To, otherwise set \p To's166 /// predecessor at \p PredIdx to \p From. If \p SuccIdx is -1, append \p To to167 /// the successors of \p From, otherwise set \p From's successor at \p SuccIdx168 /// to \p To. Both VPBlockBases must have the same parent, which can be null.169 /// Both VPBlockBases can be already connected to other VPBlockBases.170 static void connectBlocks(VPBlockBase *From, VPBlockBase *To,171 unsigned PredIdx = -1u, unsigned SuccIdx = -1u) {172 assert((From->getParent() == To->getParent()) &&173 "Can't connect two block with different parents");174 assert((SuccIdx != -1u || From->getNumSuccessors() < 2) &&175 "Blocks can't have more than two successors.");176 if (SuccIdx == -1u)177 From->appendSuccessor(To);178 else179 From->getSuccessors()[SuccIdx] = To;180 181 if (PredIdx == -1u)182 To->appendPredecessor(From);183 else184 To->getPredecessors()[PredIdx] = From;185 }186 187 /// Disconnect VPBlockBases \p From and \p To bi-directionally. Remove \p To188 /// from the successors of \p From and \p From from the predecessors of \p To.189 static void disconnectBlocks(VPBlockBase *From, VPBlockBase *To) {190 assert(To && "Successor to disconnect is null.");191 From->removeSuccessor(To);192 To->removePredecessor(From);193 }194 195 /// Reassociate all the blocks connected to \p Old so that they now point to196 /// \p New.197 static void reassociateBlocks(VPBlockBase *Old, VPBlockBase *New) {198 for (auto *Pred : to_vector(Old->getPredecessors()))199 Pred->replaceSuccessor(Old, New);200 for (auto *Succ : to_vector(Old->getSuccessors()))201 Succ->replacePredecessor(Old, New);202 New->setPredecessors(Old->getPredecessors());203 New->setSuccessors(Old->getSuccessors());204 Old->clearPredecessors();205 Old->clearSuccessors();206 }207 208 /// Return an iterator range over \p Range which only includes \p BlockTy209 /// blocks. The accesses are casted to \p BlockTy.210 template <typename BlockTy, typename T>211 static auto blocksOnly(const T &Range) {212 // Create BaseTy with correct const-ness based on BlockTy.213 using BaseTy = std::conditional_t<std::is_const<BlockTy>::value,214 const VPBlockBase, VPBlockBase>;215 216 // We need to first create an iterator range over (const) BlocktTy & instead217 // of (const) BlockTy * for filter_range to work properly.218 auto Mapped =219 map_range(Range, [](BaseTy *Block) -> BaseTy & { return *Block; });220 auto Filter = make_filter_range(221 Mapped, [](BaseTy &Block) { return isa<BlockTy>(&Block); });222 return map_range(Filter, [](BaseTy &Block) -> BlockTy * {223 return cast<BlockTy>(&Block);224 });225 }226 227 /// Inserts \p BlockPtr on the edge between \p From and \p To. That is, update228 /// \p From's successor to \p To to point to \p BlockPtr and \p To's229 /// predecessor from \p From to \p BlockPtr. \p From and \p To are added to \p230 /// BlockPtr's predecessors and successors respectively. There must be a231 /// single edge between \p From and \p To.232 static void insertOnEdge(VPBlockBase *From, VPBlockBase *To,233 VPBlockBase *BlockPtr) {234 unsigned SuccIdx = From->getIndexForSuccessor(To);235 unsigned PredIx = To->getIndexForPredecessor(From);236 VPBlockUtils::connectBlocks(From, BlockPtr, -1, SuccIdx);237 VPBlockUtils::connectBlocks(BlockPtr, To, PredIx, -1);238 }239 240 /// Returns true if \p VPB is a loop header, based on regions or \p VPDT in241 /// their absence.242 static bool isHeader(const VPBlockBase *VPB, const VPDominatorTree &VPDT);243 244 /// Returns true if \p VPB is a loop latch, using isHeader().245 static bool isLatch(const VPBlockBase *VPB, const VPDominatorTree &VPDT);246};247 248} // namespace llvm249 250#endif251