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(isa<VectorType>(V->getType()) && "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, 1 << IndexVal);
166 if (Value *V = SimplifyDemandedVectorElts(EI.getOperand(0),
167 DemandedMask, UndefElts)) {
173 if (Value *Elt = FindScalarElement(EI.getOperand(0), IndexVal))
174 return ReplaceInstUsesWith(EI, Elt);
176 // If the this extractelement is directly using a bitcast from a vector of
177 // the same number of elements, see if we can find the source element from
178 // it. In this case, we will end up needing to bitcast the scalars.
179 if (BitCastInst *BCI = dyn_cast<BitCastInst>(EI.getOperand(0))) {
180 if (const VectorType *VT =
181 dyn_cast<VectorType>(BCI->getOperand(0)->getType()))
182 if (VT->getNumElements() == VectorWidth)
183 if (Value *Elt = FindScalarElement(BCI->getOperand(0), IndexVal))
184 return new BitCastInst(Elt, EI.getType());
188 if (Instruction *I = dyn_cast<Instruction>(EI.getOperand(0))) {
189 // Push extractelement into predecessor operation if legal and
190 // profitable to do so
191 if (BinaryOperator *BO = dyn_cast<BinaryOperator>(I)) {
192 if (I->hasOneUse() &&
193 CheapToScalarize(BO, isa<ConstantInt>(EI.getOperand(1)))) {
195 Builder->CreateExtractElement(BO->getOperand(0), EI.getOperand(1),
196 EI.getName()+".lhs");
198 Builder->CreateExtractElement(BO->getOperand(1), EI.getOperand(1),
199 EI.getName()+".rhs");
200 return BinaryOperator::Create(BO->getOpcode(), newEI0, newEI1);
202 } else if (InsertElementInst *IE = dyn_cast<InsertElementInst>(I)) {
203 // Extracting the inserted element?
204 if (IE->getOperand(2) == EI.getOperand(1))
205 return ReplaceInstUsesWith(EI, IE->getOperand(1));
206 // If the inserted and extracted elements are constants, they must not
207 // be the same value, extract from the pre-inserted value instead.
208 if (isa<Constant>(IE->getOperand(2)) && isa<Constant>(EI.getOperand(1))) {
209 Worklist.AddValue(EI.getOperand(0));
210 EI.setOperand(0, IE->getOperand(0));
213 } else if (ShuffleVectorInst *SVI = dyn_cast<ShuffleVectorInst>(I)) {
214 // If this is extracting an element from a shufflevector, figure out where
215 // it came from and extract from the appropriate input element instead.
216 if (ConstantInt *Elt = dyn_cast<ConstantInt>(EI.getOperand(1))) {
217 unsigned SrcIdx = getShuffleMask(SVI)[Elt->getZExtValue()];
220 cast<VectorType>(SVI->getOperand(0)->getType())->getNumElements();
222 if (SrcIdx < LHSWidth)
223 Src = SVI->getOperand(0);
224 else if (SrcIdx < LHSWidth*2) {
226 Src = SVI->getOperand(1);
228 return ReplaceInstUsesWith(EI, UndefValue::get(EI.getType()));
230 return ExtractElementInst::Create(Src,
231 ConstantInt::get(Type::getInt32Ty(EI.getContext()),
235 // FIXME: Canonicalize extractelement(bitcast) -> bitcast(extractelement)
240 /// CollectSingleShuffleElements - If V is a shuffle of values that ONLY returns
241 /// elements from either LHS or RHS, return the shuffle mask and true.
242 /// Otherwise, return false.
243 static bool CollectSingleShuffleElements(Value *V, Value *LHS, Value *RHS,
244 std::vector<Constant*> &Mask) {
245 assert(V->getType() == LHS->getType() && V->getType() == RHS->getType() &&
246 "Invalid CollectSingleShuffleElements");
247 unsigned NumElts = cast<VectorType>(V->getType())->getNumElements();
249 if (isa<UndefValue>(V)) {
250 Mask.assign(NumElts, UndefValue::get(Type::getInt32Ty(V->getContext())));
255 for (unsigned i = 0; i != NumElts; ++i)
256 Mask.push_back(ConstantInt::get(Type::getInt32Ty(V->getContext()), i));
261 for (unsigned i = 0; i != NumElts; ++i)
262 Mask.push_back(ConstantInt::get(Type::getInt32Ty(V->getContext()),
267 if (InsertElementInst *IEI = dyn_cast<InsertElementInst>(V)) {
268 // If this is an insert of an extract from some other vector, include it.
269 Value *VecOp = IEI->getOperand(0);
270 Value *ScalarOp = IEI->getOperand(1);
271 Value *IdxOp = IEI->getOperand(2);
273 if (!isa<ConstantInt>(IdxOp))
275 unsigned InsertedIdx = cast<ConstantInt>(IdxOp)->getZExtValue();
277 if (isa<UndefValue>(ScalarOp)) { // inserting undef into vector.
278 // Okay, we can handle this if the vector we are insertinting into is
280 if (CollectSingleShuffleElements(VecOp, LHS, RHS, Mask)) {
281 // If so, update the mask to reflect the inserted undef.
282 Mask[InsertedIdx] = UndefValue::get(Type::getInt32Ty(V->getContext()));
285 } else if (ExtractElementInst *EI = dyn_cast<ExtractElementInst>(ScalarOp)){
286 if (isa<ConstantInt>(EI->getOperand(1)) &&
287 EI->getOperand(0)->getType() == V->getType()) {
288 unsigned ExtractedIdx =
289 cast<ConstantInt>(EI->getOperand(1))->getZExtValue();
291 // This must be extracting from either LHS or RHS.
292 if (EI->getOperand(0) == LHS || EI->getOperand(0) == RHS) {
293 // Okay, we can handle this if the vector we are insertinting into is
295 if (CollectSingleShuffleElements(VecOp, LHS, RHS, Mask)) {
296 // If so, update the mask to reflect the inserted value.
297 if (EI->getOperand(0) == LHS) {
298 Mask[InsertedIdx % NumElts] =
299 ConstantInt::get(Type::getInt32Ty(V->getContext()),
302 assert(EI->getOperand(0) == RHS);
303 Mask[InsertedIdx % NumElts] =
304 ConstantInt::get(Type::getInt32Ty(V->getContext()),
305 ExtractedIdx+NumElts);
314 // TODO: Handle shufflevector here!
319 /// CollectShuffleElements - We are building a shuffle of V, using RHS as the
320 /// RHS of the shuffle instruction, if it is not null. Return a shuffle mask
321 /// that computes V and the LHS value of the shuffle.
322 static Value *CollectShuffleElements(Value *V, std::vector<Constant*> &Mask,
324 assert(isa<VectorType>(V->getType()) &&
325 (RHS == 0 || V->getType() == RHS->getType()) &&
327 unsigned NumElts = cast<VectorType>(V->getType())->getNumElements();
329 if (isa<UndefValue>(V)) {
330 Mask.assign(NumElts, UndefValue::get(Type::getInt32Ty(V->getContext())));
332 } else if (isa<ConstantAggregateZero>(V)) {
333 Mask.assign(NumElts, ConstantInt::get(Type::getInt32Ty(V->getContext()),0));
335 } else if (InsertElementInst *IEI = dyn_cast<InsertElementInst>(V)) {
336 // If this is an insert of an extract from some other vector, include it.
337 Value *VecOp = IEI->getOperand(0);
338 Value *ScalarOp = IEI->getOperand(1);
339 Value *IdxOp = IEI->getOperand(2);
341 if (ExtractElementInst *EI = dyn_cast<ExtractElementInst>(ScalarOp)) {
342 if (isa<ConstantInt>(EI->getOperand(1)) && isa<ConstantInt>(IdxOp) &&
343 EI->getOperand(0)->getType() == V->getType()) {
344 unsigned ExtractedIdx =
345 cast<ConstantInt>(EI->getOperand(1))->getZExtValue();
346 unsigned InsertedIdx = cast<ConstantInt>(IdxOp)->getZExtValue();
348 // Either the extracted from or inserted into vector must be RHSVec,
349 // otherwise we'd end up with a shuffle of three inputs.
350 if (EI->getOperand(0) == RHS || RHS == 0) {
351 RHS = EI->getOperand(0);
352 Value *V = CollectShuffleElements(VecOp, Mask, RHS);
353 Mask[InsertedIdx % NumElts] =
354 ConstantInt::get(Type::getInt32Ty(V->getContext()),
355 NumElts+ExtractedIdx);
360 Value *V = CollectShuffleElements(EI->getOperand(0), Mask, RHS);
361 // Everything but the extracted element is replaced with the RHS.
362 for (unsigned i = 0; i != NumElts; ++i) {
363 if (i != InsertedIdx)
364 Mask[i] = ConstantInt::get(Type::getInt32Ty(V->getContext()),
370 // If this insertelement is a chain that comes from exactly these two
371 // vectors, return the vector and the effective shuffle.
372 if (CollectSingleShuffleElements(IEI, EI->getOperand(0), RHS, Mask))
373 return EI->getOperand(0);
377 // TODO: Handle shufflevector here!
379 // Otherwise, can't do anything fancy. Return an identity vector.
380 for (unsigned i = 0; i != NumElts; ++i)
381 Mask.push_back(ConstantInt::get(Type::getInt32Ty(V->getContext()), i));
385 Instruction *InstCombiner::visitInsertElementInst(InsertElementInst &IE) {
386 Value *VecOp = IE.getOperand(0);
387 Value *ScalarOp = IE.getOperand(1);
388 Value *IdxOp = IE.getOperand(2);
390 // Inserting an undef or into an undefined place, remove this.
391 if (isa<UndefValue>(ScalarOp) || isa<UndefValue>(IdxOp))
392 ReplaceInstUsesWith(IE, VecOp);
394 // If the inserted element was extracted from some other vector, and if the
395 // indexes are constant, try to turn this into a shufflevector operation.
396 if (ExtractElementInst *EI = dyn_cast<ExtractElementInst>(ScalarOp)) {
397 if (isa<ConstantInt>(EI->getOperand(1)) && isa<ConstantInt>(IdxOp) &&
398 EI->getOperand(0)->getType() == IE.getType()) {
399 unsigned NumVectorElts = IE.getType()->getNumElements();
400 unsigned ExtractedIdx =
401 cast<ConstantInt>(EI->getOperand(1))->getZExtValue();
402 unsigned InsertedIdx = cast<ConstantInt>(IdxOp)->getZExtValue();
404 if (ExtractedIdx >= NumVectorElts) // Out of range extract.
405 return ReplaceInstUsesWith(IE, VecOp);
407 if (InsertedIdx >= NumVectorElts) // Out of range insert.
408 return ReplaceInstUsesWith(IE, UndefValue::get(IE.getType()));
410 // If we are extracting a value from a vector, then inserting it right
411 // back into the same place, just use the input vector.
412 if (EI->getOperand(0) == VecOp && ExtractedIdx == InsertedIdx)
413 return ReplaceInstUsesWith(IE, VecOp);
415 // If this insertelement isn't used by some other insertelement, turn it
416 // (and any insertelements it points to), into one big shuffle.
417 if (!IE.hasOneUse() || !isa<InsertElementInst>(IE.use_back())) {
418 std::vector<Constant*> Mask;
420 Value *LHS = CollectShuffleElements(&IE, Mask, RHS);
421 if (RHS == 0) RHS = UndefValue::get(LHS->getType());
422 // We now have a shuffle of LHS, RHS, Mask.
423 return new ShuffleVectorInst(LHS, RHS,
424 ConstantVector::get(Mask));
429 unsigned VWidth = cast<VectorType>(VecOp->getType())->getNumElements();
430 APInt UndefElts(VWidth, 0);
431 APInt AllOnesEltMask(APInt::getAllOnesValue(VWidth));
432 if (SimplifyDemandedVectorElts(&IE, AllOnesEltMask, UndefElts))
439 Instruction *InstCombiner::visitShuffleVectorInst(ShuffleVectorInst &SVI) {
440 Value *LHS = SVI.getOperand(0);
441 Value *RHS = SVI.getOperand(1);
442 std::vector<unsigned> Mask = getShuffleMask(&SVI);
444 bool MadeChange = false;
446 // Undefined shuffle mask -> undefined value.
447 if (isa<UndefValue>(SVI.getOperand(2)))
448 return ReplaceInstUsesWith(SVI, UndefValue::get(SVI.getType()));
450 unsigned VWidth = cast<VectorType>(SVI.getType())->getNumElements();
452 if (VWidth != cast<VectorType>(LHS->getType())->getNumElements())
455 APInt UndefElts(VWidth, 0);
456 APInt AllOnesEltMask(APInt::getAllOnesValue(VWidth));
457 if (SimplifyDemandedVectorElts(&SVI, AllOnesEltMask, UndefElts)) {
458 LHS = SVI.getOperand(0);
459 RHS = SVI.getOperand(1);
463 // Canonicalize shuffle(x ,x,mask) -> shuffle(x, undef,mask')
464 // Canonicalize shuffle(undef,x,mask) -> shuffle(x, undef,mask').
465 if (LHS == RHS || isa<UndefValue>(LHS)) {
466 if (isa<UndefValue>(LHS) && LHS == RHS) {
467 // shuffle(undef,undef,mask) -> undef.
468 return ReplaceInstUsesWith(SVI, LHS);
471 // Remap any references to RHS to use LHS.
472 std::vector<Constant*> Elts;
473 for (unsigned i = 0, e = Mask.size(); i != e; ++i) {
475 Elts.push_back(UndefValue::get(Type::getInt32Ty(SVI.getContext())));
477 if ((Mask[i] >= e && isa<UndefValue>(RHS)) ||
478 (Mask[i] < e && isa<UndefValue>(LHS))) {
479 Mask[i] = 2*e; // Turn into undef.
480 Elts.push_back(UndefValue::get(Type::getInt32Ty(SVI.getContext())));
482 Mask[i] = Mask[i] % e; // Force to LHS.
483 Elts.push_back(ConstantInt::get(Type::getInt32Ty(SVI.getContext()),
488 SVI.setOperand(0, SVI.getOperand(1));
489 SVI.setOperand(1, UndefValue::get(RHS->getType()));
490 SVI.setOperand(2, ConstantVector::get(Elts));
491 LHS = SVI.getOperand(0);
492 RHS = SVI.getOperand(1);
496 // Analyze the shuffle, are the LHS or RHS and identity shuffles?
497 bool isLHSID = true, isRHSID = true;
499 for (unsigned i = 0, e = Mask.size(); i != e; ++i) {
500 if (Mask[i] >= e*2) continue; // Ignore undef values.
501 // Is this an identity shuffle of the LHS value?
502 isLHSID &= (Mask[i] == i);
504 // Is this an identity shuffle of the RHS value?
505 isRHSID &= (Mask[i]-e == i);
508 // Eliminate identity shuffles.
509 if (isLHSID) return ReplaceInstUsesWith(SVI, LHS);
510 if (isRHSID) return ReplaceInstUsesWith(SVI, RHS);
512 // If the LHS is a shufflevector itself, see if we can combine it with this
513 // one without producing an unusual shuffle. Here we are really conservative:
514 // we are absolutely afraid of producing a shuffle mask not in the input
515 // program, because the code gen may not be smart enough to turn a merged
516 // shuffle into two specific shuffles: it may produce worse code. As such,
517 // we only merge two shuffles if the result is one of the two input shuffle
518 // masks. In this case, merging the shuffles just removes one instruction,
519 // which we know is safe. This is good for things like turning:
520 // (splat(splat)) -> splat.
521 if (ShuffleVectorInst *LHSSVI = dyn_cast<ShuffleVectorInst>(LHS)) {
522 if (isa<UndefValue>(RHS)) {
523 std::vector<unsigned> LHSMask = getShuffleMask(LHSSVI);
525 if (LHSMask.size() == Mask.size()) {
526 std::vector<unsigned> NewMask;
527 for (unsigned i = 0, e = Mask.size(); i != e; ++i)
529 NewMask.push_back(2*e);
531 NewMask.push_back(LHSMask[Mask[i]]);
533 // If the result mask is equal to the src shuffle or this
534 // shuffle mask, do the replacement.
535 if (NewMask == LHSMask || NewMask == Mask) {
536 unsigned LHSInNElts =
537 cast<VectorType>(LHSSVI->getOperand(0)->getType())->
539 std::vector<Constant*> Elts;
540 for (unsigned i = 0, e = NewMask.size(); i != e; ++i) {
541 if (NewMask[i] >= LHSInNElts*2) {
542 Elts.push_back(UndefValue::get(
543 Type::getInt32Ty(SVI.getContext())));
545 Elts.push_back(ConstantInt::get(
546 Type::getInt32Ty(SVI.getContext()),
550 return new ShuffleVectorInst(LHSSVI->getOperand(0),
551 LHSSVI->getOperand(1),
552 ConstantVector::get(Elts));
558 return MadeChange ? &SVI : 0;