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 bool TryEarlyFoldsOnly)
70 : F(F), Builder(F.getContext()), TTI(TTI), DT(DT), AA(AA), AC(AC),
71 TryEarlyFoldsOnly(TryEarlyFoldsOnly) {}
72
73 bool run();
74
75private:
76 Function &F;
77 IRBuilder<> Builder;
79 const DominatorTree &DT;
80 AAResults &AA;
82
83 /// If true, only perform beneficial early IR transforms. Do not introduce new
84 /// vector operations.
85 bool TryEarlyFoldsOnly;
86
87 InstructionWorklist Worklist;
88
89 // TODO: Direct calls from the top-level "run" loop use a plain "Instruction"
90 // parameter. That should be updated to specific sub-classes because the
91 // run loop was changed to dispatch on opcode.
92 bool vectorizeLoadInsert(Instruction &I);
93 bool widenSubvectorLoad(Instruction &I);
94 ExtractElementInst *getShuffleExtract(ExtractElementInst *Ext0,
96 unsigned PreferredExtractIndex) const;
97 bool isExtractExtractCheap(ExtractElementInst *Ext0, ExtractElementInst *Ext1,
98 const Instruction &I,
99 ExtractElementInst *&ConvertToShuffle,
100 unsigned PreferredExtractIndex);
101 void foldExtExtCmp(ExtractElementInst *Ext0, ExtractElementInst *Ext1,
102 Instruction &I);
103 void foldExtExtBinop(ExtractElementInst *Ext0, ExtractElementInst *Ext1,
104 Instruction &I);
105 bool foldExtractExtract(Instruction &I);
106 bool foldInsExtFNeg(Instruction &I);
107 bool foldBitcastShuffle(Instruction &I);
108 bool scalarizeBinopOrCmp(Instruction &I);
109 bool scalarizeVPIntrinsic(Instruction &I);
110 bool foldExtractedCmps(Instruction &I);
111 bool foldSingleElementStore(Instruction &I);
112 bool scalarizeLoadExtract(Instruction &I);
113 bool foldShuffleOfBinops(Instruction &I);
114 bool foldShuffleFromReductions(Instruction &I);
115 bool foldTruncFromReductions(Instruction &I);
116 bool foldSelectShuffle(Instruction &I, bool FromReduction = false);
117
118 void replaceValue(Value &Old, Value &New) {
119 Old.replaceAllUsesWith(&New);
120 if (auto *NewI = dyn_cast<Instruction>(&New)) {
121 New.takeName(&Old);
122 Worklist.pushUsersToWorkList(*NewI);
123 Worklist.pushValue(NewI);
124 }
125 Worklist.pushValue(&Old);
126 }
127
129 for (Value *Op : I.operands())
130 Worklist.pushValue(Op);
131 Worklist.remove(&I);
132 I.eraseFromParent();
133 }
134};
135} // namespace
136
137static bool canWidenLoad(LoadInst *Load, const TargetTransformInfo &TTI) {
138 // Do not widen load if atomic/volatile or under asan/hwasan/memtag/tsan.
139 // The widened load may load data from dirty regions or create data races
140 // non-existent in the source.
141 if (!Load || !Load->isSimple() || !Load->hasOneUse() ||
142 Load->getFunction()->hasFnAttribute(Attribute::SanitizeMemTag) ||
144 return false;
145
146 // We are potentially transforming byte-sized (8-bit) memory accesses, so make
147 // sure we have all of our type-based constraints in place for this target.
148 Type *ScalarTy = Load->getType()->getScalarType();
149 uint64_t ScalarSize = ScalarTy->getPrimitiveSizeInBits();
150 unsigned MinVectorSize = TTI.getMinVectorRegisterBitWidth();
151 if (!ScalarSize || !MinVectorSize || MinVectorSize % ScalarSize != 0 ||
152 ScalarSize % 8 != 0)
153 return false;
154
155 return true;
156}
157
158bool VectorCombine::vectorizeLoadInsert(Instruction &I) {
159 // Match insert into fixed vector of scalar value.
160 // TODO: Handle non-zero insert index.
161 Value *Scalar;
162 if (!match(&I, m_InsertElt(m_Undef(), m_Value(Scalar), m_ZeroInt())) ||
163 !Scalar->hasOneUse())
164 return false;
165
166 // Optionally match an extract from another vector.
167 Value *X;
168 bool HasExtract = match(Scalar, m_ExtractElt(m_Value(X), m_ZeroInt()));
169 if (!HasExtract)
170 X = Scalar;
171
172 auto *Load = dyn_cast<LoadInst>(X);
173 if (!canWidenLoad(Load, TTI))
174 return false;
175
176 Type *ScalarTy = Scalar->getType();
177 uint64_t ScalarSize = ScalarTy->getPrimitiveSizeInBits();
178 unsigned MinVectorSize = TTI.getMinVectorRegisterBitWidth();
179
180 // Check safety of replacing the scalar load with a larger vector load.
181 // We use minimal alignment (maximum flexibility) because we only care about
182 // the dereferenceable region. When calculating cost and creating a new op,
183 // we may use a larger value based on alignment attributes.
184 const DataLayout &DL = I.getModule()->getDataLayout();
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 const DataLayout &DL = I.getModule()->getDataLayout();
302 Value *SrcPtr = Load->getPointerOperand()->stripPointerCasts();
303 assert(isa<PointerType>(SrcPtr->getType()) && "Expected a pointer type");
304 Align Alignment = Load->getAlign();
305 if (!isSafeToLoadUnconditionally(SrcPtr, Ty, Align(1), DL, Load, &AC, &DT))
306 return false;
307
308 Alignment = std::max(SrcPtr->getPointerAlignment(DL), Alignment);
309 Type *LoadTy = Load->getType();
310 unsigned AS = Load->getPointerAddressSpace();
311
312 // Original pattern: insert_subvector (load PtrOp)
313 // This conservatively assumes that the cost of a subvector insert into an
314 // undef value is 0. We could add that cost if the cost model accurately
315 // reflects the real cost of that operation.
316 InstructionCost OldCost =
317 TTI.getMemoryOpCost(Instruction::Load, LoadTy, Alignment, AS);
318
319 // New pattern: load PtrOp
320 InstructionCost NewCost =
321 TTI.getMemoryOpCost(Instruction::Load, Ty, Alignment, AS);
322
323 // We can aggressively convert to the vector form because the backend can
324 // invert this transform if it does not result in a performance win.
325 if (OldCost < NewCost || !NewCost.isValid())
326 return false;
327
328 IRBuilder<> Builder(Load);
329 Value *CastedPtr =
330 Builder.CreatePointerBitCastOrAddrSpaceCast(SrcPtr, Builder.getPtrTy(AS));
331 Value *VecLd = Builder.CreateAlignedLoad(Ty, CastedPtr, Alignment);
332 replaceValue(I, *VecLd);
333 ++NumVecLoad;
334 return true;
335}
336
337/// Determine which, if any, of the inputs should be replaced by a shuffle
338/// followed by extract from a different index.
339ExtractElementInst *VectorCombine::getShuffleExtract(
341 unsigned PreferredExtractIndex = InvalidIndex) const {
342 auto *Index0C = dyn_cast<ConstantInt>(Ext0->getIndexOperand());
343 auto *Index1C = dyn_cast<ConstantInt>(Ext1->getIndexOperand());
344 assert(Index0C && Index1C && "Expected constant extract indexes");
345
346 unsigned Index0 = Index0C->getZExtValue();
347 unsigned Index1 = Index1C->getZExtValue();
348
349 // If the extract indexes are identical, no shuffle is needed.
350 if (Index0 == Index1)
351 return nullptr;
352
353 Type *VecTy = Ext0->getVectorOperand()->getType();
355 assert(VecTy == Ext1->getVectorOperand()->getType() && "Need matching types");
356 InstructionCost Cost0 =
357 TTI.getVectorInstrCost(*Ext0, VecTy, CostKind, Index0);
358 InstructionCost Cost1 =
359 TTI.getVectorInstrCost(*Ext1, VecTy, CostKind, Index1);
360
361 // If both costs are invalid no shuffle is needed
362 if (!Cost0.isValid() && !Cost1.isValid())
363 return nullptr;
364
365 // We are extracting from 2 different indexes, so one operand must be shuffled
366 // before performing a vector operation and/or extract. The more expensive
367 // extract will be replaced by a shuffle.
368 if (Cost0 > Cost1)
369 return Ext0;
370 if (Cost1 > Cost0)
371 return Ext1;
372
373 // If the costs are equal and there is a preferred extract index, shuffle the
374 // opposite operand.
375 if (PreferredExtractIndex == Index0)
376 return Ext1;
377 if (PreferredExtractIndex == Index1)
378 return Ext0;
379
380 // Otherwise, replace the extract with the higher index.
381 return Index0 > Index1 ? Ext0 : Ext1;
382}
383
384/// Compare the relative costs of 2 extracts followed by scalar operation vs.
385/// vector operation(s) followed by extract. Return true if the existing
386/// instructions are cheaper than a vector alternative. Otherwise, return false
387/// and if one of the extracts should be transformed to a shufflevector, set
388/// \p ConvertToShuffle to that extract instruction.
389bool VectorCombine::isExtractExtractCheap(ExtractElementInst *Ext0,
390 ExtractElementInst *Ext1,
391 const Instruction &I,
392 ExtractElementInst *&ConvertToShuffle,
393 unsigned PreferredExtractIndex) {
394 auto *Ext0IndexC = dyn_cast<ConstantInt>(Ext0->getOperand(1));
395 auto *Ext1IndexC = dyn_cast<ConstantInt>(Ext1->getOperand(1));
396 assert(Ext0IndexC && Ext1IndexC && "Expected constant extract indexes");
397
398 unsigned Opcode = I.getOpcode();
399 Type *ScalarTy = Ext0->getType();
400 auto *VecTy = cast<VectorType>(Ext0->getOperand(0)->getType());
401 InstructionCost ScalarOpCost, VectorOpCost;
402
403 // Get cost estimates for scalar and vector versions of the operation.
404 bool IsBinOp = Instruction::isBinaryOp(Opcode);
405 if (IsBinOp) {
406 ScalarOpCost = TTI.getArithmeticInstrCost(Opcode, ScalarTy);
407 VectorOpCost = TTI.getArithmeticInstrCost(Opcode, VecTy);
408 } else {
409 assert((Opcode == Instruction::ICmp || Opcode == Instruction::FCmp) &&
410 "Expected a compare");
411 CmpInst::Predicate Pred = cast<CmpInst>(I).getPredicate();
412 ScalarOpCost = TTI.getCmpSelInstrCost(
413 Opcode, ScalarTy, CmpInst::makeCmpResultType(ScalarTy), Pred);
414 VectorOpCost = TTI.getCmpSelInstrCost(
415 Opcode, VecTy, CmpInst::makeCmpResultType(VecTy), Pred);
416 }
417
418 // Get cost estimates for the extract elements. These costs will factor into
419 // both sequences.
420 unsigned Ext0Index = Ext0IndexC->getZExtValue();
421 unsigned Ext1Index = Ext1IndexC->getZExtValue();
423
424 InstructionCost Extract0Cost =
425 TTI.getVectorInstrCost(*Ext0, VecTy, CostKind, Ext0Index);
426 InstructionCost Extract1Cost =
427 TTI.getVectorInstrCost(*Ext1, VecTy, CostKind, Ext1Index);
428
429 // A more expensive extract will always be replaced by a splat shuffle.
430 // For example, if Ext0 is more expensive:
431 // opcode (extelt V0, Ext0), (ext V1, Ext1) -->
432 // extelt (opcode (splat V0, Ext0), V1), Ext1
433 // TODO: Evaluate whether that always results in lowest cost. Alternatively,
434 // check the cost of creating a broadcast shuffle and shuffling both
435 // operands to element 0.
436 InstructionCost CheapExtractCost = std::min(Extract0Cost, Extract1Cost);
437
438 // Extra uses of the extracts mean that we include those costs in the
439 // vector total because those instructions will not be eliminated.
440 InstructionCost OldCost, NewCost;
441 if (Ext0->getOperand(0) == Ext1->getOperand(0) && Ext0Index == Ext1Index) {
442 // Handle a special case. If the 2 extracts are identical, adjust the
443 // formulas to account for that. The extra use charge allows for either the
444 // CSE'd pattern or an unoptimized form with identical values:
445 // opcode (extelt V, C), (extelt V, C) --> extelt (opcode V, V), C
446 bool HasUseTax = Ext0 == Ext1 ? !Ext0->hasNUses(2)
447 : !Ext0->hasOneUse() || !Ext1->hasOneUse();
448 OldCost = CheapExtractCost + ScalarOpCost;
449 NewCost = VectorOpCost + CheapExtractCost + HasUseTax * CheapExtractCost;
450 } else {
451 // Handle the general case. Each extract is actually a different value:
452 // opcode (extelt V0, C0), (extelt V1, C1) --> extelt (opcode V0, V1), C
453 OldCost = Extract0Cost + Extract1Cost + ScalarOpCost;
454 NewCost = VectorOpCost + CheapExtractCost +
455 !Ext0->hasOneUse() * Extract0Cost +
456 !Ext1->hasOneUse() * Extract1Cost;
457 }
458
459 ConvertToShuffle = getShuffleExtract(Ext0, Ext1, PreferredExtractIndex);
460 if (ConvertToShuffle) {
461 if (IsBinOp && DisableBinopExtractShuffle)
462 return true;
463
464 // If we are extracting from 2 different indexes, then one operand must be
465 // shuffled before performing the vector operation. The shuffle mask is
466 // poison except for 1 lane that is being translated to the remaining
467 // extraction lane. Therefore, it is a splat shuffle. Ex:
468 // ShufMask = { poison, poison, 0, poison }
469 // TODO: The cost model has an option for a "broadcast" shuffle
470 // (splat-from-element-0), but no option for a more general splat.
471 NewCost +=
473 }
474
475 // Aggressively form a vector op if the cost is equal because the transform
476 // may enable further optimization.
477 // Codegen can reverse this transform (scalarize) if it was not profitable.
478 return OldCost < NewCost;
479}
480
481/// Create a shuffle that translates (shifts) 1 element from the input vector
482/// to a new element location.
483static Value *createShiftShuffle(Value *Vec, unsigned OldIndex,
484 unsigned NewIndex, IRBuilder<> &Builder) {
485 // The shuffle mask is poison except for 1 lane that is being translated
486 // to the new element index. Example for OldIndex == 2 and NewIndex == 0:
487 // ShufMask = { 2, poison, poison, poison }
488 auto *VecTy = cast<FixedVectorType>(Vec->getType());
489 SmallVector<int, 32> ShufMask(VecTy->getNumElements(), PoisonMaskElem);
490 ShufMask[NewIndex] = OldIndex;
491 return Builder.CreateShuffleVector(Vec, ShufMask, "shift");
492}
493
494/// Given an extract element instruction with constant index operand, shuffle
495/// the source vector (shift the scalar element) to a NewIndex for extraction.
496/// Return null if the input can be constant folded, so that we are not creating
497/// unnecessary instructions.
499 unsigned NewIndex,
500 IRBuilder<> &Builder) {
501 // Shufflevectors can only be created for fixed-width vectors.
502 if (!isa<FixedVectorType>(ExtElt->getOperand(0)->getType()))
503 return nullptr;
504
505 // If the extract can be constant-folded, this code is unsimplified. Defer
506 // to other passes to handle that.
507 Value *X = ExtElt->getVectorOperand();
508 Value *C = ExtElt->getIndexOperand();
509 assert(isa<ConstantInt>(C) && "Expected a constant index operand");
510 if (isa<Constant>(X))
511 return nullptr;
512
513 Value *Shuf = createShiftShuffle(X, cast<ConstantInt>(C)->getZExtValue(),
514 NewIndex, Builder);
515 return cast<ExtractElementInst>(Builder.CreateExtractElement(Shuf, NewIndex));
516}
517
518/// Try to reduce extract element costs by converting scalar compares to vector
519/// compares followed by extract.
520/// cmp (ext0 V0, C), (ext1 V1, C)
521void VectorCombine::foldExtExtCmp(ExtractElementInst *Ext0,
523 assert(isa<CmpInst>(&I) && "Expected a compare");
524 assert(cast<ConstantInt>(Ext0->getIndexOperand())->getZExtValue() ==
525 cast<ConstantInt>(Ext1->getIndexOperand())->getZExtValue() &&
526 "Expected matching constant extract indexes");
527
528 // cmp Pred (extelt V0, C), (extelt V1, C) --> extelt (cmp Pred V0, V1), C
529 ++NumVecCmp;
530 CmpInst::Predicate Pred = cast<CmpInst>(&I)->getPredicate();
531 Value *V0 = Ext0->getVectorOperand(), *V1 = Ext1->getVectorOperand();
532 Value *VecCmp = Builder.CreateCmp(Pred, V0, V1);
533 Value *NewExt = Builder.CreateExtractElement(VecCmp, Ext0->getIndexOperand());
534 replaceValue(I, *NewExt);
535}
536
537/// Try to reduce extract element costs by converting scalar binops to vector
538/// binops followed by extract.
539/// bo (ext0 V0, C), (ext1 V1, C)
540void VectorCombine::foldExtExtBinop(ExtractElementInst *Ext0,
542 assert(isa<BinaryOperator>(&I) && "Expected a binary operator");
543 assert(cast<ConstantInt>(Ext0->getIndexOperand())->getZExtValue() ==
544 cast<ConstantInt>(Ext1->getIndexOperand())->getZExtValue() &&
545 "Expected matching constant extract indexes");
546
547 // bo (extelt V0, C), (extelt V1, C) --> extelt (bo V0, V1), C
548 ++NumVecBO;
549 Value *V0 = Ext0->getVectorOperand(), *V1 = Ext1->getVectorOperand();
550 Value *VecBO =
551 Builder.CreateBinOp(cast<BinaryOperator>(&I)->getOpcode(), V0, V1);
552
553 // All IR flags are safe to back-propagate because any potential poison
554 // created in unused vector elements is discarded by the extract.
555 if (auto *VecBOInst = dyn_cast<Instruction>(VecBO))
556 VecBOInst->copyIRFlags(&I);
557
558 Value *NewExt = Builder.CreateExtractElement(VecBO, Ext0->getIndexOperand());
559 replaceValue(I, *NewExt);
560}
561
562/// Match an instruction with extracted vector operands.
563bool VectorCombine::foldExtractExtract(Instruction &I) {
564 // It is not safe to transform things like div, urem, etc. because we may
565 // create undefined behavior when executing those on unknown vector elements.
567 return false;
568
569 Instruction *I0, *I1;
571 if (!match(&I, m_Cmp(Pred, m_Instruction(I0), m_Instruction(I1))) &&
573 return false;
574
575 Value *V0, *V1;
576 uint64_t C0, C1;
577 if (!match(I0, m_ExtractElt(m_Value(V0), m_ConstantInt(C0))) ||
578 !match(I1, m_ExtractElt(m_Value(V1), m_ConstantInt(C1))) ||
579 V0->getType() != V1->getType())
580 return false;
581
582 // If the scalar value 'I' is going to be re-inserted into a vector, then try
583 // to create an extract to that same element. The extract/insert can be
584 // reduced to a "select shuffle".
585 // TODO: If we add a larger pattern match that starts from an insert, this
586 // probably becomes unnecessary.
587 auto *Ext0 = cast<ExtractElementInst>(I0);
588 auto *Ext1 = cast<ExtractElementInst>(I1);
589 uint64_t InsertIndex = InvalidIndex;
590 if (I.hasOneUse())
591 match(I.user_back(),
592 m_InsertElt(m_Value(), m_Value(), m_ConstantInt(InsertIndex)));
593
594 ExtractElementInst *ExtractToChange;
595 if (isExtractExtractCheap(Ext0, Ext1, I, ExtractToChange, InsertIndex))
596 return false;
597
598 if (ExtractToChange) {
599 unsigned CheapExtractIdx = ExtractToChange == Ext0 ? C1 : C0;
600 ExtractElementInst *NewExtract =
601 translateExtract(ExtractToChange, CheapExtractIdx, Builder);
602 if (!NewExtract)
603 return false;
604 if (ExtractToChange == Ext0)
605 Ext0 = NewExtract;
606 else
607 Ext1 = NewExtract;
608 }
609
610 if (Pred != CmpInst::BAD_ICMP_PREDICATE)
611 foldExtExtCmp(Ext0, Ext1, I);
612 else
613 foldExtExtBinop(Ext0, Ext1, I);
614
615 Worklist.push(Ext0);
616 Worklist.push(Ext1);
617 return true;
618}
619
620/// Try to replace an extract + scalar fneg + insert with a vector fneg +
621/// shuffle.
622bool VectorCombine::foldInsExtFNeg(Instruction &I) {
623 // Match an insert (op (extract)) pattern.
624 Value *DestVec;
626 Instruction *FNeg;
627 if (!match(&I, m_InsertElt(m_Value(DestVec), m_OneUse(m_Instruction(FNeg)),
629 return false;
630
631 // Note: This handles the canonical fneg instruction and "fsub -0.0, X".
632 Value *SrcVec;
633 Instruction *Extract;
634 if (!match(FNeg, m_FNeg(m_CombineAnd(
635 m_Instruction(Extract),
637 return false;
638
639 // TODO: We could handle this with a length-changing shuffle.
640 auto *VecTy = cast<FixedVectorType>(I.getType());
641 if (SrcVec->getType() != VecTy)
642 return false;
643
644 // Ignore bogus insert/extract index.
645 unsigned NumElts = VecTy->getNumElements();
646 if (Index >= NumElts)
647 return false;
648
649 // We are inserting the negated element into the same lane that we extracted
650 // from. This is equivalent to a select-shuffle that chooses all but the
651 // negated element from the destination vector.
652 SmallVector<int> Mask(NumElts);
653 std::iota(Mask.begin(), Mask.end(), 0);
654 Mask[Index] = Index + NumElts;
655
656 Type *ScalarTy = VecTy->getScalarType();
658 InstructionCost OldCost =
659 TTI.getArithmeticInstrCost(Instruction::FNeg, ScalarTy) +
661
662 // If the extract has one use, it will be eliminated, so count it in the
663 // original cost. If it has more than one use, ignore the cost because it will
664 // be the same before/after.
665 if (Extract->hasOneUse())
666 OldCost += TTI.getVectorInstrCost(*Extract, VecTy, CostKind, Index);
667
668 InstructionCost NewCost =
669 TTI.getArithmeticInstrCost(Instruction::FNeg, VecTy) +
671
672 if (NewCost > OldCost)
673 return false;
674
675 // insertelt DestVec, (fneg (extractelt SrcVec, Index)), Index -->
676 // shuffle DestVec, (fneg SrcVec), Mask
677 Value *VecFNeg = Builder.CreateFNegFMF(SrcVec, FNeg);
678 Value *Shuf = Builder.CreateShuffleVector(DestVec, VecFNeg, Mask);
679 replaceValue(I, *Shuf);
680 return true;
681}
682
683/// If this is a bitcast of a shuffle, try to bitcast the source vector to the
684/// destination type followed by shuffle. This can enable further transforms by
685/// moving bitcasts or shuffles together.
686bool VectorCombine::foldBitcastShuffle(Instruction &I) {
687 Value *V;
689 if (!match(&I, m_BitCast(
690 m_OneUse(m_Shuffle(m_Value(V), m_Undef(), m_Mask(Mask))))))
691 return false;
692
693 // 1) Do not fold bitcast shuffle for scalable type. First, shuffle cost for
694 // scalable type is unknown; Second, we cannot reason if the narrowed shuffle
695 // mask for scalable type is a splat or not.
696 // 2) Disallow non-vector casts.
697 // TODO: We could allow any shuffle.
698 auto *DestTy = dyn_cast<FixedVectorType>(I.getType());
699 auto *SrcTy = dyn_cast<FixedVectorType>(V->getType());
700 if (!DestTy || !SrcTy)
701 return false;
702
703 unsigned DestEltSize = DestTy->getScalarSizeInBits();
704 unsigned SrcEltSize = SrcTy->getScalarSizeInBits();
705 if (SrcTy->getPrimitiveSizeInBits() % DestEltSize != 0)
706 return false;
707
708 SmallVector<int, 16> NewMask;
709 if (DestEltSize <= SrcEltSize) {
710 // The bitcast is from wide to narrow/equal elements. The shuffle mask can
711 // always be expanded to the equivalent form choosing narrower elements.
712 assert(SrcEltSize % DestEltSize == 0 && "Unexpected shuffle mask");
713 unsigned ScaleFactor = SrcEltSize / DestEltSize;
714 narrowShuffleMaskElts(ScaleFactor, Mask, NewMask);
715 } else {
716 // The bitcast is from narrow elements to wide elements. The shuffle mask
717 // must choose consecutive elements to allow casting first.
718 assert(DestEltSize % SrcEltSize == 0 && "Unexpected shuffle mask");
719 unsigned ScaleFactor = DestEltSize / SrcEltSize;
720 if (!widenShuffleMaskElts(ScaleFactor, Mask, NewMask))
721 return false;
722 }
723
724 // Bitcast the shuffle src - keep its original width but using the destination
725 // scalar type.
726 unsigned NumSrcElts = SrcTy->getPrimitiveSizeInBits() / DestEltSize;
727 auto *ShuffleTy = FixedVectorType::get(DestTy->getScalarType(), NumSrcElts);
728
729 // The new shuffle must not cost more than the old shuffle. The bitcast is
730 // moved ahead of the shuffle, so assume that it has the same cost as before.
732 TargetTransformInfo::SK_PermuteSingleSrc, ShuffleTy, NewMask);
733 InstructionCost SrcCost =
735 if (DestCost > SrcCost || !DestCost.isValid())
736 return false;
737
738 // bitcast (shuf V, MaskC) --> shuf (bitcast V), MaskC'
739 ++NumShufOfBitcast;
740 Value *CastV = Builder.CreateBitCast(V, ShuffleTy);
741 Value *Shuf = Builder.CreateShuffleVector(CastV, NewMask);
742 replaceValue(I, *Shuf);
743 return true;
744}
745
746/// VP Intrinsics whose vector operands are both splat values may be simplified
747/// into the scalar version of the operation and the result splatted. This
748/// can lead to scalarization down the line.
749bool VectorCombine::scalarizeVPIntrinsic(Instruction &I) {
750 if (!isa<VPIntrinsic>(I))
751 return false;
752 VPIntrinsic &VPI = cast<VPIntrinsic>(I);
753 Value *Op0 = VPI.getArgOperand(0);
754 Value *Op1 = VPI.getArgOperand(1);
755
756 if (!isSplatValue(Op0) || !isSplatValue(Op1))
757 return false;
758
759 // Check getSplatValue early in this function, to avoid doing unnecessary
760 // work.
761 Value *ScalarOp0 = getSplatValue(Op0);
762 Value *ScalarOp1 = getSplatValue(Op1);
763 if (!ScalarOp0 || !ScalarOp1)
764 return false;
765
766 // For the binary VP intrinsics supported here, the result on disabled lanes
767 // is a poison value. For now, only do this simplification if all lanes
768 // are active.
769 // TODO: Relax the condition that all lanes are active by using insertelement
770 // on inactive lanes.
771 auto IsAllTrueMask = [](Value *MaskVal) {
772 if (Value *SplattedVal = getSplatValue(MaskVal))
773 if (auto *ConstValue = dyn_cast<Constant>(SplattedVal))
774 return ConstValue->isAllOnesValue();
775 return false;
776 };
777 if (!IsAllTrueMask(VPI.getArgOperand(2)))
778 return false;
779
780 // Check to make sure we support scalarization of the intrinsic
781 Intrinsic::ID IntrID = VPI.getIntrinsicID();
782 if (!VPBinOpIntrinsic::isVPBinOp(IntrID))
783 return false;
784
785 // Calculate cost of splatting both operands into vectors and the vector
786 // intrinsic
787 VectorType *VecTy = cast<VectorType>(VPI.getType());
789 InstructionCost SplatCost =
790 TTI.getVectorInstrCost(Instruction::InsertElement, VecTy, CostKind, 0) +
792
793 // Calculate the cost of the VP Intrinsic
795 for (Value *V : VPI.args())
796 Args.push_back(V->getType());
797 IntrinsicCostAttributes Attrs(IntrID, VecTy, Args);
798 InstructionCost VectorOpCost = TTI.getIntrinsicInstrCost(Attrs, CostKind);
799 InstructionCost OldCost = 2 * SplatCost + VectorOpCost;
800
801 // Determine scalar opcode
802 std::optional<unsigned> FunctionalOpcode =
804 std::optional<Intrinsic::ID> ScalarIntrID = std::nullopt;
805 if (!FunctionalOpcode) {
806 ScalarIntrID = VPI.getFunctionalIntrinsicID();
807 if (!ScalarIntrID)
808 return false;
809 }
810
811 // Calculate cost of scalarizing
812 InstructionCost ScalarOpCost = 0;
813 if (ScalarIntrID) {
814 IntrinsicCostAttributes Attrs(*ScalarIntrID, VecTy->getScalarType(), Args);
815 ScalarOpCost = TTI.getIntrinsicInstrCost(Attrs, CostKind);
816 } else {
817 ScalarOpCost =
818 TTI.getArithmeticInstrCost(*FunctionalOpcode, VecTy->getScalarType());
819 }
820
821 // The existing splats may be kept around if other instructions use them.
822 InstructionCost CostToKeepSplats =
823 (SplatCost * !Op0->hasOneUse()) + (SplatCost * !Op1->hasOneUse());
824 InstructionCost NewCost = ScalarOpCost + SplatCost + CostToKeepSplats;
825
826 LLVM_DEBUG(dbgs() << "Found a VP Intrinsic to scalarize: " << VPI
827 << "\n");
828 LLVM_DEBUG(dbgs() << "Cost of Intrinsic: " << OldCost
829 << ", Cost of scalarizing:" << NewCost << "\n");
830
831 // We want to scalarize unless the vector variant actually has lower cost.
832 if (OldCost < NewCost || !NewCost.isValid())
833 return false;
834
835 // Scalarize the intrinsic
836 ElementCount EC = cast<VectorType>(Op0->getType())->getElementCount();
837 Value *EVL = VPI.getArgOperand(3);
838 const DataLayout &DL = VPI.getModule()->getDataLayout();
839
840 // If the VP op might introduce UB or poison, we can scalarize it provided
841 // that we know the EVL > 0: If the EVL is zero, then the original VP op
842 // becomes a no-op and thus won't be UB, so make sure we don't introduce UB by
843 // scalarizing it.
844 bool SafeToSpeculate;
845 if (ScalarIntrID)
846 SafeToSpeculate = Intrinsic::getAttributes(I.getContext(), *ScalarIntrID)
847 .hasFnAttr(Attribute::AttrKind::Speculatable);
848 else
850 *FunctionalOpcode, &VPI, nullptr, &AC, &DT);
851 if (!SafeToSpeculate && !isKnownNonZero(EVL, DL, 0, &AC, &VPI, &DT))
852 return false;
853
854 Value *ScalarVal =
855 ScalarIntrID
856 ? Builder.CreateIntrinsic(VecTy->getScalarType(), *ScalarIntrID,
857 {ScalarOp0, ScalarOp1})
858 : Builder.CreateBinOp((Instruction::BinaryOps)(*FunctionalOpcode),
859 ScalarOp0, ScalarOp1);
860
861 replaceValue(VPI, *Builder.CreateVectorSplat(EC, ScalarVal));
862 return true;
863}
864
865/// Match a vector binop or compare instruction with at least one inserted
866/// scalar operand and convert to scalar binop/cmp followed by insertelement.
867bool VectorCombine::scalarizeBinopOrCmp(Instruction &I) {
869 Value *Ins0, *Ins1;
870 if (!match(&I, m_BinOp(m_Value(Ins0), m_Value(Ins1))) &&
871 !match(&I, m_Cmp(Pred, m_Value(Ins0), m_Value(Ins1))))
872 return false;
873
874 // Do not convert the vector condition of a vector select into a scalar
875 // condition. That may cause problems for codegen because of differences in
876 // boolean formats and register-file transfers.
877 // TODO: Can we account for that in the cost model?
878 bool IsCmp = Pred != CmpInst::Predicate::BAD_ICMP_PREDICATE;
879 if (IsCmp)
880 for (User *U : I.users())
881 if (match(U, m_Select(m_Specific(&I), m_Value(), m_Value())))
882 return false;
883
884 // Match against one or both scalar values being inserted into constant
885 // vectors:
886 // vec_op VecC0, (inselt VecC1, V1, Index)
887 // vec_op (inselt VecC0, V0, Index), VecC1
888 // vec_op (inselt VecC0, V0, Index), (inselt VecC1, V1, Index)
889 // TODO: Deal with mismatched index constants and variable indexes?
890 Constant *VecC0 = nullptr, *VecC1 = nullptr;
891 Value *V0 = nullptr, *V1 = nullptr;
892 uint64_t Index0 = 0, Index1 = 0;
893 if (!match(Ins0, m_InsertElt(m_Constant(VecC0), m_Value(V0),
894 m_ConstantInt(Index0))) &&
895 !match(Ins0, m_Constant(VecC0)))
896 return false;
897 if (!match(Ins1, m_InsertElt(m_Constant(VecC1), m_Value(V1),
898 m_ConstantInt(Index1))) &&
899 !match(Ins1, m_Constant(VecC1)))
900 return false;
901
902 bool IsConst0 = !V0;
903 bool IsConst1 = !V1;
904 if (IsConst0 && IsConst1)
905 return false;
906 if (!IsConst0 && !IsConst1 && Index0 != Index1)
907 return false;
908
909 // Bail for single insertion if it is a load.
910 // TODO: Handle this once getVectorInstrCost can cost for load/stores.
911 auto *I0 = dyn_cast_or_null<Instruction>(V0);
912 auto *I1 = dyn_cast_or_null<Instruction>(V1);
913 if ((IsConst0 && I1 && I1->mayReadFromMemory()) ||
914 (IsConst1 && I0 && I0->mayReadFromMemory()))
915 return false;
916
917 uint64_t Index = IsConst0 ? Index1 : Index0;
918 Type *ScalarTy = IsConst0 ? V1->getType() : V0->getType();
919 Type *VecTy = I.getType();
920 assert(VecTy->isVectorTy() &&
921 (IsConst0 || IsConst1 || V0->getType() == V1->getType()) &&
922 (ScalarTy->isIntegerTy() || ScalarTy->isFloatingPointTy() ||
923 ScalarTy->isPointerTy()) &&
924 "Unexpected types for insert element into binop or cmp");
925
926 unsigned Opcode = I.getOpcode();
927 InstructionCost ScalarOpCost, VectorOpCost;
928 if (IsCmp) {
929 CmpInst::Predicate Pred = cast<CmpInst>(I).getPredicate();
930 ScalarOpCost = TTI.getCmpSelInstrCost(
931 Opcode, ScalarTy, CmpInst::makeCmpResultType(ScalarTy), Pred);
932 VectorOpCost = TTI.getCmpSelInstrCost(
933 Opcode, VecTy, CmpInst::makeCmpResultType(VecTy), Pred);
934 } else {
935 ScalarOpCost = TTI.getArithmeticInstrCost(Opcode, ScalarTy);
936 VectorOpCost = TTI.getArithmeticInstrCost(Opcode, VecTy);
937 }
938
939 // Get cost estimate for the insert element. This cost will factor into
940 // both sequences.
943 Instruction::InsertElement, VecTy, CostKind, Index);
944 InstructionCost OldCost =
945 (IsConst0 ? 0 : InsertCost) + (IsConst1 ? 0 : InsertCost) + VectorOpCost;
946 InstructionCost NewCost = ScalarOpCost + InsertCost +
947 (IsConst0 ? 0 : !Ins0->hasOneUse() * InsertCost) +
948 (IsConst1 ? 0 : !Ins1->hasOneUse() * InsertCost);
949
950 // We want to scalarize unless the vector variant actually has lower cost.
951 if (OldCost < NewCost || !NewCost.isValid())
952 return false;
953
954 // vec_op (inselt VecC0, V0, Index), (inselt VecC1, V1, Index) -->
955 // inselt NewVecC, (scalar_op V0, V1), Index
956 if (IsCmp)
957 ++NumScalarCmp;
958 else
959 ++NumScalarBO;
960
961 // For constant cases, extract the scalar element, this should constant fold.
962 if (IsConst0)
963 V0 = ConstantExpr::getExtractElement(VecC0, Builder.getInt64(Index));
964 if (IsConst1)
965 V1 = ConstantExpr::getExtractElement(VecC1, Builder.getInt64(Index));
966
967 Value *Scalar =
968 IsCmp ? Builder.CreateCmp(Pred, V0, V1)
969 : Builder.CreateBinOp((Instruction::BinaryOps)Opcode, V0, V1);
970
971 Scalar->setName(I.getName() + ".scalar");
972
973 // All IR flags are safe to back-propagate. There is no potential for extra
974 // poison to be created by the scalar instruction.
975 if (auto *ScalarInst = dyn_cast<Instruction>(Scalar))
976 ScalarInst->copyIRFlags(&I);
977
978 // Fold the vector constants in the original vectors into a new base vector.
979 Value *NewVecC =
980 IsCmp ? Builder.CreateCmp(Pred, VecC0, VecC1)
981 : Builder.CreateBinOp((Instruction::BinaryOps)Opcode, VecC0, VecC1);
982 Value *Insert = Builder.CreateInsertElement(NewVecC, Scalar, Index);
983 replaceValue(I, *Insert);
984 return true;
985}
986
987/// Try to combine a scalar binop + 2 scalar compares of extracted elements of
988/// a vector into vector operations followed by extract. Note: The SLP pass
989/// may miss this pattern because of implementation problems.
990bool VectorCombine::foldExtractedCmps(Instruction &I) {
991 // We are looking for a scalar binop of booleans.
992 // binop i1 (cmp Pred I0, C0), (cmp Pred I1, C1)
993 if (!I.isBinaryOp() || !I.getType()->isIntegerTy(1))
994 return false;
995
996 // The compare predicates should match, and each compare should have a
997 // constant operand.
998 // TODO: Relax the one-use constraints.
999 Value *B0 = I.getOperand(0), *B1 = I.getOperand(1);
1000 Instruction *I0, *I1;
1001 Constant *C0, *C1;
1002 CmpInst::Predicate P0, P1;
1003 if (!match(B0, m_OneUse(m_Cmp(P0, m_Instruction(I0), m_Constant(C0)))) ||
1004 !match(B1, m_OneUse(m_Cmp(P1, m_Instruction(I1), m_Constant(C1)))) ||
1005 P0 != P1)
1006 return false;
1007
1008 // The compare operands must be extracts of the same vector with constant
1009 // extract indexes.
1010 // TODO: Relax the one-use constraints.
1011 Value *X;
1012 uint64_t Index0, Index1;
1013 if (!match(I0, m_OneUse(m_ExtractElt(m_Value(X), m_ConstantInt(Index0)))) ||
1015 return false;
1016
1017 auto *Ext0 = cast<ExtractElementInst>(I0);
1018 auto *Ext1 = cast<ExtractElementInst>(I1);
1019 ExtractElementInst *ConvertToShuf = getShuffleExtract(Ext0, Ext1);
1020 if (!ConvertToShuf)
1021 return false;
1022
1023 // The original scalar pattern is:
1024 // binop i1 (cmp Pred (ext X, Index0), C0), (cmp Pred (ext X, Index1), C1)
1025 CmpInst::Predicate Pred = P0;
1026 unsigned CmpOpcode = CmpInst::isFPPredicate(Pred) ? Instruction::FCmp
1027 : Instruction::ICmp;
1028 auto *VecTy = dyn_cast<FixedVectorType>(X->getType());
1029 if (!VecTy)
1030 return false;
1031
1033 InstructionCost OldCost =
1034 TTI.getVectorInstrCost(*Ext0, VecTy, CostKind, Index0);
1035 OldCost += TTI.getVectorInstrCost(*Ext1, VecTy, CostKind, Index1);
1036 OldCost +=
1037 TTI.getCmpSelInstrCost(CmpOpcode, I0->getType(),
1038 CmpInst::makeCmpResultType(I0->getType()), Pred) *
1039 2;
1040 OldCost += TTI.getArithmeticInstrCost(I.getOpcode(), I.getType());
1041
1042 // The proposed vector pattern is:
1043 // vcmp = cmp Pred X, VecC
1044 // ext (binop vNi1 vcmp, (shuffle vcmp, Index1)), Index0
1045 int CheapIndex = ConvertToShuf == Ext0 ? Index1 : Index0;
1046 int ExpensiveIndex = ConvertToShuf == Ext0 ? Index0 : Index1;
1047 auto *CmpTy = cast<FixedVectorType>(CmpInst::makeCmpResultType(X->getType()));
1049 CmpOpcode, X->getType(), CmpInst::makeCmpResultType(X->getType()), Pred);
1050 SmallVector<int, 32> ShufMask(VecTy->getNumElements(), PoisonMaskElem);
1051 ShufMask[CheapIndex] = ExpensiveIndex;
1053 ShufMask);
1054 NewCost += TTI.getArithmeticInstrCost(I.getOpcode(), CmpTy);
1055 NewCost += TTI.getVectorInstrCost(*Ext0, CmpTy, CostKind, CheapIndex);
1056
1057 // Aggressively form vector ops if the cost is equal because the transform
1058 // may enable further optimization.
1059 // Codegen can reverse this transform (scalarize) if it was not profitable.
1060 if (OldCost < NewCost || !NewCost.isValid())
1061 return false;
1062
1063 // Create a vector constant from the 2 scalar constants.
1064 SmallVector<Constant *, 32> CmpC(VecTy->getNumElements(),
1065 PoisonValue::get(VecTy->getElementType()));
1066 CmpC[Index0] = C0;
1067 CmpC[Index1] = C1;
1068 Value *VCmp = Builder.CreateCmp(Pred, X, ConstantVector::get(CmpC));
1069
1070 Value *Shuf = createShiftShuffle(VCmp, ExpensiveIndex, CheapIndex, Builder);
1071 Value *VecLogic = Builder.CreateBinOp(cast<BinaryOperator>(I).getOpcode(),
1072 VCmp, Shuf);
1073 Value *NewExt = Builder.CreateExtractElement(VecLogic, CheapIndex);
1074 replaceValue(I, *NewExt);
1075 ++NumVecCmpBO;
1076 return true;
1077}
1078
1079// Check if memory loc modified between two instrs in the same BB
1082 const MemoryLocation &Loc, AAResults &AA) {
1083 unsigned NumScanned = 0;
1084 return std::any_of(Begin, End, [&](const Instruction &Instr) {
1085 return isModSet(AA.getModRefInfo(&Instr, Loc)) ||
1086 ++NumScanned > MaxInstrsToScan;
1087 });
1088}
1089
1090namespace {
1091/// Helper class to indicate whether a vector index can be safely scalarized and
1092/// if a freeze needs to be inserted.
1093class ScalarizationResult {
1094 enum class StatusTy { Unsafe, Safe, SafeWithFreeze };
1095
1096 StatusTy Status;
1097 Value *ToFreeze;
1098
1099 ScalarizationResult(StatusTy Status, Value *ToFreeze = nullptr)
1100 : Status(Status), ToFreeze(ToFreeze) {}
1101
1102public:
1103 ScalarizationResult(const ScalarizationResult &Other) = default;
1104 ~ScalarizationResult() {
1105 assert(!ToFreeze && "freeze() not called with ToFreeze being set");
1106 }
1107
1108 static ScalarizationResult unsafe() { return {StatusTy::Unsafe}; }
1109 static ScalarizationResult safe() { return {StatusTy::Safe}; }
1110 static ScalarizationResult safeWithFreeze(Value *ToFreeze) {
1111 return {StatusTy::SafeWithFreeze, ToFreeze};
1112 }
1113
1114 /// Returns true if the index can be scalarize without requiring a freeze.
1115 bool isSafe() const { return Status == StatusTy::Safe; }
1116 /// Returns true if the index cannot be scalarized.
1117 bool isUnsafe() const { return Status == StatusTy::Unsafe; }
1118 /// Returns true if the index can be scalarize, but requires inserting a
1119 /// freeze.
1120 bool isSafeWithFreeze() const { return Status == StatusTy::SafeWithFreeze; }
1121
1122 /// Reset the state of Unsafe and clear ToFreze if set.
1123 void discard() {
1124 ToFreeze = nullptr;
1125 Status = StatusTy::Unsafe;
1126 }
1127
1128 /// Freeze the ToFreeze and update the use in \p User to use it.
1129 void freeze(IRBuilder<> &Builder, Instruction &UserI) {
1130 assert(isSafeWithFreeze() &&
1131 "should only be used when freezing is required");
1132 assert(is_contained(ToFreeze->users(), &UserI) &&
1133 "UserI must be a user of ToFreeze");
1134 IRBuilder<>::InsertPointGuard Guard(Builder);
1135 Builder.SetInsertPoint(cast<Instruction>(&UserI));
1136 Value *Frozen =
1137 Builder.CreateFreeze(ToFreeze, ToFreeze->getName() + ".frozen");
1138 for (Use &U : make_early_inc_range((UserI.operands())))
1139 if (U.get() == ToFreeze)
1140 U.set(Frozen);
1141
1142 ToFreeze = nullptr;
1143 }
1144};
1145} // namespace
1146
1147/// Check if it is legal to scalarize a memory access to \p VecTy at index \p
1148/// Idx. \p Idx must access a valid vector element.
1149static ScalarizationResult canScalarizeAccess(VectorType *VecTy, Value *Idx,
1150 Instruction *CtxI,
1151 AssumptionCache &AC,
1152 const DominatorTree &DT) {
1153 // We do checks for both fixed vector types and scalable vector types.
1154 // This is the number of elements of fixed vector types,
1155 // or the minimum number of elements of scalable vector types.
1156 uint64_t NumElements = VecTy->getElementCount().getKnownMinValue();
1157
1158 if (auto *C = dyn_cast<ConstantInt>(Idx)) {
1159 if (C->getValue().ult(NumElements))
1160 return ScalarizationResult::safe();
1161 return ScalarizationResult::unsafe();
1162 }
1163
1164 unsigned IntWidth = Idx->getType()->getScalarSizeInBits();
1165 APInt Zero(IntWidth, 0);
1166 APInt MaxElts(IntWidth, NumElements);
1167 ConstantRange ValidIndices(Zero, MaxElts);
1168 ConstantRange IdxRange(IntWidth, true);
1169
1170 if (isGuaranteedNotToBePoison(Idx, &AC)) {
1171 if (ValidIndices.contains(computeConstantRange(Idx, /* ForSigned */ false,
1172 true, &AC, CtxI, &DT)))
1173 return ScalarizationResult::safe();
1174 return ScalarizationResult::unsafe();
1175 }
1176
1177 // If the index may be poison, check if we can insert a freeze before the
1178 // range of the index is restricted.
1179 Value *IdxBase;
1180 ConstantInt *CI;
1181 if (match(Idx, m_And(m_Value(IdxBase), m_ConstantInt(CI)))) {
1182 IdxRange = IdxRange.binaryAnd(CI->getValue());
1183 } else if (match(Idx, m_URem(m_Value(IdxBase), m_ConstantInt(CI)))) {
1184 IdxRange = IdxRange.urem(CI->getValue());
1185 }
1186
1187 if (ValidIndices.contains(IdxRange))
1188 return ScalarizationResult::safeWithFreeze(IdxBase);
1189 return ScalarizationResult::unsafe();
1190}
1191
1192/// The memory operation on a vector of \p ScalarType had alignment of
1193/// \p VectorAlignment. Compute the maximal, but conservatively correct,
1194/// alignment that will be valid for the memory operation on a single scalar
1195/// element of the same type with index \p Idx.
1197 Type *ScalarType, Value *Idx,
1198 const DataLayout &DL) {
1199 if (auto *C = dyn_cast<ConstantInt>(Idx))
1200 return commonAlignment(VectorAlignment,
1201 C->getZExtValue() * DL.getTypeStoreSize(ScalarType));
1202 return commonAlignment(VectorAlignment, DL.getTypeStoreSize(ScalarType));
1203}
1204
1205// Combine patterns like:
1206// %0 = load <4 x i32>, <4 x i32>* %a
1207// %1 = insertelement <4 x i32> %0, i32 %b, i32 1
1208// store <4 x i32> %1, <4 x i32>* %a
1209// to:
1210// %0 = bitcast <4 x i32>* %a to i32*
1211// %1 = getelementptr inbounds i32, i32* %0, i64 0, i64 1
1212// store i32 %b, i32* %1
1213bool VectorCombine::foldSingleElementStore(Instruction &I) {
1214 auto *SI = cast<StoreInst>(&I);
1215 if (!SI->isSimple() || !isa<VectorType>(SI->getValueOperand()->getType()))
1216 return false;
1217
1218 // TODO: Combine more complicated patterns (multiple insert) by referencing
1219 // TargetTransformInfo.
1221 Value *NewElement;
1222 Value *Idx;
1223 if (!match(SI->getValueOperand(),
1224 m_InsertElt(m_Instruction(Source), m_Value(NewElement),
1225 m_Value(Idx))))
1226 return false;
1227
1228 if (auto *Load = dyn_cast<LoadInst>(Source)) {
1229 auto VecTy = cast<VectorType>(SI->getValueOperand()->getType());
1230 const DataLayout &DL = I.getModule()->getDataLayout();
1231 Value *SrcAddr = Load->getPointerOperand()->stripPointerCasts();
1232 // Don't optimize for atomic/volatile load or store. Ensure memory is not
1233 // modified between, vector type matches store size, and index is inbounds.
1234 if (!Load->isSimple() || Load->getParent() != SI->getParent() ||
1235 !DL.typeSizeEqualsStoreSize(Load->getType()->getScalarType()) ||
1236 SrcAddr != SI->getPointerOperand()->stripPointerCasts())
1237 return false;
1238
1239 auto ScalarizableIdx = canScalarizeAccess(VecTy, Idx, Load, AC, DT);
1240 if (ScalarizableIdx.isUnsafe() ||
1241 isMemModifiedBetween(Load->getIterator(), SI->getIterator(),
1242 MemoryLocation::get(SI), AA))
1243 return false;
1244
1245 if (ScalarizableIdx.isSafeWithFreeze())
1246 ScalarizableIdx.freeze(Builder, *cast<Instruction>(Idx));
1247 Value *GEP = Builder.CreateInBoundsGEP(
1248 SI->getValueOperand()->getType(), SI->getPointerOperand(),
1249 {ConstantInt::get(Idx->getType(), 0), Idx});
1250 StoreInst *NSI = Builder.CreateStore(NewElement, GEP);
1251 NSI->copyMetadata(*SI);
1252 Align ScalarOpAlignment = computeAlignmentAfterScalarization(
1253 std::max(SI->getAlign(), Load->getAlign()), NewElement->getType(), Idx,
1254 DL);
1255 NSI->setAlignment(ScalarOpAlignment);
1256 replaceValue(I, *NSI);
1258 return true;
1259 }
1260
1261 return false;
1262}
1263
1264/// Try to scalarize vector loads feeding extractelement instructions.
1265bool VectorCombine::scalarizeLoadExtract(Instruction &I) {
1266 Value *Ptr;
1267 if (!match(&I, m_Load(m_Value(Ptr))))
1268 return false;
1269
1270 auto *VecTy = cast<VectorType>(I.getType());
1271 auto *LI = cast<LoadInst>(&I);
1272 const DataLayout &DL = I.getModule()->getDataLayout();
1273 if (LI->isVolatile() || !DL.typeSizeEqualsStoreSize(VecTy->getScalarType()))
1274 return false;
1275
1276 InstructionCost OriginalCost =
1277 TTI.getMemoryOpCost(Instruction::Load, VecTy, LI->getAlign(),
1278 LI->getPointerAddressSpace());
1279 InstructionCost ScalarizedCost = 0;
1280
1281 Instruction *LastCheckedInst = LI;
1282 unsigned NumInstChecked = 0;
1284 auto FailureGuard = make_scope_exit([&]() {
1285 // If the transform is aborted, discard the ScalarizationResults.
1286 for (auto &Pair : NeedFreeze)
1287 Pair.second.discard();
1288 });
1289
1290 // Check if all users of the load are extracts with no memory modifications
1291 // between the load and the extract. Compute the cost of both the original
1292 // code and the scalarized version.
1293 for (User *U : LI->users()) {
1294 auto *UI = dyn_cast<ExtractElementInst>(U);
1295 if (!UI || UI->getParent() != LI->getParent())
1296 return false;
1297
1298 // Check if any instruction between the load and the extract may modify
1299 // memory.
1300 if (LastCheckedInst->comesBefore(UI)) {
1301 for (Instruction &I :
1302 make_range(std::next(LI->getIterator()), UI->getIterator())) {
1303 // Bail out if we reached the check limit or the instruction may write
1304 // to memory.
1305 if (NumInstChecked == MaxInstrsToScan || I.mayWriteToMemory())
1306 return false;
1307 NumInstChecked++;
1308 }
1309 LastCheckedInst = UI;
1310 }
1311
1312 auto ScalarIdx = canScalarizeAccess(VecTy, UI->getOperand(1), &I, AC, DT);
1313 if (ScalarIdx.isUnsafe())
1314 return false;
1315 if (ScalarIdx.isSafeWithFreeze()) {
1316 NeedFreeze.try_emplace(UI, ScalarIdx);
1317 ScalarIdx.discard();
1318 }
1319
1320 auto *Index = dyn_cast<ConstantInt>(UI->getOperand(1));
1322 OriginalCost +=
1323 TTI.getVectorInstrCost(Instruction::ExtractElement, VecTy, CostKind,
1324 Index ? Index->getZExtValue() : -1);
1325 ScalarizedCost +=
1326 TTI.getMemoryOpCost(Instruction::Load, VecTy->getElementType(),
1327 Align(1), LI->getPointerAddressSpace());
1328 ScalarizedCost += TTI.getAddressComputationCost(VecTy->getElementType());
1329 }
1330
1331 if (ScalarizedCost >= OriginalCost)
1332 return false;
1333
1334 // Replace extracts with narrow scalar loads.
1335 for (User *U : LI->users()) {
1336 auto *EI = cast<ExtractElementInst>(U);
1337 Value *Idx = EI->getOperand(1);
1338
1339 // Insert 'freeze' for poison indexes.
1340 auto It = NeedFreeze.find(EI);
1341 if (It != NeedFreeze.end())
1342 It->second.freeze(Builder, *cast<Instruction>(Idx));
1343
1344 Builder.SetInsertPoint(EI);
1345 Value *GEP =
1346 Builder.CreateInBoundsGEP(VecTy, Ptr, {Builder.getInt32(0), Idx});
1347 auto *NewLoad = cast<LoadInst>(Builder.CreateLoad(
1348 VecTy->getElementType(), GEP, EI->getName() + ".scalar"));
1349
1350 Align ScalarOpAlignment = computeAlignmentAfterScalarization(
1351 LI->getAlign(), VecTy->getElementType(), Idx, DL);
1352 NewLoad->setAlignment(ScalarOpAlignment);
1353
1354 replaceValue(*EI, *NewLoad);
1355 }
1356
1357 FailureGuard.release();
1358 return true;
1359}
1360
1361/// Try to convert "shuffle (binop), (binop)" with a shared binop operand into
1362/// "binop (shuffle), (shuffle)".
1363bool VectorCombine::foldShuffleOfBinops(Instruction &I) {
1364 auto *VecTy = cast<FixedVectorType>(I.getType());
1365 BinaryOperator *B0, *B1;
1367 if (!match(&I, m_Shuffle(m_OneUse(m_BinOp(B0)), m_OneUse(m_BinOp(B1)),
1368 m_Mask(Mask))) ||
1369 B0->getOpcode() != B1->getOpcode() || B0->getType() != VecTy)
1370 return false;
1371
1372 // Try to replace a binop with a shuffle if the shuffle is not costly.
1373 // The new shuffle will choose from a single, common operand, so it may be
1374 // cheaper than the existing two-operand shuffle.
1375 SmallVector<int> UnaryMask = createUnaryMask(Mask, Mask.size());
1376 Instruction::BinaryOps Opcode = B0->getOpcode();
1377 InstructionCost BinopCost = TTI.getArithmeticInstrCost(Opcode, VecTy);
1380 if (ShufCost > BinopCost)
1381 return false;
1382
1383 // If we have something like "add X, Y" and "add Z, X", swap ops to match.
1384 Value *X = B0->getOperand(0), *Y = B0->getOperand(1);
1385 Value *Z = B1->getOperand(0), *W = B1->getOperand(1);
1386 if (BinaryOperator::isCommutative(Opcode) && X != Z && Y != W)
1387 std::swap(X, Y);
1388
1389 Value *Shuf0, *Shuf1;
1390 if (X == Z) {
1391 // shuf (bo X, Y), (bo X, W) --> bo (shuf X), (shuf Y, W)
1392 Shuf0 = Builder.CreateShuffleVector(X, UnaryMask);
1393 Shuf1 = Builder.CreateShuffleVector(Y, W, Mask);
1394 } else if (Y == W) {
1395 // shuf (bo X, Y), (bo Z, Y) --> bo (shuf X, Z), (shuf Y)
1396 Shuf0 = Builder.CreateShuffleVector(X, Z, Mask);
1397 Shuf1 = Builder.CreateShuffleVector(Y, UnaryMask);
1398 } else {
1399 return false;
1400 }
1401
1402 Value *NewBO = Builder.CreateBinOp(Opcode, Shuf0, Shuf1);
1403 // Intersect flags from the old binops.
1404 if (auto *NewInst = dyn_cast<Instruction>(NewBO)) {
1405 NewInst->copyIRFlags(B0);
1406 NewInst->andIRFlags(B1);
1407 }
1408 replaceValue(I, *NewBO);
1409 return true;
1410}
1411
1412/// Given a commutative reduction, the order of the input lanes does not alter
1413/// the results. We can use this to remove certain shuffles feeding the
1414/// reduction, removing the need to shuffle at all.
1415bool VectorCombine::foldShuffleFromReductions(Instruction &I) {
1416 auto *II = dyn_cast<IntrinsicInst>(&I);
1417 if (!II)
1418 return false;
1419 switch (II->getIntrinsicID()) {
1420 case Intrinsic::vector_reduce_add:
1421 case Intrinsic::vector_reduce_mul:
1422 case Intrinsic::vector_reduce_and:
1423 case Intrinsic::vector_reduce_or:
1424 case Intrinsic::vector_reduce_xor:
1425 case Intrinsic::vector_reduce_smin:
1426 case Intrinsic::vector_reduce_smax:
1427 case Intrinsic::vector_reduce_umin:
1428 case Intrinsic::vector_reduce_umax:
1429 break;
1430 default:
1431 return false;
1432 }
1433
1434 // Find all the inputs when looking through operations that do not alter the
1435 // lane order (binops, for example). Currently we look for a single shuffle,
1436 // and can ignore splat values.
1437 std::queue<Value *> Worklist;
1439 ShuffleVectorInst *Shuffle = nullptr;
1440 if (auto *Op = dyn_cast<Instruction>(I.getOperand(0)))
1441 Worklist.push(Op);
1442
1443 while (!Worklist.empty()) {
1444 Value *CV = Worklist.front();
1445 Worklist.pop();
1446 if (Visited.contains(CV))
1447 continue;
1448
1449 // Splats don't change the order, so can be safely ignored.
1450 if (isSplatValue(CV))
1451 continue;
1452
1453 Visited.insert(CV);
1454
1455 if (auto *CI = dyn_cast<Instruction>(CV)) {
1456 if (CI->isBinaryOp()) {
1457 for (auto *Op : CI->operand_values())
1458 Worklist.push(Op);
1459 continue;
1460 } else if (auto *SV = dyn_cast<ShuffleVectorInst>(CI)) {
1461 if (Shuffle && Shuffle != SV)
1462 return false;
1463 Shuffle = SV;
1464 continue;
1465 }
1466 }
1467
1468 // Anything else is currently an unknown node.
1469 return false;
1470 }
1471
1472 if (!Shuffle)
1473 return false;
1474
1475 // Check all uses of the binary ops and shuffles are also included in the
1476 // lane-invariant operations (Visited should be the list of lanewise
1477 // instructions, including the shuffle that we found).
1478 for (auto *V : Visited)
1479 for (auto *U : V->users())
1480 if (!Visited.contains(U) && U != &I)
1481 return false;
1482
1484 dyn_cast<FixedVectorType>(II->getOperand(0)->getType());
1485 if (!VecType)
1486 return false;
1487 FixedVectorType *ShuffleInputType =
1488 dyn_cast<FixedVectorType>(Shuffle->getOperand(0)->getType());
1489 if (!ShuffleInputType)
1490 return false;
1491 unsigned NumInputElts = ShuffleInputType->getNumElements();
1492
1493 // Find the mask from sorting the lanes into order. This is most likely to
1494 // become a identity or concat mask. Undef elements are pushed to the end.
1495 SmallVector<int> ConcatMask;
1496 Shuffle->getShuffleMask(ConcatMask);
1497 sort(ConcatMask, [](int X, int Y) { return (unsigned)X < (unsigned)Y; });
1498 // In the case of a truncating shuffle it's possible for the mask
1499 // to have an index greater than the size of the resulting vector.
1500 // This requires special handling.
1501 bool IsTruncatingShuffle = VecType->getNumElements() < NumInputElts;
1502 bool UsesSecondVec =
1503 any_of(ConcatMask, [&](int M) { return M >= (int)NumInputElts; });
1504
1505 FixedVectorType *VecTyForCost =
1506 (UsesSecondVec && !IsTruncatingShuffle) ? VecType : ShuffleInputType;
1509 VecTyForCost, Shuffle->getShuffleMask());
1512 VecTyForCost, ConcatMask);
1513
1514 LLVM_DEBUG(dbgs() << "Found a reduction feeding from a shuffle: " << *Shuffle
1515 << "\n");
1516 LLVM_DEBUG(dbgs() << " OldCost: " << OldCost << " vs NewCost: " << NewCost
1517 << "\n");
1518 if (NewCost < OldCost) {
1519 Builder.SetInsertPoint(Shuffle);
1520 Value *NewShuffle = Builder.CreateShuffleVector(
1521 Shuffle->getOperand(0), Shuffle->getOperand(1), ConcatMask);
1522 LLVM_DEBUG(dbgs() << "Created new shuffle: " << *NewShuffle << "\n");
1523 replaceValue(*Shuffle, *NewShuffle);
1524 }
1525
1526 // See if we can re-use foldSelectShuffle, getting it to reduce the size of
1527 // the shuffle into a nicer order, as it can ignore the order of the shuffles.
1528 return foldSelectShuffle(*Shuffle, true);
1529}
1530
1531/// Determine if its more efficient to fold:
1532/// reduce(trunc(x)) -> trunc(reduce(x)).
1533bool VectorCombine::foldTruncFromReductions(Instruction &I) {
1534 auto *II = dyn_cast<IntrinsicInst>(&I);
1535 if (!II)
1536 return false;
1537
1538 Intrinsic::ID IID = II->getIntrinsicID();
1539 switch (IID) {
1540 case Intrinsic::vector_reduce_add:
1541 case Intrinsic::vector_reduce_mul:
1542 case Intrinsic::vector_reduce_and:
1543 case Intrinsic::vector_reduce_or:
1544 case Intrinsic::vector_reduce_xor:
1545 break;
1546 default:
1547 return false;
1548 }
1549
1550 unsigned ReductionOpc = getArithmeticReductionInstruction(IID);
1551 Value *ReductionSrc = I.getOperand(0);
1552
1553 Value *TruncSrc;
1554 if (!match(ReductionSrc, m_OneUse(m_Trunc(m_Value(TruncSrc)))))
1555 return false;
1556
1557 auto *Trunc = cast<CastInst>(ReductionSrc);
1558 auto *TruncSrcTy = cast<VectorType>(TruncSrc->getType());
1559 auto *ReductionSrcTy = cast<VectorType>(ReductionSrc->getType());
1560 Type *ResultTy = I.getType();
1561
1563 InstructionCost OldCost =
1564 TTI.getCastInstrCost(Instruction::Trunc, ReductionSrcTy, TruncSrcTy,
1566 TTI.getArithmeticReductionCost(ReductionOpc, ReductionSrcTy, std::nullopt,
1567 CostKind);
1568 InstructionCost NewCost =
1569 TTI.getArithmeticReductionCost(ReductionOpc, TruncSrcTy, std::nullopt,
1570 CostKind) +
1571 TTI.getCastInstrCost(Instruction::Trunc, ResultTy,
1572 ReductionSrcTy->getScalarType(),
1574
1575 if (OldCost <= NewCost || !NewCost.isValid())
1576 return false;
1577
1578 Value *NewReduction = Builder.CreateIntrinsic(
1579 TruncSrcTy->getScalarType(), II->getIntrinsicID(), {TruncSrc});
1580 Value *NewTruncation = Builder.CreateTrunc(NewReduction, ResultTy);
1581 replaceValue(I, *NewTruncation);
1582 return true;
1583}
1584
1585/// This method looks for groups of shuffles acting on binops, of the form:
1586/// %x = shuffle ...
1587/// %y = shuffle ...
1588/// %a = binop %x, %y
1589/// %b = binop %x, %y
1590/// shuffle %a, %b, selectmask
1591/// We may, especially if the shuffle is wider than legal, be able to convert
1592/// the shuffle to a form where only parts of a and b need to be computed. On
1593/// architectures with no obvious "select" shuffle, this can reduce the total
1594/// number of operations if the target reports them as cheaper.
1595bool VectorCombine::foldSelectShuffle(Instruction &I, bool FromReduction) {
1596 auto *SVI = cast<ShuffleVectorInst>(&I);
1597 auto *VT = cast<FixedVectorType>(I.getType());
1598 auto *Op0 = dyn_cast<Instruction>(SVI->getOperand(0));
1599 auto *Op1 = dyn_cast<Instruction>(SVI->getOperand(1));
1600 if (!Op0 || !Op1 || Op0 == Op1 || !Op0->isBinaryOp() || !Op1->isBinaryOp() ||
1601 VT != Op0->getType())
1602 return false;
1603
1604 auto *SVI0A = dyn_cast<Instruction>(Op0->getOperand(0));
1605 auto *SVI0B = dyn_cast<Instruction>(Op0->getOperand(1));
1606 auto *SVI1A = dyn_cast<Instruction>(Op1->getOperand(0));
1607 auto *SVI1B = dyn_cast<Instruction>(Op1->getOperand(1));
1608 SmallPtrSet<Instruction *, 4> InputShuffles({SVI0A, SVI0B, SVI1A, SVI1B});
1609 auto checkSVNonOpUses = [&](Instruction *I) {
1610 if (!I || I->getOperand(0)->getType() != VT)
1611 return true;
1612 return any_of(I->users(), [&](User *U) {
1613 return U != Op0 && U != Op1 &&
1614 !(isa<ShuffleVectorInst>(U) &&
1615 (InputShuffles.contains(cast<Instruction>(U)) ||
1616 isInstructionTriviallyDead(cast<Instruction>(U))));
1617 });
1618 };
1619 if (checkSVNonOpUses(SVI0A) || checkSVNonOpUses(SVI0B) ||
1620 checkSVNonOpUses(SVI1A) || checkSVNonOpUses(SVI1B))
1621 return false;
1622
1623 // Collect all the uses that are shuffles that we can transform together. We
1624 // may not have a single shuffle, but a group that can all be transformed
1625 // together profitably.
1627 auto collectShuffles = [&](Instruction *I) {
1628 for (auto *U : I->users()) {
1629 auto *SV = dyn_cast<ShuffleVectorInst>(U);
1630 if (!SV || SV->getType() != VT)
1631 return false;
1632 if ((SV->getOperand(0) != Op0 && SV->getOperand(0) != Op1) ||
1633 (SV->getOperand(1) != Op0 && SV->getOperand(1) != Op1))
1634 return false;
1635 if (!llvm::is_contained(Shuffles, SV))
1636 Shuffles.push_back(SV);
1637 }
1638 return true;
1639 };
1640 if (!collectShuffles(Op0) || !collectShuffles(Op1))
1641 return false;
1642 // From a reduction, we need to be processing a single shuffle, otherwise the
1643 // other uses will not be lane-invariant.
1644 if (FromReduction && Shuffles.size() > 1)
1645 return false;
1646
1647 // Add any shuffle uses for the shuffles we have found, to include them in our
1648 // cost calculations.
1649 if (!FromReduction) {
1650 for (ShuffleVectorInst *SV : Shuffles) {
1651 for (auto *U : SV->users()) {
1652 ShuffleVectorInst *SSV = dyn_cast<ShuffleVectorInst>(U);
1653 if (SSV && isa<UndefValue>(SSV->getOperand(1)) && SSV->getType() == VT)
1654 Shuffles.push_back(SSV);
1655 }
1656 }
1657 }
1658
1659 // For each of the output shuffles, we try to sort all the first vector
1660 // elements to the beginning, followed by the second array elements at the
1661 // end. If the binops are legalized to smaller vectors, this may reduce total
1662 // number of binops. We compute the ReconstructMask mask needed to convert
1663 // back to the original lane order.
1665 SmallVector<SmallVector<int>> OrigReconstructMasks;
1666 int MaxV1Elt = 0, MaxV2Elt = 0;
1667 unsigned NumElts = VT->getNumElements();
1668 for (ShuffleVectorInst *SVN : Shuffles) {
1670 SVN->getShuffleMask(Mask);
1671
1672 // Check the operands are the same as the original, or reversed (in which
1673 // case we need to commute the mask).
1674 Value *SVOp0 = SVN->getOperand(0);
1675 Value *SVOp1 = SVN->getOperand(1);
1676 if (isa<UndefValue>(SVOp1)) {
1677 auto *SSV = cast<ShuffleVectorInst>(SVOp0);
1678 SVOp0 = SSV->getOperand(0);
1679 SVOp1 = SSV->getOperand(1);
1680 for (unsigned I = 0, E = Mask.size(); I != E; I++) {
1681 if (Mask[I] >= static_cast<int>(SSV->getShuffleMask().size()))
1682 return false;
1683 Mask[I] = Mask[I] < 0 ? Mask[I] : SSV->getMaskValue(Mask[I]);
1684 }
1685 }
1686 if (SVOp0 == Op1 && SVOp1 == Op0) {
1687 std::swap(SVOp0, SVOp1);
1689 }
1690 if (SVOp0 != Op0 || SVOp1 != Op1)
1691 return false;
1692
1693 // Calculate the reconstruction mask for this shuffle, as the mask needed to
1694 // take the packed values from Op0/Op1 and reconstructing to the original
1695 // order.
1696 SmallVector<int> ReconstructMask;
1697 for (unsigned I = 0; I < Mask.size(); I++) {
1698 if (Mask[I] < 0) {
1699 ReconstructMask.push_back(-1);
1700 } else if (Mask[I] < static_cast<int>(NumElts)) {
1701 MaxV1Elt = std::max(MaxV1Elt, Mask[I]);
1702 auto It = find_if(V1, [&](const std::pair<int, int> &A) {
1703 return Mask[I] == A.first;
1704 });
1705 if (It != V1.end())
1706 ReconstructMask.push_back(It - V1.begin());
1707 else {
1708 ReconstructMask.push_back(V1.size());
1709 V1.emplace_back(Mask[I], V1.size());
1710 }
1711 } else {
1712 MaxV2Elt = std::max<int>(MaxV2Elt, Mask[I] - NumElts);
1713 auto It = find_if(V2, [&](const std::pair<int, int> &A) {
1714 return Mask[I] - static_cast<int>(NumElts) == A.first;
1715 });
1716 if (It != V2.end())
1717 ReconstructMask.push_back(NumElts + It - V2.begin());
1718 else {
1719 ReconstructMask.push_back(NumElts + V2.size());
1720 V2.emplace_back(Mask[I] - NumElts, NumElts + V2.size());
1721 }
1722 }
1723 }
1724
1725 // For reductions, we know that the lane ordering out doesn't alter the
1726 // result. In-order can help simplify the shuffle away.
1727 if (FromReduction)
1728 sort(ReconstructMask);
1729 OrigReconstructMasks.push_back(std::move(ReconstructMask));
1730 }
1731
1732 // If the Maximum element used from V1 and V2 are not larger than the new
1733 // vectors, the vectors are already packes and performing the optimization
1734 // again will likely not help any further. This also prevents us from getting
1735 // stuck in a cycle in case the costs do not also rule it out.
1736 if (V1.empty() || V2.empty() ||
1737 (MaxV1Elt == static_cast<int>(V1.size()) - 1 &&
1738 MaxV2Elt == static_cast<int>(V2.size()) - 1))
1739 return false;
1740
1741 // GetBaseMaskValue takes one of the inputs, which may either be a shuffle, a
1742 // shuffle of another shuffle, or not a shuffle (that is treated like a
1743 // identity shuffle).
1744 auto GetBaseMaskValue = [&](Instruction *I, int M) {
1745 auto *SV = dyn_cast<ShuffleVectorInst>(I);
1746 if (!SV)
1747 return M;
1748 if (isa<UndefValue>(SV->getOperand(1)))
1749 if (auto *SSV = dyn_cast<ShuffleVectorInst>(SV->getOperand(0)))
1750 if (InputShuffles.contains(SSV))
1751 return SSV->getMaskValue(SV->getMaskValue(M));
1752 return SV->getMaskValue(M);
1753 };
1754
1755 // Attempt to sort the inputs my ascending mask values to make simpler input
1756 // shuffles and push complex shuffles down to the uses. We sort on the first
1757 // of the two input shuffle orders, to try and get at least one input into a
1758 // nice order.
1759 auto SortBase = [&](Instruction *A, std::pair<int, int> X,
1760 std::pair<int, int> Y) {
1761 int MXA = GetBaseMaskValue(A, X.first);
1762 int MYA = GetBaseMaskValue(A, Y.first);
1763 return MXA < MYA;
1764 };
1765 stable_sort(V1, [&](std::pair<int, int> A, std::pair<int, int> B) {
1766 return SortBase(SVI0A, A, B);
1767 });
1768 stable_sort(V2, [&](std::pair<int, int> A, std::pair<int, int> B) {
1769 return SortBase(SVI1A, A, B);
1770 });
1771 // Calculate our ReconstructMasks from the OrigReconstructMasks and the
1772 // modified order of the input shuffles.
1773 SmallVector<SmallVector<int>> ReconstructMasks;
1774 for (const auto &Mask : OrigReconstructMasks) {
1775 SmallVector<int> ReconstructMask;
1776 for (int M : Mask) {
1777 auto FindIndex = [](const SmallVector<std::pair<int, int>> &V, int M) {
1778 auto It = find_if(V, [M](auto A) { return A.second == M; });
1779 assert(It != V.end() && "Expected all entries in Mask");
1780 return std::distance(V.begin(), It);
1781 };
1782 if (M < 0)
1783 ReconstructMask.push_back(-1);
1784 else if (M < static_cast<int>(NumElts)) {
1785 ReconstructMask.push_back(FindIndex(V1, M));
1786 } else {
1787 ReconstructMask.push_back(NumElts + FindIndex(V2, M));
1788 }
1789 }
1790 ReconstructMasks.push_back(std::move(ReconstructMask));
1791 }
1792
1793 // Calculate the masks needed for the new input shuffles, which get padded
1794 // with undef
1795 SmallVector<int> V1A, V1B, V2A, V2B;
1796 for (unsigned I = 0; I < V1.size(); I++) {
1797 V1A.push_back(GetBaseMaskValue(SVI0A, V1[I].first));
1798 V1B.push_back(GetBaseMaskValue(SVI0B, V1[I].first));
1799 }
1800 for (unsigned I = 0; I < V2.size(); I++) {
1801 V2A.push_back(GetBaseMaskValue(SVI1A, V2[I].first));
1802 V2B.push_back(GetBaseMaskValue(SVI1B, V2[I].first));
1803 }
1804 while (V1A.size() < NumElts) {
1807 }
1808 while (V2A.size() < NumElts) {
1811 }
1812
1813 auto AddShuffleCost = [&](InstructionCost C, Instruction *I) {
1814 auto *SV = dyn_cast<ShuffleVectorInst>(I);
1815 if (!SV)
1816 return C;
1817 return C + TTI.getShuffleCost(isa<UndefValue>(SV->getOperand(1))
1820 VT, SV->getShuffleMask());
1821 };
1822 auto AddShuffleMaskCost = [&](InstructionCost C, ArrayRef<int> Mask) {
1823 return C + TTI.getShuffleCost(TTI::SK_PermuteTwoSrc, VT, Mask);
1824 };
1825
1826 // Get the costs of the shuffles + binops before and after with the new
1827 // shuffle masks.
1828 InstructionCost CostBefore =
1829 TTI.getArithmeticInstrCost(Op0->getOpcode(), VT) +
1830 TTI.getArithmeticInstrCost(Op1->getOpcode(), VT);
1831 CostBefore += std::accumulate(Shuffles.begin(), Shuffles.end(),
1832 InstructionCost(0), AddShuffleCost);
1833 CostBefore += std::accumulate(InputShuffles.begin(), InputShuffles.end(),
1834 InstructionCost(0), AddShuffleCost);
1835
1836 // The new binops will be unused for lanes past the used shuffle lengths.
1837 // These types attempt to get the correct cost for that from the target.
1838 FixedVectorType *Op0SmallVT =
1839 FixedVectorType::get(VT->getScalarType(), V1.size());
1840 FixedVectorType *Op1SmallVT =
1841 FixedVectorType::get(VT->getScalarType(), V2.size());
1842 InstructionCost CostAfter =
1843 TTI.getArithmeticInstrCost(Op0->getOpcode(), Op0SmallVT) +
1844 TTI.getArithmeticInstrCost(Op1->getOpcode(), Op1SmallVT);
1845 CostAfter += std::accumulate(ReconstructMasks.begin(), ReconstructMasks.end(),
1846 InstructionCost(0), AddShuffleMaskCost);
1847 std::set<SmallVector<int>> OutputShuffleMasks({V1A, V1B, V2A, V2B});
1848 CostAfter +=
1849 std::accumulate(OutputShuffleMasks.begin(), OutputShuffleMasks.end(),
1850 InstructionCost(0), AddShuffleMaskCost);
1851
1852 LLVM_DEBUG(dbgs() << "Found a binop select shuffle pattern: " << I << "\n");
1853 LLVM_DEBUG(dbgs() << " CostBefore: " << CostBefore
1854 << " vs CostAfter: " << CostAfter << "\n");
1855 if (CostBefore <= CostAfter)
1856 return false;
1857
1858 // The cost model has passed, create the new instructions.
1859 auto GetShuffleOperand = [&](Instruction *I, unsigned Op) -> Value * {
1860 auto *SV = dyn_cast<ShuffleVectorInst>(I);
1861 if (!SV)
1862 return I;
1863 if (isa<UndefValue>(SV->getOperand(1)))
1864 if (auto *SSV = dyn_cast<ShuffleVectorInst>(SV->getOperand(0)))
1865 if (InputShuffles.contains(SSV))
1866 return SSV->getOperand(Op);
1867 return SV->getOperand(Op);
1868 };
1869 Builder.SetInsertPoint(*SVI0A->getInsertionPointAfterDef());
1870 Value *NSV0A = Builder.CreateShuffleVector(GetShuffleOperand(SVI0A, 0),
1871 GetShuffleOperand(SVI0A, 1), V1A);
1872 Builder.SetInsertPoint(*SVI0B->getInsertionPointAfterDef());
1873 Value *NSV0B = Builder.CreateShuffleVector(GetShuffleOperand(SVI0B, 0),
1874 GetShuffleOperand(SVI0B, 1), V1B);
1875 Builder.SetInsertPoint(*SVI1A->getInsertionPointAfterDef());
1876 Value *NSV1A = Builder.CreateShuffleVector(GetShuffleOperand(SVI1A, 0),
1877 GetShuffleOperand(SVI1A, 1), V2A);
1878 Builder.SetInsertPoint(*SVI1B->getInsertionPointAfterDef());
1879 Value *NSV1B = Builder.CreateShuffleVector(GetShuffleOperand(SVI1B, 0),
1880 GetShuffleOperand(SVI1B, 1), V2B);
1881 Builder.SetInsertPoint(Op0);
1882 Value *NOp0 = Builder.CreateBinOp((Instruction::BinaryOps)Op0->getOpcode(),
1883 NSV0A, NSV0B);
1884 if (auto *I = dyn_cast<Instruction>(NOp0))
1885 I->copyIRFlags(Op0, true);
1886 Builder.SetInsertPoint(Op1);
1887 Value *NOp1 = Builder.CreateBinOp((Instruction::BinaryOps)Op1->getOpcode(),
1888 NSV1A, NSV1B);
1889 if (auto *I = dyn_cast<Instruction>(NOp1))
1890 I->copyIRFlags(Op1, true);
1891
1892 for (int S = 0, E = ReconstructMasks.size(); S != E; S++) {
1893 Builder.SetInsertPoint(Shuffles[S]);
1894 Value *NSV = Builder.CreateShuffleVector(NOp0, NOp1, ReconstructMasks[S]);
1895 replaceValue(*Shuffles[S], *NSV);
1896 }
1897
1898 Worklist.pushValue(NSV0A);
1899 Worklist.pushValue(NSV0B);
1900 Worklist.pushValue(NSV1A);
1901 Worklist.pushValue(NSV1B);
1902 for (auto *S : Shuffles)
1903 Worklist.add(S);
1904 return true;
1905}
1906
1907/// This is the entry point for all transforms. Pass manager differences are
1908/// handled in the callers of this function.
1909bool VectorCombine::run() {
1911 return false;
1912
1913 // Don't attempt vectorization if the target does not support vectors.
1914 if (!TTI.getNumberOfRegisters(TTI.getRegisterClassForType(/*Vector*/ true)))
1915 return false;
1916
1917 bool MadeChange = false;
1918 auto FoldInst = [this, &MadeChange](Instruction &I) {
1919 Builder.SetInsertPoint(&I);
1920 bool IsFixedVectorType = isa<FixedVectorType>(I.getType());
1921 auto Opcode = I.getOpcode();
1922
1923 // These folds should be beneficial regardless of when this pass is run
1924 // in the optimization pipeline.
1925 // The type checking is for run-time efficiency. We can avoid wasting time
1926 // dispatching to folding functions if there's no chance of matching.
1927 if (IsFixedVectorType) {
1928 switch (Opcode) {
1929 case Instruction::InsertElement:
1930 MadeChange |= vectorizeLoadInsert(I);
1931 break;
1932 case Instruction::ShuffleVector:
1933 MadeChange |= widenSubvectorLoad(I);
1934 break;
1935 default:
1936 break;
1937 }
1938 }
1939
1940 // This transform works with scalable and fixed vectors
1941 // TODO: Identify and allow other scalable transforms
1942 if (isa<VectorType>(I.getType())) {
1943 MadeChange |= scalarizeBinopOrCmp(I);
1944 MadeChange |= scalarizeLoadExtract(I);
1945 MadeChange |= scalarizeVPIntrinsic(I);
1946 }
1947
1948 if (Opcode == Instruction::Store)
1949 MadeChange |= foldSingleElementStore(I);
1950
1951 // If this is an early pipeline invocation of this pass, we are done.
1952 if (TryEarlyFoldsOnly)
1953 return;
1954
1955 // Otherwise, try folds that improve codegen but may interfere with
1956 // early IR canonicalizations.
1957 // The type checking is for run-time efficiency. We can avoid wasting time
1958 // dispatching to folding functions if there's no chance of matching.
1959 if (IsFixedVectorType) {
1960 switch (Opcode) {
1961 case Instruction::InsertElement:
1962 MadeChange |= foldInsExtFNeg(I);
1963 break;
1964 case Instruction::ShuffleVector:
1965 MadeChange |= foldShuffleOfBinops(I);
1966 MadeChange |= foldSelectShuffle(I);
1967 break;
1968 case Instruction::BitCast:
1969 MadeChange |= foldBitcastShuffle(I);
1970 break;
1971 }
1972 } else {
1973 switch (Opcode) {
1974 case Instruction::Call:
1975 MadeChange |= foldShuffleFromReductions(I);
1976 MadeChange |= foldTruncFromReductions(I);
1977 break;
1978 case Instruction::ICmp:
1979 case Instruction::FCmp:
1980 MadeChange |= foldExtractExtract(I);
1981 break;
1982 default:
1983 if (Instruction::isBinaryOp(Opcode)) {
1984 MadeChange |= foldExtractExtract(I);
1985 MadeChange |= foldExtractedCmps(I);
1986 }
1987 break;
1988 }
1989 }
1990 };
1991
1992 for (BasicBlock &BB : F) {
1993 // Ignore unreachable basic blocks.
1994 if (!DT.isReachableFromEntry(&BB))
1995 continue;
1996 // Use early increment range so that we can erase instructions in loop.
1997 for (Instruction &I : make_early_inc_range(BB)) {
1998 if (I.isDebugOrPseudoInst())
1999 continue;
2000 FoldInst(I);
2001 }
2002 }
2003
2004 while (!Worklist.isEmpty()) {
2005 Instruction *I = Worklist.removeOne();
2006 if (!I)
2007 continue;
2008
2011 continue;
2012 }
2013
2014 FoldInst(*I);
2015 }
2016
2017 return MadeChange;
2018}
2019
2022 auto &AC = FAM.getResult<AssumptionAnalysis>(F);
2026 VectorCombine Combiner(F, TTI, DT, AA, AC, TryEarlyFoldsOnly);
2027 if (!Combiner.run())
2028 return PreservedAnalyses::all();
2031 return PA;
2032}
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 GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
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:1290
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:173
BinaryOps getOpcode() const
Definition: InstrTypes.h:402
Represents analyses that only rely on functions' control flow.
Definition: Analysis.h:70
Value * getArgOperand(unsigned i) const
Definition: InstrTypes.h:1426
iterator_range< User::op_iterator > args()
Iteration adapter for range-for loops.
Definition: InstrTypes.h:1417
static Type * makeCmpResultType(Type *opnd_type)
Create a result type for fcmp/icmp.
Definition: InstrTypes.h:1127
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:780
bool isFPPredicate() const
Definition: InstrTypes.h:887
Combiner implementation.
Definition: Combiner.h:34
static Constant * getExtractElement(Constant *Vec, Constant *Idx, Type *OnlyIfReducedTy=nullptr)
Definition: Constants.cpp:2454
This is the shared class of boolean and integer constants.
Definition: Constants.h:79
const APInt & getValue() const
Return the constant as an APInt value reference.
Definition: Constants.h:144
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:275
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:2006
Value * CreateInsertElement(Type *VecTy, Value *NewElt, Value *Idx, const Twine &Name="")
Definition: IRBuilder.h:2455
Value * CreateExtractElement(Value *Vec, Value *Idx, const Twine &Name="")
Definition: IRBuilder.h:2443
LoadInst * CreateAlignedLoad(Type *Ty, Value *Ptr, MaybeAlign Align, const char *Name)
Definition: IRBuilder.h:1806
Value * CreateVectorSplat(unsigned NumElts, Value *V, const Twine &Name="")
Return a vector value that contains.
Definition: IRBuilder.cpp:1212
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:930
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:1739
Value * CreateFreeze(Value *V, const Twine &Name="")
Definition: IRBuilder.h:2518
Value * CreateInBoundsGEP(Type *Ty, Value *Ptr, ArrayRef< Value * > IdxList, const Twine &Name="")
Definition: IRBuilder.h:1875
Value * CreatePointerBitCastOrAddrSpaceCast(Value *V, Type *DestTy, const Twine &Name="")
Definition: IRBuilder.h:2165
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:2349
Value * CreateBitCast(Value *V, Type *DestTy, const Twine &Name="")
Definition: IRBuilder.h:2110
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:1789
Value * CreateShuffleVector(Value *V1, Value *V2, Value *Mask, const Twine &Name="")
Definition: IRBuilder.h:2477
StoreInst * CreateStore(Value *Val, Value *Ptr, bool isVolatile=false)
Definition: IRBuilder.h:1802
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:2649
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.
const Module * getModule() const
Return the module owning the function this instruction belongs to or nullptr it the function does not...
Definition: Instruction.cpp:71
bool isBinaryOp() const
Definition: Instruction.h:255
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:178
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.
const DataLayout & getDataLayout() const
Get the data layout for the module's target platform.
Definition: Module.h:275
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:302
void setAlignment(Align Align)
Definition: Instructions.h:358
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
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
@ 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)
specific_intval< false > m_SpecificInt(APInt V)
Match a specific integer value or vector with all elements equal to the value.
Definition: PatternMatch.h:862
class_match< BinaryOperator > m_BinOp()
Match an arbitrary binary operation and ignore it.
Definition: PatternMatch.h:84
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:144
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:724
specificval_ty m_Specific(const Value *V)
Match if we have a specific specified value.
Definition: PatternMatch.h:780
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:147
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:224
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:532
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:89
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:76
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:136
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:1975
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:920
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