Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/CodeGen/InterleavedLoadCombinePass.cpp
Line
Count
Source (jump to first uncovered line)
1
//===- InterleavedLoadCombine.cpp - Combine Interleaved Loads ---*- 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
// \file
10
//
11
// This file defines the interleaved-load-combine pass. The pass searches for
12
// ShuffleVectorInstruction that execute interleaving loads. If a matching
13
// pattern is found, it adds a combined load and further instructions in a
14
// pattern that is detectable by InterleavedAccesPass. The old instructions are
15
// left dead to be removed later. The pass is specifically designed to be
16
// executed just before InterleavedAccesPass to find any left-over instances
17
// that are not detected within former passes.
18
//
19
//===----------------------------------------------------------------------===//
20
21
#include "llvm/ADT/Statistic.h"
22
#include "llvm/Analysis/MemoryLocation.h"
23
#include "llvm/Analysis/MemorySSA.h"
24
#include "llvm/Analysis/MemorySSAUpdater.h"
25
#include "llvm/Analysis/OptimizationRemarkEmitter.h"
26
#include "llvm/Analysis/TargetTransformInfo.h"
27
#include "llvm/CodeGen/Passes.h"
28
#include "llvm/CodeGen/TargetLowering.h"
29
#include "llvm/CodeGen/TargetPassConfig.h"
30
#include "llvm/CodeGen/TargetSubtargetInfo.h"
31
#include "llvm/IR/DataLayout.h"
32
#include "llvm/IR/Dominators.h"
33
#include "llvm/IR/Function.h"
34
#include "llvm/IR/Instructions.h"
35
#include "llvm/IR/LegacyPassManager.h"
36
#include "llvm/IR/Module.h"
37
#include "llvm/Pass.h"
38
#include "llvm/Support/Debug.h"
39
#include "llvm/Support/ErrorHandling.h"
40
#include "llvm/Support/raw_ostream.h"
41
#include "llvm/Target/TargetMachine.h"
42
43
#include <algorithm>
44
#include <cassert>
45
#include <list>
46
47
using namespace llvm;
48
49
0
#define DEBUG_TYPE "interleaved-load-combine"
50
51
namespace {
52
53
/// Statistic counter
54
STATISTIC(NumInterleavedLoadCombine, "Number of combined loads");
55
56
/// Option to disable the pass
57
static cl::opt<bool> DisableInterleavedLoadCombine(
58
    "disable-" DEBUG_TYPE, cl::init(false), cl::Hidden,
59
    cl::desc("Disable combining of interleaved loads"));
60
61
struct VectorInfo;
62
63
struct InterleavedLoadCombineImpl {
64
public:
65
  InterleavedLoadCombineImpl(Function &F, DominatorTree &DT, MemorySSA &MSSA,
66
                             TargetMachine &TM)
67
      : F(F), DT(DT), MSSA(MSSA),
68
        TLI(*TM.getSubtargetImpl(F)->getTargetLowering()),
69
257k
        TTI(TM.getTargetTransformInfo(F)) {}
70
71
  /// Scan the function for interleaved load candidates and execute the
72
  /// replacement if applicable.
73
  bool run();
74
75
private:
76
  /// Function this pass is working on
77
  Function &F;
78
79
  /// Dominator Tree Analysis
80
  DominatorTree &DT;
81
82
  /// Memory Alias Analyses
83
  MemorySSA &MSSA;
84
85
  /// Target Lowering Information
86
  const TargetLowering &TLI;
87
88
  /// Target Transform Information
89
  const TargetTransformInfo TTI;
90
91
  /// Find the instruction in sets LIs that dominates all others, return nullptr
92
  /// if there is none.
93
  LoadInst *findFirstLoad(const std::set<LoadInst *> &LIs);
94
95
  /// Replace interleaved load candidates. It does additional
96
  /// analyses if this makes sense. Returns true on success and false
97
  /// of nothing has been changed.
98
  bool combine(std::list<VectorInfo> &InterleavedLoad,
99
               OptimizationRemarkEmitter &ORE);
100
101
  /// Given a set of VectorInfo containing candidates for a given interleave
102
  /// factor, find a set that represents a 'factor' interleaved load.
103
  bool findPattern(std::list<VectorInfo> &Candidates,
104
                   std::list<VectorInfo> &InterleavedLoad, unsigned Factor,
105
                   const DataLayout &DL);
106
}; // InterleavedLoadCombine
107
108
/// First Order Polynomial on an n-Bit Integer Value
109
///
110
/// Polynomial(Value) = Value * B + A + E*2^(n-e)
111
///
112
/// A and B are the coefficients. E*2^(n-e) is an error within 'e' most
113
/// significant bits. It is introduced if an exact computation cannot be proven
114
/// (e.q. division by 2).
115
///
116
/// As part of this optimization multiple loads will be combined. It necessary
117
/// to prove that loads are within some relative offset to each other. This
118
/// class is used to prove relative offsets of values loaded from memory.
119
///
120
/// Representing an integer in this form is sound since addition in two's
121
/// complement is associative (trivial) and multiplication distributes over the
122
/// addition (see Proof(1) in Polynomial::mul). Further, both operations
123
/// commute.
124
//
125
// Example:
126
// declare @fn(i64 %IDX, <4 x float>* %PTR) {
127
//   %Pa1 = add i64 %IDX, 2
128
//   %Pa2 = lshr i64 %Pa1, 1
129
//   %Pa3 = getelementptr inbounds <4 x float>, <4 x float>* %PTR, i64 %Pa2
130
//   %Va = load <4 x float>, <4 x float>* %Pa3
131
//
132
//   %Pb1 = add i64 %IDX, 4
133
//   %Pb2 = lshr i64 %Pb1, 1
134
//   %Pb3 = getelementptr inbounds <4 x float>, <4 x float>* %PTR, i64 %Pb2
135
//   %Vb = load <4 x float>, <4 x float>* %Pb3
136
// ... }
137
//
138
// The goal is to prove that two loads load consecutive addresses.
139
//
140
// In this case the polynomials are constructed by the following
141
// steps.
142
//
143
// The number tag #e specifies the error bits.
144
//
145
// Pa_0 = %IDX              #0
146
// Pa_1 = %IDX + 2          #0 | add 2
147
// Pa_2 = %IDX/2 + 1        #1 | lshr 1
148
// Pa_3 = %IDX/2 + 1        #1 | GEP, step signext to i64
149
// Pa_4 = (%IDX/2)*16 + 16  #0 | GEP, multiply index by sizeof(4) for floats
150
// Pa_5 = (%IDX/2)*16 + 16  #0 | GEP, add offset of leading components
151
//
152
// Pb_0 = %IDX              #0
153
// Pb_1 = %IDX + 4          #0 | add 2
154
// Pb_2 = %IDX/2 + 2        #1 | lshr 1
155
// Pb_3 = %IDX/2 + 2        #1 | GEP, step signext to i64
156
// Pb_4 = (%IDX/2)*16 + 32  #0 | GEP, multiply index by sizeof(4) for floats
157
// Pb_5 = (%IDX/2)*16 + 16  #0 | GEP, add offset of leading components
158
//
159
// Pb_5 - Pa_5 = 16         #0 | subtract to get the offset
160
//
161
// Remark: %PTR is not maintained within this class. So in this instance the
162
// offset of 16 can only be assumed if the pointers are equal.
163
//
164
class Polynomial {
165
  /// Operations on B
166
  enum BOps {
167
    LShr,
168
    Mul,
169
    SExt,
170
    Trunc,
171
  };
172
173
  /// Number of Error Bits e
174
  unsigned ErrorMSBs;
175
176
  /// Value
177
  Value *V;
178
179
  /// Coefficient B
180
  SmallVector<std::pair<BOps, APInt>, 4> B;
181
182
  /// Coefficient A
183
  APInt A;
184
185
public:
186
5.49k
  Polynomial(Value *V) : ErrorMSBs((unsigned)-1), V(V), B(), A() {
187
5.49k
    IntegerType *Ty = dyn_cast<IntegerType>(V->getType());
188
5.49k
    if (Ty) {
189
5.49k
      ErrorMSBs = 0;
190
5.49k
      this->V = V;
191
5.49k
      A = APInt(Ty->getBitWidth(), 0);
192
5.49k
    }
193
5.49k
  }
194
195
  Polynomial(const APInt &A, unsigned ErrorMSBs = 0)
196
16.6k
      : ErrorMSBs(ErrorMSBs), V(NULL), B(), A(A) {}
197
198
  Polynomial(unsigned BitWidth, uint64_t A, unsigned ErrorMSBs = 0)
199
3.30k
      : ErrorMSBs(ErrorMSBs), V(NULL), B(), A(BitWidth, A) {}
200
201
2.79M
  Polynomial() : ErrorMSBs((unsigned)-1), V(NULL), B(), A() {}
202
203
  /// Increment and clamp the number of undefined bits.
204
488
  void incErrorMSBs(unsigned amt) {
205
488
    if (ErrorMSBs == (unsigned)-1)
206
0
      return;
207
488
208
488
    ErrorMSBs += amt;
209
488
    if (ErrorMSBs > A.getBitWidth())
210
24
      ErrorMSBs = A.getBitWidth();
211
488
  }
212
213
  /// Decrement and clamp the number of undefined bits.
214
3.98k
  void decErrorMSBs(unsigned amt) {
215
3.98k
    if (ErrorMSBs == (unsigned)-1)
216
0
      return;
217
3.98k
218
3.98k
    if (ErrorMSBs > amt)
219
24
      ErrorMSBs -= amt;
220
3.96k
    else
221
3.96k
      ErrorMSBs = 0;
222
3.98k
  }
223
224
  /// Apply an add on the polynomial
225
9.29k
  Polynomial &add(const APInt &C) {
226
9.29k
    // Note: Addition is associative in two's complement even when in case of
227
9.29k
    // signed overflow.
228
9.29k
    //
229
9.29k
    // Error bits can only propagate into higher significant bits. As these are
230
9.29k
    // already regarded as undefined, there is no change.
231
9.29k
    //
232
9.29k
    // Theorem: Adding a constant to a polynomial does not change the error
233
9.29k
    // term.
234
9.29k
    //
235
9.29k
    // Proof:
236
9.29k
    //
237
9.29k
    //   Since the addition is associative and commutes:
238
9.29k
    //
239
9.29k
    //   (B + A + E*2^(n-e)) + C = B + (A + C) + E*2^(n-e)
240
9.29k
    // [qed]
241
9.29k
242
9.29k
    if (C.getBitWidth() != A.getBitWidth()) {
243
0
      ErrorMSBs = (unsigned)-1;
244
0
      return *this;
245
0
    }
246
9.29k
247
9.29k
    A += C;
248
9.29k
    return *this;
249
9.29k
  }
250
251
  /// Apply a multiplication onto the polynomial.
252
5.49k
  Polynomial &mul(const APInt &C) {
253
5.49k
    // Note: Multiplication distributes over the addition
254
5.49k
    //
255
5.49k
    // Theorem: Multiplication distributes over the addition
256
5.49k
    //
257
5.49k
    // Proof(1):
258
5.49k
    //
259
5.49k
    //   (B+A)*C =-
260
5.49k
    //        = (B + A) + (B + A) + .. {C Times}
261
5.49k
    //         addition is associative and commutes, hence
262
5.49k
    //        = B + B + .. {C Times} .. + A + A + .. {C times}
263
5.49k
    //        = B*C + A*C
264
5.49k
    //   (see (function add) for signed values and overflows)
265
5.49k
    // [qed]
266
5.49k
    //
267
5.49k
    // Theorem: If C has c trailing zeros, errors bits in A or B are shifted out
268
5.49k
    // to the left.
269
5.49k
    //
270
5.49k
    // Proof(2):
271
5.49k
    //
272
5.49k
    //   Let B' and A' be the n-Bit inputs with some unknown errors EA,
273
5.49k
    //   EB at e leading bits. B' and A' can be written down as:
274
5.49k
    //
275
5.49k
    //     B' = B + 2^(n-e)*EB
276
5.49k
    //     A' = A + 2^(n-e)*EA
277
5.49k
    //
278
5.49k
    //   Let C' be an input with c trailing zero bits. C' can be written as
279
5.49k
    //
280
5.49k
    //     C' = C*2^c
281
5.49k
    //
282
5.49k
    //   Therefore we can compute the result by using distributivity and
283
5.49k
    //   commutativity.
284
5.49k
    //
285
5.49k
    //     (B'*C' + A'*C') = [B + 2^(n-e)*EB] * C' + [A + 2^(n-e)*EA] * C' =
286
5.49k
    //                     = [B + 2^(n-e)*EB + A + 2^(n-e)*EA] * C' =
287
5.49k
    //                     = (B'+A') * C' =
288
5.49k
    //                     = [B + 2^(n-e)*EB + A + 2^(n-e)*EA] * C' =
289
5.49k
    //                     = [B + A + 2^(n-e)*EB + 2^(n-e)*EA] * C' =
290
5.49k
    //                     = (B + A) * C' + [2^(n-e)*EB + 2^(n-e)*EA)] * C' =
291
5.49k
    //                     = (B + A) * C' + [2^(n-e)*EB + 2^(n-e)*EA)] * C*2^c =
292
5.49k
    //                     = (B + A) * C' + C*(EB + EA)*2^(n-e)*2^c =
293
5.49k
    //
294
5.49k
    //   Let EC be the final error with EC = C*(EB + EA)
295
5.49k
    //
296
5.49k
    //                     = (B + A)*C' + EC*2^(n-e)*2^c =
297
5.49k
    //                     = (B + A)*C' + EC*2^(n-(e-c))
298
5.49k
    //
299
5.49k
    //   Since EC is multiplied by 2^(n-(e-c)) the resulting error contains c
300
5.49k
    //   less error bits than the input. c bits are shifted out to the left.
301
5.49k
    // [qed]
302
5.49k
303
5.49k
    if (C.getBitWidth() != A.getBitWidth()) {
304
0
      ErrorMSBs = (unsigned)-1;
305
0
      return *this;
306
0
    }
307
5.49k
308
5.49k
    // Multiplying by one is a no-op.
309
5.49k
    if (C.isOneValue()) {
310
1.50k
      return *this;
311
1.50k
    }
312
3.98k
313
3.98k
    // Multiplying by zero removes the coefficient B and defines all bits.
314
3.98k
    if (C.isNullValue()) {
315
0
      ErrorMSBs = 0;
316
0
      deleteB();
317
0
    }
318
3.98k
319
3.98k
    // See Proof(2): Trailing zero bits indicate a left shift. This removes
320
3.98k
    // leading bits from the result even if they are undefined.
321
3.98k
    decErrorMSBs(C.countTrailingZeros());
322
3.98k
323
3.98k
    A *= C;
324
3.98k
    pushBOperation(Mul, C);
325
3.98k
    return *this;
326
3.98k
  }
327
328
  /// Apply a logical shift right on the polynomial
329
464
  Polynomial &lshr(const APInt &C) {
330
464
    // Theorem(1): (B + A + E*2^(n-e)) >> 1 => (B >> 1) + (A >> 1) + E'*2^(n-e')
331
464
    //          where
332
464
    //             e' = e + 1,
333
464
    //             E is a e-bit number,
334
464
    //             E' is a e'-bit number,
335
464
    //   holds under the following precondition:
336
464
    //          pre(1): A % 2 = 0
337
464
    //          pre(2): e < n, (see Theorem(2) for the trivial case with e=n)
338
464
    //   where >> expresses a logical shift to the right, with adding zeros.
339
464
    //
340
464
    //  We need to show that for every, E there is a E'
341
464
    //
342
464
    //  B = b_h * 2^(n-1) + b_m * 2 + b_l
343
464
    //  A = a_h * 2^(n-1) + a_m * 2         (pre(1))
344
464
    //
345
464
    //  where a_h, b_h, b_l are single bits, and a_m, b_m are (n-2) bit numbers
346
464
    //
347
464
    //  Let X = (B + A + E*2^(n-e)) >> 1
348
464
    //  Let Y = (B >> 1) + (A >> 1) + E*2^(n-e) >> 1
349
464
    //
350
464
    //    X = [B + A + E*2^(n-e)] >> 1 =
351
464
    //      = [  b_h * 2^(n-1) + b_m * 2 + b_l +
352
464
    //         + a_h * 2^(n-1) + a_m * 2 +
353
464
    //         + E * 2^(n-e) ] >> 1 =
354
464
    //
355
464
    //    The sum is built by putting the overflow of [a_m + b+n] into the term
356
464
    //    2^(n-1). As there are no more bits beyond 2^(n-1) the overflow within
357
464
    //    this bit is discarded. This is expressed by % 2.
358
464
    //
359
464
    //    The bit in position 0 cannot overflow into the term (b_m + a_m).
360
464
    //
361
464
    //      = [  ([b_h + a_h + (b_m + a_m) >> (n-2)] % 2) * 2^(n-1) +
362
464
    //         + ((b_m + a_m) % 2^(n-2)) * 2 +
363
464
    //         + b_l + E * 2^(n-e) ] >> 1 =
364
464
    //
365
464
    //    The shift is computed by dividing the terms by 2 and by cutting off
366
464
    //    b_l.
367
464
    //
368
464
    //      =    ([b_h + a_h + (b_m + a_m) >> (n-2)] % 2) * 2^(n-2) +
369
464
    //         + ((b_m + a_m) % 2^(n-2)) +
370
464
    //         + E * 2^(n-(e+1)) =
371
464
    //
372
464
    //    by the definition in the Theorem e+1 = e'
373
464
    //
374
464
    //      =    ([b_h + a_h + (b_m + a_m) >> (n-2)] % 2) * 2^(n-2) +
375
464
    //         + ((b_m + a_m) % 2^(n-2)) +
376
464
    //         + E * 2^(n-e') =
377
464
    //
378
464
    //    Compute Y by applying distributivity first
379
464
    //
380
464
    //    Y =  (B >> 1) + (A >> 1) + E*2^(n-e') =
381
464
    //      =    (b_h * 2^(n-1) + b_m * 2 + b_l) >> 1 +
382
464
    //         + (a_h * 2^(n-1) + a_m * 2) >> 1 +
383
464
    //         + E * 2^(n-e) >> 1 =
384
464
    //
385
464
    //    Again, the shift is computed by dividing the terms by 2 and by cutting
386
464
    //    off b_l.
387
464
    //
388
464
    //      =     b_h * 2^(n-2) + b_m +
389
464
    //         +  a_h * 2^(n-2) + a_m +
390
464
    //         +  E * 2^(n-(e+1)) =
391
464
    //
392
464
    //    Again, the sum is built by putting the overflow of [a_m + b+n] into
393
464
    //    the term 2^(n-1). But this time there is room for a second bit in the
394
464
    //    term 2^(n-2) we add this bit to a new term and denote it o_h in a
395
464
    //    second step.
396
464
    //
397
464
    //      =    ([b_h + a_h + (b_m + a_m) >> (n-2)] >> 1) * 2^(n-1) +
398
464
    //         + ([b_h + a_h + (b_m + a_m) >> (n-2)] % 2) * 2^(n-2) +
399
464
    //         + ((b_m + a_m) % 2^(n-2)) +
400
464
    //         + E * 2^(n-(e+1)) =
401
464
    //
402
464
    //    Let o_h = [b_h + a_h + (b_m + a_m) >> (n-2)] >> 1
403
464
    //    Further replace e+1 by e'.
404
464
    //
405
464
    //      =    o_h * 2^(n-1) +
406
464
    //         + ([b_h + a_h + (b_m + a_m) >> (n-2)] % 2) * 2^(n-2) +
407
464
    //         + ((b_m + a_m) % 2^(n-2)) +
408
464
    //         + E * 2^(n-e') =
409
464
    //
410
464
    //    Move o_h into the error term and construct E'. To ensure that there is
411
464
    //    no 2^x with negative x, this step requires pre(2) (e < n).
412
464
    //
413
464
    //      =    ([b_h + a_h + (b_m + a_m) >> (n-2)] % 2) * 2^(n-2) +
414
464
    //         + ((b_m + a_m) % 2^(n-2)) +
415
464
    //         + o_h * 2^(e'-1) * 2^(n-e') +               | pre(2), move 2^(e'-1)
416
464
    //                                                     | out of the old exponent
417
464
    //         + E * 2^(n-e') =
418
464
    //      =    ([b_h + a_h + (b_m + a_m) >> (n-2)] % 2) * 2^(n-2) +
419
464
    //         + ((b_m + a_m) % 2^(n-2)) +
420
464
    //         + [o_h * 2^(e'-1) + E] * 2^(n-e') +         | move 2^(e'-1) out of
421
464
    //                                                     | the old exponent
422
464
    //
423
464
    //    Let E' = o_h * 2^(e'-1) + E
424
464
    //
425
464
    //      =    ([b_h + a_h + (b_m + a_m) >> (n-2)] % 2) * 2^(n-2) +
426
464
    //         + ((b_m + a_m) % 2^(n-2)) +
427
464
    //         + E' * 2^(n-e')
428
464
    //
429
464
    //    Because X and Y are distinct only in there error terms and E' can be
430
464
    //    constructed as shown the theorem holds.
431
464
    // [qed]
432
464
    //
433
464
    // For completeness in case of the case e=n it is also required to show that
434
464
    // distributivity can be applied.
435
464
    //
436
464
    // In this case Theorem(1) transforms to (the pre-condition on A can also be
437
464
    // dropped)
438
464
    //
439
464
    // Theorem(2): (B + A + E) >> 1 => (B >> 1) + (A >> 1) + E'
440
464
    //          where
441
464
    //             A, B, E, E' are two's complement numbers with the same bit
442
464
    //             width
443
464
    //
444
464
    //   Let A + B + E = X
445
464
    //   Let (B >> 1) + (A >> 1) = Y
446
464
    //
447
464
    //   Therefore we need to show that for every X and Y there is an E' which
448
464
    //   makes the equation
449
464
    //
450
464
    //     X = Y + E'
451
464
    //
452
464
    //   hold. This is trivially the case for E' = X - Y.
453
464
    //
454
464
    // [qed]
455
464
    //
456
464
    // Remark: Distributing lshr with and arbitrary number n can be expressed as
457
464
    //   ((((B + A) lshr 1) lshr 1) ... ) {n times}.
458
464
    // This construction induces n additional error bits at the left.
459
464
460
464
    if (C.getBitWidth() != A.getBitWidth()) {
461
0
      ErrorMSBs = (unsigned)-1;
462
0
      return *this;
463
0
    }
464
464
465
464
    if (C.isNullValue())
466
0
      return *this;
467
464
468
464
    // Test if the result will be zero
469
464
    unsigned shiftAmt = C.getZExtValue();
470
464
    if (shiftAmt >= C.getBitWidth())
471
0
      return mul(APInt(C.getBitWidth(), 0));
472
464
473
464
    // The proof that shiftAmt LSBs are zero for at least one summand is only
474
464
    // possible for the constant number.
475
464
    //
476
464
    // If this can be proven add shiftAmt to the error counter
477
464
    // `ErrorMSBs`. Otherwise set all bits as undefined.
478
464
    if (A.countTrailingZeros() < shiftAmt)
479
0
      ErrorMSBs = A.getBitWidth();
480
464
    else
481
464
      incErrorMSBs(shiftAmt);
482
464
483
464
    // Apply the operation.
484
464
    pushBOperation(LShr, C);
485
464
    A = A.lshr(shiftAmt);
486
464
487
464
    return *this;
488
464
  }
489
490
  /// Apply a sign-extend or truncate operation on the polynomial.
491
5.49k
  Polynomial &sextOrTrunc(unsigned n) {
492
5.49k
    if (n < A.getBitWidth()) {
493
0
      // Truncate: Clearly undefined Bits on the MSB side are removed
494
0
      // if there are any.
495
0
      decErrorMSBs(A.getBitWidth() - n);
496
0
      A = A.trunc(n);
497
0
      pushBOperation(Trunc, APInt(sizeof(n) * 8, n));
498
0
    }
499
5.49k
    if (n > A.getBitWidth()) {
500
24
      // Extend: Clearly extending first and adding later is different
501
24
      // to adding first and extending later in all extended bits.
502
24
      incErrorMSBs(n - A.getBitWidth());
503
24
      A = A.sext(n);
504
24
      pushBOperation(SExt, APInt(sizeof(n) * 8, n));
505
24
    }
506
5.49k
507
5.49k
    return *this;
508
5.49k
  }
509
510
  /// Test if there is a coefficient B.
511
33.0k
  bool isFirstOrder() const { return V != nullptr; }
512
513
  /// Test coefficient B of two Polynomials are equal.
514
11.7k
  bool isCompatibleTo(const Polynomial &o) const {
515
11.7k
    // The polynomial use different bit width.
516
11.7k
    if (A.getBitWidth() != o.A.getBitWidth())
517
102
      return false;
518
11.6k
519
11.6k
    // If neither Polynomial has the Coefficient B.
520
11.6k
    if (!isFirstOrder() && 
!o.isFirstOrder()7.70k
)
521
7.70k
      return true;
522
3.94k
523
3.94k
    // The index variable is different.
524
3.94k
    if (V != o.V)
525
0
      return false;
526
3.94k
527
3.94k
    // Check the operations.
528
3.94k
    if (B.size() != o.B.size())
529
0
      return false;
530
3.94k
531
3.94k
    auto ob = o.B.begin();
532
3.94k
    for (auto &b : B) {
533
2.89k
      if (b != *ob)
534
0
        return false;
535
2.89k
      ob++;
536
2.89k
    }
537
3.94k
538
3.94k
    return true;
539
3.94k
  }
540
541
  /// Subtract two polynomials, return an undefined polynomial if
542
  /// subtraction is not possible.
543
11.7k
  Polynomial operator-(const Polynomial &o) const {
544
11.7k
    // Return an undefined polynomial if incompatible.
545
11.7k
    if (!isCompatibleTo(o))
546
102
      return Polynomial();
547
11.6k
548
11.6k
    // If the polynomials are compatible (meaning they have the same
549
11.6k
    // coefficient on B), B is eliminated. Thus a polynomial solely
550
11.6k
    // containing A is returned
551
11.6k
    return Polynomial(A - o.A, std::max(ErrorMSBs, o.ErrorMSBs));
552
11.6k
  }
553
554
  /// Subtract a constant from a polynomial,
555
0
  Polynomial operator-(uint64_t C) const {
556
0
    Polynomial Result(*this);
557
0
    Result.A -= C;
558
0
    return Result;
559
0
  }
560
561
  /// Add a constant to a polynomial,
562
122k
  Polynomial operator+(uint64_t C) const {
563
122k
    Polynomial Result(*this);
564
122k
    Result.A += C;
565
122k
    return Result;
566
122k
  }
567
568
  /// Returns true if it can be proven that two Polynomials are equal.
569
11.7k
  bool isProvenEqualTo(const Polynomial &o) {
570
11.7k
    // Subtract both polynomials and test if it is fully defined and zero.
571
11.7k
    Polynomial r = *this - o;
572
11.7k
    return (r.ErrorMSBs == 0) && 
(!r.isFirstOrder())9.22k
&&
(r.A.isNullValue())9.22k
;
573
11.7k
  }
574
575
  /// Print the polynomial into a stream.
576
0
  void print(raw_ostream &OS) const {
577
0
    OS << "[{#ErrBits:" << ErrorMSBs << "} ";
578
0
579
0
    if (V) {
580
0
      for (auto b : B)
581
0
        OS << "(";
582
0
      OS << "(" << *V << ") ";
583
0
584
0
      for (auto b : B) {
585
0
        switch (b.first) {
586
0
        case LShr:
587
0
          OS << "LShr ";
588
0
          break;
589
0
        case Mul:
590
0
          OS << "Mul ";
591
0
          break;
592
0
        case SExt:
593
0
          OS << "SExt ";
594
0
          break;
595
0
        case Trunc:
596
0
          OS << "Trunc ";
597
0
          break;
598
0
        }
599
0
600
0
        OS << b.second << ") ";
601
0
      }
602
0
    }
603
0
604
0
    OS << "+ " << A << "]";
605
0
  }
606
607
private:
608
0
  void deleteB() {
609
0
    V = nullptr;
610
0
    B.clear();
611
0
  }
612
613
4.47k
  void pushBOperation(const BOps Op, const APInt &C) {
614
4.47k
    if (isFirstOrder()) {
615
4.47k
      B.push_back(std::make_pair(Op, C));
616
4.47k
      return;
617
4.47k
    }
618
4.47k
  }
619
};
620
621
#ifndef NDEBUG
622
static raw_ostream &operator<<(raw_ostream &OS, const Polynomial &S) {
623
  S.print(OS);
624
  return OS;
625
}
626
#endif
627
628
/// VectorInfo stores abstract the following information for each vector
629
/// element:
630
///
631
/// 1) The the memory address loaded into the element as Polynomial
632
/// 2) a set of load instruction necessary to construct the vector,
633
/// 3) a set of all other instructions that are necessary to create the vector and
634
/// 4) a pointer value that can be used as relative base for all elements.
635
struct VectorInfo {
636
private:
637
0
  VectorInfo(const VectorInfo &c) : VTy(c.VTy) {
638
0
    llvm_unreachable(
639
0
        "Copying VectorInfo is neither implemented nor necessary,");
640
0
  }
641
642
public:
643
  /// Information of a Vector Element
644
  struct ElementInfo {
645
    /// Offset Polynomial.
646
    Polynomial Ofs;
647
648
    /// The Load Instruction used to Load the entry. LI is null if the pointer
649
    /// of the load instruction does not point on to the entry
650
    LoadInst *LI;
651
652
    ElementInfo(Polynomial Offset = Polynomial(), LoadInst *LI = nullptr)
653
2.89M
        : Ofs(Offset), LI(LI) {}
654
  };
655
656
  /// Basic-block the load instructions are within
657
  BasicBlock *BB;
658
659
  /// Pointer value of all participation load instructions
660
  Value *PV;
661
662
  /// Participating load instructions
663
  std::set<LoadInst *> LIs;
664
665
  /// Participating instructions
666
  std::set<Instruction *> Is;
667
668
  /// Final shuffle-vector instruction
669
  ShuffleVectorInst *SVI;
670
671
  /// Information of the offset for each vector element
672
  ElementInfo *EI;
673
674
  /// Vector Type
675
  VectorType *const VTy;
676
677
  VectorInfo(VectorType *VTy)
678
287k
      : BB(nullptr), PV(nullptr), LIs(), Is(), SVI(nullptr), VTy(VTy) {
679
287k
    EI = new ElementInfo[VTy->getNumElements()];
680
287k
  }
681
682
287k
  virtual ~VectorInfo() { delete[] EI; }
683
684
133k
  unsigned getDimension() const { return VTy->getNumElements(); }
685
686
  /// Test if the VectorInfo can be part of an interleaved load with the
687
  /// specified factor.
688
  ///
689
  /// \param Factor of the interleave
690
  /// \param DL Targets Datalayout
691
  ///
692
  /// \returns true if this is possible and false if not
693
8.45k
  bool isInterleaved(unsigned Factor, const DataLayout &DL) const {
694
8.45k
    unsigned Size = DL.getTypeAllocSize(VTy->getElementType());
695
9.35k
    for (unsigned i = 1; i < getDimension(); 
i++908
) {
696
9.08k
      if (!EI[i].Ofs.isProvenEqualTo(EI[0].Ofs + i * Factor * Size)) {
697
8.17k
        return false;
698
8.17k
      }
699
9.08k
    }
700
8.45k
    
return true277
;
701
8.45k
  }
702
703
  /// Recursively computes the vector information stored in V.
704
  ///
705
  /// This function delegates the work to specialized implementations
706
  ///
707
  /// \param V Value to operate on
708
  /// \param Result Result of the computation
709
  ///
710
  /// \returns false if no sensible information can be gathered.
711
193k
  static bool compute(Value *V, VectorInfo &Result, const DataLayout &DL) {
712
193k
    ShuffleVectorInst *SVI = dyn_cast<ShuffleVectorInst>(V);
713
193k
    if (SVI)
714
3.48k
      return computeFromSVI(SVI, Result, DL);
715
190k
    LoadInst *LI = dyn_cast<LoadInst>(V);
716
190k
    if (LI)
717
13.8k
      return computeFromLI(LI, Result, DL);
718
176k
    BitCastInst *BCI = dyn_cast<BitCastInst>(V);
719
176k
    if (BCI)
720
906
      return computeFromBCI(BCI, Result, DL);
721
175k
    return false;
722
175k
  }
723
724
  /// BitCastInst specialization to compute the vector information.
725
  ///
726
  /// \param BCI BitCastInst to operate on
727
  /// \param Result Result of the computation
728
  ///
729
  /// \returns false if no sensible information can be gathered.
730
  static bool computeFromBCI(BitCastInst *BCI, VectorInfo &Result,
731
906
                             const DataLayout &DL) {
732
906
    Instruction *Op = dyn_cast<Instruction>(BCI->getOperand(0));
733
906
734
906
    if (!Op)
735
381
      return false;
736
525
737
525
    VectorType *VTy = dyn_cast<VectorType>(Op->getType());
738
525
    if (!VTy)
739
171
      return false;
740
354
741
354
    // We can only cast from large to smaller vectors
742
354
    if (Result.VTy->getNumElements() % VTy->getNumElements())
743
321
      return false;
744
33
745
33
    unsigned Factor = Result.VTy->getNumElements() / VTy->getNumElements();
746
33
    unsigned NewSize = DL.getTypeAllocSize(Result.VTy->getElementType());
747
33
    unsigned OldSize = DL.getTypeAllocSize(VTy->getElementType());
748
33
749
33
    if (NewSize * Factor != OldSize)
750
0
      return false;
751
33
752
33
    VectorInfo Old(VTy);
753
33
    if (!compute(Op, Old, DL))
754
24
      return false;
755
9
756
27
    
for (unsigned i = 0; 9
i < Result.VTy->getNumElements();
i += Factor18
) {
757
36
      for (unsigned j = 0; j < Factor; 
j++18
) {
758
18
        Result.EI[i + j] =
759
18
            ElementInfo(Old.EI[i / Factor].Ofs + j * NewSize,
760
18
                        j == 0 ? Old.EI[i / Factor].LI : 
nullptr0
);
761
18
      }
762
18
    }
763
9
764
9
    Result.BB = Old.BB;
765
9
    Result.PV = Old.PV;
766
9
    Result.LIs.insert(Old.LIs.begin(), Old.LIs.end());
767
9
    Result.Is.insert(Old.Is.begin(), Old.Is.end());
768
9
    Result.Is.insert(BCI);
769
9
    Result.SVI = nullptr;
770
9
771
9
    return true;
772
9
  }
773
774
  /// ShuffleVectorInst specialization to compute vector information.
775
  ///
776
  /// \param SVI ShuffleVectorInst to operate on
777
  /// \param Result Result of the computation
778
  ///
779
  /// Compute the left and the right side vector information and merge them by
780
  /// applying the shuffle operation. This function also ensures that the left
781
  /// and right side have compatible loads. This means that all loads are with
782
  /// in the same basic block and are based on the same pointer.
783
  ///
784
  /// \returns false if no sensible information can be gathered.
785
  static bool computeFromSVI(ShuffleVectorInst *SVI, VectorInfo &Result,
786
96.9k
                             const DataLayout &DL) {
787
96.9k
    VectorType *ArgTy = dyn_cast<VectorType>(SVI->getOperand(0)->getType());
788
96.9k
    assert(ArgTy && "ShuffleVector Operand is not a VectorType");
789
96.9k
790
96.9k
    // Compute the left hand vector information.
791
96.9k
    VectorInfo LHS(ArgTy);
792
96.9k
    if (!compute(SVI->getOperand(0), LHS, DL))
793
85.5k
      LHS.BB = nullptr;
794
96.9k
795
96.9k
    // Compute the right hand vector information.
796
96.9k
    VectorInfo RHS(ArgTy);
797
96.9k
    if (!compute(SVI->getOperand(1), RHS, DL))
798
92.6k
      RHS.BB = nullptr;
799
96.9k
800
96.9k
    // Neither operand produced sensible results?
801
96.9k
    if (!LHS.BB && 
!RHS.BB85.5k
)
802
85.4k
      return false;
803
11.4k
    // Only RHS produced sensible results?
804
11.4k
    else if (!LHS.BB) {
805
150
      Result.BB = RHS.BB;
806
150
      Result.PV = RHS.PV;
807
150
    }
808
11.3k
    // Only LHS produced sensible results?
809
11.3k
    else if (!RHS.BB) {
810
7.23k
      Result.BB = LHS.BB;
811
7.23k
      Result.PV = LHS.PV;
812
7.23k
    }
813
4.09k
    // Both operands produced sensible results?
814
4.09k
    else if ((LHS.BB == RHS.BB) && (LHS.PV == RHS.PV)) {
815
2.84k
      Result.BB = LHS.BB;
816
2.84k
      Result.PV = LHS.PV;
817
2.84k
    }
818
1.25k
    // Both operands produced sensible results but they are incompatible.
819
1.25k
    else {
820
1.25k
      return false;
821
1.25k
    }
822
10.2k
823
10.2k
    // Merge and apply the operation on the offset information.
824
10.2k
    if (LHS.BB) {
825
10.0k
      Result.LIs.insert(LHS.LIs.begin(), LHS.LIs.end());
826
10.0k
      Result.Is.insert(LHS.Is.begin(), LHS.Is.end());
827
10.0k
    }
828
10.2k
    if (RHS.BB) {
829
2.99k
      Result.LIs.insert(RHS.LIs.begin(), RHS.LIs.end());
830
2.99k
      Result.Is.insert(RHS.Is.begin(), RHS.Is.end());
831
2.99k
    }
832
10.2k
    Result.Is.insert(SVI);
833
10.2k
    Result.SVI = SVI;
834
10.2k
835
10.2k
    int j = 0;
836
89.6k
    for (int i : SVI->getShuffleMask()) {
837
89.6k
      assert((i < 2 * (signed)ArgTy->getNumElements()) &&
838
89.6k
             "Invalid ShuffleVectorInst (index out of bounds)");
839
89.6k
840
89.6k
      if (i < 0)
841
10.4k
        Result.EI[j] = ElementInfo();
842
79.1k
      else if (i < (signed)ArgTy->getNumElements()) {
843
58.2k
        if (LHS.BB)
844
57.6k
          Result.EI[j] = LHS.EI[i];
845
621
        else
846
621
          Result.EI[j] = ElementInfo();
847
58.2k
      } else {
848
20.9k
        if (RHS.BB)
849
19.3k
          Result.EI[j] = RHS.EI[i - ArgTy->getNumElements()];
850
1.57k
        else
851
1.57k
          Result.EI[j] = ElementInfo();
852
20.9k
      }
853
89.6k
      j++;
854
89.6k
    }
855
10.2k
856
10.2k
    return true;
857
10.2k
  }
858
859
  /// LoadInst specialization to compute vector information.
860
  ///
861
  /// This function also acts as abort condition to the recursion.
862
  ///
863
  /// \param LI LoadInst to operate on
864
  /// \param Result Result of the computation
865
  ///
866
  /// \returns false if no sensible information can be gathered.
867
  static bool computeFromLI(LoadInst *LI, VectorInfo &Result,
868
13.8k
                            const DataLayout &DL) {
869
13.8k
    Value *BasePtr;
870
13.8k
    Polynomial Offset;
871
13.8k
872
13.8k
    if (LI->isVolatile())
873
12
      return false;
874
13.8k
875
13.8k
    if (LI->isAtomic())
876
0
      return false;
877
13.8k
878
13.8k
    // Get the base polynomial
879
13.8k
    computePolynomialFromPointer(*LI->getPointerOperand(), Offset, BasePtr, DL);
880
13.8k
881
13.8k
    Result.BB = LI->getParent();
882
13.8k
    Result.PV = BasePtr;
883
13.8k
    Result.LIs.insert(LI);
884
13.8k
    Result.Is.insert(LI);
885
13.8k
886
124k
    for (unsigned i = 0; i < Result.getDimension(); 
i++110k
) {
887
110k
      Value *Idx[2] = {
888
110k
          ConstantInt::get(Type::getInt32Ty(LI->getContext()), 0),
889
110k
          ConstantInt::get(Type::getInt32Ty(LI->getContext()), i),
890
110k
      };
891
110k
      int64_t Ofs = DL.getIndexedOffsetInType(Result.VTy, makeArrayRef(Idx, 2));
892
110k
      Result.EI[i] = ElementInfo(Offset + Ofs, i == 0 ? 
LI13.8k
:
nullptr96.9k
);
893
110k
    }
894
13.8k
895
13.8k
    return true;
896
13.8k
  }
897
898
  /// Recursively compute polynomial of a value.
899
  ///
900
  /// \param BO Input binary operation
901
  /// \param Result Result polynomial
902
4.35k
  static void computePolynomialBinOp(BinaryOperator &BO, Polynomial &Result) {
903
4.35k
    Value *LHS = BO.getOperand(0);
904
4.35k
    Value *RHS = BO.getOperand(1);
905
4.35k
906
4.35k
    // Find the RHS Constant if any
907
4.35k
    ConstantInt *C = dyn_cast<ConstantInt>(RHS);
908
4.35k
    if ((!C) && 
BO.isCommutative()63
) {
909
63
      C = dyn_cast<ConstantInt>(LHS);
910
63
      if (C)
911
0
        std::swap(LHS, RHS);
912
63
    }
913
4.35k
914
4.35k
    switch (BO.getOpcode()) {
915
4.35k
    case Instruction::Add:
916
3.86k
      if (!C)
917
63
        break;
918
3.80k
919
3.80k
      computePolynomial(*LHS, Result);
920
3.80k
      Result.add(C->getValue());
921
3.80k
      return;
922
3.80k
923
3.80k
    case Instruction::LShr:
924
464
      if (!C)
925
0
        break;
926
464
927
464
      computePolynomial(*LHS, Result);
928
464
      Result.lshr(C->getValue());
929
464
      return;
930
464
931
464
    default:
932
24
      break;
933
87
    }
934
87
935
87
    Result = Polynomial(&BO);
936
87
  }
937
938
  /// Recursively compute polynomial of a value
939
  ///
940
  /// \param V input value
941
  /// \param Result result polynomial
942
9.76k
  static void computePolynomial(Value &V, Polynomial &Result) {
943
9.76k
    if (isa<BinaryOperator>(&V))
944
4.35k
      computePolynomialBinOp(*dyn_cast<BinaryOperator>(&V), Result);
945
5.40k
    else
946
5.40k
      Result = Polynomial(&V);
947
9.76k
  }
948
949
  /// Compute the Polynomial representation of a Pointer type.
950
  ///
951
  /// \param Ptr input pointer value
952
  /// \param Result result polynomial
953
  /// \param BasePtr pointer the polynomial is based on
954
  /// \param DL Datalayout of the target machine
955
  static void computePolynomialFromPointer(Value &Ptr, Polynomial &Result,
956
                                           Value *&BasePtr,
957
22.5k
                                           const DataLayout &DL) {
958
22.5k
    // Not a pointer type? Return an undefined polynomial
959
22.5k
    PointerType *PtrTy = dyn_cast<PointerType>(Ptr.getType());
960
22.5k
    if (!PtrTy) {
961
0
      Result = Polynomial();
962
0
      BasePtr = nullptr;
963
0
      return;
964
0
    }
965
22.5k
    unsigned PointerBits =
966
22.5k
        DL.getIndexSizeInBits(PtrTy->getPointerAddressSpace());
967
22.5k
968
22.5k
    /// Skip pointer casts. Return Zero polynomial otherwise
969
22.5k
    if (isa<CastInst>(&Ptr)) {
970
8.71k
      CastInst &CI = *cast<CastInst>(&Ptr);
971
8.71k
      switch (CI.getOpcode()) {
972
8.71k
      case Instruction::BitCast:
973
8.71k
        computePolynomialFromPointer(*CI.getOperand(0), Result, BasePtr, DL);
974
8.71k
        break;
975
8.71k
      default:
976
0
        BasePtr = &Ptr;
977
0
        Polynomial(PointerBits, 0);
978
0
        break;
979
13.8k
      }
980
13.8k
    }
981
13.8k
    /// Resolve GetElementPtrInst.
982
13.8k
    else if (isa<GetElementPtrInst>(&Ptr)) {
983
10.4k
      GetElementPtrInst &GEP = *cast<GetElementPtrInst>(&Ptr);
984
10.4k
985
10.4k
      APInt BaseOffset(PointerBits, 0);
986
10.4k
987
10.4k
      // Check if we can compute the Offset with accumulateConstantOffset
988
10.4k
      if (GEP.accumulateConstantOffset(DL, BaseOffset)) {
989
4.98k
        Result = Polynomial(BaseOffset);
990
4.98k
        BasePtr = GEP.getPointerOperand();
991
4.98k
        return;
992
5.51k
      } else {
993
5.51k
        // Otherwise we allow that the last index operand of the GEP is
994
5.51k
        // non-constant.
995
5.51k
        unsigned idxOperand, e;
996
5.51k
        SmallVector<Value *, 4> Indices;
997
5.83k
        for (idxOperand = 1, e = GEP.getNumOperands(); idxOperand < e;
998
5.83k
             
idxOperand++323
) {
999
5.83k
          ConstantInt *IDX = dyn_cast<ConstantInt>(GEP.getOperand(idxOperand));
1000
5.83k
          if (!IDX)
1001
5.51k
            break;
1002
323
          Indices.push_back(IDX);
1003
323
        }
1004
5.51k
1005
5.51k
        // It must also be the last operand.
1006
5.51k
        if (idxOperand + 1 != e) {
1007
18
          Result = Polynomial();
1008
18
          BasePtr = nullptr;
1009
18
          return;
1010
18
        }
1011
5.49k
1012
5.49k
        // Compute the polynomial of the index operand.
1013
5.49k
        computePolynomial(*GEP.getOperand(idxOperand), Result);
1014
5.49k
1015
5.49k
        // Compute base offset from zero based index, excluding the last
1016
5.49k
        // variable operand.
1017
5.49k
        BaseOffset =
1018
5.49k
            DL.getIndexedOffsetInType(GEP.getSourceElementType(), Indices);
1019
5.49k
1020
5.49k
        // Apply the operations of GEP to the polynomial.
1021
5.49k
        unsigned ResultSize = DL.getTypeAllocSize(GEP.getResultElementType());
1022
5.49k
        Result.sextOrTrunc(PointerBits);
1023
5.49k
        Result.mul(APInt(PointerBits, ResultSize));
1024
5.49k
        Result.add(BaseOffset);
1025
5.49k
        BasePtr = GEP.getPointerOperand();
1026
5.49k
      }
1027
10.4k
    }
1028
3.30k
    // All other instructions are handled by using the value as base pointer and
1029
3.30k
    // a zero polynomial.
1030
3.30k
    else {
1031
3.30k
      BasePtr = &Ptr;
1032
3.30k
      Polynomial(DL.getIndexSizeInBits(PtrTy->getPointerAddressSpace()), 0);
1033
3.30k
    }
1034
22.5k
  }
1035
1036
#ifndef NDEBUG
1037
  void print(raw_ostream &OS) const {
1038
    if (PV)
1039
      OS << *PV;
1040
    else
1041
      OS << "(none)";
1042
    OS << " + ";
1043
    for (unsigned i = 0; i < getDimension(); i++)
1044
      OS << ((i == 0) ? "[" : ", ") << EI[i].Ofs;
1045
    OS << "]";
1046
  }
1047
#endif
1048
};
1049
1050
} // anonymous namespace
1051
1052
bool InterleavedLoadCombineImpl::findPattern(
1053
    std::list<VectorInfo> &Candidates, std::list<VectorInfo> &InterleavedLoad,
1054
772k
    unsigned Factor, const DataLayout &DL) {
1055
772k
  for (auto C0 = Candidates.begin(), E0 = Candidates.end(); C0 != E0; 
++C0312
) {
1056
412
    unsigned i;
1057
412
    // Try to find an interleaved load using the front of Worklist as first line
1058
412
    unsigned Size = DL.getTypeAllocSize(C0->VTy->getElementType());
1059
412
1060
412
    // List containing iterators pointing to the VectorInfos of the candidates
1061
412
    std::vector<std::list<VectorInfo>::iterator> Res(Factor, Candidates.end());
1062
412
1063
3.95k
    for (auto C = Candidates.begin(), E = Candidates.end(); C != E; 
C++3.54k
) {
1064
3.64k
      if (C->VTy != C0->VTy)
1065
0
        continue;
1066
3.64k
      if (C->BB != C0->BB)
1067
812
        continue;
1068
2.83k
      if (C->PV != C0->PV)
1069
1.71k
        continue;
1070
1.12k
1071
1.12k
      // Check the current value matches any of factor - 1 remaining lines
1072
3.79k
      
for (i = 1; 1.12k
i < Factor;
i++2.67k
) {
1073
2.67k
        if (C->EI[0].Ofs.isProvenEqualTo(C0->EI[0].Ofs + i * Size)) {
1074
270
          Res[i] = C;
1075
270
        }
1076
2.67k
      }
1077
1.12k
1078
1.70k
      for (i = 1; i < Factor; 
i++587
) {
1079
1.60k
        if (Res[i] == Candidates.end())
1080
1.02k
          break;
1081
1.60k
      }
1082
1.12k
      if (i == Factor) {
1083
100
        Res[0] = C0;
1084
100
        break;
1085
100
      }
1086
1.12k
    }
1087
412
1088
412
    if (Res[0] != Candidates.end()) {
1089
100
      // Move the result into the output
1090
350
      for (unsigned i = 0; i < Factor; 
i++250
) {
1091
250
        InterleavedLoad.splice(InterleavedLoad.end(), Candidates, Res[i]);
1092
250
      }
1093
100
1094
100
      return true;
1095
100
    }
1096
412
  }
1097
772k
  
return false771k
;
1098
772k
}
1099
1100
LoadInst *
1101
12
InterleavedLoadCombineImpl::findFirstLoad(const std::set<LoadInst *> &LIs) {
1102
12
  assert(!LIs.empty() && "No load instructions given.");
1103
12
1104
12
  // All LIs are within the same BB. Select the first for a reference.
1105
12
  BasicBlock *BB = (*LIs.begin())->getParent();
1106
12
  BasicBlock::iterator FLI =
1107
100
      std::find_if(BB->begin(), BB->end(), [&LIs](Instruction &I) -> bool {
1108
100
        return is_contained(LIs, &I);
1109
100
      });
1110
12
  assert(FLI != BB->end());
1111
12
1112
12
  return cast<LoadInst>(FLI);
1113
12
}
1114
1115
bool InterleavedLoadCombineImpl::combine(std::list<VectorInfo> &InterleavedLoad,
1116
100
                                         OptimizationRemarkEmitter &ORE) {
1117
100
  LLVM_DEBUG(dbgs() << "Checking interleaved load\n");
1118
100
1119
100
  // The insertion point is the LoadInst which loads the first values. The
1120
100
  // following tests are used to proof that the combined load can be inserted
1121
100
  // just before InsertionPoint.
1122
100
  LoadInst *InsertionPoint = InterleavedLoad.front().EI[0].LI;
1123
100
1124
100
  // Test if the offset is computed
1125
100
  if (!InsertionPoint)
1126
2
    return false;
1127
98
1128
98
  std::set<LoadInst *> LIs;
1129
98
  std::set<Instruction *> Is;
1130
98
  std::set<Instruction *> SVIs;
1131
98
1132
98
  unsigned InterleavedCost;
1133
98
  unsigned InstructionCost = 0;
1134
98
1135
98
  // Get the interleave factor
1136
98
  unsigned Factor = InterleavedLoad.size();
1137
98
1138
98
  // Merge all input sets used in analysis
1139
246
  for (auto &VI : InterleavedLoad) {
1140
246
    // Generate a set of all load instructions to be combined
1141
246
    LIs.insert(VI.LIs.begin(), VI.LIs.end());
1142
246
1143
246
    // Generate a set of all instructions taking part in load
1144
246
    // interleaved. This list excludes the instructions necessary for the
1145
246
    // polynomial construction.
1146
246
    Is.insert(VI.Is.begin(), VI.Is.end());
1147
246
1148
246
    // Generate the set of the final ShuffleVectorInst.
1149
246
    SVIs.insert(VI.SVI);
1150
246
  }
1151
98
1152
98
  // There is nothing to combine.
1153
98
  if (LIs.size() < 2)
1154
84
    return false;
1155
14
1156
14
  // Test if all participating instruction will be dead after the
1157
14
  // transformation. If intermediate results are used, no performance gain can
1158
14
  // be expected. Also sum the cost of the Instructions beeing left dead.
1159
108
  
for (auto &I : Is)14
{
1160
108
    // Compute the old cost
1161
108
    InstructionCost +=
1162
108
        TTI.getInstructionCost(I, TargetTransformInfo::TCK_Latency);
1163
108
1164
108
    // The final SVIs are allowed not to be dead, all uses will be replaced
1165
108
    if (SVIs.find(I) != SVIs.end())
1166
38
      continue;
1167
70
1168
70
    // If there are users outside the set to be eliminated, we abort the
1169
70
    // transformation. No gain can be expected.
1170
138
    
for (const auto &U : I->users())70
{
1171
138
      if (Is.find(dyn_cast<Instruction>(U)) == Is.end())
1172
2
        return false;
1173
138
    }
1174
70
  }
1175
14
1176
14
  // We know that all LoadInst are within the same BB. This guarantees that
1177
14
  // either everything or nothing is loaded.
1178
14
  LoadInst *First = findFirstLoad(LIs);
1179
12
1180
12
  // To be safe that the loads can be combined, iterate over all loads and test
1181
12
  // that the corresponding defining access dominates first LI. This guarantees
1182
12
  // that there are no aliasing stores in between the loads.
1183
12
  auto FMA = MSSA.getMemoryAccess(First);
1184
38
  for (auto LI : LIs) {
1185
38
    auto MADef = MSSA.getMemoryAccess(LI)->getDefiningAccess();
1186
38
    if (!MSSA.dominates(MADef, FMA))
1187
0
      return false;
1188
38
  }
1189
12
  assert(!LIs.empty() && "There are no LoadInst to combine");
1190
12
1191
12
  // It is necessary that insertion point dominates all final ShuffleVectorInst.
1192
38
  for (auto &VI : InterleavedLoad) {
1193
38
    if (!DT.dominates(InsertionPoint, VI.SVI))
1194
2
      return false;
1195
38
  }
1196
12
1197
12
  // All checks are done. Add instructions detectable by InterleavedAccessPass
1198
12
  // The old instruction will are left dead.
1199
12
  IRBuilder<> Builder(InsertionPoint);
1200
10
  Type *ETy = InterleavedLoad.front().SVI->getType()->getElementType();
1201
10
  unsigned ElementsPerSVI =
1202
10
      InterleavedLoad.front().SVI->getType()->getNumElements();
1203
10
  VectorType *ILTy = VectorType::get(ETy, Factor * ElementsPerSVI);
1204
10
1205
10
  SmallVector<unsigned, 4> Indices;
1206
44
  for (unsigned i = 0; i < Factor; 
i++34
)
1207
34
    Indices.push_back(i);
1208
10
  InterleavedCost = TTI.getInterleavedMemoryOpCost(
1209
10
      Instruction::Load, ILTy, Factor, Indices, InsertionPoint->getAlignment(),
1210
10
      InsertionPoint->getPointerAddressSpace());
1211
10
1212
10
  if (InterleavedCost >= InstructionCost) {
1213
0
    return false;
1214
0
  }
1215
10
1216
10
  // Create a pointer cast for the wide load.
1217
10
  auto CI = Builder.CreatePointerCast(InsertionPoint->getOperand(0),
1218
10
                                      ILTy->getPointerTo(),
1219
10
                                      "interleaved.wide.ptrcast");
1220
10
1221
10
  // Create the wide load and update the MemorySSA.
1222
10
  auto LI = Builder.CreateAlignedLoad(ILTy, CI, InsertionPoint->getAlignment(),
1223
10
                                      "interleaved.wide.load");
1224
10
  auto MSSAU = MemorySSAUpdater(&MSSA);
1225
10
  MemoryUse *MSSALoad = cast<MemoryUse>(MSSAU.createMemoryAccessBefore(
1226
10
      LI, nullptr, MSSA.getMemoryAccess(InsertionPoint)));
1227
10
  MSSAU.insertUse(MSSALoad);
1228
10
1229
10
  // Create the final SVIs and replace all uses.
1230
10
  int i = 0;
1231
34
  for (auto &VI : InterleavedLoad) {
1232
34
    SmallVector<uint32_t, 4> Mask;
1233
170
    for (unsigned j = 0; j < ElementsPerSVI; 
j++136
)
1234
136
      Mask.push_back(i + j * Factor);
1235
34
1236
34
    Builder.SetInsertPoint(VI.SVI);
1237
34
    auto SVI = Builder.CreateShuffleVector(LI, UndefValue::get(LI->getType()),
1238
34
                                           Mask, "interleaved.shuffle");
1239
34
    VI.SVI->replaceAllUsesWith(SVI);
1240
34
    i++;
1241
34
  }
1242
10
1243
10
  NumInterleavedLoadCombine++;
1244
10
  ORE.emit([&]() {
1245
0
    return OptimizationRemark(DEBUG_TYPE, "Combined Interleaved Load", LI)
1246
0
           << "Load interleaved combined with factor "
1247
0
           << ore::NV("Factor", Factor);
1248
0
  });
1249
10
1250
10
  return true;
1251
10
}
1252
1253
257k
bool InterleavedLoadCombineImpl::run() {
1254
257k
  OptimizationRemarkEmitter ORE(&F);
1255
257k
  bool changed = false;
1256
257k
  unsigned MaxFactor = TLI.getMaxSupportedInterleaveFactor();
1257
257k
1258
257k
  auto &DL = F.getParent()->getDataLayout();
1259
257k
1260
257k
  // Start with the highest factor to avoid combining and recombining.
1261
1.02M
  for (unsigned Factor = MaxFactor; Factor >= 2; 
Factor--771k
) {
1262
771k
    std::list<VectorInfo> Candidates;
1263
771k
1264
6.39M
    for (BasicBlock &BB : F) {
1265
34.4M
      for (Instruction &I : BB) {
1266
34.4M
        if (auto SVI = dyn_cast<ShuffleVectorInst>(&I)) {
1267
93.4k
1268
93.4k
          Candidates.emplace_back(SVI->getType());
1269
93.4k
1270
93.4k
          if (!VectorInfo::computeFromSVI(SVI, Candidates.back(), DL)) {
1271
84.9k
            Candidates.pop_back();
1272
84.9k
            continue;
1273
84.9k
          }
1274
8.45k
1275
8.45k
          if (!Candidates.back().isInterleaved(Factor, DL)) {
1276
8.17k
            Candidates.pop_back();
1277
8.17k
          }
1278
8.45k
        }
1279
34.4M
      }
1280
6.39M
    }
1281
771k
1282
771k
    std::list<VectorInfo> InterleavedLoad;
1283
772k
    while (findPattern(Candidates, InterleavedLoad, Factor, DL)) {
1284
100
      if (combine(InterleavedLoad, ORE)) {
1285
10
        changed = true;
1286
90
      } else {
1287
90
        // Remove the first element of the Interleaved Load but put the others
1288
90
        // back on the list and continue searching
1289
90
        Candidates.splice(Candidates.begin(), InterleavedLoad,
1290
90
                          std::next(InterleavedLoad.begin()),
1291
90
                          InterleavedLoad.end());
1292
90
      }
1293
100
      InterleavedLoad.clear();
1294
100
    }
1295
771k
  }
1296
257k
1297
257k
  return changed;
1298
257k
}
1299
1300
namespace {
1301
/// This pass combines interleaved loads into a pattern detectable by
1302
/// InterleavedAccessPass.
1303
struct InterleavedLoadCombine : public FunctionPass {
1304
  static char ID;
1305
1306
8.62k
  InterleavedLoadCombine() : FunctionPass(ID) {
1307
8.62k
    initializeInterleavedLoadCombinePass(*PassRegistry::getPassRegistry());
1308
8.62k
  }
1309
1310
257k
  StringRef getPassName() const override {
1311
257k
    return "Interleaved Load Combine Pass";
1312
257k
  }
1313
1314
257k
  bool runOnFunction(Function &F) override {
1315
257k
    if (DisableInterleavedLoadCombine)
1316
0
      return false;
1317
257k
1318
257k
    auto *TPC = getAnalysisIfAvailable<TargetPassConfig>();
1319
257k
    if (!TPC)
1320
0
      return false;
1321
257k
1322
257k
    LLVM_DEBUG(dbgs() << "*** " << getPassName() << ": " << F.getName()
1323
257k
                      << "\n");
1324
257k
1325
257k
    return InterleavedLoadCombineImpl(
1326
257k
               F, getAnalysis<DominatorTreeWrapperPass>().getDomTree(),
1327
257k
               getAnalysis<MemorySSAWrapperPass>().getMSSA(),
1328
257k
               TPC->getTM<TargetMachine>())
1329
257k
        .run();
1330
257k
  }
1331
1332
8.59k
  void getAnalysisUsage(AnalysisUsage &AU) const override {
1333
8.59k
    AU.addRequired<MemorySSAWrapperPass>();
1334
8.59k
    AU.addRequired<DominatorTreeWrapperPass>();
1335
8.59k
    FunctionPass::getAnalysisUsage(AU);
1336
8.59k
  }
1337
1338
private:
1339
};
1340
} // anonymous namespace
1341
1342
char InterleavedLoadCombine::ID = 0;
1343
1344
49.1k
INITIALIZE_PASS_BEGIN(
1345
49.1k
    InterleavedLoadCombine, DEBUG_TYPE,
1346
49.1k
    "Combine interleaved loads into wide loads and shufflevector instructions",
1347
49.1k
    false, false)
1348
49.1k
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
1349
49.1k
INITIALIZE_PASS_DEPENDENCY(MemorySSAWrapperPass)
1350
49.1k
INITIALIZE_PASS_END(
1351
    InterleavedLoadCombine, DEBUG_TYPE,
1352
    "Combine interleaved loads into wide loads and shufflevector instructions",
1353
    false, false)
1354
1355
FunctionPass *
1356
8.62k
llvm::createInterleavedLoadCombinePass() {
1357
8.62k
  auto P = new InterleavedLoadCombine();
1358
8.62k
  return P;
1359
8.62k
}