LLVM  13.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  /// Check if \p I can be widened at the start of \p Range and possibly
60  /// decrease the range such that the returned value holds for the entire \p
61  /// Range. The function should not be called for memory instructions or calls.
62  bool shouldWiden(Instruction *I, VFRange &Range) const;
63 
64  /// Check if the load or store instruction \p I should widened for \p
65  /// Range.Start and potentially masked. Such instructions are handled by a
66  /// recipe that takes an additional VPInstruction for the mask.
67  VPRecipeBase *tryToWidenMemory(Instruction *I, VFRange &Range,
68  VPlanPtr &Plan);
69 
70  /// Check if an induction recipe should be constructed for \I. If so build and
71  /// return it. If not, return null.
72  VPWidenIntOrFpInductionRecipe *tryToOptimizeInductionPHI(PHINode *Phi,
73  VPlan &Plan) const;
74 
75  /// Optimize the special case where the operand of \p I is a constant integer
76  /// induction variable.
78  tryToOptimizeInductionTruncate(TruncInst *I, VFRange &Range,
79  VPlan &Plan) const;
80 
81  /// Handle non-loop phi nodes. Return a VPValue, if all incoming values match
82  /// or a new VPBlendRecipe otherwise. Currently all such phi nodes are turned
83  /// into a sequence of select instructions as the vectorizer currently
84  /// performs full if-conversion.
85  VPRecipeOrVPValueTy tryToBlend(PHINode *Phi, VPlanPtr &Plan);
86 
87  /// Handle call instructions. If \p CI can be widened for \p Range.Start,
88  /// return a new VPWidenCallRecipe. Range.End may be decreased to ensure same
89  /// decision from \p Range.Start to \p Range.End.
90  VPWidenCallRecipe *tryToWidenCall(CallInst *CI, VFRange &Range,
91  VPlan &Plan) const;
92 
93  /// Check if \p I has an opcode that can be widened and return a VPWidenRecipe
94  /// if it can. The function should only be called if the cost-model indicates
95  /// that widening should be performed.
96  VPWidenRecipe *tryToWiden(Instruction *I, VPlan &Plan) const;
97 
98  /// 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.
99  VPRecipeOrVPValueTy toVPRecipeResult(VPRecipeBase *R) const { return R; }
100 
101 public:
102  VPRecipeBuilder(Loop *OrigLoop, const TargetLibraryInfo *TLI,
105  PredicatedScalarEvolution &PSE, VPBuilder &Builder)
106  : OrigLoop(OrigLoop), TLI(TLI), Legal(Legal), CM(CM), PSE(PSE),
107  Builder(Builder) {}
108 
109  /// Check if an existing VPValue can be used for \p Instr or a recipe can be
110  /// create for \p I withing the given VF \p Range. If an existing VPValue can
111  /// be used or if a recipe can be created, return it. Otherwise return a
112  /// VPRecipeOrVPValueTy with nullptr.
114  VPlanPtr &Plan);
115 
116  /// Set the recipe created for given ingredient. This operation is a no-op for
117  /// ingredients that were not marked using a nullptr entry in the map.
119  if (!Ingredient2Recipe.count(I))
120  return;
121  assert(Ingredient2Recipe[I] == nullptr &&
122  "Recipe already set for ingredient");
123  Ingredient2Recipe[I] = R;
124  }
125 
126  /// A helper function that computes the predicate of the block BB, assuming
127  /// that the header block of the loop is set to True. It returns the *entry*
128  /// mask for the block BB.
130 
131  /// A helper function that computes the predicate of the edge between SRC
132  /// and DST.
134 
135  /// Mark given ingredient for recording its recipe once one is created for
136  /// it.
138  assert((!Ingredient2Recipe.count(I) || Ingredient2Recipe[I] == nullptr) &&
139  "Recipe already set for ingredient");
140  Ingredient2Recipe[I] = nullptr;
141  }
142 
143  /// Return the recipe created for given ingredient.
145  assert(Ingredient2Recipe.count(I) &&
146  "Recording this ingredients recipe was not requested");
147  assert(Ingredient2Recipe[I] != nullptr &&
148  "Ingredient doesn't have a recipe");
149  return Ingredient2Recipe[I];
150  }
151 
152  /// Create a replicating region for instruction \p I that requires
153  /// predication. \p PredRecipe is a VPReplicateRecipe holding \p I.
155  VPlanPtr &Plan);
156 
157  /// Build a VPReplicationRecipe for \p I and enclose it within a Region if it
158  /// is predicated. \return \p VPBB augmented with this new recipe if \p I is
159  /// not predicated, otherwise \return a new VPBasicBlock that succeeds the new
160  /// Region. Update the packing decision of predicated instructions if they
161  /// feed \p I. Range.End may be decreased to ensure same recipe behavior from
162  /// \p Range.Start to \p Range.End.
164  Instruction *I, VFRange &Range, VPBasicBlock *VPBB,
166  VPlanPtr &Plan);
167 };
168 } // end namespace llvm
169 
170 #endif // LLVM_TRANSFORMS_VECTORIZE_VPRECIPEBUILDER_H
llvm
This class represents lattice values for constants.
Definition: AllocatorList.h:23
llvm::VPBasicBlock
VPBasicBlock serves as the leaf of the Hierarchical Control-Flow Graph.
Definition: VPlan.h:1385
llvm::Loop
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:529
llvm::VPRecipeBuilder::VPRecipeBuilder
VPRecipeBuilder(Loop *OrigLoop, const TargetLibraryInfo *TLI, LoopVectorizationLegality *Legal, LoopVectorizationCostModel &CM, PredicatedScalarEvolution &PSE, VPBuilder &Builder)
Definition: VPRecipeBuilder.h:102
llvm::PredicatedScalarEvolution
An interface layer with SCEV used to manage how we see SCEV expressions for values in the context of ...
Definition: ScalarEvolution.h:2119
llvm::LoopVectorizationLegality
LoopVectorizationLegality checks if it is legal to vectorize a loop, and to what vectorization factor...
Definition: LoopVectorizationLegality.h:213
DenseMap.h
llvm::VPlanPtr
std::unique_ptr< VPlan > VPlanPtr
Definition: VPlan.h:91
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:816
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:71
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
llvm::LoopVectorizationCostModel
LoopVectorizationCostModel - estimates the expected speedups due to vectorization.
Definition: LoopVectorize.cpp:1200
llvm::VPBuilder
VPlan-based builder utility analogous to IRBuilder.
Definition: LoopVectorizationPlanner.h:40
llvm::VPRecipeBuilder::handleReplication
VPBasicBlock * handleReplication(Instruction *I, VFRange &Range, VPBasicBlock *VPBB, DenseMap< Instruction *, VPReplicateRecipe * > &PredInst2Recipe, VPlanPtr &Plan)
Build a VPReplicationRecipe for I and enclose it within a Region if it is predicated.
Definition: LoopVectorize.cpp:8537
llvm::VPRecipeBuilder::recordRecipeOf
void recordRecipeOf(Instruction *I)
Mark given ingredient for recording its recipe once one is created for it.
Definition: VPRecipeBuilder.h:137
llvm::Instruction
Definition: Instruction.h:45
llvm::VPValue
Definition: VPlanValue.h:44
llvm::VPRecipeBuilder::tryToCreateWidenRecipe
VPRecipeOrVPValueTy tryToCreateWidenRecipe(Instruction *Instr, 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:8613
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:8259
llvm::VPRegionBlock
VPRegionBlock represents a collection of VPBasicBlocks and VPRegionBlocks which form a Single-Entry-S...
Definition: VPlan.h:1478
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:790
llvm::TruncInst
This class represents a truncation of integer types.
Definition: Instructions.h:4691
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:908
PointerUnion.h
llvm::VPRecipeBuilder::setRecipe
void setRecipe(Instruction *I, VPRecipeBase *R)
Set the recipe created for given ingredient.
Definition: VPRecipeBuilder.h:118
Builder
assume Assume Builder
Definition: AssumeBundleBuilder.cpp:643
llvm::PointerUnion
A discriminated union of two or more pointer types, with the discriminator in the low bit of the poin...
Definition: PointerUnion.h:149
llvm::VPRecipeBase
VPRecipeBase is a base class modeling a sequence of one or more output IR instructions.
Definition: VPlan.h:603
llvm::TargetLibraryInfo
Provides information about what library functions are available for the current target.
Definition: TargetLibraryInfo.h:202
llvm::VPRecipeBuilder::createReplicateRegion
VPRegionBlock * createReplicateRegion(Instruction *I, VPRecipeBase *PredRecipe, VPlanPtr &Plan)
Create a replicating region for instruction I that requires predication.
Definition: LoopVectorize.cpp:8580
llvm::VPRecipeBuilder::getRecipe
VPRecipeBase * getRecipe(Instruction *I)
Return the recipe created for given ingredient.
Definition: VPRecipeBuilder.h:144
llvm::PHINode
Definition: Instructions.h:2572
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:8215
llvm::CallInst
This class represents a function call, abstracting a target machine's calling convention.
Definition: Instructions.h:1450
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::VPlan
VPlan models a candidate for vectorization, encoding various decisions take to produce efficient outp...
Definition: VPlan.h:1684