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