xref: /freebsd-src/contrib/llvm-project/llvm/lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp (revision e8d8bef961a50d4dc22501cde4fb9fb0be1b2532)
1 //===- InstCombineSimplifyDemanded.cpp ------------------------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This file contains logic for simplifying instructions based on information
10 // about how they are used.
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #include "InstCombineInternal.h"
15 #include "llvm/Analysis/TargetTransformInfo.h"
16 #include "llvm/Analysis/ValueTracking.h"
17 #include "llvm/IR/IntrinsicInst.h"
18 #include "llvm/IR/PatternMatch.h"
19 #include "llvm/Support/KnownBits.h"
20 #include "llvm/Transforms/InstCombine/InstCombiner.h"
21 
22 using namespace llvm;
23 using namespace llvm::PatternMatch;
24 
25 #define DEBUG_TYPE "instcombine"
26 
27 /// Check to see if the specified operand of the specified instruction is a
28 /// constant integer. If so, check to see if there are any bits set in the
29 /// constant that are not demanded. If so, shrink the constant and return true.
30 static bool ShrinkDemandedConstant(Instruction *I, unsigned OpNo,
31                                    const APInt &Demanded) {
32   assert(I && "No instruction?");
33   assert(OpNo < I->getNumOperands() && "Operand index too large");
34 
35   // The operand must be a constant integer or splat integer.
36   Value *Op = I->getOperand(OpNo);
37   const APInt *C;
38   if (!match(Op, m_APInt(C)))
39     return false;
40 
41   // If there are no bits set that aren't demanded, nothing to do.
42   if (C->isSubsetOf(Demanded))
43     return false;
44 
45   // This instruction is producing bits that are not demanded. Shrink the RHS.
46   I->setOperand(OpNo, ConstantInt::get(Op->getType(), *C & Demanded));
47 
48   return true;
49 }
50 
51 
52 
53 /// Inst is an integer instruction that SimplifyDemandedBits knows about. See if
54 /// the instruction has any properties that allow us to simplify its operands.
55 bool InstCombinerImpl::SimplifyDemandedInstructionBits(Instruction &Inst) {
56   unsigned BitWidth = Inst.getType()->getScalarSizeInBits();
57   KnownBits Known(BitWidth);
58   APInt DemandedMask(APInt::getAllOnesValue(BitWidth));
59 
60   Value *V = SimplifyDemandedUseBits(&Inst, DemandedMask, Known,
61                                      0, &Inst);
62   if (!V) return false;
63   if (V == &Inst) return true;
64   replaceInstUsesWith(Inst, V);
65   return true;
66 }
67 
68 /// This form of SimplifyDemandedBits simplifies the specified instruction
69 /// operand if possible, updating it in place. It returns true if it made any
70 /// change and false otherwise.
71 bool InstCombinerImpl::SimplifyDemandedBits(Instruction *I, unsigned OpNo,
72                                             const APInt &DemandedMask,
73                                             KnownBits &Known, unsigned Depth) {
74   Use &U = I->getOperandUse(OpNo);
75   Value *NewVal = SimplifyDemandedUseBits(U.get(), DemandedMask, Known,
76                                           Depth, I);
77   if (!NewVal) return false;
78   if (Instruction* OpInst = dyn_cast<Instruction>(U))
79     salvageDebugInfo(*OpInst);
80 
81   replaceUse(U, NewVal);
82   return true;
83 }
84 
85 /// This function attempts to replace V with a simpler value based on the
86 /// demanded bits. When this function is called, it is known that only the bits
87 /// set in DemandedMask of the result of V are ever used downstream.
88 /// Consequently, depending on the mask and V, it may be possible to replace V
89 /// with a constant or one of its operands. In such cases, this function does
90 /// the replacement and returns true. In all other cases, it returns false after
91 /// analyzing the expression and setting KnownOne and known to be one in the
92 /// expression. Known.Zero contains all the bits that are known to be zero in
93 /// the expression. These are provided to potentially allow the caller (which
94 /// might recursively be SimplifyDemandedBits itself) to simplify the
95 /// expression.
96 /// Known.One and Known.Zero always follow the invariant that:
97 ///   Known.One & Known.Zero == 0.
98 /// That is, a bit can't be both 1 and 0. Note that the bits in Known.One and
99 /// Known.Zero may only be accurate for those bits set in DemandedMask. Note
100 /// also that the bitwidth of V, DemandedMask, Known.Zero and Known.One must all
101 /// be the same.
102 ///
103 /// This returns null if it did not change anything and it permits no
104 /// simplification.  This returns V itself if it did some simplification of V's
105 /// operands based on the information about what bits are demanded. This returns
106 /// some other non-null value if it found out that V is equal to another value
107 /// in the context where the specified bits are demanded, but not for all users.
108 Value *InstCombinerImpl::SimplifyDemandedUseBits(Value *V, APInt DemandedMask,
109                                                  KnownBits &Known,
110                                                  unsigned Depth,
111                                                  Instruction *CxtI) {
112   assert(V != nullptr && "Null pointer of Value???");
113   assert(Depth <= MaxAnalysisRecursionDepth && "Limit Search Depth");
114   uint32_t BitWidth = DemandedMask.getBitWidth();
115   Type *VTy = V->getType();
116   assert(
117       (!VTy->isIntOrIntVectorTy() || VTy->getScalarSizeInBits() == BitWidth) &&
118       Known.getBitWidth() == BitWidth &&
119       "Value *V, DemandedMask and Known must have same BitWidth");
120 
121   if (isa<Constant>(V)) {
122     computeKnownBits(V, Known, Depth, CxtI);
123     return nullptr;
124   }
125 
126   Known.resetAll();
127   if (DemandedMask.isNullValue())     // Not demanding any bits from V.
128     return UndefValue::get(VTy);
129 
130   if (Depth == MaxAnalysisRecursionDepth)
131     return nullptr;
132 
133   if (isa<ScalableVectorType>(VTy))
134     return nullptr;
135 
136   Instruction *I = dyn_cast<Instruction>(V);
137   if (!I) {
138     computeKnownBits(V, Known, Depth, CxtI);
139     return nullptr;        // Only analyze instructions.
140   }
141 
142   // If there are multiple uses of this value and we aren't at the root, then
143   // we can't do any simplifications of the operands, because DemandedMask
144   // only reflects the bits demanded by *one* of the users.
145   if (Depth != 0 && !I->hasOneUse())
146     return SimplifyMultipleUseDemandedBits(I, DemandedMask, Known, Depth, CxtI);
147 
148   KnownBits LHSKnown(BitWidth), RHSKnown(BitWidth);
149 
150   // If this is the root being simplified, allow it to have multiple uses,
151   // just set the DemandedMask to all bits so that we can try to simplify the
152   // operands.  This allows visitTruncInst (for example) to simplify the
153   // operand of a trunc without duplicating all the logic below.
154   if (Depth == 0 && !V->hasOneUse())
155     DemandedMask.setAllBits();
156 
157   switch (I->getOpcode()) {
158   default:
159     computeKnownBits(I, Known, Depth, CxtI);
160     break;
161   case Instruction::And: {
162     // If either the LHS or the RHS are Zero, the result is zero.
163     if (SimplifyDemandedBits(I, 1, DemandedMask, RHSKnown, Depth + 1) ||
164         SimplifyDemandedBits(I, 0, DemandedMask & ~RHSKnown.Zero, LHSKnown,
165                              Depth + 1))
166       return I;
167     assert(!RHSKnown.hasConflict() && "Bits known to be one AND zero?");
168     assert(!LHSKnown.hasConflict() && "Bits known to be one AND zero?");
169 
170     Known = LHSKnown & RHSKnown;
171 
172     // If the client is only demanding bits that we know, return the known
173     // constant.
174     if (DemandedMask.isSubsetOf(Known.Zero | Known.One))
175       return Constant::getIntegerValue(VTy, Known.One);
176 
177     // If all of the demanded bits are known 1 on one side, return the other.
178     // These bits cannot contribute to the result of the 'and'.
179     if (DemandedMask.isSubsetOf(LHSKnown.Zero | RHSKnown.One))
180       return I->getOperand(0);
181     if (DemandedMask.isSubsetOf(RHSKnown.Zero | LHSKnown.One))
182       return I->getOperand(1);
183 
184     // If the RHS is a constant, see if we can simplify it.
185     if (ShrinkDemandedConstant(I, 1, DemandedMask & ~LHSKnown.Zero))
186       return I;
187 
188     break;
189   }
190   case Instruction::Or: {
191     // If either the LHS or the RHS are One, the result is One.
192     if (SimplifyDemandedBits(I, 1, DemandedMask, RHSKnown, Depth + 1) ||
193         SimplifyDemandedBits(I, 0, DemandedMask & ~RHSKnown.One, LHSKnown,
194                              Depth + 1))
195       return I;
196     assert(!RHSKnown.hasConflict() && "Bits known to be one AND zero?");
197     assert(!LHSKnown.hasConflict() && "Bits known to be one AND zero?");
198 
199     Known = LHSKnown | RHSKnown;
200 
201     // If the client is only demanding bits that we know, return the known
202     // constant.
203     if (DemandedMask.isSubsetOf(Known.Zero | Known.One))
204       return Constant::getIntegerValue(VTy, Known.One);
205 
206     // If all of the demanded bits are known zero on one side, return the other.
207     // These bits cannot contribute to the result of the 'or'.
208     if (DemandedMask.isSubsetOf(LHSKnown.One | RHSKnown.Zero))
209       return I->getOperand(0);
210     if (DemandedMask.isSubsetOf(RHSKnown.One | LHSKnown.Zero))
211       return I->getOperand(1);
212 
213     // If the RHS is a constant, see if we can simplify it.
214     if (ShrinkDemandedConstant(I, 1, DemandedMask))
215       return I;
216 
217     break;
218   }
219   case Instruction::Xor: {
220     if (SimplifyDemandedBits(I, 1, DemandedMask, RHSKnown, Depth + 1) ||
221         SimplifyDemandedBits(I, 0, DemandedMask, LHSKnown, Depth + 1))
222       return I;
223     assert(!RHSKnown.hasConflict() && "Bits known to be one AND zero?");
224     assert(!LHSKnown.hasConflict() && "Bits known to be one AND zero?");
225 
226     Known = LHSKnown ^ RHSKnown;
227 
228     // If the client is only demanding bits that we know, return the known
229     // constant.
230     if (DemandedMask.isSubsetOf(Known.Zero | Known.One))
231       return Constant::getIntegerValue(VTy, Known.One);
232 
233     // If all of the demanded bits are known zero on one side, return the other.
234     // These bits cannot contribute to the result of the 'xor'.
235     if (DemandedMask.isSubsetOf(RHSKnown.Zero))
236       return I->getOperand(0);
237     if (DemandedMask.isSubsetOf(LHSKnown.Zero))
238       return I->getOperand(1);
239 
240     // If all of the demanded bits are known to be zero on one side or the
241     // other, turn this into an *inclusive* or.
242     //    e.g. (A & C1)^(B & C2) -> (A & C1)|(B & C2) iff C1&C2 == 0
243     if (DemandedMask.isSubsetOf(RHSKnown.Zero | LHSKnown.Zero)) {
244       Instruction *Or =
245         BinaryOperator::CreateOr(I->getOperand(0), I->getOperand(1),
246                                  I->getName());
247       return InsertNewInstWith(Or, *I);
248     }
249 
250     // If all of the demanded bits on one side are known, and all of the set
251     // bits on that side are also known to be set on the other side, turn this
252     // into an AND, as we know the bits will be cleared.
253     //    e.g. (X | C1) ^ C2 --> (X | C1) & ~C2 iff (C1&C2) == C2
254     if (DemandedMask.isSubsetOf(RHSKnown.Zero|RHSKnown.One) &&
255         RHSKnown.One.isSubsetOf(LHSKnown.One)) {
256       Constant *AndC = Constant::getIntegerValue(VTy,
257                                                  ~RHSKnown.One & DemandedMask);
258       Instruction *And = BinaryOperator::CreateAnd(I->getOperand(0), AndC);
259       return InsertNewInstWith(And, *I);
260     }
261 
262     // If the RHS is a constant, see if we can change it. Don't alter a -1
263     // constant because that's a canonical 'not' op, and that is better for
264     // combining, SCEV, and codegen.
265     const APInt *C;
266     if (match(I->getOperand(1), m_APInt(C)) && !C->isAllOnesValue()) {
267       if ((*C | ~DemandedMask).isAllOnesValue()) {
268         // Force bits to 1 to create a 'not' op.
269         I->setOperand(1, ConstantInt::getAllOnesValue(VTy));
270         return I;
271       }
272       // If we can't turn this into a 'not', try to shrink the constant.
273       if (ShrinkDemandedConstant(I, 1, DemandedMask))
274         return I;
275     }
276 
277     // If our LHS is an 'and' and if it has one use, and if any of the bits we
278     // are flipping are known to be set, then the xor is just resetting those
279     // bits to zero.  We can just knock out bits from the 'and' and the 'xor',
280     // simplifying both of them.
281     if (Instruction *LHSInst = dyn_cast<Instruction>(I->getOperand(0))) {
282       ConstantInt *AndRHS, *XorRHS;
283       if (LHSInst->getOpcode() == Instruction::And && LHSInst->hasOneUse() &&
284           match(I->getOperand(1), m_ConstantInt(XorRHS)) &&
285           match(LHSInst->getOperand(1), m_ConstantInt(AndRHS)) &&
286           (LHSKnown.One & RHSKnown.One & DemandedMask) != 0) {
287         APInt NewMask = ~(LHSKnown.One & RHSKnown.One & DemandedMask);
288 
289         Constant *AndC =
290             ConstantInt::get(I->getType(), NewMask & AndRHS->getValue());
291         Instruction *NewAnd = BinaryOperator::CreateAnd(I->getOperand(0), AndC);
292         InsertNewInstWith(NewAnd, *I);
293 
294         Constant *XorC =
295             ConstantInt::get(I->getType(), NewMask & XorRHS->getValue());
296         Instruction *NewXor = BinaryOperator::CreateXor(NewAnd, XorC);
297         return InsertNewInstWith(NewXor, *I);
298       }
299     }
300     break;
301   }
302   case Instruction::Select: {
303     Value *LHS, *RHS;
304     SelectPatternFlavor SPF = matchSelectPattern(I, LHS, RHS).Flavor;
305     if (SPF == SPF_UMAX) {
306       // UMax(A, C) == A if ...
307       // The lowest non-zero bit of DemandMask is higher than the highest
308       // non-zero bit of C.
309       const APInt *C;
310       unsigned CTZ = DemandedMask.countTrailingZeros();
311       if (match(RHS, m_APInt(C)) && CTZ >= C->getActiveBits())
312         return LHS;
313     } else if (SPF == SPF_UMIN) {
314       // UMin(A, C) == A if ...
315       // The lowest non-zero bit of DemandMask is higher than the highest
316       // non-one bit of C.
317       // This comes from using DeMorgans on the above umax example.
318       const APInt *C;
319       unsigned CTZ = DemandedMask.countTrailingZeros();
320       if (match(RHS, m_APInt(C)) &&
321           CTZ >= C->getBitWidth() - C->countLeadingOnes())
322         return LHS;
323     }
324 
325     // If this is a select as part of any other min/max pattern, don't simplify
326     // any further in case we break the structure.
327     if (SPF != SPF_UNKNOWN)
328       return nullptr;
329 
330     if (SimplifyDemandedBits(I, 2, DemandedMask, RHSKnown, Depth + 1) ||
331         SimplifyDemandedBits(I, 1, DemandedMask, LHSKnown, Depth + 1))
332       return I;
333     assert(!RHSKnown.hasConflict() && "Bits known to be one AND zero?");
334     assert(!LHSKnown.hasConflict() && "Bits known to be one AND zero?");
335 
336     // If the operands are constants, see if we can simplify them.
337     // This is similar to ShrinkDemandedConstant, but for a select we want to
338     // try to keep the selected constants the same as icmp value constants, if
339     // we can. This helps not break apart (or helps put back together)
340     // canonical patterns like min and max.
341     auto CanonicalizeSelectConstant = [](Instruction *I, unsigned OpNo,
342                                          const APInt &DemandedMask) {
343       const APInt *SelC;
344       if (!match(I->getOperand(OpNo), m_APInt(SelC)))
345         return false;
346 
347       // Get the constant out of the ICmp, if there is one.
348       const APInt *CmpC;
349       ICmpInst::Predicate Pred;
350       if (!match(I->getOperand(0), m_c_ICmp(Pred, m_APInt(CmpC), m_Value())) ||
351           CmpC->getBitWidth() != SelC->getBitWidth())
352         return ShrinkDemandedConstant(I, OpNo, DemandedMask);
353 
354       // If the constant is already the same as the ICmp, leave it as-is.
355       if (*CmpC == *SelC)
356         return false;
357       // If the constants are not already the same, but can be with the demand
358       // mask, use the constant value from the ICmp.
359       if ((*CmpC & DemandedMask) == (*SelC & DemandedMask)) {
360         I->setOperand(OpNo, ConstantInt::get(I->getType(), *CmpC));
361         return true;
362       }
363       return ShrinkDemandedConstant(I, OpNo, DemandedMask);
364     };
365     if (CanonicalizeSelectConstant(I, 1, DemandedMask) ||
366         CanonicalizeSelectConstant(I, 2, DemandedMask))
367       return I;
368 
369     // Only known if known in both the LHS and RHS.
370     Known = KnownBits::commonBits(LHSKnown, RHSKnown);
371     break;
372   }
373   case Instruction::ZExt:
374   case Instruction::Trunc: {
375     unsigned SrcBitWidth = I->getOperand(0)->getType()->getScalarSizeInBits();
376 
377     APInt InputDemandedMask = DemandedMask.zextOrTrunc(SrcBitWidth);
378     KnownBits InputKnown(SrcBitWidth);
379     if (SimplifyDemandedBits(I, 0, InputDemandedMask, InputKnown, Depth + 1))
380       return I;
381     assert(InputKnown.getBitWidth() == SrcBitWidth && "Src width changed?");
382     Known = InputKnown.zextOrTrunc(BitWidth);
383     assert(!Known.hasConflict() && "Bits known to be one AND zero?");
384     break;
385   }
386   case Instruction::BitCast:
387     if (!I->getOperand(0)->getType()->isIntOrIntVectorTy())
388       return nullptr;  // vector->int or fp->int?
389 
390     if (VectorType *DstVTy = dyn_cast<VectorType>(I->getType())) {
391       if (VectorType *SrcVTy =
392             dyn_cast<VectorType>(I->getOperand(0)->getType())) {
393         if (cast<FixedVectorType>(DstVTy)->getNumElements() !=
394             cast<FixedVectorType>(SrcVTy)->getNumElements())
395           // Don't touch a bitcast between vectors of different element counts.
396           return nullptr;
397       } else
398         // Don't touch a scalar-to-vector bitcast.
399         return nullptr;
400     } else if (I->getOperand(0)->getType()->isVectorTy())
401       // Don't touch a vector-to-scalar bitcast.
402       return nullptr;
403 
404     if (SimplifyDemandedBits(I, 0, DemandedMask, Known, Depth + 1))
405       return I;
406     assert(!Known.hasConflict() && "Bits known to be one AND zero?");
407     break;
408   case Instruction::SExt: {
409     // Compute the bits in the result that are not present in the input.
410     unsigned SrcBitWidth = I->getOperand(0)->getType()->getScalarSizeInBits();
411 
412     APInt InputDemandedBits = DemandedMask.trunc(SrcBitWidth);
413 
414     // If any of the sign extended bits are demanded, we know that the sign
415     // bit is demanded.
416     if (DemandedMask.getActiveBits() > SrcBitWidth)
417       InputDemandedBits.setBit(SrcBitWidth-1);
418 
419     KnownBits InputKnown(SrcBitWidth);
420     if (SimplifyDemandedBits(I, 0, InputDemandedBits, InputKnown, Depth + 1))
421       return I;
422 
423     // If the input sign bit is known zero, or if the NewBits are not demanded
424     // convert this into a zero extension.
425     if (InputKnown.isNonNegative() ||
426         DemandedMask.getActiveBits() <= SrcBitWidth) {
427       // Convert to ZExt cast.
428       CastInst *NewCast = new ZExtInst(I->getOperand(0), VTy, I->getName());
429       return InsertNewInstWith(NewCast, *I);
430      }
431 
432     // If the sign bit of the input is known set or clear, then we know the
433     // top bits of the result.
434     Known = InputKnown.sext(BitWidth);
435     assert(!Known.hasConflict() && "Bits known to be one AND zero?");
436     break;
437   }
438   case Instruction::Add:
439     if ((DemandedMask & 1) == 0) {
440       // If we do not need the low bit, try to convert bool math to logic:
441       // add iN (zext i1 X), (sext i1 Y) --> sext (~X & Y) to iN
442       Value *X, *Y;
443       if (match(I, m_c_Add(m_OneUse(m_ZExt(m_Value(X))),
444                            m_OneUse(m_SExt(m_Value(Y))))) &&
445           X->getType()->isIntOrIntVectorTy(1) && X->getType() == Y->getType()) {
446         // Truth table for inputs and output signbits:
447         //       X:0 | X:1
448         //      ----------
449         // Y:0  |  0 | 0 |
450         // Y:1  | -1 | 0 |
451         //      ----------
452         IRBuilderBase::InsertPointGuard Guard(Builder);
453         Builder.SetInsertPoint(I);
454         Value *AndNot = Builder.CreateAnd(Builder.CreateNot(X), Y);
455         return Builder.CreateSExt(AndNot, VTy);
456       }
457 
458       // add iN (sext i1 X), (sext i1 Y) --> sext (X | Y) to iN
459       // TODO: Relax the one-use checks because we are removing an instruction?
460       if (match(I, m_Add(m_OneUse(m_SExt(m_Value(X))),
461                          m_OneUse(m_SExt(m_Value(Y))))) &&
462           X->getType()->isIntOrIntVectorTy(1) && X->getType() == Y->getType()) {
463         // Truth table for inputs and output signbits:
464         //       X:0 | X:1
465         //      -----------
466         // Y:0  | -1 | -1 |
467         // Y:1  | -1 |  0 |
468         //      -----------
469         IRBuilderBase::InsertPointGuard Guard(Builder);
470         Builder.SetInsertPoint(I);
471         Value *Or = Builder.CreateOr(X, Y);
472         return Builder.CreateSExt(Or, VTy);
473       }
474     }
475     LLVM_FALLTHROUGH;
476   case Instruction::Sub: {
477     /// If the high-bits of an ADD/SUB are not demanded, then we do not care
478     /// about the high bits of the operands.
479     unsigned NLZ = DemandedMask.countLeadingZeros();
480     // Right fill the mask of bits for this ADD/SUB to demand the most
481     // significant bit and all those below it.
482     APInt DemandedFromOps(APInt::getLowBitsSet(BitWidth, BitWidth-NLZ));
483     if (ShrinkDemandedConstant(I, 0, DemandedFromOps) ||
484         SimplifyDemandedBits(I, 0, DemandedFromOps, LHSKnown, Depth + 1) ||
485         ShrinkDemandedConstant(I, 1, DemandedFromOps) ||
486         SimplifyDemandedBits(I, 1, DemandedFromOps, RHSKnown, Depth + 1)) {
487       if (NLZ > 0) {
488         // Disable the nsw and nuw flags here: We can no longer guarantee that
489         // we won't wrap after simplification. Removing the nsw/nuw flags is
490         // legal here because the top bit is not demanded.
491         BinaryOperator &BinOP = *cast<BinaryOperator>(I);
492         BinOP.setHasNoSignedWrap(false);
493         BinOP.setHasNoUnsignedWrap(false);
494       }
495       return I;
496     }
497 
498     // If we are known to be adding/subtracting zeros to every bit below
499     // the highest demanded bit, we just return the other side.
500     if (DemandedFromOps.isSubsetOf(RHSKnown.Zero))
501       return I->getOperand(0);
502     // We can't do this with the LHS for subtraction, unless we are only
503     // demanding the LSB.
504     if ((I->getOpcode() == Instruction::Add ||
505          DemandedFromOps.isOneValue()) &&
506         DemandedFromOps.isSubsetOf(LHSKnown.Zero))
507       return I->getOperand(1);
508 
509     // Otherwise just compute the known bits of the result.
510     bool NSW = cast<OverflowingBinaryOperator>(I)->hasNoSignedWrap();
511     Known = KnownBits::computeForAddSub(I->getOpcode() == Instruction::Add,
512                                         NSW, LHSKnown, RHSKnown);
513     break;
514   }
515   case Instruction::Shl: {
516     const APInt *SA;
517     if (match(I->getOperand(1), m_APInt(SA))) {
518       const APInt *ShrAmt;
519       if (match(I->getOperand(0), m_Shr(m_Value(), m_APInt(ShrAmt))))
520         if (Instruction *Shr = dyn_cast<Instruction>(I->getOperand(0)))
521           if (Value *R = simplifyShrShlDemandedBits(Shr, *ShrAmt, I, *SA,
522                                                     DemandedMask, Known))
523             return R;
524 
525       uint64_t ShiftAmt = SA->getLimitedValue(BitWidth-1);
526       APInt DemandedMaskIn(DemandedMask.lshr(ShiftAmt));
527 
528       // If the shift is NUW/NSW, then it does demand the high bits.
529       ShlOperator *IOp = cast<ShlOperator>(I);
530       if (IOp->hasNoSignedWrap())
531         DemandedMaskIn.setHighBits(ShiftAmt+1);
532       else if (IOp->hasNoUnsignedWrap())
533         DemandedMaskIn.setHighBits(ShiftAmt);
534 
535       if (SimplifyDemandedBits(I, 0, DemandedMaskIn, Known, Depth + 1))
536         return I;
537       assert(!Known.hasConflict() && "Bits known to be one AND zero?");
538 
539       bool SignBitZero = Known.Zero.isSignBitSet();
540       bool SignBitOne = Known.One.isSignBitSet();
541       Known.Zero <<= ShiftAmt;
542       Known.One  <<= ShiftAmt;
543       // low bits known zero.
544       if (ShiftAmt)
545         Known.Zero.setLowBits(ShiftAmt);
546 
547       // If this shift has "nsw" keyword, then the result is either a poison
548       // value or has the same sign bit as the first operand.
549       if (IOp->hasNoSignedWrap()) {
550         if (SignBitZero)
551           Known.Zero.setSignBit();
552         else if (SignBitOne)
553           Known.One.setSignBit();
554         if (Known.hasConflict())
555           return UndefValue::get(I->getType());
556       }
557     } else {
558       computeKnownBits(I, Known, Depth, CxtI);
559     }
560     break;
561   }
562   case Instruction::LShr: {
563     const APInt *SA;
564     if (match(I->getOperand(1), m_APInt(SA))) {
565       uint64_t ShiftAmt = SA->getLimitedValue(BitWidth-1);
566 
567       // Unsigned shift right.
568       APInt DemandedMaskIn(DemandedMask.shl(ShiftAmt));
569 
570       // If the shift is exact, then it does demand the low bits (and knows that
571       // they are zero).
572       if (cast<LShrOperator>(I)->isExact())
573         DemandedMaskIn.setLowBits(ShiftAmt);
574 
575       if (SimplifyDemandedBits(I, 0, DemandedMaskIn, Known, Depth + 1))
576         return I;
577       assert(!Known.hasConflict() && "Bits known to be one AND zero?");
578       Known.Zero.lshrInPlace(ShiftAmt);
579       Known.One.lshrInPlace(ShiftAmt);
580       if (ShiftAmt)
581         Known.Zero.setHighBits(ShiftAmt);  // high bits known zero.
582     } else {
583       computeKnownBits(I, Known, Depth, CxtI);
584     }
585     break;
586   }
587   case Instruction::AShr: {
588     // If this is an arithmetic shift right and only the low-bit is set, we can
589     // always convert this into a logical shr, even if the shift amount is
590     // variable.  The low bit of the shift cannot be an input sign bit unless
591     // the shift amount is >= the size of the datatype, which is undefined.
592     if (DemandedMask.isOneValue()) {
593       // Perform the logical shift right.
594       Instruction *NewVal = BinaryOperator::CreateLShr(
595                         I->getOperand(0), I->getOperand(1), I->getName());
596       return InsertNewInstWith(NewVal, *I);
597     }
598 
599     // If the sign bit is the only bit demanded by this ashr, then there is no
600     // need to do it, the shift doesn't change the high bit.
601     if (DemandedMask.isSignMask())
602       return I->getOperand(0);
603 
604     const APInt *SA;
605     if (match(I->getOperand(1), m_APInt(SA))) {
606       uint32_t ShiftAmt = SA->getLimitedValue(BitWidth-1);
607 
608       // Signed shift right.
609       APInt DemandedMaskIn(DemandedMask.shl(ShiftAmt));
610       // If any of the high bits are demanded, we should set the sign bit as
611       // demanded.
612       if (DemandedMask.countLeadingZeros() <= ShiftAmt)
613         DemandedMaskIn.setSignBit();
614 
615       // If the shift is exact, then it does demand the low bits (and knows that
616       // they are zero).
617       if (cast<AShrOperator>(I)->isExact())
618         DemandedMaskIn.setLowBits(ShiftAmt);
619 
620       if (SimplifyDemandedBits(I, 0, DemandedMaskIn, Known, Depth + 1))
621         return I;
622 
623       unsigned SignBits = ComputeNumSignBits(I->getOperand(0), Depth + 1, CxtI);
624 
625       assert(!Known.hasConflict() && "Bits known to be one AND zero?");
626       // Compute the new bits that are at the top now plus sign bits.
627       APInt HighBits(APInt::getHighBitsSet(
628           BitWidth, std::min(SignBits + ShiftAmt - 1, BitWidth)));
629       Known.Zero.lshrInPlace(ShiftAmt);
630       Known.One.lshrInPlace(ShiftAmt);
631 
632       // If the input sign bit is known to be zero, or if none of the top bits
633       // are demanded, turn this into an unsigned shift right.
634       assert(BitWidth > ShiftAmt && "Shift amount not saturated?");
635       if (Known.Zero[BitWidth-ShiftAmt-1] ||
636           !DemandedMask.intersects(HighBits)) {
637         BinaryOperator *LShr = BinaryOperator::CreateLShr(I->getOperand(0),
638                                                           I->getOperand(1));
639         LShr->setIsExact(cast<BinaryOperator>(I)->isExact());
640         return InsertNewInstWith(LShr, *I);
641       } else if (Known.One[BitWidth-ShiftAmt-1]) { // New bits are known one.
642         Known.One |= HighBits;
643       }
644     } else {
645       computeKnownBits(I, Known, Depth, CxtI);
646     }
647     break;
648   }
649   case Instruction::UDiv: {
650     // UDiv doesn't demand low bits that are zero in the divisor.
651     const APInt *SA;
652     if (match(I->getOperand(1), m_APInt(SA))) {
653       // If the shift is exact, then it does demand the low bits.
654       if (cast<UDivOperator>(I)->isExact())
655         break;
656 
657       // FIXME: Take the demanded mask of the result into account.
658       unsigned RHSTrailingZeros = SA->countTrailingZeros();
659       APInt DemandedMaskIn =
660           APInt::getHighBitsSet(BitWidth, BitWidth - RHSTrailingZeros);
661       if (SimplifyDemandedBits(I, 0, DemandedMaskIn, LHSKnown, Depth + 1))
662         return I;
663 
664       // Propagate zero bits from the input.
665       Known.Zero.setHighBits(std::min(
666           BitWidth, LHSKnown.Zero.countLeadingOnes() + RHSTrailingZeros));
667     } else {
668       computeKnownBits(I, Known, Depth, CxtI);
669     }
670     break;
671   }
672   case Instruction::SRem: {
673     ConstantInt *Rem;
674     if (match(I->getOperand(1), m_ConstantInt(Rem))) {
675       // X % -1 demands all the bits because we don't want to introduce
676       // INT_MIN % -1 (== undef) by accident.
677       if (Rem->isMinusOne())
678         break;
679       APInt RA = Rem->getValue().abs();
680       if (RA.isPowerOf2()) {
681         if (DemandedMask.ult(RA))    // srem won't affect demanded bits
682           return I->getOperand(0);
683 
684         APInt LowBits = RA - 1;
685         APInt Mask2 = LowBits | APInt::getSignMask(BitWidth);
686         if (SimplifyDemandedBits(I, 0, Mask2, LHSKnown, Depth + 1))
687           return I;
688 
689         // The low bits of LHS are unchanged by the srem.
690         Known.Zero = LHSKnown.Zero & LowBits;
691         Known.One = LHSKnown.One & LowBits;
692 
693         // If LHS is non-negative or has all low bits zero, then the upper bits
694         // are all zero.
695         if (LHSKnown.isNonNegative() || LowBits.isSubsetOf(LHSKnown.Zero))
696           Known.Zero |= ~LowBits;
697 
698         // If LHS is negative and not all low bits are zero, then the upper bits
699         // are all one.
700         if (LHSKnown.isNegative() && LowBits.intersects(LHSKnown.One))
701           Known.One |= ~LowBits;
702 
703         assert(!Known.hasConflict() && "Bits known to be one AND zero?");
704         break;
705       }
706     }
707 
708     // The sign bit is the LHS's sign bit, except when the result of the
709     // remainder is zero.
710     if (DemandedMask.isSignBitSet()) {
711       computeKnownBits(I->getOperand(0), LHSKnown, Depth + 1, CxtI);
712       // If it's known zero, our sign bit is also zero.
713       if (LHSKnown.isNonNegative())
714         Known.makeNonNegative();
715     }
716     break;
717   }
718   case Instruction::URem: {
719     KnownBits Known2(BitWidth);
720     APInt AllOnes = APInt::getAllOnesValue(BitWidth);
721     if (SimplifyDemandedBits(I, 0, AllOnes, Known2, Depth + 1) ||
722         SimplifyDemandedBits(I, 1, AllOnes, Known2, Depth + 1))
723       return I;
724 
725     unsigned Leaders = Known2.countMinLeadingZeros();
726     Known.Zero = APInt::getHighBitsSet(BitWidth, Leaders) & DemandedMask;
727     break;
728   }
729   case Instruction::Call: {
730     bool KnownBitsComputed = false;
731     if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) {
732       switch (II->getIntrinsicID()) {
733       case Intrinsic::bswap: {
734         // If the only bits demanded come from one byte of the bswap result,
735         // just shift the input byte into position to eliminate the bswap.
736         unsigned NLZ = DemandedMask.countLeadingZeros();
737         unsigned NTZ = DemandedMask.countTrailingZeros();
738 
739         // Round NTZ down to the next byte.  If we have 11 trailing zeros, then
740         // we need all the bits down to bit 8.  Likewise, round NLZ.  If we
741         // have 14 leading zeros, round to 8.
742         NLZ &= ~7;
743         NTZ &= ~7;
744         // If we need exactly one byte, we can do this transformation.
745         if (BitWidth-NLZ-NTZ == 8) {
746           unsigned ResultBit = NTZ;
747           unsigned InputBit = BitWidth-NTZ-8;
748 
749           // Replace this with either a left or right shift to get the byte into
750           // the right place.
751           Instruction *NewVal;
752           if (InputBit > ResultBit)
753             NewVal = BinaryOperator::CreateLShr(II->getArgOperand(0),
754                     ConstantInt::get(I->getType(), InputBit-ResultBit));
755           else
756             NewVal = BinaryOperator::CreateShl(II->getArgOperand(0),
757                     ConstantInt::get(I->getType(), ResultBit-InputBit));
758           NewVal->takeName(I);
759           return InsertNewInstWith(NewVal, *I);
760         }
761         break;
762       }
763       case Intrinsic::fshr:
764       case Intrinsic::fshl: {
765         const APInt *SA;
766         if (!match(I->getOperand(2), m_APInt(SA)))
767           break;
768 
769         // Normalize to funnel shift left. APInt shifts of BitWidth are well-
770         // defined, so no need to special-case zero shifts here.
771         uint64_t ShiftAmt = SA->urem(BitWidth);
772         if (II->getIntrinsicID() == Intrinsic::fshr)
773           ShiftAmt = BitWidth - ShiftAmt;
774 
775         APInt DemandedMaskLHS(DemandedMask.lshr(ShiftAmt));
776         APInt DemandedMaskRHS(DemandedMask.shl(BitWidth - ShiftAmt));
777         if (SimplifyDemandedBits(I, 0, DemandedMaskLHS, LHSKnown, Depth + 1) ||
778             SimplifyDemandedBits(I, 1, DemandedMaskRHS, RHSKnown, Depth + 1))
779           return I;
780 
781         Known.Zero = LHSKnown.Zero.shl(ShiftAmt) |
782                      RHSKnown.Zero.lshr(BitWidth - ShiftAmt);
783         Known.One = LHSKnown.One.shl(ShiftAmt) |
784                     RHSKnown.One.lshr(BitWidth - ShiftAmt);
785         KnownBitsComputed = true;
786         break;
787       }
788       default: {
789         // Handle target specific intrinsics
790         Optional<Value *> V = targetSimplifyDemandedUseBitsIntrinsic(
791             *II, DemandedMask, Known, KnownBitsComputed);
792         if (V.hasValue())
793           return V.getValue();
794         break;
795       }
796       }
797     }
798 
799     if (!KnownBitsComputed)
800       computeKnownBits(V, Known, Depth, CxtI);
801     break;
802   }
803   }
804 
805   // If the client is only demanding bits that we know, return the known
806   // constant.
807   if (DemandedMask.isSubsetOf(Known.Zero|Known.One))
808     return Constant::getIntegerValue(VTy, Known.One);
809   return nullptr;
810 }
811 
812 /// Helper routine of SimplifyDemandedUseBits. It computes Known
813 /// bits. It also tries to handle simplifications that can be done based on
814 /// DemandedMask, but without modifying the Instruction.
815 Value *InstCombinerImpl::SimplifyMultipleUseDemandedBits(
816     Instruction *I, const APInt &DemandedMask, KnownBits &Known, unsigned Depth,
817     Instruction *CxtI) {
818   unsigned BitWidth = DemandedMask.getBitWidth();
819   Type *ITy = I->getType();
820 
821   KnownBits LHSKnown(BitWidth);
822   KnownBits RHSKnown(BitWidth);
823 
824   // Despite the fact that we can't simplify this instruction in all User's
825   // context, we can at least compute the known bits, and we can
826   // do simplifications that apply to *just* the one user if we know that
827   // this instruction has a simpler value in that context.
828   switch (I->getOpcode()) {
829   case Instruction::And: {
830     // If either the LHS or the RHS are Zero, the result is zero.
831     computeKnownBits(I->getOperand(1), RHSKnown, Depth + 1, CxtI);
832     computeKnownBits(I->getOperand(0), LHSKnown, Depth + 1,
833                      CxtI);
834 
835     Known = LHSKnown & RHSKnown;
836 
837     // If the client is only demanding bits that we know, return the known
838     // constant.
839     if (DemandedMask.isSubsetOf(Known.Zero | Known.One))
840       return Constant::getIntegerValue(ITy, Known.One);
841 
842     // If all of the demanded bits are known 1 on one side, return the other.
843     // These bits cannot contribute to the result of the 'and' in this
844     // context.
845     if (DemandedMask.isSubsetOf(LHSKnown.Zero | RHSKnown.One))
846       return I->getOperand(0);
847     if (DemandedMask.isSubsetOf(RHSKnown.Zero | LHSKnown.One))
848       return I->getOperand(1);
849 
850     break;
851   }
852   case Instruction::Or: {
853     // We can simplify (X|Y) -> X or Y in the user's context if we know that
854     // only bits from X or Y are demanded.
855 
856     // If either the LHS or the RHS are One, the result is One.
857     computeKnownBits(I->getOperand(1), RHSKnown, Depth + 1, CxtI);
858     computeKnownBits(I->getOperand(0), LHSKnown, Depth + 1,
859                      CxtI);
860 
861     Known = LHSKnown | RHSKnown;
862 
863     // If the client is only demanding bits that we know, return the known
864     // constant.
865     if (DemandedMask.isSubsetOf(Known.Zero | Known.One))
866       return Constant::getIntegerValue(ITy, Known.One);
867 
868     // If all of the demanded bits are known zero on one side, return the
869     // other.  These bits cannot contribute to the result of the 'or' in this
870     // context.
871     if (DemandedMask.isSubsetOf(LHSKnown.One | RHSKnown.Zero))
872       return I->getOperand(0);
873     if (DemandedMask.isSubsetOf(RHSKnown.One | LHSKnown.Zero))
874       return I->getOperand(1);
875 
876     break;
877   }
878   case Instruction::Xor: {
879     // We can simplify (X^Y) -> X or Y in the user's context if we know that
880     // only bits from X or Y are demanded.
881 
882     computeKnownBits(I->getOperand(1), RHSKnown, Depth + 1, CxtI);
883     computeKnownBits(I->getOperand(0), LHSKnown, Depth + 1,
884                      CxtI);
885 
886     Known = LHSKnown ^ RHSKnown;
887 
888     // If the client is only demanding bits that we know, return the known
889     // constant.
890     if (DemandedMask.isSubsetOf(Known.Zero | Known.One))
891       return Constant::getIntegerValue(ITy, Known.One);
892 
893     // If all of the demanded bits are known zero on one side, return the
894     // other.
895     if (DemandedMask.isSubsetOf(RHSKnown.Zero))
896       return I->getOperand(0);
897     if (DemandedMask.isSubsetOf(LHSKnown.Zero))
898       return I->getOperand(1);
899 
900     break;
901   }
902   case Instruction::AShr: {
903     // Compute the Known bits to simplify things downstream.
904     computeKnownBits(I, Known, Depth, CxtI);
905 
906     // If this user is only demanding bits that we know, return the known
907     // constant.
908     if (DemandedMask.isSubsetOf(Known.Zero | Known.One))
909       return Constant::getIntegerValue(ITy, Known.One);
910 
911     // If the right shift operand 0 is a result of a left shift by the same
912     // amount, this is probably a zero/sign extension, which may be unnecessary,
913     // if we do not demand any of the new sign bits. So, return the original
914     // operand instead.
915     const APInt *ShiftRC;
916     const APInt *ShiftLC;
917     Value *X;
918     unsigned BitWidth = DemandedMask.getBitWidth();
919     if (match(I,
920               m_AShr(m_Shl(m_Value(X), m_APInt(ShiftLC)), m_APInt(ShiftRC))) &&
921         ShiftLC == ShiftRC &&
922         DemandedMask.isSubsetOf(APInt::getLowBitsSet(
923             BitWidth, BitWidth - ShiftRC->getZExtValue()))) {
924       return X;
925     }
926 
927     break;
928   }
929   default:
930     // Compute the Known bits to simplify things downstream.
931     computeKnownBits(I, Known, Depth, CxtI);
932 
933     // If this user is only demanding bits that we know, return the known
934     // constant.
935     if (DemandedMask.isSubsetOf(Known.Zero|Known.One))
936       return Constant::getIntegerValue(ITy, Known.One);
937 
938     break;
939   }
940 
941   return nullptr;
942 }
943 
944 /// Helper routine of SimplifyDemandedUseBits. It tries to simplify
945 /// "E1 = (X lsr C1) << C2", where the C1 and C2 are constant, into
946 /// "E2 = X << (C2 - C1)" or "E2 = X >> (C1 - C2)", depending on the sign
947 /// of "C2-C1".
948 ///
949 /// Suppose E1 and E2 are generally different in bits S={bm, bm+1,
950 /// ..., bn}, without considering the specific value X is holding.
951 /// This transformation is legal iff one of following conditions is hold:
952 ///  1) All the bit in S are 0, in this case E1 == E2.
953 ///  2) We don't care those bits in S, per the input DemandedMask.
954 ///  3) Combination of 1) and 2). Some bits in S are 0, and we don't care the
955 ///     rest bits.
956 ///
957 /// Currently we only test condition 2).
958 ///
959 /// As with SimplifyDemandedUseBits, it returns NULL if the simplification was
960 /// not successful.
961 Value *InstCombinerImpl::simplifyShrShlDemandedBits(
962     Instruction *Shr, const APInt &ShrOp1, Instruction *Shl,
963     const APInt &ShlOp1, const APInt &DemandedMask, KnownBits &Known) {
964   if (!ShlOp1 || !ShrOp1)
965     return nullptr; // No-op.
966 
967   Value *VarX = Shr->getOperand(0);
968   Type *Ty = VarX->getType();
969   unsigned BitWidth = Ty->getScalarSizeInBits();
970   if (ShlOp1.uge(BitWidth) || ShrOp1.uge(BitWidth))
971     return nullptr; // Undef.
972 
973   unsigned ShlAmt = ShlOp1.getZExtValue();
974   unsigned ShrAmt = ShrOp1.getZExtValue();
975 
976   Known.One.clearAllBits();
977   Known.Zero.setLowBits(ShlAmt - 1);
978   Known.Zero &= DemandedMask;
979 
980   APInt BitMask1(APInt::getAllOnesValue(BitWidth));
981   APInt BitMask2(APInt::getAllOnesValue(BitWidth));
982 
983   bool isLshr = (Shr->getOpcode() == Instruction::LShr);
984   BitMask1 = isLshr ? (BitMask1.lshr(ShrAmt) << ShlAmt) :
985                       (BitMask1.ashr(ShrAmt) << ShlAmt);
986 
987   if (ShrAmt <= ShlAmt) {
988     BitMask2 <<= (ShlAmt - ShrAmt);
989   } else {
990     BitMask2 = isLshr ? BitMask2.lshr(ShrAmt - ShlAmt):
991                         BitMask2.ashr(ShrAmt - ShlAmt);
992   }
993 
994   // Check if condition-2 (see the comment to this function) is satified.
995   if ((BitMask1 & DemandedMask) == (BitMask2 & DemandedMask)) {
996     if (ShrAmt == ShlAmt)
997       return VarX;
998 
999     if (!Shr->hasOneUse())
1000       return nullptr;
1001 
1002     BinaryOperator *New;
1003     if (ShrAmt < ShlAmt) {
1004       Constant *Amt = ConstantInt::get(VarX->getType(), ShlAmt - ShrAmt);
1005       New = BinaryOperator::CreateShl(VarX, Amt);
1006       BinaryOperator *Orig = cast<BinaryOperator>(Shl);
1007       New->setHasNoSignedWrap(Orig->hasNoSignedWrap());
1008       New->setHasNoUnsignedWrap(Orig->hasNoUnsignedWrap());
1009     } else {
1010       Constant *Amt = ConstantInt::get(VarX->getType(), ShrAmt - ShlAmt);
1011       New = isLshr ? BinaryOperator::CreateLShr(VarX, Amt) :
1012                      BinaryOperator::CreateAShr(VarX, Amt);
1013       if (cast<BinaryOperator>(Shr)->isExact())
1014         New->setIsExact(true);
1015     }
1016 
1017     return InsertNewInstWith(New, *Shl);
1018   }
1019 
1020   return nullptr;
1021 }
1022 
1023 /// The specified value produces a vector with any number of elements.
1024 /// This method analyzes which elements of the operand are undef or poison and
1025 /// returns that information in UndefElts.
1026 ///
1027 /// DemandedElts contains the set of elements that are actually used by the
1028 /// caller, and by default (AllowMultipleUsers equals false) the value is
1029 /// simplified only if it has a single caller. If AllowMultipleUsers is set
1030 /// to true, DemandedElts refers to the union of sets of elements that are
1031 /// used by all callers.
1032 ///
1033 /// If the information about demanded elements can be used to simplify the
1034 /// operation, the operation is simplified, then the resultant value is
1035 /// returned.  This returns null if no change was made.
1036 Value *InstCombinerImpl::SimplifyDemandedVectorElts(Value *V,
1037                                                     APInt DemandedElts,
1038                                                     APInt &UndefElts,
1039                                                     unsigned Depth,
1040                                                     bool AllowMultipleUsers) {
1041   // Cannot analyze scalable type. The number of vector elements is not a
1042   // compile-time constant.
1043   if (isa<ScalableVectorType>(V->getType()))
1044     return nullptr;
1045 
1046   unsigned VWidth = cast<FixedVectorType>(V->getType())->getNumElements();
1047   APInt EltMask(APInt::getAllOnesValue(VWidth));
1048   assert((DemandedElts & ~EltMask) == 0 && "Invalid DemandedElts!");
1049 
1050   if (isa<UndefValue>(V)) {
1051     // If the entire vector is undef or poison, just return this info.
1052     UndefElts = EltMask;
1053     return nullptr;
1054   }
1055 
1056   if (DemandedElts.isNullValue()) { // If nothing is demanded, provide poison.
1057     UndefElts = EltMask;
1058     return PoisonValue::get(V->getType());
1059   }
1060 
1061   UndefElts = 0;
1062 
1063   if (auto *C = dyn_cast<Constant>(V)) {
1064     // Check if this is identity. If so, return 0 since we are not simplifying
1065     // anything.
1066     if (DemandedElts.isAllOnesValue())
1067       return nullptr;
1068 
1069     Type *EltTy = cast<VectorType>(V->getType())->getElementType();
1070     Constant *Poison = PoisonValue::get(EltTy);
1071     SmallVector<Constant*, 16> Elts;
1072     for (unsigned i = 0; i != VWidth; ++i) {
1073       if (!DemandedElts[i]) {   // If not demanded, set to poison.
1074         Elts.push_back(Poison);
1075         UndefElts.setBit(i);
1076         continue;
1077       }
1078 
1079       Constant *Elt = C->getAggregateElement(i);
1080       if (!Elt) return nullptr;
1081 
1082       Elts.push_back(Elt);
1083       if (isa<UndefValue>(Elt))   // Already undef or poison.
1084         UndefElts.setBit(i);
1085     }
1086 
1087     // If we changed the constant, return it.
1088     Constant *NewCV = ConstantVector::get(Elts);
1089     return NewCV != C ? NewCV : nullptr;
1090   }
1091 
1092   // Limit search depth.
1093   if (Depth == 10)
1094     return nullptr;
1095 
1096   if (!AllowMultipleUsers) {
1097     // If multiple users are using the root value, proceed with
1098     // simplification conservatively assuming that all elements
1099     // are needed.
1100     if (!V->hasOneUse()) {
1101       // Quit if we find multiple users of a non-root value though.
1102       // They'll be handled when it's their turn to be visited by
1103       // the main instcombine process.
1104       if (Depth != 0)
1105         // TODO: Just compute the UndefElts information recursively.
1106         return nullptr;
1107 
1108       // Conservatively assume that all elements are needed.
1109       DemandedElts = EltMask;
1110     }
1111   }
1112 
1113   Instruction *I = dyn_cast<Instruction>(V);
1114   if (!I) return nullptr;        // Only analyze instructions.
1115 
1116   bool MadeChange = false;
1117   auto simplifyAndSetOp = [&](Instruction *Inst, unsigned OpNum,
1118                               APInt Demanded, APInt &Undef) {
1119     auto *II = dyn_cast<IntrinsicInst>(Inst);
1120     Value *Op = II ? II->getArgOperand(OpNum) : Inst->getOperand(OpNum);
1121     if (Value *V = SimplifyDemandedVectorElts(Op, Demanded, Undef, Depth + 1)) {
1122       replaceOperand(*Inst, OpNum, V);
1123       MadeChange = true;
1124     }
1125   };
1126 
1127   APInt UndefElts2(VWidth, 0);
1128   APInt UndefElts3(VWidth, 0);
1129   switch (I->getOpcode()) {
1130   default: break;
1131 
1132   case Instruction::GetElementPtr: {
1133     // The LangRef requires that struct geps have all constant indices.  As
1134     // such, we can't convert any operand to partial undef.
1135     auto mayIndexStructType = [](GetElementPtrInst &GEP) {
1136       for (auto I = gep_type_begin(GEP), E = gep_type_end(GEP);
1137            I != E; I++)
1138         if (I.isStruct())
1139           return true;;
1140       return false;
1141     };
1142     if (mayIndexStructType(cast<GetElementPtrInst>(*I)))
1143       break;
1144 
1145     // Conservatively track the demanded elements back through any vector
1146     // operands we may have.  We know there must be at least one, or we
1147     // wouldn't have a vector result to get here. Note that we intentionally
1148     // merge the undef bits here since gepping with either an undef base or
1149     // index results in undef.
1150     for (unsigned i = 0; i < I->getNumOperands(); i++) {
1151       if (isa<UndefValue>(I->getOperand(i))) {
1152         // If the entire vector is undefined, just return this info.
1153         UndefElts = EltMask;
1154         return nullptr;
1155       }
1156       if (I->getOperand(i)->getType()->isVectorTy()) {
1157         APInt UndefEltsOp(VWidth, 0);
1158         simplifyAndSetOp(I, i, DemandedElts, UndefEltsOp);
1159         UndefElts |= UndefEltsOp;
1160       }
1161     }
1162 
1163     break;
1164   }
1165   case Instruction::InsertElement: {
1166     // If this is a variable index, we don't know which element it overwrites.
1167     // demand exactly the same input as we produce.
1168     ConstantInt *Idx = dyn_cast<ConstantInt>(I->getOperand(2));
1169     if (!Idx) {
1170       // Note that we can't propagate undef elt info, because we don't know
1171       // which elt is getting updated.
1172       simplifyAndSetOp(I, 0, DemandedElts, UndefElts2);
1173       break;
1174     }
1175 
1176     // The element inserted overwrites whatever was there, so the input demanded
1177     // set is simpler than the output set.
1178     unsigned IdxNo = Idx->getZExtValue();
1179     APInt PreInsertDemandedElts = DemandedElts;
1180     if (IdxNo < VWidth)
1181       PreInsertDemandedElts.clearBit(IdxNo);
1182 
1183     // If we only demand the element that is being inserted and that element
1184     // was extracted from the same index in another vector with the same type,
1185     // replace this insert with that other vector.
1186     // Note: This is attempted before the call to simplifyAndSetOp because that
1187     //       may change UndefElts to a value that does not match with Vec.
1188     Value *Vec;
1189     if (PreInsertDemandedElts == 0 &&
1190         match(I->getOperand(1),
1191               m_ExtractElt(m_Value(Vec), m_SpecificInt(IdxNo))) &&
1192         Vec->getType() == I->getType()) {
1193       return Vec;
1194     }
1195 
1196     simplifyAndSetOp(I, 0, PreInsertDemandedElts, UndefElts);
1197 
1198     // If this is inserting an element that isn't demanded, remove this
1199     // insertelement.
1200     if (IdxNo >= VWidth || !DemandedElts[IdxNo]) {
1201       Worklist.push(I);
1202       return I->getOperand(0);
1203     }
1204 
1205     // The inserted element is defined.
1206     UndefElts.clearBit(IdxNo);
1207     break;
1208   }
1209   case Instruction::ShuffleVector: {
1210     auto *Shuffle = cast<ShuffleVectorInst>(I);
1211     assert(Shuffle->getOperand(0)->getType() ==
1212            Shuffle->getOperand(1)->getType() &&
1213            "Expected shuffle operands to have same type");
1214     unsigned OpWidth = cast<FixedVectorType>(Shuffle->getOperand(0)->getType())
1215                            ->getNumElements();
1216     // Handle trivial case of a splat. Only check the first element of LHS
1217     // operand.
1218     if (all_of(Shuffle->getShuffleMask(), [](int Elt) { return Elt == 0; }) &&
1219         DemandedElts.isAllOnesValue()) {
1220       if (!isa<UndefValue>(I->getOperand(1))) {
1221         I->setOperand(1, UndefValue::get(I->getOperand(1)->getType()));
1222         MadeChange = true;
1223       }
1224       APInt LeftDemanded(OpWidth, 1);
1225       APInt LHSUndefElts(OpWidth, 0);
1226       simplifyAndSetOp(I, 0, LeftDemanded, LHSUndefElts);
1227       if (LHSUndefElts[0])
1228         UndefElts = EltMask;
1229       else
1230         UndefElts.clearAllBits();
1231       break;
1232     }
1233 
1234     APInt LeftDemanded(OpWidth, 0), RightDemanded(OpWidth, 0);
1235     for (unsigned i = 0; i < VWidth; i++) {
1236       if (DemandedElts[i]) {
1237         unsigned MaskVal = Shuffle->getMaskValue(i);
1238         if (MaskVal != -1u) {
1239           assert(MaskVal < OpWidth * 2 &&
1240                  "shufflevector mask index out of range!");
1241           if (MaskVal < OpWidth)
1242             LeftDemanded.setBit(MaskVal);
1243           else
1244             RightDemanded.setBit(MaskVal - OpWidth);
1245         }
1246       }
1247     }
1248 
1249     APInt LHSUndefElts(OpWidth, 0);
1250     simplifyAndSetOp(I, 0, LeftDemanded, LHSUndefElts);
1251 
1252     APInt RHSUndefElts(OpWidth, 0);
1253     simplifyAndSetOp(I, 1, RightDemanded, RHSUndefElts);
1254 
1255     // If this shuffle does not change the vector length and the elements
1256     // demanded by this shuffle are an identity mask, then this shuffle is
1257     // unnecessary.
1258     //
1259     // We are assuming canonical form for the mask, so the source vector is
1260     // operand 0 and operand 1 is not used.
1261     //
1262     // Note that if an element is demanded and this shuffle mask is undefined
1263     // for that element, then the shuffle is not considered an identity
1264     // operation. The shuffle prevents poison from the operand vector from
1265     // leaking to the result by replacing poison with an undefined value.
1266     if (VWidth == OpWidth) {
1267       bool IsIdentityShuffle = true;
1268       for (unsigned i = 0; i < VWidth; i++) {
1269         unsigned MaskVal = Shuffle->getMaskValue(i);
1270         if (DemandedElts[i] && i != MaskVal) {
1271           IsIdentityShuffle = false;
1272           break;
1273         }
1274       }
1275       if (IsIdentityShuffle)
1276         return Shuffle->getOperand(0);
1277     }
1278 
1279     bool NewUndefElts = false;
1280     unsigned LHSIdx = -1u, LHSValIdx = -1u;
1281     unsigned RHSIdx = -1u, RHSValIdx = -1u;
1282     bool LHSUniform = true;
1283     bool RHSUniform = true;
1284     for (unsigned i = 0; i < VWidth; i++) {
1285       unsigned MaskVal = Shuffle->getMaskValue(i);
1286       if (MaskVal == -1u) {
1287         UndefElts.setBit(i);
1288       } else if (!DemandedElts[i]) {
1289         NewUndefElts = true;
1290         UndefElts.setBit(i);
1291       } else if (MaskVal < OpWidth) {
1292         if (LHSUndefElts[MaskVal]) {
1293           NewUndefElts = true;
1294           UndefElts.setBit(i);
1295         } else {
1296           LHSIdx = LHSIdx == -1u ? i : OpWidth;
1297           LHSValIdx = LHSValIdx == -1u ? MaskVal : OpWidth;
1298           LHSUniform = LHSUniform && (MaskVal == i);
1299         }
1300       } else {
1301         if (RHSUndefElts[MaskVal - OpWidth]) {
1302           NewUndefElts = true;
1303           UndefElts.setBit(i);
1304         } else {
1305           RHSIdx = RHSIdx == -1u ? i : OpWidth;
1306           RHSValIdx = RHSValIdx == -1u ? MaskVal - OpWidth : OpWidth;
1307           RHSUniform = RHSUniform && (MaskVal - OpWidth == i);
1308         }
1309       }
1310     }
1311 
1312     // Try to transform shuffle with constant vector and single element from
1313     // this constant vector to single insertelement instruction.
1314     // shufflevector V, C, <v1, v2, .., ci, .., vm> ->
1315     // insertelement V, C[ci], ci-n
1316     if (OpWidth ==
1317         cast<FixedVectorType>(Shuffle->getType())->getNumElements()) {
1318       Value *Op = nullptr;
1319       Constant *Value = nullptr;
1320       unsigned Idx = -1u;
1321 
1322       // Find constant vector with the single element in shuffle (LHS or RHS).
1323       if (LHSIdx < OpWidth && RHSUniform) {
1324         if (auto *CV = dyn_cast<ConstantVector>(Shuffle->getOperand(0))) {
1325           Op = Shuffle->getOperand(1);
1326           Value = CV->getOperand(LHSValIdx);
1327           Idx = LHSIdx;
1328         }
1329       }
1330       if (RHSIdx < OpWidth && LHSUniform) {
1331         if (auto *CV = dyn_cast<ConstantVector>(Shuffle->getOperand(1))) {
1332           Op = Shuffle->getOperand(0);
1333           Value = CV->getOperand(RHSValIdx);
1334           Idx = RHSIdx;
1335         }
1336       }
1337       // Found constant vector with single element - convert to insertelement.
1338       if (Op && Value) {
1339         Instruction *New = InsertElementInst::Create(
1340             Op, Value, ConstantInt::get(Type::getInt32Ty(I->getContext()), Idx),
1341             Shuffle->getName());
1342         InsertNewInstWith(New, *Shuffle);
1343         return New;
1344       }
1345     }
1346     if (NewUndefElts) {
1347       // Add additional discovered undefs.
1348       SmallVector<int, 16> Elts;
1349       for (unsigned i = 0; i < VWidth; ++i) {
1350         if (UndefElts[i])
1351           Elts.push_back(UndefMaskElem);
1352         else
1353           Elts.push_back(Shuffle->getMaskValue(i));
1354       }
1355       Shuffle->setShuffleMask(Elts);
1356       MadeChange = true;
1357     }
1358     break;
1359   }
1360   case Instruction::Select: {
1361     // If this is a vector select, try to transform the select condition based
1362     // on the current demanded elements.
1363     SelectInst *Sel = cast<SelectInst>(I);
1364     if (Sel->getCondition()->getType()->isVectorTy()) {
1365       // TODO: We are not doing anything with UndefElts based on this call.
1366       // It is overwritten below based on the other select operands. If an
1367       // element of the select condition is known undef, then we are free to
1368       // choose the output value from either arm of the select. If we know that
1369       // one of those values is undef, then the output can be undef.
1370       simplifyAndSetOp(I, 0, DemandedElts, UndefElts);
1371     }
1372 
1373     // Next, see if we can transform the arms of the select.
1374     APInt DemandedLHS(DemandedElts), DemandedRHS(DemandedElts);
1375     if (auto *CV = dyn_cast<ConstantVector>(Sel->getCondition())) {
1376       for (unsigned i = 0; i < VWidth; i++) {
1377         // isNullValue() always returns false when called on a ConstantExpr.
1378         // Skip constant expressions to avoid propagating incorrect information.
1379         Constant *CElt = CV->getAggregateElement(i);
1380         if (isa<ConstantExpr>(CElt))
1381           continue;
1382         // TODO: If a select condition element is undef, we can demand from
1383         // either side. If one side is known undef, choosing that side would
1384         // propagate undef.
1385         if (CElt->isNullValue())
1386           DemandedLHS.clearBit(i);
1387         else
1388           DemandedRHS.clearBit(i);
1389       }
1390     }
1391 
1392     simplifyAndSetOp(I, 1, DemandedLHS, UndefElts2);
1393     simplifyAndSetOp(I, 2, DemandedRHS, UndefElts3);
1394 
1395     // Output elements are undefined if the element from each arm is undefined.
1396     // TODO: This can be improved. See comment in select condition handling.
1397     UndefElts = UndefElts2 & UndefElts3;
1398     break;
1399   }
1400   case Instruction::BitCast: {
1401     // Vector->vector casts only.
1402     VectorType *VTy = dyn_cast<VectorType>(I->getOperand(0)->getType());
1403     if (!VTy) break;
1404     unsigned InVWidth = cast<FixedVectorType>(VTy)->getNumElements();
1405     APInt InputDemandedElts(InVWidth, 0);
1406     UndefElts2 = APInt(InVWidth, 0);
1407     unsigned Ratio;
1408 
1409     if (VWidth == InVWidth) {
1410       // If we are converting from <4 x i32> -> <4 x f32>, we demand the same
1411       // elements as are demanded of us.
1412       Ratio = 1;
1413       InputDemandedElts = DemandedElts;
1414     } else if ((VWidth % InVWidth) == 0) {
1415       // If the number of elements in the output is a multiple of the number of
1416       // elements in the input then an input element is live if any of the
1417       // corresponding output elements are live.
1418       Ratio = VWidth / InVWidth;
1419       for (unsigned OutIdx = 0; OutIdx != VWidth; ++OutIdx)
1420         if (DemandedElts[OutIdx])
1421           InputDemandedElts.setBit(OutIdx / Ratio);
1422     } else if ((InVWidth % VWidth) == 0) {
1423       // If the number of elements in the input is a multiple of the number of
1424       // elements in the output then an input element is live if the
1425       // corresponding output element is live.
1426       Ratio = InVWidth / VWidth;
1427       for (unsigned InIdx = 0; InIdx != InVWidth; ++InIdx)
1428         if (DemandedElts[InIdx / Ratio])
1429           InputDemandedElts.setBit(InIdx);
1430     } else {
1431       // Unsupported so far.
1432       break;
1433     }
1434 
1435     simplifyAndSetOp(I, 0, InputDemandedElts, UndefElts2);
1436 
1437     if (VWidth == InVWidth) {
1438       UndefElts = UndefElts2;
1439     } else if ((VWidth % InVWidth) == 0) {
1440       // If the number of elements in the output is a multiple of the number of
1441       // elements in the input then an output element is undef if the
1442       // corresponding input element is undef.
1443       for (unsigned OutIdx = 0; OutIdx != VWidth; ++OutIdx)
1444         if (UndefElts2[OutIdx / Ratio])
1445           UndefElts.setBit(OutIdx);
1446     } else if ((InVWidth % VWidth) == 0) {
1447       // If the number of elements in the input is a multiple of the number of
1448       // elements in the output then an output element is undef if all of the
1449       // corresponding input elements are undef.
1450       for (unsigned OutIdx = 0; OutIdx != VWidth; ++OutIdx) {
1451         APInt SubUndef = UndefElts2.lshr(OutIdx * Ratio).zextOrTrunc(Ratio);
1452         if (SubUndef.countPopulation() == Ratio)
1453           UndefElts.setBit(OutIdx);
1454       }
1455     } else {
1456       llvm_unreachable("Unimp");
1457     }
1458     break;
1459   }
1460   case Instruction::FPTrunc:
1461   case Instruction::FPExt:
1462     simplifyAndSetOp(I, 0, DemandedElts, UndefElts);
1463     break;
1464 
1465   case Instruction::Call: {
1466     IntrinsicInst *II = dyn_cast<IntrinsicInst>(I);
1467     if (!II) break;
1468     switch (II->getIntrinsicID()) {
1469     case Intrinsic::masked_gather: // fallthrough
1470     case Intrinsic::masked_load: {
1471       // Subtlety: If we load from a pointer, the pointer must be valid
1472       // regardless of whether the element is demanded.  Doing otherwise risks
1473       // segfaults which didn't exist in the original program.
1474       APInt DemandedPtrs(APInt::getAllOnesValue(VWidth)),
1475         DemandedPassThrough(DemandedElts);
1476       if (auto *CV = dyn_cast<ConstantVector>(II->getOperand(2)))
1477         for (unsigned i = 0; i < VWidth; i++) {
1478           Constant *CElt = CV->getAggregateElement(i);
1479           if (CElt->isNullValue())
1480             DemandedPtrs.clearBit(i);
1481           else if (CElt->isAllOnesValue())
1482             DemandedPassThrough.clearBit(i);
1483         }
1484       if (II->getIntrinsicID() == Intrinsic::masked_gather)
1485         simplifyAndSetOp(II, 0, DemandedPtrs, UndefElts2);
1486       simplifyAndSetOp(II, 3, DemandedPassThrough, UndefElts3);
1487 
1488       // Output elements are undefined if the element from both sources are.
1489       // TODO: can strengthen via mask as well.
1490       UndefElts = UndefElts2 & UndefElts3;
1491       break;
1492     }
1493     default: {
1494       // Handle target specific intrinsics
1495       Optional<Value *> V = targetSimplifyDemandedVectorEltsIntrinsic(
1496           *II, DemandedElts, UndefElts, UndefElts2, UndefElts3,
1497           simplifyAndSetOp);
1498       if (V.hasValue())
1499         return V.getValue();
1500       break;
1501     }
1502     } // switch on IntrinsicID
1503     break;
1504   } // case Call
1505   } // switch on Opcode
1506 
1507   // TODO: We bail completely on integer div/rem and shifts because they have
1508   // UB/poison potential, but that should be refined.
1509   BinaryOperator *BO;
1510   if (match(I, m_BinOp(BO)) && !BO->isIntDivRem() && !BO->isShift()) {
1511     simplifyAndSetOp(I, 0, DemandedElts, UndefElts);
1512     simplifyAndSetOp(I, 1, DemandedElts, UndefElts2);
1513 
1514     // Any change to an instruction with potential poison must clear those flags
1515     // because we can not guarantee those constraints now. Other analysis may
1516     // determine that it is safe to re-apply the flags.
1517     if (MadeChange)
1518       BO->dropPoisonGeneratingFlags();
1519 
1520     // Output elements are undefined if both are undefined. Consider things
1521     // like undef & 0. The result is known zero, not undef.
1522     UndefElts &= UndefElts2;
1523   }
1524 
1525   // If we've proven all of the lanes undef, return an undef value.
1526   // TODO: Intersect w/demanded lanes
1527   if (UndefElts.isAllOnesValue())
1528     return UndefValue::get(I->getType());;
1529 
1530   return MadeChange ? I : nullptr;
1531 }
1532