1
//===- InstCombineVectorOps.cpp -------------------------------------------===//
3
// The LLVM Compiler Infrastructure
5
// This file is distributed under the University of Illinois Open Source
6
// License. See LICENSE.TXT for details.
8
//===----------------------------------------------------------------------===//
10
// This file implements instcombine for ExtractElement, InsertElement and
13
//===----------------------------------------------------------------------===//
15
#include "InstCombine.h"
18
/// CheapToScalarize - Return true if the value is cheaper to scalarize than it
19
/// is to leave as a vector operation.
20
static bool CheapToScalarize(Value *V, bool isConstant) {
21
if (isa<ConstantAggregateZero>(V))
23
if (ConstantVector *C = dyn_cast<ConstantVector>(V)) {
24
if (isConstant) return true;
25
// If all elts are the same, we can extract.
26
Constant *Op0 = C->getOperand(0);
27
for (unsigned i = 1; i < C->getNumOperands(); ++i)
28
if (C->getOperand(i) != Op0)
32
Instruction *I = dyn_cast<Instruction>(V);
35
// Insert element gets simplified to the inserted element or is deleted if
36
// this is constant idx extract element and its a constant idx insertelt.
37
if (I->getOpcode() == Instruction::InsertElement && isConstant &&
38
isa<ConstantInt>(I->getOperand(2)))
40
if (I->getOpcode() == Instruction::Load && I->hasOneUse())
42
if (BinaryOperator *BO = dyn_cast<BinaryOperator>(I))
43
if (BO->hasOneUse() &&
44
(CheapToScalarize(BO->getOperand(0), isConstant) ||
45
CheapToScalarize(BO->getOperand(1), isConstant)))
47
if (CmpInst *CI = dyn_cast<CmpInst>(I))
48
if (CI->hasOneUse() &&
49
(CheapToScalarize(CI->getOperand(0), isConstant) ||
50
CheapToScalarize(CI->getOperand(1), isConstant)))
56
/// Read and decode a shufflevector mask.
58
/// It turns undef elements into values that are larger than the number of
59
/// elements in the input.
60
static std::vector<unsigned> getShuffleMask(const ShuffleVectorInst *SVI) {
61
unsigned NElts = SVI->getType()->getNumElements();
62
if (isa<ConstantAggregateZero>(SVI->getOperand(2)))
63
return std::vector<unsigned>(NElts, 0);
64
if (isa<UndefValue>(SVI->getOperand(2)))
65
return std::vector<unsigned>(NElts, 2*NElts);
67
std::vector<unsigned> Result;
68
const ConstantVector *CP = cast<ConstantVector>(SVI->getOperand(2));
69
for (User::const_op_iterator i = CP->op_begin(), e = CP->op_end(); i!=e; ++i)
70
if (isa<UndefValue>(*i))
71
Result.push_back(NElts*2); // undef -> 8
73
Result.push_back(cast<ConstantInt>(*i)->getZExtValue());
77
/// FindScalarElement - Given a vector and an element number, see if the scalar
78
/// value is already around as a register, for example if it were inserted then
79
/// extracted from the vector.
80
static Value *FindScalarElement(Value *V, unsigned EltNo) {
81
assert(V->getType()->isVectorTy() && "Not looking at a vector?");
82
const VectorType *PTy = cast<VectorType>(V->getType());
83
unsigned Width = PTy->getNumElements();
84
if (EltNo >= Width) // Out of range access.
85
return UndefValue::get(PTy->getElementType());
87
if (isa<UndefValue>(V))
88
return UndefValue::get(PTy->getElementType());
89
if (isa<ConstantAggregateZero>(V))
90
return Constant::getNullValue(PTy->getElementType());
91
if (ConstantVector *CP = dyn_cast<ConstantVector>(V))
92
return CP->getOperand(EltNo);
94
if (InsertElementInst *III = dyn_cast<InsertElementInst>(V)) {
95
// If this is an insert to a variable element, we don't know what it is.
96
if (!isa<ConstantInt>(III->getOperand(2)))
98
unsigned IIElt = cast<ConstantInt>(III->getOperand(2))->getZExtValue();
100
// If this is an insert to the element we are looking for, return the
103
return III->getOperand(1);
105
// Otherwise, the insertelement doesn't modify the value, recurse on its
107
return FindScalarElement(III->getOperand(0), EltNo);
110
if (ShuffleVectorInst *SVI = dyn_cast<ShuffleVectorInst>(V)) {
112
cast<VectorType>(SVI->getOperand(0)->getType())->getNumElements();
113
unsigned InEl = getShuffleMask(SVI)[EltNo];
115
return FindScalarElement(SVI->getOperand(0), InEl);
116
else if (InEl < LHSWidth*2)
117
return FindScalarElement(SVI->getOperand(1), InEl - LHSWidth);
119
return UndefValue::get(PTy->getElementType());
122
// Otherwise, we don't know.
126
Instruction *InstCombiner::visitExtractElementInst(ExtractElementInst &EI) {
127
// If vector val is undef, replace extract with scalar undef.
128
if (isa<UndefValue>(EI.getOperand(0)))
129
return ReplaceInstUsesWith(EI, UndefValue::get(EI.getType()));
131
// If vector val is constant 0, replace extract with scalar 0.
132
if (isa<ConstantAggregateZero>(EI.getOperand(0)))
133
return ReplaceInstUsesWith(EI, Constant::getNullValue(EI.getType()));
135
if (ConstantVector *C = dyn_cast<ConstantVector>(EI.getOperand(0))) {
136
// If vector val is constant with all elements the same, replace EI with
137
// that element. When the elements are not identical, we cannot replace yet
138
// (we do that below, but only when the index is constant).
139
Constant *op0 = C->getOperand(0);
140
for (unsigned i = 1; i != C->getNumOperands(); ++i)
141
if (C->getOperand(i) != op0) {
146
return ReplaceInstUsesWith(EI, op0);
149
// If extracting a specified index from the vector, see if we can recursively
150
// find a previously computed scalar that was inserted into the vector.
151
if (ConstantInt *IdxC = dyn_cast<ConstantInt>(EI.getOperand(1))) {
152
unsigned IndexVal = IdxC->getZExtValue();
153
unsigned VectorWidth = EI.getVectorOperandType()->getNumElements();
155
// If this is extracting an invalid index, turn this into undef, to avoid
156
// crashing the code below.
157
if (IndexVal >= VectorWidth)
158
return ReplaceInstUsesWith(EI, UndefValue::get(EI.getType()));
160
// This instruction only demands the single element from the input vector.
161
// If the input vector has a single use, simplify it based on this use
163
if (EI.getOperand(0)->hasOneUse() && VectorWidth != 1) {
164
APInt UndefElts(VectorWidth, 0);
165
APInt DemandedMask(VectorWidth, 0);
166
DemandedMask.set(IndexVal);
167
if (Value *V = SimplifyDemandedVectorElts(EI.getOperand(0),
168
DemandedMask, UndefElts)) {
174
if (Value *Elt = FindScalarElement(EI.getOperand(0), IndexVal))
175
return ReplaceInstUsesWith(EI, Elt);
177
// If the this extractelement is directly using a bitcast from a vector of
178
// the same number of elements, see if we can find the source element from
179
// it. In this case, we will end up needing to bitcast the scalars.
180
if (BitCastInst *BCI = dyn_cast<BitCastInst>(EI.getOperand(0))) {
181
if (const VectorType *VT =
182
dyn_cast<VectorType>(BCI->getOperand(0)->getType()))
183
if (VT->getNumElements() == VectorWidth)
184
if (Value *Elt = FindScalarElement(BCI->getOperand(0), IndexVal))
185
return new BitCastInst(Elt, EI.getType());
189
if (Instruction *I = dyn_cast<Instruction>(EI.getOperand(0))) {
190
// Push extractelement into predecessor operation if legal and
191
// profitable to do so
192
if (BinaryOperator *BO = dyn_cast<BinaryOperator>(I)) {
193
if (I->hasOneUse() &&
194
CheapToScalarize(BO, isa<ConstantInt>(EI.getOperand(1)))) {
196
Builder->CreateExtractElement(BO->getOperand(0), EI.getOperand(1),
197
EI.getName()+".lhs");
199
Builder->CreateExtractElement(BO->getOperand(1), EI.getOperand(1),
200
EI.getName()+".rhs");
201
return BinaryOperator::Create(BO->getOpcode(), newEI0, newEI1);
203
} else if (InsertElementInst *IE = dyn_cast<InsertElementInst>(I)) {
204
// Extracting the inserted element?
205
if (IE->getOperand(2) == EI.getOperand(1))
206
return ReplaceInstUsesWith(EI, IE->getOperand(1));
207
// If the inserted and extracted elements are constants, they must not
208
// be the same value, extract from the pre-inserted value instead.
209
if (isa<Constant>(IE->getOperand(2)) && isa<Constant>(EI.getOperand(1))) {
210
Worklist.AddValue(EI.getOperand(0));
211
EI.setOperand(0, IE->getOperand(0));
214
} else if (ShuffleVectorInst *SVI = dyn_cast<ShuffleVectorInst>(I)) {
215
// If this is extracting an element from a shufflevector, figure out where
216
// it came from and extract from the appropriate input element instead.
217
if (ConstantInt *Elt = dyn_cast<ConstantInt>(EI.getOperand(1))) {
218
unsigned SrcIdx = getShuffleMask(SVI)[Elt->getZExtValue()];
221
cast<VectorType>(SVI->getOperand(0)->getType())->getNumElements();
223
if (SrcIdx < LHSWidth)
224
Src = SVI->getOperand(0);
225
else if (SrcIdx < LHSWidth*2) {
227
Src = SVI->getOperand(1);
229
return ReplaceInstUsesWith(EI, UndefValue::get(EI.getType()));
231
return ExtractElementInst::Create(Src,
232
ConstantInt::get(Type::getInt32Ty(EI.getContext()),
236
// FIXME: Canonicalize extractelement(bitcast) -> bitcast(extractelement)
241
/// CollectSingleShuffleElements - If V is a shuffle of values that ONLY returns
242
/// elements from either LHS or RHS, return the shuffle mask and true.
243
/// Otherwise, return false.
244
static bool CollectSingleShuffleElements(Value *V, Value *LHS, Value *RHS,
245
std::vector<Constant*> &Mask) {
246
assert(V->getType() == LHS->getType() && V->getType() == RHS->getType() &&
247
"Invalid CollectSingleShuffleElements");
248
unsigned NumElts = cast<VectorType>(V->getType())->getNumElements();
250
if (isa<UndefValue>(V)) {
251
Mask.assign(NumElts, UndefValue::get(Type::getInt32Ty(V->getContext())));
256
for (unsigned i = 0; i != NumElts; ++i)
257
Mask.push_back(ConstantInt::get(Type::getInt32Ty(V->getContext()), i));
262
for (unsigned i = 0; i != NumElts; ++i)
263
Mask.push_back(ConstantInt::get(Type::getInt32Ty(V->getContext()),
268
if (InsertElementInst *IEI = dyn_cast<InsertElementInst>(V)) {
269
// If this is an insert of an extract from some other vector, include it.
270
Value *VecOp = IEI->getOperand(0);
271
Value *ScalarOp = IEI->getOperand(1);
272
Value *IdxOp = IEI->getOperand(2);
274
if (!isa<ConstantInt>(IdxOp))
276
unsigned InsertedIdx = cast<ConstantInt>(IdxOp)->getZExtValue();
278
if (isa<UndefValue>(ScalarOp)) { // inserting undef into vector.
279
// Okay, we can handle this if the vector we are insertinting into is
281
if (CollectSingleShuffleElements(VecOp, LHS, RHS, Mask)) {
282
// If so, update the mask to reflect the inserted undef.
283
Mask[InsertedIdx] = UndefValue::get(Type::getInt32Ty(V->getContext()));
286
} else if (ExtractElementInst *EI = dyn_cast<ExtractElementInst>(ScalarOp)){
287
if (isa<ConstantInt>(EI->getOperand(1)) &&
288
EI->getOperand(0)->getType() == V->getType()) {
289
unsigned ExtractedIdx =
290
cast<ConstantInt>(EI->getOperand(1))->getZExtValue();
292
// This must be extracting from either LHS or RHS.
293
if (EI->getOperand(0) == LHS || EI->getOperand(0) == RHS) {
294
// Okay, we can handle this if the vector we are insertinting into is
296
if (CollectSingleShuffleElements(VecOp, LHS, RHS, Mask)) {
297
// If so, update the mask to reflect the inserted value.
298
if (EI->getOperand(0) == LHS) {
299
Mask[InsertedIdx % NumElts] =
300
ConstantInt::get(Type::getInt32Ty(V->getContext()),
303
assert(EI->getOperand(0) == RHS);
304
Mask[InsertedIdx % NumElts] =
305
ConstantInt::get(Type::getInt32Ty(V->getContext()),
306
ExtractedIdx+NumElts);
315
// TODO: Handle shufflevector here!
320
/// CollectShuffleElements - We are building a shuffle of V, using RHS as the
321
/// RHS of the shuffle instruction, if it is not null. Return a shuffle mask
322
/// that computes V and the LHS value of the shuffle.
323
static Value *CollectShuffleElements(Value *V, std::vector<Constant*> &Mask,
325
assert(V->getType()->isVectorTy() &&
326
(RHS == 0 || V->getType() == RHS->getType()) &&
328
unsigned NumElts = cast<VectorType>(V->getType())->getNumElements();
330
if (isa<UndefValue>(V)) {
331
Mask.assign(NumElts, UndefValue::get(Type::getInt32Ty(V->getContext())));
333
} else if (isa<ConstantAggregateZero>(V)) {
334
Mask.assign(NumElts, ConstantInt::get(Type::getInt32Ty(V->getContext()),0));
336
} else if (InsertElementInst *IEI = dyn_cast<InsertElementInst>(V)) {
337
// If this is an insert of an extract from some other vector, include it.
338
Value *VecOp = IEI->getOperand(0);
339
Value *ScalarOp = IEI->getOperand(1);
340
Value *IdxOp = IEI->getOperand(2);
342
if (ExtractElementInst *EI = dyn_cast<ExtractElementInst>(ScalarOp)) {
343
if (isa<ConstantInt>(EI->getOperand(1)) && isa<ConstantInt>(IdxOp) &&
344
EI->getOperand(0)->getType() == V->getType()) {
345
unsigned ExtractedIdx =
346
cast<ConstantInt>(EI->getOperand(1))->getZExtValue();
347
unsigned InsertedIdx = cast<ConstantInt>(IdxOp)->getZExtValue();
349
// Either the extracted from or inserted into vector must be RHSVec,
350
// otherwise we'd end up with a shuffle of three inputs.
351
if (EI->getOperand(0) == RHS || RHS == 0) {
352
RHS = EI->getOperand(0);
353
Value *V = CollectShuffleElements(VecOp, Mask, RHS);
354
Mask[InsertedIdx % NumElts] =
355
ConstantInt::get(Type::getInt32Ty(V->getContext()),
356
NumElts+ExtractedIdx);
361
Value *V = CollectShuffleElements(EI->getOperand(0), Mask, RHS);
362
// Everything but the extracted element is replaced with the RHS.
363
for (unsigned i = 0; i != NumElts; ++i) {
364
if (i != InsertedIdx)
365
Mask[i] = ConstantInt::get(Type::getInt32Ty(V->getContext()),
371
// If this insertelement is a chain that comes from exactly these two
372
// vectors, return the vector and the effective shuffle.
373
if (CollectSingleShuffleElements(IEI, EI->getOperand(0), RHS, Mask))
374
return EI->getOperand(0);
378
// TODO: Handle shufflevector here!
380
// Otherwise, can't do anything fancy. Return an identity vector.
381
for (unsigned i = 0; i != NumElts; ++i)
382
Mask.push_back(ConstantInt::get(Type::getInt32Ty(V->getContext()), i));
386
Instruction *InstCombiner::visitInsertElementInst(InsertElementInst &IE) {
387
Value *VecOp = IE.getOperand(0);
388
Value *ScalarOp = IE.getOperand(1);
389
Value *IdxOp = IE.getOperand(2);
391
// Inserting an undef or into an undefined place, remove this.
392
if (isa<UndefValue>(ScalarOp) || isa<UndefValue>(IdxOp))
393
ReplaceInstUsesWith(IE, VecOp);
395
// If the inserted element was extracted from some other vector, and if the
396
// indexes are constant, try to turn this into a shufflevector operation.
397
if (ExtractElementInst *EI = dyn_cast<ExtractElementInst>(ScalarOp)) {
398
if (isa<ConstantInt>(EI->getOperand(1)) && isa<ConstantInt>(IdxOp) &&
399
EI->getOperand(0)->getType() == IE.getType()) {
400
unsigned NumVectorElts = IE.getType()->getNumElements();
401
unsigned ExtractedIdx =
402
cast<ConstantInt>(EI->getOperand(1))->getZExtValue();
403
unsigned InsertedIdx = cast<ConstantInt>(IdxOp)->getZExtValue();
405
if (ExtractedIdx >= NumVectorElts) // Out of range extract.
406
return ReplaceInstUsesWith(IE, VecOp);
408
if (InsertedIdx >= NumVectorElts) // Out of range insert.
409
return ReplaceInstUsesWith(IE, UndefValue::get(IE.getType()));
411
// If we are extracting a value from a vector, then inserting it right
412
// back into the same place, just use the input vector.
413
if (EI->getOperand(0) == VecOp && ExtractedIdx == InsertedIdx)
414
return ReplaceInstUsesWith(IE, VecOp);
416
// If this insertelement isn't used by some other insertelement, turn it
417
// (and any insertelements it points to), into one big shuffle.
418
if (!IE.hasOneUse() || !isa<InsertElementInst>(IE.use_back())) {
419
std::vector<Constant*> Mask;
421
Value *LHS = CollectShuffleElements(&IE, Mask, RHS);
422
if (RHS == 0) RHS = UndefValue::get(LHS->getType());
423
// We now have a shuffle of LHS, RHS, Mask.
424
return new ShuffleVectorInst(LHS, RHS,
425
ConstantVector::get(Mask));
430
unsigned VWidth = cast<VectorType>(VecOp->getType())->getNumElements();
431
APInt UndefElts(VWidth, 0);
432
APInt AllOnesEltMask(APInt::getAllOnesValue(VWidth));
433
if (SimplifyDemandedVectorElts(&IE, AllOnesEltMask, UndefElts))
440
Instruction *InstCombiner::visitShuffleVectorInst(ShuffleVectorInst &SVI) {
441
Value *LHS = SVI.getOperand(0);
442
Value *RHS = SVI.getOperand(1);
443
std::vector<unsigned> Mask = getShuffleMask(&SVI);
445
bool MadeChange = false;
447
// Undefined shuffle mask -> undefined value.
448
if (isa<UndefValue>(SVI.getOperand(2)))
449
return ReplaceInstUsesWith(SVI, UndefValue::get(SVI.getType()));
451
unsigned VWidth = cast<VectorType>(SVI.getType())->getNumElements();
453
if (VWidth != cast<VectorType>(LHS->getType())->getNumElements())
456
APInt UndefElts(VWidth, 0);
457
APInt AllOnesEltMask(APInt::getAllOnesValue(VWidth));
458
if (SimplifyDemandedVectorElts(&SVI, AllOnesEltMask, UndefElts)) {
459
LHS = SVI.getOperand(0);
460
RHS = SVI.getOperand(1);
464
// Canonicalize shuffle(x ,x,mask) -> shuffle(x, undef,mask')
465
// Canonicalize shuffle(undef,x,mask) -> shuffle(x, undef,mask').
466
if (LHS == RHS || isa<UndefValue>(LHS)) {
467
if (isa<UndefValue>(LHS) && LHS == RHS) {
468
// shuffle(undef,undef,mask) -> undef.
469
return ReplaceInstUsesWith(SVI, LHS);
472
// Remap any references to RHS to use LHS.
473
std::vector<Constant*> Elts;
474
for (unsigned i = 0, e = Mask.size(); i != e; ++i) {
476
Elts.push_back(UndefValue::get(Type::getInt32Ty(SVI.getContext())));
478
if ((Mask[i] >= e && isa<UndefValue>(RHS)) ||
479
(Mask[i] < e && isa<UndefValue>(LHS))) {
480
Mask[i] = 2*e; // Turn into undef.
481
Elts.push_back(UndefValue::get(Type::getInt32Ty(SVI.getContext())));
483
Mask[i] = Mask[i] % e; // Force to LHS.
484
Elts.push_back(ConstantInt::get(Type::getInt32Ty(SVI.getContext()),
489
SVI.setOperand(0, SVI.getOperand(1));
490
SVI.setOperand(1, UndefValue::get(RHS->getType()));
491
SVI.setOperand(2, ConstantVector::get(Elts));
492
LHS = SVI.getOperand(0);
493
RHS = SVI.getOperand(1);
497
// Analyze the shuffle, are the LHS or RHS and identity shuffles?
498
bool isLHSID = true, isRHSID = true;
500
for (unsigned i = 0, e = Mask.size(); i != e; ++i) {
501
if (Mask[i] >= e*2) continue; // Ignore undef values.
502
// Is this an identity shuffle of the LHS value?
503
isLHSID &= (Mask[i] == i);
505
// Is this an identity shuffle of the RHS value?
506
isRHSID &= (Mask[i]-e == i);
509
// Eliminate identity shuffles.
510
if (isLHSID) return ReplaceInstUsesWith(SVI, LHS);
511
if (isRHSID) return ReplaceInstUsesWith(SVI, RHS);
513
// If the LHS is a shufflevector itself, see if we can combine it with this
514
// one without producing an unusual shuffle. Here we are really conservative:
515
// we are absolutely afraid of producing a shuffle mask not in the input
516
// program, because the code gen may not be smart enough to turn a merged
517
// shuffle into two specific shuffles: it may produce worse code. As such,
518
// we only merge two shuffles if the result is one of the two input shuffle
519
// masks. In this case, merging the shuffles just removes one instruction,
520
// which we know is safe. This is good for things like turning:
521
// (splat(splat)) -> splat.
522
if (ShuffleVectorInst *LHSSVI = dyn_cast<ShuffleVectorInst>(LHS)) {
523
if (isa<UndefValue>(RHS)) {
524
std::vector<unsigned> LHSMask = getShuffleMask(LHSSVI);
526
if (LHSMask.size() == Mask.size()) {
527
std::vector<unsigned> NewMask;
528
for (unsigned i = 0, e = Mask.size(); i != e; ++i)
530
NewMask.push_back(2*e);
532
NewMask.push_back(LHSMask[Mask[i]]);
534
// If the result mask is equal to the src shuffle or this
535
// shuffle mask, do the replacement.
536
if (NewMask == LHSMask || NewMask == Mask) {
537
unsigned LHSInNElts =
538
cast<VectorType>(LHSSVI->getOperand(0)->getType())->
540
std::vector<Constant*> Elts;
541
for (unsigned i = 0, e = NewMask.size(); i != e; ++i) {
542
if (NewMask[i] >= LHSInNElts*2) {
543
Elts.push_back(UndefValue::get(
544
Type::getInt32Ty(SVI.getContext())));
546
Elts.push_back(ConstantInt::get(
547
Type::getInt32Ty(SVI.getContext()),
551
return new ShuffleVectorInst(LHSSVI->getOperand(0),
552
LHSSVI->getOperand(1),
553
ConstantVector::get(Elts));
559
return MadeChange ? &SVI : 0;