Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/CodeGen/InterleavedAccessPass.cpp
Line
Count
Source (jump to first uncovered line)
1
//===- InterleavedAccessPass.cpp ------------------------------------------===//
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
// This file implements the Interleaved Access pass, which identifies
10
// interleaved memory accesses and transforms them into target specific
11
// intrinsics.
12
//
13
// An interleaved load reads data from memory into several vectors, with
14
// DE-interleaving the data on a factor. An interleaved store writes several
15
// vectors to memory with RE-interleaving the data on a factor.
16
//
17
// As interleaved accesses are difficult to identified in CodeGen (mainly
18
// because the VECTOR_SHUFFLE DAG node is quite different from the shufflevector
19
// IR), we identify and transform them to intrinsics in this pass so the
20
// intrinsics can be easily matched into target specific instructions later in
21
// CodeGen.
22
//
23
// E.g. An interleaved load (Factor = 2):
24
//        %wide.vec = load <8 x i32>, <8 x i32>* %ptr
25
//        %v0 = shuffle <8 x i32> %wide.vec, <8 x i32> undef, <0, 2, 4, 6>
26
//        %v1 = shuffle <8 x i32> %wide.vec, <8 x i32> undef, <1, 3, 5, 7>
27
//
28
// It could be transformed into a ld2 intrinsic in AArch64 backend or a vld2
29
// intrinsic in ARM backend.
30
//
31
// In X86, this can be further optimized into a set of target
32
// specific loads followed by an optimized sequence of shuffles.
33
//
34
// E.g. An interleaved store (Factor = 3):
35
//        %i.vec = shuffle <8 x i32> %v0, <8 x i32> %v1,
36
//                                    <0, 4, 8, 1, 5, 9, 2, 6, 10, 3, 7, 11>
37
//        store <12 x i32> %i.vec, <12 x i32>* %ptr
38
//
39
// It could be transformed into a st3 intrinsic in AArch64 backend or a vst3
40
// intrinsic in ARM backend.
41
//
42
// Similarly, a set of interleaved stores can be transformed into an optimized
43
// sequence of shuffles followed by a set of target specific stores for X86.
44
//
45
//===----------------------------------------------------------------------===//
46
47
#include "llvm/ADT/ArrayRef.h"
48
#include "llvm/ADT/DenseMap.h"
49
#include "llvm/ADT/SmallVector.h"
50
#include "llvm/CodeGen/TargetLowering.h"
51
#include "llvm/CodeGen/TargetPassConfig.h"
52
#include "llvm/CodeGen/TargetSubtargetInfo.h"
53
#include "llvm/IR/Constants.h"
54
#include "llvm/IR/Dominators.h"
55
#include "llvm/IR/Function.h"
56
#include "llvm/IR/IRBuilder.h"
57
#include "llvm/IR/InstIterator.h"
58
#include "llvm/IR/Instruction.h"
59
#include "llvm/IR/Instructions.h"
60
#include "llvm/IR/Type.h"
61
#include "llvm/Pass.h"
62
#include "llvm/Support/Casting.h"
63
#include "llvm/Support/CommandLine.h"
64
#include "llvm/Support/Debug.h"
65
#include "llvm/Support/MathExtras.h"
66
#include "llvm/Support/raw_ostream.h"
67
#include "llvm/Target/TargetMachine.h"
68
#include <cassert>
69
#include <utility>
70
71
using namespace llvm;
72
73
#define DEBUG_TYPE "interleaved-access"
74
75
static cl::opt<bool> LowerInterleavedAccesses(
76
    "lower-interleaved-accesses",
77
    cl::desc("Enable lowering interleaved accesses to intrinsics"),
78
    cl::init(true), cl::Hidden);
79
80
namespace {
81
82
class InterleavedAccess : public FunctionPass {
83
public:
84
  static char ID;
85
86
24.9k
  InterleavedAccess() : FunctionPass(ID) {
87
24.9k
    initializeInterleavedAccessPass(*PassRegistry::getPassRegistry());
88
24.9k
  }
89
90
418k
  StringRef getPassName() const override { return "Interleaved Access Pass"; }
91
92
  bool runOnFunction(Function &F) override;
93
94
24.8k
  void getAnalysisUsage(AnalysisUsage &AU) const override {
95
24.8k
    AU.addRequired<DominatorTreeWrapperPass>();
96
24.8k
    AU.addPreserved<DominatorTreeWrapperPass>();
97
24.8k
  }
98
99
private:
100
  DominatorTree *DT = nullptr;
101
  const TargetLowering *TLI = nullptr;
102
103
  /// The maximum supported interleave factor.
104
  unsigned MaxFactor;
105
106
  /// Transform an interleaved load into target specific intrinsics.
107
  bool lowerInterleavedLoad(LoadInst *LI,
108
                            SmallVector<Instruction *, 32> &DeadInsts);
109
110
  /// Transform an interleaved store into target specific intrinsics.
111
  bool lowerInterleavedStore(StoreInst *SI,
112
                             SmallVector<Instruction *, 32> &DeadInsts);
113
114
  /// Returns true if the uses of an interleaved load by the
115
  /// extractelement instructions in \p Extracts can be replaced by uses of the
116
  /// shufflevector instructions in \p Shuffles instead. If so, the necessary
117
  /// replacements are also performed.
118
  bool tryReplaceExtracts(ArrayRef<ExtractElementInst *> Extracts,
119
                          ArrayRef<ShuffleVectorInst *> Shuffles);
120
};
121
122
} // end anonymous namespace.
123
124
char InterleavedAccess::ID = 0;
125
126
49.1k
INITIALIZE_PASS_BEGIN(InterleavedAccess, DEBUG_TYPE,
127
49.1k
    "Lower interleaved memory accesses to target specific intrinsics", false,
128
49.1k
    false)
129
49.1k
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
130
49.1k
INITIALIZE_PASS_END(InterleavedAccess, DEBUG_TYPE,
131
    "Lower interleaved memory accesses to target specific intrinsics", false,
132
    false)
133
134
24.9k
FunctionPass *llvm::createInterleavedAccessPass() {
135
24.9k
  return new InterleavedAccess();
136
24.9k
}
137
138
/// Check if the mask is a DE-interleave mask of the given factor
139
/// \p Factor like:
140
///     <Index, Index+Factor, ..., Index+(NumElts-1)*Factor>
141
static bool isDeInterleaveMaskOfFactor(ArrayRef<int> Mask, unsigned Factor,
142
4.00k
                                       unsigned &Index) {
143
4.00k
  // Check all potential start indices from 0 to (Factor - 1).
144
11.4k
  for (Index = 0; Index < Factor; 
Index++7.49k
) {
145
9.11k
    unsigned i = 0;
146
9.11k
147
9.11k
    // Check that elements are in ascending order by Factor. Ignore undef
148
9.11k
    // elements.
149
23.3k
    for (; i < Mask.size(); 
i++14.2k
)
150
21.7k
      if (Mask[i] >= 0 && 
static_cast<unsigned>(Mask[i]) != Index + i * Factor21.6k
)
151
7.49k
        break;
152
9.11k
153
9.11k
    if (i == Mask.size())
154
1.61k
      return true;
155
9.11k
  }
156
4.00k
157
4.00k
  
return false2.38k
;
158
4.00k
}
159
160
/// Check if the mask is a DE-interleave mask for an interleaved load.
161
///
162
/// E.g. DE-interleave masks (Factor = 2) could be:
163
///     <0, 2, 4, 6>    (mask of index 0 to extract even elements)
164
///     <1, 3, 5, 7>    (mask of index 1 to extract odd elements)
165
static bool isDeInterleaveMask(ArrayRef<int> Mask, unsigned &Factor,
166
                               unsigned &Index, unsigned MaxFactor,
167
4.02k
                               unsigned NumLoadElements) {
168
4.02k
  if (Mask.size() < 2)
169
26
    return false;
170
3.99k
171
3.99k
  // Check potential Factors.
172
6.38k
  
for (Factor = 2; 3.99k
Factor <= MaxFactor;
Factor++2.38k
) {
173
6.01k
    // Make sure we don't produce a load wider than the input load.
174
6.01k
    if (Mask.size() * Factor > NumLoadElements)
175
2.67k
      return false;
176
3.33k
    if (isDeInterleaveMaskOfFactor(Mask, Factor, Index))
177
948
      return true;
178
3.33k
  }
179
3.99k
180
3.99k
  
return false373
;
181
3.99k
}
182
183
/// Check if the mask can be used in an interleaved store.
184
//
185
/// It checks for a more general pattern than the RE-interleave mask.
186
/// I.e. <x, y, ... z, x+1, y+1, ...z+1, x+2, y+2, ...z+2, ...>
187
/// E.g. For a Factor of 2 (LaneLen=4): <4, 32, 5, 33, 6, 34, 7, 35>
188
/// E.g. For a Factor of 3 (LaneLen=4): <4, 32, 16, 5, 33, 17, 6, 34, 18, 7, 35, 19>
189
/// E.g. For a Factor of 4 (LaneLen=2): <8, 2, 12, 4, 9, 3, 13, 5>
190
///
191
/// The particular case of an RE-interleave mask is:
192
/// I.e. <0, LaneLen, ... , LaneLen*(Factor - 1), 1, LaneLen + 1, ...>
193
/// E.g. For a Factor of 2 (LaneLen=4): <0, 4, 1, 5, 2, 6, 3, 7>
194
static bool isReInterleaveMask(ArrayRef<int> Mask, unsigned &Factor,
195
15.9k
                               unsigned MaxFactor, unsigned OpNumElts) {
196
15.9k
  unsigned NumElts = Mask.size();
197
15.9k
  if (NumElts < 4)
198
13.7k
    return false;
199
2.20k
200
2.20k
  // Check potential Factors.
201
6.46k
  
for (Factor = 2; 2.20k
Factor <= MaxFactor;
Factor++4.25k
) {
202
5.79k
    if (NumElts % Factor)
203
1.81k
      continue;
204
3.98k
205
3.98k
    unsigned LaneLen = NumElts / Factor;
206
3.98k
    if (!isPowerOf2_32(LaneLen))
207
138
      continue;
208
3.84k
209
3.84k
    // Check whether each element matches the general interleaved rule.
210
3.84k
    // Ignore undef elements, as long as the defined elements match the rule.
211
3.84k
    // Outer loop processes all factors (x, y, z in the above example)
212
3.84k
    unsigned I = 0, J;
213
9.19k
    for (; I < Factor; 
I++5.34k
) {
214
7.65k
      unsigned SavedLaneValue;
215
7.65k
      unsigned SavedNoUndefs = 0;
216
7.65k
217
7.65k
      // Inner loop processes consecutive accesses (x, x+1... in the example)
218
15.8k
      for (J = 0; J < LaneLen - 1; 
J++8.20k
) {
219
10.4k
        // Lane computes x's position in the Mask
220
10.4k
        unsigned Lane = J * Factor + I;
221
10.4k
        unsigned NextLane = Lane + Factor;
222
10.4k
        int LaneValue = Mask[Lane];
223
10.4k
        int NextLaneValue = Mask[NextLane];
224
10.4k
225
10.4k
        // If both are defined, values must be sequential
226
10.4k
        if (LaneValue >= 0 && 
NextLaneValue >= 010.3k
&&
227
10.4k
            
LaneValue + 1 != NextLaneValue10.2k
)
228
2.28k
          break;
229
8.21k
230
8.21k
        // If the next value is undef, save the current one as reference
231
8.21k
        if (LaneValue >= 0 && 
NextLaneValue < 08.06k
) {
232
80
          SavedLaneValue = LaneValue;
233
80
          SavedNoUndefs = 1;
234
80
        }
235
8.21k
236
8.21k
        // Undefs are allowed, but defined elements must still be consecutive:
237
8.21k
        // i.e.: x,..., undef,..., x + 2,..., undef,..., undef,..., x + 5, ....
238
8.21k
        // Verify this by storing the last non-undef followed by an undef
239
8.21k
        // Check that following non-undef masks are incremented with the
240
8.21k
        // corresponding distance.
241
8.21k
        if (SavedNoUndefs > 0 && 
LaneValue < 0140
) {
242
52
          SavedNoUndefs++;
243
52
          if (NextLaneValue >= 0 &&
244
52
              
SavedLaneValue + SavedNoUndefs != (unsigned)NextLaneValue20
)
245
8
            break;
246
52
        }
247
8.21k
      }
248
7.65k
249
7.65k
      if (J < LaneLen - 1)
250
2.29k
        break;
251
5.36k
252
5.36k
      int StartMask = 0;
253
5.36k
      if (Mask[I] >= 0) {
254
5.29k
        // Check that the start of the I range (J=0) is greater than 0
255
5.29k
        StartMask = Mask[I];
256
5.29k
      } else 
if (67
Mask[(LaneLen - 1) * Factor + I] >= 067
) {
257
31
        // StartMask defined by the last value in lane
258
31
        StartMask = Mask[(LaneLen - 1) * Factor + I] - J;
259
36
      } else if (SavedNoUndefs > 0) {
260
4
        // StartMask defined by some non-zero value in the j loop
261
4
        StartMask = SavedLaneValue - (LaneLen - 1 - SavedNoUndefs);
262
4
      }
263
5.36k
      // else StartMask remains set to 0, i.e. all elements are undefs
264
5.36k
265
5.36k
      if (StartMask < 0)
266
6
        break;
267
5.35k
      // We must stay within the vectors; This case can happen with undefs.
268
5.35k
      if (StartMask + LaneLen > OpNumElts*2)
269
10
        break;
270
5.35k
    }
271
3.84k
272
3.84k
    // Found an interleaved mask of current factor.
273
3.84k
    if (I == Factor)
274
1.54k
      return true;
275
3.84k
  }
276
2.20k
277
2.20k
  
return false669
;
278
2.20k
}
279
280
bool InterleavedAccess::lowerInterleavedLoad(
281
1.49M
    LoadInst *LI, SmallVector<Instruction *, 32> &DeadInsts) {
282
1.49M
  if (!LI->isSimple())
283
10.2k
    return false;
284
1.48M
285
1.48M
  SmallVector<ShuffleVectorInst *, 4> Shuffles;
286
1.48M
  SmallVector<ExtractElementInst *, 4> Extracts;
287
1.48M
288
1.48M
  // Check if all users of this load are shufflevectors. If we encounter any
289
1.48M
  // users that are extractelement instructions, we save them to later check if
290
1.48M
  // they can be modifed to extract from one of the shufflevectors instead of
291
1.48M
  // the load.
292
1.49M
  for (auto UI = LI->user_begin(), E = LI->user_end(); UI != E; 
UI++5.88k
) {
293
1.48M
    auto *Extract = dyn_cast<ExtractElementInst>(*UI);
294
1.48M
    if (Extract && 
isa<ConstantInt>(Extract->getIndexOperand())866
) {
295
719
      Extracts.push_back(Extract);
296
719
      continue;
297
719
    }
298
1.48M
    ShuffleVectorInst *SVI = dyn_cast<ShuffleVectorInst>(*UI);
299
1.48M
    if (!SVI || 
!isa<UndefValue>(SVI->getOperand(1))7.91k
)
300
1.48M
      return false;
301
5.16k
302
5.16k
    Shuffles.push_back(SVI);
303
5.16k
  }
304
1.48M
305
1.48M
  
if (4.58k
Shuffles.empty()4.58k
)
306
564
    return false;
307
4.02k
308
4.02k
  unsigned Factor, Index;
309
4.02k
310
4.02k
  unsigned NumLoadElements = LI->getType()->getVectorNumElements();
311
4.02k
  // Check if the first shufflevector is DE-interleave shuffle.
312
4.02k
  if (!isDeInterleaveMask(Shuffles[0]->getShuffleMask(), Factor, Index,
313
4.02k
                          MaxFactor, NumLoadElements))
314
3.07k
    return false;
315
948
316
948
  // Holds the corresponding index for each DE-interleave shuffle.
317
948
  SmallVector<unsigned, 4> Indices;
318
948
  Indices.push_back(Index);
319
948
320
948
  Type *VecTy = Shuffles[0]->getType();
321
948
322
948
  // Check if other shufflevectors are also DE-interleaved of the same type
323
948
  // and factor as the first shufflevector.
324
1.61k
  for (unsigned i = 1; i < Shuffles.size(); 
i++665
) {
325
665
    if (Shuffles[i]->getType() != VecTy)
326
0
      return false;
327
665
328
665
    if (!isDeInterleaveMaskOfFactor(Shuffles[i]->getShuffleMask(), Factor,
329
665
                                    Index))
330
0
      return false;
331
665
332
665
    Indices.push_back(Index);
333
665
  }
334
948
335
948
  // Try and modify users of the load that are extractelement instructions to
336
948
  // use the shufflevector instructions instead of the load.
337
948
  if (!tryReplaceExtracts(Extracts, Shuffles))
338
4
    return false;
339
944
340
944
  LLVM_DEBUG(dbgs() << "IA: Found an interleaved load: " << *LI << "\n");
341
944
342
944
  // Try to create target specific intrinsics to replace the load and shuffles.
343
944
  if (!TLI->lowerInterleavedLoad(LI, Shuffles, Indices, Factor))
344
644
    return false;
345
300
346
300
  for (auto SVI : Shuffles)
347
695
    DeadInsts.push_back(SVI);
348
300
349
300
  DeadInsts.push_back(LI);
350
300
  return true;
351
300
}
352
353
bool InterleavedAccess::tryReplaceExtracts(
354
    ArrayRef<ExtractElementInst *> Extracts,
355
948
    ArrayRef<ShuffleVectorInst *> Shuffles) {
356
948
  // If there aren't any extractelement instructions to modify, there's nothing
357
948
  // to do.
358
948
  if (Extracts.empty())
359
939
    return true;
360
9
361
9
  // Maps extractelement instructions to vector-index pairs. The extractlement
362
9
  // instructions will be modified to use the new vector and index operands.
363
9
  DenseMap<ExtractElementInst *, std::pair<Value *, int>> ReplacementMap;
364
9
365
13
  for (auto *Extract : Extracts) {
366
13
    // The vector index that is extracted.
367
13
    auto *IndexOperand = cast<ConstantInt>(Extract->getIndexOperand());
368
13
    auto Index = IndexOperand->getSExtValue();
369
13
370
13
    // Look for a suitable shufflevector instruction. The goal is to modify the
371
13
    // extractelement instruction (which uses an interleaved load) to use one
372
13
    // of the shufflevector instructions instead of the load.
373
13
    for (auto *Shuffle : Shuffles) {
374
13
      // If the shufflevector instruction doesn't dominate the extract, we
375
13
      // can't create a use of it.
376
13
      if (!DT->dominates(Shuffle, Extract))
377
2
        continue;
378
11
379
11
      // Inspect the indices of the shufflevector instruction. If the shuffle
380
11
      // selects the same index that is extracted, we can modify the
381
11
      // extractelement instruction.
382
11
      SmallVector<int, 4> Indices;
383
11
      Shuffle->getShuffleMask(Indices);
384
32
      for (unsigned I = 0; I < Indices.size(); 
++I21
)
385
30
        if (Indices[I] == Index) {
386
9
          assert(Extract->getOperand(0) == Shuffle->getOperand(0) &&
387
9
                 "Vector operations do not match");
388
9
          ReplacementMap[Extract] = std::make_pair(Shuffle, I);
389
9
          break;
390
9
        }
391
11
392
11
      // If we found a suitable shufflevector instruction, stop looking.
393
11
      if (ReplacementMap.count(Extract))
394
9
        break;
395
11
    }
396
13
397
13
    // If we did not find a suitable shufflevector instruction, the
398
13
    // extractelement instruction cannot be modified, so we must give up.
399
13
    if (!ReplacementMap.count(Extract))
400
4
      return false;
401
13
  }
402
9
403
9
  // Finally, perform the replacements.
404
9
  IRBuilder<> Builder(Extracts[0]->getContext());
405
7
  for (auto &Replacement : ReplacementMap) {
406
7
    auto *Extract = Replacement.first;
407
7
    auto *Vector = Replacement.second.first;
408
7
    auto Index = Replacement.second.second;
409
7
    Builder.SetInsertPoint(Extract);
410
7
    Extract->replaceAllUsesWith(Builder.CreateExtractElement(Vector, Index));
411
7
    Extract->eraseFromParent();
412
7
  }
413
5
414
5
  return true;
415
9
}
416
417
bool InterleavedAccess::lowerInterleavedStore(
418
1.08M
    StoreInst *SI, SmallVector<Instruction *, 32> &DeadInsts) {
419
1.08M
  if (!SI->isSimple())
420
14.6k
    return false;
421
1.07M
422
1.07M
  ShuffleVectorInst *SVI = dyn_cast<ShuffleVectorInst>(SI->getValueOperand());
423
1.07M
  if (!SVI || 
!SVI->hasOneUse()130k
)
424
1.05M
    return false;
425
15.9k
426
15.9k
  // Check if the shufflevector is RE-interleave shuffle.
427
15.9k
  unsigned Factor;
428
15.9k
  unsigned OpNumElts = SVI->getOperand(0)->getType()->getVectorNumElements();
429
15.9k
  if (!isReInterleaveMask(SVI->getShuffleMask(), Factor, MaxFactor, OpNumElts))
430
14.3k
    return false;
431
1.54k
432
1.54k
  LLVM_DEBUG(dbgs() << "IA: Found an interleaved store: " << *SI << "\n");
433
1.54k
434
1.54k
  // Try to create target specific intrinsics to replace the store and shuffle.
435
1.54k
  if (!TLI->lowerInterleavedStore(SI, SVI, Factor))
436
1.09k
    return false;
437
444
438
444
  // Already have a new target specific interleaved store. Erase the old store.
439
444
  DeadInsts.push_back(SI);
440
444
  DeadInsts.push_back(SVI);
441
444
  return true;
442
444
}
443
444
418k
bool InterleavedAccess::runOnFunction(Function &F) {
445
418k
  auto *TPC = getAnalysisIfAvailable<TargetPassConfig>();
446
418k
  if (
!TPC418k
|| !LowerInterleavedAccesses)
447
54
    return false;
448
418k
449
418k
  LLVM_DEBUG(dbgs() << "*** " << getPassName() << ": " << F.getName() << "\n");
450
418k
451
418k
  DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
452
418k
  auto &TM = TPC->getTM<TargetMachine>();
453
418k
  TLI = TM.getSubtargetImpl(F)->getTargetLowering();
454
418k
  MaxFactor = TLI->getMaxSupportedInterleaveFactor();
455
418k
456
418k
  // Holds dead instructions that will be erased later.
457
418k
  SmallVector<Instruction *, 32> DeadInsts;
458
418k
  bool Changed = false;
459
418k
460
13.9M
  for (auto &I : instructions(F)) {
461
13.9M
    if (LoadInst *LI = dyn_cast<LoadInst>(&I))
462
1.49M
      Changed |= lowerInterleavedLoad(LI, DeadInsts);
463
13.9M
464
13.9M
    if (StoreInst *SI = dyn_cast<StoreInst>(&I))
465
1.08M
      Changed |= lowerInterleavedStore(SI, DeadInsts);
466
13.9M
  }
467
418k
468
418k
  for (auto I : DeadInsts)
469
1.88k
    I->eraseFromParent();
470
418k
471
418k
  return Changed;
472
418k
}