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