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