LLVM  16.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  VPBasicBlock *VPBB, VPlanPtr &Plan);
105 
106  /// 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.
107  VPRecipeOrVPValueTy toVPRecipeResult(VPRecipeBase *R) const { return R; }
108 
109 public:
110  VPRecipeBuilder(Loop *OrigLoop, const TargetLibraryInfo *TLI,
113  PredicatedScalarEvolution &PSE, VPBuilder &Builder)
114  : OrigLoop(OrigLoop), TLI(TLI), Legal(Legal), CM(CM), PSE(PSE),
115  Builder(Builder) {}
116 
117  /// Check if an existing VPValue can be used for \p Instr or a recipe can be
118  /// create for \p I withing the given VF \p Range. If an existing VPValue can
119  /// be used or if a recipe can be created, return it. Otherwise return a
120  /// VPRecipeOrVPValueTy with nullptr.
123  VFRange &Range, VPBasicBlock *VPBB,
124  VPlanPtr &Plan);
125 
126  /// Set the recipe created for given ingredient. This operation is a no-op for
127  /// ingredients that were not marked using a nullptr entry in the map.
129  if (!Ingredient2Recipe.count(I))
130  return;
131  assert(Ingredient2Recipe[I] == nullptr &&
132  "Recipe already set for ingredient");
133  Ingredient2Recipe[I] = R;
134  }
135 
136  /// A helper function that computes the predicate of the block BB, assuming
137  /// that the header block of the loop is set to True. It returns the *entry*
138  /// mask for the block BB.
140 
141  /// A helper function that computes the predicate of the edge between SRC
142  /// and DST.
144 
145  /// Mark given ingredient for recording its recipe once one is created for
146  /// it.
148  assert((!Ingredient2Recipe.count(I) || Ingredient2Recipe[I] == nullptr) &&
149  "Recipe already set for ingredient");
150  Ingredient2Recipe[I] = nullptr;
151  }
152 
153  /// Return the recipe created for given ingredient.
155  assert(Ingredient2Recipe.count(I) &&
156  "Recording this ingredients recipe was not requested");
157  assert(Ingredient2Recipe[I] != nullptr &&
158  "Ingredient doesn't have a recipe");
159  return Ingredient2Recipe[I];
160  }
161 
162  /// Create a replicating region for \p PredRecipe.
164  VPlanPtr &Plan);
165 
166  /// Build a VPReplicationRecipe for \p I and enclose it within a Region if it
167  /// is predicated. \return \p VPBB augmented with this new recipe if \p I is
168  /// not predicated, otherwise \return a new VPBasicBlock that succeeds the new
169  /// Region. Update the packing decision of predicated instructions if they
170  /// feed \p I. Range.End may be decreased to ensure same recipe behavior from
171  /// \p Range.Start to \p Range.End.
173  Instruction *I, VFRange &Range, VPBasicBlock *VPBB,
174  VPlanPtr &Plan);
175 
176  /// Add the incoming values from the backedge to reduction & first-order
177  /// recurrence cross-iteration phis.
178  void fixHeaderPhis();
179 };
180 } // end namespace llvm
181 
182 #endif // LLVM_TRANSFORMS_VECTORIZE_VPRECIPEBUILDER_H
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
llvm::VPBasicBlock
VPBasicBlock serves as the leaf of the Hierarchical Control-Flow Graph.
Definition: VPlan.h:2065
llvm::Loop
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:547
llvm::VPRecipeBuilder::VPRecipeBuilder
VPRecipeBuilder(Loop *OrigLoop, const TargetLibraryInfo *TLI, LoopVectorizationLegality *Legal, LoopVectorizationCostModel &CM, PredicatedScalarEvolution &PSE, VPBuilder &Builder)
Definition: VPRecipeBuilder.h:110
llvm::PredicatedScalarEvolution
An interface layer with SCEV used to manage how we see SCEV expressions for values in the context of ...
Definition: ScalarEvolution.h:2222
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1199
llvm::LoopVectorizationLegality
LoopVectorizationLegality checks if it is legal to vectorize a loop, and to what vectorization factor...
Definition: LoopVectorizationLegality.h:241
DenseMap.h
llvm::VPlanPtr
std::unique_ptr< VPlan > VPlanPtr
Definition: VPlan.h:103
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:145
llvm::VPWidenCallRecipe
A recipe for widening Call instructions.
Definition: VPlan.h:952
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:83
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:55
llvm::LoopVectorizationCostModel
LoopVectorizationCostModel - estimates the expected speedups due to vectorization.
Definition: LoopVectorize.cpp:1145
llvm::VPReplicateRecipe
VPReplicateRecipe replicates a given instruction producing multiple scalar copies of the original sca...
Definition: VPlan.h:1545
llvm::VPRecipeBuilder::createReplicateRegion
VPRegionBlock * createReplicateRegion(VPReplicateRecipe *PredRecipe, VPlanPtr &Plan)
Create a replicating region for PredRecipe.
Definition: LoopVectorize.cpp:8539
llvm::VPBuilder
VPlan-based builder utility analogous to IRBuilder.
Definition: LoopVectorizationPlanner.h:43
llvm::VPRecipeBuilder::recordRecipeOf
void recordRecipeOf(Instruction *I)
Mark given ingredient for recording its recipe once one is created for it.
Definition: VPRecipeBuilder.h:147
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:8073
llvm::VPRegionBlock
VPRegionBlock represents a collection of VPBasicBlocks and VPRegionBlocks which form a Single-Entry-S...
Definition: VPlan.h:2189
Operands
mir Rename Register Operands
Definition: MIRNamerPass.cpp:74
llvm::IRSimilarity::Legal
@ Legal
Definition: IRSimilarityIdentifier.h:77
llvm::TruncInst
This class represents a truncation of integer types.
Definition: Instructions.h:4808
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:1055
PointerUnion.h
llvm::VPRecipeBuilder::setRecipe
void setRecipe(Instruction *I, VPRecipeBase *R)
Set the recipe created for given ingredient.
Definition: VPRecipeBuilder.h:128
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::VPRecipeBuilder::tryToCreateWidenRecipe
VPRecipeOrVPValueTy tryToCreateWidenRecipe(Instruction *Instr, ArrayRef< VPValue * > Operands, VFRange &Range, VPBasicBlock *VPBB, 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:8576
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:663
llvm::TargetLibraryInfo
Provides information about what library functions are available for the current target.
Definition: TargetLibraryInfo.h:225
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:8457
llvm::VPRecipeBuilder::getRecipe
VPRecipeBase * getRecipe(Instruction *I)
Return the recipe created for given ingredient.
Definition: VPRecipeBuilder.h:154
llvm::PHINode
Definition: Instructions.h:2697
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:8028
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:8447
llvm::VPlan
VPlan models a candidate for vectorization, encoding various decisions take to produce efficient outp...
Definition: VPlan.h:2544