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