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 OffsetKnown = OffsetKnown.sext(BitWidth);
942 WidthKnown = WidthKnown.sext(BitWidth);
943 Known = extractBits(BitWidth, SrcOpKnown, OffsetKnown, WidthKnown);
944 // Sign extend the extracted value using shift left and arithmetic shift
945 // right.
946 KnownBits ExtKnown = KnownBits::makeConstant(C: APInt(BitWidth, BitWidth));
947 KnownBits ShiftKnown = KnownBits::sub(LHS: ExtKnown, RHS: WidthKnown);
948 Known = KnownBits::ashr(LHS: KnownBits::shl(LHS: Known, RHS: ShiftKnown), RHS: ShiftKnown);
949 break;
950 }
951 case TargetOpcode::G_UADDO:
952 case TargetOpcode::G_UADDE:
953 case TargetOpcode::G_SADDO:
954 case TargetOpcode::G_SADDE: {
955 if (MI.getOperand(i: 1).getReg() == R) {
956 // If we know the result of a compare has the top bits zero, use this
957 // info.
958 if (TL.getBooleanContents(isVec: DstTy.isVector(), isFloat: false) ==
959 TargetLowering::ZeroOrOneBooleanContent &&
960 BitWidth > 1)
961 Known.Zero.setBitsFrom(1);
962 break;
963 }
964
965 assert(MI.getOperand(0).getReg() == R &&
966 "We only compute knownbits for the sum here.");
967 // With [US]ADDE, a carry bit may be added in.
968 KnownBits Carry(1);
969 if (Opcode == TargetOpcode::G_UADDE || Opcode == TargetOpcode::G_SADDE) {
970 computeKnownBitsImpl(R: MI.getOperand(i: 4).getReg(), Known&: Carry, DemandedElts,
971 Depth: Depth + 1);
972 // Carry has bit width 1
973 Carry = Carry.trunc(BitWidth: 1);
974 } else {
975 Carry.setAllZero();
976 }
977
978 computeKnownBitsImpl(R: MI.getOperand(i: 2).getReg(), Known, DemandedElts,
979 Depth: Depth + 1);
980 computeKnownBitsImpl(R: MI.getOperand(i: 3).getReg(), Known&: Known2, DemandedElts,
981 Depth: Depth + 1);
982 Known = KnownBits::computeForAddCarry(LHS: Known, RHS: Known2, Carry);
983 break;
984 }
985 case TargetOpcode::G_USUBO:
986 case TargetOpcode::G_USUBE:
987 case TargetOpcode::G_SSUBO:
988 case TargetOpcode::G_SSUBE:
989 case TargetOpcode::G_UMULO:
990 case TargetOpcode::G_SMULO: {
991 if (MI.getOperand(i: 1).getReg() == R) {
992 // If we know the result of a compare has the top bits zero, use this
993 // info.
994 if (TL.getBooleanContents(isVec: DstTy.isVector(), isFloat: false) ==
995 TargetLowering::ZeroOrOneBooleanContent &&
996 BitWidth > 1)
997 Known.Zero.setBitsFrom(1);
998 }
999 break;
1000 }
1001 case TargetOpcode::G_CTTZ:
1002 case TargetOpcode::G_CTTZ_ZERO_POISON: {
1003 KnownBits SrcOpKnown;
1004 computeKnownBitsImpl(R: MI.getOperand(i: 1).getReg(), Known&: SrcOpKnown, DemandedElts,
1005 Depth: Depth + 1);
1006 // If we have a known 1, its position is our upper bound
1007 unsigned PossibleTZ = SrcOpKnown.countMaxTrailingZeros();
1008 unsigned LowBits = llvm::bit_width(Value: PossibleTZ);
1009 Known.Zero.setBitsFrom(LowBits);
1010 break;
1011 }
1012 case TargetOpcode::G_CTLZ:
1013 case TargetOpcode::G_CTLZ_ZERO_POISON: {
1014 KnownBits SrcOpKnown;
1015 computeKnownBitsImpl(R: MI.getOperand(i: 1).getReg(), Known&: SrcOpKnown, DemandedElts,
1016 Depth: Depth + 1);
1017 // If we have a known 1, its position is our upper bound.
1018 unsigned PossibleLZ = SrcOpKnown.countMaxLeadingZeros();
1019 unsigned LowBits = llvm::bit_width(Value: PossibleLZ);
1020 Known.Zero.setBitsFrom(LowBits);
1021 break;
1022 }
1023 case TargetOpcode::G_CTLS: {
1024 Register Reg = MI.getOperand(i: 1).getReg();
1025 unsigned MinRedundantSignBits =
1026 computeNumSignBits(R: Reg, DemandedElts, Depth: Depth + 1) - 1;
1027
1028 unsigned MaxUpperRedundantSignBits = MRI.getType(Reg).getScalarSizeInBits();
1029
1030 ConstantRange Range(APInt(BitWidth, MinRedundantSignBits),
1031 APInt(BitWidth, MaxUpperRedundantSignBits));
1032
1033 Known = Range.toKnownBits();
1034 break;
1035 }
1036 case TargetOpcode::G_EXTRACT_VECTOR_ELT: {
1037 GExtractVectorElement &Extract = cast<GExtractVectorElement>(Val&: MI);
1038 Register InVec = Extract.getVectorReg();
1039 Register EltNo = Extract.getIndexReg();
1040
1041 auto ConstEltNo = getIConstantVRegVal(VReg: EltNo, MRI);
1042
1043 LLT VecVT = MRI.getType(Reg: InVec);
1044 // computeKnownBits not yet implemented for scalable vectors.
1045 if (VecVT.isScalableVector())
1046 break;
1047
1048 const unsigned EltBitWidth = VecVT.getScalarSizeInBits();
1049 const unsigned NumSrcElts = VecVT.getNumElements();
1050 // A return type different from the vector's element type may lead to
1051 // issues with pattern selection. Bail out to avoid that.
1052 if (BitWidth > EltBitWidth)
1053 break;
1054
1055 Known.Zero.setAllBits();
1056 Known.One.setAllBits();
1057
1058 // If we know the element index, just demand that vector element, else for
1059 // an unknown element index, ignore DemandedElts and demand them all.
1060 APInt DemandedSrcElts = APInt::getAllOnes(numBits: NumSrcElts);
1061 if (ConstEltNo && ConstEltNo->ult(RHS: NumSrcElts))
1062 DemandedSrcElts =
1063 APInt::getOneBitSet(numBits: NumSrcElts, BitNo: ConstEltNo->getZExtValue());
1064
1065 computeKnownBitsImpl(R: InVec, Known, DemandedElts: DemandedSrcElts, Depth: Depth + 1);
1066 break;
1067 }
1068 case TargetOpcode::G_INSERT_VECTOR_ELT: {
1069 GInsertVectorElement &Insert = cast<GInsertVectorElement>(Val&: MI);
1070 Register InVec = Insert.getVectorReg();
1071 Register InVal = Insert.getElementReg();
1072 Register EltNo = Insert.getIndexReg();
1073 LLT VecVT = MRI.getType(Reg: InVec);
1074
1075 if (VecVT.isScalableVector())
1076 break;
1077
1078 auto ConstEltNo = getIConstantVRegVal(VReg: EltNo, MRI);
1079 unsigned NumElts = VecVT.getNumElements();
1080
1081 bool DemandedVal = true;
1082 APInt DemandedVecElts = DemandedElts;
1083 if (ConstEltNo && ConstEltNo->ult(RHS: NumElts)) {
1084 unsigned EltIdx = ConstEltNo->getZExtValue();
1085 DemandedVal = !!DemandedElts[EltIdx];
1086 DemandedVecElts.clearBit(BitPosition: EltIdx);
1087 }
1088 Known.setAllConflict();
1089 if (DemandedVal) {
1090 computeKnownBitsImpl(R: InVal, Known&: Known2, DemandedElts: APInt(1, 1), Depth: Depth + 1);
1091 Known = Known.intersectWith(RHS: Known2.zextOrTrunc(BitWidth));
1092 }
1093 if (!!DemandedVecElts) {
1094 computeKnownBitsImpl(R: InVec, Known&: Known2, DemandedElts: DemandedVecElts, Depth: Depth + 1);
1095 Known = Known.intersectWith(RHS: Known2);
1096 }
1097 break;
1098 }
1099 case TargetOpcode::G_INSERT_SUBVECTOR: {
1100 GInsertSubvector &Insert = cast<GInsertSubvector>(Val&: MI);
1101 Register Src = Insert.getBigVec();
1102 Register Sub = Insert.getSubVec();
1103 uint64_t Idx = Insert.getIndexImm();
1104 LLT SrcTy = MRI.getType(Reg: Src);
1105 LLT SubTy = MRI.getType(Reg: Sub);
1106 APInt DemandedSubElts;
1107 APInt DemandedSrcElts;
1108
1109 if (SrcTy.isScalableVector()) {
1110 DemandedSubElts = SubTy.isScalableVector()
1111 ? APInt(1, 1)
1112 : APInt::getAllOnes(numBits: SubTy.getNumElements());
1113 DemandedSrcElts = APInt(1, 1);
1114 } else {
1115 unsigned NumSubElts = SubTy.getNumElements();
1116 DemandedSubElts = DemandedElts.extractBits(numBits: NumSubElts, bitPosition: Idx);
1117 DemandedSrcElts = DemandedElts;
1118 DemandedSrcElts.clearBits(LoBit: Idx, HiBit: Idx + NumSubElts);
1119 }
1120
1121 Known.setAllConflict();
1122 if (!!DemandedSubElts) {
1123 computeKnownBitsImpl(R: Sub, Known&: Known2, DemandedElts: DemandedSubElts, Depth: Depth + 1);
1124 Known = Known.intersectWith(RHS: Known2);
1125 if (Known.isUnknown())
1126 break;
1127 }
1128
1129 if (!!DemandedSrcElts) {
1130 computeKnownBitsImpl(R: Src, Known&: Known2, DemandedElts: DemandedSrcElts, Depth: Depth + 1);
1131 Known = Known.intersectWith(RHS: Known2);
1132 }
1133
1134 break;
1135 }
1136 case TargetOpcode::G_EXTRACT_SUBVECTOR: {
1137 Register SrcReg = MI.getOperand(i: 1).getReg();
1138 LLT SrcTy = MRI.getType(Reg: SrcReg);
1139 APInt DemandedSrcElts;
1140 if (SrcTy.isScalableVector()) {
1141 DemandedSrcElts = APInt(1, 1);
1142 } else {
1143 uint64_t Idx = MI.getOperand(i: 2).getImm();
1144 unsigned NumSrcElts = SrcTy.getNumElements();
1145 DemandedSrcElts = DemandedElts.zext(width: NumSrcElts).shl(shiftAmt: Idx);
1146 }
1147 computeKnownBitsImpl(R: SrcReg, Known, DemandedElts: DemandedSrcElts, Depth: Depth + 1);
1148 break;
1149 }
1150 case TargetOpcode::G_SHUFFLE_VECTOR: {
1151 APInt DemandedLHS, DemandedRHS;
1152 // Collect the known bits that are shared by every vector element referenced
1153 // by the shuffle.
1154 unsigned NumElts = MRI.getType(Reg: MI.getOperand(i: 1).getReg()).getNumElements();
1155 if (!getShuffleDemandedElts(SrcWidth: NumElts, Mask: MI.getOperand(i: 3).getShuffleMask(),
1156 DemandedElts, DemandedLHS, DemandedRHS))
1157 break;
1158
1159 // Known bits are the values that are shared by every demanded element.
1160 Known.Zero.setAllBits();
1161 Known.One.setAllBits();
1162 if (!!DemandedLHS) {
1163 computeKnownBitsImpl(R: MI.getOperand(i: 1).getReg(), Known&: Known2, DemandedElts: DemandedLHS,
1164 Depth: Depth + 1);
1165 Known = Known.intersectWith(RHS: Known2);
1166 }
1167 // If we don't know any bits, early out.
1168 if (Known.isUnknown())
1169 break;
1170 if (!!DemandedRHS) {
1171 computeKnownBitsImpl(R: MI.getOperand(i: 2).getReg(), Known&: Known2, DemandedElts: DemandedRHS,
1172 Depth: Depth + 1);
1173 Known = Known.intersectWith(RHS: Known2);
1174 }
1175 break;
1176 }
1177 case TargetOpcode::G_CONCAT_VECTORS: {
1178 if (MRI.getType(Reg: MI.getOperand(i: 0).getReg()).isScalableVector())
1179 break;
1180 // Split DemandedElts and test each of the demanded subvectors.
1181 Known.Zero.setAllBits();
1182 Known.One.setAllBits();
1183 unsigned NumSubVectorElts =
1184 MRI.getType(Reg: MI.getOperand(i: 1).getReg()).getNumElements();
1185
1186 for (const auto &[I, MO] : enumerate(First: drop_begin(RangeOrContainer: MI.operands()))) {
1187 APInt DemandedSub =
1188 DemandedElts.extractBits(numBits: NumSubVectorElts, bitPosition: I * NumSubVectorElts);
1189 if (!!DemandedSub) {
1190 computeKnownBitsImpl(R: MO.getReg(), Known&: Known2, DemandedElts: DemandedSub, Depth: Depth + 1);
1191
1192 Known = Known.intersectWith(RHS: Known2);
1193 }
1194 // If we don't know any bits, early out.
1195 if (Known.isUnknown())
1196 break;
1197 }
1198 break;
1199 }
1200 case TargetOpcode::G_VECTOR_COMPRESS: {
1201 // Each result lane is either a lane of the source vector or the passthru,
1202 // so the known bits are those shared by both.
1203 Register Vec = MI.getOperand(i: 1).getReg();
1204 Register PassThru = MI.getOperand(i: 3).getReg();
1205 computeKnownBitsImpl(R: PassThru, Known, DemandedElts, Depth: Depth + 1);
1206 // If we don't know any bits, early out.
1207 if (Known.isUnknown())
1208 break;
1209 // Compression can move any source lane to any result position, so all
1210 // source lanes are demanded.
1211 APInt DemandedSrcElts = APInt::getAllOnes(numBits: DemandedElts.getBitWidth());
1212 computeKnownBitsImpl(R: Vec, Known&: Known2, DemandedElts: DemandedSrcElts, Depth: Depth + 1);
1213 Known = Known.intersectWith(RHS: Known2);
1214 break;
1215 }
1216 case TargetOpcode::G_ABS: {
1217 Register SrcReg = MI.getOperand(i: 1).getReg();
1218 computeKnownBitsImpl(R: SrcReg, Known, DemandedElts, Depth: Depth + 1);
1219 Known = Known.abs();
1220 Known.Zero.setHighBits(computeNumSignBits(R: SrcReg, DemandedElts, Depth: Depth + 1) -
1221 1);
1222 break;
1223 }
1224 }
1225
1226 LLVM_DEBUG(dumpResult(MI, Known, Depth));
1227}
1228
1229static void genUnknown(MachineRegisterInfo &MRI, Register Reg,
1230 KnownBits &Known) {
1231 LLT Ty = MRI.getType(Reg);
1232 if (!Ty.isValid()) {
1233 Known = KnownBits();
1234 return;
1235 }
1236 unsigned BitWidth = Ty.getScalarSizeInBits();
1237 Known = KnownBits(BitWidth);
1238}
1239
1240/// Evaluate a known-bits query with an explicit worklist instead of recursive
1241/// descent.
1242void GISelValueTracking::computeKnownBitsImpl(Register R, KnownBits &Known,
1243 const APInt &DemandedElts,
1244 unsigned Depth) {
1245 // Nested queries only consult the per-query cache. If the result is not
1246 // available yet, enqueue the request and return an unknown placeholder.
1247 if (!Stack.empty()) {
1248 if (!getKnownBitsResult(Reg: R, DemandedElts, Depth, Known)) {
1249 Stack.push_back(Elt: {R, DemandedElts, Depth});
1250 genUnknown(MRI, Reg: R, Known);
1251 }
1252 return;
1253 }
1254
1255 // Top-level queries drive evaluation iteratively until every queued item has
1256 // either been computed or found in the cache.
1257 Stack.push_back(Elt: {R, DemandedElts, Depth});
1258 while (!Stack.empty()) {
1259 WorkItem Item = Stack.back();
1260 size_t StackSize = Stack.size();
1261 Register ItemReg = std::get<0>(t&: Item);
1262 const APInt &ItemDemandedElts = std::get<1>(t&: Item);
1263 const unsigned ItemDepth = std::get<2>(t&: Item);
1264 KnownBits ItemKnown;
1265
1266 if (getKnownBitsResult(Reg: ItemReg, DemandedElts: ItemDemandedElts, Depth: ItemDepth, Known&: ItemKnown)) {
1267 Stack.pop_back();
1268 continue;
1269 }
1270
1271 // Evaluate this item with the per-instruction known-bits logic. Dependent
1272 // queries issued from there re-enter this worklist driver and take the
1273 // nested-query path to enqueue more work.
1274 computeKnownBits(R: ItemReg, Known&: ItemKnown, DemandedElts: ItemDemandedElts, Depth: ItemDepth);
1275
1276 // If evaluating this item did not queue more work, its dependencies are
1277 // resolved and the result can be memoized immediately.
1278 if (Stack.size() == StackSize) {
1279 assert((std::get<0>(Stack.back()) == ItemReg &&
1280 std::get<1>(Stack.back()) == ItemDemandedElts &&
1281 std::get<2>(Stack.back()) == ItemDepth) &&
1282 "The item we just evaluated must still be the top one.");
1283
1284 setKnownBitsResult(Reg: ItemReg, DemandedElts: ItemDemandedElts, Depth: ItemDepth, Known: ItemKnown);
1285 Stack.pop_back();
1286 }
1287 }
1288
1289 // The original query must have been computed by the time the worklist is
1290 // drained.
1291 if (!getKnownBitsResult(Reg: R, DemandedElts, Depth, Known))
1292 llvm_unreachable(
1293 "Top level query must be in `results` after iteration is complete.");
1294
1295 Results.clear();
1296}
1297
1298void GISelValueTracking::computeKnownFPClass(Register R, KnownFPClass &Known,
1299 FPClassTest InterestedClasses,
1300 unsigned Depth) {
1301 LLT Ty = MRI.getType(Reg: R);
1302 APInt DemandedElts =
1303 Ty.isFixedVector() ? APInt::getAllOnes(numBits: Ty.getNumElements()) : APInt(1, 1);
1304 computeKnownFPClass(R, DemandedElts, InterestedClasses, Known, Depth);
1305}
1306
1307/// Return true if this value is known to be the fractional part x - floor(x),
1308/// which lies in [0, 1). This implies the value cannot introduce overflow in a
1309/// fmul when the other operand is known finite.
1310static bool isAbsoluteValueULEOne(Register R, const MachineRegisterInfo &MRI) {
1311 using namespace MIPatternMatch;
1312 Register SubX;
1313 return mi_match(R, MRI, P: m_GFSub(L: m_Reg(R&: SubX), R: m_GFFloor(Src: m_DeferredReg(R&: SubX))));
1314}
1315
1316void GISelValueTracking::computeKnownFPClassForFPTrunc(
1317 const MachineInstr &MI, const APInt &DemandedElts,
1318 FPClassTest InterestedClasses, KnownFPClass &Known, unsigned Depth) {
1319 if ((InterestedClasses & (KnownFPClass::OrderedLessThanZeroMask | fcNan)) ==
1320 fcNone)
1321 return;
1322
1323 Register Val = MI.getOperand(i: 1).getReg();
1324 KnownFPClass KnownSrc;
1325 computeKnownFPClass(R: Val, DemandedElts, InterestedClasses, Known&: KnownSrc,
1326 Depth: Depth + 1);
1327 Known = KnownFPClass::fptrunc(KnownSrc);
1328}
1329
1330void GISelValueTracking::computeKnownFPClass(Register R,
1331 const APInt &DemandedElts,
1332 FPClassTest InterestedClasses,
1333 KnownFPClass &Known,
1334 unsigned Depth) {
1335 assert(Known.isUnknown() && "should not be called with known information");
1336
1337 if (!DemandedElts) {
1338 // No demanded elts, better to assume we don't know anything.
1339 Known.resetAll();
1340 return;
1341 }
1342
1343 assert(Depth <= MaxAnalysisRecursionDepth && "Limit Search Depth");
1344
1345 MachineInstr &MI = *MRI.getVRegDef(Reg: R);
1346 unsigned Opcode = MI.getOpcode();
1347 LLT DstTy = MRI.getType(Reg: R);
1348
1349 if (!DstTy.isValid()) {
1350 Known.resetAll();
1351 return;
1352 }
1353
1354 if (auto Cst = GFConstant::getConstant(Const: R, MRI)) {
1355 switch (Cst->getKind()) {
1356 case GFConstant::GFConstantKind::Scalar: {
1357 auto APF = Cst->getScalarValue();
1358 Known.setKnownFPClasses(APF.classify());
1359 Known.setSignBit(APF.isNegative());
1360 break;
1361 }
1362 case GFConstant::GFConstantKind::FixedVector: {
1363 Known.setKnownFPClasses(fcNone);
1364 bool SignBitAllZero = true;
1365 bool SignBitAllOne = true;
1366
1367 for (auto C : *Cst) {
1368 Known.setKnownFPClasses(Known.getKnownFPClasses() | C.classify());
1369 if (C.isNegative())
1370 SignBitAllZero = false;
1371 else
1372 SignBitAllOne = false;
1373 }
1374
1375 if (SignBitAllOne != SignBitAllZero)
1376 Known.setSignBit(SignBitAllOne);
1377
1378 break;
1379 }
1380 case GFConstant::GFConstantKind::ScalableVector: {
1381 Known.resetAll();
1382 break;
1383 }
1384 }
1385
1386 return;
1387 }
1388
1389 FPClassTest KnownNotFromFlags = fcNone;
1390 if (MI.getFlag(Flag: MachineInstr::MIFlag::FmNoNans))
1391 KnownNotFromFlags |= fcNan;
1392 if (MI.getFlag(Flag: MachineInstr::MIFlag::FmNoInfs))
1393 KnownNotFromFlags |= fcInf;
1394
1395 // We no longer need to find out about these bits from inputs if we can
1396 // assume this from flags/attributes.
1397 InterestedClasses &= ~KnownNotFromFlags;
1398
1399 llvm::scope_exit ClearClassesFromFlags(
1400 [=, &Known] { Known.knownNot(RuleOut: KnownNotFromFlags); });
1401
1402 // All recursive calls that increase depth must come after this.
1403 if (Depth == MaxAnalysisRecursionDepth)
1404 return;
1405
1406 const MachineFunction *MF = MI.getMF();
1407
1408 switch (Opcode) {
1409 default:
1410 TL.computeKnownFPClassForTargetInstr(Analysis&: *this, R, Known, DemandedElts, MRI,
1411 Depth);
1412 break;
1413 case TargetOpcode::G_FNEG: {
1414 Register Val = MI.getOperand(i: 1).getReg();
1415 computeKnownFPClass(R: Val, DemandedElts, InterestedClasses, Known, Depth: Depth + 1);
1416 Known.fneg();
1417 break;
1418 }
1419 case TargetOpcode::G_SELECT: {
1420 GSelect &SelMI = cast<GSelect>(Val&: MI);
1421 Register Cond = SelMI.getCondReg();
1422 Register LHS = SelMI.getTrueReg();
1423 Register RHS = SelMI.getFalseReg();
1424
1425 FPClassTest FilterLHS = fcAllFlags;
1426 FPClassTest FilterRHS = fcAllFlags;
1427
1428 Register TestedValue;
1429 FPClassTest MaskIfTrue = fcAllFlags;
1430 FPClassTest MaskIfFalse = fcAllFlags;
1431 FPClassTest ClassVal = fcNone;
1432
1433 CmpInst::Predicate Pred;
1434 Register CmpLHS, CmpRHS;
1435 if (mi_match(R: Cond, MRI,
1436 P: m_GFCmp(P: m_Pred(P&: Pred), L: m_Reg(R&: CmpLHS), R: m_Reg(R&: CmpRHS)))) {
1437 // If the select filters out a value based on the class, it no longer
1438 // participates in the class of the result
1439
1440 // TODO: In some degenerate cases we can infer something if we try again
1441 // without looking through sign operations.
1442 bool LookThroughFAbsFNeg = CmpLHS != LHS && CmpLHS != RHS;
1443 std::tie(args&: TestedValue, args&: MaskIfTrue, args&: MaskIfFalse) =
1444 fcmpImpliesClass(Pred, MF: *MF, LHS: CmpLHS, RHS: CmpRHS, LookThroughSrc: LookThroughFAbsFNeg);
1445 } else if (mi_match(
1446 R: Cond, MRI,
1447 P: m_GIsFPClass(L: m_Reg(R&: TestedValue), T: m_FPClassTest(T&: ClassVal)))) {
1448 FPClassTest TestedMask = ClassVal;
1449 MaskIfTrue = TestedMask;
1450 MaskIfFalse = ~TestedMask;
1451 }
1452
1453 if (TestedValue == LHS) {
1454 // match !isnan(x) ? x : y
1455 FilterLHS = MaskIfTrue;
1456 } else if (TestedValue == RHS) { // && IsExactClass
1457 // match !isnan(x) ? y : x
1458 FilterRHS = MaskIfFalse;
1459 }
1460
1461 KnownFPClass Known2;
1462 computeKnownFPClass(R: LHS, DemandedElts, InterestedClasses: InterestedClasses & FilterLHS, Known,
1463 Depth: Depth + 1);
1464 Known.setKnownFPClasses(Known.getKnownFPClasses() & FilterLHS);
1465
1466 computeKnownFPClass(R: RHS, DemandedElts, InterestedClasses: InterestedClasses & FilterRHS,
1467 Known&: Known2, Depth: Depth + 1);
1468 Known2.setKnownFPClasses(Known2.getKnownFPClasses() & FilterRHS);
1469
1470 Known |= Known2;
1471 break;
1472 }
1473 case TargetOpcode::G_FCOPYSIGN: {
1474 Register Magnitude = MI.getOperand(i: 1).getReg();
1475 Register Sign = MI.getOperand(i: 2).getReg();
1476
1477 KnownFPClass KnownSign;
1478
1479 computeKnownFPClass(R: Magnitude, DemandedElts, InterestedClasses, Known,
1480 Depth: Depth + 1);
1481 computeKnownFPClass(R: Sign, DemandedElts, InterestedClasses, Known&: KnownSign,
1482 Depth: Depth + 1);
1483 Known.copysign(Sign: KnownSign);
1484 break;
1485 }
1486 case TargetOpcode::G_FMA:
1487 case TargetOpcode::G_STRICT_FMA:
1488 case TargetOpcode::G_FMAD: {
1489 if ((InterestedClasses & fcNegative) == fcNone)
1490 break;
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 // x * x + y
1501 KnownFPClass KnownSrc, KnownAddend;
1502 computeKnownFPClass(R: C, DemandedElts, InterestedClasses, Known&: KnownAddend,
1503 Depth: Depth + 1);
1504 computeKnownFPClass(R: A, DemandedElts, InterestedClasses, Known&: KnownSrc,
1505 Depth: Depth + 1);
1506 if (KnownNotFromFlags) {
1507 KnownSrc.knownNot(RuleOut: KnownNotFromFlags);
1508 KnownAddend.knownNot(RuleOut: KnownNotFromFlags);
1509 }
1510 Known = KnownFPClass::fma_square(Squared: KnownSrc, Addend: KnownAddend, Mode);
1511 } else {
1512 KnownFPClass KnownSrc[3];
1513 computeKnownFPClass(R: A, DemandedElts, InterestedClasses, Known&: KnownSrc[0],
1514 Depth: Depth + 1);
1515 if (KnownSrc[0].isUnknown())
1516 break;
1517 computeKnownFPClass(R: B, DemandedElts, InterestedClasses, Known&: KnownSrc[1],
1518 Depth: Depth + 1);
1519 if (KnownSrc[1].isUnknown())
1520 break;
1521 computeKnownFPClass(R: C, DemandedElts, InterestedClasses, Known&: KnownSrc[2],
1522 Depth: Depth + 1);
1523 if (KnownSrc[2].isUnknown())
1524 break;
1525 if (KnownNotFromFlags) {
1526 KnownSrc[0].knownNot(RuleOut: KnownNotFromFlags);
1527 KnownSrc[1].knownNot(RuleOut: KnownNotFromFlags);
1528 KnownSrc[2].knownNot(RuleOut: KnownNotFromFlags);
1529 }
1530 Known = KnownFPClass::fma(LHS: KnownSrc[0], RHS: KnownSrc[1], Addend: KnownSrc[2], Mode);
1531 }
1532 break;
1533 }
1534 case TargetOpcode::G_FSQRT:
1535 case TargetOpcode::G_STRICT_FSQRT: {
1536 KnownFPClass KnownSrc;
1537 FPClassTest InterestedSrcs = InterestedClasses;
1538 if (InterestedClasses & fcNan)
1539 InterestedSrcs |= KnownFPClass::OrderedLessThanZeroMask;
1540
1541 Register Val = MI.getOperand(i: 1).getReg();
1542 computeKnownFPClass(R: Val, DemandedElts, InterestedClasses: InterestedSrcs, Known&: KnownSrc, Depth: Depth + 1);
1543
1544 DenormalMode Mode =
1545 MF->getDenormalMode(FPType: getFltSemanticForLLT(Ty: DstTy.getScalarType()));
1546 Known = KnownFPClass::sqrt(Src: KnownSrc, Mode);
1547 if (MI.getFlag(Flag: MachineInstr::MIFlag::FmNsz))
1548 Known.knownNot(RuleOut: fcNegZero);
1549 break;
1550 }
1551 case TargetOpcode::G_FABS: {
1552 if ((InterestedClasses & (fcNan | fcPositive)) != fcNone) {
1553 Register Val = MI.getOperand(i: 1).getReg();
1554 // If we only care about the sign bit we don't need to inspect the
1555 // operand.
1556 computeKnownFPClass(R: Val, DemandedElts, InterestedClasses, Known,
1557 Depth: Depth + 1);
1558 }
1559 Known.fabs();
1560 break;
1561 }
1562 case TargetOpcode::G_FATAN2: {
1563 FPClassTest InterestedY = InterestedClasses;
1564 FPClassTest InterestedX = InterestedClasses;
1565
1566 // We can rule out negative values if y cannot have a negative value.
1567 if ((InterestedClasses & fcNegFinite) != fcNone)
1568 InterestedY |= fcNegative;
1569
1570 // We can rule out positive values if y cannot have a positive value.
1571 if ((InterestedClasses & fcPosFinite) != fcNone)
1572 InterestedY |= fcPositive | fcNegSubnormal;
1573
1574 // We can rule out zero and subnormal if x cannot have a positive value.
1575 if ((InterestedClasses & (fcZero | fcSubnormal)) != fcNone)
1576 InterestedX |= fcPositive | fcNegSubnormal;
1577
1578 Register Y = MI.getOperand(i: 1).getReg();
1579 Register X = MI.getOperand(i: 2).getReg();
1580 KnownFPClass KnownY, KnownX;
1581 computeKnownFPClass(R: Y, DemandedElts, InterestedClasses: InterestedY, Known&: KnownY, Depth: Depth + 1);
1582 computeKnownFPClass(R: X, DemandedElts, InterestedClasses: InterestedX, Known&: KnownX, Depth: Depth + 1);
1583 DenormalMode Mode =
1584 MF->getDenormalMode(FPType: getFltSemanticForLLT(Ty: DstTy.getScalarType()));
1585 Known = KnownFPClass::atan2(LHS: KnownY, RHS: KnownX, Mode);
1586 break;
1587 }
1588 case TargetOpcode::G_FSINH: {
1589 Register Val = MI.getOperand(i: 1).getReg();
1590 KnownFPClass KnownSrc;
1591 computeKnownFPClass(R: Val, DemandedElts, InterestedClasses, Known&: KnownSrc,
1592 Depth: Depth + 1);
1593 Known = KnownFPClass::sinh(Src: KnownSrc);
1594 break;
1595 }
1596 case TargetOpcode::G_FCOSH: {
1597 Register Val = MI.getOperand(i: 1).getReg();
1598 KnownFPClass KnownSrc;
1599 computeKnownFPClass(R: Val, DemandedElts, InterestedClasses, Known&: KnownSrc,
1600 Depth: Depth + 1);
1601 Known = KnownFPClass::cosh(Src: KnownSrc);
1602 break;
1603 }
1604 case TargetOpcode::G_FTANH: {
1605 Register Val = MI.getOperand(i: 1).getReg();
1606 KnownFPClass KnownSrc;
1607 computeKnownFPClass(R: Val, DemandedElts, InterestedClasses, Known&: KnownSrc,
1608 Depth: Depth + 1);
1609 Known = KnownFPClass::tanh(Src: KnownSrc);
1610 break;
1611 }
1612 case TargetOpcode::G_FASIN: {
1613 Register Val = MI.getOperand(i: 1).getReg();
1614 KnownFPClass KnownSrc;
1615 computeKnownFPClass(R: Val, DemandedElts, InterestedClasses, Known&: KnownSrc,
1616 Depth: Depth + 1);
1617 Known = KnownFPClass::asin(Src: KnownSrc);
1618 break;
1619 }
1620 case TargetOpcode::G_FACOS: {
1621 Register Val = MI.getOperand(i: 1).getReg();
1622 KnownFPClass KnownSrc;
1623 computeKnownFPClass(R: Val, DemandedElts, InterestedClasses, Known&: KnownSrc,
1624 Depth: Depth + 1);
1625 Known = KnownFPClass::acos(Src: KnownSrc);
1626 break;
1627 }
1628 case TargetOpcode::G_FATAN: {
1629 Register Val = MI.getOperand(i: 1).getReg();
1630 KnownFPClass KnownSrc;
1631 computeKnownFPClass(R: Val, DemandedElts, InterestedClasses, Known&: KnownSrc,
1632 Depth: Depth + 1);
1633 Known = KnownFPClass::atan(Src: KnownSrc);
1634 break;
1635 }
1636 case TargetOpcode::G_FTAN: {
1637 Register Val = MI.getOperand(i: 1).getReg();
1638 KnownFPClass KnownSrc;
1639 computeKnownFPClass(R: Val, DemandedElts, InterestedClasses, Known&: KnownSrc,
1640 Depth: Depth + 1);
1641 Known = KnownFPClass::tan(Src: KnownSrc);
1642 break;
1643 }
1644 case TargetOpcode::G_FSIN:
1645 case TargetOpcode::G_FCOS: {
1646 // Return NaN on infinite inputs.
1647 Register Val = MI.getOperand(i: 1).getReg();
1648 KnownFPClass KnownSrc;
1649 computeKnownFPClass(R: Val, DemandedElts, InterestedClasses, Known&: KnownSrc,
1650 Depth: Depth + 1);
1651 Known = Opcode == TargetOpcode::G_FCOS ? KnownFPClass::cos(Src: KnownSrc)
1652 : KnownFPClass::sin(Src: KnownSrc);
1653 break;
1654 }
1655 case TargetOpcode::G_FSINCOS: {
1656 // Operand layout: (sin_dst, cos_dst, src)
1657 Register Src = MI.getOperand(i: 2).getReg();
1658 KnownFPClass KnownSrc;
1659 computeKnownFPClass(R: Src, DemandedElts, InterestedClasses, Known&: KnownSrc,
1660 Depth: Depth + 1);
1661 if (R == MI.getOperand(i: 0).getReg())
1662 Known = KnownFPClass::sin(Src: KnownSrc);
1663 else
1664 Known = KnownFPClass::cos(Src: KnownSrc);
1665 break;
1666 }
1667 case TargetOpcode::G_FMAXNUM:
1668 case TargetOpcode::G_FMINNUM:
1669 case TargetOpcode::G_FMINNUM_IEEE:
1670 case TargetOpcode::G_FMAXIMUM:
1671 case TargetOpcode::G_FMINIMUM:
1672 case TargetOpcode::G_FMAXNUM_IEEE:
1673 case TargetOpcode::G_FMAXIMUMNUM:
1674 case TargetOpcode::G_FMINIMUMNUM: {
1675 Register LHS = MI.getOperand(i: 1).getReg();
1676 Register RHS = MI.getOperand(i: 2).getReg();
1677 KnownFPClass KnownLHS, KnownRHS;
1678
1679 computeKnownFPClass(R: LHS, DemandedElts, InterestedClasses, Known&: KnownLHS,
1680 Depth: Depth + 1);
1681 computeKnownFPClass(R: RHS, DemandedElts, InterestedClasses, Known&: KnownRHS,
1682 Depth: Depth + 1);
1683
1684 KnownFPClass::MinMaxKind Kind;
1685 switch (Opcode) {
1686 case TargetOpcode::G_FMINIMUM:
1687 Kind = KnownFPClass::MinMaxKind::minimum;
1688 break;
1689 case TargetOpcode::G_FMAXIMUM:
1690 Kind = KnownFPClass::MinMaxKind::maximum;
1691 break;
1692 case TargetOpcode::G_FMINIMUMNUM:
1693 Kind = KnownFPClass::MinMaxKind::minimumnum;
1694 break;
1695 case TargetOpcode::G_FMAXIMUMNUM:
1696 Kind = KnownFPClass::MinMaxKind::maximumnum;
1697 break;
1698 case TargetOpcode::G_FMINNUM:
1699 case TargetOpcode::G_FMINNUM_IEEE:
1700 Kind = KnownFPClass::MinMaxKind::minnum;
1701 break;
1702 case TargetOpcode::G_FMAXNUM:
1703 case TargetOpcode::G_FMAXNUM_IEEE:
1704 Kind = KnownFPClass::MinMaxKind::maxnum;
1705 break;
1706 default:
1707 llvm_unreachable("unhandled min/max opcode");
1708 }
1709
1710 DenormalMode Mode =
1711 MF->getDenormalMode(FPType: getFltSemanticForLLT(Ty: DstTy.getScalarType()));
1712 Known = KnownFPClass::minMaxLike(LHS: KnownLHS, RHS: KnownRHS, Kind, DenormMode: Mode);
1713 break;
1714 }
1715 case TargetOpcode::G_FCANONICALIZE: {
1716 Register Val = MI.getOperand(i: 1).getReg();
1717 KnownFPClass KnownSrc;
1718 computeKnownFPClass(R: Val, DemandedElts, InterestedClasses, Known&: KnownSrc,
1719 Depth: Depth + 1);
1720
1721 LLT Ty = MRI.getType(Reg: Val).getScalarType();
1722 const fltSemantics &FPType = getFltSemanticForLLT(Ty);
1723 DenormalMode DenormMode = MF->getDenormalMode(FPType);
1724 Known = KnownFPClass::canonicalize(Src: KnownSrc, DenormMode);
1725 break;
1726 }
1727 case TargetOpcode::G_VECREDUCE_FMAX:
1728 case TargetOpcode::G_VECREDUCE_FMIN:
1729 case TargetOpcode::G_VECREDUCE_FMAXIMUM:
1730 case TargetOpcode::G_VECREDUCE_FMINIMUM:
1731 case TargetOpcode::G_VECREDUCE_FMAXIMUMNUM:
1732 case TargetOpcode::G_VECREDUCE_FMINIMUMNUM: {
1733 Register Val = MI.getOperand(i: 1).getReg();
1734 // reduce min/max will choose an element from one of the vector elements,
1735 // so we can infer and class information that is common to all elements.
1736
1737 Known =
1738 computeKnownFPClass(R: Val, Flags: MI.getFlags(), InterestedClasses, Depth: Depth + 1);
1739 // Can only propagate sign if output is never NaN.
1740 if (!Known.isKnownNeverNaN())
1741 Known.setSignBit(std::nullopt);
1742 break;
1743 }
1744 case TargetOpcode::G_FFLOOR:
1745 case TargetOpcode::G_FCEIL:
1746 case TargetOpcode::G_FRINT:
1747 case TargetOpcode::G_FNEARBYINT:
1748 case TargetOpcode::G_INTRINSIC_ROUND:
1749 case TargetOpcode::G_INTRINSIC_ROUNDEVEN:
1750 case TargetOpcode::G_INTRINSIC_TRUNC: {
1751 Register Val = MI.getOperand(i: 1).getReg();
1752 KnownFPClass KnownSrc;
1753 FPClassTest InterestedSrcs = InterestedClasses;
1754
1755 // Negative round ups towards zero produce negative zero.
1756 if (InterestedSrcs & fcNegFinite)
1757 InterestedSrcs |= fcNegFinite;
1758
1759 // Negative subnormals may flush to positive zero.
1760 if (InterestedSrcs & fcPosFinite)
1761 InterestedSrcs |= fcPosFinite | fcNegSubnormal;
1762
1763 computeKnownFPClass(R: Val, DemandedElts, InterestedClasses: InterestedSrcs, Known&: KnownSrc, Depth: Depth + 1);
1764
1765 LLT Ty = MRI.getType(Reg: Val).getScalarType();
1766 const fltSemantics &FltSem = getFltSemanticForLLT(Ty);
1767 DenormalMode Mode = MF->getDenormalMode(FPType: FltSem);
1768 const bool IsMultiUnitFPType = &FltSem == &APFloat::PPCDoubleDouble();
1769
1770 const bool IsTrunc = Opcode == TargetOpcode::G_INTRINSIC_TRUNC;
1771 Known = KnownFPClass::roundToIntegral(Src: KnownSrc, IsTrunc, IsMultiUnitFPType,
1772 Mode);
1773 break;
1774 }
1775 case TargetOpcode::G_FEXP:
1776 case TargetOpcode::G_FEXP2:
1777 case TargetOpcode::G_FEXP10: {
1778 Register Val = MI.getOperand(i: 1).getReg();
1779 KnownFPClass KnownSrc;
1780 computeKnownFPClass(R: Val, DemandedElts, InterestedClasses, Known&: KnownSrc,
1781 Depth: Depth + 1);
1782 Known = KnownFPClass::exp(Src: KnownSrc);
1783 break;
1784 }
1785 case TargetOpcode::G_FLOG:
1786 case TargetOpcode::G_FLOG2:
1787 case TargetOpcode::G_FLOG10: {
1788 FPClassTest InterestedSrcs = fcNone;
1789
1790 // log(negative) produces NaN.
1791 if ((InterestedClasses & fcNan) != fcNone)
1792 InterestedSrcs |= fcNan | fcNegative;
1793
1794 // log(logical-zero) produces negative infinity.
1795 if ((InterestedClasses & fcNegInf) != fcNone)
1796 InterestedSrcs |= fcZero | fcSubnormal;
1797
1798 // log(x) < -0.0 if x < +1.0
1799 if ((InterestedClasses & fcNegNormal) != fcNone)
1800 InterestedSrcs |= fcPosSubnormal | fcPosNormal;
1801
1802 // log(x) >= +0.0 if x >= +1.0
1803 if ((InterestedClasses & (fcPosZero | fcPosNormal)) != fcNone)
1804 InterestedSrcs |= fcPosNormal;
1805
1806 // log(x) is positive infinity iff x is positive infinity.
1807 if ((InterestedClasses & fcPosInf) != fcNone)
1808 InterestedSrcs |= fcPosInf;
1809
1810 Register Val = MI.getOperand(i: 1).getReg();
1811 KnownFPClass KnownSrc;
1812 if (InterestedSrcs != fcNone)
1813 computeKnownFPClass(R: Val, DemandedElts, InterestedClasses: InterestedSrcs, Known&: KnownSrc,
1814 Depth: Depth + 1);
1815
1816 LLT Ty = MRI.getType(Reg: Val).getScalarType();
1817 const fltSemantics &FltSem = getFltSemanticForLLT(Ty);
1818 DenormalMode Mode = MF->getDenormalMode(FPType: FltSem);
1819 Known = KnownFPClass::log(Src: KnownSrc, Mode);
1820 break;
1821 }
1822 case TargetOpcode::G_FPOW: {
1823 const bool WantNaN = (InterestedClasses & fcNan) != fcNone;
1824 const bool WantNegative = (InterestedClasses & fcNegative) != fcNone;
1825 if (!WantNaN && !WantNegative)
1826 break;
1827
1828 FPClassTest InterestedLHS = fcNone;
1829 FPClassTest InterestedRHS = fcNone;
1830 if (WantNaN) {
1831 // pow may return NaN if one of the arguments is NaN. NaN may be produced
1832 // from a non-zero-finite-negative base and a non-integer exponent.
1833 InterestedLHS |= fcNan | fcNegNormal | fcNegSubnormal;
1834 InterestedRHS |= fcNan;
1835 }
1836 if (WantNegative) {
1837 // A negative value is returned when a negative base is raised to an odd
1838 // integer power. Only normal values can be odd integers.
1839 InterestedLHS |= fcNegative;
1840 InterestedRHS |= fcNormal;
1841 }
1842
1843 KnownFPClass KnownLHS;
1844 computeKnownFPClass(R: MI.getOperand(i: 1).getReg(), DemandedElts, InterestedClasses: InterestedLHS,
1845 Known&: KnownLHS, Depth: Depth + 1);
1846
1847 // If the LHS is unknown, then querying the RHS is only useful for rare edge
1848 // cases.
1849 if (KnownLHS.isUnknown())
1850 break;
1851
1852 KnownFPClass KnownRHS;
1853 computeKnownFPClass(R: MI.getOperand(i: 2).getReg(), DemandedElts, InterestedClasses: InterestedRHS,
1854 Known&: KnownRHS, Depth: Depth + 1);
1855 Known = KnownFPClass::pow(LHS: KnownLHS, RHS: KnownRHS);
1856 break;
1857 }
1858 case TargetOpcode::G_FPOWI: {
1859 if ((InterestedClasses & (fcNan | fcInf | fcNegative)) == fcNone)
1860 break;
1861
1862 Register Exp = MI.getOperand(i: 2).getReg();
1863 LLT ExpTy = MRI.getType(Reg: Exp);
1864 KnownBits ExponentKnownBits = getKnownBits(
1865 R: Exp, DemandedElts: ExpTy.isVector() ? DemandedElts : APInt(1, 1), Depth: Depth + 1);
1866
1867 FPClassTest InterestedSrcs = fcNone;
1868 if (InterestedClasses & fcNan)
1869 InterestedSrcs |= fcNan;
1870 if (!ExponentKnownBits.isZero()) {
1871 if (InterestedClasses & fcInf)
1872 InterestedSrcs |= fcFinite | fcInf;
1873 if ((InterestedClasses & fcNegative) && !ExponentKnownBits.isEven())
1874 InterestedSrcs |= fcNegative;
1875 }
1876
1877 KnownFPClass KnownSrc;
1878 if (InterestedSrcs != fcNone) {
1879 Register Val = MI.getOperand(i: 1).getReg();
1880 computeKnownFPClass(R: Val, DemandedElts, InterestedClasses: InterestedSrcs, Known&: KnownSrc,
1881 Depth: Depth + 1);
1882 }
1883
1884 Known = KnownFPClass::powi(Src: KnownSrc, N: ExponentKnownBits);
1885 break;
1886 }
1887 case TargetOpcode::G_FLDEXP:
1888 case TargetOpcode::G_STRICT_FLDEXP: {
1889 Register Val = MI.getOperand(i: 1).getReg();
1890 KnownFPClass KnownSrc;
1891 computeKnownFPClass(R: Val, DemandedElts, InterestedClasses, Known&: KnownSrc,
1892 Depth: Depth + 1);
1893
1894 // Can refine inf/zero handling based on the exponent operand.
1895 const FPClassTest ExpInfoMask = fcZero | fcSubnormal | fcInf;
1896 KnownBits ExpBits;
1897 if ((KnownSrc.getKnownFPClasses() & ExpInfoMask) != fcNone) {
1898 Register ExpReg = MI.getOperand(i: 2).getReg();
1899 LLT ExpTy = MRI.getType(Reg: ExpReg);
1900 ExpBits = getKnownBits(
1901 R: ExpReg, DemandedElts: ExpTy.isVector() ? DemandedElts : APInt(1, 1), Depth: Depth + 1);
1902 }
1903
1904 LLT ScalarTy = DstTy.getScalarType();
1905 const fltSemantics &Flt = getFltSemanticForLLT(Ty: ScalarTy);
1906 DenormalMode Mode = MF->getDenormalMode(FPType: Flt);
1907 Known = KnownFPClass::ldexp(Src: KnownSrc, ExpBits, Flt, Mode);
1908 break;
1909 }
1910 case TargetOpcode::G_FADD:
1911 case TargetOpcode::G_STRICT_FADD:
1912 case TargetOpcode::G_FSUB:
1913 case TargetOpcode::G_STRICT_FSUB: {
1914 Register LHS = MI.getOperand(i: 1).getReg();
1915 Register RHS = MI.getOperand(i: 2).getReg();
1916 bool IsAdd = (Opcode == TargetOpcode::G_FADD ||
1917 Opcode == TargetOpcode::G_STRICT_FADD);
1918 bool WantNegative =
1919 IsAdd &&
1920 (InterestedClasses & KnownFPClass::OrderedLessThanZeroMask) != fcNone;
1921 bool WantNaN = (InterestedClasses & fcNan) != fcNone;
1922 bool WantNegZero = (InterestedClasses & fcNegZero) != fcNone;
1923
1924 if (!WantNaN && !WantNegative && !WantNegZero) {
1925 break;
1926 }
1927
1928 DenormalMode Mode =
1929 MF->getDenormalMode(FPType: getFltSemanticForLLT(Ty: DstTy.getScalarType()));
1930
1931 FPClassTest InterestedSrcs = InterestedClasses;
1932 if (WantNegative)
1933 InterestedSrcs |= KnownFPClass::OrderedLessThanZeroMask;
1934 if (InterestedClasses & fcNan)
1935 InterestedSrcs |= fcInf;
1936
1937 // Special case fadd x, x (canonical form of fmul x, 2).
1938 if (IsAdd && LHS == RHS && isGuaranteedNotToBeUndef(Reg: LHS, MRI, Depth: Depth + 1)) {
1939 KnownFPClass KnownSelf;
1940 computeKnownFPClass(R: LHS, DemandedElts, InterestedClasses: InterestedSrcs, Known&: KnownSelf,
1941 Depth: Depth + 1);
1942 Known = KnownFPClass::fadd_self(Src: KnownSelf, Mode);
1943 break;
1944 }
1945
1946 KnownFPClass KnownLHS, KnownRHS;
1947 computeKnownFPClass(R: RHS, DemandedElts, InterestedClasses: InterestedSrcs, Known&: KnownRHS, Depth: Depth + 1);
1948
1949 if ((WantNaN && KnownRHS.isKnownNeverNaN()) ||
1950 (WantNegative && KnownRHS.cannotBeOrderedLessThanZero()) ||
1951 WantNegZero || !IsAdd) {
1952 // RHS is canonically cheaper to compute. Skip inspecting the LHS if
1953 // there's no point.
1954 computeKnownFPClass(R: LHS, DemandedElts, InterestedClasses: InterestedSrcs, Known&: KnownLHS,
1955 Depth: Depth + 1);
1956 }
1957
1958 if (IsAdd)
1959 Known = KnownFPClass::fadd(LHS: KnownLHS, RHS: KnownRHS, Mode);
1960 else
1961 Known = KnownFPClass::fsub(LHS: KnownLHS, RHS: KnownRHS, Mode);
1962 break;
1963 }
1964 case TargetOpcode::G_FMUL:
1965 case TargetOpcode::G_STRICT_FMUL: {
1966 Register LHS = MI.getOperand(i: 1).getReg();
1967 Register RHS = MI.getOperand(i: 2).getReg();
1968 DenormalMode Mode =
1969 MF->getDenormalMode(FPType: getFltSemanticForLLT(Ty: DstTy.getScalarType()));
1970
1971 // X * X is always non-negative or a NaN (use square() for precision).
1972 if (LHS == RHS && isGuaranteedNotToBeUndef(Reg: LHS, MRI, Depth: Depth + 1)) {
1973 KnownFPClass KnownSrc;
1974 computeKnownFPClass(R: LHS, DemandedElts, InterestedClasses: fcAllFlags, Known&: KnownSrc, Depth: Depth + 1);
1975 Known = KnownFPClass::square(Src: KnownSrc, Mode);
1976 } else {
1977 // If RHS is a scalar constant, use the more precise APFloat overload.
1978 auto RHSCst = GFConstant::getConstant(Const: RHS, MRI);
1979 if (RHSCst && RHSCst->getKind() == GFConstant::GFConstantKind::Scalar) {
1980 KnownFPClass KnownLHS;
1981 computeKnownFPClass(R: LHS, DemandedElts, InterestedClasses: fcAllFlags, Known&: KnownLHS, Depth: Depth + 1);
1982 Known = KnownFPClass::fmul(LHS: KnownLHS, RHS: RHSCst->getScalarValue(), Mode);
1983 } else {
1984 KnownFPClass KnownLHS, KnownRHS;
1985 computeKnownFPClass(R: RHS, DemandedElts, InterestedClasses: fcAllFlags, Known&: KnownRHS, Depth: Depth + 1);
1986 computeKnownFPClass(R: LHS, DemandedElts, InterestedClasses: fcAllFlags, Known&: KnownLHS, Depth: Depth + 1);
1987 Known = KnownFPClass::fmul(LHS: KnownLHS, RHS: KnownRHS, Mode);
1988
1989 // If one operand is known |x| <= 1 and the other is finite, the
1990 // product cannot overflow to infinity.
1991 if (KnownLHS.isKnownNever(Mask: fcInf) && isAbsoluteValueULEOne(R: RHS, MRI))
1992 Known.knownNot(RuleOut: fcInf);
1993 else if (KnownRHS.isKnownNever(Mask: fcInf) &&
1994 isAbsoluteValueULEOne(R: LHS, MRI))
1995 Known.knownNot(RuleOut: fcInf);
1996 }
1997 }
1998 break;
1999 }
2000 case TargetOpcode::G_FDIV: {
2001 const bool WantNan = (InterestedClasses & fcNan) != fcNone;
2002
2003 Register LHS = MI.getOperand(i: 1).getReg();
2004 Register RHS = MI.getOperand(i: 2).getReg();
2005
2006 DenormalMode Mode =
2007 MF->getDenormalMode(FPType: getFltSemanticForLLT(Ty: DstTy.getScalarType()));
2008
2009 if (LHS == RHS && isGuaranteedNotToBeUndef(Reg: LHS, MRI, Depth: Depth + 1)) {
2010 // X / X is always exactly 1.0 or a NaN.
2011 Known.setKnownFPClasses(fcPosNormal | fcNan);
2012
2013 if (!WantNan)
2014 break;
2015
2016 KnownFPClass KnownSrc;
2017 computeKnownFPClass(R: LHS, DemandedElts,
2018 InterestedClasses: fcNan | fcInf | fcZero | fcSubnormal, Known&: KnownSrc,
2019 Depth: Depth + 1);
2020 Known = KnownFPClass::fdiv_self(Src: KnownSrc, Mode);
2021 break;
2022 }
2023
2024 const bool WantNegative = (InterestedClasses & fcNegative) != fcNone;
2025 const bool WantPositive = (InterestedClasses & fcPositive) != fcNone;
2026 if (!WantNan && !WantNegative && !WantPositive)
2027 break;
2028
2029 KnownFPClass KnownLHS, KnownRHS;
2030 computeKnownFPClass(R: RHS, DemandedElts, InterestedClasses: fcAllFlags, Known&: KnownRHS, Depth: Depth + 1);
2031
2032 bool KnowSomethingUseful =
2033 KnownRHS.isKnownNeverNaN() ||
2034 KnownRHS.isKnownNever(Mask: fcNegNormal | fcNegSubnormal) ||
2035 KnownRHS.isKnownNever(Mask: fcPosNormal | fcPosSubnormal);
2036
2037 if (KnowSomethingUseful)
2038 computeKnownFPClass(R: LHS, DemandedElts, InterestedClasses: fcAllFlags, Known&: KnownLHS, Depth: Depth + 1);
2039
2040 Known = KnownFPClass::fdiv(LHS: KnownLHS, RHS: KnownRHS, Mode);
2041 break;
2042 }
2043 case TargetOpcode::G_FREM: {
2044 FPClassTest InterestedLHS = fcNone;
2045 FPClassTest InterestedRHS = fcNone;
2046
2047 // NaN is also generated for frem(Inf, x) and frem(x, 0.0).
2048 if (InterestedClasses & fcNan) {
2049 InterestedLHS |= fcNan | fcInf;
2050 InterestedRHS |= fcNan | fcZero | fcSubnormal;
2051 }
2052
2053 // The sign for frem is the same as the first operand.
2054 if (InterestedClasses & (fcPosNormal | fcPosSubnormal))
2055 InterestedLHS |= fcPosNormal | fcPosSubnormal;
2056 if (InterestedClasses & (fcNegNormal | fcNegSubnormal))
2057 InterestedLHS |= fcNegNormal | fcNegSubnormal;
2058
2059 // A negative zero result requires a negative finite first operand.
2060 if (InterestedClasses & fcNegZero)
2061 InterestedLHS |= fcNegFinite;
2062
2063 // A positive zero result can additionally come from a negative finite
2064 // result being flushed to positive zero.
2065 if (InterestedClasses & fcPosZero)
2066 InterestedLHS |= fcPosFinite | fcNegNormal | fcNegSubnormal;
2067
2068 Register LHS = MI.getOperand(i: 1).getReg();
2069 Register RHS = MI.getOperand(i: 2).getReg();
2070
2071 DenormalMode Mode =
2072 MF->getDenormalMode(FPType: getFltSemanticForLLT(Ty: DstTy.getScalarType()));
2073
2074 if (LHS == RHS && isGuaranteedNotToBeUndef(Reg: LHS, MRI, Depth: Depth + 1)) {
2075 // X % X is always exactly [+-]0.0 or a NaN.
2076 FPClassTest InterestedSrcs = InterestedLHS | InterestedRHS;
2077 KnownFPClass KnownSrc;
2078 if (InterestedSrcs != fcNone)
2079 computeKnownFPClass(R: LHS, DemandedElts, InterestedClasses: InterestedSrcs, Known&: KnownSrc,
2080 Depth: Depth + 1);
2081 Known = KnownFPClass::frem_self(Src: KnownSrc, Mode);
2082 break;
2083 }
2084
2085 KnownFPClass KnownLHS;
2086 if (InterestedLHS != fcNone)
2087 computeKnownFPClass(R: LHS, DemandedElts, InterestedClasses: InterestedLHS, Known&: KnownLHS,
2088 Depth: Depth + 1);
2089
2090 KnownFPClass KnownRHS;
2091 // RHS is only useful for refining NaN classes.
2092 if (InterestedRHS != fcNone && KnownLHS.isKnownNever(Mask: fcSNan))
2093 computeKnownFPClass(R: RHS, DemandedElts, InterestedClasses: InterestedRHS, Known&: KnownRHS,
2094 Depth: Depth + 1);
2095
2096 Known = KnownFPClass::frem(LHS: KnownLHS, RHS: KnownRHS, Mode);
2097
2098 break;
2099 }
2100 case TargetOpcode::G_FFREXP: {
2101 // Only handle the mantissa output (operand 0); the exponent is an integer.
2102 if (R != MI.getOperand(i: 0).getReg())
2103 break;
2104 Register Src = MI.getOperand(i: 2).getReg();
2105 FPClassTest InterestedSrcs = InterestedClasses;
2106
2107 // Positive subnormals and negative subnormals could become positive zero.
2108 if (InterestedClasses & fcPosZero)
2109 InterestedSrcs |= fcSubnormal;
2110
2111 // Negative subnormals could become negative zero.
2112 if (InterestedClasses & fcNegZero)
2113 InterestedSrcs |= fcNegSubnormal;
2114
2115 if (InterestedClasses & fcPosNormal)
2116 InterestedSrcs |= fcPosSubnormal;
2117
2118 if (InterestedClasses & fcNegNormal)
2119 InterestedSrcs |= fcNegSubnormal;
2120
2121 KnownFPClass KnownSrc;
2122 computeKnownFPClass(R: Src, DemandedElts, InterestedClasses: InterestedSrcs, Known&: KnownSrc, Depth: Depth + 1);
2123 DenormalMode Mode =
2124 MF->getDenormalMode(FPType: getFltSemanticForLLT(Ty: DstTy.getScalarType()));
2125 Known = KnownFPClass::frexp_mant(Src: KnownSrc, Mode);
2126 break;
2127 }
2128 case TargetOpcode::G_FPEXT: {
2129 Register Src = MI.getOperand(i: 1).getReg();
2130 KnownFPClass KnownSrc;
2131 computeKnownFPClass(R: Src, DemandedElts, InterestedClasses, Known&: KnownSrc,
2132 Depth: Depth + 1);
2133
2134 LLT DstScalarTy = DstTy.getScalarType();
2135 const fltSemantics &DstSem = getFltSemanticForLLT(Ty: DstScalarTy);
2136 LLT SrcTy = MRI.getType(Reg: Src).getScalarType();
2137 const fltSemantics &SrcSem = getFltSemanticForLLT(Ty: SrcTy);
2138
2139 Known = KnownFPClass::fpext(KnownSrc, DstTy: DstSem, SrcTy: SrcSem);
2140 break;
2141 }
2142 case TargetOpcode::G_FPTRUNC:
2143 case TargetOpcode::G_INTRINSIC_FPTRUNC_ROUND: {
2144 computeKnownFPClassForFPTrunc(MI, DemandedElts, InterestedClasses, Known,
2145 Depth);
2146 break;
2147 }
2148 case TargetOpcode::G_SITOFP:
2149 case TargetOpcode::G_UITOFP: {
2150 // Cannot produce nan
2151 Known.knownNot(RuleOut: fcNan);
2152
2153 // Integers cannot be subnormal
2154 Known.knownNot(RuleOut: fcSubnormal);
2155
2156 // sitofp and uitofp turn into +0.0 for zero.
2157 Known.knownNot(RuleOut: fcNegZero);
2158
2159 // UIToFP is always non-negative regardless of known bits.
2160 if (Opcode == TargetOpcode::G_UITOFP)
2161 Known.signBitMustBeZero();
2162
2163 // Only compute known bits if we can learn something useful from them.
2164 if (!(InterestedClasses & (fcPosZero | fcNormal | fcInf)))
2165 break;
2166
2167 Register Val = MI.getOperand(i: 1).getReg();
2168 LLT Ty = MRI.getType(Reg: Val);
2169 KnownBits IntKnown = getKnownBits(
2170 R: Val, DemandedElts: Ty.isVector() ? DemandedElts : APInt(1, 1), Depth: Depth + 1);
2171
2172 // If the integer is non-zero, the result cannot be +0.0.
2173 if (IntKnown.isNonZero())
2174 Known.knownNot(RuleOut: fcPosZero);
2175
2176 if (Opcode == TargetOpcode::G_SITOFP) {
2177 // If the signed integer is known non-negative, the result is
2178 // non-negative. If the signed integer is known negative, the result is
2179 // negative.
2180 if (IntKnown.isNonNegative())
2181 Known.signBitMustBeZero();
2182 else if (IntKnown.isNegative())
2183 Known.signBitMustBeOne();
2184 }
2185
2186 if (InterestedClasses & fcInf) {
2187 LLT FPTy = DstTy.getScalarType();
2188 const fltSemantics &FltSem = getFltSemanticForLLT(Ty: FPTy);
2189
2190 // Compute the effective integer width after removing known-zero leading
2191 // bits, to check if the result can overflow to infinity.
2192 int IntSize = IntKnown.getBitWidth();
2193 if (Opcode == TargetOpcode::G_UITOFP)
2194 IntSize -= IntKnown.countMinLeadingZeros();
2195 else
2196 IntSize -= IntKnown.countMinSignBits();
2197
2198 // If the exponent of the largest finite FP value can hold the largest
2199 // integer, the result of the cast must be finite.
2200 if (ilogb(Arg: APFloat::getLargest(Sem: FltSem)) >= IntSize)
2201 Known.knownNot(RuleOut: fcInf);
2202 }
2203
2204 break;
2205 }
2206 // case TargetOpcode::G_MERGE_VALUES:
2207 case TargetOpcode::G_BUILD_VECTOR:
2208 case TargetOpcode::G_CONCAT_VECTORS: {
2209 GMergeLikeInstr &Merge = cast<GMergeLikeInstr>(Val&: MI);
2210
2211 if (!DstTy.isFixedVector())
2212 break;
2213
2214 bool First = true;
2215 for (unsigned Idx = 0; Idx < Merge.getNumSources(); ++Idx) {
2216 // We know the index we are inserting to, so clear it from Vec check.
2217 bool NeedsElt = DemandedElts[Idx];
2218
2219 // Do we demand the inserted element?
2220 if (NeedsElt) {
2221 Register Src = Merge.getSourceReg(I: Idx);
2222 if (First) {
2223 computeKnownFPClass(R: Src, Known, InterestedClasses, Depth: Depth + 1);
2224 First = false;
2225 } else {
2226 KnownFPClass Known2;
2227 computeKnownFPClass(R: Src, Known&: Known2, InterestedClasses, Depth: Depth + 1);
2228 Known |= Known2;
2229 }
2230
2231 // If we don't know any bits, early out.
2232 if (Known.isUnknown())
2233 break;
2234 }
2235 }
2236
2237 break;
2238 }
2239 case TargetOpcode::G_EXTRACT_VECTOR_ELT: {
2240 // Look through extract element. If the index is non-constant or
2241 // out-of-range demand all elements, otherwise just the extracted
2242 // element.
2243 GExtractVectorElement &Extract = cast<GExtractVectorElement>(Val&: MI);
2244 Register Vec = Extract.getVectorReg();
2245 Register Idx = Extract.getIndexReg();
2246
2247 auto CIdx = getIConstantVRegVal(VReg: Idx, MRI);
2248
2249 LLT VecTy = MRI.getType(Reg: Vec);
2250
2251 if (VecTy.isFixedVector()) {
2252 unsigned NumElts = VecTy.getNumElements();
2253 APInt DemandedVecElts = APInt::getAllOnes(numBits: NumElts);
2254 if (CIdx && CIdx->ult(RHS: NumElts))
2255 DemandedVecElts = APInt::getOneBitSet(numBits: NumElts, BitNo: CIdx->getZExtValue());
2256 return computeKnownFPClass(R: Vec, DemandedElts: DemandedVecElts, InterestedClasses, Known,
2257 Depth: Depth + 1);
2258 }
2259
2260 break;
2261 }
2262 case TargetOpcode::G_INSERT_VECTOR_ELT: {
2263 GInsertVectorElement &Insert = cast<GInsertVectorElement>(Val&: MI);
2264 Register Vec = Insert.getVectorReg();
2265 Register Elt = Insert.getElementReg();
2266 Register Idx = Insert.getIndexReg();
2267
2268 LLT VecTy = MRI.getType(Reg: Vec);
2269
2270 if (VecTy.isScalableVector())
2271 return;
2272
2273 auto CIdx = getIConstantVRegVal(VReg: Idx, MRI);
2274
2275 unsigned NumElts = DemandedElts.getBitWidth();
2276 APInt DemandedVecElts = DemandedElts;
2277 bool NeedsElt = true;
2278 // If we know the index we are inserting to, clear it from Vec check.
2279 if (CIdx && CIdx->ult(RHS: NumElts)) {
2280 DemandedVecElts.clearBit(BitPosition: CIdx->getZExtValue());
2281 NeedsElt = DemandedElts[CIdx->getZExtValue()];
2282 }
2283
2284 // Do we demand the inserted element?
2285 if (NeedsElt) {
2286 computeKnownFPClass(R: Elt, Known, InterestedClasses, Depth: Depth + 1);
2287 // If we don't know any bits, early out.
2288 if (Known.isUnknown())
2289 break;
2290 } else {
2291 Known.setKnownFPClasses(fcNone);
2292 }
2293
2294 // Do we need anymore elements from Vec?
2295 if (!DemandedVecElts.isZero()) {
2296 KnownFPClass Known2;
2297 computeKnownFPClass(R: Vec, DemandedElts: DemandedVecElts, InterestedClasses, Known&: Known2,
2298 Depth: Depth + 1);
2299 Known |= Known2;
2300 }
2301
2302 break;
2303 }
2304 case TargetOpcode::G_SHUFFLE_VECTOR: {
2305 // For undef elements, we don't know anything about the common state of
2306 // the shuffle result.
2307 GShuffleVector &Shuf = cast<GShuffleVector>(Val&: MI);
2308 APInt DemandedLHS, DemandedRHS;
2309 if (DstTy.isScalableVector()) {
2310 assert(DemandedElts == APInt(1, 1));
2311 DemandedLHS = DemandedRHS = DemandedElts;
2312 } else {
2313 unsigned NumElts = MRI.getType(Reg: Shuf.getSrc1Reg()).getNumElements();
2314 if (!llvm::getShuffleDemandedElts(SrcWidth: NumElts, Mask: Shuf.getMask(), DemandedElts,
2315 DemandedLHS, DemandedRHS)) {
2316 Known.resetAll();
2317 return;
2318 }
2319 }
2320
2321 if (!!DemandedLHS) {
2322 Register LHS = Shuf.getSrc1Reg();
2323 computeKnownFPClass(R: LHS, DemandedElts: DemandedLHS, InterestedClasses, Known,
2324 Depth: Depth + 1);
2325
2326 // If we don't know any bits, early out.
2327 if (Known.isUnknown())
2328 break;
2329 } else {
2330 Known.setKnownFPClasses(fcNone);
2331 }
2332
2333 if (!!DemandedRHS) {
2334 KnownFPClass Known2;
2335 Register RHS = Shuf.getSrc2Reg();
2336 computeKnownFPClass(R: RHS, DemandedElts: DemandedRHS, InterestedClasses, Known&: Known2,
2337 Depth: Depth + 1);
2338 Known |= Known2;
2339 }
2340 break;
2341 }
2342 case TargetOpcode::G_PHI: {
2343 // Cap PHI recursion below the global limit to avoid spending the entire
2344 // budget chasing loop back-edges (matches ValueTracking's
2345 // PhiRecursionLimit).
2346 if (Depth + 2 > MaxAnalysisRecursionDepth)
2347 break;
2348 // PHI's operands are a mix of registers and basic blocks interleaved.
2349 // We only care about the register ones.
2350 bool First = true;
2351 for (unsigned Idx = 1; Idx < MI.getNumOperands(); Idx += 2) {
2352 const MachineOperand &Src = MI.getOperand(i: Idx);
2353 Register SrcReg = Src.getReg();
2354 if (First) {
2355 computeKnownFPClass(R: SrcReg, DemandedElts, InterestedClasses, Known,
2356 Depth: Depth + 1);
2357 First = false;
2358 } else {
2359 KnownFPClass Known2;
2360 computeKnownFPClass(R: SrcReg, DemandedElts, InterestedClasses, Known&: Known2,
2361 Depth: Depth + 1);
2362 Known = Known.intersectWith(RHS: Known2);
2363 }
2364 if (Known.isUnknown())
2365 break;
2366 }
2367 break;
2368 }
2369 case TargetOpcode::G_FREEZE: {
2370 Register Src = MI.getOperand(i: 1).getReg();
2371 if (isGuaranteedNotToBeUndefOrPoison(Reg: Src, MRI, Depth: Depth + 1)) {
2372 computeKnownFPClass(R: Src, DemandedElts, InterestedClasses, Known,
2373 Depth: Depth + 1);
2374 }
2375 break;
2376 }
2377 case TargetOpcode::COPY: {
2378 Register Src = MI.getOperand(i: 1).getReg();
2379
2380 if (!Src.isVirtual())
2381 return;
2382
2383 computeKnownFPClass(R: Src, DemandedElts, InterestedClasses, Known, Depth: Depth + 1);
2384 break;
2385 }
2386 }
2387}
2388
2389KnownFPClass
2390GISelValueTracking::computeKnownFPClass(Register R, const APInt &DemandedElts,
2391 FPClassTest InterestedClasses,
2392 unsigned Depth) {
2393 KnownFPClass KnownClasses;
2394 computeKnownFPClass(R, DemandedElts, InterestedClasses, Known&: KnownClasses, Depth);
2395 return KnownClasses;
2396}
2397
2398KnownFPClass GISelValueTracking::computeKnownFPClass(
2399 Register R, FPClassTest InterestedClasses, unsigned Depth) {
2400 KnownFPClass Known;
2401 computeKnownFPClass(R, Known, InterestedClasses, Depth);
2402 return Known;
2403}
2404
2405KnownFPClass GISelValueTracking::computeKnownFPClass(
2406 Register R, const APInt &DemandedElts, uint32_t Flags,
2407 FPClassTest InterestedClasses, unsigned Depth) {
2408 if (Flags & MachineInstr::MIFlag::FmNoNans)
2409 InterestedClasses &= ~fcNan;
2410 if (Flags & MachineInstr::MIFlag::FmNoInfs)
2411 InterestedClasses &= ~fcInf;
2412
2413 KnownFPClass Result =
2414 computeKnownFPClass(R, DemandedElts, InterestedClasses, Depth);
2415
2416 if (Flags & MachineInstr::MIFlag::FmNoNans)
2417 Result.setKnownFPClasses(Result.getKnownFPClasses() & ~fcNan);
2418 if (Flags & MachineInstr::MIFlag::FmNoInfs)
2419 Result.setKnownFPClasses(Result.getKnownFPClasses() & ~fcInf);
2420 return Result;
2421}
2422
2423KnownFPClass GISelValueTracking::computeKnownFPClass(
2424 Register R, uint32_t Flags, FPClassTest InterestedClasses, unsigned Depth) {
2425 LLT Ty = MRI.getType(Reg: R);
2426 APInt DemandedElts =
2427 Ty.isFixedVector() ? APInt::getAllOnes(numBits: Ty.getNumElements()) : APInt(1, 1);
2428 return computeKnownFPClass(R, DemandedElts, Flags, InterestedClasses, Depth);
2429}
2430
2431bool GISelValueTracking::isKnownNeverNaN(Register Val, bool SNaN) {
2432 const MachineInstr *DefMI = MRI.getVRegDef(Reg: Val);
2433 if (!DefMI)
2434 return false;
2435
2436 if (DefMI->getFlag(Flag: MachineInstr::FmNoNans))
2437 return true;
2438
2439 // IEEE 754 arithmetic operations always quiet signaling NaNs. Short-circuit
2440 // the value-tracking analysis for the SNaN-only case: if the defining op is
2441 // known to quiet sNaN, the output can never be an sNaN.
2442 if (SNaN) {
2443 switch (DefMI->getOpcode()) {
2444 default:
2445 break;
2446 case TargetOpcode::G_FADD:
2447 case TargetOpcode::G_STRICT_FADD:
2448 case TargetOpcode::G_FSUB:
2449 case TargetOpcode::G_STRICT_FSUB:
2450 case TargetOpcode::G_FMUL:
2451 case TargetOpcode::G_STRICT_FMUL:
2452 case TargetOpcode::G_FDIV:
2453 case TargetOpcode::G_FREM:
2454 case TargetOpcode::G_FMA:
2455 case TargetOpcode::G_STRICT_FMA:
2456 case TargetOpcode::G_FMAD:
2457 case TargetOpcode::G_FSQRT:
2458 case TargetOpcode::G_STRICT_FSQRT:
2459 // Note: G_FABS and G_FNEG are bit-manipulation ops that preserve sNaN
2460 // exactly (LLVM LangRef: "never change anything except possibly the sign
2461 // bit"). They must NOT be listed here.
2462 case TargetOpcode::G_FSIN:
2463 case TargetOpcode::G_FCOS:
2464 case TargetOpcode::G_FSINCOS:
2465 case TargetOpcode::G_FTAN:
2466 case TargetOpcode::G_FASIN:
2467 case TargetOpcode::G_FACOS:
2468 case TargetOpcode::G_FATAN:
2469 case TargetOpcode::G_FATAN2:
2470 case TargetOpcode::G_FSINH:
2471 case TargetOpcode::G_FCOSH:
2472 case TargetOpcode::G_FTANH:
2473 case TargetOpcode::G_FEXP:
2474 case TargetOpcode::G_FEXP2:
2475 case TargetOpcode::G_FEXP10:
2476 case TargetOpcode::G_FLOG:
2477 case TargetOpcode::G_FLOG2:
2478 case TargetOpcode::G_FLOG10:
2479 case TargetOpcode::G_FPOW:
2480 case TargetOpcode::G_FPOWI:
2481 case TargetOpcode::G_FLDEXP:
2482 case TargetOpcode::G_STRICT_FLDEXP:
2483 case TargetOpcode::G_FFREXP:
2484 case TargetOpcode::G_INTRINSIC_TRUNC:
2485 case TargetOpcode::G_INTRINSIC_ROUND:
2486 case TargetOpcode::G_INTRINSIC_ROUNDEVEN:
2487 case TargetOpcode::G_FFLOOR:
2488 case TargetOpcode::G_FCEIL:
2489 case TargetOpcode::G_FRINT:
2490 case TargetOpcode::G_FNEARBYINT:
2491 case TargetOpcode::G_FPEXT:
2492 case TargetOpcode::G_FPTRUNC:
2493 case TargetOpcode::G_FCANONICALIZE:
2494 case TargetOpcode::G_FMINNUM:
2495 case TargetOpcode::G_FMAXNUM:
2496 case TargetOpcode::G_FMINNUM_IEEE:
2497 case TargetOpcode::G_FMAXNUM_IEEE:
2498 case TargetOpcode::G_FMINIMUM:
2499 case TargetOpcode::G_FMAXIMUM:
2500 case TargetOpcode::G_FMINIMUMNUM:
2501 case TargetOpcode::G_FMAXIMUMNUM:
2502 return true;
2503 }
2504 }
2505
2506 KnownFPClass FPClass = computeKnownFPClass(R: Val, InterestedClasses: SNaN ? fcSNan : fcNan);
2507
2508 if (SNaN)
2509 return FPClass.isKnownNever(Mask: fcSNan);
2510
2511 return FPClass.isKnownNeverNaN();
2512}
2513
2514bool GISelValueTracking::isKnownNeverLogicalZero(Register Val, unsigned Depth) {
2515 KnownFPClass Known = computeKnownFPClass(R: Val, InterestedClasses: fcZero | fcSubnormal, Depth);
2516 LLT Ty = MRI.getType(Reg: Val).getScalarType();
2517 return Known.isKnownNeverLogicalZero(
2518 Mode: MF.getDenormalMode(FPType: getFltSemanticForLLT(Ty)));
2519}
2520
2521/// Compute number of sign bits for the intersection of \p Src0 and \p Src1
2522unsigned GISelValueTracking::computeNumSignBitsMin(Register Src0, Register Src1,
2523 const APInt &DemandedElts,
2524 unsigned Depth) {
2525 // Test src1 first, since we canonicalize simpler expressions to the RHS.
2526 unsigned Src1SignBits = computeNumSignBits(R: Src1, DemandedElts, Depth);
2527 if (Src1SignBits == 1)
2528 return 1;
2529 return std::min(a: computeNumSignBits(R: Src0, DemandedElts, Depth), b: Src1SignBits);
2530}
2531
2532/// Compute the known number of sign bits with attached range metadata in the
2533/// memory operand. If this is an extending load, accounts for the behavior of
2534/// the high bits.
2535static unsigned computeNumSignBitsFromRangeMetadata(const GAnyLoad *Ld,
2536 unsigned TyBits) {
2537 const MDNode *Ranges = Ld->getRanges();
2538 if (!Ranges)
2539 return 1;
2540
2541 ConstantRange CR = getConstantRangeFromMetadata(RangeMD: *Ranges);
2542 if (TyBits > CR.getBitWidth()) {
2543 switch (Ld->getOpcode()) {
2544 case TargetOpcode::G_SEXTLOAD:
2545 CR = CR.signExtend(BitWidth: TyBits);
2546 break;
2547 case TargetOpcode::G_ZEXTLOAD:
2548 CR = CR.zeroExtend(BitWidth: TyBits);
2549 break;
2550 default:
2551 break;
2552 }
2553 }
2554
2555 return std::min(a: CR.getSignedMin().getNumSignBits(),
2556 b: CR.getSignedMax().getNumSignBits());
2557}
2558
2559unsigned GISelValueTracking::computeNumSignBits(Register R,
2560 const APInt &DemandedElts,
2561 unsigned Depth) {
2562 MachineInstr &MI = *MRI.getVRegDef(Reg: R);
2563 unsigned Opcode = MI.getOpcode();
2564
2565 if (Opcode == TargetOpcode::G_CONSTANT)
2566 return MI.getOperand(i: 1).getCImm()->getValue().getNumSignBits();
2567
2568 if (Depth == getMaxDepth())
2569 return 1;
2570
2571 if (!DemandedElts)
2572 return 1; // No demanded elts, better to assume we don't know anything.
2573
2574 LLT DstTy = MRI.getType(Reg: R);
2575 const unsigned TyBits = DstTy.getScalarSizeInBits();
2576
2577 // Handle the case where this is called on a register that does not have a
2578 // type constraint. This is unlikely to occur except by looking through copies
2579 // but it is possible for the initial register being queried to be in this
2580 // state.
2581 if (!DstTy.isValid())
2582 return 1;
2583
2584 unsigned FirstAnswer = 1;
2585 switch (Opcode) {
2586 case TargetOpcode::COPY: {
2587 MachineOperand &Src = MI.getOperand(i: 1);
2588 if (Src.getReg().isVirtual() && Src.getSubReg() == 0 &&
2589 MRI.getType(Reg: Src.getReg()).isValid()) {
2590 // Don't increment Depth for this one since we didn't do any work.
2591 return computeNumSignBits(R: Src.getReg(), DemandedElts, Depth);
2592 }
2593
2594 return 1;
2595 }
2596 case TargetOpcode::G_FREEZE: {
2597 Register Src = MI.getOperand(i: 1).getReg();
2598 if (isGuaranteedNotToBeUndefOrPoison(Reg: Src, MRI, Depth: Depth + 1))
2599 return computeNumSignBits(R: Src, DemandedElts, Depth: Depth + 1);
2600 break;
2601 }
2602 case TargetOpcode::G_SEXT: {
2603 Register Src = MI.getOperand(i: 1).getReg();
2604 LLT SrcTy = MRI.getType(Reg: Src);
2605 unsigned Tmp = TyBits - SrcTy.getScalarSizeInBits();
2606 return computeNumSignBits(R: Src, DemandedElts, Depth: Depth + 1) + Tmp;
2607 }
2608 case TargetOpcode::G_ASSERT_SEXT:
2609 case TargetOpcode::G_SEXT_INREG: {
2610 // Max of the input and what this extends.
2611 Register Src = MI.getOperand(i: 1).getReg();
2612 unsigned SrcBits = MI.getOperand(i: 2).getImm();
2613 unsigned InRegBits = TyBits - SrcBits + 1;
2614 return std::max(a: computeNumSignBits(R: Src, DemandedElts, Depth: Depth + 1),
2615 b: InRegBits);
2616 }
2617 case TargetOpcode::G_LOAD: {
2618 GLoad *Ld = cast<GLoad>(Val: &MI);
2619 if (DemandedElts != 1 || !getDataLayout().isLittleEndian())
2620 break;
2621
2622 return computeNumSignBitsFromRangeMetadata(Ld, TyBits);
2623 }
2624 case TargetOpcode::G_SEXTLOAD: {
2625 GSExtLoad *Ld = cast<GSExtLoad>(Val: &MI);
2626
2627 // FIXME: We need an in-memory type representation.
2628 if (DstTy.isVector())
2629 return 1;
2630
2631 unsigned NumBits = computeNumSignBitsFromRangeMetadata(Ld, TyBits);
2632 if (NumBits != 1)
2633 return NumBits;
2634
2635 // e.g. i16->i32 = '17' bits known.
2636 const MachineMemOperand *MMO = *MI.memoperands_begin();
2637 return TyBits - MMO->getSizeInBits().getValue() + 1;
2638 }
2639 case TargetOpcode::G_ZEXTLOAD: {
2640 GZExtLoad *Ld = cast<GZExtLoad>(Val: &MI);
2641
2642 // FIXME: We need an in-memory type representation.
2643 if (DstTy.isVector())
2644 return 1;
2645
2646 unsigned NumBits = computeNumSignBitsFromRangeMetadata(Ld, TyBits);
2647 if (NumBits != 1)
2648 return NumBits;
2649
2650 // e.g. i16->i32 = '16' bits known.
2651 const MachineMemOperand *MMO = *MI.memoperands_begin();
2652 return TyBits - MMO->getSizeInBits().getValue();
2653 }
2654 case TargetOpcode::G_AND:
2655 case TargetOpcode::G_OR:
2656 case TargetOpcode::G_XOR: {
2657 Register Src1 = MI.getOperand(i: 1).getReg();
2658 unsigned Src1NumSignBits =
2659 computeNumSignBits(R: Src1, DemandedElts, Depth: Depth + 1);
2660 if (Src1NumSignBits != 1) {
2661 Register Src2 = MI.getOperand(i: 2).getReg();
2662 unsigned Src2NumSignBits =
2663 computeNumSignBits(R: Src2, DemandedElts, Depth: Depth + 1);
2664 FirstAnswer = std::min(a: Src1NumSignBits, b: Src2NumSignBits);
2665 }
2666 break;
2667 }
2668 case TargetOpcode::G_ASHR: {
2669 Register Src1 = MI.getOperand(i: 1).getReg();
2670 Register Src2 = MI.getOperand(i: 2).getReg();
2671 FirstAnswer = computeNumSignBits(R: Src1, DemandedElts, Depth: Depth + 1);
2672 if (auto C = getValidMinimumShiftAmount(R: Src2, DemandedElts, Depth: Depth + 1))
2673 FirstAnswer = std::min<uint64_t>(a: FirstAnswer + *C, b: TyBits);
2674 break;
2675 }
2676 case TargetOpcode::G_SHL: {
2677 Register Src1 = MI.getOperand(i: 1).getReg();
2678 Register Src2 = MI.getOperand(i: 2).getReg();
2679 if (std::optional<ConstantRange> ShAmtRange =
2680 getValidShiftAmountRange(R: Src2, DemandedElts, Depth: Depth + 1)) {
2681 uint64_t MaxShAmt = ShAmtRange->getUnsignedMax().getZExtValue();
2682 uint64_t MinShAmt = ShAmtRange->getUnsignedMin().getZExtValue();
2683
2684 MachineInstr &ExtMI = *MRI.getVRegDef(Reg: Src1);
2685 unsigned ExtOpc = ExtMI.getOpcode();
2686
2687 // Try to look through ZERO/SIGN/ANY_EXTEND. If all extended bits are
2688 // shifted out, then we can compute the number of sign bits for the
2689 // operand being extended. A future improvement could be to pass along the
2690 // "shifted left by" information in the recursive calls to
2691 // ComputeKnownSignBits. Allowing us to handle this more generically.
2692 if (ExtOpc == TargetOpcode::G_SEXT || ExtOpc == TargetOpcode::G_ZEXT ||
2693 ExtOpc == TargetOpcode::G_ANYEXT) {
2694 LLT ExtTy = MRI.getType(Reg: Src1);
2695 Register Extendee = ExtMI.getOperand(i: 1).getReg();
2696 LLT ExtendeeTy = MRI.getType(Reg: Extendee);
2697 uint64_t SizeDiff =
2698 ExtTy.getScalarSizeInBits() - ExtendeeTy.getScalarSizeInBits();
2699
2700 if (SizeDiff <= MinShAmt) {
2701 unsigned Tmp =
2702 SizeDiff + computeNumSignBits(R: Extendee, DemandedElts, Depth: Depth + 1);
2703 if (MaxShAmt < Tmp)
2704 return Tmp - MaxShAmt;
2705 }
2706 }
2707 // shl destroys sign bits, ensure it doesn't shift out all sign bits.
2708 unsigned Tmp = computeNumSignBits(R: Src1, DemandedElts, Depth: Depth + 1);
2709 if (MaxShAmt < Tmp)
2710 return Tmp - MaxShAmt;
2711 }
2712 break;
2713 }
2714 case TargetOpcode::G_ROTL:
2715 case TargetOpcode::G_ROTR: {
2716 Register SrcReg = MI.getOperand(i: 1).getReg();
2717 unsigned Tmp = computeNumSignBits(R: SrcReg, DemandedElts, Depth: Depth + 1);
2718 auto MaybeAmt =
2719 isConstantOrConstantSplatVector(Def: MI.getOperand(i: 2).getReg(), MRI);
2720 FirstAnswer =
2721 SignBitsOps::rot(SrcSignBits: Tmp, BitWidth: TyBits, RotAmt: MaybeAmt, IsRotateRight: Opcode == TargetOpcode::G_ROTR);
2722 break;
2723 }
2724 case TargetOpcode::G_SAVGFLOOR:
2725 case TargetOpcode::G_SAVGCEIL: {
2726 Register Src1 = MI.getOperand(i: 1).getReg();
2727 Register Src2 = MI.getOperand(i: 2).getReg();
2728 FirstAnswer = computeNumSignBitsMin(Src0: Src1, Src1: Src2, DemandedElts, Depth: Depth + 1);
2729 break;
2730 }
2731 case TargetOpcode::G_SREM: {
2732 // The sign bit is the LHS's sign bit, except when the result of the
2733 // remainder is zero. The magnitude of the result should be less than or
2734 // equal to the magnitude of the LHS. Therefore, the result should have
2735 // at least as many sign bits as the left hand side.
2736 Register Src = MI.getOperand(i: 1).getReg();
2737 return computeNumSignBits(R: Src, DemandedElts, Depth: Depth + 1);
2738 }
2739 case TargetOpcode::G_TRUNC: {
2740 Register Src = MI.getOperand(i: 1).getReg();
2741 LLT SrcTy = MRI.getType(Reg: Src);
2742
2743 // Check if the sign bits of source go down as far as the truncated value.
2744 unsigned NumSrcBits = SrcTy.getScalarSizeInBits();
2745 unsigned NumSrcSignBits = computeNumSignBits(R: Src, DemandedElts, Depth: Depth + 1);
2746 if (NumSrcSignBits > (NumSrcBits - TyBits))
2747 return NumSrcSignBits - (NumSrcBits - TyBits);
2748 break;
2749 }
2750 case TargetOpcode::G_SELECT: {
2751 return computeNumSignBitsMin(Src0: MI.getOperand(i: 2).getReg(),
2752 Src1: MI.getOperand(i: 3).getReg(), DemandedElts,
2753 Depth: Depth + 1);
2754 }
2755 case TargetOpcode::G_SMIN:
2756 case TargetOpcode::G_SMAX:
2757 case TargetOpcode::G_UMIN:
2758 case TargetOpcode::G_UMAX:
2759 // TODO: Handle clamp pattern with number of sign bits for SMIN/SMAX.
2760 return computeNumSignBitsMin(Src0: MI.getOperand(i: 1).getReg(),
2761 Src1: MI.getOperand(i: 2).getReg(), DemandedElts,
2762 Depth: Depth + 1);
2763 case TargetOpcode::G_SADDO:
2764 case TargetOpcode::G_SADDE:
2765 case TargetOpcode::G_UADDO:
2766 case TargetOpcode::G_UADDE:
2767 case TargetOpcode::G_SSUBO:
2768 case TargetOpcode::G_SSUBE:
2769 case TargetOpcode::G_USUBO:
2770 case TargetOpcode::G_USUBE:
2771 case TargetOpcode::G_SMULO:
2772 case TargetOpcode::G_UMULO: {
2773 // If compares returns 0/-1, all bits are sign bits.
2774 // We know that we have an integer-based boolean since these operations
2775 // are only available for integer.
2776 if (MI.getOperand(i: 1).getReg() == R) {
2777 if (TL.getBooleanContents(isVec: DstTy.isVector(), isFloat: false) ==
2778 TargetLowering::ZeroOrNegativeOneBooleanContent)
2779 return TyBits;
2780 }
2781
2782 break;
2783 }
2784 case TargetOpcode::G_SUB: {
2785 Register Src2 = MI.getOperand(i: 2).getReg();
2786 unsigned Src2NumSignBits =
2787 computeNumSignBits(R: Src2, DemandedElts, Depth: Depth + 1);
2788 if (Src2NumSignBits == 1)
2789 return 1; // Early out.
2790
2791 // Handle NEG.
2792 Register Src1 = MI.getOperand(i: 1).getReg();
2793 KnownBits Known1 = getKnownBits(R: Src1, DemandedElts, Depth);
2794 if (Known1.isZero()) {
2795 KnownBits Known2 = getKnownBits(R: Src2, DemandedElts, Depth);
2796 // If the input is known to be 0 or 1, the output is 0/-1, which is all
2797 // sign bits set.
2798 if ((Known2.Zero | 1).isAllOnes())
2799 return TyBits;
2800
2801 // If the input is known to be positive (the sign bit is known clear),
2802 // the output of the NEG has, at worst, the same number of sign bits as
2803 // the input.
2804 if (Known2.isNonNegative()) {
2805 FirstAnswer = Src2NumSignBits;
2806 break;
2807 }
2808
2809 // Otherwise, we treat this like a SUB.
2810 }
2811
2812 unsigned Src1NumSignBits =
2813 computeNumSignBits(R: Src1, DemandedElts, Depth: Depth + 1);
2814 if (Src1NumSignBits == 1)
2815 return 1; // Early Out.
2816
2817 // Sub can have at most one carry bit. Thus we know that the output
2818 // is, at worst, one more bit than the inputs.
2819 FirstAnswer = std::min(a: Src1NumSignBits, b: Src2NumSignBits) - 1;
2820 break;
2821 }
2822 case TargetOpcode::G_ADD: {
2823 Register Src2 = MI.getOperand(i: 2).getReg();
2824 unsigned Src2NumSignBits =
2825 computeNumSignBits(R: Src2, DemandedElts, Depth: Depth + 1);
2826 if (Src2NumSignBits <= 2)
2827 return 1; // Early out.
2828
2829 Register Src1 = MI.getOperand(i: 1).getReg();
2830 unsigned Src1NumSignBits =
2831 computeNumSignBits(R: Src1, DemandedElts, Depth: Depth + 1);
2832 if (Src1NumSignBits == 1)
2833 return 1; // Early Out.
2834
2835 // Special case decrementing a value (ADD X, -1):
2836 KnownBits Known2 = getKnownBits(R: Src2, DemandedElts, Depth);
2837 if (Known2.isAllOnes()) {
2838 KnownBits Known1 = getKnownBits(R: Src1, DemandedElts, Depth);
2839 // If the input is known to be 0 or 1, the output is 0/-1, which is all
2840 // sign bits set.
2841 if ((Known1.Zero | 1).isAllOnes())
2842 return TyBits;
2843
2844 // If we are subtracting one from a positive number, there is no carry
2845 // out of the result.
2846 if (Known1.isNonNegative()) {
2847 FirstAnswer = Src1NumSignBits;
2848 break;
2849 }
2850
2851 // Otherwise, we treat this like an ADD.
2852 }
2853
2854 // Add 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_MUL: {
2860 unsigned Src2NumSignBits =
2861 computeNumSignBits(R: MI.getOperand(i: 2).getReg(), DemandedElts, Depth: Depth + 1);
2862 if (Src2NumSignBits == 1)
2863 break;
2864 unsigned Src1NumSignBits =
2865 computeNumSignBits(R: MI.getOperand(i: 1).getReg(), DemandedElts, Depth: Depth + 1);
2866 if (Src1NumSignBits == 1)
2867 break;
2868
2869 // The product needs at most the sum of the operands' signed widths.
2870 unsigned OutValidBits =
2871 (TyBits - Src1NumSignBits + 1) + (TyBits - Src2NumSignBits + 1);
2872 if (OutValidBits <= TyBits)
2873 FirstAnswer = TyBits - OutValidBits + 1;
2874 break;
2875 }
2876 case TargetOpcode::G_FCMP:
2877 case TargetOpcode::G_ICMP: {
2878 bool IsFP = Opcode == TargetOpcode::G_FCMP;
2879 if (TyBits == 1)
2880 break;
2881 auto BC = TL.getBooleanContents(isVec: DstTy.isVector(), isFloat: IsFP);
2882 if (BC == TargetLoweringBase::ZeroOrNegativeOneBooleanContent)
2883 return TyBits; // All bits are sign bits.
2884 if (BC == TargetLowering::ZeroOrOneBooleanContent)
2885 return TyBits - 1; // Every always-zero bit is a sign bit.
2886 break;
2887 }
2888 case TargetOpcode::G_UNMERGE_VALUES: {
2889 unsigned NumOps = MI.getNumOperands();
2890 Register SrcReg = MI.getOperand(i: NumOps - 1).getReg();
2891 LLT SrcTy = MRI.getType(Reg: SrcReg);
2892
2893 if ((SrcTy.isVector() && SrcTy.getScalarType() != DstTy.getScalarType()) ||
2894 (SrcTy.isScalar() && DstTy.isVector()))
2895 break;
2896
2897 // Figure out the result operand index
2898 unsigned DstIdx = MI.findRegisterDefOperandIdx(Reg: R, TRI: nullptr);
2899
2900 APInt SubDemandedElts = DemandedElts;
2901 unsigned DstLanes = DstTy.isVector() ? DstTy.getNumElements() : 1;
2902 if (SrcTy.isVector()) {
2903 SubDemandedElts =
2904 DemandedElts.zext(width: SrcTy.getNumElements()).shl(shiftAmt: DstIdx * DstLanes);
2905 }
2906
2907 unsigned SrcOpKnown =
2908 computeNumSignBits(R: SrcReg, DemandedElts: SubDemandedElts, Depth: Depth + 1);
2909 if (SrcTy.isVector()) {
2910 FirstAnswer = SrcOpKnown;
2911 } else if (SrcOpKnown >= (MI.getNumOperands() - DstIdx - 2) * TyBits) {
2912 FirstAnswer = SrcOpKnown >= (MI.getNumOperands() - DstIdx - 1) * TyBits
2913 ? TyBits
2914 : SrcOpKnown % TyBits;
2915 }
2916 break;
2917 }
2918 case TargetOpcode::G_BUILD_VECTOR: {
2919 // Collect the known bits that are shared by every demanded vector element.
2920 FirstAnswer = TyBits;
2921 APInt SingleDemandedElt(1, 1);
2922 for (const auto &[I, MO] : enumerate(First: drop_begin(RangeOrContainer: MI.operands()))) {
2923 if (!DemandedElts[I])
2924 continue;
2925
2926 unsigned Tmp2 =
2927 computeNumSignBits(R: MO.getReg(), DemandedElts: SingleDemandedElt, Depth: Depth + 1);
2928 FirstAnswer = std::min(a: FirstAnswer, b: Tmp2);
2929
2930 // If we don't know any bits, early out.
2931 if (FirstAnswer == 1)
2932 break;
2933 }
2934 break;
2935 }
2936 case TargetOpcode::G_CONCAT_VECTORS: {
2937 if (MRI.getType(Reg: MI.getOperand(i: 0).getReg()).isScalableVector())
2938 break;
2939 FirstAnswer = TyBits;
2940 // Determine the minimum number of sign bits across all demanded
2941 // elts of the input vectors. Early out if the result is already 1.
2942 unsigned NumSubVectorElts =
2943 MRI.getType(Reg: MI.getOperand(i: 1).getReg()).getNumElements();
2944 for (const auto &[I, MO] : enumerate(First: drop_begin(RangeOrContainer: MI.operands()))) {
2945 APInt DemandedSub =
2946 DemandedElts.extractBits(numBits: NumSubVectorElts, bitPosition: I * NumSubVectorElts);
2947 if (!DemandedSub)
2948 continue;
2949 unsigned Tmp2 = computeNumSignBits(R: MO.getReg(), DemandedElts: DemandedSub, Depth: Depth + 1);
2950
2951 FirstAnswer = std::min(a: FirstAnswer, b: Tmp2);
2952
2953 // If we don't know any bits, early out.
2954 if (FirstAnswer == 1)
2955 break;
2956 }
2957 break;
2958 }
2959 case TargetOpcode::G_VECTOR_COMPRESS: {
2960 // Each result lane is either a lane of the source vector or the passthru,
2961 // so the number of sign bits is the minimum of the two.
2962 Register Vec = MI.getOperand(i: 1).getReg();
2963 Register PassThru = MI.getOperand(i: 3).getReg();
2964 unsigned Tmp = computeNumSignBits(R: PassThru, DemandedElts, Depth: Depth + 1);
2965 // If passthru contributes nothing, fall back to the KnownBits refinement.
2966 if (Tmp == 1)
2967 break;
2968 // Compression can move any source lane to any result position, so all
2969 // source lanes are demanded.
2970 APInt DemandedSrcElts = APInt::getAllOnes(numBits: DemandedElts.getBitWidth());
2971 unsigned Tmp2 = computeNumSignBits(R: Vec, DemandedElts: DemandedSrcElts, Depth: Depth + 1);
2972 FirstAnswer = std::min(a: Tmp, b: Tmp2);
2973 break;
2974 }
2975 case TargetOpcode::G_INSERT_VECTOR_ELT: {
2976 GInsertVectorElement &Insert = cast<GInsertVectorElement>(Val&: MI);
2977 Register InVec = Insert.getVectorReg();
2978 Register InVal = Insert.getElementReg();
2979 LLT VecVT = MRI.getType(Reg: InVec);
2980
2981 // If we know the element index, split the demand between the inserted
2982 // value and the source vector, otherwise assume we need both. Scalable
2983 // vectors carry no per-lane demand, so they always take the minimum of the
2984 // whole vector and the inserted value.
2985 bool DemandedVal = true;
2986 APInt DemandedVecElts = DemandedElts;
2987 if (!VecVT.isScalableVector()) {
2988 unsigned NumElts = VecVT.getNumElements();
2989 auto ConstEltNo = getIConstantVRegVal(VReg: Insert.getIndexReg(), MRI);
2990 if (ConstEltNo && ConstEltNo->ult(RHS: NumElts)) {
2991 unsigned EltIdx = ConstEltNo->getZExtValue();
2992 DemandedVal = !!DemandedElts[EltIdx];
2993 DemandedVecElts.clearBit(BitPosition: EltIdx);
2994 }
2995 }
2996
2997 unsigned Tmp = TyBits;
2998 if (DemandedVal) {
2999 // TODO: Handle implicit truncation of inserted elements.
3000 if (MRI.getType(Reg: InVal).getSizeInBits() != TyBits)
3001 break;
3002 unsigned ValSignBits = computeNumSignBits(R: InVal, DemandedElts: APInt(1, 1), Depth: Depth + 1);
3003 Tmp = std::min(a: Tmp, b: ValSignBits);
3004 }
3005 if (!!DemandedVecElts) {
3006 unsigned VecSignBits =
3007 computeNumSignBits(R: InVec, DemandedElts: DemandedVecElts, Depth: Depth + 1);
3008 Tmp = std::min(a: Tmp, b: VecSignBits);
3009 }
3010 return Tmp;
3011 }
3012 case TargetOpcode::G_EXTRACT_VECTOR_ELT: {
3013 GExtractVectorElement &Extract = cast<GExtractVectorElement>(Val&: MI);
3014 Register InVec = Extract.getVectorReg();
3015 Register EltNo = Extract.getIndexReg();
3016 LLT VecVT = MRI.getType(Reg: InVec);
3017 if (VecVT.isScalableVector())
3018 return computeNumSignBits(R: InVec, DemandedElts: APInt(1, 1), Depth: Depth + 1);
3019 unsigned NumSrcElts = VecVT.getNumElements();
3020 std::optional<APInt> ConstEltNo = getIConstantVRegVal(VReg: EltNo, MRI);
3021 APInt DemandedSrcElts =
3022 ConstEltNo && ConstEltNo->ult(RHS: NumSrcElts)
3023 ? APInt::getOneBitSet(numBits: NumSrcElts, BitNo: ConstEltNo->getZExtValue())
3024 : APInt::getAllOnes(numBits: NumSrcElts);
3025 return computeNumSignBits(R: InVec, DemandedElts: DemandedSrcElts, Depth: Depth + 1);
3026 }
3027 case TargetOpcode::G_EXTRACT_SUBVECTOR: {
3028 // Offset the demanded elts by the subvector index.
3029 Register SrcReg = MI.getOperand(i: 1).getReg();
3030 LLT SrcTy = MRI.getType(Reg: SrcReg);
3031 APInt DemandedSrcElts;
3032 if (SrcTy.isScalableVector()) {
3033 DemandedSrcElts = APInt(1, 1);
3034 } else {
3035 uint64_t Idx = MI.getOperand(i: 2).getImm();
3036 unsigned NumSrcElts = SrcTy.getNumElements();
3037 DemandedSrcElts = DemandedElts.zext(width: NumSrcElts).shl(shiftAmt: Idx);
3038 }
3039 return computeNumSignBits(R: SrcReg, DemandedElts: DemandedSrcElts, Depth: Depth + 1);
3040 }
3041 case TargetOpcode::G_SHUFFLE_VECTOR: {
3042 // Collect the minimum number of sign bits that are shared by every vector
3043 // element referenced by the shuffle.
3044 APInt DemandedLHS, DemandedRHS;
3045 Register Src1 = MI.getOperand(i: 1).getReg();
3046 unsigned NumElts = MRI.getType(Reg: Src1).getNumElements();
3047 if (!getShuffleDemandedElts(SrcWidth: NumElts, Mask: MI.getOperand(i: 3).getShuffleMask(),
3048 DemandedElts, DemandedLHS, DemandedRHS))
3049 return 1;
3050
3051 if (!!DemandedLHS)
3052 FirstAnswer = computeNumSignBits(R: Src1, DemandedElts: DemandedLHS, Depth: Depth + 1);
3053 // If we don't know anything, early out and try computeKnownBits fall-back.
3054 if (FirstAnswer == 1)
3055 break;
3056 if (!!DemandedRHS) {
3057 unsigned Tmp2 =
3058 computeNumSignBits(R: MI.getOperand(i: 2).getReg(), DemandedElts: DemandedRHS, Depth: Depth + 1);
3059 FirstAnswer = std::min(a: FirstAnswer, b: Tmp2);
3060 }
3061 break;
3062 }
3063 case TargetOpcode::G_SPLAT_VECTOR: {
3064 // Check if the sign bits of source go down as far as the truncated value.
3065 Register Src = MI.getOperand(i: 1).getReg();
3066 unsigned NumSrcSignBits = computeNumSignBits(R: Src, DemandedElts: APInt(1, 1), Depth: Depth + 1);
3067 unsigned NumSrcBits = MRI.getType(Reg: Src).getSizeInBits();
3068 if (NumSrcSignBits > (NumSrcBits - TyBits))
3069 return NumSrcSignBits - (NumSrcBits - TyBits);
3070 break;
3071 }
3072 case TargetOpcode::G_INTRINSIC:
3073 case TargetOpcode::G_INTRINSIC_W_SIDE_EFFECTS:
3074 case TargetOpcode::G_INTRINSIC_CONVERGENT:
3075 case TargetOpcode::G_INTRINSIC_CONVERGENT_W_SIDE_EFFECTS:
3076 default: {
3077 unsigned NumBits =
3078 TL.computeNumSignBitsForTargetInstr(Analysis&: *this, R, DemandedElts, MRI, Depth);
3079 if (NumBits > 1)
3080 FirstAnswer = std::max(a: FirstAnswer, b: NumBits);
3081 break;
3082 }
3083 }
3084
3085 // Finally, if we can prove that the top bits of the result are 0's or 1's,
3086 // use this information.
3087 KnownBits Known = getKnownBits(R, DemandedElts, Depth);
3088 return std::max(a: FirstAnswer, b: Known.countMinSignBits());
3089}
3090
3091unsigned GISelValueTracking::computeNumSignBits(Register R, unsigned Depth) {
3092 LLT Ty = MRI.getType(Reg: R);
3093 APInt DemandedElts =
3094 Ty.isFixedVector() ? APInt::getAllOnes(numBits: Ty.getNumElements()) : APInt(1, 1);
3095 return computeNumSignBits(R, DemandedElts, Depth);
3096}
3097
3098std::optional<ConstantRange> GISelValueTracking::getValidShiftAmountRange(
3099 Register R, const APInt &DemandedElts, unsigned Depth) {
3100 // Shifting more than the bitwidth is not valid.
3101 MachineInstr &MI = *MRI.getVRegDef(Reg: R);
3102 unsigned Opcode = MI.getOpcode();
3103
3104 LLT Ty = MRI.getType(Reg: R);
3105 unsigned BitWidth = Ty.getScalarSizeInBits();
3106
3107 if (Opcode == TargetOpcode::G_CONSTANT) {
3108 const APInt &ShAmt = MI.getOperand(i: 1).getCImm()->getValue();
3109 if (ShAmt.uge(RHS: BitWidth))
3110 return std::nullopt;
3111 return ConstantRange(ShAmt);
3112 }
3113
3114 if (Opcode == TargetOpcode::G_BUILD_VECTOR) {
3115 const APInt *MinAmt = nullptr, *MaxAmt = nullptr;
3116 for (unsigned I = 0, E = MI.getNumOperands() - 1; I != E; ++I) {
3117 if (!DemandedElts[I])
3118 continue;
3119 MachineInstr *Op = MRI.getVRegDef(Reg: MI.getOperand(i: I + 1).getReg());
3120 if (Op->getOpcode() != TargetOpcode::G_CONSTANT) {
3121 MinAmt = MaxAmt = nullptr;
3122 break;
3123 }
3124
3125 const APInt &ShAmt = Op->getOperand(i: 1).getCImm()->getValue();
3126 if (ShAmt.uge(RHS: BitWidth))
3127 return std::nullopt;
3128 if (!MinAmt || MinAmt->ugt(RHS: ShAmt))
3129 MinAmt = &ShAmt;
3130 if (!MaxAmt || MaxAmt->ult(RHS: ShAmt))
3131 MaxAmt = &ShAmt;
3132 }
3133 assert(((!MinAmt && !MaxAmt) || (MinAmt && MaxAmt)) &&
3134 "Failed to find matching min/max shift amounts");
3135 if (MinAmt && MaxAmt)
3136 return ConstantRange(*MinAmt, *MaxAmt + 1);
3137 }
3138
3139 // Use computeKnownBits to find a hidden constant/knownbits (usually type
3140 // legalized). e.g. Hidden behind multiple bitcasts/build_vector/casts etc.
3141 KnownBits KnownAmt = getKnownBits(R, DemandedElts, Depth);
3142 if (KnownAmt.getMaxValue().ult(RHS: BitWidth))
3143 return ConstantRange::fromKnownBits(Known: KnownAmt, /*IsSigned=*/false);
3144
3145 return std::nullopt;
3146}
3147
3148std::optional<uint64_t> GISelValueTracking::getValidMinimumShiftAmount(
3149 Register R, const APInt &DemandedElts, unsigned Depth) {
3150 if (std::optional<ConstantRange> AmtRange =
3151 getValidShiftAmountRange(R, DemandedElts, Depth))
3152 return AmtRange->getUnsignedMin().getZExtValue();
3153 return std::nullopt;
3154}
3155
3156void GISelValueTrackingAnalysisLegacy::getAnalysisUsage(
3157 AnalysisUsage &AU) const {
3158 AU.setPreservesAll();
3159 MachineFunctionPass::getAnalysisUsage(AU);
3160}
3161
3162bool GISelValueTrackingAnalysisLegacy::runOnMachineFunction(
3163 MachineFunction &MF) {
3164 return false;
3165}
3166
3167GISelValueTracking &GISelValueTrackingAnalysisLegacy::get(MachineFunction &MF) {
3168 if (!Info) {
3169 unsigned MaxDepth =
3170 MF.getTarget().getOptLevel() == CodeGenOptLevel::None ? 2 : 6;
3171 Info = std::make_unique<GISelValueTracking>(args&: MF, args&: MaxDepth);
3172 }
3173 return *Info;
3174}
3175
3176AnalysisKey GISelValueTrackingAnalysis::Key;
3177
3178GISelValueTrackingAnalysis::Result
3179GISelValueTrackingAnalysis::run(MachineFunction &MF,
3180 MachineFunctionAnalysisManager &MFAM) {
3181 unsigned MaxDepth =
3182 MF.getTarget().getOptLevel() == CodeGenOptLevel::None ? 2 : 6;
3183 return Result(MF, MaxDepth);
3184}
3185
3186static PreservedAnalyses
3187printGISelValueTracking(MachineFunction &MF,
3188 MachineFunctionAnalysisManager &MFAM, raw_ostream &OS,
3189 bool PrintFPClass) {
3190 auto &VTA = MFAM.getResult<GISelValueTrackingAnalysis>(IR&: MF);
3191 const auto &MRI = MF.getRegInfo();
3192 OS << "name: ";
3193 MF.getFunction().printAsOperand(O&: OS, /*PrintType=*/false);
3194 OS << '\n';
3195
3196 for (MachineBasicBlock &BB : MF) {
3197 for (MachineInstr &MI : BB) {
3198 for (MachineOperand &MO : MI.defs()) {
3199 if (!MO.isReg() || MO.getReg().isPhysical())
3200 continue;
3201 Register Reg = MO.getReg();
3202 if (!MRI.getType(Reg).isValid())
3203 continue;
3204 if (PrintFPClass) {
3205 KnownFPClass FPKnown = VTA.computeKnownFPClass(R: Reg);
3206 OS << " " << MO << " FPClasses:" << FPKnown.getKnownFPClasses()
3207 << " SignBitKnown:";
3208 if (FPKnown.getSignBit())
3209 OS << (*FPKnown.getSignBit() ? '1' : '0');
3210 else
3211 OS << '?';
3212 OS << '\n';
3213 } else {
3214 KnownBits Known = VTA.getKnownBits(R: Reg);
3215 unsigned SignedBits = VTA.computeNumSignBits(R: Reg);
3216 bool IsKnownNeverZero = VTA.isKnownNeverZero(R: Reg);
3217 OS << " " << MO << " KnownBits:" << Known
3218 << " SignBits:" << SignedBits
3219 << " IsKnownNeverZero:" << IsKnownNeverZero << '\n';
3220 }
3221 };
3222 }
3223 }
3224 return PreservedAnalyses::all();
3225}
3226
3227PreservedAnalyses
3228GISelValueTrackingPrinterPass::run(MachineFunction &MF,
3229 MachineFunctionAnalysisManager &MFAM) {
3230 return printGISelValueTracking(MF, MFAM, OS, PrintFPClass: false);
3231}
3232
3233PreservedAnalyses GISelValueTrackingFPClassPrinterPass::run(
3234 MachineFunction &MF, MachineFunctionAnalysisManager &MFAM) {
3235 return printGISelValueTracking(MF, MFAM, OS, PrintFPClass: true);
3236}
3237