contrib/llvm-project/llvm/lib/CodeGen/InterleavedLoadCombinePass.cpp

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