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;