Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Transforms/Scalar/StraightLineStrengthReduce.cpp
Line
Count
Source (jump to first uncovered line)
1
//===- StraightLineStrengthReduce.cpp - -----------------------------------===//
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 implements straight-line strength reduction (SLSR). Unlike loop
10
// strength reduction, this algorithm is designed to reduce arithmetic
11
// redundancy in straight-line code instead of loops. It has proven to be
12
// effective in simplifying arithmetic statements derived from an unrolled loop.
13
// It can also simplify the logic of SeparateConstOffsetFromGEP.
14
//
15
// There are many optimizations we can perform in the domain of SLSR. This file
16
// for now contains only an initial step. Specifically, we look for strength
17
// reduction candidates in the following forms:
18
//
19
// Form 1: B + i * S
20
// Form 2: (B + i) * S
21
// Form 3: &B[i * S]
22
//
23
// where S is an integer variable, and i is a constant integer. If we found two
24
// candidates S1 and S2 in the same form and S1 dominates S2, we may rewrite S2
25
// in a simpler way with respect to S1. For example,
26
//
27
// S1: X = B + i * S
28
// S2: Y = B + i' * S   => X + (i' - i) * S
29
//
30
// S1: X = (B + i) * S
31
// S2: Y = (B + i') * S => X + (i' - i) * S
32
//
33
// S1: X = &B[i * S]
34
// S2: Y = &B[i' * S]   => &X[(i' - i) * S]
35
//
36
// Note: (i' - i) * S is folded to the extent possible.
37
//
38
// This rewriting is in general a good idea. The code patterns we focus on
39
// usually come from loop unrolling, so (i' - i) * S is likely the same
40
// across iterations and can be reused. When that happens, the optimized form
41
// takes only one add starting from the second iteration.
42
//
43
// When such rewriting is possible, we call S1 a "basis" of S2. When S2 has
44
// multiple bases, we choose to rewrite S2 with respect to its "immediate"
45
// basis, the basis that is the closest ancestor in the dominator tree.
46
//
47
// TODO:
48
//
49
// - Floating point arithmetics when fast math is enabled.
50
//
51
// - SLSR may decrease ILP at the architecture level. Targets that are very
52
//   sensitive to ILP may want to disable it. Having SLSR to consider ILP is
53
//   left as future work.
54
//
55
// - When (i' - i) is constant but i and i' are not, we could still perform
56
//   SLSR.
57
58
#include "llvm/ADT/APInt.h"
59
#include "llvm/ADT/DepthFirstIterator.h"
60
#include "llvm/ADT/SmallVector.h"
61
#include "llvm/Analysis/ScalarEvolution.h"
62
#include "llvm/Analysis/TargetTransformInfo.h"
63
#include "llvm/Transforms/Utils/Local.h"
64
#include "llvm/Analysis/ValueTracking.h"
65
#include "llvm/IR/Constants.h"
66
#include "llvm/IR/DataLayout.h"
67
#include "llvm/IR/DerivedTypes.h"
68
#include "llvm/IR/Dominators.h"
69
#include "llvm/IR/GetElementPtrTypeIterator.h"
70
#include "llvm/IR/IRBuilder.h"
71
#include "llvm/IR/InstrTypes.h"
72
#include "llvm/IR/Instruction.h"
73
#include "llvm/IR/Instructions.h"
74
#include "llvm/IR/Module.h"
75
#include "llvm/IR/Operator.h"
76
#include "llvm/IR/PatternMatch.h"
77
#include "llvm/IR/Type.h"
78
#include "llvm/IR/Value.h"
79
#include "llvm/Pass.h"
80
#include "llvm/Support/Casting.h"
81
#include "llvm/Support/ErrorHandling.h"
82
#include "llvm/Transforms/Scalar.h"
83
#include <cassert>
84
#include <cstdint>
85
#include <limits>
86
#include <list>
87
#include <vector>
88
89
using namespace llvm;
90
using namespace PatternMatch;
91
92
static const unsigned UnknownAddressSpace =
93
    std::numeric_limits<unsigned>::max();
94
95
namespace {
96
97
class StraightLineStrengthReduce : public FunctionPass {
98
public:
99
  // SLSR candidate. Such a candidate must be in one of the forms described in
100
  // the header comments.
101
  struct Candidate {
102
    enum Kind {
103
      Invalid, // reserved for the default constructor
104
      Add,     // B + i * S
105
      Mul,     // (B + i) * S
106
      GEP,     // &B[..][i * S][..]
107
    };
108
109
    Candidate() = default;
110
    Candidate(Kind CT, const SCEV *B, ConstantInt *Idx, Value *S,
111
              Instruction *I)
112
38.6k
        : CandidateKind(CT), Base(B), Index(Idx), Stride(S), Ins(I) {}
113
114
    Kind CandidateKind = Invalid;
115
116
    const SCEV *Base = nullptr;
117
118
    // Note that Index and Stride of a GEP candidate do not necessarily have the
119
    // same integer type. In that case, during rewriting, Stride will be
120
    // sign-extended or truncated to Index's type.
121
    ConstantInt *Index = nullptr;
122
123
    Value *Stride = nullptr;
124
125
    // The instruction this candidate corresponds to. It helps us to rewrite a
126
    // candidate with respect to its immediate basis. Note that one instruction
127
    // can correspond to multiple candidates depending on how you associate the
128
    // expression. For instance,
129
    //
130
    // (a + 1) * (b + 2)
131
    //
132
    // can be treated as
133
    //
134
    // <Base: a, Index: 1, Stride: b + 2>
135
    //
136
    // or
137
    //
138
    // <Base: b, Index: 2, Stride: a + 1>
139
    Instruction *Ins = nullptr;
140
141
    // Points to the immediate basis of this candidate, or nullptr if we cannot
142
    // find any basis for this candidate.
143
    Candidate *Basis = nullptr;
144
  };
145
146
  static char ID;
147
148
2.91k
  StraightLineStrengthReduce() : FunctionPass(ID) {
149
2.91k
    initializeStraightLineStrengthReducePass(*PassRegistry::getPassRegistry());
150
2.91k
  }
151
152
2.88k
  void getAnalysisUsage(AnalysisUsage &AU) const override {
153
2.88k
    AU.addRequired<DominatorTreeWrapperPass>();
154
2.88k
    AU.addRequired<ScalarEvolutionWrapperPass>();
155
2.88k
    AU.addRequired<TargetTransformInfoWrapperPass>();
156
2.88k
    // We do not modify the shape of the CFG.
157
2.88k
    AU.setPreservesCFG();
158
2.88k
  }
159
160
2.88k
  bool doInitialization(Module &M) override {
161
2.88k
    DL = &M.getDataLayout();
162
2.88k
    return false;
163
2.88k
  }
164
165
  bool runOnFunction(Function &F) override;
166
167
private:
168
  // Returns true if Basis is a basis for C, i.e., Basis dominates C and they
169
  // share the same base and stride.
170
  bool isBasisFor(const Candidate &Basis, const Candidate &C);
171
172
  // Returns whether the candidate can be folded into an addressing mode.
173
  bool isFoldable(const Candidate &C, TargetTransformInfo *TTI,
174
                  const DataLayout *DL);
175
176
  // Returns true if C is already in a simplest form and not worth being
177
  // rewritten.
178
  bool isSimplestForm(const Candidate &C);
179
180
  // Checks whether I is in a candidate form. If so, adds all the matching forms
181
  // to Candidates, and tries to find the immediate basis for each of them.
182
  void allocateCandidatesAndFindBasis(Instruction *I);
183
184
  // Allocate candidates and find bases for Add instructions.
185
  void allocateCandidatesAndFindBasisForAdd(Instruction *I);
186
187
  // Given I = LHS + RHS, factors RHS into i * S and makes (LHS + i * S) a
188
  // candidate.
189
  void allocateCandidatesAndFindBasisForAdd(Value *LHS, Value *RHS,
190
                                            Instruction *I);
191
  // Allocate candidates and find bases for Mul instructions.
192
  void allocateCandidatesAndFindBasisForMul(Instruction *I);
193
194
  // Splits LHS into Base + Index and, if succeeds, calls
195
  // allocateCandidatesAndFindBasis.
196
  void allocateCandidatesAndFindBasisForMul(Value *LHS, Value *RHS,
197
                                            Instruction *I);
198
199
  // Allocate candidates and find bases for GetElementPtr instructions.
200
  void allocateCandidatesAndFindBasisForGEP(GetElementPtrInst *GEP);
201
202
  // A helper function that scales Idx with ElementSize before invoking
203
  // allocateCandidatesAndFindBasis.
204
  void allocateCandidatesAndFindBasisForGEP(const SCEV *B, ConstantInt *Idx,
205
                                            Value *S, uint64_t ElementSize,
206
                                            Instruction *I);
207
208
  // Adds the given form <CT, B, Idx, S> to Candidates, and finds its immediate
209
  // basis.
210
  void allocateCandidatesAndFindBasis(Candidate::Kind CT, const SCEV *B,
211
                                      ConstantInt *Idx, Value *S,
212
                                      Instruction *I);
213
214
  // Rewrites candidate C with respect to Basis.
215
  void rewriteCandidateWithBasis(const Candidate &C, const Candidate &Basis);
216
217
  // A helper function that factors ArrayIdx to a product of a stride and a
218
  // constant index, and invokes allocateCandidatesAndFindBasis with the
219
  // factorings.
220
  void factorArrayIndex(Value *ArrayIdx, const SCEV *Base, uint64_t ElementSize,
221
                        GetElementPtrInst *GEP);
222
223
  // Emit code that computes the "bump" from Basis to C. If the candidate is a
224
  // GEP and the bump is not divisible by the element size of the GEP, this
225
  // function sets the BumpWithUglyGEP flag to notify its caller to bump the
226
  // basis using an ugly GEP.
227
  static Value *emitBump(const Candidate &Basis, const Candidate &C,
228
                         IRBuilder<> &Builder, const DataLayout *DL,
229
                         bool &BumpWithUglyGEP);
230
231
  const DataLayout *DL = nullptr;
232
  DominatorTree *DT = nullptr;
233
  ScalarEvolution *SE;
234
  TargetTransformInfo *TTI = nullptr;
235
  std::list<Candidate> Candidates;
236
237
  // Temporarily holds all instructions that are unlinked (but not deleted) by
238
  // rewriteCandidateWithBasis. These instructions will be actually removed
239
  // after all rewriting finishes.
240
  std::vector<Instruction *> UnlinkedInstructions;
241
};
242
243
} // end anonymous namespace
244
245
char StraightLineStrengthReduce::ID = 0;
246
247
36.0k
INITIALIZE_PASS_BEGIN(StraightLineStrengthReduce, "slsr",
248
36.0k
                      "Straight line strength reduction", false, false)
249
36.0k
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
250
36.0k
INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass)
251
36.0k
INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)
252
36.0k
INITIALIZE_PASS_END(StraightLineStrengthReduce, "slsr",
253
                    "Straight line strength reduction", false, false)
254
255
2.90k
FunctionPass *llvm::createStraightLineStrengthReducePass() {
256
2.90k
  return new StraightLineStrengthReduce();
257
2.90k
}
258
259
bool StraightLineStrengthReduce::isBasisFor(const Candidate &Basis,
260
76.8k
                                            const Candidate &C) {
261
76.8k
  return (Basis.Ins != C.Ins && // skip the same instruction
262
76.8k
          // They must have the same type too. Basis.Base == C.Base doesn't
263
76.8k
          // guarantee their types are the same (PR23975).
264
76.8k
          
Basis.Ins->getType() == C.Ins->getType()69.6k
&&
265
76.8k
          // Basis must dominate C in order to rewrite C with respect to Basis.
266
76.8k
          
DT->dominates(Basis.Ins->getParent(), C.Ins->getParent())47.3k
&&
267
76.8k
          // They share the same base, stride, and candidate kind.
268
76.8k
          
Basis.Base == C.Base47.2k
&&
Basis.Stride == C.Stride28.7k
&&
269
76.8k
          
Basis.CandidateKind == C.CandidateKind1.09k
);
270
76.8k
}
271
272
static bool isGEPFoldable(GetElementPtrInst *GEP,
273
24.1k
                          const TargetTransformInfo *TTI) {
274
24.1k
  SmallVector<const Value*, 4> Indices;
275
52.6k
  for (auto I = GEP->idx_begin(); I != GEP->idx_end(); 
++I28.5k
)
276
28.5k
    Indices.push_back(*I);
277
24.1k
  return TTI->getGEPCost(GEP->getSourceElementType(), GEP->getPointerOperand(),
278
24.1k
                         Indices) == TargetTransformInfo::TCC_Free;
279
24.1k
}
280
281
// Returns whether (Base + Index * Stride) can be folded to an addressing mode.
282
static bool isAddFoldable(const SCEV *Base, ConstantInt *Index, Value *Stride,
283
9.60k
                          TargetTransformInfo *TTI) {
284
9.60k
  // Index->getSExtValue() may crash if Index is wider than 64-bit.
285
9.60k
  return Index->getBitWidth() <= 64 &&
286
9.60k
         TTI->isLegalAddressingMode(Base->getType(), nullptr, 0, true,
287
9.58k
                                    Index->getSExtValue(), UnknownAddressSpace);
288
9.60k
}
289
290
bool StraightLineStrengthReduce::isFoldable(const Candidate &C,
291
                                            TargetTransformInfo *TTI,
292
38.6k
                                            const DataLayout *DL) {
293
38.6k
  if (C.CandidateKind == Candidate::Add)
294
9.60k
    return isAddFoldable(C.Base, C.Index, C.Stride, TTI);
295
29.0k
  if (C.CandidateKind == Candidate::GEP)
296
24.1k
    return isGEPFoldable(cast<GetElementPtrInst>(C.Ins), TTI);
297
4.94k
  return false;
298
4.94k
}
299
300
// Returns true if GEP has zero or one non-zero index.
301
339
static bool hasOnlyOneNonZeroIndex(GetElementPtrInst *GEP) {
302
339
  unsigned NumNonZeroIndices = 0;
303
692
  for (auto I = GEP->idx_begin(); I != GEP->idx_end(); 
++I353
) {
304
353
    ConstantInt *ConstIdx = dyn_cast<ConstantInt>(*I);
305
353
    if (ConstIdx == nullptr || 
!ConstIdx->isZero()111
)
306
345
      ++NumNonZeroIndices;
307
353
  }
308
339
  return NumNonZeroIndices <= 1;
309
339
}
310
311
31.3k
bool StraightLineStrengthReduce::isSimplestForm(const Candidate &C) {
312
31.3k
  if (C.CandidateKind == Candidate::Add) {
313
9.07k
    // B + 1 * S or B + (-1) * S
314
9.07k
    return C.Index->isOne() || 
C.Index->isMinusOne()108
;
315
9.07k
  }
316
22.2k
  if (C.CandidateKind == Candidate::Mul) {
317
4.94k
    // (B + 0) * S
318
4.94k
    return C.Index->isZero();
319
4.94k
  }
320
17.3k
  if (C.CandidateKind == Candidate::GEP) {
321
17.3k
    // (char*)B + S or (char*)B - S
322
17.3k
    return ((C.Index->isOne() || 
C.Index->isMinusOne()17.0k
) &&
323
17.3k
            
hasOnlyOneNonZeroIndex(cast<GetElementPtrInst>(C.Ins))339
);
324
17.3k
  }
325
0
  return false;
326
0
}
327
328
// TODO: We currently implement an algorithm whose time complexity is linear in
329
// the number of existing candidates. However, we could do better by using
330
// ScopedHashTable. Specifically, while traversing the dominator tree, we could
331
// maintain all the candidates that dominate the basic block being traversed in
332
// a ScopedHashTable. This hash table is indexed by the base and the stride of
333
// a candidate. Therefore, finding the immediate basis of a candidate boils down
334
// to one hash-table look up.
335
void StraightLineStrengthReduce::allocateCandidatesAndFindBasis(
336
    Candidate::Kind CT, const SCEV *B, ConstantInt *Idx, Value *S,
337
38.6k
    Instruction *I) {
338
38.6k
  Candidate C(CT, B, Idx, S, I);
339
38.6k
  // SLSR can complicate an instruction in two cases:
340
38.6k
  //
341
38.6k
  // 1. If we can fold I into an addressing mode, computing I is likely free or
342
38.6k
  // takes only one instruction.
343
38.6k
  //
344
38.6k
  // 2. I is already in a simplest form. For example, when
345
38.6k
  //      X = B + 8 * S
346
38.6k
  //      Y = B + S,
347
38.6k
  //    rewriting Y to X - 7 * S is probably a bad idea.
348
38.6k
  //
349
38.6k
  // In the above cases, we still add I to the candidate list so that I can be
350
38.6k
  // the basis of other candidates, but we leave I's basis blank so that I
351
38.6k
  // won't be rewritten.
352
38.6k
  if (!isFoldable(C, TTI, DL) && 
!isSimplestForm(C)31.3k
) {
353
17.1k
    // Try to compute the immediate basis of C.
354
17.1k
    unsigned NumIterations = 0;
355
17.1k
    // Limit the scan radius to avoid running in quadratice time.
356
17.1k
    static const unsigned MaxNumIterations = 50;
357
17.1k
    for (auto Basis = Candidates.rbegin();
358
92.9k
         Basis != Candidates.rend() && 
NumIterations < MaxNumIterations77.4k
;
359
76.8k
         
++Basis, ++NumIterations75.7k
) {
360
76.8k
      if (isBasisFor(*Basis, C)) {
361
1.09k
        C.Basis = &(*Basis);
362
1.09k
        break;
363
1.09k
      }
364
76.8k
    }
365
17.1k
  }
366
38.6k
  // Regardless of whether we find a basis for C, we need to push C to the
367
38.6k
  // candidate list so that it can be the basis of other candidates.
368
38.6k
  Candidates.push_back(C);
369
38.6k
}
370
371
void StraightLineStrengthReduce::allocateCandidatesAndFindBasis(
372
188k
    Instruction *I) {
373
188k
  switch (I->getOpcode()) {
374
188k
  case Instruction::Add:
375
5.13k
    allocateCandidatesAndFindBasisForAdd(I);
376
5.13k
    break;
377
188k
  case Instruction::Mul:
378
2.60k
    allocateCandidatesAndFindBasisForMul(I);
379
2.60k
    break;
380
188k
  case Instruction::GetElementPtr:
381
16.6k
    allocateCandidatesAndFindBasisForGEP(cast<GetElementPtrInst>(I));
382
16.6k
    break;
383
188k
  }
384
188k
}
385
386
void StraightLineStrengthReduce::allocateCandidatesAndFindBasisForAdd(
387
5.13k
    Instruction *I) {
388
5.13k
  // Try matching B + i * S.
389
5.13k
  if (!isa<IntegerType>(I->getType()))
390
330
    return;
391
4.80k
392
4.80k
  assert(I->getNumOperands() == 2 && "isn't I an add?");
393
4.80k
  Value *LHS = I->getOperand(0), *RHS = I->getOperand(1);
394
4.80k
  allocateCandidatesAndFindBasisForAdd(LHS, RHS, I);
395
4.80k
  if (LHS != RHS)
396
4.79k
    allocateCandidatesAndFindBasisForAdd(RHS, LHS, I);
397
4.80k
}
398
399
void StraightLineStrengthReduce::allocateCandidatesAndFindBasisForAdd(
400
9.60k
    Value *LHS, Value *RHS, Instruction *I) {
401
9.60k
  Value *S = nullptr;
402
9.60k
  ConstantInt *Idx = nullptr;
403
9.60k
  if (match(RHS, m_Mul(m_Value(S), m_ConstantInt(Idx)))) {
404
8
    // I = LHS + RHS = LHS + Idx * S
405
8
    allocateCandidatesAndFindBasis(Candidate::Add, SE->getSCEV(LHS), Idx, S, I);
406
9.59k
  } else if (match(RHS, m_Shl(m_Value(S), m_ConstantInt(Idx)))) {
407
101
    // I = LHS + RHS = LHS + (S << Idx) = LHS + S * (1 << Idx)
408
101
    APInt One(Idx->getBitWidth(), 1);
409
101
    Idx = ConstantInt::get(Idx->getContext(), One << Idx->getValue());
410
101
    allocateCandidatesAndFindBasis(Candidate::Add, SE->getSCEV(LHS), Idx, S, I);
411
9.49k
  } else {
412
9.49k
    // At least, I = LHS + 1 * RHS
413
9.49k
    ConstantInt *One = ConstantInt::get(cast<IntegerType>(I->getType()), 1);
414
9.49k
    allocateCandidatesAndFindBasis(Candidate::Add, SE->getSCEV(LHS), One, RHS,
415
9.49k
                                   I);
416
9.49k
  }
417
9.60k
}
418
419
// Returns true if A matches B + C where C is constant.
420
4.94k
static bool matchesAdd(Value *A, Value *&B, ConstantInt *&C) {
421
4.94k
  return (match(A, m_Add(m_Value(B), m_ConstantInt(C))) ||
422
4.94k
          
match(A, m_Add(m_ConstantInt(C), m_Value(B)))4.92k
);
423
4.94k
}
424
425
// Returns true if A matches B | C where C is constant.
426
4.92k
static bool matchesOr(Value *A, Value *&B, ConstantInt *&C) {
427
4.92k
  return (match(A, m_Or(m_Value(B), m_ConstantInt(C))) ||
428
4.92k
          
match(A, m_Or(m_ConstantInt(C), m_Value(B)))4.92k
);
429
4.92k
}
430
431
void StraightLineStrengthReduce::allocateCandidatesAndFindBasisForMul(
432
4.94k
    Value *LHS, Value *RHS, Instruction *I) {
433
4.94k
  Value *B = nullptr;
434
4.94k
  ConstantInt *Idx = nullptr;
435
4.94k
  if (matchesAdd(LHS, B, Idx)) {
436
14
    // If LHS is in the form of "Base + Index", then I is in the form of
437
14
    // "(Base + Index) * RHS".
438
14
    allocateCandidatesAndFindBasis(Candidate::Mul, SE->getSCEV(B), Idx, RHS, I);
439
4.92k
  } else if (matchesOr(LHS, B, Idx) && 
haveNoCommonBitsSet(B, Idx, *DL)2
) {
440
1
    // If LHS is in the form of "Base | Index" and Base and Index have no common
441
1
    // bits set, then
442
1
    //   Base | Index = Base + Index
443
1
    // and I is thus in the form of "(Base + Index) * RHS".
444
1
    allocateCandidatesAndFindBasis(Candidate::Mul, SE->getSCEV(B), Idx, RHS, I);
445
4.92k
  } else {
446
4.92k
    // Otherwise, at least try the form (LHS + 0) * RHS.
447
4.92k
    ConstantInt *Zero = ConstantInt::get(cast<IntegerType>(I->getType()), 0);
448
4.92k
    allocateCandidatesAndFindBasis(Candidate::Mul, SE->getSCEV(LHS), Zero, RHS,
449
4.92k
                                   I);
450
4.92k
  }
451
4.94k
}
452
453
void StraightLineStrengthReduce::allocateCandidatesAndFindBasisForMul(
454
2.60k
    Instruction *I) {
455
2.60k
  // Try matching (B + i) * S.
456
2.60k
  // TODO: we could extend SLSR to float and vector types.
457
2.60k
  if (!isa<IntegerType>(I->getType()))
458
132
    return;
459
2.47k
460
2.47k
  assert(I->getNumOperands() == 2 && "isn't I a mul?");
461
2.47k
  Value *LHS = I->getOperand(0), *RHS = I->getOperand(1);
462
2.47k
  allocateCandidatesAndFindBasisForMul(LHS, RHS, I);
463
2.47k
  if (LHS != RHS) {
464
2.46k
    // Symmetrically, try to split RHS to Base + Index.
465
2.46k
    allocateCandidatesAndFindBasisForMul(RHS, LHS, I);
466
2.46k
  }
467
2.47k
}
468
469
void StraightLineStrengthReduce::allocateCandidatesAndFindBasisForGEP(
470
    const SCEV *B, ConstantInt *Idx, Value *S, uint64_t ElementSize,
471
24.1k
    Instruction *I) {
472
24.1k
  // I = B + sext(Idx *nsw S) * ElementSize
473
24.1k
  //   = B + (sext(Idx) * sext(S)) * ElementSize
474
24.1k
  //   = B + (sext(Idx) * ElementSize) * sext(S)
475
24.1k
  // Casting to IntegerType is safe because we skipped vector GEPs.
476
24.1k
  IntegerType *IntPtrTy = cast<IntegerType>(DL->getIntPtrType(I->getType()));
477
24.1k
  ConstantInt *ScaledIdx = ConstantInt::get(
478
24.1k
      IntPtrTy, Idx->getSExtValue() * (int64_t)ElementSize, true);
479
24.1k
  allocateCandidatesAndFindBasis(Candidate::GEP, B, ScaledIdx, S, I);
480
24.1k
}
481
482
void StraightLineStrengthReduce::factorArrayIndex(Value *ArrayIdx,
483
                                                  const SCEV *Base,
484
                                                  uint64_t ElementSize,
485
24.1k
                                                  GetElementPtrInst *GEP) {
486
24.1k
  // At least, ArrayIdx = ArrayIdx *nsw 1.
487
24.1k
  allocateCandidatesAndFindBasisForGEP(
488
24.1k
      Base, ConstantInt::get(cast<IntegerType>(ArrayIdx->getType()), 1),
489
24.1k
      ArrayIdx, ElementSize, GEP);
490
24.1k
  Value *LHS = nullptr;
491
24.1k
  ConstantInt *RHS = nullptr;
492
24.1k
  // One alternative is matching the SCEV of ArrayIdx instead of ArrayIdx
493
24.1k
  // itself. This would allow us to handle the shl case for free. However,
494
24.1k
  // matching SCEVs has two issues:
495
24.1k
  //
496
24.1k
  // 1. this would complicate rewriting because the rewriting procedure
497
24.1k
  // would have to translate SCEVs back to IR instructions. This translation
498
24.1k
  // is difficult when LHS is further evaluated to a composite SCEV.
499
24.1k
  //
500
24.1k
  // 2. ScalarEvolution is designed to be control-flow oblivious. It tends
501
24.1k
  // to strip nsw/nuw flags which are critical for SLSR to trace into
502
24.1k
  // sext'ed multiplication.
503
24.1k
  if (match(ArrayIdx, m_NSWMul(m_Value(LHS), m_ConstantInt(RHS)))) {
504
6
    // SLSR is currently unsafe if i * S may overflow.
505
6
    // GEP = Base + sext(LHS *nsw RHS) * ElementSize
506
6
    allocateCandidatesAndFindBasisForGEP(Base, RHS, LHS, ElementSize, GEP);
507
24.0k
  } else if (match(ArrayIdx, m_NSWShl(m_Value(LHS), m_ConstantInt(RHS)))) {
508
11
    // GEP = Base + sext(LHS <<nsw RHS) * ElementSize
509
11
    //     = Base + sext(LHS *nsw (1 << RHS)) * ElementSize
510
11
    APInt One(RHS->getBitWidth(), 1);
511
11
    ConstantInt *PowerOf2 =
512
11
        ConstantInt::get(RHS->getContext(), One << RHS->getValue());
513
11
    allocateCandidatesAndFindBasisForGEP(Base, PowerOf2, LHS, ElementSize, GEP);
514
11
  }
515
24.1k
}
516
517
void StraightLineStrengthReduce::allocateCandidatesAndFindBasisForGEP(
518
16.6k
    GetElementPtrInst *GEP) {
519
16.6k
  // TODO: handle vector GEPs
520
16.6k
  if (GEP->getType()->isVectorTy())
521
16
    return;
522
16.5k
523
16.5k
  SmallVector<const SCEV *, 4> IndexExprs;
524
35.0k
  for (auto I = GEP->idx_begin(); I != GEP->idx_end(); 
++I18.4k
)
525
18.4k
    IndexExprs.push_back(SE->getSCEV(*I));
526
16.5k
527
16.5k
  gep_type_iterator GTI = gep_type_begin(GEP);
528
35.0k
  for (unsigned I = 1, E = GEP->getNumOperands(); I != E; 
++I, ++GTI18.4k
) {
529
18.4k
    if (GTI.isStruct())
530
188
      continue;
531
18.2k
532
18.2k
    const SCEV *OrigIndexExpr = IndexExprs[I - 1];
533
18.2k
    IndexExprs[I - 1] = SE->getZero(OrigIndexExpr->getType());
534
18.2k
535
18.2k
    // The base of this candidate is GEP's base plus the offsets of all
536
18.2k
    // indices except this current one.
537
18.2k
    const SCEV *BaseExpr = SE->getGEPExpr(cast<GEPOperator>(GEP), IndexExprs);
538
18.2k
    Value *ArrayIdx = GEP->getOperand(I);
539
18.2k
    uint64_t ElementSize = DL->getTypeAllocSize(GTI.getIndexedType());
540
18.2k
    if (ArrayIdx->getType()->getIntegerBitWidth() <=
541
18.2k
        DL->getPointerSizeInBits(GEP->getAddressSpace())) {
542
18.0k
      // Skip factoring if ArrayIdx is wider than the pointer size, because
543
18.0k
      // ArrayIdx is implicitly truncated to the pointer size.
544
18.0k
      factorArrayIndex(ArrayIdx, BaseExpr, ElementSize, GEP);
545
18.0k
    }
546
18.2k
    // When ArrayIdx is the sext of a value, we try to factor that value as
547
18.2k
    // well.  Handling this case is important because array indices are
548
18.2k
    // typically sign-extended to the pointer size.
549
18.2k
    Value *TruncatedArrayIdx = nullptr;
550
18.2k
    if (match(ArrayIdx, m_SExt(m_Value(TruncatedArrayIdx))) &&
551
18.2k
        TruncatedArrayIdx->getType()->getIntegerBitWidth() <=
552
6.00k
            DL->getPointerSizeInBits(GEP->getAddressSpace())) {
553
6.00k
      // Skip factoring if TruncatedArrayIdx is wider than the pointer size,
554
6.00k
      // because TruncatedArrayIdx is implicitly truncated to the pointer size.
555
6.00k
      factorArrayIndex(TruncatedArrayIdx, BaseExpr, ElementSize, GEP);
556
6.00k
    }
557
18.2k
558
18.2k
    IndexExprs[I - 1] = OrigIndexExpr;
559
18.2k
  }
560
16.5k
}
561
562
// A helper function that unifies the bitwidth of A and B.
563
750
static void unifyBitWidth(APInt &A, APInt &B) {
564
750
  if (A.getBitWidth() < B.getBitWidth())
565
0
    A = A.sext(B.getBitWidth());
566
750
  else if (A.getBitWidth() > B.getBitWidth())
567
0
    B = B.sext(A.getBitWidth());
568
750
}
569
570
Value *StraightLineStrengthReduce::emitBump(const Candidate &Basis,
571
                                            const Candidate &C,
572
                                            IRBuilder<> &Builder,
573
                                            const DataLayout *DL,
574
750
                                            bool &BumpWithUglyGEP) {
575
750
  APInt Idx = C.Index->getValue(), BasisIdx = Basis.Index->getValue();
576
750
  unifyBitWidth(Idx, BasisIdx);
577
750
  APInt IndexOffset = Idx - BasisIdx;
578
750
579
750
  BumpWithUglyGEP = false;
580
750
  if (Basis.CandidateKind == Candidate::GEP) {
581
721
    APInt ElementSize(
582
721
        IndexOffset.getBitWidth(),
583
721
        DL->getTypeAllocSize(
584
721
            cast<GetElementPtrInst>(Basis.Ins)->getResultElementType()));
585
721
    APInt Q, R;
586
721
    APInt::sdivrem(IndexOffset, ElementSize, Q, R);
587
721
    if (R == 0)
588
719
      IndexOffset = Q;
589
2
    else
590
2
      BumpWithUglyGEP = true;
591
721
  }
592
750
593
750
  // Compute Bump = C - Basis = (i' - i) * S.
594
750
  // Common case 1: if (i' - i) is 1, Bump = S.
595
750
  if (IndexOffset == 1)
596
31
    return C.Stride;
597
719
  // Common case 2: if (i' - i) is -1, Bump = -S.
598
719
  if (IndexOffset.isAllOnesValue())
599
0
    return Builder.CreateNeg(C.Stride);
600
719
601
719
  // Otherwise, Bump = (i' - i) * sext/trunc(S). Note that (i' - i) and S may
602
719
  // have different bit widths.
603
719
  IntegerType *DeltaType =
604
719
      IntegerType::get(Basis.Ins->getContext(), IndexOffset.getBitWidth());
605
719
  Value *ExtendedStride = Builder.CreateSExtOrTrunc(C.Stride, DeltaType);
606
719
  if (IndexOffset.isPowerOf2()) {
607
5
    // If (i' - i) is a power of 2, Bump = sext/trunc(S) << log(i' - i).
608
5
    ConstantInt *Exponent = ConstantInt::get(DeltaType, IndexOffset.logBase2());
609
5
    return Builder.CreateShl(ExtendedStride, Exponent);
610
5
  }
611
714
  if ((-IndexOffset).isPowerOf2()) {
612
2
    // If (i - i') is a power of 2, Bump = -sext/trunc(S) << log(i' - i).
613
2
    ConstantInt *Exponent =
614
2
        ConstantInt::get(DeltaType, (-IndexOffset).logBase2());
615
2
    return Builder.CreateNeg(Builder.CreateShl(ExtendedStride, Exponent));
616
2
  }
617
712
  Constant *Delta = ConstantInt::get(DeltaType, IndexOffset);
618
712
  return Builder.CreateMul(ExtendedStride, Delta);
619
712
}
620
621
void StraightLineStrengthReduce::rewriteCandidateWithBasis(
622
1.09k
    const Candidate &C, const Candidate &Basis) {
623
1.09k
  assert(C.CandidateKind == Basis.CandidateKind && C.Base == Basis.Base &&
624
1.09k
         C.Stride == Basis.Stride);
625
1.09k
  // We run rewriteCandidateWithBasis on all candidates in a post-order, so the
626
1.09k
  // basis of a candidate cannot be unlinked before the candidate.
627
1.09k
  assert(Basis.Ins->getParent() != nullptr && "the basis is unlinked");
628
1.09k
629
1.09k
  // An instruction can correspond to multiple candidates. Therefore, instead of
630
1.09k
  // simply deleting an instruction when we rewrite it, we mark its parent as
631
1.09k
  // nullptr (i.e. unlink it) so that we can skip the candidates whose
632
1.09k
  // instruction is already rewritten.
633
1.09k
  if (!C.Ins->getParent())
634
345
    return;
635
750
636
750
  IRBuilder<> Builder(C.Ins);
637
750
  bool BumpWithUglyGEP;
638
750
  Value *Bump = emitBump(Basis, C, Builder, DL, BumpWithUglyGEP);
639
750
  Value *Reduced = nullptr; // equivalent to but weaker than C.Ins
640
750
  switch (C.CandidateKind) {
641
750
  case Candidate::Add:
642
29
  case Candidate::Mul: {
643
29
    // C = Basis + Bump
644
29
    Value *NegBump;
645
29
    if (match(Bump, m_Neg(m_Value(NegBump)))) {
646
2
      // If Bump is a neg instruction, emit C = Basis - (-Bump).
647
2
      Reduced = Builder.CreateSub(Basis.Ins, NegBump);
648
2
      // We only use the negative argument of Bump, and Bump itself may be
649
2
      // trivially dead.
650
2
      RecursivelyDeleteTriviallyDeadInstructions(Bump);
651
27
    } else {
652
27
      // It's tempting to preserve nsw on Bump and/or Reduced. However, it's
653
27
      // usually unsound, e.g.,
654
27
      //
655
27
      // X = (-2 +nsw 1) *nsw INT_MAX
656
27
      // Y = (-2 +nsw 3) *nsw INT_MAX
657
27
      //   =>
658
27
      // Y = X + 2 * INT_MAX
659
27
      //
660
27
      // Neither + and * in the resultant expression are nsw.
661
27
      Reduced = Builder.CreateAdd(Basis.Ins, Bump);
662
27
    }
663
29
    break;
664
29
  }
665
721
  case Candidate::GEP:
666
721
    {
667
721
      Type *IntPtrTy = DL->getIntPtrType(C.Ins->getType());
668
721
      bool InBounds = cast<GetElementPtrInst>(C.Ins)->isInBounds();
669
721
      if (BumpWithUglyGEP) {
670
2
        // C = (char *)Basis + Bump
671
2
        unsigned AS = Basis.Ins->getType()->getPointerAddressSpace();
672
2
        Type *CharTy = Type::getInt8PtrTy(Basis.Ins->getContext(), AS);
673
2
        Reduced = Builder.CreateBitCast(Basis.Ins, CharTy);
674
2
        if (InBounds)
675
2
          Reduced =
676
2
              Builder.CreateInBoundsGEP(Builder.getInt8Ty(), Reduced, Bump);
677
0
        else
678
0
          Reduced = Builder.CreateGEP(Builder.getInt8Ty(), Reduced, Bump);
679
2
        Reduced = Builder.CreateBitCast(Reduced, C.Ins->getType());
680
719
      } else {
681
719
        // C = gep Basis, Bump
682
719
        // Canonicalize bump to pointer size.
683
719
        Bump = Builder.CreateSExtOrTrunc(Bump, IntPtrTy);
684
719
        if (InBounds)
685
20
          Reduced = Builder.CreateInBoundsGEP(
686
20
              cast<GetElementPtrInst>(Basis.Ins)->getResultElementType(),
687
20
              Basis.Ins, Bump);
688
699
        else
689
699
          Reduced = Builder.CreateGEP(
690
699
              cast<GetElementPtrInst>(Basis.Ins)->getResultElementType(),
691
699
              Basis.Ins, Bump);
692
719
      }
693
721
      break;
694
29
    }
695
29
  default:
696
0
    llvm_unreachable("C.CandidateKind is invalid");
697
750
  };
698
750
  Reduced->takeName(C.Ins);
699
750
  C.Ins->replaceAllUsesWith(Reduced);
700
750
  // Unlink C.Ins so that we can skip other candidates also corresponding to
701
750
  // C.Ins. The actual deletion is postponed to the end of runOnFunction.
702
750
  C.Ins->removeFromParent();
703
750
  UnlinkedInstructions.push_back(C.Ins);
704
750
}
705
706
28.2k
bool StraightLineStrengthReduce::runOnFunction(Function &F) {
707
28.2k
  if (skipFunction(F))
708
8
    return false;
709
28.2k
710
28.2k
  TTI = &getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
711
28.2k
  DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
712
28.2k
  SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
713
28.2k
  // Traverse the dominator tree in the depth-first order. This order makes sure
714
28.2k
  // all bases of a candidate are in Candidates when we process it.
715
28.2k
  for (const auto Node : depth_first(DT))
716
31.2k
    for (auto &I : *(Node->getBlock()))
717
188k
      allocateCandidatesAndFindBasis(&I);
718
28.2k
719
28.2k
  // Rewrite candidates in the reverse depth-first order. This order makes sure
720
28.2k
  // a candidate being rewritten is not a basis for any other candidate.
721
66.9k
  while (!Candidates.empty()) {
722
38.6k
    const Candidate &C = Candidates.back();
723
38.6k
    if (C.Basis != nullptr) {
724
1.09k
      rewriteCandidateWithBasis(C, *C.Basis);
725
1.09k
    }
726
38.6k
    Candidates.pop_back();
727
38.6k
  }
728
28.2k
729
28.2k
  // Delete all unlink instructions.
730
28.2k
  for (auto *UnlinkedInst : UnlinkedInstructions) {
731
2.41k
    for (unsigned I = 0, E = UnlinkedInst->getNumOperands(); I != E; 
++I1.66k
) {
732
1.66k
      Value *Op = UnlinkedInst->getOperand(I);
733
1.66k
      UnlinkedInst->setOperand(I, nullptr);
734
1.66k
      RecursivelyDeleteTriviallyDeadInstructions(Op);
735
1.66k
    }
736
750
    UnlinkedInst->deleteValue();
737
750
  }
738
28.2k
  bool Ret = !UnlinkedInstructions.empty();
739
28.2k
  UnlinkedInstructions.clear();
740
28.2k
  return Ret;
741
28.2k
}