LLVM  14.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 \I. If so build and
76  /// return it. If not, return null.
78  tryToOptimizeInductionPHI(PHINode *Phi, ArrayRef<VPValue *> Operands) const;
79 
80  /// Optimize the special case where the operand of \p I is a constant integer
81  /// induction variable.
83  tryToOptimizeInductionTruncate(TruncInst *I, ArrayRef<VPValue *> Operands,
84  VFRange &Range, VPlan &Plan) const;
85 
86  /// Handle non-loop phi nodes. Return a VPValue, if all incoming values match
87  /// or a new VPBlendRecipe otherwise. Currently all such phi nodes are turned
88  /// into a sequence of select instructions as the vectorizer currently
89  /// performs full if-conversion.
91  VPlanPtr &Plan);
92 
93  /// Handle call instructions. If \p CI can be widened for \p Range.Start,
94  /// return a new VPWidenCallRecipe. Range.End may be decreased to ensure same
95  /// decision from \p Range.Start to \p Range.End.
97  VFRange &Range) const;
98 
99  /// Check if \p I has an opcode that can be widened and return a VPWidenRecipe
100  /// if it can. The function should only be called if the cost-model indicates
101  /// that widening should be performed.
103 
104  /// 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.
105  VPRecipeOrVPValueTy toVPRecipeResult(VPRecipeBase *R) const { return R; }
106 
107 public:
108  VPRecipeBuilder(Loop *OrigLoop, const TargetLibraryInfo *TLI,
111  PredicatedScalarEvolution &PSE, VPBuilder &Builder)
112  : OrigLoop(OrigLoop), TLI(TLI), Legal(Legal), CM(CM), PSE(PSE),
113  Builder(Builder) {}
114 
115  /// Check if an existing VPValue can be used for \p Instr or a recipe can be
116  /// create for \p I withing the given VF \p Range. If an existing VPValue can
117  /// be used or if a recipe can be created, return it. Otherwise return a
118  /// VPRecipeOrVPValueTy with nullptr.
121  VFRange &Range, VPlanPtr &Plan);
122 
123  /// Set the recipe created for given ingredient. This operation is a no-op for
124  /// ingredients that were not marked using a nullptr entry in the map.
126  if (!Ingredient2Recipe.count(I))
127  return;
128  assert(Ingredient2Recipe[I] == nullptr &&
129  "Recipe already set for ingredient");
130  Ingredient2Recipe[I] = R;
131  }
132 
133  /// A helper function that computes the predicate of the block BB, assuming
134  /// that the header block of the loop is set to True. It returns the *entry*
135  /// mask for the block BB.
137 
138  /// A helper function that computes the predicate of the edge between SRC
139  /// and DST.
141 
142  /// Mark given ingredient for recording its recipe once one is created for
143  /// it.
145  assert((!Ingredient2Recipe.count(I) || Ingredient2Recipe[I] == nullptr) &&
146  "Recipe already set for ingredient");
147  Ingredient2Recipe[I] = nullptr;
148  }
149 
150  /// Return the recipe created for given ingredient.
152  assert(Ingredient2Recipe.count(I) &&
153  "Recording this ingredients recipe was not requested");
154  assert(Ingredient2Recipe[I] != nullptr &&
155  "Ingredient doesn't have a recipe");
156  return Ingredient2Recipe[I];
157  }
158 
159  /// Create a replicating region for instruction \p I that requires
160  /// predication. \p PredRecipe is a VPReplicateRecipe holding \p I.
162  VPlanPtr &Plan);
163 
164  /// Build a VPReplicationRecipe for \p I and enclose it within a Region if it
165  /// is predicated. \return \p VPBB augmented with this new recipe if \p I is
166  /// not predicated, otherwise \return a new VPBasicBlock that succeeds the new
167  /// Region. Update the packing decision of predicated instructions if they
168  /// feed \p I. Range.End may be decreased to ensure same recipe behavior from
169  /// \p Range.Start to \p Range.End.
171  Instruction *I, VFRange &Range, VPBasicBlock *VPBB,
172  VPlanPtr &Plan);
173 
174  /// Add the incoming values from the backedge to reduction & first-order
175  /// recurrence cross-iteration phis.
176  void fixHeaderPhis();
177 };
178 } // end namespace llvm
179 
180 #endif // LLVM_TRANSFORMS_VECTORIZE_VPRECIPEBUILDER_H
llvm
---------------------— PointerInfo ------------------------------------—
Definition: AllocatorList.h:23
llvm::VPBasicBlock
VPBasicBlock serves as the leaf of the Hierarchical Control-Flow Graph.
Definition: VPlan.h:1606
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:108
llvm::PredicatedScalarEvolution
An interface layer with SCEV used to manage how we see SCEV expressions for values in the context of ...
Definition: ScalarEvolution.h:2097
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1168
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:92
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:906
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:72
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
llvm::LoopVectorizationCostModel
LoopVectorizationCostModel - estimates the expected speedups due to vectorization.
Definition: LoopVectorize.cpp:1225
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:9095
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:144
llvm::Instruction
Definition: Instruction.h:45
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:8693
llvm::VPRegionBlock
VPRegionBlock represents a collection of VPBasicBlocks and VPRegionBlocks which form a Single-Entry-S...
Definition: VPlan.h:1720
Operands
mir Rename Register Operands
Definition: MIRNamerPass.cpp:78
llvm::IRSimilarity::Legal
@ Legal
Definition: IRSimilarityIdentifier.h:75
llvm::VPWidenRecipe
VPWidenRecipe is a recipe for producing a copy of vector type its ingredient.
Definition: VPlan.h:878
llvm::TruncInst
This class represents a truncation of integer types.
Definition: Instructions.h:4755
llvm::DenseMap< std::pair< BasicBlock *, BasicBlock * >, VPValue * >
I
#define I(x, y, z)
Definition: MD5.cpp:59
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 and ...
Definition: VPlan.h:1004
PointerUnion.h
llvm::VPRecipeBuilder::setRecipe
void setRecipe(Instruction *I, VPRecipeBase *R)
Set the recipe created for given ingredient.
Definition: VPRecipeBuilder.h:125
Builder
assume Assume Builder
Definition: AssumeBundleBuilder.cpp:650
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:119
llvm::VPRecipeBase
VPRecipeBase is a base class modeling a sequence of one or more output IR instructions.
Definition: VPlan.h:664
llvm::TargetLibraryInfo
Provides information about what library functions are available for the current target.
Definition: TargetLibraryInfo.h:219
llvm::VPRecipeBuilder::createReplicateRegion
VPRegionBlock * createReplicateRegion(Instruction *I, VPRecipeBase *PredRecipe, VPlanPtr &Plan)
Create a replicating region for instruction I that requires predication.
Definition: LoopVectorize.cpp:9061
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:8984
llvm::VPRecipeBuilder::getRecipe
VPRecipeBase * getRecipe(Instruction *I)
Return the recipe created for given ingredient.
Definition: VPRecipeBuilder.h:151
llvm::PHINode
Definition: Instructions.h:2633
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:8649
llvm::CallInst
This class represents a function call, abstracting a target machine's calling convention.
Definition: Instructions.h:1475
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:8974
llvm::VPlan
VPlan models a candidate for vectorization, encoding various decisions take to produce efficient outp...
Definition: VPlan.h:2068