Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Transforms/Vectorize/LoopVectorizationPlanner.h
Line
Count
Source (jump to first uncovered line)
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
3.90k
                                   ArrayRef<VPValue *> Operands) {
42
3.90k
    VPInstruction *Instr = new VPInstruction(Opcode, Operands);
43
3.90k
    if (BB)
44
3.90k
      BB->insert(Instr, InsertPt);
45
3.90k
    return Instr;
46
3.90k
  }
47
48
  VPInstruction *createInstruction(unsigned Opcode,
49
3.45k
                                   std::initializer_list<VPValue *> Operands) {
50
3.45k
    return createInstruction(Opcode, ArrayRef<VPValue *>(Operands));
51
3.45k
  }
52
53
public:
54
19.9k
  VPBuilder() {}
55
56
  /// Clear the insertion point: created instructions will not be inserted into
57
  /// a block.
58
0
  void clearInsertionPoint() {
59
0
    BB = nullptr;
60
0
    InsertPt = VPBasicBlock::iterator();
61
0
  }
62
63
0
  VPBasicBlock *getInsertBlock() const { return BB; }
64
0
  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
0
        : Block(InsertBlock), Point(InsertPoint) {}
78
79
    /// Returns true if this insert point is set.
80
0
    bool isSet() const { return Block != nullptr; }
81
82
0
    VPBasicBlock *getBlock() const { return Block; }
83
0
    VPBasicBlock::iterator getPoint() const { return Point; }
84
  };
85
86
  /// Sets the current insert point to a previously-saved location.
87
0
  void restoreIP(VPInsertPoint IP) {
88
0
    if (IP.isSet())
89
0
      setInsertPoint(IP.getBlock(), IP.getPoint());
90
0
    else
91
0
      clearInsertionPoint();
92
0
  }
93
94
  /// This specifies that created VPInstructions should be appended to the end
95
  /// of the specified block.
96
42.6k
  void setInsertPoint(VPBasicBlock *TheBB) {
97
42.6k
    assert(TheBB && "Attempting to set a null insert point");
98
42.6k
    BB = TheBB;
99
42.6k
    InsertPt = BB->end();
100
42.6k
  }
101
102
  /// This specifies that created instructions should be inserted at the
103
  /// specified point.
104
6
  void setInsertPoint(VPBasicBlock *TheBB, VPBasicBlock::iterator IP) {
105
6
    BB = TheBB;
106
6
    InsertPt = IP;
107
6
  }
108
109
  /// Insert and return the specified instruction.
110
0
  VPInstruction *insert(VPInstruction *I) const {
111
0
    BB->insert(I, InsertPt);
112
0
    return I;
113
0
  }
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
451
                        Instruction *Inst = nullptr) {
119
451
    VPInstruction *NewVPInst = createInstruction(Opcode, Operands);
120
451
    NewVPInst->setUnderlyingValue(Inst);
121
451
    return NewVPInst;
122
451
  }
123
  VPValue *createNaryOp(unsigned Opcode,
124
                        std::initializer_list<VPValue *> Operands,
125
71
                        Instruction *Inst = nullptr) {
126
71
    return createNaryOp(Opcode, ArrayRef<VPValue *>(Operands), Inst);
127
71
  }
128
129
1.51k
  VPValue *createNot(VPValue *Operand) {
130
1.51k
    return createInstruction(VPInstruction::Not, {Operand});
131
1.51k
  }
132
133
1.54k
  VPValue *createAnd(VPValue *LHS, VPValue *RHS) {
134
1.54k
    return createInstruction(Instruction::BinaryOps::And, {LHS, RHS});
135
1.54k
  }
136
137
393
  VPValue *createOr(VPValue *LHS, VPValue *RHS) {
138
393
    return createInstruction(Instruction::BinaryOps::Or, {LHS, RHS});
139
393
  }
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
0
        : Builder(B), Block(B.getInsertBlock()), Point(B.getInsertPoint()) {}
155
156
    InsertPointGuard(const InsertPointGuard &) = delete;
157
    InsertPointGuard &operator=(const InsertPointGuard &) = delete;
158
159
0
    ~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
19.9k
  static VectorizationFactor Disabled() { return {1, 0}; }
177
178
7
  bool operator==(const VectorizationFactor &rhs) const {
179
7
    return Width == rhs.Width && 
Cost == rhs.Cost0
;
180
7
  }
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
17.0k
    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
19.9k
      : 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(bool OptForSize, 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(bool OptForSize, 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
0
  void printPlans(raw_ostream &O) {
245
0
    for (const auto &Plan : VPlans)
246
0
      O << *Plan;
247
0
  }
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