212 lines · c
1//===- VPRecipeBuilder.h - Helper class to build recipes --------*- 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_VPRECIPEBUILDER_H10#define LLVM_TRANSFORMS_VECTORIZE_VPRECIPEBUILDER_H11 12#include "LoopVectorizationPlanner.h"13#include "VPlan.h"14#include "llvm/ADT/DenseMap.h"15#include "llvm/Analysis/ScalarEvolutionExpressions.h"16 17namespace llvm {18 19class LoopVectorizationLegality;20class LoopVectorizationCostModel;21class TargetLibraryInfo;22class TargetTransformInfo;23struct HistogramInfo;24struct VFRange;25 26/// A chain of instructions that form a partial reduction.27/// Designed to match either:28/// reduction_bin_op (extend (A), accumulator), or29/// reduction_bin_op (bin_op (extend (A), (extend (B))), accumulator).30struct PartialReductionChain {31 PartialReductionChain(Instruction *Reduction, Instruction *ExtendA,32 Instruction *ExtendB, Instruction *ExtendUser)33 : Reduction(Reduction), ExtendA(ExtendA), ExtendB(ExtendB),34 ExtendUser(ExtendUser) {}35 /// The top-level binary operation that forms the reduction to a scalar36 /// after the loop body.37 Instruction *Reduction;38 /// The extension of each of the inner binary operation's operands.39 Instruction *ExtendA;40 Instruction *ExtendB;41 42 /// The user of the extends that is then reduced.43 Instruction *ExtendUser;44};45 46/// Helper class to create VPRecipies from IR instructions.47class VPRecipeBuilder {48 /// The VPlan new recipes are added to.49 VPlan &Plan;50 51 /// The loop that we evaluate.52 Loop *OrigLoop;53 54 /// Target Library Info.55 const TargetLibraryInfo *TLI;56 57 // Target Transform Info.58 const TargetTransformInfo *TTI;59 60 /// The legality analysis.61 LoopVectorizationLegality *Legal;62 63 /// The profitablity analysis.64 LoopVectorizationCostModel &CM;65 66 PredicatedScalarEvolution &PSE;67 68 VPBuilder &Builder;69 70 /// The mask of each VPBB, generated earlier and used for predicating recipes71 /// in VPBB.72 /// TODO: remove by applying predication when generating the masks.73 DenseMap<VPBasicBlock *, VPValue *> &BlockMaskCache;74 75 // VPlan construction support: Hold a mapping from ingredients to76 // their recipe.77 DenseMap<Instruction *, VPRecipeBase *> Ingredient2Recipe;78 79 /// Cross-iteration reduction & first-order recurrence phis for which we need80 /// to add the incoming value from the backedge after all recipes have been81 /// created.82 SmallVector<VPHeaderPHIRecipe *, 4> PhisToFix;83 84 /// A mapping of partial reduction exit instructions to their scaling factor.85 DenseMap<const Instruction *, unsigned> ScaledReductionMap;86 87 /// Check if \p I can be widened at the start of \p Range and possibly88 /// decrease the range such that the returned value holds for the entire \p89 /// Range. The function should not be called for memory instructions or calls.90 bool shouldWiden(Instruction *I, VFRange &Range) const;91 92 /// Check if the load or store instruction \p VPI should widened for \p93 /// Range.Start and potentially masked. Such instructions are handled by a94 /// recipe that takes an additional VPInstruction for the mask.95 VPWidenMemoryRecipe *tryToWidenMemory(VPInstruction *VPI, VFRange &Range);96 97 /// Check if an induction recipe should be constructed for \p VPI. If so build98 /// and return it. If not, return null.99 VPHeaderPHIRecipe *tryToOptimizeInductionPHI(VPInstruction *VPI);100 101 /// Optimize the special case where the operand of \p VPI is a constant102 /// integer induction variable.103 VPWidenIntOrFpInductionRecipe *104 tryToOptimizeInductionTruncate(VPInstruction *VPI, VFRange &Range);105 106 /// Handle call instructions. If \p VPI can be widened for \p Range.Start,107 /// return a new VPWidenCallRecipe or VPWidenIntrinsicRecipe. Range.End may be108 /// decreased to ensure same decision from \p Range.Start to \p Range.End.109 VPSingleDefRecipe *tryToWidenCall(VPInstruction *VPI, VFRange &Range);110 111 /// Check if \p VPI has an opcode that can be widened and return a112 /// VPWidenRecipe if it can. The function should only be called if the113 /// cost-model indicates that widening should be performed.114 VPWidenRecipe *tryToWiden(VPInstruction *VPI);115 116 /// Makes Histogram count operations safe for vectorization, by emitting a117 /// llvm.experimental.vector.histogram.add intrinsic in place of the118 /// Load + Add|Sub + Store operations that perform the histogram in the119 /// original scalar loop.120 VPHistogramRecipe *tryToWidenHistogram(const HistogramInfo *HI,121 VPInstruction *VPI);122 123 /// Examines reduction operations to see if the target can use a cheaper124 /// operation with a wider per-iteration input VF and narrower PHI VF.125 /// Each element within Chains is a pair with a struct containing reduction126 /// information and the scaling factor between the number of elements in127 /// the input and output.128 /// Recursively calls itself to identify chained scaled reductions.129 /// Returns true if this invocation added an entry to Chains, otherwise false.130 /// i.e. returns false in the case that a subcall adds an entry to Chains,131 /// but the top-level call does not.132 bool getScaledReductions(133 Instruction *PHI, Instruction *RdxExitInstr, VFRange &Range,134 SmallVectorImpl<std::pair<PartialReductionChain, unsigned>> &Chains);135 136public:137 VPRecipeBuilder(VPlan &Plan, Loop *OrigLoop, const TargetLibraryInfo *TLI,138 const TargetTransformInfo *TTI,139 LoopVectorizationLegality *Legal,140 LoopVectorizationCostModel &CM,141 PredicatedScalarEvolution &PSE, VPBuilder &Builder,142 DenseMap<VPBasicBlock *, VPValue *> &BlockMaskCache)143 : Plan(Plan), OrigLoop(OrigLoop), TLI(TLI), TTI(TTI), Legal(Legal),144 CM(CM), PSE(PSE), Builder(Builder), BlockMaskCache(BlockMaskCache) {}145 146 std::optional<unsigned> getScalingForReduction(const Instruction *ExitInst) {147 auto It = ScaledReductionMap.find(ExitInst);148 return It == ScaledReductionMap.end() ? std::nullopt149 : std::make_optional(It->second);150 }151 152 /// Find all possible partial reductions in the loop and track all of those153 /// that are valid so recipes can be formed later.154 void collectScaledReductions(VFRange &Range);155 156 /// Create and return a widened recipe for \p R if one can be created within157 /// the given VF \p Range.158 VPRecipeBase *tryToCreateWidenRecipe(VPSingleDefRecipe *R, VFRange &Range);159 160 /// Create and return a partial reduction recipe for a reduction instruction161 /// along with binary operation and reduction phi operands.162 VPRecipeBase *tryToCreatePartialReduction(VPInstruction *Reduction,163 unsigned ScaleFactor);164 165 /// Set the recipe created for given ingredient.166 void setRecipe(Instruction *I, VPRecipeBase *R) {167 assert(!Ingredient2Recipe.contains(I) &&168 "Cannot reset recipe for instruction.");169 Ingredient2Recipe[I] = R;170 }171 172 /// Returns the *entry* mask for block \p VPBB or null if the mask is173 /// all-true.174 VPValue *getBlockInMask(VPBasicBlock *VPBB) const {175 return BlockMaskCache.lookup(VPBB);176 }177 178 /// Return the recipe created for given ingredient.179 VPRecipeBase *getRecipe(Instruction *I) {180 assert(Ingredient2Recipe.count(I) &&181 "Recording this ingredients recipe was not requested");182 assert(Ingredient2Recipe[I] != nullptr &&183 "Ingredient doesn't have a recipe");184 return Ingredient2Recipe[I];185 }186 187 /// Build a VPReplicationRecipe for \p VPI. If it is predicated, add the mask188 /// as last operand. Range.End may be decreased to ensure same recipe behavior189 /// from \p Range.Start to \p Range.End.190 VPReplicateRecipe *handleReplication(VPInstruction *VPI, VFRange &Range);191 192 VPValue *getVPValueOrAddLiveIn(Value *V) {193 if (auto *I = dyn_cast<Instruction>(V)) {194 if (auto *R = Ingredient2Recipe.lookup(I))195 return R->getVPSingleValue();196 }197 return Plan.getOrAddLiveIn(V);198 }199 200 void updateBlockMaskCache(DenseMap<VPValue *, VPValue *> &Old2New) {201 for (auto &[_, V] : BlockMaskCache) {202 if (auto *New = Old2New.lookup(V)) {203 V->replaceAllUsesWith(New);204 V = New;205 }206 }207 }208};209} // end namespace llvm210 211#endif // LLVM_TRANSFORMS_VECTORIZE_VPRECIPEBUILDER_H212