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/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 #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         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   Polynomial(Value *V) : ErrorMSBs((unsigned)-1), V(V), B(), A() {
 187     IntegerType *Ty = dyn_cast<IntegerType>(V->getType());
 188     if (Ty) {
 189       ErrorMSBs = 0;
 190       this->V = V;
 191       A = APInt(Ty->getBitWidth(), 0);
 192     }
 193   }
 194
 195   Polynomial(const APInt &A, unsigned ErrorMSBs = 0)
 196       : ErrorMSBs(ErrorMSBs), V(NULL), B(), A(A) {}
 197
 198   Polynomial(unsigned BitWidth, uint64_t A, unsigned ErrorMSBs = 0)
 199       : ErrorMSBs(ErrorMSBs), V(NULL), B(), A(BitWidth, A) {}
 200
 201   Polynomial() : ErrorMSBs((unsigned)-1), V(NULL), B(), A() {}
 202
 203   /// Increment and clamp the number of undefined bits.
 204   void incErrorMSBs(unsigned amt) {
 205     if (ErrorMSBs == (unsigned)-1)
 206       return;
 207
 208     ErrorMSBs += amt;
 209     if (ErrorMSBs > A.getBitWidth())
 210       ErrorMSBs = A.getBitWidth();
 211   }
 212
 213   /// Decrement and clamp the number of undefined bits.
 214   void decErrorMSBs(unsigned amt) {
 215     if (ErrorMSBs == (unsigned)-1)
 216       return;
 217
 218     if (ErrorMSBs > amt)
 219       ErrorMSBs -= amt;
 220     else
 221       ErrorMSBs = 0;
 222   }
 223
 224   /// Apply an add on the polynomial
 225   Polynomial &add(const APInt &C) {
 226     // Note: Addition is associative in two's complement even when in case of
 227     // signed overflow.
 228     //
 229     // Error bits can only propagate into higher significant bits. As these are
 230     // already regarded as undefined, there is no change.
 231     //
 232     // Theorem: Adding a constant to a polynomial does not change the error
 233     // term.
 234     //
 235     // Proof:
 236     //
 237     //   Since the addition is associative and commutes:
 238     //
 239     //   (B + A + E*2^(n-e)) + C = B + (A + C) + E*2^(n-e)
 240     // [qed]
 241
 242     if (C.getBitWidth() != A.getBitWidth()) {
 243       ErrorMSBs = (unsigned)-1;
 244       return *this;
 245     }
 246
 247     A += C;
 248     return *this;
 249   }
 250
 251   /// Apply a multiplication onto the polynomial.
 252   Polynomial &mul(const APInt &C) {
 253     // Note: Multiplication distributes over the addition
 254     //
 255     // Theorem: Multiplication distributes over the addition
 256     //
 257     // Proof(1):
 258     //
 259     //   (B+A)*C =-
 260     //        = (B + A) + (B + A) + .. {C Times}
 261     //         addition is associative and commutes, hence
 262     //        = B + B + .. {C Times} .. + A + A + .. {C times}
 263     //        = B*C + A*C
 264     //   (see (function add) for signed values and overflows)
 265     // [qed]
 266     //
 267     // Theorem: If C has c trailing zeros, errors bits in A or B are shifted out
 268     // to the left.
 269     //
 270     // Proof(2):
 271     //
 272     //   Let B' and A' be the n-Bit inputs with some unknown errors EA,
 273     //   EB at e leading bits. B' and A' can be written down as:
 274     //
 275     //     B' = B + 2^(n-e)*EB
 276     //     A' = A + 2^(n-e)*EA
 277     //
 278     //   Let C' be an input with c trailing zero bits. C' can be written as
 279     //
 280     //     C' = C*2^c
 281     //
 282     //   Therefore we can compute the result by using distributivity and
 283     //   commutativity.
 284     //
 285     //     (B'*C' + A'*C') = [B + 2^(n-e)*EB] * C' + [A + 2^(n-e)*EA] * C' =
 286     //                     = [B + 2^(n-e)*EB + A + 2^(n-e)*EA] * C' =
 287     //                     = (B'+A') * C' =
 288     //                     = [B + 2^(n-e)*EB + A + 2^(n-e)*EA] * C' =
 289     //                     = [B + A + 2^(n-e)*EB + 2^(n-e)*EA] * C' =
 290     //                     = (B + A) * C' + [2^(n-e)*EB + 2^(n-e)*EA)] * C' =
 291     //                     = (B + A) * C' + [2^(n-e)*EB + 2^(n-e)*EA)] * C*2^c =
 292     //                     = (B + A) * C' + C*(EB + EA)*2^(n-e)*2^c =
 293     //
 294     //   Let EC be the final error with EC = C*(EB + EA)
 295     //
 296     //                     = (B + A)*C' + EC*2^(n-e)*2^c =
 297     //                     = (B + A)*C' + EC*2^(n-(e-c))
 298     //
 299     //   Since EC is multiplied by 2^(n-(e-c)) the resulting error contains c
 300     //   less error bits than the input. c bits are shifted out to the left.
 301     // [qed]
 302
 303     if (C.getBitWidth() != A.getBitWidth()) {
 304       ErrorMSBs = (unsigned)-1;
 305       return *this;
 306     }
 307
 308     // Multiplying by one is a no-op.
 309     if (C.isOneValue()) {
 310       return *this;
 311     }
 312
 313     // Multiplying by zero removes the coefficient B and defines all bits.
 314     if (C.isNullValue()) {
 315       ErrorMSBs = 0;
 316       deleteB();
 317     }
 318
 319     // See Proof(2): Trailing zero bits indicate a left shift. This removes
 320     // leading bits from the result even if they are undefined.
 321     decErrorMSBs(C.countTrailingZeros());
 322
 323     A *= C;
 324     pushBOperation(Mul, C);
 325     return *this;
 326   }
 327
 328   /// Apply a logical shift right on the polynomial
 329   Polynomial &lshr(const APInt &C) {
 330     // Theorem(1): (B + A + E*2^(n-e)) >> 1 => (B >> 1) + (A >> 1) + E'*2^(n-e')
 331     //          where
 332     //             e' = e + 1,
 333     //             E is a e-bit number,
 334     //             E' is a e'-bit number,
 335     //   holds under the following precondition:
 336     //          pre(1): A % 2 = 0
 337     //          pre(2): e < n, (see Theorem(2) for the trivial case with e=n)
 338     //   where >> expresses a logical shift to the right, with adding zeros.
 339     //
 340     //  We need to show that for every, E there is a E'
 341     //
 342     //  B = b_h * 2^(n-1) + b_m * 2 + b_l
 343     //  A = a_h * 2^(n-1) + a_m * 2         (pre(1))
 344     //
 345     //  where a_h, b_h, b_l are single bits, and a_m, b_m are (n-2) bit numbers
 346     //
 347     //  Let X = (B + A + E*2^(n-e)) >> 1
 348     //  Let Y = (B >> 1) + (A >> 1) + E*2^(n-e) >> 1
 349     //
 350     //    X = [B + A + E*2^(n-e)] >> 1 =
 351     //      = [  b_h * 2^(n-1) + b_m * 2 + b_l +
 352     //         + a_h * 2^(n-1) + a_m * 2 +
 353     //         + E * 2^(n-e) ] >> 1 =
 354     //
 355     //    The sum is built by putting the overflow of [a_m + b+n] into the term
 356     //    2^(n-1). As there are no more bits beyond 2^(n-1) the overflow within
 357     //    this bit is discarded. This is expressed by % 2.
 358     //
 359     //    The bit in position 0 cannot overflow into the term (b_m + a_m).
 360     //
 361     //      = [  ([b_h + a_h + (b_m + a_m) >> (n-2)] % 2) * 2^(n-1) +
 362     //         + ((b_m + a_m) % 2^(n-2)) * 2 +
 363     //         + b_l + E * 2^(n-e) ] >> 1 =
 364     //
 365     //    The shift is computed by dividing the terms by 2 and by cutting off
 366     //    b_l.
 367     //
 368     //      =    ([b_h + a_h + (b_m + a_m) >> (n-2)] % 2) * 2^(n-2) +
 369     //         + ((b_m + a_m) % 2^(n-2)) +
 370     //         + E * 2^(n-(e+1)) =
 371     //
 372     //    by the definition in the Theorem e+1 = e'
 373     //
 374     //      =    ([b_h + a_h + (b_m + a_m) >> (n-2)] % 2) * 2^(n-2) +
 375     //         + ((b_m + a_m) % 2^(n-2)) +
 376     //         + E * 2^(n-e') =
 377     //
 378     //    Compute Y by applying distributivity first
 379     //
 380     //    Y =  (B >> 1) + (A >> 1) + E*2^(n-e') =
 381     //      =    (b_h * 2^(n-1) + b_m * 2 + b_l) >> 1 +
 382     //         + (a_h * 2^(n-1) + a_m * 2) >> 1 +
 383     //         + E * 2^(n-e) >> 1 =
 384     //
 385     //    Again, the shift is computed by dividing the terms by 2 and by cutting
 386     //    off b_l.
 387     //
 388     //      =     b_h * 2^(n-2) + b_m +
 389     //         +  a_h * 2^(n-2) + a_m +
 390     //         +  E * 2^(n-(e+1)) =
 391     //
 392     //    Again, the sum is built by putting the overflow of [a_m + b+n] into
 393     //    the term 2^(n-1). But this time there is room for a second bit in the
 394     //    term 2^(n-2) we add this bit to a new term and denote it o_h in a
 395     //    second step.
 396     //
 397     //      =    ([b_h + a_h + (b_m + a_m) >> (n-2)] >> 1) * 2^(n-1) +
 398     //         + ([b_h + a_h + (b_m + a_m) >> (n-2)] % 2) * 2^(n-2) +
 399     //         + ((b_m + a_m) % 2^(n-2)) +
 400     //         + E * 2^(n-(e+1)) =
 401     //
 402     //    Let o_h = [b_h + a_h + (b_m + a_m) >> (n-2)] >> 1
 403     //    Further replace e+1 by e'.
 404     //
 405     //      =    o_h * 2^(n-1) +
 406     //         + ([b_h + a_h + (b_m + a_m) >> (n-2)] % 2) * 2^(n-2) +
 407     //         + ((b_m + a_m) % 2^(n-2)) +
 408     //         + E * 2^(n-e') =
 409     //
 410     //    Move o_h into the error term and construct E'. To ensure that there is
 411     //    no 2^x with negative x, this step requires pre(2) (e < n).
 412     //
 413     //      =    ([b_h + a_h + (b_m + a_m) >> (n-2)] % 2) * 2^(n-2) +
 414     //         + ((b_m + a_m) % 2^(n-2)) +
 415     //         + o_h * 2^(e'-1) * 2^(n-e') +               | pre(2), move 2^(e'-1)
 416     //                                                     | out of the old exponent
 417     //         + E * 2^(n-e') =
 418     //      =    ([b_h + a_h + (b_m + a_m) >> (n-2)] % 2) * 2^(n-2) +
 419     //         + ((b_m + a_m) % 2^(n-2)) +
 420     //         + [o_h * 2^(e'-1) + E] * 2^(n-e') +         | move 2^(e'-1) out of
 421     //                                                     | the old exponent
 422     //
 423     //    Let E' = o_h * 2^(e'-1) + E
 424     //
 425     //      =    ([b_h + a_h + (b_m + a_m) >> (n-2)] % 2) * 2^(n-2) +
 426     //         + ((b_m + a_m) % 2^(n-2)) +
 427     //         + E' * 2^(n-e')
 428     //
 429     //    Because X and Y are distinct only in there error terms and E' can be
 430     //    constructed as shown the theorem holds.
 431     // [qed]
 432     //
 433     // For completeness in case of the case e=n it is also required to show that
 434     // distributivity can be applied.
 435     //
 436     // In this case Theorem(1) transforms to (the pre-condition on A can also be
 437     // dropped)
 438     //
 439     // Theorem(2): (B + A + E) >> 1 => (B >> 1) + (A >> 1) + E'
 440     //          where
 441     //             A, B, E, E' are two's complement numbers with the same bit
 442     //             width
 443     //
 444     //   Let A + B + E = X
 445     //   Let (B >> 1) + (A >> 1) = Y
 446     //
 447     //   Therefore we need to show that for every X and Y there is an E' which
 448     //   makes the equation
 449     //
 450     //     X = Y + E'
 451     //
 452     //   hold. This is trivially the case for E' = X - Y.
 453     //
 454     // [qed]
 455     //
 456     // Remark: Distributing lshr with and arbitrary number n can be expressed as
 457     //   ((((B + A) lshr 1) lshr 1) ... ) {n times}.
 458     // This construction induces n additional error bits at the left.
 459
 460     if (C.getBitWidth() != A.getBitWidth()) {
 461       ErrorMSBs = (unsigned)-1;
 462       return *this;
 463     }
 464
 465     if (C.isNullValue())
 466       return *this;
 467
 468     // Test if the result will be zero
 469     unsigned shiftAmt = C.getZExtValue();
 470     if (shiftAmt >= C.getBitWidth())
 471       return mul(APInt(C.getBitWidth(), 0));
 472
 473     // The proof that shiftAmt LSBs are zero for at least one summand is only
 474     // possible for the constant number.
 475     //
 476     // If this can be proven add shiftAmt to the error counter
 477     // `ErrorMSBs`. Otherwise set all bits as undefined.
 478     if (A.countTrailingZeros() < shiftAmt)
 479       ErrorMSBs = A.getBitWidth();
 480     else
 481       incErrorMSBs(shiftAmt);
 482
 483     // Apply the operation.
 484     pushBOperation(LShr, C);
 485     A = A.lshr(shiftAmt);
 486
 487     return *this;
 488   }
 489
 490   /// Apply a sign-extend or truncate operation on the polynomial.
 491   Polynomial &sextOrTrunc(unsigned n) {
 492     if (n < A.getBitWidth()) {
 493       // Truncate: Clearly undefined Bits on the MSB side are removed
 494       // if there are any.
 495       decErrorMSBs(A.getBitWidth() - n);
 496       A = A.trunc(n);
 497       pushBOperation(Trunc, APInt(sizeof(n) * 8, n));
 498     }
 499     if (n > A.getBitWidth()) {
 500       // Extend: Clearly extending first and adding later is different
 501       // to adding first and extending later in all extended bits.
 502       incErrorMSBs(n - A.getBitWidth());
 503       A = A.sext(n);
 504       pushBOperation(SExt, APInt(sizeof(n) * 8, n));
 505     }
 506
 507     return *this;
 508   }
 509
 510   /// Test if there is a coefficient B.
 511   bool isFirstOrder() const { return V != nullptr; }
 512
 513   /// Test coefficient B of two Polynomials are equal.
 514   bool isCompatibleTo(const Polynomial &o) const {
 515     // The polynomial use different bit width.
 516     if (A.getBitWidth() != o.A.getBitWidth())
 517       return false;
 518
 519     // If neither Polynomial has the Coefficient B.
 520     if (!isFirstOrder() && !o.isFirstOrder())
 521       return true;
 522
 523     // The index variable is different.
 524     if (V != o.V)
 525       return false;
 526
 527     // Check the operations.
 528     if (B.size() != o.B.size())
 529       return false;
 530
 531     auto ob = o.B.begin();
 532     for (auto &b : B) {
 533       if (b != *ob)
 534         return false;
 535       ob++;
 536     }
 537
 538     return true;
 539   }
 540
 541   /// Subtract two polynomials, return an undefined polynomial if
 542   /// subtraction is not possible.
 543   Polynomial operator-(const Polynomial &o) const {
 544     // Return an undefined polynomial if incompatible.
 545     if (!isCompatibleTo(o))
 546       return Polynomial();
 547
 548     // If the polynomials are compatible (meaning they have the same
 549     // coefficient on B), B is eliminated. Thus a polynomial solely
 550     // containing A is returned
 551     return Polynomial(A - o.A, std::max(ErrorMSBs, o.ErrorMSBs));
 552   }
 553
 554   /// Subtract a constant from a polynomial,
 555   Polynomial operator-(uint64_t C) const {
 556     Polynomial Result(*this);
 557     Result.A -= C;
 558     return Result;
 559   }
 560
 561   /// Add a constant to a polynomial,
 562   Polynomial operator+(uint64_t C) const {
 563     Polynomial Result(*this);
 564     Result.A += C;
 565     return Result;
 566   }
 567
 568   /// Returns true if it can be proven that two Polynomials are equal.
 569   bool isProvenEqualTo(const Polynomial &o) {
 570     // Subtract both polynomials and test if it is fully defined and zero.
 571     Polynomial r = *this - o;
 572     return (r.ErrorMSBs == 0) && (!r.isFirstOrder()) && (r.A.isNullValue());
 573   }
 574
 575   /// Print the polynomial into a stream.
 576   void print(raw_ostream &OS) const {
 577     OS << "[{#ErrBits:" << ErrorMSBs << "} ";
 578
 579     if (V) {
 580       for (auto b : B)
 581         OS << "(";
 582       OS << "(" << *V << ") ";
 583
 584       for (auto b : B) {
 585         switch (b.first) {
 586         case LShr:
 587           OS << "LShr ";
 588           break;
 589         case Mul:
 590           OS << "Mul ";
 591           break;
 592         case SExt:
 593           OS << "SExt ";
 594           break;
 595         case Trunc:
 596           OS << "Trunc ";
 597           break;
 598         }
 599
 600         OS << b.second << ") ";
 601       }
 602     }
 603
 604     OS << "+ " << A << "]";
 605   }
 606
 607 private:
 608   void deleteB() {
 609     V = nullptr;
 610     B.clear();
 611   }
 612
 613   void pushBOperation(const BOps Op, const APInt &C) {
 614     if (isFirstOrder()) {
 615       B.push_back(std::make_pair(Op, C));
 616       return;
 617     }
 618   }
 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   VectorInfo(const VectorInfo &c) : VTy(c.VTy) {
 638     llvm_unreachable(
 639         "Copying VectorInfo is neither implemented nor necessary,");
 640   }
 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         : 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       : BB(nullptr), PV(nullptr), LIs(), Is(), SVI(nullptr), VTy(VTy) {
 679     EI = new ElementInfo[VTy->getNumElements()];
 680   }
 681
 682   virtual ~VectorInfo() { delete[] EI; }
 683
 684   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   bool isInterleaved(unsigned Factor, const DataLayout &DL) const {
 694     unsigned Size = DL.getTypeAllocSize(VTy->getElementType());
 695     for (unsigned i = 1; i < getDimension(); i++) {
 696       if (!EI[i].Ofs.isProvenEqualTo(EI[0].Ofs + i * Factor * Size)) {
 697         return false;
 698       }
 699     }
 700     return true;
 701   }
 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   static bool compute(Value *V, VectorInfo &Result, const DataLayout &DL) {
 712     ShuffleVectorInst *SVI = dyn_cast<ShuffleVectorInst>(V);
 713     if (SVI)
 714       return computeFromSVI(SVI, Result, DL);
 715     LoadInst *LI = dyn_cast<LoadInst>(V);
 716     if (LI)
 717       return computeFromLI(LI, Result, DL);
 718     BitCastInst *BCI = dyn_cast<BitCastInst>(V);
 719     if (BCI)
 720       return computeFromBCI(BCI, Result, DL);
 721     return false;
 722   }
 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                              const DataLayout &DL) {
 732     Instruction *Op = dyn_cast<Instruction>(BCI->getOperand(0));
 733
 734     if (!Op)
 735       return false;
 736
 737     VectorType *VTy = dyn_cast<VectorType>(Op->getType());
 738     if (!VTy)
 739       return false;
 740
 741     // We can only cast from large to smaller vectors
 742     if (Result.VTy->getNumElements() % VTy->getNumElements())
 743       return false;
 744
 745     unsigned Factor = Result.VTy->getNumElements() / VTy->getNumElements();
 746     unsigned NewSize = DL.getTypeAllocSize(Result.VTy->getElementType());
 747     unsigned OldSize = DL.getTypeAllocSize(VTy->getElementType());
 748
 749     if (NewSize * Factor != OldSize)
 750       return false;
 751
 752     VectorInfo Old(VTy);
 753     if (!compute(Op, Old, DL))
 754       return false;
 755
 756     for (unsigned i = 0; i < Result.VTy->getNumElements(); i += Factor) {
 757       for (unsigned j = 0; j < Factor; j++) {
 758         Result.EI[i + j] =
 759             ElementInfo(Old.EI[i / Factor].Ofs + j * NewSize,
 760                         j == 0 ? Old.EI[i / Factor].LI : nullptr);
 761       }
 762     }
 763
 764     Result.BB = Old.BB;
 765     Result.PV = Old.PV;
 766     Result.LIs.insert(Old.LIs.begin(), Old.LIs.end());
 767     Result.Is.insert(Old.Is.begin(), Old.Is.end());
 768     Result.Is.insert(BCI);
 769     Result.SVI = nullptr;
 770
 771     return true;
 772   }
 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                              const DataLayout &DL) {
 787     VectorType *ArgTy = dyn_cast<VectorType>(SVI->getOperand(0)->getType());
 788     assert(ArgTy && "ShuffleVector Operand is not a VectorType");
 789
 790     // Compute the left hand vector information.
 791     VectorInfo LHS(ArgTy);
 792     if (!compute(SVI->getOperand(0), LHS, DL))
 793       LHS.BB = nullptr;
 794
 795     // Compute the right hand vector information.
 796     VectorInfo RHS(ArgTy);
 797     if (!compute(SVI->getOperand(1), RHS, DL))
 798       RHS.BB = nullptr;
 799
 800     // Neither operand produced sensible results?
 801     if (!LHS.BB && !RHS.BB)
 802       return false;
 803     // Only RHS produced sensible results?
 804     else if (!LHS.BB) {
 805       Result.BB = RHS.BB;
 806       Result.PV = RHS.PV;
 807     }
 808     // Only LHS produced sensible results?
 809     else if (!RHS.BB) {
 810       Result.BB = LHS.BB;
 811       Result.PV = LHS.PV;
 812     }
 813     // Both operands produced sensible results?
 814     else if ((LHS.BB == RHS.BB) && (LHS.PV == RHS.PV)) {
 815       Result.BB = LHS.BB;
 816       Result.PV = LHS.PV;
 817     }
 818     // Both operands produced sensible results but they are incompatible.
 819     else {
 820       return false;
 821     }
 822
 823     // Merge and apply the operation on the offset information.
 824     if (LHS.BB) {
 825       Result.LIs.insert(LHS.LIs.begin(), LHS.LIs.end());
 826       Result.Is.insert(LHS.Is.begin(), LHS.Is.end());
 827     }
 828     if (RHS.BB) {
 829       Result.LIs.insert(RHS.LIs.begin(), RHS.LIs.end());
 830       Result.Is.insert(RHS.Is.begin(), RHS.Is.end());
 831     }
 832     Result.Is.insert(SVI);
 833     Result.SVI = SVI;
 834
 835     int j = 0;
 836     for (int i : SVI->getShuffleMask()) {
 837       assert((i < 2 * (signed)ArgTy->getNumElements()) &&
 838              "Invalid ShuffleVectorInst (index out of bounds)");
 839
 840       if (i < 0)
 841         Result.EI[j] = ElementInfo();
 842       else if (i < (signed)ArgTy->getNumElements()) {
 843         if (LHS.BB)
 844           Result.EI[j] = LHS.EI[i];
 845         else
 846           Result.EI[j] = ElementInfo();
 847       } else {
 848         if (RHS.BB)
 849           Result.EI[j] = RHS.EI[i - ArgTy->getNumElements()];
 850         else
 851           Result.EI[j] = ElementInfo();
 852       }
 853       j++;
 854     }
 855
 856     return true;
 857   }
 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                             const DataLayout &DL) {
 869     Value *BasePtr;
 870     Polynomial Offset;
 871
 872     if (LI->isVolatile())
 873       return false;
 874
 875     if (LI->isAtomic())
 876       return false;
 877
 878     // Get the base polynomial
 879     computePolynomialFromPointer(*LI->getPointerOperand(), Offset, BasePtr, DL);
 880
 881     Result.BB = LI->getParent();
 882     Result.PV = BasePtr;
 883     Result.LIs.insert(LI);
 884     Result.Is.insert(LI);
 885
 886     for (unsigned i = 0; i < Result.getDimension(); i++) {
 887       Value *Idx[2] = {
 888           ConstantInt::get(Type::getInt32Ty(LI->getContext()), 0),
 889           ConstantInt::get(Type::getInt32Ty(LI->getContext()), i),
 890       };
 891       int64_t Ofs = DL.getIndexedOffsetInType(Result.VTy, makeArrayRef(Idx, 2));
 892       Result.EI[i] = ElementInfo(Offset + Ofs, i == 0 ? LI : nullptr);
 893     }
 894
 895     return true;
 896   }
 897
 898   /// Recursively compute polynomial of a value.
 899   ///
 900   /// \param BO Input binary operation
 901   /// \param Result Result polynomial
 902   static void computePolynomialBinOp(BinaryOperator &BO, Polynomial &Result) {
 903     Value *LHS = BO.getOperand(0);
 904     Value *RHS = BO.getOperand(1);
 905
 906     // Find the RHS Constant if any
 907     ConstantInt *C = dyn_cast<ConstantInt>(RHS);
 908     if ((!C) && BO.isCommutative()) {
 909       C = dyn_cast<ConstantInt>(LHS);
 910       if (C)
 911         std::swap(LHS, RHS);
 912     }
 913
 914     switch (BO.getOpcode()) {
 915     case Instruction::Add:
 916       if (!C)
 917         break;
 918
 919       computePolynomial(*LHS, Result);
 920       Result.add(C->getValue());
 921       return;
 922
 923     case Instruction::LShr:
 924       if (!C)
 925         break;
 926
 927       computePolynomial(*LHS, Result);
 928       Result.lshr(C->getValue());
 929       return;
 930
 931     default:
 932       break;
 933     }
 934
 935     Result = Polynomial(&BO);
 936   }
 937
 938   /// Recursively compute polynomial of a value
 939   ///
 940   /// \param V input value
 941   /// \param Result result polynomial
 942   static void computePolynomial(Value &V, Polynomial &Result) {
 943     if (isa<BinaryOperator>(&V))
 944       computePolynomialBinOp(*dyn_cast<BinaryOperator>(&V), Result);
 945     else
 946       Result = Polynomial(&V);
 947   }
 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                                            const DataLayout &DL) {
 958     // Not a pointer type? Return an undefined polynomial
 959     PointerType *PtrTy = dyn_cast<PointerType>(Ptr.getType());
 960     if (!PtrTy) {
 961       Result = Polynomial();
 962       BasePtr = nullptr;
 963       return;
 964     }
 965     unsigned PointerBits =
 966         DL.getIndexSizeInBits(PtrTy->getPointerAddressSpace());
 967
 968     /// Skip pointer casts. Return Zero polynomial otherwise
 969     if (isa<CastInst>(&Ptr)) {
 970       CastInst &CI = *cast<CastInst>(&Ptr);
 971       switch (CI.getOpcode()) {
 972       case Instruction::BitCast:
 973         computePolynomialFromPointer(*CI.getOperand(0), Result, BasePtr, DL);
 974         break;
 975       default:
 976         BasePtr = &Ptr;
 977         Polynomial(PointerBits, 0);
 978         break;
 979       }
 980     }
 981     /// Resolve GetElementPtrInst.
 982     else if (isa<GetElementPtrInst>(&Ptr)) {
 983       GetElementPtrInst &GEP = *cast<GetElementPtrInst>(&Ptr);
 984
 985       APInt BaseOffset(PointerBits, 0);
 986
 987       // Check if we can compute the Offset with accumulateConstantOffset
 988       if (GEP.accumulateConstantOffset(DL, BaseOffset)) {
 989         Result = Polynomial(BaseOffset);
 990         BasePtr = GEP.getPointerOperand();
 991         return;
 992       } else {
 993         // Otherwise we allow that the last index operand of the GEP is
 994         // non-constant.
 995         unsigned idxOperand, e;
 996         SmallVector<Value *, 4> Indices;
 997         for (idxOperand = 1, e = GEP.getNumOperands(); idxOperand < e;
 998              idxOperand++) {
 999           ConstantInt *IDX = dyn_cast<ConstantInt>(GEP.getOperand(idxOperand));
1000           if (!IDX)
1001             break;
1002           Indices.push_back(IDX);
1003         }
1004
1005         // It must also be the last operand.
1006         if (idxOperand + 1 != e) {
1007           Result = Polynomial();
1008           BasePtr = nullptr;
1009           return;
1010         }
1011
1012         // Compute the polynomial of the index operand.
1013         computePolynomial(*GEP.getOperand(idxOperand), Result);
1014
1015         // Compute base offset from zero based index, excluding the last
1016         // variable operand.
1017         BaseOffset =
1018             DL.getIndexedOffsetInType(GEP.getSourceElementType(), Indices);
1019
1020         // Apply the operations of GEP to the polynomial.
1021         unsigned ResultSize = DL.getTypeAllocSize(GEP.getResultElementType());
1022         Result.sextOrTrunc(PointerBits);
1023         Result.mul(APInt(PointerBits, ResultSize));
1024         Result.add(BaseOffset);
1025         BasePtr = GEP.getPointerOperand();
1026       }
1027     }
1028     // All other instructions are handled by using the value as base pointer and
1029     // a zero polynomial.
1030     else {
1031       BasePtr = &Ptr;
1032       Polynomial(DL.getIndexSizeInBits(PtrTy->getPointerAddressSpace()), 0);
1033     }
1034   }
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     unsigned Factor, const DataLayout &DL) {
1055   for (auto C0 = Candidates.begin(), E0 = Candidates.end(); C0 != E0; ++C0) {
1056     unsigned i;
1057     // Try to find an interleaved load using the front of Worklist as first line
1058     unsigned Size = DL.getTypeAllocSize(C0->VTy->getElementType());
1059
1060     // List containing iterators pointing to the VectorInfos of the candidates
1061     std::vector<std::list<VectorInfo>::iterator> Res(Factor, Candidates.end());
1062
1063     for (auto C = Candidates.begin(), E = Candidates.end(); C != E; C++) {
1064       if (C->VTy != C0->VTy)
1065         continue;
1066       if (C->BB != C0->BB)
1067         continue;
1068       if (C->PV != C0->PV)
1069         continue;
1070
1071       // Check the current value matches any of factor - 1 remaining lines
1072       for (i = 1; i < Factor; i++) {
1073         if (C->EI[0].Ofs.isProvenEqualTo(C0->EI[0].Ofs + i * Size)) {
1074           Res[i] = C;
1075         }
1076       }
1077
1078       for (i = 1; i < Factor; i++) {
1079         if (Res[i] == Candidates.end())
1080           break;
1081       }
1082       if (i == Factor) {
1083         Res[0] = C0;
1084         break;
1085       }
1086     }
1087
1088     if (Res[0] != Candidates.end()) {
1089       // Move the result into the output
1090       for (unsigned i = 0; i < Factor; i++) {
1091         InterleavedLoad.splice(InterleavedLoad.end(), Candidates, Res[i]);
1092       }
1093
1094       return true;
1095     }
1096   }
1097   return false;
1098 }
1099
1100 LoadInst *
1101 InterleavedLoadCombineImpl::findFirstLoad(const std::set<LoadInst *> &LIs) {
1102   assert(!LIs.empty() && "No load instructions given.");
1103
1104   // All LIs are within the same BB. Select the first for a reference.
1105   BasicBlock *BB = (*LIs.begin())->getParent();
1106   BasicBlock::iterator FLI =
1107       std::find_if(BB->begin(), BB->end(), [&LIs](Instruction &I) -> bool {
1108         return is_contained(LIs, &I);
1109       });
1110   assert(FLI != BB->end());
1111
1112   return cast<LoadInst>(FLI);
1113 }
1114
1115 bool InterleavedLoadCombineImpl::combine(std::list<VectorInfo> &InterleavedLoad,
1116                                          OptimizationRemarkEmitter &ORE) {
1117   LLVM_DEBUG(dbgs() << "Checking interleaved load\n");
1118
1119   // The insertion point is the LoadInst which loads the first values. The
1120   // following tests are used to proof that the combined load can be inserted
1121   // just before InsertionPoint.
1122   LoadInst *InsertionPoint = InterleavedLoad.front().EI[0].LI;
1123
1124   // Test if the offset is computed
1125   if (!InsertionPoint)
1126     return false;
1127
1128   std::set<LoadInst *> LIs;
1129   std::set<Instruction *> Is;
1130   std::set<Instruction *> SVIs;
1131
1132   unsigned InterleavedCost;
1133   unsigned InstructionCost = 0;
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 +=
1162         TTI.getInstructionCost(I, TargetTransformInfo::TCK_Latency);
1163
1164     // The final SVIs are allowed not to be dead, all uses will be replaced
1165     if (SVIs.find(I) != SVIs.end())
1166       continue;
1167
1168     // If there are users outside the set to be eliminated, we abort the
1169     // transformation. No gain can be expected.
1170     for (const auto &U : I->users()) {
1171       if (Is.find(dyn_cast<Instruction>(U)) == Is.end())
1172         return false;
1173     }
1174   }
1175
1176   // We know that all LoadInst are within the same BB. This guarantees that
1177   // either everything or nothing is loaded.
1178   LoadInst *First = findFirstLoad(LIs);
1179
1180   // To be safe that the loads can be combined, iterate over all loads and test
1181   // that the corresponding defining access dominates first LI. This guarantees
1182   // that there are no aliasing stores in between the loads.
1183   auto FMA = MSSA.getMemoryAccess(First);
1184   for (auto LI : LIs) {
1185     auto MADef = MSSA.getMemoryAccess(LI)->getDefiningAccess();
1186     if (!MSSA.dominates(MADef, FMA))
1187       return false;
1188   }
1189   assert(!LIs.empty() && "There are no LoadInst to combine");
1190
1191   // It is necessary that insertion point dominates all final ShuffleVectorInst.
1192   for (auto &VI : InterleavedLoad) {
1193     if (!DT.dominates(InsertionPoint, VI.SVI))
1194       return false;
1195   }
1196
1197   // All checks are done. Add instructions detectable by InterleavedAccessPass
1198   // The old instruction will are left dead.
1199   IRBuilder<> Builder(InsertionPoint);
1200   Type *ETy = InterleavedLoad.front().SVI->getType()->getElementType();
1201   unsigned ElementsPerSVI =
1202       InterleavedLoad.front().SVI->getType()->getNumElements();
1203   VectorType *ILTy = VectorType::get(ETy, Factor * ElementsPerSVI);
1204
1205   SmallVector<unsigned, 4> Indices;
1206   for (unsigned i = 0; i < Factor; i++)
1207     Indices.push_back(i);
1208   InterleavedCost = TTI.getInterleavedMemoryOpCost(
1209       Instruction::Load, ILTy, Factor, Indices, InsertionPoint->getAlignment(),
1210       InsertionPoint->getPointerAddressSpace());
1211
1212   if (InterleavedCost >= InstructionCost) {
1213     return false;
1214   }
1215
1216   // Create a pointer cast for the wide load.
1217   auto CI = Builder.CreatePointerCast(InsertionPoint->getOperand(0),
1218                                       ILTy->getPointerTo(),
1219                                       "interleaved.wide.ptrcast");
1220
1221   // Create the wide load and update the MemorySSA.
1222   auto LI = Builder.CreateAlignedLoad(ILTy, CI, InsertionPoint->getAlignment(),
1223                                       "interleaved.wide.load");
1224   auto MSSAU = MemorySSAUpdater(&MSSA);
1225   MemoryUse *MSSALoad = cast<MemoryUse>(MSSAU.createMemoryAccessBefore(
1226       LI, nullptr, MSSA.getMemoryAccess(InsertionPoint)));
1227   MSSAU.insertUse(MSSALoad);
1228
1229   // Create the final SVIs and replace all uses.
1230   int i = 0;
1231   for (auto &VI : InterleavedLoad) {
1232     SmallVector<uint32_t, 4> Mask;
1233     for (unsigned j = 0; j < ElementsPerSVI; j++)
1234       Mask.push_back(i + j * Factor);
1235
1236     Builder.SetInsertPoint(VI.SVI);
1237     auto SVI = Builder.CreateShuffleVector(LI, UndefValue::get(LI->getType()),
1238                                            Mask, "interleaved.shuffle");
1239     VI.SVI->replaceAllUsesWith(SVI);
1240     i++;
1241   }
1242
1243   NumInterleavedLoadCombine++;
1244   ORE.emit([&]() {
1245     return OptimizationRemark(DEBUG_TYPE, "Combined Interleaved Load", LI)
1246            << "Load interleaved combined with factor "
1247            << ore::NV("Factor", Factor);
1248   });
1249
1250   return true;
1251 }
1252
1253 bool InterleavedLoadCombineImpl::run() {
1254   OptimizationRemarkEmitter ORE(&F);
1255   bool changed = false;
1256   unsigned MaxFactor = TLI.getMaxSupportedInterleaveFactor();
1257
1258   auto &DL = F.getParent()->getDataLayout();
1259
1260   // Start with the highest factor to avoid combining and recombining.
1261   for (unsigned Factor = MaxFactor; Factor >= 2; Factor--) {
1262     std::list<VectorInfo> Candidates;
1263
1264     for (BasicBlock &BB : F) {
1265       for (Instruction &I : BB) {
1266         if (auto SVI = dyn_cast<ShuffleVectorInst>(&I)) {
1267
1268           Candidates.emplace_back(SVI->getType());
1269
1270           if (!VectorInfo::computeFromSVI(SVI, Candidates.back(), DL)) {
1271             Candidates.pop_back();
1272             continue;
1273           }
1274
1275           if (!Candidates.back().isInterleaved(Factor, DL)) {
1276             Candidates.pop_back();
1277           }
1278         }
1279       }
1280     }
1281
1282     std::list<VectorInfo> InterleavedLoad;
1283     while (findPattern(Candidates, InterleavedLoad, Factor, DL)) {
1284       if (combine(InterleavedLoad, ORE)) {
1285         changed = true;
1286       } else {
1287         // Remove the first element of the Interleaved Load but put the others
1288         // back on the list and continue searching
1289         Candidates.splice(Candidates.begin(), InterleavedLoad,
1290                           std::next(InterleavedLoad.begin()),
1291                           InterleavedLoad.end());
1292       }
1293       InterleavedLoad.clear();
1294     }
1295   }
1296
1297   return changed;
1298 }
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   InterleavedLoadCombine() : FunctionPass(ID) {
1307     initializeInterleavedLoadCombinePass(*PassRegistry::getPassRegistry());
1308   }
1309
1310   StringRef getPassName() const override {
1311     return "Interleaved Load Combine Pass";
1312   }
1313
1314   bool runOnFunction(Function &F) override {
1315     if (DisableInterleavedLoadCombine)
1316       return false;
1317
1318     auto *TPC = getAnalysisIfAvailable<TargetPassConfig>();
1319     if (!TPC)
1320       return false;
1321
1322     LLVM_DEBUG(dbgs() << "*** " << getPassName() << ": " << F.getName()
1323                       << "\n");
1324
1325     return InterleavedLoadCombineImpl(
1326                F, getAnalysis<DominatorTreeWrapperPass>().getDomTree(),
1327                getAnalysis<MemorySSAWrapperPass>().getMSSA(),
1328                TPC->getTM<TargetMachine>())
1329         .run();
1330   }
1331
1332   void getAnalysisUsage(AnalysisUsage &AU) const override {
1333     AU.addRequired<MemorySSAWrapperPass>();
1334     AU.addRequired<DominatorTreeWrapperPass>();
1335     FunctionPass::getAnalysisUsage(AU);
1336   }
1337
1338 private:
1339 };
1340 } // anonymous namespace
1341
1342 char InterleavedLoadCombine::ID = 0;
1343
1344 INITIALIZE_PASS_BEGIN(
1345     InterleavedLoadCombine, DEBUG_TYPE,
1346     "Combine interleaved loads into wide loads and shufflevector instructions",
1347     false, false)
1348 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
1349 INITIALIZE_PASS_DEPENDENCY(MemorySSAWrapperPass)
1350 INITIALIZE_PASS_END(
1351     InterleavedLoadCombine, DEBUG_TYPE,
1352     "Combine interleaved loads into wide loads and shufflevector instructions",
1353     false, false)
1354
1355 FunctionPass *
1356 llvm::createInterleavedLoadCombinePass() {
1357   auto P = new InterleavedLoadCombine();
1358   return P;
1359 }