1//===- InstCombineVectorOps.cpp -------------------------------------------===//
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 file implements instcombine for ExtractElement, InsertElement and
10// ShuffleVector.
11//
12//===----------------------------------------------------------------------===//
13
14#include "InstCombineInternal.h"
15#include "llvm/ADT/APInt.h"
16#include "llvm/ADT/ArrayRef.h"
17#include "llvm/ADT/DenseMap.h"
18#include "llvm/ADT/STLExtras.h"
19#include "llvm/ADT/SmallBitVector.h"
20#include "llvm/ADT/SmallVector.h"
21#include "llvm/ADT/Statistic.h"
22#include "llvm/Analysis/InstructionSimplify.h"
23#include "llvm/Analysis/VectorUtils.h"
24#include "llvm/IR/BasicBlock.h"
25#include "llvm/IR/Constant.h"
26#include "llvm/IR/Constants.h"
27#include "llvm/IR/DerivedTypes.h"
28#include "llvm/IR/InstrTypes.h"
29#include "llvm/IR/Instruction.h"
30#include "llvm/IR/Instructions.h"
31#include "llvm/IR/Operator.h"
32#include "llvm/IR/PatternMatch.h"
33#include "llvm/IR/Type.h"
34#include "llvm/IR/User.h"
35#include "llvm/IR/Value.h"
36#include "llvm/Support/Casting.h"
37#include "llvm/Support/ErrorHandling.h"
38#include "llvm/Transforms/InstCombine/InstCombiner.h"
39#include <cassert>
40#include <cstdint>
41#include <iterator>
42#include <utility>
43
44#define DEBUG_TYPE "instcombine"
45
46using namespace llvm;
47using namespace PatternMatch;
48
49STATISTIC(NumAggregateReconstructionsSimplified,
50 "Number of aggregate reconstructions turned into reuse of the "
51 "original aggregate");
52
53/// Return true if the value is cheaper to scalarize than it is to leave as a
54/// vector operation. If the extract index \p EI is a constant integer then
55/// some operations may be cheap to scalarize.
56///
57/// FIXME: It's possible to create more instructions than previously existed.
58static bool cheapToScalarize(Value *V, Value *EI) {
59 ConstantInt *CEI = dyn_cast<ConstantInt>(Val: EI);
60
61 // If we can pick a scalar constant value out of a vector, that is free.
62 if (auto *C = dyn_cast<Constant>(Val: V))
63 return CEI || C->getSplatValue();
64
65 if (CEI && match(V, P: m_Intrinsic<Intrinsic::stepvector>())) {
66 ElementCount EC = cast<VectorType>(Val: V->getType())->getElementCount();
67 // Index needs to be lower than the minimum size of the vector, because
68 // for scalable vector, the vector size is known at run time.
69 return CEI->getValue().ult(RHS: EC.getKnownMinValue());
70 }
71
72 // An insertelement to the same constant index as our extract will simplify
73 // to the scalar inserted element. An insertelement to a different constant
74 // index is irrelevant to our extract.
75 if (match(V, P: m_InsertElt(Val: m_Value(), Elt: m_Value(), Idx: m_ConstantInt())))
76 return CEI;
77
78 if (match(V, P: m_OneUse(SubPattern: m_Load(Op: m_Value()))))
79 return true;
80
81 if (match(V, P: m_OneUse(SubPattern: m_UnOp())))
82 return true;
83
84 Value *V0, *V1;
85 if (match(V, P: m_OneUse(SubPattern: m_BinOp(L: m_Value(V&: V0), R: m_Value(V&: V1)))))
86 if (cheapToScalarize(V: V0, EI) || cheapToScalarize(V: V1, EI))
87 return true;
88
89 CmpPredicate UnusedPred;
90 if (match(V, P: m_OneUse(SubPattern: m_Cmp(Pred&: UnusedPred, L: m_Value(V&: V0), R: m_Value(V&: V1)))))
91 if (cheapToScalarize(V: V0, EI) || cheapToScalarize(V: V1, EI))
92 return true;
93
94 return false;
95}
96
97// If we have a PHI node with a vector type that is only used to feed
98// itself and be an operand of extractelement at a constant location,
99// try to replace the PHI of the vector type with a PHI of a scalar type.
100Instruction *InstCombinerImpl::scalarizePHI(ExtractElementInst &EI,
101 PHINode *PN) {
102 SmallVector<Instruction *, 2> Extracts;
103 // The users we want the PHI to have are:
104 // 1) The EI ExtractElement (we already know this)
105 // 2) Possibly more ExtractElements with the same index.
106 // 3) Another operand, which will feed back into the PHI.
107 Instruction *PHIUser = nullptr;
108 for (auto *U : PN->users()) {
109 if (ExtractElementInst *EU = dyn_cast<ExtractElementInst>(Val: U)) {
110 if (EI.getIndexOperand() == EU->getIndexOperand())
111 Extracts.push_back(Elt: EU);
112 else
113 return nullptr;
114 } else if (!PHIUser) {
115 PHIUser = cast<Instruction>(Val: U);
116 } else {
117 return nullptr;
118 }
119 }
120
121 if (!PHIUser)
122 return nullptr;
123
124 // Verify that this PHI user has one use, which is the PHI itself,
125 // and that it is a binary operation which is cheap to scalarize.
126 // otherwise return nullptr.
127 if (!PHIUser->hasOneUse() || !(PHIUser->user_back() == PN) ||
128 !(isa<BinaryOperator>(Val: PHIUser)) ||
129 !cheapToScalarize(V: PHIUser, EI: EI.getIndexOperand()))
130 return nullptr;
131
132 // Create a scalar PHI node that will replace the vector PHI node
133 // just before the current PHI node.
134 PHINode *scalarPHI = cast<PHINode>(Val: InsertNewInstWith(
135 New: PHINode::Create(Ty: EI.getType(), NumReservedValues: PN->getNumIncomingValues(), NameStr: ""), Old: PN->getIterator()));
136 // Scalarize each PHI operand. A switch may produce multiple edges from the
137 // same predecessor; reuse the scalar instruction for duplicate edges.
138 SmallDenseMap<BasicBlock *, Value *, 4> ScalarizedValues;
139 for (unsigned i = 0; i < PN->getNumIncomingValues(); i++) {
140 Value *PHIInVal = PN->getIncomingValue(i);
141 BasicBlock *inBB = PN->getIncomingBlock(i);
142 Value *Elt = EI.getIndexOperand();
143
144 // Reuse scalar value for duplicate edges from the same predecessor.
145 if (Value *Existing = ScalarizedValues.lookup(Val: inBB)) {
146 scalarPHI->addIncoming(V: Existing, BB: inBB);
147 continue;
148 }
149
150 Value *ScalarVal;
151 // If the operand is the PHI induction variable:
152 if (PHIInVal == PHIUser) {
153 // Scalarize the binary operation. One operand is the
154 // scalar PHI, and the other is extracted from the other
155 // vector operand.
156 BinaryOperator *B0 = cast<BinaryOperator>(Val: PHIUser);
157 unsigned opId = (B0->getOperand(i_nocapture: 0) == PN) ? 1 : 0;
158 Value *Op = InsertNewInstWith(
159 New: ExtractElementInst::Create(Vec: B0->getOperand(i_nocapture: opId), Idx: Elt,
160 NameStr: B0->getOperand(i_nocapture: opId)->getName() + ".Elt"),
161 Old: B0->getIterator());
162 // Preserve operand order for binary operation to preserve semantics of
163 // non-commutative operations.
164 Value *FirstOp = (B0->getOperand(i_nocapture: 0) == PN) ? scalarPHI : Op;
165 Value *SecondOp = (B0->getOperand(i_nocapture: 0) == PN) ? Op : scalarPHI;
166 ScalarVal = InsertNewInstWith(New: BinaryOperator::CreateWithCopiedFlags(
167 Opc: B0->getOpcode(), V1: FirstOp, V2: SecondOp, CopyO: B0),
168 Old: B0->getIterator());
169 } else {
170 // Scalarize PHI input:
171 Instruction *newEI = ExtractElementInst::Create(Vec: PHIInVal, Idx: Elt, NameStr: "");
172 // Insert the new instruction into the predecessor basic block.
173 Instruction *pos = dyn_cast<Instruction>(Val: PHIInVal);
174 BasicBlock::iterator InsertPos;
175 if (pos && !isa<PHINode>(Val: pos)) {
176 InsertPos = ++pos->getIterator();
177 } else {
178 InsertPos = inBB->getFirstInsertionPt();
179 }
180
181 ScalarVal = InsertNewInstWith(New: newEI, Old: InsertPos);
182 }
183
184 ScalarizedValues[inBB] = ScalarVal;
185 scalarPHI->addIncoming(V: ScalarVal, BB: inBB);
186 }
187
188 for (auto *E : Extracts) {
189 replaceInstUsesWith(I&: *E, V: scalarPHI);
190 // Add old extract to worklist for DCE.
191 addToWorklist(I: E);
192 }
193
194 return &EI;
195}
196
197Instruction *InstCombinerImpl::foldBitcastExtElt(ExtractElementInst &Ext) {
198 Value *X;
199 uint64_t ExtIndexC;
200 if (!match(V: Ext.getVectorOperand(), P: m_BitCast(Op: m_Value(V&: X))) ||
201 !match(V: Ext.getIndexOperand(), P: m_ConstantInt(V&: ExtIndexC)))
202 return nullptr;
203
204 ElementCount NumElts =
205 cast<VectorType>(Val: Ext.getVectorOperandType())->getElementCount();
206 Type *DestTy = Ext.getType();
207 unsigned DestWidth = DestTy->getPrimitiveSizeInBits();
208 bool IsBigEndian = DL.isBigEndian();
209
210 // If we are casting an integer to vector and extracting a portion, that is
211 // a shift-right and truncate.
212 if (X->getType()->isIntegerTy()) {
213 assert(isa<FixedVectorType>(Ext.getVectorOperand()->getType()) &&
214 "Expected fixed vector type for bitcast from scalar integer");
215
216 // Big endian requires adjusting the extract index since MSB is at index 0.
217 // LittleEndian: extelt (bitcast i32 X to v4i8), 0 -> trunc i32 X to i8
218 // BigEndian: extelt (bitcast i32 X to v4i8), 0 -> trunc i32 (X >> 24) to i8
219 if (IsBigEndian)
220 ExtIndexC = NumElts.getKnownMinValue() - 1 - ExtIndexC;
221 unsigned ShiftAmountC = ExtIndexC * DestWidth;
222 if ((!ShiftAmountC ||
223 isDesirableIntType(BitWidth: X->getType()->getPrimitiveSizeInBits())) &&
224 Ext.getVectorOperand()->hasOneUse()) {
225 if (ShiftAmountC)
226 X = Builder.CreateLShr(LHS: X, RHS: ShiftAmountC, Name: "extelt.offset");
227 if (DestTy->isFloatingPointTy()) {
228 Type *DstIntTy = IntegerType::getIntNTy(C&: X->getContext(), N: DestWidth);
229 Value *Trunc = Builder.CreateTrunc(V: X, DestTy: DstIntTy);
230 return new BitCastInst(Trunc, DestTy);
231 }
232 return new TruncInst(X, DestTy);
233 }
234 }
235
236 if (!X->getType()->isVectorTy())
237 return nullptr;
238
239 // If this extractelement is using a bitcast from a vector of the same number
240 // of elements, see if we can find the source element from the source vector:
241 // extelt (bitcast VecX), IndexC --> bitcast X[IndexC]
242 auto *SrcTy = cast<VectorType>(Val: X->getType());
243 ElementCount NumSrcElts = SrcTy->getElementCount();
244 if (NumSrcElts == NumElts)
245 if (Value *Elt = findScalarElement(V: X, EltNo: ExtIndexC))
246 return new BitCastInst(Elt, DestTy);
247
248 assert(NumSrcElts.isScalable() == NumElts.isScalable() &&
249 "Src and Dst must be the same sort of vector type");
250
251 // If the source elements are wider than the destination, try to shift and
252 // truncate a subset of scalar bits of an insert op.
253 if (NumSrcElts.getKnownMinValue() < NumElts.getKnownMinValue()) {
254 Value *Scalar;
255 Value *Vec;
256 uint64_t InsIndexC;
257 if (!match(V: X, P: m_InsertElt(Val: m_Value(V&: Vec), Elt: m_Value(V&: Scalar),
258 Idx: m_ConstantInt(V&: InsIndexC))))
259 return nullptr;
260
261 // The extract must be from the subset of vector elements that we inserted
262 // into. Example: if we inserted element 1 of a <2 x i64> and we are
263 // extracting an i16 (narrowing ratio = 4), then this extract must be from 1
264 // of elements 4-7 of the bitcasted vector.
265 unsigned NarrowingRatio =
266 NumElts.getKnownMinValue() / NumSrcElts.getKnownMinValue();
267
268 if (ExtIndexC / NarrowingRatio != InsIndexC) {
269 // Remove insertelement, if we don't use the inserted element.
270 // extractelement (bitcast (insertelement (Vec, b)), a) ->
271 // extractelement (bitcast (Vec), a)
272 // FIXME: this should be removed to SimplifyDemandedVectorElts,
273 // once scale vectors are supported.
274 if (X->hasOneUse() && Ext.getVectorOperand()->hasOneUse()) {
275 Value *NewBC = Builder.CreateBitCast(V: Vec, DestTy: Ext.getVectorOperandType());
276 return ExtractElementInst::Create(Vec: NewBC, Idx: Ext.getIndexOperand());
277 }
278 return nullptr;
279 }
280
281 // We are extracting part of the original scalar. How that scalar is
282 // inserted into the vector depends on the endian-ness. Example:
283 // Vector Byte Elt Index: 0 1 2 3 4 5 6 7
284 // +--+--+--+--+--+--+--+--+
285 // inselt <2 x i32> V, <i32> S, 1: |V0|V1|V2|V3|S0|S1|S2|S3|
286 // extelt <4 x i16> V', 3: | |S2|S3|
287 // +--+--+--+--+--+--+--+--+
288 // If this is little-endian, S2|S3 are the MSB of the 32-bit 'S' value.
289 // If this is big-endian, S2|S3 are the LSB of the 32-bit 'S' value.
290 // In this example, we must right-shift little-endian. Big-endian is just a
291 // truncate.
292 unsigned Chunk = ExtIndexC % NarrowingRatio;
293 if (IsBigEndian)
294 Chunk = NarrowingRatio - 1 - Chunk;
295
296 // Bail out if this is an FP vector to FP vector sequence. That would take
297 // more instructions than we started with unless there is no shift, and it
298 // may not be handled as well in the backend.
299 bool NeedSrcBitcast = SrcTy->getScalarType()->isFloatingPointTy();
300 bool NeedDestBitcast = DestTy->isFloatingPointTy();
301 if (NeedSrcBitcast && NeedDestBitcast)
302 return nullptr;
303
304 unsigned SrcWidth = SrcTy->getScalarSizeInBits();
305 unsigned ShAmt = Chunk * DestWidth;
306
307 // TODO: This limitation is more strict than necessary. We could sum the
308 // number of new instructions and subtract the number eliminated to know if
309 // we can proceed.
310 if (!X->hasOneUse() || !Ext.getVectorOperand()->hasOneUse())
311 if (NeedSrcBitcast || NeedDestBitcast)
312 return nullptr;
313
314 if (NeedSrcBitcast) {
315 Type *SrcIntTy = IntegerType::getIntNTy(C&: Scalar->getContext(), N: SrcWidth);
316 Scalar = Builder.CreateBitCast(V: Scalar, DestTy: SrcIntTy);
317 }
318
319 if (ShAmt) {
320 // Bail out if we could end with more instructions than we started with.
321 if (!Ext.getVectorOperand()->hasOneUse())
322 return nullptr;
323 Scalar = Builder.CreateLShr(LHS: Scalar, RHS: ShAmt);
324 }
325
326 if (NeedDestBitcast) {
327 Type *DestIntTy = IntegerType::getIntNTy(C&: Scalar->getContext(), N: DestWidth);
328 return new BitCastInst(Builder.CreateTrunc(V: Scalar, DestTy: DestIntTy), DestTy);
329 }
330 return new TruncInst(Scalar, DestTy);
331 }
332
333 return nullptr;
334}
335
336/// Find elements of V demanded by UserInstr. If returns false, we were not able
337/// to determine all elements.
338static bool findDemandedEltsBySingleUser(Value *V, Instruction *UserInstr,
339 APInt &UnionUsedElts) {
340 unsigned VWidth = cast<FixedVectorType>(Val: V->getType())->getNumElements();
341
342 switch (UserInstr->getOpcode()) {
343 case Instruction::ExtractElement: {
344 ExtractElementInst *EEI = cast<ExtractElementInst>(Val: UserInstr);
345 assert(EEI->getVectorOperand() == V);
346 ConstantInt *EEIIndexC = dyn_cast<ConstantInt>(Val: EEI->getIndexOperand());
347 if (EEIIndexC && EEIIndexC->getValue().ult(RHS: VWidth)) {
348 UnionUsedElts.setBit(EEIIndexC->getZExtValue());
349 return true;
350 }
351 break;
352 }
353 case Instruction::ShuffleVector: {
354 ShuffleVectorInst *Shuffle = cast<ShuffleVectorInst>(Val: UserInstr);
355 unsigned MaskNumElts =
356 cast<FixedVectorType>(Val: UserInstr->getType())->getNumElements();
357
358 for (auto I : llvm::seq(Size: MaskNumElts)) {
359 unsigned MaskVal = Shuffle->getMaskValue(Elt: I);
360 if (MaskVal == -1u || MaskVal >= 2 * VWidth)
361 continue;
362 if (Shuffle->getOperand(i_nocapture: 0) == V && (MaskVal < VWidth))
363 UnionUsedElts.setBit(MaskVal);
364 if (Shuffle->getOperand(i_nocapture: 1) == V &&
365 ((MaskVal >= VWidth) && (MaskVal < 2 * VWidth)))
366 UnionUsedElts.setBit(MaskVal - VWidth);
367 }
368 return true;
369 }
370 default:
371 break;
372 }
373
374 return false;
375}
376
377/// Find union of elements of V demanded by all its users.
378/// If it is known by querying findDemandedEltsBySingleUser that
379/// no user demands an element of V, then the corresponding bit
380/// remains unset in the returned value.
381static APInt findDemandedEltsByAllUsers(Value *V) {
382 unsigned VWidth = cast<FixedVectorType>(Val: V->getType())->getNumElements();
383
384 APInt UnionUsedElts(VWidth, 0);
385 for (const Use &U : V->uses()) {
386 if (Instruction *I = dyn_cast<Instruction>(Val: U.getUser())) {
387 if (!findDemandedEltsBySingleUser(V, UserInstr: I, UnionUsedElts))
388 return APInt::getAllOnes(numBits: VWidth);
389 } else {
390 UnionUsedElts = APInt::getAllOnes(numBits: VWidth);
391 break;
392 }
393
394 if (UnionUsedElts.isAllOnes())
395 break;
396 }
397
398 return UnionUsedElts;
399}
400
401/// Given a constant index for a extractelement or insertelement instruction,
402/// return it with the canonical type if it isn't already canonical. We
403/// arbitrarily pick 64 bit as our canonical type. The actual bitwidth doesn't
404/// matter, we just want a consistent type to simplify CSE.
405static ConstantInt *getPreferredVectorIndex(ConstantInt *IndexC) {
406 const unsigned IndexBW = IndexC->getBitWidth();
407 if (IndexBW == 64 || IndexC->getValue().getActiveBits() > 64)
408 return nullptr;
409 return ConstantInt::get(Context&: IndexC->getContext(),
410 V: IndexC->getValue().zextOrTrunc(width: 64));
411}
412
413/// Fold a variable extract from a vector of pointers that all point into the
414/// same object at a constant stride
415static Value *
416foldExtractOfStridedPointerVector(ExtractElementInst &EI,
417 InstCombiner::BuilderTy &Builder,
418 const DataLayout &DL) {
419 auto *VecTy = dyn_cast<FixedVectorType>(Val: EI.getVectorOperandType());
420 if (!VecTy || !VecTy->getElementType()->isPointerTy())
421 return nullptr;
422
423 unsigned NumElts = VecTy->getNumElements();
424 if (NumElts < 2)
425 return nullptr;
426
427 // Every lane must resolve to the same base pointer plus a constant byte
428 // offset. findScalarElement returns poison for a lane the vector never
429 // defines; that poison is its own base, so a vector mixing defined and
430 // undefined lanes fails the base comparison below.
431 unsigned IdxWidth = DL.getIndexTypeSizeInBits(Ty: VecTy->getElementType());
432 Value *Base = nullptr;
433 SmallVector<APInt> Offsets;
434 for (unsigned I = 0; I != NumElts; ++I) {
435 Value *Elt = findScalarElement(V: EI.getVectorOperand(), EltNo: I);
436 if (!Elt)
437 return nullptr;
438 Value *EltBase;
439 const APInt *C;
440 APInt Offset(IdxWidth, 0);
441 // m_Value may bind even when the offset is not constant, so reset it.
442 if (match(V: Elt, P: m_PtrAdd(PointerOp: m_Value(V&: EltBase), OffsetOp: m_APInt(Res&: C))))
443 Offset = C->sextOrTrunc(width: IdxWidth);
444 else
445 EltBase = Elt;
446 if (I == 0)
447 Base = EltBase;
448 else if (Base != EltBase)
449 return nullptr;
450 Offsets.push_back(Elt: Offset);
451 }
452
453 // The offsets must form an arithmetic sequence.
454 APInt Stride = Offsets[1] - Offsets[0];
455 for (unsigned I = 1; I != NumElts; ++I)
456 if (Offsets[I] - Offsets[0] != Stride * I)
457 return nullptr;
458
459 // Index off the common base, not off element 0: an element may be poison in
460 // a lane the extract never selects. The base is an operand of every element
461 // and the new GEPs have no flags, so the result is never more poisonous.
462 Type *IdxTy = DL.getIndexType(PtrTy: VecTy->getElementType());
463 Value *Idx = Builder.CreateZExtOrTrunc(V: EI.getIndexOperand(), DestTy: IdxTy);
464 Value *Ptr = Builder.CreatePtrAdd(
465 Ptr: Base, Offset: Builder.CreateMul(LHS: Idx, RHS: ConstantInt::get(Ty: IdxTy, V: Stride)));
466 return Builder.CreatePtrAdd(Ptr, Offset: ConstantInt::get(Ty: IdxTy, V: Offsets[0]));
467}
468
469Instruction *InstCombinerImpl::visitExtractElementInst(ExtractElementInst &EI) {
470 Value *SrcVec = EI.getVectorOperand();
471 Value *Index = EI.getIndexOperand();
472 if (Value *V = simplifyExtractElementInst(Vec: SrcVec, Idx: Index,
473 Q: SQ.getWithInstruction(I: &EI)))
474 return replaceInstUsesWith(I&: EI, V);
475
476 // extractelt (select %x, %vec1, %vec2), %const ->
477 // select %x, %vec1[%const], %vec2[%const]
478 // TODO: Support constant folding of multiple select operands:
479 // extractelt (select %x, %vec1, %vec2), (select %x, %c1, %c2)
480 // If the extractelement will for instance try to do out of bounds accesses
481 // because of the values of %c1 and/or %c2, the sequence could be optimized
482 // early. This is currently not possible because constant folding will reach
483 // an unreachable assertion if it doesn't find a constant operand.
484 if (SelectInst *SI = dyn_cast<SelectInst>(Val: EI.getVectorOperand()))
485 if (SI->getCondition()->getType()->isIntegerTy() &&
486 isa<Constant>(Val: EI.getIndexOperand()))
487 if (Instruction *R = FoldOpIntoSelect(Op&: EI, SI))
488 return R;
489
490 // Fold a variable index into a table of pointers into one object into
491 // address arithmetic
492 if (!isa<ConstantInt>(Val: Index))
493 if (Value *V = foldExtractOfStridedPointerVector(EI, Builder, DL))
494 return replaceInstUsesWith(I&: EI, V);
495
496 // If extracting a specified index from the vector, see if we can recursively
497 // find a previously computed scalar that was inserted into the vector.
498 auto *IndexC = dyn_cast<ConstantInt>(Val: Index);
499 bool HasKnownValidIndex = false;
500 if (IndexC) {
501 // Canonicalize type of constant indices to i64 to simplify CSE
502 if (auto *NewIdx = getPreferredVectorIndex(IndexC))
503 return replaceOperand(I&: EI, OpNum: 1, V: NewIdx);
504
505 ElementCount EC = EI.getVectorOperandType()->getElementCount();
506 unsigned NumElts = EC.getKnownMinValue();
507 HasKnownValidIndex = IndexC->getValue().ult(RHS: NumElts);
508
509 if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(Val: SrcVec)) {
510 Intrinsic::ID IID = II->getIntrinsicID();
511 // Index needs to be lower than the minimum size of the vector, because
512 // for scalable vector, the vector size is known at run time.
513 if (IID == Intrinsic::stepvector && IndexC->getValue().ult(RHS: NumElts)) {
514 Type *Ty = EI.getType();
515 unsigned BitWidth = Ty->getIntegerBitWidth();
516 Value *Idx;
517 // Return index when its value does not exceed the allowed limit
518 // for the element type of the vector.
519 // TODO: Truncate out-of-range values.
520 if (IndexC->getValue().getActiveBits() <= BitWidth)
521 Idx = ConstantInt::get(Ty, V: IndexC->getValue().zextOrTrunc(width: BitWidth));
522 else
523 return nullptr;
524 return replaceInstUsesWith(I&: EI, V: Idx);
525 }
526 }
527
528 // InstSimplify should handle cases where the index is invalid.
529 // For fixed-length vector, it's invalid to extract out-of-range element.
530 if (!EC.isScalable() && IndexC->getValue().uge(RHS: NumElts))
531 return nullptr;
532
533 if (Instruction *I = foldBitcastExtElt(Ext&: EI))
534 return I;
535
536 // If there's a vector PHI feeding a scalar use through this extractelement
537 // instruction, try to scalarize the PHI.
538 if (auto *Phi = dyn_cast<PHINode>(Val: SrcVec))
539 if (Instruction *ScalarPHI = scalarizePHI(EI, PN: Phi))
540 return ScalarPHI;
541 }
542
543 // If SrcVec is a subvector starting at index 0, extract from the
544 // wider source vector
545 Value *V;
546 if (match(V: SrcVec,
547 P: m_Intrinsic<Intrinsic::vector_extract>(Ops: m_Value(V), Ops: m_Zero())))
548 return ExtractElementInst::Create(Vec: V, Idx: Index);
549
550 // TODO come up with a n-ary matcher that subsumes both unary and
551 // binary matchers.
552 UnaryOperator *UO;
553 if (match(V: SrcVec, P: m_UnOp(I&: UO)) && cheapToScalarize(V: SrcVec, EI: Index)) {
554 // extelt (unop X), Index --> unop (extelt X, Index)
555 Value *X = UO->getOperand(i_nocapture: 0);
556 Value *E = Builder.CreateExtractElement(Vec: X, Idx: Index);
557 return UnaryOperator::CreateWithCopiedFlags(Opc: UO->getOpcode(), V: E, CopyO: UO);
558 }
559
560 // If the binop is not speculatable, we cannot hoist the extractelement if
561 // it may make the operand poison.
562 BinaryOperator *BO;
563 if (match(V: SrcVec, P: m_BinOp(I&: BO)) && cheapToScalarize(V: SrcVec, EI: Index) &&
564 (HasKnownValidIndex ||
565 isSafeToSpeculativelyExecuteWithVariableReplaced(I: BO))) {
566 // extelt (binop X, Y), Index --> binop (extelt X, Index), (extelt Y, Index)
567 Value *X = BO->getOperand(i_nocapture: 0), *Y = BO->getOperand(i_nocapture: 1);
568 Value *E0 = Builder.CreateExtractElement(Vec: X, Idx: Index);
569 Value *E1 = Builder.CreateExtractElement(Vec: Y, Idx: Index);
570 return BinaryOperator::CreateWithCopiedFlags(Opc: BO->getOpcode(), V1: E0, V2: E1, CopyO: BO);
571 }
572
573 Value *X, *Y;
574 CmpPredicate Pred;
575 if (match(V: SrcVec, P: m_Cmp(Pred, L: m_Value(V&: X), R: m_Value(V&: Y))) &&
576 cheapToScalarize(V: SrcVec, EI: Index)) {
577 // extelt (cmp X, Y), Index --> cmp (extelt X, Index), (extelt Y, Index)
578 Value *E0 = Builder.CreateExtractElement(Vec: X, Idx: Index);
579 Value *E1 = Builder.CreateExtractElement(Vec: Y, Idx: Index);
580 CmpInst *SrcCmpInst = cast<CmpInst>(Val: SrcVec);
581 return CmpInst::CreateWithCopiedFlags(Op: SrcCmpInst->getOpcode(), Pred, S1: E0, S2: E1,
582 FlagsSource: SrcCmpInst);
583 }
584
585 if (auto *I = dyn_cast<Instruction>(Val: SrcVec)) {
586 if (auto *IE = dyn_cast<InsertElementInst>(Val: I)) {
587 // instsimplify already handled the case where the indices are constants
588 // and equal by value, if both are constants, they must not be the same
589 // value, extract from the pre-inserted value instead.
590 if (isa<Constant>(Val: IE->getOperand(i_nocapture: 2)) && IndexC)
591 return replaceOperand(I&: EI, OpNum: 0, V: IE->getOperand(i_nocapture: 0));
592 } else if (auto *GEP = dyn_cast<GetElementPtrInst>(Val: I)) {
593 auto *VecType = cast<VectorType>(Val: GEP->getType());
594 ElementCount EC = VecType->getElementCount();
595 uint64_t IdxVal = IndexC ? IndexC->getZExtValue() : 0;
596 if (IndexC && IdxVal < EC.getKnownMinValue() && GEP->hasOneUse()) {
597 // Find out why we have a vector result - these are a few examples:
598 // 1. We have a scalar pointer and a vector of indices, or
599 // 2. We have a vector of pointers and a scalar index, or
600 // 3. We have a vector of pointers and a vector of indices, etc.
601 // Here we only consider combining when there is exactly one vector
602 // operand, since the optimization is less obviously a win due to
603 // needing more than one extractelements.
604
605 unsigned VectorOps =
606 llvm::count_if(Range: GEP->operands(), P: [](const Value *V) {
607 return isa<VectorType>(Val: V->getType());
608 });
609 if (VectorOps == 1) {
610 Value *NewPtr = GEP->getPointerOperand();
611 if (isa<VectorType>(Val: NewPtr->getType()))
612 NewPtr = Builder.CreateExtractElement(Vec: NewPtr, Idx: IndexC);
613
614 SmallVector<Value *> NewOps;
615 for (unsigned I = 1; I != GEP->getNumOperands(); ++I) {
616 Value *Op = GEP->getOperand(i_nocapture: I);
617 if (isa<VectorType>(Val: Op->getType()))
618 NewOps.push_back(Elt: Builder.CreateExtractElement(Vec: Op, Idx: IndexC));
619 else
620 NewOps.push_back(Elt: Op);
621 }
622
623 GetElementPtrInst *NewGEP = GetElementPtrInst::Create(
624 PointeeType: GEP->getSourceElementType(), Ptr: NewPtr, IdxList: NewOps);
625 NewGEP->setNoWrapFlags(GEP->getNoWrapFlags());
626 return NewGEP;
627 }
628 }
629 } else if (auto *SVI = dyn_cast<ShuffleVectorInst>(Val: I)) {
630 int SplatIndex = getSplatIndex(Mask: SVI->getShuffleMask());
631 // We know the all-0 splat must be reading from the first operand, even
632 // in the case of scalable vectors (vscale is always > 0).
633 if (SplatIndex == 0)
634 return ExtractElementInst::Create(Vec: SVI->getOperand(i_nocapture: 0),
635 Idx: Builder.getInt64(C: 0));
636
637 if (isa<FixedVectorType>(Val: SVI->getType())) {
638 std::optional<int> SrcIdx;
639 // getSplatIndex returns -1 to mean not-found.
640 if (SplatIndex != -1)
641 SrcIdx = SplatIndex;
642 else if (ConstantInt *CI = dyn_cast<ConstantInt>(Val: Index))
643 SrcIdx = SVI->getMaskValue(Elt: CI->getZExtValue());
644
645 if (SrcIdx) {
646 Value *Src;
647 unsigned LHSWidth =
648 cast<FixedVectorType>(Val: SVI->getOperand(i_nocapture: 0)->getType())
649 ->getNumElements();
650
651 if (*SrcIdx < 0)
652 return replaceInstUsesWith(I&: EI, V: PoisonValue::get(T: EI.getType()));
653 if (*SrcIdx < (int)LHSWidth)
654 Src = SVI->getOperand(i_nocapture: 0);
655 else {
656 *SrcIdx -= LHSWidth;
657 Src = SVI->getOperand(i_nocapture: 1);
658 }
659 Type *Int64Ty = Type::getInt64Ty(C&: EI.getContext());
660 return ExtractElementInst::Create(
661 Vec: Src, Idx: ConstantInt::get(Ty: Int64Ty, V: *SrcIdx, IsSigned: false));
662 }
663 }
664 } else if (auto *CI = dyn_cast<CastInst>(Val: I)) {
665 // Canonicalize extractelement(cast) -> cast(extractelement).
666 // Bitcasts can change the number of vector elements, and they cost
667 // nothing.
668 // If the CI has only one use, but that use is inside a loop, this
669 // canonicalization is not profitable because it would turn a vector
670 // operation into scalar operations inside the loop. Apply the transform
671 // when:
672 // - the index is constant and CI has one use, or
673 // - the CI and EI are in the same basic block, so the cast won't be sunk
674 // into a loop.
675 if (CI->hasOneUse() && (CI->getOpcode() != Instruction::BitCast) &&
676 (EI.getParent() == CI->getParent() || isa<ConstantInt>(Val: Index))) {
677 Value *EE = Builder.CreateExtractElement(Vec: CI->getOperand(i_nocapture: 0), Idx: Index);
678 return CastInst::Create(CI->getOpcode(), S: EE, Ty: EI.getType());
679 }
680 }
681 }
682
683 // Run demanded elements after other transforms as this can drop flags on
684 // binops. If there's two paths to the same final result, we prefer the
685 // one which doesn't force us to drop flags.
686 if (IndexC) {
687 ElementCount EC = EI.getVectorOperandType()->getElementCount();
688 unsigned NumElts = EC.getKnownMinValue();
689 // This instruction only demands the single element from the input vector.
690 // Skip for scalable type, the number of elements is unknown at
691 // compile-time.
692 if (!EC.isScalable() && NumElts != 1) {
693 // If the input vector has a single use, simplify it based on this use
694 // property.
695 if (SrcVec->hasOneUse()) {
696 APInt PoisonElts(NumElts, 0);
697 APInt DemandedElts(NumElts, 0);
698 DemandedElts.setBit(IndexC->getZExtValue());
699 if (Value *V =
700 SimplifyDemandedVectorElts(V: SrcVec, DemandedElts, PoisonElts))
701 return replaceOperand(I&: EI, OpNum: 0, V);
702 } else {
703 // If the input vector has multiple uses, simplify it based on a union
704 // of all elements used.
705 APInt DemandedElts = findDemandedEltsByAllUsers(V: SrcVec);
706 if (!DemandedElts.isAllOnes()) {
707 APInt PoisonElts(NumElts, 0);
708 if (Value *V = SimplifyDemandedVectorElts(
709 V: SrcVec, DemandedElts, PoisonElts, Depth: 0 /* Depth */,
710 AllowMultipleUsers: true /* AllowMultipleUsers */)) {
711 if (V != SrcVec) {
712 Worklist.addValue(V: SrcVec);
713 SrcVec->replaceAllUsesWith(V);
714 return &EI;
715 }
716 }
717 }
718 }
719 }
720 }
721 return nullptr;
722}
723
724/// If V is a shuffle of values that ONLY returns elements from either LHS or
725/// RHS, return the shuffle mask and true. Otherwise, return false.
726static bool collectSingleShuffleElements(Value *V, Value *LHS, Value *RHS,
727 SmallVectorImpl<int> &Mask) {
728 assert(LHS->getType() == RHS->getType() &&
729 "Invalid CollectSingleShuffleElements");
730 unsigned NumElts = cast<FixedVectorType>(Val: V->getType())->getNumElements();
731
732 if (match(V, P: m_Poison())) {
733 Mask.assign(NumElts, Elt: -1);
734 return true;
735 }
736
737 if (V == LHS) {
738 for (unsigned i = 0; i != NumElts; ++i)
739 Mask.push_back(Elt: i);
740 return true;
741 }
742
743 if (V == RHS) {
744 for (unsigned i = 0; i != NumElts; ++i)
745 Mask.push_back(Elt: i + NumElts);
746 return true;
747 }
748
749 if (InsertElementInst *IEI = dyn_cast<InsertElementInst>(Val: V)) {
750 // If this is an insert of an extract from some other vector, include it.
751 Value *VecOp = IEI->getOperand(i_nocapture: 0);
752 Value *ScalarOp = IEI->getOperand(i_nocapture: 1);
753 Value *IdxOp = IEI->getOperand(i_nocapture: 2);
754
755 if (!isa<ConstantInt>(Val: IdxOp))
756 return false;
757 unsigned InsertedIdx = cast<ConstantInt>(Val: IdxOp)->getZExtValue();
758
759 if (isa<PoisonValue>(Val: ScalarOp)) { // inserting poison into vector.
760 // We can handle this if the vector we are inserting into is
761 // transitively ok.
762 if (collectSingleShuffleElements(V: VecOp, LHS, RHS, Mask)) {
763 // If so, update the mask to reflect the inserted poison.
764 Mask[InsertedIdx] = -1;
765 return true;
766 }
767 } else if (ExtractElementInst *EI = dyn_cast<ExtractElementInst>(Val: ScalarOp)){
768 if (isa<ConstantInt>(Val: EI->getOperand(i_nocapture: 1))) {
769 unsigned ExtractedIdx =
770 cast<ConstantInt>(Val: EI->getOperand(i_nocapture: 1))->getZExtValue();
771 unsigned NumLHSElts =
772 cast<FixedVectorType>(Val: LHS->getType())->getNumElements();
773
774 // This must be extracting from either LHS or RHS.
775 if (EI->getOperand(i_nocapture: 0) == LHS || EI->getOperand(i_nocapture: 0) == RHS) {
776 // We can handle this if the vector we are inserting into is
777 // transitively ok.
778 if (collectSingleShuffleElements(V: VecOp, LHS, RHS, Mask)) {
779 // If so, update the mask to reflect the inserted value.
780 if (EI->getOperand(i_nocapture: 0) == LHS) {
781 Mask[InsertedIdx % NumElts] = ExtractedIdx;
782 } else {
783 assert(EI->getOperand(0) == RHS);
784 Mask[InsertedIdx % NumElts] = ExtractedIdx + NumLHSElts;
785 }
786 return true;
787 }
788 }
789 }
790 }
791 }
792
793 return false;
794}
795
796/// If we have insertion into a vector that is wider than the vector that we
797/// are extracting from, try to widen the source vector to allow a single
798/// shufflevector to replace one or more insert/extract pairs.
799static bool replaceExtractElements(InsertElementInst *InsElt,
800 ExtractElementInst *ExtElt,
801 InstCombinerImpl &IC) {
802 auto *InsVecType = cast<FixedVectorType>(Val: InsElt->getType());
803 auto *ExtVecType = cast<FixedVectorType>(Val: ExtElt->getVectorOperandType());
804 unsigned NumInsElts = InsVecType->getNumElements();
805 unsigned NumExtElts = ExtVecType->getNumElements();
806
807 // The inserted-to vector must be wider than the extracted-from vector.
808 if (InsVecType->getElementType() != ExtVecType->getElementType() ||
809 NumExtElts >= NumInsElts)
810 return false;
811
812 Value *ExtVecOp = ExtElt->getVectorOperand();
813 // Bail out on constant vectors.
814 if (isa<ConstantData>(Val: ExtVecOp))
815 return false;
816
817 // Create a shuffle mask to widen the extended-from vector using poison
818 // values. The mask selects all of the values of the original vector followed
819 // by as many poison values as needed to create a vector of the same length
820 // as the inserted-to vector.
821 SmallVector<int, 16> ExtendMask;
822 for (unsigned i = 0; i < NumExtElts; ++i)
823 ExtendMask.push_back(Elt: i);
824 for (unsigned i = NumExtElts; i < NumInsElts; ++i)
825 ExtendMask.push_back(Elt: -1);
826
827 auto *ExtVecOpInst = dyn_cast<Instruction>(Val: ExtVecOp);
828 BasicBlock *InsertionBlock = (ExtVecOpInst && !isa<PHINode>(Val: ExtVecOpInst))
829 ? ExtVecOpInst->getParent()
830 : ExtElt->getParent();
831
832 // TODO: This restriction matches the basic block check below when creating
833 // new extractelement instructions. If that limitation is removed, this one
834 // could also be removed. But for now, we just bail out to ensure that we
835 // will replace the extractelement instruction that is feeding our
836 // insertelement instruction. This allows the insertelement to then be
837 // replaced by a shufflevector. If the insertelement is not replaced, we can
838 // induce infinite looping because there's an optimization for extractelement
839 // that will delete our widening shuffle. This would trigger another attempt
840 // here to create that shuffle, and we spin forever.
841 if (InsertionBlock != InsElt->getParent())
842 return false;
843
844 // TODO: This restriction matches the check in visitInsertElementInst() and
845 // prevents an infinite loop caused by not turning the extract/insert pair
846 // into a shuffle. We really should not need either check, but we're lacking
847 // folds for shufflevectors because we're afraid to generate shuffle masks
848 // that the backend can't handle.
849 if (InsElt->hasOneUse() && isa<InsertElementInst>(Val: InsElt->user_back()))
850 return false;
851
852 auto *WideVec = new ShuffleVectorInst(ExtVecOp, ExtendMask);
853
854 // Insert the new shuffle after the vector operand of the extract is defined
855 // (as long as it's not a PHI) or at the start of the basic block of the
856 // extract, so any subsequent extracts in the same basic block can use it.
857 // TODO: Insert before the earliest ExtractElementInst that is replaced.
858 if (ExtVecOpInst && !isa<PHINode>(Val: ExtVecOpInst))
859 WideVec->insertAfter(InsertPos: ExtVecOpInst->getIterator());
860 else
861 IC.InsertNewInstWith(New: WideVec, Old: ExtElt->getParent()->getFirstInsertionPt());
862
863 // WideVec is an extension of ExtVecOp to produce a more useful value for
864 // ExtractElement instructions. If ExtVecOp is an instruction, adopt its
865 // DebugLoc; if it is not, then this is materializing a constant value, so set
866 // a CompilerGenerated location.
867 if (ExtVecOpInst)
868 WideVec->setDebugLoc(ExtVecOpInst->getDebugLoc());
869 else
870 WideVec->setDebugLoc(DebugLoc::getCompilerGenerated());
871
872 // Replace extracts from the original narrow vector with extracts from the new
873 // wide vector.
874 for (User *U : ExtVecOp->users()) {
875 ExtractElementInst *OldExt = dyn_cast<ExtractElementInst>(Val: U);
876 if (!OldExt || OldExt->getParent() != WideVec->getParent())
877 continue;
878 auto *NewExt = ExtractElementInst::Create(Vec: WideVec, Idx: OldExt->getOperand(i_nocapture: 1));
879 IC.InsertNewInstWith(New: NewExt, Old: OldExt->getIterator());
880 IC.replaceInstUsesWith(I&: *OldExt, V: NewExt);
881 // Add the old extracts to the worklist for DCE. We can't remove the
882 // extracts directly, because they may still be used by the calling code.
883 IC.addToWorklist(I: OldExt);
884 }
885
886 return true;
887}
888
889/// We are building a shuffle to create V, which is a sequence of insertelement,
890/// extractelement pairs. If PermittedRHS is set, then we must either use it or
891/// not rely on the second vector source. Return a std::pair containing the
892/// left and right vectors of the proposed shuffle (or 0), and set the Mask
893/// parameter as required.
894///
895/// Note: we intentionally don't try to fold earlier shuffles since they have
896/// often been chosen carefully to be efficiently implementable on the target.
897using ShuffleOps = std::pair<Value *, Value *>;
898
899static ShuffleOps collectShuffleElements(Value *V, SmallVectorImpl<int> &Mask,
900 Value *PermittedRHS,
901 InstCombinerImpl &IC, bool &Rerun) {
902 assert(V->getType()->isVectorTy() && "Invalid shuffle!");
903 unsigned NumElts = cast<FixedVectorType>(Val: V->getType())->getNumElements();
904
905 if (match(V, P: m_Poison())) {
906 Mask.assign(NumElts, Elt: -1);
907 return std::make_pair(
908 x: PermittedRHS ? PoisonValue::get(T: PermittedRHS->getType()) : V, y: nullptr);
909 }
910
911 if (isa<ConstantAggregateZero>(Val: V)) {
912 Mask.assign(NumElts, Elt: 0);
913 return std::make_pair(x&: V, y: nullptr);
914 }
915
916 if (InsertElementInst *IEI = dyn_cast<InsertElementInst>(Val: V)) {
917 // If this is an insert of an extract from some other vector, include it.
918 Value *VecOp = IEI->getOperand(i_nocapture: 0);
919 Value *ScalarOp = IEI->getOperand(i_nocapture: 1);
920 Value *IdxOp = IEI->getOperand(i_nocapture: 2);
921
922 if (ExtractElementInst *EI = dyn_cast<ExtractElementInst>(Val: ScalarOp)) {
923 if (isa<ConstantInt>(Val: EI->getOperand(i_nocapture: 1)) && isa<ConstantInt>(Val: IdxOp)) {
924 unsigned ExtractedIdx =
925 cast<ConstantInt>(Val: EI->getOperand(i_nocapture: 1))->getZExtValue();
926 unsigned InsertedIdx = cast<ConstantInt>(Val: IdxOp)->getZExtValue();
927
928 // Either the extracted from or inserted into vector must be RHSVec,
929 // otherwise we'd end up with a shuffle of three inputs.
930 if (EI->getOperand(i_nocapture: 0) == PermittedRHS || PermittedRHS == nullptr) {
931 Value *RHS = EI->getOperand(i_nocapture: 0);
932 ShuffleOps LR = collectShuffleElements(V: VecOp, Mask, PermittedRHS: RHS, IC, Rerun);
933 assert(LR.second == nullptr || LR.second == RHS);
934
935 if (LR.first->getType() != RHS->getType()) {
936 // Although we are giving up for now, see if we can create extracts
937 // that match the inserts for another round of combining.
938 if (replaceExtractElements(InsElt: IEI, ExtElt: EI, IC))
939 Rerun = true;
940
941 // We tried our best, but we can't find anything compatible with RHS
942 // further up the chain. Return a trivial shuffle.
943 for (unsigned i = 0; i < NumElts; ++i)
944 Mask[i] = i;
945 return std::make_pair(x&: V, y: nullptr);
946 }
947
948 unsigned NumLHSElts =
949 cast<FixedVectorType>(Val: RHS->getType())->getNumElements();
950 Mask[InsertedIdx % NumElts] = NumLHSElts + ExtractedIdx;
951 return std::make_pair(x&: LR.first, y&: RHS);
952 }
953
954 if (VecOp == PermittedRHS) {
955 // We've gone as far as we can: anything on the other side of the
956 // extractelement will already have been converted into a shuffle.
957 unsigned NumLHSElts =
958 cast<FixedVectorType>(Val: EI->getOperand(i_nocapture: 0)->getType())
959 ->getNumElements();
960 for (unsigned i = 0; i != NumElts; ++i)
961 Mask.push_back(Elt: i == InsertedIdx ? ExtractedIdx : NumLHSElts + i);
962 return std::make_pair(x: EI->getOperand(i_nocapture: 0), y&: PermittedRHS);
963 }
964
965 // If this insertelement is a chain that comes from exactly these two
966 // vectors, return the vector and the effective shuffle.
967 if (EI->getOperand(i_nocapture: 0)->getType() == PermittedRHS->getType() &&
968 collectSingleShuffleElements(V: IEI, LHS: EI->getOperand(i_nocapture: 0), RHS: PermittedRHS,
969 Mask))
970 return std::make_pair(x: EI->getOperand(i_nocapture: 0), y&: PermittedRHS);
971 }
972 }
973 }
974
975 // Otherwise, we can't do anything fancy. Return an identity vector.
976 for (unsigned i = 0; i != NumElts; ++i)
977 Mask.push_back(Elt: i);
978 return std::make_pair(x&: V, y: nullptr);
979}
980
981/// Look for chain of insertvalue's that fully define an aggregate, and trace
982/// back the values inserted, see if they are all were extractvalue'd from
983/// the same source aggregate from the exact same element indexes.
984/// If they were, just reuse the source aggregate.
985/// This potentially deals with PHI indirections.
986Instruction *InstCombinerImpl::foldAggregateConstructionIntoAggregateReuse(
987 InsertValueInst &OrigIVI) {
988 Type *AggTy = OrigIVI.getType();
989 unsigned NumAggElts;
990 switch (AggTy->getTypeID()) {
991 case Type::StructTyID:
992 NumAggElts = AggTy->getStructNumElements();
993 break;
994 case Type::ArrayTyID:
995 NumAggElts = AggTy->getArrayNumElements();
996 break;
997 default:
998 llvm_unreachable("Unhandled aggregate type?");
999 }
1000
1001 // Arbitrary aggregate size cut-off. Motivation for limit of 2 is to be able
1002 // to handle clang C++ exception struct (which is hardcoded as {i8*, i32}),
1003 // FIXME: any interesting patterns to be caught with larger limit?
1004 assert(NumAggElts > 0 && "Aggregate should have elements.");
1005 if (NumAggElts > 2)
1006 return nullptr;
1007
1008 static constexpr auto NotFound = std::nullopt;
1009 static constexpr auto FoundMismatch = nullptr;
1010
1011 // Try to find a value of each element of an aggregate.
1012 // FIXME: deal with more complex, not one-dimensional, aggregate types
1013 SmallVector<std::optional<Instruction *>, 2> AggElts(NumAggElts, NotFound);
1014
1015 // Do we know values for each element of the aggregate?
1016 auto KnowAllElts = [&AggElts]() {
1017 return !llvm::is_contained(Range&: AggElts, Element: NotFound);
1018 };
1019
1020 int Depth = 0;
1021
1022 // Arbitrary `insertvalue` visitation depth limit. Let's be okay with
1023 // every element being overwritten twice, which should never happen.
1024 static const int DepthLimit = 2 * NumAggElts;
1025
1026 // Recurse up the chain of `insertvalue` aggregate operands until either we've
1027 // reconstructed full initializer or can't visit any more `insertvalue`'s.
1028 for (InsertValueInst *CurrIVI = &OrigIVI;
1029 Depth < DepthLimit && CurrIVI && !KnowAllElts();
1030 CurrIVI = dyn_cast<InsertValueInst>(Val: CurrIVI->getAggregateOperand()),
1031 ++Depth) {
1032 auto *InsertedValue =
1033 dyn_cast<Instruction>(Val: CurrIVI->getInsertedValueOperand());
1034 if (!InsertedValue)
1035 return nullptr; // Inserted value must be produced by an instruction.
1036
1037 ArrayRef<unsigned int> Indices = CurrIVI->getIndices();
1038
1039 // Don't bother with more than single-level aggregates.
1040 if (Indices.size() != 1)
1041 return nullptr; // FIXME: deal with more complex aggregates?
1042
1043 // Now, we may have already previously recorded the value for this element
1044 // of an aggregate. If we did, that means the CurrIVI will later be
1045 // overwritten with the already-recorded value. But if not, let's record it!
1046 std::optional<Instruction *> &Elt = AggElts[Indices.front()];
1047 Elt = Elt.value_or(u&: InsertedValue);
1048
1049 // FIXME: should we handle chain-terminating undef base operand?
1050 }
1051
1052 // Was that sufficient to deduce the full initializer for the aggregate?
1053 if (!KnowAllElts())
1054 return nullptr; // Give up then.
1055
1056 // We now want to find the source[s] of the aggregate elements we've found.
1057 // And with "source" we mean the original aggregate[s] from which
1058 // the inserted elements were extracted. This may require PHI translation.
1059
1060 enum class AggregateDescription {
1061 /// When analyzing the value that was inserted into an aggregate, we did
1062 /// not manage to find defining `extractvalue` instruction to analyze.
1063 NotFound,
1064 /// When analyzing the value that was inserted into an aggregate, we did
1065 /// manage to find defining `extractvalue` instruction[s], and everything
1066 /// matched perfectly - aggregate type, element insertion/extraction index.
1067 Found,
1068 /// When analyzing the value that was inserted into an aggregate, we did
1069 /// manage to find defining `extractvalue` instruction, but there was
1070 /// a mismatch: either the source type from which the extraction was didn't
1071 /// match the aggregate type into which the insertion was,
1072 /// or the extraction/insertion channels mismatched,
1073 /// or different elements had different source aggregates.
1074 FoundMismatch
1075 };
1076 auto Describe = [](std::optional<Value *> SourceAggregate) {
1077 if (SourceAggregate == NotFound)
1078 return AggregateDescription::NotFound;
1079 if (*SourceAggregate == FoundMismatch)
1080 return AggregateDescription::FoundMismatch;
1081 return AggregateDescription::Found;
1082 };
1083
1084 // If an aggregate element is defined in UseBB, we can't use it in PredBB.
1085 bool EltDefinedInUseBB = false;
1086
1087 // Given the value \p Elt that was being inserted into element \p EltIdx of an
1088 // aggregate AggTy, see if \p Elt was originally defined by an
1089 // appropriate extractvalue (same element index, same aggregate type).
1090 // If found, return the source aggregate from which the extraction was.
1091 // If \p PredBB is provided, does PHI translation of an \p Elt first.
1092 auto FindSourceAggregate =
1093 [&](Instruction *Elt, unsigned EltIdx, std::optional<BasicBlock *> UseBB,
1094 std::optional<BasicBlock *> PredBB) -> std::optional<Value *> {
1095 // For now(?), only deal with, at most, a single level of PHI indirection.
1096 if (UseBB && PredBB) {
1097 Elt = dyn_cast<Instruction>(Val: Elt->DoPHITranslation(CurBB: *UseBB, PredBB: *PredBB));
1098 if (Elt && Elt->getParent() == *UseBB)
1099 EltDefinedInUseBB = true;
1100 }
1101 // FIXME: deal with multiple levels of PHI indirection?
1102
1103 // Did we find an extraction?
1104 auto *EVI = dyn_cast_or_null<ExtractValueInst>(Val: Elt);
1105 if (!EVI)
1106 return NotFound;
1107
1108 Value *SourceAggregate = EVI->getAggregateOperand();
1109
1110 // Is the extraction from the same type into which the insertion was?
1111 if (SourceAggregate->getType() != AggTy)
1112 return FoundMismatch;
1113 // And the element index doesn't change between extraction and insertion?
1114 if (EVI->getNumIndices() != 1 || EltIdx != EVI->getIndices().front())
1115 return FoundMismatch;
1116
1117 return SourceAggregate; // AggregateDescription::Found
1118 };
1119
1120 // Given elements AggElts that were constructing an aggregate OrigIVI,
1121 // see if we can find appropriate source aggregate for each of the elements,
1122 // and see it's the same aggregate for each element. If so, return it.
1123 auto FindCommonSourceAggregate =
1124 [&](std::optional<BasicBlock *> UseBB,
1125 std::optional<BasicBlock *> PredBB) -> std::optional<Value *> {
1126 std::optional<Value *> SourceAggregate;
1127
1128 for (auto I : enumerate(First&: AggElts)) {
1129 assert(Describe(SourceAggregate) != AggregateDescription::FoundMismatch &&
1130 "We don't store nullptr in SourceAggregate!");
1131 assert((Describe(SourceAggregate) == AggregateDescription::Found) ==
1132 (I.index() != 0) &&
1133 "SourceAggregate should be valid after the first element,");
1134
1135 // For this element, is there a plausible source aggregate?
1136 // FIXME: we could special-case undef element, IFF we know that in the
1137 // source aggregate said element isn't poison.
1138 std::optional<Value *> SourceAggregateForElement =
1139 FindSourceAggregate(*I.value(), I.index(), UseBB, PredBB);
1140
1141 // Okay, what have we found? Does that correlate with previous findings?
1142
1143 // Regardless of whether or not we have previously found source
1144 // aggregate for previous elements (if any), if we didn't find one for
1145 // this element, passthrough whatever we have just found.
1146 if (Describe(SourceAggregateForElement) != AggregateDescription::Found)
1147 return SourceAggregateForElement;
1148
1149 // Okay, we have found source aggregate for this element.
1150 // Let's see what we already know from previous elements, if any.
1151 switch (Describe(SourceAggregate)) {
1152 case AggregateDescription::NotFound:
1153 // This is apparently the first element that we have examined.
1154 SourceAggregate = SourceAggregateForElement; // Record the aggregate!
1155 continue; // Great, now look at next element.
1156 case AggregateDescription::Found:
1157 // We have previously already successfully examined other elements.
1158 // Is this the same source aggregate we've found for other elements?
1159 if (*SourceAggregateForElement != *SourceAggregate)
1160 return FoundMismatch;
1161 continue; // Still the same aggregate, look at next element.
1162 case AggregateDescription::FoundMismatch:
1163 llvm_unreachable("Can't happen. We would have early-exited then.");
1164 };
1165 }
1166
1167 assert(Describe(SourceAggregate) == AggregateDescription::Found &&
1168 "Must be a valid Value");
1169 return *SourceAggregate;
1170 };
1171
1172 std::optional<Value *> SourceAggregate;
1173
1174 // Can we find the source aggregate without looking at predecessors?
1175 SourceAggregate = FindCommonSourceAggregate(/*UseBB=*/std::nullopt,
1176 /*PredBB=*/std::nullopt);
1177 if (Describe(SourceAggregate) != AggregateDescription::NotFound) {
1178 if (Describe(SourceAggregate) == AggregateDescription::FoundMismatch)
1179 return nullptr; // Conflicting source aggregates!
1180 ++NumAggregateReconstructionsSimplified;
1181 return replaceInstUsesWith(I&: OrigIVI, V: *SourceAggregate);
1182 }
1183
1184 // Okay, apparently we need to look at predecessors.
1185
1186 // We should be smart about picking the "use" basic block, which will be the
1187 // merge point for aggregate, where we'll insert the final PHI that will be
1188 // used instead of OrigIVI. Basic block of OrigIVI is *not* the right choice.
1189 // We should look in which blocks each of the AggElts is being defined,
1190 // they all should be defined in the same basic block.
1191 BasicBlock *UseBB = nullptr;
1192
1193 for (const std::optional<Instruction *> &I : AggElts) {
1194 BasicBlock *BB = (*I)->getParent();
1195 // If it's the first instruction we've encountered, record the basic block.
1196 if (!UseBB) {
1197 UseBB = BB;
1198 continue;
1199 }
1200 // Otherwise, this must be the same basic block we've seen previously.
1201 if (UseBB != BB)
1202 return nullptr;
1203 }
1204
1205 // If *all* of the elements are basic-block-independent, meaning they are
1206 // either function arguments, or constant expressions, then if we didn't
1207 // handle them without predecessor-aware handling, we won't handle them now.
1208 if (!UseBB)
1209 return nullptr;
1210
1211 // If we didn't manage to find source aggregate without looking at
1212 // predecessors, and there are no predecessors to look at, then we're done.
1213 if (pred_empty(BB: UseBB))
1214 return nullptr;
1215
1216 // Arbitrary predecessor count limit.
1217 static const int PredCountLimit = 64;
1218
1219 // Cache the (non-uniqified!) list of predecessors in a vector,
1220 // checking the limit at the same time for efficiency.
1221 SmallVector<BasicBlock *, 4> Preds; // May have duplicates!
1222 for (BasicBlock *Pred : predecessors(BB: UseBB)) {
1223 // Don't bother if there are too many predecessors.
1224 if (Preds.size() >= PredCountLimit) // FIXME: only count duplicates once?
1225 return nullptr;
1226 Preds.emplace_back(Args&: Pred);
1227 }
1228
1229 // For each predecessor, what is the source aggregate,
1230 // from which all the elements were originally extracted from?
1231 // Note that we want for the map to have stable iteration order!
1232 SmallMapVector<BasicBlock *, Value *, 4> SourceAggregates;
1233 bool FoundSrcAgg = false;
1234 for (BasicBlock *Pred : Preds) {
1235 std::pair<decltype(SourceAggregates)::iterator, bool> IV =
1236 SourceAggregates.try_emplace(Key: Pred);
1237 // Did we already evaluate this predecessor?
1238 if (!IV.second)
1239 continue;
1240
1241 // Let's hope that when coming from predecessor Pred, all elements of the
1242 // aggregate produced by OrigIVI must have been originally extracted from
1243 // the same aggregate. Is that so? Can we find said original aggregate?
1244 SourceAggregate = FindCommonSourceAggregate(UseBB, Pred);
1245 if (Describe(SourceAggregate) == AggregateDescription::Found) {
1246 FoundSrcAgg = true;
1247 IV.first->second = *SourceAggregate;
1248 } else {
1249 // If UseBB is the single successor of Pred, we can add InsertValue to
1250 // Pred.
1251 auto *BI = dyn_cast<UncondBrInst>(Val: Pred->getTerminator());
1252 if (!BI)
1253 return nullptr;
1254 }
1255 }
1256
1257 if (!FoundSrcAgg)
1258 return nullptr;
1259
1260 // Do some sanity check if we need to add insertvalue into predecessors.
1261 auto OrigBB = OrigIVI.getParent();
1262 for (auto &It : SourceAggregates) {
1263 if (Describe(It.second) == AggregateDescription::Found)
1264 continue;
1265
1266 // Element is defined in UseBB, so it can't be used in predecessors.
1267 if (EltDefinedInUseBB)
1268 return nullptr;
1269
1270 // Do this transformation cross loop boundary may cause dead loop. So we
1271 // should avoid this situation. But LoopInfo is not generally available, we
1272 // must be conservative here.
1273 // If OrigIVI is in UseBB and it's the only successor of PredBB, PredBB
1274 // can't be in inner loop.
1275 if (UseBB != OrigBB)
1276 return nullptr;
1277
1278 // Avoid constructing constant aggregate because constant value may expose
1279 // more optimizations.
1280 bool ConstAgg = true;
1281 for (auto Val : AggElts) {
1282 Value *Elt = (*Val)->DoPHITranslation(CurBB: UseBB, PredBB: It.first);
1283 if (!isa<Constant>(Val: Elt)) {
1284 ConstAgg = false;
1285 break;
1286 }
1287 }
1288 if (ConstAgg)
1289 return nullptr;
1290 }
1291
1292 // For predecessors without appropriate source aggregate, create one in the
1293 // predecessor.
1294 for (auto &It : SourceAggregates) {
1295 if (Describe(It.second) == AggregateDescription::Found)
1296 continue;
1297
1298 BasicBlock *Pred = It.first;
1299 Builder.SetInsertPoint(Pred->getTerminator());
1300 Value *V = PoisonValue::get(T: AggTy);
1301 for (auto [Idx, Val] : enumerate(First&: AggElts)) {
1302 Value *Elt = (*Val)->DoPHITranslation(CurBB: UseBB, PredBB: Pred);
1303 V = Builder.CreateInsertValue(Agg: V, Val: Elt, Idxs: Idx);
1304 }
1305
1306 It.second = V;
1307 }
1308
1309 // All good! Now we just need to thread the source aggregates here.
1310 // Note that we have to insert the new PHI here, ourselves, because we can't
1311 // rely on InstCombinerImpl::run() inserting it into the right basic block.
1312 // Note that the same block can be a predecessor more than once,
1313 // and we need to preserve that invariant for the PHI node.
1314 BuilderTy::InsertPointGuard Guard(Builder);
1315 Builder.SetInsertPoint(UseBB->getFirstNonPHIIt());
1316 auto *PHI =
1317 Builder.CreatePHI(Ty: AggTy, NumReservedValues: Preds.size(), Name: OrigIVI.getName() + ".merged");
1318 for (BasicBlock *Pred : Preds)
1319 PHI->addIncoming(V: SourceAggregates[Pred], BB: Pred);
1320
1321 ++NumAggregateReconstructionsSimplified;
1322 return replaceInstUsesWith(I&: OrigIVI, V: PHI);
1323}
1324
1325/// Try to find redundant insertvalue instructions, like the following ones:
1326/// %0 = insertvalue { i8, i32 } undef, i8 %x, 0
1327/// %1 = insertvalue { i8, i32 } %0, i8 %y, 0
1328/// Here the second instruction inserts values at the same indices, as the
1329/// first one, making the first one redundant.
1330/// It should be transformed to:
1331/// %0 = insertvalue { i8, i32 } undef, i8 %y, 0
1332Instruction *InstCombinerImpl::visitInsertValueInst(InsertValueInst &I) {
1333 if (Value *V = simplifyInsertValueInst(
1334 Agg: I.getAggregateOperand(), Val: I.getInsertedValueOperand(), Idxs: I.getIndices(),
1335 Q: SQ.getWithInstruction(I: &I)))
1336 return replaceInstUsesWith(I, V);
1337
1338 bool IsRedundant = false;
1339 ArrayRef<unsigned int> FirstIndices = I.getIndices();
1340
1341 // If there is a chain of insertvalue instructions (each of them except the
1342 // last one has only one use and it's another insertvalue insn from this
1343 // chain), check if any of the 'children' uses the same indices as the first
1344 // instruction. In this case, the first one is redundant.
1345 Value *V = &I;
1346 unsigned Depth = 0;
1347 while (V->hasOneUse() && Depth < 10) {
1348 User *U = V->user_back();
1349 auto UserInsInst = dyn_cast<InsertValueInst>(Val: U);
1350 if (!UserInsInst || U->getOperand(i: 0) != V)
1351 break;
1352 if (UserInsInst->getIndices() == FirstIndices) {
1353 IsRedundant = true;
1354 break;
1355 }
1356 V = UserInsInst;
1357 Depth++;
1358 }
1359
1360 if (IsRedundant)
1361 return replaceInstUsesWith(I, V: I.getOperand(i_nocapture: 0));
1362
1363 if (Instruction *NewI = foldAggregateConstructionIntoAggregateReuse(OrigIVI&: I))
1364 return NewI;
1365
1366 return nullptr;
1367}
1368
1369static bool isShuffleEquivalentToSelect(ShuffleVectorInst &Shuf) {
1370 // Can not analyze scalable type, the number of elements is not a compile-time
1371 // constant.
1372 if (isa<ScalableVectorType>(Val: Shuf.getOperand(i_nocapture: 0)->getType()))
1373 return false;
1374
1375 int MaskSize = Shuf.getShuffleMask().size();
1376 int VecSize =
1377 cast<FixedVectorType>(Val: Shuf.getOperand(i_nocapture: 0)->getType())->getNumElements();
1378
1379 // A vector select does not change the size of the operands.
1380 if (MaskSize != VecSize)
1381 return false;
1382
1383 // Each mask element must be undefined or choose a vector element from one of
1384 // the source operands without crossing vector lanes.
1385 for (int i = 0; i != MaskSize; ++i) {
1386 int Elt = Shuf.getMaskValue(Elt: i);
1387 if (Elt != -1 && Elt != i && Elt != i + VecSize)
1388 return false;
1389 }
1390
1391 return true;
1392}
1393
1394/// Turn a chain of inserts that splats a value into an insert + shuffle:
1395/// insertelt(insertelt(insertelt(insertelt X, %k, 0), %k, 1), %k, 2) ... ->
1396/// shufflevector(insertelt(X, %k, 0), poison, zero)
1397static Instruction *foldInsSequenceIntoSplat(InsertElementInst &InsElt) {
1398 // We are interested in the last insert in a chain. So if this insert has a
1399 // single user and that user is an insert, bail.
1400 if (InsElt.hasOneUse() && isa<InsertElementInst>(Val: InsElt.user_back()))
1401 return nullptr;
1402
1403 VectorType *VecTy = InsElt.getType();
1404 // Can not handle scalable type, the number of elements is not a compile-time
1405 // constant.
1406 if (isa<ScalableVectorType>(Val: VecTy))
1407 return nullptr;
1408 unsigned NumElements = cast<FixedVectorType>(Val: VecTy)->getNumElements();
1409
1410 // Do not try to do this for a one-element vector, since that's a nop,
1411 // and will cause an inf-loop.
1412 if (NumElements == 1)
1413 return nullptr;
1414
1415 Value *SplatVal = InsElt.getOperand(i_nocapture: 1);
1416 InsertElementInst *CurrIE = &InsElt;
1417 SmallBitVector ElementPresent(NumElements, false);
1418 InsertElementInst *FirstIE = nullptr;
1419
1420 // Walk the chain backwards, keeping track of which indices we inserted into,
1421 // until we hit something that isn't an insert of the splatted value.
1422 while (CurrIE) {
1423 auto *Idx = dyn_cast<ConstantInt>(Val: CurrIE->getOperand(i_nocapture: 2));
1424 if (!Idx || CurrIE->getOperand(i_nocapture: 1) != SplatVal)
1425 return nullptr;
1426
1427 auto *NextIE = dyn_cast<InsertElementInst>(Val: CurrIE->getOperand(i_nocapture: 0));
1428 // Check none of the intermediate steps have any additional uses, except
1429 // for the root insertelement instruction, which can be re-used, if it
1430 // inserts at position 0.
1431 if (CurrIE != &InsElt &&
1432 (!CurrIE->hasOneUse() && (NextIE != nullptr || !Idx->isZero())))
1433 return nullptr;
1434
1435 ElementPresent[Idx->getZExtValue()] = true;
1436 FirstIE = CurrIE;
1437 CurrIE = NextIE;
1438 }
1439
1440 // If this is just a single insertelement (not a sequence), we are done.
1441 if (FirstIE == &InsElt)
1442 return nullptr;
1443
1444 // If we are not inserting into a poison vector, make sure we've seen an
1445 // insert into every element.
1446 // TODO: If the base vector is not undef, it might be better to create a splat
1447 // and then a select-shuffle (blend) with the base vector.
1448 if (!match(V: FirstIE->getOperand(i_nocapture: 0), P: m_Poison()))
1449 if (!ElementPresent.all())
1450 return nullptr;
1451
1452 // Create the insert + shuffle.
1453 Type *Int64Ty = Type::getInt64Ty(C&: InsElt.getContext());
1454 PoisonValue *PoisonVec = PoisonValue::get(T: VecTy);
1455 Constant *Zero = ConstantInt::get(Ty: Int64Ty, V: 0);
1456 if (!cast<ConstantInt>(Val: FirstIE->getOperand(i_nocapture: 2))->isZero())
1457 FirstIE = InsertElementInst::Create(Vec: PoisonVec, NewElt: SplatVal, Idx: Zero, NameStr: "",
1458 InsertBefore: InsElt.getIterator());
1459
1460 // Splat from element 0, but replace absent elements with poison in the mask.
1461 SmallVector<int, 16> Mask(NumElements, 0);
1462 for (unsigned i = 0; i != NumElements; ++i)
1463 if (!ElementPresent[i])
1464 Mask[i] = -1;
1465
1466 return new ShuffleVectorInst(FirstIE, Mask);
1467}
1468
1469/// Try to fold an insert element into an existing splat shuffle by changing
1470/// the shuffle's mask to include the index of this insert element.
1471static Instruction *foldInsEltIntoSplat(InsertElementInst &InsElt) {
1472 // Check if the vector operand of this insert is a canonical splat shuffle.
1473 auto *Shuf = dyn_cast<ShuffleVectorInst>(Val: InsElt.getOperand(i_nocapture: 0));
1474 if (!Shuf || !Shuf->isZeroEltSplat())
1475 return nullptr;
1476
1477 // Bail out early if shuffle is scalable type. The number of elements in
1478 // shuffle mask is unknown at compile-time.
1479 if (isa<ScalableVectorType>(Val: Shuf->getType()))
1480 return nullptr;
1481
1482 // Check for a constant insertion index.
1483 uint64_t IdxC;
1484 if (!match(V: InsElt.getOperand(i_nocapture: 2), P: m_ConstantInt(V&: IdxC)))
1485 return nullptr;
1486
1487 // Check if the splat shuffle's input is the same as this insert's scalar op.
1488 Value *X = InsElt.getOperand(i_nocapture: 1);
1489 Value *Op0 = Shuf->getOperand(i_nocapture: 0);
1490 if (!match(V: Op0, P: m_InsertElt(Val: m_Undef(), Elt: m_Specific(V: X), Idx: m_ZeroInt())))
1491 return nullptr;
1492
1493 // Replace the shuffle mask element at the index of this insert with a zero.
1494 // For example:
1495 // inselt (shuf (inselt undef, X, 0), _, <0,undef,0,undef>), X, 1
1496 // --> shuf (inselt undef, X, 0), poison, <0,0,0,undef>
1497 unsigned NumMaskElts =
1498 cast<FixedVectorType>(Val: Shuf->getType())->getNumElements();
1499 SmallVector<int, 16> NewMask(NumMaskElts);
1500 for (unsigned i = 0; i != NumMaskElts; ++i)
1501 NewMask[i] = i == IdxC ? 0 : Shuf->getMaskValue(Elt: i);
1502
1503 return new ShuffleVectorInst(Op0, NewMask);
1504}
1505
1506/// Try to fold an extract+insert element into an existing identity shuffle by
1507/// changing the shuffle's mask to include the index of this insert element.
1508static Instruction *foldInsEltIntoIdentityShuffle(InsertElementInst &InsElt) {
1509 // Check if the vector operand of this insert is an identity shuffle.
1510 auto *Shuf = dyn_cast<ShuffleVectorInst>(Val: InsElt.getOperand(i_nocapture: 0));
1511 if (!Shuf || !match(V: Shuf->getOperand(i_nocapture: 1), P: m_Poison()) ||
1512 !(Shuf->isIdentityWithExtract() || Shuf->isIdentityWithPadding()))
1513 return nullptr;
1514
1515 // Bail out early if shuffle is scalable type. The number of elements in
1516 // shuffle mask is unknown at compile-time.
1517 if (isa<ScalableVectorType>(Val: Shuf->getType()))
1518 return nullptr;
1519
1520 // Check for a constant insertion index.
1521 uint64_t IdxC;
1522 if (!match(V: InsElt.getOperand(i_nocapture: 2), P: m_ConstantInt(V&: IdxC)))
1523 return nullptr;
1524
1525 // Check if this insert's scalar op is extracted from the identity shuffle's
1526 // input vector.
1527 Value *Scalar = InsElt.getOperand(i_nocapture: 1);
1528 Value *X = Shuf->getOperand(i_nocapture: 0);
1529 if (!match(V: Scalar, P: m_ExtractElt(Val: m_Specific(V: X), Idx: m_SpecificInt(V: IdxC))))
1530 return nullptr;
1531
1532 // Replace the shuffle mask element at the index of this extract+insert with
1533 // that same index value.
1534 // For example:
1535 // inselt (shuf X, IdMask), (extelt X, IdxC), IdxC --> shuf X, IdMask'
1536 unsigned NumMaskElts =
1537 cast<FixedVectorType>(Val: Shuf->getType())->getNumElements();
1538 SmallVector<int, 16> NewMask(NumMaskElts);
1539 ArrayRef<int> OldMask = Shuf->getShuffleMask();
1540 for (unsigned i = 0; i != NumMaskElts; ++i) {
1541 if (i != IdxC) {
1542 // All mask elements besides the inserted element remain the same.
1543 NewMask[i] = OldMask[i];
1544 } else if (OldMask[i] == (int)IdxC) {
1545 // If the mask element was already set, there's nothing to do
1546 // (demanded elements analysis may unset it later).
1547 return nullptr;
1548 } else {
1549 assert(OldMask[i] == PoisonMaskElem &&
1550 "Unexpected shuffle mask element for identity shuffle");
1551 NewMask[i] = IdxC;
1552 }
1553 }
1554
1555 return new ShuffleVectorInst(X, Shuf->getOperand(i_nocapture: 1), NewMask);
1556}
1557
1558/// If we have an insertelement instruction feeding into another insertelement
1559/// and the 2nd is inserting a constant into the vector, canonicalize that
1560/// constant insertion before the insertion of a variable:
1561///
1562/// insertelement (insertelement X, Y, IdxC1), ScalarC, IdxC2 -->
1563/// insertelement (insertelement X, ScalarC, IdxC2), Y, IdxC1
1564///
1565/// This has the potential of eliminating the 2nd insertelement instruction
1566/// via constant folding of the scalar constant into a vector constant.
1567static Instruction *hoistInsEltConst(InsertElementInst &InsElt2,
1568 InstCombiner::BuilderTy &Builder) {
1569 auto *InsElt1 = dyn_cast<InsertElementInst>(Val: InsElt2.getOperand(i_nocapture: 0));
1570 if (!InsElt1 || !InsElt1->hasOneUse())
1571 return nullptr;
1572
1573 Value *X, *Y;
1574 Constant *ScalarC;
1575 ConstantInt *IdxC1, *IdxC2;
1576 if (match(V: InsElt1->getOperand(i_nocapture: 0), P: m_Value(V&: X)) &&
1577 match(V: InsElt1->getOperand(i_nocapture: 1), P: m_Value(V&: Y)) && !isa<Constant>(Val: Y) &&
1578 match(V: InsElt1->getOperand(i_nocapture: 2), P: m_ConstantInt(CI&: IdxC1)) &&
1579 match(V: InsElt2.getOperand(i_nocapture: 1), P: m_Constant(C&: ScalarC)) &&
1580 match(V: InsElt2.getOperand(i_nocapture: 2), P: m_ConstantInt(CI&: IdxC2)) && IdxC1 != IdxC2) {
1581 Value *NewInsElt1 = Builder.CreateInsertElement(Vec: X, NewElt: ScalarC, Idx: IdxC2);
1582 return InsertElementInst::Create(Vec: NewInsElt1, NewElt: Y, Idx: IdxC1);
1583 }
1584
1585 return nullptr;
1586}
1587
1588/// insertelt (shufflevector X, CVec, Mask|insertelt X, C1, CIndex1), C, CIndex
1589/// --> shufflevector X, CVec', Mask'
1590static Instruction *foldConstantInsEltIntoShuffle(InsertElementInst &InsElt) {
1591 auto *Inst = dyn_cast<Instruction>(Val: InsElt.getOperand(i_nocapture: 0));
1592 // Bail out if the parent has more than one use. In that case, we'd be
1593 // replacing the insertelt with a shuffle, and that's not a clear win.
1594 if (!Inst || !Inst->hasOneUse())
1595 return nullptr;
1596 if (auto *Shuf = dyn_cast<ShuffleVectorInst>(Val: InsElt.getOperand(i_nocapture: 0))) {
1597 // The shuffle must have a constant vector operand. The insertelt must have
1598 // a constant scalar being inserted at a constant position in the vector.
1599 Constant *ShufConstVec, *InsEltScalar;
1600 uint64_t InsEltIndex;
1601 if (!match(V: Shuf->getOperand(i_nocapture: 1), P: m_Constant(C&: ShufConstVec)) ||
1602 !match(V: InsElt.getOperand(i_nocapture: 1), P: m_Constant(C&: InsEltScalar)) ||
1603 !match(V: InsElt.getOperand(i_nocapture: 2), P: m_ConstantInt(V&: InsEltIndex)))
1604 return nullptr;
1605
1606 // Adding an element to an arbitrary shuffle could be expensive, but a
1607 // shuffle that selects elements from vectors without crossing lanes is
1608 // assumed cheap.
1609 // If we're just adding a constant into that shuffle, it will still be
1610 // cheap.
1611 if (!isShuffleEquivalentToSelect(Shuf&: *Shuf))
1612 return nullptr;
1613
1614 // From the above 'select' check, we know that the mask has the same number
1615 // of elements as the vector input operands. We also know that each constant
1616 // input element is used in its lane and can not be used more than once by
1617 // the shuffle. Therefore, replace the constant in the shuffle's constant
1618 // vector with the insertelt constant. Replace the constant in the shuffle's
1619 // mask vector with the insertelt index plus the length of the vector
1620 // (because the constant vector operand of a shuffle is always the 2nd
1621 // operand).
1622 ArrayRef<int> Mask = Shuf->getShuffleMask();
1623 unsigned NumElts = Mask.size();
1624 SmallVector<Constant *, 16> NewShufElts(NumElts);
1625 SmallVector<int, 16> NewMaskElts(NumElts);
1626 for (unsigned I = 0; I != NumElts; ++I) {
1627 if (I == InsEltIndex) {
1628 NewShufElts[I] = InsEltScalar;
1629 NewMaskElts[I] = InsEltIndex + NumElts;
1630 } else {
1631 // Copy over the existing values.
1632 NewShufElts[I] = ShufConstVec->getAggregateElement(Elt: I);
1633 NewMaskElts[I] = Mask[I];
1634 }
1635
1636 // Bail if we failed to find an element.
1637 if (!NewShufElts[I])
1638 return nullptr;
1639 }
1640
1641 // Create new operands for a shuffle that includes the constant of the
1642 // original insertelt. The old shuffle will be dead now.
1643 return new ShuffleVectorInst(Shuf->getOperand(i_nocapture: 0),
1644 ConstantVector::get(V: NewShufElts), NewMaskElts);
1645 } else if (auto *IEI = dyn_cast<InsertElementInst>(Val: Inst)) {
1646 // Transform sequences of insertelements ops with constant data/indexes into
1647 // a single shuffle op.
1648 // Can not handle scalable type, the number of elements needed to create
1649 // shuffle mask is not a compile-time constant.
1650 if (isa<ScalableVectorType>(Val: InsElt.getType()))
1651 return nullptr;
1652 unsigned NumElts =
1653 cast<FixedVectorType>(Val: InsElt.getType())->getNumElements();
1654
1655 uint64_t InsertIdx[2];
1656 Constant *Val[2];
1657 if (!match(V: InsElt.getOperand(i_nocapture: 2), P: m_ConstantInt(V&: InsertIdx[0])) ||
1658 !match(V: InsElt.getOperand(i_nocapture: 1), P: m_Constant(C&: Val[0])) ||
1659 !match(V: IEI->getOperand(i_nocapture: 2), P: m_ConstantInt(V&: InsertIdx[1])) ||
1660 !match(V: IEI->getOperand(i_nocapture: 1), P: m_Constant(C&: Val[1])))
1661 return nullptr;
1662 SmallVector<Constant *, 16> Values(NumElts);
1663 SmallVector<int, 16> Mask(NumElts);
1664 auto ValI = std::begin(arr&: Val);
1665 // Generate new constant vector and mask.
1666 // We have 2 values/masks from the insertelements instructions. Insert them
1667 // into new value/mask vectors.
1668 for (uint64_t I : InsertIdx) {
1669 if (!Values[I]) {
1670 Values[I] = *ValI;
1671 Mask[I] = NumElts + I;
1672 }
1673 ++ValI;
1674 }
1675 // Remaining values are filled with 'poison' values.
1676 for (unsigned I = 0; I < NumElts; ++I) {
1677 if (!Values[I]) {
1678 Values[I] = PoisonValue::get(T: InsElt.getType()->getElementType());
1679 Mask[I] = I;
1680 }
1681 }
1682 // Create new operands for a shuffle that includes the constant of the
1683 // original insertelt.
1684 return new ShuffleVectorInst(IEI->getOperand(i_nocapture: 0),
1685 ConstantVector::get(V: Values), Mask);
1686 }
1687 return nullptr;
1688}
1689
1690/// If both the base vector and the inserted element are extended from the same
1691/// type, do the insert element in the narrow source type followed by extend.
1692/// TODO: This can be extended to include other cast opcodes, but particularly
1693/// if we create a wider insertelement, make sure codegen is not harmed.
1694static Instruction *narrowInsElt(InsertElementInst &InsElt,
1695 InstCombiner::BuilderTy &Builder) {
1696 // We are creating a vector extend. If the original vector extend has another
1697 // use, that would mean we end up with 2 vector extends, so avoid that.
1698 // TODO: We could ease the use-clause to "if at least one op has one use"
1699 // (assuming that the source types match - see next TODO comment).
1700 Value *Vec = InsElt.getOperand(i_nocapture: 0);
1701 if (!Vec->hasOneUse())
1702 return nullptr;
1703
1704 Value *Scalar = InsElt.getOperand(i_nocapture: 1);
1705 Value *X, *Y;
1706 CastInst::CastOps CastOpcode;
1707 if (match(V: Vec, P: m_FPExt(Op: m_Value(V&: X))) && match(V: Scalar, P: m_FPExt(Op: m_Value(V&: Y))))
1708 CastOpcode = Instruction::FPExt;
1709 else if (match(V: Vec, P: m_SExt(Op: m_Value(V&: X))) && match(V: Scalar, P: m_SExt(Op: m_Value(V&: Y))))
1710 CastOpcode = Instruction::SExt;
1711 else if (match(V: Vec, P: m_ZExt(Op: m_Value(V&: X))) && match(V: Scalar, P: m_ZExt(Op: m_Value(V&: Y))))
1712 CastOpcode = Instruction::ZExt;
1713 else
1714 return nullptr;
1715
1716 // TODO: We can allow mismatched types by creating an intermediate cast.
1717 if (X->getType()->getScalarType() != Y->getType())
1718 return nullptr;
1719
1720 // inselt (ext X), (ext Y), Index --> ext (inselt X, Y, Index)
1721 Value *NewInsElt = Builder.CreateInsertElement(Vec: X, NewElt: Y, Idx: InsElt.getOperand(i_nocapture: 2));
1722 return CastInst::Create(CastOpcode, S: NewInsElt, Ty: InsElt.getType());
1723}
1724
1725/// If we are inserting 2 halves of a value into adjacent elements of a vector,
1726/// try to convert to a single insert with appropriate bitcasts.
1727static Instruction *foldTruncInsEltPair(InsertElementInst &InsElt,
1728 bool IsBigEndian,
1729 InstCombiner::BuilderTy &Builder) {
1730 Value *VecOp = InsElt.getOperand(i_nocapture: 0);
1731 Value *ScalarOp = InsElt.getOperand(i_nocapture: 1);
1732 Value *IndexOp = InsElt.getOperand(i_nocapture: 2);
1733
1734 // Pattern depends on endian because we expect lower index is inserted first.
1735 // Big endian:
1736 // inselt (inselt BaseVec, (trunc (lshr X, BW/2), Index0), (trunc X), Index1
1737 // Little endian:
1738 // inselt (inselt BaseVec, (trunc X), Index0), (trunc (lshr X, BW/2)), Index1
1739 // Note: It is not safe to do this transform with an arbitrary base vector
1740 // because the bitcast of that vector to fewer/larger elements could
1741 // allow poison to spill into an element that was not poison before.
1742 // TODO: Detect smaller fractions of the scalar.
1743 // TODO: One-use checks are conservative.
1744 auto *VTy = dyn_cast<FixedVectorType>(Val: InsElt.getType());
1745 Value *Scalar0, *BaseVec;
1746 uint64_t Index0, Index1;
1747 if (!VTy || (VTy->getNumElements() & 1) ||
1748 !match(V: IndexOp, P: m_ConstantInt(V&: Index1)) ||
1749 !match(V: VecOp, P: m_InsertElt(Val: m_Value(V&: BaseVec), Elt: m_Value(V&: Scalar0),
1750 Idx: m_ConstantInt(V&: Index0))) ||
1751 !match(V: BaseVec, P: m_Undef()))
1752 return nullptr;
1753
1754 // The first insert must be to the index one less than this one, and
1755 // the first insert must be to an even index.
1756 if (Index0 + 1 != Index1 || Index0 & 1)
1757 return nullptr;
1758
1759 // For big endian, the high half of the value should be inserted first.
1760 // For little endian, the low half of the value should be inserted first.
1761 Value *X;
1762 uint64_t ShAmt;
1763 if (IsBigEndian) {
1764 if (!match(V: ScalarOp, P: m_Trunc(Op: m_Value(V&: X))) ||
1765 !match(V: Scalar0, P: m_Trunc(Op: m_LShr(L: m_Specific(V: X), R: m_ConstantInt(V&: ShAmt)))))
1766 return nullptr;
1767 } else {
1768 if (!match(V: Scalar0, P: m_Trunc(Op: m_Value(V&: X))) ||
1769 !match(V: ScalarOp, P: m_Trunc(Op: m_LShr(L: m_Specific(V: X), R: m_ConstantInt(V&: ShAmt)))))
1770 return nullptr;
1771 }
1772
1773 Type *SrcTy = X->getType();
1774 unsigned ScalarWidth = SrcTy->getScalarSizeInBits();
1775 unsigned VecEltWidth = VTy->getScalarSizeInBits();
1776 if (ScalarWidth != VecEltWidth * 2 || ShAmt != VecEltWidth)
1777 return nullptr;
1778
1779 // Bitcast the base vector to a vector type with the source element type.
1780 Type *CastTy = FixedVectorType::get(ElementType: SrcTy, NumElts: VTy->getNumElements() / 2);
1781 Value *CastBaseVec = Builder.CreateBitCast(V: BaseVec, DestTy: CastTy);
1782
1783 // Scale the insert index for a vector with half as many elements.
1784 // bitcast (inselt (bitcast BaseVec), X, NewIndex)
1785 uint64_t NewIndex = IsBigEndian ? Index1 / 2 : Index0 / 2;
1786 Value *NewInsert = Builder.CreateInsertElement(Vec: CastBaseVec, NewElt: X, Idx: NewIndex);
1787 return new BitCastInst(NewInsert, VTy);
1788}
1789
1790Instruction *InstCombinerImpl::visitInsertElementInst(InsertElementInst &IE) {
1791 Value *VecOp = IE.getOperand(i_nocapture: 0);
1792 Value *ScalarOp = IE.getOperand(i_nocapture: 1);
1793 Value *IdxOp = IE.getOperand(i_nocapture: 2);
1794
1795 if (auto *V = simplifyInsertElementInst(
1796 Vec: VecOp, Elt: ScalarOp, Idx: IdxOp, Q: SQ.getWithInstruction(I: &IE)))
1797 return replaceInstUsesWith(I&: IE, V);
1798
1799 // Canonicalize type of constant indices to i64 to simplify CSE
1800 if (auto *IndexC = dyn_cast<ConstantInt>(Val: IdxOp)) {
1801 if (auto *NewIdx = getPreferredVectorIndex(IndexC))
1802 return replaceOperand(I&: IE, OpNum: 2, V: NewIdx);
1803
1804 Value *BaseVec, *OtherScalar;
1805 uint64_t OtherIndexVal;
1806 if (match(V: VecOp, P: m_OneUse(SubPattern: m_InsertElt(Val: m_Value(V&: BaseVec),
1807 Elt: m_Value(V&: OtherScalar),
1808 Idx: m_ConstantInt(V&: OtherIndexVal)))) &&
1809 !isa<Constant>(Val: OtherScalar) && OtherIndexVal > IndexC->getZExtValue()) {
1810 Value *NewIns = Builder.CreateInsertElement(Vec: BaseVec, NewElt: ScalarOp, Idx: IdxOp);
1811 return InsertElementInst::Create(Vec: NewIns, NewElt: OtherScalar,
1812 Idx: Builder.getInt64(C: OtherIndexVal));
1813 }
1814 }
1815
1816 // If the scalar is bitcast and inserted into undef, do the insert in the
1817 // source type followed by bitcast.
1818 // TODO: Generalize for insert into any constant, not just undef?
1819 Value *ScalarSrc;
1820 if (match(V: VecOp, P: m_Undef()) &&
1821 match(V: ScalarOp, P: m_OneUse(SubPattern: m_BitCast(Op: m_Value(V&: ScalarSrc)))) &&
1822 (ScalarSrc->getType()->isIntegerTy() ||
1823 ScalarSrc->getType()->isFloatingPointTy())) {
1824 // inselt undef, (bitcast ScalarSrc), IdxOp -->
1825 // bitcast (inselt undef, ScalarSrc, IdxOp)
1826 Type *ScalarTy = ScalarSrc->getType();
1827 Type *VecTy = VectorType::get(ElementType: ScalarTy, EC: IE.getType()->getElementCount());
1828 Constant *NewUndef = isa<PoisonValue>(Val: VecOp) ? PoisonValue::get(T: VecTy)
1829 : UndefValue::get(T: VecTy);
1830 Value *NewInsElt = Builder.CreateInsertElement(Vec: NewUndef, NewElt: ScalarSrc, Idx: IdxOp);
1831 return new BitCastInst(NewInsElt, IE.getType());
1832 }
1833
1834 // If the vector and scalar are both bitcast from the same element type, do
1835 // the insert in that source type followed by bitcast.
1836 Value *VecSrc;
1837 if (match(V: VecOp, P: m_BitCast(Op: m_Value(V&: VecSrc))) &&
1838 match(V: ScalarOp, P: m_BitCast(Op: m_Value(V&: ScalarSrc))) &&
1839 (VecOp->hasOneUse() || ScalarOp->hasOneUse()) &&
1840 VecSrc->getType()->isVectorTy() && !ScalarSrc->getType()->isVectorTy() &&
1841 cast<VectorType>(Val: VecSrc->getType())->getElementType() ==
1842 ScalarSrc->getType()) {
1843 // inselt (bitcast VecSrc), (bitcast ScalarSrc), IdxOp -->
1844 // bitcast (inselt VecSrc, ScalarSrc, IdxOp)
1845 Value *NewInsElt = Builder.CreateInsertElement(Vec: VecSrc, NewElt: ScalarSrc, Idx: IdxOp);
1846 return new BitCastInst(NewInsElt, IE.getType());
1847 }
1848
1849 // If the inserted element was extracted from some other fixed-length vector
1850 // and both indexes are valid constants, try to turn this into a shuffle.
1851 // Can not handle scalable vector type, the number of elements needed to
1852 // create shuffle mask is not a compile-time constant.
1853 uint64_t InsertedIdx, ExtractedIdx;
1854 Value *ExtVecOp;
1855 if (isa<FixedVectorType>(Val: IE.getType()) &&
1856 match(V: IdxOp, P: m_ConstantInt(V&: InsertedIdx)) &&
1857 match(V: ScalarOp,
1858 P: m_ExtractElt(Val: m_Value(V&: ExtVecOp), Idx: m_ConstantInt(V&: ExtractedIdx))) &&
1859 isa<FixedVectorType>(Val: ExtVecOp->getType()) &&
1860 ExtractedIdx <
1861 cast<FixedVectorType>(Val: ExtVecOp->getType())->getNumElements()) {
1862 // TODO: Looking at the user(s) to determine if this insert is a
1863 // fold-to-shuffle opportunity does not match the usual instcombine
1864 // constraints. We should decide if the transform is worthy based only
1865 // on this instruction and its operands, but that may not work currently.
1866 //
1867 // Here, we are trying to avoid creating shuffles before reaching
1868 // the end of a chain of extract-insert pairs. This is complicated because
1869 // we do not generally form arbitrary shuffle masks in instcombine
1870 // (because those may codegen poorly), but collectShuffleElements() does
1871 // exactly that.
1872 //
1873 // The rules for determining what is an acceptable target-independent
1874 // shuffle mask are fuzzy because they evolve based on the backend's
1875 // capabilities and real-world impact.
1876 auto isShuffleRootCandidate = [](InsertElementInst &Insert) {
1877 if (!Insert.hasOneUse())
1878 return true;
1879 auto *InsertUser = dyn_cast<InsertElementInst>(Val: Insert.user_back());
1880 if (!InsertUser)
1881 return true;
1882 return false;
1883 };
1884
1885 // Try to form a shuffle from a chain of extract-insert ops.
1886 if (isShuffleRootCandidate(IE)) {
1887 bool Rerun = true;
1888 while (Rerun) {
1889 Rerun = false;
1890
1891 SmallVector<int, 16> Mask;
1892 ShuffleOps LR =
1893 collectShuffleElements(V: &IE, Mask, PermittedRHS: nullptr, IC&: *this, Rerun);
1894
1895 // The proposed shuffle may be trivial, in which case we shouldn't
1896 // perform the combine.
1897 if (LR.first != &IE && LR.second != &IE) {
1898 // We now have a shuffle of LHS, RHS, Mask.
1899 if (LR.second == nullptr)
1900 LR.second = PoisonValue::get(T: LR.first->getType());
1901 return new ShuffleVectorInst(LR.first, LR.second, Mask);
1902 }
1903 }
1904 }
1905 }
1906
1907 if (auto VecTy = dyn_cast<FixedVectorType>(Val: VecOp->getType())) {
1908 unsigned VWidth = VecTy->getNumElements();
1909 APInt PoisonElts(VWidth, 0);
1910 APInt AllOnesEltMask(APInt::getAllOnes(numBits: VWidth));
1911 if (Value *V = SimplifyDemandedVectorElts(V: &IE, DemandedElts: AllOnesEltMask,
1912 PoisonElts)) {
1913 if (V != &IE)
1914 return replaceInstUsesWith(I&: IE, V);
1915 return &IE;
1916 }
1917 }
1918
1919 if (Instruction *Shuf = foldConstantInsEltIntoShuffle(InsElt&: IE))
1920 return Shuf;
1921
1922 if (Instruction *NewInsElt = hoistInsEltConst(InsElt2&: IE, Builder))
1923 return NewInsElt;
1924
1925 if (Instruction *Broadcast = foldInsSequenceIntoSplat(InsElt&: IE))
1926 return Broadcast;
1927
1928 if (Instruction *Splat = foldInsEltIntoSplat(InsElt&: IE))
1929 return Splat;
1930
1931 if (Instruction *IdentityShuf = foldInsEltIntoIdentityShuffle(InsElt&: IE))
1932 return IdentityShuf;
1933
1934 if (Instruction *Ext = narrowInsElt(InsElt&: IE, Builder))
1935 return Ext;
1936
1937 if (Instruction *Ext = foldTruncInsEltPair(InsElt&: IE, IsBigEndian: DL.isBigEndian(), Builder))
1938 return Ext;
1939
1940 return nullptr;
1941}
1942
1943/// Return true if we can evaluate the specified expression tree if the vector
1944/// elements were shuffled in a different order.
1945static bool canEvaluateShuffled(Value *V, ArrayRef<int> Mask,
1946 unsigned Depth = 5) {
1947 // We can always reorder the elements of a constant.
1948 if (isa<Constant>(Val: V))
1949 return true;
1950
1951 // We won't reorder vector arguments. No IPO here.
1952 Instruction *I = dyn_cast<Instruction>(Val: V);
1953 if (!I) return false;
1954
1955 // Two users may expect different orders of the elements. Don't try it.
1956 if (!I->hasOneUse())
1957 return false;
1958
1959 if (Depth == 0) return false;
1960
1961 switch (I->getOpcode()) {
1962 case Instruction::UDiv:
1963 case Instruction::SDiv:
1964 case Instruction::URem:
1965 case Instruction::SRem:
1966 // Propagating an undefined shuffle mask element to integer div/rem is not
1967 // allowed because those opcodes can create immediate undefined behavior
1968 // from an undefined element in an operand.
1969 if (llvm::is_contained(Range&: Mask, Element: -1))
1970 return false;
1971 [[fallthrough]];
1972 case Instruction::Add:
1973 case Instruction::FAdd:
1974 case Instruction::Sub:
1975 case Instruction::FSub:
1976 case Instruction::Mul:
1977 case Instruction::FMul:
1978 case Instruction::FDiv:
1979 case Instruction::FRem:
1980 case Instruction::Shl:
1981 case Instruction::LShr:
1982 case Instruction::AShr:
1983 case Instruction::And:
1984 case Instruction::Or:
1985 case Instruction::Xor:
1986 case Instruction::ICmp:
1987 case Instruction::FCmp:
1988 case Instruction::Trunc:
1989 case Instruction::ZExt:
1990 case Instruction::SExt:
1991 case Instruction::FPToUI:
1992 case Instruction::FPToSI:
1993 case Instruction::UIToFP:
1994 case Instruction::SIToFP:
1995 case Instruction::FPTrunc:
1996 case Instruction::FPExt:
1997 case Instruction::GetElementPtr: {
1998 // Bail out if we would create longer vector ops. We could allow creating
1999 // longer vector ops, but that may result in more expensive codegen.
2000 Type *ITy = I->getType();
2001 if (ITy->isVectorTy() &&
2002 Mask.size() > cast<FixedVectorType>(Val: ITy)->getNumElements())
2003 return false;
2004 for (Value *Operand : I->operands()) {
2005 if (!canEvaluateShuffled(V: Operand, Mask, Depth: Depth - 1))
2006 return false;
2007 }
2008 return true;
2009 }
2010 case Instruction::InsertElement: {
2011 ConstantInt *CI = dyn_cast<ConstantInt>(Val: I->getOperand(i: 2));
2012 if (!CI) return false;
2013 int ElementNumber = CI->getLimitedValue();
2014
2015 // Verify that 'CI' does not occur twice in Mask. A single 'insertelement'
2016 // can't put an element into multiple indices.
2017 bool SeenOnce = false;
2018 for (int I : Mask) {
2019 if (I == ElementNumber) {
2020 if (SeenOnce)
2021 return false;
2022 SeenOnce = true;
2023 }
2024 }
2025 return canEvaluateShuffled(V: I->getOperand(i: 0), Mask, Depth: Depth - 1);
2026 }
2027 }
2028 return false;
2029}
2030
2031/// Rebuild a new instruction just like 'I' but with the new operands given.
2032/// In the event of type mismatch, the type of the operands is correct.
2033static Value *buildNew(Instruction *I, ArrayRef<Value*> NewOps,
2034 IRBuilderBase &Builder) {
2035 Builder.SetInsertPoint(I);
2036 switch (I->getOpcode()) {
2037 case Instruction::Add:
2038 case Instruction::FAdd:
2039 case Instruction::Sub:
2040 case Instruction::FSub:
2041 case Instruction::Mul:
2042 case Instruction::FMul:
2043 case Instruction::UDiv:
2044 case Instruction::SDiv:
2045 case Instruction::FDiv:
2046 case Instruction::URem:
2047 case Instruction::SRem:
2048 case Instruction::FRem:
2049 case Instruction::Shl:
2050 case Instruction::LShr:
2051 case Instruction::AShr:
2052 case Instruction::And:
2053 case Instruction::Or:
2054 case Instruction::Xor: {
2055 BinaryOperator *BO = cast<BinaryOperator>(Val: I);
2056 assert(NewOps.size() == 2 && "binary operator with #ops != 2");
2057 Value *New = Builder.CreateBinOp(Opc: cast<BinaryOperator>(Val: I)->getOpcode(),
2058 LHS: NewOps[0], RHS: NewOps[1]);
2059 if (auto *NewI = dyn_cast<Instruction>(Val: New)) {
2060 if (isa<OverflowingBinaryOperator>(Val: BO)) {
2061 NewI->setHasNoUnsignedWrap(BO->hasNoUnsignedWrap());
2062 NewI->setHasNoSignedWrap(BO->hasNoSignedWrap());
2063 }
2064 if (isa<PossiblyExactOperator>(Val: BO)) {
2065 NewI->setIsExact(BO->isExact());
2066 }
2067 if (isa<FPMathOperator>(Val: BO))
2068 NewI->copyFastMathFlags(I);
2069 }
2070 return New;
2071 }
2072 case Instruction::ICmp: {
2073 assert(NewOps.size() == 2 && "icmp with #ops != 2");
2074 Value *New = Builder.CreateICmp(P: cast<ICmpInst>(Val: I)->getPredicate(),
2075 LHS: NewOps[0], RHS: NewOps[1]);
2076 if (auto *NewI = dyn_cast<Instruction>(Val: New))
2077 NewI->copyIRFlags(V: I);
2078 return New;
2079 }
2080 case Instruction::FCmp:
2081 assert(NewOps.size() == 2 && "fcmp with #ops != 2");
2082 return Builder.CreateFCmpFMF(P: cast<FCmpInst>(Val: I)->getPredicate(), LHS: NewOps[0],
2083 RHS: NewOps[1], FMFSource: I);
2084 case Instruction::Trunc:
2085 case Instruction::ZExt:
2086 case Instruction::SExt:
2087 case Instruction::FPToUI:
2088 case Instruction::FPToSI:
2089 case Instruction::UIToFP:
2090 case Instruction::SIToFP:
2091 case Instruction::FPTrunc:
2092 case Instruction::FPExt: {
2093 // It's possible that the mask has a different number of elements from
2094 // the original cast. We recompute the destination type to match the mask.
2095 Type *DestTy = VectorType::get(
2096 ElementType: I->getType()->getScalarType(),
2097 EC: cast<VectorType>(Val: NewOps[0]->getType())->getElementCount());
2098 assert(NewOps.size() == 1 && "cast with #ops != 1");
2099 Value *New =
2100 Builder.CreateCast(Op: cast<CastInst>(Val: I)->getOpcode(), V: NewOps[0], DestTy);
2101 if (auto *NewI = dyn_cast<Instruction>(Val: New))
2102 NewI->copyIRFlags(V: I);
2103 return New;
2104 }
2105 case Instruction::GetElementPtr: {
2106 Value *Ptr = NewOps[0];
2107 ArrayRef<Value*> Idx = NewOps.slice(N: 1);
2108 return Builder.CreateGEP(Ty: cast<GEPOperator>(Val: I)->getSourceElementType(),
2109 Ptr, IdxList: Idx, Name: "",
2110 NW: cast<GEPOperator>(Val: I)->getNoWrapFlags());
2111 }
2112 }
2113 llvm_unreachable("failed to rebuild vector instructions");
2114}
2115
2116static Value *evaluateInDifferentElementOrder(Value *V, ArrayRef<int> Mask,
2117 IRBuilderBase &Builder) {
2118 // Mask.size() does not need to be equal to the number of vector elements.
2119
2120 assert(V->getType()->isVectorTy() && "can't reorder non-vector elements");
2121 Type *EltTy = V->getType()->getScalarType();
2122
2123 if (isa<PoisonValue>(Val: V))
2124 return PoisonValue::get(T: FixedVectorType::get(ElementType: EltTy, NumElts: Mask.size()));
2125
2126 if (match(V, P: m_Undef()))
2127 return UndefValue::get(T: FixedVectorType::get(ElementType: EltTy, NumElts: Mask.size()));
2128
2129 if (isa<ConstantAggregateZero>(Val: V))
2130 return ConstantAggregateZero::get(Ty: FixedVectorType::get(ElementType: EltTy, NumElts: Mask.size()));
2131
2132 if (Constant *C = dyn_cast<Constant>(Val: V))
2133 return ConstantExpr::getShuffleVector(V1: C, V2: PoisonValue::get(T: C->getType()),
2134 Mask);
2135
2136 Instruction *I = cast<Instruction>(Val: V);
2137 switch (I->getOpcode()) {
2138 case Instruction::Add:
2139 case Instruction::FAdd:
2140 case Instruction::Sub:
2141 case Instruction::FSub:
2142 case Instruction::Mul:
2143 case Instruction::FMul:
2144 case Instruction::UDiv:
2145 case Instruction::SDiv:
2146 case Instruction::FDiv:
2147 case Instruction::URem:
2148 case Instruction::SRem:
2149 case Instruction::FRem:
2150 case Instruction::Shl:
2151 case Instruction::LShr:
2152 case Instruction::AShr:
2153 case Instruction::And:
2154 case Instruction::Or:
2155 case Instruction::Xor:
2156 case Instruction::ICmp:
2157 case Instruction::FCmp:
2158 case Instruction::Trunc:
2159 case Instruction::ZExt:
2160 case Instruction::SExt:
2161 case Instruction::FPToUI:
2162 case Instruction::FPToSI:
2163 case Instruction::UIToFP:
2164 case Instruction::SIToFP:
2165 case Instruction::FPTrunc:
2166 case Instruction::FPExt:
2167 case Instruction::Select:
2168 case Instruction::GetElementPtr: {
2169 SmallVector<Value*, 8> NewOps;
2170 bool NeedsRebuild =
2171 (Mask.size() !=
2172 cast<FixedVectorType>(Val: I->getType())->getNumElements());
2173 for (int i = 0, e = I->getNumOperands(); i != e; ++i) {
2174 Value *V;
2175 // Recursively call evaluateInDifferentElementOrder on vector arguments
2176 // as well. E.g. GetElementPtr may have scalar operands even if the
2177 // return value is a vector, so we need to examine the operand type.
2178 if (I->getOperand(i)->getType()->isVectorTy())
2179 V = evaluateInDifferentElementOrder(V: I->getOperand(i), Mask, Builder);
2180 else
2181 V = I->getOperand(i);
2182 NewOps.push_back(Elt: V);
2183 NeedsRebuild |= (V != I->getOperand(i));
2184 }
2185 if (NeedsRebuild)
2186 return buildNew(I, NewOps, Builder);
2187 return I;
2188 }
2189 case Instruction::InsertElement: {
2190 int Element = cast<ConstantInt>(Val: I->getOperand(i: 2))->getLimitedValue();
2191
2192 // The insertelement was inserting at Element. Figure out which element
2193 // that becomes after shuffling. The answer is guaranteed to be unique
2194 // by CanEvaluateShuffled.
2195 bool Found = false;
2196 int Index = 0;
2197 for (int e = Mask.size(); Index != e; ++Index) {
2198 if (Mask[Index] == Element) {
2199 Found = true;
2200 break;
2201 }
2202 }
2203
2204 // If element is not in Mask, no need to handle the operand 1 (element to
2205 // be inserted). Just evaluate values in operand 0 according to Mask.
2206 if (!Found)
2207 return evaluateInDifferentElementOrder(V: I->getOperand(i: 0), Mask, Builder);
2208
2209 Value *V = evaluateInDifferentElementOrder(V: I->getOperand(i: 0), Mask,
2210 Builder);
2211 Builder.SetInsertPoint(I);
2212 return Builder.CreateInsertElement(Vec: V, NewElt: I->getOperand(i: 1), Idx: Index);
2213 }
2214 }
2215 llvm_unreachable("failed to reorder elements of vector instruction!");
2216}
2217
2218// Returns true if the shuffle is extracting a contiguous range of values from
2219// LHS, for example:
2220// +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
2221// Input: |AA|BB|CC|DD|EE|FF|GG|HH|II|JJ|KK|LL|MM|NN|OO|PP|
2222// Shuffles to: |EE|FF|GG|HH|
2223// +--+--+--+--+
2224static bool isShuffleExtractingFromLHS(ShuffleVectorInst &SVI,
2225 ArrayRef<int> Mask) {
2226 unsigned LHSElems =
2227 cast<FixedVectorType>(Val: SVI.getOperand(i_nocapture: 0)->getType())->getNumElements();
2228 unsigned MaskElems = Mask.size();
2229 unsigned BegIdx = Mask.front();
2230 unsigned EndIdx = Mask.back();
2231 if (BegIdx > EndIdx || EndIdx >= LHSElems || EndIdx - BegIdx != MaskElems - 1)
2232 return false;
2233 for (unsigned I = 0; I != MaskElems; ++I)
2234 if (static_cast<unsigned>(Mask[I]) != BegIdx + I)
2235 return false;
2236 return true;
2237}
2238
2239/// These are the ingredients in an alternate form binary operator as described
2240/// below.
2241struct BinopElts {
2242 BinaryOperator::BinaryOps Opcode;
2243 Value *Op0;
2244 Value *Op1;
2245 BinopElts(BinaryOperator::BinaryOps Opc = (BinaryOperator::BinaryOps)0,
2246 Value *V0 = nullptr, Value *V1 = nullptr) :
2247 Opcode(Opc), Op0(V0), Op1(V1) {}
2248 operator bool() const { return Opcode != 0; }
2249};
2250
2251/// Binops may be transformed into binops with different opcodes and operands.
2252/// Reverse the usual canonicalization to enable folds with the non-canonical
2253/// form of the binop. If a transform is possible, return the elements of the
2254/// new binop. If not, return invalid elements.
2255static BinopElts getAlternateBinop(BinaryOperator *BO, const DataLayout &DL) {
2256 Value *BO0 = BO->getOperand(i_nocapture: 0), *BO1 = BO->getOperand(i_nocapture: 1);
2257 Type *Ty = BO->getType();
2258 switch (BO->getOpcode()) {
2259 case Instruction::Shl: {
2260 // shl X, C --> mul X, (1 << C)
2261 Constant *C;
2262 if (match(V: BO1, P: m_ImmConstant(C))) {
2263 Constant *ShlOne = ConstantFoldBinaryOpOperands(
2264 Opcode: Instruction::Shl, LHS: ConstantInt::get(Ty, V: 1), RHS: C, DL);
2265 assert(ShlOne && "Constant folding of immediate constants failed");
2266 return {Instruction::Mul, BO0, ShlOne};
2267 }
2268 break;
2269 }
2270 case Instruction::Or: {
2271 // or disjoin X, C --> add X, C
2272 if (cast<PossiblyDisjointInst>(Val: BO)->isDisjoint())
2273 return {Instruction::Add, BO0, BO1};
2274 break;
2275 }
2276 case Instruction::Sub:
2277 // sub 0, X --> mul X, -1
2278 if (match(V: BO0, P: m_ZeroInt()))
2279 return {Instruction::Mul, BO1, ConstantInt::getAllOnesValue(Ty)};
2280 break;
2281 default:
2282 break;
2283 }
2284 return {};
2285}
2286
2287/// A select shuffle of a select shuffle with a shared operand can be reduced
2288/// to a single select shuffle. This is an obvious improvement in IR, and the
2289/// backend is expected to lower select shuffles efficiently.
2290static Instruction *foldSelectShuffleOfSelectShuffle(ShuffleVectorInst &Shuf) {
2291 assert(Shuf.isSelect() && "Must have select-equivalent shuffle");
2292
2293 Value *Op0 = Shuf.getOperand(i_nocapture: 0), *Op1 = Shuf.getOperand(i_nocapture: 1);
2294 SmallVector<int, 16> Mask;
2295 Shuf.getShuffleMask(Result&: Mask);
2296 unsigned NumElts = Mask.size();
2297
2298 // Canonicalize a select shuffle with common operand as Op1.
2299 auto *ShufOp = dyn_cast<ShuffleVectorInst>(Val: Op0);
2300 if (ShufOp && ShufOp->isSelect() &&
2301 (ShufOp->getOperand(i_nocapture: 0) == Op1 || ShufOp->getOperand(i_nocapture: 1) == Op1)) {
2302 std::swap(a&: Op0, b&: Op1);
2303 ShuffleVectorInst::commuteShuffleMask(Mask, InVecNumElts: NumElts);
2304 }
2305
2306 ShufOp = dyn_cast<ShuffleVectorInst>(Val: Op1);
2307 if (!ShufOp || !ShufOp->isSelect() ||
2308 (ShufOp->getOperand(i_nocapture: 0) != Op0 && ShufOp->getOperand(i_nocapture: 1) != Op0))
2309 return nullptr;
2310
2311 Value *X = ShufOp->getOperand(i_nocapture: 0), *Y = ShufOp->getOperand(i_nocapture: 1);
2312 SmallVector<int, 16> Mask1;
2313 ShufOp->getShuffleMask(Result&: Mask1);
2314 assert(Mask1.size() == NumElts && "Vector size changed with select shuffle");
2315
2316 // Canonicalize common operand (Op0) as X (first operand of first shuffle).
2317 if (Y == Op0) {
2318 std::swap(a&: X, b&: Y);
2319 ShuffleVectorInst::commuteShuffleMask(Mask: Mask1, InVecNumElts: NumElts);
2320 }
2321
2322 // If the mask chooses from X (operand 0), it stays the same.
2323 // If the mask chooses from the earlier shuffle, the other mask value is
2324 // transferred to the combined select shuffle:
2325 // shuf X, (shuf X, Y, M1), M --> shuf X, Y, M'
2326 SmallVector<int, 16> NewMask(NumElts);
2327 for (unsigned i = 0; i != NumElts; ++i)
2328 NewMask[i] = Mask[i] < (signed)NumElts ? Mask[i] : Mask1[i];
2329
2330 // A select mask with undef elements might look like an identity mask.
2331 assert((ShuffleVectorInst::isSelectMask(NewMask, NumElts) ||
2332 ShuffleVectorInst::isIdentityMask(NewMask, NumElts)) &&
2333 "Unexpected shuffle mask");
2334 return new ShuffleVectorInst(X, Y, NewMask);
2335}
2336
2337static Instruction *foldSelectShuffleWith1Binop(ShuffleVectorInst &Shuf,
2338 const SimplifyQuery &SQ) {
2339 assert(Shuf.isSelect() && "Must have select-equivalent shuffle");
2340
2341 // Are we shuffling together some value and that same value after it has been
2342 // modified by a binop with a constant?
2343 Value *Op0 = Shuf.getOperand(i_nocapture: 0), *Op1 = Shuf.getOperand(i_nocapture: 1);
2344 Constant *C;
2345 bool Op0IsBinop;
2346 if (match(V: Op0, P: m_BinOp(L: m_Specific(V: Op1), R: m_Constant(C))))
2347 Op0IsBinop = true;
2348 else if (match(V: Op1, P: m_BinOp(L: m_Specific(V: Op0), R: m_Constant(C))))
2349 Op0IsBinop = false;
2350 else
2351 return nullptr;
2352
2353 // The identity constant for a binop leaves a variable operand unchanged. For
2354 // a vector, this is a splat of something like 0, -1, or 1.
2355 // If there's no identity constant for this binop, we're done.
2356 auto *BO = cast<BinaryOperator>(Val: Op0IsBinop ? Op0 : Op1);
2357 BinaryOperator::BinaryOps BOpcode = BO->getOpcode();
2358 Constant *IdC = ConstantExpr::getBinOpIdentity(Opcode: BOpcode, Ty: Shuf.getType(), AllowRHSConstant: true);
2359 if (!IdC)
2360 return nullptr;
2361
2362 Value *X = Op0IsBinop ? Op1 : Op0;
2363
2364 // Prevent folding in the case the non-binop operand might have NaN values.
2365 // If X can have NaN elements then we have that the floating point math
2366 // operation in the transformed code may not preserve the exact NaN
2367 // bit-pattern -- e.g. `fadd sNaN, 0.0 -> qNaN`.
2368 // This makes the transformation incorrect since the original program would
2369 // have preserved the exact NaN bit-pattern.
2370 // Avoid the folding if X can have NaN elements.
2371 bool IsFloatingPointTy =
2372 Shuf.getType()->getElementType()->isFloatingPointTy();
2373 if (IsFloatingPointTy && !isKnownNeverNaN(V: X, SQ))
2374 return nullptr;
2375
2376 // Shuffle identity constants into the lanes that return the original value.
2377 // Example: shuf (mul X, {-1,-2,-3,-4}), X, {0,5,6,3} --> mul X, {-1,1,1,-4}
2378 // Example: shuf X, (add X, {-1,-2,-3,-4}), {0,1,6,7} --> add X, {0,0,-3,-4}
2379 // The existing binop constant vector remains in the same operand position.
2380 ArrayRef<int> Mask = Shuf.getShuffleMask();
2381 Constant *NewC = Op0IsBinop ? ConstantExpr::getShuffleVector(V1: C, V2: IdC, Mask) :
2382 ConstantExpr::getShuffleVector(V1: IdC, V2: C, Mask);
2383
2384 bool MightCreatePoisonOrUB =
2385 is_contained(Range&: Mask, Element: PoisonMaskElem) &&
2386 (Instruction::isIntDivRem(Opcode: BOpcode) || Instruction::isShift(Opcode: BOpcode));
2387 if (MightCreatePoisonOrUB)
2388 NewC = InstCombiner::getSafeVectorConstantForBinop(Opcode: BOpcode, In: NewC, IsRHSConstant: true);
2389
2390 // shuf (bop X, C), X, M --> bop X, C'
2391 // shuf X, (bop X, C), M --> bop X, C'
2392 BinaryOperator *NewBO = BinaryOperator::Create(Op: BOpcode, S1: X, S2: NewC);
2393 NewBO->copyIRFlags(V: BO);
2394
2395 // Drop noinf FMF if X can be Inf. If X can have Inf elements and noinf FMF is
2396 // set, the transformation may generate poison where the original program
2397 // would preserve the Inf value.
2398 if (IsFloatingPointTy && NewBO->hasNoInfs() && !isKnownNeverInfinity(V: X, SQ))
2399 NewBO->setHasNoInfs(false);
2400
2401 // An undef shuffle mask element may propagate as an undef constant element in
2402 // the new binop. That would produce poison where the original code might not.
2403 // If we already made a safe constant, then there's no danger.
2404 if (is_contained(Range&: Mask, Element: PoisonMaskElem) && !MightCreatePoisonOrUB)
2405 NewBO->dropPoisonGeneratingFlags();
2406 return NewBO;
2407}
2408
2409/// If we have an insert of a scalar to a non-zero element of an undefined
2410/// vector and then shuffle that value, that's the same as inserting to the zero
2411/// element and shuffling. Splatting from the zero element is recognized as the
2412/// canonical form of splat.
2413static Instruction *canonicalizeInsertSplat(ShuffleVectorInst &Shuf,
2414 InstCombiner::BuilderTy &Builder) {
2415 Value *Op0 = Shuf.getOperand(i_nocapture: 0), *Op1 = Shuf.getOperand(i_nocapture: 1);
2416 ArrayRef<int> Mask = Shuf.getShuffleMask();
2417 Value *X;
2418 uint64_t IndexC;
2419
2420 // Match a shuffle that is a splat to a non-zero element.
2421 if (!match(V: Op0, P: m_OneUse(SubPattern: m_InsertElt(Val: m_Poison(), Elt: m_Value(V&: X),
2422 Idx: m_ConstantInt(V&: IndexC)))) ||
2423 !match(V: Op1, P: m_Poison()) || match(Mask, P: m_ZeroMask()) || IndexC == 0)
2424 return nullptr;
2425
2426 // Insert into element 0 of a poison vector.
2427 PoisonValue *PoisonVec = PoisonValue::get(T: Shuf.getType());
2428 Value *NewIns = Builder.CreateInsertElement(Vec: PoisonVec, NewElt: X, Idx: (uint64_t)0);
2429
2430 // Splat from element 0. Any mask element that is poison remains poison.
2431 // For example:
2432 // shuf (inselt poison, X, 2), _, <2,2,undef>
2433 // --> shuf (inselt poison, X, 0), poison, <0,0,undef>
2434 unsigned NumMaskElts =
2435 cast<FixedVectorType>(Val: Shuf.getType())->getNumElements();
2436 SmallVector<int, 16> NewMask(NumMaskElts, 0);
2437 for (unsigned i = 0; i != NumMaskElts; ++i)
2438 if (Mask[i] == PoisonMaskElem)
2439 NewMask[i] = Mask[i];
2440
2441 return new ShuffleVectorInst(NewIns, NewMask);
2442}
2443
2444/// Try to fold shuffles that are the equivalent of a vector select.
2445Instruction *InstCombinerImpl::foldSelectShuffle(ShuffleVectorInst &Shuf) {
2446 if (!Shuf.isSelect())
2447 return nullptr;
2448
2449 // Canonicalize to choose from operand 0 first unless operand 1 is undefined.
2450 // Commuting undef to operand 0 conflicts with another canonicalization.
2451 unsigned NumElts = cast<FixedVectorType>(Val: Shuf.getType())->getNumElements();
2452 if (!match(V: Shuf.getOperand(i_nocapture: 1), P: m_Undef()) &&
2453 Shuf.getMaskValue(Elt: 0) >= (int)NumElts) {
2454 // TODO: Can we assert that both operands of a shuffle-select are not undef
2455 // (otherwise, it would have been folded by instsimplify?
2456 Shuf.commute();
2457 return &Shuf;
2458 }
2459
2460 if (Instruction *I = foldSelectShuffleOfSelectShuffle(Shuf))
2461 return I;
2462
2463 if (Instruction *I = foldSelectShuffleWith1Binop(
2464 Shuf, SQ: getSimplifyQuery().getWithInstruction(I: &Shuf)))
2465 return I;
2466
2467 BinaryOperator *B0, *B1;
2468 if (!match(V: Shuf.getOperand(i_nocapture: 0), P: m_BinOp(I&: B0)) ||
2469 !match(V: Shuf.getOperand(i_nocapture: 1), P: m_BinOp(I&: B1)))
2470 return nullptr;
2471
2472 // If one operand is "0 - X", allow that to be viewed as "X * -1"
2473 // (ConstantsAreOp1) by getAlternateBinop below. If the neg is not paired
2474 // with a multiply, we will exit because C0/C1 will not be set.
2475 Value *X, *Y;
2476 Constant *C0 = nullptr, *C1 = nullptr;
2477 bool ConstantsAreOp1;
2478 if (match(V: B0, P: m_BinOp(L: m_Constant(C&: C0), R: m_Value(V&: X))) &&
2479 match(V: B1, P: m_BinOp(L: m_Constant(C&: C1), R: m_Value(V&: Y))))
2480 ConstantsAreOp1 = false;
2481 else if (match(V: B0, P: m_CombineOr(Ps: m_BinOp(L: m_Value(V&: X), R: m_Constant(C&: C0)),
2482 Ps: m_Neg(V: m_Value(V&: X)))) &&
2483 match(V: B1, P: m_CombineOr(Ps: m_BinOp(L: m_Value(V&: Y), R: m_Constant(C&: C1)),
2484 Ps: m_Neg(V: m_Value(V&: Y)))))
2485 ConstantsAreOp1 = true;
2486 else
2487 return nullptr;
2488
2489 // We need matching binops to fold the lanes together.
2490 BinaryOperator::BinaryOps Opc0 = B0->getOpcode();
2491 BinaryOperator::BinaryOps Opc1 = B1->getOpcode();
2492 bool DropNSW = false;
2493 if (ConstantsAreOp1 && Opc0 != Opc1) {
2494 // TODO: We drop "nsw" if shift is converted into multiply because it may
2495 // not be correct when the shift amount is BitWidth - 1. We could examine
2496 // each vector element to determine if it is safe to keep that flag.
2497 if (Opc0 == Instruction::Shl || Opc1 == Instruction::Shl)
2498 DropNSW = true;
2499 if (BinopElts AltB0 = getAlternateBinop(BO: B0, DL)) {
2500 assert(isa<Constant>(AltB0.Op1) && "Expecting constant with alt binop");
2501 Opc0 = AltB0.Opcode;
2502 C0 = cast<Constant>(Val: AltB0.Op1);
2503 } else if (BinopElts AltB1 = getAlternateBinop(BO: B1, DL)) {
2504 assert(isa<Constant>(AltB1.Op1) && "Expecting constant with alt binop");
2505 Opc1 = AltB1.Opcode;
2506 C1 = cast<Constant>(Val: AltB1.Op1);
2507 }
2508 }
2509
2510 if (Opc0 != Opc1 || !C0 || !C1)
2511 return nullptr;
2512
2513 // The opcodes must be the same. Use a new name to make that clear.
2514 BinaryOperator::BinaryOps BOpc = Opc0;
2515
2516 // Select the constant elements needed for the single binop.
2517 ArrayRef<int> Mask = Shuf.getShuffleMask();
2518 Constant *NewC = ConstantExpr::getShuffleVector(V1: C0, V2: C1, Mask);
2519
2520 // We are moving a binop after a shuffle. When a shuffle has an undefined
2521 // mask element, the result is undefined, but it is not poison or undefined
2522 // behavior. That is not necessarily true for div/rem/shift.
2523 bool MightCreatePoisonOrUB =
2524 is_contained(Range&: Mask, Element: PoisonMaskElem) &&
2525 (Instruction::isIntDivRem(Opcode: BOpc) || Instruction::isShift(Opcode: BOpc));
2526 if (MightCreatePoisonOrUB)
2527 NewC = InstCombiner::getSafeVectorConstantForBinop(Opcode: BOpc, In: NewC,
2528 IsRHSConstant: ConstantsAreOp1);
2529
2530 Value *V;
2531 if (X == Y) {
2532 // Remove a binop and the shuffle by rearranging the constant:
2533 // shuffle (op V, C0), (op V, C1), M --> op V, C'
2534 // shuffle (op C0, V), (op C1, V), M --> op C', V
2535 V = X;
2536 } else {
2537 // If there are 2 different variable operands, we must create a new shuffle
2538 // (select) first, so check uses to ensure that we don't end up with more
2539 // instructions than we started with.
2540 if (!B0->hasOneUse() && !B1->hasOneUse())
2541 return nullptr;
2542
2543 // If we use the original shuffle mask and op1 is *variable*, we would be
2544 // putting an undef into operand 1 of div/rem/shift. This is either UB or
2545 // poison. We do not have to guard against UB when *constants* are op1
2546 // because safe constants guarantee that we do not overflow sdiv/srem (and
2547 // there's no danger for other opcodes).
2548 // TODO: To allow this case, create a new shuffle mask with no undefs.
2549 if (MightCreatePoisonOrUB && !ConstantsAreOp1)
2550 return nullptr;
2551
2552 // Note: In general, we do not create new shuffles in InstCombine because we
2553 // do not know if a target can lower an arbitrary shuffle optimally. In this
2554 // case, the shuffle uses the existing mask, so there is no additional risk.
2555
2556 // Select the variable vectors first, then perform the binop:
2557 // shuffle (op X, C0), (op Y, C1), M --> op (shuffle X, Y, M), C'
2558 // shuffle (op C0, X), (op C1, Y), M --> op C', (shuffle X, Y, M)
2559 V = Builder.CreateShuffleVector(V1: X, V2: Y, Mask);
2560 }
2561
2562 Value *NewBO = ConstantsAreOp1 ? Builder.CreateBinOp(Opc: BOpc, LHS: V, RHS: NewC) :
2563 Builder.CreateBinOp(Opc: BOpc, LHS: NewC, RHS: V);
2564
2565 // Flags are intersected from the 2 source binops. But there are 2 exceptions:
2566 // 1. If we changed an opcode, poison conditions might have changed.
2567 // 2. If the shuffle had undef mask elements, the new binop might have undefs
2568 // where the original code did not. But if we already made a safe constant,
2569 // then there's no danger.
2570 if (auto *NewI = dyn_cast<Instruction>(Val: NewBO)) {
2571 NewI->copyIRFlags(V: B0);
2572 NewI->andIRFlags(V: B1);
2573 if (DropNSW)
2574 NewI->setHasNoSignedWrap(false);
2575 if (is_contained(Range&: Mask, Element: PoisonMaskElem) && !MightCreatePoisonOrUB)
2576 NewI->dropPoisonGeneratingFlags();
2577 }
2578 return replaceInstUsesWith(I&: Shuf, V: NewBO);
2579}
2580
2581/// Convert a narrowing shuffle of a bitcasted vector into a vector truncate.
2582/// Example (little endian):
2583/// shuf (bitcast <4 x i16> X to <8 x i8>), <0, 2, 4, 6> --> trunc X to <4 x i8>
2584static Instruction *foldTruncShuffle(ShuffleVectorInst &Shuf,
2585 bool IsBigEndian) {
2586 // This must be a bitcasted shuffle of 1 vector integer operand.
2587 Type *DestType = Shuf.getType();
2588 Value *X;
2589 if (!match(V: Shuf.getOperand(i_nocapture: 0), P: m_BitCast(Op: m_Value(V&: X))) ||
2590 !match(V: Shuf.getOperand(i_nocapture: 1), P: m_Poison()) || !DestType->isIntOrIntVectorTy())
2591 return nullptr;
2592
2593 // The source type must have the same number of elements as the shuffle,
2594 // and the source element type must be larger than the shuffle element type.
2595 Type *SrcType = X->getType();
2596 if (!SrcType->isVectorTy() || !SrcType->isIntOrIntVectorTy() ||
2597 cast<FixedVectorType>(Val: SrcType)->getNumElements() !=
2598 cast<FixedVectorType>(Val: DestType)->getNumElements() ||
2599 SrcType->getScalarSizeInBits() % DestType->getScalarSizeInBits() != 0)
2600 return nullptr;
2601
2602 assert(Shuf.changesLength() && !Shuf.increasesLength() &&
2603 "Expected a shuffle that decreases length");
2604
2605 // Last, check that the mask chooses the correct low bits for each narrow
2606 // element in the result.
2607 uint64_t TruncRatio =
2608 SrcType->getScalarSizeInBits() / DestType->getScalarSizeInBits();
2609 ArrayRef<int> Mask = Shuf.getShuffleMask();
2610 for (unsigned i = 0, e = Mask.size(); i != e; ++i) {
2611 if (Mask[i] == PoisonMaskElem)
2612 continue;
2613 uint64_t LSBIndex = IsBigEndian ? (i + 1) * TruncRatio - 1 : i * TruncRatio;
2614 assert(LSBIndex <= INT32_MAX && "Overflowed 32-bits");
2615 if (Mask[i] != (int)LSBIndex)
2616 return nullptr;
2617 }
2618
2619 return new TruncInst(X, DestType);
2620}
2621
2622/// Match a shuffle-select-shuffle pattern where the shuffles are widening and
2623/// narrowing (concatenating with poison and extracting back to the original
2624/// length). This allows replacing the wide select with a narrow select.
2625static Instruction *narrowVectorSelect(ShuffleVectorInst &Shuf,
2626 InstCombiner::BuilderTy &Builder) {
2627 // This must be a narrowing identity shuffle. It extracts the 1st N elements
2628 // of the 1st vector operand of a shuffle.
2629 if (!match(V: Shuf.getOperand(i_nocapture: 1), P: m_Poison()) || !Shuf.isIdentityWithExtract())
2630 return nullptr;
2631
2632 // The vector being shuffled must be a vector select that we can eliminate.
2633 // TODO: The one-use requirement could be eased if X and/or Y are constants.
2634 Value *Cond, *X, *Y;
2635 if (!match(V: Shuf.getOperand(i_nocapture: 0),
2636 P: m_OneUse(SubPattern: m_Select(C: m_Value(V&: Cond), L: m_Value(V&: X), R: m_Value(V&: Y)))))
2637 return nullptr;
2638
2639 // We need a narrow condition value. It must be extended with poison elements
2640 // and have the same number of elements as this shuffle.
2641 unsigned NarrowNumElts =
2642 cast<FixedVectorType>(Val: Shuf.getType())->getNumElements();
2643 Value *NarrowCond;
2644 if (!match(V: Cond, P: m_OneUse(SubPattern: m_Shuffle(v1: m_Value(V&: NarrowCond), v2: m_Poison()))) ||
2645 cast<FixedVectorType>(Val: NarrowCond->getType())->getNumElements() !=
2646 NarrowNumElts ||
2647 !cast<ShuffleVectorInst>(Val: Cond)->isIdentityWithPadding())
2648 return nullptr;
2649
2650 // shuf (sel (shuf NarrowCond, poison, WideMask), X, Y), poison, NarrowMask)
2651 // -->
2652 // sel NarrowCond, (shuf X, poison, NarrowMask), (shuf Y, poison, NarrowMask)
2653 Value *NarrowX = Builder.CreateShuffleVector(V: X, Mask: Shuf.getShuffleMask());
2654 Value *NarrowY = Builder.CreateShuffleVector(V: Y, Mask: Shuf.getShuffleMask());
2655 return SelectInst::Create(C: NarrowCond, S1: NarrowX, S2: NarrowY);
2656}
2657
2658/// Canonicalize FP negate/abs after shuffle.
2659static Instruction *foldShuffleOfUnaryOps(ShuffleVectorInst &Shuf,
2660 InstCombiner::BuilderTy &Builder) {
2661 auto *S0 = dyn_cast<Instruction>(Val: Shuf.getOperand(i_nocapture: 0));
2662 Value *X;
2663 if (!S0 || !match(V: S0, P: m_CombineOr(Ps: m_FNeg(X: m_Value(V&: X)), Ps: m_FAbs(Op0: m_Value(V&: X)))))
2664 return nullptr;
2665
2666 bool IsFNeg = S0->getOpcode() == Instruction::FNeg;
2667
2668 // Match 2-input (binary) shuffle.
2669 auto *S1 = dyn_cast<Instruction>(Val: Shuf.getOperand(i_nocapture: 1));
2670 Value *Y;
2671 if (!S1 || !match(V: S1, P: m_CombineOr(Ps: m_FNeg(X: m_Value(V&: Y)), Ps: m_FAbs(Op0: m_Value(V&: Y)))) ||
2672 S0->getOpcode() != S1->getOpcode() ||
2673 (!S0->hasOneUse() && !S1->hasOneUse()))
2674 return nullptr;
2675
2676 // shuf (fneg/fabs X), (fneg/fabs Y), Mask --> fneg/fabs (shuf X, Y, Mask)
2677 Value *NewShuf = Builder.CreateShuffleVector(V1: X, V2: Y, Mask: Shuf.getShuffleMask());
2678 Instruction *NewF;
2679 if (IsFNeg) {
2680 NewF = UnaryOperator::CreateFNeg(V: NewShuf);
2681 } else {
2682 Function *FAbs = Intrinsic::getOrInsertDeclaration(
2683 M: Shuf.getModule(), id: Intrinsic::fabs, OverloadTys: Shuf.getType());
2684 NewF = CallInst::Create(Func: FAbs, Args: {NewShuf});
2685 }
2686 NewF->copyIRFlags(V: S0);
2687 NewF->andIRFlags(V: S1);
2688 return NewF;
2689}
2690
2691/// Canonicalize casts after shuffle.
2692static Instruction *foldCastShuffle(ShuffleVectorInst &Shuf,
2693 InstCombiner::BuilderTy &Builder) {
2694 auto *Cast0 = dyn_cast<CastInst>(Val: Shuf.getOperand(i_nocapture: 0));
2695 if (!Cast0)
2696 return nullptr;
2697
2698 // TODO: Allow other opcodes? That would require easing the type restrictions
2699 // below here.
2700 CastInst::CastOps CastOpcode = Cast0->getOpcode();
2701 switch (CastOpcode) {
2702 case Instruction::SExt:
2703 case Instruction::ZExt:
2704 case Instruction::FPToSI:
2705 case Instruction::FPToUI:
2706 case Instruction::SIToFP:
2707 case Instruction::UIToFP:
2708 break;
2709 default:
2710 return nullptr;
2711 }
2712
2713 VectorType *CastSrcTy = cast<VectorType>(Val: Cast0->getSrcTy());
2714 VectorType *ShufTy = Shuf.getType();
2715 VectorType *ShufOpTy = cast<VectorType>(Val: Shuf.getOperand(i_nocapture: 0)->getType());
2716
2717 // TODO: Allow length-increasing shuffles?
2718 if (ShufTy->getElementCount().getKnownMinValue() >
2719 ShufOpTy->getElementCount().getKnownMinValue())
2720 return nullptr;
2721
2722 // shuffle (cast X), Poison, identity-with-extract-mask -->
2723 // cast (shuffle X, Poison, identity-with-extract-mask).
2724 if (isa<PoisonValue>(Val: Shuf.getOperand(i_nocapture: 1)) && Cast0->hasOneUse() &&
2725 Shuf.isIdentityWithExtract()) {
2726 auto *NewIns = Builder.CreateShuffleVector(V1: Cast0->getOperand(i_nocapture: 0),
2727 V2: PoisonValue::get(T: CastSrcTy),
2728 Mask: Shuf.getShuffleMask());
2729 return CastInst::Create(Cast0->getOpcode(), S: NewIns, Ty: Shuf.getType());
2730 }
2731
2732 auto *Cast1 = dyn_cast<CastInst>(Val: Shuf.getOperand(i_nocapture: 1));
2733 // Do we have 2 matching cast operands?
2734 if (!Cast1 || Cast0->getOpcode() != Cast1->getOpcode() ||
2735 Cast0->getSrcTy() != Cast1->getSrcTy())
2736 return nullptr;
2737
2738 // TODO: Allow element-size-decreasing casts (ex: fptosi float to i8)?
2739 assert(isa<FixedVectorType>(CastSrcTy) && isa<FixedVectorType>(ShufOpTy) &&
2740 "Expected fixed vector operands for casts and binary shuffle");
2741 if (CastSrcTy->getPrimitiveSizeInBits() > ShufOpTy->getPrimitiveSizeInBits())
2742 return nullptr;
2743
2744 // At least one of the operands must have only one use (the shuffle).
2745 if (!Cast0->hasOneUse() && !Cast1->hasOneUse())
2746 return nullptr;
2747
2748 // shuffle (cast X), (cast Y), Mask --> cast (shuffle X, Y, Mask)
2749 Value *X = Cast0->getOperand(i_nocapture: 0);
2750 Value *Y = Cast1->getOperand(i_nocapture: 0);
2751 Value *NewShuf = Builder.CreateShuffleVector(V1: X, V2: Y, Mask: Shuf.getShuffleMask());
2752 return CastInst::Create(CastOpcode, S: NewShuf, Ty: ShufTy);
2753}
2754
2755/// Try to fold an extract subvector operation.
2756static Instruction *foldIdentityExtractShuffle(ShuffleVectorInst &Shuf) {
2757 Value *Op0 = Shuf.getOperand(i_nocapture: 0), *Op1 = Shuf.getOperand(i_nocapture: 1);
2758 if (!Shuf.isIdentityWithExtract() || !match(V: Op1, P: m_Poison()))
2759 return nullptr;
2760
2761 // Check if we are extracting all bits of an inserted scalar:
2762 // extract-subvec (bitcast (inselt ?, X, 0) --> bitcast X to subvec type
2763 Value *X;
2764 if (match(V: Op0, P: m_BitCast(Op: m_InsertElt(Val: m_Value(), Elt: m_Value(V&: X), Idx: m_Zero()))) &&
2765 X->getType()->getPrimitiveSizeInBits() ==
2766 Shuf.getType()->getPrimitiveSizeInBits())
2767 return new BitCastInst(X, Shuf.getType());
2768
2769 // Try to combine 2 shuffles into 1 shuffle by concatenating a shuffle mask.
2770 Value *Y;
2771 ArrayRef<int> Mask;
2772 if (!match(V: Op0, P: m_Shuffle(v1: m_Value(V&: X), v2: m_Value(V&: Y), mask: m_Mask(Mask))))
2773 return nullptr;
2774
2775 // Be conservative with shuffle transforms. If we can't kill the 1st shuffle,
2776 // then combining may result in worse codegen.
2777 if (!Op0->hasOneUse())
2778 return nullptr;
2779
2780 // We are extracting a subvector from a shuffle. Remove excess elements from
2781 // the 1st shuffle mask to eliminate the extract.
2782 //
2783 // This transform is conservatively limited to identity extracts because we do
2784 // not allow arbitrary shuffle mask creation as a target-independent transform
2785 // (because we can't guarantee that will lower efficiently).
2786 //
2787 // If the extracting shuffle has an poison mask element, it transfers to the
2788 // new shuffle mask. Otherwise, copy the original mask element. Example:
2789 // shuf (shuf X, Y, <C0, C1, C2, poison, C4>), poison, <0, poison, 2, 3> -->
2790 // shuf X, Y, <C0, poison, C2, poison>
2791 unsigned NumElts = cast<FixedVectorType>(Val: Shuf.getType())->getNumElements();
2792 SmallVector<int, 16> NewMask(NumElts);
2793 assert(NumElts < Mask.size() &&
2794 "Identity with extract must have less elements than its inputs");
2795
2796 for (unsigned i = 0; i != NumElts; ++i) {
2797 int ExtractMaskElt = Shuf.getMaskValue(Elt: i);
2798 int MaskElt = Mask[i];
2799 NewMask[i] = ExtractMaskElt == PoisonMaskElem ? ExtractMaskElt : MaskElt;
2800 }
2801 return new ShuffleVectorInst(X, Y, NewMask);
2802}
2803
2804/// Try to replace a shuffle with an insertelement or try to replace a shuffle
2805/// operand with the operand of an insertelement.
2806static Instruction *foldShuffleWithInsert(ShuffleVectorInst &Shuf,
2807 InstCombinerImpl &IC) {
2808 Value *V0 = Shuf.getOperand(i_nocapture: 0), *V1 = Shuf.getOperand(i_nocapture: 1);
2809 SmallVector<int, 16> Mask;
2810 Shuf.getShuffleMask(Result&: Mask);
2811
2812 int NumElts = Mask.size();
2813 int InpNumElts = cast<FixedVectorType>(Val: V0->getType())->getNumElements();
2814
2815 // This is a specialization of a fold in SimplifyDemandedVectorElts. We may
2816 // not be able to handle it there if the insertelement has >1 use.
2817 // If the shuffle has an insertelement operand but does not choose the
2818 // inserted scalar element from that value, then we can replace that shuffle
2819 // operand with the source vector of the insertelement.
2820 Value *X;
2821 uint64_t IdxC;
2822 if (match(V: V0, P: m_InsertElt(Val: m_Value(V&: X), Elt: m_Value(), Idx: m_ConstantInt(V&: IdxC)))) {
2823 // shuf (inselt X, ?, IdxC), ?, Mask --> shuf X, ?, Mask
2824 if (!is_contained(Range&: Mask, Element: (int)IdxC))
2825 return IC.replaceOperand(I&: Shuf, OpNum: 0, V: X);
2826 }
2827 if (match(V: V1, P: m_InsertElt(Val: m_Value(V&: X), Elt: m_Value(), Idx: m_ConstantInt(V&: IdxC)))) {
2828 // Offset the index constant by the vector width because we are checking for
2829 // accesses to the 2nd vector input of the shuffle.
2830 IdxC += InpNumElts;
2831 // shuf ?, (inselt X, ?, IdxC), Mask --> shuf ?, X, Mask
2832 if (!is_contained(Range&: Mask, Element: (int)IdxC))
2833 return IC.replaceOperand(I&: Shuf, OpNum: 1, V: X);
2834 }
2835 // For the rest of the transform, the shuffle must not change vector sizes.
2836 // TODO: This restriction could be removed if the insert has only one use
2837 // (because the transform would require a new length-changing shuffle).
2838 if (NumElts != InpNumElts)
2839 return nullptr;
2840
2841 // shuffle (insert ?, Scalar, IndexC), V1, Mask --> insert V1, Scalar, IndexC'
2842 auto isShufflingScalarIntoOp1 = [&](Value *&Scalar, ConstantInt *&IndexC) {
2843 // We need an insertelement with a constant index.
2844 if (!match(V: V0, P: m_InsertElt(Val: m_Value(), Elt: m_Value(V&: Scalar),
2845 Idx: m_ConstantInt(CI&: IndexC))))
2846 return false;
2847
2848 // Test the shuffle mask to see if it splices the inserted scalar into the
2849 // operand 1 vector of the shuffle.
2850 int NewInsIndex = -1;
2851 for (int i = 0; i != NumElts; ++i) {
2852 // Ignore undef mask elements.
2853 if (Mask[i] == -1)
2854 continue;
2855
2856 // The shuffle takes elements of operand 1 without lane changes.
2857 if (Mask[i] == NumElts + i)
2858 continue;
2859
2860 // The shuffle must choose the inserted scalar exactly once.
2861 if (NewInsIndex != -1 || Mask[i] != IndexC->getSExtValue())
2862 return false;
2863
2864 // The shuffle is placing the inserted scalar into element i.
2865 NewInsIndex = i;
2866 }
2867
2868 assert(NewInsIndex != -1 && "Did not fold shuffle with unused operand?");
2869
2870 // Index is updated to the potentially translated insertion lane.
2871 IndexC = ConstantInt::get(Ty: IndexC->getIntegerType(), V: NewInsIndex);
2872 return true;
2873 };
2874
2875 // If the shuffle is unnecessary, insert the scalar operand directly into
2876 // operand 1 of the shuffle. Example:
2877 // shuffle (insert ?, S, 1), V1, <1, 5, 6, 7> --> insert V1, S, 0
2878 Value *Scalar;
2879 ConstantInt *IndexC;
2880 if (isShufflingScalarIntoOp1(Scalar, IndexC))
2881 return InsertElementInst::Create(Vec: V1, NewElt: Scalar, Idx: IndexC);
2882
2883 // Try again after commuting shuffle. Example:
2884 // shuffle V0, (insert ?, S, 0), <0, 1, 2, 4> -->
2885 // shuffle (insert ?, S, 0), V0, <4, 5, 6, 0> --> insert V0, S, 3
2886 std::swap(a&: V0, b&: V1);
2887 ShuffleVectorInst::commuteShuffleMask(Mask, InVecNumElts: NumElts);
2888 if (isShufflingScalarIntoOp1(Scalar, IndexC))
2889 return InsertElementInst::Create(Vec: V1, NewElt: Scalar, Idx: IndexC);
2890
2891 return nullptr;
2892}
2893
2894static Instruction *foldIdentityPaddedShuffles(ShuffleVectorInst &Shuf) {
2895 // Match the operands as identity with padding (also known as concatenation
2896 // with undef) shuffles of the same source type. The backend is expected to
2897 // recreate these concatenations from a shuffle of narrow operands.
2898 auto *Shuffle0 = dyn_cast<ShuffleVectorInst>(Val: Shuf.getOperand(i_nocapture: 0));
2899 auto *Shuffle1 = dyn_cast<ShuffleVectorInst>(Val: Shuf.getOperand(i_nocapture: 1));
2900 if (!Shuffle0 || !Shuffle0->isIdentityWithPadding() ||
2901 !Shuffle1 || !Shuffle1->isIdentityWithPadding())
2902 return nullptr;
2903
2904 // We limit this transform to power-of-2 types because we expect that the
2905 // backend can convert the simplified IR patterns to identical nodes as the
2906 // original IR.
2907 // TODO: If we can verify the same behavior for arbitrary types, the
2908 // power-of-2 checks can be removed.
2909 Value *X = Shuffle0->getOperand(i_nocapture: 0);
2910 Value *Y = Shuffle1->getOperand(i_nocapture: 0);
2911 if (X->getType() != Y->getType() ||
2912 !isPowerOf2_32(Value: cast<FixedVectorType>(Val: Shuf.getType())->getNumElements()) ||
2913 !isPowerOf2_32(
2914 Value: cast<FixedVectorType>(Val: Shuffle0->getType())->getNumElements()) ||
2915 !isPowerOf2_32(Value: cast<FixedVectorType>(Val: X->getType())->getNumElements()) ||
2916 match(V: X, P: m_Undef()) || match(V: Y, P: m_Undef()))
2917 return nullptr;
2918 assert(match(Shuffle0->getOperand(1), m_Undef()) &&
2919 match(Shuffle1->getOperand(1), m_Undef()) &&
2920 "Unexpected operand for identity shuffle");
2921
2922 // This is a shuffle of 2 widening shuffles. We can shuffle the narrow source
2923 // operands directly by adjusting the shuffle mask to account for the narrower
2924 // types:
2925 // shuf (widen X), (widen Y), Mask --> shuf X, Y, Mask'
2926 int NarrowElts = cast<FixedVectorType>(Val: X->getType())->getNumElements();
2927 int WideElts = cast<FixedVectorType>(Val: Shuffle0->getType())->getNumElements();
2928 assert(WideElts > NarrowElts && "Unexpected types for identity with padding");
2929
2930 ArrayRef<int> Mask = Shuf.getShuffleMask();
2931 SmallVector<int, 16> NewMask(Mask.size(), -1);
2932 for (int i = 0, e = Mask.size(); i != e; ++i) {
2933 if (Mask[i] == -1)
2934 continue;
2935
2936 // If this shuffle is choosing an undef element from 1 of the sources, that
2937 // element is undef.
2938 if (Mask[i] < WideElts) {
2939 if (Shuffle0->getMaskValue(Elt: Mask[i]) == -1)
2940 continue;
2941 } else {
2942 if (Shuffle1->getMaskValue(Elt: Mask[i] - WideElts) == -1)
2943 continue;
2944 }
2945
2946 // If this shuffle is choosing from the 1st narrow op, the mask element is
2947 // the same. If this shuffle is choosing from the 2nd narrow op, the mask
2948 // element is offset down to adjust for the narrow vector widths.
2949 if (Mask[i] < WideElts) {
2950 assert(Mask[i] < NarrowElts && "Unexpected shuffle mask");
2951 NewMask[i] = Mask[i];
2952 } else {
2953 assert(Mask[i] < (WideElts + NarrowElts) && "Unexpected shuffle mask");
2954 NewMask[i] = Mask[i] - (WideElts - NarrowElts);
2955 }
2956 }
2957 return new ShuffleVectorInst(X, Y, NewMask);
2958}
2959
2960// Splatting the first element of the result of a BinOp, where any of the
2961// BinOp's operands are the result of a first element splat can be simplified to
2962// splatting the first element of the result of the BinOp
2963Instruction *InstCombinerImpl::simplifyBinOpSplats(ShuffleVectorInst &SVI) {
2964 if (!match(V: SVI.getOperand(i_nocapture: 1), P: m_Poison()) ||
2965 !match(Mask: SVI.getShuffleMask(), P: m_ZeroMask()) ||
2966 !SVI.getOperand(i_nocapture: 0)->hasOneUse())
2967 return nullptr;
2968
2969 Value *Op0 = SVI.getOperand(i_nocapture: 0);
2970 Value *X, *Y;
2971 if (!match(V: Op0, P: m_BinOp(L: m_Shuffle(v1: m_Value(V&: X), v2: m_Poison(), mask: m_ZeroMask()),
2972 R: m_Value(V&: Y))) &&
2973 !match(V: Op0, P: m_BinOp(L: m_Value(V&: X),
2974 R: m_Shuffle(v1: m_Value(V&: Y), v2: m_Poison(), mask: m_ZeroMask()))))
2975 return nullptr;
2976 if (X->getType() != Y->getType())
2977 return nullptr;
2978
2979 auto *BinOp = cast<BinaryOperator>(Val: Op0);
2980 if (!isSafeToSpeculativelyExecuteWithVariableReplaced(I: BinOp))
2981 return nullptr;
2982
2983 Value *NewBO = Builder.CreateBinOp(Opc: BinOp->getOpcode(), LHS: X, RHS: Y);
2984 if (auto NewBOI = dyn_cast<Instruction>(Val: NewBO))
2985 NewBOI->copyIRFlags(V: BinOp);
2986
2987 return new ShuffleVectorInst(NewBO, SVI.getShuffleMask());
2988}
2989
2990Instruction *InstCombinerImpl::visitShuffleVectorInst(ShuffleVectorInst &SVI) {
2991 Value *LHS = SVI.getOperand(i_nocapture: 0);
2992 Value *RHS = SVI.getOperand(i_nocapture: 1);
2993 SimplifyQuery ShufQuery = SQ.getWithInstruction(I: &SVI);
2994 if (auto *V = simplifyShuffleVectorInst(Op0: LHS, Op1: RHS, Mask: SVI.getShuffleMask(),
2995 RetTy: SVI.getType(), Q: ShufQuery))
2996 return replaceInstUsesWith(I&: SVI, V);
2997
2998 if (Instruction *I = simplifyBinOpSplats(SVI))
2999 return I;
3000
3001 // Canonicalize splat shuffle to use poison RHS. Handle this explicitly in
3002 // order to support scalable vectors.
3003 if (match(Mask: SVI.getShuffleMask(), P: m_ZeroMask()) && !isa<PoisonValue>(Val: RHS))
3004 return replaceOperand(I&: SVI, OpNum: 1, V: PoisonValue::get(T: RHS->getType()));
3005
3006 if (isa<ScalableVectorType>(Val: LHS->getType()))
3007 return nullptr;
3008
3009 unsigned VWidth = cast<FixedVectorType>(Val: SVI.getType())->getNumElements();
3010 unsigned LHSWidth = cast<FixedVectorType>(Val: LHS->getType())->getNumElements();
3011
3012 // shuffle (bitcast X), (bitcast Y), Mask --> bitcast (shuffle X, Y, Mask)
3013 //
3014 // if X and Y are of the same (vector) type, and the element size is not
3015 // changed by the bitcasts, we can distribute the bitcasts through the
3016 // shuffle, hopefully reducing the number of instructions. We make sure that
3017 // at least one bitcast only has one use, so we don't *increase* the number of
3018 // instructions here.
3019 Value *X, *Y;
3020 if (match(V: LHS, P: m_BitCast(Op: m_Value(V&: X))) && match(V: RHS, P: m_BitCast(Op: m_Value(V&: Y))) &&
3021 X->getType()->isVectorTy() && X->getType() == Y->getType() &&
3022 X->getType()->getScalarSizeInBits() ==
3023 SVI.getType()->getScalarSizeInBits() &&
3024 (LHS->hasOneUse() || RHS->hasOneUse())) {
3025 Value *V = Builder.CreateShuffleVector(V1: X, V2: Y, Mask: SVI.getShuffleMask(),
3026 Name: SVI.getName() + ".uncasted");
3027 return new BitCastInst(V, SVI.getType());
3028 }
3029
3030 ArrayRef<int> Mask = SVI.getShuffleMask();
3031
3032 // Peek through a bitcasted shuffle operand by scaling the mask. If the
3033 // simulated shuffle can simplify, then this shuffle is unnecessary:
3034 // shuf (bitcast X), undef, Mask --> bitcast X'
3035 // TODO: This could be extended to allow length-changing shuffles.
3036 // The transform might also be obsoleted if we allowed canonicalization
3037 // of bitcasted shuffles.
3038 if (match(V: LHS, P: m_BitCast(Op: m_Value(V&: X))) && match(V: RHS, P: m_Undef()) &&
3039 X->getType()->isVectorTy() && VWidth == LHSWidth) {
3040 // Try to create a scaled mask constant.
3041 auto *XType = cast<FixedVectorType>(Val: X->getType());
3042 unsigned XNumElts = XType->getNumElements();
3043 SmallVector<int, 16> ScaledMask;
3044 if (scaleShuffleMaskElts(NumDstElts: XNumElts, Mask, ScaledMask)) {
3045 // If the shuffled source vector simplifies, cast that value to this
3046 // shuffle's type.
3047 if (auto *V = simplifyShuffleVectorInst(Op0: X, Op1: UndefValue::get(T: XType),
3048 Mask: ScaledMask, RetTy: XType, Q: ShufQuery))
3049 return BitCastInst::Create(Instruction::BitCast, S: V, Ty: SVI.getType());
3050 }
3051 }
3052
3053 // shuffle x, x, mask --> shuffle x, undef, mask'
3054 if (LHS == RHS) {
3055 assert(!match(RHS, m_Undef()) &&
3056 "Shuffle with 2 undef ops not simplified?");
3057 return new ShuffleVectorInst(LHS, createUnaryMask(Mask, NumElts: LHSWidth));
3058 }
3059
3060 // shuffle undef, x, mask --> shuffle x, undef, mask'
3061 if (match(V: LHS, P: m_Undef())) {
3062 SVI.commute();
3063 return &SVI;
3064 }
3065
3066 if (Instruction *I = canonicalizeInsertSplat(Shuf&: SVI, Builder))
3067 return I;
3068
3069 if (Instruction *I = foldSelectShuffle(Shuf&: SVI))
3070 return I;
3071
3072 if (Instruction *I = foldTruncShuffle(Shuf&: SVI, IsBigEndian: DL.isBigEndian()))
3073 return I;
3074
3075 if (Instruction *I = narrowVectorSelect(Shuf&: SVI, Builder))
3076 return I;
3077
3078 if (Instruction *I = foldShuffleOfUnaryOps(Shuf&: SVI, Builder))
3079 return I;
3080
3081 if (Instruction *I = foldCastShuffle(Shuf&: SVI, Builder))
3082 return I;
3083
3084 APInt PoisonElts(VWidth, 0);
3085 APInt AllOnesEltMask(APInt::getAllOnes(numBits: VWidth));
3086 if (Value *V = SimplifyDemandedVectorElts(V: &SVI, DemandedElts: AllOnesEltMask, PoisonElts)) {
3087 if (V != &SVI)
3088 return replaceInstUsesWith(I&: SVI, V);
3089 return &SVI;
3090 }
3091
3092 if (Instruction *I = foldIdentityExtractShuffle(Shuf&: SVI))
3093 return I;
3094
3095 // These transforms have the potential to lose undef knowledge, so they are
3096 // intentionally placed after SimplifyDemandedVectorElts().
3097 if (Instruction *I = foldShuffleWithInsert(Shuf&: SVI, IC&: *this))
3098 return I;
3099 if (Instruction *I = foldIdentityPaddedShuffles(Shuf&: SVI))
3100 return I;
3101
3102 if (match(V: RHS, P: m_Constant())) {
3103 if (auto *SI = dyn_cast<SelectInst>(Val: LHS)) {
3104 // We cannot do this fold for elementwise select since ShuffleVector is
3105 // not elementwise.
3106 if (SI->getCondition()->getType()->isIntegerTy() &&
3107 (isa<PoisonValue>(Val: RHS) ||
3108 isGuaranteedNotToBePoison(V: SI->getCondition()))) {
3109 if (Instruction *I = FoldOpIntoSelect(Op&: SVI, SI))
3110 return I;
3111 }
3112 }
3113 if (auto *PN = dyn_cast<PHINode>(Val: LHS)) {
3114 if (Instruction *I = foldOpIntoPhi(I&: SVI, PN, /*AllowMultipleUses=*/true))
3115 return I;
3116 }
3117 }
3118
3119 if (match(V: RHS, P: m_Poison()) && canEvaluateShuffled(V: LHS, Mask)) {
3120 Value *V = evaluateInDifferentElementOrder(V: LHS, Mask, Builder);
3121 return replaceInstUsesWith(I&: SVI, V);
3122 }
3123
3124 // SROA generates shuffle+bitcast when the extracted sub-vector is bitcast to
3125 // a non-vector type. We can instead bitcast the original vector followed by
3126 // an extract of the desired element:
3127 //
3128 // %sroa = shufflevector <16 x i8> %in, <16 x i8> undef,
3129 // <4 x i32> <i32 0, i32 1, i32 2, i32 3>
3130 // %1 = bitcast <4 x i8> %sroa to i32
3131 // Becomes:
3132 // %bc = bitcast <16 x i8> %in to <4 x i32>
3133 // %ext = extractelement <4 x i32> %bc, i32 0
3134 //
3135 // If the shuffle is extracting a contiguous range of values from the input
3136 // vector then each use which is a bitcast of the extracted size can be
3137 // replaced. This will work if the vector types are compatible, and the begin
3138 // index is aligned to a value in the casted vector type. If the begin index
3139 // isn't aligned then we can shuffle the original vector (keeping the same
3140 // vector type) before extracting.
3141 //
3142 // This code will bail out if the target type is fundamentally incompatible
3143 // with vectors of the source type.
3144 //
3145 // Example of <16 x i8>, target type i32:
3146 // Index range [4,8): v-----------v Will work.
3147 // +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
3148 // <16 x i8>: | | | | | | | | | | | | | | | | |
3149 // <4 x i32>: | | | | |
3150 // +-----------+-----------+-----------+-----------+
3151 // Index range [6,10): ^-----------^ Needs an extra shuffle.
3152 // Target type i40: ^--------------^ Won't work, bail.
3153 bool MadeChange = false;
3154 if (isShuffleExtractingFromLHS(SVI, Mask)) {
3155 Value *V = LHS;
3156 unsigned MaskElems = Mask.size();
3157 auto *SrcTy = cast<FixedVectorType>(Val: V->getType());
3158 unsigned VecBitWidth = DL.getTypeSizeInBits(Ty: SrcTy);
3159 unsigned SrcElemBitWidth = DL.getTypeSizeInBits(Ty: SrcTy->getElementType());
3160 assert(SrcElemBitWidth && "vector elements must have a bitwidth");
3161 unsigned SrcNumElems = SrcTy->getNumElements();
3162 SmallVector<BitCastInst *, 8> BCs;
3163 DenseMap<Type *, Value *> NewBCs;
3164 for (User *U : SVI.users())
3165 if (BitCastInst *BC = dyn_cast<BitCastInst>(Val: U)) {
3166 // Only visit bitcasts that weren't previously handled.
3167 if (BC->use_empty())
3168 continue;
3169 // Prefer to combine bitcasts of bitcasts before attempting this fold.
3170 if (BC->hasOneUse()) {
3171 auto *BC2 = dyn_cast<BitCastInst>(Val: BC->user_back());
3172 if (BC2 && isEliminableCastPair(CI1: BC, CI2: BC2))
3173 continue;
3174 }
3175 BCs.push_back(Elt: BC);
3176 }
3177 for (BitCastInst *BC : BCs) {
3178 unsigned BegIdx = Mask.front();
3179 Type *TgtTy = BC->getDestTy();
3180 unsigned TgtElemBitWidth = DL.getTypeSizeInBits(Ty: TgtTy);
3181 if (!TgtElemBitWidth)
3182 continue;
3183 unsigned TgtNumElems = VecBitWidth / TgtElemBitWidth;
3184 bool VecBitWidthsEqual = VecBitWidth == TgtNumElems * TgtElemBitWidth;
3185 bool BegIsAligned = 0 == ((SrcElemBitWidth * BegIdx) % TgtElemBitWidth);
3186 if (!VecBitWidthsEqual)
3187 continue;
3188 if (!VectorType::isValidElementType(ElemTy: TgtTy))
3189 continue;
3190 auto *CastSrcTy = FixedVectorType::get(ElementType: TgtTy, NumElts: TgtNumElems);
3191 if (!BegIsAligned) {
3192 // Shuffle the input so [0,NumElements) contains the output, and
3193 // [NumElems,SrcNumElems) is undef.
3194 SmallVector<int, 16> ShuffleMask(SrcNumElems, -1);
3195 for (unsigned I = 0, E = MaskElems, Idx = BegIdx; I != E; ++Idx, ++I)
3196 ShuffleMask[I] = Idx;
3197 V = Builder.CreateShuffleVector(V, Mask: ShuffleMask,
3198 Name: SVI.getName() + ".extract");
3199 BegIdx = 0;
3200 }
3201 unsigned SrcElemsPerTgtElem = TgtElemBitWidth / SrcElemBitWidth;
3202 assert(SrcElemsPerTgtElem);
3203 BegIdx /= SrcElemsPerTgtElem;
3204 auto [It, Inserted] = NewBCs.try_emplace(Key: CastSrcTy);
3205 if (Inserted)
3206 It->second = Builder.CreateBitCast(V, DestTy: CastSrcTy, Name: SVI.getName() + ".bc");
3207 auto *Ext = Builder.CreateExtractElement(Vec: It->second, Idx: BegIdx,
3208 Name: SVI.getName() + ".extract");
3209 // The shufflevector isn't being replaced: the bitcast that used it
3210 // is. InstCombine will visit the newly-created instructions.
3211 replaceInstUsesWith(I&: *BC, V: Ext);
3212 MadeChange = true;
3213 }
3214 }
3215
3216 // If the LHS is a shufflevector itself, see if we can combine it with this
3217 // one without producing an unusual shuffle.
3218 // Cases that might be simplified:
3219 // 1.
3220 // x1=shuffle(v1,v2,mask1)
3221 // x=shuffle(x1,undef,mask)
3222 // ==>
3223 // x=shuffle(v1,undef,newMask)
3224 // newMask[i] = (mask[i] < x1.size()) ? mask1[mask[i]] : -1
3225 // 2.
3226 // x1=shuffle(v1,undef,mask1)
3227 // x=shuffle(x1,x2,mask)
3228 // where v1.size() == mask1.size()
3229 // ==>
3230 // x=shuffle(v1,x2,newMask)
3231 // newMask[i] = (mask[i] < x1.size()) ? mask1[mask[i]] : mask[i]
3232 // 3.
3233 // x2=shuffle(v2,undef,mask2)
3234 // x=shuffle(x1,x2,mask)
3235 // where v2.size() == mask2.size()
3236 // ==>
3237 // x=shuffle(x1,v2,newMask)
3238 // newMask[i] = (mask[i] < x1.size())
3239 // ? mask[i] : mask2[mask[i]-x1.size()]+x1.size()
3240 // 4.
3241 // x1=shuffle(v1,undef,mask1)
3242 // x2=shuffle(v2,undef,mask2)
3243 // x=shuffle(x1,x2,mask)
3244 // where v1.size() == v2.size()
3245 // ==>
3246 // x=shuffle(v1,v2,newMask)
3247 // newMask[i] = (mask[i] < x1.size())
3248 // ? mask1[mask[i]] : mask2[mask[i]-x1.size()]+v1.size()
3249 //
3250 // Here we are really conservative:
3251 // we are absolutely afraid of producing a shuffle mask not in the input
3252 // program, because the code gen may not be smart enough to turn a merged
3253 // shuffle into two specific shuffles: it may produce worse code. As such,
3254 // we only merge two shuffles if the result is either a splat or one of the
3255 // input shuffle masks. In this case, merging the shuffles just removes
3256 // one instruction, which we know is safe. This is good for things like
3257 // turning: (splat(splat)) -> splat, or
3258 // merge(V[0..n], V[n+1..2n]) -> V[0..2n]
3259 ShuffleVectorInst* LHSShuffle = dyn_cast<ShuffleVectorInst>(Val: LHS);
3260 ShuffleVectorInst* RHSShuffle = dyn_cast<ShuffleVectorInst>(Val: RHS);
3261 if (LHSShuffle)
3262 if (!match(V: LHSShuffle->getOperand(i_nocapture: 1), P: m_Poison()) &&
3263 !match(V: RHS, P: m_Poison()))
3264 LHSShuffle = nullptr;
3265 if (RHSShuffle)
3266 if (!match(V: RHSShuffle->getOperand(i_nocapture: 1), P: m_Poison()))
3267 RHSShuffle = nullptr;
3268 if (!LHSShuffle && !RHSShuffle)
3269 return MadeChange ? &SVI : nullptr;
3270
3271 Value* LHSOp0 = nullptr;
3272 Value* LHSOp1 = nullptr;
3273 Value* RHSOp0 = nullptr;
3274 unsigned LHSOp0Width = 0;
3275 unsigned RHSOp0Width = 0;
3276 if (LHSShuffle) {
3277 LHSOp0 = LHSShuffle->getOperand(i_nocapture: 0);
3278 LHSOp1 = LHSShuffle->getOperand(i_nocapture: 1);
3279 LHSOp0Width = cast<FixedVectorType>(Val: LHSOp0->getType())->getNumElements();
3280 }
3281 if (RHSShuffle) {
3282 RHSOp0 = RHSShuffle->getOperand(i_nocapture: 0);
3283 RHSOp0Width = cast<FixedVectorType>(Val: RHSOp0->getType())->getNumElements();
3284 }
3285 Value* newLHS = LHS;
3286 Value* newRHS = RHS;
3287 if (LHSShuffle) {
3288 // case 1
3289 if (match(V: RHS, P: m_Poison())) {
3290 newLHS = LHSOp0;
3291 newRHS = LHSOp1;
3292 }
3293 // case 2 or 4
3294 else if (LHSOp0Width == LHSWidth) {
3295 newLHS = LHSOp0;
3296 }
3297 }
3298 // case 3 or 4
3299 if (RHSShuffle && RHSOp0Width == LHSWidth) {
3300 newRHS = RHSOp0;
3301 }
3302 // case 4
3303 if (LHSOp0 == RHSOp0) {
3304 newLHS = LHSOp0;
3305 newRHS = nullptr;
3306 }
3307
3308 if (newLHS == LHS && newRHS == RHS)
3309 return MadeChange ? &SVI : nullptr;
3310
3311 ArrayRef<int> LHSMask;
3312 ArrayRef<int> RHSMask;
3313 if (newLHS != LHS)
3314 LHSMask = LHSShuffle->getShuffleMask();
3315 if (RHSShuffle && newRHS != RHS)
3316 RHSMask = RHSShuffle->getShuffleMask();
3317
3318 unsigned newLHSWidth = (newLHS != LHS) ? LHSOp0Width : LHSWidth;
3319 SmallVector<int, 16> newMask;
3320 bool isSplat = true;
3321 int SplatElt = -1;
3322 // Create a new mask for the new ShuffleVectorInst so that the new
3323 // ShuffleVectorInst is equivalent to the original one.
3324 for (unsigned i = 0; i < VWidth; ++i) {
3325 int eltMask;
3326 if (Mask[i] < 0) {
3327 // This element is a poison value.
3328 eltMask = -1;
3329 } else if (Mask[i] < (int)LHSWidth) {
3330 // This element is from left hand side vector operand.
3331 //
3332 // If LHS is going to be replaced (case 1, 2, or 4), calculate the
3333 // new mask value for the element.
3334 if (newLHS != LHS) {
3335 eltMask = LHSMask[Mask[i]];
3336 // If the value selected is an poison value, explicitly specify it
3337 // with a -1 mask value.
3338 if (eltMask >= (int)LHSOp0Width && isa<PoisonValue>(Val: LHSOp1))
3339 eltMask = -1;
3340 } else
3341 eltMask = Mask[i];
3342 } else {
3343 // This element is from right hand side vector operand
3344 //
3345 // If the value selected is a poison value, explicitly specify it
3346 // with a -1 mask value. (case 1)
3347 if (match(V: RHS, P: m_Poison()))
3348 eltMask = -1;
3349 // If RHS is going to be replaced (case 3 or 4), calculate the
3350 // new mask value for the element.
3351 else if (newRHS != RHS) {
3352 eltMask = RHSMask[Mask[i]-LHSWidth];
3353 // If the value selected is an poison value, explicitly specify it
3354 // with a -1 mask value.
3355 if (eltMask >= (int)RHSOp0Width) {
3356 assert(match(RHSShuffle->getOperand(1), m_Poison()) &&
3357 "should have been check above");
3358 eltMask = -1;
3359 }
3360 } else
3361 eltMask = Mask[i]-LHSWidth;
3362
3363 // If LHS's width is changed, shift the mask value accordingly.
3364 // If newRHS == nullptr, i.e. LHSOp0 == RHSOp0, we want to remap any
3365 // references from RHSOp0 to LHSOp0, so we don't need to shift the mask.
3366 // If newRHS == newLHS, we want to remap any references from newRHS to
3367 // newLHS so that we can properly identify splats that may occur due to
3368 // obfuscation across the two vectors.
3369 if (eltMask >= 0 && newRHS != nullptr && newLHS != newRHS)
3370 eltMask += newLHSWidth;
3371 }
3372
3373 // Check if this could still be a splat.
3374 if (eltMask >= 0) {
3375 if (SplatElt >= 0 && SplatElt != eltMask)
3376 isSplat = false;
3377 SplatElt = eltMask;
3378 }
3379
3380 newMask.push_back(Elt: eltMask);
3381 }
3382
3383 // If the result mask is equal to one of the original shuffle masks,
3384 // or is a splat, do the replacement.
3385 if (isSplat || newMask == LHSMask || newMask == RHSMask || newMask == Mask) {
3386 if (!newRHS)
3387 newRHS = PoisonValue::get(T: newLHS->getType());
3388 return new ShuffleVectorInst(newLHS, newRHS, newMask);
3389 }
3390
3391 return MadeChange ? &SVI : nullptr;
3392}
3393
3394/// Given the following de-interleaving shufflevectors and the consuming zexts:
3395/// ```
3396/// %f0 = shufflevector <8 x i32> %v, <4 x i32> <i32 0, i32 2, i32 4, i32 6>
3397/// %f1 = shufflevector <8 x i32> %v, <4 x i32> <i32 1, i32 3, i32 5, i32 7>
3398/// %z0 = zext <4 x i32> %f0 to <4 x i64>
3399/// %z1 = zext <4 x i32> %f1 to <4 x i64>
3400/// ```
3401/// We can actually bitcast the input value, `%v` first before replacing zexts
3402/// with simple arithmetics on this new bitcast:
3403/// ```
3404/// %bc = bitcast <8 x i32> %v to <4 x i64>
3405// %z0 = and <4 x i64> %bc, splat (i64 4294967295)
3406// %z1 = lshr <4 x i64> %bc, splat (i64 32)
3407/// ```
3408/// This transformation is almost always benefitial as shufflevector is more
3409/// expensive than normal arithmetics.
3410Instruction *
3411InstCombinerImpl::foldExtractionOfVectorDeinterleave(ZExtInst &RootZExt) {
3412 // This pattern involves bitcast that is not compatible with big endian.
3413 if (DL.isBigEndian())
3414 return nullptr;
3415
3416 // The actual value that got de-interleaved.
3417 Value *DIV;
3418
3419 using namespace PatternMatch;
3420 Instruction *SVI = nullptr, *DI = nullptr;
3421 if (!match(
3422 V: &RootZExt,
3423 P: m_ZExt(Op: m_CombineOr(
3424 Ps: m_ExtractValue(V: m_Instruction(I&: DI, P: m_Deinterleave2(Op: m_Value(V&: DIV)))),
3425 Ps: m_Instruction(I&: SVI, P: m_Shuffle(v1: m_Value(), v2: m_Value()))))))
3426 return nullptr;
3427
3428 auto isDeinterleaveShuffle =
3429 [](Instruction *I) -> std::pair<Value *, unsigned> {
3430 Value *V;
3431 ArrayRef<int> ShuffleMask;
3432 unsigned Index;
3433 if (match(V: I, P: m_Shuffle(v1: m_Value(V), v2: m_Undef(), mask: m_Mask(ShuffleMask))) &&
3434 isa<FixedVectorType>(Val: V->getType())) {
3435 unsigned NumInputElements =
3436 cast<VectorType>(Val: V->getType())->getElementCount().getFixedValue();
3437 if (ShuffleVectorInst::isDeInterleaveMaskOfFactor(Mask: ShuffleMask, Factor: 2,
3438 Index) &&
3439 Index < 2 &&
3440 ShuffleVectorInst::isSingleSourceMask(Mask: ShuffleMask,
3441 NumSrcElts: NumInputElements) &&
3442 ShuffleMask.size() * 2 == NumInputElements)
3443 return {V, Index};
3444 }
3445 return {nullptr, UINT_MAX};
3446 };
3447
3448 // Validate either the shufflevector or the vector.deinterleave2 and obtain
3449 // the value they're de-interleaving.
3450 if (SVI) {
3451 // We will find other shufflevectors later.
3452 DIV = isDeinterleaveShuffle(SVI).first;
3453 if (!DIV)
3454 return nullptr;
3455 } else {
3456 // We should already capture the value that got de-interleaved (i.e. DIV).
3457 assert(DI && DIV);
3458 if (!all_of(Range: DI->users(), P: [](User *Usr) -> bool {
3459 auto *EV = dyn_cast<ExtractValueInst>(Val: Usr);
3460 return EV && EV->getNumIndices() == 1;
3461 }))
3462 return nullptr;
3463 }
3464
3465 auto *InputVecTy = dyn_cast<VectorType>(Val: DIV->getType());
3466 if (!InputVecTy)
3467 return nullptr;
3468 auto *InElementTy = dyn_cast<IntegerType>(Val: InputVecTy->getElementType());
3469 if (!InElementTy)
3470 return nullptr;
3471 if (!InputVecTy->getElementCount().isKnownEven())
3472 return nullptr;
3473
3474 // {Field instruction, Field index}
3475 SmallVector<std::pair<Instruction *, unsigned>, 4> Fields;
3476 if (SVI) {
3477 for (auto *Usr : DIV->users()) {
3478 auto *FieldI = dyn_cast<Instruction>(Val: Usr);
3479 if (!FieldI)
3480 continue;
3481 auto [V, Index] = isDeinterleaveShuffle(FieldI);
3482 if (V != DIV)
3483 continue;
3484 assert(Index < 2);
3485 // Find the earliest field extraction instruction.
3486 if (FieldI->getParent() != SVI->getParent())
3487 continue;
3488 if (FieldI != SVI && FieldI->comesBefore(Other: SVI))
3489 SVI = FieldI;
3490 Fields.push_back(Elt: {FieldI, Index});
3491 }
3492 } else {
3493 // llvm.vector.deinterleave2.
3494 for (User *Field : DI->users()) {
3495 auto *FieldI = cast<ExtractValueInst>(Val: Field);
3496 unsigned FieldIdx = *FieldI->idx_begin();
3497 assert(FieldIdx < 2);
3498 Fields.push_back(Elt: {FieldI, FieldIdx});
3499 }
3500 }
3501
3502 // {field to be replaced, field index}
3503 SmallVector<std::pair<ZExtInst *, unsigned>, 4> FieldReplacements;
3504 // We commit the transformation only if all the field users can be replaced,
3505 // otherwise the primary de-interleaving construction, regardless of
3506 // llvm.vector.deinterleave2 or shufflevectors, will still be there.
3507 for (auto [Field, FieldIdx] : Fields) {
3508 for (User *FieldUsr : Field->users()) {
3509 auto *ZExt = dyn_cast<ZExtInst>(Val: FieldUsr);
3510 if (!ZExt)
3511 return nullptr;
3512 // Only if it's doubling the element size.
3513 if (ZExt->getDestTy() != ZExt->getSrcTy()->getExtendedType())
3514 return nullptr;
3515 FieldReplacements.push_back(Elt: {ZExt, FieldIdx});
3516 }
3517 }
3518
3519 // This will insert replacement instructions before all the fields users.
3520 Builder.SetInsertPoint(DI ? DI : SVI);
3521
3522 // Double the element size but half the vector length.
3523 auto *BitcastedTy = VectorType::getExtendedElementVectorType(VTy: InputVecTy);
3524 BitcastedTy = VectorType::getHalfElementsVectorType(VTy: BitcastedTy);
3525 // Since we're going to "merge" lanes via bitcast, we need to freeze any
3526 // potential poison lanes first.
3527 Value *Freeze = Builder.CreateFreeze(V: DIV);
3528 Value *Bitcast = Builder.CreateBitCast(V: Freeze, DestTy: BitcastedTy);
3529 unsigned InElementBitWidth = InElementTy->getBitWidth();
3530 auto Mask = APInt::getLowBitsSet(numBits: InElementBitWidth * 2, loBitsSet: InElementBitWidth);
3531 Value *NewField0 = Builder.CreateAnd(LHS: Bitcast, RHS: Mask);
3532 Value *NewField1 = Builder.CreateLShr(LHS: Bitcast, RHS: InElementBitWidth);
3533
3534 for (auto [I, Idx] : FieldReplacements) {
3535 assert(Idx < 2 && "unsupported field index");
3536 replaceInstUsesWith(I&: *I, V: Idx ? NewField1 : NewField0);
3537 // Make sure the old ZExt are in the worklist so that they
3538 // can be removed in the following iterations.
3539 addToWorklist(I);
3540 }
3541
3542 return &RootZExt;
3543}
3544