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