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/Analysis/InstructionSimplify.h"
22 #include "llvm/Analysis/VectorUtils.h"
23 #include "llvm/IR/BasicBlock.h"
24 #include "llvm/IR/Constant.h"
25 #include "llvm/IR/Constants.h"
26 #include "llvm/IR/DerivedTypes.h"
27 #include "llvm/IR/InstrTypes.h"
28 #include "llvm/IR/Instruction.h"
29 #include "llvm/IR/Instructions.h"
30 #include "llvm/IR/Operator.h"
31 #include "llvm/IR/PatternMatch.h"
32 #include "llvm/IR/Type.h"
33 #include "llvm/IR/User.h"
34 #include "llvm/IR/Value.h"
35 #include "llvm/Support/Casting.h"
36 #include "llvm/Support/ErrorHandling.h"
37 #include "llvm/Transforms/InstCombine/InstCombineWorklist.h"
38 #include <cassert>
39 #include <cstdint>
40 #include <iterator>
41 #include <utility>
42
43 using namespace llvm;
44 using namespace PatternMatch;
45
46 #define DEBUG_TYPE "instcombine"
47
48 /// Return true if the value is cheaper to scalarize than it is to leave as a
49 /// vector operation. IsConstantExtractIndex indicates whether we are extracting
50 /// one known element from a vector constant.
51 ///
52 /// FIXME: It's possible to create more instructions than previously existed.
cheapToScalarize(Value * V,bool IsConstantExtractIndex)53 static bool cheapToScalarize(Value *V, bool IsConstantExtractIndex) {
54 // If we can pick a scalar constant value out of a vector, that is free.
55 if (auto *C = dyn_cast<Constant>(V))
56 return IsConstantExtractIndex || C->getSplatValue();
57
58 // An insertelement to the same constant index as our extract will simplify
59 // to the scalar inserted element. An insertelement to a different constant
60 // index is irrelevant to our extract.
61 if (match(V, m_InsertElt(m_Value(), m_Value(), m_ConstantInt())))
62 return IsConstantExtractIndex;
63
64 if (match(V, m_OneUse(m_Load(m_Value()))))
65 return true;
66
67 if (match(V, m_OneUse(m_UnOp())))
68 return true;
69
70 Value *V0, *V1;
71 if (match(V, m_OneUse(m_BinOp(m_Value(V0), m_Value(V1)))))
72 if (cheapToScalarize(V0, IsConstantExtractIndex) ||
73 cheapToScalarize(V1, IsConstantExtractIndex))
74 return true;
75
76 CmpInst::Predicate UnusedPred;
77 if (match(V, m_OneUse(m_Cmp(UnusedPred, m_Value(V0), m_Value(V1)))))
78 if (cheapToScalarize(V0, IsConstantExtractIndex) ||
79 cheapToScalarize(V1, IsConstantExtractIndex))
80 return true;
81
82 return false;
83 }
84
85 // If we have a PHI node with a vector type that is only used to feed
86 // itself and be an operand of extractelement at a constant location,
87 // try to replace the PHI of the vector type with a PHI of a scalar type.
scalarizePHI(ExtractElementInst & EI,PHINode * PN)88 Instruction *InstCombiner::scalarizePHI(ExtractElementInst &EI, PHINode *PN) {
89 SmallVector<Instruction *, 2> Extracts;
90 // The users we want the PHI to have are:
91 // 1) The EI ExtractElement (we already know this)
92 // 2) Possibly more ExtractElements with the same index.
93 // 3) Another operand, which will feed back into the PHI.
94 Instruction *PHIUser = nullptr;
95 for (auto U : PN->users()) {
96 if (ExtractElementInst *EU = dyn_cast<ExtractElementInst>(U)) {
97 if (EI.getIndexOperand() == EU->getIndexOperand())
98 Extracts.push_back(EU);
99 else
100 return nullptr;
101 } else if (!PHIUser) {
102 PHIUser = cast<Instruction>(U);
103 } else {
104 return nullptr;
105 }
106 }
107
108 if (!PHIUser)
109 return nullptr;
110
111 // Verify that this PHI user has one use, which is the PHI itself,
112 // and that it is a binary operation which is cheap to scalarize.
113 // otherwise return nullptr.
114 if (!PHIUser->hasOneUse() || !(PHIUser->user_back() == PN) ||
115 !(isa<BinaryOperator>(PHIUser)) || !cheapToScalarize(PHIUser, true))
116 return nullptr;
117
118 // Create a scalar PHI node that will replace the vector PHI node
119 // just before the current PHI node.
120 PHINode *scalarPHI = cast<PHINode>(InsertNewInstWith(
121 PHINode::Create(EI.getType(), PN->getNumIncomingValues(), ""), *PN));
122 // Scalarize each PHI operand.
123 for (unsigned i = 0; i < PN->getNumIncomingValues(); i++) {
124 Value *PHIInVal = PN->getIncomingValue(i);
125 BasicBlock *inBB = PN->getIncomingBlock(i);
126 Value *Elt = EI.getIndexOperand();
127 // If the operand is the PHI induction variable:
128 if (PHIInVal == PHIUser) {
129 // Scalarize the binary operation. Its first operand is the
130 // scalar PHI, and the second operand is extracted from the other
131 // vector operand.
132 BinaryOperator *B0 = cast<BinaryOperator>(PHIUser);
133 unsigned opId = (B0->getOperand(0) == PN) ? 1 : 0;
134 Value *Op = InsertNewInstWith(
135 ExtractElementInst::Create(B0->getOperand(opId), Elt,
136 B0->getOperand(opId)->getName() + ".Elt"),
137 *B0);
138 Value *newPHIUser = InsertNewInstWith(
139 BinaryOperator::CreateWithCopiedFlags(B0->getOpcode(),
140 scalarPHI, Op, B0), *B0);
141 scalarPHI->addIncoming(newPHIUser, inBB);
142 } else {
143 // Scalarize PHI input:
144 Instruction *newEI = ExtractElementInst::Create(PHIInVal, Elt, "");
145 // Insert the new instruction into the predecessor basic block.
146 Instruction *pos = dyn_cast<Instruction>(PHIInVal);
147 BasicBlock::iterator InsertPos;
148 if (pos && !isa<PHINode>(pos)) {
149 InsertPos = ++pos->getIterator();
150 } else {
151 InsertPos = inBB->getFirstInsertionPt();
152 }
153
154 InsertNewInstWith(newEI, *InsertPos);
155
156 scalarPHI->addIncoming(newEI, inBB);
157 }
158 }
159
160 for (auto E : Extracts)
161 replaceInstUsesWith(*E, scalarPHI);
162
163 return &EI;
164 }
165
foldBitcastExtElt(ExtractElementInst & Ext,InstCombiner::BuilderTy & Builder,bool IsBigEndian)166 static Instruction *foldBitcastExtElt(ExtractElementInst &Ext,
167 InstCombiner::BuilderTy &Builder,
168 bool IsBigEndian) {
169 Value *X;
170 uint64_t ExtIndexC;
171 if (!match(Ext.getVectorOperand(), m_BitCast(m_Value(X))) ||
172 !X->getType()->isVectorTy() ||
173 !match(Ext.getIndexOperand(), m_ConstantInt(ExtIndexC)))
174 return nullptr;
175
176 // If this extractelement is using a bitcast from a vector of the same number
177 // of elements, see if we can find the source element from the source vector:
178 // extelt (bitcast VecX), IndexC --> bitcast X[IndexC]
179 auto *SrcTy = cast<VectorType>(X->getType());
180 Type *DestTy = Ext.getType();
181 unsigned NumSrcElts = SrcTy->getNumElements();
182 unsigned NumElts = Ext.getVectorOperandType()->getNumElements();
183 if (NumSrcElts == NumElts)
184 if (Value *Elt = findScalarElement(X, ExtIndexC))
185 return new BitCastInst(Elt, DestTy);
186
187 // If the source elements are wider than the destination, try to shift and
188 // truncate a subset of scalar bits of an insert op.
189 if (NumSrcElts < NumElts) {
190 Value *Scalar;
191 uint64_t InsIndexC;
192 if (!match(X, m_InsertElt(m_Value(), m_Value(Scalar),
193 m_ConstantInt(InsIndexC))))
194 return nullptr;
195
196 // The extract must be from the subset of vector elements that we inserted
197 // into. Example: if we inserted element 1 of a <2 x i64> and we are
198 // extracting an i16 (narrowing ratio = 4), then this extract must be from 1
199 // of elements 4-7 of the bitcasted vector.
200 unsigned NarrowingRatio = NumElts / NumSrcElts;
201 if (ExtIndexC / NarrowingRatio != InsIndexC)
202 return nullptr;
203
204 // We are extracting part of the original scalar. How that scalar is
205 // inserted into the vector depends on the endian-ness. Example:
206 // Vector Byte Elt Index: 0 1 2 3 4 5 6 7
207 // +--+--+--+--+--+--+--+--+
208 // inselt <2 x i32> V, <i32> S, 1: |V0|V1|V2|V3|S0|S1|S2|S3|
209 // extelt <4 x i16> V', 3: | |S2|S3|
210 // +--+--+--+--+--+--+--+--+
211 // If this is little-endian, S2|S3 are the MSB of the 32-bit 'S' value.
212 // If this is big-endian, S2|S3 are the LSB of the 32-bit 'S' value.
213 // In this example, we must right-shift little-endian. Big-endian is just a
214 // truncate.
215 unsigned Chunk = ExtIndexC % NarrowingRatio;
216 if (IsBigEndian)
217 Chunk = NarrowingRatio - 1 - Chunk;
218
219 // Bail out if this is an FP vector to FP vector sequence. That would take
220 // more instructions than we started with unless there is no shift, and it
221 // may not be handled as well in the backend.
222 bool NeedSrcBitcast = SrcTy->getScalarType()->isFloatingPointTy();
223 bool NeedDestBitcast = DestTy->isFloatingPointTy();
224 if (NeedSrcBitcast && NeedDestBitcast)
225 return nullptr;
226
227 unsigned SrcWidth = SrcTy->getScalarSizeInBits();
228 unsigned DestWidth = DestTy->getPrimitiveSizeInBits();
229 unsigned ShAmt = Chunk * DestWidth;
230
231 // TODO: This limitation is more strict than necessary. We could sum the
232 // number of new instructions and subtract the number eliminated to know if
233 // we can proceed.
234 if (!X->hasOneUse() || !Ext.getVectorOperand()->hasOneUse())
235 if (NeedSrcBitcast || NeedDestBitcast)
236 return nullptr;
237
238 if (NeedSrcBitcast) {
239 Type *SrcIntTy = IntegerType::getIntNTy(Scalar->getContext(), SrcWidth);
240 Scalar = Builder.CreateBitCast(Scalar, SrcIntTy);
241 }
242
243 if (ShAmt) {
244 // Bail out if we could end with more instructions than we started with.
245 if (!Ext.getVectorOperand()->hasOneUse())
246 return nullptr;
247 Scalar = Builder.CreateLShr(Scalar, ShAmt);
248 }
249
250 if (NeedDestBitcast) {
251 Type *DestIntTy = IntegerType::getIntNTy(Scalar->getContext(), DestWidth);
252 return new BitCastInst(Builder.CreateTrunc(Scalar, DestIntTy), DestTy);
253 }
254 return new TruncInst(Scalar, DestTy);
255 }
256
257 return nullptr;
258 }
259
260 /// Find elements of V demanded by UserInstr.
findDemandedEltsBySingleUser(Value * V,Instruction * UserInstr)261 static APInt findDemandedEltsBySingleUser(Value *V, Instruction *UserInstr) {
262 unsigned VWidth = cast<VectorType>(V->getType())->getNumElements();
263
264 // Conservatively assume that all elements are needed.
265 APInt UsedElts(APInt::getAllOnesValue(VWidth));
266
267 switch (UserInstr->getOpcode()) {
268 case Instruction::ExtractElement: {
269 ExtractElementInst *EEI = cast<ExtractElementInst>(UserInstr);
270 assert(EEI->getVectorOperand() == V);
271 ConstantInt *EEIIndexC = dyn_cast<ConstantInt>(EEI->getIndexOperand());
272 if (EEIIndexC && EEIIndexC->getValue().ult(VWidth)) {
273 UsedElts = APInt::getOneBitSet(VWidth, EEIIndexC->getZExtValue());
274 }
275 break;
276 }
277 case Instruction::ShuffleVector: {
278 ShuffleVectorInst *Shuffle = cast<ShuffleVectorInst>(UserInstr);
279 unsigned MaskNumElts =
280 cast<VectorType>(UserInstr->getType())->getNumElements();
281
282 UsedElts = APInt(VWidth, 0);
283 for (unsigned i = 0; i < MaskNumElts; i++) {
284 unsigned MaskVal = Shuffle->getMaskValue(i);
285 if (MaskVal == -1u || MaskVal >= 2 * VWidth)
286 continue;
287 if (Shuffle->getOperand(0) == V && (MaskVal < VWidth))
288 UsedElts.setBit(MaskVal);
289 if (Shuffle->getOperand(1) == V &&
290 ((MaskVal >= VWidth) && (MaskVal < 2 * VWidth)))
291 UsedElts.setBit(MaskVal - VWidth);
292 }
293 break;
294 }
295 default:
296 break;
297 }
298 return UsedElts;
299 }
300
301 /// Find union of elements of V demanded by all its users.
302 /// If it is known by querying findDemandedEltsBySingleUser that
303 /// no user demands an element of V, then the corresponding bit
304 /// remains unset in the returned value.
findDemandedEltsByAllUsers(Value * V)305 static APInt findDemandedEltsByAllUsers(Value *V) {
306 unsigned VWidth = cast<VectorType>(V->getType())->getNumElements();
307
308 APInt UnionUsedElts(VWidth, 0);
309 for (const Use &U : V->uses()) {
310 if (Instruction *I = dyn_cast<Instruction>(U.getUser())) {
311 UnionUsedElts |= findDemandedEltsBySingleUser(V, I);
312 } else {
313 UnionUsedElts = APInt::getAllOnesValue(VWidth);
314 break;
315 }
316
317 if (UnionUsedElts.isAllOnesValue())
318 break;
319 }
320
321 return UnionUsedElts;
322 }
323
visitExtractElementInst(ExtractElementInst & EI)324 Instruction *InstCombiner::visitExtractElementInst(ExtractElementInst &EI) {
325 Value *SrcVec = EI.getVectorOperand();
326 Value *Index = EI.getIndexOperand();
327 if (Value *V = SimplifyExtractElementInst(SrcVec, Index,
328 SQ.getWithInstruction(&EI)))
329 return replaceInstUsesWith(EI, V);
330
331 // If extracting a specified index from the vector, see if we can recursively
332 // find a previously computed scalar that was inserted into the vector.
333 auto *IndexC = dyn_cast<ConstantInt>(Index);
334 if (IndexC) {
335 ElementCount EC = EI.getVectorOperandType()->getElementCount();
336 unsigned NumElts = EC.Min;
337
338 // InstSimplify should handle cases where the index is invalid.
339 // For fixed-length vector, it's invalid to extract out-of-range element.
340 if (!EC.Scalable && IndexC->getValue().uge(NumElts))
341 return nullptr;
342
343 // This instruction only demands the single element from the input vector.
344 // Skip for scalable type, the number of elements is unknown at
345 // compile-time.
346 if (!EC.Scalable && NumElts != 1) {
347 // If the input vector has a single use, simplify it based on this use
348 // property.
349 if (SrcVec->hasOneUse()) {
350 APInt UndefElts(NumElts, 0);
351 APInt DemandedElts(NumElts, 0);
352 DemandedElts.setBit(IndexC->getZExtValue());
353 if (Value *V =
354 SimplifyDemandedVectorElts(SrcVec, DemandedElts, UndefElts))
355 return replaceOperand(EI, 0, V);
356 } else {
357 // If the input vector has multiple uses, simplify it based on a union
358 // of all elements used.
359 APInt DemandedElts = findDemandedEltsByAllUsers(SrcVec);
360 if (!DemandedElts.isAllOnesValue()) {
361 APInt UndefElts(NumElts, 0);
362 if (Value *V = SimplifyDemandedVectorElts(
363 SrcVec, DemandedElts, UndefElts, 0 /* Depth */,
364 true /* AllowMultipleUsers */)) {
365 if (V != SrcVec) {
366 SrcVec->replaceAllUsesWith(V);
367 return &EI;
368 }
369 }
370 }
371 }
372 }
373 if (Instruction *I = foldBitcastExtElt(EI, Builder, DL.isBigEndian()))
374 return I;
375
376 // If there's a vector PHI feeding a scalar use through this extractelement
377 // instruction, try to scalarize the PHI.
378 if (auto *Phi = dyn_cast<PHINode>(SrcVec))
379 if (Instruction *ScalarPHI = scalarizePHI(EI, Phi))
380 return ScalarPHI;
381 }
382
383 // TODO come up with a n-ary matcher that subsumes both unary and
384 // binary matchers.
385 UnaryOperator *UO;
386 if (match(SrcVec, m_UnOp(UO)) && cheapToScalarize(SrcVec, IndexC)) {
387 // extelt (unop X), Index --> unop (extelt X, Index)
388 Value *X = UO->getOperand(0);
389 Value *E = Builder.CreateExtractElement(X, Index);
390 return UnaryOperator::CreateWithCopiedFlags(UO->getOpcode(), E, UO);
391 }
392
393 BinaryOperator *BO;
394 if (match(SrcVec, m_BinOp(BO)) && cheapToScalarize(SrcVec, IndexC)) {
395 // extelt (binop X, Y), Index --> binop (extelt X, Index), (extelt Y, Index)
396 Value *X = BO->getOperand(0), *Y = BO->getOperand(1);
397 Value *E0 = Builder.CreateExtractElement(X, Index);
398 Value *E1 = Builder.CreateExtractElement(Y, Index);
399 return BinaryOperator::CreateWithCopiedFlags(BO->getOpcode(), E0, E1, BO);
400 }
401
402 Value *X, *Y;
403 CmpInst::Predicate Pred;
404 if (match(SrcVec, m_Cmp(Pred, m_Value(X), m_Value(Y))) &&
405 cheapToScalarize(SrcVec, IndexC)) {
406 // extelt (cmp X, Y), Index --> cmp (extelt X, Index), (extelt Y, Index)
407 Value *E0 = Builder.CreateExtractElement(X, Index);
408 Value *E1 = Builder.CreateExtractElement(Y, Index);
409 return CmpInst::Create(cast<CmpInst>(SrcVec)->getOpcode(), Pred, E0, E1);
410 }
411
412 if (auto *I = dyn_cast<Instruction>(SrcVec)) {
413 if (auto *IE = dyn_cast<InsertElementInst>(I)) {
414 // Extracting the inserted element?
415 if (IE->getOperand(2) == Index)
416 return replaceInstUsesWith(EI, IE->getOperand(1));
417 // If the inserted and extracted elements are constants, they must not
418 // be the same value, extract from the pre-inserted value instead.
419 if (isa<Constant>(IE->getOperand(2)) && IndexC)
420 return replaceOperand(EI, 0, IE->getOperand(0));
421 } else if (auto *SVI = dyn_cast<ShuffleVectorInst>(I)) {
422 // If this is extracting an element from a shufflevector, figure out where
423 // it came from and extract from the appropriate input element instead.
424 // Restrict the following transformation to fixed-length vector.
425 if (isa<FixedVectorType>(SVI->getType()) && isa<ConstantInt>(Index)) {
426 int SrcIdx =
427 SVI->getMaskValue(cast<ConstantInt>(Index)->getZExtValue());
428 Value *Src;
429 unsigned LHSWidth = cast<FixedVectorType>(SVI->getOperand(0)->getType())
430 ->getNumElements();
431
432 if (SrcIdx < 0)
433 return replaceInstUsesWith(EI, UndefValue::get(EI.getType()));
434 if (SrcIdx < (int)LHSWidth)
435 Src = SVI->getOperand(0);
436 else {
437 SrcIdx -= LHSWidth;
438 Src = SVI->getOperand(1);
439 }
440 Type *Int32Ty = Type::getInt32Ty(EI.getContext());
441 return ExtractElementInst::Create(
442 Src, ConstantInt::get(Int32Ty, SrcIdx, false));
443 }
444 } else if (auto *CI = dyn_cast<CastInst>(I)) {
445 // Canonicalize extractelement(cast) -> cast(extractelement).
446 // Bitcasts can change the number of vector elements, and they cost
447 // nothing.
448 if (CI->hasOneUse() && (CI->getOpcode() != Instruction::BitCast)) {
449 Value *EE = Builder.CreateExtractElement(CI->getOperand(0), Index);
450 return CastInst::Create(CI->getOpcode(), EE, EI.getType());
451 }
452 }
453 }
454 return nullptr;
455 }
456
457 /// If V is a shuffle of values that ONLY returns elements from either LHS or
458 /// RHS, return the shuffle mask and true. Otherwise, return false.
collectSingleShuffleElements(Value * V,Value * LHS,Value * RHS,SmallVectorImpl<int> & Mask)459 static bool collectSingleShuffleElements(Value *V, Value *LHS, Value *RHS,
460 SmallVectorImpl<int> &Mask) {
461 assert(LHS->getType() == RHS->getType() &&
462 "Invalid CollectSingleShuffleElements");
463 unsigned NumElts = cast<VectorType>(V->getType())->getNumElements();
464
465 if (isa<UndefValue>(V)) {
466 Mask.assign(NumElts, -1);
467 return true;
468 }
469
470 if (V == LHS) {
471 for (unsigned i = 0; i != NumElts; ++i)
472 Mask.push_back(i);
473 return true;
474 }
475
476 if (V == RHS) {
477 for (unsigned i = 0; i != NumElts; ++i)
478 Mask.push_back(i + NumElts);
479 return true;
480 }
481
482 if (InsertElementInst *IEI = dyn_cast<InsertElementInst>(V)) {
483 // If this is an insert of an extract from some other vector, include it.
484 Value *VecOp = IEI->getOperand(0);
485 Value *ScalarOp = IEI->getOperand(1);
486 Value *IdxOp = IEI->getOperand(2);
487
488 if (!isa<ConstantInt>(IdxOp))
489 return false;
490 unsigned InsertedIdx = cast<ConstantInt>(IdxOp)->getZExtValue();
491
492 if (isa<UndefValue>(ScalarOp)) { // inserting undef into vector.
493 // We can handle this if the vector we are inserting into is
494 // transitively ok.
495 if (collectSingleShuffleElements(VecOp, LHS, RHS, Mask)) {
496 // If so, update the mask to reflect the inserted undef.
497 Mask[InsertedIdx] = -1;
498 return true;
499 }
500 } else if (ExtractElementInst *EI = dyn_cast<ExtractElementInst>(ScalarOp)){
501 if (isa<ConstantInt>(EI->getOperand(1))) {
502 unsigned ExtractedIdx =
503 cast<ConstantInt>(EI->getOperand(1))->getZExtValue();
504 unsigned NumLHSElts =
505 cast<VectorType>(LHS->getType())->getNumElements();
506
507 // This must be extracting from either LHS or RHS.
508 if (EI->getOperand(0) == LHS || EI->getOperand(0) == RHS) {
509 // We can handle this if the vector we are inserting into is
510 // transitively ok.
511 if (collectSingleShuffleElements(VecOp, LHS, RHS, Mask)) {
512 // If so, update the mask to reflect the inserted value.
513 if (EI->getOperand(0) == LHS) {
514 Mask[InsertedIdx % NumElts] = ExtractedIdx;
515 } else {
516 assert(EI->getOperand(0) == RHS);
517 Mask[InsertedIdx % NumElts] = ExtractedIdx + NumLHSElts;
518 }
519 return true;
520 }
521 }
522 }
523 }
524 }
525
526 return false;
527 }
528
529 /// If we have insertion into a vector that is wider than the vector that we
530 /// are extracting from, try to widen the source vector to allow a single
531 /// shufflevector to replace one or more insert/extract pairs.
replaceExtractElements(InsertElementInst * InsElt,ExtractElementInst * ExtElt,InstCombiner & IC)532 static void replaceExtractElements(InsertElementInst *InsElt,
533 ExtractElementInst *ExtElt,
534 InstCombiner &IC) {
535 VectorType *InsVecType = InsElt->getType();
536 VectorType *ExtVecType = ExtElt->getVectorOperandType();
537 unsigned NumInsElts = InsVecType->getNumElements();
538 unsigned NumExtElts = ExtVecType->getNumElements();
539
540 // The inserted-to vector must be wider than the extracted-from vector.
541 if (InsVecType->getElementType() != ExtVecType->getElementType() ||
542 NumExtElts >= NumInsElts)
543 return;
544
545 // Create a shuffle mask to widen the extended-from vector using undefined
546 // values. The mask selects all of the values of the original vector followed
547 // by as many undefined values as needed to create a vector of the same length
548 // as the inserted-to vector.
549 SmallVector<int, 16> ExtendMask;
550 for (unsigned i = 0; i < NumExtElts; ++i)
551 ExtendMask.push_back(i);
552 for (unsigned i = NumExtElts; i < NumInsElts; ++i)
553 ExtendMask.push_back(-1);
554
555 Value *ExtVecOp = ExtElt->getVectorOperand();
556 auto *ExtVecOpInst = dyn_cast<Instruction>(ExtVecOp);
557 BasicBlock *InsertionBlock = (ExtVecOpInst && !isa<PHINode>(ExtVecOpInst))
558 ? ExtVecOpInst->getParent()
559 : ExtElt->getParent();
560
561 // TODO: This restriction matches the basic block check below when creating
562 // new extractelement instructions. If that limitation is removed, this one
563 // could also be removed. But for now, we just bail out to ensure that we
564 // will replace the extractelement instruction that is feeding our
565 // insertelement instruction. This allows the insertelement to then be
566 // replaced by a shufflevector. If the insertelement is not replaced, we can
567 // induce infinite looping because there's an optimization for extractelement
568 // that will delete our widening shuffle. This would trigger another attempt
569 // here to create that shuffle, and we spin forever.
570 if (InsertionBlock != InsElt->getParent())
571 return;
572
573 // TODO: This restriction matches the check in visitInsertElementInst() and
574 // prevents an infinite loop caused by not turning the extract/insert pair
575 // into a shuffle. We really should not need either check, but we're lacking
576 // folds for shufflevectors because we're afraid to generate shuffle masks
577 // that the backend can't handle.
578 if (InsElt->hasOneUse() && isa<InsertElementInst>(InsElt->user_back()))
579 return;
580
581 auto *WideVec =
582 new ShuffleVectorInst(ExtVecOp, UndefValue::get(ExtVecType), ExtendMask);
583
584 // Insert the new shuffle after the vector operand of the extract is defined
585 // (as long as it's not a PHI) or at the start of the basic block of the
586 // extract, so any subsequent extracts in the same basic block can use it.
587 // TODO: Insert before the earliest ExtractElementInst that is replaced.
588 if (ExtVecOpInst && !isa<PHINode>(ExtVecOpInst))
589 WideVec->insertAfter(ExtVecOpInst);
590 else
591 IC.InsertNewInstWith(WideVec, *ExtElt->getParent()->getFirstInsertionPt());
592
593 // Replace extracts from the original narrow vector with extracts from the new
594 // wide vector.
595 for (User *U : ExtVecOp->users()) {
596 ExtractElementInst *OldExt = dyn_cast<ExtractElementInst>(U);
597 if (!OldExt || OldExt->getParent() != WideVec->getParent())
598 continue;
599 auto *NewExt = ExtractElementInst::Create(WideVec, OldExt->getOperand(1));
600 NewExt->insertAfter(OldExt);
601 IC.replaceInstUsesWith(*OldExt, NewExt);
602 }
603 }
604
605 /// We are building a shuffle to create V, which is a sequence of insertelement,
606 /// extractelement pairs. If PermittedRHS is set, then we must either use it or
607 /// not rely on the second vector source. Return a std::pair containing the
608 /// left and right vectors of the proposed shuffle (or 0), and set the Mask
609 /// parameter as required.
610 ///
611 /// Note: we intentionally don't try to fold earlier shuffles since they have
612 /// often been chosen carefully to be efficiently implementable on the target.
613 using ShuffleOps = std::pair<Value *, Value *>;
614
collectShuffleElements(Value * V,SmallVectorImpl<int> & Mask,Value * PermittedRHS,InstCombiner & IC)615 static ShuffleOps collectShuffleElements(Value *V, SmallVectorImpl<int> &Mask,
616 Value *PermittedRHS,
617 InstCombiner &IC) {
618 assert(V->getType()->isVectorTy() && "Invalid shuffle!");
619 unsigned NumElts = cast<FixedVectorType>(V->getType())->getNumElements();
620
621 if (isa<UndefValue>(V)) {
622 Mask.assign(NumElts, -1);
623 return std::make_pair(
624 PermittedRHS ? UndefValue::get(PermittedRHS->getType()) : V, nullptr);
625 }
626
627 if (isa<ConstantAggregateZero>(V)) {
628 Mask.assign(NumElts, 0);
629 return std::make_pair(V, nullptr);
630 }
631
632 if (InsertElementInst *IEI = dyn_cast<InsertElementInst>(V)) {
633 // If this is an insert of an extract from some other vector, include it.
634 Value *VecOp = IEI->getOperand(0);
635 Value *ScalarOp = IEI->getOperand(1);
636 Value *IdxOp = IEI->getOperand(2);
637
638 if (ExtractElementInst *EI = dyn_cast<ExtractElementInst>(ScalarOp)) {
639 if (isa<ConstantInt>(EI->getOperand(1)) && isa<ConstantInt>(IdxOp)) {
640 unsigned ExtractedIdx =
641 cast<ConstantInt>(EI->getOperand(1))->getZExtValue();
642 unsigned InsertedIdx = cast<ConstantInt>(IdxOp)->getZExtValue();
643
644 // Either the extracted from or inserted into vector must be RHSVec,
645 // otherwise we'd end up with a shuffle of three inputs.
646 if (EI->getOperand(0) == PermittedRHS || PermittedRHS == nullptr) {
647 Value *RHS = EI->getOperand(0);
648 ShuffleOps LR = collectShuffleElements(VecOp, Mask, RHS, IC);
649 assert(LR.second == nullptr || LR.second == RHS);
650
651 if (LR.first->getType() != RHS->getType()) {
652 // Although we are giving up for now, see if we can create extracts
653 // that match the inserts for another round of combining.
654 replaceExtractElements(IEI, EI, IC);
655
656 // We tried our best, but we can't find anything compatible with RHS
657 // further up the chain. Return a trivial shuffle.
658 for (unsigned i = 0; i < NumElts; ++i)
659 Mask[i] = i;
660 return std::make_pair(V, nullptr);
661 }
662
663 unsigned NumLHSElts =
664 cast<VectorType>(RHS->getType())->getNumElements();
665 Mask[InsertedIdx % NumElts] = NumLHSElts + ExtractedIdx;
666 return std::make_pair(LR.first, RHS);
667 }
668
669 if (VecOp == PermittedRHS) {
670 // We've gone as far as we can: anything on the other side of the
671 // extractelement will already have been converted into a shuffle.
672 unsigned NumLHSElts =
673 cast<VectorType>(EI->getOperand(0)->getType())->getNumElements();
674 for (unsigned i = 0; i != NumElts; ++i)
675 Mask.push_back(i == InsertedIdx ? ExtractedIdx : NumLHSElts + i);
676 return std::make_pair(EI->getOperand(0), PermittedRHS);
677 }
678
679 // If this insertelement is a chain that comes from exactly these two
680 // vectors, return the vector and the effective shuffle.
681 if (EI->getOperand(0)->getType() == PermittedRHS->getType() &&
682 collectSingleShuffleElements(IEI, EI->getOperand(0), PermittedRHS,
683 Mask))
684 return std::make_pair(EI->getOperand(0), PermittedRHS);
685 }
686 }
687 }
688
689 // Otherwise, we can't do anything fancy. Return an identity vector.
690 for (unsigned i = 0; i != NumElts; ++i)
691 Mask.push_back(i);
692 return std::make_pair(V, nullptr);
693 }
694
695 /// Try to find redundant insertvalue instructions, like the following ones:
696 /// %0 = insertvalue { i8, i32 } undef, i8 %x, 0
697 /// %1 = insertvalue { i8, i32 } %0, i8 %y, 0
698 /// Here the second instruction inserts values at the same indices, as the
699 /// first one, making the first one redundant.
700 /// It should be transformed to:
701 /// %0 = insertvalue { i8, i32 } undef, i8 %y, 0
visitInsertValueInst(InsertValueInst & I)702 Instruction *InstCombiner::visitInsertValueInst(InsertValueInst &I) {
703 bool IsRedundant = false;
704 ArrayRef<unsigned int> FirstIndices = I.getIndices();
705
706 // If there is a chain of insertvalue instructions (each of them except the
707 // last one has only one use and it's another insertvalue insn from this
708 // chain), check if any of the 'children' uses the same indices as the first
709 // instruction. In this case, the first one is redundant.
710 Value *V = &I;
711 unsigned Depth = 0;
712 while (V->hasOneUse() && Depth < 10) {
713 User *U = V->user_back();
714 auto UserInsInst = dyn_cast<InsertValueInst>(U);
715 if (!UserInsInst || U->getOperand(0) != V)
716 break;
717 if (UserInsInst->getIndices() == FirstIndices) {
718 IsRedundant = true;
719 break;
720 }
721 V = UserInsInst;
722 Depth++;
723 }
724
725 if (IsRedundant)
726 return replaceInstUsesWith(I, I.getOperand(0));
727 return nullptr;
728 }
729
isShuffleEquivalentToSelect(ShuffleVectorInst & Shuf)730 static bool isShuffleEquivalentToSelect(ShuffleVectorInst &Shuf) {
731 // Can not analyze scalable type, the number of elements is not a compile-time
732 // constant.
733 if (isa<ScalableVectorType>(Shuf.getOperand(0)->getType()))
734 return false;
735
736 int MaskSize = Shuf.getShuffleMask().size();
737 int VecSize =
738 cast<FixedVectorType>(Shuf.getOperand(0)->getType())->getNumElements();
739
740 // A vector select does not change the size of the operands.
741 if (MaskSize != VecSize)
742 return false;
743
744 // Each mask element must be undefined or choose a vector element from one of
745 // the source operands without crossing vector lanes.
746 for (int i = 0; i != MaskSize; ++i) {
747 int Elt = Shuf.getMaskValue(i);
748 if (Elt != -1 && Elt != i && Elt != i + VecSize)
749 return false;
750 }
751
752 return true;
753 }
754
755 /// Turn a chain of inserts that splats a value into an insert + shuffle:
756 /// insertelt(insertelt(insertelt(insertelt X, %k, 0), %k, 1), %k, 2) ... ->
757 /// shufflevector(insertelt(X, %k, 0), undef, zero)
foldInsSequenceIntoSplat(InsertElementInst & InsElt)758 static Instruction *foldInsSequenceIntoSplat(InsertElementInst &InsElt) {
759 // We are interested in the last insert in a chain. So if this insert has a
760 // single user and that user is an insert, bail.
761 if (InsElt.hasOneUse() && isa<InsertElementInst>(InsElt.user_back()))
762 return nullptr;
763
764 VectorType *VecTy = InsElt.getType();
765 // Can not handle scalable type, the number of elements is not a compile-time
766 // constant.
767 if (isa<ScalableVectorType>(VecTy))
768 return nullptr;
769 unsigned NumElements = cast<FixedVectorType>(VecTy)->getNumElements();
770
771 // Do not try to do this for a one-element vector, since that's a nop,
772 // and will cause an inf-loop.
773 if (NumElements == 1)
774 return nullptr;
775
776 Value *SplatVal = InsElt.getOperand(1);
777 InsertElementInst *CurrIE = &InsElt;
778 SmallBitVector ElementPresent(NumElements, false);
779 InsertElementInst *FirstIE = nullptr;
780
781 // Walk the chain backwards, keeping track of which indices we inserted into,
782 // until we hit something that isn't an insert of the splatted value.
783 while (CurrIE) {
784 auto *Idx = dyn_cast<ConstantInt>(CurrIE->getOperand(2));
785 if (!Idx || CurrIE->getOperand(1) != SplatVal)
786 return nullptr;
787
788 auto *NextIE = dyn_cast<InsertElementInst>(CurrIE->getOperand(0));
789 // Check none of the intermediate steps have any additional uses, except
790 // for the root insertelement instruction, which can be re-used, if it
791 // inserts at position 0.
792 if (CurrIE != &InsElt &&
793 (!CurrIE->hasOneUse() && (NextIE != nullptr || !Idx->isZero())))
794 return nullptr;
795
796 ElementPresent[Idx->getZExtValue()] = true;
797 FirstIE = CurrIE;
798 CurrIE = NextIE;
799 }
800
801 // If this is just a single insertelement (not a sequence), we are done.
802 if (FirstIE == &InsElt)
803 return nullptr;
804
805 // If we are not inserting into an undef vector, make sure we've seen an
806 // insert into every element.
807 // TODO: If the base vector is not undef, it might be better to create a splat
808 // and then a select-shuffle (blend) with the base vector.
809 if (!isa<UndefValue>(FirstIE->getOperand(0)))
810 if (!ElementPresent.all())
811 return nullptr;
812
813 // Create the insert + shuffle.
814 Type *Int32Ty = Type::getInt32Ty(InsElt.getContext());
815 UndefValue *UndefVec = UndefValue::get(VecTy);
816 Constant *Zero = ConstantInt::get(Int32Ty, 0);
817 if (!cast<ConstantInt>(FirstIE->getOperand(2))->isZero())
818 FirstIE = InsertElementInst::Create(UndefVec, SplatVal, Zero, "", &InsElt);
819
820 // Splat from element 0, but replace absent elements with undef in the mask.
821 SmallVector<int, 16> Mask(NumElements, 0);
822 for (unsigned i = 0; i != NumElements; ++i)
823 if (!ElementPresent[i])
824 Mask[i] = -1;
825
826 return new ShuffleVectorInst(FirstIE, UndefVec, Mask);
827 }
828
829 /// Try to fold an insert element into an existing splat shuffle by changing
830 /// the shuffle's mask to include the index of this insert element.
foldInsEltIntoSplat(InsertElementInst & InsElt)831 static Instruction *foldInsEltIntoSplat(InsertElementInst &InsElt) {
832 // Check if the vector operand of this insert is a canonical splat shuffle.
833 auto *Shuf = dyn_cast<ShuffleVectorInst>(InsElt.getOperand(0));
834 if (!Shuf || !Shuf->isZeroEltSplat())
835 return nullptr;
836
837 // Bail out early if shuffle is scalable type. The number of elements in
838 // shuffle mask is unknown at compile-time.
839 if (isa<ScalableVectorType>(Shuf->getType()))
840 return nullptr;
841
842 // Check for a constant insertion index.
843 uint64_t IdxC;
844 if (!match(InsElt.getOperand(2), m_ConstantInt(IdxC)))
845 return nullptr;
846
847 // Check if the splat shuffle's input is the same as this insert's scalar op.
848 Value *X = InsElt.getOperand(1);
849 Value *Op0 = Shuf->getOperand(0);
850 if (!match(Op0, m_InsertElt(m_Undef(), m_Specific(X), m_ZeroInt())))
851 return nullptr;
852
853 // Replace the shuffle mask element at the index of this insert with a zero.
854 // For example:
855 // inselt (shuf (inselt undef, X, 0), undef, <0,undef,0,undef>), X, 1
856 // --> shuf (inselt undef, X, 0), undef, <0,0,0,undef>
857 unsigned NumMaskElts = Shuf->getType()->getNumElements();
858 SmallVector<int, 16> NewMask(NumMaskElts);
859 for (unsigned i = 0; i != NumMaskElts; ++i)
860 NewMask[i] = i == IdxC ? 0 : Shuf->getMaskValue(i);
861
862 return new ShuffleVectorInst(Op0, UndefValue::get(Op0->getType()), NewMask);
863 }
864
865 /// Try to fold an extract+insert element into an existing identity shuffle by
866 /// changing the shuffle's mask to include the index of this insert element.
foldInsEltIntoIdentityShuffle(InsertElementInst & InsElt)867 static Instruction *foldInsEltIntoIdentityShuffle(InsertElementInst &InsElt) {
868 // Check if the vector operand of this insert is an identity shuffle.
869 auto *Shuf = dyn_cast<ShuffleVectorInst>(InsElt.getOperand(0));
870 if (!Shuf || !isa<UndefValue>(Shuf->getOperand(1)) ||
871 !(Shuf->isIdentityWithExtract() || Shuf->isIdentityWithPadding()))
872 return nullptr;
873
874 // Bail out early if shuffle is scalable type. The number of elements in
875 // shuffle mask is unknown at compile-time.
876 if (isa<ScalableVectorType>(Shuf->getType()))
877 return nullptr;
878
879 // Check for a constant insertion index.
880 uint64_t IdxC;
881 if (!match(InsElt.getOperand(2), m_ConstantInt(IdxC)))
882 return nullptr;
883
884 // Check if this insert's scalar op is extracted from the identity shuffle's
885 // input vector.
886 Value *Scalar = InsElt.getOperand(1);
887 Value *X = Shuf->getOperand(0);
888 if (!match(Scalar, m_ExtractElt(m_Specific(X), m_SpecificInt(IdxC))))
889 return nullptr;
890
891 // Replace the shuffle mask element at the index of this extract+insert with
892 // that same index value.
893 // For example:
894 // inselt (shuf X, IdMask), (extelt X, IdxC), IdxC --> shuf X, IdMask'
895 unsigned NumMaskElts = Shuf->getType()->getNumElements();
896 SmallVector<int, 16> NewMask(NumMaskElts);
897 ArrayRef<int> OldMask = Shuf->getShuffleMask();
898 for (unsigned i = 0; i != NumMaskElts; ++i) {
899 if (i != IdxC) {
900 // All mask elements besides the inserted element remain the same.
901 NewMask[i] = OldMask[i];
902 } else if (OldMask[i] == (int)IdxC) {
903 // If the mask element was already set, there's nothing to do
904 // (demanded elements analysis may unset it later).
905 return nullptr;
906 } else {
907 assert(OldMask[i] == UndefMaskElem &&
908 "Unexpected shuffle mask element for identity shuffle");
909 NewMask[i] = IdxC;
910 }
911 }
912
913 return new ShuffleVectorInst(X, Shuf->getOperand(1), NewMask);
914 }
915
916 /// If we have an insertelement instruction feeding into another insertelement
917 /// and the 2nd is inserting a constant into the vector, canonicalize that
918 /// constant insertion before the insertion of a variable:
919 ///
920 /// insertelement (insertelement X, Y, IdxC1), ScalarC, IdxC2 -->
921 /// insertelement (insertelement X, ScalarC, IdxC2), Y, IdxC1
922 ///
923 /// This has the potential of eliminating the 2nd insertelement instruction
924 /// via constant folding of the scalar constant into a vector constant.
hoistInsEltConst(InsertElementInst & InsElt2,InstCombiner::BuilderTy & Builder)925 static Instruction *hoistInsEltConst(InsertElementInst &InsElt2,
926 InstCombiner::BuilderTy &Builder) {
927 auto *InsElt1 = dyn_cast<InsertElementInst>(InsElt2.getOperand(0));
928 if (!InsElt1 || !InsElt1->hasOneUse())
929 return nullptr;
930
931 Value *X, *Y;
932 Constant *ScalarC;
933 ConstantInt *IdxC1, *IdxC2;
934 if (match(InsElt1->getOperand(0), m_Value(X)) &&
935 match(InsElt1->getOperand(1), m_Value(Y)) && !isa<Constant>(Y) &&
936 match(InsElt1->getOperand(2), m_ConstantInt(IdxC1)) &&
937 match(InsElt2.getOperand(1), m_Constant(ScalarC)) &&
938 match(InsElt2.getOperand(2), m_ConstantInt(IdxC2)) && IdxC1 != IdxC2) {
939 Value *NewInsElt1 = Builder.CreateInsertElement(X, ScalarC, IdxC2);
940 return InsertElementInst::Create(NewInsElt1, Y, IdxC1);
941 }
942
943 return nullptr;
944 }
945
946 /// insertelt (shufflevector X, CVec, Mask|insertelt X, C1, CIndex1), C, CIndex
947 /// --> shufflevector X, CVec', Mask'
foldConstantInsEltIntoShuffle(InsertElementInst & InsElt)948 static Instruction *foldConstantInsEltIntoShuffle(InsertElementInst &InsElt) {
949 auto *Inst = dyn_cast<Instruction>(InsElt.getOperand(0));
950 // Bail out if the parent has more than one use. In that case, we'd be
951 // replacing the insertelt with a shuffle, and that's not a clear win.
952 if (!Inst || !Inst->hasOneUse())
953 return nullptr;
954 if (auto *Shuf = dyn_cast<ShuffleVectorInst>(InsElt.getOperand(0))) {
955 // The shuffle must have a constant vector operand. The insertelt must have
956 // a constant scalar being inserted at a constant position in the vector.
957 Constant *ShufConstVec, *InsEltScalar;
958 uint64_t InsEltIndex;
959 if (!match(Shuf->getOperand(1), m_Constant(ShufConstVec)) ||
960 !match(InsElt.getOperand(1), m_Constant(InsEltScalar)) ||
961 !match(InsElt.getOperand(2), m_ConstantInt(InsEltIndex)))
962 return nullptr;
963
964 // Adding an element to an arbitrary shuffle could be expensive, but a
965 // shuffle that selects elements from vectors without crossing lanes is
966 // assumed cheap.
967 // If we're just adding a constant into that shuffle, it will still be
968 // cheap.
969 if (!isShuffleEquivalentToSelect(*Shuf))
970 return nullptr;
971
972 // From the above 'select' check, we know that the mask has the same number
973 // of elements as the vector input operands. We also know that each constant
974 // input element is used in its lane and can not be used more than once by
975 // the shuffle. Therefore, replace the constant in the shuffle's constant
976 // vector with the insertelt constant. Replace the constant in the shuffle's
977 // mask vector with the insertelt index plus the length of the vector
978 // (because the constant vector operand of a shuffle is always the 2nd
979 // operand).
980 ArrayRef<int> Mask = Shuf->getShuffleMask();
981 unsigned NumElts = Mask.size();
982 SmallVector<Constant *, 16> NewShufElts(NumElts);
983 SmallVector<int, 16> NewMaskElts(NumElts);
984 for (unsigned I = 0; I != NumElts; ++I) {
985 if (I == InsEltIndex) {
986 NewShufElts[I] = InsEltScalar;
987 NewMaskElts[I] = InsEltIndex + NumElts;
988 } else {
989 // Copy over the existing values.
990 NewShufElts[I] = ShufConstVec->getAggregateElement(I);
991 NewMaskElts[I] = Mask[I];
992 }
993 }
994
995 // Create new operands for a shuffle that includes the constant of the
996 // original insertelt. The old shuffle will be dead now.
997 return new ShuffleVectorInst(Shuf->getOperand(0),
998 ConstantVector::get(NewShufElts), NewMaskElts);
999 } else if (auto *IEI = dyn_cast<InsertElementInst>(Inst)) {
1000 // Transform sequences of insertelements ops with constant data/indexes into
1001 // a single shuffle op.
1002 // Can not handle scalable type, the number of elements needed to create
1003 // shuffle mask is not a compile-time constant.
1004 if (isa<ScalableVectorType>(InsElt.getType()))
1005 return nullptr;
1006 unsigned NumElts =
1007 cast<FixedVectorType>(InsElt.getType())->getNumElements();
1008
1009 uint64_t InsertIdx[2];
1010 Constant *Val[2];
1011 if (!match(InsElt.getOperand(2), m_ConstantInt(InsertIdx[0])) ||
1012 !match(InsElt.getOperand(1), m_Constant(Val[0])) ||
1013 !match(IEI->getOperand(2), m_ConstantInt(InsertIdx[1])) ||
1014 !match(IEI->getOperand(1), m_Constant(Val[1])))
1015 return nullptr;
1016 SmallVector<Constant *, 16> Values(NumElts);
1017 SmallVector<int, 16> Mask(NumElts);
1018 auto ValI = std::begin(Val);
1019 // Generate new constant vector and mask.
1020 // We have 2 values/masks from the insertelements instructions. Insert them
1021 // into new value/mask vectors.
1022 for (uint64_t I : InsertIdx) {
1023 if (!Values[I]) {
1024 Values[I] = *ValI;
1025 Mask[I] = NumElts + I;
1026 }
1027 ++ValI;
1028 }
1029 // Remaining values are filled with 'undef' values.
1030 for (unsigned I = 0; I < NumElts; ++I) {
1031 if (!Values[I]) {
1032 Values[I] = UndefValue::get(InsElt.getType()->getElementType());
1033 Mask[I] = I;
1034 }
1035 }
1036 // Create new operands for a shuffle that includes the constant of the
1037 // original insertelt.
1038 return new ShuffleVectorInst(IEI->getOperand(0),
1039 ConstantVector::get(Values), Mask);
1040 }
1041 return nullptr;
1042 }
1043
visitInsertElementInst(InsertElementInst & IE)1044 Instruction *InstCombiner::visitInsertElementInst(InsertElementInst &IE) {
1045 Value *VecOp = IE.getOperand(0);
1046 Value *ScalarOp = IE.getOperand(1);
1047 Value *IdxOp = IE.getOperand(2);
1048
1049 if (auto *V = SimplifyInsertElementInst(
1050 VecOp, ScalarOp, IdxOp, SQ.getWithInstruction(&IE)))
1051 return replaceInstUsesWith(IE, V);
1052
1053 // If the scalar is bitcast and inserted into undef, do the insert in the
1054 // source type followed by bitcast.
1055 // TODO: Generalize for insert into any constant, not just undef?
1056 Value *ScalarSrc;
1057 if (match(VecOp, m_Undef()) &&
1058 match(ScalarOp, m_OneUse(m_BitCast(m_Value(ScalarSrc)))) &&
1059 (ScalarSrc->getType()->isIntegerTy() ||
1060 ScalarSrc->getType()->isFloatingPointTy())) {
1061 // inselt undef, (bitcast ScalarSrc), IdxOp -->
1062 // bitcast (inselt undef, ScalarSrc, IdxOp)
1063 Type *ScalarTy = ScalarSrc->getType();
1064 Type *VecTy = VectorType::get(ScalarTy, IE.getType()->getElementCount());
1065 UndefValue *NewUndef = UndefValue::get(VecTy);
1066 Value *NewInsElt = Builder.CreateInsertElement(NewUndef, ScalarSrc, IdxOp);
1067 return new BitCastInst(NewInsElt, IE.getType());
1068 }
1069
1070 // If the vector and scalar are both bitcast from the same element type, do
1071 // the insert in that source type followed by bitcast.
1072 Value *VecSrc;
1073 if (match(VecOp, m_BitCast(m_Value(VecSrc))) &&
1074 match(ScalarOp, m_BitCast(m_Value(ScalarSrc))) &&
1075 (VecOp->hasOneUse() || ScalarOp->hasOneUse()) &&
1076 VecSrc->getType()->isVectorTy() && !ScalarSrc->getType()->isVectorTy() &&
1077 cast<VectorType>(VecSrc->getType())->getElementType() ==
1078 ScalarSrc->getType()) {
1079 // inselt (bitcast VecSrc), (bitcast ScalarSrc), IdxOp -->
1080 // bitcast (inselt VecSrc, ScalarSrc, IdxOp)
1081 Value *NewInsElt = Builder.CreateInsertElement(VecSrc, ScalarSrc, IdxOp);
1082 return new BitCastInst(NewInsElt, IE.getType());
1083 }
1084
1085 // If the inserted element was extracted from some other fixed-length vector
1086 // and both indexes are valid constants, try to turn this into a shuffle.
1087 // Can not handle scalable vector type, the number of elements needed to
1088 // create shuffle mask is not a compile-time constant.
1089 uint64_t InsertedIdx, ExtractedIdx;
1090 Value *ExtVecOp;
1091 if (isa<FixedVectorType>(IE.getType()) &&
1092 match(IdxOp, m_ConstantInt(InsertedIdx)) &&
1093 match(ScalarOp,
1094 m_ExtractElt(m_Value(ExtVecOp), m_ConstantInt(ExtractedIdx))) &&
1095 isa<FixedVectorType>(ExtVecOp->getType()) &&
1096 ExtractedIdx <
1097 cast<FixedVectorType>(ExtVecOp->getType())->getNumElements()) {
1098 // TODO: Looking at the user(s) to determine if this insert is a
1099 // fold-to-shuffle opportunity does not match the usual instcombine
1100 // constraints. We should decide if the transform is worthy based only
1101 // on this instruction and its operands, but that may not work currently.
1102 //
1103 // Here, we are trying to avoid creating shuffles before reaching
1104 // the end of a chain of extract-insert pairs. This is complicated because
1105 // we do not generally form arbitrary shuffle masks in instcombine
1106 // (because those may codegen poorly), but collectShuffleElements() does
1107 // exactly that.
1108 //
1109 // The rules for determining what is an acceptable target-independent
1110 // shuffle mask are fuzzy because they evolve based on the backend's
1111 // capabilities and real-world impact.
1112 auto isShuffleRootCandidate = [](InsertElementInst &Insert) {
1113 if (!Insert.hasOneUse())
1114 return true;
1115 auto *InsertUser = dyn_cast<InsertElementInst>(Insert.user_back());
1116 if (!InsertUser)
1117 return true;
1118 return false;
1119 };
1120
1121 // Try to form a shuffle from a chain of extract-insert ops.
1122 if (isShuffleRootCandidate(IE)) {
1123 SmallVector<int, 16> Mask;
1124 ShuffleOps LR = collectShuffleElements(&IE, Mask, nullptr, *this);
1125
1126 // The proposed shuffle may be trivial, in which case we shouldn't
1127 // perform the combine.
1128 if (LR.first != &IE && LR.second != &IE) {
1129 // We now have a shuffle of LHS, RHS, Mask.
1130 if (LR.second == nullptr)
1131 LR.second = UndefValue::get(LR.first->getType());
1132 return new ShuffleVectorInst(LR.first, LR.second, Mask);
1133 }
1134 }
1135 }
1136
1137 if (auto VecTy = dyn_cast<FixedVectorType>(VecOp->getType())) {
1138 unsigned VWidth = VecTy->getNumElements();
1139 APInt UndefElts(VWidth, 0);
1140 APInt AllOnesEltMask(APInt::getAllOnesValue(VWidth));
1141 if (Value *V = SimplifyDemandedVectorElts(&IE, AllOnesEltMask, UndefElts)) {
1142 if (V != &IE)
1143 return replaceInstUsesWith(IE, V);
1144 return &IE;
1145 }
1146 }
1147
1148 if (Instruction *Shuf = foldConstantInsEltIntoShuffle(IE))
1149 return Shuf;
1150
1151 if (Instruction *NewInsElt = hoistInsEltConst(IE, Builder))
1152 return NewInsElt;
1153
1154 if (Instruction *Broadcast = foldInsSequenceIntoSplat(IE))
1155 return Broadcast;
1156
1157 if (Instruction *Splat = foldInsEltIntoSplat(IE))
1158 return Splat;
1159
1160 if (Instruction *IdentityShuf = foldInsEltIntoIdentityShuffle(IE))
1161 return IdentityShuf;
1162
1163 return nullptr;
1164 }
1165
1166 /// Return true if we can evaluate the specified expression tree if the vector
1167 /// elements were shuffled in a different order.
canEvaluateShuffled(Value * V,ArrayRef<int> Mask,unsigned Depth=5)1168 static bool canEvaluateShuffled(Value *V, ArrayRef<int> Mask,
1169 unsigned Depth = 5) {
1170 // We can always reorder the elements of a constant.
1171 if (isa<Constant>(V))
1172 return true;
1173
1174 // We won't reorder vector arguments. No IPO here.
1175 Instruction *I = dyn_cast<Instruction>(V);
1176 if (!I) return false;
1177
1178 // Two users may expect different orders of the elements. Don't try it.
1179 if (!I->hasOneUse())
1180 return false;
1181
1182 if (Depth == 0) return false;
1183
1184 switch (I->getOpcode()) {
1185 case Instruction::UDiv:
1186 case Instruction::SDiv:
1187 case Instruction::URem:
1188 case Instruction::SRem:
1189 // Propagating an undefined shuffle mask element to integer div/rem is not
1190 // allowed because those opcodes can create immediate undefined behavior
1191 // from an undefined element in an operand.
1192 if (llvm::any_of(Mask, [](int M){ return M == -1; }))
1193 return false;
1194 LLVM_FALLTHROUGH;
1195 case Instruction::Add:
1196 case Instruction::FAdd:
1197 case Instruction::Sub:
1198 case Instruction::FSub:
1199 case Instruction::Mul:
1200 case Instruction::FMul:
1201 case Instruction::FDiv:
1202 case Instruction::FRem:
1203 case Instruction::Shl:
1204 case Instruction::LShr:
1205 case Instruction::AShr:
1206 case Instruction::And:
1207 case Instruction::Or:
1208 case Instruction::Xor:
1209 case Instruction::ICmp:
1210 case Instruction::FCmp:
1211 case Instruction::Trunc:
1212 case Instruction::ZExt:
1213 case Instruction::SExt:
1214 case Instruction::FPToUI:
1215 case Instruction::FPToSI:
1216 case Instruction::UIToFP:
1217 case Instruction::SIToFP:
1218 case Instruction::FPTrunc:
1219 case Instruction::FPExt:
1220 case Instruction::GetElementPtr: {
1221 // Bail out if we would create longer vector ops. We could allow creating
1222 // longer vector ops, but that may result in more expensive codegen.
1223 Type *ITy = I->getType();
1224 if (ITy->isVectorTy() &&
1225 Mask.size() > cast<VectorType>(ITy)->getNumElements())
1226 return false;
1227 for (Value *Operand : I->operands()) {
1228 if (!canEvaluateShuffled(Operand, Mask, Depth - 1))
1229 return false;
1230 }
1231 return true;
1232 }
1233 case Instruction::InsertElement: {
1234 ConstantInt *CI = dyn_cast<ConstantInt>(I->getOperand(2));
1235 if (!CI) return false;
1236 int ElementNumber = CI->getLimitedValue();
1237
1238 // Verify that 'CI' does not occur twice in Mask. A single 'insertelement'
1239 // can't put an element into multiple indices.
1240 bool SeenOnce = false;
1241 for (int i = 0, e = Mask.size(); i != e; ++i) {
1242 if (Mask[i] == ElementNumber) {
1243 if (SeenOnce)
1244 return false;
1245 SeenOnce = true;
1246 }
1247 }
1248 return canEvaluateShuffled(I->getOperand(0), Mask, Depth - 1);
1249 }
1250 }
1251 return false;
1252 }
1253
1254 /// Rebuild a new instruction just like 'I' but with the new operands given.
1255 /// In the event of type mismatch, the type of the operands is correct.
buildNew(Instruction * I,ArrayRef<Value * > NewOps)1256 static Value *buildNew(Instruction *I, ArrayRef<Value*> NewOps) {
1257 // We don't want to use the IRBuilder here because we want the replacement
1258 // instructions to appear next to 'I', not the builder's insertion point.
1259 switch (I->getOpcode()) {
1260 case Instruction::Add:
1261 case Instruction::FAdd:
1262 case Instruction::Sub:
1263 case Instruction::FSub:
1264 case Instruction::Mul:
1265 case Instruction::FMul:
1266 case Instruction::UDiv:
1267 case Instruction::SDiv:
1268 case Instruction::FDiv:
1269 case Instruction::URem:
1270 case Instruction::SRem:
1271 case Instruction::FRem:
1272 case Instruction::Shl:
1273 case Instruction::LShr:
1274 case Instruction::AShr:
1275 case Instruction::And:
1276 case Instruction::Or:
1277 case Instruction::Xor: {
1278 BinaryOperator *BO = cast<BinaryOperator>(I);
1279 assert(NewOps.size() == 2 && "binary operator with #ops != 2");
1280 BinaryOperator *New =
1281 BinaryOperator::Create(cast<BinaryOperator>(I)->getOpcode(),
1282 NewOps[0], NewOps[1], "", BO);
1283 if (isa<OverflowingBinaryOperator>(BO)) {
1284 New->setHasNoUnsignedWrap(BO->hasNoUnsignedWrap());
1285 New->setHasNoSignedWrap(BO->hasNoSignedWrap());
1286 }
1287 if (isa<PossiblyExactOperator>(BO)) {
1288 New->setIsExact(BO->isExact());
1289 }
1290 if (isa<FPMathOperator>(BO))
1291 New->copyFastMathFlags(I);
1292 return New;
1293 }
1294 case Instruction::ICmp:
1295 assert(NewOps.size() == 2 && "icmp with #ops != 2");
1296 return new ICmpInst(I, cast<ICmpInst>(I)->getPredicate(),
1297 NewOps[0], NewOps[1]);
1298 case Instruction::FCmp:
1299 assert(NewOps.size() == 2 && "fcmp with #ops != 2");
1300 return new FCmpInst(I, cast<FCmpInst>(I)->getPredicate(),
1301 NewOps[0], NewOps[1]);
1302 case Instruction::Trunc:
1303 case Instruction::ZExt:
1304 case Instruction::SExt:
1305 case Instruction::FPToUI:
1306 case Instruction::FPToSI:
1307 case Instruction::UIToFP:
1308 case Instruction::SIToFP:
1309 case Instruction::FPTrunc:
1310 case Instruction::FPExt: {
1311 // It's possible that the mask has a different number of elements from
1312 // the original cast. We recompute the destination type to match the mask.
1313 Type *DestTy = VectorType::get(
1314 I->getType()->getScalarType(),
1315 cast<VectorType>(NewOps[0]->getType())->getElementCount());
1316 assert(NewOps.size() == 1 && "cast with #ops != 1");
1317 return CastInst::Create(cast<CastInst>(I)->getOpcode(), NewOps[0], DestTy,
1318 "", I);
1319 }
1320 case Instruction::GetElementPtr: {
1321 Value *Ptr = NewOps[0];
1322 ArrayRef<Value*> Idx = NewOps.slice(1);
1323 GetElementPtrInst *GEP = GetElementPtrInst::Create(
1324 cast<GetElementPtrInst>(I)->getSourceElementType(), Ptr, Idx, "", I);
1325 GEP->setIsInBounds(cast<GetElementPtrInst>(I)->isInBounds());
1326 return GEP;
1327 }
1328 }
1329 llvm_unreachable("failed to rebuild vector instructions");
1330 }
1331
evaluateInDifferentElementOrder(Value * V,ArrayRef<int> Mask)1332 static Value *evaluateInDifferentElementOrder(Value *V, ArrayRef<int> Mask) {
1333 // Mask.size() does not need to be equal to the number of vector elements.
1334
1335 assert(V->getType()->isVectorTy() && "can't reorder non-vector elements");
1336 Type *EltTy = V->getType()->getScalarType();
1337 Type *I32Ty = IntegerType::getInt32Ty(V->getContext());
1338 if (isa<UndefValue>(V))
1339 return UndefValue::get(FixedVectorType::get(EltTy, Mask.size()));
1340
1341 if (isa<ConstantAggregateZero>(V))
1342 return ConstantAggregateZero::get(FixedVectorType::get(EltTy, Mask.size()));
1343
1344 if (Constant *C = dyn_cast<Constant>(V))
1345 return ConstantExpr::getShuffleVector(C, UndefValue::get(C->getType()),
1346 Mask);
1347
1348 Instruction *I = cast<Instruction>(V);
1349 switch (I->getOpcode()) {
1350 case Instruction::Add:
1351 case Instruction::FAdd:
1352 case Instruction::Sub:
1353 case Instruction::FSub:
1354 case Instruction::Mul:
1355 case Instruction::FMul:
1356 case Instruction::UDiv:
1357 case Instruction::SDiv:
1358 case Instruction::FDiv:
1359 case Instruction::URem:
1360 case Instruction::SRem:
1361 case Instruction::FRem:
1362 case Instruction::Shl:
1363 case Instruction::LShr:
1364 case Instruction::AShr:
1365 case Instruction::And:
1366 case Instruction::Or:
1367 case Instruction::Xor:
1368 case Instruction::ICmp:
1369 case Instruction::FCmp:
1370 case Instruction::Trunc:
1371 case Instruction::ZExt:
1372 case Instruction::SExt:
1373 case Instruction::FPToUI:
1374 case Instruction::FPToSI:
1375 case Instruction::UIToFP:
1376 case Instruction::SIToFP:
1377 case Instruction::FPTrunc:
1378 case Instruction::FPExt:
1379 case Instruction::Select:
1380 case Instruction::GetElementPtr: {
1381 SmallVector<Value*, 8> NewOps;
1382 bool NeedsRebuild =
1383 (Mask.size() != cast<VectorType>(I->getType())->getNumElements());
1384 for (int i = 0, e = I->getNumOperands(); i != e; ++i) {
1385 Value *V;
1386 // Recursively call evaluateInDifferentElementOrder on vector arguments
1387 // as well. E.g. GetElementPtr may have scalar operands even if the
1388 // return value is a vector, so we need to examine the operand type.
1389 if (I->getOperand(i)->getType()->isVectorTy())
1390 V = evaluateInDifferentElementOrder(I->getOperand(i), Mask);
1391 else
1392 V = I->getOperand(i);
1393 NewOps.push_back(V);
1394 NeedsRebuild |= (V != I->getOperand(i));
1395 }
1396 if (NeedsRebuild) {
1397 return buildNew(I, NewOps);
1398 }
1399 return I;
1400 }
1401 case Instruction::InsertElement: {
1402 int Element = cast<ConstantInt>(I->getOperand(2))->getLimitedValue();
1403
1404 // The insertelement was inserting at Element. Figure out which element
1405 // that becomes after shuffling. The answer is guaranteed to be unique
1406 // by CanEvaluateShuffled.
1407 bool Found = false;
1408 int Index = 0;
1409 for (int e = Mask.size(); Index != e; ++Index) {
1410 if (Mask[Index] == Element) {
1411 Found = true;
1412 break;
1413 }
1414 }
1415
1416 // If element is not in Mask, no need to handle the operand 1 (element to
1417 // be inserted). Just evaluate values in operand 0 according to Mask.
1418 if (!Found)
1419 return evaluateInDifferentElementOrder(I->getOperand(0), Mask);
1420
1421 Value *V = evaluateInDifferentElementOrder(I->getOperand(0), Mask);
1422 return InsertElementInst::Create(V, I->getOperand(1),
1423 ConstantInt::get(I32Ty, Index), "", I);
1424 }
1425 }
1426 llvm_unreachable("failed to reorder elements of vector instruction!");
1427 }
1428
1429 // Returns true if the shuffle is extracting a contiguous range of values from
1430 // LHS, for example:
1431 // +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
1432 // Input: |AA|BB|CC|DD|EE|FF|GG|HH|II|JJ|KK|LL|MM|NN|OO|PP|
1433 // Shuffles to: |EE|FF|GG|HH|
1434 // +--+--+--+--+
isShuffleExtractingFromLHS(ShuffleVectorInst & SVI,ArrayRef<int> Mask)1435 static bool isShuffleExtractingFromLHS(ShuffleVectorInst &SVI,
1436 ArrayRef<int> Mask) {
1437 unsigned LHSElems =
1438 cast<VectorType>(SVI.getOperand(0)->getType())->getNumElements();
1439 unsigned MaskElems = Mask.size();
1440 unsigned BegIdx = Mask.front();
1441 unsigned EndIdx = Mask.back();
1442 if (BegIdx > EndIdx || EndIdx >= LHSElems || EndIdx - BegIdx != MaskElems - 1)
1443 return false;
1444 for (unsigned I = 0; I != MaskElems; ++I)
1445 if (static_cast<unsigned>(Mask[I]) != BegIdx + I)
1446 return false;
1447 return true;
1448 }
1449
1450 /// These are the ingredients in an alternate form binary operator as described
1451 /// below.
1452 struct BinopElts {
1453 BinaryOperator::BinaryOps Opcode;
1454 Value *Op0;
1455 Value *Op1;
BinopEltsBinopElts1456 BinopElts(BinaryOperator::BinaryOps Opc = (BinaryOperator::BinaryOps)0,
1457 Value *V0 = nullptr, Value *V1 = nullptr) :
1458 Opcode(Opc), Op0(V0), Op1(V1) {}
operator boolBinopElts1459 operator bool() const { return Opcode != 0; }
1460 };
1461
1462 /// Binops may be transformed into binops with different opcodes and operands.
1463 /// Reverse the usual canonicalization to enable folds with the non-canonical
1464 /// form of the binop. If a transform is possible, return the elements of the
1465 /// new binop. If not, return invalid elements.
getAlternateBinop(BinaryOperator * BO,const DataLayout & DL)1466 static BinopElts getAlternateBinop(BinaryOperator *BO, const DataLayout &DL) {
1467 Value *BO0 = BO->getOperand(0), *BO1 = BO->getOperand(1);
1468 Type *Ty = BO->getType();
1469 switch (BO->getOpcode()) {
1470 case Instruction::Shl: {
1471 // shl X, C --> mul X, (1 << C)
1472 Constant *C;
1473 if (match(BO1, m_Constant(C))) {
1474 Constant *ShlOne = ConstantExpr::getShl(ConstantInt::get(Ty, 1), C);
1475 return { Instruction::Mul, BO0, ShlOne };
1476 }
1477 break;
1478 }
1479 case Instruction::Or: {
1480 // or X, C --> add X, C (when X and C have no common bits set)
1481 const APInt *C;
1482 if (match(BO1, m_APInt(C)) && MaskedValueIsZero(BO0, *C, DL))
1483 return { Instruction::Add, BO0, BO1 };
1484 break;
1485 }
1486 default:
1487 break;
1488 }
1489 return {};
1490 }
1491
foldSelectShuffleWith1Binop(ShuffleVectorInst & Shuf)1492 static Instruction *foldSelectShuffleWith1Binop(ShuffleVectorInst &Shuf) {
1493 assert(Shuf.isSelect() && "Must have select-equivalent shuffle");
1494
1495 // Are we shuffling together some value and that same value after it has been
1496 // modified by a binop with a constant?
1497 Value *Op0 = Shuf.getOperand(0), *Op1 = Shuf.getOperand(1);
1498 Constant *C;
1499 bool Op0IsBinop;
1500 if (match(Op0, m_BinOp(m_Specific(Op1), m_Constant(C))))
1501 Op0IsBinop = true;
1502 else if (match(Op1, m_BinOp(m_Specific(Op0), m_Constant(C))))
1503 Op0IsBinop = false;
1504 else
1505 return nullptr;
1506
1507 // The identity constant for a binop leaves a variable operand unchanged. For
1508 // a vector, this is a splat of something like 0, -1, or 1.
1509 // If there's no identity constant for this binop, we're done.
1510 auto *BO = cast<BinaryOperator>(Op0IsBinop ? Op0 : Op1);
1511 BinaryOperator::BinaryOps BOpcode = BO->getOpcode();
1512 Constant *IdC = ConstantExpr::getBinOpIdentity(BOpcode, Shuf.getType(), true);
1513 if (!IdC)
1514 return nullptr;
1515
1516 // Shuffle identity constants into the lanes that return the original value.
1517 // Example: shuf (mul X, {-1,-2,-3,-4}), X, {0,5,6,3} --> mul X, {-1,1,1,-4}
1518 // Example: shuf X, (add X, {-1,-2,-3,-4}), {0,1,6,7} --> add X, {0,0,-3,-4}
1519 // The existing binop constant vector remains in the same operand position.
1520 ArrayRef<int> Mask = Shuf.getShuffleMask();
1521 Constant *NewC = Op0IsBinop ? ConstantExpr::getShuffleVector(C, IdC, Mask) :
1522 ConstantExpr::getShuffleVector(IdC, C, Mask);
1523
1524 bool MightCreatePoisonOrUB =
1525 is_contained(Mask, UndefMaskElem) &&
1526 (Instruction::isIntDivRem(BOpcode) || Instruction::isShift(BOpcode));
1527 if (MightCreatePoisonOrUB)
1528 NewC = getSafeVectorConstantForBinop(BOpcode, NewC, true);
1529
1530 // shuf (bop X, C), X, M --> bop X, C'
1531 // shuf X, (bop X, C), M --> bop X, C'
1532 Value *X = Op0IsBinop ? Op1 : Op0;
1533 Instruction *NewBO = BinaryOperator::Create(BOpcode, X, NewC);
1534 NewBO->copyIRFlags(BO);
1535
1536 // An undef shuffle mask element may propagate as an undef constant element in
1537 // the new binop. That would produce poison where the original code might not.
1538 // If we already made a safe constant, then there's no danger.
1539 if (is_contained(Mask, UndefMaskElem) && !MightCreatePoisonOrUB)
1540 NewBO->dropPoisonGeneratingFlags();
1541 return NewBO;
1542 }
1543
1544 /// If we have an insert of a scalar to a non-zero element of an undefined
1545 /// vector and then shuffle that value, that's the same as inserting to the zero
1546 /// element and shuffling. Splatting from the zero element is recognized as the
1547 /// canonical form of splat.
canonicalizeInsertSplat(ShuffleVectorInst & Shuf,InstCombiner::BuilderTy & Builder)1548 static Instruction *canonicalizeInsertSplat(ShuffleVectorInst &Shuf,
1549 InstCombiner::BuilderTy &Builder) {
1550 Value *Op0 = Shuf.getOperand(0), *Op1 = Shuf.getOperand(1);
1551 ArrayRef<int> Mask = Shuf.getShuffleMask();
1552 Value *X;
1553 uint64_t IndexC;
1554
1555 // Match a shuffle that is a splat to a non-zero element.
1556 if (!match(Op0, m_OneUse(m_InsertElt(m_Undef(), m_Value(X),
1557 m_ConstantInt(IndexC)))) ||
1558 !match(Op1, m_Undef()) || match(Mask, m_ZeroMask()) || IndexC == 0)
1559 return nullptr;
1560
1561 // Insert into element 0 of an undef vector.
1562 UndefValue *UndefVec = UndefValue::get(Shuf.getType());
1563 Constant *Zero = Builder.getInt32(0);
1564 Value *NewIns = Builder.CreateInsertElement(UndefVec, X, Zero);
1565
1566 // Splat from element 0. Any mask element that is undefined remains undefined.
1567 // For example:
1568 // shuf (inselt undef, X, 2), undef, <2,2,undef>
1569 // --> shuf (inselt undef, X, 0), undef, <0,0,undef>
1570 unsigned NumMaskElts = Shuf.getType()->getNumElements();
1571 SmallVector<int, 16> NewMask(NumMaskElts, 0);
1572 for (unsigned i = 0; i != NumMaskElts; ++i)
1573 if (Mask[i] == UndefMaskElem)
1574 NewMask[i] = Mask[i];
1575
1576 return new ShuffleVectorInst(NewIns, UndefVec, NewMask);
1577 }
1578
1579 /// Try to fold shuffles that are the equivalent of a vector select.
foldSelectShuffle(ShuffleVectorInst & Shuf,InstCombiner::BuilderTy & Builder,const DataLayout & DL)1580 static Instruction *foldSelectShuffle(ShuffleVectorInst &Shuf,
1581 InstCombiner::BuilderTy &Builder,
1582 const DataLayout &DL) {
1583 if (!Shuf.isSelect())
1584 return nullptr;
1585
1586 // Canonicalize to choose from operand 0 first unless operand 1 is undefined.
1587 // Commuting undef to operand 0 conflicts with another canonicalization.
1588 unsigned NumElts = Shuf.getType()->getNumElements();
1589 if (!isa<UndefValue>(Shuf.getOperand(1)) &&
1590 Shuf.getMaskValue(0) >= (int)NumElts) {
1591 // TODO: Can we assert that both operands of a shuffle-select are not undef
1592 // (otherwise, it would have been folded by instsimplify?
1593 Shuf.commute();
1594 return &Shuf;
1595 }
1596
1597 if (Instruction *I = foldSelectShuffleWith1Binop(Shuf))
1598 return I;
1599
1600 BinaryOperator *B0, *B1;
1601 if (!match(Shuf.getOperand(0), m_BinOp(B0)) ||
1602 !match(Shuf.getOperand(1), m_BinOp(B1)))
1603 return nullptr;
1604
1605 Value *X, *Y;
1606 Constant *C0, *C1;
1607 bool ConstantsAreOp1;
1608 if (match(B0, m_BinOp(m_Value(X), m_Constant(C0))) &&
1609 match(B1, m_BinOp(m_Value(Y), m_Constant(C1))))
1610 ConstantsAreOp1 = true;
1611 else if (match(B0, m_BinOp(m_Constant(C0), m_Value(X))) &&
1612 match(B1, m_BinOp(m_Constant(C1), m_Value(Y))))
1613 ConstantsAreOp1 = false;
1614 else
1615 return nullptr;
1616
1617 // We need matching binops to fold the lanes together.
1618 BinaryOperator::BinaryOps Opc0 = B0->getOpcode();
1619 BinaryOperator::BinaryOps Opc1 = B1->getOpcode();
1620 bool DropNSW = false;
1621 if (ConstantsAreOp1 && Opc0 != Opc1) {
1622 // TODO: We drop "nsw" if shift is converted into multiply because it may
1623 // not be correct when the shift amount is BitWidth - 1. We could examine
1624 // each vector element to determine if it is safe to keep that flag.
1625 if (Opc0 == Instruction::Shl || Opc1 == Instruction::Shl)
1626 DropNSW = true;
1627 if (BinopElts AltB0 = getAlternateBinop(B0, DL)) {
1628 assert(isa<Constant>(AltB0.Op1) && "Expecting constant with alt binop");
1629 Opc0 = AltB0.Opcode;
1630 C0 = cast<Constant>(AltB0.Op1);
1631 } else if (BinopElts AltB1 = getAlternateBinop(B1, DL)) {
1632 assert(isa<Constant>(AltB1.Op1) && "Expecting constant with alt binop");
1633 Opc1 = AltB1.Opcode;
1634 C1 = cast<Constant>(AltB1.Op1);
1635 }
1636 }
1637
1638 if (Opc0 != Opc1)
1639 return nullptr;
1640
1641 // The opcodes must be the same. Use a new name to make that clear.
1642 BinaryOperator::BinaryOps BOpc = Opc0;
1643
1644 // Select the constant elements needed for the single binop.
1645 ArrayRef<int> Mask = Shuf.getShuffleMask();
1646 Constant *NewC = ConstantExpr::getShuffleVector(C0, C1, Mask);
1647
1648 // We are moving a binop after a shuffle. When a shuffle has an undefined
1649 // mask element, the result is undefined, but it is not poison or undefined
1650 // behavior. That is not necessarily true for div/rem/shift.
1651 bool MightCreatePoisonOrUB =
1652 is_contained(Mask, UndefMaskElem) &&
1653 (Instruction::isIntDivRem(BOpc) || Instruction::isShift(BOpc));
1654 if (MightCreatePoisonOrUB)
1655 NewC = getSafeVectorConstantForBinop(BOpc, NewC, ConstantsAreOp1);
1656
1657 Value *V;
1658 if (X == Y) {
1659 // Remove a binop and the shuffle by rearranging the constant:
1660 // shuffle (op V, C0), (op V, C1), M --> op V, C'
1661 // shuffle (op C0, V), (op C1, V), M --> op C', V
1662 V = X;
1663 } else {
1664 // If there are 2 different variable operands, we must create a new shuffle
1665 // (select) first, so check uses to ensure that we don't end up with more
1666 // instructions than we started with.
1667 if (!B0->hasOneUse() && !B1->hasOneUse())
1668 return nullptr;
1669
1670 // If we use the original shuffle mask and op1 is *variable*, we would be
1671 // putting an undef into operand 1 of div/rem/shift. This is either UB or
1672 // poison. We do not have to guard against UB when *constants* are op1
1673 // because safe constants guarantee that we do not overflow sdiv/srem (and
1674 // there's no danger for other opcodes).
1675 // TODO: To allow this case, create a new shuffle mask with no undefs.
1676 if (MightCreatePoisonOrUB && !ConstantsAreOp1)
1677 return nullptr;
1678
1679 // Note: In general, we do not create new shuffles in InstCombine because we
1680 // do not know if a target can lower an arbitrary shuffle optimally. In this
1681 // case, the shuffle uses the existing mask, so there is no additional risk.
1682
1683 // Select the variable vectors first, then perform the binop:
1684 // shuffle (op X, C0), (op Y, C1), M --> op (shuffle X, Y, M), C'
1685 // shuffle (op C0, X), (op C1, Y), M --> op C', (shuffle X, Y, M)
1686 V = Builder.CreateShuffleVector(X, Y, Mask);
1687 }
1688
1689 Instruction *NewBO = ConstantsAreOp1 ? BinaryOperator::Create(BOpc, V, NewC) :
1690 BinaryOperator::Create(BOpc, NewC, V);
1691
1692 // Flags are intersected from the 2 source binops. But there are 2 exceptions:
1693 // 1. If we changed an opcode, poison conditions might have changed.
1694 // 2. If the shuffle had undef mask elements, the new binop might have undefs
1695 // where the original code did not. But if we already made a safe constant,
1696 // then there's no danger.
1697 NewBO->copyIRFlags(B0);
1698 NewBO->andIRFlags(B1);
1699 if (DropNSW)
1700 NewBO->setHasNoSignedWrap(false);
1701 if (is_contained(Mask, UndefMaskElem) && !MightCreatePoisonOrUB)
1702 NewBO->dropPoisonGeneratingFlags();
1703 return NewBO;
1704 }
1705
1706 /// Convert a narrowing shuffle of a bitcasted vector into a vector truncate.
1707 /// Example (little endian):
1708 /// shuf (bitcast <4 x i16> X to <8 x i8>), <0, 2, 4, 6> --> trunc X to <4 x i8>
foldTruncShuffle(ShuffleVectorInst & Shuf,bool IsBigEndian)1709 static Instruction *foldTruncShuffle(ShuffleVectorInst &Shuf,
1710 bool IsBigEndian) {
1711 // This must be a bitcasted shuffle of 1 vector integer operand.
1712 Type *DestType = Shuf.getType();
1713 Value *X;
1714 if (!match(Shuf.getOperand(0), m_BitCast(m_Value(X))) ||
1715 !match(Shuf.getOperand(1), m_Undef()) || !DestType->isIntOrIntVectorTy())
1716 return nullptr;
1717
1718 // The source type must have the same number of elements as the shuffle,
1719 // and the source element type must be larger than the shuffle element type.
1720 Type *SrcType = X->getType();
1721 if (!SrcType->isVectorTy() || !SrcType->isIntOrIntVectorTy() ||
1722 cast<VectorType>(SrcType)->getNumElements() !=
1723 cast<VectorType>(DestType)->getNumElements() ||
1724 SrcType->getScalarSizeInBits() % DestType->getScalarSizeInBits() != 0)
1725 return nullptr;
1726
1727 assert(Shuf.changesLength() && !Shuf.increasesLength() &&
1728 "Expected a shuffle that decreases length");
1729
1730 // Last, check that the mask chooses the correct low bits for each narrow
1731 // element in the result.
1732 uint64_t TruncRatio =
1733 SrcType->getScalarSizeInBits() / DestType->getScalarSizeInBits();
1734 ArrayRef<int> Mask = Shuf.getShuffleMask();
1735 for (unsigned i = 0, e = Mask.size(); i != e; ++i) {
1736 if (Mask[i] == UndefMaskElem)
1737 continue;
1738 uint64_t LSBIndex = IsBigEndian ? (i + 1) * TruncRatio - 1 : i * TruncRatio;
1739 assert(LSBIndex <= std::numeric_limits<int32_t>::max() &&
1740 "Overflowed 32-bits");
1741 if (Mask[i] != (int)LSBIndex)
1742 return nullptr;
1743 }
1744
1745 return new TruncInst(X, DestType);
1746 }
1747
1748 /// Match a shuffle-select-shuffle pattern where the shuffles are widening and
1749 /// narrowing (concatenating with undef and extracting back to the original
1750 /// length). This allows replacing the wide select with a narrow select.
narrowVectorSelect(ShuffleVectorInst & Shuf,InstCombiner::BuilderTy & Builder)1751 static Instruction *narrowVectorSelect(ShuffleVectorInst &Shuf,
1752 InstCombiner::BuilderTy &Builder) {
1753 // This must be a narrowing identity shuffle. It extracts the 1st N elements
1754 // of the 1st vector operand of a shuffle.
1755 if (!match(Shuf.getOperand(1), m_Undef()) || !Shuf.isIdentityWithExtract())
1756 return nullptr;
1757
1758 // The vector being shuffled must be a vector select that we can eliminate.
1759 // TODO: The one-use requirement could be eased if X and/or Y are constants.
1760 Value *Cond, *X, *Y;
1761 if (!match(Shuf.getOperand(0),
1762 m_OneUse(m_Select(m_Value(Cond), m_Value(X), m_Value(Y)))))
1763 return nullptr;
1764
1765 // We need a narrow condition value. It must be extended with undef elements
1766 // and have the same number of elements as this shuffle.
1767 unsigned NarrowNumElts = Shuf.getType()->getNumElements();
1768 Value *NarrowCond;
1769 if (!match(Cond, m_OneUse(m_Shuffle(m_Value(NarrowCond), m_Undef()))) ||
1770 cast<VectorType>(NarrowCond->getType())->getNumElements() !=
1771 NarrowNumElts ||
1772 !cast<ShuffleVectorInst>(Cond)->isIdentityWithPadding())
1773 return nullptr;
1774
1775 // shuf (sel (shuf NarrowCond, undef, WideMask), X, Y), undef, NarrowMask) -->
1776 // sel NarrowCond, (shuf X, undef, NarrowMask), (shuf Y, undef, NarrowMask)
1777 Value *Undef = UndefValue::get(X->getType());
1778 Value *NarrowX = Builder.CreateShuffleVector(X, Undef, Shuf.getShuffleMask());
1779 Value *NarrowY = Builder.CreateShuffleVector(Y, Undef, Shuf.getShuffleMask());
1780 return SelectInst::Create(NarrowCond, NarrowX, NarrowY);
1781 }
1782
1783 /// Try to combine 2 shuffles into 1 shuffle by concatenating a shuffle mask.
foldIdentityExtractShuffle(ShuffleVectorInst & Shuf)1784 static Instruction *foldIdentityExtractShuffle(ShuffleVectorInst &Shuf) {
1785 Value *Op0 = Shuf.getOperand(0), *Op1 = Shuf.getOperand(1);
1786 if (!Shuf.isIdentityWithExtract() || !isa<UndefValue>(Op1))
1787 return nullptr;
1788
1789 Value *X, *Y;
1790 ArrayRef<int> Mask;
1791 if (!match(Op0, m_Shuffle(m_Value(X), m_Value(Y), m_Mask(Mask))))
1792 return nullptr;
1793
1794 // Be conservative with shuffle transforms. If we can't kill the 1st shuffle,
1795 // then combining may result in worse codegen.
1796 if (!Op0->hasOneUse())
1797 return nullptr;
1798
1799 // We are extracting a subvector from a shuffle. Remove excess elements from
1800 // the 1st shuffle mask to eliminate the extract.
1801 //
1802 // This transform is conservatively limited to identity extracts because we do
1803 // not allow arbitrary shuffle mask creation as a target-independent transform
1804 // (because we can't guarantee that will lower efficiently).
1805 //
1806 // If the extracting shuffle has an undef mask element, it transfers to the
1807 // new shuffle mask. Otherwise, copy the original mask element. Example:
1808 // shuf (shuf X, Y, <C0, C1, C2, undef, C4>), undef, <0, undef, 2, 3> -->
1809 // shuf X, Y, <C0, undef, C2, undef>
1810 unsigned NumElts = Shuf.getType()->getNumElements();
1811 SmallVector<int, 16> NewMask(NumElts);
1812 assert(NumElts < Mask.size() &&
1813 "Identity with extract must have less elements than its inputs");
1814
1815 for (unsigned i = 0; i != NumElts; ++i) {
1816 int ExtractMaskElt = Shuf.getMaskValue(i);
1817 int MaskElt = Mask[i];
1818 NewMask[i] = ExtractMaskElt == UndefMaskElem ? ExtractMaskElt : MaskElt;
1819 }
1820 return new ShuffleVectorInst(X, Y, NewMask);
1821 }
1822
1823 /// Try to replace a shuffle with an insertelement or try to replace a shuffle
1824 /// operand with the operand of an insertelement.
foldShuffleWithInsert(ShuffleVectorInst & Shuf,InstCombiner & IC)1825 static Instruction *foldShuffleWithInsert(ShuffleVectorInst &Shuf,
1826 InstCombiner &IC) {
1827 Value *V0 = Shuf.getOperand(0), *V1 = Shuf.getOperand(1);
1828 SmallVector<int, 16> Mask;
1829 Shuf.getShuffleMask(Mask);
1830
1831 // The shuffle must not change vector sizes.
1832 // TODO: This restriction could be removed if the insert has only one use
1833 // (because the transform would require a new length-changing shuffle).
1834 int NumElts = Mask.size();
1835 if (NumElts != (int)(cast<VectorType>(V0->getType())->getNumElements()))
1836 return nullptr;
1837
1838 // This is a specialization of a fold in SimplifyDemandedVectorElts. We may
1839 // not be able to handle it there if the insertelement has >1 use.
1840 // If the shuffle has an insertelement operand but does not choose the
1841 // inserted scalar element from that value, then we can replace that shuffle
1842 // operand with the source vector of the insertelement.
1843 Value *X;
1844 uint64_t IdxC;
1845 if (match(V0, m_InsertElt(m_Value(X), m_Value(), m_ConstantInt(IdxC)))) {
1846 // shuf (inselt X, ?, IdxC), ?, Mask --> shuf X, ?, Mask
1847 if (none_of(Mask, [IdxC](int MaskElt) { return MaskElt == (int)IdxC; }))
1848 return IC.replaceOperand(Shuf, 0, X);
1849 }
1850 if (match(V1, m_InsertElt(m_Value(X), m_Value(), m_ConstantInt(IdxC)))) {
1851 // Offset the index constant by the vector width because we are checking for
1852 // accesses to the 2nd vector input of the shuffle.
1853 IdxC += NumElts;
1854 // shuf ?, (inselt X, ?, IdxC), Mask --> shuf ?, X, Mask
1855 if (none_of(Mask, [IdxC](int MaskElt) { return MaskElt == (int)IdxC; }))
1856 return IC.replaceOperand(Shuf, 1, X);
1857 }
1858
1859 // shuffle (insert ?, Scalar, IndexC), V1, Mask --> insert V1, Scalar, IndexC'
1860 auto isShufflingScalarIntoOp1 = [&](Value *&Scalar, ConstantInt *&IndexC) {
1861 // We need an insertelement with a constant index.
1862 if (!match(V0, m_InsertElt(m_Value(), m_Value(Scalar),
1863 m_ConstantInt(IndexC))))
1864 return false;
1865
1866 // Test the shuffle mask to see if it splices the inserted scalar into the
1867 // operand 1 vector of the shuffle.
1868 int NewInsIndex = -1;
1869 for (int i = 0; i != NumElts; ++i) {
1870 // Ignore undef mask elements.
1871 if (Mask[i] == -1)
1872 continue;
1873
1874 // The shuffle takes elements of operand 1 without lane changes.
1875 if (Mask[i] == NumElts + i)
1876 continue;
1877
1878 // The shuffle must choose the inserted scalar exactly once.
1879 if (NewInsIndex != -1 || Mask[i] != IndexC->getSExtValue())
1880 return false;
1881
1882 // The shuffle is placing the inserted scalar into element i.
1883 NewInsIndex = i;
1884 }
1885
1886 assert(NewInsIndex != -1 && "Did not fold shuffle with unused operand?");
1887
1888 // Index is updated to the potentially translated insertion lane.
1889 IndexC = ConstantInt::get(IndexC->getType(), NewInsIndex);
1890 return true;
1891 };
1892
1893 // If the shuffle is unnecessary, insert the scalar operand directly into
1894 // operand 1 of the shuffle. Example:
1895 // shuffle (insert ?, S, 1), V1, <1, 5, 6, 7> --> insert V1, S, 0
1896 Value *Scalar;
1897 ConstantInt *IndexC;
1898 if (isShufflingScalarIntoOp1(Scalar, IndexC))
1899 return InsertElementInst::Create(V1, Scalar, IndexC);
1900
1901 // Try again after commuting shuffle. Example:
1902 // shuffle V0, (insert ?, S, 0), <0, 1, 2, 4> -->
1903 // shuffle (insert ?, S, 0), V0, <4, 5, 6, 0> --> insert V0, S, 3
1904 std::swap(V0, V1);
1905 ShuffleVectorInst::commuteShuffleMask(Mask, NumElts);
1906 if (isShufflingScalarIntoOp1(Scalar, IndexC))
1907 return InsertElementInst::Create(V1, Scalar, IndexC);
1908
1909 return nullptr;
1910 }
1911
foldIdentityPaddedShuffles(ShuffleVectorInst & Shuf)1912 static Instruction *foldIdentityPaddedShuffles(ShuffleVectorInst &Shuf) {
1913 // Match the operands as identity with padding (also known as concatenation
1914 // with undef) shuffles of the same source type. The backend is expected to
1915 // recreate these concatenations from a shuffle of narrow operands.
1916 auto *Shuffle0 = dyn_cast<ShuffleVectorInst>(Shuf.getOperand(0));
1917 auto *Shuffle1 = dyn_cast<ShuffleVectorInst>(Shuf.getOperand(1));
1918 if (!Shuffle0 || !Shuffle0->isIdentityWithPadding() ||
1919 !Shuffle1 || !Shuffle1->isIdentityWithPadding())
1920 return nullptr;
1921
1922 // We limit this transform to power-of-2 types because we expect that the
1923 // backend can convert the simplified IR patterns to identical nodes as the
1924 // original IR.
1925 // TODO: If we can verify the same behavior for arbitrary types, the
1926 // power-of-2 checks can be removed.
1927 Value *X = Shuffle0->getOperand(0);
1928 Value *Y = Shuffle1->getOperand(0);
1929 if (X->getType() != Y->getType() ||
1930 !isPowerOf2_32(Shuf.getType()->getNumElements()) ||
1931 !isPowerOf2_32(Shuffle0->getType()->getNumElements()) ||
1932 !isPowerOf2_32(cast<VectorType>(X->getType())->getNumElements()) ||
1933 isa<UndefValue>(X) || isa<UndefValue>(Y))
1934 return nullptr;
1935 assert(isa<UndefValue>(Shuffle0->getOperand(1)) &&
1936 isa<UndefValue>(Shuffle1->getOperand(1)) &&
1937 "Unexpected operand for identity shuffle");
1938
1939 // This is a shuffle of 2 widening shuffles. We can shuffle the narrow source
1940 // operands directly by adjusting the shuffle mask to account for the narrower
1941 // types:
1942 // shuf (widen X), (widen Y), Mask --> shuf X, Y, Mask'
1943 int NarrowElts = cast<VectorType>(X->getType())->getNumElements();
1944 int WideElts = Shuffle0->getType()->getNumElements();
1945 assert(WideElts > NarrowElts && "Unexpected types for identity with padding");
1946
1947 ArrayRef<int> Mask = Shuf.getShuffleMask();
1948 SmallVector<int, 16> NewMask(Mask.size(), -1);
1949 for (int i = 0, e = Mask.size(); i != e; ++i) {
1950 if (Mask[i] == -1)
1951 continue;
1952
1953 // If this shuffle is choosing an undef element from 1 of the sources, that
1954 // element is undef.
1955 if (Mask[i] < WideElts) {
1956 if (Shuffle0->getMaskValue(Mask[i]) == -1)
1957 continue;
1958 } else {
1959 if (Shuffle1->getMaskValue(Mask[i] - WideElts) == -1)
1960 continue;
1961 }
1962
1963 // If this shuffle is choosing from the 1st narrow op, the mask element is
1964 // the same. If this shuffle is choosing from the 2nd narrow op, the mask
1965 // element is offset down to adjust for the narrow vector widths.
1966 if (Mask[i] < WideElts) {
1967 assert(Mask[i] < NarrowElts && "Unexpected shuffle mask");
1968 NewMask[i] = Mask[i];
1969 } else {
1970 assert(Mask[i] < (WideElts + NarrowElts) && "Unexpected shuffle mask");
1971 NewMask[i] = Mask[i] - (WideElts - NarrowElts);
1972 }
1973 }
1974 return new ShuffleVectorInst(X, Y, NewMask);
1975 }
1976
visitShuffleVectorInst(ShuffleVectorInst & SVI)1977 Instruction *InstCombiner::visitShuffleVectorInst(ShuffleVectorInst &SVI) {
1978 Value *LHS = SVI.getOperand(0);
1979 Value *RHS = SVI.getOperand(1);
1980 SimplifyQuery ShufQuery = SQ.getWithInstruction(&SVI);
1981 if (auto *V = SimplifyShuffleVectorInst(LHS, RHS, SVI.getShuffleMask(),
1982 SVI.getType(), ShufQuery))
1983 return replaceInstUsesWith(SVI, V);
1984
1985 // shuffle x, x, mask --> shuffle x, undef, mask'
1986 unsigned VWidth = SVI.getType()->getNumElements();
1987 unsigned LHSWidth = cast<VectorType>(LHS->getType())->getNumElements();
1988 ArrayRef<int> Mask = SVI.getShuffleMask();
1989 Type *Int32Ty = Type::getInt32Ty(SVI.getContext());
1990
1991 // Peek through a bitcasted shuffle operand by scaling the mask. If the
1992 // simulated shuffle can simplify, then this shuffle is unnecessary:
1993 // shuf (bitcast X), undef, Mask --> bitcast X'
1994 // TODO: This could be extended to allow length-changing shuffles.
1995 // The transform might also be obsoleted if we allowed canonicalization
1996 // of bitcasted shuffles.
1997 Value *X;
1998 if (match(LHS, m_BitCast(m_Value(X))) && match(RHS, m_Undef()) &&
1999 X->getType()->isVectorTy() && VWidth == LHSWidth) {
2000 // Try to create a scaled mask constant.
2001 auto *XType = cast<VectorType>(X->getType());
2002 unsigned XNumElts = XType->getNumElements();
2003 SmallVector<int, 16> ScaledMask;
2004 if (XNumElts >= VWidth) {
2005 assert(XNumElts % VWidth == 0 && "Unexpected vector bitcast");
2006 narrowShuffleMaskElts(XNumElts / VWidth, Mask, ScaledMask);
2007 } else {
2008 assert(VWidth % XNumElts == 0 && "Unexpected vector bitcast");
2009 if (!widenShuffleMaskElts(VWidth / XNumElts, Mask, ScaledMask))
2010 ScaledMask.clear();
2011 }
2012 if (!ScaledMask.empty()) {
2013 // If the shuffled source vector simplifies, cast that value to this
2014 // shuffle's type.
2015 if (auto *V = SimplifyShuffleVectorInst(X, UndefValue::get(XType),
2016 ScaledMask, XType, ShufQuery))
2017 return BitCastInst::Create(Instruction::BitCast, V, SVI.getType());
2018 }
2019 }
2020
2021 if (LHS == RHS) {
2022 assert(!isa<UndefValue>(RHS) && "Shuffle with 2 undef ops not simplified?");
2023 // Remap any references to RHS to use LHS.
2024 SmallVector<int, 16> Elts;
2025 for (unsigned i = 0; i != VWidth; ++i) {
2026 // Propagate undef elements or force mask to LHS.
2027 if (Mask[i] < 0)
2028 Elts.push_back(UndefMaskElem);
2029 else
2030 Elts.push_back(Mask[i] % LHSWidth);
2031 }
2032 return new ShuffleVectorInst(LHS, UndefValue::get(RHS->getType()), Elts);
2033 }
2034
2035 // shuffle undef, x, mask --> shuffle x, undef, mask'
2036 if (isa<UndefValue>(LHS)) {
2037 SVI.commute();
2038 return &SVI;
2039 }
2040
2041 if (Instruction *I = canonicalizeInsertSplat(SVI, Builder))
2042 return I;
2043
2044 if (Instruction *I = foldSelectShuffle(SVI, Builder, DL))
2045 return I;
2046
2047 if (Instruction *I = foldTruncShuffle(SVI, DL.isBigEndian()))
2048 return I;
2049
2050 if (Instruction *I = narrowVectorSelect(SVI, Builder))
2051 return I;
2052
2053 APInt UndefElts(VWidth, 0);
2054 APInt AllOnesEltMask(APInt::getAllOnesValue(VWidth));
2055 if (Value *V = SimplifyDemandedVectorElts(&SVI, AllOnesEltMask, UndefElts)) {
2056 if (V != &SVI)
2057 return replaceInstUsesWith(SVI, V);
2058 return &SVI;
2059 }
2060
2061 if (Instruction *I = foldIdentityExtractShuffle(SVI))
2062 return I;
2063
2064 // These transforms have the potential to lose undef knowledge, so they are
2065 // intentionally placed after SimplifyDemandedVectorElts().
2066 if (Instruction *I = foldShuffleWithInsert(SVI, *this))
2067 return I;
2068 if (Instruction *I = foldIdentityPaddedShuffles(SVI))
2069 return I;
2070
2071 if (isa<UndefValue>(RHS) && canEvaluateShuffled(LHS, Mask)) {
2072 Value *V = evaluateInDifferentElementOrder(LHS, Mask);
2073 return replaceInstUsesWith(SVI, V);
2074 }
2075
2076 // SROA generates shuffle+bitcast when the extracted sub-vector is bitcast to
2077 // a non-vector type. We can instead bitcast the original vector followed by
2078 // an extract of the desired element:
2079 //
2080 // %sroa = shufflevector <16 x i8> %in, <16 x i8> undef,
2081 // <4 x i32> <i32 0, i32 1, i32 2, i32 3>
2082 // %1 = bitcast <4 x i8> %sroa to i32
2083 // Becomes:
2084 // %bc = bitcast <16 x i8> %in to <4 x i32>
2085 // %ext = extractelement <4 x i32> %bc, i32 0
2086 //
2087 // If the shuffle is extracting a contiguous range of values from the input
2088 // vector then each use which is a bitcast of the extracted size can be
2089 // replaced. This will work if the vector types are compatible, and the begin
2090 // index is aligned to a value in the casted vector type. If the begin index
2091 // isn't aligned then we can shuffle the original vector (keeping the same
2092 // vector type) before extracting.
2093 //
2094 // This code will bail out if the target type is fundamentally incompatible
2095 // with vectors of the source type.
2096 //
2097 // Example of <16 x i8>, target type i32:
2098 // Index range [4,8): v-----------v Will work.
2099 // +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
2100 // <16 x i8>: | | | | | | | | | | | | | | | | |
2101 // <4 x i32>: | | | | |
2102 // +-----------+-----------+-----------+-----------+
2103 // Index range [6,10): ^-----------^ Needs an extra shuffle.
2104 // Target type i40: ^--------------^ Won't work, bail.
2105 bool MadeChange = false;
2106 if (isShuffleExtractingFromLHS(SVI, Mask)) {
2107 Value *V = LHS;
2108 unsigned MaskElems = Mask.size();
2109 VectorType *SrcTy = cast<VectorType>(V->getType());
2110 unsigned VecBitWidth = SrcTy->getPrimitiveSizeInBits().getFixedSize();
2111 unsigned SrcElemBitWidth = DL.getTypeSizeInBits(SrcTy->getElementType());
2112 assert(SrcElemBitWidth && "vector elements must have a bitwidth");
2113 unsigned SrcNumElems = SrcTy->getNumElements();
2114 SmallVector<BitCastInst *, 8> BCs;
2115 DenseMap<Type *, Value *> NewBCs;
2116 for (User *U : SVI.users())
2117 if (BitCastInst *BC = dyn_cast<BitCastInst>(U))
2118 if (!BC->use_empty())
2119 // Only visit bitcasts that weren't previously handled.
2120 BCs.push_back(BC);
2121 for (BitCastInst *BC : BCs) {
2122 unsigned BegIdx = Mask.front();
2123 Type *TgtTy = BC->getDestTy();
2124 unsigned TgtElemBitWidth = DL.getTypeSizeInBits(TgtTy);
2125 if (!TgtElemBitWidth)
2126 continue;
2127 unsigned TgtNumElems = VecBitWidth / TgtElemBitWidth;
2128 bool VecBitWidthsEqual = VecBitWidth == TgtNumElems * TgtElemBitWidth;
2129 bool BegIsAligned = 0 == ((SrcElemBitWidth * BegIdx) % TgtElemBitWidth);
2130 if (!VecBitWidthsEqual)
2131 continue;
2132 if (!VectorType::isValidElementType(TgtTy))
2133 continue;
2134 auto *CastSrcTy = FixedVectorType::get(TgtTy, TgtNumElems);
2135 if (!BegIsAligned) {
2136 // Shuffle the input so [0,NumElements) contains the output, and
2137 // [NumElems,SrcNumElems) is undef.
2138 SmallVector<int, 16> ShuffleMask(SrcNumElems, -1);
2139 for (unsigned I = 0, E = MaskElems, Idx = BegIdx; I != E; ++Idx, ++I)
2140 ShuffleMask[I] = Idx;
2141 V = Builder.CreateShuffleVector(V, UndefValue::get(V->getType()),
2142 ShuffleMask,
2143 SVI.getName() + ".extract");
2144 BegIdx = 0;
2145 }
2146 unsigned SrcElemsPerTgtElem = TgtElemBitWidth / SrcElemBitWidth;
2147 assert(SrcElemsPerTgtElem);
2148 BegIdx /= SrcElemsPerTgtElem;
2149 bool BCAlreadyExists = NewBCs.find(CastSrcTy) != NewBCs.end();
2150 auto *NewBC =
2151 BCAlreadyExists
2152 ? NewBCs[CastSrcTy]
2153 : Builder.CreateBitCast(V, CastSrcTy, SVI.getName() + ".bc");
2154 if (!BCAlreadyExists)
2155 NewBCs[CastSrcTy] = NewBC;
2156 auto *Ext = Builder.CreateExtractElement(
2157 NewBC, ConstantInt::get(Int32Ty, BegIdx), SVI.getName() + ".extract");
2158 // The shufflevector isn't being replaced: the bitcast that used it
2159 // is. InstCombine will visit the newly-created instructions.
2160 replaceInstUsesWith(*BC, Ext);
2161 MadeChange = true;
2162 }
2163 }
2164
2165 // If the LHS is a shufflevector itself, see if we can combine it with this
2166 // one without producing an unusual shuffle.
2167 // Cases that might be simplified:
2168 // 1.
2169 // x1=shuffle(v1,v2,mask1)
2170 // x=shuffle(x1,undef,mask)
2171 // ==>
2172 // x=shuffle(v1,undef,newMask)
2173 // newMask[i] = (mask[i] < x1.size()) ? mask1[mask[i]] : -1
2174 // 2.
2175 // x1=shuffle(v1,undef,mask1)
2176 // x=shuffle(x1,x2,mask)
2177 // where v1.size() == mask1.size()
2178 // ==>
2179 // x=shuffle(v1,x2,newMask)
2180 // newMask[i] = (mask[i] < x1.size()) ? mask1[mask[i]] : mask[i]
2181 // 3.
2182 // x2=shuffle(v2,undef,mask2)
2183 // x=shuffle(x1,x2,mask)
2184 // where v2.size() == mask2.size()
2185 // ==>
2186 // x=shuffle(x1,v2,newMask)
2187 // newMask[i] = (mask[i] < x1.size())
2188 // ? mask[i] : mask2[mask[i]-x1.size()]+x1.size()
2189 // 4.
2190 // x1=shuffle(v1,undef,mask1)
2191 // x2=shuffle(v2,undef,mask2)
2192 // x=shuffle(x1,x2,mask)
2193 // where v1.size() == v2.size()
2194 // ==>
2195 // x=shuffle(v1,v2,newMask)
2196 // newMask[i] = (mask[i] < x1.size())
2197 // ? mask1[mask[i]] : mask2[mask[i]-x1.size()]+v1.size()
2198 //
2199 // Here we are really conservative:
2200 // we are absolutely afraid of producing a shuffle mask not in the input
2201 // program, because the code gen may not be smart enough to turn a merged
2202 // shuffle into two specific shuffles: it may produce worse code. As such,
2203 // we only merge two shuffles if the result is either a splat or one of the
2204 // input shuffle masks. In this case, merging the shuffles just removes
2205 // one instruction, which we know is safe. This is good for things like
2206 // turning: (splat(splat)) -> splat, or
2207 // merge(V[0..n], V[n+1..2n]) -> V[0..2n]
2208 ShuffleVectorInst* LHSShuffle = dyn_cast<ShuffleVectorInst>(LHS);
2209 ShuffleVectorInst* RHSShuffle = dyn_cast<ShuffleVectorInst>(RHS);
2210 if (LHSShuffle)
2211 if (!isa<UndefValue>(LHSShuffle->getOperand(1)) && !isa<UndefValue>(RHS))
2212 LHSShuffle = nullptr;
2213 if (RHSShuffle)
2214 if (!isa<UndefValue>(RHSShuffle->getOperand(1)))
2215 RHSShuffle = nullptr;
2216 if (!LHSShuffle && !RHSShuffle)
2217 return MadeChange ? &SVI : nullptr;
2218
2219 Value* LHSOp0 = nullptr;
2220 Value* LHSOp1 = nullptr;
2221 Value* RHSOp0 = nullptr;
2222 unsigned LHSOp0Width = 0;
2223 unsigned RHSOp0Width = 0;
2224 if (LHSShuffle) {
2225 LHSOp0 = LHSShuffle->getOperand(0);
2226 LHSOp1 = LHSShuffle->getOperand(1);
2227 LHSOp0Width = cast<VectorType>(LHSOp0->getType())->getNumElements();
2228 }
2229 if (RHSShuffle) {
2230 RHSOp0 = RHSShuffle->getOperand(0);
2231 RHSOp0Width = cast<VectorType>(RHSOp0->getType())->getNumElements();
2232 }
2233 Value* newLHS = LHS;
2234 Value* newRHS = RHS;
2235 if (LHSShuffle) {
2236 // case 1
2237 if (isa<UndefValue>(RHS)) {
2238 newLHS = LHSOp0;
2239 newRHS = LHSOp1;
2240 }
2241 // case 2 or 4
2242 else if (LHSOp0Width == LHSWidth) {
2243 newLHS = LHSOp0;
2244 }
2245 }
2246 // case 3 or 4
2247 if (RHSShuffle && RHSOp0Width == LHSWidth) {
2248 newRHS = RHSOp0;
2249 }
2250 // case 4
2251 if (LHSOp0 == RHSOp0) {
2252 newLHS = LHSOp0;
2253 newRHS = nullptr;
2254 }
2255
2256 if (newLHS == LHS && newRHS == RHS)
2257 return MadeChange ? &SVI : nullptr;
2258
2259 ArrayRef<int> LHSMask;
2260 ArrayRef<int> RHSMask;
2261 if (newLHS != LHS)
2262 LHSMask = LHSShuffle->getShuffleMask();
2263 if (RHSShuffle && newRHS != RHS)
2264 RHSMask = RHSShuffle->getShuffleMask();
2265
2266 unsigned newLHSWidth = (newLHS != LHS) ? LHSOp0Width : LHSWidth;
2267 SmallVector<int, 16> newMask;
2268 bool isSplat = true;
2269 int SplatElt = -1;
2270 // Create a new mask for the new ShuffleVectorInst so that the new
2271 // ShuffleVectorInst is equivalent to the original one.
2272 for (unsigned i = 0; i < VWidth; ++i) {
2273 int eltMask;
2274 if (Mask[i] < 0) {
2275 // This element is an undef value.
2276 eltMask = -1;
2277 } else if (Mask[i] < (int)LHSWidth) {
2278 // This element is from left hand side vector operand.
2279 //
2280 // If LHS is going to be replaced (case 1, 2, or 4), calculate the
2281 // new mask value for the element.
2282 if (newLHS != LHS) {
2283 eltMask = LHSMask[Mask[i]];
2284 // If the value selected is an undef value, explicitly specify it
2285 // with a -1 mask value.
2286 if (eltMask >= (int)LHSOp0Width && isa<UndefValue>(LHSOp1))
2287 eltMask = -1;
2288 } else
2289 eltMask = Mask[i];
2290 } else {
2291 // This element is from right hand side vector operand
2292 //
2293 // If the value selected is an undef value, explicitly specify it
2294 // with a -1 mask value. (case 1)
2295 if (isa<UndefValue>(RHS))
2296 eltMask = -1;
2297 // If RHS is going to be replaced (case 3 or 4), calculate the
2298 // new mask value for the element.
2299 else if (newRHS != RHS) {
2300 eltMask = RHSMask[Mask[i]-LHSWidth];
2301 // If the value selected is an undef value, explicitly specify it
2302 // with a -1 mask value.
2303 if (eltMask >= (int)RHSOp0Width) {
2304 assert(isa<UndefValue>(RHSShuffle->getOperand(1))
2305 && "should have been check above");
2306 eltMask = -1;
2307 }
2308 } else
2309 eltMask = Mask[i]-LHSWidth;
2310
2311 // If LHS's width is changed, shift the mask value accordingly.
2312 // If newRHS == nullptr, i.e. LHSOp0 == RHSOp0, we want to remap any
2313 // references from RHSOp0 to LHSOp0, so we don't need to shift the mask.
2314 // If newRHS == newLHS, we want to remap any references from newRHS to
2315 // newLHS so that we can properly identify splats that may occur due to
2316 // obfuscation across the two vectors.
2317 if (eltMask >= 0 && newRHS != nullptr && newLHS != newRHS)
2318 eltMask += newLHSWidth;
2319 }
2320
2321 // Check if this could still be a splat.
2322 if (eltMask >= 0) {
2323 if (SplatElt >= 0 && SplatElt != eltMask)
2324 isSplat = false;
2325 SplatElt = eltMask;
2326 }
2327
2328 newMask.push_back(eltMask);
2329 }
2330
2331 // If the result mask is equal to one of the original shuffle masks,
2332 // or is a splat, do the replacement.
2333 if (isSplat || newMask == LHSMask || newMask == RHSMask || newMask == Mask) {
2334 SmallVector<Constant*, 16> Elts;
2335 for (unsigned i = 0, e = newMask.size(); i != e; ++i) {
2336 if (newMask[i] < 0) {
2337 Elts.push_back(UndefValue::get(Int32Ty));
2338 } else {
2339 Elts.push_back(ConstantInt::get(Int32Ty, newMask[i]));
2340 }
2341 }
2342 if (!newRHS)
2343 newRHS = UndefValue::get(newLHS->getType());
2344 return new ShuffleVectorInst(newLHS, newRHS, ConstantVector::get(Elts));
2345 }
2346
2347 return MadeChange ? &SVI : nullptr;
2348 }
2349