contrib/llvm-project/llvm/lib/Transforms/Vectorize/LoopVectorizationPlanner.h

   1 //===- LoopVectorizationPlanner.h - Planner for LoopVectorization ---------===//
   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 /// \file
  10 /// This file provides a LoopVectorizationPlanner class.
  11 /// InnerLoopVectorizer vectorizes loops which contain only one basic
  12 /// LoopVectorizationPlanner - drives the vectorization process after having
  13 /// passed Legality checks.
  14 /// The planner builds and optimizes the Vectorization Plans which record the
  15 /// decisions how to vectorize the given loop. In particular, represent the
  16 /// control-flow of the vectorized version, the replication of instructions that
  17 /// are to be scalarized, and interleave access groups.
  18 ///
  19 /// Also provides a VPlan-based builder utility analogous to IRBuilder.
  20 /// It provides an instruction-level API for generating VPInstructions while
  21 /// abstracting away the Recipe manipulation details.
  22 //===----------------------------------------------------------------------===//
  23
  24 #ifndef LLVM_TRANSFORMS_VECTORIZE_LOOPVECTORIZATIONPLANNER_H
  25 #define LLVM_TRANSFORMS_VECTORIZE_LOOPVECTORIZATIONPLANNER_H
  26
  27 #include "VPlan.h"
  28 #include "llvm/Analysis/LoopInfo.h"
  29 #include "llvm/Analysis/TargetLibraryInfo.h"
  30 #include "llvm/Analysis/TargetTransformInfo.h"
  31
  32 namespace llvm {
  33
  34 class LoopVectorizationLegality;
  35 class LoopVectorizationCostModel;
  36 class PredicatedScalarEvolution;
  37
  38 /// VPlan-based builder utility analogous to IRBuilder.
  39 class VPBuilder {
  40   VPBasicBlock *BB = nullptr;
  41   VPBasicBlock::iterator InsertPt = VPBasicBlock::iterator();
  42
  43   VPInstruction *createInstruction(unsigned Opcode,
  44                                    ArrayRef<VPValue *> Operands) {
  45     VPInstruction *Instr = new VPInstruction(Opcode, Operands);
  46     if (BB)
  47       BB->insert(Instr, InsertPt);
  48     return Instr;
  49   }
  50
  51   VPInstruction *createInstruction(unsigned Opcode,
  52                                    std::initializer_list<VPValue *> Operands) {
  53     return createInstruction(Opcode, ArrayRef<VPValue *>(Operands));
  54   }
  55
  56 public:
  57   VPBuilder() {}
  58
  59   /// Clear the insertion point: created instructions will not be inserted into
  60   /// a block.
  61   void clearInsertionPoint() {
  62     BB = nullptr;
  63     InsertPt = VPBasicBlock::iterator();
  64   }
  65
  66   VPBasicBlock *getInsertBlock() const { return BB; }
  67   VPBasicBlock::iterator getInsertPoint() const { return InsertPt; }
  68
  69   /// InsertPoint - A saved insertion point.
  70   class VPInsertPoint {
  71     VPBasicBlock *Block = nullptr;
  72     VPBasicBlock::iterator Point;
  73
  74   public:
  75     /// Creates a new insertion point which doesn't point to anything.
  76     VPInsertPoint() = default;
  77
  78     /// Creates a new insertion point at the given location.
  79     VPInsertPoint(VPBasicBlock *InsertBlock, VPBasicBlock::iterator InsertPoint)
  80         : Block(InsertBlock), Point(InsertPoint) {}
  81
  82     /// Returns true if this insert point is set.
  83     bool isSet() const { return Block != nullptr; }
  84
  85     VPBasicBlock *getBlock() const { return Block; }
  86     VPBasicBlock::iterator getPoint() const { return Point; }
  87   };
  88
  89   /// Sets the current insert point to a previously-saved location.
  90   void restoreIP(VPInsertPoint IP) {
  91     if (IP.isSet())
  92       setInsertPoint(IP.getBlock(), IP.getPoint());
  93     else
  94       clearInsertionPoint();
  95   }
  96
  97   /// This specifies that created VPInstructions should be appended to the end
  98   /// of the specified block.
  99   void setInsertPoint(VPBasicBlock *TheBB) {
 100     assert(TheBB && "Attempting to set a null insert point");
 101     BB = TheBB;
 102     InsertPt = BB->end();
 103   }
 104
 105   /// This specifies that created instructions should be inserted at the
 106   /// specified point.
 107   void setInsertPoint(VPBasicBlock *TheBB, VPBasicBlock::iterator IP) {
 108     BB = TheBB;
 109     InsertPt = IP;
 110   }
 111
 112   /// Insert and return the specified instruction.
 113   VPInstruction *insert(VPInstruction *I) const {
 114     BB->insert(I, InsertPt);
 115     return I;
 116   }
 117
 118   /// Create an N-ary operation with \p Opcode, \p Operands and set \p Inst as
 119   /// its underlying Instruction.
 120   VPValue *createNaryOp(unsigned Opcode, ArrayRef<VPValue *> Operands,
 121                         Instruction *Inst = nullptr) {
 122     VPInstruction *NewVPInst = createInstruction(Opcode, Operands);
 123     NewVPInst->setUnderlyingValue(Inst);
 124     return NewVPInst;
 125   }
 126   VPValue *createNaryOp(unsigned Opcode,
 127                         std::initializer_list<VPValue *> Operands,
 128                         Instruction *Inst = nullptr) {
 129     return createNaryOp(Opcode, ArrayRef<VPValue *>(Operands), Inst);
 130   }
 131
 132   VPValue *createNot(VPValue *Operand) {
 133     return createInstruction(VPInstruction::Not, {Operand});
 134   }
 135
 136   VPValue *createAnd(VPValue *LHS, VPValue *RHS) {
 137     return createInstruction(Instruction::BinaryOps::And, {LHS, RHS});
 138   }
 139
 140   VPValue *createOr(VPValue *LHS, VPValue *RHS) {
 141     return createInstruction(Instruction::BinaryOps::Or, {LHS, RHS});
 142   }
 143
 144   //===--------------------------------------------------------------------===//
 145   // RAII helpers.
 146   //===--------------------------------------------------------------------===//
 147
 148   /// RAII object that stores the current insertion point and restores it when
 149   /// the object is destroyed.
 150   class InsertPointGuard {
 151     VPBuilder &Builder;
 152     VPBasicBlock *Block;
 153     VPBasicBlock::iterator Point;
 154
 155   public:
 156     InsertPointGuard(VPBuilder &B)
 157         : Builder(B), Block(B.getInsertBlock()), Point(B.getInsertPoint()) {}
 158
 159     InsertPointGuard(const InsertPointGuard &) = delete;
 160     InsertPointGuard &operator=(const InsertPointGuard &) = delete;
 161
 162     ~InsertPointGuard() { Builder.restoreIP(VPInsertPoint(Block, Point)); }
 163   };
 164 };
 165
 166 /// TODO: The following VectorizationFactor was pulled out of
 167 /// LoopVectorizationCostModel class. LV also deals with
 168 /// VectorizerParams::VectorizationFactor and VectorizationCostTy.
 169 /// We need to streamline them.
 170
 171 /// Information about vectorization costs
 172 struct VectorizationFactor {
 173   // Vector width with best cost
 174   unsigned Width;
 175   // Cost of the loop with that width
 176   unsigned Cost;
 177
 178   // Width 1 means no vectorization, cost 0 means uncomputed cost.
 179   static VectorizationFactor Disabled() { return {1, 0}; }
 180
 181   bool operator==(const VectorizationFactor &rhs) const {
 182     return Width == rhs.Width && Cost == rhs.Cost;
 183   }
 184 };
 185
 186 /// Planner drives the vectorization process after having passed
 187 /// Legality checks.
 188 class LoopVectorizationPlanner {
 189   /// The loop that we evaluate.
 190   Loop *OrigLoop;
 191
 192   /// Loop Info analysis.
 193   LoopInfo *LI;
 194
 195   /// Target Library Info.
 196   const TargetLibraryInfo *TLI;
 197
 198   /// Target Transform Info.
 199   const TargetTransformInfo *TTI;
 200
 201   /// The legality analysis.
 202   LoopVectorizationLegality *Legal;
 203
 204   /// The profitability analysis.
 205   LoopVectorizationCostModel &CM;
 206
 207   /// The interleaved access analysis.
 208   InterleavedAccessInfo &IAI;
 209
 210   PredicatedScalarEvolution &PSE;
 211
 212   SmallVector<VPlanPtr, 4> VPlans;
 213
 214   /// This class is used to enable the VPlan to invoke a method of ILV. This is
 215   /// needed until the method is refactored out of ILV and becomes reusable.
 216   struct VPCallbackILV : public VPCallback {
 217     InnerLoopVectorizer &ILV;
 218
 219     VPCallbackILV(InnerLoopVectorizer &ILV) : ILV(ILV) {}
 220
 221     Value *getOrCreateVectorValues(Value *V, unsigned Part) override;
 222     Value *getOrCreateScalarValue(Value *V,
 223                                   const VPIteration &Instance) override;
 224   };
 225
 226   /// A builder used to construct the current plan.
 227   VPBuilder Builder;
 228
 229   unsigned BestVF = 0;
 230   unsigned BestUF = 0;
 231
 232 public:
 233   LoopVectorizationPlanner(Loop *L, LoopInfo *LI, const TargetLibraryInfo *TLI,
 234                            const TargetTransformInfo *TTI,
 235                            LoopVectorizationLegality *Legal,
 236                            LoopVectorizationCostModel &CM,
 237                            InterleavedAccessInfo &IAI,
 238                            PredicatedScalarEvolution &PSE)
 239       : OrigLoop(L), LI(LI), TLI(TLI), TTI(TTI), Legal(Legal), CM(CM), IAI(IAI),
 240         PSE(PSE) {}
 241
 242   /// Plan how to best vectorize, return the best VF and its cost, or None if
 243   /// vectorization and interleaving should be avoided up front.
 244   Optional<VectorizationFactor> plan(unsigned UserVF, unsigned UserIC);
 245
 246   /// Use the VPlan-native path to plan how to best vectorize, return the best
 247   /// VF and its cost.
 248   VectorizationFactor planInVPlanNativePath(unsigned UserVF);
 249
 250   /// Finalize the best decision and dispose of all other VPlans.
 251   void setBestPlan(unsigned VF, unsigned UF);
 252
 253   /// Generate the IR code for the body of the vectorized loop according to the
 254   /// best selected VPlan.
 255   void executePlan(InnerLoopVectorizer &LB, DominatorTree *DT);
 256
 257   void printPlans(raw_ostream &O) {
 258     for (const auto &Plan : VPlans)
 259       O << *Plan;
 260   }
 261
 262   /// Test a \p Predicate on a \p Range of VF's. Return the value of applying
 263   /// \p Predicate on Range.Start, possibly decreasing Range.End such that the
 264   /// returned value holds for the entire \p Range.
 265   static bool
 266   getDecisionAndClampRange(const std::function<bool(unsigned)> &Predicate,
 267                            VFRange &Range);
 268
 269 protected:
 270   /// Collect the instructions from the original loop that would be trivially
 271   /// dead in the vectorized loop if generated.
 272   void collectTriviallyDeadInstructions(
 273       SmallPtrSetImpl<Instruction *> &DeadInstructions);
 274
 275   /// Build VPlans for power-of-2 VF's between \p MinVF and \p MaxVF inclusive,
 276   /// according to the information gathered by Legal when it checked if it is
 277   /// legal to vectorize the loop.
 278   void buildVPlans(unsigned MinVF, unsigned MaxVF);
 279
 280 private:
 281   /// Build a VPlan according to the information gathered by Legal. \return a
 282   /// VPlan for vectorization factors \p Range.Start and up to \p Range.End
 283   /// exclusive, possibly decreasing \p Range.End.
 284   VPlanPtr buildVPlan(VFRange &Range);
 285
 286   /// Build a VPlan using VPRecipes according to the information gather by
 287   /// Legal. This method is only used for the legacy inner loop vectorizer.
 288   VPlanPtr buildVPlanWithVPRecipes(
 289       VFRange &Range, SmallPtrSetImpl<Value *> &NeedDef,
 290       SmallPtrSetImpl<Instruction *> &DeadInstructions,
 291       const DenseMap<Instruction *, Instruction *> &SinkAfter);
 292
 293   /// Build VPlans for power-of-2 VF's between \p MinVF and \p MaxVF inclusive,
 294   /// according to the information gathered by Legal when it checked if it is
 295   /// legal to vectorize the loop. This method creates VPlans using VPRecipes.
 296   void buildVPlansWithVPRecipes(unsigned MinVF, unsigned MaxVF);
 297 };
 298
 299 } // namespace llvm
 300
 301 #endif // LLVM_TRANSFORMS_VECTORIZE_LOOPVECTORIZATIONPLANNER_H