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

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