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