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