LLVM  9.0.0svn
InterleavedLoadCombinePass.cpp
Go to the documentation of this file.
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"
27 #include "llvm/CodeGen/Passes.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"
36 #include "llvm/IR/Module.h"
37 #include "llvm/Pass.h"
38 #include "llvm/Support/Debug.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,
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,
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
181 
182  /// Coefficient A
183  APInt A;
184 
185 public:
186  Polynomial(Value *V) : ErrorMSBs((unsigned)-1), V(V), B(), A() {
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) {
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) {
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) {
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] = {
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
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 =
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,
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) {
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() {
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) {
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 {
1336  }
1337 
1338 private:
1339 };
1340 } // anonymous namespace
1341 
1343 
1345  InterleavedLoadCombine, DEBUG_TYPE,
1346  "Combine interleaved loads into wide loads and shufflevector instructions",
1347  false, false)
1351  InterleavedLoadCombine, DEBUG_TYPE,
1352  "Combine interleaved loads into wide loads and shufflevector instructions",
1353  false, false)
1354 
1355 FunctionPass *
1357  auto P = new InterleavedLoadCombine();
1358  return P;
1359 }
uint64_t CallInst * C
A parsed version of the target data layout string in and methods for querying it. ...
Definition: DataLayout.h:110
unsigned getIndexSizeInBits(unsigned AS) const
Size in bits of index used for address calculation in getelementptr.
Definition: DataLayout.h:398
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
uint64_t getZExtValue() const
Get zero extended value.
Definition: APInt.h:1562
GCNRegPressure max(const GCNRegPressure &P1, const GCNRegPressure &P2)
DiagnosticInfoOptimizationBase::Argument NV
APInt operator+(APInt a, const APInt &b)
Definition: APInt.h:2048
This class represents lattice values for constants.
Definition: AllocatorList.h:23
BinaryOps getOpcode() const
Definition: InstrTypes.h:379
bool isAtomic() const
Return true if this instruction has an AtomicOrdering of unordered or higher.
LoadInst * CreateAlignedLoad(Type *Ty, Value *Ptr, unsigned Align, const char *Name)
Provided to resolve &#39;CreateAlignedLoad(Ptr, Align, "...")&#39; correctly, instead of converting the strin...
Definition: IRBuilder.h:1428
virtual const TargetLowering * getTargetLowering() const
This instruction constructs a fixed permutation of two input vectors.
LLVMContext & getContext() const
All values hold a context through their type.
Definition: Value.cpp:709
APInt trunc(unsigned width) const
Truncate to new width.
Definition: APInt.cpp:810
STATISTIC(NumFunctions, "Total number of functions")
F(f)
unsigned getPointerAddressSpace() const
Get the address space of this pointer or pointer vector type.
Definition: DerivedTypes.h:534
An instruction for reading from memory.
Definition: Instructions.h:167
Hexagon Common GEP
unsigned getBitWidth() const
Return the number of bits in the APInt.
Definition: APInt.h:1508
Represents read-only accesses to memory.
Definition: MemorySSA.h:319
unsigned countTrailingZeros() const
Count the number of trailing zero bits.
Definition: APInt.h:1631
AnalysisUsage & addRequired()
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:50
Legacy analysis pass which computes MemorySSA.
Definition: MemorySSA.h:963
bool isVolatile() const
Return true if this is a load from a volatile memory location.
Definition: Instructions.h:231
This is the base class for all instructions that perform data casts.
Definition: InstrTypes.h:416
ArrayRef< T > makeArrayRef(const T &OneElt)
Construct an ArrayRef from a single element.
Definition: ArrayRef.h:450
PointerType * getPointerTo(unsigned AddrSpace=0) const
Return a pointer to the current type.
Definition: Type.cpp:651
Encapsulates MemorySSA, including all data associated with memory accesses.
Definition: MemorySSA.h:703
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Definition: IRBuilder.h:742
uint64_t getNumElements() const
Definition: DerivedTypes.h:390
Type * getSourceElementType() const
Definition: Instructions.h:970
This class defines information used to lower LLVM code to legal SelectionDAG operators that the targe...
virtual void getAnalysisUsage(AnalysisUsage &) const
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
Definition: Pass.cpp:96
Instruction::CastOps getOpcode() const
Return the opcode of this CastInst.
Definition: InstrTypes.h:669
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:244
FunctionPass * createInterleavedLoadCombinePass()
InterleavedLoadCombines Pass - This pass identifies interleaved loads and combines them into wide loa...
This class represents a no-op cast from one type to another.
const APInt & getValue() const
Return the constant as an APInt value reference.
Definition: Constants.h:137
unsigned getBitWidth() const
Get the number of bits in this IntegerType.
Definition: DerivedTypes.h:65
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:144
void SetInsertPoint(BasicBlock *TheBB)
This specifies that created instructions should be appended to the end of the specified block...
Definition: IRBuilder.h:126
virtual TargetTransformInfo getTargetTransformInfo(const Function &F)
Return a TargetTransformInfo for a given function.
Value * getOperand(unsigned i) const
Definition: User.h:169
Class to represent pointers.
Definition: DerivedTypes.h:498
an instruction for type-safe pointer arithmetic to access elements of arrays and structs ...
Definition: Instructions.h:873
static bool runOnFunction(Function &F, bool PostInlining)
#define P(N)
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:432
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
#define DEBUG_TYPE
LLVM Basic Block Representation.
Definition: BasicBlock.h:57
The instances of the Type class are immutable: once they are created, they are never changed...
Definition: Type.h:45
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
bool isOneValue() const
Determine if this is a value of 1.
Definition: APInt.h:410
Diagnostic information for applied optimization remarks.
Represent the analysis usage information of a pass.
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:284
Value * getPointerOperand()
Definition: Instructions.h:284
static void print(raw_ostream &Out, object::Archive::Kind Kind, T Val)
Class to represent integer types.
Definition: DerivedTypes.h:39
auto find_if(R &&Range, UnaryPredicate P) -> decltype(adl_begin(Range))
Provide wrappers to std::find_if which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1213
static UndefValue * get(Type *T)
Static factory methods - Return an &#39;undef&#39; object of the specified type.
Definition: Constants.cpp:1424
size_t size() const
Definition: SmallVector.h:52
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Iterator for intrusive lists based on ilist_node.
unsigned getNumOperands() const
Definition: User.h:191
This is the shared class of boolean and integer constants.
Definition: Constants.h:83
void emit(DiagnosticInfoOptimizationBase &OptDiag)
Output the remark via the diagnostic handler and to the optimization record file. ...
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
static uint64_t add(uint64_t LeftOp, uint64_t RightOp)
Definition: FileCheck.cpp:124
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:841
Module.h This file contains the declarations for the Module class.
static void getShuffleMask(const Constant *Mask, SmallVectorImpl< int > &Result)
Convert the input shuffle mask operand to a vector of integers.
Value * CreateShuffleVector(Value *V1, Value *V2, Value *Mask, const Twine &Name="")
Definition: IRBuilder.h:2104
static Constant * get(Type *Ty, uint64_t V, bool isSigned=false)
If Ty is a vector type, return a Constant with a splat of the given value.
Definition: Constants.cpp:631
bool isCommutative() const
Return true if the instruction is commutative:
Definition: Instruction.h:488
virtual const TargetSubtargetInfo * getSubtargetImpl(const Function &) const
Virtual method implemented by subclasses that returns a reference to that target&#39;s TargetSubtargetInf...
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:940
Class to represent vector types.
Definition: DerivedTypes.h:424
void initializeInterleavedLoadCombinePass(PassRegistry &)
Class for arbitrary precision integers.
Definition: APInt.h:69
Value * CreatePointerCast(Value *V, Type *DestTy, const Twine &Name="")
Definition: IRBuilder.h:1813
uint64_t getTypeAllocSize(Type *Ty) const
Returns the offset in bytes between successive objects of the specified type, including alignment pad...
Definition: DataLayout.h:461
unsigned getAlignment() const
Return the alignment of the access that is being performed.
Definition: Instructions.h:240
static IntegerType * getInt32Ty(LLVMContext &C)
Definition: Type.cpp:175
bool accumulateConstantOffset(const DataLayout &DL, APInt &Offset) const
Accumulate the constant address offset of this GEP if possible.
This file provides utility analysis objects describing memory locations.
StringRef getName() const
Return a constant reference to the value&#39;s name.
Definition: Value.cpp:214
#define I(x, y, z)
Definition: MD5.cpp:58
Type * getResultElementType() const
Definition: Instructions.h:975
APInt operator-(APInt)
Definition: APInt.h:2043
LLVM_NODISCARD std::enable_if<!is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type >::type dyn_cast(const Y &Val)
Definition: Casting.h:332
uint32_t Size
Definition: Profile.cpp:46
raw_ostream & operator<<(raw_ostream &OS, const APInt &I)
Definition: APInt.h:2038
unsigned getPointerAddressSpace() const
Returns the address space of the pointer operand.
Definition: Instructions.h:290
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
INITIALIZE_PASS_BEGIN(InterleavedLoadCombine, DEBUG_TYPE, "Combine interleaved loads into wide loads and shufflevector instructions", false, false) INITIALIZE_PASS_END(InterleavedLoadCombine
LLVM Value Representation.
Definition: Value.h:72
FMA - Perform a * b + c with no intermediate rounding step.
Definition: ISDOpcodes.h:321
static VectorType * get(Type *ElementType, unsigned NumElements)
This static method is the primary way to construct an VectorType.
Definition: Type.cpp:605
std::underlying_type< E >::type Mask()
Get a bitmask with 1s in all places up to the high-order bit of E&#39;s largest value.
Definition: BitmaskEnum.h:80
static const Function * getParent(const Value *V)
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:45
Primary interface to the complete machine description for the target machine.
Definition: TargetMachine.h:65
This file exposes an interface to building/using memory SSA to walk memory instructions using a use/d...
Type * getElementType() const
Definition: DerivedTypes.h:391
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:48
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:259
This pass exposes codegen information to IR-level passes.
#define LLVM_DEBUG(X)
Definition: Debug.h:122
The optimization diagnostic interface.
int64_t getIndexedOffsetInType(Type *ElemTy, ArrayRef< Value *> Indices) const
Returns the offset from the beginning of the type for the specified indices.
Definition: DataLayout.cpp:806
bool isNullValue() const
Determine if all bits are clear.
Definition: APInt.h:405
This file describes how to lower LLVM code to machine code.
const BasicBlock * getParent() const
Definition: Instruction.h:66
bool is_contained(R &&Range, const E &Element)
Wrapper function around std::find to detect if an element exists in a container.
Definition: STLExtras.h:1244