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