• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 //===- InstCombineSimplifyDemanded.cpp ------------------------------------===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file contains logic for simplifying instructions based on information
11 // about how they are used.
12 //
13 //===----------------------------------------------------------------------===//
14 
15 
16 #include "InstCombine.h"
17 #include "llvm/IR/DataLayout.h"
18 #include "llvm/IR/IntrinsicInst.h"
19 #include "llvm/Support/PatternMatch.h"
20 
21 using namespace llvm;
22 using namespace llvm::PatternMatch;
23 
24 /// ShrinkDemandedConstant - Check to see if the specified operand of the
25 /// specified instruction is a constant integer.  If so, check to see if there
26 /// are any bits set in the constant that are not demanded.  If so, shrink the
27 /// constant and return true.
ShrinkDemandedConstant(Instruction * I,unsigned OpNo,APInt Demanded)28 static bool ShrinkDemandedConstant(Instruction *I, unsigned OpNo,
29                                    APInt Demanded) {
30   assert(I && "No instruction?");
31   assert(OpNo < I->getNumOperands() && "Operand index too large");
32 
33   // If the operand is not a constant integer, nothing to do.
34   ConstantInt *OpC = dyn_cast<ConstantInt>(I->getOperand(OpNo));
35   if (!OpC) return false;
36 
37   // If there are no bits set that aren't demanded, nothing to do.
38   Demanded = Demanded.zextOrTrunc(OpC->getValue().getBitWidth());
39   if ((~Demanded & OpC->getValue()) == 0)
40     return false;
41 
42   // This instruction is producing bits that are not demanded. Shrink the RHS.
43   Demanded &= OpC->getValue();
44   I->setOperand(OpNo, ConstantInt::get(OpC->getType(), Demanded));
45   return true;
46 }
47 
48 
49 
50 /// SimplifyDemandedInstructionBits - Inst is an integer instruction that
51 /// SimplifyDemandedBits knows about.  See if the instruction has any
52 /// properties that allow us to simplify its operands.
SimplifyDemandedInstructionBits(Instruction & Inst)53 bool InstCombiner::SimplifyDemandedInstructionBits(Instruction &Inst) {
54   unsigned BitWidth = Inst.getType()->getScalarSizeInBits();
55   APInt KnownZero(BitWidth, 0), KnownOne(BitWidth, 0);
56   APInt DemandedMask(APInt::getAllOnesValue(BitWidth));
57 
58   Value *V = SimplifyDemandedUseBits(&Inst, DemandedMask,
59                                      KnownZero, KnownOne, 0);
60   if (V == 0) return false;
61   if (V == &Inst) return true;
62   ReplaceInstUsesWith(Inst, V);
63   return true;
64 }
65 
66 /// SimplifyDemandedBits - This form of SimplifyDemandedBits simplifies the
67 /// specified instruction operand if possible, updating it in place.  It returns
68 /// true if it made any change and false otherwise.
SimplifyDemandedBits(Use & U,APInt DemandedMask,APInt & KnownZero,APInt & KnownOne,unsigned Depth)69 bool InstCombiner::SimplifyDemandedBits(Use &U, APInt DemandedMask,
70                                         APInt &KnownZero, APInt &KnownOne,
71                                         unsigned Depth) {
72   Value *NewVal = SimplifyDemandedUseBits(U.get(), DemandedMask,
73                                           KnownZero, KnownOne, Depth);
74   if (NewVal == 0) return false;
75   U = NewVal;
76   return true;
77 }
78 
79 
80 /// SimplifyDemandedUseBits - This function attempts to replace V with a simpler
81 /// value based on the demanded bits.  When this function is called, it is known
82 /// that only the bits set in DemandedMask of the result of V are ever used
83 /// downstream. Consequently, depending on the mask and V, it may be possible
84 /// to replace V with a constant or one of its operands. In such cases, this
85 /// function does the replacement and returns true. In all other cases, it
86 /// returns false after analyzing the expression and setting KnownOne and known
87 /// to be one in the expression.  KnownZero contains all the bits that are known
88 /// to be zero in the expression. These are provided to potentially allow the
89 /// caller (which might recursively be SimplifyDemandedBits itself) to simplify
90 /// the expression. KnownOne and KnownZero always follow the invariant that
91 /// KnownOne & KnownZero == 0. That is, a bit can't be both 1 and 0. Note that
92 /// the bits in KnownOne and KnownZero may only be accurate for those bits set
93 /// in DemandedMask. Note also that the bitwidth of V, DemandedMask, KnownZero
94 /// and KnownOne must all be the same.
95 ///
96 /// This returns null if it did not change anything and it permits no
97 /// simplification.  This returns V itself if it did some simplification of V's
98 /// operands based on the information about what bits are demanded. This returns
99 /// some other non-null value if it found out that V is equal to another value
100 /// in the context where the specified bits are demanded, but not for all users.
SimplifyDemandedUseBits(Value * V,APInt DemandedMask,APInt & KnownZero,APInt & KnownOne,unsigned Depth)101 Value *InstCombiner::SimplifyDemandedUseBits(Value *V, APInt DemandedMask,
102                                              APInt &KnownZero, APInt &KnownOne,
103                                              unsigned Depth) {
104   assert(V != 0 && "Null pointer of Value???");
105   assert(Depth <= 6 && "Limit Search Depth");
106   uint32_t BitWidth = DemandedMask.getBitWidth();
107   Type *VTy = V->getType();
108   assert((TD || !VTy->isPointerTy()) &&
109          "SimplifyDemandedBits needs to know bit widths!");
110   assert((!TD || TD->getTypeSizeInBits(VTy->getScalarType()) == BitWidth) &&
111          (!VTy->isIntOrIntVectorTy() ||
112           VTy->getScalarSizeInBits() == BitWidth) &&
113          KnownZero.getBitWidth() == BitWidth &&
114          KnownOne.getBitWidth() == BitWidth &&
115          "Value *V, DemandedMask, KnownZero and KnownOne "
116          "must have same BitWidth");
117   if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) {
118     // We know all of the bits for a constant!
119     KnownOne = CI->getValue() & DemandedMask;
120     KnownZero = ~KnownOne & DemandedMask;
121     return 0;
122   }
123   if (isa<ConstantPointerNull>(V)) {
124     // We know all of the bits for a constant!
125     KnownOne.clearAllBits();
126     KnownZero = DemandedMask;
127     return 0;
128   }
129 
130   KnownZero.clearAllBits();
131   KnownOne.clearAllBits();
132   if (DemandedMask == 0) {   // Not demanding any bits from V.
133     if (isa<UndefValue>(V))
134       return 0;
135     return UndefValue::get(VTy);
136   }
137 
138   if (Depth == 6)        // Limit search depth.
139     return 0;
140 
141   APInt LHSKnownZero(BitWidth, 0), LHSKnownOne(BitWidth, 0);
142   APInt RHSKnownZero(BitWidth, 0), RHSKnownOne(BitWidth, 0);
143 
144   Instruction *I = dyn_cast<Instruction>(V);
145   if (!I) {
146     ComputeMaskedBits(V, KnownZero, KnownOne, Depth);
147     return 0;        // Only analyze instructions.
148   }
149 
150   // If there are multiple uses of this value and we aren't at the root, then
151   // we can't do any simplifications of the operands, because DemandedMask
152   // only reflects the bits demanded by *one* of the users.
153   if (Depth != 0 && !I->hasOneUse()) {
154     // Despite the fact that we can't simplify this instruction in all User's
155     // context, we can at least compute the knownzero/knownone bits, and we can
156     // do simplifications that apply to *just* the one user if we know that
157     // this instruction has a simpler value in that context.
158     if (I->getOpcode() == Instruction::And) {
159       // If either the LHS or the RHS are Zero, the result is zero.
160       ComputeMaskedBits(I->getOperand(1), RHSKnownZero, RHSKnownOne, Depth+1);
161       ComputeMaskedBits(I->getOperand(0), LHSKnownZero, LHSKnownOne, Depth+1);
162 
163       // If all of the demanded bits are known 1 on one side, return the other.
164       // These bits cannot contribute to the result of the 'and' in this
165       // context.
166       if ((DemandedMask & ~LHSKnownZero & RHSKnownOne) ==
167           (DemandedMask & ~LHSKnownZero))
168         return I->getOperand(0);
169       if ((DemandedMask & ~RHSKnownZero & LHSKnownOne) ==
170           (DemandedMask & ~RHSKnownZero))
171         return I->getOperand(1);
172 
173       // If all of the demanded bits in the inputs are known zeros, return zero.
174       if ((DemandedMask & (RHSKnownZero|LHSKnownZero)) == DemandedMask)
175         return Constant::getNullValue(VTy);
176 
177     } else if (I->getOpcode() == Instruction::Or) {
178       // We can simplify (X|Y) -> X or Y in the user's context if we know that
179       // only bits from X or Y are demanded.
180 
181       // If either the LHS or the RHS are One, the result is One.
182       ComputeMaskedBits(I->getOperand(1), RHSKnownZero, RHSKnownOne, Depth+1);
183       ComputeMaskedBits(I->getOperand(0), LHSKnownZero, LHSKnownOne, Depth+1);
184 
185       // If all of the demanded bits are known zero on one side, return the
186       // other.  These bits cannot contribute to the result of the 'or' in this
187       // context.
188       if ((DemandedMask & ~LHSKnownOne & RHSKnownZero) ==
189           (DemandedMask & ~LHSKnownOne))
190         return I->getOperand(0);
191       if ((DemandedMask & ~RHSKnownOne & LHSKnownZero) ==
192           (DemandedMask & ~RHSKnownOne))
193         return I->getOperand(1);
194 
195       // If all of the potentially set bits on one side are known to be set on
196       // the other side, just use the 'other' side.
197       if ((DemandedMask & (~RHSKnownZero) & LHSKnownOne) ==
198           (DemandedMask & (~RHSKnownZero)))
199         return I->getOperand(0);
200       if ((DemandedMask & (~LHSKnownZero) & RHSKnownOne) ==
201           (DemandedMask & (~LHSKnownZero)))
202         return I->getOperand(1);
203     } else if (I->getOpcode() == Instruction::Xor) {
204       // We can simplify (X^Y) -> X or Y in the user's context if we know that
205       // only bits from X or Y are demanded.
206 
207       ComputeMaskedBits(I->getOperand(1), RHSKnownZero, RHSKnownOne, Depth+1);
208       ComputeMaskedBits(I->getOperand(0), LHSKnownZero, LHSKnownOne, Depth+1);
209 
210       // If all of the demanded bits are known zero on one side, return the
211       // other.
212       if ((DemandedMask & RHSKnownZero) == DemandedMask)
213         return I->getOperand(0);
214       if ((DemandedMask & LHSKnownZero) == DemandedMask)
215         return I->getOperand(1);
216     }
217 
218     // Compute the KnownZero/KnownOne bits to simplify things downstream.
219     ComputeMaskedBits(I, KnownZero, KnownOne, Depth);
220     return 0;
221   }
222 
223   // If this is the root being simplified, allow it to have multiple uses,
224   // just set the DemandedMask to all bits so that we can try to simplify the
225   // operands.  This allows visitTruncInst (for example) to simplify the
226   // operand of a trunc without duplicating all the logic below.
227   if (Depth == 0 && !V->hasOneUse())
228     DemandedMask = APInt::getAllOnesValue(BitWidth);
229 
230   switch (I->getOpcode()) {
231   default:
232     ComputeMaskedBits(I, KnownZero, KnownOne, Depth);
233     break;
234   case Instruction::And:
235     // If either the LHS or the RHS are Zero, the result is zero.
236     if (SimplifyDemandedBits(I->getOperandUse(1), DemandedMask,
237                              RHSKnownZero, RHSKnownOne, Depth+1) ||
238         SimplifyDemandedBits(I->getOperandUse(0), DemandedMask & ~RHSKnownZero,
239                              LHSKnownZero, LHSKnownOne, Depth+1))
240       return I;
241     assert(!(RHSKnownZero & RHSKnownOne) && "Bits known to be one AND zero?");
242     assert(!(LHSKnownZero & LHSKnownOne) && "Bits known to be one AND zero?");
243 
244     // If all of the demanded bits are known 1 on one side, return the other.
245     // These bits cannot contribute to the result of the 'and'.
246     if ((DemandedMask & ~LHSKnownZero & RHSKnownOne) ==
247         (DemandedMask & ~LHSKnownZero))
248       return I->getOperand(0);
249     if ((DemandedMask & ~RHSKnownZero & LHSKnownOne) ==
250         (DemandedMask & ~RHSKnownZero))
251       return I->getOperand(1);
252 
253     // If all of the demanded bits in the inputs are known zeros, return zero.
254     if ((DemandedMask & (RHSKnownZero|LHSKnownZero)) == DemandedMask)
255       return Constant::getNullValue(VTy);
256 
257     // If the RHS is a constant, see if we can simplify it.
258     if (ShrinkDemandedConstant(I, 1, DemandedMask & ~LHSKnownZero))
259       return I;
260 
261     // Output known-1 bits are only known if set in both the LHS & RHS.
262     KnownOne = RHSKnownOne & LHSKnownOne;
263     // Output known-0 are known to be clear if zero in either the LHS | RHS.
264     KnownZero = RHSKnownZero | LHSKnownZero;
265     break;
266   case Instruction::Or:
267     // If either the LHS or the RHS are One, the result is One.
268     if (SimplifyDemandedBits(I->getOperandUse(1), DemandedMask,
269                              RHSKnownZero, RHSKnownOne, Depth+1) ||
270         SimplifyDemandedBits(I->getOperandUse(0), DemandedMask & ~RHSKnownOne,
271                              LHSKnownZero, LHSKnownOne, Depth+1))
272       return I;
273     assert(!(RHSKnownZero & RHSKnownOne) && "Bits known to be one AND zero?");
274     assert(!(LHSKnownZero & LHSKnownOne) && "Bits known to be one AND zero?");
275 
276     // If all of the demanded bits are known zero on one side, return the other.
277     // These bits cannot contribute to the result of the 'or'.
278     if ((DemandedMask & ~LHSKnownOne & RHSKnownZero) ==
279         (DemandedMask & ~LHSKnownOne))
280       return I->getOperand(0);
281     if ((DemandedMask & ~RHSKnownOne & LHSKnownZero) ==
282         (DemandedMask & ~RHSKnownOne))
283       return I->getOperand(1);
284 
285     // If all of the potentially set bits on one side are known to be set on
286     // the other side, just use the 'other' side.
287     if ((DemandedMask & (~RHSKnownZero) & LHSKnownOne) ==
288         (DemandedMask & (~RHSKnownZero)))
289       return I->getOperand(0);
290     if ((DemandedMask & (~LHSKnownZero) & RHSKnownOne) ==
291         (DemandedMask & (~LHSKnownZero)))
292       return I->getOperand(1);
293 
294     // If the RHS is a constant, see if we can simplify it.
295     if (ShrinkDemandedConstant(I, 1, DemandedMask))
296       return I;
297 
298     // Output known-0 bits are only known if clear in both the LHS & RHS.
299     KnownZero = RHSKnownZero & LHSKnownZero;
300     // Output known-1 are known to be set if set in either the LHS | RHS.
301     KnownOne = RHSKnownOne | LHSKnownOne;
302     break;
303   case Instruction::Xor: {
304     if (SimplifyDemandedBits(I->getOperandUse(1), DemandedMask,
305                              RHSKnownZero, RHSKnownOne, Depth+1) ||
306         SimplifyDemandedBits(I->getOperandUse(0), DemandedMask,
307                              LHSKnownZero, LHSKnownOne, Depth+1))
308       return I;
309     assert(!(RHSKnownZero & RHSKnownOne) && "Bits known to be one AND zero?");
310     assert(!(LHSKnownZero & LHSKnownOne) && "Bits known to be one AND zero?");
311 
312     // If all of the demanded bits are known zero on one side, return the other.
313     // These bits cannot contribute to the result of the 'xor'.
314     if ((DemandedMask & RHSKnownZero) == DemandedMask)
315       return I->getOperand(0);
316     if ((DemandedMask & LHSKnownZero) == DemandedMask)
317       return I->getOperand(1);
318 
319     // If all of the demanded bits are known to be zero on one side or the
320     // other, turn this into an *inclusive* or.
321     //    e.g. (A & C1)^(B & C2) -> (A & C1)|(B & C2) iff C1&C2 == 0
322     if ((DemandedMask & ~RHSKnownZero & ~LHSKnownZero) == 0) {
323       Instruction *Or =
324         BinaryOperator::CreateOr(I->getOperand(0), I->getOperand(1),
325                                  I->getName());
326       return InsertNewInstWith(Or, *I);
327     }
328 
329     // If all of the demanded bits on one side are known, and all of the set
330     // bits on that side are also known to be set on the other side, turn this
331     // into an AND, as we know the bits will be cleared.
332     //    e.g. (X | C1) ^ C2 --> (X | C1) & ~C2 iff (C1&C2) == C2
333     if ((DemandedMask & (RHSKnownZero|RHSKnownOne)) == DemandedMask) {
334       // all known
335       if ((RHSKnownOne & LHSKnownOne) == RHSKnownOne) {
336         Constant *AndC = Constant::getIntegerValue(VTy,
337                                                    ~RHSKnownOne & DemandedMask);
338         Instruction *And = BinaryOperator::CreateAnd(I->getOperand(0), AndC);
339         return InsertNewInstWith(And, *I);
340       }
341     }
342 
343     // If the RHS is a constant, see if we can simplify it.
344     // FIXME: for XOR, we prefer to force bits to 1 if they will make a -1.
345     if (ShrinkDemandedConstant(I, 1, DemandedMask))
346       return I;
347 
348     // If our LHS is an 'and' and if it has one use, and if any of the bits we
349     // are flipping are known to be set, then the xor is just resetting those
350     // bits to zero.  We can just knock out bits from the 'and' and the 'xor',
351     // simplifying both of them.
352     if (Instruction *LHSInst = dyn_cast<Instruction>(I->getOperand(0)))
353       if (LHSInst->getOpcode() == Instruction::And && LHSInst->hasOneUse() &&
354           isa<ConstantInt>(I->getOperand(1)) &&
355           isa<ConstantInt>(LHSInst->getOperand(1)) &&
356           (LHSKnownOne & RHSKnownOne & DemandedMask) != 0) {
357         ConstantInt *AndRHS = cast<ConstantInt>(LHSInst->getOperand(1));
358         ConstantInt *XorRHS = cast<ConstantInt>(I->getOperand(1));
359         APInt NewMask = ~(LHSKnownOne & RHSKnownOne & DemandedMask);
360 
361         Constant *AndC =
362           ConstantInt::get(I->getType(), NewMask & AndRHS->getValue());
363         Instruction *NewAnd = BinaryOperator::CreateAnd(I->getOperand(0), AndC);
364         InsertNewInstWith(NewAnd, *I);
365 
366         Constant *XorC =
367           ConstantInt::get(I->getType(), NewMask & XorRHS->getValue());
368         Instruction *NewXor = BinaryOperator::CreateXor(NewAnd, XorC);
369         return InsertNewInstWith(NewXor, *I);
370       }
371 
372     // Output known-0 bits are known if clear or set in both the LHS & RHS.
373     KnownZero= (RHSKnownZero & LHSKnownZero) | (RHSKnownOne & LHSKnownOne);
374     // Output known-1 are known to be set if set in only one of the LHS, RHS.
375     KnownOne = (RHSKnownZero & LHSKnownOne) | (RHSKnownOne & LHSKnownZero);
376     break;
377   }
378   case Instruction::Select:
379     if (SimplifyDemandedBits(I->getOperandUse(2), DemandedMask,
380                              RHSKnownZero, RHSKnownOne, Depth+1) ||
381         SimplifyDemandedBits(I->getOperandUse(1), DemandedMask,
382                              LHSKnownZero, LHSKnownOne, Depth+1))
383       return I;
384     assert(!(RHSKnownZero & RHSKnownOne) && "Bits known to be one AND zero?");
385     assert(!(LHSKnownZero & LHSKnownOne) && "Bits known to be one AND zero?");
386 
387     // If the operands are constants, see if we can simplify them.
388     if (ShrinkDemandedConstant(I, 1, DemandedMask) ||
389         ShrinkDemandedConstant(I, 2, DemandedMask))
390       return I;
391 
392     // Only known if known in both the LHS and RHS.
393     KnownOne = RHSKnownOne & LHSKnownOne;
394     KnownZero = RHSKnownZero & LHSKnownZero;
395     break;
396   case Instruction::Trunc: {
397     unsigned truncBf = I->getOperand(0)->getType()->getScalarSizeInBits();
398     DemandedMask = DemandedMask.zext(truncBf);
399     KnownZero = KnownZero.zext(truncBf);
400     KnownOne = KnownOne.zext(truncBf);
401     if (SimplifyDemandedBits(I->getOperandUse(0), DemandedMask,
402                              KnownZero, KnownOne, Depth+1))
403       return I;
404     DemandedMask = DemandedMask.trunc(BitWidth);
405     KnownZero = KnownZero.trunc(BitWidth);
406     KnownOne = KnownOne.trunc(BitWidth);
407     assert(!(KnownZero & KnownOne) && "Bits known to be one AND zero?");
408     break;
409   }
410   case Instruction::BitCast:
411     if (!I->getOperand(0)->getType()->isIntOrIntVectorTy())
412       return 0;  // vector->int or fp->int?
413 
414     if (VectorType *DstVTy = dyn_cast<VectorType>(I->getType())) {
415       if (VectorType *SrcVTy =
416             dyn_cast<VectorType>(I->getOperand(0)->getType())) {
417         if (DstVTy->getNumElements() != SrcVTy->getNumElements())
418           // Don't touch a bitcast between vectors of different element counts.
419           return 0;
420       } else
421         // Don't touch a scalar-to-vector bitcast.
422         return 0;
423     } else if (I->getOperand(0)->getType()->isVectorTy())
424       // Don't touch a vector-to-scalar bitcast.
425       return 0;
426 
427     if (SimplifyDemandedBits(I->getOperandUse(0), DemandedMask,
428                              KnownZero, KnownOne, Depth+1))
429       return I;
430     assert(!(KnownZero & KnownOne) && "Bits known to be one AND zero?");
431     break;
432   case Instruction::ZExt: {
433     // Compute the bits in the result that are not present in the input.
434     unsigned SrcBitWidth =I->getOperand(0)->getType()->getScalarSizeInBits();
435 
436     DemandedMask = DemandedMask.trunc(SrcBitWidth);
437     KnownZero = KnownZero.trunc(SrcBitWidth);
438     KnownOne = KnownOne.trunc(SrcBitWidth);
439     if (SimplifyDemandedBits(I->getOperandUse(0), DemandedMask,
440                              KnownZero, KnownOne, Depth+1))
441       return I;
442     DemandedMask = DemandedMask.zext(BitWidth);
443     KnownZero = KnownZero.zext(BitWidth);
444     KnownOne = KnownOne.zext(BitWidth);
445     assert(!(KnownZero & KnownOne) && "Bits known to be one AND zero?");
446     // The top bits are known to be zero.
447     KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - SrcBitWidth);
448     break;
449   }
450   case Instruction::SExt: {
451     // Compute the bits in the result that are not present in the input.
452     unsigned SrcBitWidth =I->getOperand(0)->getType()->getScalarSizeInBits();
453 
454     APInt InputDemandedBits = DemandedMask &
455                               APInt::getLowBitsSet(BitWidth, SrcBitWidth);
456 
457     APInt NewBits(APInt::getHighBitsSet(BitWidth, BitWidth - SrcBitWidth));
458     // If any of the sign extended bits are demanded, we know that the sign
459     // bit is demanded.
460     if ((NewBits & DemandedMask) != 0)
461       InputDemandedBits.setBit(SrcBitWidth-1);
462 
463     InputDemandedBits = InputDemandedBits.trunc(SrcBitWidth);
464     KnownZero = KnownZero.trunc(SrcBitWidth);
465     KnownOne = KnownOne.trunc(SrcBitWidth);
466     if (SimplifyDemandedBits(I->getOperandUse(0), InputDemandedBits,
467                              KnownZero, KnownOne, Depth+1))
468       return I;
469     InputDemandedBits = InputDemandedBits.zext(BitWidth);
470     KnownZero = KnownZero.zext(BitWidth);
471     KnownOne = KnownOne.zext(BitWidth);
472     assert(!(KnownZero & KnownOne) && "Bits known to be one AND zero?");
473 
474     // If the sign bit of the input is known set or clear, then we know the
475     // top bits of the result.
476 
477     // If the input sign bit is known zero, or if the NewBits are not demanded
478     // convert this into a zero extension.
479     if (KnownZero[SrcBitWidth-1] || (NewBits & ~DemandedMask) == NewBits) {
480       // Convert to ZExt cast
481       CastInst *NewCast = new ZExtInst(I->getOperand(0), VTy, I->getName());
482       return InsertNewInstWith(NewCast, *I);
483     } else if (KnownOne[SrcBitWidth-1]) {    // Input sign bit known set
484       KnownOne |= NewBits;
485     }
486     break;
487   }
488   case Instruction::Add: {
489     // Figure out what the input bits are.  If the top bits of the and result
490     // are not demanded, then the add doesn't demand them from its input
491     // either.
492     unsigned NLZ = DemandedMask.countLeadingZeros();
493 
494     // If there is a constant on the RHS, there are a variety of xformations
495     // we can do.
496     if (ConstantInt *RHS = dyn_cast<ConstantInt>(I->getOperand(1))) {
497       // If null, this should be simplified elsewhere.  Some of the xforms here
498       // won't work if the RHS is zero.
499       if (RHS->isZero())
500         break;
501 
502       // If the top bit of the output is demanded, demand everything from the
503       // input.  Otherwise, we demand all the input bits except NLZ top bits.
504       APInt InDemandedBits(APInt::getLowBitsSet(BitWidth, BitWidth - NLZ));
505 
506       // Find information about known zero/one bits in the input.
507       if (SimplifyDemandedBits(I->getOperandUse(0), InDemandedBits,
508                                LHSKnownZero, LHSKnownOne, Depth+1))
509         return I;
510 
511       // If the RHS of the add has bits set that can't affect the input, reduce
512       // the constant.
513       if (ShrinkDemandedConstant(I, 1, InDemandedBits))
514         return I;
515 
516       // Avoid excess work.
517       if (LHSKnownZero == 0 && LHSKnownOne == 0)
518         break;
519 
520       // Turn it into OR if input bits are zero.
521       if ((LHSKnownZero & RHS->getValue()) == RHS->getValue()) {
522         Instruction *Or =
523           BinaryOperator::CreateOr(I->getOperand(0), I->getOperand(1),
524                                    I->getName());
525         return InsertNewInstWith(Or, *I);
526       }
527 
528       // We can say something about the output known-zero and known-one bits,
529       // depending on potential carries from the input constant and the
530       // unknowns.  For example if the LHS is known to have at most the 0x0F0F0
531       // bits set and the RHS constant is 0x01001, then we know we have a known
532       // one mask of 0x00001 and a known zero mask of 0xE0F0E.
533 
534       // To compute this, we first compute the potential carry bits.  These are
535       // the bits which may be modified.  I'm not aware of a better way to do
536       // this scan.
537       const APInt &RHSVal = RHS->getValue();
538       APInt CarryBits((~LHSKnownZero + RHSVal) ^ (~LHSKnownZero ^ RHSVal));
539 
540       // Now that we know which bits have carries, compute the known-1/0 sets.
541 
542       // Bits are known one if they are known zero in one operand and one in the
543       // other, and there is no input carry.
544       KnownOne = ((LHSKnownZero & RHSVal) |
545                   (LHSKnownOne & ~RHSVal)) & ~CarryBits;
546 
547       // Bits are known zero if they are known zero in both operands and there
548       // is no input carry.
549       KnownZero = LHSKnownZero & ~RHSVal & ~CarryBits;
550     } else {
551       // If the high-bits of this ADD are not demanded, then it does not demand
552       // the high bits of its LHS or RHS.
553       if (DemandedMask[BitWidth-1] == 0) {
554         // Right fill the mask of bits for this ADD to demand the most
555         // significant bit and all those below it.
556         APInt DemandedFromOps(APInt::getLowBitsSet(BitWidth, BitWidth-NLZ));
557         if (SimplifyDemandedBits(I->getOperandUse(0), DemandedFromOps,
558                                  LHSKnownZero, LHSKnownOne, Depth+1) ||
559             SimplifyDemandedBits(I->getOperandUse(1), DemandedFromOps,
560                                  LHSKnownZero, LHSKnownOne, Depth+1))
561           return I;
562       }
563     }
564     break;
565   }
566   case Instruction::Sub:
567     // If the high-bits of this SUB are not demanded, then it does not demand
568     // the high bits of its LHS or RHS.
569     if (DemandedMask[BitWidth-1] == 0) {
570       // Right fill the mask of bits for this SUB to demand the most
571       // significant bit and all those below it.
572       uint32_t NLZ = DemandedMask.countLeadingZeros();
573       APInt DemandedFromOps(APInt::getLowBitsSet(BitWidth, BitWidth-NLZ));
574       if (SimplifyDemandedBits(I->getOperandUse(0), DemandedFromOps,
575                                LHSKnownZero, LHSKnownOne, Depth+1) ||
576           SimplifyDemandedBits(I->getOperandUse(1), DemandedFromOps,
577                                LHSKnownZero, LHSKnownOne, Depth+1))
578         return I;
579     }
580 
581     // Otherwise just hand the sub off to ComputeMaskedBits to fill in
582     // the known zeros and ones.
583     ComputeMaskedBits(V, KnownZero, KnownOne, Depth);
584 
585     // Turn this into a xor if LHS is 2^n-1 and the remaining bits are known
586     // zero.
587     if (ConstantInt *C0 = dyn_cast<ConstantInt>(I->getOperand(0))) {
588       APInt I0 = C0->getValue();
589       if ((I0 + 1).isPowerOf2() && (I0 | KnownZero).isAllOnesValue()) {
590         Instruction *Xor = BinaryOperator::CreateXor(I->getOperand(1), C0);
591         return InsertNewInstWith(Xor, *I);
592       }
593     }
594     break;
595   case Instruction::Shl:
596     if (ConstantInt *SA = dyn_cast<ConstantInt>(I->getOperand(1))) {
597       {
598         Value *VarX; ConstantInt *C1;
599         if (match(I->getOperand(0), m_Shr(m_Value(VarX), m_ConstantInt(C1)))) {
600           Instruction *Shr = cast<Instruction>(I->getOperand(0));
601           Value *R = SimplifyShrShlDemandedBits(Shr, I, DemandedMask,
602                                                 KnownZero, KnownOne);
603           if (R)
604             return R;
605         }
606       }
607 
608       uint64_t ShiftAmt = SA->getLimitedValue(BitWidth-1);
609       APInt DemandedMaskIn(DemandedMask.lshr(ShiftAmt));
610 
611       // If the shift is NUW/NSW, then it does demand the high bits.
612       ShlOperator *IOp = cast<ShlOperator>(I);
613       if (IOp->hasNoSignedWrap())
614         DemandedMaskIn |= APInt::getHighBitsSet(BitWidth, ShiftAmt+1);
615       else if (IOp->hasNoUnsignedWrap())
616         DemandedMaskIn |= APInt::getHighBitsSet(BitWidth, ShiftAmt);
617 
618       if (SimplifyDemandedBits(I->getOperandUse(0), DemandedMaskIn,
619                                KnownZero, KnownOne, Depth+1))
620         return I;
621       assert(!(KnownZero & KnownOne) && "Bits known to be one AND zero?");
622       KnownZero <<= ShiftAmt;
623       KnownOne  <<= ShiftAmt;
624       // low bits known zero.
625       if (ShiftAmt)
626         KnownZero |= APInt::getLowBitsSet(BitWidth, ShiftAmt);
627     }
628     break;
629   case Instruction::LShr:
630     // For a logical shift right
631     if (ConstantInt *SA = dyn_cast<ConstantInt>(I->getOperand(1))) {
632       uint64_t ShiftAmt = SA->getLimitedValue(BitWidth-1);
633 
634       // Unsigned shift right.
635       APInt DemandedMaskIn(DemandedMask.shl(ShiftAmt));
636 
637       // If the shift is exact, then it does demand the low bits (and knows that
638       // they are zero).
639       if (cast<LShrOperator>(I)->isExact())
640         DemandedMaskIn |= APInt::getLowBitsSet(BitWidth, ShiftAmt);
641 
642       if (SimplifyDemandedBits(I->getOperandUse(0), DemandedMaskIn,
643                                KnownZero, KnownOne, Depth+1))
644         return I;
645       assert(!(KnownZero & KnownOne) && "Bits known to be one AND zero?");
646       KnownZero = APIntOps::lshr(KnownZero, ShiftAmt);
647       KnownOne  = APIntOps::lshr(KnownOne, ShiftAmt);
648       if (ShiftAmt) {
649         // Compute the new bits that are at the top now.
650         APInt HighBits(APInt::getHighBitsSet(BitWidth, ShiftAmt));
651         KnownZero |= HighBits;  // high bits known zero.
652       }
653     }
654     break;
655   case Instruction::AShr:
656     // If this is an arithmetic shift right and only the low-bit is set, we can
657     // always convert this into a logical shr, even if the shift amount is
658     // variable.  The low bit of the shift cannot be an input sign bit unless
659     // the shift amount is >= the size of the datatype, which is undefined.
660     if (DemandedMask == 1) {
661       // Perform the logical shift right.
662       Instruction *NewVal = BinaryOperator::CreateLShr(
663                         I->getOperand(0), I->getOperand(1), I->getName());
664       return InsertNewInstWith(NewVal, *I);
665     }
666 
667     // If the sign bit is the only bit demanded by this ashr, then there is no
668     // need to do it, the shift doesn't change the high bit.
669     if (DemandedMask.isSignBit())
670       return I->getOperand(0);
671 
672     if (ConstantInt *SA = dyn_cast<ConstantInt>(I->getOperand(1))) {
673       uint32_t ShiftAmt = SA->getLimitedValue(BitWidth-1);
674 
675       // Signed shift right.
676       APInt DemandedMaskIn(DemandedMask.shl(ShiftAmt));
677       // If any of the "high bits" are demanded, we should set the sign bit as
678       // demanded.
679       if (DemandedMask.countLeadingZeros() <= ShiftAmt)
680         DemandedMaskIn.setBit(BitWidth-1);
681 
682       // If the shift is exact, then it does demand the low bits (and knows that
683       // they are zero).
684       if (cast<AShrOperator>(I)->isExact())
685         DemandedMaskIn |= APInt::getLowBitsSet(BitWidth, ShiftAmt);
686 
687       if (SimplifyDemandedBits(I->getOperandUse(0), DemandedMaskIn,
688                                KnownZero, KnownOne, Depth+1))
689         return I;
690       assert(!(KnownZero & KnownOne) && "Bits known to be one AND zero?");
691       // Compute the new bits that are at the top now.
692       APInt HighBits(APInt::getHighBitsSet(BitWidth, ShiftAmt));
693       KnownZero = APIntOps::lshr(KnownZero, ShiftAmt);
694       KnownOne  = APIntOps::lshr(KnownOne, ShiftAmt);
695 
696       // Handle the sign bits.
697       APInt SignBit(APInt::getSignBit(BitWidth));
698       // Adjust to where it is now in the mask.
699       SignBit = APIntOps::lshr(SignBit, ShiftAmt);
700 
701       // If the input sign bit is known to be zero, or if none of the top bits
702       // are demanded, turn this into an unsigned shift right.
703       if (BitWidth <= ShiftAmt || KnownZero[BitWidth-ShiftAmt-1] ||
704           (HighBits & ~DemandedMask) == HighBits) {
705         // Perform the logical shift right.
706         BinaryOperator *NewVal = BinaryOperator::CreateLShr(I->getOperand(0),
707                                                             SA, I->getName());
708         NewVal->setIsExact(cast<BinaryOperator>(I)->isExact());
709         return InsertNewInstWith(NewVal, *I);
710       } else if ((KnownOne & SignBit) != 0) { // New bits are known one.
711         KnownOne |= HighBits;
712       }
713     }
714     break;
715   case Instruction::SRem:
716     if (ConstantInt *Rem = dyn_cast<ConstantInt>(I->getOperand(1))) {
717       // X % -1 demands all the bits because we don't want to introduce
718       // INT_MIN % -1 (== undef) by accident.
719       if (Rem->isAllOnesValue())
720         break;
721       APInt RA = Rem->getValue().abs();
722       if (RA.isPowerOf2()) {
723         if (DemandedMask.ult(RA))    // srem won't affect demanded bits
724           return I->getOperand(0);
725 
726         APInt LowBits = RA - 1;
727         APInt Mask2 = LowBits | APInt::getSignBit(BitWidth);
728         if (SimplifyDemandedBits(I->getOperandUse(0), Mask2,
729                                  LHSKnownZero, LHSKnownOne, Depth+1))
730           return I;
731 
732         // The low bits of LHS are unchanged by the srem.
733         KnownZero = LHSKnownZero & LowBits;
734         KnownOne = LHSKnownOne & LowBits;
735 
736         // If LHS is non-negative or has all low bits zero, then the upper bits
737         // are all zero.
738         if (LHSKnownZero[BitWidth-1] || ((LHSKnownZero & LowBits) == LowBits))
739           KnownZero |= ~LowBits;
740 
741         // If LHS is negative and not all low bits are zero, then the upper bits
742         // are all one.
743         if (LHSKnownOne[BitWidth-1] && ((LHSKnownOne & LowBits) != 0))
744           KnownOne |= ~LowBits;
745 
746         assert(!(KnownZero & KnownOne) && "Bits known to be one AND zero?");
747       }
748     }
749 
750     // The sign bit is the LHS's sign bit, except when the result of the
751     // remainder is zero.
752     if (DemandedMask.isNegative() && KnownZero.isNonNegative()) {
753       APInt LHSKnownZero(BitWidth, 0), LHSKnownOne(BitWidth, 0);
754       ComputeMaskedBits(I->getOperand(0), LHSKnownZero, LHSKnownOne, Depth+1);
755       // If it's known zero, our sign bit is also zero.
756       if (LHSKnownZero.isNegative())
757         KnownZero |= LHSKnownZero;
758     }
759     break;
760   case Instruction::URem: {
761     APInt KnownZero2(BitWidth, 0), KnownOne2(BitWidth, 0);
762     APInt AllOnes = APInt::getAllOnesValue(BitWidth);
763     if (SimplifyDemandedBits(I->getOperandUse(0), AllOnes,
764                              KnownZero2, KnownOne2, Depth+1) ||
765         SimplifyDemandedBits(I->getOperandUse(1), AllOnes,
766                              KnownZero2, KnownOne2, Depth+1))
767       return I;
768 
769     unsigned Leaders = KnownZero2.countLeadingOnes();
770     Leaders = std::max(Leaders,
771                        KnownZero2.countLeadingOnes());
772     KnownZero = APInt::getHighBitsSet(BitWidth, Leaders) & DemandedMask;
773     break;
774   }
775   case Instruction::Call:
776     if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) {
777       switch (II->getIntrinsicID()) {
778       default: break;
779       case Intrinsic::bswap: {
780         // If the only bits demanded come from one byte of the bswap result,
781         // just shift the input byte into position to eliminate the bswap.
782         unsigned NLZ = DemandedMask.countLeadingZeros();
783         unsigned NTZ = DemandedMask.countTrailingZeros();
784 
785         // Round NTZ down to the next byte.  If we have 11 trailing zeros, then
786         // we need all the bits down to bit 8.  Likewise, round NLZ.  If we
787         // have 14 leading zeros, round to 8.
788         NLZ &= ~7;
789         NTZ &= ~7;
790         // If we need exactly one byte, we can do this transformation.
791         if (BitWidth-NLZ-NTZ == 8) {
792           unsigned ResultBit = NTZ;
793           unsigned InputBit = BitWidth-NTZ-8;
794 
795           // Replace this with either a left or right shift to get the byte into
796           // the right place.
797           Instruction *NewVal;
798           if (InputBit > ResultBit)
799             NewVal = BinaryOperator::CreateLShr(II->getArgOperand(0),
800                     ConstantInt::get(I->getType(), InputBit-ResultBit));
801           else
802             NewVal = BinaryOperator::CreateShl(II->getArgOperand(0),
803                     ConstantInt::get(I->getType(), ResultBit-InputBit));
804           NewVal->takeName(I);
805           return InsertNewInstWith(NewVal, *I);
806         }
807 
808         // TODO: Could compute known zero/one bits based on the input.
809         break;
810       }
811       case Intrinsic::x86_sse42_crc32_64_8:
812       case Intrinsic::x86_sse42_crc32_64_64:
813         KnownZero = APInt::getHighBitsSet(64, 32);
814         return 0;
815       }
816     }
817     ComputeMaskedBits(V, KnownZero, KnownOne, Depth);
818     break;
819   }
820 
821   // If the client is only demanding bits that we know, return the known
822   // constant.
823   if ((DemandedMask & (KnownZero|KnownOne)) == DemandedMask)
824     return Constant::getIntegerValue(VTy, KnownOne);
825   return 0;
826 }
827 
828 /// Helper routine of SimplifyDemandedUseBits. It tries to simplify
829 /// "E1 = (X lsr C1) << C2", where the C1 and C2 are constant, into
830 /// "E2 = X << (C2 - C1)" or "E2 = X >> (C1 - C2)", depending on the sign
831 /// of "C2-C1".
832 ///
833 /// Suppose E1 and E2 are generally different in bits S={bm, bm+1,
834 /// ..., bn}, without considering the specific value X is holding.
835 /// This transformation is legal iff one of following conditions is hold:
836 ///  1) All the bit in S are 0, in this case E1 == E2.
837 ///  2) We don't care those bits in S, per the input DemandedMask.
838 ///  3) Combination of 1) and 2). Some bits in S are 0, and we don't care the
839 ///     rest bits.
840 ///
841 /// Currently we only test condition 2).
842 ///
843 /// As with SimplifyDemandedUseBits, it returns NULL if the simplification was
844 /// not successful.
SimplifyShrShlDemandedBits(Instruction * Shr,Instruction * Shl,APInt DemandedMask,APInt & KnownZero,APInt & KnownOne)845 Value *InstCombiner::SimplifyShrShlDemandedBits(Instruction *Shr,
846   Instruction *Shl, APInt DemandedMask, APInt &KnownZero, APInt &KnownOne) {
847 
848   unsigned ShlAmt = cast<ConstantInt>(Shl->getOperand(1))->getZExtValue();
849   unsigned ShrAmt = cast<ConstantInt>(Shr->getOperand(1))->getZExtValue();
850 
851   KnownOne.clearAllBits();
852   KnownZero = APInt::getBitsSet(KnownZero.getBitWidth(), 0, ShlAmt-1);
853   KnownZero &= DemandedMask;
854 
855   if (ShlAmt == 0 || ShrAmt == 0)
856     return 0;
857 
858   Value *VarX = Shr->getOperand(0);
859   Type *Ty = VarX->getType();
860 
861   APInt BitMask1(APInt::getAllOnesValue(Ty->getIntegerBitWidth()));
862   APInt BitMask2(APInt::getAllOnesValue(Ty->getIntegerBitWidth()));
863 
864   bool isLshr = (Shr->getOpcode() == Instruction::LShr);
865   BitMask1 = isLshr ? (BitMask1.lshr(ShrAmt) << ShlAmt) :
866                       (BitMask1.ashr(ShrAmt) << ShlAmt);
867 
868   if (ShrAmt <= ShlAmt) {
869     BitMask2 <<= (ShlAmt - ShrAmt);
870   } else {
871     BitMask2 = isLshr ? BitMask2.lshr(ShrAmt - ShlAmt):
872                         BitMask2.ashr(ShrAmt - ShlAmt);
873   }
874 
875   // Check if condition-2 (see the comment to this function) is satified.
876   if ((BitMask1 & DemandedMask) == (BitMask2 & DemandedMask)) {
877     if (ShrAmt == ShlAmt)
878       return VarX;
879 
880     if (!Shr->hasOneUse())
881       return 0;
882 
883     BinaryOperator *New;
884     if (ShrAmt < ShlAmt) {
885       Constant *Amt = ConstantInt::get(VarX->getType(), ShlAmt - ShrAmt);
886       New = BinaryOperator::CreateShl(VarX, Amt);
887       BinaryOperator *Orig = cast<BinaryOperator>(Shl);
888       New->setHasNoSignedWrap(Orig->hasNoSignedWrap());
889       New->setHasNoUnsignedWrap(Orig->hasNoUnsignedWrap());
890     } else {
891       Constant *Amt = ConstantInt::get(VarX->getType(), ShrAmt - ShlAmt);
892       New = isLshr ? BinaryOperator::CreateLShr(VarX, Amt) :
893                      BinaryOperator::CreateAShr(VarX, Amt);
894       if (cast<BinaryOperator>(Shr)->isExact())
895         New->setIsExact(true);
896     }
897 
898     return InsertNewInstWith(New, *Shl);
899   }
900 
901   return 0;
902 }
903 
904 /// SimplifyDemandedVectorElts - The specified value produces a vector with
905 /// any number of elements. DemandedElts contains the set of elements that are
906 /// actually used by the caller.  This method analyzes which elements of the
907 /// operand are undef and returns that information in UndefElts.
908 ///
909 /// If the information about demanded elements can be used to simplify the
910 /// operation, the operation is simplified, then the resultant value is
911 /// returned.  This returns null if no change was made.
SimplifyDemandedVectorElts(Value * V,APInt DemandedElts,APInt & UndefElts,unsigned Depth)912 Value *InstCombiner::SimplifyDemandedVectorElts(Value *V, APInt DemandedElts,
913                                                 APInt &UndefElts,
914                                                 unsigned Depth) {
915   unsigned VWidth = cast<VectorType>(V->getType())->getNumElements();
916   APInt EltMask(APInt::getAllOnesValue(VWidth));
917   assert((DemandedElts & ~EltMask) == 0 && "Invalid DemandedElts!");
918 
919   if (isa<UndefValue>(V)) {
920     // If the entire vector is undefined, just return this info.
921     UndefElts = EltMask;
922     return 0;
923   }
924 
925   if (DemandedElts == 0) { // If nothing is demanded, provide undef.
926     UndefElts = EltMask;
927     return UndefValue::get(V->getType());
928   }
929 
930   UndefElts = 0;
931 
932   // Handle ConstantAggregateZero, ConstantVector, ConstantDataSequential.
933   if (Constant *C = dyn_cast<Constant>(V)) {
934     // Check if this is identity. If so, return 0 since we are not simplifying
935     // anything.
936     if (DemandedElts.isAllOnesValue())
937       return 0;
938 
939     Type *EltTy = cast<VectorType>(V->getType())->getElementType();
940     Constant *Undef = UndefValue::get(EltTy);
941 
942     SmallVector<Constant*, 16> Elts;
943     for (unsigned i = 0; i != VWidth; ++i) {
944       if (!DemandedElts[i]) {   // If not demanded, set to undef.
945         Elts.push_back(Undef);
946         UndefElts.setBit(i);
947         continue;
948       }
949 
950       Constant *Elt = C->getAggregateElement(i);
951       if (Elt == 0) return 0;
952 
953       if (isa<UndefValue>(Elt)) {   // Already undef.
954         Elts.push_back(Undef);
955         UndefElts.setBit(i);
956       } else {                               // Otherwise, defined.
957         Elts.push_back(Elt);
958       }
959     }
960 
961     // If we changed the constant, return it.
962     Constant *NewCV = ConstantVector::get(Elts);
963     return NewCV != C ? NewCV : 0;
964   }
965 
966   // Limit search depth.
967   if (Depth == 10)
968     return 0;
969 
970   // If multiple users are using the root value, proceed with
971   // simplification conservatively assuming that all elements
972   // are needed.
973   if (!V->hasOneUse()) {
974     // Quit if we find multiple users of a non-root value though.
975     // They'll be handled when it's their turn to be visited by
976     // the main instcombine process.
977     if (Depth != 0)
978       // TODO: Just compute the UndefElts information recursively.
979       return 0;
980 
981     // Conservatively assume that all elements are needed.
982     DemandedElts = EltMask;
983   }
984 
985   Instruction *I = dyn_cast<Instruction>(V);
986   if (!I) return 0;        // Only analyze instructions.
987 
988   bool MadeChange = false;
989   APInt UndefElts2(VWidth, 0);
990   Value *TmpV;
991   switch (I->getOpcode()) {
992   default: break;
993 
994   case Instruction::InsertElement: {
995     // If this is a variable index, we don't know which element it overwrites.
996     // demand exactly the same input as we produce.
997     ConstantInt *Idx = dyn_cast<ConstantInt>(I->getOperand(2));
998     if (Idx == 0) {
999       // Note that we can't propagate undef elt info, because we don't know
1000       // which elt is getting updated.
1001       TmpV = SimplifyDemandedVectorElts(I->getOperand(0), DemandedElts,
1002                                         UndefElts2, Depth+1);
1003       if (TmpV) { I->setOperand(0, TmpV); MadeChange = true; }
1004       break;
1005     }
1006 
1007     // If this is inserting an element that isn't demanded, remove this
1008     // insertelement.
1009     unsigned IdxNo = Idx->getZExtValue();
1010     if (IdxNo >= VWidth || !DemandedElts[IdxNo]) {
1011       Worklist.Add(I);
1012       return I->getOperand(0);
1013     }
1014 
1015     // Otherwise, the element inserted overwrites whatever was there, so the
1016     // input demanded set is simpler than the output set.
1017     APInt DemandedElts2 = DemandedElts;
1018     DemandedElts2.clearBit(IdxNo);
1019     TmpV = SimplifyDemandedVectorElts(I->getOperand(0), DemandedElts2,
1020                                       UndefElts, Depth+1);
1021     if (TmpV) { I->setOperand(0, TmpV); MadeChange = true; }
1022 
1023     // The inserted element is defined.
1024     UndefElts.clearBit(IdxNo);
1025     break;
1026   }
1027   case Instruction::ShuffleVector: {
1028     ShuffleVectorInst *Shuffle = cast<ShuffleVectorInst>(I);
1029     uint64_t LHSVWidth =
1030       cast<VectorType>(Shuffle->getOperand(0)->getType())->getNumElements();
1031     APInt LeftDemanded(LHSVWidth, 0), RightDemanded(LHSVWidth, 0);
1032     for (unsigned i = 0; i < VWidth; i++) {
1033       if (DemandedElts[i]) {
1034         unsigned MaskVal = Shuffle->getMaskValue(i);
1035         if (MaskVal != -1u) {
1036           assert(MaskVal < LHSVWidth * 2 &&
1037                  "shufflevector mask index out of range!");
1038           if (MaskVal < LHSVWidth)
1039             LeftDemanded.setBit(MaskVal);
1040           else
1041             RightDemanded.setBit(MaskVal - LHSVWidth);
1042         }
1043       }
1044     }
1045 
1046     APInt UndefElts4(LHSVWidth, 0);
1047     TmpV = SimplifyDemandedVectorElts(I->getOperand(0), LeftDemanded,
1048                                       UndefElts4, Depth+1);
1049     if (TmpV) { I->setOperand(0, TmpV); MadeChange = true; }
1050 
1051     APInt UndefElts3(LHSVWidth, 0);
1052     TmpV = SimplifyDemandedVectorElts(I->getOperand(1), RightDemanded,
1053                                       UndefElts3, Depth+1);
1054     if (TmpV) { I->setOperand(1, TmpV); MadeChange = true; }
1055 
1056     bool NewUndefElts = false;
1057     for (unsigned i = 0; i < VWidth; i++) {
1058       unsigned MaskVal = Shuffle->getMaskValue(i);
1059       if (MaskVal == -1u) {
1060         UndefElts.setBit(i);
1061       } else if (!DemandedElts[i]) {
1062         NewUndefElts = true;
1063         UndefElts.setBit(i);
1064       } else if (MaskVal < LHSVWidth) {
1065         if (UndefElts4[MaskVal]) {
1066           NewUndefElts = true;
1067           UndefElts.setBit(i);
1068         }
1069       } else {
1070         if (UndefElts3[MaskVal - LHSVWidth]) {
1071           NewUndefElts = true;
1072           UndefElts.setBit(i);
1073         }
1074       }
1075     }
1076 
1077     if (NewUndefElts) {
1078       // Add additional discovered undefs.
1079       SmallVector<Constant*, 16> Elts;
1080       for (unsigned i = 0; i < VWidth; ++i) {
1081         if (UndefElts[i])
1082           Elts.push_back(UndefValue::get(Type::getInt32Ty(I->getContext())));
1083         else
1084           Elts.push_back(ConstantInt::get(Type::getInt32Ty(I->getContext()),
1085                                           Shuffle->getMaskValue(i)));
1086       }
1087       I->setOperand(2, ConstantVector::get(Elts));
1088       MadeChange = true;
1089     }
1090     break;
1091   }
1092   case Instruction::Select: {
1093     APInt LeftDemanded(DemandedElts), RightDemanded(DemandedElts);
1094     if (ConstantVector* CV = dyn_cast<ConstantVector>(I->getOperand(0))) {
1095       for (unsigned i = 0; i < VWidth; i++) {
1096         if (CV->getAggregateElement(i)->isNullValue())
1097           LeftDemanded.clearBit(i);
1098         else
1099           RightDemanded.clearBit(i);
1100       }
1101     }
1102 
1103     TmpV = SimplifyDemandedVectorElts(I->getOperand(1), LeftDemanded,
1104                                       UndefElts, Depth+1);
1105     if (TmpV) { I->setOperand(1, TmpV); MadeChange = true; }
1106 
1107     TmpV = SimplifyDemandedVectorElts(I->getOperand(2), RightDemanded,
1108                                       UndefElts2, Depth+1);
1109     if (TmpV) { I->setOperand(2, TmpV); MadeChange = true; }
1110 
1111     // Output elements are undefined if both are undefined.
1112     UndefElts &= UndefElts2;
1113     break;
1114   }
1115   case Instruction::BitCast: {
1116     // Vector->vector casts only.
1117     VectorType *VTy = dyn_cast<VectorType>(I->getOperand(0)->getType());
1118     if (!VTy) break;
1119     unsigned InVWidth = VTy->getNumElements();
1120     APInt InputDemandedElts(InVWidth, 0);
1121     unsigned Ratio;
1122 
1123     if (VWidth == InVWidth) {
1124       // If we are converting from <4 x i32> -> <4 x f32>, we demand the same
1125       // elements as are demanded of us.
1126       Ratio = 1;
1127       InputDemandedElts = DemandedElts;
1128     } else if (VWidth > InVWidth) {
1129       // Untested so far.
1130       break;
1131 
1132       // If there are more elements in the result than there are in the source,
1133       // then an input element is live if any of the corresponding output
1134       // elements are live.
1135       Ratio = VWidth/InVWidth;
1136       for (unsigned OutIdx = 0; OutIdx != VWidth; ++OutIdx) {
1137         if (DemandedElts[OutIdx])
1138           InputDemandedElts.setBit(OutIdx/Ratio);
1139       }
1140     } else {
1141       // Untested so far.
1142       break;
1143 
1144       // If there are more elements in the source than there are in the result,
1145       // then an input element is live if the corresponding output element is
1146       // live.
1147       Ratio = InVWidth/VWidth;
1148       for (unsigned InIdx = 0; InIdx != InVWidth; ++InIdx)
1149         if (DemandedElts[InIdx/Ratio])
1150           InputDemandedElts.setBit(InIdx);
1151     }
1152 
1153     // div/rem demand all inputs, because they don't want divide by zero.
1154     TmpV = SimplifyDemandedVectorElts(I->getOperand(0), InputDemandedElts,
1155                                       UndefElts2, Depth+1);
1156     if (TmpV) {
1157       I->setOperand(0, TmpV);
1158       MadeChange = true;
1159     }
1160 
1161     UndefElts = UndefElts2;
1162     if (VWidth > InVWidth) {
1163       llvm_unreachable("Unimp");
1164       // If there are more elements in the result than there are in the source,
1165       // then an output element is undef if the corresponding input element is
1166       // undef.
1167       for (unsigned OutIdx = 0; OutIdx != VWidth; ++OutIdx)
1168         if (UndefElts2[OutIdx/Ratio])
1169           UndefElts.setBit(OutIdx);
1170     } else if (VWidth < InVWidth) {
1171       llvm_unreachable("Unimp");
1172       // If there are more elements in the source than there are in the result,
1173       // then a result element is undef if all of the corresponding input
1174       // elements are undef.
1175       UndefElts = ~0ULL >> (64-VWidth);  // Start out all undef.
1176       for (unsigned InIdx = 0; InIdx != InVWidth; ++InIdx)
1177         if (!UndefElts2[InIdx])            // Not undef?
1178           UndefElts.clearBit(InIdx/Ratio);    // Clear undef bit.
1179     }
1180     break;
1181   }
1182   case Instruction::And:
1183   case Instruction::Or:
1184   case Instruction::Xor:
1185   case Instruction::Add:
1186   case Instruction::Sub:
1187   case Instruction::Mul:
1188     // div/rem demand all inputs, because they don't want divide by zero.
1189     TmpV = SimplifyDemandedVectorElts(I->getOperand(0), DemandedElts,
1190                                       UndefElts, Depth+1);
1191     if (TmpV) { I->setOperand(0, TmpV); MadeChange = true; }
1192     TmpV = SimplifyDemandedVectorElts(I->getOperand(1), DemandedElts,
1193                                       UndefElts2, Depth+1);
1194     if (TmpV) { I->setOperand(1, TmpV); MadeChange = true; }
1195 
1196     // Output elements are undefined if both are undefined.  Consider things
1197     // like undef&0.  The result is known zero, not undef.
1198     UndefElts &= UndefElts2;
1199     break;
1200   case Instruction::FPTrunc:
1201   case Instruction::FPExt:
1202     TmpV = SimplifyDemandedVectorElts(I->getOperand(0), DemandedElts,
1203                                       UndefElts, Depth+1);
1204     if (TmpV) { I->setOperand(0, TmpV); MadeChange = true; }
1205     break;
1206 
1207   case Instruction::Call: {
1208     IntrinsicInst *II = dyn_cast<IntrinsicInst>(I);
1209     if (!II) break;
1210     switch (II->getIntrinsicID()) {
1211     default: break;
1212 
1213     // Binary vector operations that work column-wise.  A dest element is a
1214     // function of the corresponding input elements from the two inputs.
1215     case Intrinsic::x86_sse_sub_ss:
1216     case Intrinsic::x86_sse_mul_ss:
1217     case Intrinsic::x86_sse_min_ss:
1218     case Intrinsic::x86_sse_max_ss:
1219     case Intrinsic::x86_sse2_sub_sd:
1220     case Intrinsic::x86_sse2_mul_sd:
1221     case Intrinsic::x86_sse2_min_sd:
1222     case Intrinsic::x86_sse2_max_sd:
1223       TmpV = SimplifyDemandedVectorElts(II->getArgOperand(0), DemandedElts,
1224                                         UndefElts, Depth+1);
1225       if (TmpV) { II->setArgOperand(0, TmpV); MadeChange = true; }
1226       TmpV = SimplifyDemandedVectorElts(II->getArgOperand(1), DemandedElts,
1227                                         UndefElts2, Depth+1);
1228       if (TmpV) { II->setArgOperand(1, TmpV); MadeChange = true; }
1229 
1230       // If only the low elt is demanded and this is a scalarizable intrinsic,
1231       // scalarize it now.
1232       if (DemandedElts == 1) {
1233         switch (II->getIntrinsicID()) {
1234         default: break;
1235         case Intrinsic::x86_sse_sub_ss:
1236         case Intrinsic::x86_sse_mul_ss:
1237         case Intrinsic::x86_sse2_sub_sd:
1238         case Intrinsic::x86_sse2_mul_sd:
1239           // TODO: Lower MIN/MAX/ABS/etc
1240           Value *LHS = II->getArgOperand(0);
1241           Value *RHS = II->getArgOperand(1);
1242           // Extract the element as scalars.
1243           LHS = InsertNewInstWith(ExtractElementInst::Create(LHS,
1244             ConstantInt::get(Type::getInt32Ty(I->getContext()), 0U)), *II);
1245           RHS = InsertNewInstWith(ExtractElementInst::Create(RHS,
1246             ConstantInt::get(Type::getInt32Ty(I->getContext()), 0U)), *II);
1247 
1248           switch (II->getIntrinsicID()) {
1249           default: llvm_unreachable("Case stmts out of sync!");
1250           case Intrinsic::x86_sse_sub_ss:
1251           case Intrinsic::x86_sse2_sub_sd:
1252             TmpV = InsertNewInstWith(BinaryOperator::CreateFSub(LHS, RHS,
1253                                                         II->getName()), *II);
1254             break;
1255           case Intrinsic::x86_sse_mul_ss:
1256           case Intrinsic::x86_sse2_mul_sd:
1257             TmpV = InsertNewInstWith(BinaryOperator::CreateFMul(LHS, RHS,
1258                                                          II->getName()), *II);
1259             break;
1260           }
1261 
1262           Instruction *New =
1263             InsertElementInst::Create(
1264               UndefValue::get(II->getType()), TmpV,
1265               ConstantInt::get(Type::getInt32Ty(I->getContext()), 0U, false),
1266                                       II->getName());
1267           InsertNewInstWith(New, *II);
1268           return New;
1269         }
1270       }
1271 
1272       // Output elements are undefined if both are undefined.  Consider things
1273       // like undef&0.  The result is known zero, not undef.
1274       UndefElts &= UndefElts2;
1275       break;
1276     }
1277     break;
1278   }
1279   }
1280   return MadeChange ? I : 0;
1281 }
1282