LLVM  12.0.0git
VectorCombine.cpp
Go to the documentation of this file.
1 //===------- VectorCombine.cpp - Optimize partial vector operations -------===//
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 pass optimizes scalar/vector interactions using target cost models. The
10 // transforms implemented here may not fit in traditional loop-based or SLP
11 // vectorization passes.
12 //
13 //===----------------------------------------------------------------------===//
14 
16 #include "llvm/ADT/Statistic.h"
19 #include "llvm/Analysis/Loads.h"
23 #include "llvm/IR/Dominators.h"
24 #include "llvm/IR/Function.h"
25 #include "llvm/IR/IRBuilder.h"
26 #include "llvm/IR/PatternMatch.h"
27 #include "llvm/InitializePasses.h"
28 #include "llvm/Pass.h"
32 
33 using namespace llvm;
34 using namespace llvm::PatternMatch;
35 
36 #define DEBUG_TYPE "vector-combine"
37 STATISTIC(NumVecLoad, "Number of vector loads formed");
38 STATISTIC(NumVecCmp, "Number of vector compares formed");
39 STATISTIC(NumVecBO, "Number of vector binops formed");
40 STATISTIC(NumVecCmpBO, "Number of vector compare + binop formed");
41 STATISTIC(NumShufOfBitcast, "Number of shuffles moved after bitcast");
42 STATISTIC(NumScalarBO, "Number of scalar binops formed");
43 STATISTIC(NumScalarCmp, "Number of scalar compares formed");
44 
46  "disable-vector-combine", cl::init(false), cl::Hidden,
47  cl::desc("Disable all vector combine transforms"));
48 
50  "disable-binop-extract-shuffle", cl::init(false), cl::Hidden,
51  cl::desc("Disable binop extract to shuffle transforms"));
52 
54 
55 namespace {
56 class VectorCombine {
57 public:
58  VectorCombine(Function &F, const TargetTransformInfo &TTI,
59  const DominatorTree &DT)
60  : F(F), Builder(F.getContext()), TTI(TTI), DT(DT) {}
61 
62  bool run();
63 
64 private:
65  Function &F;
67  const TargetTransformInfo &TTI;
68  const DominatorTree &DT;
69 
70  bool vectorizeLoadInsert(Instruction &I);
71  ExtractElementInst *getShuffleExtract(ExtractElementInst *Ext0,
72  ExtractElementInst *Ext1,
73  unsigned PreferredExtractIndex) const;
74  bool isExtractExtractCheap(ExtractElementInst *Ext0, ExtractElementInst *Ext1,
75  unsigned Opcode,
76  ExtractElementInst *&ConvertToShuffle,
77  unsigned PreferredExtractIndex);
78  void foldExtExtCmp(ExtractElementInst *Ext0, ExtractElementInst *Ext1,
79  Instruction &I);
80  void foldExtExtBinop(ExtractElementInst *Ext0, ExtractElementInst *Ext1,
81  Instruction &I);
82  bool foldExtractExtract(Instruction &I);
83  bool foldBitcastShuf(Instruction &I);
84  bool scalarizeBinopOrCmp(Instruction &I);
85  bool foldExtractedCmps(Instruction &I);
86 };
87 } // namespace
88 
89 static void replaceValue(Value &Old, Value &New) {
90  Old.replaceAllUsesWith(&New);
91  New.takeName(&Old);
92 }
93 
94 bool VectorCombine::vectorizeLoadInsert(Instruction &I) {
95  // Match insert into fixed vector of scalar value.
96  // TODO: Handle non-zero insert index.
97  auto *Ty = dyn_cast<FixedVectorType>(I.getType());
98  Value *Scalar;
99  if (!Ty || !match(&I, m_InsertElt(m_Undef(), m_Value(Scalar), m_ZeroInt())) ||
100  !Scalar->hasOneUse())
101  return false;
102 
103  // Optionally match an extract from another vector.
104  Value *X;
105  bool HasExtract = match(Scalar, m_ExtractElt(m_Value(X), m_ZeroInt()));
106  if (!HasExtract)
107  X = Scalar;
108 
109  // Match source value as load of scalar or vector.
110  // Do not vectorize scalar load (widening) if atomic/volatile or under
111  // asan/hwasan/memtag/tsan. The widened load may load data from dirty regions
112  // or create data races non-existent in the source.
113  auto *Load = dyn_cast<LoadInst>(X);
114  if (!Load || !Load->isSimple() || !Load->hasOneUse() ||
115  Load->getFunction()->hasFnAttribute(Attribute::SanitizeMemTag) ||
117  return false;
118 
119  const DataLayout &DL = I.getModule()->getDataLayout();
120  Value *SrcPtr = Load->getPointerOperand()->stripPointerCasts();
121  assert(isa<PointerType>(SrcPtr->getType()) && "Expected a pointer type");
122 
123  // If original AS != Load's AS, we can't bitcast the original pointer and have
124  // to use Load's operand instead. Ideally we would want to strip pointer casts
125  // without changing AS, but there's no API to do that ATM.
126  unsigned AS = Load->getPointerAddressSpace();
127  if (AS != SrcPtr->getType()->getPointerAddressSpace())
128  SrcPtr = Load->getPointerOperand();
129 
130  // We are potentially transforming byte-sized (8-bit) memory accesses, so make
131  // sure we have all of our type-based constraints in place for this target.
132  Type *ScalarTy = Scalar->getType();
133  uint64_t ScalarSize = ScalarTy->getPrimitiveSizeInBits();
134  unsigned MinVectorSize = TTI.getMinVectorRegisterBitWidth();
135  if (!ScalarSize || !MinVectorSize || MinVectorSize % ScalarSize != 0 ||
136  ScalarSize % 8 != 0)
137  return false;
138 
139  // Check safety of replacing the scalar load with a larger vector load.
140  // We use minimal alignment (maximum flexibility) because we only care about
141  // the dereferenceable region. When calculating cost and creating a new op,
142  // we may use a larger value based on alignment attributes.
143  unsigned MinVecNumElts = MinVectorSize / ScalarSize;
144  auto *MinVecTy = VectorType::get(ScalarTy, MinVecNumElts, false);
145  unsigned OffsetEltIndex = 0;
146  Align Alignment = Load->getAlign();
147  if (!isSafeToLoadUnconditionally(SrcPtr, MinVecTy, Align(1), DL, Load, &DT)) {
148  // It is not safe to load directly from the pointer, but we can still peek
149  // through gep offsets and check if it safe to load from a base address with
150  // updated alignment. If it is, we can shuffle the element(s) into place
151  // after loading.
152  unsigned OffsetBitWidth = DL.getIndexTypeSizeInBits(SrcPtr->getType());
153  APInt Offset(OffsetBitWidth, 0);
155 
156  // We want to shuffle the result down from a high element of a vector, so
157  // the offset must be positive.
158  if (Offset.isNegative())
159  return false;
160 
161  // The offset must be a multiple of the scalar element to shuffle cleanly
162  // in the element's size.
163  uint64_t ScalarSizeInBytes = ScalarSize / 8;
164  if (Offset.urem(ScalarSizeInBytes) != 0)
165  return false;
166 
167  // If we load MinVecNumElts, will our target element still be loaded?
168  OffsetEltIndex = Offset.udiv(ScalarSizeInBytes).getZExtValue();
169  if (OffsetEltIndex >= MinVecNumElts)
170  return false;
171 
172  if (!isSafeToLoadUnconditionally(SrcPtr, MinVecTy, Align(1), DL, Load, &DT))
173  return false;
174 
175  // Update alignment with offset value. Note that the offset could be negated
176  // to more accurately represent "(new) SrcPtr - Offset = (old) SrcPtr", but
177  // negation does not change the result of the alignment calculation.
178  Alignment = commonAlignment(Alignment, Offset.getZExtValue());
179  }
180 
181  // Original pattern: insertelt undef, load [free casts of] PtrOp, 0
182  // Use the greater of the alignment on the load or its source pointer.
183  Alignment = std::max(SrcPtr->getPointerAlignment(DL), Alignment);
184  Type *LoadTy = Load->getType();
185  int OldCost = TTI.getMemoryOpCost(Instruction::Load, LoadTy, Alignment, AS);
186  APInt DemandedElts = APInt::getOneBitSet(MinVecNumElts, 0);
187  OldCost += TTI.getScalarizationOverhead(MinVecTy, DemandedElts,
188  /* Insert */ true, HasExtract);
189 
190  // New pattern: load VecPtr
191  int NewCost = TTI.getMemoryOpCost(Instruction::Load, MinVecTy, Alignment, AS);
192  // Optionally, we are shuffling the loaded vector element(s) into place.
193  if (OffsetEltIndex)
194  NewCost += TTI.getShuffleCost(TTI::SK_PermuteSingleSrc, MinVecTy);
195 
196  // We can aggressively convert to the vector form because the backend can
197  // invert this transform if it does not result in a performance win.
198  if (OldCost < NewCost)
199  return false;
200 
201  // It is safe and potentially profitable to load a vector directly:
202  // inselt undef, load Scalar, 0 --> load VecPtr
204  Value *CastedPtr = Builder.CreateBitCast(SrcPtr, MinVecTy->getPointerTo(AS));
205  Value *VecLd = Builder.CreateAlignedLoad(MinVecTy, CastedPtr, Alignment);
206 
207  // Set everything but element 0 to undef to prevent poison from propagating
208  // from the extra loaded memory. This will also optionally shrink/grow the
209  // vector from the loaded size to the output size.
210  // We assume this operation has no cost in codegen if there was no offset.
211  // Note that we could use freeze to avoid poison problems, but then we might
212  // still need a shuffle to change the vector size.
213  unsigned OutputNumElts = Ty->getNumElements();
214  SmallVector<int, 16> Mask(OutputNumElts, UndefMaskElem);
215  assert(OffsetEltIndex < MinVecNumElts && "Address offset too big");
216  Mask[0] = OffsetEltIndex;
217  VecLd = Builder.CreateShuffleVector(VecLd, Mask);
218 
219  replaceValue(I, *VecLd);
220  ++NumVecLoad;
221  return true;
222 }
223 
224 /// Determine which, if any, of the inputs should be replaced by a shuffle
225 /// followed by extract from a different index.
226 ExtractElementInst *VectorCombine::getShuffleExtract(
228  unsigned PreferredExtractIndex = InvalidIndex) const {
229  assert(isa<ConstantInt>(Ext0->getIndexOperand()) &&
230  isa<ConstantInt>(Ext1->getIndexOperand()) &&
231  "Expected constant extract indexes");
232 
233  unsigned Index0 = cast<ConstantInt>(Ext0->getIndexOperand())->getZExtValue();
234  unsigned Index1 = cast<ConstantInt>(Ext1->getIndexOperand())->getZExtValue();
235 
236  // If the extract indexes are identical, no shuffle is needed.
237  if (Index0 == Index1)
238  return nullptr;
239 
240  Type *VecTy = Ext0->getVectorOperand()->getType();
241  assert(VecTy == Ext1->getVectorOperand()->getType() && "Need matching types");
242  int Cost0 = TTI.getVectorInstrCost(Ext0->getOpcode(), VecTy, Index0);
243  int Cost1 = TTI.getVectorInstrCost(Ext1->getOpcode(), VecTy, Index1);
244 
245  // We are extracting from 2 different indexes, so one operand must be shuffled
246  // before performing a vector operation and/or extract. The more expensive
247  // extract will be replaced by a shuffle.
248  if (Cost0 > Cost1)
249  return Ext0;
250  if (Cost1 > Cost0)
251  return Ext1;
252 
253  // If the costs are equal and there is a preferred extract index, shuffle the
254  // opposite operand.
255  if (PreferredExtractIndex == Index0)
256  return Ext1;
257  if (PreferredExtractIndex == Index1)
258  return Ext0;
259 
260  // Otherwise, replace the extract with the higher index.
261  return Index0 > Index1 ? Ext0 : Ext1;
262 }
263 
264 /// Compare the relative costs of 2 extracts followed by scalar operation vs.
265 /// vector operation(s) followed by extract. Return true if the existing
266 /// instructions are cheaper than a vector alternative. Otherwise, return false
267 /// and if one of the extracts should be transformed to a shufflevector, set
268 /// \p ConvertToShuffle to that extract instruction.
269 bool VectorCombine::isExtractExtractCheap(ExtractElementInst *Ext0,
270  ExtractElementInst *Ext1,
271  unsigned Opcode,
272  ExtractElementInst *&ConvertToShuffle,
273  unsigned PreferredExtractIndex) {
274  assert(isa<ConstantInt>(Ext0->getOperand(1)) &&
275  isa<ConstantInt>(Ext1->getOperand(1)) &&
276  "Expected constant extract indexes");
277  Type *ScalarTy = Ext0->getType();
278  auto *VecTy = cast<VectorType>(Ext0->getOperand(0)->getType());
279  int ScalarOpCost, VectorOpCost;
280 
281  // Get cost estimates for scalar and vector versions of the operation.
282  bool IsBinOp = Instruction::isBinaryOp(Opcode);
283  if (IsBinOp) {
284  ScalarOpCost = TTI.getArithmeticInstrCost(Opcode, ScalarTy);
285  VectorOpCost = TTI.getArithmeticInstrCost(Opcode, VecTy);
286  } else {
287  assert((Opcode == Instruction::ICmp || Opcode == Instruction::FCmp) &&
288  "Expected a compare");
289  ScalarOpCost = TTI.getCmpSelInstrCost(Opcode, ScalarTy,
290  CmpInst::makeCmpResultType(ScalarTy));
291  VectorOpCost = TTI.getCmpSelInstrCost(Opcode, VecTy,
293  }
294 
295  // Get cost estimates for the extract elements. These costs will factor into
296  // both sequences.
297  unsigned Ext0Index = cast<ConstantInt>(Ext0->getOperand(1))->getZExtValue();
298  unsigned Ext1Index = cast<ConstantInt>(Ext1->getOperand(1))->getZExtValue();
299 
300  int Extract0Cost =
301  TTI.getVectorInstrCost(Instruction::ExtractElement, VecTy, Ext0Index);
302  int Extract1Cost =
303  TTI.getVectorInstrCost(Instruction::ExtractElement, VecTy, Ext1Index);
304 
305  // A more expensive extract will always be replaced by a splat shuffle.
306  // For example, if Ext0 is more expensive:
307  // opcode (extelt V0, Ext0), (ext V1, Ext1) -->
308  // extelt (opcode (splat V0, Ext0), V1), Ext1
309  // TODO: Evaluate whether that always results in lowest cost. Alternatively,
310  // check the cost of creating a broadcast shuffle and shuffling both
311  // operands to element 0.
312  int CheapExtractCost = std::min(Extract0Cost, Extract1Cost);
313 
314  // Extra uses of the extracts mean that we include those costs in the
315  // vector total because those instructions will not be eliminated.
316  int OldCost, NewCost;
317  if (Ext0->getOperand(0) == Ext1->getOperand(0) && Ext0Index == Ext1Index) {
318  // Handle a special case. If the 2 extracts are identical, adjust the
319  // formulas to account for that. The extra use charge allows for either the
320  // CSE'd pattern or an unoptimized form with identical values:
321  // opcode (extelt V, C), (extelt V, C) --> extelt (opcode V, V), C
322  bool HasUseTax = Ext0 == Ext1 ? !Ext0->hasNUses(2)
323  : !Ext0->hasOneUse() || !Ext1->hasOneUse();
324  OldCost = CheapExtractCost + ScalarOpCost;
325  NewCost = VectorOpCost + CheapExtractCost + HasUseTax * CheapExtractCost;
326  } else {
327  // Handle the general case. Each extract is actually a different value:
328  // opcode (extelt V0, C0), (extelt V1, C1) --> extelt (opcode V0, V1), C
329  OldCost = Extract0Cost + Extract1Cost + ScalarOpCost;
330  NewCost = VectorOpCost + CheapExtractCost +
331  !Ext0->hasOneUse() * Extract0Cost +
332  !Ext1->hasOneUse() * Extract1Cost;
333  }
334 
335  ConvertToShuffle = getShuffleExtract(Ext0, Ext1, PreferredExtractIndex);
336  if (ConvertToShuffle) {
337  if (IsBinOp && DisableBinopExtractShuffle)
338  return true;
339 
340  // If we are extracting from 2 different indexes, then one operand must be
341  // shuffled before performing the vector operation. The shuffle mask is
342  // undefined except for 1 lane that is being translated to the remaining
343  // extraction lane. Therefore, it is a splat shuffle. Ex:
344  // ShufMask = { undef, undef, 0, undef }
345  // TODO: The cost model has an option for a "broadcast" shuffle
346  // (splat-from-element-0), but no option for a more general splat.
347  NewCost +=
349  }
350 
351  // Aggressively form a vector op if the cost is equal because the transform
352  // may enable further optimization.
353  // Codegen can reverse this transform (scalarize) if it was not profitable.
354  return OldCost < NewCost;
355 }
356 
357 /// Create a shuffle that translates (shifts) 1 element from the input vector
358 /// to a new element location.
359 static Value *createShiftShuffle(Value *Vec, unsigned OldIndex,
360  unsigned NewIndex, IRBuilder<> &Builder) {
361  // The shuffle mask is undefined except for 1 lane that is being translated
362  // to the new element index. Example for OldIndex == 2 and NewIndex == 0:
363  // ShufMask = { 2, undef, undef, undef }
364  auto *VecTy = cast<FixedVectorType>(Vec->getType());
365  SmallVector<int, 32> ShufMask(VecTy->getNumElements(), UndefMaskElem);
366  ShufMask[NewIndex] = OldIndex;
367  return Builder.CreateShuffleVector(Vec, ShufMask, "shift");
368 }
369 
370 /// Given an extract element instruction with constant index operand, shuffle
371 /// the source vector (shift the scalar element) to a NewIndex for extraction.
372 /// Return null if the input can be constant folded, so that we are not creating
373 /// unnecessary instructions.
375  unsigned NewIndex,
376  IRBuilder<> &Builder) {
377  // If the extract can be constant-folded, this code is unsimplified. Defer
378  // to other passes to handle that.
379  Value *X = ExtElt->getVectorOperand();
380  Value *C = ExtElt->getIndexOperand();
381  assert(isa<ConstantInt>(C) && "Expected a constant index operand");
382  if (isa<Constant>(X))
383  return nullptr;
384 
385  Value *Shuf = createShiftShuffle(X, cast<ConstantInt>(C)->getZExtValue(),
386  NewIndex, Builder);
387  return cast<ExtractElementInst>(Builder.CreateExtractElement(Shuf, NewIndex));
388 }
389 
390 /// Try to reduce extract element costs by converting scalar compares to vector
391 /// compares followed by extract.
392 /// cmp (ext0 V0, C), (ext1 V1, C)
393 void VectorCombine::foldExtExtCmp(ExtractElementInst *Ext0,
394  ExtractElementInst *Ext1, Instruction &I) {
395  assert(isa<CmpInst>(&I) && "Expected a compare");
396  assert(cast<ConstantInt>(Ext0->getIndexOperand())->getZExtValue() ==
397  cast<ConstantInt>(Ext1->getIndexOperand())->getZExtValue() &&
398  "Expected matching constant extract indexes");
399 
400  // cmp Pred (extelt V0, C), (extelt V1, C) --> extelt (cmp Pred V0, V1), C
401  ++NumVecCmp;
402  CmpInst::Predicate Pred = cast<CmpInst>(&I)->getPredicate();
403  Value *V0 = Ext0->getVectorOperand(), *V1 = Ext1->getVectorOperand();
404  Value *VecCmp = Builder.CreateCmp(Pred, V0, V1);
405  Value *NewExt = Builder.CreateExtractElement(VecCmp, Ext0->getIndexOperand());
406  replaceValue(I, *NewExt);
407 }
408 
409 /// Try to reduce extract element costs by converting scalar binops to vector
410 /// binops followed by extract.
411 /// bo (ext0 V0, C), (ext1 V1, C)
412 void VectorCombine::foldExtExtBinop(ExtractElementInst *Ext0,
413  ExtractElementInst *Ext1, Instruction &I) {
414  assert(isa<BinaryOperator>(&I) && "Expected a binary operator");
415  assert(cast<ConstantInt>(Ext0->getIndexOperand())->getZExtValue() ==
416  cast<ConstantInt>(Ext1->getIndexOperand())->getZExtValue() &&
417  "Expected matching constant extract indexes");
418 
419  // bo (extelt V0, C), (extelt V1, C) --> extelt (bo V0, V1), C
420  ++NumVecBO;
421  Value *V0 = Ext0->getVectorOperand(), *V1 = Ext1->getVectorOperand();
422  Value *VecBO =
423  Builder.CreateBinOp(cast<BinaryOperator>(&I)->getOpcode(), V0, V1);
424 
425  // All IR flags are safe to back-propagate because any potential poison
426  // created in unused vector elements is discarded by the extract.
427  if (auto *VecBOInst = dyn_cast<Instruction>(VecBO))
428  VecBOInst->copyIRFlags(&I);
429 
430  Value *NewExt = Builder.CreateExtractElement(VecBO, Ext0->getIndexOperand());
431  replaceValue(I, *NewExt);
432 }
433 
434 /// Match an instruction with extracted vector operands.
435 bool VectorCombine::foldExtractExtract(Instruction &I) {
436  // It is not safe to transform things like div, urem, etc. because we may
437  // create undefined behavior when executing those on unknown vector elements.
439  return false;
440 
441  Instruction *I0, *I1;
443  if (!match(&I, m_Cmp(Pred, m_Instruction(I0), m_Instruction(I1))) &&
444  !match(&I, m_BinOp(m_Instruction(I0), m_Instruction(I1))))
445  return false;
446 
447  Value *V0, *V1;
448  uint64_t C0, C1;
449  if (!match(I0, m_ExtractElt(m_Value(V0), m_ConstantInt(C0))) ||
450  !match(I1, m_ExtractElt(m_Value(V1), m_ConstantInt(C1))) ||
451  V0->getType() != V1->getType())
452  return false;
453 
454  // If the scalar value 'I' is going to be re-inserted into a vector, then try
455  // to create an extract to that same element. The extract/insert can be
456  // reduced to a "select shuffle".
457  // TODO: If we add a larger pattern match that starts from an insert, this
458  // probably becomes unnecessary.
459  auto *Ext0 = cast<ExtractElementInst>(I0);
460  auto *Ext1 = cast<ExtractElementInst>(I1);
461  uint64_t InsertIndex = InvalidIndex;
462  if (I.hasOneUse())
463  match(I.user_back(),
464  m_InsertElt(m_Value(), m_Value(), m_ConstantInt(InsertIndex)));
465 
466  ExtractElementInst *ExtractToChange;
467  if (isExtractExtractCheap(Ext0, Ext1, I.getOpcode(), ExtractToChange,
468  InsertIndex))
469  return false;
470 
471  if (ExtractToChange) {
472  unsigned CheapExtractIdx = ExtractToChange == Ext0 ? C1 : C0;
473  ExtractElementInst *NewExtract =
474  translateExtract(ExtractToChange, CheapExtractIdx, Builder);
475  if (!NewExtract)
476  return false;
477  if (ExtractToChange == Ext0)
478  Ext0 = NewExtract;
479  else
480  Ext1 = NewExtract;
481  }
482 
483  if (Pred != CmpInst::BAD_ICMP_PREDICATE)
484  foldExtExtCmp(Ext0, Ext1, I);
485  else
486  foldExtExtBinop(Ext0, Ext1, I);
487 
488  return true;
489 }
490 
491 /// If this is a bitcast of a shuffle, try to bitcast the source vector to the
492 /// destination type followed by shuffle. This can enable further transforms by
493 /// moving bitcasts or shuffles together.
494 bool VectorCombine::foldBitcastShuf(Instruction &I) {
495  Value *V;
497  if (!match(&I, m_BitCast(
499  return false;
500 
501  // 1) Do not fold bitcast shuffle for scalable type. First, shuffle cost for
502  // scalable type is unknown; Second, we cannot reason if the narrowed shuffle
503  // mask for scalable type is a splat or not.
504  // 2) Disallow non-vector casts and length-changing shuffles.
505  // TODO: We could allow any shuffle.
506  auto *DestTy = dyn_cast<FixedVectorType>(I.getType());
507  auto *SrcTy = dyn_cast<FixedVectorType>(V->getType());
508  if (!SrcTy || !DestTy || I.getOperand(0)->getType() != SrcTy)
509  return false;
510 
511  // The new shuffle must not cost more than the old shuffle. The bitcast is
512  // moved ahead of the shuffle, so assume that it has the same cost as before.
515  return false;
516 
517  unsigned DestNumElts = DestTy->getNumElements();
518  unsigned SrcNumElts = SrcTy->getNumElements();
519  SmallVector<int, 16> NewMask;
520  if (SrcNumElts <= DestNumElts) {
521  // The bitcast is from wide to narrow/equal elements. The shuffle mask can
522  // always be expanded to the equivalent form choosing narrower elements.
523  assert(DestNumElts % SrcNumElts == 0 && "Unexpected shuffle mask");
524  unsigned ScaleFactor = DestNumElts / SrcNumElts;
525  narrowShuffleMaskElts(ScaleFactor, Mask, NewMask);
526  } else {
527  // The bitcast is from narrow elements to wide elements. The shuffle mask
528  // must choose consecutive elements to allow casting first.
529  assert(SrcNumElts % DestNumElts == 0 && "Unexpected shuffle mask");
530  unsigned ScaleFactor = SrcNumElts / DestNumElts;
531  if (!widenShuffleMaskElts(ScaleFactor, Mask, NewMask))
532  return false;
533  }
534  // bitcast (shuf V, MaskC) --> shuf (bitcast V), MaskC'
535  ++NumShufOfBitcast;
536  Value *CastV = Builder.CreateBitCast(V, DestTy);
537  Value *Shuf = Builder.CreateShuffleVector(CastV, NewMask);
538  replaceValue(I, *Shuf);
539  return true;
540 }
541 
542 /// Match a vector binop or compare instruction with at least one inserted
543 /// scalar operand and convert to scalar binop/cmp followed by insertelement.
544 bool VectorCombine::scalarizeBinopOrCmp(Instruction &I) {
546  Value *Ins0, *Ins1;
547  if (!match(&I, m_BinOp(m_Value(Ins0), m_Value(Ins1))) &&
548  !match(&I, m_Cmp(Pred, m_Value(Ins0), m_Value(Ins1))))
549  return false;
550 
551  // Do not convert the vector condition of a vector select into a scalar
552  // condition. That may cause problems for codegen because of differences in
553  // boolean formats and register-file transfers.
554  // TODO: Can we account for that in the cost model?
555  bool IsCmp = Pred != CmpInst::Predicate::BAD_ICMP_PREDICATE;
556  if (IsCmp)
557  for (User *U : I.users())
558  if (match(U, m_Select(m_Specific(&I), m_Value(), m_Value())))
559  return false;
560 
561  // Match against one or both scalar values being inserted into constant
562  // vectors:
563  // vec_op VecC0, (inselt VecC1, V1, Index)
564  // vec_op (inselt VecC0, V0, Index), VecC1
565  // vec_op (inselt VecC0, V0, Index), (inselt VecC1, V1, Index)
566  // TODO: Deal with mismatched index constants and variable indexes?
567  Constant *VecC0 = nullptr, *VecC1 = nullptr;
568  Value *V0 = nullptr, *V1 = nullptr;
569  uint64_t Index0 = 0, Index1 = 0;
570  if (!match(Ins0, m_InsertElt(m_Constant(VecC0), m_Value(V0),
571  m_ConstantInt(Index0))) &&
572  !match(Ins0, m_Constant(VecC0)))
573  return false;
574  if (!match(Ins1, m_InsertElt(m_Constant(VecC1), m_Value(V1),
575  m_ConstantInt(Index1))) &&
576  !match(Ins1, m_Constant(VecC1)))
577  return false;
578 
579  bool IsConst0 = !V0;
580  bool IsConst1 = !V1;
581  if (IsConst0 && IsConst1)
582  return false;
583  if (!IsConst0 && !IsConst1 && Index0 != Index1)
584  return false;
585 
586  // Bail for single insertion if it is a load.
587  // TODO: Handle this once getVectorInstrCost can cost for load/stores.
588  auto *I0 = dyn_cast_or_null<Instruction>(V0);
589  auto *I1 = dyn_cast_or_null<Instruction>(V1);
590  if ((IsConst0 && I1 && I1->mayReadFromMemory()) ||
591  (IsConst1 && I0 && I0->mayReadFromMemory()))
592  return false;
593 
594  uint64_t Index = IsConst0 ? Index1 : Index0;
595  Type *ScalarTy = IsConst0 ? V1->getType() : V0->getType();
596  Type *VecTy = I.getType();
597  assert(VecTy->isVectorTy() &&
598  (IsConst0 || IsConst1 || V0->getType() == V1->getType()) &&
599  (ScalarTy->isIntegerTy() || ScalarTy->isFloatingPointTy() ||
600  ScalarTy->isPointerTy()) &&
601  "Unexpected types for insert element into binop or cmp");
602 
603  unsigned Opcode = I.getOpcode();
604  int ScalarOpCost, VectorOpCost;
605  if (IsCmp) {
606  ScalarOpCost = TTI.getCmpSelInstrCost(Opcode, ScalarTy);
607  VectorOpCost = TTI.getCmpSelInstrCost(Opcode, VecTy);
608  } else {
609  ScalarOpCost = TTI.getArithmeticInstrCost(Opcode, ScalarTy);
610  VectorOpCost = TTI.getArithmeticInstrCost(Opcode, VecTy);
611  }
612 
613  // Get cost estimate for the insert element. This cost will factor into
614  // both sequences.
615  int InsertCost =
616  TTI.getVectorInstrCost(Instruction::InsertElement, VecTy, Index);
617  int OldCost = (IsConst0 ? 0 : InsertCost) + (IsConst1 ? 0 : InsertCost) +
618  VectorOpCost;
619  int NewCost = ScalarOpCost + InsertCost +
620  (IsConst0 ? 0 : !Ins0->hasOneUse() * InsertCost) +
621  (IsConst1 ? 0 : !Ins1->hasOneUse() * InsertCost);
622 
623  // We want to scalarize unless the vector variant actually has lower cost.
624  if (OldCost < NewCost)
625  return false;
626 
627  // vec_op (inselt VecC0, V0, Index), (inselt VecC1, V1, Index) -->
628  // inselt NewVecC, (scalar_op V0, V1), Index
629  if (IsCmp)
630  ++NumScalarCmp;
631  else
632  ++NumScalarBO;
633 
634  // For constant cases, extract the scalar element, this should constant fold.
635  if (IsConst0)
636  V0 = ConstantExpr::getExtractElement(VecC0, Builder.getInt64(Index));
637  if (IsConst1)
638  V1 = ConstantExpr::getExtractElement(VecC1, Builder.getInt64(Index));
639 
640  Value *Scalar =
641  IsCmp ? Builder.CreateCmp(Pred, V0, V1)
642  : Builder.CreateBinOp((Instruction::BinaryOps)Opcode, V0, V1);
643 
644  Scalar->setName(I.getName() + ".scalar");
645 
646  // All IR flags are safe to back-propagate. There is no potential for extra
647  // poison to be created by the scalar instruction.
648  if (auto *ScalarInst = dyn_cast<Instruction>(Scalar))
649  ScalarInst->copyIRFlags(&I);
650 
651  // Fold the vector constants in the original vectors into a new base vector.
652  Constant *NewVecC = IsCmp ? ConstantExpr::getCompare(Pred, VecC0, VecC1)
653  : ConstantExpr::get(Opcode, VecC0, VecC1);
654  Value *Insert = Builder.CreateInsertElement(NewVecC, Scalar, Index);
655  replaceValue(I, *Insert);
656  return true;
657 }
658 
659 /// Try to combine a scalar binop + 2 scalar compares of extracted elements of
660 /// a vector into vector operations followed by extract. Note: The SLP pass
661 /// may miss this pattern because of implementation problems.
662 bool VectorCombine::foldExtractedCmps(Instruction &I) {
663  // We are looking for a scalar binop of booleans.
664  // binop i1 (cmp Pred I0, C0), (cmp Pred I1, C1)
665  if (!I.isBinaryOp() || !I.getType()->isIntegerTy(1))
666  return false;
667 
668  // The compare predicates should match, and each compare should have a
669  // constant operand.
670  // TODO: Relax the one-use constraints.
671  Value *B0 = I.getOperand(0), *B1 = I.getOperand(1);
672  Instruction *I0, *I1;
673  Constant *C0, *C1;
674  CmpInst::Predicate P0, P1;
675  if (!match(B0, m_OneUse(m_Cmp(P0, m_Instruction(I0), m_Constant(C0)))) ||
676  !match(B1, m_OneUse(m_Cmp(P1, m_Instruction(I1), m_Constant(C1)))) ||
677  P0 != P1)
678  return false;
679 
680  // The compare operands must be extracts of the same vector with constant
681  // extract indexes.
682  // TODO: Relax the one-use constraints.
683  Value *X;
684  uint64_t Index0, Index1;
685  if (!match(I0, m_OneUse(m_ExtractElt(m_Value(X), m_ConstantInt(Index0)))) ||
687  return false;
688 
689  auto *Ext0 = cast<ExtractElementInst>(I0);
690  auto *Ext1 = cast<ExtractElementInst>(I1);
691  ExtractElementInst *ConvertToShuf = getShuffleExtract(Ext0, Ext1);
692  if (!ConvertToShuf)
693  return false;
694 
695  // The original scalar pattern is:
696  // binop i1 (cmp Pred (ext X, Index0), C0), (cmp Pred (ext X, Index1), C1)
697  CmpInst::Predicate Pred = P0;
698  unsigned CmpOpcode = CmpInst::isFPPredicate(Pred) ? Instruction::FCmp
699  : Instruction::ICmp;
700  auto *VecTy = dyn_cast<FixedVectorType>(X->getType());
701  if (!VecTy)
702  return false;
703 
704  int OldCost = TTI.getVectorInstrCost(Ext0->getOpcode(), VecTy, Index0);
705  OldCost += TTI.getVectorInstrCost(Ext1->getOpcode(), VecTy, Index1);
706  OldCost += TTI.getCmpSelInstrCost(CmpOpcode, I0->getType()) * 2;
707  OldCost += TTI.getArithmeticInstrCost(I.getOpcode(), I.getType());
708 
709  // The proposed vector pattern is:
710  // vcmp = cmp Pred X, VecC
711  // ext (binop vNi1 vcmp, (shuffle vcmp, Index1)), Index0
712  int CheapIndex = ConvertToShuf == Ext0 ? Index1 : Index0;
713  int ExpensiveIndex = ConvertToShuf == Ext0 ? Index0 : Index1;
714  auto *CmpTy = cast<FixedVectorType>(CmpInst::makeCmpResultType(X->getType()));
715  int NewCost = TTI.getCmpSelInstrCost(CmpOpcode, X->getType());
716  NewCost +=
718  NewCost += TTI.getArithmeticInstrCost(I.getOpcode(), CmpTy);
719  NewCost += TTI.getVectorInstrCost(Ext0->getOpcode(), CmpTy, CheapIndex);
720 
721  // Aggressively form vector ops if the cost is equal because the transform
722  // may enable further optimization.
723  // Codegen can reverse this transform (scalarize) if it was not profitable.
724  if (OldCost < NewCost)
725  return false;
726 
727  // Create a vector constant from the 2 scalar constants.
728  SmallVector<Constant *, 32> CmpC(VecTy->getNumElements(),
729  UndefValue::get(VecTy->getElementType()));
730  CmpC[Index0] = C0;
731  CmpC[Index1] = C1;
732  Value *VCmp = Builder.CreateCmp(Pred, X, ConstantVector::get(CmpC));
733 
734  Value *Shuf = createShiftShuffle(VCmp, ExpensiveIndex, CheapIndex, Builder);
735  Value *VecLogic = Builder.CreateBinOp(cast<BinaryOperator>(I).getOpcode(),
736  VCmp, Shuf);
737  Value *NewExt = Builder.CreateExtractElement(VecLogic, CheapIndex);
738  replaceValue(I, *NewExt);
739  ++NumVecCmpBO;
740  return true;
741 }
742 
743 /// This is the entry point for all transforms. Pass manager differences are
744 /// handled in the callers of this function.
745 bool VectorCombine::run() {
747  return false;
748 
749  // Don't attempt vectorization if the target does not support vectors.
750  if (!TTI.getNumberOfRegisters(TTI.getRegisterClassForType(/*Vector*/ true)))
751  return false;
752 
753  bool MadeChange = false;
754  for (BasicBlock &BB : F) {
755  // Ignore unreachable basic blocks.
756  if (!DT.isReachableFromEntry(&BB))
757  continue;
758  // Do not delete instructions under here and invalidate the iterator.
759  // Walk the block forwards to enable simple iterative chains of transforms.
760  // TODO: It could be more efficient to remove dead instructions
761  // iteratively in this loop rather than waiting until the end.
762  for (Instruction &I : BB) {
763  if (isa<DbgInfoIntrinsic>(I))
764  continue;
765  Builder.SetInsertPoint(&I);
766  MadeChange |= vectorizeLoadInsert(I);
767  MadeChange |= foldExtractExtract(I);
768  MadeChange |= foldBitcastShuf(I);
769  MadeChange |= scalarizeBinopOrCmp(I);
770  MadeChange |= foldExtractedCmps(I);
771  }
772  }
773 
774  // We're done with transforms, so remove dead instructions.
775  if (MadeChange)
776  for (BasicBlock &BB : F)
778 
779  return MadeChange;
780 }
781 
782 // Pass manager boilerplate below here.
783 
784 namespace {
785 class VectorCombineLegacyPass : public FunctionPass {
786 public:
787  static char ID;
788  VectorCombineLegacyPass() : FunctionPass(ID) {
790  }
791 
792  void getAnalysisUsage(AnalysisUsage &AU) const override {
795  AU.setPreservesCFG();
801  }
802 
803  bool runOnFunction(Function &F) override {
804  if (skipFunction(F))
805  return false;
806  auto &TTI = getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
807  auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
808  VectorCombine Combiner(F, TTI, DT);
809  return Combiner.run();
810  }
811 };
812 } // namespace
813 
815 INITIALIZE_PASS_BEGIN(VectorCombineLegacyPass, "vector-combine",
816  "Optimize scalar/vector ops", false,
817  false)
819 INITIALIZE_PASS_END(VectorCombineLegacyPass, "vector-combine",
820  "Optimize scalar/vector ops", false, false)
822  return new VectorCombineLegacyPass();
823 }
824 
829  VectorCombine Combiner(F, TTI, DT);
830  if (!Combiner.run())
831  return PreservedAnalyses::all();
833  PA.preserveSet<CFGAnalyses>();
834  PA.preserve<GlobalsAA>();
835  PA.preserve<AAManager>();
836  PA.preserve<BasicAA>();
837  return PA;
838 }
Legacy wrapper pass to provide the GlobalsAAResult object.
Pass interface - Implemented by all 'passes'.
Definition: Pass.h:91
bool isFPPredicate() const
Definition: InstrTypes.h:816
uint64_t CallInst * C
int getArithmeticInstrCost(unsigned Opcode, Type *Ty, TTI::TargetCostKind CostKind=TTI::TCK_RecipThroughput, OperandValueKind Opd1Info=OK_AnyValue, OperandValueKind Opd2Info=OK_AnyValue, OperandValueProperties Opd1PropInfo=OP_None, OperandValueProperties Opd2PropInfo=OP_None, ArrayRef< const Value * > Args=ArrayRef< const Value * >(), const Instruction *CxtI=nullptr) const
This is an approximation of reciprocal throughput of a math/logic op.
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:111
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
Definition: PatternMatch.h:76
static const unsigned InvalidIndex
class_match< UndefValue > m_Undef()
Match an arbitrary undef constant.
Definition: PatternMatch.h:92
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
Pass * createVectorCombinePass()
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
class_match< CmpInst > m_Cmp()
Matches any compare instruction and ignore it.
Definition: PatternMatch.h:89
TargetTransformInfo TTI
ThreeOps_match< Val_t, Elt_t, Idx_t, Instruction::InsertElement > m_InsertElt(const Val_t &Val, const Elt_t &Elt, const Idx_t &Idx)
Matches InsertElementInst.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
ThreeOps_match< Cond, LHS, RHS, Instruction::Select > m_Select(const Cond &C, const LHS &L, const RHS &R)
Matches SelectInst.
static Type * makeCmpResultType(Type *opnd_type)
Create a result type for fcmp/icmp.
Definition: InstrTypes.h:1034
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:785
This class represents lattice values for constants.
Definition: AllocatorList.h:23
DEBUG_TYPE to vector
bool widenShuffleMaskElts(int Scale, ArrayRef< int > Mask, SmallVectorImpl< int > &ScaledMask)
Try to transform a shuffle mask by replacing elements with the scaled index for an equivalent mask of...
This is the interface for a simple mod/ref and alias analysis over globals.
Align getPointerAlignment(const DataLayout &DL) const
Returns an alignment of the pointer value.
Definition: Value.cpp:795
class_match< Constant > m_Constant()
Match an arbitrary Constant and ignore it.
Definition: PatternMatch.h:98
constexpr int UndefMaskElem
unsigned getScalarizationOverhead(VectorType *Ty, const APInt &DemandedElts, bool Insert, bool Extract) const
Estimate the overhead of scalarizing an instruction.
Analysis pass providing the TargetTransformInfo.
static Constant * getExtractElement(Constant *Vec, Constant *Idx, Type *OnlyIfReducedTy=nullptr)
Definition: Constants.cpp:2492
bool mustSuppressSpeculation(const LoadInst &LI)
Return true if speculation of the given load must be suppressed to avoid ordering or interfering with...
INITIALIZE_PASS_BEGIN(VectorCombineLegacyPass, "vector-combine", "Optimize scalar/vector ops", false, false) INITIALIZE_PASS_END(VectorCombineLegacyPass
STATISTIC(NumFunctions, "Total number of functions")
bool SimplifyInstructionsInBlock(BasicBlock *BB, const TargetLibraryInfo *TLI=nullptr)
Scan the specified basic block and try to simplify any instructions in it and recursively delete dead...
Definition: Local.cpp:674
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:249
F(f)
unsigned getPointerAddressSpace() const
Get the address space of this pointer or pointer vector type.
Definition: DerivedTypes.h:711
static Constant * getCompare(unsigned short pred, Constant *C1, Constant *C2, bool OnlyIfReduced=false)
Return an ICmp or FCmp comparison operator constant expression.
Definition: Constants.cpp:2338
bool isVectorTy() const
True if this is an instance of VectorType.
Definition: Type.h:235
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:722
cst_pred_ty< is_zero_int > m_ZeroInt()
Match an integer 0 or a vector with all elements equal to 0.
Definition: PatternMatch.h:478
bool match(Val *V, const Pattern &P)
Definition: PatternMatch.h:49
AnalysisUsage & addRequired()
static cl::opt< bool > DisableBinopExtractShuffle("disable-binop-extract-shuffle", cl::init(false), cl::Hidden, cl::desc("Disable binop extract to shuffle transforms"))
unsigned getRegisterClassForType(bool Vector, Type *Ty=nullptr) const
bool isFloatingPointTy() const
Return true if this is one of the six floating-point types.
Definition: Type.h:163
static Constant * get(ArrayRef< Constant * > V)
Definition: Constants.cpp:1326
bool isIntegerTy() const
True if this is an instance of IntegerType.
Definition: Type.h:202
std::underlying_type_t< E > Mask()
Get a bitmask with 1s in all places up to the high-order bit of E's largest value.
Definition: BitmaskEnum.h:80
static Value * createShiftShuffle(Value *Vec, unsigned OldIndex, unsigned NewIndex, IRBuilder<> &Builder)
Create a shuffle that translates (shifts) 1 element from the input vector to a new element location.
Align commonAlignment(Align A, Align B)
Returns the alignment that satisfies both alignments.
Definition: Alignment.h:221
A constant value that is initialized with an expression using other constant values.
Definition: Constants.h:936
virtual void getAnalysisUsage(AnalysisUsage &) const
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
Definition: Pass.cpp:93
unsigned getMinVectorRegisterBitWidth() const
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:246
class_match< ConstantInt > m_ConstantInt()
Match an arbitrary ConstantInt and ignore it.
Definition: PatternMatch.h:101
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
Definition: Instruction.h:160
int getShuffleCost(ShuffleKind Kind, VectorType *Tp, int Index=0, VectorType *SubTp=nullptr) const
const Value * stripAndAccumulateInBoundsConstantOffsets(const DataLayout &DL, APInt &Offset) const
This is a wrapper around stripAndAccumulateConstantOffsets with the in-bounds requirement set to fals...
Definition: Value.h:718
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:523
int getVectorInstrCost(unsigned Opcode, Type *Val, unsigned Index=-1) const
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:151
Value * getOperand(unsigned i) const
Definition: User.h:169
OneUse_match< T > m_OneUse(const T &SubPattern)
Definition: PatternMatch.h:67
static bool runOnFunction(Function &F, bool PostInlining)
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:427
void initializeVectorCombineLegacyPassPass(PassRegistry &)
Wrapper pass for TargetTransformInfo.
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:155
bool hasNUses(unsigned N) const
Return true if this Value has exactly N uses.
Definition: Value.cpp:146
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
TypeSize getPrimitiveSizeInBits() const LLVM_READONLY
Return the basic size of this type if it is a primitive type.
Definition: Type.cpp:122
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:46
CastClass_match< OpTy, Instruction::BitCast > m_BitCast(const OpTy &Op)
Matches BitCast.
This is an important base class in LLVM.
Definition: Constant.h:41
bool isPointerTy() const
True if this is an instance of PointerType.
Definition: Type.h:229
A manager for alias analyses.
static APInt getOneBitSet(unsigned numBits, unsigned BitNo)
Return an APInt with exactly one bit set in the result.
Definition: APInt.h:593
specificval_ty m_Specific(const Value *V)
Match if we have a specific specified value.
Definition: PatternMatch.h:754
Represent the analysis usage information of a pass.
Expected< ExpressionValue > min(const ExpressionValue &Lhs, const ExpressionValue &Rhs)
Definition: FileCheck.cpp:339
Analysis pass providing a never-invalidated alias analysis result.
bool isBinaryOp() const
Definition: Instruction.h:165
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:298
class_match< BinaryOperator > m_BinOp()
Match an arbitrary binary operation and ignore it.
Definition: PatternMatch.h:84
assume Assume Builder
uint64_t Align
static UndefValue * get(Type *T)
Static factory methods - Return an 'undef' object of the specified type.
Definition: Constants.cpp:1742
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:161
TwoOps_match< Val_t, Idx_t, Instruction::ExtractElement > m_ExtractElt(const Val_t &Val, const Idx_t &Idx)
Matches ExtractElementInst.
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
This struct is a compact representation of a valid (non-zero power of two) alignment.
Definition: Alignment.h:39
unsigned getNumberOfRegisters(unsigned ClassID) const
uint64_t Offset
Align max(MaybeAlign Lhs, Align Rhs)
Definition: Alignment.h:350
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1116
uint32_t Index
void setPreservesCFG()
This function should be called by the pass, iff they do not:
Definition: Pass.cpp:253
int getMemoryOpCost(unsigned Opcode, Type *Src, Align Alignment, unsigned AddressSpace, TTI::TargetCostKind CostKind=TTI::TCK_RecipThroughput, const Instruction *I=nullptr) const
Class for arbitrary precision integers.
Definition: APInt.h:70
static cl::opt< bool > DisableVectorCombine("disable-vector-combine", cl::init(false), cl::Hidden, cl::desc("Disable all vector combine transforms"))
void narrowShuffleMaskElts(int Scale, ArrayRef< int > Mask, SmallVectorImpl< int > &ScaledMask)
Replace each shuffle mask index with the scaled sequential indices for an equivalent mask of narrowed...
Represents analyses that only rely on functions' control flow.
Definition: PassManager.h:116
vector combine
Analysis pass providing a never-invalidated alias analysis result.
PreservedAnalyses run(Function &F, FunctionAnalysisManager &)
static Optional< unsigned > getOpcode(ArrayRef< VPValue * > Values)
Returns the opcode of Values or ~0 if they do not all agree.
Definition: VPlanSLP.cpp:197
static VectorType * get(Type *ElementType, ElementCount EC)
This static method is the primary way to construct an VectorType.
Definition: Type.cpp:610
void preserveSet()
Mark an analysis set as preserved.
Definition: PassManager.h:191
#define I(x, y, z)
Definition: MD5.cpp:59
bool mayReadFromMemory() const
Return true if this instruction may read memory.
This instruction extracts a single (scalar) element from a VectorType value.
void preserve()
Mark an analysis as preserved.
Definition: PassManager.h:176
static ExtractElementInst * translateExtract(ExtractElementInst *ExtElt, unsigned NewIndex, IRBuilder<> &Builder)
Given an extract element instruction with constant index operand, shuffle the source vector (shift th...
int getCmpSelInstrCost(unsigned Opcode, Type *ValTy, Type *CondTy=nullptr, CmpInst::Predicate VecPred=CmpInst::BAD_ICMP_PREDICATE, TTI::TargetCostKind CostKind=TTI::TCK_RecipThroughput, const Instruction *I=nullptr) const
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
bool isSafeToSpeculativelyExecute(const Value *V, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr)
Return true if the instruction does not have any effects besides calculating the result and does not ...
bool isSafeToLoadUnconditionally(Value *V, Align Alignment, APInt &Size, const DataLayout &DL, Instruction *ScanFrom=nullptr, const DominatorTree *DT=nullptr)
Return true if we know that executing a load from this value cannot trap.
Definition: Loads.cpp:298
LLVM Value Representation.
Definition: Value.h:75
TwoOps_match< V1_t, V2_t, Instruction::ShuffleVector > m_Shuffle(const V1_t &v1, const V2_t &v2)
Matches ShuffleVectorInst independently of mask value.
bool hasOneUse() const
Return true if there is exactly one use of this value.
Definition: Value.h:437
This is the interface for LLVM's primary stateless and local alias analysis.
A container for analyses that lazily runs them and caches their results.
vector Optimize scalar vector ops
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:278
This pass exposes codegen information to IR-level passes.
static void replaceValue(Value &Old, Value &New)
A wrapper pass to provide the legacy pass manager access to a suitably prepared AAResults object.
bind_ty< Instruction > m_Instruction(Instruction *&I)
Match an instruction, capturing it if we match.
Definition: PatternMatch.h:704
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Legacy wrapper pass to provide the BasicAAResult object.
Shuffle elements of single source vector with any shuffle mask.