LLVM 17.0.0git
InstCombineSimplifyDemanded.cpp
Go to the documentation of this file.
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"
21
22using namespace llvm;
23using 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.
30static 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.
56 unsigned BitWidth = Inst.getType()->getScalarSizeInBits();
57 KnownBits Known(BitWidth);
58 APInt DemandedMask(APInt::getAllOnes(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.
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.
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.isZero()) // Not demanding any bits from V.
128 return UndefValue::get(VTy);
129
131 return nullptr;
132
133 Instruction *I = dyn_cast<Instruction>(V);
134 if (!I) {
135 computeKnownBits(V, Known, Depth, CxtI);
136 return nullptr; // Only analyze instructions.
137 }
138
139 // If there are multiple uses of this value and we aren't at the root, then
140 // we can't do any simplifications of the operands, because DemandedMask
141 // only reflects the bits demanded by *one* of the users.
142 if (Depth != 0 && !I->hasOneUse())
143 return SimplifyMultipleUseDemandedBits(I, DemandedMask, Known, Depth, CxtI);
144
145 KnownBits LHSKnown(BitWidth), RHSKnown(BitWidth);
146
147 // If this is the root being simplified, allow it to have multiple uses,
148 // just set the DemandedMask to all bits so that we can try to simplify the
149 // operands. This allows visitTruncInst (for example) to simplify the
150 // operand of a trunc without duplicating all the logic below.
151 if (Depth == 0 && !V->hasOneUse())
152 DemandedMask.setAllBits();
153
154 // Update flags after simplifying an operand based on the fact that some high
155 // order bits are not demanded.
156 auto disableWrapFlagsBasedOnUnusedHighBits = [](Instruction *I,
157 unsigned NLZ) {
158 if (NLZ > 0) {
159 // Disable the nsw and nuw flags here: We can no longer guarantee that
160 // we won't wrap after simplification. Removing the nsw/nuw flags is
161 // legal here because the top bit is not demanded.
162 I->setHasNoSignedWrap(false);
163 I->setHasNoUnsignedWrap(false);
164 }
165 return I;
166 };
167
168 // If the high-bits of an ADD/SUB/MUL are not demanded, then we do not care
169 // about the high bits of the operands.
170 auto simplifyOperandsBasedOnUnusedHighBits = [&](APInt &DemandedFromOps) {
171 unsigned NLZ = DemandedMask.countl_zero();
172 // Right fill the mask of bits for the operands to demand the most
173 // significant bit and all those below it.
174 DemandedFromOps = APInt::getLowBitsSet(BitWidth, BitWidth - NLZ);
175 if (ShrinkDemandedConstant(I, 0, DemandedFromOps) ||
176 SimplifyDemandedBits(I, 0, DemandedFromOps, LHSKnown, Depth + 1) ||
177 ShrinkDemandedConstant(I, 1, DemandedFromOps) ||
178 SimplifyDemandedBits(I, 1, DemandedFromOps, RHSKnown, Depth + 1)) {
179 disableWrapFlagsBasedOnUnusedHighBits(I, NLZ);
180 return true;
181 }
182 return false;
183 };
184
185 switch (I->getOpcode()) {
186 default:
187 computeKnownBits(I, Known, Depth, CxtI);
188 break;
189 case Instruction::And: {
190 // If either the LHS or the RHS are Zero, the result is zero.
191 if (SimplifyDemandedBits(I, 1, DemandedMask, RHSKnown, Depth + 1) ||
192 SimplifyDemandedBits(I, 0, DemandedMask & ~RHSKnown.Zero, LHSKnown,
193 Depth + 1))
194 return I;
195 assert(!RHSKnown.hasConflict() && "Bits known to be one AND zero?");
196 assert(!LHSKnown.hasConflict() && "Bits known to be one AND zero?");
197
198 Known = analyzeKnownBitsFromAndXorOr(cast<Operator>(I), LHSKnown, RHSKnown,
199 Depth, DL, &AC, CxtI, &DT);
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 1 on one side, return the other.
207 // These bits cannot contribute to the result of the 'and'.
208 if (DemandedMask.isSubsetOf(LHSKnown.Zero | RHSKnown.One))
209 return I->getOperand(0);
210 if (DemandedMask.isSubsetOf(RHSKnown.Zero | LHSKnown.One))
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 & ~LHSKnown.Zero))
215 return I;
216
217 break;
218 }
219 case Instruction::Or: {
220 // If either the LHS or the RHS are One, the result is One.
221 if (SimplifyDemandedBits(I, 1, DemandedMask, RHSKnown, Depth + 1) ||
222 SimplifyDemandedBits(I, 0, DemandedMask & ~RHSKnown.One, LHSKnown,
223 Depth + 1))
224 return I;
225 assert(!RHSKnown.hasConflict() && "Bits known to be one AND zero?");
226 assert(!LHSKnown.hasConflict() && "Bits known to be one AND zero?");
227
228 Known = analyzeKnownBitsFromAndXorOr(cast<Operator>(I), LHSKnown, RHSKnown,
229 Depth, DL, &AC, CxtI, &DT);
230
231 // If the client is only demanding bits that we know, return the known
232 // constant.
233 if (DemandedMask.isSubsetOf(Known.Zero | Known.One))
234 return Constant::getIntegerValue(VTy, Known.One);
235
236 // If all of the demanded bits are known zero on one side, return the other.
237 // These bits cannot contribute to the result of the 'or'.
238 if (DemandedMask.isSubsetOf(LHSKnown.One | RHSKnown.Zero))
239 return I->getOperand(0);
240 if (DemandedMask.isSubsetOf(RHSKnown.One | LHSKnown.Zero))
241 return I->getOperand(1);
242
243 // If the RHS is a constant, see if we can simplify it.
244 if (ShrinkDemandedConstant(I, 1, DemandedMask))
245 return I;
246
247 break;
248 }
249 case Instruction::Xor: {
250 if (SimplifyDemandedBits(I, 1, DemandedMask, RHSKnown, Depth + 1) ||
251 SimplifyDemandedBits(I, 0, DemandedMask, LHSKnown, Depth + 1))
252 return I;
253 Value *LHS, *RHS;
254 if (DemandedMask == 1 &&
255 match(I->getOperand(0), m_Intrinsic<Intrinsic::ctpop>(m_Value(LHS))) &&
256 match(I->getOperand(1), m_Intrinsic<Intrinsic::ctpop>(m_Value(RHS)))) {
257 // (ctpop(X) ^ ctpop(Y)) & 1 --> ctpop(X^Y) & 1
260 auto *Xor = Builder.CreateXor(LHS, RHS);
261 return Builder.CreateUnaryIntrinsic(Intrinsic::ctpop, Xor);
262 }
263
264 assert(!RHSKnown.hasConflict() && "Bits known to be one AND zero?");
265 assert(!LHSKnown.hasConflict() && "Bits known to be one AND zero?");
266
267 Known = analyzeKnownBitsFromAndXorOr(cast<Operator>(I), LHSKnown, RHSKnown,
268 Depth, DL, &AC, CxtI, &DT);
269
270 // If the client is only demanding bits that we know, return the known
271 // constant.
272 if (DemandedMask.isSubsetOf(Known.Zero | Known.One))
273 return Constant::getIntegerValue(VTy, Known.One);
274
275 // If all of the demanded bits are known zero on one side, return the other.
276 // These bits cannot contribute to the result of the 'xor'.
277 if (DemandedMask.isSubsetOf(RHSKnown.Zero))
278 return I->getOperand(0);
279 if (DemandedMask.isSubsetOf(LHSKnown.Zero))
280 return I->getOperand(1);
281
282 // If all of the demanded bits are known to be zero on one side or the
283 // other, turn this into an *inclusive* or.
284 // e.g. (A & C1)^(B & C2) -> (A & C1)|(B & C2) iff C1&C2 == 0
285 if (DemandedMask.isSubsetOf(RHSKnown.Zero | LHSKnown.Zero)) {
286 Instruction *Or =
287 BinaryOperator::CreateOr(I->getOperand(0), I->getOperand(1),
288 I->getName());
289 return InsertNewInstWith(Or, *I);
290 }
291
292 // If all of the demanded bits on one side are known, and all of the set
293 // bits on that side are also known to be set on the other side, turn this
294 // into an AND, as we know the bits will be cleared.
295 // e.g. (X | C1) ^ C2 --> (X | C1) & ~C2 iff (C1&C2) == C2
296 if (DemandedMask.isSubsetOf(RHSKnown.Zero|RHSKnown.One) &&
297 RHSKnown.One.isSubsetOf(LHSKnown.One)) {
299 ~RHSKnown.One & DemandedMask);
300 Instruction *And = BinaryOperator::CreateAnd(I->getOperand(0), AndC);
301 return InsertNewInstWith(And, *I);
302 }
303
304 // If the RHS is a constant, see if we can change it. Don't alter a -1
305 // constant because that's a canonical 'not' op, and that is better for
306 // combining, SCEV, and codegen.
307 const APInt *C;
308 if (match(I->getOperand(1), m_APInt(C)) && !C->isAllOnes()) {
309 if ((*C | ~DemandedMask).isAllOnes()) {
310 // Force bits to 1 to create a 'not' op.
311 I->setOperand(1, ConstantInt::getAllOnesValue(VTy));
312 return I;
313 }
314 // If we can't turn this into a 'not', try to shrink the constant.
315 if (ShrinkDemandedConstant(I, 1, DemandedMask))
316 return I;
317 }
318
319 // If our LHS is an 'and' and if it has one use, and if any of the bits we
320 // are flipping are known to be set, then the xor is just resetting those
321 // bits to zero. We can just knock out bits from the 'and' and the 'xor',
322 // simplifying both of them.
323 if (Instruction *LHSInst = dyn_cast<Instruction>(I->getOperand(0))) {
324 ConstantInt *AndRHS, *XorRHS;
325 if (LHSInst->getOpcode() == Instruction::And && LHSInst->hasOneUse() &&
326 match(I->getOperand(1), m_ConstantInt(XorRHS)) &&
327 match(LHSInst->getOperand(1), m_ConstantInt(AndRHS)) &&
328 (LHSKnown.One & RHSKnown.One & DemandedMask) != 0) {
329 APInt NewMask = ~(LHSKnown.One & RHSKnown.One & DemandedMask);
330
331 Constant *AndC = ConstantInt::get(VTy, NewMask & AndRHS->getValue());
332 Instruction *NewAnd = BinaryOperator::CreateAnd(I->getOperand(0), AndC);
333 InsertNewInstWith(NewAnd, *I);
334
335 Constant *XorC = ConstantInt::get(VTy, NewMask & XorRHS->getValue());
336 Instruction *NewXor = BinaryOperator::CreateXor(NewAnd, XorC);
337 return InsertNewInstWith(NewXor, *I);
338 }
339 }
340 break;
341 }
342 case Instruction::Select: {
343 if (SimplifyDemandedBits(I, 2, DemandedMask, RHSKnown, Depth + 1) ||
344 SimplifyDemandedBits(I, 1, DemandedMask, LHSKnown, Depth + 1))
345 return I;
346 assert(!RHSKnown.hasConflict() && "Bits known to be one AND zero?");
347 assert(!LHSKnown.hasConflict() && "Bits known to be one AND zero?");
348
349 // If the operands are constants, see if we can simplify them.
350 // This is similar to ShrinkDemandedConstant, but for a select we want to
351 // try to keep the selected constants the same as icmp value constants, if
352 // we can. This helps not break apart (or helps put back together)
353 // canonical patterns like min and max.
354 auto CanonicalizeSelectConstant = [](Instruction *I, unsigned OpNo,
355 const APInt &DemandedMask) {
356 const APInt *SelC;
357 if (!match(I->getOperand(OpNo), m_APInt(SelC)))
358 return false;
359
360 // Get the constant out of the ICmp, if there is one.
361 // Only try this when exactly 1 operand is a constant (if both operands
362 // are constant, the icmp should eventually simplify). Otherwise, we may
363 // invert the transform that reduces set bits and infinite-loop.
364 Value *X;
365 const APInt *CmpC;
367 if (!match(I->getOperand(0), m_ICmp(Pred, m_Value(X), m_APInt(CmpC))) ||
368 isa<Constant>(X) || CmpC->getBitWidth() != SelC->getBitWidth())
369 return ShrinkDemandedConstant(I, OpNo, DemandedMask);
370
371 // If the constant is already the same as the ICmp, leave it as-is.
372 if (*CmpC == *SelC)
373 return false;
374 // If the constants are not already the same, but can be with the demand
375 // mask, use the constant value from the ICmp.
376 if ((*CmpC & DemandedMask) == (*SelC & DemandedMask)) {
377 I->setOperand(OpNo, ConstantInt::get(I->getType(), *CmpC));
378 return true;
379 }
380 return ShrinkDemandedConstant(I, OpNo, DemandedMask);
381 };
382 if (CanonicalizeSelectConstant(I, 1, DemandedMask) ||
383 CanonicalizeSelectConstant(I, 2, DemandedMask))
384 return I;
385
386 // Only known if known in both the LHS and RHS.
387 Known = KnownBits::commonBits(LHSKnown, RHSKnown);
388 break;
389 }
390 case Instruction::Trunc: {
391 // If we do not demand the high bits of a right-shifted and truncated value,
392 // then we may be able to truncate it before the shift.
393 Value *X;
394 const APInt *C;
395 if (match(I->getOperand(0), m_OneUse(m_LShr(m_Value(X), m_APInt(C))))) {
396 // The shift amount must be valid (not poison) in the narrow type, and
397 // it must not be greater than the high bits demanded of the result.
398 if (C->ult(VTy->getScalarSizeInBits()) &&
399 C->ule(DemandedMask.countl_zero())) {
400 // trunc (lshr X, C) --> lshr (trunc X), C
403 Value *Trunc = Builder.CreateTrunc(X, VTy);
404 return Builder.CreateLShr(Trunc, C->getZExtValue());
405 }
406 }
407 }
408 [[fallthrough]];
409 case Instruction::ZExt: {
410 unsigned SrcBitWidth = I->getOperand(0)->getType()->getScalarSizeInBits();
411
412 APInt InputDemandedMask = DemandedMask.zextOrTrunc(SrcBitWidth);
413 KnownBits InputKnown(SrcBitWidth);
414 if (SimplifyDemandedBits(I, 0, InputDemandedMask, InputKnown, Depth + 1))
415 return I;
416 assert(InputKnown.getBitWidth() == SrcBitWidth && "Src width changed?");
417 Known = InputKnown.zextOrTrunc(BitWidth);
418 assert(!Known.hasConflict() && "Bits known to be one AND zero?");
419 break;
420 }
421 case Instruction::BitCast:
422 if (!I->getOperand(0)->getType()->isIntOrIntVectorTy())
423 return nullptr; // vector->int or fp->int?
424
425 if (auto *DstVTy = dyn_cast<VectorType>(VTy)) {
426 if (auto *SrcVTy = dyn_cast<VectorType>(I->getOperand(0)->getType())) {
427 if (isa<ScalableVectorType>(DstVTy) ||
428 isa<ScalableVectorType>(SrcVTy) ||
429 cast<FixedVectorType>(DstVTy)->getNumElements() !=
430 cast<FixedVectorType>(SrcVTy)->getNumElements())
431 // Don't touch a bitcast between vectors of different element counts.
432 return nullptr;
433 } else
434 // Don't touch a scalar-to-vector bitcast.
435 return nullptr;
436 } else if (I->getOperand(0)->getType()->isVectorTy())
437 // Don't touch a vector-to-scalar bitcast.
438 return nullptr;
439
440 if (SimplifyDemandedBits(I, 0, DemandedMask, Known, Depth + 1))
441 return I;
442 assert(!Known.hasConflict() && "Bits known to be one AND zero?");
443 break;
444 case Instruction::SExt: {
445 // Compute the bits in the result that are not present in the input.
446 unsigned SrcBitWidth = I->getOperand(0)->getType()->getScalarSizeInBits();
447
448 APInt InputDemandedBits = DemandedMask.trunc(SrcBitWidth);
449
450 // If any of the sign extended bits are demanded, we know that the sign
451 // bit is demanded.
452 if (DemandedMask.getActiveBits() > SrcBitWidth)
453 InputDemandedBits.setBit(SrcBitWidth-1);
454
455 KnownBits InputKnown(SrcBitWidth);
456 if (SimplifyDemandedBits(I, 0, InputDemandedBits, InputKnown, Depth + 1))
457 return I;
458
459 // If the input sign bit is known zero, or if the NewBits are not demanded
460 // convert this into a zero extension.
461 if (InputKnown.isNonNegative() ||
462 DemandedMask.getActiveBits() <= SrcBitWidth) {
463 // Convert to ZExt cast.
464 CastInst *NewCast = new ZExtInst(I->getOperand(0), VTy, I->getName());
465 return InsertNewInstWith(NewCast, *I);
466 }
467
468 // If the sign bit of the input is known set or clear, then we know the
469 // top bits of the result.
470 Known = InputKnown.sext(BitWidth);
471 assert(!Known.hasConflict() && "Bits known to be one AND zero?");
472 break;
473 }
474 case Instruction::Add: {
475 if ((DemandedMask & 1) == 0) {
476 // If we do not need the low bit, try to convert bool math to logic:
477 // add iN (zext i1 X), (sext i1 Y) --> sext (~X & Y) to iN
478 Value *X, *Y;
480 m_OneUse(m_SExt(m_Value(Y))))) &&
481 X->getType()->isIntOrIntVectorTy(1) && X->getType() == Y->getType()) {
482 // Truth table for inputs and output signbits:
483 // X:0 | X:1
484 // ----------
485 // Y:0 | 0 | 0 |
486 // Y:1 | -1 | 0 |
487 // ----------
491 return Builder.CreateSExt(AndNot, VTy);
492 }
493
494 // add iN (sext i1 X), (sext i1 Y) --> sext (X | Y) to iN
495 // TODO: Relax the one-use checks because we are removing an instruction?
497 m_OneUse(m_SExt(m_Value(Y))))) &&
498 X->getType()->isIntOrIntVectorTy(1) && X->getType() == Y->getType()) {
499 // Truth table for inputs and output signbits:
500 // X:0 | X:1
501 // -----------
502 // Y:0 | -1 | -1 |
503 // Y:1 | -1 | 0 |
504 // -----------
507 Value *Or = Builder.CreateOr(X, Y);
508 return Builder.CreateSExt(Or, VTy);
509 }
510 }
511
512 // Right fill the mask of bits for the operands to demand the most
513 // significant bit and all those below it.
514 unsigned NLZ = DemandedMask.countl_zero();
515 APInt DemandedFromOps = APInt::getLowBitsSet(BitWidth, BitWidth - NLZ);
516 if (ShrinkDemandedConstant(I, 1, DemandedFromOps) ||
517 SimplifyDemandedBits(I, 1, DemandedFromOps, RHSKnown, Depth + 1))
518 return disableWrapFlagsBasedOnUnusedHighBits(I, NLZ);
519
520 // If low order bits are not demanded and known to be zero in one operand,
521 // then we don't need to demand them from the other operand, since they
522 // can't cause overflow into any bits that are demanded in the result.
523 unsigned NTZ = (~DemandedMask & RHSKnown.Zero).countr_one();
524 APInt DemandedFromLHS = DemandedFromOps;
525 DemandedFromLHS.clearLowBits(NTZ);
526 if (ShrinkDemandedConstant(I, 0, DemandedFromLHS) ||
527 SimplifyDemandedBits(I, 0, DemandedFromLHS, LHSKnown, Depth + 1))
528 return disableWrapFlagsBasedOnUnusedHighBits(I, NLZ);
529
530 // If we are known to be adding zeros to every bit below
531 // the highest demanded bit, we just return the other side.
532 if (DemandedFromOps.isSubsetOf(RHSKnown.Zero))
533 return I->getOperand(0);
534 if (DemandedFromOps.isSubsetOf(LHSKnown.Zero))
535 return I->getOperand(1);
536
537 // Otherwise just compute the known bits of the result.
538 bool NSW = cast<OverflowingBinaryOperator>(I)->hasNoSignedWrap();
539 Known = KnownBits::computeForAddSub(true, NSW, LHSKnown, RHSKnown);
540 break;
541 }
542 case Instruction::Sub: {
543 // Right fill the mask of bits for the operands to demand the most
544 // significant bit and all those below it.
545 unsigned NLZ = DemandedMask.countl_zero();
546 APInt DemandedFromOps = APInt::getLowBitsSet(BitWidth, BitWidth - NLZ);
547 if (ShrinkDemandedConstant(I, 1, DemandedFromOps) ||
548 SimplifyDemandedBits(I, 1, DemandedFromOps, RHSKnown, Depth + 1))
549 return disableWrapFlagsBasedOnUnusedHighBits(I, NLZ);
550
551 // If low order bits are not demanded and are known to be zero in RHS,
552 // then we don't need to demand them from LHS, since they can't cause a
553 // borrow from any bits that are demanded in the result.
554 unsigned NTZ = (~DemandedMask & RHSKnown.Zero).countr_one();
555 APInt DemandedFromLHS = DemandedFromOps;
556 DemandedFromLHS.clearLowBits(NTZ);
557 if (ShrinkDemandedConstant(I, 0, DemandedFromLHS) ||
558 SimplifyDemandedBits(I, 0, DemandedFromLHS, LHSKnown, Depth + 1))
559 return disableWrapFlagsBasedOnUnusedHighBits(I, NLZ);
560
561 // If we are known to be subtracting zeros from every bit below
562 // the highest demanded bit, we just return the other side.
563 if (DemandedFromOps.isSubsetOf(RHSKnown.Zero))
564 return I->getOperand(0);
565 // We can't do this with the LHS for subtraction, unless we are only
566 // demanding the LSB.
567 if (DemandedFromOps.isOne() && DemandedFromOps.isSubsetOf(LHSKnown.Zero))
568 return I->getOperand(1);
569
570 // Otherwise just compute the known bits of the result.
571 bool NSW = cast<OverflowingBinaryOperator>(I)->hasNoSignedWrap();
572 Known = KnownBits::computeForAddSub(false, NSW, LHSKnown, RHSKnown);
573 break;
574 }
575 case Instruction::Mul: {
576 APInt DemandedFromOps;
577 if (simplifyOperandsBasedOnUnusedHighBits(DemandedFromOps))
578 return I;
579
580 if (DemandedMask.isPowerOf2()) {
581 // The LSB of X*Y is set only if (X & 1) == 1 and (Y & 1) == 1.
582 // If we demand exactly one bit N and we have "X * (C' << N)" where C' is
583 // odd (has LSB set), then the left-shifted low bit of X is the answer.
584 unsigned CTZ = DemandedMask.countr_zero();
585 const APInt *C;
586 if (match(I->getOperand(1), m_APInt(C)) && C->countr_zero() == CTZ) {
587 Constant *ShiftC = ConstantInt::get(VTy, CTZ);
588 Instruction *Shl = BinaryOperator::CreateShl(I->getOperand(0), ShiftC);
589 return InsertNewInstWith(Shl, *I);
590 }
591 }
592 // For a squared value "X * X", the bottom 2 bits are 0 and X[0] because:
593 // X * X is odd iff X is odd.
594 // 'Quadratic Reciprocity': X * X -> 0 for bit[1]
595 if (I->getOperand(0) == I->getOperand(1) && DemandedMask.ult(4)) {
596 Constant *One = ConstantInt::get(VTy, 1);
597 Instruction *And1 = BinaryOperator::CreateAnd(I->getOperand(0), One);
598 return InsertNewInstWith(And1, *I);
599 }
600
601 computeKnownBits(I, Known, Depth, CxtI);
602 break;
603 }
604 case Instruction::Shl: {
605 const APInt *SA;
606 if (match(I->getOperand(1), m_APInt(SA))) {
607 const APInt *ShrAmt;
608 if (match(I->getOperand(0), m_Shr(m_Value(), m_APInt(ShrAmt))))
609 if (Instruction *Shr = dyn_cast<Instruction>(I->getOperand(0)))
610 if (Value *R = simplifyShrShlDemandedBits(Shr, *ShrAmt, I, *SA,
611 DemandedMask, Known))
612 return R;
613
614 // TODO: If we only want bits that already match the signbit then we don't
615 // need to shift.
616
617 // If we can pre-shift a right-shifted constant to the left without
618 // losing any high bits amd we don't demand the low bits, then eliminate
619 // the left-shift:
620 // (C >> X) << LeftShiftAmtC --> (C << RightShiftAmtC) >> X
621 uint64_t ShiftAmt = SA->getLimitedValue(BitWidth-1);
622 Value *X;
623 Constant *C;
624 if (DemandedMask.countr_zero() >= ShiftAmt &&
625 match(I->getOperand(0), m_LShr(m_ImmConstant(C), m_Value(X)))) {
626 Constant *LeftShiftAmtC = ConstantInt::get(VTy, ShiftAmt);
627 Constant *NewC = ConstantExpr::getShl(C, LeftShiftAmtC);
628 if (ConstantExpr::getLShr(NewC, LeftShiftAmtC) == C) {
629 Instruction *Lshr = BinaryOperator::CreateLShr(NewC, X);
630 return InsertNewInstWith(Lshr, *I);
631 }
632 }
633
634 APInt DemandedMaskIn(DemandedMask.lshr(ShiftAmt));
635
636 // If the shift is NUW/NSW, then it does demand the high bits.
637 ShlOperator *IOp = cast<ShlOperator>(I);
638 if (IOp->hasNoSignedWrap())
639 DemandedMaskIn.setHighBits(ShiftAmt+1);
640 else if (IOp->hasNoUnsignedWrap())
641 DemandedMaskIn.setHighBits(ShiftAmt);
642
643 if (SimplifyDemandedBits(I, 0, DemandedMaskIn, Known, Depth + 1))
644 return I;
645 assert(!Known.hasConflict() && "Bits known to be one AND zero?");
646
647 bool SignBitZero = Known.Zero.isSignBitSet();
648 bool SignBitOne = Known.One.isSignBitSet();
649 Known.Zero <<= ShiftAmt;
650 Known.One <<= ShiftAmt;
651 // low bits known zero.
652 if (ShiftAmt)
653 Known.Zero.setLowBits(ShiftAmt);
654
655 // If this shift has "nsw" keyword, then the result is either a poison
656 // value or has the same sign bit as the first operand.
657 if (IOp->hasNoSignedWrap()) {
658 if (SignBitZero)
659 Known.Zero.setSignBit();
660 else if (SignBitOne)
661 Known.One.setSignBit();
662 if (Known.hasConflict())
663 return UndefValue::get(VTy);
664 }
665 } else {
666 // This is a variable shift, so we can't shift the demand mask by a known
667 // amount. But if we are not demanding high bits, then we are not
668 // demanding those bits from the pre-shifted operand either.
669 if (unsigned CTLZ = DemandedMask.countl_zero()) {
670 APInt DemandedFromOp(APInt::getLowBitsSet(BitWidth, BitWidth - CTLZ));
671 if (SimplifyDemandedBits(I, 0, DemandedFromOp, Known, Depth + 1)) {
672 // We can't guarantee that nsw/nuw hold after simplifying the operand.
673 I->dropPoisonGeneratingFlags();
674 return I;
675 }
676 }
677 computeKnownBits(I, Known, Depth, CxtI);
678 }
679 break;
680 }
681 case Instruction::LShr: {
682 const APInt *SA;
683 if (match(I->getOperand(1), m_APInt(SA))) {
684 uint64_t ShiftAmt = SA->getLimitedValue(BitWidth-1);
685
686 // If we are just demanding the shifted sign bit and below, then this can
687 // be treated as an ASHR in disguise.
688 if (DemandedMask.countl_zero() >= ShiftAmt) {
689 // If we only want bits that already match the signbit then we don't
690 // need to shift.
691 unsigned NumHiDemandedBits = BitWidth - DemandedMask.countr_zero();
692 unsigned SignBits =
693 ComputeNumSignBits(I->getOperand(0), Depth + 1, CxtI);
694 if (SignBits >= NumHiDemandedBits)
695 return I->getOperand(0);
696
697 // If we can pre-shift a left-shifted constant to the right without
698 // losing any low bits (we already know we don't demand the high bits),
699 // then eliminate the right-shift:
700 // (C << X) >> RightShiftAmtC --> (C >> RightShiftAmtC) << X
701 Value *X;
702 Constant *C;
703 if (match(I->getOperand(0), m_Shl(m_ImmConstant(C), m_Value(X)))) {
704 Constant *RightShiftAmtC = ConstantInt::get(VTy, ShiftAmt);
705 Constant *NewC = ConstantExpr::getLShr(C, RightShiftAmtC);
706 if (ConstantExpr::getShl(NewC, RightShiftAmtC) == C) {
707 Instruction *Shl = BinaryOperator::CreateShl(NewC, X);
708 return InsertNewInstWith(Shl, *I);
709 }
710 }
711 }
712
713 // Unsigned shift right.
714 APInt DemandedMaskIn(DemandedMask.shl(ShiftAmt));
715
716 // If the shift is exact, then it does demand the low bits (and knows that
717 // they are zero).
718 if (cast<LShrOperator>(I)->isExact())
719 DemandedMaskIn.setLowBits(ShiftAmt);
720
721 if (SimplifyDemandedBits(I, 0, DemandedMaskIn, Known, Depth + 1))
722 return I;
723 assert(!Known.hasConflict() && "Bits known to be one AND zero?");
724 Known.Zero.lshrInPlace(ShiftAmt);
725 Known.One.lshrInPlace(ShiftAmt);
726 if (ShiftAmt)
727 Known.Zero.setHighBits(ShiftAmt); // high bits known zero.
728 } else {
729 computeKnownBits(I, Known, Depth, CxtI);
730 }
731 break;
732 }
733 case Instruction::AShr: {
734 unsigned SignBits = ComputeNumSignBits(I->getOperand(0), Depth + 1, CxtI);
735
736 // If we only want bits that already match the signbit then we don't need
737 // to shift.
738 unsigned NumHiDemandedBits = BitWidth - DemandedMask.countr_zero();
739 if (SignBits >= NumHiDemandedBits)
740 return I->getOperand(0);
741
742 // If this is an arithmetic shift right and only the low-bit is set, we can
743 // always convert this into a logical shr, even if the shift amount is
744 // variable. The low bit of the shift cannot be an input sign bit unless
745 // the shift amount is >= the size of the datatype, which is undefined.
746 if (DemandedMask.isOne()) {
747 // Perform the logical shift right.
748 Instruction *NewVal = BinaryOperator::CreateLShr(
749 I->getOperand(0), I->getOperand(1), I->getName());
750 return InsertNewInstWith(NewVal, *I);
751 }
752
753 const APInt *SA;
754 if (match(I->getOperand(1), m_APInt(SA))) {
755 uint32_t ShiftAmt = SA->getLimitedValue(BitWidth-1);
756
757 // Signed shift right.
758 APInt DemandedMaskIn(DemandedMask.shl(ShiftAmt));
759 // If any of the high bits are demanded, we should set the sign bit as
760 // demanded.
761 if (DemandedMask.countl_zero() <= ShiftAmt)
762 DemandedMaskIn.setSignBit();
763
764 // If the shift is exact, then it does demand the low bits (and knows that
765 // they are zero).
766 if (cast<AShrOperator>(I)->isExact())
767 DemandedMaskIn.setLowBits(ShiftAmt);
768
769 if (SimplifyDemandedBits(I, 0, DemandedMaskIn, Known, Depth + 1))
770 return I;
771
772 assert(!Known.hasConflict() && "Bits known to be one AND zero?");
773 // Compute the new bits that are at the top now plus sign bits.
775 BitWidth, std::min(SignBits + ShiftAmt - 1, BitWidth)));
776 Known.Zero.lshrInPlace(ShiftAmt);
777 Known.One.lshrInPlace(ShiftAmt);
778
779 // If the input sign bit is known to be zero, or if none of the top bits
780 // are demanded, turn this into an unsigned shift right.
781 assert(BitWidth > ShiftAmt && "Shift amount not saturated?");
782 if (Known.Zero[BitWidth-ShiftAmt-1] ||
783 !DemandedMask.intersects(HighBits)) {
784 BinaryOperator *LShr = BinaryOperator::CreateLShr(I->getOperand(0),
785 I->getOperand(1));
786 LShr->setIsExact(cast<BinaryOperator>(I)->isExact());
787 return InsertNewInstWith(LShr, *I);
788 } else if (Known.One[BitWidth-ShiftAmt-1]) { // New bits are known one.
789 Known.One |= HighBits;
790 }
791 } else {
792 computeKnownBits(I, Known, Depth, CxtI);
793 }
794 break;
795 }
796 case Instruction::UDiv: {
797 // UDiv doesn't demand low bits that are zero in the divisor.
798 const APInt *SA;
799 if (match(I->getOperand(1), m_APInt(SA))) {
800 // TODO: Take the demanded mask of the result into account.
801 unsigned RHSTrailingZeros = SA->countr_zero();
802 APInt DemandedMaskIn =
803 APInt::getHighBitsSet(BitWidth, BitWidth - RHSTrailingZeros);
804 if (SimplifyDemandedBits(I, 0, DemandedMaskIn, LHSKnown, Depth + 1)) {
805 // We can't guarantee that "exact" is still true after changing the
806 // the dividend.
807 I->dropPoisonGeneratingFlags();
808 return I;
809 }
810
811 // Increase high zero bits from the input.
812 Known.Zero.setHighBits(
813 std::min(BitWidth, LHSKnown.Zero.countl_one() + RHSTrailingZeros));
814 } else {
815 computeKnownBits(I, Known, Depth, CxtI);
816 }
817 break;
818 }
819 case Instruction::SRem: {
820 const APInt *Rem;
821 if (match(I->getOperand(1), m_APInt(Rem))) {
822 // X % -1 demands all the bits because we don't want to introduce
823 // INT_MIN % -1 (== undef) by accident.
824 if (Rem->isAllOnes())
825 break;
826 APInt RA = Rem->abs();
827 if (RA.isPowerOf2()) {
828 if (DemandedMask.ult(RA)) // srem won't affect demanded bits
829 return I->getOperand(0);
830
831 APInt LowBits = RA - 1;
832 APInt Mask2 = LowBits | APInt::getSignMask(BitWidth);
833 if (SimplifyDemandedBits(I, 0, Mask2, LHSKnown, Depth + 1))
834 return I;
835
836 // The low bits of LHS are unchanged by the srem.
837 Known.Zero = LHSKnown.Zero & LowBits;
838 Known.One = LHSKnown.One & LowBits;
839
840 // If LHS is non-negative or has all low bits zero, then the upper bits
841 // are all zero.
842 if (LHSKnown.isNonNegative() || LowBits.isSubsetOf(LHSKnown.Zero))
843 Known.Zero |= ~LowBits;
844
845 // If LHS is negative and not all low bits are zero, then the upper bits
846 // are all one.
847 if (LHSKnown.isNegative() && LowBits.intersects(LHSKnown.One))
848 Known.One |= ~LowBits;
849
850 assert(!Known.hasConflict() && "Bits known to be one AND zero?");
851 break;
852 }
853 }
854
855 // The sign bit is the LHS's sign bit, except when the result of the
856 // remainder is zero.
857 if (DemandedMask.isSignBitSet()) {
858 computeKnownBits(I->getOperand(0), LHSKnown, Depth + 1, CxtI);
859 // If it's known zero, our sign bit is also zero.
860 if (LHSKnown.isNonNegative())
861 Known.makeNonNegative();
862 }
863 break;
864 }
865 case Instruction::URem: {
866 KnownBits Known2(BitWidth);
868 if (SimplifyDemandedBits(I, 0, AllOnes, Known2, Depth + 1) ||
869 SimplifyDemandedBits(I, 1, AllOnes, Known2, Depth + 1))
870 return I;
871
872 unsigned Leaders = Known2.countMinLeadingZeros();
873 Known.Zero = APInt::getHighBitsSet(BitWidth, Leaders) & DemandedMask;
874 break;
875 }
876 case Instruction::Call: {
877 bool KnownBitsComputed = false;
878 if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) {
879 switch (II->getIntrinsicID()) {
880 case Intrinsic::abs: {
881 if (DemandedMask == 1)
882 return II->getArgOperand(0);
883 break;
884 }
885 case Intrinsic::ctpop: {
886 // Checking if the number of clear bits is odd (parity)? If the type has
887 // an even number of bits, that's the same as checking if the number of
888 // set bits is odd, so we can eliminate the 'not' op.
889 Value *X;
890 if (DemandedMask == 1 && VTy->getScalarSizeInBits() % 2 == 0 &&
891 match(II->getArgOperand(0), m_Not(m_Value(X)))) {
893 II->getModule(), Intrinsic::ctpop, VTy);
894 return InsertNewInstWith(CallInst::Create(Ctpop, {X}), *I);
895 }
896 break;
897 }
898 case Intrinsic::bswap: {
899 // If the only bits demanded come from one byte of the bswap result,
900 // just shift the input byte into position to eliminate the bswap.
901 unsigned NLZ = DemandedMask.countl_zero();
902 unsigned NTZ = DemandedMask.countr_zero();
903
904 // Round NTZ down to the next byte. If we have 11 trailing zeros, then
905 // we need all the bits down to bit 8. Likewise, round NLZ. If we
906 // have 14 leading zeros, round to 8.
907 NLZ = alignDown(NLZ, 8);
908 NTZ = alignDown(NTZ, 8);
909 // If we need exactly one byte, we can do this transformation.
910 if (BitWidth - NLZ - NTZ == 8) {
911 // Replace this with either a left or right shift to get the byte into
912 // the right place.
913 Instruction *NewVal;
914 if (NLZ > NTZ)
915 NewVal = BinaryOperator::CreateLShr(
916 II->getArgOperand(0), ConstantInt::get(VTy, NLZ - NTZ));
917 else
918 NewVal = BinaryOperator::CreateShl(
919 II->getArgOperand(0), ConstantInt::get(VTy, NTZ - NLZ));
920 NewVal->takeName(I);
921 return InsertNewInstWith(NewVal, *I);
922 }
923 break;
924 }
925 case Intrinsic::fshr:
926 case Intrinsic::fshl: {
927 const APInt *SA;
928 if (!match(I->getOperand(2), m_APInt(SA)))
929 break;
930
931 // Normalize to funnel shift left. APInt shifts of BitWidth are well-
932 // defined, so no need to special-case zero shifts here.
933 uint64_t ShiftAmt = SA->urem(BitWidth);
934 if (II->getIntrinsicID() == Intrinsic::fshr)
935 ShiftAmt = BitWidth - ShiftAmt;
936
937 APInt DemandedMaskLHS(DemandedMask.lshr(ShiftAmt));
938 APInt DemandedMaskRHS(DemandedMask.shl(BitWidth - ShiftAmt));
939 if (SimplifyDemandedBits(I, 0, DemandedMaskLHS, LHSKnown, Depth + 1) ||
940 SimplifyDemandedBits(I, 1, DemandedMaskRHS, RHSKnown, Depth + 1))
941 return I;
942
943 Known.Zero = LHSKnown.Zero.shl(ShiftAmt) |
944 RHSKnown.Zero.lshr(BitWidth - ShiftAmt);
945 Known.One = LHSKnown.One.shl(ShiftAmt) |
946 RHSKnown.One.lshr(BitWidth - ShiftAmt);
947 KnownBitsComputed = true;
948 break;
949 }
950 case Intrinsic::umax: {
951 // UMax(A, C) == A if ...
952 // The lowest non-zero bit of DemandMask is higher than the highest
953 // non-zero bit of C.
954 const APInt *C;
955 unsigned CTZ = DemandedMask.countr_zero();
956 if (match(II->getArgOperand(1), m_APInt(C)) &&
957 CTZ >= C->getActiveBits())
958 return II->getArgOperand(0);
959 break;
960 }
961 case Intrinsic::umin: {
962 // UMin(A, C) == A if ...
963 // The lowest non-zero bit of DemandMask is higher than the highest
964 // non-one bit of C.
965 // This comes from using DeMorgans on the above umax example.
966 const APInt *C;
967 unsigned CTZ = DemandedMask.countr_zero();
968 if (match(II->getArgOperand(1), m_APInt(C)) &&
969 CTZ >= C->getBitWidth() - C->countl_one())
970 return II->getArgOperand(0);
971 break;
972 }
973 default: {
974 // Handle target specific intrinsics
975 std::optional<Value *> V = targetSimplifyDemandedUseBitsIntrinsic(
976 *II, DemandedMask, Known, KnownBitsComputed);
977 if (V)
978 return *V;
979 break;
980 }
981 }
982 }
983
984 if (!KnownBitsComputed)
985 computeKnownBits(V, Known, Depth, CxtI);
986 break;
987 }
988 }
989
990 // If the client is only demanding bits that we know, return the known
991 // constant.
992 if (DemandedMask.isSubsetOf(Known.Zero|Known.One))
993 return Constant::getIntegerValue(VTy, Known.One);
994 return nullptr;
995}
996
997/// Helper routine of SimplifyDemandedUseBits. It computes Known
998/// bits. It also tries to handle simplifications that can be done based on
999/// DemandedMask, but without modifying the Instruction.
1001 Instruction *I, const APInt &DemandedMask, KnownBits &Known, unsigned Depth,
1002 Instruction *CxtI) {
1003 unsigned BitWidth = DemandedMask.getBitWidth();
1004 Type *ITy = I->getType();
1005
1006 KnownBits LHSKnown(BitWidth);
1007 KnownBits RHSKnown(BitWidth);
1008
1009 // Despite the fact that we can't simplify this instruction in all User's
1010 // context, we can at least compute the known bits, and we can
1011 // do simplifications that apply to *just* the one user if we know that
1012 // this instruction has a simpler value in that context.
1013 switch (I->getOpcode()) {
1014 case Instruction::And: {
1015 computeKnownBits(I->getOperand(1), RHSKnown, Depth + 1, CxtI);
1016 computeKnownBits(I->getOperand(0), LHSKnown, Depth + 1, CxtI);
1017 Known = LHSKnown & RHSKnown;
1018
1019 // If the client is only demanding bits that we know, return the known
1020 // constant.
1021 if (DemandedMask.isSubsetOf(Known.Zero | Known.One))
1022 return Constant::getIntegerValue(ITy, Known.One);
1023
1024 // If all of the demanded bits are known 1 on one side, return the other.
1025 // These bits cannot contribute to the result of the 'and' in this context.
1026 if (DemandedMask.isSubsetOf(LHSKnown.Zero | RHSKnown.One))
1027 return I->getOperand(0);
1028 if (DemandedMask.isSubsetOf(RHSKnown.Zero | LHSKnown.One))
1029 return I->getOperand(1);
1030
1031 break;
1032 }
1033 case Instruction::Or: {
1034 computeKnownBits(I->getOperand(1), RHSKnown, Depth + 1, CxtI);
1035 computeKnownBits(I->getOperand(0), LHSKnown, Depth + 1, CxtI);
1036 Known = LHSKnown | RHSKnown;
1037
1038 // If the client is only demanding bits that we know, return the known
1039 // constant.
1040 if (DemandedMask.isSubsetOf(Known.Zero | Known.One))
1041 return Constant::getIntegerValue(ITy, Known.One);
1042
1043 // We can simplify (X|Y) -> X or Y in the user's context if we know that
1044 // only bits from X or Y are demanded.
1045 // If all of the demanded bits are known zero on one side, return the other.
1046 // These bits cannot contribute to the result of the 'or' in this context.
1047 if (DemandedMask.isSubsetOf(LHSKnown.One | RHSKnown.Zero))
1048 return I->getOperand(0);
1049 if (DemandedMask.isSubsetOf(RHSKnown.One | LHSKnown.Zero))
1050 return I->getOperand(1);
1051
1052 break;
1053 }
1054 case Instruction::Xor: {
1055 computeKnownBits(I->getOperand(1), RHSKnown, Depth + 1, CxtI);
1056 computeKnownBits(I->getOperand(0), LHSKnown, Depth + 1, CxtI);
1057 Known = LHSKnown ^ RHSKnown;
1058
1059 // If the client is only demanding bits that we know, return the known
1060 // constant.
1061 if (DemandedMask.isSubsetOf(Known.Zero | Known.One))
1062 return Constant::getIntegerValue(ITy, Known.One);
1063
1064 // We can simplify (X^Y) -> X or Y in the user's context if we know that
1065 // only bits from X or Y are demanded.
1066 // If all of the demanded bits are known zero on one side, return the other.
1067 if (DemandedMask.isSubsetOf(RHSKnown.Zero))
1068 return I->getOperand(0);
1069 if (DemandedMask.isSubsetOf(LHSKnown.Zero))
1070 return I->getOperand(1);
1071
1072 break;
1073 }
1074 case Instruction::Add: {
1075 unsigned NLZ = DemandedMask.countl_zero();
1076 APInt DemandedFromOps = APInt::getLowBitsSet(BitWidth, BitWidth - NLZ);
1077
1078 // If an operand adds zeros to every bit below the highest demanded bit,
1079 // that operand doesn't change the result. Return the other side.
1080 computeKnownBits(I->getOperand(1), RHSKnown, Depth + 1, CxtI);
1081 if (DemandedFromOps.isSubsetOf(RHSKnown.Zero))
1082 return I->getOperand(0);
1083
1084 computeKnownBits(I->getOperand(0), LHSKnown, Depth + 1, CxtI);
1085 if (DemandedFromOps.isSubsetOf(LHSKnown.Zero))
1086 return I->getOperand(1);
1087
1088 break;
1089 }
1090 case Instruction::Sub: {
1091 unsigned NLZ = DemandedMask.countl_zero();
1092 APInt DemandedFromOps = APInt::getLowBitsSet(BitWidth, BitWidth - NLZ);
1093
1094 // If an operand subtracts zeros from every bit below the highest demanded
1095 // bit, that operand doesn't change the result. Return the other side.
1096 computeKnownBits(I->getOperand(1), RHSKnown, Depth + 1, CxtI);
1097 if (DemandedFromOps.isSubsetOf(RHSKnown.Zero))
1098 return I->getOperand(0);
1099
1100 break;
1101 }
1102 case Instruction::AShr: {
1103 // Compute the Known bits to simplify things downstream.
1104 computeKnownBits(I, Known, Depth, CxtI);
1105
1106 // If this user is only demanding bits that we know, return the known
1107 // constant.
1108 if (DemandedMask.isSubsetOf(Known.Zero | Known.One))
1109 return Constant::getIntegerValue(ITy, Known.One);
1110
1111 // If the right shift operand 0 is a result of a left shift by the same
1112 // amount, this is probably a zero/sign extension, which may be unnecessary,
1113 // if we do not demand any of the new sign bits. So, return the original
1114 // operand instead.
1115 const APInt *ShiftRC;
1116 const APInt *ShiftLC;
1117 Value *X;
1118 unsigned BitWidth = DemandedMask.getBitWidth();
1119 if (match(I,
1120 m_AShr(m_Shl(m_Value(X), m_APInt(ShiftLC)), m_APInt(ShiftRC))) &&
1121 ShiftLC == ShiftRC && ShiftLC->ult(BitWidth) &&
1122 DemandedMask.isSubsetOf(APInt::getLowBitsSet(
1123 BitWidth, BitWidth - ShiftRC->getZExtValue()))) {
1124 return X;
1125 }
1126
1127 break;
1128 }
1129 default:
1130 // Compute the Known bits to simplify things downstream.
1131 computeKnownBits(I, Known, Depth, CxtI);
1132
1133 // If this user is only demanding bits that we know, return the known
1134 // constant.
1135 if (DemandedMask.isSubsetOf(Known.Zero|Known.One))
1136 return Constant::getIntegerValue(ITy, Known.One);
1137
1138 break;
1139 }
1140
1141 return nullptr;
1142}
1143
1144/// Helper routine of SimplifyDemandedUseBits. It tries to simplify
1145/// "E1 = (X lsr C1) << C2", where the C1 and C2 are constant, into
1146/// "E2 = X << (C2 - C1)" or "E2 = X >> (C1 - C2)", depending on the sign
1147/// of "C2-C1".
1148///
1149/// Suppose E1 and E2 are generally different in bits S={bm, bm+1,
1150/// ..., bn}, without considering the specific value X is holding.
1151/// This transformation is legal iff one of following conditions is hold:
1152/// 1) All the bit in S are 0, in this case E1 == E2.
1153/// 2) We don't care those bits in S, per the input DemandedMask.
1154/// 3) Combination of 1) and 2). Some bits in S are 0, and we don't care the
1155/// rest bits.
1156///
1157/// Currently we only test condition 2).
1158///
1159/// As with SimplifyDemandedUseBits, it returns NULL if the simplification was
1160/// not successful.
1162 Instruction *Shr, const APInt &ShrOp1, Instruction *Shl,
1163 const APInt &ShlOp1, const APInt &DemandedMask, KnownBits &Known) {
1164 if (!ShlOp1 || !ShrOp1)
1165 return nullptr; // No-op.
1166
1167 Value *VarX = Shr->getOperand(0);
1168 Type *Ty = VarX->getType();
1169 unsigned BitWidth = Ty->getScalarSizeInBits();
1170 if (ShlOp1.uge(BitWidth) || ShrOp1.uge(BitWidth))
1171 return nullptr; // Undef.
1172
1173 unsigned ShlAmt = ShlOp1.getZExtValue();
1174 unsigned ShrAmt = ShrOp1.getZExtValue();
1175
1176 Known.One.clearAllBits();
1177 Known.Zero.setLowBits(ShlAmt - 1);
1178 Known.Zero &= DemandedMask;
1179
1180 APInt BitMask1(APInt::getAllOnes(BitWidth));
1181 APInt BitMask2(APInt::getAllOnes(BitWidth));
1182
1183 bool isLshr = (Shr->getOpcode() == Instruction::LShr);
1184 BitMask1 = isLshr ? (BitMask1.lshr(ShrAmt) << ShlAmt) :
1185 (BitMask1.ashr(ShrAmt) << ShlAmt);
1186
1187 if (ShrAmt <= ShlAmt) {
1188 BitMask2 <<= (ShlAmt - ShrAmt);
1189 } else {
1190 BitMask2 = isLshr ? BitMask2.lshr(ShrAmt - ShlAmt):
1191 BitMask2.ashr(ShrAmt - ShlAmt);
1192 }
1193
1194 // Check if condition-2 (see the comment to this function) is satified.
1195 if ((BitMask1 & DemandedMask) == (BitMask2 & DemandedMask)) {
1196 if (ShrAmt == ShlAmt)
1197 return VarX;
1198
1199 if (!Shr->hasOneUse())
1200 return nullptr;
1201
1202 BinaryOperator *New;
1203 if (ShrAmt < ShlAmt) {
1204 Constant *Amt = ConstantInt::get(VarX->getType(), ShlAmt - ShrAmt);
1205 New = BinaryOperator::CreateShl(VarX, Amt);
1206 BinaryOperator *Orig = cast<BinaryOperator>(Shl);
1207 New->setHasNoSignedWrap(Orig->hasNoSignedWrap());
1208 New->setHasNoUnsignedWrap(Orig->hasNoUnsignedWrap());
1209 } else {
1210 Constant *Amt = ConstantInt::get(VarX->getType(), ShrAmt - ShlAmt);
1211 New = isLshr ? BinaryOperator::CreateLShr(VarX, Amt) :
1212 BinaryOperator::CreateAShr(VarX, Amt);
1213 if (cast<BinaryOperator>(Shr)->isExact())
1214 New->setIsExact(true);
1215 }
1216
1217 return InsertNewInstWith(New, *Shl);
1218 }
1219
1220 return nullptr;
1221}
1222
1223/// The specified value produces a vector with any number of elements.
1224/// This method analyzes which elements of the operand are undef or poison and
1225/// returns that information in UndefElts.
1226///
1227/// DemandedElts contains the set of elements that are actually used by the
1228/// caller, and by default (AllowMultipleUsers equals false) the value is
1229/// simplified only if it has a single caller. If AllowMultipleUsers is set
1230/// to true, DemandedElts refers to the union of sets of elements that are
1231/// used by all callers.
1232///
1233/// If the information about demanded elements can be used to simplify the
1234/// operation, the operation is simplified, then the resultant value is
1235/// returned. This returns null if no change was made.
1237 APInt DemandedElts,
1238 APInt &UndefElts,
1239 unsigned Depth,
1240 bool AllowMultipleUsers) {
1241 // Cannot analyze scalable type. The number of vector elements is not a
1242 // compile-time constant.
1243 if (isa<ScalableVectorType>(V->getType()))
1244 return nullptr;
1245
1246 unsigned VWidth = cast<FixedVectorType>(V->getType())->getNumElements();
1247 APInt EltMask(APInt::getAllOnes(VWidth));
1248 assert((DemandedElts & ~EltMask) == 0 && "Invalid DemandedElts!");
1249
1250 if (match(V, m_Undef())) {
1251 // If the entire vector is undef or poison, just return this info.
1252 UndefElts = EltMask;
1253 return nullptr;
1254 }
1255
1256 if (DemandedElts.isZero()) { // If nothing is demanded, provide poison.
1257 UndefElts = EltMask;
1258 return PoisonValue::get(V->getType());
1259 }
1260
1261 UndefElts = 0;
1262
1263 if (auto *C = dyn_cast<Constant>(V)) {
1264 // Check if this is identity. If so, return 0 since we are not simplifying
1265 // anything.
1266 if (DemandedElts.isAllOnes())
1267 return nullptr;
1268
1269 Type *EltTy = cast<VectorType>(V->getType())->getElementType();
1270 Constant *Poison = PoisonValue::get(EltTy);
1272 for (unsigned i = 0; i != VWidth; ++i) {
1273 if (!DemandedElts[i]) { // If not demanded, set to poison.
1274 Elts.push_back(Poison);
1275 UndefElts.setBit(i);
1276 continue;
1277 }
1278
1279 Constant *Elt = C->getAggregateElement(i);
1280 if (!Elt) return nullptr;
1281
1282 Elts.push_back(Elt);
1283 if (isa<UndefValue>(Elt)) // Already undef or poison.
1284 UndefElts.setBit(i);
1285 }
1286
1287 // If we changed the constant, return it.
1288 Constant *NewCV = ConstantVector::get(Elts);
1289 return NewCV != C ? NewCV : nullptr;
1290 }
1291
1292 // Limit search depth.
1293 if (Depth == 10)
1294 return nullptr;
1295
1296 if (!AllowMultipleUsers) {
1297 // If multiple users are using the root value, proceed with
1298 // simplification conservatively assuming that all elements
1299 // are needed.
1300 if (!V->hasOneUse()) {
1301 // Quit if we find multiple users of a non-root value though.
1302 // They'll be handled when it's their turn to be visited by
1303 // the main instcombine process.
1304 if (Depth != 0)
1305 // TODO: Just compute the UndefElts information recursively.
1306 return nullptr;
1307
1308 // Conservatively assume that all elements are needed.
1309 DemandedElts = EltMask;
1310 }
1311 }
1312
1313 Instruction *I = dyn_cast<Instruction>(V);
1314 if (!I) return nullptr; // Only analyze instructions.
1315
1316 bool MadeChange = false;
1317 auto simplifyAndSetOp = [&](Instruction *Inst, unsigned OpNum,
1318 APInt Demanded, APInt &Undef) {
1319 auto *II = dyn_cast<IntrinsicInst>(Inst);
1320 Value *Op = II ? II->getArgOperand(OpNum) : Inst->getOperand(OpNum);
1321 if (Value *V = SimplifyDemandedVectorElts(Op, Demanded, Undef, Depth + 1)) {
1322 replaceOperand(*Inst, OpNum, V);
1323 MadeChange = true;
1324 }
1325 };
1326
1327 APInt UndefElts2(VWidth, 0);
1328 APInt UndefElts3(VWidth, 0);
1329 switch (I->getOpcode()) {
1330 default: break;
1331
1332 case Instruction::GetElementPtr: {
1333 // The LangRef requires that struct geps have all constant indices. As
1334 // such, we can't convert any operand to partial undef.
1335 auto mayIndexStructType = [](GetElementPtrInst &GEP) {
1336 for (auto I = gep_type_begin(GEP), E = gep_type_end(GEP);
1337 I != E; I++)
1338 if (I.isStruct())
1339 return true;
1340 return false;
1341 };
1342 if (mayIndexStructType(cast<GetElementPtrInst>(*I)))
1343 break;
1344
1345 // Conservatively track the demanded elements back through any vector
1346 // operands we may have. We know there must be at least one, or we
1347 // wouldn't have a vector result to get here. Note that we intentionally
1348 // merge the undef bits here since gepping with either an poison base or
1349 // index results in poison.
1350 for (unsigned i = 0; i < I->getNumOperands(); i++) {
1351 if (i == 0 ? match(I->getOperand(i), m_Undef())
1352 : match(I->getOperand(i), m_Poison())) {
1353 // If the entire vector is undefined, just return this info.
1354 UndefElts = EltMask;
1355 return nullptr;
1356 }
1357 if (I->getOperand(i)->getType()->isVectorTy()) {
1358 APInt UndefEltsOp(VWidth, 0);
1359 simplifyAndSetOp(I, i, DemandedElts, UndefEltsOp);
1360 // gep(x, undef) is not undef, so skip considering idx ops here
1361 // Note that we could propagate poison, but we can't distinguish between
1362 // undef & poison bits ATM
1363 if (i == 0)
1364 UndefElts |= UndefEltsOp;
1365 }
1366 }
1367
1368 break;
1369 }
1370 case Instruction::InsertElement: {
1371 // If this is a variable index, we don't know which element it overwrites.
1372 // demand exactly the same input as we produce.
1373 ConstantInt *Idx = dyn_cast<ConstantInt>(I->getOperand(2));
1374 if (!Idx) {
1375 // Note that we can't propagate undef elt info, because we don't know
1376 // which elt is getting updated.
1377 simplifyAndSetOp(I, 0, DemandedElts, UndefElts2);
1378 break;
1379 }
1380
1381 // The element inserted overwrites whatever was there, so the input demanded
1382 // set is simpler than the output set.
1383 unsigned IdxNo = Idx->getZExtValue();
1384 APInt PreInsertDemandedElts = DemandedElts;
1385 if (IdxNo < VWidth)
1386 PreInsertDemandedElts.clearBit(IdxNo);
1387
1388 // If we only demand the element that is being inserted and that element
1389 // was extracted from the same index in another vector with the same type,
1390 // replace this insert with that other vector.
1391 // Note: This is attempted before the call to simplifyAndSetOp because that
1392 // may change UndefElts to a value that does not match with Vec.
1393 Value *Vec;
1394 if (PreInsertDemandedElts == 0 &&
1395 match(I->getOperand(1),
1396 m_ExtractElt(m_Value(Vec), m_SpecificInt(IdxNo))) &&
1397 Vec->getType() == I->getType()) {
1398 return Vec;
1399 }
1400
1401 simplifyAndSetOp(I, 0, PreInsertDemandedElts, UndefElts);
1402
1403 // If this is inserting an element that isn't demanded, remove this
1404 // insertelement.
1405 if (IdxNo >= VWidth || !DemandedElts[IdxNo]) {
1406 Worklist.push(I);
1407 return I->getOperand(0);
1408 }
1409
1410 // The inserted element is defined.
1411 UndefElts.clearBit(IdxNo);
1412 break;
1413 }
1414 case Instruction::ShuffleVector: {
1415 auto *Shuffle = cast<ShuffleVectorInst>(I);
1416 assert(Shuffle->getOperand(0)->getType() ==
1417 Shuffle->getOperand(1)->getType() &&
1418 "Expected shuffle operands to have same type");
1419 unsigned OpWidth = cast<FixedVectorType>(Shuffle->getOperand(0)->getType())
1420 ->getNumElements();
1421 // Handle trivial case of a splat. Only check the first element of LHS
1422 // operand.
1423 if (all_of(Shuffle->getShuffleMask(), [](int Elt) { return Elt == 0; }) &&
1424 DemandedElts.isAllOnes()) {
1425 if (!match(I->getOperand(1), m_Undef())) {
1426 I->setOperand(1, PoisonValue::get(I->getOperand(1)->getType()));
1427 MadeChange = true;
1428 }
1429 APInt LeftDemanded(OpWidth, 1);
1430 APInt LHSUndefElts(OpWidth, 0);
1431 simplifyAndSetOp(I, 0, LeftDemanded, LHSUndefElts);
1432 if (LHSUndefElts[0])
1433 UndefElts = EltMask;
1434 else
1435 UndefElts.clearAllBits();
1436 break;
1437 }
1438
1439 APInt LeftDemanded(OpWidth, 0), RightDemanded(OpWidth, 0);
1440 for (unsigned i = 0; i < VWidth; i++) {
1441 if (DemandedElts[i]) {
1442 unsigned MaskVal = Shuffle->getMaskValue(i);
1443 if (MaskVal != -1u) {
1444 assert(MaskVal < OpWidth * 2 &&
1445 "shufflevector mask index out of range!");
1446 if (MaskVal < OpWidth)
1447 LeftDemanded.setBit(MaskVal);
1448 else
1449 RightDemanded.setBit(MaskVal - OpWidth);
1450 }
1451 }
1452 }
1453
1454 APInt LHSUndefElts(OpWidth, 0);
1455 simplifyAndSetOp(I, 0, LeftDemanded, LHSUndefElts);
1456
1457 APInt RHSUndefElts(OpWidth, 0);
1458 simplifyAndSetOp(I, 1, RightDemanded, RHSUndefElts);
1459
1460 // If this shuffle does not change the vector length and the elements
1461 // demanded by this shuffle are an identity mask, then this shuffle is
1462 // unnecessary.
1463 //
1464 // We are assuming canonical form for the mask, so the source vector is
1465 // operand 0 and operand 1 is not used.
1466 //
1467 // Note that if an element is demanded and this shuffle mask is undefined
1468 // for that element, then the shuffle is not considered an identity
1469 // operation. The shuffle prevents poison from the operand vector from
1470 // leaking to the result by replacing poison with an undefined value.
1471 if (VWidth == OpWidth) {
1472 bool IsIdentityShuffle = true;
1473 for (unsigned i = 0; i < VWidth; i++) {
1474 unsigned MaskVal = Shuffle->getMaskValue(i);
1475 if (DemandedElts[i] && i != MaskVal) {
1476 IsIdentityShuffle = false;
1477 break;
1478 }
1479 }
1480 if (IsIdentityShuffle)
1481 return Shuffle->getOperand(0);
1482 }
1483
1484 bool NewUndefElts = false;
1485 unsigned LHSIdx = -1u, LHSValIdx = -1u;
1486 unsigned RHSIdx = -1u, RHSValIdx = -1u;
1487 bool LHSUniform = true;
1488 bool RHSUniform = true;
1489 for (unsigned i = 0; i < VWidth; i++) {
1490 unsigned MaskVal = Shuffle->getMaskValue(i);
1491 if (MaskVal == -1u) {
1492 UndefElts.setBit(i);
1493 } else if (!DemandedElts[i]) {
1494 NewUndefElts = true;
1495 UndefElts.setBit(i);
1496 } else if (MaskVal < OpWidth) {
1497 if (LHSUndefElts[MaskVal]) {
1498 NewUndefElts = true;
1499 UndefElts.setBit(i);
1500 } else {
1501 LHSIdx = LHSIdx == -1u ? i : OpWidth;
1502 LHSValIdx = LHSValIdx == -1u ? MaskVal : OpWidth;
1503 LHSUniform = LHSUniform && (MaskVal == i);
1504 }
1505 } else {
1506 if (RHSUndefElts[MaskVal - OpWidth]) {
1507 NewUndefElts = true;
1508 UndefElts.setBit(i);
1509 } else {
1510 RHSIdx = RHSIdx == -1u ? i : OpWidth;
1511 RHSValIdx = RHSValIdx == -1u ? MaskVal - OpWidth : OpWidth;
1512 RHSUniform = RHSUniform && (MaskVal - OpWidth == i);
1513 }
1514 }
1515 }
1516
1517 // Try to transform shuffle with constant vector and single element from
1518 // this constant vector to single insertelement instruction.
1519 // shufflevector V, C, <v1, v2, .., ci, .., vm> ->
1520 // insertelement V, C[ci], ci-n
1521 if (OpWidth ==
1522 cast<FixedVectorType>(Shuffle->getType())->getNumElements()) {
1523 Value *Op = nullptr;
1524 Constant *Value = nullptr;
1525 unsigned Idx = -1u;
1526
1527 // Find constant vector with the single element in shuffle (LHS or RHS).
1528 if (LHSIdx < OpWidth && RHSUniform) {
1529 if (auto *CV = dyn_cast<ConstantVector>(Shuffle->getOperand(0))) {
1530 Op = Shuffle->getOperand(1);
1531 Value = CV->getOperand(LHSValIdx);
1532 Idx = LHSIdx;
1533 }
1534 }
1535 if (RHSIdx < OpWidth && LHSUniform) {
1536 if (auto *CV = dyn_cast<ConstantVector>(Shuffle->getOperand(1))) {
1537 Op = Shuffle->getOperand(0);
1538 Value = CV->getOperand(RHSValIdx);
1539 Idx = RHSIdx;
1540 }
1541 }
1542 // Found constant vector with single element - convert to insertelement.
1543 if (Op && Value) {
1545 Op, Value, ConstantInt::get(Type::getInt32Ty(I->getContext()), Idx),
1546 Shuffle->getName());
1548 return New;
1549 }
1550 }
1551 if (NewUndefElts) {
1552 // Add additional discovered undefs.
1554 for (unsigned i = 0; i < VWidth; ++i) {
1555 if (UndefElts[i])
1557 else
1558 Elts.push_back(Shuffle->getMaskValue(i));
1559 }
1560 Shuffle->setShuffleMask(Elts);
1561 MadeChange = true;
1562 }
1563 break;
1564 }
1565 case Instruction::Select: {
1566 // If this is a vector select, try to transform the select condition based
1567 // on the current demanded elements.
1568 SelectInst *Sel = cast<SelectInst>(I);
1569 if (Sel->getCondition()->getType()->isVectorTy()) {
1570 // TODO: We are not doing anything with UndefElts based on this call.
1571 // It is overwritten below based on the other select operands. If an
1572 // element of the select condition is known undef, then we are free to
1573 // choose the output value from either arm of the select. If we know that
1574 // one of those values is undef, then the output can be undef.
1575 simplifyAndSetOp(I, 0, DemandedElts, UndefElts);
1576 }
1577
1578 // Next, see if we can transform the arms of the select.
1579 APInt DemandedLHS(DemandedElts), DemandedRHS(DemandedElts);
1580 if (auto *CV = dyn_cast<ConstantVector>(Sel->getCondition())) {
1581 for (unsigned i = 0; i < VWidth; i++) {
1582 // isNullValue() always returns false when called on a ConstantExpr.
1583 // Skip constant expressions to avoid propagating incorrect information.
1584 Constant *CElt = CV->getAggregateElement(i);
1585 if (isa<ConstantExpr>(CElt))
1586 continue;
1587 // TODO: If a select condition element is undef, we can demand from
1588 // either side. If one side is known undef, choosing that side would
1589 // propagate undef.
1590 if (CElt->isNullValue())
1591 DemandedLHS.clearBit(i);
1592 else
1593 DemandedRHS.clearBit(i);
1594 }
1595 }
1596
1597 simplifyAndSetOp(I, 1, DemandedLHS, UndefElts2);
1598 simplifyAndSetOp(I, 2, DemandedRHS, UndefElts3);
1599
1600 // Output elements are undefined if the element from each arm is undefined.
1601 // TODO: This can be improved. See comment in select condition handling.
1602 UndefElts = UndefElts2 & UndefElts3;
1603 break;
1604 }
1605 case Instruction::BitCast: {
1606 // Vector->vector casts only.
1607 VectorType *VTy = dyn_cast<VectorType>(I->getOperand(0)->getType());
1608 if (!VTy) break;
1609 unsigned InVWidth = cast<FixedVectorType>(VTy)->getNumElements();
1610 APInt InputDemandedElts(InVWidth, 0);
1611 UndefElts2 = APInt(InVWidth, 0);
1612 unsigned Ratio;
1613
1614 if (VWidth == InVWidth) {
1615 // If we are converting from <4 x i32> -> <4 x f32>, we demand the same
1616 // elements as are demanded of us.
1617 Ratio = 1;
1618 InputDemandedElts = DemandedElts;
1619 } else if ((VWidth % InVWidth) == 0) {
1620 // If the number of elements in the output is a multiple of the number of
1621 // elements in the input then an input element is live if any of the
1622 // corresponding output elements are live.
1623 Ratio = VWidth / InVWidth;
1624 for (unsigned OutIdx = 0; OutIdx != VWidth; ++OutIdx)
1625 if (DemandedElts[OutIdx])
1626 InputDemandedElts.setBit(OutIdx / Ratio);
1627 } else if ((InVWidth % VWidth) == 0) {
1628 // If the number of elements in the input is a multiple of the number of
1629 // elements in the output then an input element is live if the
1630 // corresponding output element is live.
1631 Ratio = InVWidth / VWidth;
1632 for (unsigned InIdx = 0; InIdx != InVWidth; ++InIdx)
1633 if (DemandedElts[InIdx / Ratio])
1634 InputDemandedElts.setBit(InIdx);
1635 } else {
1636 // Unsupported so far.
1637 break;
1638 }
1639
1640 simplifyAndSetOp(I, 0, InputDemandedElts, UndefElts2);
1641
1642 if (VWidth == InVWidth) {
1643 UndefElts = UndefElts2;
1644 } else if ((VWidth % InVWidth) == 0) {
1645 // If the number of elements in the output is a multiple of the number of
1646 // elements in the input then an output element is undef if the
1647 // corresponding input element is undef.
1648 for (unsigned OutIdx = 0; OutIdx != VWidth; ++OutIdx)
1649 if (UndefElts2[OutIdx / Ratio])
1650 UndefElts.setBit(OutIdx);
1651 } else if ((InVWidth % VWidth) == 0) {
1652 // If the number of elements in the input is a multiple of the number of
1653 // elements in the output then an output element is undef if all of the
1654 // corresponding input elements are undef.
1655 for (unsigned OutIdx = 0; OutIdx != VWidth; ++OutIdx) {
1656 APInt SubUndef = UndefElts2.lshr(OutIdx * Ratio).zextOrTrunc(Ratio);
1657 if (SubUndef.popcount() == Ratio)
1658 UndefElts.setBit(OutIdx);
1659 }
1660 } else {
1661 llvm_unreachable("Unimp");
1662 }
1663 break;
1664 }
1665 case Instruction::FPTrunc:
1666 case Instruction::FPExt:
1667 simplifyAndSetOp(I, 0, DemandedElts, UndefElts);
1668 break;
1669
1670 case Instruction::Call: {
1671 IntrinsicInst *II = dyn_cast<IntrinsicInst>(I);
1672 if (!II) break;
1673 switch (II->getIntrinsicID()) {
1674 case Intrinsic::masked_gather: // fallthrough
1675 case Intrinsic::masked_load: {
1676 // Subtlety: If we load from a pointer, the pointer must be valid
1677 // regardless of whether the element is demanded. Doing otherwise risks
1678 // segfaults which didn't exist in the original program.
1679 APInt DemandedPtrs(APInt::getAllOnes(VWidth)),
1680 DemandedPassThrough(DemandedElts);
1681 if (auto *CV = dyn_cast<ConstantVector>(II->getOperand(2)))
1682 for (unsigned i = 0; i < VWidth; i++) {
1683 Constant *CElt = CV->getAggregateElement(i);
1684 if (CElt->isNullValue())
1685 DemandedPtrs.clearBit(i);
1686 else if (CElt->isAllOnesValue())
1687 DemandedPassThrough.clearBit(i);
1688 }
1689 if (II->getIntrinsicID() == Intrinsic::masked_gather)
1690 simplifyAndSetOp(II, 0, DemandedPtrs, UndefElts2);
1691 simplifyAndSetOp(II, 3, DemandedPassThrough, UndefElts3);
1692
1693 // Output elements are undefined if the element from both sources are.
1694 // TODO: can strengthen via mask as well.
1695 UndefElts = UndefElts2 & UndefElts3;
1696 break;
1697 }
1698 default: {
1699 // Handle target specific intrinsics
1700 std::optional<Value *> V = targetSimplifyDemandedVectorEltsIntrinsic(
1701 *II, DemandedElts, UndefElts, UndefElts2, UndefElts3,
1702 simplifyAndSetOp);
1703 if (V)
1704 return *V;
1705 break;
1706 }
1707 } // switch on IntrinsicID
1708 break;
1709 } // case Call
1710 } // switch on Opcode
1711
1712 // TODO: We bail completely on integer div/rem and shifts because they have
1713 // UB/poison potential, but that should be refined.
1714 BinaryOperator *BO;
1715 if (match(I, m_BinOp(BO)) && !BO->isIntDivRem() && !BO->isShift()) {
1716 Value *X = BO->getOperand(0);
1717 Value *Y = BO->getOperand(1);
1718
1719 // Look for an equivalent binop except that one operand has been shuffled.
1720 // If the demand for this binop only includes elements that are the same as
1721 // the other binop, then we may be able to replace this binop with a use of
1722 // the earlier one.
1723 //
1724 // Example:
1725 // %other_bo = bo (shuf X, {0}), Y
1726 // %this_extracted_bo = extelt (bo X, Y), 0
1727 // -->
1728 // %other_bo = bo (shuf X, {0}), Y
1729 // %this_extracted_bo = extelt %other_bo, 0
1730 //
1731 // TODO: Handle demand of an arbitrary single element or more than one
1732 // element instead of just element 0.
1733 // TODO: Unlike general demanded elements transforms, this should be safe
1734 // for any (div/rem/shift) opcode too.
1735 if (DemandedElts == 1 && !X->hasOneUse() && !Y->hasOneUse() &&
1736 BO->hasOneUse() ) {
1737
1738 auto findShufBO = [&](bool MatchShufAsOp0) -> User * {
1739 // Try to use shuffle-of-operand in place of an operand:
1740 // bo X, Y --> bo (shuf X), Y
1741 // bo X, Y --> bo X, (shuf Y)
1742 BinaryOperator::BinaryOps Opcode = BO->getOpcode();
1743 Value *ShufOp = MatchShufAsOp0 ? X : Y;
1744 Value *OtherOp = MatchShufAsOp0 ? Y : X;
1745 for (User *U : OtherOp->users()) {
1746 auto Shuf = m_Shuffle(m_Specific(ShufOp), m_Value(), m_ZeroMask());
1747 if (BO->isCommutative()
1748 ? match(U, m_c_BinOp(Opcode, Shuf, m_Specific(OtherOp)))
1749 : MatchShufAsOp0
1750 ? match(U, m_BinOp(Opcode, Shuf, m_Specific(OtherOp)))
1751 : match(U, m_BinOp(Opcode, m_Specific(OtherOp), Shuf)))
1752 if (DT.dominates(U, I))
1753 return U;
1754 }
1755 return nullptr;
1756 };
1757
1758 if (User *ShufBO = findShufBO(/* MatchShufAsOp0 */ true))
1759 return ShufBO;
1760 if (User *ShufBO = findShufBO(/* MatchShufAsOp0 */ false))
1761 return ShufBO;
1762 }
1763
1764 simplifyAndSetOp(I, 0, DemandedElts, UndefElts);
1765 simplifyAndSetOp(I, 1, DemandedElts, UndefElts2);
1766
1767 // Output elements are undefined if both are undefined. Consider things
1768 // like undef & 0. The result is known zero, not undef.
1769 UndefElts &= UndefElts2;
1770 }
1771
1772 // If we've proven all of the lanes undef, return an undef value.
1773 // TODO: Intersect w/demanded lanes
1774 if (UndefElts.isAllOnes())
1775 return UndefValue::get(I->getType());;
1776
1777 return MadeChange ? I : nullptr;
1778}
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
Returns the sub type a function will return at a given Idx Should correspond to the result type of an ExtractValue instruction executed with just that one unsigned Idx
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
Hexagon Common GEP
This file provides internal interfaces used to implement the InstCombine.
static bool ShrinkDemandedConstant(Instruction *I, unsigned OpNo, const APInt &Demanded)
Check to see if the specified operand of the specified instruction is a constant integer.
This file provides the interface for the instcombine pass implementation.
#define I(x, y, z)
Definition: MD5.cpp:58
static GCMetadataPrinterRegistry::Add< OcamlGCMetadataPrinter > Y("ocaml", "ocaml 3.10-compatible collector")
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
SI optimize exec mask operations pre RA
Value * RHS
Value * LHS
Class for arbitrary precision integers.
Definition: APInt.h:75
static APInt getAllOnes(unsigned numBits)
Return an APInt of a specified width with all bits set.
Definition: APInt.h:214
void clearBit(unsigned BitPosition)
Set a given bit to 0.
Definition: APInt.h:1385
static APInt getSignMask(unsigned BitWidth)
Get the SignMask for a specific bit width.
Definition: APInt.h:209
uint64_t getZExtValue() const
Get zero extended value.
Definition: APInt.h:1494
void setHighBits(unsigned hiBits)
Set the top hiBits bits.
Definition: APInt.h:1370
unsigned popcount() const
Count the number of bits set.
Definition: APInt.h:1623
APInt zextOrTrunc(unsigned width) const
Zero extend or truncate to width.
Definition: APInt.cpp:994
unsigned getActiveBits() const
Compute the number of active bits in the value.
Definition: APInt.h:1463
APInt trunc(unsigned width) const
Truncate to new width.
Definition: APInt.cpp:898
void setBit(unsigned BitPosition)
Set the given bit to 1 whose position is given as "bitPosition".
Definition: APInt.h:1308
APInt abs() const
Get the absolute value.
Definition: APInt.h:1741
bool isAllOnes() const
Determine if all bits are set. This is true for zero-width values.
Definition: APInt.h:354
bool isZero() const
Determine if this value is zero, i.e. all bits are clear.
Definition: APInt.h:366
APInt urem(const APInt &RHS) const
Unsigned remainder operation.
Definition: APInt.cpp:1664
void setSignBit()
Set the sign bit to 1.
Definition: APInt.h:1318
unsigned getBitWidth() const
Return the number of bits in the APInt.
Definition: APInt.h:1439
bool ult(const APInt &RHS) const
Unsigned less than comparison.
Definition: APInt.h:1089
bool intersects(const APInt &RHS) const
This operation tests if there are any pairs of corresponding bits between this APInt and RHS that are...
Definition: APInt.h:1227
void clearAllBits()
Set every bit to 0.
Definition: APInt.h:1375
unsigned countr_zero() const
Count the number of trailing zero bits.
Definition: APInt.h:1592
unsigned countl_zero() const
The APInt version of std::countl_zero.
Definition: APInt.h:1551
void clearLowBits(unsigned loBits)
Set bottom loBits bits to 0.
Definition: APInt.h:1395
uint64_t getLimitedValue(uint64_t Limit=UINT64_MAX) const
If this value is smaller than the specified limit, return it, otherwise return the limit value.
Definition: APInt.h:463
APInt ashr(unsigned ShiftAmt) const
Arithmetic right-shift function.
Definition: APInt.h:815
void setAllBits()
Set every bit to 1.
Definition: APInt.h:1297
APInt shl(unsigned shiftAmt) const
Left-shift function.
Definition: APInt.h:861
bool isSubsetOf(const APInt &RHS) const
This operation checks that all bits set in this APInt are also set in RHS.
Definition: APInt.h:1235
bool isPowerOf2() const
Check if this APInt's value is a power of two greater than zero.
Definition: APInt.h:432
static APInt getLowBitsSet(unsigned numBits, unsigned loBitsSet)
Constructs an APInt value that has the bottom loBitsSet bits set.
Definition: APInt.h:289
bool isSignBitSet() const
Determine if sign bit of this APInt is set.
Definition: APInt.h:324
static APInt getHighBitsSet(unsigned numBits, unsigned hiBitsSet)
Constructs an APInt value that has the top hiBitsSet bits set.
Definition: APInt.h:279
void setLowBits(unsigned loBits)
Set the bottom loBits bits.
Definition: APInt.h:1367
bool isOne() const
Determine if this is a value of 1.
Definition: APInt.h:378
void lshrInPlace(unsigned ShiftAmt)
Logical right-shift this APInt by ShiftAmt in place.
Definition: APInt.h:846
APInt lshr(unsigned shiftAmt) const
Logical right-shift function.
Definition: APInt.h:839
bool uge(const APInt &RHS) const
Unsigned greater or equal comparison.
Definition: APInt.h:1199
BinaryOps getOpcode() const
Definition: InstrTypes.h:391
static CallInst * Create(FunctionType *Ty, Value *F, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
This is the base class for all instructions that perform data casts.
Definition: InstrTypes.h:428
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:718
static Constant * getShl(Constant *C1, Constant *C2, bool HasNUW=false, bool HasNSW=false)
Definition: Constants.cpp:2647
static Constant * getLShr(Constant *C1, Constant *C2, bool isExact=false)
Definition: Constants.cpp:2654
This is the shared class of boolean and integer constants.
Definition: Constants.h:78
static Constant * get(Type *Ty, uint64_t V, bool IsSigned=false)
If Ty is a vector type, return a Constant with a splat of the given value.
Definition: Constants.cpp:888
const APInt & getValue() const
Return the constant as an APInt value reference.
Definition: Constants.h:136
static Constant * get(ArrayRef< Constant * > V)
Definition: Constants.cpp:1349
This is an important base class in LLVM.
Definition: Constant.h:41
static Constant * getIntegerValue(Type *Ty, const APInt &V)
Return the value for an integer or pointer constant, or a vector thereof, with the given scalar value...
Definition: Constants.cpp:386
static Constant * getAllOnesValue(Type *Ty)
Definition: Constants.cpp:403
bool isAllOnesValue() const
Return true if this is the value that would be returned by getAllOnesValue.
Definition: Constants.cpp:93
Constant * getAggregateElement(unsigned Elt) const
For aggregates (struct/array/vector) return the constant that corresponds to the specified element if...
Definition: Constants.cpp:418
bool isNullValue() const
Return true if this is the value that would be returned by getNullValue.
Definition: Constants.cpp:76
bool dominates(const BasicBlock *BB, const Use &U) const
Return true if the (end of the) basic block BB dominates the use U.
Definition: Dominators.cpp:122
an instruction for type-safe pointer arithmetic to access elements of arrays and structs
Definition: Instructions.h:940
CallInst * CreateUnaryIntrinsic(Intrinsic::ID ID, Value *V, Instruction *FMFSource=nullptr, const Twine &Name="")
Create a call to intrinsic ID with 1 operand which is mangled on its type.
Definition: IRBuilder.cpp:956
Value * CreateTrunc(Value *V, Type *DestTy, const Twine &Name="")
Definition: IRBuilder.h:1926
Value * CreateSExt(Value *V, Type *DestTy, const Twine &Name="")
Definition: IRBuilder.h:1934
Value * CreateLShr(Value *LHS, Value *RHS, const Twine &Name="", bool isExact=false)
Definition: IRBuilder.h:1366
Value * CreateNot(Value *V, const Twine &Name="")
Definition: IRBuilder.h:1678
Value * CreateAnd(Value *LHS, Value *RHS, const Twine &Name="")
Definition: IRBuilder.h:1404
Value * CreateOr(Value *LHS, Value *RHS, const Twine &Name="")
Definition: IRBuilder.h:1426
void SetInsertPoint(BasicBlock *TheBB)
This specifies that created instructions should be appended to the end of the specified block.
Definition: IRBuilder.h:180
Value * CreateXor(Value *LHS, Value *RHS, const Twine &Name="")
Definition: IRBuilder.h:1448
static InsertElementInst * Create(Value *Vec, Value *NewElt, Value *Idx, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
bool SimplifyDemandedBits(Instruction *I, unsigned Op, const APInt &DemandedMask, KnownBits &Known, unsigned Depth=0) override
This form of SimplifyDemandedBits simplifies the specified instruction operand if possible,...
Value * SimplifyDemandedVectorElts(Value *V, APInt DemandedElts, APInt &UndefElts, unsigned Depth=0, bool AllowMultipleUsers=false) override
The specified value produces a vector with any number of elements.
Value * SimplifyDemandedUseBits(Value *V, APInt DemandedMask, KnownBits &Known, unsigned Depth, Instruction *CxtI)
Attempts to replace V with a simpler value based on the demanded bits.
Value * SimplifyMultipleUseDemandedBits(Instruction *I, const APInt &DemandedMask, KnownBits &Known, unsigned Depth, Instruction *CxtI)
Helper routine of SimplifyDemandedUseBits.
Value * simplifyShrShlDemandedBits(Instruction *Shr, const APInt &ShrOp1, Instruction *Shl, const APInt &ShlOp1, const APInt &DemandedMask, KnownBits &Known)
Helper routine of SimplifyDemandedUseBits.
bool SimplifyDemandedInstructionBits(Instruction &Inst)
Tries to simplify operands to an integer instruction based on its demanded bits.
Instruction * InsertNewInstWith(Instruction *New, Instruction &Old)
Same as InsertNewInstBefore, but also sets the debug loc.
Definition: InstCombiner.h:407
Instruction * replaceInstUsesWith(Instruction &I, Value *V)
A combiner-aware RAUW-like routine.
Definition: InstCombiner.h:418
void replaceUse(Use &U, Value *NewValue)
Replace use and add the previously used value to the worklist.
Definition: InstCombiner.h:449
InstructionWorklist & Worklist
A worklist of the instructions that need to be simplified.
Definition: InstCombiner.h:62
const DataLayout & DL
Definition: InstCombiner.h:73
unsigned ComputeNumSignBits(const Value *Op, unsigned Depth=0, const Instruction *CxtI=nullptr) const
Definition: InstCombiner.h:482
AssumptionCache & AC
Definition: InstCombiner.h:70
std::optional< Value * > targetSimplifyDemandedVectorEltsIntrinsic(IntrinsicInst &II, APInt DemandedElts, APInt &UndefElts, APInt &UndefElts2, APInt &UndefElts3, std::function< void(Instruction *, unsigned, APInt, APInt &)> SimplifyAndSetOp)
Instruction * replaceOperand(Instruction &I, unsigned OpNum, Value *V)
Replace operand of instruction and add old operand to the worklist.
Definition: InstCombiner.h:442
DominatorTree & DT
Definition: InstCombiner.h:72
std::optional< Value * > targetSimplifyDemandedUseBitsIntrinsic(IntrinsicInst &II, APInt DemandedMask, KnownBits &Known, bool &KnownBitsComputed)
void computeKnownBits(const Value *V, KnownBits &Known, unsigned Depth, const Instruction *CxtI) const
Definition: InstCombiner.h:461
BuilderTy & Builder
Definition: InstCombiner.h:58
void push(Instruction *I)
Push the instruction onto the worklist stack.
bool hasNoUnsignedWrap() const LLVM_READONLY
Determine whether the no unsigned wrap flag is set.
bool hasNoSignedWrap() const LLVM_READONLY
Determine whether the no signed wrap flag is set.
bool isCommutative() const LLVM_READONLY
Return true if the instruction is commutative:
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
Definition: Instruction.h:168
void setIsExact(bool b=true)
Set or clear the exact flag on this instruction, which must be an operator which supports this flag.
bool isShift() const
Definition: Instruction.h:175
bool isIntDivRem() const
Definition: Instruction.h:174
A wrapper class for inspecting calls to intrinsic functions.
Definition: IntrinsicInst.h:47
Intrinsic::ID getIntrinsicID() const
Return the intrinsic ID of this intrinsic.
Definition: IntrinsicInst.h:54
bool hasNoSignedWrap() const
Test whether this operation is known to never undergo signed overflow, aka the nsw property.
Definition: Operator.h:105
bool hasNoUnsignedWrap() const
Test whether this operation is known to never undergo unsigned overflow, aka the nuw property.
Definition: Operator.h:99
static PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
Definition: Constants.cpp:1750
This class represents the LLVM 'select' instruction.
const Value * getCondition() const
void push_back(const T &Elt)
Definition: SmallVector.h:416
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1200
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
bool isVectorTy() const
True if this is an instance of VectorType.
Definition: Type.h:267
bool isIntOrIntVectorTy() const
Return true if this is an integer type or a vector of integer types.
Definition: Type.h:237
unsigned getScalarSizeInBits() const LLVM_READONLY
If this is a vector type, return the getPrimitiveSizeInBits value for the element type.
static IntegerType * getInt32Ty(LLVMContext &C)
static UndefValue * get(Type *T)
Static factory methods - Return an 'undef' object of the specified type.
Definition: Constants.cpp:1731
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43
Value * getOperand(unsigned i) const
Definition: User.h:169
LLVM Value Representation.
Definition: Value.h:74
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:255
bool hasOneUse() const
Return true if there is exactly one use of this value.
Definition: Value.h:434
iterator_range< user_iterator > users()
Definition: Value.h:421
void takeName(Value *V)
Transfer the name from V to this value.
Definition: Value.cpp:383
Base class of all SIMD vector types.
Definition: DerivedTypes.h:389
This class represents zero extension of integer types.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
@ C
The default llvm calling convention, compatible with C.
Definition: CallingConv.h:34
Function * getDeclaration(Module *M, ID id, ArrayRef< Type * > Tys=std::nullopt)
Create or insert an LLVM Function declaration for an intrinsic, and return it.
Definition: Function.cpp:1506
class_match< PoisonValue > m_Poison()
Match an arbitrary poison constant.
Definition: PatternMatch.h:139
specific_intval< false > m_SpecificInt(APInt V)
Match a specific integer value or vector with all elements equal to the value.
Definition: PatternMatch.h:854
BinaryOp_match< LHS, RHS, Instruction::Add > m_Add(const LHS &L, const RHS &R)
Definition: PatternMatch.h:979
class_match< BinaryOperator > m_BinOp()
Match an arbitrary binary operation and ignore it.
Definition: PatternMatch.h:84
BinaryOp_match< LHS, RHS, Instruction::AShr > m_AShr(const LHS &L, const RHS &R)
CastClass_match< OpTy, Instruction::SExt > m_SExt(const OpTy &Op)
Matches SExt.
CastClass_match< OpTy, Instruction::ZExt > m_ZExt(const OpTy &Op)
Matches ZExt.
bool match(Val *V, const Pattern &P)
Definition: PatternMatch.h:49
specificval_ty m_Specific(const Value *V)
Match if we have a specific specified value.
Definition: PatternMatch.h:772
BinOpPred_match< LHS, RHS, is_right_shift_op > m_Shr(const LHS &L, const RHS &R)
Matches logical shift operations.
TwoOps_match< Val_t, Idx_t, Instruction::ExtractElement > m_ExtractElt(const Val_t &Val, const Idx_t &Idx)
Matches ExtractElementInst.
class_match< ConstantInt > m_ConstantInt()
Match an arbitrary ConstantInt and ignore it.
Definition: PatternMatch.h:147
CmpClass_match< LHS, RHS, ICmpInst, ICmpInst::Predicate > m_ICmp(ICmpInst::Predicate &Pred, const LHS &L, const RHS &R)
OneUse_match< T > m_OneUse(const T &SubPattern)
Definition: PatternMatch.h:67
TwoOps_match< V1_t, V2_t, Instruction::ShuffleVector > m_Shuffle(const V1_t &v1, const V2_t &v2)
Matches ShuffleVectorInst independently of mask value.
match_combine_and< class_match< Constant >, match_unless< constantexpr_match > > m_ImmConstant()
Match an arbitrary immediate Constant and ignore it.
Definition: PatternMatch.h:751
BinaryOp_match< LHS, RHS, Instruction::Add, true > m_c_Add(const LHS &L, const RHS &R)
Matches a Add with LHS and RHS in either order.
apint_match m_APInt(const APInt *&Res)
Match a ConstantInt or splatted ConstantVector, binding the specified pointer to the contained APInt.
Definition: PatternMatch.h:278
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
Definition: PatternMatch.h:76
AnyBinaryOp_match< LHS, RHS, true > m_c_BinOp(const LHS &L, const RHS &R)
Matches a BinaryOperator with LHS and RHS in either order.
BinaryOp_match< LHS, RHS, Instruction::LShr > m_LShr(const LHS &L, const RHS &R)
BinaryOp_match< LHS, RHS, Instruction::Shl > m_Shl(const LHS &L, const RHS &R)
auto m_Undef()
Match an arbitrary undef constant.
Definition: PatternMatch.h:136
BinaryOp_match< cst_pred_ty< is_all_ones >, ValTy, Instruction::Xor, true > m_Not(const ValTy &V)
Matches a 'Not' as 'xor V, -1' or 'xor -1, V'.
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1819
int countr_one(T Value)
Count the number of ones from the least significant bit to the first zero bit.
Definition: bit.h:271
void salvageDebugInfo(const MachineRegisterInfo &MRI, MachineInstr &MI)
Assuming the instruction MI is going to be deleted, attempt to salvage debug users of MI by writing t...
Definition: Utils.cpp:1367
gep_type_iterator gep_type_end(const User *GEP)
constexpr int UndefMaskElem
constexpr unsigned MaxAnalysisRecursionDepth
Definition: ValueTracking.h:46
KnownBits analyzeKnownBitsFromAndXorOr(const Operator *I, const KnownBits &KnownLHS, const KnownBits &KnownRHS, unsigned Depth, const DataLayout &DL, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, OptimizationRemarkEmitter *ORE=nullptr, bool UseInstrInfo=true)
Using KnownBits LHS/RHS produce the known bits for logic op (and/xor/or).
@ Or
Bitwise or logical OR of integers.
@ Xor
Bitwise or logical XOR of integers.
@ And
Bitwise or logical AND of integers.
constexpr unsigned BitWidth
Definition: BitmaskEnum.h:184
gep_type_iterator gep_type_begin(const User *GEP)
uint64_t alignDown(uint64_t Value, uint64_t Align, uint64_t Skew=0)
Returns the largest uint64_t less than or equal to Value and is Skew mod Align.
Definition: MathExtras.h:533
bool isNonNegative() const
Returns true if this value is known to be non-negative.
Definition: KnownBits.h:99
void makeNonNegative()
Make this value non-negative.
Definition: KnownBits.h:115
static KnownBits commonBits(const KnownBits &LHS, const KnownBits &RHS)
Compute known bits common to LHS and RHS.
Definition: KnownBits.h:297
bool hasConflict() const
Returns true if there is conflicting information.
Definition: KnownBits.h:47
unsigned getBitWidth() const
Get the bit width of this value.
Definition: KnownBits.h:40
void resetAll()
Resets the known state of all bits.
Definition: KnownBits.h:66
KnownBits sext(unsigned BitWidth) const
Return known bits for a sign extension of the value we're tracking.
Definition: KnownBits.h:171
KnownBits zextOrTrunc(unsigned BitWidth) const
Return known bits for a zero extension or truncation of the value we're tracking.
Definition: KnownBits.h:187
unsigned countMinLeadingZeros() const
Returns the minimum number of leading zero bits.
Definition: KnownBits.h:239
static KnownBits computeForAddSub(bool Add, bool NSW, const KnownBits &LHS, KnownBits RHS)
Compute known bits resulting from adding LHS and RHS.
Definition: KnownBits.cpp:57