LLVM 19.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/DenseMap.h"
17#include "llvm/ADT/STLExtras.h"
18#include "llvm/ADT/ScopeExit.h"
19#include "llvm/ADT/Statistic.h"
23#include "llvm/Analysis/Loads.h"
27#include "llvm/IR/Dominators.h"
28#include "llvm/IR/Function.h"
29#include "llvm/IR/IRBuilder.h"
34#include <numeric>
35#include <queue>
36
37#define DEBUG_TYPE "vector-combine"
39
40using namespace llvm;
41using namespace llvm::PatternMatch;
42
43STATISTIC(NumVecLoad, "Number of vector loads formed");
44STATISTIC(NumVecCmp, "Number of vector compares formed");
45STATISTIC(NumVecBO, "Number of vector binops formed");
46STATISTIC(NumVecCmpBO, "Number of vector compare + binop formed");
47STATISTIC(NumShufOfBitcast, "Number of shuffles moved after bitcast");
48STATISTIC(NumScalarBO, "Number of scalar binops formed");
49STATISTIC(NumScalarCmp, "Number of scalar compares formed");
50
52 "disable-vector-combine", cl::init(false), cl::Hidden,
53 cl::desc("Disable all vector combine transforms"));
54
56 "disable-binop-extract-shuffle", cl::init(false), cl::Hidden,
57 cl::desc("Disable binop extract to shuffle transforms"));
58
60 "vector-combine-max-scan-instrs", cl::init(30), cl::Hidden,
61 cl::desc("Max number of instructions to scan for vector combining."));
62
63static const unsigned InvalidIndex = std::numeric_limits<unsigned>::max();
64
65namespace {
66class VectorCombine {
67public:
68 VectorCombine(Function &F, const TargetTransformInfo &TTI,
69 const DominatorTree &DT, AAResults &AA, AssumptionCache &AC,
70 const DataLayout *DL, bool TryEarlyFoldsOnly)
71 : F(F), Builder(F.getContext()), TTI(TTI), DT(DT), AA(AA), AC(AC), DL(DL),
72 TryEarlyFoldsOnly(TryEarlyFoldsOnly) {}
73
74 bool run();
75
76private:
77 Function &F;
78 IRBuilder<> Builder;
80 const DominatorTree &DT;
81 AAResults &AA;
83 const DataLayout *DL;
84
85 /// If true, only perform beneficial early IR transforms. Do not introduce new
86 /// vector operations.
87 bool TryEarlyFoldsOnly;
88
89 InstructionWorklist Worklist;
90
91 // TODO: Direct calls from the top-level "run" loop use a plain "Instruction"
92 // parameter. That should be updated to specific sub-classes because the
93 // run loop was changed to dispatch on opcode.
94 bool vectorizeLoadInsert(Instruction &I);
95 bool widenSubvectorLoad(Instruction &I);
96 ExtractElementInst *getShuffleExtract(ExtractElementInst *Ext0,
98 unsigned PreferredExtractIndex) const;
99 bool isExtractExtractCheap(ExtractElementInst *Ext0, ExtractElementInst *Ext1,
100 const Instruction &I,
101 ExtractElementInst *&ConvertToShuffle,
102 unsigned PreferredExtractIndex);
103 void foldExtExtCmp(ExtractElementInst *Ext0, ExtractElementInst *Ext1,
104 Instruction &I);
105 void foldExtExtBinop(ExtractElementInst *Ext0, ExtractElementInst *Ext1,
106 Instruction &I);
107 bool foldExtractExtract(Instruction &I);
108 bool foldInsExtFNeg(Instruction &I);
109 bool foldBitcastShuffle(Instruction &I);
110 bool scalarizeBinopOrCmp(Instruction &I);
111 bool scalarizeVPIntrinsic(Instruction &I);
112 bool foldExtractedCmps(Instruction &I);
113 bool foldSingleElementStore(Instruction &I);
114 bool scalarizeLoadExtract(Instruction &I);
115 bool foldShuffleOfBinops(Instruction &I);
116 bool foldShuffleOfCastops(Instruction &I);
117 bool foldShuffleOfShuffles(Instruction &I);
118 bool foldShuffleToIdentity(Instruction &I);
119 bool foldShuffleFromReductions(Instruction &I);
120 bool foldTruncFromReductions(Instruction &I);
121 bool foldSelectShuffle(Instruction &I, bool FromReduction = false);
122
123 void replaceValue(Value &Old, Value &New) {
124 Old.replaceAllUsesWith(&New);
125 if (auto *NewI = dyn_cast<Instruction>(&New)) {
126 New.takeName(&Old);
127 Worklist.pushUsersToWorkList(*NewI);
128 Worklist.pushValue(NewI);
129 }
130 Worklist.pushValue(&Old);
131 }
132
134 for (Value *Op : I.operands())
135 Worklist.pushValue(Op);
136 Worklist.remove(&I);
137 I.eraseFromParent();
138 }
139};
140} // namespace
141
142/// Return the source operand of a potentially bitcasted value. If there is no
143/// bitcast, return the input value itself.
145 while (auto *BitCast = dyn_cast<BitCastInst>(V))
146 V = BitCast->getOperand(0);
147 return V;
148}
149
150static bool canWidenLoad(LoadInst *Load, const TargetTransformInfo &TTI) {
151 // Do not widen load if atomic/volatile or under asan/hwasan/memtag/tsan.
152 // The widened load may load data from dirty regions or create data races
153 // non-existent in the source.
154 if (!Load || !Load->isSimple() || !Load->hasOneUse() ||
155 Load->getFunction()->hasFnAttribute(Attribute::SanitizeMemTag) ||
157 return false;
158
159 // We are potentially transforming byte-sized (8-bit) memory accesses, so make
160 // sure we have all of our type-based constraints in place for this target.
161 Type *ScalarTy = Load->getType()->getScalarType();
162 uint64_t ScalarSize = ScalarTy->getPrimitiveSizeInBits();
163 unsigned MinVectorSize = TTI.getMinVectorRegisterBitWidth();
164 if (!ScalarSize || !MinVectorSize || MinVectorSize % ScalarSize != 0 ||
165 ScalarSize % 8 != 0)
166 return false;
167
168 return true;
169}
170
171bool VectorCombine::vectorizeLoadInsert(Instruction &I) {
172 // Match insert into fixed vector of scalar value.
173 // TODO: Handle non-zero insert index.
174 Value *Scalar;
175 if (!match(&I, m_InsertElt(m_Undef(), m_Value(Scalar), m_ZeroInt())) ||
176 !Scalar->hasOneUse())
177 return false;
178
179 // Optionally match an extract from another vector.
180 Value *X;
181 bool HasExtract = match(Scalar, m_ExtractElt(m_Value(X), m_ZeroInt()));
182 if (!HasExtract)
183 X = Scalar;
184
185 auto *Load = dyn_cast<LoadInst>(X);
186 if (!canWidenLoad(Load, TTI))
187 return false;
188
189 Type *ScalarTy = Scalar->getType();
190 uint64_t ScalarSize = ScalarTy->getPrimitiveSizeInBits();
191 unsigned MinVectorSize = TTI.getMinVectorRegisterBitWidth();
192
193 // Check safety of replacing the scalar load with a larger vector load.
194 // We use minimal alignment (maximum flexibility) because we only care about
195 // the dereferenceable region. When calculating cost and creating a new op,
196 // we may use a larger value based on alignment attributes.
197 Value *SrcPtr = Load->getPointerOperand()->stripPointerCasts();
198 assert(isa<PointerType>(SrcPtr->getType()) && "Expected a pointer type");
199
200 unsigned MinVecNumElts = MinVectorSize / ScalarSize;
201 auto *MinVecTy = VectorType::get(ScalarTy, MinVecNumElts, false);
202 unsigned OffsetEltIndex = 0;
203 Align Alignment = Load->getAlign();
204 if (!isSafeToLoadUnconditionally(SrcPtr, MinVecTy, Align(1), *DL, Load, &AC,
205 &DT)) {
206 // It is not safe to load directly from the pointer, but we can still peek
207 // through gep offsets and check if it safe to load from a base address with
208 // updated alignment. If it is, we can shuffle the element(s) into place
209 // after loading.
210 unsigned OffsetBitWidth = DL->getIndexTypeSizeInBits(SrcPtr->getType());
211 APInt Offset(OffsetBitWidth, 0);
213
214 // We want to shuffle the result down from a high element of a vector, so
215 // the offset must be positive.
216 if (Offset.isNegative())
217 return false;
218
219 // The offset must be a multiple of the scalar element to shuffle cleanly
220 // in the element's size.
221 uint64_t ScalarSizeInBytes = ScalarSize / 8;
222 if (Offset.urem(ScalarSizeInBytes) != 0)
223 return false;
224
225 // If we load MinVecNumElts, will our target element still be loaded?
226 OffsetEltIndex = Offset.udiv(ScalarSizeInBytes).getZExtValue();
227 if (OffsetEltIndex >= MinVecNumElts)
228 return false;
229
230 if (!isSafeToLoadUnconditionally(SrcPtr, MinVecTy, Align(1), *DL, Load, &AC,
231 &DT))
232 return false;
233
234 // Update alignment with offset value. Note that the offset could be negated
235 // to more accurately represent "(new) SrcPtr - Offset = (old) SrcPtr", but
236 // negation does not change the result of the alignment calculation.
237 Alignment = commonAlignment(Alignment, Offset.getZExtValue());
238 }
239
240 // Original pattern: insertelt undef, load [free casts of] PtrOp, 0
241 // Use the greater of the alignment on the load or its source pointer.
242 Alignment = std::max(SrcPtr->getPointerAlignment(*DL), Alignment);
243 Type *LoadTy = Load->getType();
244 unsigned AS = Load->getPointerAddressSpace();
245 InstructionCost OldCost =
246 TTI.getMemoryOpCost(Instruction::Load, LoadTy, Alignment, AS);
247 APInt DemandedElts = APInt::getOneBitSet(MinVecNumElts, 0);
249 OldCost +=
250 TTI.getScalarizationOverhead(MinVecTy, DemandedElts,
251 /* Insert */ true, HasExtract, CostKind);
252
253 // New pattern: load VecPtr
254 InstructionCost NewCost =
255 TTI.getMemoryOpCost(Instruction::Load, MinVecTy, Alignment, AS);
256 // Optionally, we are shuffling the loaded vector element(s) into place.
257 // For the mask set everything but element 0 to undef to prevent poison from
258 // propagating from the extra loaded memory. This will also optionally
259 // shrink/grow the vector from the loaded size to the output size.
260 // We assume this operation has no cost in codegen if there was no offset.
261 // Note that we could use freeze to avoid poison problems, but then we might
262 // still need a shuffle to change the vector size.
263 auto *Ty = cast<FixedVectorType>(I.getType());
264 unsigned OutputNumElts = Ty->getNumElements();
266 assert(OffsetEltIndex < MinVecNumElts && "Address offset too big");
267 Mask[0] = OffsetEltIndex;
268 if (OffsetEltIndex)
269 NewCost += TTI.getShuffleCost(TTI::SK_PermuteSingleSrc, MinVecTy, Mask);
270
271 // We can aggressively convert to the vector form because the backend can
272 // invert this transform if it does not result in a performance win.
273 if (OldCost < NewCost || !NewCost.isValid())
274 return false;
275
276 // It is safe and potentially profitable to load a vector directly:
277 // inselt undef, load Scalar, 0 --> load VecPtr
278 IRBuilder<> Builder(Load);
279 Value *CastedPtr =
280 Builder.CreatePointerBitCastOrAddrSpaceCast(SrcPtr, Builder.getPtrTy(AS));
281 Value *VecLd = Builder.CreateAlignedLoad(MinVecTy, CastedPtr, Alignment);
282 VecLd = Builder.CreateShuffleVector(VecLd, Mask);
283
284 replaceValue(I, *VecLd);
285 ++NumVecLoad;
286 return true;
287}
288
289/// If we are loading a vector and then inserting it into a larger vector with
290/// undefined elements, try to load the larger vector and eliminate the insert.
291/// This removes a shuffle in IR and may allow combining of other loaded values.
292bool VectorCombine::widenSubvectorLoad(Instruction &I) {
293 // Match subvector insert of fixed vector.
294 auto *Shuf = cast<ShuffleVectorInst>(&I);
295 if (!Shuf->isIdentityWithPadding())
296 return false;
297
298 // Allow a non-canonical shuffle mask that is choosing elements from op1.
299 unsigned NumOpElts =
300 cast<FixedVectorType>(Shuf->getOperand(0)->getType())->getNumElements();
301 unsigned OpIndex = any_of(Shuf->getShuffleMask(), [&NumOpElts](int M) {
302 return M >= (int)(NumOpElts);
303 });
304
305 auto *Load = dyn_cast<LoadInst>(Shuf->getOperand(OpIndex));
306 if (!canWidenLoad(Load, TTI))
307 return false;
308
309 // We use minimal alignment (maximum flexibility) because we only care about
310 // the dereferenceable region. When calculating cost and creating a new op,
311 // we may use a larger value based on alignment attributes.
312 auto *Ty = cast<FixedVectorType>(I.getType());
313 Value *SrcPtr = Load->getPointerOperand()->stripPointerCasts();
314 assert(isa<PointerType>(SrcPtr->getType()) && "Expected a pointer type");
315 Align Alignment = Load->getAlign();
316 if (!isSafeToLoadUnconditionally(SrcPtr, Ty, Align(1), *DL, Load, &AC, &DT))
317 return false;
318
319 Alignment = std::max(SrcPtr->getPointerAlignment(*DL), Alignment);
320 Type *LoadTy = Load->getType();
321 unsigned AS = Load->getPointerAddressSpace();
322
323 // Original pattern: insert_subvector (load PtrOp)
324 // This conservatively assumes that the cost of a subvector insert into an
325 // undef value is 0. We could add that cost if the cost model accurately
326 // reflects the real cost of that operation.
327 InstructionCost OldCost =
328 TTI.getMemoryOpCost(Instruction::Load, LoadTy, Alignment, AS);
329
330 // New pattern: load PtrOp
331 InstructionCost NewCost =
332 TTI.getMemoryOpCost(Instruction::Load, Ty, Alignment, AS);
333
334 // We can aggressively convert to the vector form because the backend can
335 // invert this transform if it does not result in a performance win.
336 if (OldCost < NewCost || !NewCost.isValid())
337 return false;
338
339 IRBuilder<> Builder(Load);
340 Value *CastedPtr =
341 Builder.CreatePointerBitCastOrAddrSpaceCast(SrcPtr, Builder.getPtrTy(AS));
342 Value *VecLd = Builder.CreateAlignedLoad(Ty, CastedPtr, Alignment);
343 replaceValue(I, *VecLd);
344 ++NumVecLoad;
345 return true;
346}
347
348/// Determine which, if any, of the inputs should be replaced by a shuffle
349/// followed by extract from a different index.
350ExtractElementInst *VectorCombine::getShuffleExtract(
352 unsigned PreferredExtractIndex = InvalidIndex) const {
353 auto *Index0C = dyn_cast<ConstantInt>(Ext0->getIndexOperand());
354 auto *Index1C = dyn_cast<ConstantInt>(Ext1->getIndexOperand());
355 assert(Index0C && Index1C && "Expected constant extract indexes");
356
357 unsigned Index0 = Index0C->getZExtValue();
358 unsigned Index1 = Index1C->getZExtValue();
359
360 // If the extract indexes are identical, no shuffle is needed.
361 if (Index0 == Index1)
362 return nullptr;
363
364 Type *VecTy = Ext0->getVectorOperand()->getType();
366 assert(VecTy == Ext1->getVectorOperand()->getType() && "Need matching types");
367 InstructionCost Cost0 =
368 TTI.getVectorInstrCost(*Ext0, VecTy, CostKind, Index0);
369 InstructionCost Cost1 =
370 TTI.getVectorInstrCost(*Ext1, VecTy, CostKind, Index1);
371
372 // If both costs are invalid no shuffle is needed
373 if (!Cost0.isValid() && !Cost1.isValid())
374 return nullptr;
375
376 // We are extracting from 2 different indexes, so one operand must be shuffled
377 // before performing a vector operation and/or extract. The more expensive
378 // extract will be replaced by a shuffle.
379 if (Cost0 > Cost1)
380 return Ext0;
381 if (Cost1 > Cost0)
382 return Ext1;
383
384 // If the costs are equal and there is a preferred extract index, shuffle the
385 // opposite operand.
386 if (PreferredExtractIndex == Index0)
387 return Ext1;
388 if (PreferredExtractIndex == Index1)
389 return Ext0;
390
391 // Otherwise, replace the extract with the higher index.
392 return Index0 > Index1 ? Ext0 : Ext1;
393}
394
395/// Compare the relative costs of 2 extracts followed by scalar operation vs.
396/// vector operation(s) followed by extract. Return true if the existing
397/// instructions are cheaper than a vector alternative. Otherwise, return false
398/// and if one of the extracts should be transformed to a shufflevector, set
399/// \p ConvertToShuffle to that extract instruction.
400bool VectorCombine::isExtractExtractCheap(ExtractElementInst *Ext0,
401 ExtractElementInst *Ext1,
402 const Instruction &I,
403 ExtractElementInst *&ConvertToShuffle,
404 unsigned PreferredExtractIndex) {
405 auto *Ext0IndexC = dyn_cast<ConstantInt>(Ext0->getOperand(1));
406 auto *Ext1IndexC = dyn_cast<ConstantInt>(Ext1->getOperand(1));
407 assert(Ext0IndexC && Ext1IndexC && "Expected constant extract indexes");
408
409 unsigned Opcode = I.getOpcode();
410 Type *ScalarTy = Ext0->getType();
411 auto *VecTy = cast<VectorType>(Ext0->getOperand(0)->getType());
412 InstructionCost ScalarOpCost, VectorOpCost;
413
414 // Get cost estimates for scalar and vector versions of the operation.
415 bool IsBinOp = Instruction::isBinaryOp(Opcode);
416 if (IsBinOp) {
417 ScalarOpCost = TTI.getArithmeticInstrCost(Opcode, ScalarTy);
418 VectorOpCost = TTI.getArithmeticInstrCost(Opcode, VecTy);
419 } else {
420 assert((Opcode == Instruction::ICmp || Opcode == Instruction::FCmp) &&
421 "Expected a compare");
422 CmpInst::Predicate Pred = cast<CmpInst>(I).getPredicate();
423 ScalarOpCost = TTI.getCmpSelInstrCost(
424 Opcode, ScalarTy, CmpInst::makeCmpResultType(ScalarTy), Pred);
425 VectorOpCost = TTI.getCmpSelInstrCost(
426 Opcode, VecTy, CmpInst::makeCmpResultType(VecTy), Pred);
427 }
428
429 // Get cost estimates for the extract elements. These costs will factor into
430 // both sequences.
431 unsigned Ext0Index = Ext0IndexC->getZExtValue();
432 unsigned Ext1Index = Ext1IndexC->getZExtValue();
434
435 InstructionCost Extract0Cost =
436 TTI.getVectorInstrCost(*Ext0, VecTy, CostKind, Ext0Index);
437 InstructionCost Extract1Cost =
438 TTI.getVectorInstrCost(*Ext1, VecTy, CostKind, Ext1Index);
439
440 // A more expensive extract will always be replaced by a splat shuffle.
441 // For example, if Ext0 is more expensive:
442 // opcode (extelt V0, Ext0), (ext V1, Ext1) -->
443 // extelt (opcode (splat V0, Ext0), V1), Ext1
444 // TODO: Evaluate whether that always results in lowest cost. Alternatively,
445 // check the cost of creating a broadcast shuffle and shuffling both
446 // operands to element 0.
447 InstructionCost CheapExtractCost = std::min(Extract0Cost, Extract1Cost);
448
449 // Extra uses of the extracts mean that we include those costs in the
450 // vector total because those instructions will not be eliminated.
451 InstructionCost OldCost, NewCost;
452 if (Ext0->getOperand(0) == Ext1->getOperand(0) && Ext0Index == Ext1Index) {
453 // Handle a special case. If the 2 extracts are identical, adjust the
454 // formulas to account for that. The extra use charge allows for either the
455 // CSE'd pattern or an unoptimized form with identical values:
456 // opcode (extelt V, C), (extelt V, C) --> extelt (opcode V, V), C
457 bool HasUseTax = Ext0 == Ext1 ? !Ext0->hasNUses(2)
458 : !Ext0->hasOneUse() || !Ext1->hasOneUse();
459 OldCost = CheapExtractCost + ScalarOpCost;
460 NewCost = VectorOpCost + CheapExtractCost + HasUseTax * CheapExtractCost;
461 } else {
462 // Handle the general case. Each extract is actually a different value:
463 // opcode (extelt V0, C0), (extelt V1, C1) --> extelt (opcode V0, V1), C
464 OldCost = Extract0Cost + Extract1Cost + ScalarOpCost;
465 NewCost = VectorOpCost + CheapExtractCost +
466 !Ext0->hasOneUse() * Extract0Cost +
467 !Ext1->hasOneUse() * Extract1Cost;
468 }
469
470 ConvertToShuffle = getShuffleExtract(Ext0, Ext1, PreferredExtractIndex);
471 if (ConvertToShuffle) {
472 if (IsBinOp && DisableBinopExtractShuffle)
473 return true;
474
475 // If we are extracting from 2 different indexes, then one operand must be
476 // shuffled before performing the vector operation. The shuffle mask is
477 // poison except for 1 lane that is being translated to the remaining
478 // extraction lane. Therefore, it is a splat shuffle. Ex:
479 // ShufMask = { poison, poison, 0, poison }
480 // TODO: The cost model has an option for a "broadcast" shuffle
481 // (splat-from-element-0), but no option for a more general splat.
482 NewCost +=
484 }
485
486 // Aggressively form a vector op if the cost is equal because the transform
487 // may enable further optimization.
488 // Codegen can reverse this transform (scalarize) if it was not profitable.
489 return OldCost < NewCost;
490}
491
492/// Create a shuffle that translates (shifts) 1 element from the input vector
493/// to a new element location.
494static Value *createShiftShuffle(Value *Vec, unsigned OldIndex,
495 unsigned NewIndex, IRBuilder<> &Builder) {
496 // The shuffle mask is poison except for 1 lane that is being translated
497 // to the new element index. Example for OldIndex == 2 and NewIndex == 0:
498 // ShufMask = { 2, poison, poison, poison }
499 auto *VecTy = cast<FixedVectorType>(Vec->getType());
500 SmallVector<int, 32> ShufMask(VecTy->getNumElements(), PoisonMaskElem);
501 ShufMask[NewIndex] = OldIndex;
502 return Builder.CreateShuffleVector(Vec, ShufMask, "shift");
503}
504
505/// Given an extract element instruction with constant index operand, shuffle
506/// the source vector (shift the scalar element) to a NewIndex for extraction.
507/// Return null if the input can be constant folded, so that we are not creating
508/// unnecessary instructions.
510 unsigned NewIndex,
511 IRBuilder<> &Builder) {
512 // Shufflevectors can only be created for fixed-width vectors.
513 if (!isa<FixedVectorType>(ExtElt->getOperand(0)->getType()))
514 return nullptr;
515
516 // If the extract can be constant-folded, this code is unsimplified. Defer
517 // to other passes to handle that.
518 Value *X = ExtElt->getVectorOperand();
519 Value *C = ExtElt->getIndexOperand();
520 assert(isa<ConstantInt>(C) && "Expected a constant index operand");
521 if (isa<Constant>(X))
522 return nullptr;
523
524 Value *Shuf = createShiftShuffle(X, cast<ConstantInt>(C)->getZExtValue(),
525 NewIndex, Builder);
526 return cast<ExtractElementInst>(Builder.CreateExtractElement(Shuf, NewIndex));
527}
528
529/// Try to reduce extract element costs by converting scalar compares to vector
530/// compares followed by extract.
531/// cmp (ext0 V0, C), (ext1 V1, C)
532void VectorCombine::foldExtExtCmp(ExtractElementInst *Ext0,
534 assert(isa<CmpInst>(&I) && "Expected a compare");
535 assert(cast<ConstantInt>(Ext0->getIndexOperand())->getZExtValue() ==
536 cast<ConstantInt>(Ext1->getIndexOperand())->getZExtValue() &&
537 "Expected matching constant extract indexes");
538
539 // cmp Pred (extelt V0, C), (extelt V1, C) --> extelt (cmp Pred V0, V1), C
540 ++NumVecCmp;
541 CmpInst::Predicate Pred = cast<CmpInst>(&I)->getPredicate();
542 Value *V0 = Ext0->getVectorOperand(), *V1 = Ext1->getVectorOperand();
543 Value *VecCmp = Builder.CreateCmp(Pred, V0, V1);
544 Value *NewExt = Builder.CreateExtractElement(VecCmp, Ext0->getIndexOperand());
545 replaceValue(I, *NewExt);
546}
547
548/// Try to reduce extract element costs by converting scalar binops to vector
549/// binops followed by extract.
550/// bo (ext0 V0, C), (ext1 V1, C)
551void VectorCombine::foldExtExtBinop(ExtractElementInst *Ext0,
553 assert(isa<BinaryOperator>(&I) && "Expected a binary operator");
554 assert(cast<ConstantInt>(Ext0->getIndexOperand())->getZExtValue() ==
555 cast<ConstantInt>(Ext1->getIndexOperand())->getZExtValue() &&
556 "Expected matching constant extract indexes");
557
558 // bo (extelt V0, C), (extelt V1, C) --> extelt (bo V0, V1), C
559 ++NumVecBO;
560 Value *V0 = Ext0->getVectorOperand(), *V1 = Ext1->getVectorOperand();
561 Value *VecBO =
562 Builder.CreateBinOp(cast<BinaryOperator>(&I)->getOpcode(), V0, V1);
563
564 // All IR flags are safe to back-propagate because any potential poison
565 // created in unused vector elements is discarded by the extract.
566 if (auto *VecBOInst = dyn_cast<Instruction>(VecBO))
567 VecBOInst->copyIRFlags(&I);
568
569 Value *NewExt = Builder.CreateExtractElement(VecBO, Ext0->getIndexOperand());
570 replaceValue(I, *NewExt);
571}
572
573/// Match an instruction with extracted vector operands.
574bool VectorCombine::foldExtractExtract(Instruction &I) {
575 // It is not safe to transform things like div, urem, etc. because we may
576 // create undefined behavior when executing those on unknown vector elements.
578 return false;
579
580 Instruction *I0, *I1;
582 if (!match(&I, m_Cmp(Pred, m_Instruction(I0), m_Instruction(I1))) &&
584 return false;
585
586 Value *V0, *V1;
587 uint64_t C0, C1;
588 if (!match(I0, m_ExtractElt(m_Value(V0), m_ConstantInt(C0))) ||
589 !match(I1, m_ExtractElt(m_Value(V1), m_ConstantInt(C1))) ||
590 V0->getType() != V1->getType())
591 return false;
592
593 // If the scalar value 'I' is going to be re-inserted into a vector, then try
594 // to create an extract to that same element. The extract/insert can be
595 // reduced to a "select shuffle".
596 // TODO: If we add a larger pattern match that starts from an insert, this
597 // probably becomes unnecessary.
598 auto *Ext0 = cast<ExtractElementInst>(I0);
599 auto *Ext1 = cast<ExtractElementInst>(I1);
600 uint64_t InsertIndex = InvalidIndex;
601 if (I.hasOneUse())
602 match(I.user_back(),
603 m_InsertElt(m_Value(), m_Value(), m_ConstantInt(InsertIndex)));
604
605 ExtractElementInst *ExtractToChange;
606 if (isExtractExtractCheap(Ext0, Ext1, I, ExtractToChange, InsertIndex))
607 return false;
608
609 if (ExtractToChange) {
610 unsigned CheapExtractIdx = ExtractToChange == Ext0 ? C1 : C0;
611 ExtractElementInst *NewExtract =
612 translateExtract(ExtractToChange, CheapExtractIdx, Builder);
613 if (!NewExtract)
614 return false;
615 if (ExtractToChange == Ext0)
616 Ext0 = NewExtract;
617 else
618 Ext1 = NewExtract;
619 }
620
621 if (Pred != CmpInst::BAD_ICMP_PREDICATE)
622 foldExtExtCmp(Ext0, Ext1, I);
623 else
624 foldExtExtBinop(Ext0, Ext1, I);
625
626 Worklist.push(Ext0);
627 Worklist.push(Ext1);
628 return true;
629}
630
631/// Try to replace an extract + scalar fneg + insert with a vector fneg +
632/// shuffle.
633bool VectorCombine::foldInsExtFNeg(Instruction &I) {
634 // Match an insert (op (extract)) pattern.
635 Value *DestVec;
637 Instruction *FNeg;
638 if (!match(&I, m_InsertElt(m_Value(DestVec), m_OneUse(m_Instruction(FNeg)),
640 return false;
641
642 // Note: This handles the canonical fneg instruction and "fsub -0.0, X".
643 Value *SrcVec;
644 Instruction *Extract;
645 if (!match(FNeg, m_FNeg(m_CombineAnd(
646 m_Instruction(Extract),
648 return false;
649
650 // TODO: We could handle this with a length-changing shuffle.
651 auto *VecTy = cast<FixedVectorType>(I.getType());
652 if (SrcVec->getType() != VecTy)
653 return false;
654
655 // Ignore bogus insert/extract index.
656 unsigned NumElts = VecTy->getNumElements();
657 if (Index >= NumElts)
658 return false;
659
660 // We are inserting the negated element into the same lane that we extracted
661 // from. This is equivalent to a select-shuffle that chooses all but the
662 // negated element from the destination vector.
663 SmallVector<int> Mask(NumElts);
664 std::iota(Mask.begin(), Mask.end(), 0);
665 Mask[Index] = Index + NumElts;
666
667 Type *ScalarTy = VecTy->getScalarType();
669 InstructionCost OldCost =
670 TTI.getArithmeticInstrCost(Instruction::FNeg, ScalarTy) +
672
673 // If the extract has one use, it will be eliminated, so count it in the
674 // original cost. If it has more than one use, ignore the cost because it will
675 // be the same before/after.
676 if (Extract->hasOneUse())
677 OldCost += TTI.getVectorInstrCost(*Extract, VecTy, CostKind, Index);
678
679 InstructionCost NewCost =
680 TTI.getArithmeticInstrCost(Instruction::FNeg, VecTy) +
682
683 if (NewCost > OldCost)
684 return false;
685
686 // insertelt DestVec, (fneg (extractelt SrcVec, Index)), Index -->
687 // shuffle DestVec, (fneg SrcVec), Mask
688 Value *VecFNeg = Builder.CreateFNegFMF(SrcVec, FNeg);
689 Value *Shuf = Builder.CreateShuffleVector(DestVec, VecFNeg, Mask);
690 replaceValue(I, *Shuf);
691 return true;
692}
693
694/// If this is a bitcast of a shuffle, try to bitcast the source vector to the
695/// destination type followed by shuffle. This can enable further transforms by
696/// moving bitcasts or shuffles together.
697bool VectorCombine::foldBitcastShuffle(Instruction &I) {
698 Value *V0, *V1;
700 if (!match(&I, m_BitCast(m_OneUse(
701 m_Shuffle(m_Value(V0), m_Value(V1), m_Mask(Mask))))))
702 return false;
703
704 // 1) Do not fold bitcast shuffle for scalable type. First, shuffle cost for
705 // scalable type is unknown; Second, we cannot reason if the narrowed shuffle
706 // mask for scalable type is a splat or not.
707 // 2) Disallow non-vector casts.
708 // TODO: We could allow any shuffle.
709 auto *DestTy = dyn_cast<FixedVectorType>(I.getType());
710 auto *SrcTy = dyn_cast<FixedVectorType>(V0->getType());
711 if (!DestTy || !SrcTy)
712 return false;
713
714 unsigned DestEltSize = DestTy->getScalarSizeInBits();
715 unsigned SrcEltSize = SrcTy->getScalarSizeInBits();
716 if (SrcTy->getPrimitiveSizeInBits() % DestEltSize != 0)
717 return false;
718
719 bool IsUnary = isa<UndefValue>(V1);
720
721 // For binary shuffles, only fold bitcast(shuffle(X,Y))
722 // if it won't increase the number of bitcasts.
723 if (!IsUnary) {
724 auto *BCTy0 = dyn_cast<FixedVectorType>(peekThroughBitcasts(V0)->getType());
725 auto *BCTy1 = dyn_cast<FixedVectorType>(peekThroughBitcasts(V1)->getType());
726 if (!(BCTy0 && BCTy0->getElementType() == DestTy->getElementType()) &&
727 !(BCTy1 && BCTy1->getElementType() == DestTy->getElementType()))
728 return false;
729 }
730
731 SmallVector<int, 16> NewMask;
732 if (DestEltSize <= SrcEltSize) {
733 // The bitcast is from wide to narrow/equal elements. The shuffle mask can
734 // always be expanded to the equivalent form choosing narrower elements.
735 assert(SrcEltSize % DestEltSize == 0 && "Unexpected shuffle mask");
736 unsigned ScaleFactor = SrcEltSize / DestEltSize;
737 narrowShuffleMaskElts(ScaleFactor, Mask, NewMask);
738 } else {
739 // The bitcast is from narrow elements to wide elements. The shuffle mask
740 // must choose consecutive elements to allow casting first.
741 assert(DestEltSize % SrcEltSize == 0 && "Unexpected shuffle mask");
742 unsigned ScaleFactor = DestEltSize / SrcEltSize;
743 if (!widenShuffleMaskElts(ScaleFactor, Mask, NewMask))
744 return false;
745 }
746
747 // Bitcast the shuffle src - keep its original width but using the destination
748 // scalar type.
749 unsigned NumSrcElts = SrcTy->getPrimitiveSizeInBits() / DestEltSize;
750 auto *NewShuffleTy =
751 FixedVectorType::get(DestTy->getScalarType(), NumSrcElts);
752 auto *OldShuffleTy =
753 FixedVectorType::get(SrcTy->getScalarType(), Mask.size());
754 unsigned NumOps = IsUnary ? 1 : 2;
755
756 // The new shuffle must not cost more than the old shuffle.
762
763 InstructionCost DestCost =
764 TTI.getShuffleCost(SK, NewShuffleTy, NewMask, CK) +
765 (NumOps * TTI.getCastInstrCost(Instruction::BitCast, NewShuffleTy, SrcTy,
766 TargetTransformInfo::CastContextHint::None,
767 CK));
768 InstructionCost SrcCost =
769 TTI.getShuffleCost(SK, SrcTy, Mask, CK) +
770 TTI.getCastInstrCost(Instruction::BitCast, DestTy, OldShuffleTy,
771 TargetTransformInfo::CastContextHint::None, CK);
772 if (DestCost > SrcCost || !DestCost.isValid())
773 return false;
774
775 // bitcast (shuf V0, V1, MaskC) --> shuf (bitcast V0), (bitcast V1), MaskC'
776 ++NumShufOfBitcast;
777 Value *CastV0 = Builder.CreateBitCast(peekThroughBitcasts(V0), NewShuffleTy);
778 Value *CastV1 = Builder.CreateBitCast(peekThroughBitcasts(V1), NewShuffleTy);
779 Value *Shuf = Builder.CreateShuffleVector(CastV0, CastV1, NewMask);
780 replaceValue(I, *Shuf);
781 return true;
782}
783
784/// VP Intrinsics whose vector operands are both splat values may be simplified
785/// into the scalar version of the operation and the result splatted. This
786/// can lead to scalarization down the line.
787bool VectorCombine::scalarizeVPIntrinsic(Instruction &I) {
788 if (!isa<VPIntrinsic>(I))
789 return false;
790 VPIntrinsic &VPI = cast<VPIntrinsic>(I);
791 Value *Op0 = VPI.getArgOperand(0);
792 Value *Op1 = VPI.getArgOperand(1);
793
794 if (!isSplatValue(Op0) || !isSplatValue(Op1))
795 return false;
796
797 // Check getSplatValue early in this function, to avoid doing unnecessary
798 // work.
799 Value *ScalarOp0 = getSplatValue(Op0);
800 Value *ScalarOp1 = getSplatValue(Op1);
801 if (!ScalarOp0 || !ScalarOp1)
802 return false;
803
804 // For the binary VP intrinsics supported here, the result on disabled lanes
805 // is a poison value. For now, only do this simplification if all lanes
806 // are active.
807 // TODO: Relax the condition that all lanes are active by using insertelement
808 // on inactive lanes.
809 auto IsAllTrueMask = [](Value *MaskVal) {
810 if (Value *SplattedVal = getSplatValue(MaskVal))
811 if (auto *ConstValue = dyn_cast<Constant>(SplattedVal))
812 return ConstValue->isAllOnesValue();
813 return false;
814 };
815 if (!IsAllTrueMask(VPI.getArgOperand(2)))
816 return false;
817
818 // Check to make sure we support scalarization of the intrinsic
819 Intrinsic::ID IntrID = VPI.getIntrinsicID();
820 if (!VPBinOpIntrinsic::isVPBinOp(IntrID))
821 return false;
822
823 // Calculate cost of splatting both operands into vectors and the vector
824 // intrinsic
825 VectorType *VecTy = cast<VectorType>(VPI.getType());
828 if (auto *FVTy = dyn_cast<FixedVectorType>(VecTy))
829 Mask.resize(FVTy->getNumElements(), 0);
830 InstructionCost SplatCost =
831 TTI.getVectorInstrCost(Instruction::InsertElement, VecTy, CostKind, 0) +
833
834 // Calculate the cost of the VP Intrinsic
836 for (Value *V : VPI.args())
837 Args.push_back(V->getType());
838 IntrinsicCostAttributes Attrs(IntrID, VecTy, Args);
839 InstructionCost VectorOpCost = TTI.getIntrinsicInstrCost(Attrs, CostKind);
840 InstructionCost OldCost = 2 * SplatCost + VectorOpCost;
841
842 // Determine scalar opcode
843 std::optional<unsigned> FunctionalOpcode =
845 std::optional<Intrinsic::ID> ScalarIntrID = std::nullopt;
846 if (!FunctionalOpcode) {
847 ScalarIntrID = VPI.getFunctionalIntrinsicID();
848 if (!ScalarIntrID)
849 return false;
850 }
851
852 // Calculate cost of scalarizing
853 InstructionCost ScalarOpCost = 0;
854 if (ScalarIntrID) {
855 IntrinsicCostAttributes Attrs(*ScalarIntrID, VecTy->getScalarType(), Args);
856 ScalarOpCost = TTI.getIntrinsicInstrCost(Attrs, CostKind);
857 } else {
858 ScalarOpCost =
859 TTI.getArithmeticInstrCost(*FunctionalOpcode, VecTy->getScalarType());
860 }
861
862 // The existing splats may be kept around if other instructions use them.
863 InstructionCost CostToKeepSplats =
864 (SplatCost * !Op0->hasOneUse()) + (SplatCost * !Op1->hasOneUse());
865 InstructionCost NewCost = ScalarOpCost + SplatCost + CostToKeepSplats;
866
867 LLVM_DEBUG(dbgs() << "Found a VP Intrinsic to scalarize: " << VPI
868 << "\n");
869 LLVM_DEBUG(dbgs() << "Cost of Intrinsic: " << OldCost
870 << ", Cost of scalarizing:" << NewCost << "\n");
871
872 // We want to scalarize unless the vector variant actually has lower cost.
873 if (OldCost < NewCost || !NewCost.isValid())
874 return false;
875
876 // Scalarize the intrinsic
877 ElementCount EC = cast<VectorType>(Op0->getType())->getElementCount();
878 Value *EVL = VPI.getArgOperand(3);
879
880 // If the VP op might introduce UB or poison, we can scalarize it provided
881 // that we know the EVL > 0: If the EVL is zero, then the original VP op
882 // becomes a no-op and thus won't be UB, so make sure we don't introduce UB by
883 // scalarizing it.
884 bool SafeToSpeculate;
885 if (ScalarIntrID)
886 SafeToSpeculate = Intrinsic::getAttributes(I.getContext(), *ScalarIntrID)
887 .hasFnAttr(Attribute::AttrKind::Speculatable);
888 else
890 *FunctionalOpcode, &VPI, nullptr, &AC, &DT);
891 if (!SafeToSpeculate &&
892 !isKnownNonZero(EVL, SimplifyQuery(*DL, &DT, &AC, &VPI)))
893 return false;
894
895 Value *ScalarVal =
896 ScalarIntrID
897 ? Builder.CreateIntrinsic(VecTy->getScalarType(), *ScalarIntrID,
898 {ScalarOp0, ScalarOp1})
899 : Builder.CreateBinOp((Instruction::BinaryOps)(*FunctionalOpcode),
900 ScalarOp0, ScalarOp1);
901
902 replaceValue(VPI, *Builder.CreateVectorSplat(EC, ScalarVal));
903 return true;
904}
905
906/// Match a vector binop or compare instruction with at least one inserted
907/// scalar operand and convert to scalar binop/cmp followed by insertelement.
908bool VectorCombine::scalarizeBinopOrCmp(Instruction &I) {
910 Value *Ins0, *Ins1;
911 if (!match(&I, m_BinOp(m_Value(Ins0), m_Value(Ins1))) &&
912 !match(&I, m_Cmp(Pred, m_Value(Ins0), m_Value(Ins1))))
913 return false;
914
915 // Do not convert the vector condition of a vector select into a scalar
916 // condition. That may cause problems for codegen because of differences in
917 // boolean formats and register-file transfers.
918 // TODO: Can we account for that in the cost model?
919 bool IsCmp = Pred != CmpInst::Predicate::BAD_ICMP_PREDICATE;
920 if (IsCmp)
921 for (User *U : I.users())
922 if (match(U, m_Select(m_Specific(&I), m_Value(), m_Value())))
923 return false;
924
925 // Match against one or both scalar values being inserted into constant
926 // vectors:
927 // vec_op VecC0, (inselt VecC1, V1, Index)
928 // vec_op (inselt VecC0, V0, Index), VecC1
929 // vec_op (inselt VecC0, V0, Index), (inselt VecC1, V1, Index)
930 // TODO: Deal with mismatched index constants and variable indexes?
931 Constant *VecC0 = nullptr, *VecC1 = nullptr;
932 Value *V0 = nullptr, *V1 = nullptr;
933 uint64_t Index0 = 0, Index1 = 0;
934 if (!match(Ins0, m_InsertElt(m_Constant(VecC0), m_Value(V0),
935 m_ConstantInt(Index0))) &&
936 !match(Ins0, m_Constant(VecC0)))
937 return false;
938 if (!match(Ins1, m_InsertElt(m_Constant(VecC1), m_Value(V1),
939 m_ConstantInt(Index1))) &&
940 !match(Ins1, m_Constant(VecC1)))
941 return false;
942
943 bool IsConst0 = !V0;
944 bool IsConst1 = !V1;
945 if (IsConst0 && IsConst1)
946 return false;
947 if (!IsConst0 && !IsConst1 && Index0 != Index1)
948 return false;
949
950 // Bail for single insertion if it is a load.
951 // TODO: Handle this once getVectorInstrCost can cost for load/stores.
952 auto *I0 = dyn_cast_or_null<Instruction>(V0);
953 auto *I1 = dyn_cast_or_null<Instruction>(V1);
954 if ((IsConst0 && I1 && I1->mayReadFromMemory()) ||
955 (IsConst1 && I0 && I0->mayReadFromMemory()))
956 return false;
957
958 uint64_t Index = IsConst0 ? Index1 : Index0;
959 Type *ScalarTy = IsConst0 ? V1->getType() : V0->getType();
960 Type *VecTy = I.getType();
961 assert(VecTy->isVectorTy() &&
962 (IsConst0 || IsConst1 || V0->getType() == V1->getType()) &&
963 (ScalarTy->isIntegerTy() || ScalarTy->isFloatingPointTy() ||
964 ScalarTy->isPointerTy()) &&
965 "Unexpected types for insert element into binop or cmp");
966
967 unsigned Opcode = I.getOpcode();
968 InstructionCost ScalarOpCost, VectorOpCost;
969 if (IsCmp) {
970 CmpInst::Predicate Pred = cast<CmpInst>(I).getPredicate();
971 ScalarOpCost = TTI.getCmpSelInstrCost(
972 Opcode, ScalarTy, CmpInst::makeCmpResultType(ScalarTy), Pred);
973 VectorOpCost = TTI.getCmpSelInstrCost(
974 Opcode, VecTy, CmpInst::makeCmpResultType(VecTy), Pred);
975 } else {
976 ScalarOpCost = TTI.getArithmeticInstrCost(Opcode, ScalarTy);
977 VectorOpCost = TTI.getArithmeticInstrCost(Opcode, VecTy);
978 }
979
980 // Get cost estimate for the insert element. This cost will factor into
981 // both sequences.
984 Instruction::InsertElement, VecTy, CostKind, Index);
985 InstructionCost OldCost =
986 (IsConst0 ? 0 : InsertCost) + (IsConst1 ? 0 : InsertCost) + VectorOpCost;
987 InstructionCost NewCost = ScalarOpCost + InsertCost +
988 (IsConst0 ? 0 : !Ins0->hasOneUse() * InsertCost) +
989 (IsConst1 ? 0 : !Ins1->hasOneUse() * InsertCost);
990
991 // We want to scalarize unless the vector variant actually has lower cost.
992 if (OldCost < NewCost || !NewCost.isValid())
993 return false;
994
995 // vec_op (inselt VecC0, V0, Index), (inselt VecC1, V1, Index) -->
996 // inselt NewVecC, (scalar_op V0, V1), Index
997 if (IsCmp)
998 ++NumScalarCmp;
999 else
1000 ++NumScalarBO;
1001
1002 // For constant cases, extract the scalar element, this should constant fold.
1003 if (IsConst0)
1004 V0 = ConstantExpr::getExtractElement(VecC0, Builder.getInt64(Index));
1005 if (IsConst1)
1006 V1 = ConstantExpr::getExtractElement(VecC1, Builder.getInt64(Index));
1007
1008 Value *Scalar =
1009 IsCmp ? Builder.CreateCmp(Pred, V0, V1)
1010 : Builder.CreateBinOp((Instruction::BinaryOps)Opcode, V0, V1);
1011
1012 Scalar->setName(I.getName() + ".scalar");
1013
1014 // All IR flags are safe to back-propagate. There is no potential for extra
1015 // poison to be created by the scalar instruction.
1016 if (auto *ScalarInst = dyn_cast<Instruction>(Scalar))
1017 ScalarInst->copyIRFlags(&I);
1018
1019 // Fold the vector constants in the original vectors into a new base vector.
1020 Value *NewVecC =
1021 IsCmp ? Builder.CreateCmp(Pred, VecC0, VecC1)
1022 : Builder.CreateBinOp((Instruction::BinaryOps)Opcode, VecC0, VecC1);
1023 Value *Insert = Builder.CreateInsertElement(NewVecC, Scalar, Index);
1024 replaceValue(I, *Insert);
1025 return true;
1026}
1027
1028/// Try to combine a scalar binop + 2 scalar compares of extracted elements of
1029/// a vector into vector operations followed by extract. Note: The SLP pass
1030/// may miss this pattern because of implementation problems.
1031bool VectorCombine::foldExtractedCmps(Instruction &I) {
1032 // We are looking for a scalar binop of booleans.
1033 // binop i1 (cmp Pred I0, C0), (cmp Pred I1, C1)
1034 if (!I.isBinaryOp() || !I.getType()->isIntegerTy(1))
1035 return false;
1036
1037 // The compare predicates should match, and each compare should have a
1038 // constant operand.
1039 // TODO: Relax the one-use constraints.
1040 Value *B0 = I.getOperand(0), *B1 = I.getOperand(1);
1041 Instruction *I0, *I1;
1042 Constant *C0, *C1;
1043 CmpInst::Predicate P0, P1;
1044 if (!match(B0, m_OneUse(m_Cmp(P0, m_Instruction(I0), m_Constant(C0)))) ||
1045 !match(B1, m_OneUse(m_Cmp(P1, m_Instruction(I1), m_Constant(C1)))) ||
1046 P0 != P1)
1047 return false;
1048
1049 // The compare operands must be extracts of the same vector with constant
1050 // extract indexes.
1051 // TODO: Relax the one-use constraints.
1052 Value *X;
1053 uint64_t Index0, Index1;
1054 if (!match(I0, m_OneUse(m_ExtractElt(m_Value(X), m_ConstantInt(Index0)))) ||
1056 return false;
1057
1058 auto *Ext0 = cast<ExtractElementInst>(I0);
1059 auto *Ext1 = cast<ExtractElementInst>(I1);
1060 ExtractElementInst *ConvertToShuf = getShuffleExtract(Ext0, Ext1);
1061 if (!ConvertToShuf)
1062 return false;
1063
1064 // The original scalar pattern is:
1065 // binop i1 (cmp Pred (ext X, Index0), C0), (cmp Pred (ext X, Index1), C1)
1066 CmpInst::Predicate Pred = P0;
1067 unsigned CmpOpcode = CmpInst::isFPPredicate(Pred) ? Instruction::FCmp
1068 : Instruction::ICmp;
1069 auto *VecTy = dyn_cast<FixedVectorType>(X->getType());
1070 if (!VecTy)
1071 return false;
1072
1074 InstructionCost OldCost =
1075 TTI.getVectorInstrCost(*Ext0, VecTy, CostKind, Index0);
1076 OldCost += TTI.getVectorInstrCost(*Ext1, VecTy, CostKind, Index1);
1077 OldCost +=
1078 TTI.getCmpSelInstrCost(CmpOpcode, I0->getType(),
1079 CmpInst::makeCmpResultType(I0->getType()), Pred) *
1080 2;
1081 OldCost += TTI.getArithmeticInstrCost(I.getOpcode(), I.getType());
1082
1083 // The proposed vector pattern is:
1084 // vcmp = cmp Pred X, VecC
1085 // ext (binop vNi1 vcmp, (shuffle vcmp, Index1)), Index0
1086 int CheapIndex = ConvertToShuf == Ext0 ? Index1 : Index0;
1087 int ExpensiveIndex = ConvertToShuf == Ext0 ? Index0 : Index1;
1088 auto *CmpTy = cast<FixedVectorType>(CmpInst::makeCmpResultType(X->getType()));
1090 CmpOpcode, X->getType(), CmpInst::makeCmpResultType(X->getType()), Pred);
1091 SmallVector<int, 32> ShufMask(VecTy->getNumElements(), PoisonMaskElem);
1092 ShufMask[CheapIndex] = ExpensiveIndex;
1094 ShufMask);
1095 NewCost += TTI.getArithmeticInstrCost(I.getOpcode(), CmpTy);
1096 NewCost += TTI.getVectorInstrCost(*Ext0, CmpTy, CostKind, CheapIndex);
1097
1098 // Aggressively form vector ops if the cost is equal because the transform
1099 // may enable further optimization.
1100 // Codegen can reverse this transform (scalarize) if it was not profitable.
1101 if (OldCost < NewCost || !NewCost.isValid())
1102 return false;
1103
1104 // Create a vector constant from the 2 scalar constants.
1105 SmallVector<Constant *, 32> CmpC(VecTy->getNumElements(),
1106 PoisonValue::get(VecTy->getElementType()));
1107 CmpC[Index0] = C0;
1108 CmpC[Index1] = C1;
1109 Value *VCmp = Builder.CreateCmp(Pred, X, ConstantVector::get(CmpC));
1110
1111 Value *Shuf = createShiftShuffle(VCmp, ExpensiveIndex, CheapIndex, Builder);
1112 Value *VecLogic = Builder.CreateBinOp(cast<BinaryOperator>(I).getOpcode(),
1113 VCmp, Shuf);
1114 Value *NewExt = Builder.CreateExtractElement(VecLogic, CheapIndex);
1115 replaceValue(I, *NewExt);
1116 ++NumVecCmpBO;
1117 return true;
1118}
1119
1120// Check if memory loc modified between two instrs in the same BB
1123 const MemoryLocation &Loc, AAResults &AA) {
1124 unsigned NumScanned = 0;
1125 return std::any_of(Begin, End, [&](const Instruction &Instr) {
1126 return isModSet(AA.getModRefInfo(&Instr, Loc)) ||
1127 ++NumScanned > MaxInstrsToScan;
1128 });
1129}
1130
1131namespace {
1132/// Helper class to indicate whether a vector index can be safely scalarized and
1133/// if a freeze needs to be inserted.
1134class ScalarizationResult {
1135 enum class StatusTy { Unsafe, Safe, SafeWithFreeze };
1136
1137 StatusTy Status;
1138 Value *ToFreeze;
1139
1140 ScalarizationResult(StatusTy Status, Value *ToFreeze = nullptr)
1141 : Status(Status), ToFreeze(ToFreeze) {}
1142
1143public:
1144 ScalarizationResult(const ScalarizationResult &Other) = default;
1145 ~ScalarizationResult() {
1146 assert(!ToFreeze && "freeze() not called with ToFreeze being set");
1147 }
1148
1149 static ScalarizationResult unsafe() { return {StatusTy::Unsafe}; }
1150 static ScalarizationResult safe() { return {StatusTy::Safe}; }
1151 static ScalarizationResult safeWithFreeze(Value *ToFreeze) {
1152 return {StatusTy::SafeWithFreeze, ToFreeze};
1153 }
1154
1155 /// Returns true if the index can be scalarize without requiring a freeze.
1156 bool isSafe() const { return Status == StatusTy::Safe; }
1157 /// Returns true if the index cannot be scalarized.
1158 bool isUnsafe() const { return Status == StatusTy::Unsafe; }
1159 /// Returns true if the index can be scalarize, but requires inserting a
1160 /// freeze.
1161 bool isSafeWithFreeze() const { return Status == StatusTy::SafeWithFreeze; }
1162
1163 /// Reset the state of Unsafe and clear ToFreze if set.
1164 void discard() {
1165 ToFreeze = nullptr;
1166 Status = StatusTy::Unsafe;
1167 }
1168
1169 /// Freeze the ToFreeze and update the use in \p User to use it.
1170 void freeze(IRBuilder<> &Builder, Instruction &UserI) {
1171 assert(isSafeWithFreeze() &&
1172 "should only be used when freezing is required");
1173 assert(is_contained(ToFreeze->users(), &UserI) &&
1174 "UserI must be a user of ToFreeze");
1175 IRBuilder<>::InsertPointGuard Guard(Builder);
1176 Builder.SetInsertPoint(cast<Instruction>(&UserI));
1177 Value *Frozen =
1178 Builder.CreateFreeze(ToFreeze, ToFreeze->getName() + ".frozen");
1179 for (Use &U : make_early_inc_range((UserI.operands())))
1180 if (U.get() == ToFreeze)
1181 U.set(Frozen);
1182
1183 ToFreeze = nullptr;
1184 }
1185};
1186} // namespace
1187
1188/// Check if it is legal to scalarize a memory access to \p VecTy at index \p
1189/// Idx. \p Idx must access a valid vector element.
1190static ScalarizationResult canScalarizeAccess(VectorType *VecTy, Value *Idx,
1191 Instruction *CtxI,
1192 AssumptionCache &AC,
1193 const DominatorTree &DT) {
1194 // We do checks for both fixed vector types and scalable vector types.
1195 // This is the number of elements of fixed vector types,
1196 // or the minimum number of elements of scalable vector types.
1197 uint64_t NumElements = VecTy->getElementCount().getKnownMinValue();
1198
1199 if (auto *C = dyn_cast<ConstantInt>(Idx)) {
1200 if (C->getValue().ult(NumElements))
1201 return ScalarizationResult::safe();
1202 return ScalarizationResult::unsafe();
1203 }
1204
1205 unsigned IntWidth = Idx->getType()->getScalarSizeInBits();
1206 APInt Zero(IntWidth, 0);
1207 APInt MaxElts(IntWidth, NumElements);
1208 ConstantRange ValidIndices(Zero, MaxElts);
1209 ConstantRange IdxRange(IntWidth, true);
1210
1211 if (isGuaranteedNotToBePoison(Idx, &AC)) {
1212 if (ValidIndices.contains(computeConstantRange(Idx, /* ForSigned */ false,
1213 true, &AC, CtxI, &DT)))
1214 return ScalarizationResult::safe();
1215 return ScalarizationResult::unsafe();
1216 }
1217
1218 // If the index may be poison, check if we can insert a freeze before the
1219 // range of the index is restricted.
1220 Value *IdxBase;
1221 ConstantInt *CI;
1222 if (match(Idx, m_And(m_Value(IdxBase), m_ConstantInt(CI)))) {
1223 IdxRange = IdxRange.binaryAnd(CI->getValue());
1224 } else if (match(Idx, m_URem(m_Value(IdxBase), m_ConstantInt(CI)))) {
1225 IdxRange = IdxRange.urem(CI->getValue());
1226 }
1227
1228 if (ValidIndices.contains(IdxRange))
1229 return ScalarizationResult::safeWithFreeze(IdxBase);
1230 return ScalarizationResult::unsafe();
1231}
1232
1233/// The memory operation on a vector of \p ScalarType had alignment of
1234/// \p VectorAlignment. Compute the maximal, but conservatively correct,
1235/// alignment that will be valid for the memory operation on a single scalar
1236/// element of the same type with index \p Idx.
1238 Type *ScalarType, Value *Idx,
1239 const DataLayout &DL) {
1240 if (auto *C = dyn_cast<ConstantInt>(Idx))
1241 return commonAlignment(VectorAlignment,
1242 C->getZExtValue() * DL.getTypeStoreSize(ScalarType));
1243 return commonAlignment(VectorAlignment, DL.getTypeStoreSize(ScalarType));
1244}
1245
1246// Combine patterns like:
1247// %0 = load <4 x i32>, <4 x i32>* %a
1248// %1 = insertelement <4 x i32> %0, i32 %b, i32 1
1249// store <4 x i32> %1, <4 x i32>* %a
1250// to:
1251// %0 = bitcast <4 x i32>* %a to i32*
1252// %1 = getelementptr inbounds i32, i32* %0, i64 0, i64 1
1253// store i32 %b, i32* %1
1254bool VectorCombine::foldSingleElementStore(Instruction &I) {
1255 auto *SI = cast<StoreInst>(&I);
1256 if (!SI->isSimple() || !isa<VectorType>(SI->getValueOperand()->getType()))
1257 return false;
1258
1259 // TODO: Combine more complicated patterns (multiple insert) by referencing
1260 // TargetTransformInfo.
1262 Value *NewElement;
1263 Value *Idx;
1264 if (!match(SI->getValueOperand(),
1265 m_InsertElt(m_Instruction(Source), m_Value(NewElement),
1266 m_Value(Idx))))
1267 return false;
1268
1269 if (auto *Load = dyn_cast<LoadInst>(Source)) {
1270 auto VecTy = cast<VectorType>(SI->getValueOperand()->getType());
1271 Value *SrcAddr = Load->getPointerOperand()->stripPointerCasts();
1272 // Don't optimize for atomic/volatile load or store. Ensure memory is not
1273 // modified between, vector type matches store size, and index is inbounds.
1274 if (!Load->isSimple() || Load->getParent() != SI->getParent() ||
1275 !DL->typeSizeEqualsStoreSize(Load->getType()->getScalarType()) ||
1276 SrcAddr != SI->getPointerOperand()->stripPointerCasts())
1277 return false;
1278
1279 auto ScalarizableIdx = canScalarizeAccess(VecTy, Idx, Load, AC, DT);
1280 if (ScalarizableIdx.isUnsafe() ||
1281 isMemModifiedBetween(Load->getIterator(), SI->getIterator(),
1282 MemoryLocation::get(SI), AA))
1283 return false;
1284
1285 if (ScalarizableIdx.isSafeWithFreeze())
1286 ScalarizableIdx.freeze(Builder, *cast<Instruction>(Idx));
1287 Value *GEP = Builder.CreateInBoundsGEP(
1288 SI->getValueOperand()->getType(), SI->getPointerOperand(),
1289 {ConstantInt::get(Idx->getType(), 0), Idx});
1290 StoreInst *NSI = Builder.CreateStore(NewElement, GEP);
1291 NSI->copyMetadata(*SI);
1292 Align ScalarOpAlignment = computeAlignmentAfterScalarization(
1293 std::max(SI->getAlign(), Load->getAlign()), NewElement->getType(), Idx,
1294 *DL);
1295 NSI->setAlignment(ScalarOpAlignment);
1296 replaceValue(I, *NSI);
1298 return true;
1299 }
1300
1301 return false;
1302}
1303
1304/// Try to scalarize vector loads feeding extractelement instructions.
1305bool VectorCombine::scalarizeLoadExtract(Instruction &I) {
1306 Value *Ptr;
1307 if (!match(&I, m_Load(m_Value(Ptr))))
1308 return false;
1309
1310 auto *VecTy = cast<VectorType>(I.getType());
1311 auto *LI = cast<LoadInst>(&I);
1312 if (LI->isVolatile() || !DL->typeSizeEqualsStoreSize(VecTy->getScalarType()))
1313 return false;
1314
1315 InstructionCost OriginalCost =
1316 TTI.getMemoryOpCost(Instruction::Load, VecTy, LI->getAlign(),
1317 LI->getPointerAddressSpace());
1318 InstructionCost ScalarizedCost = 0;
1319
1320 Instruction *LastCheckedInst = LI;
1321 unsigned NumInstChecked = 0;
1323 auto FailureGuard = make_scope_exit([&]() {
1324 // If the transform is aborted, discard the ScalarizationResults.
1325 for (auto &Pair : NeedFreeze)
1326 Pair.second.discard();
1327 });
1328
1329 // Check if all users of the load are extracts with no memory modifications
1330 // between the load and the extract. Compute the cost of both the original
1331 // code and the scalarized version.
1332 for (User *U : LI->users()) {
1333 auto *UI = dyn_cast<ExtractElementInst>(U);
1334 if (!UI || UI->getParent() != LI->getParent())
1335 return false;
1336
1337 // Check if any instruction between the load and the extract may modify
1338 // memory.
1339 if (LastCheckedInst->comesBefore(UI)) {
1340 for (Instruction &I :
1341 make_range(std::next(LI->getIterator()), UI->getIterator())) {
1342 // Bail out if we reached the check limit or the instruction may write
1343 // to memory.
1344 if (NumInstChecked == MaxInstrsToScan || I.mayWriteToMemory())
1345 return false;
1346 NumInstChecked++;
1347 }
1348 LastCheckedInst = UI;
1349 }
1350
1351 auto ScalarIdx = canScalarizeAccess(VecTy, UI->getOperand(1), &I, AC, DT);
1352 if (ScalarIdx.isUnsafe())
1353 return false;
1354 if (ScalarIdx.isSafeWithFreeze()) {
1355 NeedFreeze.try_emplace(UI, ScalarIdx);
1356 ScalarIdx.discard();
1357 }
1358
1359 auto *Index = dyn_cast<ConstantInt>(UI->getOperand(1));
1361 OriginalCost +=
1362 TTI.getVectorInstrCost(Instruction::ExtractElement, VecTy, CostKind,
1363 Index ? Index->getZExtValue() : -1);
1364 ScalarizedCost +=
1365 TTI.getMemoryOpCost(Instruction::Load, VecTy->getElementType(),
1366 Align(1), LI->getPointerAddressSpace());
1367 ScalarizedCost += TTI.getAddressComputationCost(VecTy->getElementType());
1368 }
1369
1370 if (ScalarizedCost >= OriginalCost)
1371 return false;
1372
1373 // Replace extracts with narrow scalar loads.
1374 for (User *U : LI->users()) {
1375 auto *EI = cast<ExtractElementInst>(U);
1376 Value *Idx = EI->getOperand(1);
1377
1378 // Insert 'freeze' for poison indexes.
1379 auto It = NeedFreeze.find(EI);
1380 if (It != NeedFreeze.end())
1381 It->second.freeze(Builder, *cast<Instruction>(Idx));
1382
1383 Builder.SetInsertPoint(EI);
1384 Value *GEP =
1385 Builder.CreateInBoundsGEP(VecTy, Ptr, {Builder.getInt32(0), Idx});
1386 auto *NewLoad = cast<LoadInst>(Builder.CreateLoad(
1387 VecTy->getElementType(), GEP, EI->getName() + ".scalar"));
1388
1389 Align ScalarOpAlignment = computeAlignmentAfterScalarization(
1390 LI->getAlign(), VecTy->getElementType(), Idx, *DL);
1391 NewLoad->setAlignment(ScalarOpAlignment);
1392
1393 replaceValue(*EI, *NewLoad);
1394 }
1395
1396 FailureGuard.release();
1397 return true;
1398}
1399
1400/// Try to convert "shuffle (binop), (binop)" into "binop (shuffle), (shuffle)".
1401bool VectorCombine::foldShuffleOfBinops(Instruction &I) {
1402 BinaryOperator *B0, *B1;
1403 ArrayRef<int> OldMask;
1404 if (!match(&I, m_Shuffle(m_OneUse(m_BinOp(B0)), m_OneUse(m_BinOp(B1)),
1405 m_Mask(OldMask))))
1406 return false;
1407
1408 // Don't introduce poison into div/rem.
1409 if (any_of(OldMask, [](int M) { return M == PoisonMaskElem; }) &&
1410 B0->isIntDivRem())
1411 return false;
1412
1413 // TODO: Add support for addlike etc.
1414 Instruction::BinaryOps Opcode = B0->getOpcode();
1415 if (Opcode != B1->getOpcode())
1416 return false;
1417
1418 auto *ShuffleDstTy = dyn_cast<FixedVectorType>(I.getType());
1419 auto *BinOpTy = dyn_cast<FixedVectorType>(B0->getType());
1420 if (!ShuffleDstTy || !BinOpTy)
1421 return false;
1422
1423 unsigned NumSrcElts = BinOpTy->getNumElements();
1424
1425 // If we have something like "add X, Y" and "add Z, X", swap ops to match.
1426 Value *X = B0->getOperand(0), *Y = B0->getOperand(1);
1427 Value *Z = B1->getOperand(0), *W = B1->getOperand(1);
1428 if (BinaryOperator::isCommutative(Opcode) && X != Z && Y != W &&
1429 (X == W || Y == Z))
1430 std::swap(X, Y);
1431
1432 auto ConvertToUnary = [NumSrcElts](int &M) {
1433 if (M >= (int)NumSrcElts)
1434 M -= NumSrcElts;
1435 };
1436
1437 SmallVector<int> NewMask0(OldMask.begin(), OldMask.end());
1439 if (X == Z) {
1440 llvm::for_each(NewMask0, ConvertToUnary);
1442 Z = PoisonValue::get(BinOpTy);
1443 }
1444
1445 SmallVector<int> NewMask1(OldMask.begin(), OldMask.end());
1447 if (Y == W) {
1448 llvm::for_each(NewMask1, ConvertToUnary);
1450 W = PoisonValue::get(BinOpTy);
1451 }
1452
1453 // Try to replace a binop with a shuffle if the shuffle is not costly.
1455
1456 InstructionCost OldCost =
1457 TTI.getArithmeticInstrCost(B0->getOpcode(), BinOpTy, CostKind) +
1458 TTI.getArithmeticInstrCost(B1->getOpcode(), BinOpTy, CostKind) +
1460 OldMask, CostKind, 0, nullptr, {B0, B1}, &I);
1461
1462 InstructionCost NewCost =
1463 TTI.getShuffleCost(SK0, BinOpTy, NewMask0, CostKind, 0, nullptr, {X, Z}) +
1464 TTI.getShuffleCost(SK1, BinOpTy, NewMask1, CostKind, 0, nullptr, {Y, W}) +
1465 TTI.getArithmeticInstrCost(Opcode, ShuffleDstTy, CostKind);
1466
1467 LLVM_DEBUG(dbgs() << "Found a shuffle feeding two binops: " << I
1468 << "\n OldCost: " << OldCost << " vs NewCost: " << NewCost
1469 << "\n");
1470 if (NewCost >= OldCost)
1471 return false;
1472
1473 Value *Shuf0 = Builder.CreateShuffleVector(X, Z, NewMask0);
1474 Value *Shuf1 = Builder.CreateShuffleVector(Y, W, NewMask1);
1475 Value *NewBO = Builder.CreateBinOp(Opcode, Shuf0, Shuf1);
1476
1477 // Intersect flags from the old binops.
1478 if (auto *NewInst = dyn_cast<Instruction>(NewBO)) {
1479 NewInst->copyIRFlags(B0);
1480 NewInst->andIRFlags(B1);
1481 }
1482
1483 Worklist.pushValue(Shuf0);
1484 Worklist.pushValue(Shuf1);
1485 replaceValue(I, *NewBO);
1486 return true;
1487}
1488
1489/// Try to convert "shuffle (castop), (castop)" with a shared castop operand
1490/// into "castop (shuffle)".
1491bool VectorCombine::foldShuffleOfCastops(Instruction &I) {
1492 Value *V0, *V1;
1493 ArrayRef<int> OldMask;
1494 if (!match(&I, m_Shuffle(m_OneUse(m_Value(V0)), m_OneUse(m_Value(V1)),
1495 m_Mask(OldMask))))
1496 return false;
1497
1498 auto *C0 = dyn_cast<CastInst>(V0);
1499 auto *C1 = dyn_cast<CastInst>(V1);
1500 if (!C0 || !C1)
1501 return false;
1502
1503 Instruction::CastOps Opcode = C0->getOpcode();
1504 if (C0->getSrcTy() != C1->getSrcTy())
1505 return false;
1506
1507 // Handle shuffle(zext_nneg(x), sext(y)) -> sext(shuffle(x,y)) folds.
1508 if (Opcode != C1->getOpcode()) {
1509 if (match(C0, m_SExtLike(m_Value())) && match(C1, m_SExtLike(m_Value())))
1510 Opcode = Instruction::SExt;
1511 else
1512 return false;
1513 }
1514
1515 auto *ShuffleDstTy = dyn_cast<FixedVectorType>(I.getType());
1516 auto *CastDstTy = dyn_cast<FixedVectorType>(C0->getDestTy());
1517 auto *CastSrcTy = dyn_cast<FixedVectorType>(C0->getSrcTy());
1518 if (!ShuffleDstTy || !CastDstTy || !CastSrcTy)
1519 return false;
1520
1521 unsigned NumSrcElts = CastSrcTy->getNumElements();
1522 unsigned NumDstElts = CastDstTy->getNumElements();
1523 assert((NumDstElts == NumSrcElts || Opcode == Instruction::BitCast) &&
1524 "Only bitcasts expected to alter src/dst element counts");
1525
1526 // Check for bitcasting of unscalable vector types.
1527 // e.g. <32 x i40> -> <40 x i32>
1528 if (NumDstElts != NumSrcElts && (NumSrcElts % NumDstElts) != 0 &&
1529 (NumDstElts % NumSrcElts) != 0)
1530 return false;
1531
1532 SmallVector<int, 16> NewMask;
1533 if (NumSrcElts >= NumDstElts) {
1534 // The bitcast is from wide to narrow/equal elements. The shuffle mask can
1535 // always be expanded to the equivalent form choosing narrower elements.
1536 assert(NumSrcElts % NumDstElts == 0 && "Unexpected shuffle mask");
1537 unsigned ScaleFactor = NumSrcElts / NumDstElts;
1538 narrowShuffleMaskElts(ScaleFactor, OldMask, NewMask);
1539 } else {
1540 // The bitcast is from narrow elements to wide elements. The shuffle mask
1541 // must choose consecutive elements to allow casting first.
1542 assert(NumDstElts % NumSrcElts == 0 && "Unexpected shuffle mask");
1543 unsigned ScaleFactor = NumDstElts / NumSrcElts;
1544 if (!widenShuffleMaskElts(ScaleFactor, OldMask, NewMask))
1545 return false;
1546 }
1547
1548 auto *NewShuffleDstTy =
1549 FixedVectorType::get(CastSrcTy->getScalarType(), NewMask.size());
1550
1551 // Try to replace a castop with a shuffle if the shuffle is not costly.
1553
1554 InstructionCost OldCost =
1555 TTI.getCastInstrCost(C0->getOpcode(), CastDstTy, CastSrcTy,
1557 TTI.getCastInstrCost(C1->getOpcode(), CastDstTy, CastSrcTy,
1559 OldCost +=
1561 OldMask, CostKind, 0, nullptr, std::nullopt, &I);
1562
1564 TargetTransformInfo::SK_PermuteTwoSrc, CastSrcTy, NewMask, CostKind);
1565 NewCost += TTI.getCastInstrCost(Opcode, ShuffleDstTy, NewShuffleDstTy,
1567
1568 LLVM_DEBUG(dbgs() << "Found a shuffle feeding two casts: " << I
1569 << "\n OldCost: " << OldCost << " vs NewCost: " << NewCost
1570 << "\n");
1571 if (NewCost > OldCost)
1572 return false;
1573
1574 Value *Shuf = Builder.CreateShuffleVector(C0->getOperand(0),
1575 C1->getOperand(0), NewMask);
1576 Value *Cast = Builder.CreateCast(Opcode, Shuf, ShuffleDstTy);
1577
1578 // Intersect flags from the old casts.
1579 if (auto *NewInst = dyn_cast<Instruction>(Cast)) {
1580 NewInst->copyIRFlags(C0);
1581 NewInst->andIRFlags(C1);
1582 }
1583
1584 Worklist.pushValue(Shuf);
1585 replaceValue(I, *Cast);
1586 return true;
1587}
1588
1589/// Try to convert "shuffle (shuffle x, undef), (shuffle y, undef)"
1590/// into "shuffle x, y".
1591bool VectorCombine::foldShuffleOfShuffles(Instruction &I) {
1592 Value *V0, *V1;
1593 UndefValue *U0, *U1;
1594 ArrayRef<int> OuterMask, InnerMask0, InnerMask1;
1596 m_Mask(InnerMask0))),
1598 m_Mask(InnerMask1))),
1599 m_Mask(OuterMask))))
1600 return false;
1601
1602 auto *ShufI0 = dyn_cast<Instruction>(I.getOperand(0));
1603 auto *ShufI1 = dyn_cast<Instruction>(I.getOperand(1));
1604 auto *ShuffleDstTy = dyn_cast<FixedVectorType>(I.getType());
1605 auto *ShuffleSrcTy = dyn_cast<FixedVectorType>(V0->getType());
1606 auto *ShuffleImmTy = dyn_cast<FixedVectorType>(I.getOperand(0)->getType());
1607 if (!ShuffleDstTy || !ShuffleSrcTy || !ShuffleImmTy ||
1608 V0->getType() != V1->getType())
1609 return false;
1610
1611 unsigned NumSrcElts = ShuffleSrcTy->getNumElements();
1612 unsigned NumImmElts = ShuffleImmTy->getNumElements();
1613
1614 // Bail if either inner masks reference a RHS undef arg.
1615 if ((!isa<PoisonValue>(U0) &&
1616 any_of(InnerMask0, [&](int M) { return M >= (int)NumSrcElts; })) ||
1617 (!isa<PoisonValue>(U1) &&
1618 any_of(InnerMask1, [&](int M) { return M >= (int)NumSrcElts; })))
1619 return false;
1620
1621 // Merge shuffles - replace index to the RHS poison arg with PoisonMaskElem,
1622 SmallVector<int, 16> NewMask(OuterMask.begin(), OuterMask.end());
1623 for (int &M : NewMask) {
1624 if (0 <= M && M < (int)NumImmElts) {
1625 M = (InnerMask0[M] >= (int)NumSrcElts) ? PoisonMaskElem : InnerMask0[M];
1626 } else if (M >= (int)NumImmElts) {
1627 if (InnerMask1[M - NumImmElts] >= (int)NumSrcElts)
1628 M = PoisonMaskElem;
1629 else
1630 M = InnerMask1[M - NumImmElts] + (V0 == V1 ? 0 : NumSrcElts);
1631 }
1632 }
1633
1634 // Have we folded to an Identity shuffle?
1635 if (ShuffleVectorInst::isIdentityMask(NewMask, NumSrcElts)) {
1636 replaceValue(I, *V0);
1637 return true;
1638 }
1639
1640 // Try to merge the shuffles if the new shuffle is not costly.
1642
1643 InstructionCost OldCost =
1645 InnerMask0, CostKind, 0, nullptr, {V0, U0}, ShufI0) +
1647 InnerMask1, CostKind, 0, nullptr, {V1, U1}, ShufI1) +
1649 OuterMask, CostKind, 0, nullptr, {ShufI0, ShufI1}, &I);
1650
1651 InstructionCost NewCost =
1653 NewMask, CostKind, 0, nullptr, {V0, V1});
1654
1655 LLVM_DEBUG(dbgs() << "Found a shuffle feeding two shuffles: " << I
1656 << "\n OldCost: " << OldCost << " vs NewCost: " << NewCost
1657 << "\n");
1658 if (NewCost > OldCost)
1659 return false;
1660
1661 // Clear unused sources to poison.
1662 if (none_of(NewMask, [&](int M) { return 0 <= M && M < (int)NumSrcElts; }))
1663 V0 = PoisonValue::get(ShuffleSrcTy);
1664 if (none_of(NewMask, [&](int M) { return (int)NumSrcElts <= M; }))
1665 V1 = PoisonValue::get(ShuffleSrcTy);
1666
1667 Value *Shuf = Builder.CreateShuffleVector(V0, V1, NewMask);
1668 replaceValue(I, *Shuf);
1669 return true;
1670}
1671
1672using InstLane = std::pair<Use *, int>;
1673
1674static InstLane lookThroughShuffles(Use *U, int Lane) {
1675 while (auto *SV = dyn_cast<ShuffleVectorInst>(U->get())) {
1676 unsigned NumElts =
1677 cast<FixedVectorType>(SV->getOperand(0)->getType())->getNumElements();
1678 int M = SV->getMaskValue(Lane);
1679 if (M < 0)
1680 return {nullptr, PoisonMaskElem};
1681 if (static_cast<unsigned>(M) < NumElts) {
1682 U = &SV->getOperandUse(0);
1683 Lane = M;
1684 } else {
1685 U = &SV->getOperandUse(1);
1686 Lane = M - NumElts;
1687 }
1688 }
1689 return InstLane{U, Lane};
1690}
1691
1695 for (InstLane IL : Item) {
1696 auto [U, Lane] = IL;
1697 InstLane OpLane =
1698 U ? lookThroughShuffles(&cast<Instruction>(U->get())->getOperandUse(Op),
1699 Lane)
1700 : InstLane{nullptr, PoisonMaskElem};
1701 NItem.emplace_back(OpLane);
1702 }
1703 return NItem;
1704}
1705
1707 const SmallPtrSet<Use *, 4> &IdentityLeafs,
1708 const SmallPtrSet<Use *, 4> &SplatLeafs,
1709 IRBuilder<> &Builder) {
1710 auto [FrontU, FrontLane] = Item.front();
1711
1712 if (IdentityLeafs.contains(FrontU)) {
1713 return FrontU->get();
1714 }
1715 if (SplatLeafs.contains(FrontU)) {
1716 if (auto *ILI = dyn_cast<Instruction>(FrontU))
1717 Builder.SetInsertPoint(*ILI->getInsertionPointAfterDef());
1718 else if (auto *Arg = dyn_cast<Argument>(FrontU))
1719 Builder.SetInsertPointPastAllocas(Arg->getParent());
1720 SmallVector<int, 16> Mask(Ty->getNumElements(), FrontLane);
1721 return Builder.CreateShuffleVector(FrontU->get(), Mask);
1722 }
1723
1724 auto *I = cast<Instruction>(FrontU->get());
1725 auto *II = dyn_cast<IntrinsicInst>(I);
1726 unsigned NumOps = I->getNumOperands() - (II ? 1 : 0);
1727 SmallVector<Value *> Ops(NumOps);
1728 for (unsigned Idx = 0; Idx < NumOps; Idx++) {
1729 if (II && isVectorIntrinsicWithScalarOpAtArg(II->getIntrinsicID(), Idx)) {
1730 Ops[Idx] = II->getOperand(Idx);
1731 continue;
1732 }
1734 Ty, IdentityLeafs, SplatLeafs, Builder);
1735 }
1736
1737 SmallVector<Value *, 8> ValueList;
1738 for (const auto &Lane : Item)
1739 if (Lane.first)
1740 ValueList.push_back(Lane.first->get());
1741
1742 Builder.SetInsertPoint(I);
1743 Type *DstTy =
1744 FixedVectorType::get(I->getType()->getScalarType(), Ty->getNumElements());
1745 if (auto *BI = dyn_cast<BinaryOperator>(I)) {
1746 auto *Value = Builder.CreateBinOp((Instruction::BinaryOps)BI->getOpcode(),
1747 Ops[0], Ops[1]);
1748 propagateIRFlags(Value, ValueList);
1749 return Value;
1750 }
1751 if (auto *CI = dyn_cast<CmpInst>(I)) {
1752 auto *Value = Builder.CreateCmp(CI->getPredicate(), Ops[0], Ops[1]);
1753 propagateIRFlags(Value, ValueList);
1754 return Value;
1755 }
1756 if (auto *SI = dyn_cast<SelectInst>(I)) {
1757 auto *Value = Builder.CreateSelect(Ops[0], Ops[1], Ops[2], "", SI);
1758 propagateIRFlags(Value, ValueList);
1759 return Value;
1760 }
1761 if (auto *CI = dyn_cast<CastInst>(I)) {
1762 auto *Value = Builder.CreateCast((Instruction::CastOps)CI->getOpcode(),
1763 Ops[0], DstTy);
1764 propagateIRFlags(Value, ValueList);
1765 return Value;
1766 }
1767 if (II) {
1768 auto *Value = Builder.CreateIntrinsic(DstTy, II->getIntrinsicID(), Ops);
1769 propagateIRFlags(Value, ValueList);
1770 return Value;
1771 }
1772 assert(isa<UnaryInstruction>(I) && "Unexpected instruction type in Generate");
1773 auto *Value =
1774 Builder.CreateUnOp((Instruction::UnaryOps)I->getOpcode(), Ops[0]);
1775 propagateIRFlags(Value, ValueList);
1776 return Value;
1777}
1778
1779// Starting from a shuffle, look up through operands tracking the shuffled index
1780// of each lane. If we can simplify away the shuffles to identities then
1781// do so.
1782bool VectorCombine::foldShuffleToIdentity(Instruction &I) {
1783 auto *Ty = dyn_cast<FixedVectorType>(I.getType());
1784 if (!Ty || I.use_empty())
1785 return false;
1786
1787 SmallVector<InstLane> Start(Ty->getNumElements());
1788 for (unsigned M = 0, E = Ty->getNumElements(); M < E; ++M)
1789 Start[M] = lookThroughShuffles(&*I.use_begin(), M);
1790
1792 Worklist.push_back(Start);
1793 SmallPtrSet<Use *, 4> IdentityLeafs, SplatLeafs;
1794 unsigned NumVisited = 0;
1795
1796 while (!Worklist.empty()) {
1797 if (++NumVisited > MaxInstrsToScan)
1798 return false;
1799
1800 SmallVector<InstLane> Item = Worklist.pop_back_val();
1801 auto [FrontU, FrontLane] = Item.front();
1802
1803 // If we found an undef first lane then bail out to keep things simple.
1804 if (!FrontU)
1805 return false;
1806
1807 // Look for an identity value.
1808 if (FrontLane == 0 &&
1809 cast<FixedVectorType>(FrontU->get()->getType())->getNumElements() ==
1810 Ty->getNumElements() &&
1811 all_of(drop_begin(enumerate(Item)), [Item](const auto &E) {
1812 Value *FrontV = Item.front().first->get();
1813 return !E.value().first || (E.value().first->get() == FrontV &&
1814 E.value().second == (int)E.index());
1815 })) {
1816 IdentityLeafs.insert(FrontU);
1817 continue;
1818 }
1819 // Look for constants, for the moment only supporting constant splats.
1820 if (auto *C = dyn_cast<Constant>(FrontU);
1821 C && C->getSplatValue() &&
1822 all_of(drop_begin(Item), [Item](InstLane &IL) {
1823 Value *FrontV = Item.front().first->get();
1824 Use *U = IL.first;
1825 return !U || U->get() == FrontV;
1826 })) {
1827 SplatLeafs.insert(FrontU);
1828 continue;
1829 }
1830 // Look for a splat value.
1831 if (all_of(drop_begin(Item), [Item](InstLane &IL) {
1832 auto [FrontU, FrontLane] = Item.front();
1833 auto [U, Lane] = IL;
1834 return !U || (U->get() == FrontU->get() && Lane == FrontLane);
1835 })) {
1836 SplatLeafs.insert(FrontU);
1837 continue;
1838 }
1839
1840 // We need each element to be the same type of value, and check that each
1841 // element has a single use.
1842 if (!all_of(drop_begin(Item), [Item](InstLane IL) {
1843 Value *FrontV = Item.front().first->get();
1844 if (!IL.first)
1845 return true;
1846 Value *V = IL.first->get();
1847 if (auto *I = dyn_cast<Instruction>(V); I && !I->hasOneUse())
1848 return false;
1849 if (V->getValueID() != FrontV->getValueID())
1850 return false;
1851 if (auto *CI = dyn_cast<CmpInst>(V))
1852 if (CI->getPredicate() != cast<CmpInst>(FrontV)->getPredicate())
1853 return false;
1854 if (auto *SI = dyn_cast<SelectInst>(V))
1855 if (!isa<VectorType>(SI->getOperand(0)->getType()))
1856 return false;
1857 if (isa<CallInst>(V) && !isa<IntrinsicInst>(V))
1858 return false;
1859 auto *II = dyn_cast<IntrinsicInst>(V);
1860 return !II || (isa<IntrinsicInst>(FrontV) &&
1861 II->getIntrinsicID() ==
1862 cast<IntrinsicInst>(FrontV)->getIntrinsicID());
1863 }))
1864 return false;
1865
1866 // Check the operator is one that we support. We exclude div/rem in case
1867 // they hit UB from poison lanes.
1868 if ((isa<BinaryOperator>(FrontU) &&
1869 !cast<BinaryOperator>(FrontU)->isIntDivRem()) ||
1870 isa<CmpInst>(FrontU)) {
1873 } else if (isa<UnaryOperator, TruncInst, ZExtInst, SExtInst>(FrontU)) {
1875 } else if (isa<SelectInst>(FrontU)) {
1879 } else if (auto *II = dyn_cast<IntrinsicInst>(FrontU);
1880 II && isTriviallyVectorizable(II->getIntrinsicID())) {
1881 for (unsigned Op = 0, E = II->getNumOperands() - 1; Op < E; Op++) {
1882 if (isVectorIntrinsicWithScalarOpAtArg(II->getIntrinsicID(), Op)) {
1883 if (!all_of(drop_begin(Item), [Item, Op](InstLane &IL) {
1884 Value *FrontV = Item.front().first->get();
1885 Use *U = IL.first;
1886 return !U || (cast<Instruction>(U->get())->getOperand(Op) ==
1887 cast<Instruction>(FrontV)->getOperand(Op));
1888 }))
1889 return false;
1890 continue;
1891 }
1893 }
1894 } else {
1895 return false;
1896 }
1897 }
1898
1899 if (NumVisited <= 1)
1900 return false;
1901
1902 // If we got this far, we know the shuffles are superfluous and can be
1903 // removed. Scan through again and generate the new tree of instructions.
1904 Value *V = generateNewInstTree(Start, Ty, IdentityLeafs, SplatLeafs, Builder);
1905 replaceValue(I, *V);
1906 return true;
1907}
1908
1909/// Given a commutative reduction, the order of the input lanes does not alter
1910/// the results. We can use this to remove certain shuffles feeding the
1911/// reduction, removing the need to shuffle at all.
1912bool VectorCombine::foldShuffleFromReductions(Instruction &I) {
1913 auto *II = dyn_cast<IntrinsicInst>(&I);
1914 if (!II)
1915 return false;
1916 switch (II->getIntrinsicID()) {
1917 case Intrinsic::vector_reduce_add:
1918 case Intrinsic::vector_reduce_mul:
1919 case Intrinsic::vector_reduce_and:
1920 case Intrinsic::vector_reduce_or:
1921 case Intrinsic::vector_reduce_xor:
1922 case Intrinsic::vector_reduce_smin:
1923 case Intrinsic::vector_reduce_smax:
1924 case Intrinsic::vector_reduce_umin:
1925 case Intrinsic::vector_reduce_umax:
1926 break;
1927 default:
1928 return false;
1929 }
1930
1931 // Find all the inputs when looking through operations that do not alter the
1932 // lane order (binops, for example). Currently we look for a single shuffle,
1933 // and can ignore splat values.
1934 std::queue<Value *> Worklist;
1936 ShuffleVectorInst *Shuffle = nullptr;
1937 if (auto *Op = dyn_cast<Instruction>(I.getOperand(0)))
1938 Worklist.push(Op);
1939
1940 while (!Worklist.empty()) {
1941 Value *CV = Worklist.front();
1942 Worklist.pop();
1943 if (Visited.contains(CV))
1944 continue;
1945
1946 // Splats don't change the order, so can be safely ignored.
1947 if (isSplatValue(CV))
1948 continue;
1949
1950 Visited.insert(CV);
1951
1952 if (auto *CI = dyn_cast<Instruction>(CV)) {
1953 if (CI->isBinaryOp()) {
1954 for (auto *Op : CI->operand_values())
1955 Worklist.push(Op);
1956 continue;
1957 } else if (auto *SV = dyn_cast<ShuffleVectorInst>(CI)) {
1958 if (Shuffle && Shuffle != SV)
1959 return false;
1960 Shuffle = SV;
1961 continue;
1962 }
1963 }
1964
1965 // Anything else is currently an unknown node.
1966 return false;
1967 }
1968
1969 if (!Shuffle)
1970 return false;
1971
1972 // Check all uses of the binary ops and shuffles are also included in the
1973 // lane-invariant operations (Visited should be the list of lanewise
1974 // instructions, including the shuffle that we found).
1975 for (auto *V : Visited)
1976 for (auto *U : V->users())
1977 if (!Visited.contains(U) && U != &I)
1978 return false;
1979
1981 dyn_cast<FixedVectorType>(II->getOperand(0)->getType());
1982 if (!VecType)
1983 return false;
1984 FixedVectorType *ShuffleInputType =
1985 dyn_cast<FixedVectorType>(Shuffle->getOperand(0)->getType());
1986 if (!ShuffleInputType)
1987 return false;
1988 unsigned NumInputElts = ShuffleInputType->getNumElements();
1989
1990 // Find the mask from sorting the lanes into order. This is most likely to
1991 // become a identity or concat mask. Undef elements are pushed to the end.
1992 SmallVector<int> ConcatMask;
1993 Shuffle->getShuffleMask(ConcatMask);
1994 sort(ConcatMask, [](int X, int Y) { return (unsigned)X < (unsigned)Y; });
1995 // In the case of a truncating shuffle it's possible for the mask
1996 // to have an index greater than the size of the resulting vector.
1997 // This requires special handling.
1998 bool IsTruncatingShuffle = VecType->getNumElements() < NumInputElts;
1999 bool UsesSecondVec =
2000 any_of(ConcatMask, [&](int M) { return M >= (int)NumInputElts; });
2001
2002 FixedVectorType *VecTyForCost =
2003 (UsesSecondVec && !IsTruncatingShuffle) ? VecType : ShuffleInputType;
2006 VecTyForCost, Shuffle->getShuffleMask());
2009 VecTyForCost, ConcatMask);
2010
2011 LLVM_DEBUG(dbgs() << "Found a reduction feeding from a shuffle: " << *Shuffle
2012 << "\n");
2013 LLVM_DEBUG(dbgs() << " OldCost: " << OldCost << " vs NewCost: " << NewCost
2014 << "\n");
2015 if (NewCost < OldCost) {
2016 Builder.SetInsertPoint(Shuffle);
2017 Value *NewShuffle = Builder.CreateShuffleVector(
2018 Shuffle->getOperand(0), Shuffle->getOperand(1), ConcatMask);
2019 LLVM_DEBUG(dbgs() << "Created new shuffle: " << *NewShuffle << "\n");
2020 replaceValue(*Shuffle, *NewShuffle);
2021 }
2022
2023 // See if we can re-use foldSelectShuffle, getting it to reduce the size of
2024 // the shuffle into a nicer order, as it can ignore the order of the shuffles.
2025 return foldSelectShuffle(*Shuffle, true);
2026}
2027
2028/// Determine if its more efficient to fold:
2029/// reduce(trunc(x)) -> trunc(reduce(x)).
2030bool VectorCombine::foldTruncFromReductions(Instruction &I) {
2031 auto *II = dyn_cast<IntrinsicInst>(&I);
2032 if (!II)
2033 return false;
2034
2035 Intrinsic::ID IID = II->getIntrinsicID();
2036 switch (IID) {
2037 case Intrinsic::vector_reduce_add:
2038 case Intrinsic::vector_reduce_mul:
2039 case Intrinsic::vector_reduce_and:
2040 case Intrinsic::vector_reduce_or:
2041 case Intrinsic::vector_reduce_xor:
2042 break;
2043 default:
2044 return false;
2045 }
2046
2047 unsigned ReductionOpc = getArithmeticReductionInstruction(IID);
2048 Value *ReductionSrc = I.getOperand(0);
2049
2050 Value *TruncSrc;
2051 if (!match(ReductionSrc, m_OneUse(m_Trunc(m_Value(TruncSrc)))))
2052 return false;
2053
2054 auto *TruncSrcTy = cast<VectorType>(TruncSrc->getType());
2055 auto *ReductionSrcTy = cast<VectorType>(ReductionSrc->getType());
2056 Type *ResultTy = I.getType();
2057
2060 ReductionOpc, ReductionSrcTy, std::nullopt, CostKind);
2061 if (auto *Trunc = dyn_cast<CastInst>(ReductionSrc))
2062 OldCost +=
2063 TTI.getCastInstrCost(Instruction::Trunc, ReductionSrcTy, TruncSrcTy,
2065 InstructionCost NewCost =
2066 TTI.getArithmeticReductionCost(ReductionOpc, TruncSrcTy, std::nullopt,
2067 CostKind) +
2068 TTI.getCastInstrCost(Instruction::Trunc, ResultTy,
2069 ReductionSrcTy->getScalarType(),
2071
2072 if (OldCost <= NewCost || !NewCost.isValid())
2073 return false;
2074
2075 Value *NewReduction = Builder.CreateIntrinsic(
2076 TruncSrcTy->getScalarType(), II->getIntrinsicID(), {TruncSrc});
2077 Value *NewTruncation = Builder.CreateTrunc(NewReduction, ResultTy);
2078 replaceValue(I, *NewTruncation);
2079 return true;
2080}
2081
2082/// This method looks for groups of shuffles acting on binops, of the form:
2083/// %x = shuffle ...
2084/// %y = shuffle ...
2085/// %a = binop %x, %y
2086/// %b = binop %x, %y
2087/// shuffle %a, %b, selectmask
2088/// We may, especially if the shuffle is wider than legal, be able to convert
2089/// the shuffle to a form where only parts of a and b need to be computed. On
2090/// architectures with no obvious "select" shuffle, this can reduce the total
2091/// number of operations if the target reports them as cheaper.
2092bool VectorCombine::foldSelectShuffle(Instruction &I, bool FromReduction) {
2093 auto *SVI = cast<ShuffleVectorInst>(&I);
2094 auto *VT = cast<FixedVectorType>(I.getType());
2095 auto *Op0 = dyn_cast<Instruction>(SVI->getOperand(0));
2096 auto *Op1 = dyn_cast<Instruction>(SVI->getOperand(1));
2097 if (!Op0 || !Op1 || Op0 == Op1 || !Op0->isBinaryOp() || !Op1->isBinaryOp() ||
2098 VT != Op0->getType())
2099 return false;
2100
2101 auto *SVI0A = dyn_cast<Instruction>(Op0->getOperand(0));
2102 auto *SVI0B = dyn_cast<Instruction>(Op0->getOperand(1));
2103 auto *SVI1A = dyn_cast<Instruction>(Op1->getOperand(0));
2104 auto *SVI1B = dyn_cast<Instruction>(Op1->getOperand(1));
2105 SmallPtrSet<Instruction *, 4> InputShuffles({SVI0A, SVI0B, SVI1A, SVI1B});
2106 auto checkSVNonOpUses = [&](Instruction *I) {
2107 if (!I || I->getOperand(0)->getType() != VT)
2108 return true;
2109 return any_of(I->users(), [&](User *U) {
2110 return U != Op0 && U != Op1 &&
2111 !(isa<ShuffleVectorInst>(U) &&
2112 (InputShuffles.contains(cast<Instruction>(U)) ||
2113 isInstructionTriviallyDead(cast<Instruction>(U))));
2114 });
2115 };
2116 if (checkSVNonOpUses(SVI0A) || checkSVNonOpUses(SVI0B) ||
2117 checkSVNonOpUses(SVI1A) || checkSVNonOpUses(SVI1B))
2118 return false;
2119
2120 // Collect all the uses that are shuffles that we can transform together. We
2121 // may not have a single shuffle, but a group that can all be transformed
2122 // together profitably.
2124 auto collectShuffles = [&](Instruction *I) {
2125 for (auto *U : I->users()) {
2126 auto *SV = dyn_cast<ShuffleVectorInst>(U);
2127 if (!SV || SV->getType() != VT)
2128 return false;
2129 if ((SV->getOperand(0) != Op0 && SV->getOperand(0) != Op1) ||
2130 (SV->getOperand(1) != Op0 && SV->getOperand(1) != Op1))
2131 return false;
2132 if (!llvm::is_contained(Shuffles, SV))
2133 Shuffles.push_back(SV);
2134 }
2135 return true;
2136 };
2137 if (!collectShuffles(Op0) || !collectShuffles(Op1))
2138 return false;
2139 // From a reduction, we need to be processing a single shuffle, otherwise the
2140 // other uses will not be lane-invariant.
2141 if (FromReduction && Shuffles.size() > 1)
2142 return false;
2143
2144 // Add any shuffle uses for the shuffles we have found, to include them in our
2145 // cost calculations.
2146 if (!FromReduction) {
2147 for (ShuffleVectorInst *SV : Shuffles) {
2148 for (auto *U : SV->users()) {
2149 ShuffleVectorInst *SSV = dyn_cast<ShuffleVectorInst>(U);
2150 if (SSV && isa<UndefValue>(SSV->getOperand(1)) && SSV->getType() == VT)
2151 Shuffles.push_back(SSV);
2152 }
2153 }
2154 }
2155
2156 // For each of the output shuffles, we try to sort all the first vector
2157 // elements to the beginning, followed by the second array elements at the
2158 // end. If the binops are legalized to smaller vectors, this may reduce total
2159 // number of binops. We compute the ReconstructMask mask needed to convert
2160 // back to the original lane order.
2162 SmallVector<SmallVector<int>> OrigReconstructMasks;
2163 int MaxV1Elt = 0, MaxV2Elt = 0;
2164 unsigned NumElts = VT->getNumElements();
2165 for (ShuffleVectorInst *SVN : Shuffles) {
2167 SVN->getShuffleMask(Mask);
2168
2169 // Check the operands are the same as the original, or reversed (in which
2170 // case we need to commute the mask).
2171 Value *SVOp0 = SVN->getOperand(0);
2172 Value *SVOp1 = SVN->getOperand(1);
2173 if (isa<UndefValue>(SVOp1)) {
2174 auto *SSV = cast<ShuffleVectorInst>(SVOp0);
2175 SVOp0 = SSV->getOperand(0);
2176 SVOp1 = SSV->getOperand(1);
2177 for (unsigned I = 0, E = Mask.size(); I != E; I++) {
2178 if (Mask[I] >= static_cast<int>(SSV->getShuffleMask().size()))
2179 return false;
2180 Mask[I] = Mask[I] < 0 ? Mask[I] : SSV->getMaskValue(Mask[I]);
2181 }
2182 }
2183 if (SVOp0 == Op1 && SVOp1 == Op0) {
2184 std::swap(SVOp0, SVOp1);
2186 }
2187 if (SVOp0 != Op0 || SVOp1 != Op1)
2188 return false;
2189
2190 // Calculate the reconstruction mask for this shuffle, as the mask needed to
2191 // take the packed values from Op0/Op1 and reconstructing to the original
2192 // order.
2193 SmallVector<int> ReconstructMask;
2194 for (unsigned I = 0; I < Mask.size(); I++) {
2195 if (Mask[I] < 0) {
2196 ReconstructMask.push_back(-1);
2197 } else if (Mask[I] < static_cast<int>(NumElts)) {
2198 MaxV1Elt = std::max(MaxV1Elt, Mask[I]);
2199 auto It = find_if(V1, [&](const std::pair<int, int> &A) {
2200 return Mask[I] == A.first;
2201 });
2202 if (It != V1.end())
2203 ReconstructMask.push_back(It - V1.begin());
2204 else {
2205 ReconstructMask.push_back(V1.size());
2206 V1.emplace_back(Mask[I], V1.size());
2207 }
2208 } else {
2209 MaxV2Elt = std::max<int>(MaxV2Elt, Mask[I] - NumElts);
2210 auto It = find_if(V2, [&](const std::pair<int, int> &A) {
2211 return Mask[I] - static_cast<int>(NumElts) == A.first;
2212 });
2213 if (It != V2.end())
2214 ReconstructMask.push_back(NumElts + It - V2.begin());
2215 else {
2216 ReconstructMask.push_back(NumElts + V2.size());
2217 V2.emplace_back(Mask[I] - NumElts, NumElts + V2.size());
2218 }
2219 }
2220 }
2221
2222 // For reductions, we know that the lane ordering out doesn't alter the
2223 // result. In-order can help simplify the shuffle away.
2224 if (FromReduction)
2225 sort(ReconstructMask);
2226 OrigReconstructMasks.push_back(std::move(ReconstructMask));
2227 }
2228
2229 // If the Maximum element used from V1 and V2 are not larger than the new
2230 // vectors, the vectors are already packes and performing the optimization
2231 // again will likely not help any further. This also prevents us from getting
2232 // stuck in a cycle in case the costs do not also rule it out.
2233 if (V1.empty() || V2.empty() ||
2234 (MaxV1Elt == static_cast<int>(V1.size()) - 1 &&
2235 MaxV2Elt == static_cast<int>(V2.size()) - 1))
2236 return false;
2237
2238 // GetBaseMaskValue takes one of the inputs, which may either be a shuffle, a
2239 // shuffle of another shuffle, or not a shuffle (that is treated like a
2240 // identity shuffle).
2241 auto GetBaseMaskValue = [&](Instruction *I, int M) {
2242 auto *SV = dyn_cast<ShuffleVectorInst>(I);
2243 if (!SV)
2244 return M;
2245 if (isa<UndefValue>(SV->getOperand(1)))
2246 if (auto *SSV = dyn_cast<ShuffleVectorInst>(SV->getOperand(0)))
2247 if (InputShuffles.contains(SSV))
2248 return SSV->getMaskValue(SV->getMaskValue(M));
2249 return SV->getMaskValue(M);
2250 };
2251
2252 // Attempt to sort the inputs my ascending mask values to make simpler input
2253 // shuffles and push complex shuffles down to the uses. We sort on the first
2254 // of the two input shuffle orders, to try and get at least one input into a
2255 // nice order.
2256 auto SortBase = [&](Instruction *A, std::pair<int, int> X,
2257 std::pair<int, int> Y) {
2258 int MXA = GetBaseMaskValue(A, X.first);
2259 int MYA = GetBaseMaskValue(A, Y.first);
2260 return MXA < MYA;
2261 };
2262 stable_sort(V1, [&](std::pair<int, int> A, std::pair<int, int> B) {
2263 return SortBase(SVI0A, A, B);
2264 });
2265 stable_sort(V2, [&](std::pair<int, int> A, std::pair<int, int> B) {
2266 return SortBase(SVI1A, A, B);
2267 });
2268 // Calculate our ReconstructMasks from the OrigReconstructMasks and the
2269 // modified order of the input shuffles.
2270 SmallVector<SmallVector<int>> ReconstructMasks;
2271 for (const auto &Mask : OrigReconstructMasks) {
2272 SmallVector<int> ReconstructMask;
2273 for (int M : Mask) {
2274 auto FindIndex = [](const SmallVector<std::pair<int, int>> &V, int M) {
2275 auto It = find_if(V, [M](auto A) { return A.second == M; });
2276 assert(It != V.end() && "Expected all entries in Mask");
2277 return std::distance(V.begin(), It);
2278 };
2279 if (M < 0)
2280 ReconstructMask.push_back(-1);
2281 else if (M < static_cast<int>(NumElts)) {
2282 ReconstructMask.push_back(FindIndex(V1, M));
2283 } else {
2284 ReconstructMask.push_back(NumElts + FindIndex(V2, M));
2285 }
2286 }
2287 ReconstructMasks.push_back(std::move(ReconstructMask));
2288 }
2289
2290 // Calculate the masks needed for the new input shuffles, which get padded
2291 // with undef
2292 SmallVector<int> V1A, V1B, V2A, V2B;
2293 for (unsigned I = 0; I < V1.size(); I++) {
2294 V1A.push_back(GetBaseMaskValue(SVI0A, V1[I].first));
2295 V1B.push_back(GetBaseMaskValue(SVI0B, V1[I].first));
2296 }
2297 for (unsigned I = 0; I < V2.size(); I++) {
2298 V2A.push_back(GetBaseMaskValue(SVI1A, V2[I].first));
2299 V2B.push_back(GetBaseMaskValue(SVI1B, V2[I].first));
2300 }
2301 while (V1A.size() < NumElts) {
2304 }
2305 while (V2A.size() < NumElts) {
2308 }
2309
2310 auto AddShuffleCost = [&](InstructionCost C, Instruction *I) {
2311 auto *SV = dyn_cast<ShuffleVectorInst>(I);
2312 if (!SV)
2313 return C;
2314 return C + TTI.getShuffleCost(isa<UndefValue>(SV->getOperand(1))
2317 VT, SV->getShuffleMask());
2318 };
2319 auto AddShuffleMaskCost = [&](InstructionCost C, ArrayRef<int> Mask) {
2320 return C + TTI.getShuffleCost(TTI::SK_PermuteTwoSrc, VT, Mask);
2321 };
2322
2323 // Get the costs of the shuffles + binops before and after with the new
2324 // shuffle masks.
2325 InstructionCost CostBefore =
2326 TTI.getArithmeticInstrCost(Op0->getOpcode(), VT) +
2327 TTI.getArithmeticInstrCost(Op1->getOpcode(), VT);
2328 CostBefore += std::accumulate(Shuffles.begin(), Shuffles.end(),
2329 InstructionCost(0), AddShuffleCost);
2330 CostBefore += std::accumulate(InputShuffles.begin(), InputShuffles.end(),
2331 InstructionCost(0), AddShuffleCost);
2332
2333 // The new binops will be unused for lanes past the used shuffle lengths.
2334 // These types attempt to get the correct cost for that from the target.
2335 FixedVectorType *Op0SmallVT =
2336 FixedVectorType::get(VT->getScalarType(), V1.size());
2337 FixedVectorType *Op1SmallVT =
2338 FixedVectorType::get(VT->getScalarType(), V2.size());
2339 InstructionCost CostAfter =
2340 TTI.getArithmeticInstrCost(Op0->getOpcode(), Op0SmallVT) +
2341 TTI.getArithmeticInstrCost(Op1->getOpcode(), Op1SmallVT);
2342 CostAfter += std::accumulate(ReconstructMasks.begin(), ReconstructMasks.end(),
2343 InstructionCost(0), AddShuffleMaskCost);
2344 std::set<SmallVector<int>> OutputShuffleMasks({V1A, V1B, V2A, V2B});
2345 CostAfter +=
2346 std::accumulate(OutputShuffleMasks.begin(), OutputShuffleMasks.end(),
2347 InstructionCost(0), AddShuffleMaskCost);
2348
2349 LLVM_DEBUG(dbgs() << "Found a binop select shuffle pattern: " << I << "\n");
2350 LLVM_DEBUG(dbgs() << " CostBefore: " << CostBefore
2351 << " vs CostAfter: " << CostAfter << "\n");
2352 if (CostBefore <= CostAfter)
2353 return false;
2354
2355 // The cost model has passed, create the new instructions.
2356 auto GetShuffleOperand = [&](Instruction *I, unsigned Op) -> Value * {
2357 auto *SV = dyn_cast<ShuffleVectorInst>(I);
2358 if (!SV)
2359 return I;
2360 if (isa<UndefValue>(SV->getOperand(1)))
2361 if (auto *SSV = dyn_cast<ShuffleVectorInst>(SV->getOperand(0)))
2362 if (InputShuffles.contains(SSV))
2363 return SSV->getOperand(Op);
2364 return SV->getOperand(Op);
2365 };
2366 Builder.SetInsertPoint(*SVI0A->getInsertionPointAfterDef());
2367 Value *NSV0A = Builder.CreateShuffleVector(GetShuffleOperand(SVI0A, 0),
2368 GetShuffleOperand(SVI0A, 1), V1A);
2369 Builder.SetInsertPoint(*SVI0B->getInsertionPointAfterDef());
2370 Value *NSV0B = Builder.CreateShuffleVector(GetShuffleOperand(SVI0B, 0),
2371 GetShuffleOperand(SVI0B, 1), V1B);
2372 Builder.SetInsertPoint(*SVI1A->getInsertionPointAfterDef());
2373 Value *NSV1A = Builder.CreateShuffleVector(GetShuffleOperand(SVI1A, 0),
2374 GetShuffleOperand(SVI1A, 1), V2A);
2375 Builder.SetInsertPoint(*SVI1B->getInsertionPointAfterDef());
2376 Value *NSV1B = Builder.CreateShuffleVector(GetShuffleOperand(SVI1B, 0),
2377 GetShuffleOperand(SVI1B, 1), V2B);
2378 Builder.SetInsertPoint(Op0);
2379 Value *NOp0 = Builder.CreateBinOp((Instruction::BinaryOps)Op0->getOpcode(),
2380 NSV0A, NSV0B);
2381 if (auto *I = dyn_cast<Instruction>(NOp0))
2382 I->copyIRFlags(Op0, true);
2383 Builder.SetInsertPoint(Op1);
2384 Value *NOp1 = Builder.CreateBinOp((Instruction::BinaryOps)Op1->getOpcode(),
2385 NSV1A, NSV1B);
2386 if (auto *I = dyn_cast<Instruction>(NOp1))
2387 I->copyIRFlags(Op1, true);
2388
2389 for (int S = 0, E = ReconstructMasks.size(); S != E; S++) {
2390 Builder.SetInsertPoint(Shuffles[S]);
2391 Value *NSV = Builder.CreateShuffleVector(NOp0, NOp1, ReconstructMasks[S]);
2392 replaceValue(*Shuffles[S], *NSV);
2393 }
2394
2395 Worklist.pushValue(NSV0A);
2396 Worklist.pushValue(NSV0B);
2397 Worklist.pushValue(NSV1A);
2398 Worklist.pushValue(NSV1B);
2399 for (auto *S : Shuffles)
2400 Worklist.add(S);
2401 return true;
2402}
2403
2404/// This is the entry point for all transforms. Pass manager differences are
2405/// handled in the callers of this function.
2406bool VectorCombine::run() {
2408 return false;
2409
2410 // Don't attempt vectorization if the target does not support vectors.
2411 if (!TTI.getNumberOfRegisters(TTI.getRegisterClassForType(/*Vector*/ true)))
2412 return false;
2413
2414 bool MadeChange = false;
2415 auto FoldInst = [this, &MadeChange](Instruction &I) {
2416 Builder.SetInsertPoint(&I);
2417 bool IsFixedVectorType = isa<FixedVectorType>(I.getType());
2418 auto Opcode = I.getOpcode();
2419
2420 // These folds should be beneficial regardless of when this pass is run
2421 // in the optimization pipeline.
2422 // The type checking is for run-time efficiency. We can avoid wasting time
2423 // dispatching to folding functions if there's no chance of matching.
2424 if (IsFixedVectorType) {
2425 switch (Opcode) {
2426 case Instruction::InsertElement:
2427 MadeChange |= vectorizeLoadInsert(I);
2428 break;
2429 case Instruction::ShuffleVector:
2430 MadeChange |= widenSubvectorLoad(I);
2431 break;
2432 default:
2433 break;
2434 }
2435 }
2436
2437 // This transform works with scalable and fixed vectors
2438 // TODO: Identify and allow other scalable transforms
2439 if (isa<VectorType>(I.getType())) {
2440 MadeChange |= scalarizeBinopOrCmp(I);
2441 MadeChange |= scalarizeLoadExtract(I);
2442 MadeChange |= scalarizeVPIntrinsic(I);
2443 }
2444
2445 if (Opcode == Instruction::Store)
2446 MadeChange |= foldSingleElementStore(I);
2447
2448 // If this is an early pipeline invocation of this pass, we are done.
2449 if (TryEarlyFoldsOnly)
2450 return;
2451
2452 // Otherwise, try folds that improve codegen but may interfere with
2453 // early IR canonicalizations.
2454 // The type checking is for run-time efficiency. We can avoid wasting time
2455 // dispatching to folding functions if there's no chance of matching.
2456 if (IsFixedVectorType) {
2457 switch (Opcode) {
2458 case Instruction::InsertElement:
2459 MadeChange |= foldInsExtFNeg(I);
2460 break;
2461 case Instruction::ShuffleVector:
2462 MadeChange |= foldShuffleOfBinops(I);
2463 MadeChange |= foldShuffleOfCastops(I);
2464 MadeChange |= foldShuffleOfShuffles(I);
2465 MadeChange |= foldSelectShuffle(I);
2466 MadeChange |= foldShuffleToIdentity(I);
2467 break;
2468 case Instruction::BitCast:
2469 MadeChange |= foldBitcastShuffle(I);
2470 break;
2471 }
2472 } else {
2473 switch (Opcode) {
2474 case Instruction::Call:
2475 MadeChange |= foldShuffleFromReductions(I);
2476 MadeChange |= foldTruncFromReductions(I);
2477 break;
2478 case Instruction::ICmp:
2479 case Instruction::FCmp:
2480 MadeChange |= foldExtractExtract(I);
2481 break;
2482 default:
2483 if (Instruction::isBinaryOp(Opcode)) {
2484 MadeChange |= foldExtractExtract(I);
2485 MadeChange |= foldExtractedCmps(I);
2486 }
2487 break;
2488 }
2489 }
2490 };
2491
2492 for (BasicBlock &BB : F) {
2493 // Ignore unreachable basic blocks.
2494 if (!DT.isReachableFromEntry(&BB))
2495 continue;
2496 // Use early increment range so that we can erase instructions in loop.
2497 for (Instruction &I : make_early_inc_range(BB)) {
2498 if (I.isDebugOrPseudoInst())
2499 continue;
2500 FoldInst(I);
2501 }
2502 }
2503
2504 while (!Worklist.isEmpty()) {
2505 Instruction *I = Worklist.removeOne();
2506 if (!I)
2507 continue;
2508
2511 continue;
2512 }
2513
2514 FoldInst(*I);
2515 }
2516
2517 return MadeChange;
2518}
2519
2522 auto &AC = FAM.getResult<AssumptionAnalysis>(F);
2526 const DataLayout *DL = &F.getParent()->getDataLayout();
2527 VectorCombine Combiner(F, TTI, DT, AA, AC, DL, TryEarlyFoldsOnly);
2528 if (!Combiner.run())
2529 return PreservedAnalyses::all();
2532 return PA;
2533}
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
This is the interface for LLVM's primary stateless and local alias analysis.
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static cl::opt< TargetTransformInfo::TargetCostKind > CostKind("cost-kind", cl::desc("Target cost kind"), cl::init(TargetTransformInfo::TCK_RecipThroughput), cl::values(clEnumValN(TargetTransformInfo::TCK_RecipThroughput, "throughput", "Reciprocal throughput"), clEnumValN(TargetTransformInfo::TCK_Latency, "latency", "Instruction latency"), clEnumValN(TargetTransformInfo::TCK_CodeSize, "code-size", "Code size"), clEnumValN(TargetTransformInfo::TCK_SizeAndLatency, "size-latency", "Code size and latency")))
Returns the sub type a function will return at a given Idx Should correspond to the result type of an ExtractValue instruction executed with just that one unsigned Idx
#define LLVM_DEBUG(X)
Definition: Debug.h:101
This file defines the DenseMap class.
std::optional< std::vector< StOtherPiece > > Other
Definition: ELFYAML.cpp:1293
bool End
Definition: ELF_riscv.cpp:480
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
This is the interface for a simple mod/ref and alias analysis over globals.
Hexagon Common GEP
static void eraseInstruction(Instruction &I, ICFLoopSafetyInfo &SafetyInfo, MemorySSAUpdater &MSSAU)
Definition: LICM.cpp:1500
#define F(x, y, z)
Definition: MD5.cpp:55
#define I(x, y, z)
Definition: MD5.cpp:58
uint64_t IntrinsicInst * II
static GCMetadataPrinterRegistry::Add< OcamlGCMetadataPrinter > Y("ocaml", "ocaml 3.10-compatible collector")
if(VerifyEach)
FunctionAnalysisManager FAM
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
unsigned OpIndex
This file contains some templates that are useful if you are working with the STL at all.
This file defines the make_scope_exit function, which executes user-defined cleanup logic at scope ex...
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
Definition: Statistic.h:167
static SymbolRef::Type getType(const Symbol *Sym)
Definition: TapiFile.cpp:40
This pass exposes codegen information to IR-level passes.
static std::optional< unsigned > getOpcode(ArrayRef< VPValue * > Values)
Returns the opcode of Values or ~0 if they do not all agree.
Definition: VPlanSLP.cpp:191
static Value * generateNewInstTree(ArrayRef< InstLane > Item, FixedVectorType *Ty, const SmallPtrSet< Use *, 4 > &IdentityLeafs, const SmallPtrSet< Use *, 4 > &SplatLeafs, IRBuilder<> &Builder)
static SmallVector< InstLane > generateInstLaneVectorFromOperand(ArrayRef< InstLane > Item, int Op)
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.
static Value * peekThroughBitcasts(Value *V)
Return the source operand of a potentially bitcasted value.
static Align computeAlignmentAfterScalarization(Align VectorAlignment, Type *ScalarType, Value *Idx, const DataLayout &DL)
The memory operation on a vector of ScalarType had alignment of VectorAlignment.
static ScalarizationResult canScalarizeAccess(VectorType *VecTy, Value *Idx, Instruction *CtxI, AssumptionCache &AC, const DominatorTree &DT)
Check if it is legal to scalarize a memory access to VecTy at index Idx.
static cl::opt< bool > DisableVectorCombine("disable-vector-combine", cl::init(false), cl::Hidden, cl::desc("Disable all vector combine transforms"))
static InstLane lookThroughShuffles(Use *U, int Lane)
static bool canWidenLoad(LoadInst *Load, const TargetTransformInfo &TTI)
static const unsigned InvalidIndex
std::pair< Use *, int > InstLane
static cl::opt< unsigned > MaxInstrsToScan("vector-combine-max-scan-instrs", cl::init(30), cl::Hidden, cl::desc("Max number of instructions to scan for vector combining."))
static cl::opt< bool > DisableBinopExtractShuffle("disable-binop-extract-shuffle", cl::init(false), cl::Hidden, cl::desc("Disable binop extract to shuffle transforms"))
static bool isMemModifiedBetween(BasicBlock::iterator Begin, BasicBlock::iterator End, const MemoryLocation &Loc, AAResults &AA)
static ExtractElementInst * translateExtract(ExtractElementInst *ExtElt, unsigned NewIndex, IRBuilder<> &Builder)
Given an extract element instruction with constant index operand, shuffle the source vector (shift th...
A manager for alias analyses.
ModRefInfo getModRefInfo(const Instruction *I, const std::optional< MemoryLocation > &OptLoc)
Check whether or not an instruction may read or write the optionally specified memory location.
Class for arbitrary precision integers.
Definition: APInt.h:77
static APInt getOneBitSet(unsigned numBits, unsigned BitNo)
Return an APInt with exactly one bit set in the result.
Definition: APInt.h:218
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:321
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:473
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: ArrayRef.h:41
const T & front() const
front - Get the first element.
Definition: ArrayRef.h:168
iterator end() const
Definition: ArrayRef.h:154
iterator begin() const
Definition: ArrayRef.h:153
A function analysis which provides an AssumptionCache.
A cache of @llvm.assume calls within a function.
bool hasFnAttr(Attribute::AttrKind Kind) const
Return true if the attribute exists for the function.
LLVM Basic Block Representation.
Definition: BasicBlock.h:60
InstListType::iterator iterator
Instruction iterators...
Definition: BasicBlock.h:166
BinaryOps getOpcode() const
Definition: InstrTypes.h:513
Represents analyses that only rely on functions' control flow.
Definition: Analysis.h:70
Value * getArgOperand(unsigned i) const
Definition: InstrTypes.h:1695
iterator_range< User::op_iterator > args()
Iteration adapter for range-for loops.
Definition: InstrTypes.h:1686
static Type * makeCmpResultType(Type *opnd_type)
Create a result type for fcmp/icmp.
Definition: InstrTypes.h:1362
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:993
bool isFPPredicate() const
Definition: InstrTypes.h:1122
Combiner implementation.
Definition: Combiner.h:34
static Constant * getExtractElement(Constant *Vec, Constant *Idx, Type *OnlyIfReducedTy=nullptr)
Definition: Constants.cpp:2484
This is the shared class of boolean and integer constants.
Definition: Constants.h:81
const APInt & getValue() const
Return the constant as an APInt value reference.
Definition: Constants.h:146
This class represents a range of values.
Definition: ConstantRange.h:47
ConstantRange urem(const ConstantRange &Other) const
Return a new range representing the possible values resulting from an unsigned remainder operation of...
ConstantRange binaryAnd(const ConstantRange &Other) const
Return a new range representing the possible values resulting from a binary-and of a value in this ra...
bool contains(const APInt &Val) const
Return true if the specified value is in the set.
static Constant * get(ArrayRef< Constant * > V)
Definition: Constants.cpp:1399
This is an important base class in LLVM.
Definition: Constant.h:41
This class represents an Operation in the Expression.
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:110
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:155
std::pair< iterator, bool > try_emplace(KeyT &&Key, Ts &&... Args)
Definition: DenseMap.h:235
iterator end()
Definition: DenseMap.h:84
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:279
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:162
bool isReachableFromEntry(const Use &U) const
Provide an overload for a Use.
Definition: Dominators.cpp:321
This instruction extracts a single (scalar) element from a VectorType value.
Class to represent fixed width SIMD vectors.
Definition: DerivedTypes.h:539
unsigned getNumElements() const
Definition: DerivedTypes.h:582
static FixedVectorType * get(Type *ElementType, unsigned NumElts)
Definition: Type.cpp:692
Value * CreateInsertElement(Type *VecTy, Value *NewElt, Value *Idx, const Twine &Name="")
Definition: IRBuilder.h:2472
Value * CreateExtractElement(Value *Vec, Value *Idx, const Twine &Name="")
Definition: IRBuilder.h:2460
LoadInst * CreateAlignedLoad(Type *Ty, Value *Ptr, MaybeAlign Align, const char *Name)
Definition: IRBuilder.h:1807
Value * CreateVectorSplat(unsigned NumElts, Value *V, const Twine &Name="")
Return a vector value that contains.
Definition: IRBuilder.cpp:1192
CallInst * CreateIntrinsic(Intrinsic::ID ID, ArrayRef< Type * > Types, ArrayRef< Value * > Args, Instruction *FMFSource=nullptr, const Twine &Name="")
Create a call to intrinsic ID with Args, mangled using Types.
Definition: IRBuilder.cpp:932
Value * CreateFNegFMF(Value *V, Instruction *FMFSource, const Twine &Name="")
Copy fast-math-flags from an instruction rather than using the builder's default FMF.
Definition: IRBuilder.h:1740
Value * CreateSelect(Value *C, Value *True, Value *False, const Twine &Name="", Instruction *MDFrom=nullptr)
Definition: IRBuilder.cpp:1090
Value * CreateFreeze(Value *V, const Twine &Name="")
Definition: IRBuilder.h:2535
void SetInsertPointPastAllocas(Function *F)
This specifies that created instructions should inserted at the beginning end of the specified functi...
Definition: IRBuilder.h:214
Value * CreateInBoundsGEP(Type *Ty, Value *Ptr, ArrayRef< Value * > IdxList, const Twine &Name="")
Definition: IRBuilder.h:1874
Value * CreatePointerBitCastOrAddrSpaceCast(Value *V, Type *DestTy, const Twine &Name="")
Definition: IRBuilder.h:2182
ConstantInt * getInt64(uint64_t C)
Get a constant 64-bit value.
Definition: IRBuilder.h:491
Value * CreateUnOp(Instruction::UnaryOps Opc, Value *V, const Twine &Name="", MDNode *FPMathTag=nullptr)
Definition: IRBuilder.h:1753
ConstantInt * getInt32(uint32_t C)
Get a constant 32-bit value.
Definition: IRBuilder.h:486
Value * CreateCmp(CmpInst::Predicate Pred, Value *LHS, Value *RHS, const Twine &Name="", MDNode *FPMathTag=nullptr)
Definition: IRBuilder.h:2366
Value * CreateBitCast(Value *V, Type *DestTy, const Twine &Name="")
Definition: IRBuilder.h:2127
LoadInst * CreateLoad(Type *Ty, Value *Ptr, const char *Name)
Provided to resolve 'CreateLoad(Ty, Ptr, "...")' correctly, instead of converting the string to 'bool...
Definition: IRBuilder.h:1790
Value * CreateShuffleVector(Value *V1, Value *V2, Value *Mask, const Twine &Name="")
Definition: IRBuilder.h:2494
StoreInst * CreateStore(Value *Val, Value *Ptr, bool isVolatile=false)
Definition: IRBuilder.h:1803
Value * CreateTrunc(Value *V, Type *DestTy, const Twine &Name="", bool IsNUW=false, bool IsNSW=false)
Definition: IRBuilder.h:2007
PointerType * getPtrTy(unsigned AddrSpace=0)
Fetch the type representing a pointer.
Definition: IRBuilder.h:569
Value * CreateBinOp(Instruction::BinaryOps Opc, Value *LHS, Value *RHS, const Twine &Name="", MDNode *FPMathTag=nullptr)
Definition: IRBuilder.h:1666
Value * CreateCast(Instruction::CastOps Op, Value *V, Type *DestTy, const Twine &Name="")
Definition: IRBuilder.h:2161
void SetInsertPoint(BasicBlock *TheBB)
This specifies that created instructions should be appended to the end of the specified block.
Definition: IRBuilder.h:180
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Definition: IRBuilder.h:2666
InstructionWorklist - This is the worklist management logic for InstCombine and other simplification ...
void pushUsersToWorkList(Instruction &I)
When an instruction is simplified, add all users of the instruction to the work lists because they mi...
void push(Instruction *I)
Push the instruction onto the worklist stack.
void remove(Instruction *I)
Remove I from the worklist if it exists.
bool isBinaryOp() const
Definition: Instruction.h:256
bool comesBefore(const Instruction *Other) const
Given an instruction Other in the same basic block as this instruction, return true if this instructi...
bool mayReadFromMemory() const LLVM_READONLY
Return true if this instruction may read memory.
void copyMetadata(const Instruction &SrcInst, ArrayRef< unsigned > WL=ArrayRef< unsigned >())
Copy metadata from SrcInst to this instruction.
bool isIntDivRem() const
Definition: Instruction.h:257
Intrinsic::ID getIntrinsicID() const
Return the intrinsic ID of this intrinsic.
Definition: IntrinsicInst.h:55
An instruction for reading from memory.
Definition: Instructions.h:185
Representation for a specific memory location.
static MemoryLocation get(const LoadInst *LI)
Return a location with information about the memory reference by the given instruction.
static PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
Definition: Constants.cpp:1814
A set of analyses that are preserved following a run of a transformation pass.
Definition: Analysis.h:109
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: Analysis.h:115
void preserveSet()
Mark an analysis set as preserved.
Definition: Analysis.h:144
This instruction constructs a fixed permutation of two input vectors.
int getMaskValue(unsigned Elt) const
Return the shuffle mask value of this instruction for the given element index.
VectorType * getType() const
Overload to return most specific vector type.
static void getShuffleMask(const Constant *Mask, SmallVectorImpl< int > &Result)
Convert the input shuffle mask operand to a vector of integers.
static bool isIdentityMask(ArrayRef< int > Mask, int NumSrcElts)
Return true if this shuffle mask chooses elements from exactly one source vector without lane crossin...
static void commuteShuffleMask(MutableArrayRef< int > Mask, unsigned InVecNumElts)
Change values in a shuffle permute mask assuming the two vector operands of length InVecNumElts have ...
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:342
bool contains(ConstPtrType Ptr) const
Definition: SmallPtrSet.h:366
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:427
bool empty() const
Definition: SmallVector.h:94
size_t size() const
Definition: SmallVector.h:91
reference emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:950
void push_back(const T &Elt)
Definition: SmallVector.h:426
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1209
An instruction for storing to memory.
Definition: Instructions.h:318
void setAlignment(Align Align)
Definition: Instructions.h:374
Analysis pass providing the TargetTransformInfo.
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
InstructionCost getAddressComputationCost(Type *Ty, ScalarEvolution *SE=nullptr, const SCEV *Ptr=nullptr) const
InstructionCost getMemoryOpCost(unsigned Opcode, Type *Src, Align Alignment, unsigned AddressSpace, TTI::TargetCostKind CostKind=TTI::TCK_RecipThroughput, OperandValueInfo OpdInfo={OK_AnyValue, OP_None}, const Instruction *I=nullptr) const
InstructionCost getIntrinsicInstrCost(const IntrinsicCostAttributes &ICA, TTI::TargetCostKind CostKind) const
InstructionCost getArithmeticReductionCost(unsigned Opcode, VectorType *Ty, std::optional< FastMathFlags > FMF, TTI::TargetCostKind CostKind=TTI::TCK_RecipThroughput) const
Calculate the cost of vector reduction intrinsics.
InstructionCost getCastInstrCost(unsigned Opcode, Type *Dst, Type *Src, TTI::CastContextHint CCH, TTI::TargetCostKind CostKind=TTI::TCK_SizeAndLatency, const Instruction *I=nullptr) const
InstructionCost getArithmeticInstrCost(unsigned Opcode, Type *Ty, TTI::TargetCostKind CostKind=TTI::TCK_RecipThroughput, TTI::OperandValueInfo Opd1Info={TTI::OK_AnyValue, TTI::OP_None}, TTI::OperandValueInfo Opd2Info={TTI::OK_AnyValue, TTI::OP_None}, ArrayRef< const Value * > Args=std::nullopt, const Instruction *CxtI=nullptr, const TargetLibraryInfo *TLibInfo=nullptr) const
This is an approximation of reciprocal throughput of a math/logic op.
unsigned getRegisterClassForType(bool Vector, Type *Ty=nullptr) const
TargetCostKind
The kind of cost model.
@ TCK_RecipThroughput
Reciprocal throughput.
unsigned getMinVectorRegisterBitWidth() const
unsigned getNumberOfRegisters(unsigned ClassID) const
InstructionCost getShuffleCost(ShuffleKind Kind, VectorType *Tp, ArrayRef< int > Mask=std::nullopt, TTI::TargetCostKind CostKind=TTI::TCK_RecipThroughput, int Index=0, VectorType *SubTp=nullptr, ArrayRef< const Value * > Args=std::nullopt, const Instruction *CxtI=nullptr) const
InstructionCost getScalarizationOverhead(VectorType *Ty, const APInt &DemandedElts, bool Insert, bool Extract, TTI::TargetCostKind CostKind) const
Estimate the overhead of scalarizing an instruction.
InstructionCost getVectorInstrCost(unsigned Opcode, Type *Val, TTI::TargetCostKind CostKind, unsigned Index=-1, Value *Op0=nullptr, Value *Op1=nullptr) const
ShuffleKind
The various kinds of shuffle patterns for vector queries.
@ SK_Select
Selects elements from the corresponding lane of either source operand.
@ SK_PermuteSingleSrc
Shuffle elements of single source vector with any shuffle mask.
@ SK_Broadcast
Broadcast element 0 to all other elements.
@ SK_PermuteTwoSrc
Merge elements from two source vectors into one with any shuffle mask.
@ None
The cast is not used with a load/store of any kind.
InstructionCost getCmpSelInstrCost(unsigned Opcode, Type *ValTy, Type *CondTy, CmpInst::Predicate VecPred, TTI::TargetCostKind CostKind=TTI::TCK_RecipThroughput, const Instruction *I=nullptr) const
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
bool isVectorTy() const
True if this is an instance of VectorType.
Definition: Type.h:265
bool isPointerTy() const
True if this is an instance of PointerType.
Definition: Type.h:255
bool isFloatingPointTy() const
Return true if this is one of the floating-point types.
Definition: Type.h:185
bool isIntegerTy() const
True if this is an instance of IntegerType.
Definition: Type.h:228
TypeSize getPrimitiveSizeInBits() const LLVM_READONLY
Return the basic size of this type if it is a primitive type.
Type * getScalarType() const
If this is a vector type, return the element type, otherwise return 'this'.
Definition: Type.h:348
'undef' values are things that do not have specified contents.
Definition: Constants.h:1395
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43
op_range operands()
Definition: User.h:242
Value * getOperand(unsigned i) const
Definition: User.h:169
static bool isVPBinOp(Intrinsic::ID ID)
This is the common base class for vector predication intrinsics.
std::optional< unsigned > getFunctionalIntrinsicID() const
std::optional< unsigned > getFunctionalOpcode() const
LLVM Value Representation.
Definition: Value.h:74
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:255
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:736
bool hasOneUse() const
Return true if there is exactly one use of this value.
Definition: Value.h:434
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:534
iterator_range< user_iterator > users()
Definition: Value.h:421
Align getPointerAlignment(const DataLayout &DL) const
Returns an alignment of the pointer value.
Definition: Value.cpp:926
unsigned getValueID() const
Return an ID for the concrete type of this object.
Definition: Value.h:532
bool hasNUses(unsigned N) const
Return true if this Value has exactly N uses.
Definition: Value.cpp:149
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:309
PreservedAnalyses run(Function &F, FunctionAnalysisManager &)
constexpr char Args[]
Key for Kernel::Metadata::mArgs.
constexpr char Attrs[]
Key for Kernel::Metadata::mAttrs.
constexpr 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:121
@ C
The default llvm calling convention, compatible with C.
Definition: CallingConv.h:34
AttributeList getAttributes(LLVMContext &C, ID id)
Return the attributes for an intrinsic.
BinaryOp_match< LHS, RHS, Instruction::And > m_And(const LHS &L, const RHS &R)
class_match< BinaryOperator > m_BinOp()
Match an arbitrary binary operation and ignore it.
Definition: PatternMatch.h:100
BinaryOp_match< LHS, RHS, Instruction::URem > m_URem(const LHS &L, const RHS &R)
class_match< Constant > m_Constant()
Match an arbitrary Constant and ignore it.
Definition: PatternMatch.h:165
CastInst_match< OpTy, TruncInst > m_Trunc(const OpTy &Op)
Matches Trunc.
specific_intval< false > m_SpecificInt(const APInt &V)
Match a specific integer value or vector with all elements equal to the value.
Definition: PatternMatch.h:972
bool match(Val *V, const Pattern &P)
Definition: PatternMatch.h:49
bind_ty< Instruction > m_Instruction(Instruction *&I)
Match an instruction, capturing it if we match.
Definition: PatternMatch.h:816
specificval_ty m_Specific(const Value *V)
Match if we have a specific specified value.
Definition: PatternMatch.h:875
TwoOps_match< Val_t, Idx_t, Instruction::ExtractElement > m_ExtractElt(const Val_t &Val, const Idx_t &Idx)
Matches ExtractElementInst.
class_match< ConstantInt > m_ConstantInt()
Match an arbitrary ConstantInt and ignore it.
Definition: PatternMatch.h:168
ThreeOps_match< Cond, LHS, RHS, Instruction::Select > m_Select(const Cond &C, const LHS &L, const RHS &R)
Matches SelectInst.
match_combine_and< LTy, RTy > m_CombineAnd(const LTy &L, const RTy &R)
Combine two pattern matchers matching L && R.
Definition: PatternMatch.h:245
cst_pred_ty< is_zero_int > m_ZeroInt()
Match an integer 0 or a vector with all elements equal to 0.
Definition: PatternMatch.h:599
OneUse_match< T > m_OneUse(const T &SubPattern)
Definition: PatternMatch.h:67
TwoOps_match< V1_t, V2_t, Instruction::ShuffleVector > m_Shuffle(const V1_t &v1, const V2_t &v2)
Matches ShuffleVectorInst independently of mask value.
OneOps_match< OpTy, Instruction::Load > m_Load(const OpTy &Op)
Matches LoadInst.
class_match< UndefValue > m_UndefValue()
Match an arbitrary UndefValue constant.
Definition: PatternMatch.h:155
class_match< CmpInst > m_Cmp()
Matches any compare instruction and ignore it.
Definition: PatternMatch.h:105
CastOperator_match< OpTy, Instruction::BitCast > m_BitCast(const OpTy &Op)
Matches BitCast.
match_combine_or< CastInst_match< OpTy, SExtInst >, NNegZExt_match< OpTy > > m_SExtLike(const OpTy &Op)
Match either "sext" or "zext nneg".
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
Definition: PatternMatch.h:92
FNeg_match< OpTy > m_FNeg(const OpTy &X)
Match 'fneg X' as 'fsub -0.0, X'.
auto m_Undef()
Match an arbitrary undef constant.
Definition: PatternMatch.h:152
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.
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:450
PointerTypeMap run(const Module &M)
Compute the PointerTypeMap for the module M.
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
auto drop_begin(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the first N elements excluded.
Definition: STLExtras.h:329
@ Offset
Definition: DWP.cpp:456
void stable_sort(R &&Range)
Definition: STLExtras.h:1995
UnaryFunction for_each(R &&Range, UnaryFunction F)
Provide wrappers to std::for_each which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1715
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1722
detail::scope_exit< std::decay_t< Callable > > make_scope_exit(Callable &&F)
Definition: ScopeExit.h:59
auto enumerate(FirstRange &&First, RestRanges &&...Rest)
Given two or more input ranges, returns a new range whose values are are tuples (A,...
Definition: STLExtras.h:2400
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
unsigned getArithmeticReductionInstruction(Intrinsic::ID RdxID)
Returns the arithmetic instruction opcode used when expanding a reduction.
Definition: LoopUtils.cpp:921
iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)
Make a range that does early increment to allow mutation of the underlying range without disrupting i...
Definition: STLExtras.h:656
bool mustSuppressSpeculation(const LoadInst &LI)
Return true if speculation of the given load must be suppressed to avoid ordering or interfering with...
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...
Value * getSplatValue(const Value *V)
Get splat value if the input is a splat vector or return nullptr.
ConstantRange computeConstantRange(const Value *V, bool ForSigned, bool UseInstrInfo=true, AssumptionCache *AC=nullptr, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, unsigned Depth=0)
Determine the possible constant range of an integer or vector of integer value.
bool isSafeToSpeculativelyExecuteWithOpcode(unsigned Opcode, const Instruction *Inst, const Instruction *CtxI=nullptr, AssumptionCache *AC=nullptr, const DominatorTree *DT=nullptr, const TargetLibraryInfo *TLI=nullptr)
This returns the same result as isSafeToSpeculativelyExecute if Opcode is the actual opcode of Inst.
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1729
bool isInstructionTriviallyDead(Instruction *I, const TargetLibraryInfo *TLI=nullptr)
Return true if the result produced by the instruction is not used, and the instruction will return.
Definition: Local.cpp:400
bool isSplatValue(const Value *V, int Index=-1, unsigned Depth=0)
Return true if each element of the vector value V is poisoned or equal to every other non-poisoned el...
bool isModSet(const ModRefInfo MRI)
Definition: ModRef.h:48
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1647
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
bool none_of(R &&Range, UnaryPredicate P)
Provide wrappers to std::none_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1736
void propagateIRFlags(Value *I, ArrayRef< Value * > VL, Value *OpValue=nullptr, bool IncludeWrapFlags=true)
Get the intersection (logical and) of all of the potential IR flags of each scalar operation (VL) tha...
Definition: LoopUtils.cpp:1223
bool isKnownNonZero(const Value *V, const SimplifyQuery &Q, unsigned Depth=0)
Return true if the given value is known to be non-zero when defined.
constexpr int PoisonMaskElem
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...
DWARFExpression::Operation Op
bool isSafeToSpeculativelyExecute(const Instruction *I, const Instruction *CtxI=nullptr, AssumptionCache *AC=nullptr, const DominatorTree *DT=nullptr, const TargetLibraryInfo *TLI=nullptr)
Return true if the instruction does not have any effects besides calculating the result and does not ...
auto find_if(R &&Range, UnaryPredicate P)
Provide wrappers to std::find_if which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1749
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
Definition: STLExtras.h:1879
Align commonAlignment(Align A, uint64_t Offset)
Returns the alignment that satisfies both alignments.
Definition: Alignment.h:212
bool isSafeToLoadUnconditionally(Value *V, Align Alignment, APInt &Size, const DataLayout &DL, Instruction *ScanFrom=nullptr, AssumptionCache *AC=nullptr, const DominatorTree *DT=nullptr, const TargetLibraryInfo *TLI=nullptr)
Return true if we know that executing a load from this value cannot trap.
Definition: Loads.cpp:352
bool isVectorIntrinsicWithScalarOpAtArg(Intrinsic::ID ID, unsigned ScalarOpdIdx)
Identifies if the vector form of the intrinsic has a scalar operand.
bool isGuaranteedNotToBePoison(const Value *V, AssumptionCache *AC=nullptr, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, unsigned Depth=0)
Returns true if V cannot be poison, but may be undef.
bool isTriviallyVectorizable(Intrinsic::ID ID)
Identify if the intrinsic is trivially vectorizable.
Definition: VectorUtils.cpp:46
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:860
This struct is a compact representation of a valid (non-zero power of two) alignment.
Definition: Alignment.h:39