LLVM 20.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, TTI::TargetCostKind CostKind,
71 bool TryEarlyFoldsOnly)
72 : F(F), Builder(F.getContext()), TTI(TTI), DT(DT), AA(AA), AC(AC), DL(DL),
73 CostKind(CostKind), TryEarlyFoldsOnly(TryEarlyFoldsOnly) {}
74
75 bool run();
76
77private:
78 Function &F;
79 IRBuilder<> Builder;
81 const DominatorTree &DT;
82 AAResults &AA;
84 const DataLayout *DL;
85 TTI::TargetCostKind CostKind;
86
87 /// If true, only perform beneficial early IR transforms. Do not introduce new
88 /// vector operations.
89 bool TryEarlyFoldsOnly;
90
91 InstructionWorklist Worklist;
92
93 // TODO: Direct calls from the top-level "run" loop use a plain "Instruction"
94 // parameter. That should be updated to specific sub-classes because the
95 // run loop was changed to dispatch on opcode.
96 bool vectorizeLoadInsert(Instruction &I);
97 bool widenSubvectorLoad(Instruction &I);
98 ExtractElementInst *getShuffleExtract(ExtractElementInst *Ext0,
100 unsigned PreferredExtractIndex) const;
101 bool isExtractExtractCheap(ExtractElementInst *Ext0, ExtractElementInst *Ext1,
102 const Instruction &I,
103 ExtractElementInst *&ConvertToShuffle,
104 unsigned PreferredExtractIndex);
105 void foldExtExtCmp(ExtractElementInst *Ext0, ExtractElementInst *Ext1,
106 Instruction &I);
107 void foldExtExtBinop(ExtractElementInst *Ext0, ExtractElementInst *Ext1,
108 Instruction &I);
109 bool foldExtractExtract(Instruction &I);
110 bool foldInsExtFNeg(Instruction &I);
111 bool foldInsExtVectorToShuffle(Instruction &I);
112 bool foldBitcastShuffle(Instruction &I);
113 bool scalarizeBinopOrCmp(Instruction &I);
114 bool scalarizeVPIntrinsic(Instruction &I);
115 bool foldExtractedCmps(Instruction &I);
116 bool foldSingleElementStore(Instruction &I);
117 bool scalarizeLoadExtract(Instruction &I);
118 bool foldConcatOfBoolMasks(Instruction &I);
119 bool foldPermuteOfBinops(Instruction &I);
120 bool foldShuffleOfBinops(Instruction &I);
121 bool foldShuffleOfCastops(Instruction &I);
122 bool foldShuffleOfShuffles(Instruction &I);
123 bool foldShuffleOfIntrinsics(Instruction &I);
124 bool foldShuffleToIdentity(Instruction &I);
125 bool foldShuffleFromReductions(Instruction &I);
126 bool foldCastFromReductions(Instruction &I);
127 bool foldSelectShuffle(Instruction &I, bool FromReduction = false);
128 bool shrinkType(Instruction &I);
129
130 void replaceValue(Value &Old, Value &New) {
131 LLVM_DEBUG(dbgs() << "VC: Replacing: " << Old << '\n');
132 LLVM_DEBUG(dbgs() << " With: " << New << '\n');
133 Old.replaceAllUsesWith(&New);
134 if (auto *NewI = dyn_cast<Instruction>(&New)) {
135 New.takeName(&Old);
136 Worklist.pushUsersToWorkList(*NewI);
137 Worklist.pushValue(NewI);
138 }
139 Worklist.pushValue(&Old);
140 }
141
143 LLVM_DEBUG(dbgs() << "VC: Erasing: " << I << '\n');
144 SmallVector<Value *> Ops(I.operands());
145 Worklist.remove(&I);
146 I.eraseFromParent();
147
148 // Push remaining users of the operands and then the operand itself - allows
149 // further folds that were hindered by OneUse limits.
150 for (Value *Op : Ops)
151 if (auto *OpI = dyn_cast<Instruction>(Op)) {
152 Worklist.pushUsersToWorkList(*OpI);
153 Worklist.pushValue(OpI);
154 }
155 }
156};
157} // namespace
158
159/// Return the source operand of a potentially bitcasted value. If there is no
160/// bitcast, return the input value itself.
162 while (auto *BitCast = dyn_cast<BitCastInst>(V))
163 V = BitCast->getOperand(0);
164 return V;
165}
166
167static bool canWidenLoad(LoadInst *Load, const TargetTransformInfo &TTI) {
168 // Do not widen load if atomic/volatile or under asan/hwasan/memtag/tsan.
169 // The widened load may load data from dirty regions or create data races
170 // non-existent in the source.
171 if (!Load || !Load->isSimple() || !Load->hasOneUse() ||
172 Load->getFunction()->hasFnAttribute(Attribute::SanitizeMemTag) ||
174 return false;
175
176 // We are potentially transforming byte-sized (8-bit) memory accesses, so make
177 // sure we have all of our type-based constraints in place for this target.
178 Type *ScalarTy = Load->getType()->getScalarType();
179 uint64_t ScalarSize = ScalarTy->getPrimitiveSizeInBits();
180 unsigned MinVectorSize = TTI.getMinVectorRegisterBitWidth();
181 if (!ScalarSize || !MinVectorSize || MinVectorSize % ScalarSize != 0 ||
182 ScalarSize % 8 != 0)
183 return false;
184
185 return true;
186}
187
188bool VectorCombine::vectorizeLoadInsert(Instruction &I) {
189 // Match insert into fixed vector of scalar value.
190 // TODO: Handle non-zero insert index.
191 Value *Scalar;
192 if (!match(&I,
194 return false;
195
196 // Optionally match an extract from another vector.
197 Value *X;
198 bool HasExtract = match(Scalar, m_ExtractElt(m_Value(X), m_ZeroInt()));
199 if (!HasExtract)
200 X = Scalar;
201
202 auto *Load = dyn_cast<LoadInst>(X);
203 if (!canWidenLoad(Load, TTI))
204 return false;
205
206 Type *ScalarTy = Scalar->getType();
207 uint64_t ScalarSize = ScalarTy->getPrimitiveSizeInBits();
208 unsigned MinVectorSize = TTI.getMinVectorRegisterBitWidth();
209
210 // Check safety of replacing the scalar load with a larger vector load.
211 // We use minimal alignment (maximum flexibility) because we only care about
212 // the dereferenceable region. When calculating cost and creating a new op,
213 // we may use a larger value based on alignment attributes.
214 Value *SrcPtr = Load->getPointerOperand()->stripPointerCasts();
215 assert(isa<PointerType>(SrcPtr->getType()) && "Expected a pointer type");
216
217 unsigned MinVecNumElts = MinVectorSize / ScalarSize;
218 auto *MinVecTy = VectorType::get(ScalarTy, MinVecNumElts, false);
219 unsigned OffsetEltIndex = 0;
220 Align Alignment = Load->getAlign();
221 if (!isSafeToLoadUnconditionally(SrcPtr, MinVecTy, Align(1), *DL, Load, &AC,
222 &DT)) {
223 // It is not safe to load directly from the pointer, but we can still peek
224 // through gep offsets and check if it safe to load from a base address with
225 // updated alignment. If it is, we can shuffle the element(s) into place
226 // after loading.
227 unsigned OffsetBitWidth = DL->getIndexTypeSizeInBits(SrcPtr->getType());
228 APInt Offset(OffsetBitWidth, 0);
230
231 // We want to shuffle the result down from a high element of a vector, so
232 // the offset must be positive.
233 if (Offset.isNegative())
234 return false;
235
236 // The offset must be a multiple of the scalar element to shuffle cleanly
237 // in the element's size.
238 uint64_t ScalarSizeInBytes = ScalarSize / 8;
239 if (Offset.urem(ScalarSizeInBytes) != 0)
240 return false;
241
242 // If we load MinVecNumElts, will our target element still be loaded?
243 OffsetEltIndex = Offset.udiv(ScalarSizeInBytes).getZExtValue();
244 if (OffsetEltIndex >= MinVecNumElts)
245 return false;
246
247 if (!isSafeToLoadUnconditionally(SrcPtr, MinVecTy, Align(1), *DL, Load, &AC,
248 &DT))
249 return false;
250
251 // Update alignment with offset value. Note that the offset could be negated
252 // to more accurately represent "(new) SrcPtr - Offset = (old) SrcPtr", but
253 // negation does not change the result of the alignment calculation.
254 Alignment = commonAlignment(Alignment, Offset.getZExtValue());
255 }
256
257 // Original pattern: insertelt undef, load [free casts of] PtrOp, 0
258 // Use the greater of the alignment on the load or its source pointer.
259 Alignment = std::max(SrcPtr->getPointerAlignment(*DL), Alignment);
260 Type *LoadTy = Load->getType();
261 unsigned AS = Load->getPointerAddressSpace();
262 InstructionCost OldCost =
263 TTI.getMemoryOpCost(Instruction::Load, LoadTy, Alignment, AS, CostKind);
264 APInt DemandedElts = APInt::getOneBitSet(MinVecNumElts, 0);
265 OldCost +=
266 TTI.getScalarizationOverhead(MinVecTy, DemandedElts,
267 /* Insert */ true, HasExtract, CostKind);
268
269 // New pattern: load VecPtr
270 InstructionCost NewCost =
271 TTI.getMemoryOpCost(Instruction::Load, MinVecTy, Alignment, AS, CostKind);
272 // Optionally, we are shuffling the loaded vector element(s) into place.
273 // For the mask set everything but element 0 to undef to prevent poison from
274 // propagating from the extra loaded memory. This will also optionally
275 // shrink/grow the vector from the loaded size to the output size.
276 // We assume this operation has no cost in codegen if there was no offset.
277 // Note that we could use freeze to avoid poison problems, but then we might
278 // still need a shuffle to change the vector size.
279 auto *Ty = cast<FixedVectorType>(I.getType());
280 unsigned OutputNumElts = Ty->getNumElements();
282 assert(OffsetEltIndex < MinVecNumElts && "Address offset too big");
283 Mask[0] = OffsetEltIndex;
284 if (OffsetEltIndex)
285 NewCost +=
287
288 // We can aggressively convert to the vector form because the backend can
289 // invert this transform if it does not result in a performance win.
290 if (OldCost < NewCost || !NewCost.isValid())
291 return false;
292
293 // It is safe and potentially profitable to load a vector directly:
294 // inselt undef, load Scalar, 0 --> load VecPtr
295 IRBuilder<> Builder(Load);
296 Value *CastedPtr =
297 Builder.CreatePointerBitCastOrAddrSpaceCast(SrcPtr, Builder.getPtrTy(AS));
298 Value *VecLd = Builder.CreateAlignedLoad(MinVecTy, CastedPtr, Alignment);
299 VecLd = Builder.CreateShuffleVector(VecLd, Mask);
300
301 replaceValue(I, *VecLd);
302 ++NumVecLoad;
303 return true;
304}
305
306/// If we are loading a vector and then inserting it into a larger vector with
307/// undefined elements, try to load the larger vector and eliminate the insert.
308/// This removes a shuffle in IR and may allow combining of other loaded values.
309bool VectorCombine::widenSubvectorLoad(Instruction &I) {
310 // Match subvector insert of fixed vector.
311 auto *Shuf = cast<ShuffleVectorInst>(&I);
312 if (!Shuf->isIdentityWithPadding())
313 return false;
314
315 // Allow a non-canonical shuffle mask that is choosing elements from op1.
316 unsigned NumOpElts =
317 cast<FixedVectorType>(Shuf->getOperand(0)->getType())->getNumElements();
318 unsigned OpIndex = any_of(Shuf->getShuffleMask(), [&NumOpElts](int M) {
319 return M >= (int)(NumOpElts);
320 });
321
322 auto *Load = dyn_cast<LoadInst>(Shuf->getOperand(OpIndex));
323 if (!canWidenLoad(Load, TTI))
324 return false;
325
326 // We use minimal alignment (maximum flexibility) because we only care about
327 // the dereferenceable region. When calculating cost and creating a new op,
328 // we may use a larger value based on alignment attributes.
329 auto *Ty = cast<FixedVectorType>(I.getType());
330 Value *SrcPtr = Load->getPointerOperand()->stripPointerCasts();
331 assert(isa<PointerType>(SrcPtr->getType()) && "Expected a pointer type");
332 Align Alignment = Load->getAlign();
333 if (!isSafeToLoadUnconditionally(SrcPtr, Ty, Align(1), *DL, Load, &AC, &DT))
334 return false;
335
336 Alignment = std::max(SrcPtr->getPointerAlignment(*DL), Alignment);
337 Type *LoadTy = Load->getType();
338 unsigned AS = Load->getPointerAddressSpace();
339
340 // Original pattern: insert_subvector (load PtrOp)
341 // This conservatively assumes that the cost of a subvector insert into an
342 // undef value is 0. We could add that cost if the cost model accurately
343 // reflects the real cost of that operation.
344 InstructionCost OldCost =
345 TTI.getMemoryOpCost(Instruction::Load, LoadTy, Alignment, AS, CostKind);
346
347 // New pattern: load PtrOp
348 InstructionCost NewCost =
349 TTI.getMemoryOpCost(Instruction::Load, Ty, Alignment, AS, CostKind);
350
351 // We can aggressively convert to the vector form because the backend can
352 // invert this transform if it does not result in a performance win.
353 if (OldCost < NewCost || !NewCost.isValid())
354 return false;
355
356 IRBuilder<> Builder(Load);
357 Value *CastedPtr =
358 Builder.CreatePointerBitCastOrAddrSpaceCast(SrcPtr, Builder.getPtrTy(AS));
359 Value *VecLd = Builder.CreateAlignedLoad(Ty, CastedPtr, Alignment);
360 replaceValue(I, *VecLd);
361 ++NumVecLoad;
362 return true;
363}
364
365/// Determine which, if any, of the inputs should be replaced by a shuffle
366/// followed by extract from a different index.
367ExtractElementInst *VectorCombine::getShuffleExtract(
369 unsigned PreferredExtractIndex = InvalidIndex) const {
370 auto *Index0C = dyn_cast<ConstantInt>(Ext0->getIndexOperand());
371 auto *Index1C = dyn_cast<ConstantInt>(Ext1->getIndexOperand());
372 assert(Index0C && Index1C && "Expected constant extract indexes");
373
374 unsigned Index0 = Index0C->getZExtValue();
375 unsigned Index1 = Index1C->getZExtValue();
376
377 // If the extract indexes are identical, no shuffle is needed.
378 if (Index0 == Index1)
379 return nullptr;
380
381 Type *VecTy = Ext0->getVectorOperand()->getType();
382 assert(VecTy == Ext1->getVectorOperand()->getType() && "Need matching types");
383 InstructionCost Cost0 =
384 TTI.getVectorInstrCost(*Ext0, VecTy, CostKind, Index0);
385 InstructionCost Cost1 =
386 TTI.getVectorInstrCost(*Ext1, VecTy, CostKind, Index1);
387
388 // If both costs are invalid no shuffle is needed
389 if (!Cost0.isValid() && !Cost1.isValid())
390 return nullptr;
391
392 // We are extracting from 2 different indexes, so one operand must be shuffled
393 // before performing a vector operation and/or extract. The more expensive
394 // extract will be replaced by a shuffle.
395 if (Cost0 > Cost1)
396 return Ext0;
397 if (Cost1 > Cost0)
398 return Ext1;
399
400 // If the costs are equal and there is a preferred extract index, shuffle the
401 // opposite operand.
402 if (PreferredExtractIndex == Index0)
403 return Ext1;
404 if (PreferredExtractIndex == Index1)
405 return Ext0;
406
407 // Otherwise, replace the extract with the higher index.
408 return Index0 > Index1 ? Ext0 : Ext1;
409}
410
411/// Compare the relative costs of 2 extracts followed by scalar operation vs.
412/// vector operation(s) followed by extract. Return true if the existing
413/// instructions are cheaper than a vector alternative. Otherwise, return false
414/// and if one of the extracts should be transformed to a shufflevector, set
415/// \p ConvertToShuffle to that extract instruction.
416bool VectorCombine::isExtractExtractCheap(ExtractElementInst *Ext0,
417 ExtractElementInst *Ext1,
418 const Instruction &I,
419 ExtractElementInst *&ConvertToShuffle,
420 unsigned PreferredExtractIndex) {
421 auto *Ext0IndexC = dyn_cast<ConstantInt>(Ext0->getIndexOperand());
422 auto *Ext1IndexC = dyn_cast<ConstantInt>(Ext1->getIndexOperand());
423 assert(Ext0IndexC && Ext1IndexC && "Expected constant extract indexes");
424
425 unsigned Opcode = I.getOpcode();
426 Value *Ext0Src = Ext0->getVectorOperand();
427 Value *Ext1Src = Ext1->getVectorOperand();
428 Type *ScalarTy = Ext0->getType();
429 auto *VecTy = cast<VectorType>(Ext0Src->getType());
430 InstructionCost ScalarOpCost, VectorOpCost;
431
432 // Get cost estimates for scalar and vector versions of the operation.
433 bool IsBinOp = Instruction::isBinaryOp(Opcode);
434 if (IsBinOp) {
435 ScalarOpCost = TTI.getArithmeticInstrCost(Opcode, ScalarTy, CostKind);
436 VectorOpCost = TTI.getArithmeticInstrCost(Opcode, VecTy, CostKind);
437 } else {
438 assert((Opcode == Instruction::ICmp || Opcode == Instruction::FCmp) &&
439 "Expected a compare");
440 CmpInst::Predicate Pred = cast<CmpInst>(I).getPredicate();
441 ScalarOpCost = TTI.getCmpSelInstrCost(
442 Opcode, ScalarTy, CmpInst::makeCmpResultType(ScalarTy), Pred, CostKind);
443 VectorOpCost = TTI.getCmpSelInstrCost(
444 Opcode, VecTy, CmpInst::makeCmpResultType(VecTy), Pred, CostKind);
445 }
446
447 // Get cost estimates for the extract elements. These costs will factor into
448 // both sequences.
449 unsigned Ext0Index = Ext0IndexC->getZExtValue();
450 unsigned Ext1Index = Ext1IndexC->getZExtValue();
451
452 InstructionCost Extract0Cost =
453 TTI.getVectorInstrCost(*Ext0, VecTy, CostKind, Ext0Index);
454 InstructionCost Extract1Cost =
455 TTI.getVectorInstrCost(*Ext1, VecTy, CostKind, Ext1Index);
456
457 // A more expensive extract will always be replaced by a splat shuffle.
458 // For example, if Ext0 is more expensive:
459 // opcode (extelt V0, Ext0), (ext V1, Ext1) -->
460 // extelt (opcode (splat V0, Ext0), V1), Ext1
461 // TODO: Evaluate whether that always results in lowest cost. Alternatively,
462 // check the cost of creating a broadcast shuffle and shuffling both
463 // operands to element 0.
464 unsigned BestExtIndex = Extract0Cost > Extract1Cost ? Ext0Index : Ext1Index;
465 unsigned BestInsIndex = Extract0Cost > Extract1Cost ? Ext1Index : Ext0Index;
466 InstructionCost CheapExtractCost = std::min(Extract0Cost, Extract1Cost);
467
468 // Extra uses of the extracts mean that we include those costs in the
469 // vector total because those instructions will not be eliminated.
470 InstructionCost OldCost, NewCost;
471 if (Ext0Src == Ext1Src && Ext0Index == Ext1Index) {
472 // Handle a special case. If the 2 extracts are identical, adjust the
473 // formulas to account for that. The extra use charge allows for either the
474 // CSE'd pattern or an unoptimized form with identical values:
475 // opcode (extelt V, C), (extelt V, C) --> extelt (opcode V, V), C
476 bool HasUseTax = Ext0 == Ext1 ? !Ext0->hasNUses(2)
477 : !Ext0->hasOneUse() || !Ext1->hasOneUse();
478 OldCost = CheapExtractCost + ScalarOpCost;
479 NewCost = VectorOpCost + CheapExtractCost + HasUseTax * CheapExtractCost;
480 } else {
481 // Handle the general case. Each extract is actually a different value:
482 // opcode (extelt V0, C0), (extelt V1, C1) --> extelt (opcode V0, V1), C
483 OldCost = Extract0Cost + Extract1Cost + ScalarOpCost;
484 NewCost = VectorOpCost + CheapExtractCost +
485 !Ext0->hasOneUse() * Extract0Cost +
486 !Ext1->hasOneUse() * Extract1Cost;
487 }
488
489 ConvertToShuffle = getShuffleExtract(Ext0, Ext1, PreferredExtractIndex);
490 if (ConvertToShuffle) {
491 if (IsBinOp && DisableBinopExtractShuffle)
492 return true;
493
494 // If we are extracting from 2 different indexes, then one operand must be
495 // shuffled before performing the vector operation. The shuffle mask is
496 // poison except for 1 lane that is being translated to the remaining
497 // extraction lane. Therefore, it is a splat shuffle. Ex:
498 // ShufMask = { poison, poison, 0, poison }
499 // TODO: The cost model has an option for a "broadcast" shuffle
500 // (splat-from-element-0), but no option for a more general splat.
501 if (auto *FixedVecTy = dyn_cast<FixedVectorType>(VecTy)) {
502 SmallVector<int> ShuffleMask(FixedVecTy->getNumElements(),
504 ShuffleMask[BestInsIndex] = BestExtIndex;
506 VecTy, ShuffleMask, CostKind, 0, nullptr,
507 {ConvertToShuffle});
508 } else {
509 NewCost +=
511 {}, CostKind, 0, nullptr, {ConvertToShuffle});
512 }
513 }
514
515 // Aggressively form a vector op if the cost is equal because the transform
516 // may enable further optimization.
517 // Codegen can reverse this transform (scalarize) if it was not profitable.
518 return OldCost < NewCost;
519}
520
521/// Create a shuffle that translates (shifts) 1 element from the input vector
522/// to a new element location.
523static Value *createShiftShuffle(Value *Vec, unsigned OldIndex,
524 unsigned NewIndex, IRBuilder<> &Builder) {
525 // The shuffle mask is poison except for 1 lane that is being translated
526 // to the new element index. Example for OldIndex == 2 and NewIndex == 0:
527 // ShufMask = { 2, poison, poison, poison }
528 auto *VecTy = cast<FixedVectorType>(Vec->getType());
529 SmallVector<int, 32> ShufMask(VecTy->getNumElements(), PoisonMaskElem);
530 ShufMask[NewIndex] = OldIndex;
531 return Builder.CreateShuffleVector(Vec, ShufMask, "shift");
532}
533
534/// Given an extract element instruction with constant index operand, shuffle
535/// the source vector (shift the scalar element) to a NewIndex for extraction.
536/// Return null if the input can be constant folded, so that we are not creating
537/// unnecessary instructions.
539 unsigned NewIndex,
540 IRBuilder<> &Builder) {
541 // Shufflevectors can only be created for fixed-width vectors.
542 Value *X = ExtElt->getVectorOperand();
543 if (!isa<FixedVectorType>(X->getType()))
544 return nullptr;
545
546 // If the extract can be constant-folded, this code is unsimplified. Defer
547 // to other passes to handle that.
548 Value *C = ExtElt->getIndexOperand();
549 assert(isa<ConstantInt>(C) && "Expected a constant index operand");
550 if (isa<Constant>(X))
551 return nullptr;
552
553 Value *Shuf = createShiftShuffle(X, cast<ConstantInt>(C)->getZExtValue(),
554 NewIndex, Builder);
555 return cast<ExtractElementInst>(Builder.CreateExtractElement(Shuf, NewIndex));
556}
557
558/// Try to reduce extract element costs by converting scalar compares to vector
559/// compares followed by extract.
560/// cmp (ext0 V0, C), (ext1 V1, C)
561void VectorCombine::foldExtExtCmp(ExtractElementInst *Ext0,
563 assert(isa<CmpInst>(&I) && "Expected a compare");
564 assert(cast<ConstantInt>(Ext0->getIndexOperand())->getZExtValue() ==
565 cast<ConstantInt>(Ext1->getIndexOperand())->getZExtValue() &&
566 "Expected matching constant extract indexes");
567
568 // cmp Pred (extelt V0, C), (extelt V1, C) --> extelt (cmp Pred V0, V1), C
569 ++NumVecCmp;
570 CmpInst::Predicate Pred = cast<CmpInst>(&I)->getPredicate();
571 Value *V0 = Ext0->getVectorOperand(), *V1 = Ext1->getVectorOperand();
572 Value *VecCmp = Builder.CreateCmp(Pred, V0, V1);
573 Value *NewExt = Builder.CreateExtractElement(VecCmp, Ext0->getIndexOperand());
574 replaceValue(I, *NewExt);
575}
576
577/// Try to reduce extract element costs by converting scalar binops to vector
578/// binops followed by extract.
579/// bo (ext0 V0, C), (ext1 V1, C)
580void VectorCombine::foldExtExtBinop(ExtractElementInst *Ext0,
582 assert(isa<BinaryOperator>(&I) && "Expected a binary operator");
583 assert(cast<ConstantInt>(Ext0->getIndexOperand())->getZExtValue() ==
584 cast<ConstantInt>(Ext1->getIndexOperand())->getZExtValue() &&
585 "Expected matching constant extract indexes");
586
587 // bo (extelt V0, C), (extelt V1, C) --> extelt (bo V0, V1), C
588 ++NumVecBO;
589 Value *V0 = Ext0->getVectorOperand(), *V1 = Ext1->getVectorOperand();
590 Value *VecBO =
591 Builder.CreateBinOp(cast<BinaryOperator>(&I)->getOpcode(), V0, V1);
592
593 // All IR flags are safe to back-propagate because any potential poison
594 // created in unused vector elements is discarded by the extract.
595 if (auto *VecBOInst = dyn_cast<Instruction>(VecBO))
596 VecBOInst->copyIRFlags(&I);
597
598 Value *NewExt = Builder.CreateExtractElement(VecBO, Ext0->getIndexOperand());
599 replaceValue(I, *NewExt);
600}
601
602/// Match an instruction with extracted vector operands.
603bool VectorCombine::foldExtractExtract(Instruction &I) {
604 // It is not safe to transform things like div, urem, etc. because we may
605 // create undefined behavior when executing those on unknown vector elements.
607 return false;
608
609 Instruction *I0, *I1;
611 if (!match(&I, m_Cmp(Pred, m_Instruction(I0), m_Instruction(I1))) &&
613 return false;
614
615 Value *V0, *V1;
616 uint64_t C0, C1;
617 if (!match(I0, m_ExtractElt(m_Value(V0), m_ConstantInt(C0))) ||
618 !match(I1, m_ExtractElt(m_Value(V1), m_ConstantInt(C1))) ||
619 V0->getType() != V1->getType())
620 return false;
621
622 // If the scalar value 'I' is going to be re-inserted into a vector, then try
623 // to create an extract to that same element. The extract/insert can be
624 // reduced to a "select shuffle".
625 // TODO: If we add a larger pattern match that starts from an insert, this
626 // probably becomes unnecessary.
627 auto *Ext0 = cast<ExtractElementInst>(I0);
628 auto *Ext1 = cast<ExtractElementInst>(I1);
629 uint64_t InsertIndex = InvalidIndex;
630 if (I.hasOneUse())
631 match(I.user_back(),
632 m_InsertElt(m_Value(), m_Value(), m_ConstantInt(InsertIndex)));
633
634 ExtractElementInst *ExtractToChange;
635 if (isExtractExtractCheap(Ext0, Ext1, I, ExtractToChange, InsertIndex))
636 return false;
637
638 if (ExtractToChange) {
639 unsigned CheapExtractIdx = ExtractToChange == Ext0 ? C1 : C0;
640 ExtractElementInst *NewExtract =
641 translateExtract(ExtractToChange, CheapExtractIdx, Builder);
642 if (!NewExtract)
643 return false;
644 if (ExtractToChange == Ext0)
645 Ext0 = NewExtract;
646 else
647 Ext1 = NewExtract;
648 }
649
650 if (Pred != CmpInst::BAD_ICMP_PREDICATE)
651 foldExtExtCmp(Ext0, Ext1, I);
652 else
653 foldExtExtBinop(Ext0, Ext1, I);
654
655 Worklist.push(Ext0);
656 Worklist.push(Ext1);
657 return true;
658}
659
660/// Try to replace an extract + scalar fneg + insert with a vector fneg +
661/// shuffle.
662bool VectorCombine::foldInsExtFNeg(Instruction &I) {
663 // Match an insert (op (extract)) pattern.
664 Value *DestVec;
666 Instruction *FNeg;
667 if (!match(&I, m_InsertElt(m_Value(DestVec), m_OneUse(m_Instruction(FNeg)),
668 m_ConstantInt(Index))))
669 return false;
670
671 // Note: This handles the canonical fneg instruction and "fsub -0.0, X".
672 Value *SrcVec;
673 Instruction *Extract;
674 if (!match(FNeg, m_FNeg(m_CombineAnd(
675 m_Instruction(Extract),
676 m_ExtractElt(m_Value(SrcVec), m_SpecificInt(Index))))))
677 return false;
678
679 auto *VecTy = cast<FixedVectorType>(I.getType());
680 auto *ScalarTy = VecTy->getScalarType();
681 auto *SrcVecTy = dyn_cast<FixedVectorType>(SrcVec->getType());
682 if (!SrcVecTy || ScalarTy != SrcVecTy->getScalarType())
683 return false;
684
685 // Ignore bogus insert/extract index.
686 unsigned NumElts = VecTy->getNumElements();
687 if (Index >= NumElts)
688 return false;
689
690 // We are inserting the negated element into the same lane that we extracted
691 // from. This is equivalent to a select-shuffle that chooses all but the
692 // negated element from the destination vector.
693 SmallVector<int> Mask(NumElts);
694 std::iota(Mask.begin(), Mask.end(), 0);
695 Mask[Index] = Index + NumElts;
696 InstructionCost OldCost =
697 TTI.getArithmeticInstrCost(Instruction::FNeg, ScalarTy, CostKind) +
698 TTI.getVectorInstrCost(I, VecTy, CostKind, Index);
699
700 // If the extract has one use, it will be eliminated, so count it in the
701 // original cost. If it has more than one use, ignore the cost because it will
702 // be the same before/after.
703 if (Extract->hasOneUse())
704 OldCost += TTI.getVectorInstrCost(*Extract, VecTy, CostKind, Index);
705
706 InstructionCost NewCost =
707 TTI.getArithmeticInstrCost(Instruction::FNeg, VecTy, CostKind) +
709
710 bool NeedLenChg = SrcVecTy->getNumElements() != NumElts;
711 // If the lengths of the two vectors are not equal,
712 // we need to add a length-change vector. Add this cost.
713 SmallVector<int> SrcMask;
714 if (NeedLenChg) {
715 SrcMask.assign(NumElts, PoisonMaskElem);
716 SrcMask[Index] = Index;
718 SrcVecTy, SrcMask, CostKind);
719 }
720
721 if (NewCost > OldCost)
722 return false;
723
724 Value *NewShuf;
725 // insertelt DestVec, (fneg (extractelt SrcVec, Index)), Index
726 Value *VecFNeg = Builder.CreateFNegFMF(SrcVec, FNeg);
727 if (NeedLenChg) {
728 // shuffle DestVec, (shuffle (fneg SrcVec), poison, SrcMask), Mask
729 Value *LenChgShuf = Builder.CreateShuffleVector(VecFNeg, SrcMask);
730 NewShuf = Builder.CreateShuffleVector(DestVec, LenChgShuf, Mask);
731 } else {
732 // shuffle DestVec, (fneg SrcVec), Mask
733 NewShuf = Builder.CreateShuffleVector(DestVec, VecFNeg, Mask);
734 }
735
736 replaceValue(I, *NewShuf);
737 return true;
738}
739
740/// If this is a bitcast of a shuffle, try to bitcast the source vector to the
741/// destination type followed by shuffle. This can enable further transforms by
742/// moving bitcasts or shuffles together.
743bool VectorCombine::foldBitcastShuffle(Instruction &I) {
744 Value *V0, *V1;
746 if (!match(&I, m_BitCast(m_OneUse(
747 m_Shuffle(m_Value(V0), m_Value(V1), m_Mask(Mask))))))
748 return false;
749
750 // 1) Do not fold bitcast shuffle for scalable type. First, shuffle cost for
751 // scalable type is unknown; Second, we cannot reason if the narrowed shuffle
752 // mask for scalable type is a splat or not.
753 // 2) Disallow non-vector casts.
754 // TODO: We could allow any shuffle.
755 auto *DestTy = dyn_cast<FixedVectorType>(I.getType());
756 auto *SrcTy = dyn_cast<FixedVectorType>(V0->getType());
757 if (!DestTy || !SrcTy)
758 return false;
759
760 unsigned DestEltSize = DestTy->getScalarSizeInBits();
761 unsigned SrcEltSize = SrcTy->getScalarSizeInBits();
762 if (SrcTy->getPrimitiveSizeInBits() % DestEltSize != 0)
763 return false;
764
765 bool IsUnary = isa<UndefValue>(V1);
766
767 // For binary shuffles, only fold bitcast(shuffle(X,Y))
768 // if it won't increase the number of bitcasts.
769 if (!IsUnary) {
770 auto *BCTy0 = dyn_cast<FixedVectorType>(peekThroughBitcasts(V0)->getType());
771 auto *BCTy1 = dyn_cast<FixedVectorType>(peekThroughBitcasts(V1)->getType());
772 if (!(BCTy0 && BCTy0->getElementType() == DestTy->getElementType()) &&
773 !(BCTy1 && BCTy1->getElementType() == DestTy->getElementType()))
774 return false;
775 }
776
777 SmallVector<int, 16> NewMask;
778 if (DestEltSize <= SrcEltSize) {
779 // The bitcast is from wide to narrow/equal elements. The shuffle mask can
780 // always be expanded to the equivalent form choosing narrower elements.
781 assert(SrcEltSize % DestEltSize == 0 && "Unexpected shuffle mask");
782 unsigned ScaleFactor = SrcEltSize / DestEltSize;
783 narrowShuffleMaskElts(ScaleFactor, Mask, NewMask);
784 } else {
785 // The bitcast is from narrow elements to wide elements. The shuffle mask
786 // must choose consecutive elements to allow casting first.
787 assert(DestEltSize % SrcEltSize == 0 && "Unexpected shuffle mask");
788 unsigned ScaleFactor = DestEltSize / SrcEltSize;
789 if (!widenShuffleMaskElts(ScaleFactor, Mask, NewMask))
790 return false;
791 }
792
793 // Bitcast the shuffle src - keep its original width but using the destination
794 // scalar type.
795 unsigned NumSrcElts = SrcTy->getPrimitiveSizeInBits() / DestEltSize;
796 auto *NewShuffleTy =
797 FixedVectorType::get(DestTy->getScalarType(), NumSrcElts);
798 auto *OldShuffleTy =
799 FixedVectorType::get(SrcTy->getScalarType(), Mask.size());
800 unsigned NumOps = IsUnary ? 1 : 2;
801
802 // The new shuffle must not cost more than the old shuffle.
806
807 InstructionCost NewCost =
808 TTI.getShuffleCost(SK, NewShuffleTy, NewMask, CostKind) +
809 (NumOps * TTI.getCastInstrCost(Instruction::BitCast, NewShuffleTy, SrcTy,
810 TargetTransformInfo::CastContextHint::None,
811 CostKind));
812 InstructionCost OldCost =
813 TTI.getShuffleCost(SK, SrcTy, Mask, CostKind) +
814 TTI.getCastInstrCost(Instruction::BitCast, DestTy, OldShuffleTy,
815 TargetTransformInfo::CastContextHint::None,
816 CostKind);
817
818 LLVM_DEBUG(dbgs() << "Found a bitcasted shuffle: " << I << "\n OldCost: "
819 << OldCost << " vs NewCost: " << NewCost << "\n");
820
821 if (NewCost > OldCost || !NewCost.isValid())
822 return false;
823
824 // bitcast (shuf V0, V1, MaskC) --> shuf (bitcast V0), (bitcast V1), MaskC'
825 ++NumShufOfBitcast;
826 Value *CastV0 = Builder.CreateBitCast(peekThroughBitcasts(V0), NewShuffleTy);
827 Value *CastV1 = Builder.CreateBitCast(peekThroughBitcasts(V1), NewShuffleTy);
828 Value *Shuf = Builder.CreateShuffleVector(CastV0, CastV1, NewMask);
829 replaceValue(I, *Shuf);
830 return true;
831}
832
833/// VP Intrinsics whose vector operands are both splat values may be simplified
834/// into the scalar version of the operation and the result splatted. This
835/// can lead to scalarization down the line.
836bool VectorCombine::scalarizeVPIntrinsic(Instruction &I) {
837 if (!isa<VPIntrinsic>(I))
838 return false;
839 VPIntrinsic &VPI = cast<VPIntrinsic>(I);
840 Value *Op0 = VPI.getArgOperand(0);
841 Value *Op1 = VPI.getArgOperand(1);
842
843 if (!isSplatValue(Op0) || !isSplatValue(Op1))
844 return false;
845
846 // Check getSplatValue early in this function, to avoid doing unnecessary
847 // work.
848 Value *ScalarOp0 = getSplatValue(Op0);
849 Value *ScalarOp1 = getSplatValue(Op1);
850 if (!ScalarOp0 || !ScalarOp1)
851 return false;
852
853 // For the binary VP intrinsics supported here, the result on disabled lanes
854 // is a poison value. For now, only do this simplification if all lanes
855 // are active.
856 // TODO: Relax the condition that all lanes are active by using insertelement
857 // on inactive lanes.
858 auto IsAllTrueMask = [](Value *MaskVal) {
859 if (Value *SplattedVal = getSplatValue(MaskVal))
860 if (auto *ConstValue = dyn_cast<Constant>(SplattedVal))
861 return ConstValue->isAllOnesValue();
862 return false;
863 };
864 if (!IsAllTrueMask(VPI.getArgOperand(2)))
865 return false;
866
867 // Check to make sure we support scalarization of the intrinsic
868 Intrinsic::ID IntrID = VPI.getIntrinsicID();
869 if (!VPBinOpIntrinsic::isVPBinOp(IntrID))
870 return false;
871
872 // Calculate cost of splatting both operands into vectors and the vector
873 // intrinsic
874 VectorType *VecTy = cast<VectorType>(VPI.getType());
876 if (auto *FVTy = dyn_cast<FixedVectorType>(VecTy))
877 Mask.resize(FVTy->getNumElements(), 0);
878 InstructionCost SplatCost =
879 TTI.getVectorInstrCost(Instruction::InsertElement, VecTy, CostKind, 0) +
881 CostKind);
882
883 // Calculate the cost of the VP Intrinsic
885 for (Value *V : VPI.args())
886 Args.push_back(V->getType());
887 IntrinsicCostAttributes Attrs(IntrID, VecTy, Args);
888 InstructionCost VectorOpCost = TTI.getIntrinsicInstrCost(Attrs, CostKind);
889 InstructionCost OldCost = 2 * SplatCost + VectorOpCost;
890
891 // Determine scalar opcode
892 std::optional<unsigned> FunctionalOpcode =
894 std::optional<Intrinsic::ID> ScalarIntrID = std::nullopt;
895 if (!FunctionalOpcode) {
896 ScalarIntrID = VPI.getFunctionalIntrinsicID();
897 if (!ScalarIntrID)
898 return false;
899 }
900
901 // Calculate cost of scalarizing
902 InstructionCost ScalarOpCost = 0;
903 if (ScalarIntrID) {
904 IntrinsicCostAttributes Attrs(*ScalarIntrID, VecTy->getScalarType(), Args);
905 ScalarOpCost = TTI.getIntrinsicInstrCost(Attrs, CostKind);
906 } else {
907 ScalarOpCost = TTI.getArithmeticInstrCost(*FunctionalOpcode,
908 VecTy->getScalarType(), CostKind);
909 }
910
911 // The existing splats may be kept around if other instructions use them.
912 InstructionCost CostToKeepSplats =
913 (SplatCost * !Op0->hasOneUse()) + (SplatCost * !Op1->hasOneUse());
914 InstructionCost NewCost = ScalarOpCost + SplatCost + CostToKeepSplats;
915
916 LLVM_DEBUG(dbgs() << "Found a VP Intrinsic to scalarize: " << VPI
917 << "\n");
918 LLVM_DEBUG(dbgs() << "Cost of Intrinsic: " << OldCost
919 << ", Cost of scalarizing:" << NewCost << "\n");
920
921 // We want to scalarize unless the vector variant actually has lower cost.
922 if (OldCost < NewCost || !NewCost.isValid())
923 return false;
924
925 // Scalarize the intrinsic
926 ElementCount EC = cast<VectorType>(Op0->getType())->getElementCount();
927 Value *EVL = VPI.getArgOperand(3);
928
929 // If the VP op might introduce UB or poison, we can scalarize it provided
930 // that we know the EVL > 0: If the EVL is zero, then the original VP op
931 // becomes a no-op and thus won't be UB, so make sure we don't introduce UB by
932 // scalarizing it.
933 bool SafeToSpeculate;
934 if (ScalarIntrID)
935 SafeToSpeculate = Intrinsic::getAttributes(I.getContext(), *ScalarIntrID)
936 .hasFnAttr(Attribute::AttrKind::Speculatable);
937 else
939 *FunctionalOpcode, &VPI, nullptr, &AC, &DT);
940 if (!SafeToSpeculate &&
941 !isKnownNonZero(EVL, SimplifyQuery(*DL, &DT, &AC, &VPI)))
942 return false;
943
944 Value *ScalarVal =
945 ScalarIntrID
946 ? Builder.CreateIntrinsic(VecTy->getScalarType(), *ScalarIntrID,
947 {ScalarOp0, ScalarOp1})
948 : Builder.CreateBinOp((Instruction::BinaryOps)(*FunctionalOpcode),
949 ScalarOp0, ScalarOp1);
950
951 replaceValue(VPI, *Builder.CreateVectorSplat(EC, ScalarVal));
952 return true;
953}
954
955/// Match a vector binop or compare instruction with at least one inserted
956/// scalar operand and convert to scalar binop/cmp followed by insertelement.
957bool VectorCombine::scalarizeBinopOrCmp(Instruction &I) {
959 Value *Ins0, *Ins1;
960 if (!match(&I, m_BinOp(m_Value(Ins0), m_Value(Ins1))) &&
961 !match(&I, m_Cmp(Pred, m_Value(Ins0), m_Value(Ins1))))
962 return false;
963
964 // Do not convert the vector condition of a vector select into a scalar
965 // condition. That may cause problems for codegen because of differences in
966 // boolean formats and register-file transfers.
967 // TODO: Can we account for that in the cost model?
968 bool IsCmp = Pred != CmpInst::Predicate::BAD_ICMP_PREDICATE;
969 if (IsCmp)
970 for (User *U : I.users())
971 if (match(U, m_Select(m_Specific(&I), m_Value(), m_Value())))
972 return false;
973
974 // Match against one or both scalar values being inserted into constant
975 // vectors:
976 // vec_op VecC0, (inselt VecC1, V1, Index)
977 // vec_op (inselt VecC0, V0, Index), VecC1
978 // vec_op (inselt VecC0, V0, Index), (inselt VecC1, V1, Index)
979 // TODO: Deal with mismatched index constants and variable indexes?
980 Constant *VecC0 = nullptr, *VecC1 = nullptr;
981 Value *V0 = nullptr, *V1 = nullptr;
982 uint64_t Index0 = 0, Index1 = 0;
983 if (!match(Ins0, m_InsertElt(m_Constant(VecC0), m_Value(V0),
984 m_ConstantInt(Index0))) &&
985 !match(Ins0, m_Constant(VecC0)))
986 return false;
987 if (!match(Ins1, m_InsertElt(m_Constant(VecC1), m_Value(V1),
988 m_ConstantInt(Index1))) &&
989 !match(Ins1, m_Constant(VecC1)))
990 return false;
991
992 bool IsConst0 = !V0;
993 bool IsConst1 = !V1;
994 if (IsConst0 && IsConst1)
995 return false;
996 if (!IsConst0 && !IsConst1 && Index0 != Index1)
997 return false;
998
999 auto *VecTy0 = cast<VectorType>(Ins0->getType());
1000 auto *VecTy1 = cast<VectorType>(Ins1->getType());
1001 if (VecTy0->getElementCount().getKnownMinValue() <= Index0 ||
1002 VecTy1->getElementCount().getKnownMinValue() <= Index1)
1003 return false;
1004
1005 // Bail for single insertion if it is a load.
1006 // TODO: Handle this once getVectorInstrCost can cost for load/stores.
1007 auto *I0 = dyn_cast_or_null<Instruction>(V0);
1008 auto *I1 = dyn_cast_or_null<Instruction>(V1);
1009 if ((IsConst0 && I1 && I1->mayReadFromMemory()) ||
1010 (IsConst1 && I0 && I0->mayReadFromMemory()))
1011 return false;
1012
1013 uint64_t Index = IsConst0 ? Index1 : Index0;
1014 Type *ScalarTy = IsConst0 ? V1->getType() : V0->getType();
1015 Type *VecTy = I.getType();
1016 assert(VecTy->isVectorTy() &&
1017 (IsConst0 || IsConst1 || V0->getType() == V1->getType()) &&
1018 (ScalarTy->isIntegerTy() || ScalarTy->isFloatingPointTy() ||
1019 ScalarTy->isPointerTy()) &&
1020 "Unexpected types for insert element into binop or cmp");
1021
1022 unsigned Opcode = I.getOpcode();
1023 InstructionCost ScalarOpCost, VectorOpCost;
1024 if (IsCmp) {
1025 CmpInst::Predicate Pred = cast<CmpInst>(I).getPredicate();
1026 ScalarOpCost = TTI.getCmpSelInstrCost(
1027 Opcode, ScalarTy, CmpInst::makeCmpResultType(ScalarTy), Pred, CostKind);
1028 VectorOpCost = TTI.getCmpSelInstrCost(
1029 Opcode, VecTy, CmpInst::makeCmpResultType(VecTy), Pred, CostKind);
1030 } else {
1031 ScalarOpCost = TTI.getArithmeticInstrCost(Opcode, ScalarTy, CostKind);
1032 VectorOpCost = TTI.getArithmeticInstrCost(Opcode, VecTy, CostKind);
1033 }
1034
1035 // Get cost estimate for the insert element. This cost will factor into
1036 // both sequences.
1038 Instruction::InsertElement, VecTy, CostKind, Index);
1039 InstructionCost OldCost =
1040 (IsConst0 ? 0 : InsertCost) + (IsConst1 ? 0 : InsertCost) + VectorOpCost;
1041 InstructionCost NewCost = ScalarOpCost + InsertCost +
1042 (IsConst0 ? 0 : !Ins0->hasOneUse() * InsertCost) +
1043 (IsConst1 ? 0 : !Ins1->hasOneUse() * InsertCost);
1044
1045 // We want to scalarize unless the vector variant actually has lower cost.
1046 if (OldCost < NewCost || !NewCost.isValid())
1047 return false;
1048
1049 // vec_op (inselt VecC0, V0, Index), (inselt VecC1, V1, Index) -->
1050 // inselt NewVecC, (scalar_op V0, V1), Index
1051 if (IsCmp)
1052 ++NumScalarCmp;
1053 else
1054 ++NumScalarBO;
1055
1056 // For constant cases, extract the scalar element, this should constant fold.
1057 if (IsConst0)
1058 V0 = ConstantExpr::getExtractElement(VecC0, Builder.getInt64(Index));
1059 if (IsConst1)
1060 V1 = ConstantExpr::getExtractElement(VecC1, Builder.getInt64(Index));
1061
1062 Value *Scalar =
1063 IsCmp ? Builder.CreateCmp(Pred, V0, V1)
1064 : Builder.CreateBinOp((Instruction::BinaryOps)Opcode, V0, V1);
1065
1066 Scalar->setName(I.getName() + ".scalar");
1067
1068 // All IR flags are safe to back-propagate. There is no potential for extra
1069 // poison to be created by the scalar instruction.
1070 if (auto *ScalarInst = dyn_cast<Instruction>(Scalar))
1071 ScalarInst->copyIRFlags(&I);
1072
1073 // Fold the vector constants in the original vectors into a new base vector.
1074 Value *NewVecC =
1075 IsCmp ? Builder.CreateCmp(Pred, VecC0, VecC1)
1076 : Builder.CreateBinOp((Instruction::BinaryOps)Opcode, VecC0, VecC1);
1077 Value *Insert = Builder.CreateInsertElement(NewVecC, Scalar, Index);
1078 replaceValue(I, *Insert);
1079 return true;
1080}
1081
1082/// Try to combine a scalar binop + 2 scalar compares of extracted elements of
1083/// a vector into vector operations followed by extract. Note: The SLP pass
1084/// may miss this pattern because of implementation problems.
1085bool VectorCombine::foldExtractedCmps(Instruction &I) {
1086 auto *BI = dyn_cast<BinaryOperator>(&I);
1087
1088 // We are looking for a scalar binop of booleans.
1089 // binop i1 (cmp Pred I0, C0), (cmp Pred I1, C1)
1090 if (!BI || !I.getType()->isIntegerTy(1))
1091 return false;
1092
1093 // The compare predicates should match, and each compare should have a
1094 // constant operand.
1095 Value *B0 = I.getOperand(0), *B1 = I.getOperand(1);
1096 Instruction *I0, *I1;
1097 Constant *C0, *C1;
1098 CmpPredicate P0, P1;
1099 // FIXME: Use CmpPredicate::getMatching here.
1100 if (!match(B0, m_Cmp(P0, m_Instruction(I0), m_Constant(C0))) ||
1101 !match(B1, m_Cmp(P1, m_Instruction(I1), m_Constant(C1))) ||
1102 P0 != static_cast<CmpInst::Predicate>(P1))
1103 return false;
1104
1105 // The compare operands must be extracts of the same vector with constant
1106 // extract indexes.
1107 Value *X;
1108 uint64_t Index0, Index1;
1109 if (!match(I0, m_ExtractElt(m_Value(X), m_ConstantInt(Index0))) ||
1110 !match(I1, m_ExtractElt(m_Specific(X), m_ConstantInt(Index1))))
1111 return false;
1112
1113 auto *Ext0 = cast<ExtractElementInst>(I0);
1114 auto *Ext1 = cast<ExtractElementInst>(I1);
1115 ExtractElementInst *ConvertToShuf = getShuffleExtract(Ext0, Ext1, CostKind);
1116 if (!ConvertToShuf)
1117 return false;
1118 assert((ConvertToShuf == Ext0 || ConvertToShuf == Ext1) &&
1119 "Unknown ExtractElementInst");
1120
1121 // The original scalar pattern is:
1122 // binop i1 (cmp Pred (ext X, Index0), C0), (cmp Pred (ext X, Index1), C1)
1123 CmpInst::Predicate Pred = P0;
1124 unsigned CmpOpcode =
1125 CmpInst::isFPPredicate(Pred) ? Instruction::FCmp : Instruction::ICmp;
1126 auto *VecTy = dyn_cast<FixedVectorType>(X->getType());
1127 if (!VecTy)
1128 return false;
1129
1130 InstructionCost Ext0Cost =
1131 TTI.getVectorInstrCost(*Ext0, VecTy, CostKind, Index0);
1132 InstructionCost Ext1Cost =
1133 TTI.getVectorInstrCost(*Ext1, VecTy, CostKind, Index1);
1135 CmpOpcode, I0->getType(), CmpInst::makeCmpResultType(I0->getType()), Pred,
1136 CostKind);
1137
1138 InstructionCost OldCost =
1139 Ext0Cost + Ext1Cost + CmpCost * 2 +
1140 TTI.getArithmeticInstrCost(I.getOpcode(), I.getType(), CostKind);
1141
1142 // The proposed vector pattern is:
1143 // vcmp = cmp Pred X, VecC
1144 // ext (binop vNi1 vcmp, (shuffle vcmp, Index1)), Index0
1145 int CheapIndex = ConvertToShuf == Ext0 ? Index1 : Index0;
1146 int ExpensiveIndex = ConvertToShuf == Ext0 ? Index0 : Index1;
1147 auto *CmpTy = cast<FixedVectorType>(CmpInst::makeCmpResultType(X->getType()));
1149 CmpOpcode, X->getType(), CmpInst::makeCmpResultType(X->getType()), Pred,
1150 CostKind);
1151 SmallVector<int, 32> ShufMask(VecTy->getNumElements(), PoisonMaskElem);
1152 ShufMask[CheapIndex] = ExpensiveIndex;
1154 ShufMask, CostKind);
1155 NewCost += TTI.getArithmeticInstrCost(I.getOpcode(), CmpTy, CostKind);
1156 NewCost += TTI.getVectorInstrCost(*Ext0, CmpTy, CostKind, CheapIndex);
1157 NewCost += Ext0->hasOneUse() ? 0 : Ext0Cost;
1158 NewCost += Ext1->hasOneUse() ? 0 : Ext1Cost;
1159
1160 // Aggressively form vector ops if the cost is equal because the transform
1161 // may enable further optimization.
1162 // Codegen can reverse this transform (scalarize) if it was not profitable.
1163 if (OldCost < NewCost || !NewCost.isValid())
1164 return false;
1165
1166 // Create a vector constant from the 2 scalar constants.
1167 SmallVector<Constant *, 32> CmpC(VecTy->getNumElements(),
1168 PoisonValue::get(VecTy->getElementType()));
1169 CmpC[Index0] = C0;
1170 CmpC[Index1] = C1;
1171 Value *VCmp = Builder.CreateCmp(Pred, X, ConstantVector::get(CmpC));
1172 Value *Shuf = createShiftShuffle(VCmp, ExpensiveIndex, CheapIndex, Builder);
1173 Value *LHS = ConvertToShuf == Ext0 ? Shuf : VCmp;
1174 Value *RHS = ConvertToShuf == Ext0 ? VCmp : Shuf;
1175 Value *VecLogic = Builder.CreateBinOp(BI->getOpcode(), LHS, RHS);
1176 Value *NewExt = Builder.CreateExtractElement(VecLogic, CheapIndex);
1177 replaceValue(I, *NewExt);
1178 ++NumVecCmpBO;
1179 return true;
1180}
1181
1182// Check if memory loc modified between two instrs in the same BB
1185 const MemoryLocation &Loc, AAResults &AA) {
1186 unsigned NumScanned = 0;
1187 return std::any_of(Begin, End, [&](const Instruction &Instr) {
1188 return isModSet(AA.getModRefInfo(&Instr, Loc)) ||
1189 ++NumScanned > MaxInstrsToScan;
1190 });
1191}
1192
1193namespace {
1194/// Helper class to indicate whether a vector index can be safely scalarized and
1195/// if a freeze needs to be inserted.
1196class ScalarizationResult {
1197 enum class StatusTy { Unsafe, Safe, SafeWithFreeze };
1198
1199 StatusTy Status;
1200 Value *ToFreeze;
1201
1202 ScalarizationResult(StatusTy Status, Value *ToFreeze = nullptr)
1203 : Status(Status), ToFreeze(ToFreeze) {}
1204
1205public:
1206 ScalarizationResult(const ScalarizationResult &Other) = default;
1207 ~ScalarizationResult() {
1208 assert(!ToFreeze && "freeze() not called with ToFreeze being set");
1209 }
1210
1211 static ScalarizationResult unsafe() { return {StatusTy::Unsafe}; }
1212 static ScalarizationResult safe() { return {StatusTy::Safe}; }
1213 static ScalarizationResult safeWithFreeze(Value *ToFreeze) {
1214 return {StatusTy::SafeWithFreeze, ToFreeze};
1215 }
1216
1217 /// Returns true if the index can be scalarize without requiring a freeze.
1218 bool isSafe() const { return Status == StatusTy::Safe; }
1219 /// Returns true if the index cannot be scalarized.
1220 bool isUnsafe() const { return Status == StatusTy::Unsafe; }
1221 /// Returns true if the index can be scalarize, but requires inserting a
1222 /// freeze.
1223 bool isSafeWithFreeze() const { return Status == StatusTy::SafeWithFreeze; }
1224
1225 /// Reset the state of Unsafe and clear ToFreze if set.
1226 void discard() {
1227 ToFreeze = nullptr;
1228 Status = StatusTy::Unsafe;
1229 }
1230
1231 /// Freeze the ToFreeze and update the use in \p User to use it.
1232 void freeze(IRBuilder<> &Builder, Instruction &UserI) {
1233 assert(isSafeWithFreeze() &&
1234 "should only be used when freezing is required");
1235 assert(is_contained(ToFreeze->users(), &UserI) &&
1236 "UserI must be a user of ToFreeze");
1237 IRBuilder<>::InsertPointGuard Guard(Builder);
1238 Builder.SetInsertPoint(cast<Instruction>(&UserI));
1239 Value *Frozen =
1240 Builder.CreateFreeze(ToFreeze, ToFreeze->getName() + ".frozen");
1241 for (Use &U : make_early_inc_range((UserI.operands())))
1242 if (U.get() == ToFreeze)
1243 U.set(Frozen);
1244
1245 ToFreeze = nullptr;
1246 }
1247};
1248} // namespace
1249
1250/// Check if it is legal to scalarize a memory access to \p VecTy at index \p
1251/// Idx. \p Idx must access a valid vector element.
1252static ScalarizationResult canScalarizeAccess(VectorType *VecTy, Value *Idx,
1253 Instruction *CtxI,
1254 AssumptionCache &AC,
1255 const DominatorTree &DT) {
1256 // We do checks for both fixed vector types and scalable vector types.
1257 // This is the number of elements of fixed vector types,
1258 // or the minimum number of elements of scalable vector types.
1259 uint64_t NumElements = VecTy->getElementCount().getKnownMinValue();
1260
1261 if (auto *C = dyn_cast<ConstantInt>(Idx)) {
1262 if (C->getValue().ult(NumElements))
1263 return ScalarizationResult::safe();
1264 return ScalarizationResult::unsafe();
1265 }
1266
1267 unsigned IntWidth = Idx->getType()->getScalarSizeInBits();
1268 APInt Zero(IntWidth, 0);
1269 APInt MaxElts(IntWidth, NumElements);
1270 ConstantRange ValidIndices(Zero, MaxElts);
1271 ConstantRange IdxRange(IntWidth, true);
1272
1273 if (isGuaranteedNotToBePoison(Idx, &AC)) {
1274 if (ValidIndices.contains(computeConstantRange(Idx, /* ForSigned */ false,
1275 true, &AC, CtxI, &DT)))
1276 return ScalarizationResult::safe();
1277 return ScalarizationResult::unsafe();
1278 }
1279
1280 // If the index may be poison, check if we can insert a freeze before the
1281 // range of the index is restricted.
1282 Value *IdxBase;
1283 ConstantInt *CI;
1284 if (match(Idx, m_And(m_Value(IdxBase), m_ConstantInt(CI)))) {
1285 IdxRange = IdxRange.binaryAnd(CI->getValue());
1286 } else if (match(Idx, m_URem(m_Value(IdxBase), m_ConstantInt(CI)))) {
1287 IdxRange = IdxRange.urem(CI->getValue());
1288 }
1289
1290 if (ValidIndices.contains(IdxRange))
1291 return ScalarizationResult::safeWithFreeze(IdxBase);
1292 return ScalarizationResult::unsafe();
1293}
1294
1295/// The memory operation on a vector of \p ScalarType had alignment of
1296/// \p VectorAlignment. Compute the maximal, but conservatively correct,
1297/// alignment that will be valid for the memory operation on a single scalar
1298/// element of the same type with index \p Idx.
1300 Type *ScalarType, Value *Idx,
1301 const DataLayout &DL) {
1302 if (auto *C = dyn_cast<ConstantInt>(Idx))
1303 return commonAlignment(VectorAlignment,
1304 C->getZExtValue() * DL.getTypeStoreSize(ScalarType));
1305 return commonAlignment(VectorAlignment, DL.getTypeStoreSize(ScalarType));
1306}
1307
1308// Combine patterns like:
1309// %0 = load <4 x i32>, <4 x i32>* %a
1310// %1 = insertelement <4 x i32> %0, i32 %b, i32 1
1311// store <4 x i32> %1, <4 x i32>* %a
1312// to:
1313// %0 = bitcast <4 x i32>* %a to i32*
1314// %1 = getelementptr inbounds i32, i32* %0, i64 0, i64 1
1315// store i32 %b, i32* %1
1316bool VectorCombine::foldSingleElementStore(Instruction &I) {
1317 auto *SI = cast<StoreInst>(&I);
1318 if (!SI->isSimple() || !isa<VectorType>(SI->getValueOperand()->getType()))
1319 return false;
1320
1321 // TODO: Combine more complicated patterns (multiple insert) by referencing
1322 // TargetTransformInfo.
1324 Value *NewElement;
1325 Value *Idx;
1326 if (!match(SI->getValueOperand(),
1327 m_InsertElt(m_Instruction(Source), m_Value(NewElement),
1328 m_Value(Idx))))
1329 return false;
1330
1331 if (auto *Load = dyn_cast<LoadInst>(Source)) {
1332 auto VecTy = cast<VectorType>(SI->getValueOperand()->getType());
1333 Value *SrcAddr = Load->getPointerOperand()->stripPointerCasts();
1334 // Don't optimize for atomic/volatile load or store. Ensure memory is not
1335 // modified between, vector type matches store size, and index is inbounds.
1336 if (!Load->isSimple() || Load->getParent() != SI->getParent() ||
1337 !DL->typeSizeEqualsStoreSize(Load->getType()->getScalarType()) ||
1338 SrcAddr != SI->getPointerOperand()->stripPointerCasts())
1339 return false;
1340
1341 auto ScalarizableIdx = canScalarizeAccess(VecTy, Idx, Load, AC, DT);
1342 if (ScalarizableIdx.isUnsafe() ||
1343 isMemModifiedBetween(Load->getIterator(), SI->getIterator(),
1344 MemoryLocation::get(SI), AA))
1345 return false;
1346
1347 // Ensure we add the load back to the worklist BEFORE its users so they can
1348 // erased in the correct order.
1349 Worklist.push(Load);
1350
1351 if (ScalarizableIdx.isSafeWithFreeze())
1352 ScalarizableIdx.freeze(Builder, *cast<Instruction>(Idx));
1353 Value *GEP = Builder.CreateInBoundsGEP(
1354 SI->getValueOperand()->getType(), SI->getPointerOperand(),
1355 {ConstantInt::get(Idx->getType(), 0), Idx});
1356 StoreInst *NSI = Builder.CreateStore(NewElement, GEP);
1357 NSI->copyMetadata(*SI);
1358 Align ScalarOpAlignment = computeAlignmentAfterScalarization(
1359 std::max(SI->getAlign(), Load->getAlign()), NewElement->getType(), Idx,
1360 *DL);
1361 NSI->setAlignment(ScalarOpAlignment);
1362 replaceValue(I, *NSI);
1364 return true;
1365 }
1366
1367 return false;
1368}
1369
1370/// Try to scalarize vector loads feeding extractelement instructions.
1371bool VectorCombine::scalarizeLoadExtract(Instruction &I) {
1372 Value *Ptr;
1373 if (!match(&I, m_Load(m_Value(Ptr))))
1374 return false;
1375
1376 auto *LI = cast<LoadInst>(&I);
1377 auto *VecTy = cast<VectorType>(LI->getType());
1378 if (LI->isVolatile() || !DL->typeSizeEqualsStoreSize(VecTy->getScalarType()))
1379 return false;
1380
1381 InstructionCost OriginalCost =
1382 TTI.getMemoryOpCost(Instruction::Load, VecTy, LI->getAlign(),
1383 LI->getPointerAddressSpace(), CostKind);
1384 InstructionCost ScalarizedCost = 0;
1385
1386 Instruction *LastCheckedInst = LI;
1387 unsigned NumInstChecked = 0;
1389 auto FailureGuard = make_scope_exit([&]() {
1390 // If the transform is aborted, discard the ScalarizationResults.
1391 for (auto &Pair : NeedFreeze)
1392 Pair.second.discard();
1393 });
1394
1395 // Check if all users of the load are extracts with no memory modifications
1396 // between the load and the extract. Compute the cost of both the original
1397 // code and the scalarized version.
1398 for (User *U : LI->users()) {
1399 auto *UI = dyn_cast<ExtractElementInst>(U);
1400 if (!UI || UI->getParent() != LI->getParent())
1401 return false;
1402
1403 // Check if any instruction between the load and the extract may modify
1404 // memory.
1405 if (LastCheckedInst->comesBefore(UI)) {
1406 for (Instruction &I :
1407 make_range(std::next(LI->getIterator()), UI->getIterator())) {
1408 // Bail out if we reached the check limit or the instruction may write
1409 // to memory.
1410 if (NumInstChecked == MaxInstrsToScan || I.mayWriteToMemory())
1411 return false;
1412 NumInstChecked++;
1413 }
1414 LastCheckedInst = UI;
1415 }
1416
1417 auto ScalarIdx =
1418 canScalarizeAccess(VecTy, UI->getIndexOperand(), LI, AC, DT);
1419 if (ScalarIdx.isUnsafe())
1420 return false;
1421 if (ScalarIdx.isSafeWithFreeze()) {
1422 NeedFreeze.try_emplace(UI, ScalarIdx);
1423 ScalarIdx.discard();
1424 }
1425
1426 auto *Index = dyn_cast<ConstantInt>(UI->getIndexOperand());
1427 OriginalCost +=
1428 TTI.getVectorInstrCost(Instruction::ExtractElement, VecTy, CostKind,
1429 Index ? Index->getZExtValue() : -1);
1430 ScalarizedCost +=
1431 TTI.getMemoryOpCost(Instruction::Load, VecTy->getElementType(),
1432 Align(1), LI->getPointerAddressSpace(), CostKind);
1433 ScalarizedCost += TTI.getAddressComputationCost(VecTy->getElementType());
1434 }
1435
1436 if (ScalarizedCost >= OriginalCost)
1437 return false;
1438
1439 // Ensure we add the load back to the worklist BEFORE its users so they can
1440 // erased in the correct order.
1441 Worklist.push(LI);
1442
1443 // Replace extracts with narrow scalar loads.
1444 for (User *U : LI->users()) {
1445 auto *EI = cast<ExtractElementInst>(U);
1446 Value *Idx = EI->getIndexOperand();
1447
1448 // Insert 'freeze' for poison indexes.
1449 auto It = NeedFreeze.find(EI);
1450 if (It != NeedFreeze.end())
1451 It->second.freeze(Builder, *cast<Instruction>(Idx));
1452
1453 Builder.SetInsertPoint(EI);
1454 Value *GEP =
1455 Builder.CreateInBoundsGEP(VecTy, Ptr, {Builder.getInt32(0), Idx});
1456 auto *NewLoad = cast<LoadInst>(Builder.CreateLoad(
1457 VecTy->getElementType(), GEP, EI->getName() + ".scalar"));
1458
1459 Align ScalarOpAlignment = computeAlignmentAfterScalarization(
1460 LI->getAlign(), VecTy->getElementType(), Idx, *DL);
1461 NewLoad->setAlignment(ScalarOpAlignment);
1462
1463 replaceValue(*EI, *NewLoad);
1464 }
1465
1466 FailureGuard.release();
1467 return true;
1468}
1469
1470/// Try to fold "(or (zext (bitcast X)), (shl (zext (bitcast Y)), C))"
1471/// to "(bitcast (concat X, Y))"
1472/// where X/Y are bitcasted from i1 mask vectors.
1473bool VectorCombine::foldConcatOfBoolMasks(Instruction &I) {
1474 Type *Ty = I.getType();
1475 if (!Ty->isIntegerTy())
1476 return false;
1477
1478 // TODO: Add big endian test coverage
1479 if (DL->isBigEndian())
1480 return false;
1481
1482 // Restrict to disjoint cases so the mask vectors aren't overlapping.
1483 Instruction *X, *Y;
1485 return false;
1486
1487 // Allow both sources to contain shl, to handle more generic pattern:
1488 // "(or (shl (zext (bitcast X)), C1), (shl (zext (bitcast Y)), C2))"
1489 Value *SrcX;
1490 uint64_t ShAmtX = 0;
1491 if (!match(X, m_OneUse(m_ZExt(m_OneUse(m_BitCast(m_Value(SrcX)))))) &&
1492 !match(X, m_OneUse(
1494 m_ConstantInt(ShAmtX)))))
1495 return false;
1496
1497 Value *SrcY;
1498 uint64_t ShAmtY = 0;
1499 if (!match(Y, m_OneUse(m_ZExt(m_OneUse(m_BitCast(m_Value(SrcY)))))) &&
1500 !match(Y, m_OneUse(
1502 m_ConstantInt(ShAmtY)))))
1503 return false;
1504
1505 // Canonicalize larger shift to the RHS.
1506 if (ShAmtX > ShAmtY) {
1507 std::swap(X, Y);
1508 std::swap(SrcX, SrcY);
1509 std::swap(ShAmtX, ShAmtY);
1510 }
1511
1512 // Ensure both sources are matching vXi1 bool mask types, and that the shift
1513 // difference is the mask width so they can be easily concatenated together.
1514 uint64_t ShAmtDiff = ShAmtY - ShAmtX;
1515 unsigned NumSHL = (ShAmtX > 0) + (ShAmtY > 0);
1516 unsigned BitWidth = Ty->getPrimitiveSizeInBits();
1517 auto *MaskTy = dyn_cast<FixedVectorType>(SrcX->getType());
1518 if (!MaskTy || SrcX->getType() != SrcY->getType() ||
1519 !MaskTy->getElementType()->isIntegerTy(1) ||
1520 MaskTy->getNumElements() != ShAmtDiff ||
1521 MaskTy->getNumElements() > (BitWidth / 2))
1522 return false;
1523
1524 auto *ConcatTy = FixedVectorType::getDoubleElementsVectorType(MaskTy);
1525 auto *ConcatIntTy =
1526 Type::getIntNTy(Ty->getContext(), ConcatTy->getNumElements());
1527 auto *MaskIntTy = Type::getIntNTy(Ty->getContext(), ShAmtDiff);
1528
1529 SmallVector<int, 32> ConcatMask(ConcatTy->getNumElements());
1530 std::iota(ConcatMask.begin(), ConcatMask.end(), 0);
1531
1532 // TODO: Is it worth supporting multi use cases?
1533 InstructionCost OldCost = 0;
1534 OldCost += TTI.getArithmeticInstrCost(Instruction::Or, Ty, CostKind);
1535 OldCost +=
1536 NumSHL * TTI.getArithmeticInstrCost(Instruction::Shl, Ty, CostKind);
1537 OldCost += 2 * TTI.getCastInstrCost(Instruction::ZExt, Ty, MaskIntTy,
1539 OldCost += 2 * TTI.getCastInstrCost(Instruction::BitCast, MaskIntTy, MaskTy,
1541
1542 InstructionCost NewCost = 0;
1544 ConcatMask, CostKind);
1545 NewCost += TTI.getCastInstrCost(Instruction::BitCast, ConcatIntTy, ConcatTy,
1547 if (Ty != ConcatIntTy)
1548 NewCost += TTI.getCastInstrCost(Instruction::ZExt, Ty, ConcatIntTy,
1550 if (ShAmtX > 0)
1551 NewCost += TTI.getArithmeticInstrCost(Instruction::Shl, Ty, CostKind);
1552
1553 LLVM_DEBUG(dbgs() << "Found a concatenation of bitcasted bool masks: " << I
1554 << "\n OldCost: " << OldCost << " vs NewCost: " << NewCost
1555 << "\n");
1556
1557 if (NewCost > OldCost)
1558 return false;
1559
1560 // Build bool mask concatenation, bitcast back to scalar integer, and perform
1561 // any residual zero-extension or shifting.
1562 Value *Concat = Builder.CreateShuffleVector(SrcX, SrcY, ConcatMask);
1563 Worklist.pushValue(Concat);
1564
1565 Value *Result = Builder.CreateBitCast(Concat, ConcatIntTy);
1566
1567 if (Ty != ConcatIntTy) {
1568 Worklist.pushValue(Result);
1569 Result = Builder.CreateZExt(Result, Ty);
1570 }
1571
1572 if (ShAmtX > 0) {
1573 Worklist.pushValue(Result);
1574 Result = Builder.CreateShl(Result, ShAmtX);
1575 }
1576
1577 replaceValue(I, *Result);
1578 return true;
1579}
1580
1581/// Try to convert "shuffle (binop (shuffle, shuffle)), undef"
1582/// --> "binop (shuffle), (shuffle)".
1583bool VectorCombine::foldPermuteOfBinops(Instruction &I) {
1584 BinaryOperator *BinOp;
1585 ArrayRef<int> OuterMask;
1586 if (!match(&I,
1587 m_Shuffle(m_OneUse(m_BinOp(BinOp)), m_Undef(), m_Mask(OuterMask))))
1588 return false;
1589
1590 // Don't introduce poison into div/rem.
1591 if (BinOp->isIntDivRem() && llvm::is_contained(OuterMask, PoisonMaskElem))
1592 return false;
1593
1594 Value *Op00, *Op01;
1595 ArrayRef<int> Mask0;
1596 if (!match(BinOp->getOperand(0),
1597 m_OneUse(m_Shuffle(m_Value(Op00), m_Value(Op01), m_Mask(Mask0)))))
1598 return false;
1599
1600 Value *Op10, *Op11;
1601 ArrayRef<int> Mask1;
1602 if (!match(BinOp->getOperand(1),
1603 m_OneUse(m_Shuffle(m_Value(Op10), m_Value(Op11), m_Mask(Mask1)))))
1604 return false;
1605
1606 Instruction::BinaryOps Opcode = BinOp->getOpcode();
1607 auto *ShuffleDstTy = dyn_cast<FixedVectorType>(I.getType());
1608 auto *BinOpTy = dyn_cast<FixedVectorType>(BinOp->getType());
1609 auto *Op0Ty = dyn_cast<FixedVectorType>(Op00->getType());
1610 auto *Op1Ty = dyn_cast<FixedVectorType>(Op10->getType());
1611 if (!ShuffleDstTy || !BinOpTy || !Op0Ty || !Op1Ty)
1612 return false;
1613
1614 unsigned NumSrcElts = BinOpTy->getNumElements();
1615
1616 // Don't accept shuffles that reference the second operand in
1617 // div/rem or if its an undef arg.
1618 if ((BinOp->isIntDivRem() || !isa<PoisonValue>(I.getOperand(1))) &&
1619 any_of(OuterMask, [NumSrcElts](int M) { return M >= (int)NumSrcElts; }))
1620 return false;
1621
1622 // Merge outer / inner shuffles.
1623 SmallVector<int> NewMask0, NewMask1;
1624 for (int M : OuterMask) {
1625 if (M < 0 || M >= (int)NumSrcElts) {
1626 NewMask0.push_back(PoisonMaskElem);
1627 NewMask1.push_back(PoisonMaskElem);
1628 } else {
1629 NewMask0.push_back(Mask0[M]);
1630 NewMask1.push_back(Mask1[M]);
1631 }
1632 }
1633
1634 // Try to merge shuffles across the binop if the new shuffles are not costly.
1635 InstructionCost OldCost =
1636 TTI.getArithmeticInstrCost(Opcode, BinOpTy, CostKind) +
1638 OuterMask, CostKind, 0, nullptr, {BinOp}, &I) +
1640 CostKind, 0, nullptr, {Op00, Op01},
1641 cast<Instruction>(BinOp->getOperand(0))) +
1643 CostKind, 0, nullptr, {Op10, Op11},
1644 cast<Instruction>(BinOp->getOperand(1)));
1645
1646 InstructionCost NewCost =
1648 CostKind, 0, nullptr, {Op00, Op01}) +
1650 CostKind, 0, nullptr, {Op10, Op11}) +
1651 TTI.getArithmeticInstrCost(Opcode, ShuffleDstTy, CostKind);
1652
1653 LLVM_DEBUG(dbgs() << "Found a shuffle feeding a shuffled binop: " << I
1654 << "\n OldCost: " << OldCost << " vs NewCost: " << NewCost
1655 << "\n");
1656
1657 // If costs are equal, still fold as we reduce instruction count.
1658 if (NewCost > OldCost)
1659 return false;
1660
1661 Value *Shuf0 = Builder.CreateShuffleVector(Op00, Op01, NewMask0);
1662 Value *Shuf1 = Builder.CreateShuffleVector(Op10, Op11, NewMask1);
1663 Value *NewBO = Builder.CreateBinOp(Opcode, Shuf0, Shuf1);
1664
1665 // Intersect flags from the old binops.
1666 if (auto *NewInst = dyn_cast<Instruction>(NewBO))
1667 NewInst->copyIRFlags(BinOp);
1668
1669 Worklist.pushValue(Shuf0);
1670 Worklist.pushValue(Shuf1);
1671 replaceValue(I, *NewBO);
1672 return true;
1673}
1674
1675/// Try to convert "shuffle (binop), (binop)" into "binop (shuffle), (shuffle)".
1676/// Try to convert "shuffle (cmpop), (cmpop)" into "cmpop (shuffle), (shuffle)".
1677bool VectorCombine::foldShuffleOfBinops(Instruction &I) {
1678 ArrayRef<int> OldMask;
1679 Instruction *LHS, *RHS;
1680 if (!match(&I, m_Shuffle(m_OneUse(m_Instruction(LHS)),
1681 m_OneUse(m_Instruction(RHS)), m_Mask(OldMask))))
1682 return false;
1683
1684 // TODO: Add support for addlike etc.
1685 if (LHS->getOpcode() != RHS->getOpcode())
1686 return false;
1687
1688 Value *X, *Y, *Z, *W;
1689 bool IsCommutative = false;
1692 if (match(LHS, m_BinOp(m_Value(X), m_Value(Y))) &&
1693 match(RHS, m_BinOp(m_Value(Z), m_Value(W)))) {
1694 auto *BO = cast<BinaryOperator>(LHS);
1695 // Don't introduce poison into div/rem.
1696 if (llvm::is_contained(OldMask, PoisonMaskElem) && BO->isIntDivRem())
1697 return false;
1698 IsCommutative = BinaryOperator::isCommutative(BO->getOpcode());
1699 } else if (match(LHS, m_Cmp(PredLHS, m_Value(X), m_Value(Y))) &&
1700 match(RHS, m_Cmp(PredRHS, m_Value(Z), m_Value(W))) &&
1701 (CmpInst::Predicate)PredLHS == (CmpInst::Predicate)PredRHS) {
1702 IsCommutative = cast<CmpInst>(LHS)->isCommutative();
1703 } else
1704 return false;
1705
1706 auto *ShuffleDstTy = dyn_cast<FixedVectorType>(I.getType());
1707 auto *BinResTy = dyn_cast<FixedVectorType>(LHS->getType());
1708 auto *BinOpTy = dyn_cast<FixedVectorType>(X->getType());
1709 if (!ShuffleDstTy || !BinResTy || !BinOpTy || X->getType() != Z->getType())
1710 return false;
1711
1712 unsigned NumSrcElts = BinOpTy->getNumElements();
1713
1714 // If we have something like "add X, Y" and "add Z, X", swap ops to match.
1715 if (IsCommutative && X != Z && Y != W && (X == W || Y == Z))
1716 std::swap(X, Y);
1717
1718 auto ConvertToUnary = [NumSrcElts](int &M) {
1719 if (M >= (int)NumSrcElts)
1720 M -= NumSrcElts;
1721 };
1722
1723 SmallVector<int> NewMask0(OldMask);
1725 if (X == Z) {
1726 llvm::for_each(NewMask0, ConvertToUnary);
1728 Z = PoisonValue::get(BinOpTy);
1729 }
1730
1731 SmallVector<int> NewMask1(OldMask);
1733 if (Y == W) {
1734 llvm::for_each(NewMask1, ConvertToUnary);
1736 W = PoisonValue::get(BinOpTy);
1737 }
1738
1739 // Try to replace a binop with a shuffle if the shuffle is not costly.
1740 InstructionCost OldCost =
1744 OldMask, CostKind, 0, nullptr, {LHS, RHS}, &I);
1745
1746 // Handle shuffle(binop(shuffle(x),y),binop(z,shuffle(w))) style patterns
1747 // where one use shuffles have gotten split across the binop/cmp. These
1748 // often allow a major reduction in total cost that wouldn't happen as
1749 // individual folds.
1750 auto MergeInner = [&](Value *&Op, int Offset, MutableArrayRef<int> Mask,
1751 TTI::TargetCostKind CostKind) -> bool {
1752 Value *InnerOp;
1753 ArrayRef<int> InnerMask;
1754 if (match(Op, m_OneUse(m_Shuffle(m_Value(InnerOp), m_Undef(),
1755 m_Mask(InnerMask)))) &&
1756 InnerOp->getType() == Op->getType() &&
1757 all_of(InnerMask,
1758 [NumSrcElts](int M) { return M < (int)NumSrcElts; })) {
1759 for (int &M : Mask)
1760 if (Offset <= M && M < (int)(Offset + NumSrcElts)) {
1761 M = InnerMask[M - Offset];
1762 M = 0 <= M ? M + Offset : M;
1763 }
1764 OldCost += TTI.getInstructionCost(cast<Instruction>(Op), CostKind);
1765 Op = InnerOp;
1766 return true;
1767 }
1768 return false;
1769 };
1770 bool ReducedInstCount = false;
1771 ReducedInstCount |= MergeInner(X, 0, NewMask0, CostKind);
1772 ReducedInstCount |= MergeInner(Y, 0, NewMask1, CostKind);
1773 ReducedInstCount |= MergeInner(Z, NumSrcElts, NewMask0, CostKind);
1774 ReducedInstCount |= MergeInner(W, NumSrcElts, NewMask1, CostKind);
1775
1776 InstructionCost NewCost =
1777 TTI.getShuffleCost(SK0, BinOpTy, NewMask0, CostKind, 0, nullptr, {X, Z}) +
1778 TTI.getShuffleCost(SK1, BinOpTy, NewMask1, CostKind, 0, nullptr, {Y, W});
1779
1780 if (PredLHS == CmpInst::BAD_ICMP_PREDICATE) {
1781 NewCost +=
1782 TTI.getArithmeticInstrCost(LHS->getOpcode(), ShuffleDstTy, CostKind);
1783 } else {
1784 auto *ShuffleCmpTy =
1785 FixedVectorType::get(BinOpTy->getElementType(), ShuffleDstTy);
1786 NewCost += TTI.getCmpSelInstrCost(LHS->getOpcode(), ShuffleCmpTy,
1787 ShuffleDstTy, PredLHS, CostKind);
1788 }
1789
1790 LLVM_DEBUG(dbgs() << "Found a shuffle feeding two binops: " << I
1791 << "\n OldCost: " << OldCost << " vs NewCost: " << NewCost
1792 << "\n");
1793
1794 // If either shuffle will constant fold away, then fold for the same cost as
1795 // we will reduce the instruction count.
1796 ReducedInstCount |= (isa<Constant>(X) && isa<Constant>(Z)) ||
1797 (isa<Constant>(Y) && isa<Constant>(W));
1798 if (ReducedInstCount ? (NewCost > OldCost) : (NewCost >= OldCost))
1799 return false;
1800
1801 Value *Shuf0 = Builder.CreateShuffleVector(X, Z, NewMask0);
1802 Value *Shuf1 = Builder.CreateShuffleVector(Y, W, NewMask1);
1803 Value *NewBO = PredLHS == CmpInst::BAD_ICMP_PREDICATE
1804 ? Builder.CreateBinOp(
1805 cast<BinaryOperator>(LHS)->getOpcode(), Shuf0, Shuf1)
1806 : Builder.CreateCmp(PredLHS, Shuf0, Shuf1);
1807
1808 // Intersect flags from the old binops.
1809 if (auto *NewInst = dyn_cast<Instruction>(NewBO)) {
1810 NewInst->copyIRFlags(LHS);
1811 NewInst->andIRFlags(RHS);
1812 }
1813
1814 Worklist.pushValue(Shuf0);
1815 Worklist.pushValue(Shuf1);
1816 replaceValue(I, *NewBO);
1817 return true;
1818}
1819
1820/// Try to convert "shuffle (castop), (castop)" with a shared castop operand
1821/// into "castop (shuffle)".
1822bool VectorCombine::foldShuffleOfCastops(Instruction &I) {
1823 Value *V0, *V1;
1824 ArrayRef<int> OldMask;
1825 if (!match(&I, m_Shuffle(m_Value(V0), m_Value(V1), m_Mask(OldMask))))
1826 return false;
1827
1828 auto *C0 = dyn_cast<CastInst>(V0);
1829 auto *C1 = dyn_cast<CastInst>(V1);
1830 if (!C0 || !C1)
1831 return false;
1832
1833 Instruction::CastOps Opcode = C0->getOpcode();
1834 if (C0->getSrcTy() != C1->getSrcTy())
1835 return false;
1836
1837 // Handle shuffle(zext_nneg(x), sext(y)) -> sext(shuffle(x,y)) folds.
1838 if (Opcode != C1->getOpcode()) {
1839 if (match(C0, m_SExtLike(m_Value())) && match(C1, m_SExtLike(m_Value())))
1840 Opcode = Instruction::SExt;
1841 else
1842 return false;
1843 }
1844
1845 auto *ShuffleDstTy = dyn_cast<FixedVectorType>(I.getType());
1846 auto *CastDstTy = dyn_cast<FixedVectorType>(C0->getDestTy());
1847 auto *CastSrcTy = dyn_cast<FixedVectorType>(C0->getSrcTy());
1848 if (!ShuffleDstTy || !CastDstTy || !CastSrcTy)
1849 return false;
1850
1851 unsigned NumSrcElts = CastSrcTy->getNumElements();
1852 unsigned NumDstElts = CastDstTy->getNumElements();
1853 assert((NumDstElts == NumSrcElts || Opcode == Instruction::BitCast) &&
1854 "Only bitcasts expected to alter src/dst element counts");
1855
1856 // Check for bitcasting of unscalable vector types.
1857 // e.g. <32 x i40> -> <40 x i32>
1858 if (NumDstElts != NumSrcElts && (NumSrcElts % NumDstElts) != 0 &&
1859 (NumDstElts % NumSrcElts) != 0)
1860 return false;
1861
1862 SmallVector<int, 16> NewMask;
1863 if (NumSrcElts >= NumDstElts) {
1864 // The bitcast is from wide to narrow/equal elements. The shuffle mask can
1865 // always be expanded to the equivalent form choosing narrower elements.
1866 assert(NumSrcElts % NumDstElts == 0 && "Unexpected shuffle mask");
1867 unsigned ScaleFactor = NumSrcElts / NumDstElts;
1868 narrowShuffleMaskElts(ScaleFactor, OldMask, NewMask);
1869 } else {
1870 // The bitcast is from narrow elements to wide elements. The shuffle mask
1871 // must choose consecutive elements to allow casting first.
1872 assert(NumDstElts % NumSrcElts == 0 && "Unexpected shuffle mask");
1873 unsigned ScaleFactor = NumDstElts / NumSrcElts;
1874 if (!widenShuffleMaskElts(ScaleFactor, OldMask, NewMask))
1875 return false;
1876 }
1877
1878 auto *NewShuffleDstTy =
1879 FixedVectorType::get(CastSrcTy->getScalarType(), NewMask.size());
1880
1881 // Try to replace a castop with a shuffle if the shuffle is not costly.
1882 InstructionCost CostC0 =
1883 TTI.getCastInstrCost(C0->getOpcode(), CastDstTy, CastSrcTy,
1885 InstructionCost CostC1 =
1886 TTI.getCastInstrCost(C1->getOpcode(), CastDstTy, CastSrcTy,
1888 InstructionCost OldCost = CostC0 + CostC1;
1889 OldCost +=
1891 OldMask, CostKind, 0, nullptr, {}, &I);
1892
1894 TargetTransformInfo::SK_PermuteTwoSrc, CastSrcTy, NewMask, CostKind);
1895 NewCost += TTI.getCastInstrCost(Opcode, ShuffleDstTy, NewShuffleDstTy,
1897 if (!C0->hasOneUse())
1898 NewCost += CostC0;
1899 if (!C1->hasOneUse())
1900 NewCost += CostC1;
1901
1902 LLVM_DEBUG(dbgs() << "Found a shuffle feeding two casts: " << I
1903 << "\n OldCost: " << OldCost << " vs NewCost: " << NewCost
1904 << "\n");
1905 if (NewCost > OldCost)
1906 return false;
1907
1908 Value *Shuf = Builder.CreateShuffleVector(C0->getOperand(0),
1909 C1->getOperand(0), NewMask);
1910 Value *Cast = Builder.CreateCast(Opcode, Shuf, ShuffleDstTy);
1911
1912 // Intersect flags from the old casts.
1913 if (auto *NewInst = dyn_cast<Instruction>(Cast)) {
1914 NewInst->copyIRFlags(C0);
1915 NewInst->andIRFlags(C1);
1916 }
1917
1918 Worklist.pushValue(Shuf);
1919 replaceValue(I, *Cast);
1920 return true;
1921}
1922
1923/// Try to convert any of:
1924/// "shuffle (shuffle x, y), (shuffle y, x)"
1925/// "shuffle (shuffle x, undef), (shuffle y, undef)"
1926/// "shuffle (shuffle x, undef), y"
1927/// "shuffle x, (shuffle y, undef)"
1928/// into "shuffle x, y".
1929bool VectorCombine::foldShuffleOfShuffles(Instruction &I) {
1930 ArrayRef<int> OuterMask;
1931 Value *OuterV0, *OuterV1;
1932 if (!match(&I,
1933 m_Shuffle(m_Value(OuterV0), m_Value(OuterV1), m_Mask(OuterMask))))
1934 return false;
1935
1936 ArrayRef<int> InnerMask0, InnerMask1;
1937 Value *X0, *X1, *Y0, *Y1;
1938 bool Match0 =
1939 match(OuterV0, m_Shuffle(m_Value(X0), m_Value(Y0), m_Mask(InnerMask0)));
1940 bool Match1 =
1941 match(OuterV1, m_Shuffle(m_Value(X1), m_Value(Y1), m_Mask(InnerMask1)));
1942 if (!Match0 && !Match1)
1943 return false;
1944
1945 X0 = Match0 ? X0 : OuterV0;
1946 Y0 = Match0 ? Y0 : OuterV0;
1947 X1 = Match1 ? X1 : OuterV1;
1948 Y1 = Match1 ? Y1 : OuterV1;
1949 auto *ShuffleDstTy = dyn_cast<FixedVectorType>(I.getType());
1950 auto *ShuffleSrcTy = dyn_cast<FixedVectorType>(X0->getType());
1951 auto *ShuffleImmTy = dyn_cast<FixedVectorType>(OuterV0->getType());
1952 if (!ShuffleDstTy || !ShuffleSrcTy || !ShuffleImmTy ||
1953 X0->getType() != X1->getType())
1954 return false;
1955
1956 unsigned NumSrcElts = ShuffleSrcTy->getNumElements();
1957 unsigned NumImmElts = ShuffleImmTy->getNumElements();
1958
1959 // Attempt to merge shuffles, matching upto 2 source operands.
1960 // Replace index to a poison arg with PoisonMaskElem.
1961 // Bail if either inner masks reference an undef arg.
1962 SmallVector<int, 16> NewMask(OuterMask);
1963 Value *NewX = nullptr, *NewY = nullptr;
1964 for (int &M : NewMask) {
1965 Value *Src = nullptr;
1966 if (0 <= M && M < (int)NumImmElts) {
1967 Src = OuterV0;
1968 if (Match0) {
1969 M = InnerMask0[M];
1970 Src = M >= (int)NumSrcElts ? Y0 : X0;
1971 M = M >= (int)NumSrcElts ? (M - NumSrcElts) : M;
1972 }
1973 } else if (M >= (int)NumImmElts) {
1974 Src = OuterV1;
1975 M -= NumImmElts;
1976 if (Match1) {
1977 M = InnerMask1[M];
1978 Src = M >= (int)NumSrcElts ? Y1 : X1;
1979 M = M >= (int)NumSrcElts ? (M - NumSrcElts) : M;
1980 }
1981 }
1982 if (Src && M != PoisonMaskElem) {
1983 assert(0 <= M && M < (int)NumSrcElts && "Unexpected shuffle mask index");
1984 if (isa<UndefValue>(Src)) {
1985 // We've referenced an undef element - if its poison, update the shuffle
1986 // mask, else bail.
1987 if (!isa<PoisonValue>(Src))
1988 return false;
1989 M = PoisonMaskElem;
1990 continue;
1991 }
1992 if (!NewX || NewX == Src) {
1993 NewX = Src;
1994 continue;
1995 }
1996 if (!NewY || NewY == Src) {
1997 M += NumSrcElts;
1998 NewY = Src;
1999 continue;
2000 }
2001 return false;
2002 }
2003 }
2004
2005 if (!NewX)
2006 return PoisonValue::get(ShuffleDstTy);
2007 if (!NewY)
2008 NewY = PoisonValue::get(ShuffleSrcTy);
2009
2010 // Have we folded to an Identity shuffle?
2011 if (ShuffleVectorInst::isIdentityMask(NewMask, NumSrcElts)) {
2012 replaceValue(I, *NewX);
2013 return true;
2014 }
2015
2016 // Try to merge the shuffles if the new shuffle is not costly.
2017 InstructionCost InnerCost0 = 0;
2018 if (Match0)
2019 InnerCost0 = TTI.getInstructionCost(cast<Instruction>(OuterV0), CostKind);
2020
2021 InstructionCost InnerCost1 = 0;
2022 if (Match1)
2023 InnerCost1 = TTI.getInstructionCost(cast<Instruction>(OuterV1), CostKind);
2024
2026 TargetTransformInfo::SK_PermuteTwoSrc, ShuffleImmTy, OuterMask, CostKind,
2027 0, nullptr, {OuterV0, OuterV1}, &I);
2028
2029 InstructionCost OldCost = InnerCost0 + InnerCost1 + OuterCost;
2030
2031 bool IsUnary = all_of(NewMask, [&](int M) { return M < (int)NumSrcElts; });
2036 SK, ShuffleSrcTy, NewMask, CostKind, 0, nullptr, {NewX, NewY});
2037 if (!OuterV0->hasOneUse())
2038 NewCost += InnerCost0;
2039 if (!OuterV1->hasOneUse())
2040 NewCost += InnerCost1;
2041
2042 LLVM_DEBUG(dbgs() << "Found a shuffle feeding two shuffles: " << I
2043 << "\n OldCost: " << OldCost << " vs NewCost: " << NewCost
2044 << "\n");
2045 if (NewCost > OldCost)
2046 return false;
2047
2048 Value *Shuf = Builder.CreateShuffleVector(NewX, NewY, NewMask);
2049 replaceValue(I, *Shuf);
2050 return true;
2051}
2052
2053/// Try to convert
2054/// "shuffle (intrinsic), (intrinsic)" into "intrinsic (shuffle), (shuffle)".
2055bool VectorCombine::foldShuffleOfIntrinsics(Instruction &I) {
2056 Value *V0, *V1;
2057 ArrayRef<int> OldMask;
2058 if (!match(&I, m_Shuffle(m_OneUse(m_Value(V0)), m_OneUse(m_Value(V1)),
2059 m_Mask(OldMask))))
2060 return false;
2061
2062 auto *II0 = dyn_cast<IntrinsicInst>(V0);
2063 auto *II1 = dyn_cast<IntrinsicInst>(V1);
2064 if (!II0 || !II1)
2065 return false;
2066
2067 Intrinsic::ID IID = II0->getIntrinsicID();
2068 if (IID != II1->getIntrinsicID())
2069 return false;
2070
2071 auto *ShuffleDstTy = dyn_cast<FixedVectorType>(I.getType());
2072 auto *II0Ty = dyn_cast<FixedVectorType>(II0->getType());
2073 if (!ShuffleDstTy || !II0Ty)
2074 return false;
2075
2076 if (!isTriviallyVectorizable(IID))
2077 return false;
2078
2079 for (unsigned I = 0, E = II0->arg_size(); I != E; ++I)
2081 II0->getArgOperand(I) != II1->getArgOperand(I))
2082 return false;
2083
2084 InstructionCost OldCost =
2088 CostKind, 0, nullptr, {II0, II1}, &I);
2089
2090 SmallVector<Type *> NewArgsTy;
2091 InstructionCost NewCost = 0;
2092 for (unsigned I = 0, E = II0->arg_size(); I != E; ++I)
2094 NewArgsTy.push_back(II0->getArgOperand(I)->getType());
2095 } else {
2096 auto *VecTy = cast<FixedVectorType>(II0->getArgOperand(I)->getType());
2097 NewArgsTy.push_back(FixedVectorType::get(VecTy->getElementType(),
2098 VecTy->getNumElements() * 2));
2100 VecTy, OldMask, CostKind);
2101 }
2102 IntrinsicCostAttributes NewAttr(IID, ShuffleDstTy, NewArgsTy);
2103 NewCost += TTI.getIntrinsicInstrCost(NewAttr, CostKind);
2104
2105 LLVM_DEBUG(dbgs() << "Found a shuffle feeding two intrinsics: " << I
2106 << "\n OldCost: " << OldCost << " vs NewCost: " << NewCost
2107 << "\n");
2108
2109 if (NewCost > OldCost)
2110 return false;
2111
2112 SmallVector<Value *> NewArgs;
2113 for (unsigned I = 0, E = II0->arg_size(); I != E; ++I)
2115 NewArgs.push_back(II0->getArgOperand(I));
2116 } else {
2117 Value *Shuf = Builder.CreateShuffleVector(II0->getArgOperand(I),
2118 II1->getArgOperand(I), OldMask);
2119 NewArgs.push_back(Shuf);
2120 Worklist.pushValue(Shuf);
2121 }
2122 Value *NewIntrinsic = Builder.CreateIntrinsic(ShuffleDstTy, IID, NewArgs);
2123
2124 // Intersect flags from the old intrinsics.
2125 if (auto *NewInst = dyn_cast<Instruction>(NewIntrinsic)) {
2126 NewInst->copyIRFlags(II0);
2127 NewInst->andIRFlags(II1);
2128 }
2129
2130 replaceValue(I, *NewIntrinsic);
2131 return true;
2132}
2133
2134using InstLane = std::pair<Use *, int>;
2135
2136static InstLane lookThroughShuffles(Use *U, int Lane) {
2137 while (auto *SV = dyn_cast<ShuffleVectorInst>(U->get())) {
2138 unsigned NumElts =
2139 cast<FixedVectorType>(SV->getOperand(0)->getType())->getNumElements();
2140 int M = SV->getMaskValue(Lane);
2141 if (M < 0)
2142 return {nullptr, PoisonMaskElem};
2143 if (static_cast<unsigned>(M) < NumElts) {
2144 U = &SV->getOperandUse(0);
2145 Lane = M;
2146 } else {
2147 U = &SV->getOperandUse(1);
2148 Lane = M - NumElts;
2149 }
2150 }
2151 return InstLane{U, Lane};
2152}
2153
2157 for (InstLane IL : Item) {
2158 auto [U, Lane] = IL;
2159 InstLane OpLane =
2160 U ? lookThroughShuffles(&cast<Instruction>(U->get())->getOperandUse(Op),
2161 Lane)
2162 : InstLane{nullptr, PoisonMaskElem};
2163 NItem.emplace_back(OpLane);
2164 }
2165 return NItem;
2166}
2167
2168/// Detect concat of multiple values into a vector
2170 const TargetTransformInfo &TTI) {
2171 auto *Ty = cast<FixedVectorType>(Item.front().first->get()->getType());
2172 unsigned NumElts = Ty->getNumElements();
2173 if (Item.size() == NumElts || NumElts == 1 || Item.size() % NumElts != 0)
2174 return false;
2175
2176 // Check that the concat is free, usually meaning that the type will be split
2177 // during legalization.
2178 SmallVector<int, 16> ConcatMask(NumElts * 2);
2179 std::iota(ConcatMask.begin(), ConcatMask.end(), 0);
2180 if (TTI.getShuffleCost(TTI::SK_PermuteTwoSrc, Ty, ConcatMask, CostKind) != 0)
2181 return false;
2182
2183 unsigned NumSlices = Item.size() / NumElts;
2184 // Currently we generate a tree of shuffles for the concats, which limits us
2185 // to a power2.
2186 if (!isPowerOf2_32(NumSlices))
2187 return false;
2188 for (unsigned Slice = 0; Slice < NumSlices; ++Slice) {
2189 Use *SliceV = Item[Slice * NumElts].first;
2190 if (!SliceV || SliceV->get()->getType() != Ty)
2191 return false;
2192 for (unsigned Elt = 0; Elt < NumElts; ++Elt) {
2193 auto [V, Lane] = Item[Slice * NumElts + Elt];
2194 if (Lane != static_cast<int>(Elt) || SliceV->get() != V->get())
2195 return false;
2196 }
2197 }
2198 return true;
2199}
2200
2202 const SmallPtrSet<Use *, 4> &IdentityLeafs,
2203 const SmallPtrSet<Use *, 4> &SplatLeafs,
2204 const SmallPtrSet<Use *, 4> &ConcatLeafs,
2205 IRBuilder<> &Builder,
2206 const TargetTransformInfo *TTI) {
2207 auto [FrontU, FrontLane] = Item.front();
2208
2209 if (IdentityLeafs.contains(FrontU)) {
2210 return FrontU->get();
2211 }
2212 if (SplatLeafs.contains(FrontU)) {
2213 SmallVector<int, 16> Mask(Ty->getNumElements(), FrontLane);
2214 return Builder.CreateShuffleVector(FrontU->get(), Mask);
2215 }
2216 if (ConcatLeafs.contains(FrontU)) {
2217 unsigned NumElts =
2218 cast<FixedVectorType>(FrontU->get()->getType())->getNumElements();
2219 SmallVector<Value *> Values(Item.size() / NumElts, nullptr);
2220 for (unsigned S = 0; S < Values.size(); ++S)
2221 Values[S] = Item[S * NumElts].first->get();
2222
2223 while (Values.size() > 1) {
2224 NumElts *= 2;
2225 SmallVector<int, 16> Mask(NumElts, 0);
2226 std::iota(Mask.begin(), Mask.end(), 0);
2227 SmallVector<Value *> NewValues(Values.size() / 2, nullptr);
2228 for (unsigned S = 0; S < NewValues.size(); ++S)
2229 NewValues[S] =
2230 Builder.CreateShuffleVector(Values[S * 2], Values[S * 2 + 1], Mask);
2231 Values = NewValues;
2232 }
2233 return Values[0];
2234 }
2235
2236 auto *I = cast<Instruction>(FrontU->get());
2237 auto *II = dyn_cast<IntrinsicInst>(I);
2238 unsigned NumOps = I->getNumOperands() - (II ? 1 : 0);
2239 SmallVector<Value *> Ops(NumOps);
2240 for (unsigned Idx = 0; Idx < NumOps; Idx++) {
2241 if (II &&
2242 isVectorIntrinsicWithScalarOpAtArg(II->getIntrinsicID(), Idx, TTI)) {
2243 Ops[Idx] = II->getOperand(Idx);
2244 continue;
2245 }
2247 Ty, IdentityLeafs, SplatLeafs, ConcatLeafs,
2248 Builder, TTI);
2249 }
2250
2251 SmallVector<Value *, 8> ValueList;
2252 for (const auto &Lane : Item)
2253 if (Lane.first)
2254 ValueList.push_back(Lane.first->get());
2255
2256 Type *DstTy =
2257 FixedVectorType::get(I->getType()->getScalarType(), Ty->getNumElements());
2258 if (auto *BI = dyn_cast<BinaryOperator>(I)) {
2259 auto *Value = Builder.CreateBinOp((Instruction::BinaryOps)BI->getOpcode(),
2260 Ops[0], Ops[1]);
2261 propagateIRFlags(Value, ValueList);
2262 return Value;
2263 }
2264 if (auto *CI = dyn_cast<CmpInst>(I)) {
2265 auto *Value = Builder.CreateCmp(CI->getPredicate(), Ops[0], Ops[1]);
2266 propagateIRFlags(Value, ValueList);
2267 return Value;
2268 }
2269 if (auto *SI = dyn_cast<SelectInst>(I)) {
2270 auto *Value = Builder.CreateSelect(Ops[0], Ops[1], Ops[2], "", SI);
2271 propagateIRFlags(Value, ValueList);
2272 return Value;
2273 }
2274 if (auto *CI = dyn_cast<CastInst>(I)) {
2275 auto *Value = Builder.CreateCast((Instruction::CastOps)CI->getOpcode(),
2276 Ops[0], DstTy);
2277 propagateIRFlags(Value, ValueList);
2278 return Value;
2279 }
2280 if (II) {
2281 auto *Value = Builder.CreateIntrinsic(DstTy, II->getIntrinsicID(), Ops);
2282 propagateIRFlags(Value, ValueList);
2283 return Value;
2284 }
2285 assert(isa<UnaryInstruction>(I) && "Unexpected instruction type in Generate");
2286 auto *Value =
2287 Builder.CreateUnOp((Instruction::UnaryOps)I->getOpcode(), Ops[0]);
2288 propagateIRFlags(Value, ValueList);
2289 return Value;
2290}
2291
2292// Starting from a shuffle, look up through operands tracking the shuffled index
2293// of each lane. If we can simplify away the shuffles to identities then
2294// do so.
2295bool VectorCombine::foldShuffleToIdentity(Instruction &I) {
2296 auto *Ty = dyn_cast<FixedVectorType>(I.getType());
2297 if (!Ty || I.use_empty())
2298 return false;
2299
2300 SmallVector<InstLane> Start(Ty->getNumElements());
2301 for (unsigned M = 0, E = Ty->getNumElements(); M < E; ++M)
2302 Start[M] = lookThroughShuffles(&*I.use_begin(), M);
2303
2305 Worklist.push_back(Start);
2306 SmallPtrSet<Use *, 4> IdentityLeafs, SplatLeafs, ConcatLeafs;
2307 unsigned NumVisited = 0;
2308
2309 while (!Worklist.empty()) {
2310 if (++NumVisited > MaxInstrsToScan)
2311 return false;
2312
2313 SmallVector<InstLane> Item = Worklist.pop_back_val();
2314 auto [FrontU, FrontLane] = Item.front();
2315
2316 // If we found an undef first lane then bail out to keep things simple.
2317 if (!FrontU)
2318 return false;
2319
2320 // Helper to peek through bitcasts to the same value.
2321 auto IsEquiv = [&](Value *X, Value *Y) {
2322 return X->getType() == Y->getType() &&
2324 };
2325
2326 // Look for an identity value.
2327 if (FrontLane == 0 &&
2328 cast<FixedVectorType>(FrontU->get()->getType())->getNumElements() ==
2329 Ty->getNumElements() &&
2330 all_of(drop_begin(enumerate(Item)), [IsEquiv, Item](const auto &E) {
2331 Value *FrontV = Item.front().first->get();
2332 return !E.value().first || (IsEquiv(E.value().first->get(), FrontV) &&
2333 E.value().second == (int)E.index());
2334 })) {
2335 IdentityLeafs.insert(FrontU);
2336 continue;
2337 }
2338 // Look for constants, for the moment only supporting constant splats.
2339 if (auto *C = dyn_cast<Constant>(FrontU);
2340 C && C->getSplatValue() &&
2341 all_of(drop_begin(Item), [Item](InstLane &IL) {
2342 Value *FrontV = Item.front().first->get();
2343 Use *U = IL.first;
2344 return !U || (isa<Constant>(U->get()) &&
2345 cast<Constant>(U->get())->getSplatValue() ==
2346 cast<Constant>(FrontV)->getSplatValue());
2347 })) {
2348 SplatLeafs.insert(FrontU);
2349 continue;
2350 }
2351 // Look for a splat value.
2352 if (all_of(drop_begin(Item), [Item](InstLane &IL) {
2353 auto [FrontU, FrontLane] = Item.front();
2354 auto [U, Lane] = IL;
2355 return !U || (U->get() == FrontU->get() && Lane == FrontLane);
2356 })) {
2357 SplatLeafs.insert(FrontU);
2358 continue;
2359 }
2360
2361 // We need each element to be the same type of value, and check that each
2362 // element has a single use.
2363 auto CheckLaneIsEquivalentToFirst = [Item](InstLane IL) {
2364 Value *FrontV = Item.front().first->get();
2365 if (!IL.first)
2366 return true;
2367 Value *V = IL.first->get();
2368 if (auto *I = dyn_cast<Instruction>(V); I && !I->hasOneUse())
2369 return false;
2370 if (V->getValueID() != FrontV->getValueID())
2371 return false;
2372 if (auto *CI = dyn_cast<CmpInst>(V))
2373 if (CI->getPredicate() != cast<CmpInst>(FrontV)->getPredicate())
2374 return false;
2375 if (auto *CI = dyn_cast<CastInst>(V))
2376 if (CI->getSrcTy()->getScalarType() !=
2377 cast<CastInst>(FrontV)->getSrcTy()->getScalarType())
2378 return false;
2379 if (auto *SI = dyn_cast<SelectInst>(V))
2380 if (!isa<VectorType>(SI->getOperand(0)->getType()) ||
2381 SI->getOperand(0)->getType() !=
2382 cast<SelectInst>(FrontV)->getOperand(0)->getType())
2383 return false;
2384 if (isa<CallInst>(V) && !isa<IntrinsicInst>(V))
2385 return false;
2386 auto *II = dyn_cast<IntrinsicInst>(V);
2387 return !II || (isa<IntrinsicInst>(FrontV) &&
2388 II->getIntrinsicID() ==
2389 cast<IntrinsicInst>(FrontV)->getIntrinsicID() &&
2390 !II->hasOperandBundles());
2391 };
2392 if (all_of(drop_begin(Item), CheckLaneIsEquivalentToFirst)) {
2393 // Check the operator is one that we support.
2394 if (isa<BinaryOperator, CmpInst>(FrontU)) {
2395 // We exclude div/rem in case they hit UB from poison lanes.
2396 if (auto *BO = dyn_cast<BinaryOperator>(FrontU);
2397 BO && BO->isIntDivRem())
2398 return false;
2401 continue;
2403 FPToUIInst, SIToFPInst, UIToFPInst>(FrontU)) {
2405 continue;
2406 } else if (auto *BitCast = dyn_cast<BitCastInst>(FrontU)) {
2407 // TODO: Handle vector widening/narrowing bitcasts.
2408 auto *DstTy = dyn_cast<FixedVectorType>(BitCast->getDestTy());
2409 auto *SrcTy = dyn_cast<FixedVectorType>(BitCast->getSrcTy());
2410 if (DstTy && SrcTy &&
2411 SrcTy->getNumElements() == DstTy->getNumElements()) {
2413 continue;
2414 }
2415 } else if (isa<SelectInst>(FrontU)) {
2419 continue;
2420 } else if (auto *II = dyn_cast<IntrinsicInst>(FrontU);
2421 II && isTriviallyVectorizable(II->getIntrinsicID()) &&
2422 !II->hasOperandBundles()) {
2423 for (unsigned Op = 0, E = II->getNumOperands() - 1; Op < E; Op++) {
2424 if (isVectorIntrinsicWithScalarOpAtArg(II->getIntrinsicID(), Op,
2425 &TTI)) {
2426 if (!all_of(drop_begin(Item), [Item, Op](InstLane &IL) {
2427 Value *FrontV = Item.front().first->get();
2428 Use *U = IL.first;
2429 return !U || (cast<Instruction>(U->get())->getOperand(Op) ==
2430 cast<Instruction>(FrontV)->getOperand(Op));
2431 }))
2432 return false;
2433 continue;
2434 }
2436 }
2437 continue;
2438 }
2439 }
2440
2441 if (isFreeConcat(Item, CostKind, TTI)) {
2442 ConcatLeafs.insert(FrontU);
2443 continue;
2444 }
2445
2446 return false;
2447 }
2448
2449 if (NumVisited <= 1)
2450 return false;
2451
2452 LLVM_DEBUG(dbgs() << "Found a superfluous identity shuffle: " << I << "\n");
2453
2454 // If we got this far, we know the shuffles are superfluous and can be
2455 // removed. Scan through again and generate the new tree of instructions.
2456 Builder.SetInsertPoint(&I);
2457 Value *V = generateNewInstTree(Start, Ty, IdentityLeafs, SplatLeafs,
2458 ConcatLeafs, Builder, &TTI);
2459 replaceValue(I, *V);
2460 return true;
2461}
2462
2463/// Given a commutative reduction, the order of the input lanes does not alter
2464/// the results. We can use this to remove certain shuffles feeding the
2465/// reduction, removing the need to shuffle at all.
2466bool VectorCombine::foldShuffleFromReductions(Instruction &I) {
2467 auto *II = dyn_cast<IntrinsicInst>(&I);
2468 if (!II)
2469 return false;
2470 switch (II->getIntrinsicID()) {
2471 case Intrinsic::vector_reduce_add:
2472 case Intrinsic::vector_reduce_mul:
2473 case Intrinsic::vector_reduce_and:
2474 case Intrinsic::vector_reduce_or:
2475 case Intrinsic::vector_reduce_xor:
2476 case Intrinsic::vector_reduce_smin:
2477 case Intrinsic::vector_reduce_smax:
2478 case Intrinsic::vector_reduce_umin:
2479 case Intrinsic::vector_reduce_umax:
2480 break;
2481 default:
2482 return false;
2483 }
2484
2485 // Find all the inputs when looking through operations that do not alter the
2486 // lane order (binops, for example). Currently we look for a single shuffle,
2487 // and can ignore splat values.
2488 std::queue<Value *> Worklist;
2490 ShuffleVectorInst *Shuffle = nullptr;
2491 if (auto *Op = dyn_cast<Instruction>(I.getOperand(0)))
2492 Worklist.push(Op);
2493
2494 while (!Worklist.empty()) {
2495 Value *CV = Worklist.front();
2496 Worklist.pop();
2497 if (Visited.contains(CV))
2498 continue;
2499
2500 // Splats don't change the order, so can be safely ignored.
2501 if (isSplatValue(CV))
2502 continue;
2503
2504 Visited.insert(CV);
2505
2506 if (auto *CI = dyn_cast<Instruction>(CV)) {
2507 if (CI->isBinaryOp()) {
2508 for (auto *Op : CI->operand_values())
2509 Worklist.push(Op);
2510 continue;
2511 } else if (auto *SV = dyn_cast<ShuffleVectorInst>(CI)) {
2512 if (Shuffle && Shuffle != SV)
2513 return false;
2514 Shuffle = SV;
2515 continue;
2516 }
2517 }
2518
2519 // Anything else is currently an unknown node.
2520 return false;
2521 }
2522
2523 if (!Shuffle)
2524 return false;
2525
2526 // Check all uses of the binary ops and shuffles are also included in the
2527 // lane-invariant operations (Visited should be the list of lanewise
2528 // instructions, including the shuffle that we found).
2529 for (auto *V : Visited)
2530 for (auto *U : V->users())
2531 if (!Visited.contains(U) && U != &I)
2532 return false;
2533
2535 dyn_cast<FixedVectorType>(II->getOperand(0)->getType());
2536 if (!VecType)
2537 return false;
2538 FixedVectorType *ShuffleInputType =
2539 dyn_cast<FixedVectorType>(Shuffle->getOperand(0)->getType());
2540 if (!ShuffleInputType)
2541 return false;
2542 unsigned NumInputElts = ShuffleInputType->getNumElements();
2543
2544 // Find the mask from sorting the lanes into order. This is most likely to
2545 // become a identity or concat mask. Undef elements are pushed to the end.
2546 SmallVector<int> ConcatMask;
2547 Shuffle->getShuffleMask(ConcatMask);
2548 sort(ConcatMask, [](int X, int Y) { return (unsigned)X < (unsigned)Y; });
2549 // In the case of a truncating shuffle it's possible for the mask
2550 // to have an index greater than the size of the resulting vector.
2551 // This requires special handling.
2552 bool IsTruncatingShuffle = VecType->getNumElements() < NumInputElts;
2553 bool UsesSecondVec =
2554 any_of(ConcatMask, [&](int M) { return M >= (int)NumInputElts; });
2555
2556 FixedVectorType *VecTyForCost =
2557 (UsesSecondVec && !IsTruncatingShuffle) ? VecType : ShuffleInputType;
2560 VecTyForCost, Shuffle->getShuffleMask(), CostKind);
2563 VecTyForCost, ConcatMask, CostKind);
2564
2565 LLVM_DEBUG(dbgs() << "Found a reduction feeding from a shuffle: " << *Shuffle
2566 << "\n");
2567 LLVM_DEBUG(dbgs() << " OldCost: " << OldCost << " vs NewCost: " << NewCost
2568 << "\n");
2569 if (NewCost < OldCost) {
2570 Builder.SetInsertPoint(Shuffle);
2571 Value *NewShuffle = Builder.CreateShuffleVector(
2572 Shuffle->getOperand(0), Shuffle->getOperand(1), ConcatMask);
2573 LLVM_DEBUG(dbgs() << "Created new shuffle: " << *NewShuffle << "\n");
2574 replaceValue(*Shuffle, *NewShuffle);
2575 }
2576
2577 // See if we can re-use foldSelectShuffle, getting it to reduce the size of
2578 // the shuffle into a nicer order, as it can ignore the order of the shuffles.
2579 return foldSelectShuffle(*Shuffle, true);
2580}
2581
2582/// Determine if its more efficient to fold:
2583/// reduce(trunc(x)) -> trunc(reduce(x)).
2584/// reduce(sext(x)) -> sext(reduce(x)).
2585/// reduce(zext(x)) -> zext(reduce(x)).
2586bool VectorCombine::foldCastFromReductions(Instruction &I) {
2587 auto *II = dyn_cast<IntrinsicInst>(&I);
2588 if (!II)
2589 return false;
2590
2591 bool TruncOnly = false;
2592 Intrinsic::ID IID = II->getIntrinsicID();
2593 switch (IID) {
2594 case Intrinsic::vector_reduce_add:
2595 case Intrinsic::vector_reduce_mul:
2596 TruncOnly = true;
2597 break;
2598 case Intrinsic::vector_reduce_and:
2599 case Intrinsic::vector_reduce_or:
2600 case Intrinsic::vector_reduce_xor:
2601 break;
2602 default:
2603 return false;
2604 }
2605
2606 unsigned ReductionOpc = getArithmeticReductionInstruction(IID);
2607 Value *ReductionSrc = I.getOperand(0);
2608
2609 Value *Src;
2610 if (!match(ReductionSrc, m_OneUse(m_Trunc(m_Value(Src)))) &&
2611 (TruncOnly || !match(ReductionSrc, m_OneUse(m_ZExtOrSExt(m_Value(Src))))))
2612 return false;
2613
2614 auto CastOpc =
2615 (Instruction::CastOps)cast<Instruction>(ReductionSrc)->getOpcode();
2616
2617 auto *SrcTy = cast<VectorType>(Src->getType());
2618 auto *ReductionSrcTy = cast<VectorType>(ReductionSrc->getType());
2619 Type *ResultTy = I.getType();
2620
2622 ReductionOpc, ReductionSrcTy, std::nullopt, CostKind);
2623 OldCost += TTI.getCastInstrCost(CastOpc, ReductionSrcTy, SrcTy,
2625 cast<CastInst>(ReductionSrc));
2626 InstructionCost NewCost =
2627 TTI.getArithmeticReductionCost(ReductionOpc, SrcTy, std::nullopt,
2628 CostKind) +
2629 TTI.getCastInstrCost(CastOpc, ResultTy, ReductionSrcTy->getScalarType(),
2631
2632 if (OldCost <= NewCost || !NewCost.isValid())
2633 return false;
2634
2635 Value *NewReduction = Builder.CreateIntrinsic(SrcTy->getScalarType(),
2636 II->getIntrinsicID(), {Src});
2637 Value *NewCast = Builder.CreateCast(CastOpc, NewReduction, ResultTy);
2638 replaceValue(I, *NewCast);
2639 return true;
2640}
2641
2642/// This method looks for groups of shuffles acting on binops, of the form:
2643/// %x = shuffle ...
2644/// %y = shuffle ...
2645/// %a = binop %x, %y
2646/// %b = binop %x, %y
2647/// shuffle %a, %b, selectmask
2648/// We may, especially if the shuffle is wider than legal, be able to convert
2649/// the shuffle to a form where only parts of a and b need to be computed. On
2650/// architectures with no obvious "select" shuffle, this can reduce the total
2651/// number of operations if the target reports them as cheaper.
2652bool VectorCombine::foldSelectShuffle(Instruction &I, bool FromReduction) {
2653 auto *SVI = cast<ShuffleVectorInst>(&I);
2654 auto *VT = cast<FixedVectorType>(I.getType());
2655 auto *Op0 = dyn_cast<Instruction>(SVI->getOperand(0));
2656 auto *Op1 = dyn_cast<Instruction>(SVI->getOperand(1));
2657 if (!Op0 || !Op1 || Op0 == Op1 || !Op0->isBinaryOp() || !Op1->isBinaryOp() ||
2658 VT != Op0->getType())
2659 return false;
2660
2661 auto *SVI0A = dyn_cast<Instruction>(Op0->getOperand(0));
2662 auto *SVI0B = dyn_cast<Instruction>(Op0->getOperand(1));
2663 auto *SVI1A = dyn_cast<Instruction>(Op1->getOperand(0));
2664 auto *SVI1B = dyn_cast<Instruction>(Op1->getOperand(1));
2665 SmallPtrSet<Instruction *, 4> InputShuffles({SVI0A, SVI0B, SVI1A, SVI1B});
2666 auto checkSVNonOpUses = [&](Instruction *I) {
2667 if (!I || I->getOperand(0)->getType() != VT)
2668 return true;
2669 return any_of(I->users(), [&](User *U) {
2670 return U != Op0 && U != Op1 &&
2671 !(isa<ShuffleVectorInst>(U) &&
2672 (InputShuffles.contains(cast<Instruction>(U)) ||
2673 isInstructionTriviallyDead(cast<Instruction>(U))));
2674 });
2675 };
2676 if (checkSVNonOpUses(SVI0A) || checkSVNonOpUses(SVI0B) ||
2677 checkSVNonOpUses(SVI1A) || checkSVNonOpUses(SVI1B))
2678 return false;
2679
2680 // Collect all the uses that are shuffles that we can transform together. We
2681 // may not have a single shuffle, but a group that can all be transformed
2682 // together profitably.
2684 auto collectShuffles = [&](Instruction *I) {
2685 for (auto *U : I->users()) {
2686 auto *SV = dyn_cast<ShuffleVectorInst>(U);
2687 if (!SV || SV->getType() != VT)
2688 return false;
2689 if ((SV->getOperand(0) != Op0 && SV->getOperand(0) != Op1) ||
2690 (SV->getOperand(1) != Op0 && SV->getOperand(1) != Op1))
2691 return false;
2692 if (!llvm::is_contained(Shuffles, SV))
2693 Shuffles.push_back(SV);
2694 }
2695 return true;
2696 };
2697 if (!collectShuffles(Op0) || !collectShuffles(Op1))
2698 return false;
2699 // From a reduction, we need to be processing a single shuffle, otherwise the
2700 // other uses will not be lane-invariant.
2701 if (FromReduction && Shuffles.size() > 1)
2702 return false;
2703
2704 // Add any shuffle uses for the shuffles we have found, to include them in our
2705 // cost calculations.
2706 if (!FromReduction) {
2707 for (ShuffleVectorInst *SV : Shuffles) {
2708 for (auto *U : SV->users()) {
2709 ShuffleVectorInst *SSV = dyn_cast<ShuffleVectorInst>(U);
2710 if (SSV && isa<UndefValue>(SSV->getOperand(1)) && SSV->getType() == VT)
2711 Shuffles.push_back(SSV);
2712 }
2713 }
2714 }
2715
2716 // For each of the output shuffles, we try to sort all the first vector
2717 // elements to the beginning, followed by the second array elements at the
2718 // end. If the binops are legalized to smaller vectors, this may reduce total
2719 // number of binops. We compute the ReconstructMask mask needed to convert
2720 // back to the original lane order.
2722 SmallVector<SmallVector<int>> OrigReconstructMasks;
2723 int MaxV1Elt = 0, MaxV2Elt = 0;
2724 unsigned NumElts = VT->getNumElements();
2725 for (ShuffleVectorInst *SVN : Shuffles) {
2727 SVN->getShuffleMask(Mask);
2728
2729 // Check the operands are the same as the original, or reversed (in which
2730 // case we need to commute the mask).
2731 Value *SVOp0 = SVN->getOperand(0);
2732 Value *SVOp1 = SVN->getOperand(1);
2733 if (isa<UndefValue>(SVOp1)) {
2734 auto *SSV = cast<ShuffleVectorInst>(SVOp0);
2735 SVOp0 = SSV->getOperand(0);
2736 SVOp1 = SSV->getOperand(1);
2737 for (unsigned I = 0, E = Mask.size(); I != E; I++) {
2738 if (Mask[I] >= static_cast<int>(SSV->getShuffleMask().size()))
2739 return false;
2740 Mask[I] = Mask[I] < 0 ? Mask[I] : SSV->getMaskValue(Mask[I]);
2741 }
2742 }
2743 if (SVOp0 == Op1 && SVOp1 == Op0) {
2744 std::swap(SVOp0, SVOp1);
2746 }
2747 if (SVOp0 != Op0 || SVOp1 != Op1)
2748 return false;
2749
2750 // Calculate the reconstruction mask for this shuffle, as the mask needed to
2751 // take the packed values from Op0/Op1 and reconstructing to the original
2752 // order.
2753 SmallVector<int> ReconstructMask;
2754 for (unsigned I = 0; I < Mask.size(); I++) {
2755 if (Mask[I] < 0) {
2756 ReconstructMask.push_back(-1);
2757 } else if (Mask[I] < static_cast<int>(NumElts)) {
2758 MaxV1Elt = std::max(MaxV1Elt, Mask[I]);
2759 auto It = find_if(V1, [&](const std::pair<int, int> &A) {
2760 return Mask[I] == A.first;
2761 });
2762 if (It != V1.end())
2763 ReconstructMask.push_back(It - V1.begin());
2764 else {
2765 ReconstructMask.push_back(V1.size());
2766 V1.emplace_back(Mask[I], V1.size());
2767 }
2768 } else {
2769 MaxV2Elt = std::max<int>(MaxV2Elt, Mask[I] - NumElts);
2770 auto It = find_if(V2, [&](const std::pair<int, int> &A) {
2771 return Mask[I] - static_cast<int>(NumElts) == A.first;
2772 });
2773 if (It != V2.end())
2774 ReconstructMask.push_back(NumElts + It - V2.begin());
2775 else {
2776 ReconstructMask.push_back(NumElts + V2.size());
2777 V2.emplace_back(Mask[I] - NumElts, NumElts + V2.size());
2778 }
2779 }
2780 }
2781
2782 // For reductions, we know that the lane ordering out doesn't alter the
2783 // result. In-order can help simplify the shuffle away.
2784 if (FromReduction)
2785 sort(ReconstructMask);
2786 OrigReconstructMasks.push_back(std::move(ReconstructMask));
2787 }
2788
2789 // If the Maximum element used from V1 and V2 are not larger than the new
2790 // vectors, the vectors are already packes and performing the optimization
2791 // again will likely not help any further. This also prevents us from getting
2792 // stuck in a cycle in case the costs do not also rule it out.
2793 if (V1.empty() || V2.empty() ||
2794 (MaxV1Elt == static_cast<int>(V1.size()) - 1 &&
2795 MaxV2Elt == static_cast<int>(V2.size()) - 1))
2796 return false;
2797
2798 // GetBaseMaskValue takes one of the inputs, which may either be a shuffle, a
2799 // shuffle of another shuffle, or not a shuffle (that is treated like a
2800 // identity shuffle).
2801 auto GetBaseMaskValue = [&](Instruction *I, int M) {
2802 auto *SV = dyn_cast<ShuffleVectorInst>(I);
2803 if (!SV)
2804 return M;
2805 if (isa<UndefValue>(SV->getOperand(1)))
2806 if (auto *SSV = dyn_cast<ShuffleVectorInst>(SV->getOperand(0)))
2807 if (InputShuffles.contains(SSV))
2808 return SSV->getMaskValue(SV->getMaskValue(M));
2809 return SV->getMaskValue(M);
2810 };
2811
2812 // Attempt to sort the inputs my ascending mask values to make simpler input
2813 // shuffles and push complex shuffles down to the uses. We sort on the first
2814 // of the two input shuffle orders, to try and get at least one input into a
2815 // nice order.
2816 auto SortBase = [&](Instruction *A, std::pair<int, int> X,
2817 std::pair<int, int> Y) {
2818 int MXA = GetBaseMaskValue(A, X.first);
2819 int MYA = GetBaseMaskValue(A, Y.first);
2820 return MXA < MYA;
2821 };
2822 stable_sort(V1, [&](std::pair<int, int> A, std::pair<int, int> B) {
2823 return SortBase(SVI0A, A, B);
2824 });
2825 stable_sort(V2, [&](std::pair<int, int> A, std::pair<int, int> B) {
2826 return SortBase(SVI1A, A, B);
2827 });
2828 // Calculate our ReconstructMasks from the OrigReconstructMasks and the
2829 // modified order of the input shuffles.
2830 SmallVector<SmallVector<int>> ReconstructMasks;
2831 for (const auto &Mask : OrigReconstructMasks) {
2832 SmallVector<int> ReconstructMask;
2833 for (int M : Mask) {
2834 auto FindIndex = [](const SmallVector<std::pair<int, int>> &V, int M) {
2835 auto It = find_if(V, [M](auto A) { return A.second == M; });
2836 assert(It != V.end() && "Expected all entries in Mask");
2837 return std::distance(V.begin(), It);
2838 };
2839 if (M < 0)
2840 ReconstructMask.push_back(-1);
2841 else if (M < static_cast<int>(NumElts)) {
2842 ReconstructMask.push_back(FindIndex(V1, M));
2843 } else {
2844 ReconstructMask.push_back(NumElts + FindIndex(V2, M));
2845 }
2846 }
2847 ReconstructMasks.push_back(std::move(ReconstructMask));
2848 }
2849
2850 // Calculate the masks needed for the new input shuffles, which get padded
2851 // with undef
2852 SmallVector<int> V1A, V1B, V2A, V2B;
2853 for (unsigned I = 0; I < V1.size(); I++) {
2854 V1A.push_back(GetBaseMaskValue(SVI0A, V1[I].first));
2855 V1B.push_back(GetBaseMaskValue(SVI0B, V1[I].first));
2856 }
2857 for (unsigned I = 0; I < V2.size(); I++) {
2858 V2A.push_back(GetBaseMaskValue(SVI1A, V2[I].first));
2859 V2B.push_back(GetBaseMaskValue(SVI1B, V2[I].first));
2860 }
2861 while (V1A.size() < NumElts) {
2864 }
2865 while (V2A.size() < NumElts) {
2868 }
2869
2870 auto AddShuffleCost = [&](InstructionCost C, Instruction *I) {
2871 auto *SV = dyn_cast<ShuffleVectorInst>(I);
2872 if (!SV)
2873 return C;
2874 return C + TTI.getShuffleCost(isa<UndefValue>(SV->getOperand(1))
2877 VT, SV->getShuffleMask(), CostKind);
2878 };
2879 auto AddShuffleMaskCost = [&](InstructionCost C, ArrayRef<int> Mask) {
2880 return C + TTI.getShuffleCost(TTI::SK_PermuteTwoSrc, VT, Mask, CostKind);
2881 };
2882
2883 // Get the costs of the shuffles + binops before and after with the new
2884 // shuffle masks.
2885 InstructionCost CostBefore =
2886 TTI.getArithmeticInstrCost(Op0->getOpcode(), VT, CostKind) +
2887 TTI.getArithmeticInstrCost(Op1->getOpcode(), VT, CostKind);
2888 CostBefore += std::accumulate(Shuffles.begin(), Shuffles.end(),
2889 InstructionCost(0), AddShuffleCost);
2890 CostBefore += std::accumulate(InputShuffles.begin(), InputShuffles.end(),
2891 InstructionCost(0), AddShuffleCost);
2892
2893 // The new binops will be unused for lanes past the used shuffle lengths.
2894 // These types attempt to get the correct cost for that from the target.
2895 FixedVectorType *Op0SmallVT =
2896 FixedVectorType::get(VT->getScalarType(), V1.size());
2897 FixedVectorType *Op1SmallVT =
2898 FixedVectorType::get(VT->getScalarType(), V2.size());
2899 InstructionCost CostAfter =
2900 TTI.getArithmeticInstrCost(Op0->getOpcode(), Op0SmallVT, CostKind) +
2901 TTI.getArithmeticInstrCost(Op1->getOpcode(), Op1SmallVT, CostKind);
2902 CostAfter += std::accumulate(ReconstructMasks.begin(), ReconstructMasks.end(),
2903 InstructionCost(0), AddShuffleMaskCost);
2904 std::set<SmallVector<int>> OutputShuffleMasks({V1A, V1B, V2A, V2B});
2905 CostAfter +=
2906 std::accumulate(OutputShuffleMasks.begin(), OutputShuffleMasks.end(),
2907 InstructionCost(0), AddShuffleMaskCost);
2908
2909 LLVM_DEBUG(dbgs() << "Found a binop select shuffle pattern: " << I << "\n");
2910 LLVM_DEBUG(dbgs() << " CostBefore: " << CostBefore
2911 << " vs CostAfter: " << CostAfter << "\n");
2912 if (CostBefore <= CostAfter)
2913 return false;
2914
2915 // The cost model has passed, create the new instructions.
2916 auto GetShuffleOperand = [&](Instruction *I, unsigned Op) -> Value * {
2917 auto *SV = dyn_cast<ShuffleVectorInst>(I);
2918 if (!SV)
2919 return I;
2920 if (isa<UndefValue>(SV->getOperand(1)))
2921 if (auto *SSV = dyn_cast<ShuffleVectorInst>(SV->getOperand(0)))
2922 if (InputShuffles.contains(SSV))
2923 return SSV->getOperand(Op);
2924 return SV->getOperand(Op);
2925 };
2926 Builder.SetInsertPoint(*SVI0A->getInsertionPointAfterDef());
2927 Value *NSV0A = Builder.CreateShuffleVector(GetShuffleOperand(SVI0A, 0),
2928 GetShuffleOperand(SVI0A, 1), V1A);
2929 Builder.SetInsertPoint(*SVI0B->getInsertionPointAfterDef());
2930 Value *NSV0B = Builder.CreateShuffleVector(GetShuffleOperand(SVI0B, 0),
2931 GetShuffleOperand(SVI0B, 1), V1B);
2932 Builder.SetInsertPoint(*SVI1A->getInsertionPointAfterDef());
2933 Value *NSV1A = Builder.CreateShuffleVector(GetShuffleOperand(SVI1A, 0),
2934 GetShuffleOperand(SVI1A, 1), V2A);
2935 Builder.SetInsertPoint(*SVI1B->getInsertionPointAfterDef());
2936 Value *NSV1B = Builder.CreateShuffleVector(GetShuffleOperand(SVI1B, 0),
2937 GetShuffleOperand(SVI1B, 1), V2B);
2938 Builder.SetInsertPoint(Op0);
2939 Value *NOp0 = Builder.CreateBinOp((Instruction::BinaryOps)Op0->getOpcode(),
2940 NSV0A, NSV0B);
2941 if (auto *I = dyn_cast<Instruction>(NOp0))
2942 I->copyIRFlags(Op0, true);
2943 Builder.SetInsertPoint(Op1);
2944 Value *NOp1 = Builder.CreateBinOp((Instruction::BinaryOps)Op1->getOpcode(),
2945 NSV1A, NSV1B);
2946 if (auto *I = dyn_cast<Instruction>(NOp1))
2947 I->copyIRFlags(Op1, true);
2948
2949 for (int S = 0, E = ReconstructMasks.size(); S != E; S++) {
2950 Builder.SetInsertPoint(Shuffles[S]);
2951 Value *NSV = Builder.CreateShuffleVector(NOp0, NOp1, ReconstructMasks[S]);
2952 replaceValue(*Shuffles[S], *NSV);
2953 }
2954
2955 Worklist.pushValue(NSV0A);
2956 Worklist.pushValue(NSV0B);
2957 Worklist.pushValue(NSV1A);
2958 Worklist.pushValue(NSV1B);
2959 for (auto *S : Shuffles)
2960 Worklist.add(S);
2961 return true;
2962}
2963
2964/// Check if instruction depends on ZExt and this ZExt can be moved after the
2965/// instruction. Move ZExt if it is profitable. For example:
2966/// logic(zext(x),y) -> zext(logic(x,trunc(y)))
2967/// lshr((zext(x),y) -> zext(lshr(x,trunc(y)))
2968/// Cost model calculations takes into account if zext(x) has other users and
2969/// whether it can be propagated through them too.
2970bool VectorCombine::shrinkType(Instruction &I) {
2971 Value *ZExted, *OtherOperand;
2972 if (!match(&I, m_c_BitwiseLogic(m_ZExt(m_Value(ZExted)),
2973 m_Value(OtherOperand))) &&
2974 !match(&I, m_LShr(m_ZExt(m_Value(ZExted)), m_Value(OtherOperand))))
2975 return false;
2976
2977 Value *ZExtOperand = I.getOperand(I.getOperand(0) == OtherOperand ? 1 : 0);
2978
2979 auto *BigTy = cast<FixedVectorType>(I.getType());
2980 auto *SmallTy = cast<FixedVectorType>(ZExted->getType());
2981 unsigned BW = SmallTy->getElementType()->getPrimitiveSizeInBits();
2982
2983 if (I.getOpcode() == Instruction::LShr) {
2984 // Check that the shift amount is less than the number of bits in the
2985 // smaller type. Otherwise, the smaller lshr will return a poison value.
2986 KnownBits ShAmtKB = computeKnownBits(I.getOperand(1), *DL);
2987 if (ShAmtKB.getMaxValue().uge(BW))
2988 return false;
2989 } else {
2990 // Check that the expression overall uses at most the same number of bits as
2991 // ZExted
2992 KnownBits KB = computeKnownBits(&I, *DL);
2993 if (KB.countMaxActiveBits() > BW)
2994 return false;
2995 }
2996
2997 // Calculate costs of leaving current IR as it is and moving ZExt operation
2998 // later, along with adding truncates if needed
3000 Instruction::ZExt, BigTy, SmallTy,
3001 TargetTransformInfo::CastContextHint::None, CostKind);
3002 InstructionCost CurrentCost = ZExtCost;
3003 InstructionCost ShrinkCost = 0;
3004
3005 // Calculate total cost and check that we can propagate through all ZExt users
3006 for (User *U : ZExtOperand->users()) {
3007 auto *UI = cast<Instruction>(U);
3008 if (UI == &I) {
3009 CurrentCost +=
3010 TTI.getArithmeticInstrCost(UI->getOpcode(), BigTy, CostKind);
3011 ShrinkCost +=
3012 TTI.getArithmeticInstrCost(UI->getOpcode(), SmallTy, CostKind);
3013 ShrinkCost += ZExtCost;
3014 continue;
3015 }
3016
3017 if (!Instruction::isBinaryOp(UI->getOpcode()))
3018 return false;
3019
3020 // Check if we can propagate ZExt through its other users
3021 KnownBits KB = computeKnownBits(UI, *DL);
3022 if (KB.countMaxActiveBits() > BW)
3023 return false;
3024
3025 CurrentCost += TTI.getArithmeticInstrCost(UI->getOpcode(), BigTy, CostKind);
3026 ShrinkCost +=
3027 TTI.getArithmeticInstrCost(UI->getOpcode(), SmallTy, CostKind);
3028 ShrinkCost += ZExtCost;
3029 }
3030
3031 // If the other instruction operand is not a constant, we'll need to
3032 // generate a truncate instruction. So we have to adjust cost
3033 if (!isa<Constant>(OtherOperand))
3034 ShrinkCost += TTI.getCastInstrCost(
3035 Instruction::Trunc, SmallTy, BigTy,
3036 TargetTransformInfo::CastContextHint::None, CostKind);
3037
3038 // If the cost of shrinking types and leaving the IR is the same, we'll lean
3039 // towards modifying the IR because shrinking opens opportunities for other
3040 // shrinking optimisations.
3041 if (ShrinkCost > CurrentCost)
3042 return false;
3043
3044 Builder.SetInsertPoint(&I);
3045 Value *Op0 = ZExted;
3046 Value *Op1 = Builder.CreateTrunc(OtherOperand, SmallTy);
3047 // Keep the order of operands the same
3048 if (I.getOperand(0) == OtherOperand)
3049 std::swap(Op0, Op1);
3050 Value *NewBinOp =
3051 Builder.CreateBinOp((Instruction::BinaryOps)I.getOpcode(), Op0, Op1);
3052 cast<Instruction>(NewBinOp)->copyIRFlags(&I);
3053 cast<Instruction>(NewBinOp)->copyMetadata(I);
3054 Value *NewZExtr = Builder.CreateZExt(NewBinOp, BigTy);
3055 replaceValue(I, *NewZExtr);
3056 return true;
3057}
3058
3059/// insert (DstVec, (extract SrcVec, ExtIdx), InsIdx) -->
3060/// shuffle (DstVec, SrcVec, Mask)
3061bool VectorCombine::foldInsExtVectorToShuffle(Instruction &I) {
3062 Value *DstVec, *SrcVec;
3063 uint64_t ExtIdx, InsIdx;
3064 if (!match(&I,
3065 m_InsertElt(m_Value(DstVec),
3066 m_ExtractElt(m_Value(SrcVec), m_ConstantInt(ExtIdx)),
3067 m_ConstantInt(InsIdx))))
3068 return false;
3069
3070 auto *VecTy = dyn_cast<FixedVectorType>(I.getType());
3071 if (!VecTy || SrcVec->getType() != VecTy)
3072 return false;
3073
3074 unsigned NumElts = VecTy->getNumElements();
3075 if (ExtIdx >= NumElts || InsIdx >= NumElts)
3076 return false;
3077
3078 // Insertion into poison is a cheaper single operand shuffle.
3081 if (isa<PoisonValue>(DstVec) && !isa<UndefValue>(SrcVec)) {
3083 Mask[InsIdx] = ExtIdx;
3084 std::swap(DstVec, SrcVec);
3085 } else {
3087 std::iota(Mask.begin(), Mask.end(), 0);
3088 Mask[InsIdx] = ExtIdx + NumElts;
3089 }
3090
3091 // Cost
3092 auto *Ins = cast<InsertElementInst>(&I);
3093 auto *Ext = cast<ExtractElementInst>(I.getOperand(1));
3094 InstructionCost InsCost =
3095 TTI.getVectorInstrCost(*Ins, VecTy, CostKind, InsIdx);
3096 InstructionCost ExtCost =
3097 TTI.getVectorInstrCost(*Ext, VecTy, CostKind, ExtIdx);
3098 InstructionCost OldCost = ExtCost + InsCost;
3099
3100 // Ignore 'free' identity insertion shuffle.
3101 // TODO: getShuffleCost should return TCC_Free for Identity shuffles.
3102 InstructionCost NewCost = 0;
3103 if (!ShuffleVectorInst::isIdentityMask(Mask, NumElts))
3104 NewCost += TTI.getShuffleCost(SK, VecTy, Mask, CostKind, 0, nullptr,
3105 {DstVec, SrcVec});
3106 if (!Ext->hasOneUse())
3107 NewCost += ExtCost;
3108
3109 LLVM_DEBUG(dbgs() << "Found a insert/extract shuffle-like pair: " << I
3110 << "\n OldCost: " << OldCost << " vs NewCost: " << NewCost
3111 << "\n");
3112
3113 if (OldCost < NewCost)
3114 return false;
3115
3116 // Canonicalize undef param to RHS to help further folds.
3117 if (isa<UndefValue>(DstVec) && !isa<UndefValue>(SrcVec)) {
3119 std::swap(DstVec, SrcVec);
3120 }
3121
3122 Value *Shuf = Builder.CreateShuffleVector(DstVec, SrcVec, Mask);
3123 replaceValue(I, *Shuf);
3124
3125 return true;
3126}
3127
3128/// This is the entry point for all transforms. Pass manager differences are
3129/// handled in the callers of this function.
3130bool VectorCombine::run() {
3132 return false;
3133
3134 // Don't attempt vectorization if the target does not support vectors.
3135 if (!TTI.getNumberOfRegisters(TTI.getRegisterClassForType(/*Vector*/ true)))
3136 return false;
3137
3138 LLVM_DEBUG(dbgs() << "\n\nVECTORCOMBINE on " << F.getName() << "\n");
3139
3140 bool MadeChange = false;
3141 auto FoldInst = [this, &MadeChange](Instruction &I) {
3142 Builder.SetInsertPoint(&I);
3143 bool IsVectorType = isa<VectorType>(I.getType());
3144 bool IsFixedVectorType = isa<FixedVectorType>(I.getType());
3145 auto Opcode = I.getOpcode();
3146
3147 LLVM_DEBUG(dbgs() << "VC: Visiting: " << I << '\n');
3148
3149 // These folds should be beneficial regardless of when this pass is run
3150 // in the optimization pipeline.
3151 // The type checking is for run-time efficiency. We can avoid wasting time
3152 // dispatching to folding functions if there's no chance of matching.
3153 if (IsFixedVectorType) {
3154 switch (Opcode) {
3155 case Instruction::InsertElement:
3156 MadeChange |= vectorizeLoadInsert(I);
3157 break;
3158 case Instruction::ShuffleVector:
3159 MadeChange |= widenSubvectorLoad(I);
3160 break;
3161 default:
3162 break;
3163 }
3164 }
3165
3166 // This transform works with scalable and fixed vectors
3167 // TODO: Identify and allow other scalable transforms
3168 if (IsVectorType) {
3169 MadeChange |= scalarizeBinopOrCmp(I);
3170 MadeChange |= scalarizeLoadExtract(I);
3171 MadeChange |= scalarizeVPIntrinsic(I);
3172 }
3173
3174 if (Opcode == Instruction::Store)
3175 MadeChange |= foldSingleElementStore(I);
3176
3177 // If this is an early pipeline invocation of this pass, we are done.
3178 if (TryEarlyFoldsOnly)
3179 return;
3180
3181 // Otherwise, try folds that improve codegen but may interfere with
3182 // early IR canonicalizations.
3183 // The type checking is for run-time efficiency. We can avoid wasting time
3184 // dispatching to folding functions if there's no chance of matching.
3185 if (IsFixedVectorType) {
3186 switch (Opcode) {
3187 case Instruction::InsertElement:
3188 MadeChange |= foldInsExtFNeg(I);
3189 MadeChange |= foldInsExtVectorToShuffle(I);
3190 break;
3191 case Instruction::ShuffleVector:
3192 MadeChange |= foldPermuteOfBinops(I);
3193 MadeChange |= foldShuffleOfBinops(I);
3194 MadeChange |= foldShuffleOfCastops(I);
3195 MadeChange |= foldShuffleOfShuffles(I);
3196 MadeChange |= foldShuffleOfIntrinsics(I);
3197 MadeChange |= foldSelectShuffle(I);
3198 MadeChange |= foldShuffleToIdentity(I);
3199 break;
3200 case Instruction::BitCast:
3201 MadeChange |= foldBitcastShuffle(I);
3202 break;
3203 default:
3204 MadeChange |= shrinkType(I);
3205 break;
3206 }
3207 } else {
3208 switch (Opcode) {
3209 case Instruction::Call:
3210 MadeChange |= foldShuffleFromReductions(I);
3211 MadeChange |= foldCastFromReductions(I);
3212 break;
3213 case Instruction::ICmp:
3214 case Instruction::FCmp:
3215 MadeChange |= foldExtractExtract(I);
3216 break;
3217 case Instruction::Or:
3218 MadeChange |= foldConcatOfBoolMasks(I);
3219 [[fallthrough]];
3220 default:
3221 if (Instruction::isBinaryOp(Opcode)) {
3222 MadeChange |= foldExtractExtract(I);
3223 MadeChange |= foldExtractedCmps(I);
3224 }
3225 break;
3226 }
3227 }
3228 };
3229
3230 for (BasicBlock &BB : F) {
3231 // Ignore unreachable basic blocks.
3232 if (!DT.isReachableFromEntry(&BB))
3233 continue;
3234 // Use early increment range so that we can erase instructions in loop.
3235 for (Instruction &I : make_early_inc_range(BB)) {
3236 if (I.isDebugOrPseudoInst())
3237 continue;
3238 FoldInst(I);
3239 }
3240 }
3241
3242 while (!Worklist.isEmpty()) {
3243 Instruction *I = Worklist.removeOne();
3244 if (!I)
3245 continue;
3246
3249 continue;
3250 }
3251
3252 FoldInst(*I);
3253 }
3254
3255 return MadeChange;
3256}
3257
3260 auto &AC = FAM.getResult<AssumptionAnalysis>(F);
3264 const DataLayout *DL = &F.getDataLayout();
3265 VectorCombine Combiner(F, TTI, DT, AA, AC, DL, TTI::TCK_RecipThroughput,
3266 TryEarlyFoldsOnly);
3267 if (!Combiner.run())
3268 return PreservedAnalyses::all();
3271 return PA;
3272}
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(...)
Definition: Debug.h:106
This file defines the DenseMap class.
std::optional< std::vector< StOtherPiece > > Other
Definition: ELFYAML.cpp:1315
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:1504
#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")
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:166
static SymbolRef::Type getType(const Symbol *Sym)
Definition: TapiFile.cpp:39
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 bool isFreeConcat(ArrayRef< InstLane > Item, TTI::TargetCostKind CostKind, const TargetTransformInfo &TTI)
Detect concat of multiple values into a vector.
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
static Value * generateNewInstTree(ArrayRef< InstLane > Item, FixedVectorType *Ty, const SmallPtrSet< Use *, 4 > &IdentityLeafs, const SmallPtrSet< Use *, 4 > &SplatLeafs, const SmallPtrSet< Use *, 4 > &ConcatLeafs, IRBuilder<> &Builder, const TargetTransformInfo *TTI)
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...
static constexpr int Concat[]
Value * RHS
Value * LHS
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:78
static APInt getOneBitSet(unsigned numBits, unsigned BitNo)
Return an APInt with exactly one bit set in the result.
Definition: APInt.h:239
bool uge(const APInt &RHS) const
Unsigned greater or equal comparison.
Definition: APInt.h:1221
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:253
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:410
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:171
size_t size() const
size - Get the array size.
Definition: ArrayRef.h:168
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:61
InstListType::iterator iterator
Instruction iterators...
Definition: BasicBlock.h:177
BinaryOps getOpcode() const
Definition: InstrTypes.h:370
Represents analyses that only rely on functions' control flow.
Definition: Analysis.h:72
Value * getArgOperand(unsigned i) const
Definition: InstrTypes.h:1294
iterator_range< User::op_iterator > args()
Iteration adapter for range-for loops.
Definition: InstrTypes.h:1285
static Type * makeCmpResultType(Type *opnd_type)
Create a result type for fcmp/icmp.
Definition: InstrTypes.h:988
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:673
bool isFPPredicate() const
Definition: InstrTypes.h:780
An abstraction over a floating-point predicate, and a pack of an integer predicate with samesign info...
Definition: CmpPredicate.h:22
Combiner implementation.
Definition: Combiner.h:34
static Constant * getExtractElement(Constant *Vec, Constant *Idx, Type *OnlyIfReducedTy=nullptr)
Definition: Constants.cpp:2554
This is the shared class of boolean and integer constants.
Definition: Constants.h:83
const APInt & getValue() const
Return the constant as an APInt value reference.
Definition: Constants.h:148
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:1421
This is an important base class in LLVM.
Definition: Constant.h:42
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:63
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:156
std::pair< iterator, bool > try_emplace(KeyT &&Key, Ts &&...Args)
Definition: DenseMap.h:226
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.
This class represents a cast from floating point to signed integer.
This class represents a cast from floating point to unsigned integer.
Class to represent fixed width SIMD vectors.
Definition: DerivedTypes.h:563
unsigned getNumElements() const
Definition: DerivedTypes.h:606
static FixedVectorType * getDoubleElementsVectorType(FixedVectorType *VTy)
Definition: DerivedTypes.h:598
static FixedVectorType * get(Type *ElementType, unsigned NumElts)
Definition: Type.cpp:791
Value * CreateInsertElement(Type *VecTy, Value *NewElt, Value *Idx, const Twine &Name="")
Definition: IRBuilder.h:2505
Value * CreateExtractElement(Value *Vec, Value *Idx, const Twine &Name="")
Definition: IRBuilder.h:2493
LoadInst * CreateAlignedLoad(Type *Ty, Value *Ptr, MaybeAlign Align, const char *Name)
Definition: IRBuilder.h:1809
Value * CreateVectorSplat(unsigned NumElts, Value *V, const Twine &Name="")
Return a vector value that contains.
Definition: IRBuilder.cpp:1153
Value * CreateSelect(Value *C, Value *True, Value *False, const Twine &Name="", Instruction *MDFrom=nullptr)
Definition: IRBuilder.cpp:1043
Value * CreateFreeze(Value *V, const Twine &Name="")
Definition: IRBuilder.h:2568
Value * CreateCast(Instruction::CastOps Op, Value *V, Type *DestTy, const Twine &Name="", MDNode *FPMathTag=nullptr, FMFSource FMFSource={})
Definition: IRBuilder.h:2180
Value * CreateInBoundsGEP(Type *Ty, Value *Ptr, ArrayRef< Value * > IdxList, const Twine &Name="")
Definition: IRBuilder.h:1876
Value * CreatePointerBitCastOrAddrSpaceCast(Value *V, Type *DestTy, const Twine &Name="")
Definition: IRBuilder.h:2205
ConstantInt * getInt64(uint64_t C)
Get a constant 64-bit value.
Definition: IRBuilder.h:505
Value * CreateUnOp(Instruction::UnaryOps Opc, Value *V, const Twine &Name="", MDNode *FPMathTag=nullptr)
Definition: IRBuilder.h:1755
CallInst * CreateIntrinsic(Intrinsic::ID ID, ArrayRef< Type * > Types, ArrayRef< Value * > Args, FMFSource FMFSource={}, const Twine &Name="")
Create a call to intrinsic ID with Args, mangled using Types.
Definition: IRBuilder.cpp:890
ConstantInt * getInt32(uint32_t C)
Get a constant 32-bit value.
Definition: IRBuilder.h:500
Value * CreateCmp(CmpInst::Predicate Pred, Value *LHS, Value *RHS, const Twine &Name="", MDNode *FPMathTag=nullptr)
Definition: IRBuilder.h:2398
Value * CreateBitCast(Value *V, Type *DestTy, const Twine &Name="")
Definition: IRBuilder.h:2146
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:1792
Value * CreateShl(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
Definition: IRBuilder.h:1453
Value * CreateZExt(Value *V, Type *DestTy, const Twine &Name="", bool IsNonNeg=false)
Definition: IRBuilder.h:2027
Value * CreateShuffleVector(Value *V1, Value *V2, Value *Mask, const Twine &Name="")
Definition: IRBuilder.h:2527
StoreInst * CreateStore(Value *Val, Value *Ptr, bool isVolatile=false)
Definition: IRBuilder.h:1805
Value * CreateTrunc(Value *V, Type *DestTy, const Twine &Name="", bool IsNUW=false, bool IsNSW=false)
Definition: IRBuilder.h:2013
PointerType * getPtrTy(unsigned AddrSpace=0)
Fetch the type representing a pointer.
Definition: IRBuilder.h:583
Value * CreateBinOp(Instruction::BinaryOps Opc, Value *LHS, Value *RHS, const Twine &Name="", MDNode *FPMathTag=nullptr)
Definition: IRBuilder.h:1665
void SetInsertPoint(BasicBlock *TheBB)
This specifies that created instructions should be appended to the end of the specified block.
Definition: IRBuilder.h:194
Value * CreateFNegFMF(Value *V, FMFSource FMFSource, const Twine &Name="", MDNode *FPMathTag=nullptr)
Definition: IRBuilder.h:1741
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Definition: IRBuilder.h:2699
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.
void copyIRFlags(const Value *V, bool IncludeWrapFlags=true)
Convenience method to copy supported exact, fast-math, and (optionally) wrapping flags from V to this...
bool isBinaryOp() const
Definition: Instruction.h:279
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:280
Intrinsic::ID getIntrinsicID() const
Return the intrinsic ID of this intrinsic.
Definition: IntrinsicInst.h:55
An instruction for reading from memory.
Definition: Instructions.h:176
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.
MutableArrayRef - Represent a mutable reference to an array (0 or more elements consecutively in memo...
Definition: ArrayRef.h:310
static PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
Definition: Constants.cpp:1878
A set of analyses that are preserved following a run of a transformation pass.
Definition: Analysis.h:111
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: Analysis.h:117
void preserveSet()
Mark an analysis set as preserved.
Definition: Analysis.h:146
This class represents a sign extension of integer types.
This class represents a cast from signed integer to floating point.
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:384
bool contains(ConstPtrType Ptr) const
Definition: SmallPtrSet.h:458
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:519
bool empty() const
Definition: SmallVector.h:81
size_t size() const
Definition: SmallVector.h:78
void assign(size_type NumElts, ValueParamT Elt)
Definition: SmallVector.h:704
reference emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:937
void push_back(const T &Elt)
Definition: SmallVector.h:413
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1196
An instruction for storing to memory.
Definition: Instructions.h:292
void setAlignment(Align Align)
Definition: Instructions.h:337
Analysis pass providing the TargetTransformInfo.
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
InstructionCost getCmpSelInstrCost(unsigned Opcode, Type *ValTy, Type *CondTy, CmpInst::Predicate VecPred, TTI::TargetCostKind CostKind=TTI::TCK_RecipThroughput, OperandValueInfo Op1Info={OK_AnyValue, OP_None}, OperandValueInfo Op2Info={OK_AnyValue, OP_None}, const Instruction *I=nullptr) const
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
unsigned getRegisterClassForType(bool Vector, Type *Ty=nullptr) const
TargetCostKind
The kind of cost model.
@ TCK_RecipThroughput
Reciprocal throughput.
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={}, const Instruction *CxtI=nullptr, const TargetLibraryInfo *TLibInfo=nullptr) const
This is an approximation of reciprocal throughput of a math/logic op.
InstructionCost getShuffleCost(ShuffleKind Kind, VectorType *Tp, ArrayRef< int > Mask={}, TTI::TargetCostKind CostKind=TTI::TCK_RecipThroughput, int Index=0, VectorType *SubTp=nullptr, ArrayRef< const Value * > Args={}, const Instruction *CxtI=nullptr) const
unsigned getMinVectorRegisterBitWidth() const
unsigned getNumberOfRegisters(unsigned ClassID) const
InstructionCost getScalarizationOverhead(VectorType *Ty, const APInt &DemandedElts, bool Insert, bool Extract, TTI::TargetCostKind CostKind, ArrayRef< Value * > VL={}) const
Estimate the overhead of scalarizing an instruction.
InstructionCost getInstructionCost(const User *U, ArrayRef< const Value * > Operands, TargetCostKind CostKind) const
Estimate the cost of a given IR user when lowered.
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.
This class represents a truncation of integer types.
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:270
bool isPointerTy() const
True if this is an instance of PointerType.
Definition: Type.h:264
static IntegerType * getIntNTy(LLVMContext &C, unsigned N)
LLVMContext & getContext() const
Return the LLVMContext in which this type was uniqued.
Definition: Type.h:128
bool isFloatingPointTy() const
Return true if this is one of the floating-point types.
Definition: Type.h:184
bool isIntegerTy() const
True if this is an instance of IntegerType.
Definition: Type.h:237
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:355
This class represents a cast unsigned integer to floating point.
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43
op_range operands()
Definition: User.h:288
Value * getOperand(unsigned i) const
Definition: User.h:228
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:740
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:927
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 &)
This class represents zero extension of integer types.
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:125
@ 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.
class_match< PoisonValue > m_Poison()
Match an arbitrary poison constant.
Definition: PatternMatch.h:160
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:982
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:826
specificval_ty m_Specific(const Value *V)
Match if we have a specific specified value.
Definition: PatternMatch.h:885
DisjointOr_match< LHS, RHS > m_DisjointOr(const LHS &L, const RHS &R)
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.
CastInst_match< OpTy, ZExtInst > m_ZExt(const OpTy &Op)
Matches ZExt.
BinOpPred_match< LHS, RHS, is_bitwiselogic_op, true > m_c_BitwiseLogic(const LHS &L, const RHS &R)
Matches bitwise logic operations in either order.
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
BinaryOp_match< LHS, RHS, Instruction::LShr > m_LShr(const LHS &L, const RHS &R)
match_combine_or< CastInst_match< OpTy, ZExtInst >, CastInst_match< OpTy, SExtInst > > m_ZExtOrSExt(const OpTy &Op)
FNeg_match< OpTy > m_FNeg(const OpTy &X)
Match 'fneg X' as 'fsub -0.0, X'.
BinaryOp_match< LHS, RHS, Instruction::Shl > m_Shl(const LHS &L, const RHS &R)
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:443
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:480
void stable_sort(R &&Range)
Definition: STLExtras.h:2037
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:1732
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:1739
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 tuples (A, B,...
Definition: STLExtras.h:2448
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:960
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:657
bool mustSuppressSpeculation(const LoadInst &LI)
Return true if speculation of the given load must be suppressed to avoid ordering or interfering with...
Definition: Loads.cpp:370
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, bool UseVariableInfo=true)
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:1746
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:406
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...
constexpr bool isPowerOf2_32(uint32_t Value)
Return true if the argument is a power of two > 0.
Definition: MathExtras.h:291
bool isModSet(const ModRefInfo MRI)
Definition: ModRef.h:48
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1664
bool isSafeToLoadUnconditionally(Value *V, Align Alignment, const APInt &Size, const DataLayout &DL, Instruction *ScanFrom, 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:385
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
bool isSafeToSpeculativelyExecute(const Instruction *I, const Instruction *CtxI=nullptr, AssumptionCache *AC=nullptr, const DominatorTree *DT=nullptr, const TargetLibraryInfo *TLI=nullptr, bool UseVariableInfo=true)
Return true if the instruction does not have any effects besides calculating the result and does not ...
bool isa(const From &Val)
isa<X> - Return true if the parameter to the template is an instance of one of the template type argu...
Definition: Casting.h:548
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:1368
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...
bool isVectorIntrinsicWithScalarOpAtArg(Intrinsic::ID ID, unsigned ScalarOpdIdx, const TargetTransformInfo *TTI)
Identifies if the vector form of the intrinsic has a scalar operand.
void computeKnownBits(const Value *V, KnownBits &Known, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true)
Determine which bits of V are known to be either zero or one and return them in the KnownZero/KnownOn...
DWARFExpression::Operation Op
constexpr unsigned BitWidth
Definition: BitmaskEnum.h:217
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:1766
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
Definition: STLExtras.h:1903
Align commonAlignment(Align A, uint64_t Offset)
Returns the alignment that satisfies both alignments.
Definition: Alignment.h:212
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
unsigned countMaxActiveBits() const
Returns the maximum number of bits needed to represent all possible unsigned values with these known ...
Definition: KnownBits.h:288
APInt getMaxValue() const
Return the maximal unsigned value possible given these KnownBits.
Definition: KnownBits.h:137