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/ADT/SmallBitVector.h"
16#include "llvm/Analysis/ValueTracking.h"
17#include "llvm/IR/GetElementPtrTypeIterator.h"
18#include "llvm/IR/IntrinsicInst.h"
19#include "llvm/IR/PatternMatch.h"
20#include "llvm/Support/KnownBits.h"
21#include "llvm/Transforms/InstCombine/InstCombiner.h"
22
23using namespace llvm;
24using namespace llvm::PatternMatch;
25
26#define DEBUG_TYPE "instcombine"
27
28static cl::opt<bool>
29 VerifyKnownBits("instcombine-verify-known-bits",
30 cl::desc("Verify that computeKnownBits() and "
31 "SimplifyDemandedBits() are consistent"),
32 cl::Hidden, cl::init(Val: false));
33
34static cl::opt<unsigned> SimplifyDemandedVectorEltsDepthLimit(
35 "instcombine-simplify-vector-elts-depth",
36 cl::desc(
37 "Depth limit when simplifying vector instructions and their operands"),
38 cl::Hidden, cl::init(Val: 10));
39
40/// Check to see if the specified operand of the specified instruction is a
41/// constant integer. If so, check to see if there are any bits set in the
42/// constant that are not demanded. If so, shrink the constant and return true.
43static bool ShrinkDemandedConstant(Instruction *I, unsigned OpNo,
44 const APInt &Demanded) {
45 assert(I && "No instruction?");
46 assert(OpNo < I->getNumOperands() && "Operand index too large");
47
48 // The operand must be a constant integer or splat integer.
49 Value *Op = I->getOperand(i: OpNo);
50 const APInt *C;
51 if (!match(V: Op, P: m_APInt(Res&: C)))
52 return false;
53
54 // If there are no bits set that aren't demanded, nothing to do.
55 if (C->isSubsetOf(RHS: Demanded))
56 return false;
57
58 // This instruction is producing bits that are not demanded. Shrink the RHS.
59 I->setOperand(i: OpNo, Val: ConstantInt::get(Ty: Op->getType(), V: *C & Demanded));
60
61 return true;
62}
63
64/// Let N = 2 * M.
65/// Given an N-bit integer representing a pack of two M-bit integers,
66/// we can select one of the packed integers by right-shifting by either
67/// zero or M (which is the most straightforward to check if M is a power
68/// of 2), and then isolating the lower M bits. In this case, we can
69/// represent the shift as a select on whether the shr amount is nonzero.
70static Value *simplifyShiftSelectingPackedElement(Instruction *I,
71 const APInt &DemandedMask,
72 InstCombinerImpl &IC,
73 unsigned Depth) {
74 assert(I->getOpcode() == Instruction::LShr &&
75 "Only lshr instruction supported");
76
77 uint64_t ShlAmt;
78 Value *Upper, *Lower;
79 if (!match(V: I->getOperand(i: 0),
80 P: m_OneUse(SubPattern: m_c_DisjointOr(
81 L: m_OneUse(SubPattern: m_Shl(L: m_Value(V&: Upper), R: m_ConstantInt(V&: ShlAmt))),
82 R: m_Value(V&: Lower)))))
83 return nullptr;
84
85 if (!isPowerOf2_64(Value: ShlAmt))
86 return nullptr;
87
88 const uint64_t DemandedBitWidth = DemandedMask.getActiveBits();
89 if (DemandedBitWidth > ShlAmt)
90 return nullptr;
91
92 // Check that upper demanded bits are not lost from lshift.
93 if (Upper->getType()->getScalarSizeInBits() < ShlAmt + DemandedBitWidth)
94 return nullptr;
95
96 KnownBits KnownLowerBits = IC.computeKnownBits(V: Lower, CxtI: I, Depth);
97 if (!KnownLowerBits.getMaxValue().isIntN(N: ShlAmt))
98 return nullptr;
99
100 Value *ShrAmt = I->getOperand(i: 1);
101 KnownBits KnownShrBits = IC.computeKnownBits(V: ShrAmt, CxtI: I, Depth);
102
103 // Verify that ShrAmt is either exactly ShlAmt (which is a power of 2) or
104 // zero.
105 if (~KnownShrBits.Zero != ShlAmt)
106 return nullptr;
107
108 IRBuilderBase::InsertPointGuard Guard(IC.Builder);
109 IC.Builder.SetInsertPoint(I);
110 Value *ShrAmtZ =
111 IC.Builder.CreateICmpEQ(LHS: ShrAmt, RHS: Constant::getNullValue(Ty: ShrAmt->getType()),
112 Name: ShrAmt->getName() + ".z");
113 // There is no existing !prof metadata we can derive the !prof metadata for
114 // this select.
115 Value *Select = IC.Builder.CreateSelectWithUnknownProfile(C: ShrAmtZ, True: Lower,
116 False: Upper, DEBUG_TYPE);
117 Select->takeName(V: I);
118 return Select;
119}
120
121/// Returns the bitwidth of the given scalar or pointer type. For vector types,
122/// returns the element type's bitwidth.
123static unsigned getBitWidth(Type *Ty, const DataLayout &DL) {
124 if (unsigned BitWidth = Ty->getScalarSizeInBits())
125 return BitWidth;
126
127 return DL.getPointerTypeSizeInBits(Ty);
128}
129
130/// Inst is an integer instruction that SimplifyDemandedBits knows about. See if
131/// the instruction has any properties that allow us to simplify its operands.
132bool InstCombinerImpl::SimplifyDemandedInstructionBits(Instruction &Inst,
133 KnownBits &Known) {
134 APInt DemandedMask(APInt::getAllOnes(numBits: Known.getBitWidth()));
135 Value *V = SimplifyDemandedUseBits(I: &Inst, DemandedMask, Known,
136 Q: SQ.getWithInstruction(I: &Inst));
137 if (!V) return false;
138 if (V == &Inst) return true;
139 replaceInstUsesWith(I&: Inst, V);
140 return true;
141}
142
143/// Inst is an integer instruction that SimplifyDemandedBits knows about. See if
144/// the instruction has any properties that allow us to simplify its operands.
145bool InstCombinerImpl::SimplifyDemandedInstructionBits(Instruction &Inst) {
146 KnownBits Known(getBitWidth(Ty: Inst.getType(), DL));
147 return SimplifyDemandedInstructionBits(Inst, Known);
148}
149
150bool InstCombinerImpl::SimplifyDemandedInstructionFPClass(Instruction &Inst) {
151 KnownFPClass Known;
152
153 Value *V = SimplifyDemandedUseFPClass(I: &Inst, DemandedMask: fcAllFlags, Known,
154 Q: SQ.getWithInstruction(I: &Inst));
155 if (!V)
156 return false;
157 if (V == &Inst)
158 return true;
159 replaceInstUsesWith(I&: Inst, V);
160 return true;
161}
162
163/// This form of SimplifyDemandedBits simplifies the specified instruction
164/// operand if possible, updating it in place. It returns true if it made any
165/// change and false otherwise.
166bool InstCombinerImpl::SimplifyDemandedBits(Instruction *I, unsigned OpNo,
167 const APInt &DemandedMask,
168 KnownBits &Known,
169 const SimplifyQuery &Q,
170 unsigned Depth) {
171 Use &U = I->getOperandUse(i: OpNo);
172 Value *V = U.get();
173 if (isa<Constant>(Val: V)) {
174 llvm::computeKnownBits(V, Known, Q, Depth);
175 return false;
176 }
177
178 Known.resetAll();
179 if (DemandedMask.isZero()) {
180 // Not demanding any bits from V.
181 replaceUse(U, NewValue: UndefValue::get(T: V->getType()));
182 return true;
183 }
184
185 Instruction *VInst = dyn_cast<Instruction>(Val: V);
186 if (!VInst) {
187 llvm::computeKnownBits(V, Known, Q, Depth);
188 return false;
189 }
190
191 if (Depth == MaxAnalysisRecursionDepth)
192 return false;
193
194 Value *NewVal;
195 if (VInst->hasOneUse()) {
196 // If the instruction has one use, we can directly simplify it.
197 NewVal = SimplifyDemandedUseBits(I: VInst, DemandedMask, Known, Q, Depth);
198 } else {
199 // If there are multiple uses of this instruction, then we can simplify
200 // VInst to some other value, but not modify the instruction.
201 NewVal =
202 SimplifyMultipleUseDemandedBits(I: VInst, DemandedMask, Known, Q, Depth);
203 }
204 if (!NewVal) return false;
205 if (Instruction* OpInst = dyn_cast<Instruction>(Val&: U))
206 salvageDebugInfo(I&: *OpInst);
207
208 replaceUse(U, NewValue: NewVal);
209 return true;
210}
211
212/// This function attempts to replace V with a simpler value based on the
213/// demanded bits. When this function is called, it is known that only the bits
214/// set in DemandedMask of the result of V are ever used downstream.
215/// Consequently, depending on the mask and V, it may be possible to replace V
216/// with a constant or one of its operands. In such cases, this function does
217/// the replacement and returns true. In all other cases, it returns false after
218/// analyzing the expression and setting KnownOne and known to be one in the
219/// expression. Known.Zero contains all the bits that are known to be zero in
220/// the expression. These are provided to potentially allow the caller (which
221/// might recursively be SimplifyDemandedBits itself) to simplify the
222/// expression.
223/// Known.One and Known.Zero always follow the invariant that:
224/// Known.One & Known.Zero == 0.
225/// That is, a bit can't be both 1 and 0. The bits in Known.One and Known.Zero
226/// are accurate even for bits not in DemandedMask. Note
227/// also that the bitwidth of V, DemandedMask, Known.Zero and Known.One must all
228/// be the same.
229///
230/// This returns null if it did not change anything and it permits no
231/// simplification. This returns V itself if it did some simplification of V's
232/// operands based on the information about what bits are demanded. This returns
233/// some other non-null value if it found out that V is equal to another value
234/// in the context where the specified bits are demanded, but not for all users.
235Value *InstCombinerImpl::SimplifyDemandedUseBits(Instruction *I,
236 const APInt &DemandedMask,
237 KnownBits &Known,
238 const SimplifyQuery &Q,
239 unsigned Depth) {
240 assert(I != nullptr && "Null pointer of Value???");
241 assert(Depth <= MaxAnalysisRecursionDepth && "Limit Search Depth");
242 uint32_t BitWidth = DemandedMask.getBitWidth();
243 Type *VTy = I->getType();
244 assert(
245 (!VTy->isIntOrIntVectorTy() || VTy->getScalarSizeInBits() == BitWidth) &&
246 Known.getBitWidth() == BitWidth &&
247 "Value *V, DemandedMask and Known must have same BitWidth");
248
249 KnownBits LHSKnown(BitWidth), RHSKnown(BitWidth);
250
251 // Update flags after simplifying an operand based on the fact that some high
252 // order bits are not demanded.
253 auto disableWrapFlagsBasedOnUnusedHighBits = [](Instruction *I,
254 unsigned NLZ) {
255 if (NLZ > 0) {
256 // Disable the nsw and nuw flags here: We can no longer guarantee that
257 // we won't wrap after simplification. Removing the nsw/nuw flags is
258 // legal here because the top bit is not demanded.
259 I->setHasNoSignedWrap(false);
260 I->setHasNoUnsignedWrap(false);
261 }
262 return I;
263 };
264
265 // If the high-bits of an ADD/SUB/MUL are not demanded, then we do not care
266 // about the high bits of the operands.
267 auto simplifyOperandsBasedOnUnusedHighBits = [&](APInt &DemandedFromOps) {
268 unsigned NLZ = DemandedMask.countl_zero();
269 // Right fill the mask of bits for the operands to demand the most
270 // significant bit and all those below it.
271 DemandedFromOps = APInt::getLowBitsSet(numBits: BitWidth, loBitsSet: BitWidth - NLZ);
272 if (ShrinkDemandedConstant(I, OpNo: 0, Demanded: DemandedFromOps) ||
273 SimplifyDemandedBits(I, OpNo: 0, DemandedMask: DemandedFromOps, Known&: LHSKnown, Q, Depth: Depth + 1) ||
274 ShrinkDemandedConstant(I, OpNo: 1, Demanded: DemandedFromOps) ||
275 SimplifyDemandedBits(I, OpNo: 1, DemandedMask: DemandedFromOps, Known&: RHSKnown, Q, Depth: Depth + 1)) {
276 disableWrapFlagsBasedOnUnusedHighBits(I, NLZ);
277 return true;
278 }
279 return false;
280 };
281
282 switch (I->getOpcode()) {
283 default:
284 llvm::computeKnownBits(V: I, Known, Q, Depth);
285 break;
286 case Instruction::And: {
287 // If either the LHS or the RHS are Zero, the result is zero.
288 if (SimplifyDemandedBits(I, OpNo: 1, DemandedMask, Known&: RHSKnown, Q, Depth: Depth + 1) ||
289 SimplifyDemandedBits(I, OpNo: 0, DemandedMask: DemandedMask & ~RHSKnown.Zero, Known&: LHSKnown, Q,
290 Depth: Depth + 1))
291 return I;
292
293 Known = analyzeKnownBitsFromAndXorOr(I: cast<Operator>(Val: I), KnownLHS: LHSKnown, KnownRHS: RHSKnown,
294 SQ: Q, Depth);
295
296 // If the client is only demanding bits that we know, return the known
297 // constant.
298 if (DemandedMask.isSubsetOf(RHS: Known.Zero | Known.One))
299 return Constant::getIntegerValue(Ty: VTy, V: Known.One);
300
301 // If all of the demanded bits are known 1 on one side, return the other.
302 // These bits cannot contribute to the result of the 'and'.
303 if (DemandedMask.isSubsetOf(RHS: LHSKnown.Zero | RHSKnown.One))
304 return I->getOperand(i: 0);
305 if (DemandedMask.isSubsetOf(RHS: RHSKnown.Zero | LHSKnown.One))
306 return I->getOperand(i: 1);
307
308 // If the RHS is a constant, see if we can simplify it.
309 if (ShrinkDemandedConstant(I, OpNo: 1, Demanded: DemandedMask & ~LHSKnown.Zero))
310 return I;
311
312 break;
313 }
314 case Instruction::Or: {
315 // If either the LHS or the RHS are One, the result is One.
316 if (SimplifyDemandedBits(I, OpNo: 1, DemandedMask, Known&: RHSKnown, Q, Depth: Depth + 1) ||
317 SimplifyDemandedBits(I, OpNo: 0, DemandedMask: DemandedMask & ~RHSKnown.One, Known&: LHSKnown, Q,
318 Depth: Depth + 1)) {
319 // Disjoint flag may not longer hold.
320 I->dropPoisonGeneratingFlags();
321 return I;
322 }
323
324 Known = analyzeKnownBitsFromAndXorOr(I: cast<Operator>(Val: I), KnownLHS: LHSKnown, KnownRHS: RHSKnown,
325 SQ: Q, Depth);
326
327 // If the client is only demanding bits that we know, return the known
328 // constant.
329 if (DemandedMask.isSubsetOf(RHS: Known.Zero | Known.One))
330 return Constant::getIntegerValue(Ty: VTy, V: Known.One);
331
332 // If all of the demanded bits are known zero on one side, return the other.
333 // These bits cannot contribute to the result of the 'or'.
334 if (DemandedMask.isSubsetOf(RHS: LHSKnown.One | RHSKnown.Zero))
335 return I->getOperand(i: 0);
336 if (DemandedMask.isSubsetOf(RHS: RHSKnown.One | LHSKnown.Zero))
337 return I->getOperand(i: 1);
338
339 // If the RHS is a constant, see if we can simplify it.
340 if (ShrinkDemandedConstant(I, OpNo: 1, Demanded: DemandedMask))
341 return I;
342
343 // Infer disjoint flag if no common bits are set.
344 if (!cast<PossiblyDisjointInst>(Val: I)->isDisjoint()) {
345 WithCache<const Value *> LHSCache(I->getOperand(i: 0), LHSKnown),
346 RHSCache(I->getOperand(i: 1), RHSKnown);
347 if (haveNoCommonBitsSet(LHSCache, RHSCache, SQ: Q)) {
348 cast<PossiblyDisjointInst>(Val: I)->setIsDisjoint(true);
349 return I;
350 }
351 }
352
353 break;
354 }
355 case Instruction::Xor: {
356 if (SimplifyDemandedBits(I, OpNo: 1, DemandedMask, Known&: RHSKnown, Q, Depth: Depth + 1) ||
357 SimplifyDemandedBits(I, OpNo: 0, DemandedMask, Known&: LHSKnown, Q, Depth: Depth + 1))
358 return I;
359 Value *LHS, *RHS;
360 if (DemandedMask == 1 && match(V: I->getOperand(i: 0), P: m_Ctpop(Op0: m_Value(V&: LHS))) &&
361 match(V: I->getOperand(i: 1), P: m_Ctpop(Op0: m_Value(V&: RHS)))) {
362 // (ctpop(X) ^ ctpop(Y)) & 1 --> ctpop(X^Y) & 1
363 IRBuilderBase::InsertPointGuard Guard(Builder);
364 Builder.SetInsertPoint(I);
365 auto *Xor = Builder.CreateXor(LHS, RHS);
366 return Builder.CreateUnaryIntrinsic(ID: Intrinsic::ctpop, Op: Xor);
367 }
368
369 Known = analyzeKnownBitsFromAndXorOr(I: cast<Operator>(Val: I), KnownLHS: LHSKnown, KnownRHS: RHSKnown,
370 SQ: Q, Depth);
371
372 // If the client is only demanding bits that we know, return the known
373 // constant.
374 if (DemandedMask.isSubsetOf(RHS: Known.Zero | Known.One))
375 return Constant::getIntegerValue(Ty: VTy, V: Known.One);
376
377 // If all of the demanded bits are known zero on one side, return the other.
378 // These bits cannot contribute to the result of the 'xor'.
379 if (DemandedMask.isSubsetOf(RHS: RHSKnown.Zero))
380 return I->getOperand(i: 0);
381 if (DemandedMask.isSubsetOf(RHS: LHSKnown.Zero))
382 return I->getOperand(i: 1);
383
384 // If all of the demanded bits are known to be zero on one side or the
385 // other, turn this into an *inclusive* or.
386 // e.g. (A & C1)^(B & C2) -> (A & C1)|(B & C2) iff C1&C2 == 0
387 if (DemandedMask.isSubsetOf(RHS: RHSKnown.Zero | LHSKnown.Zero)) {
388 Instruction *Or =
389 BinaryOperator::CreateOr(V1: I->getOperand(i: 0), V2: I->getOperand(i: 1));
390 if (DemandedMask.isAllOnes())
391 cast<PossiblyDisjointInst>(Val: Or)->setIsDisjoint(true);
392 Or->takeName(V: I);
393 return InsertNewInstWith(New: Or, Old: I->getIterator());
394 }
395
396 // If all of the demanded bits on one side are known, and all of the set
397 // bits on that side are also known to be set on the other side, turn this
398 // into an AND, as we know the bits will be cleared.
399 // e.g. (X | C1) ^ C2 --> (X | C1) & ~C2 iff (C1&C2) == C2
400 if (DemandedMask.isSubsetOf(RHS: RHSKnown.Zero|RHSKnown.One) &&
401 RHSKnown.One.isSubsetOf(RHS: LHSKnown.One)) {
402 Constant *AndC = Constant::getIntegerValue(Ty: VTy,
403 V: ~RHSKnown.One & DemandedMask);
404 Instruction *And = BinaryOperator::CreateAnd(V1: I->getOperand(i: 0), V2: AndC);
405 return InsertNewInstWith(New: And, Old: I->getIterator());
406 }
407
408 // If the RHS is a constant, see if we can change it. Don't alter a -1
409 // constant because that's a canonical 'not' op, and that is better for
410 // combining, SCEV, and codegen.
411 const APInt *C;
412 if (match(V: I->getOperand(i: 1), P: m_APInt(Res&: C)) && !C->isAllOnes()) {
413 if ((*C | ~DemandedMask).isAllOnes()) {
414 // Force bits to 1 to create a 'not' op.
415 I->setOperand(i: 1, Val: ConstantInt::getAllOnesValue(Ty: VTy));
416 return I;
417 }
418 // If we can't turn this into a 'not', try to shrink the constant.
419 if (ShrinkDemandedConstant(I, OpNo: 1, Demanded: DemandedMask))
420 return I;
421 }
422
423 // If our LHS is an 'and' and if it has one use, and if any of the bits we
424 // are flipping are known to be set, then the xor is just resetting those
425 // bits to zero. We can just knock out bits from the 'and' and the 'xor',
426 // simplifying both of them.
427 if (Instruction *LHSInst = dyn_cast<Instruction>(Val: I->getOperand(i: 0))) {
428 ConstantInt *AndRHS, *XorRHS;
429 if (LHSInst->getOpcode() == Instruction::And && LHSInst->hasOneUse() &&
430 match(V: I->getOperand(i: 1), P: m_ConstantInt(CI&: XorRHS)) &&
431 match(V: LHSInst->getOperand(i: 1), P: m_ConstantInt(CI&: AndRHS)) &&
432 (LHSKnown.One & RHSKnown.One & DemandedMask) != 0) {
433 APInt NewMask = ~(LHSKnown.One & RHSKnown.One & DemandedMask);
434
435 Constant *AndC = ConstantInt::get(Ty: VTy, V: NewMask & AndRHS->getValue());
436 Instruction *NewAnd = BinaryOperator::CreateAnd(V1: I->getOperand(i: 0), V2: AndC);
437 InsertNewInstWith(New: NewAnd, Old: I->getIterator());
438
439 Constant *XorC = ConstantInt::get(Ty: VTy, V: NewMask & XorRHS->getValue());
440 Instruction *NewXor = BinaryOperator::CreateXor(V1: NewAnd, V2: XorC);
441 return InsertNewInstWith(New: NewXor, Old: I->getIterator());
442 }
443 }
444 break;
445 }
446 case Instruction::Select: {
447 if (SimplifyDemandedBits(I, OpNo: 2, DemandedMask, Known&: RHSKnown, Q, Depth: Depth + 1) ||
448 SimplifyDemandedBits(I, OpNo: 1, DemandedMask, Known&: LHSKnown, Q, Depth: Depth + 1))
449 return I;
450
451 // If the operands are constants, see if we can simplify them.
452 // This is similar to ShrinkDemandedConstant, but for a select we want to
453 // try to keep the selected constants the same as icmp value constants, if
454 // we can. This helps not break apart (or helps put back together)
455 // canonical patterns like min and max.
456 auto CanonicalizeSelectConstant = [](Instruction *I, unsigned OpNo,
457 const APInt &DemandedMask) {
458 const APInt *SelC;
459 if (!match(V: I->getOperand(i: OpNo), P: m_APInt(Res&: SelC)))
460 return false;
461
462 // Get the constant out of the ICmp, if there is one.
463 // Only try this when exactly 1 operand is a constant (if both operands
464 // are constant, the icmp should eventually simplify). Otherwise, we may
465 // invert the transform that reduces set bits and infinite-loop.
466 Value *X;
467 const APInt *CmpC;
468 if (!match(V: I->getOperand(i: 0), P: m_ICmp(L: m_Value(V&: X), R: m_APInt(Res&: CmpC))) ||
469 isa<Constant>(Val: X) || CmpC->getBitWidth() != SelC->getBitWidth())
470 return ShrinkDemandedConstant(I, OpNo, Demanded: DemandedMask);
471
472 // If the constant is already the same as the ICmp, leave it as-is.
473 if (*CmpC == *SelC)
474 return false;
475 // If the constants are not already the same, but can be with the demand
476 // mask, use the constant value from the ICmp.
477 if ((*CmpC & DemandedMask) == (*SelC & DemandedMask)) {
478 I->setOperand(i: OpNo, Val: ConstantInt::get(Ty: I->getType(), V: *CmpC));
479 return true;
480 }
481 return ShrinkDemandedConstant(I, OpNo, Demanded: DemandedMask);
482 };
483 if (CanonicalizeSelectConstant(I, 1, DemandedMask) ||
484 CanonicalizeSelectConstant(I, 2, DemandedMask))
485 return I;
486
487 // Only known if known in both the LHS and RHS.
488 adjustKnownBitsForSelectArm(Known&: LHSKnown, Cond: I->getOperand(i: 0), Arm: I->getOperand(i: 1),
489 /*Invert=*/false, Q, Depth);
490 adjustKnownBitsForSelectArm(Known&: RHSKnown, Cond: I->getOperand(i: 0), Arm: I->getOperand(i: 2),
491 /*Invert=*/true, Q, Depth);
492 Known = LHSKnown.intersectWith(RHS: RHSKnown);
493 break;
494 }
495 case Instruction::Trunc: {
496 // If we do not demand the high bits of a right-shifted and truncated value,
497 // then we may be able to truncate it before the shift.
498 Value *X;
499 const APInt *C;
500 if (match(V: I->getOperand(i: 0), P: m_OneUse(SubPattern: m_LShr(L: m_Value(V&: X), R: m_APInt(Res&: C))))) {
501 // The shift amount must be valid (not poison) in the narrow type, and
502 // it must not be greater than the high bits demanded of the result.
503 if (C->ult(RHS: VTy->getScalarSizeInBits()) &&
504 C->ule(RHS: DemandedMask.countl_zero())) {
505 // trunc (lshr X, C) --> lshr (trunc X), C
506 IRBuilderBase::InsertPointGuard Guard(Builder);
507 Builder.SetInsertPoint(I);
508 Value *Trunc = Builder.CreateTrunc(V: X, DestTy: VTy);
509 return Builder.CreateLShr(LHS: Trunc, RHS: C->getZExtValue());
510 }
511 }
512 }
513 [[fallthrough]];
514 case Instruction::ZExt: {
515 unsigned SrcBitWidth = I->getOperand(i: 0)->getType()->getScalarSizeInBits();
516
517 APInt InputDemandedMask = DemandedMask.zextOrTrunc(width: SrcBitWidth);
518 KnownBits InputKnown(SrcBitWidth);
519 if (SimplifyDemandedBits(I, OpNo: 0, DemandedMask: InputDemandedMask, Known&: InputKnown, Q,
520 Depth: Depth + 1)) {
521 // For zext nneg, we may have dropped the instruction which made the
522 // input non-negative.
523 I->dropPoisonGeneratingFlags();
524 return I;
525 }
526 assert(InputKnown.getBitWidth() == SrcBitWidth && "Src width changed?");
527 if (I->getOpcode() == Instruction::ZExt && I->hasNonNeg() &&
528 !InputKnown.isNegative())
529 InputKnown.makeNonNegative();
530 Known = InputKnown.zextOrTrunc(BitWidth);
531
532 break;
533 }
534 case Instruction::SExt: {
535 // Compute the bits in the result that are not present in the input.
536 unsigned SrcBitWidth = I->getOperand(i: 0)->getType()->getScalarSizeInBits();
537
538 APInt InputDemandedBits = DemandedMask.trunc(width: SrcBitWidth);
539
540 // If any of the sign extended bits are demanded, we know that the sign
541 // bit is demanded.
542 if (DemandedMask.getActiveBits() > SrcBitWidth)
543 InputDemandedBits.setBit(SrcBitWidth-1);
544
545 KnownBits InputKnown(SrcBitWidth);
546 if (SimplifyDemandedBits(I, OpNo: 0, DemandedMask: InputDemandedBits, Known&: InputKnown, Q, Depth: Depth + 1))
547 return I;
548
549 // If the input sign bit is known zero, or if the NewBits are not demanded
550 // convert this into a zero extension.
551 if (InputKnown.isNonNegative() ||
552 DemandedMask.getActiveBits() <= SrcBitWidth) {
553 // Convert to ZExt cast.
554 CastInst *NewCast = new ZExtInst(I->getOperand(i: 0), VTy);
555 NewCast->takeName(V: I);
556 return InsertNewInstWith(New: NewCast, Old: I->getIterator());
557 }
558
559 // If the sign bit of the input is known set or clear, then we know the
560 // top bits of the result.
561 Known = InputKnown.sext(BitWidth);
562 break;
563 }
564 case Instruction::Add: {
565 if ((DemandedMask & 1) == 0) {
566 // If we do not need the low bit, try to convert bool math to logic:
567 // add iN (zext i1 X), (sext i1 Y) --> sext (~X & Y) to iN
568 Value *X, *Y;
569 if (match(V: I, P: m_c_Add(L: m_OneUse(SubPattern: m_ZExt(Op: m_Value(V&: X))),
570 R: m_OneUse(SubPattern: m_SExt(Op: m_Value(V&: Y))))) &&
571 X->getType()->isIntOrIntVectorTy(BitWidth: 1) && X->getType() == Y->getType()) {
572 // Truth table for inputs and output signbits:
573 // X:0 | X:1
574 // ----------
575 // Y:0 | 0 | 0 |
576 // Y:1 | -1 | 0 |
577 // ----------
578 IRBuilderBase::InsertPointGuard Guard(Builder);
579 Builder.SetInsertPoint(I);
580 Value *AndNot = Builder.CreateAnd(LHS: Builder.CreateNot(V: X), RHS: Y);
581 return Builder.CreateSExt(V: AndNot, DestTy: VTy);
582 }
583
584 // add iN (sext i1 X), (sext i1 Y) --> sext (X | Y) to iN
585 if (match(V: I, P: m_Add(L: m_SExt(Op: m_Value(V&: X)), R: m_SExt(Op: m_Value(V&: Y)))) &&
586 X->getType()->isIntOrIntVectorTy(BitWidth: 1) && X->getType() == Y->getType() &&
587 (I->getOperand(i: 0)->hasOneUse() || I->getOperand(i: 1)->hasOneUse())) {
588
589 // Truth table for inputs and output signbits:
590 // X:0 | X:1
591 // -----------
592 // Y:0 | 0 | -1 |
593 // Y:1 | -1 | -1 |
594 // -----------
595 IRBuilderBase::InsertPointGuard Guard(Builder);
596 Builder.SetInsertPoint(I);
597 Value *Or = Builder.CreateOr(LHS: X, RHS: Y);
598 return Builder.CreateSExt(V: Or, DestTy: VTy);
599 }
600 }
601
602 // Right fill the mask of bits for the operands to demand the most
603 // significant bit and all those below it.
604 unsigned NLZ = DemandedMask.countl_zero();
605 APInt DemandedFromOps = APInt::getLowBitsSet(numBits: BitWidth, loBitsSet: BitWidth - NLZ);
606 if (ShrinkDemandedConstant(I, OpNo: 1, Demanded: DemandedFromOps) ||
607 SimplifyDemandedBits(I, OpNo: 1, DemandedMask: DemandedFromOps, Known&: RHSKnown, Q, Depth: Depth + 1))
608 return disableWrapFlagsBasedOnUnusedHighBits(I, NLZ);
609
610 // If low order bits are not demanded and known to be zero in one operand,
611 // then we don't need to demand them from the other operand, since they
612 // can't cause overflow into any bits that are demanded in the result.
613 unsigned NTZ = (~DemandedMask & RHSKnown.Zero).countr_one();
614 APInt DemandedFromLHS = DemandedFromOps;
615 DemandedFromLHS.clearLowBits(loBits: NTZ);
616 if (ShrinkDemandedConstant(I, OpNo: 0, Demanded: DemandedFromLHS) ||
617 SimplifyDemandedBits(I, OpNo: 0, DemandedMask: DemandedFromLHS, Known&: LHSKnown, Q, Depth: Depth + 1))
618 return disableWrapFlagsBasedOnUnusedHighBits(I, NLZ);
619
620 unsigned NtzLHS = (~DemandedMask & LHSKnown.Zero).countr_one();
621 APInt DemandedFromRHS = DemandedFromOps;
622 DemandedFromRHS.clearLowBits(loBits: NtzLHS);
623 if (ShrinkDemandedConstant(I, OpNo: 1, Demanded: DemandedFromRHS))
624 return disableWrapFlagsBasedOnUnusedHighBits(I, NLZ);
625
626 // If we are known to be adding zeros to every bit below
627 // the highest demanded bit, we just return the other side.
628 if (DemandedFromOps.isSubsetOf(RHS: RHSKnown.Zero))
629 return I->getOperand(i: 0);
630 if (DemandedFromOps.isSubsetOf(RHS: LHSKnown.Zero))
631 return I->getOperand(i: 1);
632
633 // (add X, C) --> (xor X, C) IFF C is equal to the top bit of the DemandMask
634 {
635 const APInt *C;
636 if (match(V: I->getOperand(i: 1), P: m_APInt(Res&: C)) &&
637 C->isOneBitSet(BitNo: DemandedMask.getActiveBits() - 1)) {
638 IRBuilderBase::InsertPointGuard Guard(Builder);
639 Builder.SetInsertPoint(I);
640 return Builder.CreateXor(LHS: I->getOperand(i: 0), RHS: ConstantInt::get(Ty: VTy, V: *C));
641 }
642 }
643
644 // Otherwise just compute the known bits of the result.
645 bool NSW = cast<OverflowingBinaryOperator>(Val: I)->hasNoSignedWrap();
646 bool NUW = cast<OverflowingBinaryOperator>(Val: I)->hasNoUnsignedWrap();
647 Known = KnownBits::add(LHS: LHSKnown, RHS: RHSKnown, NSW, NUW);
648 break;
649 }
650 case Instruction::Sub: {
651 // Right fill the mask of bits for the operands to demand the most
652 // significant bit and all those below it.
653 unsigned NLZ = DemandedMask.countl_zero();
654 APInt DemandedFromOps = APInt::getLowBitsSet(numBits: BitWidth, loBitsSet: BitWidth - NLZ);
655 if (ShrinkDemandedConstant(I, OpNo: 1, Demanded: DemandedFromOps) ||
656 SimplifyDemandedBits(I, OpNo: 1, DemandedMask: DemandedFromOps, Known&: RHSKnown, Q, Depth: Depth + 1))
657 return disableWrapFlagsBasedOnUnusedHighBits(I, NLZ);
658
659 // If low order bits are not demanded and are known to be zero in RHS,
660 // then we don't need to demand them from LHS, since they can't cause a
661 // borrow from any bits that are demanded in the result.
662 unsigned NTZ = (~DemandedMask & RHSKnown.Zero).countr_one();
663 APInt DemandedFromLHS = DemandedFromOps;
664 DemandedFromLHS.clearLowBits(loBits: NTZ);
665 if (ShrinkDemandedConstant(I, OpNo: 0, Demanded: DemandedFromLHS) ||
666 SimplifyDemandedBits(I, OpNo: 0, DemandedMask: DemandedFromLHS, Known&: LHSKnown, Q, Depth: Depth + 1))
667 return disableWrapFlagsBasedOnUnusedHighBits(I, NLZ);
668
669 // If we are known to be subtracting zeros from every bit below
670 // the highest demanded bit, we just return the other side.
671 if (DemandedFromOps.isSubsetOf(RHS: RHSKnown.Zero))
672 return I->getOperand(i: 0);
673 // We can't do this with the LHS for subtraction, unless we are only
674 // demanding the LSB.
675 if (DemandedFromOps.isOne() && DemandedFromOps.isSubsetOf(RHS: LHSKnown.Zero))
676 return I->getOperand(i: 1);
677
678 // Canonicalize sub mask, X -> ~X
679 const APInt *LHSC;
680 if (match(V: I->getOperand(i: 0), P: m_LowBitMask(V&: LHSC)) &&
681 DemandedFromOps.isSubsetOf(RHS: *LHSC)) {
682 IRBuilderBase::InsertPointGuard Guard(Builder);
683 Builder.SetInsertPoint(I);
684 return Builder.CreateNot(V: I->getOperand(i: 1));
685 }
686
687 // Otherwise just compute the known bits of the result.
688 bool NSW = cast<OverflowingBinaryOperator>(Val: I)->hasNoSignedWrap();
689 bool NUW = cast<OverflowingBinaryOperator>(Val: I)->hasNoUnsignedWrap();
690 Known = KnownBits::sub(LHS: LHSKnown, RHS: RHSKnown, NSW, NUW);
691 break;
692 }
693 case Instruction::Mul: {
694 APInt DemandedFromOps;
695 if (simplifyOperandsBasedOnUnusedHighBits(DemandedFromOps))
696 return I;
697
698 if (DemandedMask.isPowerOf2()) {
699 // The LSB of X*Y is set only if (X & 1) == 1 and (Y & 1) == 1.
700 // If we demand exactly one bit N and we have "X * (C' << N)" where C' is
701 // odd (has LSB set), then the left-shifted low bit of X is the answer.
702 unsigned CTZ = DemandedMask.countr_zero();
703 const APInt *C;
704 if (match(V: I->getOperand(i: 1), P: m_APInt(Res&: C)) && C->countr_zero() == CTZ) {
705 Constant *ShiftC = ConstantInt::get(Ty: VTy, V: CTZ);
706 Instruction *Shl = BinaryOperator::CreateShl(V1: I->getOperand(i: 0), V2: ShiftC);
707 return InsertNewInstWith(New: Shl, Old: I->getIterator());
708 }
709 }
710 // For a squared value "X * X", the bottom 2 bits are 0 and X[0] because:
711 // X * X is odd iff X is odd.
712 // 'Quadratic Reciprocity': X * X -> 0 for bit[1]
713 if (I->getOperand(i: 0) == I->getOperand(i: 1) && DemandedMask.ult(RHS: 4)) {
714 Constant *One = ConstantInt::get(Ty: VTy, V: 1);
715 Instruction *And1 = BinaryOperator::CreateAnd(V1: I->getOperand(i: 0), V2: One);
716 return InsertNewInstWith(New: And1, Old: I->getIterator());
717 }
718
719 llvm::computeKnownBits(V: I, Known, Q, Depth);
720 break;
721 }
722 case Instruction::Shl: {
723 const APInt *SA;
724 if (match(V: I->getOperand(i: 1), P: m_APInt(Res&: SA))) {
725 const APInt *ShrAmt;
726 if (match(V: I->getOperand(i: 0), P: m_Shr(L: m_Value(), R: m_APInt(Res&: ShrAmt))))
727 if (Instruction *Shr = dyn_cast<Instruction>(Val: I->getOperand(i: 0)))
728 if (Value *R = simplifyShrShlDemandedBits(Shr, ShrOp1: *ShrAmt, Shl: I, ShlOp1: *SA,
729 DemandedMask, Known))
730 return R;
731
732 // Do not simplify if shl is part of funnel-shift pattern
733 if (I->hasOneUse()) {
734 Instruction *Inst = I->user_back();
735 if (Inst->getOpcode() == BinaryOperator::Or) {
736 if (auto Opt = convertOrOfShiftsToFunnelShift(Or&: *Inst)) {
737 auto [IID, FShiftArgs] = *Opt;
738 if ((IID == Intrinsic::fshl || IID == Intrinsic::fshr) &&
739 FShiftArgs[0] == FShiftArgs[1]) {
740 llvm::computeKnownBits(V: I, Known, Q, Depth);
741 break;
742 }
743 }
744 }
745 }
746
747 // We only want bits that already match the signbit then we don't
748 // need to shift.
749 uint64_t ShiftAmt = SA->getLimitedValue(Limit: BitWidth - 1);
750 if (DemandedMask.countr_zero() >= ShiftAmt) {
751 if (I->hasNoSignedWrap()) {
752 unsigned NumHiDemandedBits = BitWidth - DemandedMask.countr_zero();
753 unsigned SignBits =
754 ComputeNumSignBits(Op: I->getOperand(i: 0), CxtI: Q.CxtI, Depth: Depth + 1);
755 if (SignBits > ShiftAmt && SignBits - ShiftAmt >= NumHiDemandedBits)
756 return I->getOperand(i: 0);
757 }
758
759 // If we can pre-shift a right-shifted constant to the left without
760 // losing any high bits and we don't demand the low bits, then eliminate
761 // the left-shift:
762 // (C >> X) << LeftShiftAmtC --> (C << LeftShiftAmtC) >> X
763 Value *X;
764 Constant *C;
765 if (match(V: I->getOperand(i: 0), P: m_LShr(L: m_ImmConstant(C), R: m_Value(V&: X)))) {
766 Constant *LeftShiftAmtC = ConstantInt::get(Ty: VTy, V: ShiftAmt);
767 Constant *NewC = ConstantFoldBinaryOpOperands(Opcode: Instruction::Shl, LHS: C,
768 RHS: LeftShiftAmtC, DL);
769 if (ConstantFoldBinaryOpOperands(Opcode: Instruction::LShr, LHS: NewC,
770 RHS: LeftShiftAmtC, DL) == C) {
771 Instruction *Lshr = BinaryOperator::CreateLShr(V1: NewC, V2: X);
772 return InsertNewInstWith(New: Lshr, Old: I->getIterator());
773 }
774 }
775 }
776
777 APInt DemandedMaskIn(DemandedMask.lshr(shiftAmt: ShiftAmt));
778
779 // If the shift is NUW/NSW, then it does demand the high bits.
780 ShlOperator *IOp = cast<ShlOperator>(Val: I);
781 if (IOp->hasNoSignedWrap())
782 DemandedMaskIn.setHighBits(ShiftAmt+1);
783 else if (IOp->hasNoUnsignedWrap())
784 DemandedMaskIn.setHighBits(ShiftAmt);
785
786 if (SimplifyDemandedBits(I, OpNo: 0, DemandedMask: DemandedMaskIn, Known, Q, Depth: Depth + 1))
787 return I;
788
789 Known = KnownBits::shl(LHS: Known,
790 RHS: KnownBits::makeConstant(C: APInt(BitWidth, ShiftAmt)),
791 /* NUW */ IOp->hasNoUnsignedWrap(),
792 /* NSW */ IOp->hasNoSignedWrap());
793 } else {
794 // This is a variable shift, so we can't shift the demand mask by a known
795 // amount. But if we are not demanding high bits, then we are not
796 // demanding those bits from the pre-shifted operand either.
797 if (unsigned CTLZ = DemandedMask.countl_zero()) {
798 APInt DemandedFromOp(APInt::getLowBitsSet(numBits: BitWidth, loBitsSet: BitWidth - CTLZ));
799 if (SimplifyDemandedBits(I, OpNo: 0, DemandedMask: DemandedFromOp, Known, Q, Depth: Depth + 1)) {
800 // We can't guarantee that nsw/nuw hold after simplifying the operand.
801 I->dropPoisonGeneratingFlags();
802 return I;
803 }
804 }
805 llvm::computeKnownBits(V: I, Known, Q, Depth);
806 }
807 break;
808 }
809 case Instruction::LShr: {
810 const APInt *SA;
811 if (match(V: I->getOperand(i: 1), P: m_APInt(Res&: SA))) {
812 uint64_t ShiftAmt = SA->getLimitedValue(Limit: BitWidth-1);
813
814 // Do not simplify if lshr is part of funnel-shift pattern
815 if (I->hasOneUse()) {
816 Instruction *Inst = I->user_back();
817 if (Inst->getOpcode() == BinaryOperator::Or) {
818 if (auto Opt = convertOrOfShiftsToFunnelShift(Or&: *Inst)) {
819 auto [IID, FShiftArgs] = *Opt;
820 if ((IID == Intrinsic::fshl || IID == Intrinsic::fshr) &&
821 FShiftArgs[0] == FShiftArgs[1]) {
822 llvm::computeKnownBits(V: I, Known, Q, Depth);
823 break;
824 }
825 }
826 }
827 }
828
829 // If we are just demanding the shifted sign bit and below, then this can
830 // be treated as an ASHR in disguise.
831 if (DemandedMask.countl_zero() >= ShiftAmt) {
832 // If we only want bits that already match the signbit then we don't
833 // need to shift.
834 unsigned NumHiDemandedBits = BitWidth - DemandedMask.countr_zero();
835 unsigned SignBits =
836 ComputeNumSignBits(Op: I->getOperand(i: 0), CxtI: Q.CxtI, Depth: Depth + 1);
837 if (SignBits >= NumHiDemandedBits)
838 return I->getOperand(i: 0);
839
840 // If we can pre-shift a left-shifted constant to the right without
841 // losing any low bits (we already know we don't demand the high bits),
842 // then eliminate the right-shift:
843 // (C << X) >> RightShiftAmtC --> (C >> RightShiftAmtC) << X
844 Value *X;
845 Constant *C;
846 if (match(V: I->getOperand(i: 0), P: m_Shl(L: m_ImmConstant(C), R: m_Value(V&: X)))) {
847 Constant *RightShiftAmtC = ConstantInt::get(Ty: VTy, V: ShiftAmt);
848 Constant *NewC = ConstantFoldBinaryOpOperands(Opcode: Instruction::LShr, LHS: C,
849 RHS: RightShiftAmtC, DL);
850 if (ConstantFoldBinaryOpOperands(Opcode: Instruction::Shl, LHS: NewC,
851 RHS: RightShiftAmtC, DL) == C) {
852 Instruction *Shl = BinaryOperator::CreateShl(V1: NewC, V2: X);
853 return InsertNewInstWith(New: Shl, Old: I->getIterator());
854 }
855 }
856
857 const APInt *Factor;
858 if (match(V: I->getOperand(i: 0),
859 P: m_OneUse(SubPattern: m_Mul(L: m_Value(V&: X), R: m_APInt(Res&: Factor)))) &&
860 Factor->countr_zero() >= ShiftAmt) {
861 BinaryOperator *Mul = BinaryOperator::CreateMul(
862 V1: X, V2: ConstantInt::get(Ty: X->getType(), V: Factor->lshr(shiftAmt: ShiftAmt)));
863 return InsertNewInstWith(New: Mul, Old: I->getIterator());
864 }
865 }
866
867 // Unsigned shift right.
868 APInt DemandedMaskIn(DemandedMask.shl(shiftAmt: ShiftAmt));
869 if (SimplifyDemandedBits(I, OpNo: 0, DemandedMask: DemandedMaskIn, Known, Q, Depth: Depth + 1)) {
870 // exact flag may not longer hold.
871 I->dropPoisonGeneratingFlags();
872 return I;
873 }
874 Known >>= ShiftAmt;
875 if (ShiftAmt)
876 Known.Zero.setHighBits(ShiftAmt); // high bits known zero.
877 break;
878 }
879 if (Value *V =
880 simplifyShiftSelectingPackedElement(I, DemandedMask, IC&: *this, Depth))
881 return V;
882
883 llvm::computeKnownBits(V: I, Known, Q, Depth);
884 break;
885 }
886 case Instruction::AShr: {
887 unsigned SignBits = ComputeNumSignBits(Op: I->getOperand(i: 0), CxtI: Q.CxtI, Depth: Depth + 1);
888
889 // If we only want bits that already match the signbit then we don't need
890 // to shift.
891 unsigned NumHiDemandedBits = BitWidth - DemandedMask.countr_zero();
892 if (SignBits >= NumHiDemandedBits)
893 return I->getOperand(i: 0);
894
895 // If this is an arithmetic shift right and only the low-bit is set, we can
896 // always convert this into a logical shr, even if the shift amount is
897 // variable. The low bit of the shift cannot be an input sign bit unless
898 // the shift amount is >= the size of the datatype, which is undefined.
899 if (DemandedMask.isOne()) {
900 // Perform the logical shift right.
901 Instruction *NewVal = BinaryOperator::CreateLShr(
902 V1: I->getOperand(i: 0), V2: I->getOperand(i: 1), Name: I->getName());
903 return InsertNewInstWith(New: NewVal, Old: I->getIterator());
904 }
905
906 const APInt *SA;
907 if (match(V: I->getOperand(i: 1), P: m_APInt(Res&: SA))) {
908 uint32_t ShiftAmt = SA->getLimitedValue(Limit: BitWidth-1);
909
910 // Signed shift right.
911 APInt DemandedMaskIn(DemandedMask.shl(shiftAmt: ShiftAmt));
912 // If any of the bits being shifted in are demanded, then we should set
913 // the sign bit as demanded.
914 bool ShiftedInBitsDemanded = DemandedMask.countl_zero() < ShiftAmt;
915 if (ShiftedInBitsDemanded)
916 DemandedMaskIn.setSignBit();
917 if (SimplifyDemandedBits(I, OpNo: 0, DemandedMask: DemandedMaskIn, Known, Q, Depth: Depth + 1)) {
918 // exact flag may not longer hold.
919 I->dropPoisonGeneratingFlags();
920 return I;
921 }
922
923 // If the input sign bit is known to be zero, or if none of the shifted in
924 // bits are demanded, turn this into an unsigned shift right.
925 if (Known.Zero[BitWidth - 1] || !ShiftedInBitsDemanded) {
926 BinaryOperator *LShr = BinaryOperator::CreateLShr(V1: I->getOperand(i: 0),
927 V2: I->getOperand(i: 1));
928 LShr->setIsExact(cast<BinaryOperator>(Val: I)->isExact());
929 LShr->takeName(V: I);
930 return InsertNewInstWith(New: LShr, Old: I->getIterator());
931 }
932
933 Known = KnownBits::ashr(
934 LHS: Known, RHS: KnownBits::makeConstant(C: APInt(BitWidth, ShiftAmt)),
935 ShAmtNonZero: ShiftAmt != 0, Exact: I->isExact());
936 } else {
937 llvm::computeKnownBits(V: I, Known, Q, Depth);
938 }
939 break;
940 }
941 case Instruction::UDiv: {
942 // UDiv doesn't demand low bits that are zero in the divisor.
943 const APInt *SA;
944 if (match(V: I->getOperand(i: 1), P: m_APInt(Res&: SA))) {
945 // TODO: Take the demanded mask of the result into account.
946 unsigned RHSTrailingZeros = SA->countr_zero();
947 APInt DemandedMaskIn =
948 APInt::getHighBitsSet(numBits: BitWidth, hiBitsSet: BitWidth - RHSTrailingZeros);
949 if (SimplifyDemandedBits(I, OpNo: 0, DemandedMask: DemandedMaskIn, Known&: LHSKnown, Q, Depth: Depth + 1)) {
950 // We can't guarantee that "exact" is still true after changing the
951 // the dividend.
952 I->dropPoisonGeneratingFlags();
953 return I;
954 }
955
956 Known = KnownBits::udiv(LHS: LHSKnown, RHS: KnownBits::makeConstant(C: *SA),
957 Exact: cast<BinaryOperator>(Val: I)->isExact());
958 } else {
959 llvm::computeKnownBits(V: I, Known, Q, Depth);
960 }
961 break;
962 }
963 case Instruction::SRem: {
964 const APInt *Rem;
965 if (match(V: I->getOperand(i: 1), P: m_APInt(Res&: Rem)) && Rem->isPowerOf2()) {
966 if (DemandedMask.ult(RHS: *Rem)) // srem won't affect demanded bits
967 return I->getOperand(i: 0);
968
969 APInt LowBits = *Rem - 1;
970 APInt Mask2 = LowBits | APInt::getSignMask(BitWidth);
971 if (SimplifyDemandedBits(I, OpNo: 0, DemandedMask: Mask2, Known&: LHSKnown, Q, Depth: Depth + 1))
972 return I;
973 Known = KnownBits::srem(LHS: LHSKnown, RHS: KnownBits::makeConstant(C: *Rem));
974 break;
975 }
976
977 llvm::computeKnownBits(V: I, Known, Q, Depth);
978 break;
979 }
980 case Instruction::Call: {
981 bool KnownBitsComputed = false;
982 if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(Val: I)) {
983 switch (II->getIntrinsicID()) {
984 case Intrinsic::abs: {
985 if (DemandedMask == 1)
986 return II->getArgOperand(i: 0);
987 break;
988 }
989 case Intrinsic::ctpop: {
990 // Checking if the number of clear bits is odd (parity)? If the type has
991 // an even number of bits, that's the same as checking if the number of
992 // set bits is odd, so we can eliminate the 'not' op.
993 Value *X;
994 if (DemandedMask == 1 && VTy->getScalarSizeInBits() % 2 == 0 &&
995 match(V: II->getArgOperand(i: 0), P: m_Not(V: m_Value(V&: X)))) {
996 Function *Ctpop = Intrinsic::getOrInsertDeclaration(
997 M: II->getModule(), id: Intrinsic::ctpop, OverloadTys: VTy);
998 return InsertNewInstWith(New: CallInst::Create(Func: Ctpop, Args: {X}), Old: I->getIterator());
999 }
1000 break;
1001 }
1002 case Intrinsic::bswap: {
1003 // If the only bits demanded come from one byte of the bswap result,
1004 // just shift the input byte into position to eliminate the bswap.
1005 unsigned NLZ = DemandedMask.countl_zero();
1006 unsigned NTZ = DemandedMask.countr_zero();
1007
1008 // Round NTZ down to the next byte. If we have 11 trailing zeros, then
1009 // we need all the bits down to bit 8. Likewise, round NLZ. If we
1010 // have 14 leading zeros, round to 8.
1011 NLZ = alignDown(Value: NLZ, Align: 8);
1012 NTZ = alignDown(Value: NTZ, Align: 8);
1013 // If we need exactly one byte, we can do this transformation.
1014 if (BitWidth - NLZ - NTZ == 8) {
1015 // Replace this with either a left or right shift to get the byte into
1016 // the right place.
1017 Instruction *NewVal;
1018 if (NLZ > NTZ)
1019 NewVal = BinaryOperator::CreateLShr(
1020 V1: II->getArgOperand(i: 0), V2: ConstantInt::get(Ty: VTy, V: NLZ - NTZ));
1021 else
1022 NewVal = BinaryOperator::CreateShl(
1023 V1: II->getArgOperand(i: 0), V2: ConstantInt::get(Ty: VTy, V: NTZ - NLZ));
1024 NewVal->takeName(V: I);
1025 return InsertNewInstWith(New: NewVal, Old: I->getIterator());
1026 }
1027 break;
1028 }
1029 case Intrinsic::ptrmask: {
1030 unsigned MaskWidth = I->getOperand(i: 1)->getType()->getScalarSizeInBits();
1031 RHSKnown = KnownBits(MaskWidth);
1032 // If either the LHS or the RHS are Zero, the result is zero.
1033 if (SimplifyDemandedBits(I, OpNo: 0, DemandedMask, Known&: LHSKnown, Q, Depth: Depth + 1) ||
1034 SimplifyDemandedBits(
1035 I, OpNo: 1, DemandedMask: (DemandedMask & ~LHSKnown.Zero).zextOrTrunc(width: MaskWidth),
1036 Known&: RHSKnown, Q, Depth: Depth + 1))
1037 return I;
1038
1039 // TODO: Should be 1-extend
1040 RHSKnown = RHSKnown.anyextOrTrunc(BitWidth);
1041
1042 Known = LHSKnown & RHSKnown;
1043 KnownBitsComputed = true;
1044
1045 // If the client is only demanding bits we know to be zero, return
1046 // `llvm.ptrmask(p, 0)`. We can't return `null` here due to pointer
1047 // provenance, but making the mask zero will be easily optimizable in
1048 // the backend.
1049 if (DemandedMask.isSubsetOf(RHS: Known.Zero) &&
1050 !match(V: I->getOperand(i: 1), P: m_Zero()))
1051 return replaceOperand(
1052 I&: *I, OpNum: 1, V: Constant::getNullValue(Ty: I->getOperand(i: 1)->getType()));
1053
1054 // Mask in demanded space does nothing.
1055 // NOTE: We may have attributes associated with the return value of the
1056 // llvm.ptrmask intrinsic that will be lost when we just return the
1057 // operand. We should try to preserve them.
1058 if (DemandedMask.isSubsetOf(RHS: RHSKnown.One | LHSKnown.Zero))
1059 return I->getOperand(i: 0);
1060
1061 // If the RHS is a constant, see if we can simplify it.
1062 if (ShrinkDemandedConstant(
1063 I, OpNo: 1, Demanded: (DemandedMask & ~LHSKnown.Zero).zextOrTrunc(width: MaskWidth)))
1064 return I;
1065
1066 // Combine:
1067 // (ptrmask (getelementptr i8, ptr p, imm i), imm mask)
1068 // -> (ptrmask (getelementptr i8, ptr p, imm (i & mask)), imm mask)
1069 // where only the low bits known to be zero in the pointer are changed
1070 Value *InnerPtr;
1071 uint64_t GEPIndex;
1072 uint64_t PtrMaskImmediate;
1073 if (match(V: I, P: m_Intrinsic<Intrinsic::ptrmask>(
1074 Ops: m_PtrAdd(PointerOp: m_Value(V&: InnerPtr), OffsetOp: m_ConstantInt(V&: GEPIndex)),
1075 Ops: m_ConstantInt(V&: PtrMaskImmediate)))) {
1076
1077 LHSKnown = computeKnownBits(V: InnerPtr, CxtI: I, Depth: Depth + 1);
1078 if (!LHSKnown.isZero()) {
1079 const unsigned trailingZeros = LHSKnown.countMinTrailingZeros();
1080 uint64_t PointerAlignBits = (uint64_t(1) << trailingZeros) - 1;
1081
1082 uint64_t HighBitsGEPIndex = GEPIndex & ~PointerAlignBits;
1083 uint64_t MaskedLowBitsGEPIndex =
1084 GEPIndex & PointerAlignBits & PtrMaskImmediate;
1085
1086 uint64_t MaskedGEPIndex = HighBitsGEPIndex | MaskedLowBitsGEPIndex;
1087
1088 if (MaskedGEPIndex != GEPIndex) {
1089 auto *GEP = cast<GEPOperator>(Val: II->getArgOperand(i: 0));
1090 Builder.SetInsertPoint(I);
1091 Type *GEPIndexType =
1092 DL.getIndexType(PtrTy: GEP->getPointerOperand()->getType());
1093 Value *MaskedGEP = Builder.CreateGEP(
1094 Ty: GEP->getSourceElementType(), Ptr: InnerPtr,
1095 IdxList: ConstantInt::get(Ty: GEPIndexType, V: MaskedGEPIndex),
1096 Name: GEP->getName(), NW: GEP->isInBounds());
1097
1098 replaceOperand(I&: *I, OpNum: 0, V: MaskedGEP);
1099 return I;
1100 }
1101 }
1102 }
1103
1104 break;
1105 }
1106
1107 case Intrinsic::fshr:
1108 case Intrinsic::fshl: {
1109 const APInt *SA;
1110 if (!match(V: I->getOperand(i: 2), P: m_APInt(Res&: SA)))
1111 break;
1112
1113 // Normalize to funnel shift left. APInt shifts of BitWidth are well-
1114 // defined, so no need to special-case zero shifts here.
1115 uint64_t ShiftAmt = SA->urem(RHS: BitWidth);
1116 if (II->getIntrinsicID() == Intrinsic::fshr)
1117 ShiftAmt = BitWidth - ShiftAmt;
1118
1119 APInt DemandedMaskLHS(DemandedMask.lshr(shiftAmt: ShiftAmt));
1120 APInt DemandedMaskRHS(DemandedMask.shl(shiftAmt: BitWidth - ShiftAmt));
1121 if (I->getOperand(i: 0) != I->getOperand(i: 1)) {
1122 if (SimplifyDemandedBits(I, OpNo: 0, DemandedMask: DemandedMaskLHS, Known&: LHSKnown, Q,
1123 Depth: Depth + 1) ||
1124 SimplifyDemandedBits(I, OpNo: 1, DemandedMask: DemandedMaskRHS, Known&: RHSKnown, Q,
1125 Depth: Depth + 1)) {
1126 // Range attribute or metadata may no longer hold.
1127 I->dropPoisonGeneratingAnnotations();
1128 return I;
1129 }
1130 } else { // fshl is a rotate
1131 // Avoid converting rotate into funnel shift.
1132 // Only simplify if one operand is constant.
1133 LHSKnown = computeKnownBits(V: I->getOperand(i: 0), CxtI: I, Depth: Depth + 1);
1134 if (DemandedMaskLHS.isSubsetOf(RHS: LHSKnown.Zero | LHSKnown.One) &&
1135 !match(V: I->getOperand(i: 0), P: m_SpecificInt(V: LHSKnown.One))) {
1136 replaceOperand(I&: *I, OpNum: 0, V: Constant::getIntegerValue(Ty: VTy, V: LHSKnown.One));
1137 // Range attribute or metadata may no longer hold.
1138 I->dropPoisonGeneratingAnnotations();
1139 return I;
1140 }
1141
1142 RHSKnown = computeKnownBits(V: I->getOperand(i: 1), CxtI: I, Depth: Depth + 1);
1143 if (DemandedMaskRHS.isSubsetOf(RHS: RHSKnown.Zero | RHSKnown.One) &&
1144 !match(V: I->getOperand(i: 1), P: m_SpecificInt(V: RHSKnown.One))) {
1145 replaceOperand(I&: *I, OpNum: 1, V: Constant::getIntegerValue(Ty: VTy, V: RHSKnown.One));
1146 // Range attribute or metadata may no longer hold.
1147 I->dropPoisonGeneratingAnnotations();
1148 return I;
1149 }
1150 }
1151
1152 LHSKnown <<= ShiftAmt;
1153 RHSKnown >>= BitWidth - ShiftAmt;
1154 Known = LHSKnown.unionWith(RHS: RHSKnown);
1155 KnownBitsComputed = true;
1156 break;
1157 }
1158 case Intrinsic::umax: {
1159 // UMax(A, C) == A if ...
1160 // The lowest non-zero bit of DemandMask is higher than the highest
1161 // non-zero bit of C.
1162 const APInt *C;
1163 unsigned CTZ = DemandedMask.countr_zero();
1164 if (match(V: II->getArgOperand(i: 1), P: m_APInt(Res&: C)) &&
1165 CTZ >= C->getActiveBits())
1166 return II->getArgOperand(i: 0);
1167 break;
1168 }
1169 case Intrinsic::umin: {
1170 // UMin(A, C) == A if ...
1171 // The lowest non-zero bit of DemandMask is higher than the highest
1172 // non-one bit of C.
1173 // This comes from using DeMorgans on the above umax example.
1174 const APInt *C;
1175 unsigned CTZ = DemandedMask.countr_zero();
1176 if (match(V: II->getArgOperand(i: 1), P: m_APInt(Res&: C)) &&
1177 CTZ >= C->getBitWidth() - C->countl_one())
1178 return II->getArgOperand(i: 0);
1179 break;
1180 }
1181 default: {
1182 // Handle target specific intrinsics
1183 std::optional<Value *> V = targetSimplifyDemandedUseBitsIntrinsic(
1184 II&: *II, DemandedMask, Known, KnownBitsComputed);
1185 if (V)
1186 return *V;
1187 break;
1188 }
1189 }
1190 }
1191
1192 if (!KnownBitsComputed)
1193 llvm::computeKnownBits(V: I, Known, Q, Depth);
1194 break;
1195 }
1196 }
1197
1198 if (I->getType()->isPointerTy()) {
1199 Align Alignment = I->getPointerAlignment(DL);
1200 Known.Zero.setLowBits(Log2(A: Alignment));
1201 }
1202
1203 // If the client is only demanding bits that we know, return the known
1204 // constant. We can't directly simplify pointers as a constant because of
1205 // pointer provenance.
1206 // TODO: We could return `(inttoptr const)` for pointers.
1207 if (!I->getType()->isPointerTy() &&
1208 DemandedMask.isSubsetOf(RHS: Known.Zero | Known.One))
1209 return Constant::getIntegerValue(Ty: VTy, V: Known.One);
1210
1211 if (VerifyKnownBits) {
1212 KnownBits ReferenceKnown = llvm::computeKnownBits(V: I, Q, Depth);
1213 if (Known != ReferenceKnown) {
1214 errs() << "Mismatched known bits for " << *I << " in "
1215 << I->getFunction()->getName() << "\n";
1216 errs() << "computeKnownBits(): " << ReferenceKnown << "\n";
1217 errs() << "SimplifyDemandedBits(): " << Known << "\n";
1218 std::abort();
1219 }
1220 }
1221
1222 return nullptr;
1223}
1224
1225/// Helper routine of SimplifyDemandedUseBits. It computes Known
1226/// bits. It also tries to handle simplifications that can be done based on
1227/// DemandedMask, but without modifying the Instruction.
1228Value *InstCombinerImpl::SimplifyMultipleUseDemandedBits(
1229 Instruction *I, const APInt &DemandedMask, KnownBits &Known,
1230 const SimplifyQuery &Q, unsigned Depth) {
1231 unsigned BitWidth = DemandedMask.getBitWidth();
1232 Type *ITy = I->getType();
1233
1234 KnownBits LHSKnown(BitWidth);
1235 KnownBits RHSKnown(BitWidth);
1236
1237 // Despite the fact that we can't simplify this instruction in all User's
1238 // context, we can at least compute the known bits, and we can
1239 // do simplifications that apply to *just* the one user if we know that
1240 // this instruction has a simpler value in that context.
1241 switch (I->getOpcode()) {
1242 case Instruction::And: {
1243 llvm::computeKnownBits(V: I->getOperand(i: 1), Known&: RHSKnown, Q, Depth: Depth + 1);
1244 llvm::computeKnownBits(V: I->getOperand(i: 0), Known&: LHSKnown, Q, Depth: Depth + 1);
1245 Known = analyzeKnownBitsFromAndXorOr(I: cast<Operator>(Val: I), KnownLHS: LHSKnown, KnownRHS: RHSKnown,
1246 SQ: Q, Depth);
1247 computeKnownBitsFromContext(V: I, Known, Q, Depth);
1248
1249 // If the client is only demanding bits that we know, return the known
1250 // constant.
1251 if (DemandedMask.isSubsetOf(RHS: Known.Zero | Known.One))
1252 return Constant::getIntegerValue(Ty: ITy, V: Known.One);
1253
1254 // If all of the demanded bits are known 1 on one side, return the other.
1255 // These bits cannot contribute to the result of the 'and' in this context.
1256 if (DemandedMask.isSubsetOf(RHS: LHSKnown.Zero | RHSKnown.One))
1257 return I->getOperand(i: 0);
1258 if (DemandedMask.isSubsetOf(RHS: RHSKnown.Zero | LHSKnown.One))
1259 return I->getOperand(i: 1);
1260
1261 break;
1262 }
1263 case Instruction::Or: {
1264 llvm::computeKnownBits(V: I->getOperand(i: 1), Known&: RHSKnown, Q, Depth: Depth + 1);
1265 llvm::computeKnownBits(V: I->getOperand(i: 0), Known&: LHSKnown, Q, Depth: Depth + 1);
1266 Known = analyzeKnownBitsFromAndXorOr(I: cast<Operator>(Val: I), KnownLHS: LHSKnown, KnownRHS: RHSKnown,
1267 SQ: Q, Depth);
1268 computeKnownBitsFromContext(V: I, Known, Q, Depth);
1269
1270 // If the client is only demanding bits that we know, return the known
1271 // constant.
1272 if (DemandedMask.isSubsetOf(RHS: Known.Zero | Known.One))
1273 return Constant::getIntegerValue(Ty: ITy, V: Known.One);
1274
1275 // We can simplify (X|Y) -> X or Y in the user's context if we know that
1276 // only bits from X or Y are demanded.
1277 // If all of the demanded bits are known zero on one side, return the other.
1278 // These bits cannot contribute to the result of the 'or' in this context.
1279 if (DemandedMask.isSubsetOf(RHS: LHSKnown.One | RHSKnown.Zero))
1280 return I->getOperand(i: 0);
1281 if (DemandedMask.isSubsetOf(RHS: RHSKnown.One | LHSKnown.Zero))
1282 return I->getOperand(i: 1);
1283
1284 break;
1285 }
1286 case Instruction::Xor: {
1287 llvm::computeKnownBits(V: I->getOperand(i: 1), Known&: RHSKnown, Q, Depth: Depth + 1);
1288 llvm::computeKnownBits(V: I->getOperand(i: 0), Known&: LHSKnown, Q, Depth: Depth + 1);
1289 Known = analyzeKnownBitsFromAndXorOr(I: cast<Operator>(Val: I), KnownLHS: LHSKnown, KnownRHS: RHSKnown,
1290 SQ: Q, Depth);
1291 computeKnownBitsFromContext(V: I, Known, Q, Depth);
1292
1293 // If the client is only demanding bits that we know, return the known
1294 // constant.
1295 if (DemandedMask.isSubsetOf(RHS: Known.Zero | Known.One))
1296 return Constant::getIntegerValue(Ty: ITy, V: Known.One);
1297
1298 // We can simplify (X^Y) -> X or Y in the user's context if we know that
1299 // only bits from X or Y are demanded.
1300 // If all of the demanded bits are known zero on one side, return the other.
1301 if (DemandedMask.isSubsetOf(RHS: RHSKnown.Zero))
1302 return I->getOperand(i: 0);
1303 if (DemandedMask.isSubsetOf(RHS: LHSKnown.Zero))
1304 return I->getOperand(i: 1);
1305
1306 break;
1307 }
1308 case Instruction::Add: {
1309 unsigned NLZ = DemandedMask.countl_zero();
1310 APInt DemandedFromOps = APInt::getLowBitsSet(numBits: BitWidth, loBitsSet: BitWidth - NLZ);
1311
1312 // If an operand adds zeros to every bit below the highest demanded bit,
1313 // that operand doesn't change the result. Return the other side.
1314 llvm::computeKnownBits(V: I->getOperand(i: 1), Known&: RHSKnown, Q, Depth: Depth + 1);
1315 if (DemandedFromOps.isSubsetOf(RHS: RHSKnown.Zero))
1316 return I->getOperand(i: 0);
1317
1318 llvm::computeKnownBits(V: I->getOperand(i: 0), Known&: LHSKnown, Q, Depth: Depth + 1);
1319 if (DemandedFromOps.isSubsetOf(RHS: LHSKnown.Zero))
1320 return I->getOperand(i: 1);
1321
1322 bool NSW = cast<OverflowingBinaryOperator>(Val: I)->hasNoSignedWrap();
1323 bool NUW = cast<OverflowingBinaryOperator>(Val: I)->hasNoUnsignedWrap();
1324 Known = KnownBits::add(LHS: LHSKnown, RHS: RHSKnown, NSW, NUW);
1325 computeKnownBitsFromContext(V: I, Known, Q, Depth);
1326 break;
1327 }
1328 case Instruction::Sub: {
1329 unsigned NLZ = DemandedMask.countl_zero();
1330 APInt DemandedFromOps = APInt::getLowBitsSet(numBits: BitWidth, loBitsSet: BitWidth - NLZ);
1331
1332 // If an operand subtracts zeros from every bit below the highest demanded
1333 // bit, that operand doesn't change the result. Return the other side.
1334 llvm::computeKnownBits(V: I->getOperand(i: 1), Known&: RHSKnown, Q, Depth: Depth + 1);
1335 if (DemandedFromOps.isSubsetOf(RHS: RHSKnown.Zero))
1336 return I->getOperand(i: 0);
1337
1338 bool NSW = cast<OverflowingBinaryOperator>(Val: I)->hasNoSignedWrap();
1339 bool NUW = cast<OverflowingBinaryOperator>(Val: I)->hasNoUnsignedWrap();
1340 llvm::computeKnownBits(V: I->getOperand(i: 0), Known&: LHSKnown, Q, Depth: Depth + 1);
1341 Known = KnownBits::sub(LHS: LHSKnown, RHS: RHSKnown, NSW, NUW);
1342 computeKnownBitsFromContext(V: I, Known, Q, Depth);
1343 break;
1344 }
1345 case Instruction::AShr: {
1346 // Compute the Known bits to simplify things downstream.
1347 llvm::computeKnownBits(V: I, Known, Q, Depth);
1348
1349 // If this user is only demanding bits that we know, return the known
1350 // constant.
1351 if (DemandedMask.isSubsetOf(RHS: Known.Zero | Known.One))
1352 return Constant::getIntegerValue(Ty: ITy, V: Known.One);
1353
1354 // If the right shift operand 0 is a result of a left shift by the same
1355 // amount, this is probably a zero/sign extension, which may be unnecessary,
1356 // if we do not demand any of the new sign bits. So, return the original
1357 // operand instead.
1358 const APInt *ShiftRC;
1359 const APInt *ShiftLC;
1360 Value *X;
1361 unsigned BitWidth = DemandedMask.getBitWidth();
1362 if (match(V: I,
1363 P: m_AShr(L: m_Shl(L: m_Value(V&: X), R: m_APInt(Res&: ShiftLC)), R: m_APInt(Res&: ShiftRC))) &&
1364 ShiftLC == ShiftRC && ShiftLC->ult(RHS: BitWidth) &&
1365 DemandedMask.isSubsetOf(RHS: APInt::getLowBitsSet(
1366 numBits: BitWidth, loBitsSet: BitWidth - ShiftRC->getZExtValue()))) {
1367 return X;
1368 }
1369
1370 break;
1371 }
1372 default:
1373 // Compute the Known bits to simplify things downstream.
1374 llvm::computeKnownBits(V: I, Known, Q, Depth);
1375
1376 // If this user is only demanding bits that we know, return the known
1377 // constant.
1378 if (DemandedMask.isSubsetOf(RHS: Known.Zero|Known.One))
1379 return Constant::getIntegerValue(Ty: ITy, V: Known.One);
1380
1381 break;
1382 }
1383
1384 return nullptr;
1385}
1386
1387/// Helper routine of SimplifyDemandedUseBits. It tries to simplify
1388/// "E1 = (X lsr C1) << C2", where the C1 and C2 are constant, into
1389/// "E2 = X << (C2 - C1)" or "E2 = X >> (C1 - C2)", depending on the sign
1390/// of "C2-C1".
1391///
1392/// Suppose E1 and E2 are generally different in bits S={bm, bm+1,
1393/// ..., bn}, without considering the specific value X is holding.
1394/// This transformation is legal iff one of following conditions is hold:
1395/// 1) All the bit in S are 0, in this case E1 == E2.
1396/// 2) We don't care those bits in S, per the input DemandedMask.
1397/// 3) Combination of 1) and 2). Some bits in S are 0, and we don't care the
1398/// rest bits.
1399///
1400/// Currently we only test condition 2).
1401///
1402/// As with SimplifyDemandedUseBits, it returns NULL if the simplification was
1403/// not successful.
1404Value *InstCombinerImpl::simplifyShrShlDemandedBits(
1405 Instruction *Shr, const APInt &ShrOp1, Instruction *Shl,
1406 const APInt &ShlOp1, const APInt &DemandedMask, KnownBits &Known) {
1407 if (!ShlOp1 || !ShrOp1)
1408 return nullptr; // No-op.
1409
1410 Value *VarX = Shr->getOperand(i: 0);
1411 Type *Ty = VarX->getType();
1412 unsigned BitWidth = Ty->getScalarSizeInBits();
1413 if (ShlOp1.uge(RHS: BitWidth) || ShrOp1.uge(RHS: BitWidth))
1414 return nullptr; // Undef.
1415
1416 unsigned ShlAmt = ShlOp1.getZExtValue();
1417 unsigned ShrAmt = ShrOp1.getZExtValue();
1418
1419 Known.One.clearAllBits();
1420 Known.Zero.setLowBits(ShlAmt - 1);
1421 Known.Zero &= DemandedMask;
1422
1423 APInt BitMask1(APInt::getAllOnes(numBits: BitWidth));
1424 APInt BitMask2(APInt::getAllOnes(numBits: BitWidth));
1425
1426 bool isLshr = (Shr->getOpcode() == Instruction::LShr);
1427 BitMask1 = isLshr ? (BitMask1.lshr(shiftAmt: ShrAmt) << ShlAmt) :
1428 (BitMask1.ashr(ShiftAmt: ShrAmt) << ShlAmt);
1429
1430 if (ShrAmt <= ShlAmt) {
1431 BitMask2 <<= (ShlAmt - ShrAmt);
1432 } else {
1433 BitMask2 = isLshr ? BitMask2.lshr(shiftAmt: ShrAmt - ShlAmt):
1434 BitMask2.ashr(ShiftAmt: ShrAmt - ShlAmt);
1435 }
1436
1437 // Check if condition-2 (see the comment to this function) is satified.
1438 if ((BitMask1 & DemandedMask) == (BitMask2 & DemandedMask)) {
1439 if (ShrAmt == ShlAmt)
1440 return VarX;
1441
1442 if (!Shr->hasOneUse())
1443 return nullptr;
1444
1445 BinaryOperator *New;
1446 if (ShrAmt < ShlAmt) {
1447 Constant *Amt = ConstantInt::get(Ty: VarX->getType(), V: ShlAmt - ShrAmt);
1448 New = BinaryOperator::CreateShl(V1: VarX, V2: Amt);
1449 BinaryOperator *Orig = cast<BinaryOperator>(Val: Shl);
1450 New->setHasNoSignedWrap(Orig->hasNoSignedWrap());
1451 New->setHasNoUnsignedWrap(Orig->hasNoUnsignedWrap());
1452 } else {
1453 Constant *Amt = ConstantInt::get(Ty: VarX->getType(), V: ShrAmt - ShlAmt);
1454 New = isLshr ? BinaryOperator::CreateLShr(V1: VarX, V2: Amt) :
1455 BinaryOperator::CreateAShr(V1: VarX, V2: Amt);
1456 if (cast<BinaryOperator>(Val: Shr)->isExact())
1457 New->setIsExact(true);
1458 }
1459
1460 return InsertNewInstWith(New, Old: Shl->getIterator());
1461 }
1462
1463 return nullptr;
1464}
1465
1466/// Return true if the top-level all-lanes demanded-elements query can be
1467/// skipped for an intermediate insertelement chain node. This is limited to a
1468/// bounded one-use chain with distinct in-range constant indices, where SDVE
1469/// cannot remove a dead insert before hitting its depth limit.
1470static bool canSkipDemandedEltsInInsertChain(InsertElementInst &IE,
1471 unsigned VWidth,
1472 unsigned DepthLimit) {
1473 // Only skip chain nodes that feed another insertelement; the final chain root
1474 // still runs the full query.
1475 if (!IE.hasOneUse())
1476 return false;
1477 auto *UserIE = dyn_cast<InsertElementInst>(Val: IE.user_back());
1478 if (!UserIE || UserIE->getOperand(i_nocapture: 0) != &IE)
1479 return false;
1480
1481 SmallBitVector SeenIndices(VWidth);
1482 auto HasNewIndexInRange = [&](InsertElementInst &Insert) {
1483 auto *Idx = dyn_cast<ConstantInt>(Val: Insert.getOperand(i_nocapture: 2));
1484 // Let the normal SDVE path handle variable or out-of-range indices. The
1485 // latter may simplify the chain and must not be passed to getZExtValue().
1486 if (!Idx || Idx->getValue().uge(RHS: VWidth))
1487 return false;
1488
1489 unsigned Index = Idx->getZExtValue();
1490 if (SeenIndices.test(Idx: Index))
1491 return false;
1492
1493 SeenIndices.set(Index);
1494 return true;
1495 };
1496
1497 auto *Cur = &IE;
1498 for (unsigned I = 0; I != DepthLimit; ++I) {
1499 // This loop scans the same base-chain window that the SDVE query would
1500 // inspect before hitting its depth limit. With distinct insert indices in
1501 // that window, the all-lanes query cannot remove a dead insert; with
1502 // VWidth > DepthLimit, it also cannot narrow demand to a single lane.
1503 if (!HasNewIndexInRange(*Cur))
1504 return false;
1505
1506 Value *Base = Cur->getOperand(i_nocapture: 0);
1507 if (match(V: Base, P: m_Poison()))
1508 return true;
1509
1510 Cur = dyn_cast<InsertElementInst>(Val: Base);
1511 if (!Cur || !Cur->hasOneUse())
1512 return false;
1513 }
1514
1515 return true;
1516}
1517
1518/// The specified value produces a vector with any number of elements.
1519/// This method analyzes which elements of the operand are poison and
1520/// returns that information in PoisonElts.
1521///
1522/// DemandedElts contains the set of elements that are actually used by the
1523/// caller, and by default (AllowMultipleUsers equals false) the value is
1524/// simplified only if it has a single caller. If AllowMultipleUsers is set
1525/// to true, DemandedElts refers to the union of sets of elements that are
1526/// used by all callers.
1527///
1528/// If the information about demanded elements can be used to simplify the
1529/// operation, the operation is simplified, then the resultant value is
1530/// returned. This returns null if no change was made.
1531Value *InstCombinerImpl::SimplifyDemandedVectorElts(Value *V,
1532 APInt DemandedElts,
1533 APInt &PoisonElts,
1534 unsigned Depth,
1535 bool AllowMultipleUsers) {
1536 // Cannot analyze scalable type. The number of vector elements is not a
1537 // compile-time constant.
1538 if (isa<ScalableVectorType>(Val: V->getType()))
1539 return nullptr;
1540
1541 unsigned VWidth = cast<FixedVectorType>(Val: V->getType())->getNumElements();
1542 APInt EltMask(APInt::getAllOnes(numBits: VWidth));
1543 assert((DemandedElts & ~EltMask) == 0 && "Invalid DemandedElts!");
1544
1545 if (match(V, P: m_Poison())) {
1546 // If the entire vector is poison, just return this info.
1547 PoisonElts = EltMask;
1548 return nullptr;
1549 }
1550
1551 if (DemandedElts.isZero()) { // If nothing is demanded, provide poison.
1552 PoisonElts = EltMask;
1553 return PoisonValue::get(T: V->getType());
1554 }
1555
1556 PoisonElts = 0;
1557
1558 if (auto *C = dyn_cast<Constant>(Val: V)) {
1559 // Check if this is identity. If so, return 0 since we are not simplifying
1560 // anything.
1561 if (DemandedElts.isAllOnes())
1562 return nullptr;
1563
1564 Type *EltTy = cast<VectorType>(Val: V->getType())->getElementType();
1565 Constant *Poison = PoisonValue::get(T: EltTy);
1566 SmallVector<Constant*, 16> Elts;
1567 for (unsigned i = 0; i != VWidth; ++i) {
1568 if (!DemandedElts[i]) { // If not demanded, set to poison.
1569 Elts.push_back(Elt: Poison);
1570 PoisonElts.setBit(i);
1571 continue;
1572 }
1573
1574 Constant *Elt = C->getAggregateElement(Elt: i);
1575 if (!Elt) return nullptr;
1576
1577 Elts.push_back(Elt);
1578 if (isa<PoisonValue>(Val: Elt)) // Already poison.
1579 PoisonElts.setBit(i);
1580 }
1581
1582 // If we changed the constant, return it.
1583 Constant *NewCV = ConstantVector::get(V: Elts);
1584 return NewCV != C ? NewCV : nullptr;
1585 }
1586
1587 // Limit search depth.
1588 if (Depth == SimplifyDemandedVectorEltsDepthLimit)
1589 return nullptr;
1590
1591 if (!AllowMultipleUsers) {
1592 // If multiple users are using the root value, proceed with
1593 // simplification conservatively assuming that all elements
1594 // are needed.
1595 if (!V->hasOneUse()) {
1596 // Quit if we find multiple users of a non-root value though.
1597 // They'll be handled when it's their turn to be visited by
1598 // the main instcombine process.
1599 if (Depth != 0)
1600 // TODO: Just compute the PoisonElts information recursively.
1601 return nullptr;
1602
1603 // Conservatively assume that all elements are needed.
1604 DemandedElts = EltMask;
1605 }
1606 }
1607
1608 Instruction *I = dyn_cast<Instruction>(Val: V);
1609 if (!I) return nullptr; // Only analyze instructions.
1610
1611 bool MadeChange = false;
1612 auto simplifyAndSetOp = [&](Instruction *Inst, unsigned OpNum,
1613 APInt Demanded, APInt &Undef) {
1614 auto *II = dyn_cast<IntrinsicInst>(Val: Inst);
1615 Value *Op = II ? II->getArgOperand(i: OpNum) : Inst->getOperand(i: OpNum);
1616 if (Value *V = SimplifyDemandedVectorElts(V: Op, DemandedElts: Demanded, PoisonElts&: Undef, Depth: Depth + 1)) {
1617 replaceOperand(I&: *Inst, OpNum, V);
1618 MadeChange = true;
1619 }
1620 };
1621
1622 APInt PoisonElts2(VWidth, 0);
1623 APInt PoisonElts3(VWidth, 0);
1624 switch (I->getOpcode()) {
1625 default: break;
1626
1627 case Instruction::GetElementPtr: {
1628 // The LangRef requires that struct geps have all constant indices. As
1629 // such, we can't convert any operand to partial undef.
1630 auto mayIndexStructType = [](GetElementPtrInst &GEP) {
1631 for (auto I = gep_type_begin(GEP), E = gep_type_end(GEP);
1632 I != E; I++)
1633 if (I.isStruct())
1634 return true;
1635 return false;
1636 };
1637 if (mayIndexStructType(cast<GetElementPtrInst>(Val&: *I)))
1638 break;
1639
1640 // Conservatively track the demanded elements back through any vector
1641 // operands we may have. We know there must be at least one, or we
1642 // wouldn't have a vector result to get here. Note that we intentionally
1643 // merge the undef bits here since gepping with either an poison base or
1644 // index results in poison.
1645 for (unsigned i = 0; i < I->getNumOperands(); i++) {
1646 if (i == 0 ? match(V: I->getOperand(i), P: m_Undef())
1647 : match(V: I->getOperand(i), P: m_Poison())) {
1648 // If the entire vector is undefined, just return this info.
1649 PoisonElts = EltMask;
1650 return nullptr;
1651 }
1652 if (I->getOperand(i)->getType()->isVectorTy()) {
1653 APInt PoisonEltsOp(VWidth, 0);
1654 simplifyAndSetOp(I, i, DemandedElts, PoisonEltsOp);
1655 // gep(x, undef) is not undef, so skip considering idx ops here
1656 // Note that we could propagate poison, but we can't distinguish between
1657 // undef & poison bits ATM
1658 if (i == 0)
1659 PoisonElts |= PoisonEltsOp;
1660 }
1661 }
1662
1663 break;
1664 }
1665 case Instruction::InsertElement: {
1666 unsigned DepthLimit = SimplifyDemandedVectorEltsDepthLimit;
1667 auto *IE = cast<InsertElementInst>(Val: I);
1668 // Skip only when SDVE cannot simplify this insert chain before the limit.
1669 if (Depth == 0 && DemandedElts.isAllOnes() && VWidth > DepthLimit &&
1670 canSkipDemandedEltsInInsertChain(IE&: *IE, VWidth, DepthLimit))
1671 return nullptr;
1672
1673 // If this is a variable index, we don't know which element it overwrites.
1674 // demand exactly the same input as we produce.
1675 ConstantInt *Idx = dyn_cast<ConstantInt>(Val: I->getOperand(i: 2));
1676 if (!Idx) {
1677 // Note that we can't propagate undef elt info, because we don't know
1678 // which elt is getting updated.
1679 simplifyAndSetOp(I, 0, DemandedElts, PoisonElts2);
1680 break;
1681 }
1682
1683 // The element inserted overwrites whatever was there, so the input demanded
1684 // set is simpler than the output set.
1685 unsigned IdxNo = Idx->getZExtValue();
1686 APInt PreInsertDemandedElts = DemandedElts;
1687 if (IdxNo < VWidth)
1688 PreInsertDemandedElts.clearBit(BitPosition: IdxNo);
1689
1690 // If we only demand the element that is being inserted and that element
1691 // was extracted from the same index in another vector with the same type,
1692 // replace this insert with that other vector.
1693 // Note: This is attempted before the call to simplifyAndSetOp because that
1694 // may change PoisonElts to a value that does not match with Vec.
1695 Value *Vec;
1696 if (PreInsertDemandedElts == 0 &&
1697 match(V: I->getOperand(i: 1),
1698 P: m_ExtractElt(Val: m_Value(V&: Vec), Idx: m_SpecificInt(V: IdxNo))) &&
1699 Vec->getType() == I->getType()) {
1700 return Vec;
1701 }
1702
1703 simplifyAndSetOp(I, 0, PreInsertDemandedElts, PoisonElts);
1704
1705 // If this is inserting an element that isn't demanded, remove this
1706 // insertelement.
1707 if (IdxNo >= VWidth || !DemandedElts[IdxNo]) {
1708 Worklist.push(I);
1709 return I->getOperand(i: 0);
1710 }
1711
1712 // The inserted element is defined.
1713 PoisonElts.clearBit(BitPosition: IdxNo);
1714 break;
1715 }
1716 case Instruction::ShuffleVector: {
1717 auto *Shuffle = cast<ShuffleVectorInst>(Val: I);
1718 assert(Shuffle->getOperand(0)->getType() ==
1719 Shuffle->getOperand(1)->getType() &&
1720 "Expected shuffle operands to have same type");
1721 unsigned OpWidth = cast<FixedVectorType>(Val: Shuffle->getOperand(i_nocapture: 0)->getType())
1722 ->getNumElements();
1723 // Handle trivial case of a splat. Only check the first element of LHS
1724 // operand.
1725 if (all_of(Range: Shuffle->getShuffleMask(), P: equal_to(Arg: 0)) &&
1726 DemandedElts.isAllOnes()) {
1727 if (!isa<PoisonValue>(Val: I->getOperand(i: 1))) {
1728 I->setOperand(i: 1, Val: PoisonValue::get(T: I->getOperand(i: 1)->getType()));
1729 MadeChange = true;
1730 }
1731 APInt LeftDemanded(OpWidth, 1);
1732 APInt LHSPoisonElts(OpWidth, 0);
1733 simplifyAndSetOp(I, 0, LeftDemanded, LHSPoisonElts);
1734 if (LHSPoisonElts[0])
1735 PoisonElts = EltMask;
1736 else
1737 PoisonElts.clearAllBits();
1738 break;
1739 }
1740
1741 APInt LeftDemanded(OpWidth, 0), RightDemanded(OpWidth, 0);
1742 for (unsigned i = 0; i < VWidth; i++) {
1743 if (DemandedElts[i]) {
1744 unsigned MaskVal = Shuffle->getMaskValue(Elt: i);
1745 if (MaskVal != -1u) {
1746 assert(MaskVal < OpWidth * 2 &&
1747 "shufflevector mask index out of range!");
1748 if (MaskVal < OpWidth)
1749 LeftDemanded.setBit(MaskVal);
1750 else
1751 RightDemanded.setBit(MaskVal - OpWidth);
1752 }
1753 }
1754 }
1755
1756 APInt LHSPoisonElts(OpWidth, 0);
1757 simplifyAndSetOp(I, 0, LeftDemanded, LHSPoisonElts);
1758
1759 APInt RHSPoisonElts(OpWidth, 0);
1760 simplifyAndSetOp(I, 1, RightDemanded, RHSPoisonElts);
1761
1762 // If this shuffle does not change the vector length and the elements
1763 // demanded by this shuffle are an identity mask, then this shuffle is
1764 // unnecessary.
1765 //
1766 // We are assuming canonical form for the mask, so the source vector is
1767 // operand 0 and operand 1 is not used.
1768 //
1769 // Note that if an element is demanded and this shuffle mask is undefined
1770 // for that element, then the shuffle is not considered an identity
1771 // operation. The shuffle prevents poison from the operand vector from
1772 // leaking to the result by replacing poison with an undefined value.
1773 if (VWidth == OpWidth) {
1774 bool IsIdentityShuffle = true;
1775 for (unsigned i = 0; i < VWidth; i++) {
1776 unsigned MaskVal = Shuffle->getMaskValue(Elt: i);
1777 if (DemandedElts[i] && i != MaskVal) {
1778 IsIdentityShuffle = false;
1779 break;
1780 }
1781 }
1782 if (IsIdentityShuffle)
1783 return Shuffle->getOperand(i_nocapture: 0);
1784 }
1785
1786 bool NewPoisonElts = false;
1787 unsigned LHSIdx = -1u, LHSValIdx = -1u;
1788 unsigned RHSIdx = -1u, RHSValIdx = -1u;
1789 bool LHSUniform = true;
1790 bool RHSUniform = true;
1791 for (unsigned i = 0; i < VWidth; i++) {
1792 unsigned MaskVal = Shuffle->getMaskValue(Elt: i);
1793 if (MaskVal == -1u) {
1794 PoisonElts.setBit(i);
1795 } else if (!DemandedElts[i]) {
1796 NewPoisonElts = true;
1797 PoisonElts.setBit(i);
1798 } else if (MaskVal < OpWidth) {
1799 if (LHSPoisonElts[MaskVal]) {
1800 NewPoisonElts = true;
1801 PoisonElts.setBit(i);
1802 } else {
1803 LHSIdx = LHSIdx == -1u ? i : OpWidth;
1804 LHSValIdx = LHSValIdx == -1u ? MaskVal : OpWidth;
1805 LHSUniform = LHSUniform && (MaskVal == i);
1806 }
1807 } else {
1808 if (RHSPoisonElts[MaskVal - OpWidth]) {
1809 NewPoisonElts = true;
1810 PoisonElts.setBit(i);
1811 } else {
1812 RHSIdx = RHSIdx == -1u ? i : OpWidth;
1813 RHSValIdx = RHSValIdx == -1u ? MaskVal - OpWidth : OpWidth;
1814 RHSUniform = RHSUniform && (MaskVal - OpWidth == i);
1815 }
1816 }
1817 }
1818
1819 // Try to transform shuffle with constant vector and single element from
1820 // this constant vector to single insertelement instruction.
1821 // shufflevector V, C, <v1, v2, .., ci, .., vm> ->
1822 // insertelement V, C[ci], ci-n
1823 if (OpWidth ==
1824 cast<FixedVectorType>(Val: Shuffle->getType())->getNumElements()) {
1825 Value *Op = nullptr;
1826 Constant *Value = nullptr;
1827 unsigned Idx = -1u;
1828
1829 // Find constant vector with the single element in shuffle (LHS or RHS).
1830 if (LHSIdx < OpWidth && RHSUniform) {
1831 if (auto *CV = dyn_cast<ConstantVector>(Val: Shuffle->getOperand(i_nocapture: 0))) {
1832 Op = Shuffle->getOperand(i_nocapture: 1);
1833 Value = CV->getOperand(i_nocapture: LHSValIdx);
1834 Idx = LHSIdx;
1835 }
1836 }
1837 if (RHSIdx < OpWidth && LHSUniform) {
1838 if (auto *CV = dyn_cast<ConstantVector>(Val: Shuffle->getOperand(i_nocapture: 1))) {
1839 Op = Shuffle->getOperand(i_nocapture: 0);
1840 Value = CV->getOperand(i_nocapture: RHSValIdx);
1841 Idx = RHSIdx;
1842 }
1843 }
1844 // Found constant vector with single element - convert to insertelement.
1845 if (Op && Value) {
1846 Instruction *New = InsertElementInst::Create(
1847 Vec: Op, NewElt: Value, Idx: ConstantInt::get(Ty: Type::getInt64Ty(C&: I->getContext()), V: Idx),
1848 NameStr: Shuffle->getName());
1849 InsertNewInstWith(New, Old: Shuffle->getIterator());
1850 return New;
1851 }
1852 }
1853 if (NewPoisonElts) {
1854 // Add additional discovered undefs.
1855 SmallVector<int, 16> Elts;
1856 for (unsigned i = 0; i < VWidth; ++i) {
1857 if (PoisonElts[i])
1858 Elts.push_back(Elt: PoisonMaskElem);
1859 else
1860 Elts.push_back(Elt: Shuffle->getMaskValue(Elt: i));
1861 }
1862 Shuffle->setShuffleMask(Elts);
1863 MadeChange = true;
1864 }
1865 break;
1866 }
1867 case Instruction::Select: {
1868 // If this is a vector select, try to transform the select condition based
1869 // on the current demanded elements.
1870 SelectInst *Sel = cast<SelectInst>(Val: I);
1871 if (Sel->getCondition()->getType()->isVectorTy()) {
1872 // TODO: We are not doing anything with PoisonElts based on this call.
1873 // It is overwritten below based on the other select operands. If an
1874 // element of the select condition is known undef, then we are free to
1875 // choose the output value from either arm of the select. If we know that
1876 // one of those values is undef, then the output can be undef.
1877 simplifyAndSetOp(I, 0, DemandedElts, PoisonElts);
1878 }
1879
1880 // Next, see if we can transform the arms of the select.
1881 APInt DemandedLHS(DemandedElts), DemandedRHS(DemandedElts);
1882 if (auto *CV = dyn_cast<ConstantVector>(Val: Sel->getCondition())) {
1883 for (unsigned i = 0; i < VWidth; i++) {
1884 Constant *CElt = CV->getAggregateElement(Elt: i);
1885
1886 // isNullValue() always returns false when called on a ConstantExpr.
1887 if (CElt->isNullValue())
1888 DemandedLHS.clearBit(BitPosition: i);
1889 else if (CElt->isOneValue())
1890 DemandedRHS.clearBit(BitPosition: i);
1891 }
1892 }
1893
1894 simplifyAndSetOp(I, 1, DemandedLHS, PoisonElts2);
1895 simplifyAndSetOp(I, 2, DemandedRHS, PoisonElts3);
1896
1897 // Output elements are undefined if the element from each arm is undefined.
1898 // TODO: This can be improved. See comment in select condition handling.
1899 PoisonElts = PoisonElts2 & PoisonElts3;
1900 break;
1901 }
1902 case Instruction::BitCast: {
1903 // Vector->vector casts only.
1904 VectorType *VTy = dyn_cast<VectorType>(Val: I->getOperand(i: 0)->getType());
1905 if (!VTy) break;
1906 unsigned InVWidth = cast<FixedVectorType>(Val: VTy)->getNumElements();
1907 APInt InputDemandedElts(InVWidth, 0);
1908 PoisonElts2 = APInt(InVWidth, 0);
1909 unsigned Ratio;
1910
1911 if (VWidth == InVWidth) {
1912 // If we are converting from <4 x i32> -> <4 x f32>, we demand the same
1913 // elements as are demanded of us.
1914 Ratio = 1;
1915 InputDemandedElts = DemandedElts;
1916 } else if ((VWidth % InVWidth) == 0) {
1917 // If the number of elements in the output is a multiple of the number of
1918 // elements in the input then an input element is live if any of the
1919 // corresponding output elements are live.
1920 Ratio = VWidth / InVWidth;
1921 for (unsigned OutIdx = 0; OutIdx != VWidth; ++OutIdx)
1922 if (DemandedElts[OutIdx])
1923 InputDemandedElts.setBit(OutIdx / Ratio);
1924 } else if ((InVWidth % VWidth) == 0) {
1925 // If the number of elements in the input is a multiple of the number of
1926 // elements in the output then an input element is live if the
1927 // corresponding output element is live.
1928 Ratio = InVWidth / VWidth;
1929 for (unsigned InIdx = 0; InIdx != InVWidth; ++InIdx)
1930 if (DemandedElts[InIdx / Ratio])
1931 InputDemandedElts.setBit(InIdx);
1932 } else {
1933 // Unsupported so far.
1934 break;
1935 }
1936
1937 simplifyAndSetOp(I, 0, InputDemandedElts, PoisonElts2);
1938
1939 if (VWidth == InVWidth) {
1940 PoisonElts = PoisonElts2;
1941 } else if ((VWidth % InVWidth) == 0) {
1942 // If the number of elements in the output is a multiple of the number of
1943 // elements in the input then an output element is undef if the
1944 // corresponding input element is undef.
1945 for (unsigned OutIdx = 0; OutIdx != VWidth; ++OutIdx)
1946 if (PoisonElts2[OutIdx / Ratio])
1947 PoisonElts.setBit(OutIdx);
1948 } else if ((InVWidth % VWidth) == 0) {
1949 // If the number of elements in the input is a multiple of the number of
1950 // elements in the output then an output element is undef if all of the
1951 // corresponding input elements are undef.
1952 for (unsigned OutIdx = 0; OutIdx != VWidth; ++OutIdx) {
1953 APInt SubUndef = PoisonElts2.lshr(shiftAmt: OutIdx * Ratio).zextOrTrunc(width: Ratio);
1954 if (SubUndef.popcount() == Ratio)
1955 PoisonElts.setBit(OutIdx);
1956 }
1957 } else {
1958 llvm_unreachable("Unimp");
1959 }
1960 break;
1961 }
1962 case Instruction::FPTrunc:
1963 case Instruction::FPExt:
1964 simplifyAndSetOp(I, 0, DemandedElts, PoisonElts);
1965 break;
1966
1967 case Instruction::Call: {
1968 IntrinsicInst *II = dyn_cast<IntrinsicInst>(Val: I);
1969 if (!II) break;
1970 switch (II->getIntrinsicID()) {
1971 case Intrinsic::masked_gather: // fallthrough
1972 case Intrinsic::masked_load: {
1973 // Subtlety: If we load from a pointer, the pointer must be valid
1974 // regardless of whether the element is demanded. Doing otherwise risks
1975 // segfaults which didn't exist in the original program.
1976 APInt DemandedPtrs(APInt::getAllOnes(numBits: VWidth)),
1977 DemandedPassThrough(DemandedElts);
1978 if (auto *CMask = dyn_cast<Constant>(Val: II->getOperand(i_nocapture: 1))) {
1979 for (unsigned i = 0; i < VWidth; i++) {
1980 if (Constant *CElt = CMask->getAggregateElement(Elt: i)) {
1981 if (CElt->isNullValue())
1982 DemandedPtrs.clearBit(BitPosition: i);
1983 else if (CElt->isAllOnesValue())
1984 DemandedPassThrough.clearBit(BitPosition: i);
1985 }
1986 }
1987 }
1988
1989 if (II->getIntrinsicID() == Intrinsic::masked_gather)
1990 simplifyAndSetOp(II, 0, DemandedPtrs, PoisonElts2);
1991 simplifyAndSetOp(II, 2, DemandedPassThrough, PoisonElts3);
1992
1993 // Output elements are undefined if the element from both sources are.
1994 // TODO: can strengthen via mask as well.
1995 PoisonElts = PoisonElts2 & PoisonElts3;
1996 break;
1997 }
1998 default: {
1999 // Handle target specific intrinsics
2000 std::optional<Value *> V = targetSimplifyDemandedVectorEltsIntrinsic(
2001 II&: *II, DemandedElts, UndefElts&: PoisonElts, UndefElts2&: PoisonElts2, UndefElts3&: PoisonElts3,
2002 SimplifyAndSetOp: simplifyAndSetOp);
2003 if (V)
2004 return *V;
2005 break;
2006 }
2007 } // switch on IntrinsicID
2008 break;
2009 } // case Call
2010 } // switch on Opcode
2011
2012 // TODO: We bail completely on integer div/rem and shifts because they have
2013 // UB/poison potential, but that should be refined.
2014 BinaryOperator *BO;
2015 if (match(V: I, P: m_BinOp(I&: BO)) && !BO->isIntDivRem() && !BO->isShift()) {
2016 Value *X = BO->getOperand(i_nocapture: 0);
2017 Value *Y = BO->getOperand(i_nocapture: 1);
2018
2019 // Look for an equivalent binop except that one operand has been shuffled.
2020 // If the demand for this binop only includes elements that are the same as
2021 // the other binop, then we may be able to replace this binop with a use of
2022 // the earlier one.
2023 //
2024 // Example:
2025 // %other_bo = bo (shuf X, {0}), Y
2026 // %this_extracted_bo = extelt (bo X, Y), 0
2027 // -->
2028 // %other_bo = bo (shuf X, {0}), Y
2029 // %this_extracted_bo = extelt %other_bo, 0
2030 //
2031 // TODO: Handle demand of an arbitrary single element or more than one
2032 // element instead of just element 0.
2033 // TODO: Unlike general demanded elements transforms, this should be safe
2034 // for any (div/rem/shift) opcode too.
2035 if (DemandedElts == 1 && !X->hasOneUse() && !Y->hasOneUse() &&
2036 BO->hasOneUse() ) {
2037
2038 auto findShufBO = [&](bool MatchShufAsOp0) -> User * {
2039 // Try to use shuffle-of-operand in place of an operand:
2040 // bo X, Y --> bo (shuf X), Y
2041 // bo X, Y --> bo X, (shuf Y)
2042
2043 Value *OtherOp = MatchShufAsOp0 ? Y : X;
2044 if (!OtherOp->hasUseList())
2045 return nullptr;
2046
2047 BinaryOperator::BinaryOps Opcode = BO->getOpcode();
2048 Value *ShufOp = MatchShufAsOp0 ? X : Y;
2049
2050 for (User *U : OtherOp->users()) {
2051 ArrayRef<int> Mask;
2052 auto Shuf = m_Shuffle(v1: m_Specific(V: ShufOp), v2: m_Value(), mask: m_Mask(Mask));
2053 if (BO->isCommutative()
2054 ? match(V: U, P: m_c_BinOp(Opcode, L: Shuf, R: m_Specific(V: OtherOp)))
2055 : MatchShufAsOp0
2056 ? match(V: U, P: m_BinOp(Opcode, L: Shuf, R: m_Specific(V: OtherOp)))
2057 : match(V: U, P: m_BinOp(Opcode, L: m_Specific(V: OtherOp), R: Shuf)))
2058 if (match(Mask, P: m_ZeroMask()) && Mask[0] != PoisonMaskElem)
2059 if (DT.dominates(Def: U, User: I))
2060 return U;
2061 }
2062 return nullptr;
2063 };
2064
2065 User *ShufBO = findShufBO(/* MatchShufAsOp0 */ true);
2066 if (!ShufBO)
2067 ShufBO = findShufBO(/* MatchShufAsOp0 */ false);
2068 if (ShufBO) {
2069 auto *ShufBOI = cast<Instruction>(Val: ShufBO);
2070 ShufBOI->andIRFlags(V: BO);
2071 Worklist.add(I: ShufBOI);
2072 return ShufBO;
2073 }
2074 }
2075
2076 simplifyAndSetOp(I, 0, DemandedElts, PoisonElts);
2077 simplifyAndSetOp(I, 1, DemandedElts, PoisonElts2);
2078
2079 // Output elements are undefined if both are undefined. Consider things
2080 // like undef & 0. The result is known zero, not undef.
2081 PoisonElts &= PoisonElts2;
2082 }
2083
2084 // If we've proven all of the lanes poison, return a poison value.
2085 // TODO: Intersect w/demanded lanes
2086 if (PoisonElts.isAllOnes())
2087 return PoisonValue::get(T: I->getType());
2088
2089 return MadeChange ? I : nullptr;
2090}
2091
2092/// For floating-point classes that resolve to a single bit pattern, return that
2093/// value.
2094static Constant *getFPClassConstant(Type *Ty, FPClassTest Mask,
2095 bool IsCanonicalizing = false) {
2096 if (Mask == fcNone)
2097 return PoisonValue::get(T: Ty);
2098
2099 if (Mask == fcPosZero)
2100 return Constant::getNullValue(Ty);
2101
2102 // TODO: Support aggregate types that are allowed by FPMathOperator.
2103 if (Ty->isAggregateType())
2104 return nullptr;
2105
2106 // Turn any possible snans into quiet if we can.
2107 if (Mask == fcNan && IsCanonicalizing)
2108 return ConstantFP::getQNaN(Ty);
2109
2110 switch (Mask) {
2111 case fcNegZero:
2112 return ConstantFP::getZero(Ty, Negative: true);
2113 case fcPosInf:
2114 return ConstantFP::getInfinity(Ty);
2115 case fcNegInf:
2116 return ConstantFP::getInfinity(Ty, Negative: true);
2117 case fcQNan:
2118 // Payload bits cannot be dropped for pure signbit operations.
2119 return IsCanonicalizing ? ConstantFP::getQNaN(Ty) : nullptr;
2120 default:
2121 return nullptr;
2122 }
2123}
2124
2125/// Perform multiple-use aware simplfications for fabs(\p Src). Returns a
2126/// replacement value if it's simplified, otherwise nullptr. Updates \p Known
2127/// with the known fpclass if not simplified.
2128static Value *simplifyDemandedFPClassFabs(KnownFPClass &Known, Value *Src,
2129 FPClassTest DemandedMask,
2130 KnownFPClass KnownSrc, bool NSZ) {
2131 if ((DemandedMask & fcNan) == fcNone)
2132 KnownSrc.knownNot(RuleOut: fcNan);
2133 if ((DemandedMask & fcInf) == fcNone)
2134 KnownSrc.knownNot(RuleOut: fcInf);
2135
2136 if (KnownSrc.getSignBit() == false ||
2137 ((DemandedMask & fcNan) == fcNone && KnownSrc.isKnownNever(Mask: fcNegative)))
2138 return Src;
2139
2140 // If the only sign bit difference is due to -0, ignore it with nsz
2141 if (NSZ &&
2142 KnownSrc.isKnownNever(Mask: KnownFPClass::OrderedLessThanZeroMask | fcNan))
2143 return Src;
2144
2145 Known = KnownFPClass::fabs(Src: KnownSrc);
2146 Known.knownNot(RuleOut: ~DemandedMask);
2147 return nullptr;
2148}
2149
2150/// Try to set an inferred no-nans or no-infs in \p FMF. \p ValidResults is a
2151/// mask of known valid results for the operator (already computed from the
2152/// result, and the known operand inputs in \p Known)
2153static FastMathFlags inferFastMathValueFlags(FastMathFlags FMF,
2154 FPClassTest ValidResults,
2155 ArrayRef<KnownFPClass> Known) {
2156 if (!FMF.noNaNs() && (ValidResults & fcNan) == fcNone) {
2157 if (all_of(Range&: Known, P: [](const KnownFPClass KnownSrc) {
2158 return KnownSrc.isKnownNeverNaN();
2159 }))
2160 FMF.setNoNaNs();
2161 }
2162
2163 if (!FMF.noInfs() && (ValidResults & fcInf) == fcNone) {
2164 if (all_of(Range&: Known, P: [](const KnownFPClass KnownSrc) {
2165 return KnownSrc.isKnownNeverInfinity();
2166 }))
2167 FMF.setNoInfs();
2168 }
2169
2170 return FMF;
2171}
2172
2173static FPClassTest adjustDemandedMaskFromFlags(FPClassTest DemandedMask,
2174 FastMathFlags FMF) {
2175 if (FMF.noNaNs())
2176 DemandedMask &= ~fcNan;
2177
2178 if (FMF.noInfs())
2179 DemandedMask &= ~fcInf;
2180 return DemandedMask;
2181}
2182
2183/// Apply epilog fixups to a floating-point intrinsic. See if the result can
2184/// fold to a constant, or apply fast math flags.
2185static Value *simplifyDemandedFPClassResult(Instruction *FPOp,
2186 FastMathFlags FMF,
2187 FPClassTest DemandedMask,
2188 KnownFPClass &Known,
2189 ArrayRef<KnownFPClass> KnownSrcs) {
2190 FPClassTest ValidResults = DemandedMask & Known.getKnownFPClasses();
2191 Constant *SingleVal = getFPClassConstant(Ty: FPOp->getType(), Mask: ValidResults,
2192 /*IsCanonicalizing=*/true);
2193 if (SingleVal)
2194 return SingleVal;
2195
2196 FastMathFlags InferredFMF =
2197 inferFastMathValueFlags(FMF, ValidResults, Known: KnownSrcs);
2198 if (InferredFMF != FMF) {
2199 FPOp->dropUBImplyingAttrsAndMetadata();
2200 FPOp->setFastMathFlags(InferredFMF);
2201 return FPOp;
2202 }
2203
2204 return nullptr;
2205}
2206
2207/// Perform multiple-use aware simplfications for fneg(fabs(\p Src)). Returns a
2208/// replacement value if it's simplified, otherwise nullptr. Updates \p Known
2209/// with the known fpclass if not simplified.
2210static Value *simplifyDemandedFPClassFnegFabs(KnownFPClass &Known, Value *Src,
2211 FPClassTest DemandedMask,
2212 KnownFPClass KnownSrc, bool NSZ) {
2213 if ((DemandedMask & fcNan) == fcNone)
2214 KnownSrc.knownNot(RuleOut: fcNan);
2215 if ((DemandedMask & fcInf) == fcNone)
2216 KnownSrc.knownNot(RuleOut: fcInf);
2217
2218 // If the source value is known negative, we can directly fold to it.
2219 if (KnownSrc.getSignBit() == true)
2220 return Src;
2221
2222 // If the only sign bit difference is for 0, ignore it with nsz.
2223 if (NSZ &&
2224 KnownSrc.isKnownNever(Mask: KnownFPClass::OrderedGreaterThanZeroMask | fcNan))
2225 return Src;
2226
2227 Known = KnownFPClass::fneg(Src: KnownFPClass::fabs(Src: KnownSrc));
2228 Known.knownNot(RuleOut: ~DemandedMask);
2229 return nullptr;
2230}
2231
2232static Value *simplifyDemandedFPClassCopysignMag(Value *MagSrc,
2233 FPClassTest DemandedMask,
2234 KnownFPClass KnownSrc,
2235 bool NSZ) {
2236 if (NSZ) {
2237 constexpr FPClassTest NegOrZero = fcNegative | fcPosZero;
2238 constexpr FPClassTest PosOrZero = fcPositive | fcNegZero;
2239
2240 if ((DemandedMask & ~NegOrZero) == fcNone &&
2241 KnownSrc.isKnownAlways(Mask: NegOrZero))
2242 return MagSrc;
2243
2244 if ((DemandedMask & ~PosOrZero) == fcNone &&
2245 KnownSrc.isKnownAlways(Mask: PosOrZero))
2246 return MagSrc;
2247 } else {
2248 if ((DemandedMask & ~fcNegative) == fcNone && KnownSrc.getSignBit() == true)
2249 return MagSrc;
2250
2251 if ((DemandedMask & ~fcPositive) == fcNone &&
2252 KnownSrc.getSignBit() == false)
2253 return MagSrc;
2254 }
2255
2256 return nullptr;
2257}
2258
2259static Value *
2260simplifyDemandedFPClassMinMax(KnownFPClass &Known, Intrinsic::ID IID,
2261 const CallInst *CI, FPClassTest DemandedMask,
2262 KnownFPClass KnownLHS, KnownFPClass KnownRHS,
2263 const Function &F, bool NSZ) {
2264 bool OrderedZeroSign = !NSZ;
2265
2266 KnownFPClass::MinMaxKind OpKind;
2267 switch (IID) {
2268 case Intrinsic::maximum: {
2269 OpKind = KnownFPClass::MinMaxKind::maximum;
2270
2271 // If one operand is known greater than the other, it must be that
2272 // operand unless the other is a nan.
2273 if (cannotOrderStrictlyLess(LHS: KnownLHS.getKnownFPClasses(),
2274 RHS: KnownRHS.getKnownFPClasses(),
2275 OrderedZeroSign) &&
2276 KnownRHS.isKnownNever(Mask: fcNan))
2277 return CI->getArgOperand(i: 0);
2278
2279 if (cannotOrderStrictlyGreater(LHS: KnownLHS.getKnownFPClasses(),
2280 RHS: KnownRHS.getKnownFPClasses(),
2281 OrderedZeroSign) &&
2282 KnownLHS.isKnownNever(Mask: fcNan))
2283 return CI->getArgOperand(i: 1);
2284
2285 break;
2286 }
2287 case Intrinsic::minimum: {
2288 OpKind = KnownFPClass::MinMaxKind::minimum;
2289
2290 // If one operand is known less than the other, it must be that operand
2291 // unless the other is a nan.
2292 if (cannotOrderStrictlyGreater(LHS: KnownLHS.getKnownFPClasses(),
2293 RHS: KnownRHS.getKnownFPClasses(),
2294 OrderedZeroSign) &&
2295 KnownRHS.isKnownNever(Mask: fcNan))
2296 return CI->getArgOperand(i: 0);
2297
2298 if (cannotOrderStrictlyLess(LHS: KnownLHS.getKnownFPClasses(),
2299 RHS: KnownRHS.getKnownFPClasses(),
2300 OrderedZeroSign) &&
2301 KnownLHS.isKnownNever(Mask: fcNan))
2302 return CI->getArgOperand(i: 1);
2303
2304 break;
2305 }
2306 case Intrinsic::maxnum:
2307 case Intrinsic::maximumnum: {
2308 OpKind = IID == Intrinsic::maxnum ? KnownFPClass::MinMaxKind::maxnum
2309 : KnownFPClass::MinMaxKind::maximumnum;
2310
2311 if (cannotOrderStrictlyLess(LHS: KnownLHS.getKnownFPClasses(),
2312 RHS: KnownRHS.getKnownFPClasses(),
2313 OrderedZeroSign) &&
2314 KnownLHS.isKnownNever(Mask: fcNan))
2315 return CI->getArgOperand(i: 0);
2316
2317 if (cannotOrderStrictlyGreater(LHS: KnownLHS.getKnownFPClasses(),
2318 RHS: KnownRHS.getKnownFPClasses(),
2319 OrderedZeroSign) &&
2320 KnownRHS.isKnownNever(Mask: fcNan))
2321 return CI->getArgOperand(i: 1);
2322
2323 break;
2324 }
2325 case Intrinsic::minnum:
2326 case Intrinsic::minimumnum: {
2327 OpKind = IID == Intrinsic::minnum ? KnownFPClass::MinMaxKind::minnum
2328 : KnownFPClass::MinMaxKind::minimumnum;
2329
2330 if (cannotOrderStrictlyGreater(LHS: KnownLHS.getKnownFPClasses(),
2331 RHS: KnownRHS.getKnownFPClasses(),
2332 OrderedZeroSign) &&
2333 KnownLHS.isKnownNever(Mask: fcNan))
2334 return CI->getArgOperand(i: 0);
2335
2336 if (cannotOrderStrictlyLess(LHS: KnownLHS.getKnownFPClasses(),
2337 RHS: KnownRHS.getKnownFPClasses(),
2338 OrderedZeroSign) &&
2339 KnownRHS.isKnownNever(Mask: fcNan))
2340 return CI->getArgOperand(i: 1);
2341
2342 break;
2343 }
2344 default:
2345 llvm_unreachable("not a min/max intrinsic");
2346 }
2347
2348 Type *EltTy = CI->getType()->getScalarType();
2349 DenormalMode Mode = F.getDenormalMode(FPType: EltTy->getFltSemantics());
2350 Known = KnownFPClass::minMaxLike(LHS: KnownLHS, RHS: KnownRHS, Kind: OpKind, DenormMode: Mode);
2351 Known.knownNot(RuleOut: ~DemandedMask);
2352
2353 return getFPClassConstant(Ty: CI->getType(), Mask: Known.getKnownFPClasses(),
2354 /*IsCanonicalizing=*/true);
2355}
2356
2357static Value *
2358simplifyDemandedUseFPClassFPTrunc(InstCombinerImpl &IC, Instruction &I,
2359 FastMathFlags FMF, FPClassTest DemandedMask,
2360 KnownFPClass &Known, const SimplifyQuery &SQ,
2361 unsigned Depth) {
2362
2363 FPClassTest SrcDemandedMask = DemandedMask;
2364 if (DemandedMask & fcNan)
2365 SrcDemandedMask |= fcNan;
2366
2367 // Zero results may have been rounded from subnormal or normal sources.
2368 if (DemandedMask & fcNegZero)
2369 SrcDemandedMask |= fcNegSubnormal | fcNegNormal;
2370 if (DemandedMask & fcPosZero)
2371 SrcDemandedMask |= fcPosSubnormal | fcPosNormal;
2372
2373 // Subnormal results may have been normal in the source type
2374 if (DemandedMask & fcNegSubnormal)
2375 SrcDemandedMask |= fcNegNormal;
2376 if (DemandedMask & fcPosSubnormal)
2377 SrcDemandedMask |= fcPosNormal;
2378
2379 if (DemandedMask & fcPosInf)
2380 SrcDemandedMask |= fcPosNormal;
2381 if (DemandedMask & fcNegInf)
2382 SrcDemandedMask |= fcNegNormal;
2383
2384 KnownFPClass KnownSrc;
2385 if (IC.SimplifyDemandedFPClass(I: &I, Op: 0, DemandedMask: SrcDemandedMask, Known&: KnownSrc, Q: SQ,
2386 Depth: Depth + 1))
2387 return &I;
2388
2389 Known = KnownFPClass::fptrunc(KnownSrc);
2390 Known.knownNot(RuleOut: ~DemandedMask);
2391
2392 return simplifyDemandedFPClassResult(FPOp: &I, FMF, DemandedMask, Known,
2393 KnownSrcs: {KnownSrc});
2394}
2395
2396Value *InstCombinerImpl::SimplifyDemandedUseFPClass(Instruction *I,
2397 FPClassTest DemandedMask,
2398 KnownFPClass &Known,
2399 const SimplifyQuery &SQ,
2400 unsigned Depth) {
2401 assert(Depth <= MaxAnalysisRecursionDepth && "Limit Search Depth");
2402 assert(Known == KnownFPClass() && "expected uninitialized state");
2403
2404 Type *VTy = I->getType();
2405
2406 FastMathFlags FMF;
2407 if (auto *FPOp = dyn_cast<FPMathOperator>(Val: I)) {
2408 FMF = FPOp->getFastMathFlags();
2409 DemandedMask = adjustDemandedMaskFromFlags(DemandedMask, FMF);
2410 }
2411
2412 switch (I->getOpcode()) {
2413 case Instruction::FNeg: {
2414 // Special case fneg(fabs(x))
2415
2416 Value *FNegSrc = I->getOperand(i: 0);
2417 Value *FNegFAbsSrc;
2418 if (match(V: FNegSrc, P: m_OneUse(SubPattern: m_FAbs(Op0: m_Value(V&: FNegFAbsSrc))))) {
2419 KnownFPClass KnownSrc;
2420 if (SimplifyDemandedFPClass(I: cast<Instruction>(Val: FNegSrc), Op: 0,
2421 DemandedMask: llvm::unknown_sign(Mask: DemandedMask), Known&: KnownSrc,
2422 Q: SQ, Depth: Depth + 1))
2423 return I;
2424
2425 FastMathFlags FabsFMF = cast<FPMathOperator>(Val: FNegSrc)->getFastMathFlags();
2426 FPClassTest ThisDemandedMask =
2427 adjustDemandedMaskFromFlags(DemandedMask, FMF: FabsFMF);
2428
2429 bool IsNSZ = FMF.noSignedZeros() || FabsFMF.noSignedZeros();
2430 if (Value *Simplified = simplifyDemandedFPClassFnegFabs(
2431 Known, Src: FNegFAbsSrc, DemandedMask: ThisDemandedMask, KnownSrc, NSZ: IsNSZ))
2432 return Simplified;
2433
2434 if ((ThisDemandedMask & fcNan) == fcNone)
2435 KnownSrc.knownNot(RuleOut: fcNan);
2436 if ((ThisDemandedMask & fcInf) == fcNone)
2437 KnownSrc.knownNot(RuleOut: fcInf);
2438
2439 // fneg(fabs(x)) => fneg(x)
2440 if (KnownSrc.getSignBit() == false)
2441 return replaceOperand(I&: *I, OpNum: 0, V: FNegFAbsSrc);
2442
2443 // fneg(fabs(x)) => fneg(x), ignoring -0 if nsz.
2444 if (IsNSZ &&
2445 KnownSrc.isKnownNever(Mask: KnownFPClass::OrderedLessThanZeroMask | fcNan))
2446 return replaceOperand(I&: *I, OpNum: 0, V: FNegFAbsSrc);
2447
2448 break;
2449 }
2450
2451 if (SimplifyDemandedFPClass(I, Op: 0, DemandedMask: llvm::fneg(Mask: DemandedMask), Known, Q: SQ,
2452 Depth: Depth + 1))
2453 return I;
2454 Known.fneg();
2455 Known.knownNot(RuleOut: ~DemandedMask);
2456 break;
2457 }
2458 case Instruction::FAdd:
2459 case Instruction::FSub: {
2460 KnownFPClass KnownLHS, KnownRHS;
2461
2462 // fadd x, x can be handled more aggressively.
2463 if (I->getOperand(i: 0) == I->getOperand(i: 1) &&
2464 I->getOpcode() == Instruction::FAdd &&
2465 isGuaranteedNotToBeUndef(V: I->getOperand(i: 0), AC: SQ.AC, CtxI: SQ.CxtI, DT: SQ.DT,
2466 Depth: Depth + 1)) {
2467 Type *EltTy = VTy->getScalarType();
2468 DenormalMode Mode = F.getDenormalMode(FPType: EltTy->getFltSemantics());
2469
2470 FPClassTest SrcDemandedMask = DemandedMask;
2471 if (DemandedMask & fcNan)
2472 SrcDemandedMask |= fcNan;
2473
2474 // Doubling a subnormal could have resulted in a normal value.
2475 if (DemandedMask & fcPosNormal)
2476 SrcDemandedMask |= fcPosSubnormal;
2477 if (DemandedMask & fcNegNormal)
2478 SrcDemandedMask |= fcNegSubnormal;
2479
2480 // Doubling a subnormal may produce 0 if FTZ/DAZ.
2481 if (Mode != DenormalMode::getIEEE()) {
2482 if (DemandedMask & fcPosZero) {
2483 SrcDemandedMask |= fcPosSubnormal;
2484
2485 if (Mode.inputsMayBePositiveZero() || Mode.outputsMayBePositiveZero())
2486 SrcDemandedMask |= fcNegSubnormal;
2487 }
2488
2489 if (DemandedMask & fcNegZero)
2490 SrcDemandedMask |= fcNegSubnormal;
2491 }
2492
2493 // Doubling a normal could have resulted in an infinity.
2494 if (DemandedMask & fcPosInf)
2495 SrcDemandedMask |= fcPosNormal;
2496 if (DemandedMask & fcNegInf)
2497 SrcDemandedMask |= fcNegNormal;
2498
2499 if (SimplifyDemandedFPClass(I, Op: 0, DemandedMask: SrcDemandedMask, Known&: KnownLHS, Q: SQ,
2500 Depth: Depth + 1))
2501 return I;
2502
2503 Known = KnownFPClass::fadd_self(Src: KnownLHS, Mode);
2504 KnownRHS = KnownLHS;
2505 } else {
2506 FPClassTest SrcDemandedMask = fcFinite;
2507
2508 // inf + (-inf) = nan
2509 if (DemandedMask & fcNan)
2510 SrcDemandedMask |= fcNan | fcInf;
2511
2512 if (DemandedMask & fcInf)
2513 SrcDemandedMask |= fcInf;
2514
2515 if (SimplifyDemandedFPClass(I, Op: 1, DemandedMask: SrcDemandedMask, Known&: KnownRHS, Q: SQ,
2516 Depth: Depth + 1) ||
2517 SimplifyDemandedFPClass(I, Op: 0, DemandedMask: SrcDemandedMask, Known&: KnownLHS, Q: SQ,
2518 Depth: Depth + 1))
2519 return I;
2520
2521 Type *EltTy = VTy->getScalarType();
2522 DenormalMode Mode = F.getDenormalMode(FPType: EltTy->getFltSemantics());
2523
2524 Known = I->getOpcode() == Instruction::FAdd
2525 ? KnownFPClass::fadd(LHS: KnownLHS, RHS: KnownRHS, Mode)
2526 : KnownFPClass::fsub(LHS: KnownLHS, RHS: KnownRHS, Mode);
2527 }
2528
2529 Known.knownNot(RuleOut: ~DemandedMask);
2530
2531 if (Constant *SingleVal = getFPClassConstant(Ty: VTy, Mask: Known.getKnownFPClasses(),
2532 /*IsCanonicalizing=*/true))
2533 return SingleVal;
2534
2535 // Propagate known result to simplify edge case checks.
2536 bool ResultNotNan = (DemandedMask & fcNan) == fcNone;
2537
2538 // With nnan: X + {+/-}Inf --> {+/-}Inf
2539 if (ResultNotNan && I->getOpcode() == Instruction::FAdd &&
2540 KnownRHS.isKnownAlways(Mask: fcInf | fcNan) && KnownLHS.isKnownNever(Mask: fcNan))
2541 return I->getOperand(i: 1);
2542
2543 // With nnan: {+/-}Inf + X --> {+/-}Inf
2544 // With nnan: {+/-}Inf - X --> {+/-}Inf
2545 if (ResultNotNan && KnownLHS.isKnownAlways(Mask: fcInf | fcNan) &&
2546 KnownRHS.isKnownNever(Mask: fcNan))
2547 return I->getOperand(i: 0);
2548
2549 FastMathFlags InferredFMF = inferFastMathValueFlags(
2550 FMF, ValidResults: Known.getKnownFPClasses(), Known: {KnownLHS, KnownRHS});
2551 if (InferredFMF != FMF) {
2552 I->setFastMathFlags(InferredFMF);
2553 return I;
2554 }
2555
2556 return nullptr;
2557 }
2558 case Instruction::FMul: {
2559 KnownFPClass KnownLHS, KnownRHS;
2560
2561 Value *X = I->getOperand(i: 0);
2562 Value *Y = I->getOperand(i: 1);
2563
2564 FPClassTest SrcDemandedMask =
2565 DemandedMask & (fcNan | fcZero | fcSubnormal | fcNormal);
2566
2567 if (DemandedMask & fcInf) {
2568 // mul x, inf = inf
2569 // mul large_x, large_y = inf
2570 SrcDemandedMask |= fcSubnormal | fcNormal | fcInf;
2571 }
2572
2573 if (DemandedMask & fcNan) {
2574 // mul +/-inf, 0 => nan
2575 SrcDemandedMask |= fcZero | fcInf | fcNan;
2576
2577 // TODO: Mode check
2578 // mul +/-inf, sub => nan if daz
2579 SrcDemandedMask |= fcSubnormal;
2580 }
2581
2582 // mul normal, subnormal = normal
2583 // Normal inputs may result in underflow.
2584 if (DemandedMask & (fcNormal | fcSubnormal))
2585 SrcDemandedMask |= fcNormal | fcSubnormal;
2586
2587 if (DemandedMask & fcZero)
2588 SrcDemandedMask |= fcNormal | fcSubnormal;
2589
2590 if (X == Y &&
2591 isGuaranteedNotToBeUndef(V: X, AC: SQ.AC, CtxI: SQ.CxtI, DT: SQ.DT, Depth: Depth + 1)) {
2592 if (SimplifyDemandedFPClass(I, Op: 0, DemandedMask: SrcDemandedMask, Known&: KnownLHS, Q: SQ,
2593 Depth: Depth + 1))
2594 return I;
2595 Type *EltTy = VTy->getScalarType();
2596
2597 DenormalMode Mode = F.getDenormalMode(FPType: EltTy->getFltSemantics());
2598 Known = KnownFPClass::square(Src: KnownLHS, Mode);
2599 Known.knownNot(RuleOut: ~DemandedMask);
2600
2601 if (Constant *Folded = getFPClassConstant(Ty: VTy, Mask: Known.getKnownFPClasses(),
2602 /*IsCanonicalizing=*/true))
2603 return Folded;
2604
2605 if (Known.isKnownAlways(Mask: fcPosZero | fcPosInf | fcNan) &&
2606 KnownLHS.isKnownNever(Mask: fcSubnormal | fcNormal)) {
2607 // We can skip the fabs if the source was already known positive.
2608 if (KnownLHS.isKnownAlways(Mask: fcPositive))
2609 return X;
2610
2611 // => fabs(x), in case this was a -inf or -0.
2612 // Note: Dropping canonicalize.
2613 IRBuilderBase::InsertPointGuard Guard(Builder);
2614 Builder.SetInsertPoint(I);
2615 Value *Fabs = Builder.CreateFAbs(V: X, FMFSource: FMF);
2616 Fabs->takeName(V: I);
2617 return Fabs;
2618 }
2619
2620 return nullptr;
2621 }
2622
2623 if (SimplifyDemandedFPClass(I, Op: 1, DemandedMask: SrcDemandedMask, Known&: KnownRHS, Q: SQ,
2624 Depth: Depth + 1) ||
2625 SimplifyDemandedFPClass(I, Op: 0, DemandedMask: SrcDemandedMask, Known&: KnownLHS, Q: SQ, Depth: Depth + 1))
2626 return I;
2627
2628 if (FMF.noInfs()) {
2629 // Flag implies inputs cannot be infinity.
2630 KnownLHS.knownNot(RuleOut: fcInf);
2631 KnownRHS.knownNot(RuleOut: fcInf);
2632 }
2633
2634 bool NonNanResult = (DemandedMask & fcNan) == fcNone;
2635
2636 // With no-nans/no-infs:
2637 // X * 0.0 --> copysign(0.0, X)
2638 // X * -0.0 --> copysign(0.0, -X)
2639 if ((NonNanResult || KnownLHS.isKnownNeverInfOrNaN()) &&
2640 KnownRHS.isKnownAlways(Mask: fcPosZero | fcNan)) {
2641 IRBuilderBase::InsertPointGuard Guard(Builder);
2642 Builder.SetInsertPoint(I);
2643
2644 // => copysign(+0, lhs)
2645 // Note: Dropping canonicalize
2646 Value *Copysign = Builder.CreateCopySign(LHS: Y, RHS: X, FMFSource: FMF);
2647 Copysign->takeName(V: I);
2648 return Copysign;
2649 }
2650
2651 if (KnownLHS.isKnownAlways(Mask: fcPosZero | fcNan) &&
2652 (NonNanResult || KnownRHS.isKnownNeverInfOrNaN())) {
2653 IRBuilderBase::InsertPointGuard Guard(Builder);
2654 Builder.SetInsertPoint(I);
2655
2656 // => copysign(+0, rhs)
2657 // Note: Dropping canonicalize
2658 Value *Copysign = Builder.CreateCopySign(LHS: X, RHS: Y, FMFSource: FMF);
2659 Copysign->takeName(V: I);
2660 return Copysign;
2661 }
2662
2663 if ((NonNanResult || KnownLHS.isKnownNeverInfOrNaN()) &&
2664 KnownRHS.isKnownAlways(Mask: fcNegZero | fcNan)) {
2665 IRBuilderBase::InsertPointGuard Guard(Builder);
2666 Builder.SetInsertPoint(I);
2667
2668 // => copysign(0, fneg(lhs))
2669 // Note: Dropping canonicalize
2670 Value *Copysign =
2671 Builder.CreateCopySign(LHS: Y, RHS: Builder.CreateFNegFMF(V: X, FMFSource: FMF), FMFSource: FMF);
2672 Copysign->takeName(V: I);
2673 return Copysign;
2674 }
2675
2676 if (KnownLHS.isKnownAlways(Mask: fcNegZero | fcNan) &&
2677 (NonNanResult || KnownRHS.isKnownNeverInfOrNaN())) {
2678 IRBuilderBase::InsertPointGuard Guard(Builder);
2679 Builder.SetInsertPoint(I);
2680
2681 // => copysign(+0, fneg(rhs))
2682 // Note: Dropping canonicalize
2683 Value *Copysign =
2684 Builder.CreateCopySign(LHS: X, RHS: Builder.CreateFNegFMF(V: Y, FMFSource: FMF), FMFSource: FMF);
2685 Copysign->takeName(V: I);
2686 return Copysign;
2687 }
2688
2689 Type *EltTy = VTy->getScalarType();
2690 DenormalMode Mode = F.getDenormalMode(FPType: EltTy->getFltSemantics());
2691
2692 if (KnownLHS.isKnownAlways(Mask: fcInf | fcNan) &&
2693 (KnownRHS.isKnownNeverNaN() &&
2694 KnownRHS.cannotBeOrderedGreaterEqZero(Mode))) {
2695 IRBuilderBase::InsertPointGuard Guard(Builder);
2696 Builder.SetInsertPoint(I);
2697
2698 // Note: Dropping canonicalize
2699 Value *Neg = Builder.CreateFNegFMF(V: X, FMFSource: FMF);
2700 Neg->takeName(V: I);
2701 return Neg;
2702 }
2703
2704 if (KnownRHS.isKnownAlways(Mask: fcInf | fcNan) &&
2705 (KnownLHS.isKnownNeverNaN() &&
2706 KnownLHS.cannotBeOrderedGreaterEqZero(Mode))) {
2707 IRBuilderBase::InsertPointGuard Guard(Builder);
2708 Builder.SetInsertPoint(I);
2709
2710 // Note: Dropping canonicalize
2711 Value *Neg = Builder.CreateFNegFMF(V: Y, FMFSource: FMF);
2712 Neg->takeName(V: I);
2713 return Neg;
2714 }
2715
2716 Known = KnownFPClass::fmul(LHS: KnownLHS, RHS: KnownRHS, Mode);
2717 Known.knownNot(RuleOut: ~DemandedMask);
2718
2719 if (Constant *SingleVal = getFPClassConstant(Ty: VTy, Mask: Known.getKnownFPClasses(),
2720 /*IsCanonicalizing=*/true))
2721 return SingleVal;
2722
2723 FastMathFlags InferredFMF = inferFastMathValueFlags(
2724 FMF, ValidResults: Known.getKnownFPClasses(), Known: {KnownLHS, KnownRHS});
2725 if (InferredFMF != FMF) {
2726 I->setFastMathFlags(InferredFMF);
2727 return I;
2728 }
2729
2730 return nullptr;
2731 }
2732 case Instruction::FDiv: {
2733 Value *X = I->getOperand(i: 0);
2734 Value *Y = I->getOperand(i: 1);
2735 if (X == Y &&
2736 isGuaranteedNotToBeUndef(V: X, AC: SQ.AC, CtxI: SQ.CxtI, DT: SQ.DT, Depth: Depth + 1)) {
2737 // If the source is 0, inf or nan, the result is a nan
2738 IRBuilderBase::InsertPointGuard Guard(Builder);
2739 Builder.SetInsertPoint(I);
2740
2741 Value *IsZeroOrNan = Builder.CreateFCmpFMF(
2742 P: FCmpInst::FCMP_UEQ, LHS: I->getOperand(i: 0), RHS: ConstantFP::getZero(Ty: VTy), FMFSource: FMF);
2743
2744 Value *Fabs = Builder.CreateFAbs(V: I->getOperand(i: 0), FMFSource: FMF);
2745 Value *IsInfOrNan = Builder.CreateFCmpFMF(
2746 P: FCmpInst::FCMP_UEQ, LHS: Fabs, RHS: ConstantFP::getInfinity(Ty: VTy), FMFSource: FMF);
2747
2748 Value *IsInfOrZeroOrNan = Builder.CreateOr(LHS: IsInfOrNan, RHS: IsZeroOrNan);
2749
2750 return Builder.CreateSelectFMFWithUnknownProfile(
2751 C: IsInfOrZeroOrNan, True: ConstantFP::getQNaN(Ty: VTy),
2752 False: ConstantFP::get(
2753 Ty: VTy, V: APFloat::getOne(Sem: VTy->getScalarType()->getFltSemantics())),
2754 FMFSource: FMF, DEBUG_TYPE);
2755 }
2756
2757 Type *EltTy = VTy->getScalarType();
2758 DenormalMode Mode = F.getDenormalMode(FPType: EltTy->getFltSemantics());
2759
2760 // Every output class could require denormal inputs (except for the
2761 // degenerate case of only-nan results, without DAZ).
2762 FPClassTest SrcDemandedMask = (DemandedMask & fcNan) | fcSubnormal;
2763
2764 // Normal inputs may result in underflow.
2765 // x / x = 1.0 for non0/inf/nan
2766 // -x = +y / -z
2767 // -x = -y / +z
2768 if (DemandedMask & (fcSubnormal | fcNormal))
2769 SrcDemandedMask |= fcNormal;
2770
2771 if (DemandedMask & fcNan) {
2772 // 0 / 0 = nan
2773 // inf / inf = nan
2774
2775 // Subnormal is added in case of DAZ, but this isn't strictly
2776 // necessary. Every other input class implies a possible subnormal source,
2777 // so this only could matter in the degenerate case of only-nan results.
2778 SrcDemandedMask |= fcZero | fcInf | fcNan;
2779 }
2780
2781 // Zero outputs may be the result of underflow.
2782 if (DemandedMask & fcZero)
2783 SrcDemandedMask |= fcNormal | fcSubnormal;
2784
2785 FPClassTest LHSDemandedMask = SrcDemandedMask;
2786 FPClassTest RHSDemandedMask = SrcDemandedMask;
2787
2788 // 0 / inf = 0
2789 if (DemandedMask & fcZero) {
2790 assert((LHSDemandedMask & fcSubnormal) &&
2791 "should not have to worry about daz here");
2792 LHSDemandedMask |= fcZero;
2793 RHSDemandedMask |= fcInf;
2794 }
2795
2796 // x / 0 = inf
2797 // large_normal / small_normal = inf
2798 // inf / 1 = inf
2799 // large_normal / subnormal = inf
2800 if (DemandedMask & fcInf) {
2801 LHSDemandedMask |= fcInf | fcNormal | fcSubnormal;
2802 RHSDemandedMask |= fcZero | fcSubnormal | fcNormal;
2803 }
2804
2805 KnownFPClass KnownLHS, KnownRHS;
2806 if (SimplifyDemandedFPClass(I, Op: 0, DemandedMask: LHSDemandedMask, Known&: KnownLHS, Q: SQ,
2807 Depth: Depth + 1) ||
2808 SimplifyDemandedFPClass(I, Op: 1, DemandedMask: RHSDemandedMask, Known&: KnownRHS, Q: SQ, Depth: Depth + 1))
2809 return I;
2810
2811 bool ResultNotNan = (DemandedMask & fcNan) == fcNone;
2812 bool ResultNotInf = (DemandedMask & fcInf) == fcNone;
2813
2814 // Replacing 0/x with a zero is only valid when the divisor can't be
2815 // (logical) zero, since 0/0 is NaN -- unless NaN results aren't demanded. A
2816 // subnormal divisor can flush to zero under a flushing denormal mode.
2817 bool CanIgnoreZeroByZeroNan =
2818 ResultNotNan || KnownRHS.isKnownNeverLogicalZero(Mode);
2819
2820 // nsz [+-]0 / x -> 0
2821 if (FMF.noSignedZeros() && KnownLHS.isKnownAlways(Mask: fcZero) &&
2822 KnownRHS.isKnownNeverNaN() && CanIgnoreZeroByZeroNan)
2823 return ConstantFP::getZero(Ty: VTy);
2824
2825 if (KnownLHS.isKnownAlways(Mask: fcPosZero) && KnownRHS.isKnownNeverNaN() &&
2826 CanIgnoreZeroByZeroNan) {
2827 IRBuilderBase::InsertPointGuard Guard(Builder);
2828 Builder.SetInsertPoint(I);
2829
2830 // nnan +0 / x -> copysign(0, rhs)
2831 // TODO: -0 / x => copysign(0, fneg(rhs))
2832 Value *Copysign = Builder.CreateCopySign(LHS: X, RHS: Y, FMFSource: FMF);
2833 Copysign->takeName(V: I);
2834 return Copysign;
2835 }
2836
2837 if (!ResultNotInf &&
2838 ((ResultNotNan || (KnownLHS.isKnownNeverNaN() &&
2839 KnownLHS.isKnownNeverLogicalZero(Mode))) &&
2840 (KnownRHS.isKnownAlways(Mask: fcPosZero) ||
2841 (FMF.noSignedZeros() && KnownRHS.isKnownAlways(Mask: fcZero))))) {
2842 IRBuilderBase::InsertPointGuard Guard(Builder);
2843 Builder.SetInsertPoint(I);
2844
2845 // nnan x / 0 => copysign(inf, x);
2846 // nnan nsz x / -0 => copysign(inf, x);
2847 Value *Copysign =
2848 Builder.CreateCopySign(LHS: ConstantFP::getInfinity(Ty: VTy), RHS: X, FMFSource: FMF);
2849 Copysign->takeName(V: I);
2850 return Copysign;
2851 }
2852
2853 // nnan ninf X / [-]0.0 -> poison
2854 if (ResultNotNan && ResultNotInf && KnownRHS.isKnownAlways(Mask: fcZero))
2855 return PoisonValue::get(T: VTy);
2856
2857 Known = KnownFPClass::fdiv(LHS: KnownLHS, RHS: KnownRHS, Mode);
2858 Known.knownNot(RuleOut: ~DemandedMask);
2859
2860 if (Constant *SingleVal = getFPClassConstant(Ty: VTy, Mask: Known.getKnownFPClasses(),
2861 /*IsCanonicalizing=*/true))
2862 return SingleVal;
2863
2864 FastMathFlags InferredFMF = inferFastMathValueFlags(
2865 FMF, ValidResults: Known.getKnownFPClasses(), Known: {KnownLHS, KnownRHS});
2866 if (InferredFMF != FMF) {
2867 I->setFastMathFlags(InferredFMF);
2868 return I;
2869 }
2870
2871 return nullptr;
2872 }
2873 case Instruction::FPTrunc:
2874 return simplifyDemandedUseFPClassFPTrunc(IC&: *this, I&: *I, FMF, DemandedMask,
2875 Known, SQ, Depth);
2876 case Instruction::FPExt: {
2877 FPClassTest SrcDemandedMask = DemandedMask;
2878 if (DemandedMask & fcNan)
2879 SrcDemandedMask |= fcNan;
2880
2881 // No subnormal result does not imply not-subnormal in the source type.
2882 if ((DemandedMask & fcNegNormal) != fcNone)
2883 SrcDemandedMask |= fcNegSubnormal;
2884 if ((DemandedMask & fcPosNormal) != fcNone)
2885 SrcDemandedMask |= fcPosSubnormal;
2886
2887 KnownFPClass KnownSrc;
2888 if (SimplifyDemandedFPClass(I, Op: 0, DemandedMask: SrcDemandedMask, Known&: KnownSrc, Q: SQ, Depth: Depth + 1))
2889 return I;
2890
2891 const fltSemantics &DstTy = VTy->getScalarType()->getFltSemantics();
2892 const fltSemantics &SrcTy =
2893 I->getOperand(i: 0)->getType()->getScalarType()->getFltSemantics();
2894
2895 Known = KnownFPClass::fpext(KnownSrc, DstTy, SrcTy);
2896 Known.knownNot(RuleOut: ~DemandedMask);
2897
2898 return simplifyDemandedFPClassResult(FPOp: I, FMF, DemandedMask, Known,
2899 KnownSrcs: {KnownSrc});
2900 }
2901 case Instruction::Call: {
2902 CallInst *CI = cast<CallInst>(Val: I);
2903 const Intrinsic::ID IID = CI->getIntrinsicID();
2904 switch (IID) {
2905 case Intrinsic::fabs: {
2906 KnownFPClass KnownSrc;
2907 if (SimplifyDemandedFPClass(I, Op: 0, DemandedMask: llvm::inverse_fabs(Mask: DemandedMask),
2908 Known&: KnownSrc, Q: SQ, Depth: Depth + 1))
2909 return I;
2910
2911 if (Value *Simplified = simplifyDemandedFPClassFabs(
2912 Known, Src: CI->getArgOperand(i: 0), DemandedMask, KnownSrc,
2913 NSZ: FMF.noSignedZeros()))
2914 return Simplified;
2915 break;
2916 }
2917 case Intrinsic::arithmetic_fence:
2918 if (SimplifyDemandedFPClass(I, Op: 0, DemandedMask, Known, Q: SQ, Depth: Depth + 1))
2919 return I;
2920 break;
2921 case Intrinsic::copysign: {
2922 // Flip on more potentially demanded classes
2923 const FPClassTest DemandedMaskAnySign = llvm::unknown_sign(Mask: DemandedMask);
2924 KnownFPClass KnownMag;
2925 if (SimplifyDemandedFPClass(I: CI, Op: 0, DemandedMask: DemandedMaskAnySign, Known&: KnownMag, Q: SQ,
2926 Depth: Depth + 1))
2927 return I;
2928
2929 if ((DemandedMask & fcNegative) == DemandedMask) {
2930 // Roundabout way of replacing with fneg(fabs)
2931 CI->setOperand(i_nocapture: 1, Val_nocapture: ConstantFP::get(Ty: VTy, V: -1.0));
2932 return I;
2933 }
2934
2935 if ((DemandedMask & fcPositive) == DemandedMask) {
2936 // Roundabout way of replacing with fabs
2937 CI->setOperand(i_nocapture: 1, Val_nocapture: ConstantFP::getZero(Ty: VTy));
2938 return I;
2939 }
2940
2941 if (Value *Simplified = simplifyDemandedFPClassCopysignMag(
2942 MagSrc: CI->getArgOperand(i: 0), DemandedMask, KnownSrc: KnownMag,
2943 NSZ: FMF.noSignedZeros()))
2944 return Simplified;
2945
2946 KnownFPClass KnownSign =
2947 computeKnownFPClass(V: CI->getArgOperand(i: 1), InterestedClasses: fcAllFlags, SQ, Depth: Depth + 1);
2948 if (KnownMag.getSignBit() && KnownSign.getSignBit() &&
2949 *KnownMag.getSignBit() == *KnownSign.getSignBit())
2950 return CI->getOperand(i_nocapture: 0);
2951
2952 // TODO: Call argument attribute not considered
2953 // Input implied not-nan from flag.
2954 if (FMF.noNaNs())
2955 KnownSign.knownNot(RuleOut: fcNan);
2956
2957 if (KnownSign.getSignBit() == false) {
2958 CI->dropUBImplyingAttrsAndMetadata();
2959 CI->setOperand(i_nocapture: 1, Val_nocapture: ConstantFP::getZero(Ty: VTy));
2960 return I;
2961 }
2962
2963 if (KnownSign.getSignBit() == true) {
2964 CI->dropUBImplyingAttrsAndMetadata();
2965 CI->setOperand(i_nocapture: 1, Val_nocapture: ConstantFP::get(Ty: VTy, V: -1.0));
2966 return I;
2967 }
2968
2969 Known = KnownFPClass::copysign(KnownMag, KnownSign);
2970 Known.knownNot(RuleOut: ~DemandedMask);
2971 break;
2972 }
2973 case Intrinsic::fma:
2974 case Intrinsic::fmuladd: {
2975 // We can't do any simplification on the source besides stripping out
2976 // unneeded nans.
2977 FPClassTest SrcDemandedMask = DemandedMask | ~fcNan;
2978 if (DemandedMask & fcNan)
2979 SrcDemandedMask |= fcNan;
2980
2981 KnownFPClass KnownSrc[3];
2982
2983 Type *EltTy = VTy->getScalarType();
2984 if (CI->getArgOperand(i: 0) == CI->getArgOperand(i: 1) &&
2985 isGuaranteedNotToBeUndef(V: CI->getArgOperand(i: 0), AC: SQ.AC, CtxI: SQ.CxtI, DT: SQ.DT,
2986 Depth: Depth + 1)) {
2987 if (SimplifyDemandedFPClass(I: CI, Op: 0, DemandedMask: SrcDemandedMask, Known&: KnownSrc[0], Q: SQ,
2988 Depth: Depth + 1) ||
2989 SimplifyDemandedFPClass(I: CI, Op: 2, DemandedMask: SrcDemandedMask, Known&: KnownSrc[2], Q: SQ,
2990 Depth: Depth + 1))
2991 return I;
2992
2993 KnownSrc[1] = KnownSrc[0];
2994 DenormalMode Mode = F.getDenormalMode(FPType: EltTy->getFltSemantics());
2995 Known = KnownFPClass::fma_square(Squared: KnownSrc[0], Addend: KnownSrc[2], Mode);
2996 } else {
2997 for (int OpIdx = 0; OpIdx != 3; ++OpIdx) {
2998 if (SimplifyDemandedFPClass(I: CI, Op: OpIdx, DemandedMask: SrcDemandedMask,
2999 Known&: KnownSrc[OpIdx], Q: SQ, Depth: Depth + 1))
3000 return CI;
3001 }
3002
3003 DenormalMode Mode = F.getDenormalMode(FPType: EltTy->getFltSemantics());
3004 Known = KnownFPClass::fma(LHS: KnownSrc[0], RHS: KnownSrc[1], Addend: KnownSrc[2], Mode);
3005 }
3006
3007 return simplifyDemandedFPClassResult(FPOp: CI, FMF, DemandedMask, Known,
3008 KnownSrcs: {KnownSrc});
3009 }
3010 case Intrinsic::maximum:
3011 case Intrinsic::minimum:
3012 case Intrinsic::maximumnum:
3013 case Intrinsic::minimumnum:
3014 case Intrinsic::maxnum:
3015 case Intrinsic::minnum: {
3016 const bool PropagateNaN =
3017 IID == Intrinsic::maximum || IID == Intrinsic::minimum;
3018
3019 // We can't tell much based on the demanded result without inspecting the
3020 // operands (e.g., a known-positive result could have been clamped), but
3021 // we can still prune known-nan inputs.
3022 FPClassTest SrcDemandedMask =
3023 PropagateNaN && ((DemandedMask & fcNan) == fcNone)
3024 ? DemandedMask | ~fcNan
3025 : fcAllFlags;
3026
3027 KnownFPClass KnownLHS, KnownRHS;
3028 if (SimplifyDemandedFPClass(I: CI, Op: 1, DemandedMask: SrcDemandedMask, Known&: KnownRHS, Q: SQ,
3029 Depth: Depth + 1) ||
3030 SimplifyDemandedFPClass(I: CI, Op: 0, DemandedMask: SrcDemandedMask, Known&: KnownLHS, Q: SQ,
3031 Depth: Depth + 1))
3032 return I;
3033
3034 Value *Simplified =
3035 simplifyDemandedFPClassMinMax(Known, IID, CI, DemandedMask, KnownLHS,
3036 KnownRHS, F, NSZ: FMF.noSignedZeros());
3037 if (Simplified)
3038 return Simplified;
3039
3040 auto *FPOp = cast<FPMathOperator>(Val: CI);
3041
3042 FPClassTest ValidResults = DemandedMask & Known.getKnownFPClasses();
3043 FastMathFlags InferredFMF = FMF;
3044
3045 if (!FMF.noSignedZeros()) {
3046 // Add NSZ flag if we know the result will not be sensitive to the sign
3047 // of 0.
3048 FPClassTest ZeroMask = fcZero;
3049
3050 Type *EltTy = VTy->getScalarType();
3051 DenormalMode Mode = F.getDenormalMode(FPType: EltTy->getFltSemantics());
3052 if (Mode != DenormalMode::getIEEE())
3053 ZeroMask |= fcSubnormal;
3054
3055 bool ResultNotLogical0 = (ValidResults & ZeroMask) == fcNone;
3056 if (ResultNotLogical0 || ((KnownLHS.isKnownNeverLogicalNegZero(Mode) ||
3057 KnownRHS.isKnownNeverLogicalPosZero(Mode)) &&
3058 (KnownLHS.isKnownNeverLogicalPosZero(Mode) ||
3059 KnownRHS.isKnownNeverLogicalNegZero(Mode))))
3060 InferredFMF.setNoSignedZeros(true);
3061 }
3062
3063 if (!FMF.noNaNs() &&
3064 ((PropagateNaN && (ValidResults & fcNan) == fcNone) ||
3065 (KnownLHS.isKnownNeverNaN() && KnownRHS.isKnownNeverNaN()))) {
3066 CI->dropUBImplyingAttrsAndMetadata();
3067 InferredFMF.setNoNaNs(true);
3068 }
3069
3070 if (InferredFMF != FMF) {
3071 CI->setFastMathFlags(InferredFMF);
3072 return FPOp;
3073 }
3074
3075 return nullptr;
3076 }
3077 case Intrinsic::exp:
3078 case Intrinsic::exp2:
3079 case Intrinsic::exp10: {
3080 if ((DemandedMask & fcPositive) == fcNone) {
3081 // Only returns positive values or nans.
3082 if ((DemandedMask & fcNan) == fcNone)
3083 return PoisonValue::get(T: VTy);
3084
3085 // Only need nan propagation.
3086 if ((DemandedMask & ~fcNan) == fcNone)
3087 return ConstantFP::getQNaN(Ty: VTy);
3088
3089 return CI->getArgOperand(i: 0);
3090 }
3091
3092 FPClassTest SrcDemandedMask = DemandedMask & fcNan;
3093 if (DemandedMask & fcNan)
3094 SrcDemandedMask |= fcNan;
3095
3096 if (DemandedMask & fcZero) {
3097 // exp(-infinity) = 0
3098 SrcDemandedMask |= fcNegInf;
3099
3100 // exp(-largest_normal) = 0
3101 //
3102 // Negative numbers of sufficiently large magnitude underflow to 0. No
3103 // subnormal input has a 0 result.
3104 SrcDemandedMask |= fcNegNormal;
3105 }
3106
3107 if (DemandedMask & fcPosSubnormal) {
3108 // Negative numbers of sufficiently large magnitude underflow to 0. No
3109 // subnormal input has a 0 result.
3110 SrcDemandedMask |= fcNegNormal;
3111 }
3112
3113 if (DemandedMask & fcPosNormal) {
3114 // exp(0) = 1
3115 // exp(+/- smallest_normal) = 1
3116 // exp(+/- largest_denormal) = 1
3117 // exp(+/- smallest_denormal) = 1
3118 // exp(-1) = pos normal
3119 SrcDemandedMask |= fcNormal | fcSubnormal | fcZero;
3120 }
3121
3122 // exp(inf), exp(largest_normal) = inf
3123 if (DemandedMask & fcPosInf)
3124 SrcDemandedMask |= fcPosInf | fcPosNormal;
3125
3126 KnownFPClass KnownSrc;
3127
3128 // TODO: This could really make use of KnownFPClass of specific value
3129 // range, (i.e., close enough to 1)
3130 if (SimplifyDemandedFPClass(I, Op: 0, DemandedMask: SrcDemandedMask, Known&: KnownSrc, Q: SQ,
3131 Depth: Depth + 1))
3132 return I;
3133
3134 // exp(+/-0) = 1
3135 if (KnownSrc.isKnownAlways(Mask: fcZero))
3136 return ConstantFP::get(Ty: VTy, V: 1.0);
3137
3138 // Only perform nan propagation.
3139 // Note: Dropping canonicalize / quiet of signaling nan.
3140 if (KnownSrc.isKnownAlways(Mask: fcNan))
3141 return CI->getArgOperand(i: 0);
3142
3143 // exp(0 | nan) => x == 0.0 ? 1.0 : x
3144 if (KnownSrc.isKnownAlways(Mask: fcZero | fcNan)) {
3145 IRBuilderBase::InsertPointGuard Guard(Builder);
3146 Builder.SetInsertPoint(CI);
3147
3148 // fadd +/-0, 1.0 => 1.0
3149 // fadd nan, 1.0 => nan
3150 return Builder.CreateFAddFMF(L: CI->getArgOperand(i: 0),
3151 R: ConstantFP::get(Ty: VTy, V: 1.0), FMFSource: FMF);
3152 }
3153
3154 if (KnownSrc.isKnownAlways(Mask: fcInf | fcNan)) {
3155 // exp(-inf) = 0
3156 // exp(+inf) = +inf
3157 IRBuilderBase::InsertPointGuard Guard(Builder);
3158 Builder.SetInsertPoint(CI);
3159
3160 // Note: Dropping canonicalize / quiet of signaling nan.
3161 Value *X = CI->getArgOperand(i: 0);
3162 Value *IsPosInfOrNan = Builder.CreateFCmpFMF(
3163 P: FCmpInst::FCMP_UEQ, LHS: X, RHS: ConstantFP::getInfinity(Ty: VTy), FMFSource: FMF);
3164 // We do not know whether an infinity or a NaN is more likely here,
3165 // so mark the branch weights as unkown.
3166 Value *ZeroOrInf = Builder.CreateSelectFMFWithUnknownProfile(
3167 C: IsPosInfOrNan, True: X, False: ConstantFP::getZero(Ty: VTy), FMFSource: FMF, DEBUG_TYPE);
3168 return ZeroOrInf;
3169 }
3170
3171 Known = KnownFPClass::exp(Src: KnownSrc);
3172 Known.knownNot(RuleOut: ~DemandedMask);
3173
3174 return simplifyDemandedFPClassResult(FPOp: CI, FMF, DemandedMask, Known,
3175 KnownSrcs: KnownSrc);
3176 }
3177 case Intrinsic::log:
3178 case Intrinsic::log2:
3179 case Intrinsic::log10: {
3180 FPClassTest DemandedSrcMask = DemandedMask & (fcNan | fcPosInf);
3181 if (DemandedMask & fcNan)
3182 DemandedSrcMask |= fcNan;
3183
3184 Type *EltTy = VTy->getScalarType();
3185 DenormalMode Mode = F.getDenormalMode(FPType: EltTy->getFltSemantics());
3186
3187 // log(x < 0) = nan
3188 if (DemandedMask & fcNan)
3189 DemandedSrcMask |= (fcNegative & ~fcNegZero);
3190
3191 // log(0) = -inf
3192 if (DemandedMask & fcNegInf) {
3193 DemandedSrcMask |= fcZero;
3194
3195 // No value produces subnormal result.
3196 if (Mode.inputsMayBeZero())
3197 DemandedSrcMask |= fcSubnormal;
3198 }
3199
3200 if (DemandedMask & fcNormal)
3201 DemandedSrcMask |= fcNormal | fcSubnormal;
3202
3203 // log(1) = 0
3204 if (DemandedMask & fcZero)
3205 DemandedSrcMask |= fcPosNormal;
3206
3207 KnownFPClass KnownSrc;
3208 if (SimplifyDemandedFPClass(I, Op: 0, DemandedMask: DemandedSrcMask, Known&: KnownSrc, Q: SQ,
3209 Depth: Depth + 1))
3210 return I;
3211
3212 Known = KnownFPClass::log(Src: KnownSrc, Mode);
3213 Known.knownNot(RuleOut: ~DemandedMask);
3214
3215 return simplifyDemandedFPClassResult(FPOp: CI, FMF, DemandedMask, Known,
3216 KnownSrcs: KnownSrc);
3217 }
3218 case Intrinsic::sqrt: {
3219 FPClassTest DemandedSrcMask =
3220 DemandedMask & (fcNegZero | fcPositive | fcNan);
3221
3222 if (DemandedMask & fcNan)
3223 DemandedSrcMask |= fcNan | (fcNegative & ~fcNegZero);
3224
3225 // sqrt(max_subnormal) is a normal value
3226 if (DemandedMask & fcPosNormal)
3227 DemandedSrcMask |= fcPosSubnormal;
3228
3229 KnownFPClass KnownSrc;
3230 if (SimplifyDemandedFPClass(I, Op: 0, DemandedMask: DemandedSrcMask, Known&: KnownSrc, Q: SQ,
3231 Depth: Depth + 1))
3232 return I;
3233
3234 // Infer the source cannot be negative if the result cannot be nan.
3235 if ((DemandedMask & fcNan) == fcNone)
3236 KnownSrc.knownNot(RuleOut: (fcNegative & ~fcNegZero) | fcNan);
3237
3238 // Infer the source cannot be +inf if the result is not +nf
3239 if ((DemandedMask & fcPosInf) == fcNone)
3240 KnownSrc.knownNot(RuleOut: fcPosInf);
3241
3242 Type *EltTy = VTy->getScalarType();
3243 DenormalMode Mode = F.getDenormalMode(FPType: EltTy->getFltSemantics());
3244
3245 // sqrt(-x) = nan, but be careful of negative subnormals flushed to 0.
3246 if (KnownSrc.isKnownNever(Mask: fcPositive) &&
3247 KnownSrc.isKnownNeverLogicalZero(Mode))
3248 return ConstantFP::getQNaN(Ty: VTy);
3249
3250 Known = KnownFPClass::sqrt(Src: KnownSrc, Mode);
3251 Known.knownNot(RuleOut: ~DemandedMask);
3252
3253 if (Known.getKnownFPClasses() == fcZero) {
3254 if (FMF.noSignedZeros())
3255 return ConstantFP::getZero(Ty: VTy);
3256 IRBuilderBase::InsertPointGuard Guard(Builder);
3257 Builder.SetInsertPoint(CI);
3258
3259 Value *Copysign = Builder.CreateCopySign(LHS: ConstantFP::getZero(Ty: VTy),
3260 RHS: CI->getArgOperand(i: 0), FMFSource: FMF);
3261 Copysign->takeName(V: CI);
3262 return Copysign;
3263 }
3264
3265 return simplifyDemandedFPClassResult(FPOp: CI, FMF, DemandedMask, Known,
3266 KnownSrcs: {KnownSrc});
3267 }
3268 case Intrinsic::ldexp: {
3269 FPClassTest SrcDemandedMask = DemandedMask & fcInf;
3270 if (DemandedMask & fcNan)
3271 SrcDemandedMask |= fcNan;
3272
3273 if (DemandedMask & fcPosInf)
3274 SrcDemandedMask |= fcPosNormal | fcPosSubnormal;
3275 if (DemandedMask & fcNegInf)
3276 SrcDemandedMask |= fcNegNormal | fcNegSubnormal;
3277
3278 if (DemandedMask & (fcPosNormal | fcPosSubnormal))
3279 SrcDemandedMask |= fcPosNormal | fcPosSubnormal;
3280 if (DemandedMask & (fcNegNormal | fcNegSubnormal))
3281 SrcDemandedMask |= fcNegNormal | fcNegSubnormal;
3282
3283 if (DemandedMask & fcPosZero)
3284 SrcDemandedMask |= fcPosFinite;
3285 if (DemandedMask & fcNegZero)
3286 SrcDemandedMask |= fcNegFinite;
3287
3288 KnownFPClass KnownSrc;
3289 if (SimplifyDemandedFPClass(I: CI, Op: 0, DemandedMask: SrcDemandedMask, Known&: KnownSrc, Q: SQ,
3290 Depth: Depth + 1))
3291 return CI;
3292
3293 Type *EltTy = VTy->getScalarType();
3294 const fltSemantics &FltSem = EltTy->getFltSemantics();
3295 DenormalMode Mode = F.getDenormalMode(FPType: FltSem);
3296
3297 KnownBits KnownExpBits =
3298 ::computeKnownBits(V: CI->getArgOperand(i: 1), Q: SQ, Depth: Depth + 1);
3299
3300 Known = KnownFPClass::ldexp(Src: KnownSrc, ExpBits: KnownExpBits, Flt: FltSem, Mode);
3301 Known.knownNot(RuleOut: ~DemandedMask);
3302
3303 return simplifyDemandedFPClassResult(FPOp: CI, FMF, DemandedMask, Known,
3304 KnownSrcs: {KnownSrc});
3305 }
3306 case Intrinsic::trunc:
3307 case Intrinsic::floor:
3308 case Intrinsic::ceil:
3309 case Intrinsic::rint:
3310 case Intrinsic::nearbyint:
3311 case Intrinsic::round:
3312 case Intrinsic::roundeven: {
3313 FPClassTest DemandedSrcMask = DemandedMask;
3314 if (DemandedMask & fcNan)
3315 DemandedSrcMask |= fcNan;
3316
3317 // Zero results imply valid subnormal sources.
3318 if (DemandedMask & fcNegZero)
3319 DemandedSrcMask |= fcNegSubnormal | fcNegNormal;
3320
3321 if (DemandedMask & fcPosZero)
3322 DemandedSrcMask |= fcPosSubnormal | fcPosNormal;
3323
3324 KnownFPClass KnownSrc;
3325 if (SimplifyDemandedFPClass(I: CI, Op: 0, DemandedMask: DemandedSrcMask, Known&: KnownSrc, Q: SQ,
3326 Depth: Depth + 1))
3327 return I;
3328
3329 // Note: Possibly dropping snan quiet.
3330 if (KnownSrc.isKnownAlways(Mask: fcInf | fcNan | fcZero))
3331 return CI->getArgOperand(i: 0);
3332
3333 bool IsRoundNearestOrTrunc =
3334 IID == Intrinsic::round || IID == Intrinsic::roundeven ||
3335 IID == Intrinsic::nearbyint || IID == Intrinsic::rint ||
3336 IID == Intrinsic::trunc;
3337
3338 // Ignore denormals-as-zero, as canonicalization is not mandated.
3339 if ((IID == Intrinsic::floor || IsRoundNearestOrTrunc) &&
3340 KnownSrc.isKnownAlways(Mask: fcPosZero | fcPosSubnormal))
3341 return ConstantFP::getZero(Ty: VTy);
3342
3343 if ((IID == Intrinsic::ceil || IsRoundNearestOrTrunc) &&
3344 KnownSrc.isKnownAlways(Mask: fcNegZero | fcNegSubnormal))
3345 return ConstantFP::getZero(Ty: VTy, Negative: true);
3346
3347 if (IID == Intrinsic::floor && KnownSrc.isKnownAlways(Mask: fcNegSubnormal))
3348 return ConstantFP::get(Ty: VTy, V: -1.0);
3349
3350 if (IID == Intrinsic::ceil && KnownSrc.isKnownAlways(Mask: fcPosSubnormal))
3351 return ConstantFP::get(Ty: VTy, V: 1.0);
3352
3353 Known = KnownFPClass::roundToIntegral(
3354 Src: KnownSrc, IsTrunc: IID == Intrinsic::trunc,
3355 IsMultiUnitFPType: VTy->getScalarType()->isMultiUnitFPType());
3356
3357 Known.knownNot(RuleOut: ~DemandedMask);
3358
3359 if (Constant *SingleVal =
3360 getFPClassConstant(Ty: VTy, Mask: Known.getKnownFPClasses(),
3361 /*IsCanonicalizing=*/true))
3362 return SingleVal;
3363
3364 if ((IID == Intrinsic::trunc || IsRoundNearestOrTrunc) &&
3365 KnownSrc.isKnownAlways(Mask: fcZero | fcSubnormal)) {
3366 IRBuilderBase::InsertPointGuard Guard(Builder);
3367 Builder.SetInsertPoint(CI);
3368
3369 Value *Copysign = Builder.CreateCopySign(LHS: ConstantFP::getZero(Ty: VTy),
3370 RHS: CI->getArgOperand(i: 0));
3371 Copysign->takeName(V: CI);
3372 return Copysign;
3373 }
3374
3375 FastMathFlags InferredFMF =
3376 inferFastMathValueFlags(FMF, ValidResults: Known.getKnownFPClasses(), Known: KnownSrc);
3377 if (InferredFMF != FMF) {
3378 CI->dropUBImplyingAttrsAndMetadata();
3379 CI->setFastMathFlags(InferredFMF);
3380 return CI;
3381 }
3382
3383 return nullptr;
3384 }
3385 case Intrinsic::fptrunc_round:
3386 return simplifyDemandedUseFPClassFPTrunc(IC&: *this, I&: *CI, FMF, DemandedMask,
3387 Known, SQ, Depth);
3388 case Intrinsic::canonicalize: {
3389 Type *EltTy = VTy->getScalarType();
3390
3391 // TODO: This could have more refined support for PositiveZero denormal
3392 // mode.
3393 if (EltTy->isIEEELikeFPTy()) {
3394 DenormalMode Mode = F.getDenormalMode(FPType: EltTy->getFltSemantics());
3395
3396 FPClassTest SrcDemandedMask = DemandedMask;
3397
3398 // A demanded quiet nan result may have come from a signaling nan, so we
3399 // need to expand the demanded mask.
3400 if ((DemandedMask & fcQNan) != fcNone)
3401 SrcDemandedMask |= fcSNan;
3402
3403 if (Mode != DenormalMode::getIEEE()) {
3404 // Any zero results may have come from flushed denormals.
3405 if (DemandedMask & fcPosZero)
3406 SrcDemandedMask |= fcPosSubnormal;
3407 if (DemandedMask & fcNegZero)
3408 SrcDemandedMask |= fcNegSubnormal;
3409 }
3410
3411 if (Mode == DenormalMode::getPreserveSign()) {
3412 // If a denormal input will be flushed, and we don't need zeros, we
3413 // don't need denormals either.
3414 if ((DemandedMask & fcPosZero) == fcNone)
3415 SrcDemandedMask &= ~fcPosSubnormal;
3416
3417 if ((DemandedMask & fcNegZero) == fcNone)
3418 SrcDemandedMask &= ~fcNegSubnormal;
3419 }
3420
3421 KnownFPClass KnownSrc;
3422
3423 // Simplify upstream operations before trying to simplify this call.
3424 if (SimplifyDemandedFPClass(I, Op: 0, DemandedMask: SrcDemandedMask, Known&: KnownSrc, Q: SQ,
3425 Depth: Depth + 1))
3426 return I;
3427
3428 // Perform the canonicalization to see if this folded to a constant.
3429 Known = KnownFPClass::canonicalize(Src: KnownSrc, DenormMode: Mode);
3430 Known.knownNot(RuleOut: ~DemandedMask);
3431
3432 if (Constant *SingleVal =
3433 getFPClassConstant(Ty: VTy, Mask: Known.getKnownFPClasses()))
3434 return SingleVal;
3435
3436 // For IEEE handling, there is only a bit change for nan inputs, so we
3437 // can drop it if we do not demand nan results or we know the input
3438 // isn't a nan.
3439 // Otherwise, we also need to avoid denormal inputs to drop the
3440 // canonicalize.
3441 if (KnownSrc.isKnownNeverNaN() && (Mode == DenormalMode::getIEEE() ||
3442 KnownSrc.isKnownNeverSubnormal()))
3443 return CI->getArgOperand(i: 0);
3444
3445 FastMathFlags InferredFMF =
3446 inferFastMathValueFlags(FMF, ValidResults: Known.getKnownFPClasses(), Known: KnownSrc);
3447 if (InferredFMF != FMF) {
3448 CI->dropUBImplyingAttrsAndMetadata();
3449 CI->setFastMathFlags(InferredFMF);
3450 return CI;
3451 }
3452
3453 return nullptr;
3454 }
3455
3456 [[fallthrough]];
3457 }
3458 default:
3459 Known = computeKnownFPClass(V: I, InterestedClasses: DemandedMask, SQ, Depth: Depth + 1);
3460 Known.knownNot(RuleOut: ~DemandedMask);
3461 break;
3462 }
3463
3464 break;
3465 }
3466 case Instruction::Select: {
3467 KnownFPClass KnownLHS, KnownRHS;
3468 if (SimplifyDemandedFPClass(I, Op: 2, DemandedMask, Known&: KnownRHS, Q: SQ, Depth: Depth + 1) ||
3469 SimplifyDemandedFPClass(I, Op: 1, DemandedMask, Known&: KnownLHS, Q: SQ, Depth: Depth + 1))
3470 return I;
3471
3472 if (KnownLHS.isKnownNever(Mask: DemandedMask))
3473 return I->getOperand(i: 2);
3474 if (KnownRHS.isKnownNever(Mask: DemandedMask))
3475 return I->getOperand(i: 1);
3476
3477 adjustKnownFPClassForSelectArm(Known&: KnownLHS, Cond: I->getOperand(i: 0), Arm: I->getOperand(i: 1),
3478 /*Invert=*/false, Q: SQ, Depth);
3479 adjustKnownFPClassForSelectArm(Known&: KnownRHS, Cond: I->getOperand(i: 0), Arm: I->getOperand(i: 2),
3480 /*Invert=*/true, Q: SQ, Depth);
3481 Known = KnownLHS.intersectWith(RHS: KnownRHS);
3482 Known.knownNot(RuleOut: ~DemandedMask);
3483 break;
3484 }
3485 case Instruction::ExtractElement: {
3486 // TODO: Handle demanded element mask
3487 if (SimplifyDemandedFPClass(I, Op: 0, DemandedMask, Known, Q: SQ, Depth: Depth + 1))
3488 return I;
3489 Known.knownNot(RuleOut: ~DemandedMask);
3490 break;
3491 }
3492 case Instruction::InsertElement: {
3493 KnownFPClass KnownInserted, KnownVec;
3494 if (SimplifyDemandedFPClass(I, Op: 1, DemandedMask, Known&: KnownInserted, Q: SQ,
3495 Depth: Depth + 1) ||
3496 SimplifyDemandedFPClass(I, Op: 0, DemandedMask, Known&: KnownVec, Q: SQ, Depth: Depth + 1))
3497 return I;
3498
3499 // TODO: Use demanded elements logic from computeKnownFPClass
3500 Known = KnownVec | KnownInserted;
3501 Known.knownNot(RuleOut: ~DemandedMask);
3502 break;
3503 }
3504 case Instruction::ShuffleVector: {
3505 KnownFPClass KnownLHS, KnownRHS;
3506 if (SimplifyDemandedFPClass(I, Op: 1, DemandedMask, Known&: KnownRHS, Q: SQ, Depth: Depth + 1) ||
3507 SimplifyDemandedFPClass(I, Op: 0, DemandedMask, Known&: KnownLHS, Q: SQ, Depth: Depth + 1))
3508 return I;
3509
3510 // TODO: This is overly conservative and should consider demanded elements,
3511 // and splats.
3512 Known = KnownLHS | KnownRHS;
3513 Known.knownNot(RuleOut: ~DemandedMask);
3514 break;
3515 }
3516 case Instruction::InsertValue: {
3517 KnownFPClass KnownAgg, KnownElt;
3518 if (SimplifyDemandedFPClass(I, Op: 0, DemandedMask, Known&: KnownAgg, Q: SQ, Depth: Depth + 1) ||
3519 SimplifyDemandedFPClass(I, Op: 1, DemandedMask, Known&: KnownElt, Q: SQ, Depth: Depth + 1))
3520 return I;
3521
3522 Known = KnownAgg | KnownElt;
3523 break;
3524 }
3525 case Instruction::ExtractValue: {
3526 Value *ExtractSrc;
3527 if (match(V: I, P: m_ExtractValue<0>(V: m_OneUse(SubPattern: m_Value(V&: ExtractSrc))))) {
3528 if (auto *II = dyn_cast<IntrinsicInst>(Val: ExtractSrc)) {
3529 const Intrinsic::ID IID = II->getIntrinsicID();
3530 switch (IID) {
3531 case Intrinsic::frexp: {
3532 FPClassTest SrcDemandedMask = fcNone;
3533 if (DemandedMask & fcNan)
3534 SrcDemandedMask |= fcNan;
3535 if (DemandedMask & fcNegFinite)
3536 SrcDemandedMask |= fcNegFinite;
3537 if (DemandedMask & fcPosFinite)
3538 SrcDemandedMask |= fcPosFinite;
3539 if (DemandedMask & fcPosInf)
3540 SrcDemandedMask |= fcPosInf;
3541 if (DemandedMask & fcNegInf)
3542 SrcDemandedMask |= fcNegInf;
3543
3544 KnownFPClass KnownSrc;
3545 if (SimplifyDemandedFPClass(I: II, Op: 0, DemandedMask: SrcDemandedMask, Known&: KnownSrc, Q: SQ,
3546 Depth: Depth + 1))
3547 return I;
3548
3549 Type *EltTy = VTy->getScalarType();
3550 DenormalMode Mode = F.getDenormalMode(FPType: EltTy->getFltSemantics());
3551
3552 Known = KnownFPClass::frexp_mant(Src: KnownSrc, Mode);
3553 Known.setKnownFPClasses(Known.getKnownFPClasses() & DemandedMask);
3554
3555 if (Constant *SingleVal =
3556 getFPClassConstant(Ty: VTy, Mask: Known.getKnownFPClasses(),
3557 /*IsCanonicalizing=*/true))
3558 return SingleVal;
3559
3560 if (Known.isKnownAlways(Mask: fcInf | fcNan))
3561 return II->getArgOperand(i: 0);
3562
3563 return nullptr;
3564 }
3565 default:
3566 break;
3567 }
3568 }
3569 }
3570
3571 KnownFPClass KnownSrc;
3572 if (SimplifyDemandedFPClass(I, Op: 0, DemandedMask, Known&: KnownSrc, Q: SQ, Depth: Depth + 1))
3573 return I;
3574 Known = KnownSrc;
3575 break;
3576 }
3577 case Instruction::PHI: {
3578 const unsigned PhiRecursionLimit = MaxAnalysisRecursionDepth - 2;
3579 if (Depth >= PhiRecursionLimit)
3580 break;
3581
3582 PHINode *P = cast<PHINode>(Val: I);
3583 SimplifyQuery ContextSQ = SQ.getWithoutCondContext();
3584
3585 bool First = true;
3586 bool Changed = false;
3587 for (unsigned I = 0, E = P->getNumIncomingValues(); I != E; ++I) {
3588 // TODO: Better support for self recursive phi
3589 BasicBlock *PredBB = P->getIncomingBlock(i: I);
3590 const Instruction *CtxI = PredBB->getTerminator();
3591
3592 // Attempt to simplify all incoming edges at a time. If we simplify one
3593 // incoming edge, the phi may fold away, losing information on a later
3594 // visit.
3595 KnownFPClass KnownSrc;
3596 if (SimplifyDemandedFPClass(
3597 I: P, Op: P->getOperandNumForIncomingValue(i: I), DemandedMask, Known&: KnownSrc,
3598 Q: ContextSQ.getWithInstruction(I: CtxI), Depth: Depth + 1)) {
3599 // Fixup the other block references to the simplified value.
3600 P->setIncomingValueForBlock(BB: PredBB, V: P->getIncomingValue(i: I));
3601 Changed = true;
3602 }
3603
3604 if (First) {
3605 Known = KnownSrc;
3606 First = false;
3607 } else {
3608 Known |= KnownSrc;
3609 }
3610 }
3611
3612 if (Changed)
3613 return P;
3614
3615 Known.knownNot(RuleOut: ~DemandedMask);
3616 break;
3617 }
3618 default:
3619 Known = computeKnownFPClass(V: I, InterestedClasses: DemandedMask, SQ, Depth: Depth + 1);
3620 Known.knownNot(RuleOut: ~DemandedMask);
3621 break;
3622 }
3623
3624 return getFPClassConstant(Ty: VTy, Mask: Known.getKnownFPClasses());
3625}
3626
3627/// Helper routine of SimplifyDemandedUseFPClass. It computes Known
3628/// floating-point classes. It also tries to handle simplifications that can be
3629/// done based on DemandedMask, but without modifying the Instruction.
3630Value *InstCombinerImpl::SimplifyMultipleUseDemandedFPClass(
3631 Instruction *I, FPClassTest DemandedMask, KnownFPClass &Known,
3632 const SimplifyQuery &SQ, unsigned Depth) {
3633 FastMathFlags FMF;
3634 if (auto *FPOp = dyn_cast<FPMathOperator>(Val: I)) {
3635 FMF = FPOp->getFastMathFlags();
3636 DemandedMask = adjustDemandedMaskFromFlags(DemandedMask, FMF);
3637 }
3638
3639 switch (I->getOpcode()) {
3640 case Instruction::Select: {
3641 // TODO: Can we infer which side it came from based on adjusted result
3642 // class?
3643 KnownFPClass KnownRHS =
3644 computeKnownFPClass(V: I->getOperand(i: 2), InterestedClasses: DemandedMask, SQ, Depth: Depth + 1);
3645 if (KnownRHS.isKnownNever(Mask: DemandedMask))
3646 return I->getOperand(i: 1);
3647
3648 KnownFPClass KnownLHS =
3649 computeKnownFPClass(V: I->getOperand(i: 1), InterestedClasses: DemandedMask, SQ, Depth: Depth + 1);
3650 if (KnownLHS.isKnownNever(Mask: DemandedMask))
3651 return I->getOperand(i: 2);
3652
3653 adjustKnownFPClassForSelectArm(Known&: KnownLHS, Cond: I->getOperand(i: 0), Arm: I->getOperand(i: 1),
3654 /*Invert=*/false, Q: SQ, Depth);
3655 adjustKnownFPClassForSelectArm(Known&: KnownRHS, Cond: I->getOperand(i: 0), Arm: I->getOperand(i: 2),
3656 /*Invert=*/true, Q: SQ, Depth);
3657 Known = KnownLHS.intersectWith(RHS: KnownRHS);
3658 Known.knownNot(RuleOut: ~DemandedMask);
3659 break;
3660 }
3661 case Instruction::FNeg: {
3662 // Special case fneg(fabs(x))
3663 Value *Src;
3664
3665 Value *FNegSrc = I->getOperand(i: 0);
3666 if (!match(V: FNegSrc, P: m_FAbs(Op0: m_Value(V&: Src)))) {
3667 Known = computeKnownFPClass(V: I, InterestedClasses: DemandedMask, SQ, Depth: Depth + 1);
3668 break;
3669 }
3670
3671 KnownFPClass KnownSrc = computeKnownFPClass(V: Src, InterestedClasses: fcAllFlags, SQ, Depth: Depth + 1);
3672
3673 FastMathFlags FabsFMF = cast<FPMathOperator>(Val: FNegSrc)->getFastMathFlags();
3674 FPClassTest ThisDemandedMask =
3675 adjustDemandedMaskFromFlags(DemandedMask, FMF: FabsFMF);
3676
3677 // We cannot apply the NSZ logic with multiple uses. We can apply it if the
3678 // inner fabs has it and this is the only use.
3679 if (Value *Simplified = simplifyDemandedFPClassFnegFabs(
3680 Known, Src, DemandedMask: ThisDemandedMask, KnownSrc, /*NSZ=*/false))
3681 return Simplified;
3682 break;
3683 }
3684 case Instruction::Call: {
3685 const CallInst *CI = cast<CallInst>(Val: I);
3686 const Intrinsic::ID IID = CI->getIntrinsicID();
3687 switch (IID) {
3688 case Intrinsic::fabs: {
3689 Value *Src = CI->getArgOperand(i: 0);
3690 KnownFPClass KnownSrc =
3691 computeKnownFPClass(V: Src, InterestedClasses: fcAllFlags, SQ, Depth: Depth + 1);
3692
3693 // NSZ cannot be applied in multiple use case (maybe it could if all uses
3694 // were known nsz)
3695 if (Value *Simplified = simplifyDemandedFPClassFabs(
3696 Known, Src: CI->getArgOperand(i: 0), DemandedMask, KnownSrc,
3697 /*NSZ=*/false))
3698 return Simplified;
3699 break;
3700 }
3701 case Intrinsic::copysign: {
3702 Value *Mag = CI->getArgOperand(i: 0);
3703 Value *Sign = CI->getArgOperand(i: 1);
3704 KnownFPClass KnownMag =
3705 computeKnownFPClass(V: Mag, InterestedClasses: fcAllFlags, SQ, Depth: Depth + 1);
3706
3707 // Rule out some cases by magnitude, which may help prove the sign bit is
3708 // one direction or the other.
3709 KnownMag.knownNot(RuleOut: ~llvm::unknown_sign(Mask: DemandedMask));
3710
3711 // Cannot use nsz in the multiple use case.
3712 if (Value *Simplified = simplifyDemandedFPClassCopysignMag(
3713 MagSrc: Mag, DemandedMask, KnownSrc: KnownMag, /*NSZ=*/false))
3714 return Simplified;
3715
3716 KnownFPClass KnownSign =
3717 computeKnownFPClass(V: Sign, InterestedClasses: fcAllFlags, SQ, Depth: Depth + 1);
3718
3719 if (FMF.noInfs())
3720 KnownSign.knownNot(RuleOut: fcInf);
3721 if (FMF.noNaNs())
3722 KnownSign.knownNot(RuleOut: fcNan);
3723
3724 if (KnownSign.getSignBit() && KnownMag.getSignBit() &&
3725 *KnownSign.getSignBit() == *KnownMag.getSignBit())
3726 return Mag;
3727
3728 Known = KnownFPClass::copysign(KnownMag, KnownSign);
3729 break;
3730 }
3731 case Intrinsic::maxnum:
3732 case Intrinsic::minnum:
3733 case Intrinsic::maximum:
3734 case Intrinsic::minimum:
3735 case Intrinsic::maximumnum:
3736 case Intrinsic::minimumnum: {
3737 KnownFPClass KnownRHS = computeKnownFPClass(V: CI->getArgOperand(i: 1),
3738 InterestedClasses: DemandedMask, SQ, Depth: Depth + 1);
3739 if (KnownRHS.isUnknown())
3740 return nullptr;
3741
3742 KnownFPClass KnownLHS = computeKnownFPClass(V: CI->getArgOperand(i: 0),
3743 InterestedClasses: DemandedMask, SQ, Depth: Depth + 1);
3744
3745 // Cannot use NSZ in the multiple use case.
3746 return simplifyDemandedFPClassMinMax(Known, IID, CI, DemandedMask,
3747 KnownLHS, KnownRHS, F,
3748 /*NSZ=*/false);
3749 }
3750 default:
3751 break;
3752 }
3753
3754 [[fallthrough]];
3755 }
3756 default:
3757 Known = computeKnownFPClass(V: I, InterestedClasses: DemandedMask, SQ, Depth: Depth + 1);
3758 Known.knownNot(RuleOut: ~DemandedMask);
3759 break;
3760 }
3761
3762 return getFPClassConstant(Ty: I->getType(), Mask: Known.getKnownFPClasses());
3763}
3764
3765bool InstCombinerImpl::SimplifyDemandedFPClass(Instruction *I, unsigned OpNo,
3766 FPClassTest DemandedMask,
3767 KnownFPClass &Known,
3768 const SimplifyQuery &SQ,
3769 unsigned Depth) {
3770 Use &U = I->getOperandUse(i: OpNo);
3771 Value *V = U.get();
3772 Type *VTy = V->getType();
3773
3774 if (DemandedMask == fcNone) {
3775 if (isa<PoisonValue>(Val: V))
3776 return false;
3777 replaceUse(U, NewValue: PoisonValue::get(T: VTy));
3778 return true;
3779 }
3780
3781 // Handle constant
3782 Instruction *VInst = dyn_cast<Instruction>(Val: V);
3783 if (!VInst) {
3784 // Handle constants and arguments
3785 Known = computeKnownFPClass(V, InterestedClasses: fcAllFlags, SQ, Depth);
3786 Known.knownNot(RuleOut: ~DemandedMask);
3787
3788 if (Known.getKnownFPClasses() == fcNone) {
3789 if (isa<PoisonValue>(Val: V))
3790 return false;
3791 replaceUse(U, NewValue: PoisonValue::get(T: VTy));
3792 return true;
3793 }
3794
3795 // Do not try to replace values which are already constants (unless we are
3796 // folding to poison). Doing so could promote poison elements to non-poison
3797 // constants.
3798 if (isa<Constant>(Val: V))
3799 return false;
3800
3801 Value *FoldedToConst = getFPClassConstant(Ty: VTy, Mask: Known.getKnownFPClasses());
3802 if (!FoldedToConst || FoldedToConst == V)
3803 return false;
3804
3805 replaceUse(U, NewValue: FoldedToConst);
3806 return true;
3807 }
3808
3809 if (Depth == MaxAnalysisRecursionDepth) {
3810 Known.knownNot(RuleOut: ~DemandedMask);
3811 return false;
3812 }
3813
3814 Value *NewVal;
3815
3816 if (VInst->hasOneUse()) {
3817 // If the instruction has one use, we can directly simplify it.
3818 NewVal = SimplifyDemandedUseFPClass(I: VInst, DemandedMask, Known, SQ, Depth);
3819 } else {
3820 // If there are multiple uses of this instruction, then we can simplify
3821 // VInst to some other value, but not modify the instruction.
3822 NewVal = SimplifyMultipleUseDemandedFPClass(I: VInst, DemandedMask, Known, SQ,
3823 Depth);
3824 }
3825
3826 if (!NewVal)
3827 return false;
3828 if (Instruction *OpInst = dyn_cast<Instruction>(Val&: U))
3829 salvageDebugInfo(I&: *OpInst);
3830
3831 replaceUse(U, NewValue: NewVal);
3832 return true;
3833}
3834