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