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-exception
6//
7//===----------------------------------------------------------------------===//
8
9#ifndef LLVM_TRANSFORMS_VECTORIZE_VPRECIPEBUILDER_H
10#define LLVM_TRANSFORMS_VECTORIZE_VPRECIPEBUILDER_H
11
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;
22struct HistogramInfo;
23struct VFRange;
24
25/// Helper class to create VPRecipies from IR instructions.
26class VPRecipeBuilder {
27 /// The VPlan new recipes are added to.
28 VPlan &Plan;
29
30 /// Target Library Info.
31 const TargetLibraryInfo *TLI;
32
33 /// The legality analysis.
34 LoopVectorizationLegality *Legal;
35
36 /// The profitablity analysis.
37 LoopVectorizationCostModel &CM;
38
39 VPBuilder &Builder;
40
41 /// The mask of each VPBB, generated earlier and used for predicating recipes
42 /// in VPBB.
43 /// TODO: remove by applying predication when generating the masks.
44 DenseMap<VPBasicBlock *, VPValue *> &BlockMaskCache;
45
46 // VPlan construction support: Hold a mapping from ingredients to
47 // their recipe.
48 DenseMap<Instruction *, VPRecipeBase *> Ingredient2Recipe;
49
50 /// Cross-iteration reduction & first-order recurrence phis for which we need
51 /// to add the incoming value from the backedge after all recipes have been
52 /// created.
53 SmallVector<VPHeaderPHIRecipe *, 4> PhisToFix;
54
55 /// Check if \p I can be widened at the start of \p Range and possibly
56 /// decrease the range such that the returned value holds for the entire \p
57 /// Range. The function should not be called for memory instructions or calls.
58 bool shouldWiden(Instruction *I, VFRange &Range) const;
59
60 /// Check if the load or store instruction \p VPI should widened for \p
61 /// Range.Start and potentially masked. Such instructions are handled by a
62 /// recipe that takes an additional VPInstruction for the mask.
63 VPRecipeBase *tryToWidenMemory(VPInstruction *VPI, VFRange &Range);
64
65 /// Optimize the special case where the operand of \p VPI is a constant
66 /// integer induction variable.
67 VPWidenIntOrFpInductionRecipe *
68 tryToOptimizeInductionTruncate(VPInstruction *VPI, VFRange &Range);
69
70 /// Handle call instructions. If \p VPI can be widened for \p Range.Start,
71 /// return a new VPWidenCallRecipe or VPWidenIntrinsicRecipe. Range.End may be
72 /// decreased to ensure same decision from \p Range.Start to \p Range.End.
73 VPSingleDefRecipe *tryToWidenCall(VPInstruction *VPI, VFRange &Range);
74
75 /// Check if \p VPI has an opcode that can be widened and return a
76 /// VPWidenRecipe if it can. The function should only be called if the
77 /// cost-model indicates that widening should be performed.
78 VPWidenRecipe *tryToWiden(VPInstruction *VPI);
79
80 /// Makes Histogram count operations safe for vectorization, by emitting a
81 /// llvm.experimental.vector.histogram.add intrinsic in place of the
82 /// Load + Add|Sub + Store operations that perform the histogram in the
83 /// original scalar loop.
84 VPHistogramRecipe *tryToWidenHistogram(const HistogramInfo *HI,
85 VPInstruction *VPI);
86
87public:
88 VPRecipeBuilder(VPlan &Plan, const TargetLibraryInfo *TLI,
89 LoopVectorizationLegality *Legal,
90 LoopVectorizationCostModel &CM, VPBuilder &Builder,
91 DenseMap<VPBasicBlock *, VPValue *> &BlockMaskCache)
92 : Plan(Plan), TLI(TLI), Legal(Legal), CM(CM), Builder(Builder),
93 BlockMaskCache(BlockMaskCache) {}
94
95 /// Create and return a widened recipe for a non-phi recipe \p R if one can be
96 /// created within the given VF \p Range.
97 VPRecipeBase *tryToCreateWidenNonPhiRecipe(VPSingleDefRecipe *R,
98 VFRange &Range);
99
100 /// Set the recipe created for given ingredient.
101 void setRecipe(Instruction *I, VPRecipeBase *R) {
102 assert(!Ingredient2Recipe.contains(I) &&
103 "Cannot reset recipe for instruction.");
104 Ingredient2Recipe[I] = R;
105 }
106
107 /// Returns the *entry* mask for block \p VPBB or null if the mask is
108 /// all-true.
109 VPValue *getBlockInMask(VPBasicBlock *VPBB) const {
110 return BlockMaskCache.lookup(Val: VPBB);
111 }
112
113 /// Return the recipe created for given ingredient.
114 VPRecipeBase *getRecipe(Instruction *I) {
115 assert(Ingredient2Recipe.count(I) &&
116 "Recording this ingredients recipe was not requested");
117 assert(Ingredient2Recipe[I] != nullptr &&
118 "Ingredient doesn't have a recipe");
119 return Ingredient2Recipe[I];
120 }
121
122 /// Build a VPReplicationRecipe for \p VPI. If it is predicated, add the mask
123 /// as last operand. Range.End may be decreased to ensure same recipe behavior
124 /// from \p Range.Start to \p Range.End.
125 VPReplicateRecipe *handleReplication(VPInstruction *VPI, VFRange &Range);
126
127 VPValue *getVPValueOrAddLiveIn(Value *V) {
128 if (auto *I = dyn_cast<Instruction>(Val: V)) {
129 if (auto *R = Ingredient2Recipe.lookup(Val: I))
130 return R->getVPSingleValue();
131 }
132 return Plan.getOrAddLiveIn(V);
133 }
134
135 void updateBlockMaskCache(DenseMap<VPValue *, VPValue *> &Old2New) {
136 for (auto &[_, V] : BlockMaskCache) {
137 if (auto *New = Old2New.lookup(Val: V)) {
138 V->replaceAllUsesWith(New);
139 V = New;
140 }
141 }
142 }
143};
144} // end namespace llvm
145
146#endif // LLVM_TRANSFORMS_VECTORIZE_VPRECIPEBUILDER_H
147