LLVM  10.0.0svn
InterleavedAccessPass.cpp
Go to the documentation of this file.
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"
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"
64 #include "llvm/Support/Debug.h"
68 #include <cassert>
69 #include <utility>
70 
71 using namespace llvm;
72 
73 #define DEBUG_TYPE "interleaved-access"
74 
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  InterleavedAccess() : FunctionPass(ID) {
88  }
89 
90  StringRef getPassName() const override { return "Interleaved Access Pass"; }
91 
92  bool runOnFunction(Function &F) override;
93 
94  void getAnalysisUsage(AnalysisUsage &AU) const override {
97  }
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,
120 };
121 
122 } // end anonymous namespace.
123 
124 char InterleavedAccess::ID = 0;
125 
126 INITIALIZE_PASS_BEGIN(InterleavedAccess, DEBUG_TYPE,
127  "Lower interleaved memory accesses to target specific intrinsics", false,
128  false)
130 INITIALIZE_PASS_END(InterleavedAccess, DEBUG_TYPE,
131  "Lower interleaved memory accesses to target specific intrinsics", false,
132  false)
133 
135  return new InterleavedAccess();
136 }
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  unsigned &Index) {
143  // Check all potential start indices from 0 to (Factor - 1).
144  for (Index = 0; Index < Factor; Index++) {
145  unsigned i = 0;
146 
147  // Check that elements are in ascending order by Factor. Ignore undef
148  // elements.
149  for (; i < Mask.size(); i++)
150  if (Mask[i] >= 0 && static_cast<unsigned>(Mask[i]) != Index + i * Factor)
151  break;
152 
153  if (i == Mask.size())
154  return true;
155  }
156 
157  return false;
158 }
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  unsigned NumLoadElements) {
168  if (Mask.size() < 2)
169  return false;
170 
171  // Check potential Factors.
172  for (Factor = 2; Factor <= MaxFactor; Factor++) {
173  // Make sure we don't produce a load wider than the input load.
174  if (Mask.size() * Factor > NumLoadElements)
175  return false;
176  if (isDeInterleaveMaskOfFactor(Mask, Factor, Index))
177  return true;
178  }
179 
180  return false;
181 }
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  unsigned MaxFactor, unsigned OpNumElts) {
196  unsigned NumElts = Mask.size();
197  if (NumElts < 4)
198  return false;
199 
200  // Check potential Factors.
201  for (Factor = 2; Factor <= MaxFactor; Factor++) {
202  if (NumElts % Factor)
203  continue;
204 
205  unsigned LaneLen = NumElts / Factor;
206  if (!isPowerOf2_32(LaneLen))
207  continue;
208 
209  // Check whether each element matches the general interleaved rule.
210  // Ignore undef elements, as long as the defined elements match the rule.
211  // Outer loop processes all factors (x, y, z in the above example)
212  unsigned I = 0, J;
213  for (; I < Factor; I++) {
214  unsigned SavedLaneValue;
215  unsigned SavedNoUndefs = 0;
216 
217  // Inner loop processes consecutive accesses (x, x+1... in the example)
218  for (J = 0; J < LaneLen - 1; J++) {
219  // Lane computes x's position in the Mask
220  unsigned Lane = J * Factor + I;
221  unsigned NextLane = Lane + Factor;
222  int LaneValue = Mask[Lane];
223  int NextLaneValue = Mask[NextLane];
224 
225  // If both are defined, values must be sequential
226  if (LaneValue >= 0 && NextLaneValue >= 0 &&
227  LaneValue + 1 != NextLaneValue)
228  break;
229 
230  // If the next value is undef, save the current one as reference
231  if (LaneValue >= 0 && NextLaneValue < 0) {
232  SavedLaneValue = LaneValue;
233  SavedNoUndefs = 1;
234  }
235 
236  // Undefs are allowed, but defined elements must still be consecutive:
237  // i.e.: x,..., undef,..., x + 2,..., undef,..., undef,..., x + 5, ....
238  // Verify this by storing the last non-undef followed by an undef
239  // Check that following non-undef masks are incremented with the
240  // corresponding distance.
241  if (SavedNoUndefs > 0 && LaneValue < 0) {
242  SavedNoUndefs++;
243  if (NextLaneValue >= 0 &&
244  SavedLaneValue + SavedNoUndefs != (unsigned)NextLaneValue)
245  break;
246  }
247  }
248 
249  if (J < LaneLen - 1)
250  break;
251 
252  int StartMask = 0;
253  if (Mask[I] >= 0) {
254  // Check that the start of the I range (J=0) is greater than 0
255  StartMask = Mask[I];
256  } else if (Mask[(LaneLen - 1) * Factor + I] >= 0) {
257  // StartMask defined by the last value in lane
258  StartMask = Mask[(LaneLen - 1) * Factor + I] - J;
259  } else if (SavedNoUndefs > 0) {
260  // StartMask defined by some non-zero value in the j loop
261  StartMask = SavedLaneValue - (LaneLen - 1 - SavedNoUndefs);
262  }
263  // else StartMask remains set to 0, i.e. all elements are undefs
264 
265  if (StartMask < 0)
266  break;
267  // We must stay within the vectors; This case can happen with undefs.
268  if (StartMask + LaneLen > OpNumElts*2)
269  break;
270  }
271 
272  // Found an interleaved mask of current factor.
273  if (I == Factor)
274  return true;
275  }
276 
277  return false;
278 }
279 
280 bool InterleavedAccess::lowerInterleavedLoad(
281  LoadInst *LI, SmallVector<Instruction *, 32> &DeadInsts) {
282  if (!LI->isSimple())
283  return false;
284 
287 
288  // Check if all users of this load are shufflevectors. If we encounter any
289  // users that are extractelement instructions, we save them to later check if
290  // they can be modifed to extract from one of the shufflevectors instead of
291  // the load.
292  for (auto UI = LI->user_begin(), E = LI->user_end(); UI != E; UI++) {
293  auto *Extract = dyn_cast<ExtractElementInst>(*UI);
294  if (Extract && isa<ConstantInt>(Extract->getIndexOperand())) {
295  Extracts.push_back(Extract);
296  continue;
297  }
299  if (!SVI || !isa<UndefValue>(SVI->getOperand(1)))
300  return false;
301 
302  Shuffles.push_back(SVI);
303  }
304 
305  if (Shuffles.empty())
306  return false;
307 
308  unsigned Factor, Index;
309 
310  unsigned NumLoadElements = LI->getType()->getVectorNumElements();
311  // Check if the first shufflevector is DE-interleave shuffle.
312  if (!isDeInterleaveMask(Shuffles[0]->getShuffleMask(), Factor, Index,
313  MaxFactor, NumLoadElements))
314  return false;
315 
316  // Holds the corresponding index for each DE-interleave shuffle.
317  SmallVector<unsigned, 4> Indices;
318  Indices.push_back(Index);
319 
320  Type *VecTy = Shuffles[0]->getType();
321 
322  // Check if other shufflevectors are also DE-interleaved of the same type
323  // and factor as the first shufflevector.
324  for (unsigned i = 1; i < Shuffles.size(); i++) {
325  if (Shuffles[i]->getType() != VecTy)
326  return false;
327 
328  if (!isDeInterleaveMaskOfFactor(Shuffles[i]->getShuffleMask(), Factor,
329  Index))
330  return false;
331 
332  Indices.push_back(Index);
333  }
334 
335  // Try and modify users of the load that are extractelement instructions to
336  // use the shufflevector instructions instead of the load.
337  if (!tryReplaceExtracts(Extracts, Shuffles))
338  return false;
339 
340  LLVM_DEBUG(dbgs() << "IA: Found an interleaved load: " << *LI << "\n");
341 
342  // Try to create target specific intrinsics to replace the load and shuffles.
343  if (!TLI->lowerInterleavedLoad(LI, Shuffles, Indices, Factor))
344  return false;
345 
346  for (auto SVI : Shuffles)
347  DeadInsts.push_back(SVI);
348 
349  DeadInsts.push_back(LI);
350  return true;
351 }
352 
353 bool InterleavedAccess::tryReplaceExtracts(
356  // If there aren't any extractelement instructions to modify, there's nothing
357  // to do.
358  if (Extracts.empty())
359  return true;
360 
361  // Maps extractelement instructions to vector-index pairs. The extractlement
362  // instructions will be modified to use the new vector and index operands.
364 
365  for (auto *Extract : Extracts) {
366  // The vector index that is extracted.
367  auto *IndexOperand = cast<ConstantInt>(Extract->getIndexOperand());
368  auto Index = IndexOperand->getSExtValue();
369 
370  // Look for a suitable shufflevector instruction. The goal is to modify the
371  // extractelement instruction (which uses an interleaved load) to use one
372  // of the shufflevector instructions instead of the load.
373  for (auto *Shuffle : Shuffles) {
374  // If the shufflevector instruction doesn't dominate the extract, we
375  // can't create a use of it.
376  if (!DT->dominates(Shuffle, Extract))
377  continue;
378 
379  // Inspect the indices of the shufflevector instruction. If the shuffle
380  // selects the same index that is extracted, we can modify the
381  // extractelement instruction.
382  SmallVector<int, 4> Indices;
383  Shuffle->getShuffleMask(Indices);
384  for (unsigned I = 0; I < Indices.size(); ++I)
385  if (Indices[I] == Index) {
386  assert(Extract->getOperand(0) == Shuffle->getOperand(0) &&
387  "Vector operations do not match");
388  ReplacementMap[Extract] = std::make_pair(Shuffle, I);
389  break;
390  }
391 
392  // If we found a suitable shufflevector instruction, stop looking.
393  if (ReplacementMap.count(Extract))
394  break;
395  }
396 
397  // If we did not find a suitable shufflevector instruction, the
398  // extractelement instruction cannot be modified, so we must give up.
399  if (!ReplacementMap.count(Extract))
400  return false;
401  }
402 
403  // Finally, perform the replacements.
404  IRBuilder<> Builder(Extracts[0]->getContext());
405  for (auto &Replacement : ReplacementMap) {
406  auto *Extract = Replacement.first;
407  auto *Vector = Replacement.second.first;
408  auto Index = Replacement.second.second;
409  Builder.SetInsertPoint(Extract);
410  Extract->replaceAllUsesWith(Builder.CreateExtractElement(Vector, Index));
411  Extract->eraseFromParent();
412  }
413 
414  return true;
415 }
416 
417 bool InterleavedAccess::lowerInterleavedStore(
419  if (!SI->isSimple())
420  return false;
421 
423  if (!SVI || !SVI->hasOneUse())
424  return false;
425 
426  // Check if the shufflevector is RE-interleave shuffle.
427  unsigned Factor;
428  unsigned OpNumElts = SVI->getOperand(0)->getType()->getVectorNumElements();
429  if (!isReInterleaveMask(SVI->getShuffleMask(), Factor, MaxFactor, OpNumElts))
430  return false;
431 
432  LLVM_DEBUG(dbgs() << "IA: Found an interleaved store: " << *SI << "\n");
433 
434  // Try to create target specific intrinsics to replace the store and shuffle.
435  if (!TLI->lowerInterleavedStore(SI, SVI, Factor))
436  return false;
437 
438  // Already have a new target specific interleaved store. Erase the old store.
439  DeadInsts.push_back(SI);
440  DeadInsts.push_back(SVI);
441  return true;
442 }
443 
445  auto *TPC = getAnalysisIfAvailable<TargetPassConfig>();
446  if (!TPC || !LowerInterleavedAccesses)
447  return false;
448 
449  LLVM_DEBUG(dbgs() << "*** " << getPassName() << ": " << F.getName() << "\n");
450 
451  DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
452  auto &TM = TPC->getTM<TargetMachine>();
453  TLI = TM.getSubtargetImpl(F)->getTargetLowering();
454  MaxFactor = TLI->getMaxSupportedInterleaveFactor();
455 
456  // Holds dead instructions that will be erased later.
458  bool Changed = false;
459 
460  for (auto &I : instructions(F)) {
461  if (LoadInst *LI = dyn_cast<LoadInst>(&I))
462  Changed |= lowerInterleavedLoad(LI, DeadInsts);
463 
464  if (StoreInst *SI = dyn_cast<StoreInst>(&I))
465  Changed |= lowerInterleavedStore(SI, DeadInsts);
466  }
467 
468  for (auto I : DeadInsts)
469  I->eraseFromParent();
470 
471  return Changed;
472 }
Value * getValueOperand()
Definition: Instructions.h:409
bool isSimple() const
Definition: Instructions.h:276
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
This class represents lattice values for constants.
Definition: AllocatorList.h:23
INITIALIZE_PASS_BEGIN(InterleavedAccess, DEBUG_TYPE, "Lower interleaved memory accesses to target specific intrinsics", false, false) INITIALIZE_PASS_END(InterleavedAccess
static cl::opt< bool > LowerInterleavedAccesses("lower-interleaved-accesses", cl::desc("Enable lowering interleaved accesses to intrinsics"), cl::init(true), cl::Hidden)
This instruction constructs a fixed permutation of two input vectors.
F(f)
An instruction for reading from memory.
Definition: Instructions.h:167
static bool isDeInterleaveMask(ArrayRef< int > Mask, unsigned &Factor, unsigned &Index, unsigned MaxFactor, unsigned NumLoadElements)
Check if the mask is a DE-interleave mask for an interleaved load.
AnalysisUsage & addRequired()
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:50
#define DEBUG_TYPE
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Definition: IRBuilder.h:779
This class defines information used to lower LLVM code to legal SelectionDAG operators that the targe...
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:245
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory)...
Definition: APInt.h:32
An instruction for storing to memory.
Definition: Instructions.h:320
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:144
static bool isReInterleaveMask(ArrayRef< int > Mask, unsigned &Factor, unsigned MaxFactor, unsigned OpNumElts)
Check if the mask can be used in an interleaved store.
void SetInsertPoint(BasicBlock *TheBB)
This specifies that created instructions should be appended to the end of the specified block...
Definition: IRBuilder.h:132
Value * getOperand(unsigned i) const
Definition: User.h:169
static bool runOnFunction(Function &F, bool PostInlining)
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:432
constexpr bool isPowerOf2_32(uint32_t Value)
Return true if the argument is a power of two > 0.
Definition: MathExtras.h:428
The instances of the Type class are immutable: once they are created, they are never changed...
Definition: Type.h:45
size_t size() const
size - Get the array size.
Definition: ArrayRef.h:148
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
This file contains the declarations for the subclasses of Constant, which represent the different fla...
FunctionPass * createInterleavedAccessPass()
InterleavedAccess Pass - This pass identifies and matches interleaved memory accesses to target speci...
Represent the analysis usage information of a pass.
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:284
Value * CreateExtractElement(Value *Vec, Value *Idx, const Twine &Name="")
Definition: IRBuilder.h:2307
size_t size() const
Definition: SmallVector.h:52
static wasm::ValType getType(const TargetRegisterClass *RC)
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
void initializeInterleavedAccessPass(PassRegistry &)
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:837
static void getShuffleMask(const Constant *Mask, SmallVectorImpl< int > &Result)
Convert the input shuffle mask operand to a vector of integers.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
unsigned getVectorNumElements() const
Definition: DerivedTypes.h:561
Lower interleaved memory accesses to target specific intrinsics
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:55
StringRef getName() const
Return a constant reference to the value&#39;s name.
Definition: Value.cpp:214
#define I(x, y, z)
Definition: MD5.cpp:58
LLVM_NODISCARD std::enable_if<!is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type >::type dyn_cast(const Y &Val)
Definition: Casting.h:332
This instruction extracts a single (scalar) element from a VectorType value.
size_type count(const_arg_type_t< KeyT > Val) const
Return 1 if the specified key is in the map, 0 otherwise.
Definition: DenseMap.h:145
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
user_iterator user_begin()
Definition: Value.h:395
std::underlying_type< E >::type Mask()
Get a bitmask with 1s in all places up to the high-order bit of E&#39;s largest value.
Definition: BitmaskEnum.h:80
Primary interface to the complete machine description for the target machine.
Definition: TargetMachine.h:65
bool hasOneUse() const
Return true if there is exactly one user of this value.
Definition: Value.h:432
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:48
inst_range instructions(Function *F)
Definition: InstIterator.h:133
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:259
static bool isDeInterleaveMaskOfFactor(ArrayRef< int > Mask, unsigned Factor, unsigned &Index)
Check if the mask is a DE-interleave mask of the given factor Factor like: <Index, Index+Factor, ..., Index+(NumElts-1)*Factor>
bool isSimple() const
Definition: Instructions.h:401
#define LLVM_DEBUG(X)
Definition: Debug.h:122
bool empty() const
empty - Check if the array is empty.
Definition: ArrayRef.h:143
This file describes how to lower LLVM code to machine code.
user_iterator user_end()
Definition: Value.h:403