LLVM  15.0.0git
VPRecipeBuilder.h
Go to the documentation of this file.
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 
13 #include "VPlan.h"
14 #include "llvm/ADT/DenseMap.h"
15 #include "llvm/ADT/PointerUnion.h"
16 #include "llvm/IR/IRBuilder.h"
17 
18 namespace llvm {
19 
20 class LoopVectorizationLegality;
21 class LoopVectorizationCostModel;
22 class TargetLibraryInfo;
23 
25 
26 /// Helper class to create VPRecipies from IR instructions.
28  /// The loop that we evaluate.
29  Loop *OrigLoop;
30 
31  /// Target Library Info.
32  const TargetLibraryInfo *TLI;
33 
34  /// The legality analysis.
36 
37  /// The profitablity analysis.
39 
41 
42  VPBuilder &Builder;
43 
44  /// When we if-convert we need to create edge masks. We have to cache values
45  /// so that we don't end up with exponential recursion/IR. Note that
46  /// if-conversion currently takes place during VPlan-construction, so these
47  /// caches are only used at that stage.
48  using EdgeMaskCacheTy =
51  EdgeMaskCacheTy EdgeMaskCache;
52  BlockMaskCacheTy BlockMaskCache;
53 
54  // VPlan-VPlan transformations support: Hold a mapping from ingredients to
55  // their recipe. To save on memory, only do so for selected ingredients,
56  // marked by having a nullptr entry in this map.
58 
59  /// Cross-iteration reduction & first-order recurrence phis for which we need
60  /// to add the incoming value from the backedge after all recipes have been
61  /// created.
63 
64  /// Check if \p I can be widened at the start of \p Range and possibly
65  /// decrease the range such that the returned value holds for the entire \p
66  /// Range. The function should not be called for memory instructions or calls.
67  bool shouldWiden(Instruction *I, VFRange &Range) const;
68 
69  /// Check if the load or store instruction \p I should widened for \p
70  /// Range.Start and potentially masked. Such instructions are handled by a
71  /// recipe that takes an additional VPInstruction for the mask.
73  VFRange &Range, VPlanPtr &Plan);
74 
75  /// Check if an induction recipe should be constructed for \p Phi. If so build
76  /// and return it. If not, return null.
77  VPRecipeBase *tryToOptimizeInductionPHI(PHINode *Phi,
79  VPlan &Plan, VFRange &Range);
80 
81  /// Optimize the special case where the operand of \p I is a constant integer
82  /// induction variable.
84  tryToOptimizeInductionTruncate(TruncInst *I, ArrayRef<VPValue *> Operands,
85  VFRange &Range, VPlan &Plan);
86 
87  /// Handle non-loop phi nodes. Return a VPValue, if all incoming values match
88  /// or a new VPBlendRecipe otherwise. Currently all such phi nodes are turned
89  /// into a sequence of select instructions as the vectorizer currently
90  /// performs full if-conversion.
92  VPlanPtr &Plan);
93 
94  /// Handle call instructions. If \p CI can be widened for \p Range.Start,
95  /// return a new VPWidenCallRecipe. Range.End may be decreased to ensure same
96  /// decision from \p Range.Start to \p Range.End.
98  VFRange &Range) const;
99 
100  /// Check if \p I has an opcode that can be widened and return a VPWidenRecipe
101  /// if it can. The function should only be called if the cost-model indicates
102  /// that widening should be performed.
104 
105  /// Return a VPRecipeOrValueTy with VPRecipeBase * being set. This can be used to force the use as VPRecipeBase* for recipe sub-types that also inherit from VPValue.
106  VPRecipeOrVPValueTy toVPRecipeResult(VPRecipeBase *R) const { return R; }
107 
108 public:
109  VPRecipeBuilder(Loop *OrigLoop, const TargetLibraryInfo *TLI,
112  PredicatedScalarEvolution &PSE, VPBuilder &Builder)
113  : OrigLoop(OrigLoop), TLI(TLI), Legal(Legal), CM(CM), PSE(PSE),
114  Builder(Builder) {}
115 
116  /// Check if an existing VPValue can be used for \p Instr or a recipe can be
117  /// create for \p I withing the given VF \p Range. If an existing VPValue can
118  /// be used or if a recipe can be created, return it. Otherwise return a
119  /// VPRecipeOrVPValueTy with nullptr.
122  VFRange &Range, VPlanPtr &Plan);
123 
124  /// Set the recipe created for given ingredient. This operation is a no-op for
125  /// ingredients that were not marked using a nullptr entry in the map.
127  if (!Ingredient2Recipe.count(I))
128  return;
129  assert(Ingredient2Recipe[I] == nullptr &&
130  "Recipe already set for ingredient");
131  Ingredient2Recipe[I] = R;
132  }
133 
134  /// A helper function that computes the predicate of the block BB, assuming
135  /// that the header block of the loop is set to True. It returns the *entry*
136  /// mask for the block BB.
138 
139  /// A helper function that computes the predicate of the edge between SRC
140  /// and DST.
142 
143  /// Mark given ingredient for recording its recipe once one is created for
144  /// it.
146  assert((!Ingredient2Recipe.count(I) || Ingredient2Recipe[I] == nullptr) &&
147  "Recipe already set for ingredient");
148  Ingredient2Recipe[I] = nullptr;
149  }
150 
151  /// Return the recipe created for given ingredient.
153  assert(Ingredient2Recipe.count(I) &&
154  "Recording this ingredients recipe was not requested");
155  assert(Ingredient2Recipe[I] != nullptr &&
156  "Ingredient doesn't have a recipe");
157  return Ingredient2Recipe[I];
158  }
159 
160  /// Create a replicating region for instruction \p I that requires
161  /// predication. \p PredRecipe is a VPReplicateRecipe holding \p I.
163  VPlanPtr &Plan);
164 
165  /// Build a VPReplicationRecipe for \p I and enclose it within a Region if it
166  /// is predicated. \return \p VPBB augmented with this new recipe if \p I is
167  /// not predicated, otherwise \return a new VPBasicBlock that succeeds the new
168  /// Region. Update the packing decision of predicated instructions if they
169  /// feed \p I. Range.End may be decreased to ensure same recipe behavior from
170  /// \p Range.Start to \p Range.End.
172  Instruction *I, VFRange &Range, VPBasicBlock *VPBB,
173  VPlanPtr &Plan);
174 
175  /// Add the incoming values from the backedge to reduction & first-order
176  /// recurrence cross-iteration phis.
177  void fixHeaderPhis();
178 };
179 } // end namespace llvm
180 
181 #endif // LLVM_TRANSFORMS_VECTORIZE_VPRECIPEBUILDER_H
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:17
llvm::VPBasicBlock
VPBasicBlock serves as the leaf of the Hierarchical Control-Flow Graph.
Definition: VPlan.h:1973
llvm::Loop
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:530
llvm::VPRecipeBuilder::VPRecipeBuilder
VPRecipeBuilder(Loop *OrigLoop, const TargetLibraryInfo *TLI, LoopVectorizationLegality *Legal, LoopVectorizationCostModel &CM, PredicatedScalarEvolution &PSE, VPBuilder &Builder)
Definition: VPRecipeBuilder.h:109
llvm::PredicatedScalarEvolution
An interface layer with SCEV used to manage how we see SCEV expressions for values in the context of ...
Definition: ScalarEvolution.h:2176
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1185
llvm::LoopVectorizationLegality
LoopVectorizationLegality checks if it is legal to vectorize a loop, and to what vectorization factor...
Definition: LoopVectorizationLegality.h:248
DenseMap.h
llvm::VPlanPtr
std::unique_ptr< VPlan > VPlanPtr
Definition: VPlan.h:97
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::count
size_type count(const_arg_type_t< KeyT > Val) const
Return 1 if the specified key is in the map, 0 otherwise.
Definition: DenseMap.h:147
llvm::VPWidenCallRecipe
A recipe for widening Call instructions.
Definition: VPlan.h:949
llvm::VPRecipeBuilder
Helper class to create VPRecipies from IR instructions.
Definition: VPRecipeBuilder.h:27
llvm::VFRange
A range of powers-of-2 vectorization factors with fixed start and adjustable end.
Definition: VPlan.h:77
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:55
llvm::LoopVectorizationCostModel
LoopVectorizationCostModel - estimates the expected speedups due to vectorization.
Definition: LoopVectorize.cpp:1226
llvm::VPRecipeBuilder::tryToCreateWidenRecipe
VPRecipeOrVPValueTy tryToCreateWidenRecipe(Instruction *Instr, ArrayRef< VPValue * > Operands, VFRange &Range, VPlanPtr &Plan)
Check if an existing VPValue can be used for Instr or a recipe can be create for I withing the given ...
Definition: LoopVectorize.cpp:8572
llvm::VPBuilder
VPlan-based builder utility analogous to IRBuilder.
Definition: LoopVectorizationPlanner.h:44
llvm::VPRecipeBuilder::recordRecipeOf
void recordRecipeOf(Instruction *I)
Mark given ingredient for recording its recipe once one is created for it.
Definition: VPRecipeBuilder.h:145
llvm::Instruction
Definition: Instruction.h:42
llvm::VPValue
Definition: VPlanValue.h:44
VPlan.h
llvm::VPRecipeBuilder::createBlockInMask
VPValue * createBlockInMask(BasicBlock *BB, VPlanPtr &Plan)
A helper function that computes the predicate of the block BB, assuming that the header block of the ...
Definition: LoopVectorize.cpp:8098
llvm::VPRegionBlock
VPRegionBlock represents a collection of VPBasicBlocks and VPRegionBlocks which form a Single-Entry-S...
Definition: VPlan.h:2089
Operands
mir Rename Register Operands
Definition: MIRNamerPass.cpp:74
llvm::IRSimilarity::Legal
@ Legal
Definition: IRSimilarityIdentifier.h:76
llvm::VPWidenRecipe
VPWidenRecipe is a recipe for producing a copy of vector type its ingredient.
Definition: VPlan.h:921
llvm::TruncInst
This class represents a truncation of integer types.
Definition: Instructions.h:4780
llvm::DenseMap< std::pair< BasicBlock *, BasicBlock * >, VPValue * >
I
#define I(x, y, z)
Definition: MD5.cpp:58
LoopVectorizationPlanner.h
IRBuilder.h
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::VPWidenIntOrFpInductionRecipe
A recipe for handling phi nodes of integer and floating-point inductions, producing their vector valu...
Definition: VPlan.h:1047
PointerUnion.h
llvm::VPRecipeBuilder::setRecipe
void setRecipe(Instruction *I, VPRecipeBase *R)
Set the recipe created for given ingredient.
Definition: VPRecipeBuilder.h:126
Builder
assume Assume Builder
Definition: AssumeBundleBuilder.cpp:651
llvm::ArrayRef
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: APInt.h:32
llvm::PointerUnion
A discriminated union of two or more pointer types, with the discriminator in the low bit of the poin...
Definition: PointerUnion.h:112
llvm::VPRecipeBase
VPRecipeBase is a base class modeling a sequence of one or more output IR instructions.
Definition: VPlan.h:672
llvm::TargetLibraryInfo
Provides information about what library functions are available for the current target.
Definition: TargetLibraryInfo.h:222
llvm::VPRecipeBuilder::createReplicateRegion
VPRegionBlock * createReplicateRegion(Instruction *I, VPRecipeBase *PredRecipe, VPlanPtr &Plan)
Create a replicating region for instruction I that requires predication.
Definition: LoopVectorize.cpp:8538
llvm::VPRecipeBuilder::handleReplication
VPBasicBlock * handleReplication(Instruction *I, VFRange &Range, VPBasicBlock *VPBB, VPlanPtr &Plan)
Build a VPReplicationRecipe for I and enclose it within a Region if it is predicated.
Definition: LoopVectorize.cpp:8456
llvm::VPRecipeBuilder::getRecipe
VPRecipeBase * getRecipe(Instruction *I)
Return the recipe created for given ingredient.
Definition: VPRecipeBuilder.h:152
llvm::PHINode
Definition: Instructions.h:2664
llvm::VPRecipeBuilder::createEdgeMask
VPValue * createEdgeMask(BasicBlock *Src, BasicBlock *Dst, VPlanPtr &Plan)
A helper function that computes the predicate of the edge between SRC and DST.
Definition: LoopVectorize.cpp:8053
llvm::CallInst
This class represents a function call, abstracting a target machine's calling convention.
Definition: Instructions.h:1474
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
llvm::VPRecipeBuilder::fixHeaderPhis
void fixHeaderPhis()
Add the incoming values from the backedge to reduction & first-order recurrence cross-iteration phis.
Definition: LoopVectorize.cpp:8446
llvm::VPlan
VPlan models a candidate for vectorization, encoding various decisions take to produce efficient outp...
Definition: VPlan.h:2443