Coverage Report

Created: 2019-02-15 18:59

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/include/llvm/Analysis/ScalarEvolutionExpander.h
Line
Count
Source (jump to first uncovered line)
1
//===---- llvm/Analysis/ScalarEvolutionExpander.h - SCEV Exprs --*- 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
// This file defines the classes used to generate code from scalar expressions.
10
//
11
//===----------------------------------------------------------------------===//
12
13
#ifndef LLVM_ANALYSIS_SCALAREVOLUTIONEXPANDER_H
14
#define LLVM_ANALYSIS_SCALAREVOLUTIONEXPANDER_H
15
16
#include "llvm/ADT/DenseMap.h"
17
#include "llvm/ADT/DenseSet.h"
18
#include "llvm/ADT/Optional.h"
19
#include "llvm/Analysis/ScalarEvolutionExpressions.h"
20
#include "llvm/Analysis/ScalarEvolutionNormalization.h"
21
#include "llvm/Analysis/TargetFolder.h"
22
#include "llvm/IR/IRBuilder.h"
23
#include "llvm/IR/ValueHandle.h"
24
25
namespace llvm {
26
  class TargetTransformInfo;
27
28
  /// Return true if the given expression is safe to expand in the sense that
29
  /// all materialized values are safe to speculate anywhere their operands are
30
  /// defined.
31
  bool isSafeToExpand(const SCEV *S, ScalarEvolution &SE);
32
33
  /// Return true if the given expression is safe to expand in the sense that
34
  /// all materialized values are defined and safe to speculate at the specified
35
  /// location and their operands are defined at this location.
36
  bool isSafeToExpandAt(const SCEV *S, const Instruction *InsertionPoint,
37
                        ScalarEvolution &SE);
38
39
  /// This class uses information about analyze scalars to rewrite expressions
40
  /// in canonical form.
41
  ///
42
  /// Clients should create an instance of this class when rewriting is needed,
43
  /// and destroy it when finished to allow the release of the associated
44
  /// memory.
45
  class SCEVExpander : public SCEVVisitor<SCEVExpander, Value*> {
46
    ScalarEvolution &SE;
47
    const DataLayout &DL;
48
49
    // New instructions receive a name to identify them with the current pass.
50
    const char* IVName;
51
52
    // InsertedExpressions caches Values for reuse, so must track RAUW.
53
    DenseMap<std::pair<const SCEV *, Instruction *>, TrackingVH<Value>>
54
        InsertedExpressions;
55
56
    // InsertedValues only flags inserted instructions so needs no RAUW.
57
    DenseSet<AssertingVH<Value>> InsertedValues;
58
    DenseSet<AssertingVH<Value>> InsertedPostIncValues;
59
60
    /// A memoization of the "relevant" loop for a given SCEV.
61
    DenseMap<const SCEV *, const Loop *> RelevantLoops;
62
63
    /// Addrecs referring to any of the given loops are expanded in post-inc
64
    /// mode. For example, expanding {1,+,1}<L> in post-inc mode returns the add
65
    /// instruction that adds one to the phi for {0,+,1}<L>, as opposed to a new
66
    /// phi starting at 1. This is only supported in non-canonical mode.
67
    PostIncLoopSet PostIncLoops;
68
69
    /// When this is non-null, addrecs expanded in the loop it indicates should
70
    /// be inserted with increments at IVIncInsertPos.
71
    const Loop *IVIncInsertLoop;
72
73
    /// When expanding addrecs in the IVIncInsertLoop loop, insert the IV
74
    /// increment at this position.
75
    Instruction *IVIncInsertPos;
76
77
    /// Phis that complete an IV chain. Reuse
78
    DenseSet<AssertingVH<PHINode>> ChainedPhis;
79
80
    /// When true, expressions are expanded in "canonical" form. In particular,
81
    /// addrecs are expanded as arithmetic based on a canonical induction
82
    /// variable. When false, expression are expanded in a more literal form.
83
    bool CanonicalMode;
84
85
    /// When invoked from LSR, the expander is in "strength reduction" mode. The
86
    /// only difference is that phi's are only reused if they are already in
87
    /// "expanded" form.
88
    bool LSRMode;
89
90
    typedef IRBuilder<TargetFolder> BuilderType;
91
    BuilderType Builder;
92
93
    // RAII object that stores the current insertion point and restores it when
94
    // the object is destroyed. This includes the debug location.  Duplicated
95
    // from InsertPointGuard to add SetInsertPoint() which is used to updated
96
    // InsertPointGuards stack when insert points are moved during SCEV
97
    // expansion.
98
    class SCEVInsertPointGuard {
99
      IRBuilderBase &Builder;
100
      AssertingVH<BasicBlock> Block;
101
      BasicBlock::iterator Point;
102
      DebugLoc DbgLoc;
103
      SCEVExpander *SE;
104
105
      SCEVInsertPointGuard(const SCEVInsertPointGuard &) = delete;
106
      SCEVInsertPointGuard &operator=(const SCEVInsertPointGuard &) = delete;
107
108
    public:
109
      SCEVInsertPointGuard(IRBuilderBase &B, SCEVExpander *SE)
110
          : Builder(B), Block(B.GetInsertBlock()), Point(B.GetInsertPoint()),
111
3.26M
            DbgLoc(B.getCurrentDebugLocation()), SE(SE) {
112
3.26M
        SE->InsertPointGuards.push_back(this);
113
3.26M
      }
114
115
3.26M
      ~SCEVInsertPointGuard() {
116
3.26M
        // These guards should always created/destroyed in FIFO order since they
117
3.26M
        // are used to guard lexically scoped blocks of code in
118
3.26M
        // ScalarEvolutionExpander.
119
3.26M
        assert(SE->InsertPointGuards.back() == this);
120
3.26M
        SE->InsertPointGuards.pop_back();
121
3.26M
        Builder.restoreIP(IRBuilderBase::InsertPoint(Block, Point));
122
3.26M
        Builder.SetCurrentDebugLocation(DbgLoc);
123
3.26M
      }
124
125
25
      BasicBlock::iterator GetInsertPoint() const { return Point; }
126
1
      void SetInsertPoint(BasicBlock::iterator I) { Point = I; }
127
    };
128
129
    /// Stack of pointers to saved insert points, used to keep insert points
130
    /// consistent when instructions are moved.
131
    SmallVector<SCEVInsertPointGuard *, 8> InsertPointGuards;
132
133
#ifndef NDEBUG
134
    const char *DebugType;
135
#endif
136
137
    friend struct SCEVVisitor<SCEVExpander, Value*>;
138
139
  public:
140
    /// Construct a SCEVExpander in "canonical" mode.
141
    explicit SCEVExpander(ScalarEvolution &se, const DataLayout &DL,
142
                          const char *name)
143
        : SE(se), DL(DL), IVName(name), IVIncInsertLoop(nullptr),
144
          IVIncInsertPos(nullptr), CanonicalMode(true), LSRMode(false),
145
628k
          Builder(se.getContext(), TargetFolder(DL)) {
146
628k
#ifndef NDEBUG
147
628k
      DebugType = "";
148
628k
#endif
149
628k
    }
150
151
628k
    ~SCEVExpander() {
152
628k
      // Make sure the insert point guard stack is consistent.
153
628k
      assert(InsertPointGuards.empty());
154
628k
    }
155
156
#ifndef NDEBUG
157
    void setDebugType(const char* s) { DebugType = s; }
158
#endif
159
160
    /// Erase the contents of the InsertedExpressions map so that users trying
161
    /// to expand the same expression into multiple BasicBlocks or different
162
    /// places within the same BasicBlock can do so.
163
332k
    void clear() {
164
332k
      InsertedExpressions.clear();
165
332k
      InsertedValues.clear();
166
332k
      InsertedPostIncValues.clear();
167
332k
      ChainedPhis.clear();
168
332k
    }
169
170
    /// Return true for expressions that may incur non-trivial cost to evaluate
171
    /// at runtime.
172
    ///
173
    /// At is an optional parameter which specifies point in code where user is
174
    /// going to expand this expression. Sometimes this knowledge can lead to a
175
    /// more accurate cost estimation.
176
    bool isHighCostExpansion(const SCEV *Expr, Loop *L,
177
90.4k
                             const Instruction *At = nullptr) {
178
90.4k
      SmallPtrSet<const SCEV *, 8> Processed;
179
90.4k
      return isHighCostExpansionHelper(Expr, L, At, Processed);
180
90.4k
    }
181
182
    /// This method returns the canonical induction variable of the specified
183
    /// type for the specified loop (inserting one if there is none).  A
184
    /// canonical induction variable starts at zero and steps by one on each
185
    /// iteration.
186
    PHINode *getOrInsertCanonicalInductionVariable(const Loop *L, Type *Ty);
187
188
    /// Return the induction variable increment's IV operand.
189
    Instruction *getIVIncOperand(Instruction *IncV, Instruction *InsertPos,
190
                                 bool allowScale);
191
192
    /// Utility for hoisting an IV increment.
193
    bool hoistIVInc(Instruction *IncV, Instruction *InsertPos);
194
195
    /// replace congruent phis with their most canonical representative. Return
196
    /// the number of phis eliminated.
197
    unsigned replaceCongruentIVs(Loop *L, const DominatorTree *DT,
198
                                 SmallVectorImpl<WeakTrackingVH> &DeadInsts,
199
                                 const TargetTransformInfo *TTI = nullptr);
200
201
    /// Insert code to directly compute the specified SCEV expression into the
202
    /// program.  The inserted code is inserted into the specified block.
203
    Value *expandCodeFor(const SCEV *SH, Type *Ty, Instruction *I);
204
205
    /// Insert code to directly compute the specified SCEV expression into the
206
    /// program.  The inserted code is inserted into the SCEVExpander's current
207
    /// insertion point. If a type is specified, the result will be expanded to
208
    /// have that type, with a cast if necessary.
209
    Value *expandCodeFor(const SCEV *SH, Type *Ty = nullptr);
210
211
212
    /// Generates a code sequence that evaluates this predicate.  The inserted
213
    /// instructions will be at position \p Loc.  The result will be of type i1
214
    /// and will have a value of 0 when the predicate is false and 1 otherwise.
215
    Value *expandCodeForPredicate(const SCEVPredicate *Pred, Instruction *Loc);
216
217
    /// A specialized variant of expandCodeForPredicate, handling the case when
218
    /// we are expanding code for a SCEVEqualPredicate.
219
    Value *expandEqualPredicate(const SCEVEqualPredicate *Pred,
220
                                Instruction *Loc);
221
222
    /// Generates code that evaluates if the \p AR expression will overflow.
223
    Value *generateOverflowCheck(const SCEVAddRecExpr *AR, Instruction *Loc,
224
                                 bool Signed);
225
226
    /// A specialized variant of expandCodeForPredicate, handling the case when
227
    /// we are expanding code for a SCEVWrapPredicate.
228
    Value *expandWrapPredicate(const SCEVWrapPredicate *P, Instruction *Loc);
229
230
    /// A specialized variant of expandCodeForPredicate, handling the case when
231
    /// we are expanding code for a SCEVUnionPredicate.
232
    Value *expandUnionPredicate(const SCEVUnionPredicate *Pred,
233
                                Instruction *Loc);
234
235
    /// Set the current IV increment loop and position.
236
102k
    void setIVIncInsertPos(const Loop *L, Instruction *Pos) {
237
102k
      assert(!CanonicalMode &&
238
102k
             "IV increment positions are not supported in CanonicalMode");
239
102k
      IVIncInsertLoop = L;
240
102k
      IVIncInsertPos = Pos;
241
102k
    }
242
243
    /// Enable post-inc expansion for addrecs referring to the given
244
    /// loops. Post-inc expansion is only supported in non-canonical mode.
245
499k
    void setPostInc(const PostIncLoopSet &L) {
246
499k
      assert(!CanonicalMode &&
247
499k
             "Post-inc expansion is not supported in CanonicalMode");
248
499k
      PostIncLoops = L;
249
499k
    }
250
251
    /// Disable all post-inc expansion.
252
505k
    void clearPostInc() {
253
505k
      PostIncLoops.clear();
254
505k
255
505k
      // When we change the post-inc loop set, cached expansions may no
256
505k
      // longer be valid.
257
505k
      InsertedPostIncValues.clear();
258
505k
    }
259
260
    /// Disable the behavior of expanding expressions in canonical form rather
261
    /// than in a more literal form. Non-canonical mode is useful for late
262
    /// optimization passes.
263
323k
    void disableCanonicalMode() { CanonicalMode = false; }
264
265
102k
    void enableLSRMode() { LSRMode = true; }
266
267
    /// Set the current insertion point. This is useful if multiple calls to
268
    /// expandCodeFor() are going to be made with the same insert point and the
269
    /// insert point may be moved during one of the expansions (e.g. if the
270
    /// insert point is not a block terminator).
271
923k
    void setInsertPoint(Instruction *IP) {
272
923k
      assert(IP);
273
923k
      Builder.SetInsertPoint(IP);
274
923k
    }
275
276
    /// Clear the current insertion point. This is useful if the instruction
277
    /// that had been serving as the insertion point may have been deleted.
278
87.5k
    void clearInsertPoint() {
279
87.5k
      Builder.ClearInsertionPoint();
280
87.5k
    }
281
282
    /// Return true if the specified instruction was inserted by the code
283
    /// rewriter.  If so, the client should not modify the instruction.
284
1.30M
    bool isInsertedInstruction(Instruction *I) const {
285
1.30M
      return InsertedValues.count(I) || 
InsertedPostIncValues.count(I)1.03M
;
286
1.30M
    }
287
288
1.25k
    void setChainedPhi(PHINode *PN) { ChainedPhis.insert(PN); }
289
290
    /// Try to find existing LLVM IR value for S available at the point At.
291
    Value *getExactExistingExpansion(const SCEV *S, const Instruction *At,
292
                                     Loop *L);
293
294
    /// Try to find the ValueOffsetPair for S. The function is mainly used to
295
    /// check whether S can be expanded cheaply.  If this returns a non-None
296
    /// value, we know we can codegen the `ValueOffsetPair` into a suitable
297
    /// expansion identical with S so that S can be expanded cheaply.
298
    ///
299
    /// L is a hint which tells in which loop to look for the suitable value.
300
    /// On success return value which is equivalent to the expanded S at point
301
    /// At. Return nullptr if value was not found.
302
    ///
303
    /// Note that this function does not perform an exhaustive search. I.e if it
304
    /// didn't find any value it does not mean that there is no such value.
305
    ///
306
    Optional<ScalarEvolution::ValueOffsetPair>
307
    getRelatedExistingExpansion(const SCEV *S, const Instruction *At, Loop *L);
308
309
  private:
310
0
    LLVMContext &getContext() const { return SE.getContext(); }
311
312
    /// Recursive helper function for isHighCostExpansion.
313
    bool isHighCostExpansionHelper(const SCEV *S, Loop *L,
314
                                   const Instruction *At,
315
                                   SmallPtrSetImpl<const SCEV *> &Processed);
316
317
    /// Insert the specified binary operator, doing a small amount of work to
318
    /// avoid inserting an obviously redundant operation.
319
    Value *InsertBinop(Instruction::BinaryOps Opcode, Value *LHS, Value *RHS);
320
321
    /// Arrange for there to be a cast of V to Ty at IP, reusing an existing
322
    /// cast if a suitable one exists, moving an existing cast if a suitable one
323
    /// exists but isn't in the right place, or creating a new one.
324
    Value *ReuseOrCreateCast(Value *V, Type *Ty,
325
                             Instruction::CastOps Op,
326
                             BasicBlock::iterator IP);
327
328
    /// Insert a cast of V to the specified type, which must be possible with a
329
    /// noop cast, doing what we can to share the casts.
330
    Value *InsertNoopCastOfTo(Value *V, Type *Ty);
331
332
    /// Expand a SCEVAddExpr with a pointer type into a GEP instead of using
333
    /// ptrtoint+arithmetic+inttoptr.
334
    Value *expandAddToGEP(const SCEV *const *op_begin,
335
                          const SCEV *const *op_end,
336
                          PointerType *PTy, Type *Ty, Value *V);
337
    Value *expandAddToGEP(const SCEV *Op, PointerType *PTy, Type *Ty, Value *V);
338
339
    /// Find a previous Value in ExprValueMap for expand.
340
    ScalarEvolution::ValueOffsetPair
341
    FindValueInExprValueMap(const SCEV *S, const Instruction *InsertPt);
342
343
    Value *expand(const SCEV *S);
344
345
    /// Determine the most "relevant" loop for the given SCEV.
346
    const Loop *getRelevantLoop(const SCEV *);
347
348
499k
    Value *visitConstant(const SCEVConstant *S) {
349
499k
      return S->getValue();
350
499k
    }
351
352
    Value *visitTruncateExpr(const SCEVTruncateExpr *S);
353
354
    Value *visitZeroExtendExpr(const SCEVZeroExtendExpr *S);
355
356
    Value *visitSignExtendExpr(const SCEVSignExtendExpr *S);
357
358
    Value *visitAddExpr(const SCEVAddExpr *S);
359
360
    Value *visitMulExpr(const SCEVMulExpr *S);
361
362
    Value *visitUDivExpr(const SCEVUDivExpr *S);
363
364
    Value *visitAddRecExpr(const SCEVAddRecExpr *S);
365
366
    Value *visitSMaxExpr(const SCEVSMaxExpr *S);
367
368
    Value *visitUMaxExpr(const SCEVUMaxExpr *S);
369
370
1.21M
    Value *visitUnknown(const SCEVUnknown *S) {
371
1.21M
      return S->getValue();
372
1.21M
    }
373
374
    void rememberInstruction(Value *I);
375
376
    bool isNormalAddRecExprPHI(PHINode *PN, Instruction *IncV, const Loop *L);
377
378
    bool isExpandedAddRecExprPHI(PHINode *PN, Instruction *IncV, const Loop *L);
379
380
    Value *expandAddRecExprLiterally(const SCEVAddRecExpr *);
381
    PHINode *getAddRecExprPHILiterally(const SCEVAddRecExpr *Normalized,
382
                                       const Loop *L,
383
                                       Type *ExpandTy,
384
                                       Type *IntTy,
385
                                       Type *&TruncTy,
386
                                       bool &InvertStep);
387
    Value *expandIVInc(PHINode *PN, Value *StepV, const Loop *L,
388
                       Type *ExpandTy, Type *IntTy, bool useSubtract);
389
390
    void hoistBeforePos(DominatorTree *DT, Instruction *InstToHoist,
391
                        Instruction *Pos, PHINode *LoopPhi);
392
393
    void fixupInsertPoints(Instruction *I);
394
  };
395
}
396
397
#endif