VPRecipeBuilder.h revision 360784 
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/IR/IRBuilder.h"
16
17namespace llvm {
18
19class LoopVectorizationLegality;
20class LoopVectorizationCostModel;
21class TargetTransformInfo;
22class TargetLibraryInfo;
23
24/// Helper class to create VPRecipies from IR instructions.
25class VPRecipeBuilder {
26  /// The loop that we evaluate.
27  Loop *OrigLoop;
28
29  /// Target Library Info.
30  const TargetLibraryInfo *TLI;
31
32  /// The legality analysis.
33  LoopVectorizationLegality *Legal;
34
35  /// The profitablity analysis.
36  LoopVectorizationCostModel &CM;
37
38  VPBuilder &Builder;
39
40  /// When we if-convert we need to create edge masks. We have to cache values
41  /// so that we don't end up with exponential recursion/IR. Note that
42  /// if-conversion currently takes place during VPlan-construction, so these
43  /// caches are only used at that stage.
44  using EdgeMaskCacheTy =
45      DenseMap<std::pair<BasicBlock *, BasicBlock *>, VPValue *>;
46  using BlockMaskCacheTy = DenseMap<BasicBlock *, VPValue *>;
47  EdgeMaskCacheTy EdgeMaskCache;
48  BlockMaskCacheTy BlockMaskCache;
49
50  // VPlan-VPlan transformations support: Hold a mapping from ingredients to
51  // their recipe. To save on memory, only do so for selected ingredients,
52  // marked by having a nullptr entry in this map. If those ingredients get a
53  // VPWidenRecipe, also avoid compressing other ingredients into it to avoid
54  // having to split such recipes later.
55  DenseMap<Instruction *, VPRecipeBase *> Ingredient2Recipe;
56  VPWidenRecipe *LastExtensibleRecipe = nullptr;
57
58  /// Set the recipe created for given ingredient. This operation is a no-op for
59  /// ingredients that were not marked using a nullptr entry in the map.
60  void setRecipe(Instruction *I, VPRecipeBase *R) {
61    if (!Ingredient2Recipe.count(I))
62      return;
63    assert(Ingredient2Recipe[I] == nullptr &&
64           "Recipe already set for ingredient");
65    Ingredient2Recipe[I] = R;
66  }
67
68public:
69  /// A helper function that computes the predicate of the block BB, assuming
70  /// that the header block of the loop is set to True. It returns the *entry*
71  /// mask for the block BB.
72  VPValue *createBlockInMask(BasicBlock *BB, VPlanPtr &Plan);
73
74  /// A helper function that computes the predicate of the edge between SRC
75  /// and DST.
76  VPValue *createEdgeMask(BasicBlock *Src, BasicBlock *Dst, VPlanPtr &Plan);
77
78  /// Mark given ingredient for recording its recipe once one is created for
79  /// it.
80  void recordRecipeOf(Instruction *I) {
81    assert((!Ingredient2Recipe.count(I) || Ingredient2Recipe[I] == nullptr) &&
82           "Recipe already set for ingredient");
83    Ingredient2Recipe[I] = nullptr;
84  }
85
86  /// Return the recipe created for given ingredient.
87  VPRecipeBase *getRecipe(Instruction *I) {
88    assert(Ingredient2Recipe.count(I) &&
89           "Recording this ingredients recipe was not requested");
90    assert(Ingredient2Recipe[I] != nullptr &&
91           "Ingredient doesn't have a recipe");
92    return Ingredient2Recipe[I];
93  }
94
95  /// Check if \I is a memory instruction to be widened for \p Range.Start and
96  /// potentially masked. Such instructions are handled by a recipe that takes
97  /// an additional VPInstruction for the mask.
98  VPWidenMemoryInstructionRecipe *
99  tryToWidenMemory(Instruction *I, VFRange &Range, VPlanPtr &Plan);
100
101  /// Check if an induction recipe should be constructed for \I within the given
102  /// VF \p Range. If so build and return it. If not, return null. \p Range.End
103  /// may be decreased to ensure same decision from \p Range.Start to
104  /// \p Range.End.
105  VPWidenIntOrFpInductionRecipe *tryToOptimizeInduction(Instruction *I,
106                                                        VFRange &Range);
107
108  /// Handle non-loop phi nodes. Currently all such phi nodes are turned into
109  /// a sequence of select instructions as the vectorizer currently performs
110  /// full if-conversion.
111  VPBlendRecipe *tryToBlend(Instruction *I, VPlanPtr &Plan);
112
113  /// Check if \p I can be widened within the given VF \p Range. If \p I can be
114  /// widened for \p Range.Start, check if the last recipe of \p VPBB can be
115  /// extended to include \p I or else build a new VPWidenRecipe for it and
116  /// append it to \p VPBB. Return true if \p I can be widened for Range.Start,
117  /// false otherwise. Range.End may be decreased to ensure same decision from
118  /// \p Range.Start to \p Range.End.
119  bool tryToWiden(Instruction *I, VPBasicBlock *VPBB, VFRange &Range);
120
121  /// Create a replicating region for instruction \p I that requires
122  /// predication. \p PredRecipe is a VPReplicateRecipe holding \p I.
123  VPRegionBlock *createReplicateRegion(Instruction *I, VPRecipeBase *PredRecipe,
124                                       VPlanPtr &Plan);
125
126public:
127  VPRecipeBuilder(Loop *OrigLoop, const TargetLibraryInfo *TLI,
128                  LoopVectorizationLegality *Legal,
129                  LoopVectorizationCostModel &CM, VPBuilder &Builder)
130      : OrigLoop(OrigLoop), TLI(TLI), Legal(Legal), CM(CM), Builder(Builder) {}
131
132  /// Check if a recipe can be create for \p I withing the given VF \p Range.
133  /// If a recipe can be created, it adds it to \p VPBB.
134  bool tryToCreateRecipe(Instruction *Instr, VFRange &Range, VPlanPtr &Plan,
135                         VPBasicBlock *VPBB);
136
137  /// Build a VPReplicationRecipe for \p I and enclose it within a Region if it
138  /// is predicated. \return \p VPBB augmented with this new recipe if \p I is
139  /// not predicated, otherwise \return a new VPBasicBlock that succeeds the new
140  /// Region. Update the packing decision of predicated instructions if they
141  /// feed \p I. Range.End may be decreased to ensure same recipe behavior from
142  /// \p Range.Start to \p Range.End.
143  VPBasicBlock *handleReplication(
144      Instruction *I, VFRange &Range, VPBasicBlock *VPBB,
145      DenseMap<Instruction *, VPReplicateRecipe *> &PredInst2Recipe,
146      VPlanPtr &Plan);
147};
148} // end namespace llvm
149
150#endif // LLVM_TRANSFORMS_VECTORIZE_VPRECIPEBUILDER_H
151