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/ArrayRef.h"
22#include "llvm/ADT/Hashing.h"
23#include "llvm/ADT/STLExtras.h"
24#include "llvm/ADT/SmallPtrSet.h"
25#include "llvm/ADT/Statistic.h"
26#include "llvm/Analysis/MemorySSA.h"
27#include "llvm/Analysis/MemorySSAUpdater.h"
28#include "llvm/Analysis/OptimizationRemarkEmitter.h"
29#include "llvm/Analysis/TargetTransformInfo.h"
30#include "llvm/Analysis/ValueTracking.h"
31#include "llvm/CodeGen/InterleavedLoadCombine.h"
32#include "llvm/CodeGen/Passes.h"
33#include "llvm/CodeGen/TargetLowering.h"
34#include "llvm/CodeGen/TargetPassConfig.h"
35#include "llvm/CodeGen/TargetSubtargetInfo.h"
36#include "llvm/IR/DataLayout.h"
37#include "llvm/IR/Dominators.h"
38#include "llvm/IR/Function.h"
39#include "llvm/IR/IRBuilder.h"
40#include "llvm/IR/Instructions.h"
41#include "llvm/InitializePasses.h"
42#include "llvm/Pass.h"
43#include "llvm/Support/Debug.h"
44#include "llvm/Support/ErrorHandling.h"
45#include "llvm/Support/raw_ostream.h"
46#include "llvm/Target/TargetMachine.h"
47
48#include <algorithm>
49#include <cassert>
50#include <list>
51#include <unordered_map>
52
53using namespace llvm;
54
55#define DEBUG_TYPE "interleaved-load-combine"
56
57namespace {
58
59/// Statistic counter
60STATISTIC(NumInterleavedLoadCombine, "Number of combined loads");
61
62/// Option to disable the pass
63static cl::opt<bool> DisableInterleavedLoadCombine(
64 "disable-" DEBUG_TYPE, cl::init(Val: false), cl::Hidden,
65 cl::desc("Disable combining of interleaved loads"));
66
67struct VectorInfo;
68
69struct InterleavedLoadCombineImpl {
70public:
71 InterleavedLoadCombineImpl(Function &F, DominatorTree &DT, MemorySSA &MSSA,
72 const TargetTransformInfo &TTI,
73 const TargetMachine &TM)
74 : F(F), DT(DT), MSSA(MSSA),
75 TLI(*TM.getSubtargetImpl(F)->getTargetLowering()), TTI(TTI) {}
76
77 /// Scan the function for interleaved load candidates and execute the
78 /// replacement if applicable.
79 bool run();
80
81private:
82 /// Function this pass is working on
83 Function &F;
84
85 /// Dominator Tree Analysis
86 DominatorTree &DT;
87
88 /// Memory Alias Analyses
89 MemorySSA &MSSA;
90
91 /// Target Lowering Information
92 const TargetLowering &TLI;
93
94 /// Target Transform Information
95 const TargetTransformInfo &TTI;
96
97 /// Find the instruction in sets LIs that dominates all others, return nullptr
98 /// if there is none.
99 LoadInst *findFirstLoad(const std::set<LoadInst *> &LIs);
100
101 /// Replace interleaved load candidates. It does additional
102 /// analyses if this makes sense. Returns true on success and false
103 /// of nothing has been changed.
104 bool combine(ArrayRef<VectorInfo *> InterleavedLoad,
105 OptimizationRemarkEmitter &ORE);
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//
164class 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 = (unsigned)-1;
175
176 /// Value
177 Value *V = nullptr;
178
179 /// Coefficient B
180 SmallVector<std::pair<BOps, APInt>, 4> B;
181
182 /// Coefficient A
183 APInt A;
184
185public:
186 Polynomial(Value *V) : V(V) {
187 IntegerType *Ty = dyn_cast<IntegerType>(Val: V->getType());
188 if (Ty) {
189 ErrorMSBs = 0;
190 this->V = V;
191 A = APInt(Ty->getBitWidth(), 0);
192 }
193 }
194
195 Polynomial(const APInt &A, unsigned ErrorMSBs = 0)
196 : ErrorMSBs(ErrorMSBs), A(A) {}
197
198 Polynomial(unsigned BitWidth, uint64_t A, unsigned ErrorMSBs = 0)
199 : ErrorMSBs(ErrorMSBs), A(BitWidth, A) {}
200
201 Polynomial() = default;
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.isOne()) {
310 return *this;
311 }
312
313 // Multiplying by zero removes the coefficient B and defines all bits.
314 if (C.isZero()) {
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(amt: C.countr_zero());
322
323 A *= C;
324 pushBOperation(Op: 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.isZero())
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(C: 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.countr_zero() < shiftAmt)
479 ErrorMSBs = A.getBitWidth();
480 else
481 incErrorMSBs(amt: shiftAmt);
482
483 // Apply the operation.
484 pushBOperation(Op: 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(amt: A.getBitWidth() - n);
496 A = A.trunc(width: n);
497 pushBOperation(Op: Trunc, C: 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(amt: n - A.getBitWidth());
503 A = A.sext(width: n);
504 pushBOperation(Op: SExt, C: 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 (const 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(a: ErrorMSBs, b: 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) const {
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.isZero());
573 }
574
575 /// Returns true if every bit of the polynomial is provably exact. An inexact
576 /// polynomial can never be proven equal to another, so it is never a valid
577 /// match candidate.
578 bool isProvenExact() const { return ErrorMSBs == 0; }
579
580 /// Hash the identity checked by isProvenEqualTo. Only meaningful for exact
581 /// polynomials; two exact, proven-equal polynomials hash identically.
582 friend hash_code hash_value(const Polynomial &P) {
583 hash_code H = hash_combine(args: P.A.getBitWidth(), args: P.V);
584 for (const auto &BO : P.B)
585 H = hash_combine(args: H, args: BO.first, args: hash_value(Arg: BO.second));
586 return hash_combine(args: H, args: hash_value(Arg: P.A));
587 }
588
589 /// Print the polynomial into a stream.
590 void print(raw_ostream &OS) const {
591 OS << "[{#ErrBits:" << ErrorMSBs << "} ";
592
593 if (V) {
594 for (auto b : B)
595 OS << "(";
596 OS << "(" << *V << ") ";
597
598 for (auto b : B) {
599 switch (b.first) {
600 case LShr:
601 OS << "LShr ";
602 break;
603 case Mul:
604 OS << "Mul ";
605 break;
606 case SExt:
607 OS << "SExt ";
608 break;
609 case Trunc:
610 OS << "Trunc ";
611 break;
612 }
613
614 OS << b.second << ") ";
615 }
616 }
617
618 OS << "+ " << A << "]";
619 }
620
621private:
622 void deleteB() {
623 V = nullptr;
624 B.clear();
625 }
626
627 void pushBOperation(const BOps Op, const APInt &C) {
628 if (isFirstOrder()) {
629 B.push_back(Elt: std::make_pair(x: Op, y: C));
630 return;
631 }
632 }
633};
634
635#ifndef NDEBUG
636static raw_ostream &operator<<(raw_ostream &OS, const Polynomial &S) {
637 S.print(OS);
638 return OS;
639}
640#endif
641
642/// Address key of a candidate's first vector element: the common base pointer,
643/// the vector type and the offset polynomial. Candidates are collected and
644/// matched one basic block at a time and only candidates whose loads live in
645/// that block take part (see run()), so the block is common to a whole index
646/// and need not be part of the key. Two candidates belong to the same
647/// interleaved group iff their keys agree on everything but the constant
648/// offset, so consecutive elements are located by building the neighbouring
649/// keys and looking them up.
650struct OffsetKey {
651 Value *PV;
652 FixedVectorType *VTy;
653 Polynomial Ofs;
654
655 bool operator==(const OffsetKey &O) const {
656 return PV == O.PV && VTy == O.VTy && Ofs.isProvenEqualTo(o: O.Ofs);
657 }
658};
659
660struct OffsetKeyHash {
661 size_t operator()(const OffsetKey &K) const {
662 return hash_combine(args: K.PV, args: K.VTy, args: hash_value(P: K.Ofs));
663 }
664};
665
666/// VectorInfo stores abstract the following information for each vector
667/// element:
668///
669/// 1) The memory address loaded into the element as Polynomial
670/// 2) a set of load instruction necessary to construct the vector,
671/// 3) a set of all other instructions that are necessary to create the vector and
672/// 4) a pointer value that can be used as relative base for all elements.
673struct VectorInfo {
674private:
675 VectorInfo(const VectorInfo &c) : VTy(c.VTy) {
676 llvm_unreachable(
677 "Copying VectorInfo is neither implemented nor necessary,");
678 }
679
680public:
681 /// Information of a Vector Element
682 struct ElementInfo {
683 /// Offset Polynomial.
684 Polynomial Ofs;
685
686 /// The Load Instruction used to Load the entry. LI is null if the pointer
687 /// of the load instruction does not point on to the entry
688 LoadInst *LI;
689
690 ElementInfo(Polynomial Offset = Polynomial(), LoadInst *LI = nullptr)
691 : Ofs(Offset), LI(LI) {}
692 };
693
694 /// Basic-block the load instructions are within
695 BasicBlock *BB = nullptr;
696
697 /// Pointer value of all participation load instructions
698 Value *PV = nullptr;
699
700 /// Participating load instructions
701 std::set<LoadInst *> LIs;
702
703 /// Participating instructions
704 std::set<Instruction *> Is;
705
706 /// Final shuffle-vector instruction
707 ShuffleVectorInst *SVI = nullptr;
708
709 /// Information of the offset for each vector element
710 ElementInfo *EI;
711
712 /// Vector Type
713 FixedVectorType *const VTy;
714
715 VectorInfo(FixedVectorType *VTy) : VTy(VTy) {
716 EI = new ElementInfo[VTy->getNumElements()];
717 }
718
719 VectorInfo &operator=(const VectorInfo &other) = delete;
720
721 virtual ~VectorInfo() { delete[] EI; }
722
723 unsigned getDimension() const { return VTy->getNumElements(); }
724
725 /// Test if the VectorInfo can be part of an interleaved load with the
726 /// specified factor.
727 ///
728 /// \param Factor of the interleave
729 /// \param DL Targets Datalayout
730 ///
731 /// \returns true if this is possible and false if not
732 bool isInterleaved(unsigned Factor, const DataLayout &DL) const {
733 unsigned Size = DL.getTypeAllocSize(Ty: VTy->getElementType());
734 for (unsigned i = 1; i < getDimension(); i++) {
735 if (!EI[i].Ofs.isProvenEqualTo(o: EI[0].Ofs + i * Factor * Size)) {
736 return false;
737 }
738 }
739 return true;
740 }
741
742 /// Recursively computes the vector information stored in V.
743 ///
744 /// This function delegates the work to specialized implementations
745 ///
746 /// \param V Value to operate on
747 /// \param Result Result of the computation
748 ///
749 /// \returns false if no sensible information can be gathered.
750 static bool compute(Value *V, VectorInfo &Result, const DataLayout &DL) {
751 ShuffleVectorInst *SVI = dyn_cast<ShuffleVectorInst>(Val: V);
752 if (SVI)
753 return computeFromSVI(SVI, Result, DL);
754 LoadInst *LI = dyn_cast<LoadInst>(Val: V);
755 if (LI)
756 return computeFromLI(LI, Result, DL);
757 BitCastInst *BCI = dyn_cast<BitCastInst>(Val: V);
758 if (BCI)
759 return computeFromBCI(BCI, Result, DL);
760 return false;
761 }
762
763 /// BitCastInst specialization to compute the vector information.
764 ///
765 /// \param BCI BitCastInst to operate on
766 /// \param Result Result of the computation
767 ///
768 /// \returns false if no sensible information can be gathered.
769 static bool computeFromBCI(BitCastInst *BCI, VectorInfo &Result,
770 const DataLayout &DL) {
771 Instruction *Op = dyn_cast<Instruction>(Val: BCI->getOperand(i_nocapture: 0));
772
773 if (!Op)
774 return false;
775
776 FixedVectorType *VTy = dyn_cast<FixedVectorType>(Val: Op->getType());
777 if (!VTy)
778 return false;
779
780 // We can only cast from large to smaller vectors
781 if (Result.VTy->getNumElements() % VTy->getNumElements())
782 return false;
783
784 unsigned Factor = Result.VTy->getNumElements() / VTy->getNumElements();
785 unsigned NewSize = DL.getTypeAllocSize(Ty: Result.VTy->getElementType());
786 unsigned OldSize = DL.getTypeAllocSize(Ty: VTy->getElementType());
787
788 if (NewSize * Factor != OldSize)
789 return false;
790
791 VectorInfo Old(VTy);
792 if (!compute(V: Op, Result&: Old, DL))
793 return false;
794
795 for (unsigned i = 0; i < Result.VTy->getNumElements(); i += Factor) {
796 for (unsigned j = 0; j < Factor; j++) {
797 Result.EI[i + j] =
798 ElementInfo(Old.EI[i / Factor].Ofs + j * NewSize,
799 j == 0 ? Old.EI[i / Factor].LI : nullptr);
800 }
801 }
802
803 Result.BB = Old.BB;
804 Result.PV = Old.PV;
805 Result.LIs.insert(first: Old.LIs.begin(), last: Old.LIs.end());
806 Result.Is.insert(first: Old.Is.begin(), last: Old.Is.end());
807 Result.Is.insert(x: BCI);
808 Result.SVI = nullptr;
809
810 return true;
811 }
812
813 /// ShuffleVectorInst specialization to compute vector information.
814 ///
815 /// \param SVI ShuffleVectorInst to operate on
816 /// \param Result Result of the computation
817 ///
818 /// Compute the left and the right side vector information and merge them by
819 /// applying the shuffle operation. This function also ensures that the left
820 /// and right side have compatible loads. This means that all loads are with
821 /// in the same basic block and are based on the same pointer.
822 ///
823 /// \returns false if no sensible information can be gathered.
824 static bool computeFromSVI(ShuffleVectorInst *SVI, VectorInfo &Result,
825 const DataLayout &DL) {
826 FixedVectorType *ArgTy =
827 cast<FixedVectorType>(Val: SVI->getOperand(i_nocapture: 0)->getType());
828
829 // Compute the left hand vector information.
830 VectorInfo LHS(ArgTy);
831 if (!compute(V: SVI->getOperand(i_nocapture: 0), Result&: LHS, DL))
832 LHS.BB = nullptr;
833
834 // Compute the right hand vector information.
835 VectorInfo RHS(ArgTy);
836 if (!compute(V: SVI->getOperand(i_nocapture: 1), Result&: RHS, DL))
837 RHS.BB = nullptr;
838
839 // Neither operand produced sensible results?
840 if (!LHS.BB && !RHS.BB)
841 return false;
842 // Only RHS produced sensible results?
843 else if (!LHS.BB) {
844 Result.BB = RHS.BB;
845 Result.PV = RHS.PV;
846 }
847 // Only LHS produced sensible results?
848 else if (!RHS.BB) {
849 Result.BB = LHS.BB;
850 Result.PV = LHS.PV;
851 }
852 // Both operands produced sensible results?
853 else if ((LHS.BB == RHS.BB) && (LHS.PV == RHS.PV)) {
854 Result.BB = LHS.BB;
855 Result.PV = LHS.PV;
856 }
857 // Both operands produced sensible results but they are incompatible.
858 else {
859 return false;
860 }
861
862 // Merge and apply the operation on the offset information.
863 if (LHS.BB) {
864 Result.LIs.insert(first: LHS.LIs.begin(), last: LHS.LIs.end());
865 Result.Is.insert(first: LHS.Is.begin(), last: LHS.Is.end());
866 }
867 if (RHS.BB) {
868 Result.LIs.insert(first: RHS.LIs.begin(), last: RHS.LIs.end());
869 Result.Is.insert(first: RHS.Is.begin(), last: RHS.Is.end());
870 }
871 Result.Is.insert(x: SVI);
872 Result.SVI = SVI;
873
874 int j = 0;
875 for (int i : SVI->getShuffleMask()) {
876 assert((i < 2 * (signed)ArgTy->getNumElements()) &&
877 "Invalid ShuffleVectorInst (index out of bounds)");
878
879 if (i < 0)
880 Result.EI[j] = ElementInfo();
881 else if (i < (signed)ArgTy->getNumElements()) {
882 if (LHS.BB)
883 Result.EI[j] = LHS.EI[i];
884 else
885 Result.EI[j] = ElementInfo();
886 } else {
887 if (RHS.BB)
888 Result.EI[j] = RHS.EI[i - ArgTy->getNumElements()];
889 else
890 Result.EI[j] = ElementInfo();
891 }
892 j++;
893 }
894
895 return true;
896 }
897
898 /// LoadInst specialization to compute vector information.
899 ///
900 /// This function also acts as abort condition to the recursion.
901 ///
902 /// \param LI LoadInst to operate on
903 /// \param Result Result of the computation
904 ///
905 /// \returns false if no sensible information can be gathered.
906 static bool computeFromLI(LoadInst *LI, VectorInfo &Result,
907 const DataLayout &DL) {
908 Value *BasePtr;
909 Polynomial Offset;
910
911 if (LI->isVolatile())
912 return false;
913
914 if (LI->isAtomic())
915 return false;
916
917 if (!DL.typeSizeEqualsStoreSize(Ty: Result.VTy->getElementType()))
918 return false;
919
920 // Get the base polynomial
921 computePolynomialFromPointer(Ptr&: *LI->getPointerOperand(), Result&: Offset, BasePtr, DL);
922
923 Result.BB = LI->getParent();
924 Result.PV = BasePtr;
925 Result.LIs.insert(x: LI);
926 Result.Is.insert(x: LI);
927
928 for (unsigned i = 0; i < Result.getDimension(); i++) {
929 Value *Idx[2] = {
930 ConstantInt::get(Ty: Type::getInt32Ty(C&: LI->getContext()), V: 0),
931 ConstantInt::get(Ty: Type::getInt32Ty(C&: LI->getContext()), V: i),
932 };
933 int64_t Ofs = DL.getIndexedOffsetInType(ElemTy: Result.VTy, Indices: Idx);
934 Result.EI[i] = ElementInfo(Offset + Ofs, i == 0 ? LI : nullptr);
935 }
936
937 return true;
938 }
939
940 /// Recursively compute polynomial of a value.
941 ///
942 /// \param BO Input binary operation
943 /// \param Result Result polynomial
944 static void computePolynomialBinOp(BinaryOperator &BO, Polynomial &Result) {
945 Value *LHS = BO.getOperand(i_nocapture: 0);
946 Value *RHS = BO.getOperand(i_nocapture: 1);
947
948 // Find the RHS Constant if any
949 ConstantInt *C = dyn_cast<ConstantInt>(Val: RHS);
950 if ((!C) && BO.isCommutative()) {
951 C = dyn_cast<ConstantInt>(Val: LHS);
952 if (C)
953 std::swap(a&: LHS, b&: RHS);
954 }
955
956 switch (BO.getOpcode()) {
957 case Instruction::Add:
958 if (!C)
959 break;
960
961 computePolynomial(V&: *LHS, Result);
962 Result.add(C: C->getValue());
963 return;
964
965 case Instruction::LShr:
966 if (!C)
967 break;
968
969 computePolynomial(V&: *LHS, Result);
970 Result.lshr(C: C->getValue());
971 return;
972
973 default:
974 break;
975 }
976
977 Result = Polynomial(&BO);
978 }
979
980 /// Recursively compute polynomial of a value
981 ///
982 /// \param V input value
983 /// \param Result result polynomial
984 static void computePolynomial(Value &V, Polynomial &Result) {
985 if (auto *BO = dyn_cast<BinaryOperator>(Val: &V))
986 computePolynomialBinOp(BO&: *BO, Result);
987 else
988 Result = Polynomial(&V);
989 }
990
991 /// Compute the Polynomial representation of a Pointer type.
992 ///
993 /// \param Ptr input pointer value
994 /// \param Result result polynomial
995 /// \param BasePtr pointer the polynomial is based on
996 /// \param DL Datalayout of the target machine
997 static void computePolynomialFromPointer(Value &Ptr, Polynomial &Result,
998 Value *&BasePtr,
999 const DataLayout &DL) {
1000 // Not a pointer type? Return an undefined polynomial
1001 PointerType *PtrTy = dyn_cast<PointerType>(Val: Ptr.getType());
1002 if (!PtrTy) {
1003 Result = Polynomial();
1004 BasePtr = nullptr;
1005 return;
1006 }
1007 unsigned PointerBits =
1008 DL.getIndexSizeInBits(AS: PtrTy->getPointerAddressSpace());
1009
1010 /// Skip pointer casts. Return Zero polynomial otherwise
1011 if (isa<CastInst>(Val: &Ptr)) {
1012 CastInst &CI = *cast<CastInst>(Val: &Ptr);
1013 switch (CI.getOpcode()) {
1014 case Instruction::BitCast:
1015 computePolynomialFromPointer(Ptr&: *CI.getOperand(i_nocapture: 0), Result, BasePtr, DL);
1016 break;
1017 default:
1018 BasePtr = &Ptr;
1019 Polynomial(PointerBits, 0);
1020 break;
1021 }
1022 }
1023 /// Resolve GetElementPtrInst.
1024 else if (isa<GetElementPtrInst>(Val: &Ptr)) {
1025 GetElementPtrInst &GEP = *cast<GetElementPtrInst>(Val: &Ptr);
1026
1027 APInt BaseOffset(PointerBits, 0);
1028
1029 // Check if we can compute the Offset with accumulateConstantOffset
1030 if (GEP.accumulateConstantOffset(DL, Offset&: BaseOffset)) {
1031 Result = Polynomial(BaseOffset);
1032 BasePtr = GEP.getPointerOperand();
1033 return;
1034 } else {
1035 // Otherwise we allow that the last index operand of the GEP is
1036 // non-constant.
1037 unsigned idxOperand, e;
1038 SmallVector<Value *, 4> Indices;
1039 for (idxOperand = 1, e = GEP.getNumOperands(); idxOperand < e;
1040 idxOperand++) {
1041 ConstantInt *IDX = dyn_cast<ConstantInt>(Val: GEP.getOperand(i_nocapture: idxOperand));
1042 if (!IDX)
1043 break;
1044 Indices.push_back(Elt: IDX);
1045 }
1046
1047 // It must also be the last operand.
1048 if (idxOperand + 1 != e) {
1049 Result = Polynomial();
1050 BasePtr = nullptr;
1051 return;
1052 }
1053
1054 // Compute the polynomial of the index operand.
1055 computePolynomial(V&: *GEP.getOperand(i_nocapture: idxOperand), Result);
1056
1057 // Compute base offset from zero based index, excluding the last
1058 // variable operand.
1059 BaseOffset =
1060 DL.getIndexedOffsetInType(ElemTy: GEP.getSourceElementType(), Indices);
1061
1062 // Apply the operations of GEP to the polynomial.
1063 unsigned ResultSize = DL.getTypeAllocSize(Ty: GEP.getResultElementType());
1064 Result.sextOrTrunc(n: PointerBits);
1065 Result.mul(C: APInt(PointerBits, ResultSize));
1066 Result.add(C: BaseOffset);
1067 BasePtr = GEP.getPointerOperand();
1068 }
1069 }
1070 // All other instructions are handled by using the value as base pointer and
1071 // a zero polynomial.
1072 else {
1073 BasePtr = &Ptr;
1074 Polynomial(DL.getIndexSizeInBits(AS: PtrTy->getPointerAddressSpace()), 0);
1075 }
1076 }
1077
1078#ifndef NDEBUG
1079 void print(raw_ostream &OS) const {
1080 if (PV)
1081 OS << *PV;
1082 else
1083 OS << "(none)";
1084 OS << " + ";
1085 for (unsigned i = 0; i < getDimension(); i++)
1086 OS << ((i == 0) ? "[" : ", ") << EI[i].Ofs;
1087 OS << "]";
1088 }
1089#endif
1090};
1091
1092} // anonymous namespace
1093
1094LoadInst *
1095InterleavedLoadCombineImpl::findFirstLoad(const std::set<LoadInst *> &LIs) {
1096 assert(!LIs.empty() && "No load instructions given.");
1097
1098 // All LIs are within the same BB. Select the first for a reference.
1099 BasicBlock *BB = (*LIs.begin())->getParent();
1100 BasicBlock::iterator FLI = llvm::find_if(
1101 Range&: *BB, P: [&LIs](Instruction &I) -> bool { return is_contained(Range: LIs, Element: &I); });
1102 assert(FLI != BB->end());
1103
1104 return cast<LoadInst>(Val&: FLI);
1105}
1106
1107bool InterleavedLoadCombineImpl::combine(ArrayRef<VectorInfo *> InterleavedLoad,
1108 OptimizationRemarkEmitter &ORE) {
1109 LLVM_DEBUG(dbgs() << "Checking interleaved load\n");
1110
1111 // The insertion point is the LoadInst which loads the first values. The
1112 // following tests are used to proof that the combined load can be inserted
1113 // just before InsertionPoint.
1114 LoadInst *InsertionPoint = InterleavedLoad.front()->EI[0].LI;
1115
1116 // Test if the offset is computed
1117 if (!InsertionPoint)
1118 return false;
1119
1120 std::set<LoadInst *> LIs;
1121 std::set<Instruction *> Is;
1122 std::set<Instruction *> SVIs;
1123
1124 InstructionCost InterleavedCost;
1125 InstructionCost InstructionCost = 0;
1126 const TTI::TargetCostKind CostKind = TTI::TCK_SizeAndLatency;
1127
1128 // Get the interleave factor
1129 unsigned Factor = InterleavedLoad.size();
1130
1131 // Merge all input sets used in analysis
1132 for (const VectorInfo *VI : InterleavedLoad) {
1133 // Generate a set of all load instructions to be combined
1134 LIs.insert(first: VI->LIs.begin(), last: VI->LIs.end());
1135
1136 // Generate a set of all instructions taking part in load
1137 // interleaved. This list excludes the instructions necessary for the
1138 // polynomial construction.
1139 Is.insert(first: VI->Is.begin(), last: VI->Is.end());
1140
1141 // Generate the set of the final ShuffleVectorInst.
1142 SVIs.insert(x: VI->SVI);
1143 }
1144
1145 // There is nothing to combine.
1146 if (LIs.size() < 2)
1147 return false;
1148
1149 // Test if all participating instruction will be dead after the
1150 // transformation. If intermediate results are used, no performance gain can
1151 // be expected. Also sum the cost of the Instructions beeing left dead.
1152 for (const auto &I : Is) {
1153 // Compute the old cost
1154 InstructionCost += TTI.getInstructionCost(U: I, CostKind);
1155
1156 // The final SVIs are allowed not to be dead, all uses will be replaced
1157 if (SVIs.find(x: I) != SVIs.end())
1158 continue;
1159
1160 // If there are users outside the set to be eliminated, we abort the
1161 // transformation. No gain can be expected.
1162 for (auto *U : I->users()) {
1163 if (Is.find(x: dyn_cast<Instruction>(Val: U)) == Is.end())
1164 return false;
1165 }
1166 }
1167
1168 // We need to have a valid cost in order to proceed.
1169 if (!InstructionCost.isValid())
1170 return false;
1171
1172 // We know that all LoadInst are within the same BB. This guarantees that
1173 // either everything or nothing is loaded.
1174 LoadInst *First = findFirstLoad(LIs);
1175
1176 // To be safe that the loads can be combined, iterate over all loads and test
1177 // that the corresponding defining access dominates first LI. This guarantees
1178 // that there are no aliasing stores in between the loads.
1179 auto FMA = MSSA.getMemoryAccess(I: First);
1180 for (auto *LI : LIs) {
1181 auto MADef = MSSA.getMemoryAccess(I: LI)->getDefiningAccess();
1182 if (!MSSA.dominates(A: MADef, B: FMA))
1183 return false;
1184 }
1185 assert(!LIs.empty() && "There are no LoadInst to combine");
1186
1187 // The wide load reads the whole span at once and is inserted at the first
1188 // load, so widening must not pull a later load across an instruction that may
1189 // not transfer control to its successor (e.g. a call that might not return or
1190 // might throw). Otherwise a load the original program reached only
1191 // conditionally would run unconditionally. All combined loads are in one
1192 // block, so check the span from the first to the last is barrier-free.
1193 LoadInst *Last = First;
1194 for (auto *LI : LIs)
1195 if (Last->comesBefore(Other: LI))
1196 Last = LI;
1197 if (!isGuaranteedToTransferExecutionToSuccessor(Begin: First->getIterator(),
1198 End: Last->getIterator()))
1199 return false;
1200
1201 // It is necessary that insertion point dominates all final ShuffleVectorInst.
1202 for (const VectorInfo *VI : InterleavedLoad) {
1203 if (!DT.dominates(Def: InsertionPoint, User: VI->SVI))
1204 return false;
1205 }
1206
1207 // All checks are done. Add instructions detectable by InterleavedAccessPass
1208 // The old instruction will are left dead.
1209 IRBuilder<> Builder(InsertionPoint);
1210 Type *ETy = InterleavedLoad.front()->SVI->getType()->getElementType();
1211 unsigned ElementsPerSVI =
1212 cast<FixedVectorType>(Val: InterleavedLoad.front()->SVI->getType())
1213 ->getNumElements();
1214 FixedVectorType *ILTy = FixedVectorType::get(ElementType: ETy, NumElts: Factor * ElementsPerSVI);
1215
1216 auto Indices = llvm::to_vector<4>(Range: llvm::seq<unsigned>(Begin: 0, End: Factor));
1217 InterleavedCost = TTI.getInterleavedMemoryOpCost(
1218 Opcode: Instruction::Load, VecTy: ILTy, Factor, Indices, Alignment: InsertionPoint->getAlign(),
1219 AddressSpace: InsertionPoint->getPointerAddressSpace(), CostKind);
1220
1221 if (InterleavedCost >= InstructionCost) {
1222 return false;
1223 }
1224
1225 // Create the wide load and update the MemorySSA.
1226 auto Ptr = InsertionPoint->getPointerOperand();
1227 auto LI = Builder.CreateAlignedLoad(Ty: ILTy, Ptr, Align: InsertionPoint->getAlign(),
1228 Name: "interleaved.wide.load");
1229 auto MSSAU = MemorySSAUpdater(&MSSA);
1230 MemoryUse *MSSALoad = cast<MemoryUse>(Val: MSSAU.createMemoryAccessBefore(
1231 I: LI, Definition: nullptr, InsertPt: MSSA.getMemoryAccess(I: InsertionPoint)));
1232 MSSAU.insertUse(Use: MSSALoad, /*RenameUses=*/ true);
1233
1234 // Create the final SVIs and replace all uses.
1235 int i = 0;
1236 for (const VectorInfo *VI : InterleavedLoad) {
1237 SmallVector<int, 4> Mask;
1238 for (unsigned j = 0; j < ElementsPerSVI; j++)
1239 Mask.push_back(Elt: i + j * Factor);
1240
1241 Builder.SetInsertPoint(VI->SVI);
1242 auto SVI = Builder.CreateShuffleVector(V: LI, Mask, Name: "interleaved.shuffle");
1243 VI->SVI->replaceAllUsesWith(V: SVI);
1244 i++;
1245 }
1246
1247 NumInterleavedLoadCombine++;
1248 ORE.emit(RemarkBuilder: [&]() {
1249 return OptimizationRemark(DEBUG_TYPE, "Combined Interleaved Load", LI)
1250 << "Load interleaved combined with factor "
1251 << ore::NV("Factor", Factor);
1252 });
1253
1254 return true;
1255}
1256
1257bool InterleavedLoadCombineImpl::run() {
1258 OptimizationRemarkEmitter ORE(&F);
1259 bool changed = false;
1260 unsigned MaxFactor = TLI.getMaxSupportedInterleaveFactor();
1261
1262 auto &DL = F.getDataLayout();
1263
1264 // Start with the highest factor to avoid combining and recombining.
1265 for (unsigned Factor = MaxFactor; Factor >= 2; Factor--) {
1266 // Process one block at a time. A group can only be combined when all of its
1267 // loads are in a single block, so keeping the candidate list and the offset
1268 // index per block keeps both small.
1269 for (BasicBlock &BB : F) {
1270 std::list<VectorInfo> Candidates;
1271 for (Instruction &I : BB) {
1272 auto *SVI = dyn_cast<ShuffleVectorInst>(Val: &I);
1273 if (!SVI)
1274 continue;
1275
1276 // We don't support scalable vectors in this pass.
1277 if (isa<ScalableVectorType>(Val: SVI->getType()))
1278 continue;
1279
1280 Candidates.emplace_back(args: cast<FixedVectorType>(Val: SVI->getType()));
1281 VectorInfo &C = Candidates.back();
1282
1283 if (!VectorInfo::computeFromSVI(SVI, Result&: C, DL) ||
1284 !C.isInterleaved(Factor, DL)) {
1285 Candidates.pop_back();
1286 continue;
1287 }
1288
1289 // Only combine loads that live in the block being processed. Widening
1290 // over loads from another block could read memory that is only
1291 // conditionally accessed.
1292 if (C.BB != &BB)
1293 Candidates.pop_back();
1294 }
1295
1296 // Index every candidate whose first element has a provably exact offset
1297 // by its address key. Finding an interleaved group then only needs
1298 // lookups of the neighbouring keys. The key embeds a Polynomial, which
1299 // has no natural empty/tombstone value, so use std::unordered_map rather
1300 // than DenseMap.
1301 std::unordered_map<OffsetKey, SmallVector<VectorInfo *, 1>, OffsetKeyHash>
1302 OffsetMap;
1303 for (VectorInfo &C : Candidates) {
1304 if (!C.EI[0].Ofs.isProvenExact())
1305 continue;
1306 OffsetMap[{.PV: C.PV, .VTy: C.VTy, .Ofs: C.EI[0].Ofs}].push_back(Elt: &C);
1307 }
1308
1309 // Candidates already combined (a whole group) or dropped (a failed base).
1310 SmallPtrSet<const VectorInfo *, 16> Consumed;
1311
1312 // Return the last still-available candidate registered under Key.
1313 // Iterating in reverse makes a later duplicate offset win over an earlier
1314 // one.
1315 auto FindNeighbor = [&](const OffsetKey &Key) -> VectorInfo * {
1316 auto It = OffsetMap.find(x: Key);
1317 if (It == OffsetMap.end())
1318 return nullptr;
1319 for (VectorInfo *Cand : reverse(C&: It->second))
1320 if (!Consumed.contains(Ptr: Cand))
1321 return Cand;
1322 return nullptr;
1323 };
1324
1325 for (VectorInfo &C0 : Candidates) {
1326 if (Consumed.contains(Ptr: &C0) || !C0.EI[0].Ofs.isProvenExact())
1327 continue;
1328
1329 unsigned Size = DL.getTypeAllocSize(Ty: C0.VTy->getElementType());
1330
1331 // Collect C0 and its Factor - 1 consecutive neighbours.
1332 SmallVector<VectorInfo *, 4> Group;
1333 Group.push_back(Elt: &C0);
1334 for (unsigned i = 1; i < Factor; i++) {
1335 VectorInfo *Nb =
1336 FindNeighbor({.PV: C0.PV, .VTy: C0.VTy, .Ofs: C0.EI[0].Ofs + i * Size});
1337 if (!Nb)
1338 break;
1339 Group.push_back(Elt: Nb);
1340 }
1341 if (Group.size() != Factor)
1342 continue;
1343
1344 if (combine(InterleavedLoad: Group, ORE)) {
1345 // The whole group is combined and left dead.
1346 Consumed.insert(I: Group.begin(), E: Group.end());
1347 changed = true;
1348 } else {
1349 // Drop only the base; keep its neighbours available as future bases.
1350 Consumed.insert(Ptr: &C0);
1351 }
1352 }
1353 }
1354 }
1355
1356 return changed;
1357}
1358
1359namespace {
1360/// This pass combines interleaved loads into a pattern detectable by
1361/// InterleavedAccessPass.
1362struct InterleavedLoadCombine : public FunctionPass {
1363 static char ID;
1364
1365 InterleavedLoadCombine() : FunctionPass(ID) {}
1366
1367 StringRef getPassName() const override {
1368 return "Interleaved Load Combine Pass";
1369 }
1370
1371 bool runOnFunction(Function &F) override {
1372 if (DisableInterleavedLoadCombine)
1373 return false;
1374
1375 auto *TPC = getAnalysisIfAvailable<TargetPassConfig>();
1376 if (!TPC)
1377 return false;
1378
1379 LLVM_DEBUG(dbgs() << "*** " << getPassName() << ": " << F.getName()
1380 << "\n");
1381
1382 return InterleavedLoadCombineImpl(
1383 F, getAnalysis<DominatorTreeWrapperPass>().getDomTree(),
1384 getAnalysis<MemorySSAWrapperPass>().getMSSA(),
1385 getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F),
1386 TPC->getTM<TargetMachine>())
1387 .run();
1388 }
1389
1390 void getAnalysisUsage(AnalysisUsage &AU) const override {
1391 AU.addRequired<MemorySSAWrapperPass>();
1392 AU.addRequired<DominatorTreeWrapperPass>();
1393 AU.addRequired<TargetTransformInfoWrapperPass>();
1394 FunctionPass::getAnalysisUsage(AU);
1395 }
1396
1397private:
1398};
1399} // anonymous namespace
1400
1401PreservedAnalyses
1402InterleavedLoadCombinePass::run(Function &F, FunctionAnalysisManager &FAM) {
1403
1404 auto &DT = FAM.getResult<DominatorTreeAnalysis>(IR&: F);
1405 auto &MemSSA = FAM.getResult<MemorySSAAnalysis>(IR&: F).getMSSA();
1406 auto &TTI = FAM.getResult<TargetIRAnalysis>(IR&: F);
1407 bool Changed = InterleavedLoadCombineImpl(F, DT, MemSSA, TTI, *TM).run();
1408 return Changed ? PreservedAnalyses::none() : PreservedAnalyses::all();
1409}
1410
1411char InterleavedLoadCombine::ID = 0;
1412
1413INITIALIZE_PASS_BEGIN(
1414 InterleavedLoadCombine, DEBUG_TYPE,
1415 "Combine interleaved loads into wide loads and shufflevector instructions",
1416 false, false)
1417INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
1418INITIALIZE_PASS_DEPENDENCY(MemorySSAWrapperPass)
1419INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)
1420INITIALIZE_PASS_END(
1421 InterleavedLoadCombine, DEBUG_TYPE,
1422 "Combine interleaved loads into wide loads and shufflevector instructions",
1423 false, false)
1424
1425FunctionPass *
1426llvm::createInterleavedLoadCombinePass() {
1427 auto P = new InterleavedLoadCombine();
1428 return P;
1429}
1430