1//===- lib/CodeGen/GlobalISel/GISelValueTracking.cpp --------------*- C++
2//*-===//
3//
4// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
5// See https://llvm.org/LICENSE.txt for license information.
6// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7//
8//===----------------------------------------------------------------------===//
9//
10/// Provides analysis for querying information about KnownBits during GISel
11/// passes.
12//
13//===----------------------------------------------------------------------===//
14#include "llvm/CodeGen/GlobalISel/GISelValueTracking.h"
15#include "llvm/ADT/APFloat.h"
16#include "llvm/ADT/FloatingPointMode.h"
17#include "llvm/ADT/ScopeExit.h"
18#include "llvm/ADT/StringExtras.h"
19#include "llvm/Analysis/ValueTracking.h"
20#include "llvm/Analysis/VectorUtils.h"
21#include "llvm/CodeGen/GlobalISel/GenericMachineInstrs.h"
22#include "llvm/CodeGen/GlobalISel/MIPatternMatch.h"
23#include "llvm/CodeGen/GlobalISel/MachineFloatingPointPredicateUtils.h"
24#include "llvm/CodeGen/GlobalISel/Utils.h"
25#include "llvm/CodeGen/LowLevelTypeUtils.h"
26#include "llvm/CodeGen/MachineFrameInfo.h"
27#include "llvm/CodeGen/MachineInstr.h"
28#include "llvm/CodeGen/MachineOperand.h"
29#include "llvm/CodeGen/MachineRegisterInfo.h"
30#include "llvm/CodeGen/Register.h"
31#include "llvm/CodeGen/TargetLowering.h"
32#include "llvm/CodeGen/TargetOpcodes.h"
33#include "llvm/IR/ConstantRange.h"
34#include "llvm/IR/DerivedTypes.h"
35#include "llvm/IR/FMF.h"
36#include "llvm/InitializePasses.h"
37#include "llvm/MC/TargetRegistry.h"
38#include "llvm/Support/KnownBits.h"
39#include "llvm/Support/KnownFPClass.h"
40#include "llvm/Target/TargetMachine.h"
41
42#define DEBUG_TYPE "gisel-known-bits"
43
44using namespace llvm;
45using namespace MIPatternMatch;
46
47char llvm::GISelValueTrackingAnalysisLegacy::ID = 0;
48
49INITIALIZE_PASS(GISelValueTrackingAnalysisLegacy, DEBUG_TYPE,
50 "Analysis for ComputingKnownBits", false, true)
51
52GISelValueTracking::GISelValueTracking(MachineFunction &MF, unsigned MaxDepth)
53 : MF(MF), MRI(MF.getRegInfo()), TL(*MF.getSubtarget().getTargetLowering()),
54 DL(MF.getFunction().getDataLayout()), MaxDepth(MaxDepth) {}
55
56Align GISelValueTracking::computeKnownAlignment(Register R, unsigned Depth) {
57 const MachineInstr *MI = MRI.getVRegDef(Reg: R);
58 switch (MI->getOpcode()) {
59 case TargetOpcode::COPY:
60 return computeKnownAlignment(R: MI->getOperand(i: 1).getReg(), Depth);
61 case TargetOpcode::G_ASSERT_ALIGN: {
62 // TODO: Min with source
63 return Align(MI->getOperand(i: 2).getImm());
64 }
65 case TargetOpcode::G_FRAME_INDEX: {
66 int FrameIdx = MI->getOperand(i: 1).getIndex();
67 return MF.getFrameInfo().getObjectAlign(ObjectIdx: FrameIdx);
68 }
69 case TargetOpcode::G_INTRINSIC:
70 case TargetOpcode::G_INTRINSIC_W_SIDE_EFFECTS:
71 case TargetOpcode::G_INTRINSIC_CONVERGENT:
72 case TargetOpcode::G_INTRINSIC_CONVERGENT_W_SIDE_EFFECTS:
73 default:
74 return TL.computeKnownAlignForTargetInstr(Analysis&: *this, R, MRI, Depth: Depth + 1);
75 }
76}
77
78KnownBits GISelValueTracking::getKnownBits(Register R) {
79 const LLT Ty = MRI.getType(Reg: R);
80 // Since the number of lanes in a scalable vector is unknown at compile time,
81 // we track one bit which is implicitly broadcast to all lanes. This means
82 // that all lanes in a scalable vector are considered demanded.
83 APInt DemandedElts =
84 Ty.isFixedVector() ? APInt::getAllOnes(numBits: Ty.getNumElements()) : APInt(1, 1);
85 return getKnownBits(R, DemandedElts);
86}
87
88KnownBits GISelValueTracking::getKnownBits(Register R,
89 const APInt &DemandedElts,
90 unsigned Depth) {
91 KnownBits Known;
92 computeKnownBitsImpl(R, Known, DemandedElts, Depth);
93 return Known;
94}
95
96bool GISelValueTracking::signBitIsZero(Register R) {
97 LLT Ty = MRI.getType(Reg: R);
98 unsigned BitWidth = Ty.getScalarSizeInBits();
99 return maskedValueIsZero(Val: R, Mask: APInt::getSignMask(BitWidth));
100}
101
102bool GISelValueTracking::isKnownNeverZero(Register R, unsigned Depth) {
103 LLT Ty = MRI.getType(Reg: R);
104 const APInt ScalarDemandedElts(1, 1);
105 APInt DemandedElts = Ty.isFixedVector()
106 ? APInt::getAllOnes(numBits: Ty.getNumElements())
107 : ScalarDemandedElts;
108 return isKnownNeverZero(R, DemandedElts, Depth);
109}
110
111bool GISelValueTracking::isKnownNeverZero(Register R, const APInt &DemandedElts,
112 unsigned Depth) {
113 if (Depth >= getMaxDepth())
114 return false;
115
116 const APInt ScalarDemandedElts(1, 1);
117 MachineInstr &MI = *MRI.getVRegDef(Reg: R);
118
119 switch (MI.getOpcode()) {
120 default:
121 break;
122
123 case TargetOpcode::G_BUILD_VECTOR: {
124 for (const auto &[I, MO] : enumerate(First: drop_begin(RangeOrContainer: MI.operands()))) {
125 if (!DemandedElts[I])
126 continue;
127 if (!isKnownNeverZero(R: MO.getReg(), DemandedElts: ScalarDemandedElts, Depth: Depth + 1))
128 return false;
129 }
130 return true;
131 }
132
133 case TargetOpcode::G_EXTRACT_VECTOR_ELT: {
134 GExtractVectorElement &Extract = cast<GExtractVectorElement>(Val&: MI);
135 Register InVec = Extract.getVectorReg();
136 LLT VecTy = MRI.getType(Reg: InVec);
137 if (VecTy.isScalableVector())
138 break;
139 unsigned NumSrcElts = VecTy.getNumElements();
140 // An out-of-range constant index produces poison. Keep all lanes demanded,
141 // which is poison-safe and matches SelectionDAG's conservative behavior.
142 APInt DemandedSrcElts = APInt::getAllOnes(numBits: NumSrcElts);
143 if (auto Idx = getIConstantVRegVal(VReg: Extract.getIndexReg(), MRI)) {
144 if (Idx->ult(RHS: NumSrcElts))
145 DemandedSrcElts = APInt::getOneBitSet(numBits: NumSrcElts, BitNo: Idx->getZExtValue());
146 }
147 return isKnownNeverZero(R: InVec, DemandedElts: DemandedSrcElts, Depth: Depth + 1);
148 }
149
150 case TargetOpcode::G_SHUFFLE_VECTOR: {
151 GShuffleVector &Shuf = cast<GShuffleVector>(Val&: MI);
152 LLT SrcTy = MRI.getType(Reg: Shuf.getSrc1Reg());
153 if (SrcTy.isScalableVector())
154 break;
155 APInt DemandedLHS, DemandedRHS;
156 if (!getShuffleDemandedElts(SrcWidth: SrcTy.getNumElements(), Mask: Shuf.getMask(),
157 DemandedElts, DemandedLHS, DemandedRHS))
158 break;
159 if (!DemandedLHS.isZero() &&
160 !isKnownNeverZero(R: Shuf.getSrc1Reg(), DemandedElts: DemandedLHS, Depth: Depth + 1))
161 return false;
162 if (!DemandedRHS.isZero() &&
163 !isKnownNeverZero(R: Shuf.getSrc2Reg(), DemandedElts: DemandedRHS, Depth: Depth + 1))
164 return false;
165 return true;
166 }
167
168 case TargetOpcode::G_OR:
169 return isKnownNeverZero(R: MI.getOperand(i: 1).getReg(), DemandedElts,
170 Depth: Depth + 1) ||
171 isKnownNeverZero(R: MI.getOperand(i: 2).getReg(), DemandedElts, Depth: Depth + 1);
172
173 case TargetOpcode::G_SELECT:
174 return isKnownNeverZero(R: MI.getOperand(i: 2).getReg(), DemandedElts,
175 Depth: Depth + 1) &&
176 isKnownNeverZero(R: MI.getOperand(i: 3).getReg(), DemandedElts, Depth: Depth + 1);
177
178 case TargetOpcode::G_SHL: {
179 Register LHSReg = MI.getOperand(i: 1).getReg();
180 if (MI.getFlag(Flag: MachineInstr::NoSWrap) || MI.getFlag(Flag: MachineInstr::NoUWrap))
181 return isKnownNeverZero(R: LHSReg, DemandedElts, Depth: Depth + 1);
182 KnownBits ValKnown = getKnownBits(R: LHSReg, DemandedElts, Depth: Depth + 1);
183 if (ValKnown.One[0])
184 return true;
185 APInt MaxCnt =
186 getKnownBits(R: MI.getOperand(i: 2).getReg(), DemandedElts, Depth: Depth + 1)
187 .getMaxValue();
188 if (MaxCnt.ult(RHS: ValKnown.getBitWidth()) &&
189 !ValKnown.One.shl(ShiftAmt: MaxCnt).isZero())
190 return true;
191 break;
192 }
193 }
194
195 // Pass through this frame's Depth (not Depth+1) because we have not recursed
196 // into a child MI here: the fallback queries KnownBits for the same R.
197 return getKnownBits(R, DemandedElts, Depth).isNonZero();
198}
199
200APInt GISelValueTracking::getKnownZeroes(Register R) {
201 return getKnownBits(R).Zero;
202}
203
204APInt GISelValueTracking::getKnownOnes(Register R) {
205 return getKnownBits(R).One;
206}
207
208[[maybe_unused]] static void
209dumpResult(const MachineInstr &MI, const KnownBits &Known, unsigned Depth) {
210 dbgs() << "[" << Depth << "] Compute known bits: " << MI << "[" << Depth
211 << "] Computed for: " << MI << "[" << Depth << "] Known: 0x"
212 << toString(I: Known.Zero | Known.One, Radix: 16, Signed: false) << "\n"
213 << "[" << Depth << "] Zero: 0x" << toString(I: Known.Zero, Radix: 16, Signed: false)
214 << "\n"
215 << "[" << Depth << "] One: 0x" << toString(I: Known.One, Radix: 16, Signed: false)
216 << "\n";
217}
218
219/// Compute known bits for the intersection of \p Src0 and \p Src1
220void GISelValueTracking::computeKnownBitsMin(Register Src0, Register Src1,
221 KnownBits &Known,
222 const APInt &DemandedElts,
223 unsigned Depth) {
224 // Test src1 first, since we canonicalize simpler expressions to the RHS.
225 computeKnownBitsImpl(R: Src1, Known, DemandedElts, Depth);
226
227 // If we don't know any bits, early out.
228 if (Known.isUnknown())
229 return;
230
231 KnownBits Known2;
232 computeKnownBitsImpl(R: Src0, Known&: Known2, DemandedElts, Depth);
233
234 // Only known if known in both the LHS and RHS.
235 Known = Known.intersectWith(RHS: Known2);
236}
237
238// Bitfield extract is computed as (Src >> Offset) & Mask, where Mask is
239// created using Width. Use this function when the inputs are KnownBits
240// objects. TODO: Move this KnownBits.h if this is usable in more cases.
241static KnownBits extractBits(unsigned BitWidth, const KnownBits &SrcOpKnown,
242 const KnownBits &OffsetKnown,
243 const KnownBits &WidthKnown) {
244 KnownBits Mask(BitWidth);
245 Mask.Zero = APInt::getBitsSetFrom(
246 numBits: BitWidth, loBit: WidthKnown.getMaxValue().getLimitedValue(Limit: BitWidth));
247 Mask.One = APInt::getLowBitsSet(
248 numBits: BitWidth, loBitsSet: WidthKnown.getMinValue().getLimitedValue(Limit: BitWidth));
249 return KnownBits::lshr(LHS: SrcOpKnown, RHS: OffsetKnown) & Mask;
250}
251
252void GISelValueTracking::computeKnownBits(Register R, KnownBits &Known,
253 const APInt &DemandedElts,
254 unsigned Depth) {
255 MachineInstr &MI = *MRI.getVRegDef(Reg: R);
256 unsigned Opcode = MI.getOpcode();
257 LLT DstTy = MRI.getType(Reg: R);
258
259 // Handle the case where this is called on a register that does not have a
260 // type constraint. For example, it may be post-ISel or this target might not
261 // preserve the type when early-selecting instructions.
262 if (!DstTy.isValid()) {
263 Known = KnownBits();
264 return;
265 }
266
267#ifndef NDEBUG
268 if (DstTy.isFixedVector()) {
269 assert(
270 DstTy.getNumElements() == DemandedElts.getBitWidth() &&
271 "DemandedElt width should equal the fixed vector number of elements");
272 } else {
273 assert(DemandedElts.getBitWidth() == 1 && DemandedElts == APInt(1, 1) &&
274 "DemandedElt width should be 1 for scalars or scalable vectors");
275 }
276#endif
277
278 unsigned BitWidth = DstTy.getScalarSizeInBits();
279 Known = KnownBits(BitWidth); // Don't know anything
280
281 // Depth may get bigger than max depth if it gets passed to a different
282 // GISelValueTracking object.
283 // This may happen when say a generic part uses a GISelValueTracking object
284 // with some max depth, but then we hit TL.computeKnownBitsForTargetInstr
285 // which creates a new GISelValueTracking object with a different and smaller
286 // depth. If we just check for equality, we would never exit if the depth
287 // that is passed down to the target specific GISelValueTracking object is
288 // already bigger than its max depth.
289 if (Depth >= getMaxDepth())
290 return;
291
292 if (!DemandedElts)
293 return; // No demanded elts, better to assume we don't know anything.
294
295 KnownBits Known2;
296
297 switch (Opcode) {
298 default:
299 TL.computeKnownBitsForTargetInstr(Analysis&: *this, R, Known, DemandedElts, MRI,
300 Depth);
301 break;
302 case TargetOpcode::G_BUILD_VECTOR: {
303 // Collect the known bits that are shared by every demanded vector element.
304 Known.Zero.setAllBits();
305 Known.One.setAllBits();
306 for (const auto &[I, MO] : enumerate(First: drop_begin(RangeOrContainer: MI.operands()))) {
307 if (!DemandedElts[I])
308 continue;
309
310 computeKnownBitsImpl(R: MO.getReg(), Known&: Known2, DemandedElts: APInt(1, 1), Depth: Depth + 1);
311
312 // Known bits are the values that are shared by every demanded element.
313 Known = Known.intersectWith(RHS: Known2);
314
315 // If we don't know any bits, early out.
316 if (Known.isUnknown())
317 break;
318 }
319 break;
320 }
321 case TargetOpcode::G_SPLAT_VECTOR: {
322 computeKnownBitsImpl(R: MI.getOperand(i: 1).getReg(), Known, DemandedElts: APInt(1, 1),
323 Depth: Depth + 1);
324 // Implicitly truncate the bits to match the official semantics of
325 // G_SPLAT_VECTOR.
326 Known = Known.trunc(BitWidth);
327 break;
328 }
329 case TargetOpcode::G_FREEZE: {
330 Register Src = MI.getOperand(i: 1).getReg();
331 // freeze of undef/poison is an arbitrary noundef bit pattern, so the known
332 // bits of the source only carry over when it cannot be undef or poison.
333 if (isGuaranteedNotToBeUndefOrPoison(Reg: Src, MRI, Depth: Depth + 1))
334 computeKnownBitsImpl(R: Src, Known, DemandedElts, Depth: Depth + 1);
335 break;
336 }
337 case TargetOpcode::COPY:
338 case TargetOpcode::G_PHI:
339 case TargetOpcode::PHI: {
340 Known.One = APInt::getAllOnes(numBits: BitWidth);
341 Known.Zero = APInt::getAllOnes(numBits: BitWidth);
342 // Destination registers should not have subregisters at this
343 // point of the pipeline, otherwise the main live-range will be
344 // defined more than once, which is against SSA.
345 assert(MI.getOperand(0).getSubReg() == 0 && "Is this code in SSA?");
346 // PHI's operand are a mix of registers and basic blocks interleaved.
347 // We only care about the register ones.
348 for (unsigned Idx = 1; Idx < MI.getNumOperands(); Idx += 2) {
349 const MachineOperand &Src = MI.getOperand(i: Idx);
350 Register SrcReg = Src.getReg();
351 LLT SrcTy = MRI.getType(Reg: SrcReg);
352 // Look through trivial copies and phis but don't look through trivial
353 // copies or phis of the form `%1:(s32) = OP %0:gpr32`, known-bits
354 // analysis is currently unable to determine the bit width of a
355 // register class.
356 //
357 // We can't use NoSubRegister by name as it's defined by each target but
358 // it's always defined to be 0 by tablegen.
359 if (SrcReg.isVirtual() && Src.getSubReg() == 0 /*NoSubRegister*/ &&
360 SrcTy.isValid()) {
361 APInt NowDemandedElts;
362 if (!SrcTy.isFixedVector()) {
363 NowDemandedElts = APInt(1, 1);
364 } else if (DstTy.isFixedVector() &&
365 SrcTy.getNumElements() == DstTy.getNumElements()) {
366 NowDemandedElts = DemandedElts;
367 } else {
368 NowDemandedElts = APInt::getAllOnes(numBits: SrcTy.getNumElements());
369 }
370
371 // For COPYs we don't do anything, don't increase the depth.
372 computeKnownBitsImpl(R: SrcReg, Known&: Known2, DemandedElts: NowDemandedElts,
373 Depth: Depth + (Opcode != TargetOpcode::COPY));
374 Known2 = Known2.anyextOrTrunc(BitWidth);
375 Known = Known.intersectWith(RHS: Known2);
376 // If we reach a point where we don't know anything
377 // just stop looking through the operands.
378 if (Known.isUnknown())
379 break;
380 } else {
381 // We know nothing.
382 Known = KnownBits(BitWidth);
383 break;
384 }
385 }
386 break;
387 }
388 case TargetOpcode::G_STEP_VECTOR: {
389 APInt Step = MI.getOperand(i: 1).getCImm()->getValue();
390
391 if (Step.isPowerOf2())
392 Known.Zero.setLowBits(Step.logBase2());
393
394 if (!isUIntN(N: BitWidth, x: DstTy.getElementCount().getKnownMinValue()))
395 break;
396
397 const APInt MinNumElts =
398 APInt(BitWidth, DstTy.getElementCount().getKnownMinValue());
399 const Function &F = getMachineFunction().getFunction();
400 bool Overflow;
401 const APInt MaxNumElts = getVScaleRange(F: &F, BitWidth)
402 .getUnsignedMax()
403 .umul_ov(RHS: MinNumElts, Overflow);
404 if (Overflow)
405 break;
406 const APInt MaxValue = (MaxNumElts - 1).umul_ov(RHS: Step, Overflow);
407 if (Overflow)
408 break;
409 Known.Zero.setHighBits(MaxValue.countl_zero());
410 break;
411 }
412 case TargetOpcode::G_VSCALE: {
413 const Function &F = getMachineFunction().getFunction();
414 const APInt &Multiplier = MI.getOperand(i: 1).getCImm()->getValue();
415 Known = getVScaleRange(F: &F, BitWidth).multiply(Other: Multiplier).toKnownBits();
416 break;
417 }
418 case TargetOpcode::G_CONSTANT: {
419 Known = KnownBits::makeConstant(C: MI.getOperand(i: 1).getCImm()->getValue());
420 break;
421 }
422 case TargetOpcode::G_FRAME_INDEX: {
423 int FrameIdx = MI.getOperand(i: 1).getIndex();
424 TL.computeKnownBitsForStackObjectPointer(
425 Known, MF, Alignment: MF.getFrameInfo().getObjectAlign(ObjectIdx: FrameIdx));
426 break;
427 }
428 case TargetOpcode::G_SUB: {
429 computeKnownBitsImpl(R: MI.getOperand(i: 1).getReg(), Known, DemandedElts,
430 Depth: Depth + 1);
431 computeKnownBitsImpl(R: MI.getOperand(i: 2).getReg(), Known&: Known2, DemandedElts,
432 Depth: Depth + 1);
433 Known = KnownBits::sub(LHS: Known, RHS: Known2, NSW: MI.getFlag(Flag: MachineInstr::NoSWrap),
434 NUW: MI.getFlag(Flag: MachineInstr::NoUWrap));
435 break;
436 }
437 case TargetOpcode::G_XOR: {
438 computeKnownBitsImpl(R: MI.getOperand(i: 2).getReg(), Known, DemandedElts,
439 Depth: Depth + 1);
440 computeKnownBitsImpl(R: MI.getOperand(i: 1).getReg(), Known&: Known2, DemandedElts,
441 Depth: Depth + 1);
442
443 Known ^= Known2;
444 break;
445 }
446 case TargetOpcode::G_PTR_ADD: {
447 if (DstTy.isVector())
448 break;
449 // G_PTR_ADD is like G_ADD. FIXME: Is this true for all targets?
450 LLT Ty = MRI.getType(Reg: MI.getOperand(i: 1).getReg());
451 if (DL.isNonIntegralAddressSpace(AddrSpace: Ty.getAddressSpace()))
452 break;
453 [[fallthrough]];
454 }
455 case TargetOpcode::G_ADD: {
456 computeKnownBitsImpl(R: MI.getOperand(i: 1).getReg(), Known, DemandedElts,
457 Depth: Depth + 1);
458 computeKnownBitsImpl(R: MI.getOperand(i: 2).getReg(), Known&: Known2, DemandedElts,
459 Depth: Depth + 1);
460 Known = KnownBits::add(LHS: Known, RHS: Known2);
461 break;
462 }
463 case TargetOpcode::G_AND: {
464 // If either the LHS or the RHS are Zero, the result is zero.
465 computeKnownBitsImpl(R: MI.getOperand(i: 2).getReg(), Known, DemandedElts,
466 Depth: Depth + 1);
467 computeKnownBitsImpl(R: MI.getOperand(i: 1).getReg(), Known&: Known2, DemandedElts,
468 Depth: Depth + 1);
469
470 Known &= Known2;
471 break;
472 }
473 case TargetOpcode::G_OR: {
474 // If either the LHS or the RHS are Zero, the result is zero.
475 computeKnownBitsImpl(R: MI.getOperand(i: 2).getReg(), Known, DemandedElts,
476 Depth: Depth + 1);
477 computeKnownBitsImpl(R: MI.getOperand(i: 1).getReg(), Known&: Known2, DemandedElts,
478 Depth: Depth + 1);
479
480 Known |= Known2;
481 break;
482 }
483 case TargetOpcode::G_MUL: {
484 computeKnownBitsImpl(R: MI.getOperand(i: 2).getReg(), Known, DemandedElts,
485 Depth: Depth + 1);
486 computeKnownBitsImpl(R: MI.getOperand(i: 1).getReg(), Known&: Known2, DemandedElts,
487 Depth: Depth + 1);
488 Known = KnownBits::mul(LHS: Known, RHS: Known2);
489 break;
490 }
491 case TargetOpcode::G_UMULH: {
492 computeKnownBitsImpl(R: MI.getOperand(i: 2).getReg(), Known, DemandedElts,
493 Depth: Depth + 1);
494 computeKnownBitsImpl(R: MI.getOperand(i: 1).getReg(), Known&: Known2, DemandedElts,
495 Depth: Depth + 1);
496 Known = KnownBits::mulhu(LHS: Known, RHS: Known2);
497 break;
498 }
499 case TargetOpcode::G_SMULH: {
500 computeKnownBitsImpl(R: MI.getOperand(i: 2).getReg(), Known, DemandedElts,
501 Depth: Depth + 1);
502 computeKnownBitsImpl(R: MI.getOperand(i: 1).getReg(), Known&: Known2, DemandedElts,
503 Depth: Depth + 1);
504 Known = KnownBits::mulhs(LHS: Known, RHS: Known2);
505 break;
506 }
507 case TargetOpcode::G_CLMUL: {
508 computeKnownBitsImpl(R: MI.getOperand(i: 2).getReg(), Known, DemandedElts,
509 Depth: Depth + 1);
510 computeKnownBitsImpl(R: MI.getOperand(i: 1).getReg(), Known&: Known2, DemandedElts,
511 Depth: Depth + 1);
512 Known = KnownBits::clmul(LHS: Known, RHS: Known2);
513 break;
514 }
515 case TargetOpcode::G_UAVGFLOOR: {
516 computeKnownBitsImpl(R: MI.getOperand(i: 1).getReg(), Known, DemandedElts,
517 Depth: Depth + 1);
518 computeKnownBitsImpl(R: MI.getOperand(i: 2).getReg(), Known&: Known2, DemandedElts,
519 Depth: Depth + 1);
520 Known = KnownBits::avgFloorU(LHS: Known, RHS: Known2);
521 break;
522 }
523 case TargetOpcode::G_UAVGCEIL: {
524 computeKnownBitsImpl(R: MI.getOperand(i: 1).getReg(), Known, DemandedElts,
525 Depth: Depth + 1);
526 computeKnownBitsImpl(R: MI.getOperand(i: 2).getReg(), Known&: Known2, DemandedElts,
527 Depth: Depth + 1);
528 Known = KnownBits::avgCeilU(LHS: Known, RHS: Known2);
529 break;
530 }
531 case TargetOpcode::G_SAVGFLOOR: {
532 computeKnownBitsImpl(R: MI.getOperand(i: 1).getReg(), Known, DemandedElts,
533 Depth: Depth + 1);
534 computeKnownBitsImpl(R: MI.getOperand(i: 2).getReg(), Known&: Known2, DemandedElts,
535 Depth: Depth + 1);
536 Known = KnownBits::avgFloorS(LHS: Known, RHS: Known2);
537 break;
538 }
539 case TargetOpcode::G_SAVGCEIL: {
540 computeKnownBitsImpl(R: MI.getOperand(i: 1).getReg(), Known, DemandedElts,
541 Depth: Depth + 1);
542 computeKnownBitsImpl(R: MI.getOperand(i: 2).getReg(), Known&: Known2, DemandedElts,
543 Depth: Depth + 1);
544 Known = KnownBits::avgCeilS(LHS: Known, RHS: Known2);
545 break;
546 }
547 case TargetOpcode::G_ABDU: {
548 computeKnownBitsImpl(R: MI.getOperand(i: 2).getReg(), Known, DemandedElts,
549 Depth: Depth + 1);
550 computeKnownBitsImpl(R: MI.getOperand(i: 1).getReg(), Known&: Known2, DemandedElts,
551 Depth: Depth + 1);
552 Known = KnownBits::abdu(LHS: Known, RHS: Known2);
553 break;
554 }
555 case TargetOpcode::G_ABDS: {
556 computeKnownBitsImpl(R: MI.getOperand(i: 2).getReg(), Known, DemandedElts,
557 Depth: Depth + 1);
558 computeKnownBitsImpl(R: MI.getOperand(i: 1).getReg(), Known&: Known2, DemandedElts,
559 Depth: Depth + 1);
560 Known = KnownBits::abds(LHS: Known, RHS: Known2);
561
562 unsigned SignBits1 =
563 computeNumSignBits(R: MI.getOperand(i: 2).getReg(), DemandedElts, Depth: Depth + 1);
564 if (SignBits1 == 1) {
565 break;
566 }
567 unsigned SignBits0 =
568 computeNumSignBits(R: MI.getOperand(i: 1).getReg(), DemandedElts, Depth: Depth + 1);
569
570 Known.Zero.setHighBits(std::min(a: SignBits0, b: SignBits1) - 1);
571 break;
572 }
573 case TargetOpcode::G_SADDSAT: {
574 computeKnownBitsImpl(R: MI.getOperand(i: 1).getReg(), Known, DemandedElts,
575 Depth: Depth + 1);
576 computeKnownBitsImpl(R: MI.getOperand(i: 2).getReg(), Known&: Known2, DemandedElts,
577 Depth: Depth + 1);
578 Known = KnownBits::sadd_sat(LHS: Known, RHS: Known2);
579 break;
580 }
581 case TargetOpcode::G_UADDSAT: {
582 computeKnownBitsImpl(R: MI.getOperand(i: 1).getReg(), Known, DemandedElts,
583 Depth: Depth + 1);
584 computeKnownBitsImpl(R: MI.getOperand(i: 2).getReg(), Known&: Known2, DemandedElts,
585 Depth: Depth + 1);
586 Known = KnownBits::uadd_sat(LHS: Known, RHS: Known2);
587 break;
588 }
589 case TargetOpcode::G_SSUBSAT: {
590 computeKnownBitsImpl(R: MI.getOperand(i: 1).getReg(), Known, DemandedElts,
591 Depth: Depth + 1);
592 computeKnownBitsImpl(R: MI.getOperand(i: 2).getReg(), Known&: Known2, DemandedElts,
593 Depth: Depth + 1);
594 Known = KnownBits::ssub_sat(LHS: Known, RHS: Known2);
595 break;
596 }
597 case TargetOpcode::G_USUBSAT: {
598 computeKnownBitsImpl(R: MI.getOperand(i: 1).getReg(), Known, DemandedElts,
599 Depth: Depth + 1);
600 computeKnownBitsImpl(R: MI.getOperand(i: 2).getReg(), Known&: Known2, DemandedElts,
601 Depth: Depth + 1);
602 Known = KnownBits::usub_sat(LHS: Known, RHS: Known2);
603 break;
604 }
605 case TargetOpcode::G_UDIV: {
606 computeKnownBitsImpl(R: MI.getOperand(i: 1).getReg(), Known, DemandedElts,
607 Depth: Depth + 1);
608 computeKnownBitsImpl(R: MI.getOperand(i: 2).getReg(), Known&: Known2, DemandedElts,
609 Depth: Depth + 1);
610 Known = KnownBits::udiv(LHS: Known, RHS: Known2,
611 Exact: MI.getFlag(Flag: MachineInstr::MIFlag::IsExact));
612 break;
613 }
614 case TargetOpcode::G_SDIV: {
615 computeKnownBitsImpl(R: MI.getOperand(i: 1).getReg(), Known, DemandedElts,
616 Depth: Depth + 1);
617 computeKnownBitsImpl(R: MI.getOperand(i: 2).getReg(), Known&: Known2, DemandedElts,
618 Depth: Depth + 1);
619 Known = KnownBits::sdiv(LHS: Known, RHS: Known2,
620 Exact: MI.getFlag(Flag: MachineInstr::MIFlag::IsExact));
621 break;
622 }
623 case TargetOpcode::G_UREM: {
624 KnownBits LHSKnown(Known.getBitWidth());
625 KnownBits RHSKnown(Known.getBitWidth());
626
627 computeKnownBitsImpl(R: MI.getOperand(i: 1).getReg(), Known&: LHSKnown, DemandedElts,
628 Depth: Depth + 1);
629 computeKnownBitsImpl(R: MI.getOperand(i: 2).getReg(), Known&: RHSKnown, DemandedElts,
630 Depth: Depth + 1);
631
632 Known = KnownBits::urem(LHS: LHSKnown, RHS: RHSKnown);
633 break;
634 }
635 case TargetOpcode::G_SREM: {
636 KnownBits LHSKnown(Known.getBitWidth());
637 KnownBits RHSKnown(Known.getBitWidth());
638
639 computeKnownBitsImpl(R: MI.getOperand(i: 1).getReg(), Known&: LHSKnown, DemandedElts,
640 Depth: Depth + 1);
641 computeKnownBitsImpl(R: MI.getOperand(i: 2).getReg(), Known&: RHSKnown, DemandedElts,
642 Depth: Depth + 1);
643
644 Known = KnownBits::srem(LHS: LHSKnown, RHS: RHSKnown);
645 break;
646 }
647 case TargetOpcode::G_SELECT: {
648 computeKnownBitsMin(Src0: MI.getOperand(i: 2).getReg(), Src1: MI.getOperand(i: 3).getReg(),
649 Known, DemandedElts, Depth: Depth + 1);
650 break;
651 }
652 case TargetOpcode::G_SMIN: {
653 // TODO: Handle clamp pattern with number of sign bits
654 KnownBits KnownRHS;
655 computeKnownBitsImpl(R: MI.getOperand(i: 1).getReg(), Known, DemandedElts,
656 Depth: Depth + 1);
657 computeKnownBitsImpl(R: MI.getOperand(i: 2).getReg(), Known&: KnownRHS, DemandedElts,
658 Depth: Depth + 1);
659 Known = KnownBits::smin(LHS: Known, RHS: KnownRHS);
660 break;
661 }
662 case TargetOpcode::G_SMAX: {
663 // TODO: Handle clamp pattern with number of sign bits
664 KnownBits KnownRHS;
665 computeKnownBitsImpl(R: MI.getOperand(i: 1).getReg(), Known, DemandedElts,
666 Depth: Depth + 1);
667 computeKnownBitsImpl(R: MI.getOperand(i: 2).getReg(), Known&: KnownRHS, DemandedElts,
668 Depth: Depth + 1);
669 Known = KnownBits::smax(LHS: Known, RHS: KnownRHS);
670 break;
671 }
672 case TargetOpcode::G_UMIN: {
673 KnownBits KnownRHS;
674 computeKnownBitsImpl(R: MI.getOperand(i: 1).getReg(), Known, DemandedElts,
675 Depth: Depth + 1);
676 computeKnownBitsImpl(R: MI.getOperand(i: 2).getReg(), Known&: KnownRHS, DemandedElts,
677 Depth: Depth + 1);
678 Known = KnownBits::umin(LHS: Known, RHS: KnownRHS);
679 break;
680 }
681 case TargetOpcode::G_UMAX: {
682 KnownBits KnownRHS;
683 computeKnownBitsImpl(R: MI.getOperand(i: 1).getReg(), Known, DemandedElts,
684 Depth: Depth + 1);
685 computeKnownBitsImpl(R: MI.getOperand(i: 2).getReg(), Known&: KnownRHS, DemandedElts,
686 Depth: Depth + 1);
687 Known = KnownBits::umax(LHS: Known, RHS: KnownRHS);
688 break;
689 }
690 case TargetOpcode::G_FCMP:
691 case TargetOpcode::G_ICMP: {
692 if (DstTy.isVector())
693 break;
694 if (TL.getBooleanContents(isVec: DstTy.isVector(),
695 isFloat: Opcode == TargetOpcode::G_FCMP) ==
696 TargetLowering::ZeroOrOneBooleanContent &&
697 BitWidth > 1)
698 Known.Zero.setBitsFrom(1);
699 break;
700 }
701 case TargetOpcode::G_SEXT: {
702 computeKnownBitsImpl(R: MI.getOperand(i: 1).getReg(), Known, DemandedElts,
703 Depth: Depth + 1);
704 // If the sign bit is known to be zero or one, then sext will extend
705 // it to the top bits, else it will just zext.
706 Known = Known.sext(BitWidth);
707 break;
708 }
709 case TargetOpcode::G_ASSERT_SEXT:
710 case TargetOpcode::G_SEXT_INREG: {
711 computeKnownBitsImpl(R: MI.getOperand(i: 1).getReg(), Known, DemandedElts,
712 Depth: Depth + 1);
713 Known = Known.sextInReg(SrcBitWidth: MI.getOperand(i: 2).getImm());
714 break;
715 }
716 case TargetOpcode::G_ANYEXT: {
717 computeKnownBitsImpl(R: MI.getOperand(i: 1).getReg(), Known, DemandedElts,
718 Depth: Depth + 1);
719 Known = Known.anyext(BitWidth);
720 break;
721 }
722 case TargetOpcode::G_LOAD: {
723 const MachineMemOperand *MMO = *MI.memoperands_begin();
724 KnownBits KnownRange(MMO->getMemoryType().getScalarSizeInBits());
725 if (const MDNode *Ranges = MMO->getRanges())
726 computeKnownBitsFromRangeMetadata(Ranges: *Ranges, Known&: KnownRange);
727 Known = KnownRange.anyext(BitWidth: Known.getBitWidth());
728 break;
729 }
730 case TargetOpcode::G_SEXTLOAD:
731 case TargetOpcode::G_ZEXTLOAD: {
732 if (DstTy.isVector())
733 break;
734 const MachineMemOperand *MMO = *MI.memoperands_begin();
735 KnownBits KnownRange(MMO->getMemoryType().getScalarSizeInBits());
736 if (const MDNode *Ranges = MMO->getRanges())
737 computeKnownBitsFromRangeMetadata(Ranges: *Ranges, Known&: KnownRange);
738 Known = Opcode == TargetOpcode::G_SEXTLOAD
739 ? KnownRange.sext(BitWidth: Known.getBitWidth())
740 : KnownRange.zext(BitWidth: Known.getBitWidth());
741 break;
742 }
743 case TargetOpcode::G_ASHR: {
744 KnownBits LHSKnown, RHSKnown;
745 computeKnownBitsImpl(R: MI.getOperand(i: 1).getReg(), Known&: LHSKnown, DemandedElts,
746 Depth: Depth + 1);
747 computeKnownBitsImpl(R: MI.getOperand(i: 2).getReg(), Known&: RHSKnown, DemandedElts,
748 Depth: Depth + 1);
749 Known = KnownBits::ashr(LHS: LHSKnown, RHS: RHSKnown);
750 break;
751 }
752 case TargetOpcode::G_LSHR: {
753 KnownBits LHSKnown, RHSKnown;
754 computeKnownBitsImpl(R: MI.getOperand(i: 1).getReg(), Known&: LHSKnown, DemandedElts,
755 Depth: Depth + 1);
756 computeKnownBitsImpl(R: MI.getOperand(i: 2).getReg(), Known&: RHSKnown, DemandedElts,
757 Depth: Depth + 1);
758 Known = KnownBits::lshr(LHS: LHSKnown, RHS: RHSKnown);
759 break;
760 }
761 case TargetOpcode::G_SHL: {
762 KnownBits LHSKnown, RHSKnown;
763 computeKnownBitsImpl(R: MI.getOperand(i: 1).getReg(), Known&: LHSKnown, DemandedElts,
764 Depth: Depth + 1);
765 computeKnownBitsImpl(R: MI.getOperand(i: 2).getReg(), Known&: RHSKnown, DemandedElts,
766 Depth: Depth + 1);
767 Known = KnownBits::shl(LHS: LHSKnown, RHS: RHSKnown);
768 break;
769 }
770 case TargetOpcode::G_ROTL:
771 case TargetOpcode::G_ROTR: {
772 auto MaybeAmtOp =
773 isConstantOrConstantSplatVector(Def: MI.getOperand(i: 2).getReg(), MRI);
774 if (!MaybeAmtOp)
775 break;
776
777 Register SrcReg = MI.getOperand(i: 1).getReg();
778 computeKnownBitsImpl(R: SrcReg, Known, DemandedElts, Depth: Depth + 1);
779
780 unsigned Amt = MaybeAmtOp->urem(RHS: BitWidth);
781
782 // Canonicalize to ROTR.
783 if (Opcode == TargetOpcode::G_ROTL)
784 Amt = BitWidth - Amt;
785
786 Known.Zero = Known.Zero.rotr(rotateAmt: Amt);
787 Known.One = Known.One.rotr(rotateAmt: Amt);
788 break;
789 }
790 case TargetOpcode::G_FSHL:
791 case TargetOpcode::G_FSHR: {
792 auto MaybeAmtOp =
793 isConstantOrConstantSplatVector(Def: MI.getOperand(i: 3).getReg(), MRI);
794 if (!MaybeAmtOp)
795 break;
796
797 const APInt Amt = *MaybeAmtOp;
798 computeKnownBitsImpl(R: MI.getOperand(i: 1).getReg(), Known, DemandedElts,
799 Depth: Depth + 1);
800 computeKnownBitsImpl(R: MI.getOperand(i: 2).getReg(), Known&: Known2, DemandedElts,
801 Depth: Depth + 1);
802 Known = Opcode == TargetOpcode::G_FSHL
803 ? KnownBits::fshl(LHS: Known, RHS: Known2, Amt)
804 : KnownBits::fshr(LHS: Known, RHS: Known2, Amt);
805 break;
806 }
807 case TargetOpcode::G_INTTOPTR:
808 case TargetOpcode::G_PTRTOINT:
809 if (DstTy.isVector())
810 break;
811 // Fall through and handle them the same as zext/trunc.
812 [[fallthrough]];
813 case TargetOpcode::G_ZEXT:
814 case TargetOpcode::G_TRUNC: {
815 Register SrcReg = MI.getOperand(i: 1).getReg();
816 computeKnownBitsImpl(R: SrcReg, Known, DemandedElts, Depth: Depth + 1);
817 Known = Known.zextOrTrunc(BitWidth);
818 break;
819 }
820 case TargetOpcode::G_TRUNC_SSAT_S: {
821 Register SrcReg = MI.getOperand(i: 1).getReg();
822 computeKnownBitsImpl(R: SrcReg, Known, DemandedElts, Depth: Depth + 1);
823 Known = Known.truncSSat(BitWidth);
824 break;
825 }
826 case TargetOpcode::G_TRUNC_SSAT_U: {
827 Register SrcReg = MI.getOperand(i: 1).getReg();
828 computeKnownBitsImpl(R: SrcReg, Known, DemandedElts, Depth: Depth + 1);
829 Known = Known.truncSSatU(BitWidth);
830 break;
831 }
832 case TargetOpcode::G_TRUNC_USAT_U: {
833 Register SrcReg = MI.getOperand(i: 1).getReg();
834 computeKnownBitsImpl(R: SrcReg, Known, DemandedElts, Depth: Depth + 1);
835 Known = Known.truncUSat(BitWidth);
836 break;
837 }
838 case TargetOpcode::G_ASSERT_ZEXT: {
839 Register SrcReg = MI.getOperand(i: 1).getReg();
840 computeKnownBitsImpl(R: SrcReg, Known, DemandedElts, Depth: Depth + 1);
841
842 unsigned SrcBitWidth = MI.getOperand(i: 2).getImm();
843 assert(SrcBitWidth && "SrcBitWidth can't be zero");
844 APInt InMask = APInt::getLowBitsSet(numBits: BitWidth, loBitsSet: SrcBitWidth);
845 Known.Zero |= (~InMask);
846 Known.One &= (~Known.Zero);
847 break;
848 }
849 case TargetOpcode::G_ASSERT_ALIGN: {
850 int64_t LogOfAlign = Log2_64(Value: MI.getOperand(i: 2).getImm());
851
852 // TODO: Should use maximum with source
853 // If a node is guaranteed to be aligned, set low zero bits accordingly as
854 // well as clearing one bits.
855 Known.Zero.setLowBits(LogOfAlign);
856 Known.One.clearLowBits(loBits: LogOfAlign);
857 break;
858 }
859 case TargetOpcode::G_MERGE_VALUES: {
860 unsigned NumOps = MI.getNumOperands();
861 unsigned OpSize = MRI.getType(Reg: MI.getOperand(i: 1).getReg()).getSizeInBits();
862
863 for (unsigned I = 0; I != NumOps - 1; ++I) {
864 KnownBits SrcOpKnown;
865 computeKnownBitsImpl(R: MI.getOperand(i: I + 1).getReg(), Known&: SrcOpKnown,
866 DemandedElts, Depth: Depth + 1);
867 Known.insertBits(SubBits: SrcOpKnown, BitPosition: I * OpSize);
868 }
869 break;
870 }
871 case TargetOpcode::G_UNMERGE_VALUES: {
872 unsigned NumOps = MI.getNumOperands();
873 Register SrcReg = MI.getOperand(i: NumOps - 1).getReg();
874 LLT SrcTy = MRI.getType(Reg: SrcReg);
875
876 if (SrcTy.isVector() && SrcTy.getScalarType() != DstTy.getScalarType())
877 return; // TODO: Handle vector->subelement unmerges
878
879 // Figure out the result operand index
880 unsigned DstIdx = MI.findRegisterDefOperandIdx(Reg: R, TRI: nullptr);
881
882 APInt SubDemandedElts = DemandedElts;
883 if (SrcTy.isVector()) {
884 unsigned DstLanes = DstTy.isVector() ? DstTy.getNumElements() : 1;
885 SubDemandedElts =
886 DemandedElts.zext(width: SrcTy.getNumElements()).shl(shiftAmt: DstIdx * DstLanes);
887 }
888
889 KnownBits SrcOpKnown;
890 computeKnownBitsImpl(R: SrcReg, Known&: SrcOpKnown, DemandedElts: SubDemandedElts, Depth: Depth + 1);
891
892 if (SrcTy.isVector())
893 Known = std::move(SrcOpKnown);
894 else
895 Known = SrcOpKnown.extractBits(NumBits: BitWidth, BitPosition: BitWidth * DstIdx);
896 break;
897 }
898 case TargetOpcode::G_BSWAP: {
899 Register SrcReg = MI.getOperand(i: 1).getReg();
900 computeKnownBitsImpl(R: SrcReg, Known, DemandedElts, Depth: Depth + 1);
901 Known = Known.byteSwap();
902 break;
903 }
904 case TargetOpcode::G_BITREVERSE: {
905 Register SrcReg = MI.getOperand(i: 1).getReg();
906 computeKnownBitsImpl(R: SrcReg, Known, DemandedElts, Depth: Depth + 1);
907 Known = Known.reverseBits();
908 break;
909 }
910 case TargetOpcode::G_CTPOP: {
911 computeKnownBitsImpl(R: MI.getOperand(i: 1).getReg(), Known&: Known2, DemandedElts,
912 Depth: Depth + 1);
913 // We can bound the space the count needs. Also, bits known to be zero
914 // can't contribute to the population.
915 unsigned BitsPossiblySet = Known2.countMaxPopulation();
916 unsigned LowBits = llvm::bit_width(Value: BitsPossiblySet);
917 Known.Zero.setBitsFrom(LowBits);
918 // TODO: we could bound Known.One using the lower bound on the number of
919 // bits which might be set provided by popcnt KnownOne2.
920 break;
921 }
922 case TargetOpcode::G_UBFX: {
923 KnownBits SrcOpKnown, OffsetKnown, WidthKnown;
924 computeKnownBitsImpl(R: MI.getOperand(i: 1).getReg(), Known&: SrcOpKnown, DemandedElts,
925 Depth: Depth + 1);
926 computeKnownBitsImpl(R: MI.getOperand(i: 2).getReg(), Known&: OffsetKnown, DemandedElts,
927 Depth: Depth + 1);
928 computeKnownBitsImpl(R: MI.getOperand(i: 3).getReg(), Known&: WidthKnown, DemandedElts,
929 Depth: Depth + 1);
930 Known = extractBits(BitWidth, SrcOpKnown, OffsetKnown, WidthKnown);
931 break;
932 }
933 case TargetOpcode::G_SBFX: {
934 KnownBits SrcOpKnown, OffsetKnown, WidthKnown;
935 computeKnownBitsImpl(R: MI.getOperand(i: 1).getReg(), Known&: SrcOpKnown, DemandedElts,
936 Depth: Depth + 1);
937 computeKnownBitsImpl(R: MI.getOperand(i: 2).getReg(), Known&: OffsetKnown, DemandedElts,
938 Depth: Depth + 1);
939 computeKnownBitsImpl(R: MI.getOperand(i: 3).getReg(), Known&: WidthKnown, DemandedElts,
940 Depth: Depth + 1);
941 // The offset and width are unsigned and can have a different type than the
942 // source. extractBits reads both as unsigned values of any width. The
943 // width is also used below in a subtraction of BitWidth type. A valid width
944 // is at most BitWidth, so it fits in BitWidth bits.
945 WidthKnown = WidthKnown.zextOrTrunc(BitWidth);
946 Known = extractBits(BitWidth, SrcOpKnown, OffsetKnown, WidthKnown);
947 // Sign extend the extracted value using shift left and arithmetic shift
948 // right.
949 KnownBits ExtKnown = KnownBits::makeConstant(C: APInt(BitWidth, BitWidth));
950 KnownBits ShiftKnown = KnownBits::sub(LHS: ExtKnown, RHS: WidthKnown);
951 Known = KnownBits::ashr(LHS: KnownBits::shl(LHS: Known, RHS: ShiftKnown), RHS: ShiftKnown);
952 break;
953 }
954 case TargetOpcode::G_UADDO:
955 case TargetOpcode::G_UADDE:
956 case TargetOpcode::G_SADDO:
957 case TargetOpcode::G_SADDE: {
958 if (MI.getOperand(i: 1).getReg() == R) {
959 // If we know the result of a compare has the top bits zero, use this
960 // info.
961 if (TL.getBooleanContents(isVec: DstTy.isVector(), isFloat: false) ==
962 TargetLowering::ZeroOrOneBooleanContent &&
963 BitWidth > 1)
964 Known.Zero.setBitsFrom(1);
965 break;
966 }
967
968 assert(MI.getOperand(0).getReg() == R &&
969 "We only compute knownbits for the sum here.");
970 // With [US]ADDE, a carry bit may be added in.
971 KnownBits Carry(1);
972 if (Opcode == TargetOpcode::G_UADDE || Opcode == TargetOpcode::G_SADDE) {
973 computeKnownBitsImpl(R: MI.getOperand(i: 4).getReg(), Known&: Carry, DemandedElts,
974 Depth: Depth + 1);
975 // Carry has bit width 1
976 Carry = Carry.trunc(BitWidth: 1);
977 } else {
978 Carry.setAllZero();
979 }
980
981 computeKnownBitsImpl(R: MI.getOperand(i: 2).getReg(), Known, DemandedElts,
982 Depth: Depth + 1);
983 computeKnownBitsImpl(R: MI.getOperand(i: 3).getReg(), Known&: Known2, DemandedElts,
984 Depth: Depth + 1);
985 Known = KnownBits::computeForAddCarry(LHS: Known, RHS: Known2, Carry);
986 break;
987 }
988 case TargetOpcode::G_USUBO:
989 case TargetOpcode::G_USUBE:
990 case TargetOpcode::G_SSUBO:
991 case TargetOpcode::G_SSUBE:
992 case TargetOpcode::G_UMULO:
993 case TargetOpcode::G_SMULO: {
994 if (MI.getOperand(i: 1).getReg() == R) {
995 // If we know the result of a compare has the top bits zero, use this
996 // info.
997 if (TL.getBooleanContents(isVec: DstTy.isVector(), isFloat: false) ==
998 TargetLowering::ZeroOrOneBooleanContent &&
999 BitWidth > 1)
1000 Known.Zero.setBitsFrom(1);
1001 }
1002 break;
1003 }
1004 case TargetOpcode::G_CTTZ:
1005 case TargetOpcode::G_CTTZ_ZERO_POISON: {
1006 KnownBits SrcOpKnown;
1007 computeKnownBitsImpl(R: MI.getOperand(i: 1).getReg(), Known&: SrcOpKnown, DemandedElts,
1008 Depth: Depth + 1);
1009 // If we have a known 1, its position is our upper bound
1010 unsigned PossibleTZ = SrcOpKnown.countMaxTrailingZeros();
1011 unsigned LowBits = llvm::bit_width(Value: PossibleTZ);
1012 Known.Zero.setBitsFrom(LowBits);
1013 break;
1014 }
1015 case TargetOpcode::G_CTLZ:
1016 case TargetOpcode::G_CTLZ_ZERO_POISON: {
1017 KnownBits SrcOpKnown;
1018 computeKnownBitsImpl(R: MI.getOperand(i: 1).getReg(), Known&: SrcOpKnown, DemandedElts,
1019 Depth: Depth + 1);
1020 // If we have a known 1, its position is our upper bound.
1021 unsigned PossibleLZ = SrcOpKnown.countMaxLeadingZeros();
1022 unsigned LowBits = llvm::bit_width(Value: PossibleLZ);
1023 Known.Zero.setBitsFrom(LowBits);
1024 break;
1025 }
1026 case TargetOpcode::G_CTLS: {
1027 Register Reg = MI.getOperand(i: 1).getReg();
1028 unsigned MinRedundantSignBits =
1029 computeNumSignBits(R: Reg, DemandedElts, Depth: Depth + 1) - 1;
1030
1031 unsigned MaxUpperRedundantSignBits = MRI.getType(Reg).getScalarSizeInBits();
1032
1033 ConstantRange Range(APInt(BitWidth, MinRedundantSignBits),
1034 APInt(BitWidth, MaxUpperRedundantSignBits));
1035
1036 Known = Range.toKnownBits();
1037 break;
1038 }
1039 case TargetOpcode::G_EXTRACT_VECTOR_ELT: {
1040 GExtractVectorElement &Extract = cast<GExtractVectorElement>(Val&: MI);
1041 Register InVec = Extract.getVectorReg();
1042 Register EltNo = Extract.getIndexReg();
1043
1044 auto ConstEltNo = getIConstantVRegVal(VReg: EltNo, MRI);
1045
1046 LLT VecVT = MRI.getType(Reg: InVec);
1047 // computeKnownBits not yet implemented for scalable vectors.
1048 if (VecVT.isScalableVector())
1049 break;
1050
1051 const unsigned EltBitWidth = VecVT.getScalarSizeInBits();
1052 const unsigned NumSrcElts = VecVT.getNumElements();
1053 // A return type different from the vector's element type may lead to
1054 // issues with pattern selection. Bail out to avoid that.
1055 if (BitWidth > EltBitWidth)
1056 break;
1057
1058 Known.Zero.setAllBits();
1059 Known.One.setAllBits();
1060
1061 // If we know the element index, just demand that vector element, else for
1062 // an unknown element index, ignore DemandedElts and demand them all.
1063 APInt DemandedSrcElts = APInt::getAllOnes(numBits: NumSrcElts);
1064 if (ConstEltNo && ConstEltNo->ult(RHS: NumSrcElts))
1065 DemandedSrcElts =
1066 APInt::getOneBitSet(numBits: NumSrcElts, BitNo: ConstEltNo->getZExtValue());
1067
1068 computeKnownBitsImpl(R: InVec, Known, DemandedElts: DemandedSrcElts, Depth: Depth + 1);
1069 break;
1070 }
1071 case TargetOpcode::G_INSERT_VECTOR_ELT: {
1072 GInsertVectorElement &Insert = cast<GInsertVectorElement>(Val&: MI);
1073 Register InVec = Insert.getVectorReg();
1074 Register InVal = Insert.getElementReg();
1075 Register EltNo = Insert.getIndexReg();
1076 LLT VecVT = MRI.getType(Reg: InVec);
1077
1078 if (VecVT.isScalableVector())
1079 break;
1080
1081 auto ConstEltNo = getIConstantVRegVal(VReg: EltNo, MRI);
1082 unsigned NumElts = VecVT.getNumElements();
1083
1084 bool DemandedVal = true;
1085 APInt DemandedVecElts = DemandedElts;
1086 if (ConstEltNo && ConstEltNo->ult(RHS: NumElts)) {
1087 unsigned EltIdx = ConstEltNo->getZExtValue();
1088 DemandedVal = !!DemandedElts[EltIdx];
1089 DemandedVecElts.clearBit(BitPosition: EltIdx);
1090 }
1091 Known.setAllConflict();
1092 if (DemandedVal) {
1093 computeKnownBitsImpl(R: InVal, Known&: Known2, DemandedElts: APInt(1, 1), Depth: Depth + 1);
1094 Known = Known.intersectWith(RHS: Known2.zextOrTrunc(BitWidth));
1095 }
1096 if (!!DemandedVecElts) {
1097 computeKnownBitsImpl(R: InVec, Known&: Known2, DemandedElts: DemandedVecElts, Depth: Depth + 1);
1098 Known = Known.intersectWith(RHS: Known2);
1099 }
1100 break;
1101 }
1102 case TargetOpcode::G_INSERT_SUBVECTOR: {
1103 GInsertSubvector &Insert = cast<GInsertSubvector>(Val&: MI);
1104 Register Src = Insert.getBigVec();
1105 Register Sub = Insert.getSubVec();
1106 uint64_t Idx = Insert.getIndexImm();
1107 LLT SrcTy = MRI.getType(Reg: Src);
1108 LLT SubTy = MRI.getType(Reg: Sub);
1109 APInt DemandedSubElts;
1110 APInt DemandedSrcElts;
1111
1112 if (SrcTy.isScalableVector()) {
1113 DemandedSubElts = SubTy.isScalableVector()
1114 ? APInt(1, 1)
1115 : APInt::getAllOnes(numBits: SubTy.getNumElements());
1116 DemandedSrcElts = APInt(1, 1);
1117 } else {
1118 unsigned NumSubElts = SubTy.getNumElements();
1119 DemandedSubElts = DemandedElts.extractBits(numBits: NumSubElts, bitPosition: Idx);
1120 DemandedSrcElts = DemandedElts;
1121 DemandedSrcElts.clearBits(LoBit: Idx, HiBit: Idx + NumSubElts);
1122 }
1123
1124 Known.setAllConflict();
1125 if (!!DemandedSubElts) {
1126 computeKnownBitsImpl(R: Sub, Known&: Known2, DemandedElts: DemandedSubElts, Depth: Depth + 1);
1127 Known = Known.intersectWith(RHS: Known2);
1128 if (Known.isUnknown())
1129 break;
1130 }
1131
1132 if (!!DemandedSrcElts) {
1133 computeKnownBitsImpl(R: Src, Known&: Known2, DemandedElts: DemandedSrcElts, Depth: Depth + 1);
1134 Known = Known.intersectWith(RHS: Known2);
1135 }
1136
1137 break;
1138 }
1139 case TargetOpcode::G_EXTRACT_SUBVECTOR: {
1140 Register SrcReg = MI.getOperand(i: 1).getReg();
1141 LLT SrcTy = MRI.getType(Reg: SrcReg);
1142 APInt DemandedSrcElts;
1143 if (SrcTy.isScalableVector()) {
1144 DemandedSrcElts = APInt(1, 1);
1145 } else {
1146 uint64_t Idx = MI.getOperand(i: 2).getImm();
1147 unsigned NumSrcElts = SrcTy.getNumElements();
1148 DemandedSrcElts = DemandedElts.zext(width: NumSrcElts).shl(shiftAmt: Idx);
1149 }
1150 computeKnownBitsImpl(R: SrcReg, Known, DemandedElts: DemandedSrcElts, Depth: Depth + 1);
1151 break;
1152 }
1153 case TargetOpcode::G_SHUFFLE_VECTOR: {
1154 APInt DemandedLHS, DemandedRHS;
1155 // Collect the known bits that are shared by every vector element referenced
1156 // by the shuffle.
1157 unsigned NumElts = MRI.getType(Reg: MI.getOperand(i: 1).getReg()).getNumElements();
1158 if (!getShuffleDemandedElts(SrcWidth: NumElts, Mask: MI.getOperand(i: 3).getShuffleMask(),
1159 DemandedElts, DemandedLHS, DemandedRHS))
1160 break;
1161
1162 // Known bits are the values that are shared by every demanded element.
1163 Known.Zero.setAllBits();
1164 Known.One.setAllBits();
1165 if (!!DemandedLHS) {
1166 computeKnownBitsImpl(R: MI.getOperand(i: 1).getReg(), Known&: Known2, DemandedElts: DemandedLHS,
1167 Depth: Depth + 1);
1168 Known = Known.intersectWith(RHS: Known2);
1169 }
1170 // If we don't know any bits, early out.
1171 if (Known.isUnknown())
1172 break;
1173 if (!!DemandedRHS) {
1174 computeKnownBitsImpl(R: MI.getOperand(i: 2).getReg(), Known&: Known2, DemandedElts: DemandedRHS,
1175 Depth: Depth + 1);
1176 Known = Known.intersectWith(RHS: Known2);
1177 }
1178 break;
1179 }
1180 case TargetOpcode::G_CONCAT_VECTORS: {
1181 if (MRI.getType(Reg: MI.getOperand(i: 0).getReg()).isScalableVector())
1182 break;
1183 // Split DemandedElts and test each of the demanded subvectors.
1184 Known.Zero.setAllBits();
1185 Known.One.setAllBits();
1186 unsigned NumSubVectorElts =
1187 MRI.getType(Reg: MI.getOperand(i: 1).getReg()).getNumElements();
1188
1189 for (const auto &[I, MO] : enumerate(First: drop_begin(RangeOrContainer: MI.operands()))) {
1190 APInt DemandedSub =
1191 DemandedElts.extractBits(numBits: NumSubVectorElts, bitPosition: I * NumSubVectorElts);
1192 if (!!DemandedSub) {
1193 computeKnownBitsImpl(R: MO.getReg(), Known&: Known2, DemandedElts: DemandedSub, Depth: Depth + 1);
1194
1195 Known = Known.intersectWith(RHS: Known2);
1196 }
1197 // If we don't know any bits, early out.
1198 if (Known.isUnknown())
1199 break;
1200 }
1201 break;
1202 }
1203 case TargetOpcode::G_VECTOR_COMPRESS: {
1204 // Each result lane is either a lane of the source vector or the passthru,
1205 // so the known bits are those shared by both.
1206 Register Vec = MI.getOperand(i: 1).getReg();
1207 Register PassThru = MI.getOperand(i: 3).getReg();
1208 computeKnownBitsImpl(R: PassThru, Known, DemandedElts, Depth: Depth + 1);
1209 // If we don't know any bits, early out.
1210 if (Known.isUnknown())
1211 break;
1212 // Compression can move any source lane to any result position, so all
1213 // source lanes are demanded.
1214 APInt DemandedSrcElts = APInt::getAllOnes(numBits: DemandedElts.getBitWidth());
1215 computeKnownBitsImpl(R: Vec, Known&: Known2, DemandedElts: DemandedSrcElts, Depth: Depth + 1);
1216 Known = Known.intersectWith(RHS: Known2);
1217 break;
1218 }
1219 case TargetOpcode::G_ABS: {
1220 Register SrcReg = MI.getOperand(i: 1).getReg();
1221 computeKnownBitsImpl(R: SrcReg, Known, DemandedElts, Depth: Depth + 1);
1222 Known = Known.abs();
1223 Known.Zero.setHighBits(computeNumSignBits(R: SrcReg, DemandedElts, Depth: Depth + 1) -
1224 1);
1225 break;
1226 }
1227 }
1228
1229 LLVM_DEBUG(dumpResult(MI, Known, Depth));
1230}
1231
1232static void genUnknown(MachineRegisterInfo &MRI, Register Reg,
1233 KnownBits &Known) {
1234 LLT Ty = MRI.getType(Reg);
1235 if (!Ty.isValid()) {
1236 Known = KnownBits();
1237 return;
1238 }
1239 unsigned BitWidth = Ty.getScalarSizeInBits();
1240 Known = KnownBits(BitWidth);
1241}
1242
1243/// Evaluate a known-bits query with an explicit worklist instead of recursive
1244/// descent.
1245void GISelValueTracking::computeKnownBitsImpl(Register R, KnownBits &Known,
1246 const APInt &DemandedElts,
1247 unsigned Depth) {
1248 // Nested queries only consult the per-query cache. If the result is not
1249 // available yet, enqueue the request and return an unknown placeholder.
1250 if (!Stack.empty()) {
1251 if (!getKnownBitsResult(Reg: R, DemandedElts, Depth, Known)) {
1252 Stack.push_back(Elt: {R, DemandedElts, Depth});
1253 genUnknown(MRI, Reg: R, Known);
1254 }
1255 return;
1256 }
1257
1258 // Top-level queries drive evaluation iteratively until every queued item has
1259 // either been computed or found in the cache.
1260 Stack.push_back(Elt: {R, DemandedElts, Depth});
1261 while (!Stack.empty()) {
1262 WorkItem Item = Stack.back();
1263 size_t StackSize = Stack.size();
1264 Register ItemReg = std::get<0>(t&: Item);
1265 const APInt &ItemDemandedElts = std::get<1>(t&: Item);
1266 const unsigned ItemDepth = std::get<2>(t&: Item);
1267 KnownBits ItemKnown;
1268
1269 if (getKnownBitsResult(Reg: ItemReg, DemandedElts: ItemDemandedElts, Depth: ItemDepth, Known&: ItemKnown)) {
1270 Stack.pop_back();
1271 continue;
1272 }
1273
1274 // Evaluate this item with the per-instruction known-bits logic. Dependent
1275 // queries issued from there re-enter this worklist driver and take the
1276 // nested-query path to enqueue more work.
1277 computeKnownBits(R: ItemReg, Known&: ItemKnown, DemandedElts: ItemDemandedElts, Depth: ItemDepth);
1278
1279 // If evaluating this item did not queue more work, its dependencies are
1280 // resolved and the result can be memoized immediately.
1281 if (Stack.size() == StackSize) {
1282 assert((std::get<0>(Stack.back()) == ItemReg &&
1283 std::get<1>(Stack.back()) == ItemDemandedElts &&
1284 std::get<2>(Stack.back()) == ItemDepth) &&
1285 "The item we just evaluated must still be the top one.");
1286
1287 setKnownBitsResult(Reg: ItemReg, DemandedElts: ItemDemandedElts, Depth: ItemDepth, Known: ItemKnown);
1288 Stack.pop_back();
1289 }
1290 }
1291
1292 // The original query must have been computed by the time the worklist is
1293 // drained.
1294 if (!getKnownBitsResult(Reg: R, DemandedElts, Depth, Known))
1295 llvm_unreachable(
1296 "Top level query must be in `results` after iteration is complete.");
1297
1298 Results.clear();
1299}
1300
1301void GISelValueTracking::computeKnownFPClass(Register R, KnownFPClass &Known,
1302 FPClassTest InterestedClasses,
1303 unsigned Depth) {
1304 LLT Ty = MRI.getType(Reg: R);
1305 APInt DemandedElts =
1306 Ty.isFixedVector() ? APInt::getAllOnes(numBits: Ty.getNumElements()) : APInt(1, 1);
1307 computeKnownFPClass(R, DemandedElts, InterestedClasses, Known, Depth);
1308}
1309
1310/// Return true if this value is known to be the fractional part x - floor(x),
1311/// which lies in [0, 1). This implies the value cannot introduce overflow in a
1312/// fmul when the other operand is known finite.
1313static bool isAbsoluteValueULEOne(Register R, const MachineRegisterInfo &MRI) {
1314 using namespace MIPatternMatch;
1315 Register SubX;
1316 return mi_match(R, MRI, P: m_GFSub(L: m_Reg(R&: SubX), R: m_GFFloor(Src: m_DeferredReg(R&: SubX))));
1317}
1318
1319void GISelValueTracking::computeKnownFPClassForFPTrunc(
1320 const MachineInstr &MI, const APInt &DemandedElts,
1321 FPClassTest InterestedClasses, KnownFPClass &Known, unsigned Depth) {
1322 if ((InterestedClasses & (KnownFPClass::OrderedLessThanZeroMask | fcNan)) ==
1323 fcNone)
1324 return;
1325
1326 Register Val = MI.getOperand(i: 1).getReg();
1327 KnownFPClass KnownSrc;
1328 computeKnownFPClass(R: Val, DemandedElts, InterestedClasses, Known&: KnownSrc,
1329 Depth: Depth + 1);
1330
1331 const fltSemantics &DstSem = getFltSemanticForLLT(
1332 Ty: MRI.getType(Reg: MI.getOperand(i: 0).getReg()).getScalarType());
1333 const fltSemantics &SrcSem =
1334 getFltSemanticForLLT(Ty: MRI.getType(Reg: Val).getScalarType());
1335
1336 Known = KnownFPClass::fptrunc(KnownSrc, DstTy: DstSem, SrcTy: SrcSem,
1337 DstMode: MF.getDenormalMode(FPType: DstSem),
1338 SrcMode: MF.getDenormalMode(FPType: SrcSem));
1339}
1340
1341void GISelValueTracking::computeKnownFPClass(Register R,
1342 const APInt &DemandedElts,
1343 FPClassTest InterestedClasses,
1344 KnownFPClass &Known,
1345 unsigned Depth) {
1346 assert(Known.isUnknown() && "should not be called with known information");
1347
1348 if (!DemandedElts) {
1349 // No demanded elts, better to assume we don't know anything.
1350 Known.resetAll();
1351 return;
1352 }
1353
1354 assert(Depth <= MaxAnalysisRecursionDepth && "Limit Search Depth");
1355
1356 MachineInstr &MI = *MRI.getVRegDef(Reg: R);
1357 unsigned Opcode = MI.getOpcode();
1358 LLT DstTy = MRI.getType(Reg: R);
1359
1360 if (!DstTy.isValid()) {
1361 Known.resetAll();
1362 return;
1363 }
1364
1365 if (auto Cst = GFConstant::getConstant(Const: R, MRI)) {
1366 switch (Cst->getKind()) {
1367 case GFConstant::GFConstantKind::Scalar: {
1368 Known = KnownFPClass(Cst->getScalarValue());
1369 break;
1370 }
1371 case GFConstant::GFConstantKind::FixedVector: {
1372 Known = KnownFPClass::getEmpty();
1373
1374 for (const APFloat &C : *Cst)
1375 Known |= KnownFPClass(C);
1376
1377 break;
1378 }
1379 case GFConstant::GFConstantKind::ScalableVector: {
1380 Known.resetAll();
1381 break;
1382 }
1383 }
1384
1385 return;
1386 }
1387
1388 FPClassTest KnownNotFromFlags = fcNone;
1389 if (MI.getFlag(Flag: MachineInstr::MIFlag::FmNoNans))
1390 KnownNotFromFlags |= fcNan;
1391 if (MI.getFlag(Flag: MachineInstr::MIFlag::FmNoInfs))
1392 KnownNotFromFlags |= fcInf;
1393
1394 // We no longer need to find out about these bits from inputs if we can
1395 // assume this from flags/attributes.
1396 InterestedClasses &= ~KnownNotFromFlags;
1397
1398 llvm::scope_exit ClearClassesFromFlags(
1399 [=, &Known] { Known.knownNot(RuleOut: KnownNotFromFlags); });
1400
1401 // All recursive calls that increase depth must come after this.
1402 if (Depth == MaxAnalysisRecursionDepth)
1403 return;
1404
1405 const MachineFunction *MF = MI.getMF();
1406
1407 switch (Opcode) {
1408 default:
1409 TL.computeKnownFPClassForTargetInstr(Analysis&: *this, R, Known, DemandedElts, MRI,
1410 Depth);
1411 break;
1412 case TargetOpcode::G_FNEG: {
1413 Register Val = MI.getOperand(i: 1).getReg();
1414 computeKnownFPClass(R: Val, DemandedElts, InterestedClasses, Known, Depth: Depth + 1);
1415 Known.fneg();
1416 break;
1417 }
1418 case TargetOpcode::G_SELECT: {
1419 GSelect &SelMI = cast<GSelect>(Val&: MI);
1420 Register Cond = SelMI.getCondReg();
1421 Register LHS = SelMI.getTrueReg();
1422 Register RHS = SelMI.getFalseReg();
1423
1424 FPClassTest FilterLHS = fcAllFlags;
1425 FPClassTest FilterRHS = fcAllFlags;
1426
1427 Register TestedValue;
1428 FPClassTest MaskIfTrue = fcAllFlags;
1429 FPClassTest MaskIfFalse = fcAllFlags;
1430 FPClassTest ClassVal = fcNone;
1431
1432 CmpInst::Predicate Pred;
1433 Register CmpLHS, CmpRHS;
1434 if (mi_match(R: Cond, MRI,
1435 P: m_GFCmp(P: m_Pred(P&: Pred), L: m_Reg(R&: CmpLHS), R: m_Reg(R&: CmpRHS)))) {
1436 // If the select filters out a value based on the class, it no longer
1437 // participates in the class of the result
1438
1439 // TODO: In some degenerate cases we can infer something if we try again
1440 // without looking through sign operations.
1441 bool LookThroughFAbsFNeg = CmpLHS != LHS && CmpLHS != RHS;
1442 std::tie(args&: TestedValue, args&: MaskIfTrue, args&: MaskIfFalse) =
1443 fcmpImpliesClass(Pred, MF: *MF, LHS: CmpLHS, RHS: CmpRHS, LookThroughSrc: LookThroughFAbsFNeg);
1444 } else if (mi_match(
1445 R: Cond, MRI,
1446 P: m_GIsFPClass(L: m_Reg(R&: TestedValue), T: m_FPClassTest(T&: ClassVal)))) {
1447 FPClassTest TestedMask = ClassVal;
1448 MaskIfTrue = TestedMask;
1449 MaskIfFalse = ~TestedMask;
1450 }
1451
1452 if (TestedValue == LHS) {
1453 // match !isnan(x) ? x : y
1454 FilterLHS = MaskIfTrue;
1455 } else if (TestedValue == RHS) { // && IsExactClass
1456 // match !isnan(x) ? y : x
1457 FilterRHS = MaskIfFalse;
1458 }
1459
1460 KnownFPClass Known2;
1461 computeKnownFPClass(R: LHS, DemandedElts, InterestedClasses: InterestedClasses & FilterLHS, Known,
1462 Depth: Depth + 1);
1463 Known.setKnownFPClasses(Known.getKnownFPClasses() & FilterLHS);
1464
1465 computeKnownFPClass(R: RHS, DemandedElts, InterestedClasses: InterestedClasses & FilterRHS,
1466 Known&: Known2, Depth: Depth + 1);
1467 Known2.setKnownFPClasses(Known2.getKnownFPClasses() & FilterRHS);
1468
1469 Known |= Known2;
1470 break;
1471 }
1472 case TargetOpcode::G_FCOPYSIGN: {
1473 Register Magnitude = MI.getOperand(i: 1).getReg();
1474 Register Sign = MI.getOperand(i: 2).getReg();
1475
1476 KnownFPClass KnownSign;
1477
1478 computeKnownFPClass(R: Magnitude, DemandedElts, InterestedClasses, Known,
1479 Depth: Depth + 1);
1480 computeKnownFPClass(R: Sign, DemandedElts, InterestedClasses, Known&: KnownSign,
1481 Depth: Depth + 1);
1482 Known.copysign(Sign: KnownSign);
1483 break;
1484 }
1485 case TargetOpcode::G_FMA:
1486 case TargetOpcode::G_FMAD: {
1487 if ((InterestedClasses & (fcNegative | fcNan)) == fcNone)
1488 break;
1489
1490 const bool IsFMA = Opcode == TargetOpcode::G_FMA;
1491
1492 Register A = MI.getOperand(i: 1).getReg();
1493 Register B = MI.getOperand(i: 2).getReg();
1494 Register C = MI.getOperand(i: 3).getReg();
1495
1496 DenormalMode Mode =
1497 MF->getDenormalMode(FPType: getFltSemanticForLLT(Ty: DstTy.getScalarType()));
1498
1499 if (A == B && isGuaranteedNotToBeUndef(Reg: A, MRI, Depth: Depth + 1)) {
1500 FPClassTest InterestedSquared = InterestedClasses;
1501 FPClassTest InterestedAddend = InterestedClasses;
1502 // Only fma(+inf, +inf, -inf) and fma(-inf, -inf, -inf) produce NaN when
1503 // squaring.
1504 if (InterestedClasses & fcQNan) {
1505 InterestedSquared |= fcSNan | fcInf;
1506 InterestedAddend |= fcSNan | fcNegInf;
1507 }
1508
1509 KnownFPClass KnownSrc, KnownAddend;
1510 computeKnownFPClass(R: C, DemandedElts, InterestedClasses: InterestedAddend, Known&: KnownAddend,
1511 Depth: Depth + 1);
1512 computeKnownFPClass(R: A, DemandedElts, InterestedClasses: InterestedSquared, Known&: KnownSrc,
1513 Depth: Depth + 1);
1514 if (KnownNotFromFlags) {
1515 KnownSrc.knownNot(RuleOut: KnownNotFromFlags);
1516 KnownAddend.knownNot(RuleOut: KnownNotFromFlags);
1517 }
1518 Known = IsFMA ? KnownFPClass::fma_square(Squared: KnownSrc, Addend: KnownAddend, Mode)
1519 : KnownFPClass::fmuladd_square(Squared: KnownSrc, Addend: KnownAddend, Mode);
1520 } else {
1521 KnownFPClass KnownSrc[3];
1522 computeKnownFPClass(R: A, DemandedElts, InterestedClasses, Known&: KnownSrc[0],
1523 Depth: Depth + 1);
1524 if (KnownSrc[0].isUnknown())
1525 break;
1526 computeKnownFPClass(R: B, DemandedElts, InterestedClasses, Known&: KnownSrc[1],
1527 Depth: Depth + 1);
1528 if (KnownSrc[1].isUnknown())
1529 break;
1530 computeKnownFPClass(R: C, DemandedElts, InterestedClasses, Known&: KnownSrc[2],
1531 Depth: Depth + 1);
1532 if (KnownSrc[2].isUnknown())
1533 break;
1534 if (KnownNotFromFlags) {
1535 KnownSrc[0].knownNot(RuleOut: KnownNotFromFlags);
1536 KnownSrc[1].knownNot(RuleOut: KnownNotFromFlags);
1537 KnownSrc[2].knownNot(RuleOut: KnownNotFromFlags);
1538 }
1539 Known =
1540 IsFMA ? KnownFPClass::fma(LHS: KnownSrc[0], RHS: KnownSrc[1], Addend: KnownSrc[2], Mode)
1541 : KnownFPClass::fmuladd(LHS: KnownSrc[0], RHS: KnownSrc[1], Addend: KnownSrc[2],
1542 Mode);
1543 }
1544 break;
1545 }
1546 case TargetOpcode::G_FSQRT:
1547 case TargetOpcode::G_STRICT_FSQRT: {
1548 KnownFPClass KnownSrc;
1549 FPClassTest InterestedSrcs = InterestedClasses;
1550 if (InterestedClasses & fcQNan)
1551 InterestedSrcs |= KnownFPClass::OrderedLessThanZeroMask | fcSNan;
1552 // Subnormals may flush to zero.
1553 if (InterestedClasses & fcZero)
1554 InterestedSrcs |= fcSubnormal;
1555
1556 Register Val = MI.getOperand(i: 1).getReg();
1557 computeKnownFPClass(R: Val, DemandedElts, InterestedClasses: InterestedSrcs, Known&: KnownSrc, Depth: Depth + 1);
1558
1559 DenormalMode Mode =
1560 MF->getDenormalMode(FPType: getFltSemanticForLLT(Ty: DstTy.getScalarType()));
1561 Known = KnownFPClass::sqrt(Src: KnownSrc, Mode);
1562 if (MI.getFlag(Flag: MachineInstr::MIFlag::FmNsz))
1563 Known.knownNot(RuleOut: fcNegZero);
1564 break;
1565 }
1566 case TargetOpcode::G_FABS: {
1567 if ((InterestedClasses & (fcNan | fcPositive)) != fcNone) {
1568 Register Val = MI.getOperand(i: 1).getReg();
1569 // If we only care about the sign bit we don't need to inspect the
1570 // operand.
1571 computeKnownFPClass(R: Val, DemandedElts, InterestedClasses, Known,
1572 Depth: Depth + 1);
1573 }
1574 Known.fabs();
1575 break;
1576 }
1577 case TargetOpcode::G_FATAN2: {
1578 FPClassTest InterestedY = InterestedClasses;
1579 FPClassTest InterestedX = InterestedClasses;
1580
1581 // We can rule out negative values if y cannot have a negative value.
1582 if ((InterestedClasses & fcNegFinite) != fcNone)
1583 InterestedY |= fcNegative;
1584
1585 // We can rule out positive values if y cannot have a positive value.
1586 if ((InterestedClasses & fcPosFinite) != fcNone)
1587 InterestedY |= fcPositive | fcNegSubnormal;
1588
1589 // We can rule out zero and subnormal if x cannot have a positive value.
1590 if ((InterestedClasses & (fcZero | fcSubnormal)) != fcNone)
1591 InterestedX |= fcPositive | fcNegSubnormal;
1592
1593 Register Y = MI.getOperand(i: 1).getReg();
1594 Register X = MI.getOperand(i: 2).getReg();
1595 KnownFPClass KnownY, KnownX;
1596 computeKnownFPClass(R: Y, DemandedElts, InterestedClasses: InterestedY, Known&: KnownY, Depth: Depth + 1);
1597 computeKnownFPClass(R: X, DemandedElts, InterestedClasses: InterestedX, Known&: KnownX, Depth: Depth + 1);
1598 DenormalMode Mode =
1599 MF->getDenormalMode(FPType: getFltSemanticForLLT(Ty: DstTy.getScalarType()));
1600 Known = KnownFPClass::atan2(LHS: KnownY, RHS: KnownX, Mode);
1601 break;
1602 }
1603 case TargetOpcode::G_FSINH: {
1604 Register Val = MI.getOperand(i: 1).getReg();
1605 KnownFPClass KnownSrc;
1606 computeKnownFPClass(R: Val, DemandedElts, InterestedClasses, Known&: KnownSrc,
1607 Depth: Depth + 1);
1608 Known = KnownFPClass::sinh(Src: KnownSrc);
1609 break;
1610 }
1611 case TargetOpcode::G_FCOSH: {
1612 Register Val = MI.getOperand(i: 1).getReg();
1613 KnownFPClass KnownSrc;
1614 computeKnownFPClass(R: Val, DemandedElts, InterestedClasses, Known&: KnownSrc,
1615 Depth: Depth + 1);
1616 Known = KnownFPClass::cosh(Src: KnownSrc);
1617 break;
1618 }
1619 case TargetOpcode::G_FTANH: {
1620 Register Val = MI.getOperand(i: 1).getReg();
1621 KnownFPClass KnownSrc;
1622 computeKnownFPClass(R: Val, DemandedElts, InterestedClasses, Known&: KnownSrc,
1623 Depth: Depth + 1);
1624 Known = KnownFPClass::tanh(Src: KnownSrc);
1625 break;
1626 }
1627 case TargetOpcode::G_FASIN: {
1628 Register Val = MI.getOperand(i: 1).getReg();
1629 KnownFPClass KnownSrc;
1630 computeKnownFPClass(R: Val, DemandedElts, InterestedClasses, Known&: KnownSrc,
1631 Depth: Depth + 1);
1632 Known = KnownFPClass::asin(Src: KnownSrc);
1633 break;
1634 }
1635 case TargetOpcode::G_FACOS: {
1636 Register Val = MI.getOperand(i: 1).getReg();
1637 KnownFPClass KnownSrc;
1638 computeKnownFPClass(R: Val, DemandedElts, InterestedClasses, Known&: KnownSrc,
1639 Depth: Depth + 1);
1640 Known = KnownFPClass::acos(Src: KnownSrc);
1641 break;
1642 }
1643 case TargetOpcode::G_FATAN: {
1644 Register Val = MI.getOperand(i: 1).getReg();
1645 KnownFPClass KnownSrc;
1646 computeKnownFPClass(R: Val, DemandedElts, InterestedClasses, Known&: KnownSrc,
1647 Depth: Depth + 1);
1648 Known = KnownFPClass::atan(Src: KnownSrc);
1649 break;
1650 }
1651 case TargetOpcode::G_FTAN: {
1652 Register Val = MI.getOperand(i: 1).getReg();
1653 KnownFPClass KnownSrc;
1654 computeKnownFPClass(R: Val, DemandedElts, InterestedClasses, Known&: KnownSrc,
1655 Depth: Depth + 1);
1656 Known = KnownFPClass::tan(Src: KnownSrc);
1657 break;
1658 }
1659 case TargetOpcode::G_FSIN:
1660 case TargetOpcode::G_FCOS: {
1661 // Return NaN on infinite inputs.
1662 Register Val = MI.getOperand(i: 1).getReg();
1663 KnownFPClass KnownSrc;
1664 computeKnownFPClass(R: Val, DemandedElts, InterestedClasses, Known&: KnownSrc,
1665 Depth: Depth + 1);
1666 Known = Opcode == TargetOpcode::G_FCOS ? KnownFPClass::cos(Src: KnownSrc)
1667 : KnownFPClass::sin(Src: KnownSrc);
1668 break;
1669 }
1670 case TargetOpcode::G_FSINCOS: {
1671 // Operand layout: (sin_dst, cos_dst, src)
1672 Register Src = MI.getOperand(i: 2).getReg();
1673 KnownFPClass KnownSrc;
1674 computeKnownFPClass(R: Src, DemandedElts, InterestedClasses, Known&: KnownSrc,
1675 Depth: Depth + 1);
1676 if (R == MI.getOperand(i: 0).getReg())
1677 Known = KnownFPClass::sin(Src: KnownSrc);
1678 else
1679 Known = KnownFPClass::cos(Src: KnownSrc);
1680 break;
1681 }
1682 case TargetOpcode::G_FMAXNUM:
1683 case TargetOpcode::G_FMINNUM:
1684 case TargetOpcode::G_FMINNUM_IEEE:
1685 case TargetOpcode::G_FMAXIMUM:
1686 case TargetOpcode::G_FMINIMUM:
1687 case TargetOpcode::G_FMAXNUM_IEEE:
1688 case TargetOpcode::G_FMAXIMUMNUM:
1689 case TargetOpcode::G_FMINIMUMNUM: {
1690 Register LHS = MI.getOperand(i: 1).getReg();
1691 Register RHS = MI.getOperand(i: 2).getReg();
1692 KnownFPClass KnownLHS, KnownRHS;
1693
1694 computeKnownFPClass(R: LHS, DemandedElts, InterestedClasses, Known&: KnownLHS,
1695 Depth: Depth + 1);
1696 computeKnownFPClass(R: RHS, DemandedElts, InterestedClasses, Known&: KnownRHS,
1697 Depth: Depth + 1);
1698
1699 KnownFPClass::MinMaxKind Kind;
1700 switch (Opcode) {
1701 case TargetOpcode::G_FMINIMUM:
1702 Kind = KnownFPClass::MinMaxKind::minimum;
1703 break;
1704 case TargetOpcode::G_FMAXIMUM:
1705 Kind = KnownFPClass::MinMaxKind::maximum;
1706 break;
1707 case TargetOpcode::G_FMINIMUMNUM:
1708 Kind = KnownFPClass::MinMaxKind::minimumnum;
1709 break;
1710 case TargetOpcode::G_FMAXIMUMNUM:
1711 Kind = KnownFPClass::MinMaxKind::maximumnum;
1712 break;
1713 case TargetOpcode::G_FMINNUM:
1714 case TargetOpcode::G_FMINNUM_IEEE:
1715 Kind = KnownFPClass::MinMaxKind::minnum;
1716 break;
1717 case TargetOpcode::G_FMAXNUM:
1718 case TargetOpcode::G_FMAXNUM_IEEE:
1719 Kind = KnownFPClass::MinMaxKind::maxnum;
1720 break;
1721 default:
1722 llvm_unreachable("unhandled min/max opcode");
1723 }
1724
1725 DenormalMode Mode =
1726 MF->getDenormalMode(FPType: getFltSemanticForLLT(Ty: DstTy.getScalarType()));
1727 Known = KnownFPClass::minMaxLike(LHS: KnownLHS, RHS: KnownRHS, Kind, Mode);
1728 break;
1729 }
1730 case TargetOpcode::G_FCANONICALIZE: {
1731 Register Val = MI.getOperand(i: 1).getReg();
1732 KnownFPClass KnownSrc;
1733 computeKnownFPClass(R: Val, DemandedElts, InterestedClasses, Known&: KnownSrc,
1734 Depth: Depth + 1);
1735
1736 LLT Ty = MRI.getType(Reg: Val).getScalarType();
1737 const fltSemantics &FPType = getFltSemanticForLLT(Ty);
1738 DenormalMode Mode = MF->getDenormalMode(FPType);
1739 Known = KnownFPClass::canonicalize(Src: KnownSrc, Flt: FPType, Mode);
1740 break;
1741 }
1742 case TargetOpcode::G_VECREDUCE_FMAX:
1743 case TargetOpcode::G_VECREDUCE_FMIN:
1744 case TargetOpcode::G_VECREDUCE_FMAXIMUM:
1745 case TargetOpcode::G_VECREDUCE_FMINIMUM:
1746 case TargetOpcode::G_VECREDUCE_FMAXIMUMNUM:
1747 case TargetOpcode::G_VECREDUCE_FMINIMUMNUM: {
1748 Register Val = MI.getOperand(i: 1).getReg();
1749 // reduce min/max will choose an element from one of the vector elements,
1750 // so we can infer and class information that is common to all elements.
1751
1752 Known =
1753 computeKnownFPClass(R: Val, Flags: MI.getFlags(), InterestedClasses, Depth: Depth + 1);
1754 // Can only propagate sign if output is never NaN.
1755 if (!Known.isKnownNeverNaN())
1756 Known.setSignBit(std::nullopt);
1757 break;
1758 }
1759 case TargetOpcode::G_FFLOOR:
1760 case TargetOpcode::G_FCEIL:
1761 case TargetOpcode::G_FRINT:
1762 case TargetOpcode::G_FNEARBYINT:
1763 case TargetOpcode::G_INTRINSIC_ROUND:
1764 case TargetOpcode::G_INTRINSIC_ROUNDEVEN:
1765 case TargetOpcode::G_INTRINSIC_TRUNC: {
1766 Register Val = MI.getOperand(i: 1).getReg();
1767 KnownFPClass KnownSrc;
1768 FPClassTest InterestedSrcs = InterestedClasses;
1769
1770 // Negative round ups towards zero produce negative zero.
1771 if (InterestedSrcs & fcNegFinite)
1772 InterestedSrcs |= fcNegFinite;
1773
1774 // Negative subnormals may flush to positive zero.
1775 if (InterestedSrcs & fcPosFinite)
1776 InterestedSrcs |= fcPosFinite | fcNegSubnormal;
1777
1778 computeKnownFPClass(R: Val, DemandedElts, InterestedClasses: InterestedSrcs, Known&: KnownSrc, Depth: Depth + 1);
1779
1780 LLT Ty = MRI.getType(Reg: Val).getScalarType();
1781 const fltSemantics &FltSem = getFltSemanticForLLT(Ty);
1782 DenormalMode Mode = MF->getDenormalMode(FPType: FltSem);
1783 const bool IsMultiUnitFPType = &FltSem == &APFloat::PPCDoubleDouble();
1784
1785 switch (Opcode) {
1786 case TargetOpcode::G_INTRINSIC_TRUNC:
1787 Known = KnownFPClass::trunc(Src: KnownSrc, Mode);
1788 break;
1789 case TargetOpcode::G_FFLOOR:
1790 Known = KnownFPClass::floor(Src: KnownSrc, IsMultiUnitFPType, Mode);
1791 break;
1792 case TargetOpcode::G_FCEIL:
1793 Known = KnownFPClass::ceil(Src: KnownSrc, IsMultiUnitFPType, Mode);
1794 break;
1795 default:
1796 Known = KnownFPClass::roundToIntegral(Src: KnownSrc, IsMultiUnitFPType, Mode);
1797 break;
1798 }
1799 break;
1800 }
1801 case TargetOpcode::G_FEXP:
1802 case TargetOpcode::G_FEXP2:
1803 case TargetOpcode::G_FEXP10: {
1804 Register Val = MI.getOperand(i: 1).getReg();
1805 KnownFPClass KnownSrc;
1806 computeKnownFPClass(R: Val, DemandedElts, InterestedClasses, Known&: KnownSrc,
1807 Depth: Depth + 1);
1808 Known = KnownFPClass::exp(Src: KnownSrc);
1809 break;
1810 }
1811 case TargetOpcode::G_FLOG:
1812 case TargetOpcode::G_FLOG2:
1813 case TargetOpcode::G_FLOG10: {
1814 FPClassTest InterestedSrcs = fcNone;
1815
1816 // log(negative) produces NaN.
1817 if ((InterestedClasses & fcNan) != fcNone)
1818 InterestedSrcs |= fcNan | fcNegative;
1819
1820 // log(logical-zero) produces negative infinity.
1821 if ((InterestedClasses & fcNegInf) != fcNone)
1822 InterestedSrcs |= fcZero | fcSubnormal;
1823
1824 // log(x) < -0.0 if x < +1.0
1825 if ((InterestedClasses & fcNegNormal) != fcNone)
1826 InterestedSrcs |= fcPosSubnormal | fcPosNormal;
1827
1828 // log(x) >= +0.0 if x >= +1.0
1829 if ((InterestedClasses & (fcPosZero | fcPosNormal)) != fcNone)
1830 InterestedSrcs |= fcPosNormal;
1831
1832 // log(x) is positive infinity iff x is positive infinity.
1833 if ((InterestedClasses & fcPosInf) != fcNone)
1834 InterestedSrcs |= fcPosInf;
1835
1836 Register Val = MI.getOperand(i: 1).getReg();
1837 KnownFPClass KnownSrc;
1838 if (InterestedSrcs != fcNone)
1839 computeKnownFPClass(R: Val, DemandedElts, InterestedClasses: InterestedSrcs, Known&: KnownSrc,
1840 Depth: Depth + 1);
1841
1842 LLT Ty = MRI.getType(Reg: Val).getScalarType();
1843 const fltSemantics &FltSem = getFltSemanticForLLT(Ty);
1844 DenormalMode Mode = MF->getDenormalMode(FPType: FltSem);
1845 bool IsMultiUnitFPType = &FltSem == &APFloat::PPCDoubleDouble();
1846 Known = KnownFPClass::log(Src: KnownSrc, Mode, IsMultiUnitFPType);
1847 break;
1848 }
1849 case TargetOpcode::G_FPOW: {
1850 const bool WantNaN = (InterestedClasses & fcNan) != fcNone;
1851 const bool WantNegative = (InterestedClasses & fcNegative) != fcNone;
1852 if (!WantNaN && !WantNegative)
1853 break;
1854
1855 FPClassTest InterestedLHS = fcNone;
1856 FPClassTest InterestedRHS = fcNone;
1857 if (WantNaN) {
1858 // pow may return NaN if one of the arguments is NaN. NaN may be produced
1859 // from a non-zero-finite-negative base and a non-integer exponent.
1860 InterestedLHS |= fcNan | fcNegNormal | fcNegSubnormal;
1861 InterestedRHS |= fcNan;
1862 }
1863 if (WantNegative) {
1864 // A negative value is returned when a negative base is raised to an odd
1865 // integer power. Only normal values can be odd integers.
1866 InterestedLHS |= fcNegative;
1867 InterestedRHS |= fcNormal;
1868 }
1869
1870 KnownFPClass KnownLHS;
1871 computeKnownFPClass(R: MI.getOperand(i: 1).getReg(), DemandedElts, InterestedClasses: InterestedLHS,
1872 Known&: KnownLHS, Depth: Depth + 1);
1873
1874 // If the LHS is unknown, then querying the RHS is only useful for rare edge
1875 // cases.
1876 if (KnownLHS.isUnknown())
1877 break;
1878
1879 KnownFPClass KnownRHS;
1880 computeKnownFPClass(R: MI.getOperand(i: 2).getReg(), DemandedElts, InterestedClasses: InterestedRHS,
1881 Known&: KnownRHS, Depth: Depth + 1);
1882 Known = KnownFPClass::pow(LHS: KnownLHS, RHS: KnownRHS);
1883 break;
1884 }
1885 case TargetOpcode::G_FPOWI: {
1886 if ((InterestedClasses & (fcNan | fcInf | fcNegative)) == fcNone)
1887 break;
1888
1889 Register Exp = MI.getOperand(i: 2).getReg();
1890 LLT ExpTy = MRI.getType(Reg: Exp);
1891 KnownBits ExponentKnownBits = getKnownBits(
1892 R: Exp, DemandedElts: ExpTy.isVector() ? DemandedElts : APInt(1, 1), Depth: Depth + 1);
1893
1894 FPClassTest InterestedSrcs = fcNone;
1895 if (InterestedClasses & fcNan)
1896 InterestedSrcs |= fcNan;
1897 if (!ExponentKnownBits.isZero()) {
1898 if (InterestedClasses & fcInf)
1899 InterestedSrcs |= fcFinite | fcInf;
1900 if ((InterestedClasses & fcNegative) && !ExponentKnownBits.isEven())
1901 InterestedSrcs |= fcNegative;
1902 }
1903
1904 KnownFPClass KnownSrc;
1905 if (InterestedSrcs != fcNone) {
1906 Register Val = MI.getOperand(i: 1).getReg();
1907 computeKnownFPClass(R: Val, DemandedElts, InterestedClasses: InterestedSrcs, Known&: KnownSrc,
1908 Depth: Depth + 1);
1909 }
1910
1911 Known = KnownFPClass::powi(Src: KnownSrc, N: ExponentKnownBits);
1912 break;
1913 }
1914 case TargetOpcode::G_FLDEXP: {
1915 Register Val = MI.getOperand(i: 1).getReg();
1916 KnownFPClass KnownSrc;
1917 computeKnownFPClass(R: Val, DemandedElts, InterestedClasses, Known&: KnownSrc,
1918 Depth: Depth + 1);
1919
1920 // Can refine inf/zero handling based on the exponent operand.
1921 const FPClassTest ExpInfoMask = fcZero | fcSubnormal | fcInf;
1922 KnownBits ExpBits;
1923 if ((KnownSrc.getKnownFPClasses() & ExpInfoMask) != fcNone) {
1924 Register ExpReg = MI.getOperand(i: 2).getReg();
1925 LLT ExpTy = MRI.getType(Reg: ExpReg);
1926 ExpBits = getKnownBits(
1927 R: ExpReg, DemandedElts: ExpTy.isVector() ? DemandedElts : APInt(1, 1), Depth: Depth + 1);
1928 }
1929
1930 LLT ScalarTy = DstTy.getScalarType();
1931 const fltSemantics &Flt = getFltSemanticForLLT(Ty: ScalarTy);
1932 DenormalMode Mode = MF->getDenormalMode(FPType: Flt);
1933 Known = KnownFPClass::ldexp(Src: KnownSrc, ExpBits, Flt, Mode);
1934 break;
1935 }
1936 case TargetOpcode::G_FADD:
1937 case TargetOpcode::G_STRICT_FADD:
1938 case TargetOpcode::G_FSUB:
1939 case TargetOpcode::G_STRICT_FSUB: {
1940 Register LHS = MI.getOperand(i: 1).getReg();
1941 Register RHS = MI.getOperand(i: 2).getReg();
1942
1943 const bool IsAdd =
1944 Opcode == TargetOpcode::G_FADD || Opcode == TargetOpcode::G_STRICT_FADD;
1945 const bool IsStrict = Opcode == TargetOpcode::G_STRICT_FADD ||
1946 Opcode == TargetOpcode::G_STRICT_FSUB;
1947 // TODO: Obtain rounding mode for strict fadd/fsub.
1948 const RoundingMode RM =
1949 IsStrict ? RoundingMode::Dynamic : RoundingMode::NearestTiesToEven;
1950
1951 bool WantNegative =
1952 IsAdd &&
1953 (InterestedClasses & KnownFPClass::OrderedLessThanZeroMask) != fcNone;
1954 bool WantNaN = (InterestedClasses & fcNan) != fcNone;
1955 bool WantNegZero = (InterestedClasses & fcNegZero) != fcNone;
1956
1957 if (!WantNaN && !WantNegative && !WantNegZero) {
1958 break;
1959 }
1960
1961 DenormalMode Mode =
1962 MF->getDenormalMode(FPType: getFltSemanticForLLT(Ty: DstTy.getScalarType()));
1963
1964 FPClassTest InterestedSrcs = InterestedClasses;
1965 if (WantNegative)
1966 InterestedSrcs |= KnownFPClass::OrderedLessThanZeroMask;
1967 if (InterestedClasses & fcNan)
1968 InterestedSrcs |= fcInf;
1969
1970 // Special case fadd x, x (canonical form of fmul x, 2).
1971 if (IsAdd && LHS == RHS && isGuaranteedNotToBeUndef(Reg: LHS, MRI, Depth: Depth + 1)) {
1972 KnownFPClass KnownSelf;
1973 computeKnownFPClass(R: LHS, DemandedElts, InterestedClasses: InterestedSrcs, Known&: KnownSelf,
1974 Depth: Depth + 1);
1975 Known = KnownFPClass::fadd_self(Src: KnownSelf, RM, Mode);
1976 break;
1977 }
1978
1979 KnownFPClass KnownLHS, KnownRHS;
1980 computeKnownFPClass(R: RHS, DemandedElts, InterestedClasses: InterestedSrcs, Known&: KnownRHS, Depth: Depth + 1);
1981
1982 if ((WantNaN && KnownRHS.isKnownNeverNaN()) ||
1983 (WantNegative && KnownRHS.cannotBeOrderedLessThanZero()) ||
1984 WantNegZero || !IsAdd) {
1985 // RHS is canonically cheaper to compute. Skip inspecting the LHS if
1986 // there's no point.
1987 computeKnownFPClass(R: LHS, DemandedElts, InterestedClasses: InterestedSrcs, Known&: KnownLHS,
1988 Depth: Depth + 1);
1989 }
1990
1991 if (IsAdd)
1992 Known = KnownFPClass::fadd(LHS: KnownLHS, RHS: KnownRHS, RM, Mode);
1993 else
1994 Known = KnownFPClass::fsub(LHS: KnownLHS, RHS: KnownRHS, RM, Mode);
1995 break;
1996 }
1997 case TargetOpcode::G_FMUL: {
1998 Register LHS = MI.getOperand(i: 1).getReg();
1999 Register RHS = MI.getOperand(i: 2).getReg();
2000 DenormalMode Mode =
2001 MF->getDenormalMode(FPType: getFltSemanticForLLT(Ty: DstTy.getScalarType()));
2002
2003 // X * X is always non-negative or a NaN (use square() for precision).
2004 if (LHS == RHS && isGuaranteedNotToBeUndef(Reg: LHS, MRI, Depth: Depth + 1)) {
2005 KnownFPClass KnownSrc;
2006 computeKnownFPClass(R: LHS, DemandedElts, InterestedClasses: fcAllFlags, Known&: KnownSrc, Depth: Depth + 1);
2007 Known = KnownFPClass::square(Src: KnownSrc, Mode);
2008 } else {
2009 // If RHS is a scalar constant, use the more precise APFloat overload.
2010 auto RHSCst = GFConstant::getConstant(Const: RHS, MRI);
2011 if (RHSCst && RHSCst->getKind() == GFConstant::GFConstantKind::Scalar) {
2012 KnownFPClass KnownLHS;
2013 computeKnownFPClass(R: LHS, DemandedElts, InterestedClasses: fcAllFlags, Known&: KnownLHS, Depth: Depth + 1);
2014 Known = KnownFPClass::fmul(LHS: KnownLHS, RHS: RHSCst->getScalarValue(), Mode);
2015 } else {
2016 KnownFPClass KnownLHS, KnownRHS;
2017 computeKnownFPClass(R: RHS, DemandedElts, InterestedClasses: fcAllFlags, Known&: KnownRHS, Depth: Depth + 1);
2018 computeKnownFPClass(R: LHS, DemandedElts, InterestedClasses: fcAllFlags, Known&: KnownLHS, Depth: Depth + 1);
2019 Known = KnownFPClass::fmul(LHS: KnownLHS, RHS: KnownRHS, Mode);
2020
2021 // If one operand is known |x| <= 1 and the other is finite, the
2022 // product cannot overflow to infinity.
2023 if (KnownLHS.isKnownNever(Mask: fcInf) && isAbsoluteValueULEOne(R: RHS, MRI))
2024 Known.knownNot(RuleOut: fcInf);
2025 else if (KnownRHS.isKnownNever(Mask: fcInf) &&
2026 isAbsoluteValueULEOne(R: LHS, MRI))
2027 Known.knownNot(RuleOut: fcInf);
2028 }
2029 }
2030 break;
2031 }
2032 case TargetOpcode::G_FDIV: {
2033 const bool WantNan = (InterestedClasses & fcNan) != fcNone;
2034
2035 Register LHS = MI.getOperand(i: 1).getReg();
2036 Register RHS = MI.getOperand(i: 2).getReg();
2037
2038 DenormalMode Mode =
2039 MF->getDenormalMode(FPType: getFltSemanticForLLT(Ty: DstTy.getScalarType()));
2040
2041 if (LHS == RHS && isGuaranteedNotToBeUndef(Reg: LHS, MRI, Depth: Depth + 1)) {
2042 // X / X is always exactly 1.0 or a NaN.
2043 Known.setKnownFPClasses(fcPosNormal | fcNan);
2044
2045 if (!WantNan)
2046 break;
2047
2048 KnownFPClass KnownSrc;
2049 computeKnownFPClass(R: LHS, DemandedElts,
2050 InterestedClasses: fcNan | fcInf | fcZero | fcSubnormal, Known&: KnownSrc,
2051 Depth: Depth + 1);
2052 Known = KnownFPClass::fdiv_self(Src: KnownSrc, Mode);
2053 break;
2054 }
2055
2056 const bool WantNegative = (InterestedClasses & fcNegative) != fcNone;
2057 const bool WantPositive = (InterestedClasses & fcPositive) != fcNone;
2058 if (!WantNan && !WantNegative && !WantPositive)
2059 break;
2060
2061 KnownFPClass KnownLHS, KnownRHS;
2062 computeKnownFPClass(R: RHS, DemandedElts, InterestedClasses: fcAllFlags, Known&: KnownRHS, Depth: Depth + 1);
2063
2064 bool KnowSomethingUseful =
2065 KnownRHS.isKnownNever(Mask: fcSNan) ||
2066 KnownRHS.isKnownNever(Mask: fcNegNormal | fcNegSubnormal) ||
2067 KnownRHS.isKnownNever(Mask: fcPosNormal | fcPosSubnormal);
2068
2069 if (KnowSomethingUseful)
2070 computeKnownFPClass(R: LHS, DemandedElts, InterestedClasses: fcAllFlags, Known&: KnownLHS, Depth: Depth + 1);
2071
2072 Known = KnownFPClass::fdiv(LHS: KnownLHS, RHS: KnownRHS, Mode);
2073 break;
2074 }
2075 case TargetOpcode::G_FREM:
2076 case TargetOpcode::G_STRICT_FREM: {
2077 FPClassTest InterestedLHS = fcNone;
2078 FPClassTest InterestedRHS = fcNone;
2079
2080 // NaN is also generated for frem(Inf, x) and frem(x, 0.0).
2081 if (InterestedClasses & fcNan) {
2082 InterestedLHS |= fcNan | fcInf;
2083 InterestedRHS |= fcNan | fcZero | fcSubnormal;
2084 }
2085
2086 // The sign for frem is the same as the first operand.
2087 if (InterestedClasses & (fcPosNormal | fcPosSubnormal))
2088 InterestedLHS |= fcPosNormal | fcPosSubnormal;
2089 if (InterestedClasses & (fcNegNormal | fcNegSubnormal))
2090 InterestedLHS |= fcNegNormal | fcNegSubnormal;
2091
2092 // A negative zero result requires a negative finite first operand.
2093 if (InterestedClasses & fcNegZero)
2094 InterestedLHS |= fcNegFinite;
2095
2096 // A positive zero result can additionally come from a negative finite
2097 // result being flushed to positive zero.
2098 if (InterestedClasses & fcPosZero)
2099 InterestedLHS |= fcPosFinite | fcNegNormal | fcNegSubnormal;
2100
2101 Register LHS = MI.getOperand(i: 1).getReg();
2102 Register RHS = MI.getOperand(i: 2).getReg();
2103
2104 DenormalMode Mode =
2105 MF->getDenormalMode(FPType: getFltSemanticForLLT(Ty: DstTy.getScalarType()));
2106
2107 if (LHS == RHS && isGuaranteedNotToBeUndef(Reg: LHS, MRI, Depth: Depth + 1)) {
2108 // X % X is always exactly [+-]0.0 or a NaN.
2109 FPClassTest InterestedSrcs = InterestedLHS | InterestedRHS;
2110 KnownFPClass KnownSrc;
2111 if (InterestedSrcs != fcNone)
2112 computeKnownFPClass(R: LHS, DemandedElts, InterestedClasses: InterestedSrcs, Known&: KnownSrc,
2113 Depth: Depth + 1);
2114 Known = KnownFPClass::frem_self(Src: KnownSrc, Mode);
2115 break;
2116 }
2117
2118 KnownFPClass KnownLHS;
2119 if (InterestedLHS != fcNone)
2120 computeKnownFPClass(R: LHS, DemandedElts, InterestedClasses: InterestedLHS, Known&: KnownLHS,
2121 Depth: Depth + 1);
2122
2123 KnownFPClass KnownRHS;
2124 // RHS is only useful for refining NaN classes.
2125 if (InterestedRHS != fcNone && KnownLHS.isKnownNever(Mask: fcSNan))
2126 computeKnownFPClass(R: RHS, DemandedElts, InterestedClasses: InterestedRHS, Known&: KnownRHS,
2127 Depth: Depth + 1);
2128
2129 Known = KnownFPClass::frem(LHS: KnownLHS, RHS: KnownRHS, Mode);
2130
2131 break;
2132 }
2133 case TargetOpcode::G_FFREXP: {
2134 // Only handle the mantissa output (operand 0); the exponent is an integer.
2135 if (R != MI.getOperand(i: 0).getReg())
2136 break;
2137 Register Src = MI.getOperand(i: 2).getReg();
2138 FPClassTest InterestedSrcs = InterestedClasses;
2139
2140 // Positive subnormals and negative subnormals could become positive zero.
2141 if (InterestedClasses & fcPosZero)
2142 InterestedSrcs |= fcSubnormal;
2143
2144 // Negative subnormals could become negative zero.
2145 if (InterestedClasses & fcNegZero)
2146 InterestedSrcs |= fcNegSubnormal;
2147
2148 if (InterestedClasses & fcPosNormal)
2149 InterestedSrcs |= fcPosSubnormal;
2150
2151 if (InterestedClasses & fcNegNormal)
2152 InterestedSrcs |= fcNegSubnormal;
2153
2154 KnownFPClass KnownSrc;
2155 computeKnownFPClass(R: Src, DemandedElts, InterestedClasses: InterestedSrcs, Known&: KnownSrc, Depth: Depth + 1);
2156 DenormalMode Mode =
2157 MF->getDenormalMode(FPType: getFltSemanticForLLT(Ty: DstTy.getScalarType()));
2158 Known = KnownFPClass::frexp_mant(Src: KnownSrc, Mode);
2159 break;
2160 }
2161 case TargetOpcode::G_FPEXT: {
2162 Register Src = MI.getOperand(i: 1).getReg();
2163 KnownFPClass KnownSrc;
2164 computeKnownFPClass(R: Src, DemandedElts, InterestedClasses, Known&: KnownSrc,
2165 Depth: Depth + 1);
2166
2167 LLT DstScalarTy = DstTy.getScalarType();
2168 const fltSemantics &DstSem = getFltSemanticForLLT(Ty: DstScalarTy);
2169 LLT SrcTy = MRI.getType(Reg: Src).getScalarType();
2170 const fltSemantics &SrcSem = getFltSemanticForLLT(Ty: SrcTy);
2171
2172 Known = KnownFPClass::fpext(KnownSrc, DstTy: DstSem, SrcTy: SrcSem,
2173 DstMode: MF->getDenormalMode(FPType: DstSem),
2174 SrcMode: MF->getDenormalMode(FPType: SrcSem));
2175 break;
2176 }
2177 case TargetOpcode::G_FPTRUNC:
2178 case TargetOpcode::G_INTRINSIC_FPTRUNC_ROUND: {
2179 computeKnownFPClassForFPTrunc(MI, DemandedElts, InterestedClasses, Known,
2180 Depth);
2181 break;
2182 }
2183 case TargetOpcode::G_SITOFP:
2184 case TargetOpcode::G_UITOFP: {
2185 // Cannot produce nan
2186 Known.knownNot(RuleOut: fcNan);
2187
2188 // Integers cannot be subnormal
2189 Known.knownNot(RuleOut: fcSubnormal);
2190
2191 // sitofp and uitofp turn into +0.0 for zero.
2192 Known.knownNot(RuleOut: fcNegZero);
2193
2194 // UIToFP is always non-negative regardless of known bits.
2195 if (Opcode == TargetOpcode::G_UITOFP)
2196 Known.signBitMustBeZero();
2197
2198 // Only compute known bits if we can learn something useful from them.
2199 if (!(InterestedClasses & (fcPosZero | fcNormal | fcInf)))
2200 break;
2201
2202 Register Val = MI.getOperand(i: 1).getReg();
2203 LLT Ty = MRI.getType(Reg: Val);
2204 KnownBits IntKnown = getKnownBits(
2205 R: Val, DemandedElts: Ty.isVector() ? DemandedElts : APInt(1, 1), Depth: Depth + 1);
2206
2207 // If the integer is non-zero, the result cannot be +0.0.
2208 if (IntKnown.isNonZero())
2209 Known.knownNot(RuleOut: fcPosZero);
2210
2211 if (Opcode == TargetOpcode::G_SITOFP) {
2212 // If the signed integer is known non-negative, the result is
2213 // non-negative. If the signed integer is known negative, the result is
2214 // negative.
2215 if (IntKnown.isNonNegative())
2216 Known.signBitMustBeZero();
2217 else if (IntKnown.isNegative())
2218 Known.signBitMustBeOne();
2219 }
2220
2221 if (InterestedClasses & fcInf) {
2222 LLT FPTy = DstTy.getScalarType();
2223 const fltSemantics &FltSem = getFltSemanticForLLT(Ty: FPTy);
2224
2225 // Compute the effective integer width after removing known-zero leading
2226 // bits, to check if the result can overflow to infinity.
2227 int IntSize = IntKnown.getBitWidth();
2228 if (Opcode == TargetOpcode::G_UITOFP)
2229 IntSize -= IntKnown.countMinLeadingZeros();
2230 else
2231 IntSize -= IntKnown.countMinSignBits();
2232
2233 // If the exponent of the largest finite FP value can hold the largest
2234 // integer, the result of the cast must be finite.
2235 if (ilogb(Arg: APFloat::getLargest(Sem: FltSem)) >= IntSize)
2236 Known.knownNot(RuleOut: fcInf);
2237 }
2238
2239 break;
2240 }
2241 // case TargetOpcode::G_MERGE_VALUES:
2242 case TargetOpcode::G_BUILD_VECTOR:
2243 case TargetOpcode::G_CONCAT_VECTORS: {
2244 GMergeLikeInstr &Merge = cast<GMergeLikeInstr>(Val&: MI);
2245
2246 if (!DstTy.isFixedVector())
2247 break;
2248
2249 bool First = true;
2250 for (unsigned Idx = 0; Idx < Merge.getNumSources(); ++Idx) {
2251 // We know the index we are inserting to, so clear it from Vec check.
2252 bool NeedsElt = DemandedElts[Idx];
2253
2254 // Do we demand the inserted element?
2255 if (NeedsElt) {
2256 Register Src = Merge.getSourceReg(I: Idx);
2257 if (First) {
2258 computeKnownFPClass(R: Src, Known, InterestedClasses, Depth: Depth + 1);
2259 First = false;
2260 } else {
2261 KnownFPClass Known2;
2262 computeKnownFPClass(R: Src, Known&: Known2, InterestedClasses, Depth: Depth + 1);
2263 Known |= Known2;
2264 }
2265
2266 // If we don't know any bits, early out.
2267 if (Known.isUnknown())
2268 break;
2269 }
2270 }
2271
2272 break;
2273 }
2274 case TargetOpcode::G_EXTRACT_VECTOR_ELT: {
2275 // Look through extract element. If the index is non-constant or
2276 // out-of-range demand all elements, otherwise just the extracted
2277 // element.
2278 GExtractVectorElement &Extract = cast<GExtractVectorElement>(Val&: MI);
2279 Register Vec = Extract.getVectorReg();
2280 Register Idx = Extract.getIndexReg();
2281
2282 auto CIdx = getIConstantVRegVal(VReg: Idx, MRI);
2283
2284 LLT VecTy = MRI.getType(Reg: Vec);
2285
2286 if (VecTy.isFixedVector()) {
2287 unsigned NumElts = VecTy.getNumElements();
2288 APInt DemandedVecElts = APInt::getAllOnes(numBits: NumElts);
2289 if (CIdx && CIdx->ult(RHS: NumElts))
2290 DemandedVecElts = APInt::getOneBitSet(numBits: NumElts, BitNo: CIdx->getZExtValue());
2291 return computeKnownFPClass(R: Vec, DemandedElts: DemandedVecElts, InterestedClasses, Known,
2292 Depth: Depth + 1);
2293 }
2294
2295 break;
2296 }
2297 case TargetOpcode::G_INSERT_VECTOR_ELT: {
2298 GInsertVectorElement &Insert = cast<GInsertVectorElement>(Val&: MI);
2299 Register Vec = Insert.getVectorReg();
2300 Register Elt = Insert.getElementReg();
2301 Register Idx = Insert.getIndexReg();
2302
2303 LLT VecTy = MRI.getType(Reg: Vec);
2304
2305 if (VecTy.isScalableVector())
2306 return;
2307
2308 auto CIdx = getIConstantVRegVal(VReg: Idx, MRI);
2309
2310 unsigned NumElts = DemandedElts.getBitWidth();
2311 APInt DemandedVecElts = DemandedElts;
2312 bool NeedsElt = true;
2313 // If we know the index we are inserting to, clear it from Vec check.
2314 if (CIdx && CIdx->ult(RHS: NumElts)) {
2315 DemandedVecElts.clearBit(BitPosition: CIdx->getZExtValue());
2316 NeedsElt = DemandedElts[CIdx->getZExtValue()];
2317 }
2318
2319 // Do we demand the inserted element?
2320 if (NeedsElt) {
2321 computeKnownFPClass(R: Elt, Known, InterestedClasses, Depth: Depth + 1);
2322 // If we don't know any bits, early out.
2323 if (Known.isUnknown())
2324 break;
2325 } else {
2326 Known = KnownFPClass::getEmpty();
2327 }
2328
2329 // Do we need anymore elements from Vec?
2330 if (!DemandedVecElts.isZero()) {
2331 KnownFPClass Known2;
2332 computeKnownFPClass(R: Vec, DemandedElts: DemandedVecElts, InterestedClasses, Known&: Known2,
2333 Depth: Depth + 1);
2334 Known |= Known2;
2335 }
2336
2337 break;
2338 }
2339 case TargetOpcode::G_SHUFFLE_VECTOR: {
2340 // For undef elements, we don't know anything about the common state of
2341 // the shuffle result.
2342 GShuffleVector &Shuf = cast<GShuffleVector>(Val&: MI);
2343 APInt DemandedLHS, DemandedRHS;
2344 if (DstTy.isScalableVector()) {
2345 assert(DemandedElts == APInt(1, 1));
2346 DemandedLHS = DemandedRHS = DemandedElts;
2347 } else {
2348 unsigned NumElts = MRI.getType(Reg: Shuf.getSrc1Reg()).getNumElements();
2349 if (!llvm::getShuffleDemandedElts(SrcWidth: NumElts, Mask: Shuf.getMask(), DemandedElts,
2350 DemandedLHS, DemandedRHS)) {
2351 Known.resetAll();
2352 return;
2353 }
2354 }
2355
2356 if (!!DemandedLHS) {
2357 Register LHS = Shuf.getSrc1Reg();
2358 computeKnownFPClass(R: LHS, DemandedElts: DemandedLHS, InterestedClasses, Known,
2359 Depth: Depth + 1);
2360
2361 // If we don't know any bits, early out.
2362 if (Known.isUnknown())
2363 break;
2364 } else {
2365 Known = KnownFPClass::getEmpty();
2366 }
2367
2368 if (!!DemandedRHS) {
2369 KnownFPClass Known2;
2370 Register RHS = Shuf.getSrc2Reg();
2371 computeKnownFPClass(R: RHS, DemandedElts: DemandedRHS, InterestedClasses, Known&: Known2,
2372 Depth: Depth + 1);
2373 Known |= Known2;
2374 }
2375 break;
2376 }
2377 case TargetOpcode::G_PHI: {
2378 // Cap PHI recursion below the global limit to avoid spending the entire
2379 // budget chasing loop back-edges (matches ValueTracking's
2380 // PhiRecursionLimit).
2381 if (Depth + 2 > MaxAnalysisRecursionDepth)
2382 break;
2383 // PHI's operands are a mix of registers and basic blocks interleaved.
2384 // We only care about the register ones.
2385 bool First = true;
2386 for (unsigned Idx = 1; Idx < MI.getNumOperands(); Idx += 2) {
2387 const MachineOperand &Src = MI.getOperand(i: Idx);
2388 Register SrcReg = Src.getReg();
2389 if (First) {
2390 computeKnownFPClass(R: SrcReg, DemandedElts, InterestedClasses, Known,
2391 Depth: Depth + 1);
2392 First = false;
2393 } else {
2394 KnownFPClass Known2;
2395 computeKnownFPClass(R: SrcReg, DemandedElts, InterestedClasses, Known&: Known2,
2396 Depth: Depth + 1);
2397 Known = Known.intersectWith(RHS: Known2);
2398 }
2399 if (Known.isUnknown())
2400 break;
2401 }
2402 break;
2403 }
2404 case TargetOpcode::G_FREEZE: {
2405 Register Src = MI.getOperand(i: 1).getReg();
2406 if (isGuaranteedNotToBeUndefOrPoison(Reg: Src, MRI, Depth: Depth + 1)) {
2407 computeKnownFPClass(R: Src, DemandedElts, InterestedClasses, Known,
2408 Depth: Depth + 1);
2409 }
2410 break;
2411 }
2412 case TargetOpcode::COPY: {
2413 Register Src = MI.getOperand(i: 1).getReg();
2414
2415 if (!Src.isVirtual())
2416 return;
2417
2418 computeKnownFPClass(R: Src, DemandedElts, InterestedClasses, Known, Depth: Depth + 1);
2419 break;
2420 }
2421 }
2422}
2423
2424KnownFPClass
2425GISelValueTracking::computeKnownFPClass(Register R, const APInt &DemandedElts,
2426 FPClassTest InterestedClasses,
2427 unsigned Depth) {
2428 KnownFPClass KnownClasses;
2429 computeKnownFPClass(R, DemandedElts, InterestedClasses, Known&: KnownClasses, Depth);
2430 return KnownClasses;
2431}
2432
2433KnownFPClass GISelValueTracking::computeKnownFPClass(
2434 Register R, FPClassTest InterestedClasses, unsigned Depth) {
2435 KnownFPClass Known;
2436 computeKnownFPClass(R, Known, InterestedClasses, Depth);
2437 return Known;
2438}
2439
2440KnownFPClass GISelValueTracking::computeKnownFPClass(
2441 Register R, const APInt &DemandedElts, uint32_t Flags,
2442 FPClassTest InterestedClasses, unsigned Depth) {
2443 if (Flags & MachineInstr::MIFlag::FmNoNans)
2444 InterestedClasses &= ~fcNan;
2445 if (Flags & MachineInstr::MIFlag::FmNoInfs)
2446 InterestedClasses &= ~fcInf;
2447
2448 KnownFPClass Result =
2449 computeKnownFPClass(R, DemandedElts, InterestedClasses, Depth);
2450
2451 if (Flags & MachineInstr::MIFlag::FmNoNans)
2452 Result.setKnownFPClasses(Result.getKnownFPClasses() & ~fcNan);
2453 if (Flags & MachineInstr::MIFlag::FmNoInfs)
2454 Result.setKnownFPClasses(Result.getKnownFPClasses() & ~fcInf);
2455 return Result;
2456}
2457
2458KnownFPClass GISelValueTracking::computeKnownFPClass(
2459 Register R, uint32_t Flags, FPClassTest InterestedClasses, unsigned Depth) {
2460 LLT Ty = MRI.getType(Reg: R);
2461 APInt DemandedElts =
2462 Ty.isFixedVector() ? APInt::getAllOnes(numBits: Ty.getNumElements()) : APInt(1, 1);
2463 return computeKnownFPClass(R, DemandedElts, Flags, InterestedClasses, Depth);
2464}
2465
2466bool GISelValueTracking::isKnownNeverNaN(Register Val, bool SNaN) {
2467 const MachineInstr *DefMI = MRI.getVRegDef(Reg: Val);
2468 if (!DefMI)
2469 return false;
2470
2471 if (DefMI->getFlag(Flag: MachineInstr::FmNoNans))
2472 return true;
2473
2474 // IEEE 754 arithmetic operations always quiet signaling NaNs. Short-circuit
2475 // the value-tracking analysis for the SNaN-only case: if the defining op is
2476 // known to quiet sNaN, the output can never be an sNaN.
2477 if (SNaN) {
2478 switch (DefMI->getOpcode()) {
2479 default:
2480 break;
2481 case TargetOpcode::G_FADD:
2482 case TargetOpcode::G_STRICT_FADD:
2483 case TargetOpcode::G_FSUB:
2484 case TargetOpcode::G_STRICT_FSUB:
2485 case TargetOpcode::G_FMUL:
2486 case TargetOpcode::G_STRICT_FMUL:
2487 case TargetOpcode::G_FDIV:
2488 case TargetOpcode::G_STRICT_FDIV:
2489 case TargetOpcode::G_FREM:
2490 case TargetOpcode::G_STRICT_FREM:
2491 case TargetOpcode::G_FMA:
2492 case TargetOpcode::G_STRICT_FMA:
2493 case TargetOpcode::G_FMAD:
2494 case TargetOpcode::G_FSQRT:
2495 case TargetOpcode::G_STRICT_FSQRT:
2496 // Note: G_FABS and G_FNEG are bit-manipulation ops that preserve sNaN
2497 // exactly (LLVM LangRef: "never change anything except possibly the sign
2498 // bit"). They must NOT be listed here.
2499 case TargetOpcode::G_FSIN:
2500 case TargetOpcode::G_FCOS:
2501 case TargetOpcode::G_FSINCOS:
2502 case TargetOpcode::G_FTAN:
2503 case TargetOpcode::G_FASIN:
2504 case TargetOpcode::G_FACOS:
2505 case TargetOpcode::G_FATAN:
2506 case TargetOpcode::G_FATAN2:
2507 case TargetOpcode::G_FSINH:
2508 case TargetOpcode::G_FCOSH:
2509 case TargetOpcode::G_FTANH:
2510 case TargetOpcode::G_FEXP:
2511 case TargetOpcode::G_FEXP2:
2512 case TargetOpcode::G_FEXP10:
2513 case TargetOpcode::G_FLOG:
2514 case TargetOpcode::G_FLOG2:
2515 case TargetOpcode::G_FLOG10:
2516 case TargetOpcode::G_FPOW:
2517 case TargetOpcode::G_FPOWI:
2518 case TargetOpcode::G_FLDEXP:
2519 case TargetOpcode::G_STRICT_FLDEXP:
2520 case TargetOpcode::G_FFREXP:
2521 case TargetOpcode::G_INTRINSIC_TRUNC:
2522 case TargetOpcode::G_INTRINSIC_ROUND:
2523 case TargetOpcode::G_INTRINSIC_ROUNDEVEN:
2524 case TargetOpcode::G_FFLOOR:
2525 case TargetOpcode::G_FCEIL:
2526 case TargetOpcode::G_FRINT:
2527 case TargetOpcode::G_FNEARBYINT:
2528 case TargetOpcode::G_FPEXT:
2529 case TargetOpcode::G_FPTRUNC:
2530 case TargetOpcode::G_FCANONICALIZE:
2531 case TargetOpcode::G_FMINNUM:
2532 case TargetOpcode::G_FMAXNUM:
2533 case TargetOpcode::G_FMINNUM_IEEE:
2534 case TargetOpcode::G_FMAXNUM_IEEE:
2535 case TargetOpcode::G_FMINIMUM:
2536 case TargetOpcode::G_FMAXIMUM:
2537 case TargetOpcode::G_FMINIMUMNUM:
2538 case TargetOpcode::G_FMAXIMUMNUM:
2539 return true;
2540 }
2541 }
2542
2543 KnownFPClass FPClass = computeKnownFPClass(R: Val, InterestedClasses: SNaN ? fcSNan : fcNan);
2544
2545 if (SNaN)
2546 return FPClass.isKnownNever(Mask: fcSNan);
2547
2548 return FPClass.isKnownNeverNaN();
2549}
2550
2551bool GISelValueTracking::isKnownNeverLogicalZero(Register Val, unsigned Depth) {
2552 KnownFPClass Known = computeKnownFPClass(R: Val, InterestedClasses: fcZero | fcSubnormal, Depth);
2553 LLT Ty = MRI.getType(Reg: Val).getScalarType();
2554 return Known.isKnownNeverLogicalZero(
2555 Mode: MF.getDenormalMode(FPType: getFltSemanticForLLT(Ty)));
2556}
2557
2558/// Compute number of sign bits for the intersection of \p Src0 and \p Src1
2559unsigned GISelValueTracking::computeNumSignBitsMin(Register Src0, Register Src1,
2560 const APInt &DemandedElts,
2561 unsigned Depth) {
2562 // Test src1 first, since we canonicalize simpler expressions to the RHS.
2563 unsigned Src1SignBits = computeNumSignBits(R: Src1, DemandedElts, Depth);
2564 if (Src1SignBits == 1)
2565 return 1;
2566 return std::min(a: computeNumSignBits(R: Src0, DemandedElts, Depth), b: Src1SignBits);
2567}
2568
2569/// Compute the known number of sign bits with attached range metadata in the
2570/// memory operand. If this is an extending load, accounts for the behavior of
2571/// the high bits.
2572static unsigned computeNumSignBitsFromRangeMetadata(const GAnyLoad *Ld,
2573 unsigned TyBits) {
2574 const MDNode *Ranges = Ld->getRanges();
2575 if (!Ranges)
2576 return 1;
2577
2578 ConstantRange CR = getConstantRangeFromMetadata(RangeMD: *Ranges);
2579 if (TyBits > CR.getBitWidth()) {
2580 switch (Ld->getOpcode()) {
2581 case TargetOpcode::G_SEXTLOAD:
2582 CR = CR.signExtend(BitWidth: TyBits);
2583 break;
2584 case TargetOpcode::G_ZEXTLOAD:
2585 CR = CR.zeroExtend(BitWidth: TyBits);
2586 break;
2587 default:
2588 break;
2589 }
2590 }
2591
2592 return std::min(a: CR.getSignedMin().getNumSignBits(),
2593 b: CR.getSignedMax().getNumSignBits());
2594}
2595
2596unsigned GISelValueTracking::computeNumSignBits(Register R,
2597 const APInt &DemandedElts,
2598 unsigned Depth) {
2599 MachineInstr &MI = *MRI.getVRegDef(Reg: R);
2600 unsigned Opcode = MI.getOpcode();
2601
2602 if (Opcode == TargetOpcode::G_CONSTANT)
2603 return MI.getOperand(i: 1).getCImm()->getValue().getNumSignBits();
2604
2605 if (Depth == getMaxDepth())
2606 return 1;
2607
2608 if (!DemandedElts)
2609 return 1; // No demanded elts, better to assume we don't know anything.
2610
2611 LLT DstTy = MRI.getType(Reg: R);
2612 const unsigned TyBits = DstTy.getScalarSizeInBits();
2613
2614 // Handle the case where this is called on a register that does not have a
2615 // type constraint. This is unlikely to occur except by looking through copies
2616 // but it is possible for the initial register being queried to be in this
2617 // state.
2618 if (!DstTy.isValid())
2619 return 1;
2620
2621 unsigned FirstAnswer = 1;
2622 switch (Opcode) {
2623 case TargetOpcode::COPY: {
2624 MachineOperand &Src = MI.getOperand(i: 1);
2625 if (Src.getReg().isVirtual() && Src.getSubReg() == 0 &&
2626 MRI.getType(Reg: Src.getReg()).isValid()) {
2627 // Don't increment Depth for this one since we didn't do any work.
2628 return computeNumSignBits(R: Src.getReg(), DemandedElts, Depth);
2629 }
2630
2631 return 1;
2632 }
2633 case TargetOpcode::G_FREEZE: {
2634 Register Src = MI.getOperand(i: 1).getReg();
2635 if (isGuaranteedNotToBeUndefOrPoison(Reg: Src, MRI, Depth: Depth + 1))
2636 return computeNumSignBits(R: Src, DemandedElts, Depth: Depth + 1);
2637 break;
2638 }
2639 case TargetOpcode::G_SEXT: {
2640 Register Src = MI.getOperand(i: 1).getReg();
2641 LLT SrcTy = MRI.getType(Reg: Src);
2642 unsigned Tmp = TyBits - SrcTy.getScalarSizeInBits();
2643 return computeNumSignBits(R: Src, DemandedElts, Depth: Depth + 1) + Tmp;
2644 }
2645 case TargetOpcode::G_ASSERT_SEXT:
2646 case TargetOpcode::G_SEXT_INREG: {
2647 // Max of the input and what this extends.
2648 Register Src = MI.getOperand(i: 1).getReg();
2649 unsigned SrcBits = MI.getOperand(i: 2).getImm();
2650 unsigned InRegBits = TyBits - SrcBits + 1;
2651 return std::max(a: computeNumSignBits(R: Src, DemandedElts, Depth: Depth + 1),
2652 b: InRegBits);
2653 }
2654 case TargetOpcode::G_LOAD: {
2655 GLoad *Ld = cast<GLoad>(Val: &MI);
2656 if (DemandedElts != 1 || !getDataLayout().isLittleEndian())
2657 break;
2658
2659 return computeNumSignBitsFromRangeMetadata(Ld, TyBits);
2660 }
2661 case TargetOpcode::G_SEXTLOAD: {
2662 GSExtLoad *Ld = cast<GSExtLoad>(Val: &MI);
2663
2664 // FIXME: We need an in-memory type representation.
2665 if (DstTy.isVector())
2666 return 1;
2667
2668 unsigned NumBits = computeNumSignBitsFromRangeMetadata(Ld, TyBits);
2669 if (NumBits != 1)
2670 return NumBits;
2671
2672 // e.g. i16->i32 = '17' bits known.
2673 const MachineMemOperand *MMO = *MI.memoperands_begin();
2674 return TyBits - MMO->getSizeInBits().getValue() + 1;
2675 }
2676 case TargetOpcode::G_ZEXTLOAD: {
2677 GZExtLoad *Ld = cast<GZExtLoad>(Val: &MI);
2678
2679 // FIXME: We need an in-memory type representation.
2680 if (DstTy.isVector())
2681 return 1;
2682
2683 unsigned NumBits = computeNumSignBitsFromRangeMetadata(Ld, TyBits);
2684 if (NumBits != 1)
2685 return NumBits;
2686
2687 // e.g. i16->i32 = '16' bits known.
2688 const MachineMemOperand *MMO = *MI.memoperands_begin();
2689 return TyBits - MMO->getSizeInBits().getValue();
2690 }
2691 case TargetOpcode::G_AND:
2692 case TargetOpcode::G_OR:
2693 case TargetOpcode::G_XOR: {
2694 Register Src1 = MI.getOperand(i: 1).getReg();
2695 unsigned Src1NumSignBits =
2696 computeNumSignBits(R: Src1, DemandedElts, Depth: Depth + 1);
2697 if (Src1NumSignBits != 1) {
2698 Register Src2 = MI.getOperand(i: 2).getReg();
2699 unsigned Src2NumSignBits =
2700 computeNumSignBits(R: Src2, DemandedElts, Depth: Depth + 1);
2701 FirstAnswer = std::min(a: Src1NumSignBits, b: Src2NumSignBits);
2702 }
2703 break;
2704 }
2705 case TargetOpcode::G_ASHR: {
2706 Register Src1 = MI.getOperand(i: 1).getReg();
2707 Register Src2 = MI.getOperand(i: 2).getReg();
2708 FirstAnswer = computeNumSignBits(R: Src1, DemandedElts, Depth: Depth + 1);
2709 if (auto C = getValidMinimumShiftAmount(R: Src2, DemandedElts, Depth: Depth + 1))
2710 FirstAnswer = std::min<uint64_t>(a: FirstAnswer + *C, b: TyBits);
2711 break;
2712 }
2713 case TargetOpcode::G_SHL: {
2714 Register Src1 = MI.getOperand(i: 1).getReg();
2715 Register Src2 = MI.getOperand(i: 2).getReg();
2716 if (std::optional<ConstantRange> ShAmtRange =
2717 getValidShiftAmountRange(R: Src2, DemandedElts, Depth: Depth + 1)) {
2718 uint64_t MaxShAmt = ShAmtRange->getUnsignedMax().getZExtValue();
2719 uint64_t MinShAmt = ShAmtRange->getUnsignedMin().getZExtValue();
2720
2721 MachineInstr &ExtMI = *MRI.getVRegDef(Reg: Src1);
2722 unsigned ExtOpc = ExtMI.getOpcode();
2723
2724 // Try to look through ZERO/SIGN/ANY_EXTEND. If all extended bits are
2725 // shifted out, then we can compute the number of sign bits for the
2726 // operand being extended. A future improvement could be to pass along the
2727 // "shifted left by" information in the recursive calls to
2728 // ComputeKnownSignBits. Allowing us to handle this more generically.
2729 if (ExtOpc == TargetOpcode::G_SEXT || ExtOpc == TargetOpcode::G_ZEXT ||
2730 ExtOpc == TargetOpcode::G_ANYEXT) {
2731 LLT ExtTy = MRI.getType(Reg: Src1);
2732 Register Extendee = ExtMI.getOperand(i: 1).getReg();
2733 LLT ExtendeeTy = MRI.getType(Reg: Extendee);
2734 uint64_t SizeDiff =
2735 ExtTy.getScalarSizeInBits() - ExtendeeTy.getScalarSizeInBits();
2736
2737 if (SizeDiff <= MinShAmt) {
2738 unsigned Tmp =
2739 SizeDiff + computeNumSignBits(R: Extendee, DemandedElts, Depth: Depth + 1);
2740 if (MaxShAmt < Tmp)
2741 return Tmp - MaxShAmt;
2742 }
2743 }
2744 // shl destroys sign bits, ensure it doesn't shift out all sign bits.
2745 unsigned Tmp = computeNumSignBits(R: Src1, DemandedElts, Depth: Depth + 1);
2746 if (MaxShAmt < Tmp)
2747 return Tmp - MaxShAmt;
2748 }
2749 break;
2750 }
2751 case TargetOpcode::G_ROTL:
2752 case TargetOpcode::G_ROTR: {
2753 Register SrcReg = MI.getOperand(i: 1).getReg();
2754 unsigned Tmp = computeNumSignBits(R: SrcReg, DemandedElts, Depth: Depth + 1);
2755 auto MaybeAmt =
2756 isConstantOrConstantSplatVector(Def: MI.getOperand(i: 2).getReg(), MRI);
2757 FirstAnswer =
2758 SignBitsOps::rot(SrcSignBits: Tmp, BitWidth: TyBits, RotAmt: MaybeAmt, IsRotateRight: Opcode == TargetOpcode::G_ROTR);
2759 break;
2760 }
2761 case TargetOpcode::G_SAVGFLOOR:
2762 case TargetOpcode::G_SAVGCEIL: {
2763 Register Src1 = MI.getOperand(i: 1).getReg();
2764 Register Src2 = MI.getOperand(i: 2).getReg();
2765 FirstAnswer = computeNumSignBitsMin(Src0: Src1, Src1: Src2, DemandedElts, Depth: Depth + 1);
2766 break;
2767 }
2768 case TargetOpcode::G_SREM: {
2769 // The sign bit is the LHS's sign bit, except when the result of the
2770 // remainder is zero. The magnitude of the result should be less than or
2771 // equal to the magnitude of the LHS. Therefore, the result should have
2772 // at least as many sign bits as the left hand side.
2773 Register Src = MI.getOperand(i: 1).getReg();
2774 return computeNumSignBits(R: Src, DemandedElts, Depth: Depth + 1);
2775 }
2776 case TargetOpcode::G_TRUNC: {
2777 Register Src = MI.getOperand(i: 1).getReg();
2778 LLT SrcTy = MRI.getType(Reg: Src);
2779
2780 // Check if the sign bits of source go down as far as the truncated value.
2781 unsigned NumSrcBits = SrcTy.getScalarSizeInBits();
2782 unsigned NumSrcSignBits = computeNumSignBits(R: Src, DemandedElts, Depth: Depth + 1);
2783 if (NumSrcSignBits > (NumSrcBits - TyBits))
2784 return NumSrcSignBits - (NumSrcBits - TyBits);
2785 break;
2786 }
2787 case TargetOpcode::G_SELECT: {
2788 return computeNumSignBitsMin(Src0: MI.getOperand(i: 2).getReg(),
2789 Src1: MI.getOperand(i: 3).getReg(), DemandedElts,
2790 Depth: Depth + 1);
2791 }
2792 case TargetOpcode::G_SMIN:
2793 case TargetOpcode::G_SMAX:
2794 case TargetOpcode::G_UMIN:
2795 case TargetOpcode::G_UMAX:
2796 // TODO: Handle clamp pattern with number of sign bits for SMIN/SMAX.
2797 return computeNumSignBitsMin(Src0: MI.getOperand(i: 1).getReg(),
2798 Src1: MI.getOperand(i: 2).getReg(), DemandedElts,
2799 Depth: Depth + 1);
2800 case TargetOpcode::G_SADDO:
2801 case TargetOpcode::G_SADDE:
2802 case TargetOpcode::G_UADDO:
2803 case TargetOpcode::G_UADDE:
2804 case TargetOpcode::G_SSUBO:
2805 case TargetOpcode::G_SSUBE:
2806 case TargetOpcode::G_USUBO:
2807 case TargetOpcode::G_USUBE:
2808 case TargetOpcode::G_SMULO:
2809 case TargetOpcode::G_UMULO: {
2810 // If compares returns 0/-1, all bits are sign bits.
2811 // We know that we have an integer-based boolean since these operations
2812 // are only available for integer.
2813 if (MI.getOperand(i: 1).getReg() == R) {
2814 if (TL.getBooleanContents(isVec: DstTy.isVector(), isFloat: false) ==
2815 TargetLowering::ZeroOrNegativeOneBooleanContent)
2816 return TyBits;
2817 }
2818
2819 break;
2820 }
2821 case TargetOpcode::G_SUB: {
2822 Register Src2 = MI.getOperand(i: 2).getReg();
2823 unsigned Src2NumSignBits =
2824 computeNumSignBits(R: Src2, DemandedElts, Depth: Depth + 1);
2825 if (Src2NumSignBits == 1)
2826 return 1; // Early out.
2827
2828 // Handle NEG.
2829 Register Src1 = MI.getOperand(i: 1).getReg();
2830 KnownBits Known1 = getKnownBits(R: Src1, DemandedElts, Depth);
2831 if (Known1.isZero()) {
2832 KnownBits Known2 = getKnownBits(R: Src2, DemandedElts, Depth);
2833 // If the input is known to be 0 or 1, the output is 0/-1, which is all
2834 // sign bits set.
2835 if ((Known2.Zero | 1).isAllOnes())
2836 return TyBits;
2837
2838 // If the input is known to be positive (the sign bit is known clear),
2839 // the output of the NEG has, at worst, the same number of sign bits as
2840 // the input.
2841 if (Known2.isNonNegative()) {
2842 FirstAnswer = Src2NumSignBits;
2843 break;
2844 }
2845
2846 // Otherwise, we treat this like a SUB.
2847 }
2848
2849 unsigned Src1NumSignBits =
2850 computeNumSignBits(R: Src1, DemandedElts, Depth: Depth + 1);
2851 if (Src1NumSignBits == 1)
2852 return 1; // Early Out.
2853
2854 // Sub can have at most one carry bit. Thus we know that the output
2855 // is, at worst, one more bit than the inputs.
2856 FirstAnswer = std::min(a: Src1NumSignBits, b: Src2NumSignBits) - 1;
2857 break;
2858 }
2859 case TargetOpcode::G_ADD: {
2860 Register Src2 = MI.getOperand(i: 2).getReg();
2861 unsigned Src2NumSignBits =
2862 computeNumSignBits(R: Src2, DemandedElts, Depth: Depth + 1);
2863 if (Src2NumSignBits <= 2)
2864 return 1; // Early out.
2865
2866 Register Src1 = MI.getOperand(i: 1).getReg();
2867 unsigned Src1NumSignBits =
2868 computeNumSignBits(R: Src1, DemandedElts, Depth: Depth + 1);
2869 if (Src1NumSignBits == 1)
2870 return 1; // Early Out.
2871
2872 // Special case decrementing a value (ADD X, -1):
2873 KnownBits Known2 = getKnownBits(R: Src2, DemandedElts, Depth);
2874 if (Known2.isAllOnes()) {
2875 KnownBits Known1 = getKnownBits(R: Src1, DemandedElts, Depth);
2876 // If the input is known to be 0 or 1, the output is 0/-1, which is all
2877 // sign bits set.
2878 if ((Known1.Zero | 1).isAllOnes())
2879 return TyBits;
2880
2881 // If we are subtracting one from a positive number, there is no carry
2882 // out of the result.
2883 if (Known1.isNonNegative()) {
2884 FirstAnswer = Src1NumSignBits;
2885 break;
2886 }
2887
2888 // Otherwise, we treat this like an ADD.
2889 }
2890
2891 // Add can have at most one carry bit. Thus we know that the output
2892 // is, at worst, one more bit than the inputs.
2893 FirstAnswer = std::min(a: Src1NumSignBits, b: Src2NumSignBits) - 1;
2894 break;
2895 }
2896 case TargetOpcode::G_MUL: {
2897 unsigned Src2NumSignBits =
2898 computeNumSignBits(R: MI.getOperand(i: 2).getReg(), DemandedElts, Depth: Depth + 1);
2899 if (Src2NumSignBits == 1)
2900 break;
2901 unsigned Src1NumSignBits =
2902 computeNumSignBits(R: MI.getOperand(i: 1).getReg(), DemandedElts, Depth: Depth + 1);
2903 if (Src1NumSignBits == 1)
2904 break;
2905
2906 // The product needs at most the sum of the operands' signed widths.
2907 unsigned OutValidBits =
2908 (TyBits - Src1NumSignBits + 1) + (TyBits - Src2NumSignBits + 1);
2909 if (OutValidBits <= TyBits)
2910 FirstAnswer = TyBits - OutValidBits + 1;
2911 break;
2912 }
2913 case TargetOpcode::G_FCMP:
2914 case TargetOpcode::G_ICMP: {
2915 bool IsFP = Opcode == TargetOpcode::G_FCMP;
2916 if (TyBits == 1)
2917 break;
2918 auto BC = TL.getBooleanContents(isVec: DstTy.isVector(), isFloat: IsFP);
2919 if (BC == TargetLoweringBase::ZeroOrNegativeOneBooleanContent)
2920 return TyBits; // All bits are sign bits.
2921 if (BC == TargetLowering::ZeroOrOneBooleanContent)
2922 return TyBits - 1; // Every always-zero bit is a sign bit.
2923 break;
2924 }
2925 case TargetOpcode::G_UNMERGE_VALUES: {
2926 unsigned NumOps = MI.getNumOperands();
2927 Register SrcReg = MI.getOperand(i: NumOps - 1).getReg();
2928 LLT SrcTy = MRI.getType(Reg: SrcReg);
2929
2930 if ((SrcTy.isVector() && SrcTy.getScalarType() != DstTy.getScalarType()) ||
2931 (SrcTy.isScalar() && DstTy.isVector()))
2932 break;
2933
2934 // Figure out the result operand index
2935 unsigned DstIdx = MI.findRegisterDefOperandIdx(Reg: R, TRI: nullptr);
2936
2937 APInt SubDemandedElts = DemandedElts;
2938 unsigned DstLanes = DstTy.isVector() ? DstTy.getNumElements() : 1;
2939 if (SrcTy.isVector()) {
2940 SubDemandedElts =
2941 DemandedElts.zext(width: SrcTy.getNumElements()).shl(shiftAmt: DstIdx * DstLanes);
2942 }
2943
2944 unsigned SrcOpKnown =
2945 computeNumSignBits(R: SrcReg, DemandedElts: SubDemandedElts, Depth: Depth + 1);
2946 if (SrcTy.isVector()) {
2947 FirstAnswer = SrcOpKnown;
2948 } else if (SrcOpKnown >= (MI.getNumOperands() - DstIdx - 2) * TyBits) {
2949 FirstAnswer = SrcOpKnown >= (MI.getNumOperands() - DstIdx - 1) * TyBits
2950 ? TyBits
2951 : SrcOpKnown % TyBits;
2952 }
2953 break;
2954 }
2955 case TargetOpcode::G_BUILD_VECTOR: {
2956 // Collect the known bits that are shared by every demanded vector element.
2957 FirstAnswer = TyBits;
2958 APInt SingleDemandedElt(1, 1);
2959 for (const auto &[I, MO] : enumerate(First: drop_begin(RangeOrContainer: MI.operands()))) {
2960 if (!DemandedElts[I])
2961 continue;
2962
2963 unsigned Tmp2 =
2964 computeNumSignBits(R: MO.getReg(), DemandedElts: SingleDemandedElt, Depth: Depth + 1);
2965 FirstAnswer = std::min(a: FirstAnswer, b: Tmp2);
2966
2967 // If we don't know any bits, early out.
2968 if (FirstAnswer == 1)
2969 break;
2970 }
2971 break;
2972 }
2973 case TargetOpcode::G_CONCAT_VECTORS: {
2974 if (MRI.getType(Reg: MI.getOperand(i: 0).getReg()).isScalableVector())
2975 break;
2976 FirstAnswer = TyBits;
2977 // Determine the minimum number of sign bits across all demanded
2978 // elts of the input vectors. Early out if the result is already 1.
2979 unsigned NumSubVectorElts =
2980 MRI.getType(Reg: MI.getOperand(i: 1).getReg()).getNumElements();
2981 for (const auto &[I, MO] : enumerate(First: drop_begin(RangeOrContainer: MI.operands()))) {
2982 APInt DemandedSub =
2983 DemandedElts.extractBits(numBits: NumSubVectorElts, bitPosition: I * NumSubVectorElts);
2984 if (!DemandedSub)
2985 continue;
2986 unsigned Tmp2 = computeNumSignBits(R: MO.getReg(), DemandedElts: DemandedSub, Depth: Depth + 1);
2987
2988 FirstAnswer = std::min(a: FirstAnswer, b: Tmp2);
2989
2990 // If we don't know any bits, early out.
2991 if (FirstAnswer == 1)
2992 break;
2993 }
2994 break;
2995 }
2996 case TargetOpcode::G_VECTOR_COMPRESS: {
2997 // Each result lane is either a lane of the source vector or the passthru,
2998 // so the number of sign bits is the minimum of the two.
2999 Register Vec = MI.getOperand(i: 1).getReg();
3000 Register PassThru = MI.getOperand(i: 3).getReg();
3001 unsigned Tmp = computeNumSignBits(R: PassThru, DemandedElts, Depth: Depth + 1);
3002 // If passthru contributes nothing, fall back to the KnownBits refinement.
3003 if (Tmp == 1)
3004 break;
3005 // Compression can move any source lane to any result position, so all
3006 // source lanes are demanded.
3007 APInt DemandedSrcElts = APInt::getAllOnes(numBits: DemandedElts.getBitWidth());
3008 unsigned Tmp2 = computeNumSignBits(R: Vec, DemandedElts: DemandedSrcElts, Depth: Depth + 1);
3009 FirstAnswer = std::min(a: Tmp, b: Tmp2);
3010 break;
3011 }
3012 case TargetOpcode::G_INSERT_VECTOR_ELT: {
3013 GInsertVectorElement &Insert = cast<GInsertVectorElement>(Val&: MI);
3014 Register InVec = Insert.getVectorReg();
3015 Register InVal = Insert.getElementReg();
3016 LLT VecVT = MRI.getType(Reg: InVec);
3017
3018 // If we know the element index, split the demand between the inserted
3019 // value and the source vector, otherwise assume we need both. Scalable
3020 // vectors carry no per-lane demand, so they always take the minimum of the
3021 // whole vector and the inserted value.
3022 bool DemandedVal = true;
3023 APInt DemandedVecElts = DemandedElts;
3024 if (!VecVT.isScalableVector()) {
3025 unsigned NumElts = VecVT.getNumElements();
3026 auto ConstEltNo = getIConstantVRegVal(VReg: Insert.getIndexReg(), MRI);
3027 if (ConstEltNo && ConstEltNo->ult(RHS: NumElts)) {
3028 unsigned EltIdx = ConstEltNo->getZExtValue();
3029 DemandedVal = !!DemandedElts[EltIdx];
3030 DemandedVecElts.clearBit(BitPosition: EltIdx);
3031 }
3032 }
3033
3034 unsigned Tmp = TyBits;
3035 if (DemandedVal) {
3036 // TODO: Handle implicit truncation of inserted elements.
3037 if (MRI.getType(Reg: InVal).getSizeInBits() != TyBits)
3038 break;
3039 unsigned ValSignBits = computeNumSignBits(R: InVal, DemandedElts: APInt(1, 1), Depth: Depth + 1);
3040 Tmp = std::min(a: Tmp, b: ValSignBits);
3041 }
3042 if (!!DemandedVecElts) {
3043 unsigned VecSignBits =
3044 computeNumSignBits(R: InVec, DemandedElts: DemandedVecElts, Depth: Depth + 1);
3045 Tmp = std::min(a: Tmp, b: VecSignBits);
3046 }
3047 return Tmp;
3048 }
3049 case TargetOpcode::G_EXTRACT_VECTOR_ELT: {
3050 GExtractVectorElement &Extract = cast<GExtractVectorElement>(Val&: MI);
3051 Register InVec = Extract.getVectorReg();
3052 Register EltNo = Extract.getIndexReg();
3053 LLT VecVT = MRI.getType(Reg: InVec);
3054 if (VecVT.isScalableVector())
3055 return computeNumSignBits(R: InVec, DemandedElts: APInt(1, 1), Depth: Depth + 1);
3056 unsigned NumSrcElts = VecVT.getNumElements();
3057 std::optional<APInt> ConstEltNo = getIConstantVRegVal(VReg: EltNo, MRI);
3058 APInt DemandedSrcElts =
3059 ConstEltNo && ConstEltNo->ult(RHS: NumSrcElts)
3060 ? APInt::getOneBitSet(numBits: NumSrcElts, BitNo: ConstEltNo->getZExtValue())
3061 : APInt::getAllOnes(numBits: NumSrcElts);
3062 return computeNumSignBits(R: InVec, DemandedElts: DemandedSrcElts, Depth: Depth + 1);
3063 }
3064 case TargetOpcode::G_EXTRACT_SUBVECTOR: {
3065 // Offset the demanded elts by the subvector index.
3066 Register SrcReg = MI.getOperand(i: 1).getReg();
3067 LLT SrcTy = MRI.getType(Reg: SrcReg);
3068 APInt DemandedSrcElts;
3069 if (SrcTy.isScalableVector()) {
3070 DemandedSrcElts = APInt(1, 1);
3071 } else {
3072 uint64_t Idx = MI.getOperand(i: 2).getImm();
3073 unsigned NumSrcElts = SrcTy.getNumElements();
3074 DemandedSrcElts = DemandedElts.zext(width: NumSrcElts).shl(shiftAmt: Idx);
3075 }
3076 return computeNumSignBits(R: SrcReg, DemandedElts: DemandedSrcElts, Depth: Depth + 1);
3077 }
3078 case TargetOpcode::G_SHUFFLE_VECTOR: {
3079 // Collect the minimum number of sign bits that are shared by every vector
3080 // element referenced by the shuffle.
3081 APInt DemandedLHS, DemandedRHS;
3082 Register Src1 = MI.getOperand(i: 1).getReg();
3083 unsigned NumElts = MRI.getType(Reg: Src1).getNumElements();
3084 if (!getShuffleDemandedElts(SrcWidth: NumElts, Mask: MI.getOperand(i: 3).getShuffleMask(),
3085 DemandedElts, DemandedLHS, DemandedRHS))
3086 return 1;
3087
3088 if (!!DemandedLHS)
3089 FirstAnswer = computeNumSignBits(R: Src1, DemandedElts: DemandedLHS, Depth: Depth + 1);
3090 // If we don't know anything, early out and try computeKnownBits fall-back.
3091 if (FirstAnswer == 1)
3092 break;
3093 if (!!DemandedRHS) {
3094 unsigned Tmp2 =
3095 computeNumSignBits(R: MI.getOperand(i: 2).getReg(), DemandedElts: DemandedRHS, Depth: Depth + 1);
3096 FirstAnswer = std::min(a: FirstAnswer, b: Tmp2);
3097 }
3098 break;
3099 }
3100 case TargetOpcode::G_SPLAT_VECTOR: {
3101 // Check if the sign bits of source go down as far as the truncated value.
3102 Register Src = MI.getOperand(i: 1).getReg();
3103 unsigned NumSrcSignBits = computeNumSignBits(R: Src, DemandedElts: APInt(1, 1), Depth: Depth + 1);
3104 unsigned NumSrcBits = MRI.getType(Reg: Src).getSizeInBits();
3105 if (NumSrcSignBits > (NumSrcBits - TyBits))
3106 return NumSrcSignBits - (NumSrcBits - TyBits);
3107 break;
3108 }
3109 case TargetOpcode::G_INTRINSIC:
3110 case TargetOpcode::G_INTRINSIC_W_SIDE_EFFECTS:
3111 case TargetOpcode::G_INTRINSIC_CONVERGENT:
3112 case TargetOpcode::G_INTRINSIC_CONVERGENT_W_SIDE_EFFECTS:
3113 default: {
3114 unsigned NumBits =
3115 TL.computeNumSignBitsForTargetInstr(Analysis&: *this, R, DemandedElts, MRI, Depth);
3116 if (NumBits > 1)
3117 FirstAnswer = std::max(a: FirstAnswer, b: NumBits);
3118 break;
3119 }
3120 }
3121
3122 // Finally, if we can prove that the top bits of the result are 0's or 1's,
3123 // use this information.
3124 KnownBits Known = getKnownBits(R, DemandedElts, Depth);
3125 return std::max(a: FirstAnswer, b: Known.countMinSignBits());
3126}
3127
3128unsigned GISelValueTracking::computeNumSignBits(Register R, unsigned Depth) {
3129 LLT Ty = MRI.getType(Reg: R);
3130 APInt DemandedElts =
3131 Ty.isFixedVector() ? APInt::getAllOnes(numBits: Ty.getNumElements()) : APInt(1, 1);
3132 return computeNumSignBits(R, DemandedElts, Depth);
3133}
3134
3135std::optional<ConstantRange> GISelValueTracking::getValidShiftAmountRange(
3136 Register R, const APInt &DemandedElts, unsigned Depth) {
3137 // Shifting more than the bitwidth is not valid.
3138 MachineInstr &MI = *MRI.getVRegDef(Reg: R);
3139 unsigned Opcode = MI.getOpcode();
3140
3141 LLT Ty = MRI.getType(Reg: R);
3142 unsigned BitWidth = Ty.getScalarSizeInBits();
3143
3144 if (Opcode == TargetOpcode::G_CONSTANT) {
3145 const APInt &ShAmt = MI.getOperand(i: 1).getCImm()->getValue();
3146 if (ShAmt.uge(RHS: BitWidth))
3147 return std::nullopt;
3148 return ConstantRange(ShAmt);
3149 }
3150
3151 if (Opcode == TargetOpcode::G_BUILD_VECTOR) {
3152 const APInt *MinAmt = nullptr, *MaxAmt = nullptr;
3153 for (unsigned I = 0, E = MI.getNumOperands() - 1; I != E; ++I) {
3154 if (!DemandedElts[I])
3155 continue;
3156 MachineInstr *Op = MRI.getVRegDef(Reg: MI.getOperand(i: I + 1).getReg());
3157 if (Op->getOpcode() != TargetOpcode::G_CONSTANT) {
3158 MinAmt = MaxAmt = nullptr;
3159 break;
3160 }
3161
3162 const APInt &ShAmt = Op->getOperand(i: 1).getCImm()->getValue();
3163 if (ShAmt.uge(RHS: BitWidth))
3164 return std::nullopt;
3165 if (!MinAmt || MinAmt->ugt(RHS: ShAmt))
3166 MinAmt = &ShAmt;
3167 if (!MaxAmt || MaxAmt->ult(RHS: ShAmt))
3168 MaxAmt = &ShAmt;
3169 }
3170 assert(((!MinAmt && !MaxAmt) || (MinAmt && MaxAmt)) &&
3171 "Failed to find matching min/max shift amounts");
3172 if (MinAmt && MaxAmt)
3173 return ConstantRange(*MinAmt, *MaxAmt + 1);
3174 }
3175
3176 // Use computeKnownBits to find a hidden constant/knownbits (usually type
3177 // legalized). e.g. Hidden behind multiple bitcasts/build_vector/casts etc.
3178 KnownBits KnownAmt = getKnownBits(R, DemandedElts, Depth);
3179 if (KnownAmt.getMaxValue().ult(RHS: BitWidth))
3180 return ConstantRange::fromKnownBits(Known: KnownAmt, /*IsSigned=*/false);
3181
3182 return std::nullopt;
3183}
3184
3185std::optional<uint64_t> GISelValueTracking::getValidMinimumShiftAmount(
3186 Register R, const APInt &DemandedElts, unsigned Depth) {
3187 if (std::optional<ConstantRange> AmtRange =
3188 getValidShiftAmountRange(R, DemandedElts, Depth))
3189 return AmtRange->getUnsignedMin().getZExtValue();
3190 return std::nullopt;
3191}
3192
3193void GISelValueTrackingAnalysisLegacy::getAnalysisUsage(
3194 AnalysisUsage &AU) const {
3195 AU.setPreservesAll();
3196 MachineFunctionPass::getAnalysisUsage(AU);
3197}
3198
3199bool GISelValueTrackingAnalysisLegacy::runOnMachineFunction(
3200 MachineFunction &MF) {
3201 return false;
3202}
3203
3204GISelValueTracking &GISelValueTrackingAnalysisLegacy::get(MachineFunction &MF) {
3205 if (!Info) {
3206 unsigned MaxDepth =
3207 MF.getTarget().getOptLevel() == CodeGenOptLevel::None ? 2 : 6;
3208 Info = std::make_unique<GISelValueTracking>(args&: MF, args&: MaxDepth);
3209 }
3210 return *Info;
3211}
3212
3213AnalysisKey GISelValueTrackingAnalysis::Key;
3214
3215GISelValueTrackingAnalysis::Result
3216GISelValueTrackingAnalysis::run(MachineFunction &MF,
3217 MachineFunctionAnalysisManager &MFAM) {
3218 unsigned MaxDepth =
3219 MF.getTarget().getOptLevel() == CodeGenOptLevel::None ? 2 : 6;
3220 return Result(MF, MaxDepth);
3221}
3222
3223static PreservedAnalyses
3224printGISelValueTracking(MachineFunction &MF,
3225 MachineFunctionAnalysisManager &MFAM, raw_ostream &OS,
3226 bool PrintFPClass) {
3227 auto &VTA = MFAM.getResult<GISelValueTrackingAnalysis>(IR&: MF);
3228 const auto &MRI = MF.getRegInfo();
3229 OS << "name: ";
3230 MF.getFunction().printAsOperand(O&: OS, /*PrintType=*/false);
3231 OS << '\n';
3232
3233 for (MachineBasicBlock &BB : MF) {
3234 for (MachineInstr &MI : BB) {
3235 for (MachineOperand &MO : MI.defs()) {
3236 if (!MO.isReg() || MO.getReg().isPhysical())
3237 continue;
3238 Register Reg = MO.getReg();
3239 if (!MRI.getType(Reg).isValid())
3240 continue;
3241 if (PrintFPClass) {
3242 KnownFPClass FPKnown = VTA.computeKnownFPClass(R: Reg);
3243 OS << " " << MO << " FPClasses:" << FPKnown.getKnownFPClasses()
3244 << " SignBitKnown:";
3245 if (FPKnown.getSignBit())
3246 OS << (*FPKnown.getSignBit() ? '1' : '0');
3247 else
3248 OS << '?';
3249 OS << '\n';
3250 } else {
3251 KnownBits Known = VTA.getKnownBits(R: Reg);
3252 unsigned SignedBits = VTA.computeNumSignBits(R: Reg);
3253 bool IsKnownNeverZero = VTA.isKnownNeverZero(R: Reg);
3254 OS << " " << MO << " KnownBits:" << Known
3255 << " SignBits:" << SignedBits
3256 << " IsKnownNeverZero:" << IsKnownNeverZero << '\n';
3257 }
3258 };
3259 }
3260 }
3261 return PreservedAnalyses::all();
3262}
3263
3264PreservedAnalyses
3265GISelValueTrackingPrinterPass::run(MachineFunction &MF,
3266 MachineFunctionAnalysisManager &MFAM) {
3267 return printGISelValueTracking(MF, MFAM, OS, PrintFPClass: false);
3268}
3269
3270PreservedAnalyses GISelValueTrackingFPClassPrinterPass::run(
3271 MachineFunction &MF, MachineFunctionAnalysisManager &MFAM) {
3272 return printGISelValueTracking(MF, MFAM, OS, PrintFPClass: true);
3273}
3274