LLVM 19.0.0git
GISelKnownBits.cpp
Go to the documentation of this file.
1//===- lib/CodeGen/GlobalISel/GISelKnownBits.cpp --------------*- C++ *-===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9/// Provides analysis for querying information about KnownBits during GISel
10/// passes.
11//
12//===----------------------------------------------------------------------===//
21#include "llvm/IR/Module.h"
23
24#define DEBUG_TYPE "gisel-known-bits"
25
26using namespace llvm;
27
29
31 "Analysis for ComputingKnownBits", false, true)
32
34 : MF(MF), MRI(MF.getRegInfo()), TL(*MF.getSubtarget().getTargetLowering()),
35 DL(MF.getFunction().getParent()->getDataLayout()), MaxDepth(MaxDepth) {}
36
38 const MachineInstr *MI = MRI.getVRegDef(R);
39 switch (MI->getOpcode()) {
40 case TargetOpcode::COPY:
41 return computeKnownAlignment(MI->getOperand(1).getReg(), Depth);
42 case TargetOpcode::G_ASSERT_ALIGN: {
43 // TODO: Min with source
44 return Align(MI->getOperand(2).getImm());
45 }
46 case TargetOpcode::G_FRAME_INDEX: {
47 int FrameIdx = MI->getOperand(1).getIndex();
48 return MF.getFrameInfo().getObjectAlign(FrameIdx);
49 }
50 case TargetOpcode::G_INTRINSIC:
51 case TargetOpcode::G_INTRINSIC_W_SIDE_EFFECTS:
52 case TargetOpcode::G_INTRINSIC_CONVERGENT:
53 case TargetOpcode::G_INTRINSIC_CONVERGENT_W_SIDE_EFFECTS:
54 default:
55 return TL.computeKnownAlignForTargetInstr(*this, R, MRI, Depth + 1);
56 }
57}
58
60 assert(MI.getNumExplicitDefs() == 1 &&
61 "expected single return generic instruction");
62 return getKnownBits(MI.getOperand(0).getReg());
63}
64
66 const LLT Ty = MRI.getType(R);
67 APInt DemandedElts =
69 return getKnownBits(R, DemandedElts);
70}
71
73 unsigned Depth) {
74 // For now, we only maintain the cache during one request.
75 assert(ComputeKnownBitsCache.empty() && "Cache should have been cleared");
76
77 KnownBits Known;
78 computeKnownBitsImpl(R, Known, DemandedElts, Depth);
79 ComputeKnownBitsCache.clear();
80 return Known;
81}
82
84 LLT Ty = MRI.getType(R);
85 unsigned BitWidth = Ty.getScalarSizeInBits();
87}
88
90 return getKnownBits(R).Zero;
91}
92
94
95LLVM_ATTRIBUTE_UNUSED static void
96dumpResult(const MachineInstr &MI, const KnownBits &Known, unsigned Depth) {
97 dbgs() << "[" << Depth << "] Compute known bits: " << MI << "[" << Depth
98 << "] Computed for: " << MI << "[" << Depth << "] Known: 0x"
99 << toString(Known.Zero | Known.One, 16, false) << "\n"
100 << "[" << Depth << "] Zero: 0x" << toString(Known.Zero, 16, false)
101 << "\n"
102 << "[" << Depth << "] One: 0x" << toString(Known.One, 16, false)
103 << "\n";
104}
105
106/// Compute known bits for the intersection of \p Src0 and \p Src1
107void GISelKnownBits::computeKnownBitsMin(Register Src0, Register Src1,
108 KnownBits &Known,
109 const APInt &DemandedElts,
110 unsigned Depth) {
111 // Test src1 first, since we canonicalize simpler expressions to the RHS.
112 computeKnownBitsImpl(Src1, Known, DemandedElts, Depth);
113
114 // If we don't know any bits, early out.
115 if (Known.isUnknown())
116 return;
117
118 KnownBits Known2;
119 computeKnownBitsImpl(Src0, Known2, DemandedElts, Depth);
120
121 // Only known if known in both the LHS and RHS.
122 Known = Known.intersectWith(Known2);
123}
124
125// Bitfield extract is computed as (Src >> Offset) & Mask, where Mask is
126// created using Width. Use this function when the inputs are KnownBits
127// objects. TODO: Move this KnownBits.h if this is usable in more cases.
128static KnownBits extractBits(unsigned BitWidth, const KnownBits &SrcOpKnown,
129 const KnownBits &OffsetKnown,
130 const KnownBits &WidthKnown) {
131 KnownBits Mask(BitWidth);
132 Mask.Zero = APInt::getBitsSetFrom(
134 Mask.One = APInt::getLowBitsSet(
136 return KnownBits::lshr(SrcOpKnown, OffsetKnown) & Mask;
137}
138
140 const APInt &DemandedElts,
141 unsigned Depth) {
142 MachineInstr &MI = *MRI.getVRegDef(R);
143 unsigned Opcode = MI.getOpcode();
144 LLT DstTy = MRI.getType(R);
145
146 // Handle the case where this is called on a register that does not have a
147 // type constraint (i.e. it has a register class constraint instead). This is
148 // unlikely to occur except by looking through copies but it is possible for
149 // the initial register being queried to be in this state.
150 if (!DstTy.isValid()) {
151 Known = KnownBits();
152 return;
153 }
154
155 unsigned BitWidth = DstTy.getScalarSizeInBits();
156 auto CacheEntry = ComputeKnownBitsCache.find(R);
157 if (CacheEntry != ComputeKnownBitsCache.end()) {
158 Known = CacheEntry->second;
159 LLVM_DEBUG(dbgs() << "Cache hit at ");
160 LLVM_DEBUG(dumpResult(MI, Known, Depth));
161 assert(Known.getBitWidth() == BitWidth && "Cache entry size doesn't match");
162 return;
163 }
164 Known = KnownBits(BitWidth); // Don't know anything
165
166 // Depth may get bigger than max depth if it gets passed to a different
167 // GISelKnownBits object.
168 // This may happen when say a generic part uses a GISelKnownBits object
169 // with some max depth, but then we hit TL.computeKnownBitsForTargetInstr
170 // which creates a new GISelKnownBits object with a different and smaller
171 // depth. If we just check for equality, we would never exit if the depth
172 // that is passed down to the target specific GISelKnownBits object is
173 // already bigger than its max depth.
174 if (Depth >= getMaxDepth())
175 return;
176
177 if (!DemandedElts)
178 return; // No demanded elts, better to assume we don't know anything.
179
180 KnownBits Known2;
181
182 switch (Opcode) {
183 default:
184 TL.computeKnownBitsForTargetInstr(*this, R, Known, DemandedElts, MRI,
185 Depth);
186 break;
187 case TargetOpcode::G_BUILD_VECTOR: {
188 // Collect the known bits that are shared by every demanded vector element.
189 Known.Zero.setAllBits(); Known.One.setAllBits();
190 for (unsigned i = 0, e = MI.getNumOperands() - 1; i < e; ++i) {
191 if (!DemandedElts[i])
192 continue;
193
194 computeKnownBitsImpl(MI.getOperand(i + 1).getReg(), Known2, DemandedElts,
195 Depth + 1);
196
197 // Known bits are the values that are shared by every demanded element.
198 Known = Known.intersectWith(Known2);
199
200 // If we don't know any bits, early out.
201 if (Known.isUnknown())
202 break;
203 }
204 break;
205 }
206 case TargetOpcode::COPY:
207 case TargetOpcode::G_PHI:
208 case TargetOpcode::PHI: {
211 // Destination registers should not have subregisters at this
212 // point of the pipeline, otherwise the main live-range will be
213 // defined more than once, which is against SSA.
214 assert(MI.getOperand(0).getSubReg() == 0 && "Is this code in SSA?");
215 // Record in the cache that we know nothing for MI.
216 // This will get updated later and in the meantime, if we reach that
217 // phi again, because of a loop, we will cut the search thanks to this
218 // cache entry.
219 // We could actually build up more information on the phi by not cutting
220 // the search, but that additional information is more a side effect
221 // than an intended choice.
222 // Therefore, for now, save on compile time until we derive a proper way
223 // to derive known bits for PHIs within loops.
224 ComputeKnownBitsCache[R] = KnownBits(BitWidth);
225 // PHI's operand are a mix of registers and basic blocks interleaved.
226 // We only care about the register ones.
227 for (unsigned Idx = 1; Idx < MI.getNumOperands(); Idx += 2) {
228 const MachineOperand &Src = MI.getOperand(Idx);
229 Register SrcReg = Src.getReg();
230 // Look through trivial copies and phis but don't look through trivial
231 // copies or phis of the form `%1:(s32) = OP %0:gpr32`, known-bits
232 // analysis is currently unable to determine the bit width of a
233 // register class.
234 //
235 // We can't use NoSubRegister by name as it's defined by each target but
236 // it's always defined to be 0 by tablegen.
237 if (SrcReg.isVirtual() && Src.getSubReg() == 0 /*NoSubRegister*/ &&
238 MRI.getType(SrcReg).isValid()) {
239 // For COPYs we don't do anything, don't increase the depth.
240 computeKnownBitsImpl(SrcReg, Known2, DemandedElts,
241 Depth + (Opcode != TargetOpcode::COPY));
242 Known = Known.intersectWith(Known2);
243 // If we reach a point where we don't know anything
244 // just stop looking through the operands.
245 if (Known.isUnknown())
246 break;
247 } else {
248 // We know nothing.
249 Known = KnownBits(BitWidth);
250 break;
251 }
252 }
253 break;
254 }
255 case TargetOpcode::G_CONSTANT: {
256 auto CstVal = getIConstantVRegVal(R, MRI);
257 if (!CstVal)
258 break;
259 Known = KnownBits::makeConstant(*CstVal);
260 break;
261 }
262 case TargetOpcode::G_FRAME_INDEX: {
263 int FrameIdx = MI.getOperand(1).getIndex();
264 TL.computeKnownBitsForFrameIndex(FrameIdx, Known, MF);
265 break;
266 }
267 case TargetOpcode::G_SUB: {
268 computeKnownBitsImpl(MI.getOperand(1).getReg(), Known, DemandedElts,
269 Depth + 1);
270 computeKnownBitsImpl(MI.getOperand(2).getReg(), Known2, DemandedElts,
271 Depth + 1);
272 Known = KnownBits::computeForAddSub(/*Add=*/false, /*NSW=*/false,
273 /* NUW=*/false, Known, Known2);
274 break;
275 }
276 case TargetOpcode::G_XOR: {
277 computeKnownBitsImpl(MI.getOperand(2).getReg(), Known, DemandedElts,
278 Depth + 1);
279 computeKnownBitsImpl(MI.getOperand(1).getReg(), Known2, DemandedElts,
280 Depth + 1);
281
282 Known ^= Known2;
283 break;
284 }
285 case TargetOpcode::G_PTR_ADD: {
286 if (DstTy.isVector())
287 break;
288 // G_PTR_ADD is like G_ADD. FIXME: Is this true for all targets?
289 LLT Ty = MRI.getType(MI.getOperand(1).getReg());
291 break;
292 [[fallthrough]];
293 }
294 case TargetOpcode::G_ADD: {
295 computeKnownBitsImpl(MI.getOperand(1).getReg(), Known, DemandedElts,
296 Depth + 1);
297 computeKnownBitsImpl(MI.getOperand(2).getReg(), Known2, DemandedElts,
298 Depth + 1);
299 Known = KnownBits::computeForAddSub(/*Add=*/true, /*NSW=*/false,
300 /* NUW=*/false, Known, Known2);
301 break;
302 }
303 case TargetOpcode::G_AND: {
304 // If either the LHS or the RHS are Zero, the result is zero.
305 computeKnownBitsImpl(MI.getOperand(2).getReg(), Known, DemandedElts,
306 Depth + 1);
307 computeKnownBitsImpl(MI.getOperand(1).getReg(), Known2, DemandedElts,
308 Depth + 1);
309
310 Known &= Known2;
311 break;
312 }
313 case TargetOpcode::G_OR: {
314 // If either the LHS or the RHS are Zero, the result is zero.
315 computeKnownBitsImpl(MI.getOperand(2).getReg(), Known, DemandedElts,
316 Depth + 1);
317 computeKnownBitsImpl(MI.getOperand(1).getReg(), Known2, DemandedElts,
318 Depth + 1);
319
320 Known |= Known2;
321 break;
322 }
323 case TargetOpcode::G_MUL: {
324 computeKnownBitsImpl(MI.getOperand(2).getReg(), Known, DemandedElts,
325 Depth + 1);
326 computeKnownBitsImpl(MI.getOperand(1).getReg(), Known2, DemandedElts,
327 Depth + 1);
328 Known = KnownBits::mul(Known, Known2);
329 break;
330 }
331 case TargetOpcode::G_SELECT: {
332 computeKnownBitsMin(MI.getOperand(2).getReg(), MI.getOperand(3).getReg(),
333 Known, DemandedElts, Depth + 1);
334 break;
335 }
336 case TargetOpcode::G_SMIN: {
337 // TODO: Handle clamp pattern with number of sign bits
338 KnownBits KnownRHS;
339 computeKnownBitsImpl(MI.getOperand(1).getReg(), Known, DemandedElts,
340 Depth + 1);
341 computeKnownBitsImpl(MI.getOperand(2).getReg(), KnownRHS, DemandedElts,
342 Depth + 1);
343 Known = KnownBits::smin(Known, KnownRHS);
344 break;
345 }
346 case TargetOpcode::G_SMAX: {
347 // TODO: Handle clamp pattern with number of sign bits
348 KnownBits KnownRHS;
349 computeKnownBitsImpl(MI.getOperand(1).getReg(), Known, DemandedElts,
350 Depth + 1);
351 computeKnownBitsImpl(MI.getOperand(2).getReg(), KnownRHS, DemandedElts,
352 Depth + 1);
353 Known = KnownBits::smax(Known, KnownRHS);
354 break;
355 }
356 case TargetOpcode::G_UMIN: {
357 KnownBits KnownRHS;
358 computeKnownBitsImpl(MI.getOperand(1).getReg(), Known,
359 DemandedElts, Depth + 1);
360 computeKnownBitsImpl(MI.getOperand(2).getReg(), KnownRHS,
361 DemandedElts, Depth + 1);
362 Known = KnownBits::umin(Known, KnownRHS);
363 break;
364 }
365 case TargetOpcode::G_UMAX: {
366 KnownBits KnownRHS;
367 computeKnownBitsImpl(MI.getOperand(1).getReg(), Known,
368 DemandedElts, Depth + 1);
369 computeKnownBitsImpl(MI.getOperand(2).getReg(), KnownRHS,
370 DemandedElts, Depth + 1);
371 Known = KnownBits::umax(Known, KnownRHS);
372 break;
373 }
374 case TargetOpcode::G_FCMP:
375 case TargetOpcode::G_ICMP: {
376 if (DstTy.isVector())
377 break;
378 if (TL.getBooleanContents(DstTy.isVector(),
379 Opcode == TargetOpcode::G_FCMP) ==
381 BitWidth > 1)
382 Known.Zero.setBitsFrom(1);
383 break;
384 }
385 case TargetOpcode::G_SEXT: {
386 computeKnownBitsImpl(MI.getOperand(1).getReg(), Known, DemandedElts,
387 Depth + 1);
388 // If the sign bit is known to be zero or one, then sext will extend
389 // it to the top bits, else it will just zext.
390 Known = Known.sext(BitWidth);
391 break;
392 }
393 case TargetOpcode::G_ASSERT_SEXT:
394 case TargetOpcode::G_SEXT_INREG: {
395 computeKnownBitsImpl(MI.getOperand(1).getReg(), Known, DemandedElts,
396 Depth + 1);
397 Known = Known.sextInReg(MI.getOperand(2).getImm());
398 break;
399 }
400 case TargetOpcode::G_ANYEXT: {
401 computeKnownBitsImpl(MI.getOperand(1).getReg(), Known, DemandedElts,
402 Depth + 1);
403 Known = Known.anyext(BitWidth);
404 break;
405 }
406 case TargetOpcode::G_LOAD: {
407 const MachineMemOperand *MMO = *MI.memoperands_begin();
408 KnownBits KnownRange(MMO->getMemoryType().getScalarSizeInBits());
409 if (const MDNode *Ranges = MMO->getRanges())
410 computeKnownBitsFromRangeMetadata(*Ranges, KnownRange);
411 Known = KnownRange.anyext(Known.getBitWidth());
412 break;
413 }
414 case TargetOpcode::G_SEXTLOAD:
415 case TargetOpcode::G_ZEXTLOAD: {
416 if (DstTy.isVector())
417 break;
418 const MachineMemOperand *MMO = *MI.memoperands_begin();
419 KnownBits KnownRange(MMO->getMemoryType().getScalarSizeInBits());
420 if (const MDNode *Ranges = MMO->getRanges())
421 computeKnownBitsFromRangeMetadata(*Ranges, KnownRange);
422 Known = Opcode == TargetOpcode::G_SEXTLOAD
423 ? KnownRange.sext(Known.getBitWidth())
424 : KnownRange.zext(Known.getBitWidth());
425 break;
426 }
427 case TargetOpcode::G_ASHR: {
428 KnownBits LHSKnown, RHSKnown;
429 computeKnownBitsImpl(MI.getOperand(1).getReg(), LHSKnown, DemandedElts,
430 Depth + 1);
431 computeKnownBitsImpl(MI.getOperand(2).getReg(), RHSKnown, DemandedElts,
432 Depth + 1);
433 Known = KnownBits::ashr(LHSKnown, RHSKnown);
434 break;
435 }
436 case TargetOpcode::G_LSHR: {
437 KnownBits LHSKnown, RHSKnown;
438 computeKnownBitsImpl(MI.getOperand(1).getReg(), LHSKnown, DemandedElts,
439 Depth + 1);
440 computeKnownBitsImpl(MI.getOperand(2).getReg(), RHSKnown, DemandedElts,
441 Depth + 1);
442 Known = KnownBits::lshr(LHSKnown, RHSKnown);
443 break;
444 }
445 case TargetOpcode::G_SHL: {
446 KnownBits LHSKnown, RHSKnown;
447 computeKnownBitsImpl(MI.getOperand(1).getReg(), LHSKnown, DemandedElts,
448 Depth + 1);
449 computeKnownBitsImpl(MI.getOperand(2).getReg(), RHSKnown, DemandedElts,
450 Depth + 1);
451 Known = KnownBits::shl(LHSKnown, RHSKnown);
452 break;
453 }
454 case TargetOpcode::G_INTTOPTR:
455 case TargetOpcode::G_PTRTOINT:
456 if (DstTy.isVector())
457 break;
458 // Fall through and handle them the same as zext/trunc.
459 [[fallthrough]];
460 case TargetOpcode::G_ASSERT_ZEXT:
461 case TargetOpcode::G_ZEXT:
462 case TargetOpcode::G_TRUNC: {
463 Register SrcReg = MI.getOperand(1).getReg();
464 LLT SrcTy = MRI.getType(SrcReg);
465 unsigned SrcBitWidth;
466
467 // G_ASSERT_ZEXT stores the original bitwidth in the immediate operand.
468 if (Opcode == TargetOpcode::G_ASSERT_ZEXT)
469 SrcBitWidth = MI.getOperand(2).getImm();
470 else {
471 SrcBitWidth = SrcTy.isPointer()
473 : SrcTy.getSizeInBits();
474 }
475 assert(SrcBitWidth && "SrcBitWidth can't be zero");
476 Known = Known.zextOrTrunc(SrcBitWidth);
477 computeKnownBitsImpl(SrcReg, Known, DemandedElts, Depth + 1);
478 Known = Known.zextOrTrunc(BitWidth);
479 if (BitWidth > SrcBitWidth)
480 Known.Zero.setBitsFrom(SrcBitWidth);
481 break;
482 }
483 case TargetOpcode::G_ASSERT_ALIGN: {
484 int64_t LogOfAlign = Log2_64(MI.getOperand(2).getImm());
485
486 // TODO: Should use maximum with source
487 // If a node is guaranteed to be aligned, set low zero bits accordingly as
488 // well as clearing one bits.
489 Known.Zero.setLowBits(LogOfAlign);
490 Known.One.clearLowBits(LogOfAlign);
491 break;
492 }
493 case TargetOpcode::G_MERGE_VALUES: {
494 unsigned NumOps = MI.getNumOperands();
495 unsigned OpSize = MRI.getType(MI.getOperand(1).getReg()).getSizeInBits();
496
497 for (unsigned I = 0; I != NumOps - 1; ++I) {
498 KnownBits SrcOpKnown;
499 computeKnownBitsImpl(MI.getOperand(I + 1).getReg(), SrcOpKnown,
500 DemandedElts, Depth + 1);
501 Known.insertBits(SrcOpKnown, I * OpSize);
502 }
503 break;
504 }
505 case TargetOpcode::G_UNMERGE_VALUES: {
506 if (DstTy.isVector())
507 break;
508 unsigned NumOps = MI.getNumOperands();
509 Register SrcReg = MI.getOperand(NumOps - 1).getReg();
510 if (MRI.getType(SrcReg).isVector())
511 return; // TODO: Handle vectors.
512
513 KnownBits SrcOpKnown;
514 computeKnownBitsImpl(SrcReg, SrcOpKnown, DemandedElts, Depth + 1);
515
516 // Figure out the result operand index
517 unsigned DstIdx = 0;
518 for (; DstIdx != NumOps - 1 && MI.getOperand(DstIdx).getReg() != R;
519 ++DstIdx)
520 ;
521
522 Known = SrcOpKnown.extractBits(BitWidth, BitWidth * DstIdx);
523 break;
524 }
525 case TargetOpcode::G_BSWAP: {
526 Register SrcReg = MI.getOperand(1).getReg();
527 computeKnownBitsImpl(SrcReg, Known, DemandedElts, Depth + 1);
528 Known = Known.byteSwap();
529 break;
530 }
531 case TargetOpcode::G_BITREVERSE: {
532 Register SrcReg = MI.getOperand(1).getReg();
533 computeKnownBitsImpl(SrcReg, Known, DemandedElts, Depth + 1);
534 Known = Known.reverseBits();
535 break;
536 }
537 case TargetOpcode::G_CTPOP: {
538 computeKnownBitsImpl(MI.getOperand(1).getReg(), Known2, DemandedElts,
539 Depth + 1);
540 // We can bound the space the count needs. Also, bits known to be zero can't
541 // contribute to the population.
542 unsigned BitsPossiblySet = Known2.countMaxPopulation();
543 unsigned LowBits = llvm::bit_width(BitsPossiblySet);
544 Known.Zero.setBitsFrom(LowBits);
545 // TODO: we could bound Known.One using the lower bound on the number of
546 // bits which might be set provided by popcnt KnownOne2.
547 break;
548 }
549 case TargetOpcode::G_UBFX: {
550 KnownBits SrcOpKnown, OffsetKnown, WidthKnown;
551 computeKnownBitsImpl(MI.getOperand(1).getReg(), SrcOpKnown, DemandedElts,
552 Depth + 1);
553 computeKnownBitsImpl(MI.getOperand(2).getReg(), OffsetKnown, DemandedElts,
554 Depth + 1);
555 computeKnownBitsImpl(MI.getOperand(3).getReg(), WidthKnown, DemandedElts,
556 Depth + 1);
557 Known = extractBits(BitWidth, SrcOpKnown, OffsetKnown, WidthKnown);
558 break;
559 }
560 case TargetOpcode::G_SBFX: {
561 KnownBits SrcOpKnown, OffsetKnown, WidthKnown;
562 computeKnownBitsImpl(MI.getOperand(1).getReg(), SrcOpKnown, DemandedElts,
563 Depth + 1);
564 computeKnownBitsImpl(MI.getOperand(2).getReg(), OffsetKnown, DemandedElts,
565 Depth + 1);
566 computeKnownBitsImpl(MI.getOperand(3).getReg(), WidthKnown, DemandedElts,
567 Depth + 1);
568 Known = extractBits(BitWidth, SrcOpKnown, OffsetKnown, WidthKnown);
569 // Sign extend the extracted value using shift left and arithmetic shift
570 // right.
573 /*Add=*/false, /*NSW=*/false, /* NUW=*/false, ExtKnown, WidthKnown);
574 Known = KnownBits::ashr(KnownBits::shl(Known, ShiftKnown), ShiftKnown);
575 break;
576 }
577 case TargetOpcode::G_UADDO:
578 case TargetOpcode::G_UADDE:
579 case TargetOpcode::G_SADDO:
580 case TargetOpcode::G_SADDE:
581 case TargetOpcode::G_USUBO:
582 case TargetOpcode::G_USUBE:
583 case TargetOpcode::G_SSUBO:
584 case TargetOpcode::G_SSUBE:
585 case TargetOpcode::G_UMULO:
586 case TargetOpcode::G_SMULO: {
587 if (MI.getOperand(1).getReg() == R) {
588 // If we know the result of a compare has the top bits zero, use this
589 // info.
590 if (TL.getBooleanContents(DstTy.isVector(), false) ==
592 BitWidth > 1)
593 Known.Zero.setBitsFrom(1);
594 }
595 break;
596 }
597 case TargetOpcode::G_CTLZ:
598 case TargetOpcode::G_CTLZ_ZERO_UNDEF: {
599 KnownBits SrcOpKnown;
600 computeKnownBitsImpl(MI.getOperand(1).getReg(), SrcOpKnown, DemandedElts,
601 Depth + 1);
602 // If we have a known 1, its position is our upper bound.
603 unsigned PossibleLZ = SrcOpKnown.countMaxLeadingZeros();
604 unsigned LowBits = llvm::bit_width(PossibleLZ);
605 Known.Zero.setBitsFrom(LowBits);
606 break;
607 }
608 }
609
610 assert(!Known.hasConflict() && "Bits known to be one AND zero?");
611 LLVM_DEBUG(dumpResult(MI, Known, Depth));
612
613 // Update the cache.
614 ComputeKnownBitsCache[R] = Known;
615}
616
617/// Compute number of sign bits for the intersection of \p Src0 and \p Src1
618unsigned GISelKnownBits::computeNumSignBitsMin(Register Src0, Register Src1,
619 const APInt &DemandedElts,
620 unsigned Depth) {
621 // Test src1 first, since we canonicalize simpler expressions to the RHS.
622 unsigned Src1SignBits = computeNumSignBits(Src1, DemandedElts, Depth);
623 if (Src1SignBits == 1)
624 return 1;
625 return std::min(computeNumSignBits(Src0, DemandedElts, Depth), Src1SignBits);
626}
627
629 const APInt &DemandedElts,
630 unsigned Depth) {
631 MachineInstr &MI = *MRI.getVRegDef(R);
632 unsigned Opcode = MI.getOpcode();
633
634 if (Opcode == TargetOpcode::G_CONSTANT)
635 return MI.getOperand(1).getCImm()->getValue().getNumSignBits();
636
637 if (Depth == getMaxDepth())
638 return 1;
639
640 if (!DemandedElts)
641 return 1; // No demanded elts, better to assume we don't know anything.
642
643 LLT DstTy = MRI.getType(R);
644 const unsigned TyBits = DstTy.getScalarSizeInBits();
645
646 // Handle the case where this is called on a register that does not have a
647 // type constraint. This is unlikely to occur except by looking through copies
648 // but it is possible for the initial register being queried to be in this
649 // state.
650 if (!DstTy.isValid())
651 return 1;
652
653 unsigned FirstAnswer = 1;
654 switch (Opcode) {
655 case TargetOpcode::COPY: {
656 MachineOperand &Src = MI.getOperand(1);
657 if (Src.getReg().isVirtual() && Src.getSubReg() == 0 &&
658 MRI.getType(Src.getReg()).isValid()) {
659 // Don't increment Depth for this one since we didn't do any work.
660 return computeNumSignBits(Src.getReg(), DemandedElts, Depth);
661 }
662
663 return 1;
664 }
665 case TargetOpcode::G_SEXT: {
666 Register Src = MI.getOperand(1).getReg();
667 LLT SrcTy = MRI.getType(Src);
668 unsigned Tmp = DstTy.getScalarSizeInBits() - SrcTy.getScalarSizeInBits();
669 return computeNumSignBits(Src, DemandedElts, Depth + 1) + Tmp;
670 }
671 case TargetOpcode::G_ASSERT_SEXT:
672 case TargetOpcode::G_SEXT_INREG: {
673 // Max of the input and what this extends.
674 Register Src = MI.getOperand(1).getReg();
675 unsigned SrcBits = MI.getOperand(2).getImm();
676 unsigned InRegBits = TyBits - SrcBits + 1;
677 return std::max(computeNumSignBits(Src, DemandedElts, Depth + 1), InRegBits);
678 }
679 case TargetOpcode::G_SEXTLOAD: {
680 // FIXME: We need an in-memory type representation.
681 if (DstTy.isVector())
682 return 1;
683
684 // e.g. i16->i32 = '17' bits known.
685 const MachineMemOperand *MMO = *MI.memoperands_begin();
686 return TyBits - MMO->getSizeInBits().getValue() + 1;
687 }
688 case TargetOpcode::G_ZEXTLOAD: {
689 // FIXME: We need an in-memory type representation.
690 if (DstTy.isVector())
691 return 1;
692
693 // e.g. i16->i32 = '16' bits known.
694 const MachineMemOperand *MMO = *MI.memoperands_begin();
695 return TyBits - MMO->getSizeInBits().getValue();
696 }
697 case TargetOpcode::G_TRUNC: {
698 Register Src = MI.getOperand(1).getReg();
699 LLT SrcTy = MRI.getType(Src);
700
701 // Check if the sign bits of source go down as far as the truncated value.
702 unsigned DstTyBits = DstTy.getScalarSizeInBits();
703 unsigned NumSrcBits = SrcTy.getScalarSizeInBits();
704 unsigned NumSrcSignBits = computeNumSignBits(Src, DemandedElts, Depth + 1);
705 if (NumSrcSignBits > (NumSrcBits - DstTyBits))
706 return NumSrcSignBits - (NumSrcBits - DstTyBits);
707 break;
708 }
709 case TargetOpcode::G_SELECT: {
710 return computeNumSignBitsMin(MI.getOperand(2).getReg(),
711 MI.getOperand(3).getReg(), DemandedElts,
712 Depth + 1);
713 }
714 case TargetOpcode::G_SADDO:
715 case TargetOpcode::G_SADDE:
716 case TargetOpcode::G_UADDO:
717 case TargetOpcode::G_UADDE:
718 case TargetOpcode::G_SSUBO:
719 case TargetOpcode::G_SSUBE:
720 case TargetOpcode::G_USUBO:
721 case TargetOpcode::G_USUBE:
722 case TargetOpcode::G_SMULO:
723 case TargetOpcode::G_UMULO: {
724 // If compares returns 0/-1, all bits are sign bits.
725 // We know that we have an integer-based boolean since these operations
726 // are only available for integer.
727 if (MI.getOperand(1).getReg() == R) {
728 if (TL.getBooleanContents(DstTy.isVector(), false) ==
730 return TyBits;
731 }
732
733 break;
734 }
735 case TargetOpcode::G_FCMP:
736 case TargetOpcode::G_ICMP: {
737 bool IsFP = Opcode == TargetOpcode::G_FCMP;
738 if (TyBits == 1)
739 break;
740 auto BC = TL.getBooleanContents(DstTy.isVector(), IsFP);
742 return TyBits; // All bits are sign bits.
744 return TyBits - 1; // Every always-zero bit is a sign bit.
745 break;
746 }
747 case TargetOpcode::G_INTRINSIC:
748 case TargetOpcode::G_INTRINSIC_W_SIDE_EFFECTS:
749 case TargetOpcode::G_INTRINSIC_CONVERGENT:
750 case TargetOpcode::G_INTRINSIC_CONVERGENT_W_SIDE_EFFECTS:
751 default: {
752 unsigned NumBits =
753 TL.computeNumSignBitsForTargetInstr(*this, R, DemandedElts, MRI, Depth);
754 if (NumBits > 1)
755 FirstAnswer = std::max(FirstAnswer, NumBits);
756 break;
757 }
758 }
759
760 // Finally, if we can prove that the top bits of the result are 0's or 1's,
761 // use this information.
762 KnownBits Known = getKnownBits(R, DemandedElts, Depth);
763 APInt Mask;
764 if (Known.isNonNegative()) { // sign bit is 0
765 Mask = Known.Zero;
766 } else if (Known.isNegative()) { // sign bit is 1;
767 Mask = Known.One;
768 } else {
769 // Nothing known.
770 return FirstAnswer;
771 }
772
773 // Okay, we know that the sign bit in Mask is set. Use CLO to determine
774 // the number of identical bits in the top of the input value.
775 Mask <<= Mask.getBitWidth() - TyBits;
776 return std::max(FirstAnswer, Mask.countl_one());
777}
778
780 LLT Ty = MRI.getType(R);
781 APInt DemandedElts =
782 Ty.isVector() ? APInt::getAllOnes(Ty.getNumElements()) : APInt(1, 1);
783 return computeNumSignBits(R, DemandedElts, Depth);
784}
785
787 AU.setPreservesAll();
789}
790
792 return false;
793}
794
796 if (!Info) {
797 unsigned MaxDepth =
799 Info = std::make_unique<GISelKnownBits>(MF, MaxDepth);
800 }
801 return *Info.get();
802}
unsigned const MachineRegisterInfo * MRI
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
static const Function * getParent(const Value *V)
#define LLVM_ATTRIBUTE_UNUSED
Definition: Compiler.h:203
Returns the sub type a function will return at a given Idx Should correspond to the result type of an ExtractValue instruction executed with just that one unsigned Idx
#define LLVM_DEBUG(X)
Definition: Debug.h:101
static Function * getFunction(Constant *C)
Definition: Evaluator.cpp:236
static KnownBits extractBits(unsigned BitWidth, const KnownBits &SrcOpKnown, const KnownBits &OffsetKnown, const KnownBits &WidthKnown)
#define DEBUG_TYPE
Provides analysis for querying information about KnownBits during GISel passes.
static LLVM_ATTRIBUTE_UNUSED void dumpResult(const MachineInstr &MI, const KnownBits &Known, unsigned Depth)
Provides analysis for querying information about KnownBits during GISel passes.
IRTranslator LLVM IR MI
static const unsigned MaxDepth
#define I(x, y, z)
Definition: MD5.cpp:58
static unsigned getReg(const MCDisassembler *D, unsigned RC, unsigned RegNo)
Module.h This file contains the declarations for the Module class.
#define INITIALIZE_PASS(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:38
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file contains some functions that are useful when dealing with strings.
This file describes how to lower LLVM code to machine code.
Class for arbitrary precision integers.
Definition: APInt.h:76
static APInt getAllOnes(unsigned numBits)
Return an APInt of a specified width with all bits set.
Definition: APInt.h:212
static APInt getSignMask(unsigned BitWidth)
Get the SignMask for a specific bit width.
Definition: APInt.h:207
void setBitsFrom(unsigned loBit)
Set the top bits starting from loBit.
Definition: APInt.h:1364
void clearLowBits(unsigned loBits)
Set bottom loBits bits to 0.
Definition: APInt.h:1395
uint64_t getLimitedValue(uint64_t Limit=UINT64_MAX) const
If this value is smaller than the specified limit, return it, otherwise return the limit value.
Definition: APInt.h:453
void setAllBits()
Set every bit to 1.
Definition: APInt.h:1297
static APInt getLowBitsSet(unsigned numBits, unsigned loBitsSet)
Constructs an APInt value that has the bottom loBitsSet bits set.
Definition: APInt.h:284
void setLowBits(unsigned loBits)
Set the bottom loBits bits.
Definition: APInt.h:1367
static APInt getBitsSetFrom(unsigned numBits, unsigned loBit)
Constructs an APInt value that has a contiguous range of bits set.
Definition: APInt.h:264
Represent the analysis usage information of a pass.
void setPreservesAll()
Set by analyses that do not transform their input at all.
bool isNonIntegralAddressSpace(unsigned AddrSpace) const
Definition: DataLayout.h:393
unsigned getIndexSizeInBits(unsigned AS) const
Size in bits of index used for address calculation in getelementptr.
Definition: DataLayout.h:420
To use KnownBitsInfo analysis in a pass, KnownBitsInfo &Info = getAnalysis<GISelKnownBitsInfoAnalysis...
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
GISelKnownBits & get(MachineFunction &MF)
bool runOnMachineFunction(MachineFunction &MF) override
runOnMachineFunction - This method must be overloaded to perform the desired machine code transformat...
virtual void computeKnownBitsImpl(Register R, KnownBits &Known, const APInt &DemandedElts, unsigned Depth=0)
Align computeKnownAlignment(Register R, unsigned Depth=0)
APInt getKnownOnes(Register R)
unsigned computeNumSignBits(Register R, const APInt &DemandedElts, unsigned Depth=0)
KnownBits getKnownBits(Register R)
bool maskedValueIsZero(Register Val, const APInt &Mask)
unsigned getMaxDepth() const
bool signBitIsZero(Register Op)
APInt getKnownZeroes(Register R)
constexpr unsigned getScalarSizeInBits() const
Definition: LowLevelType.h:267
constexpr bool isValid() const
Definition: LowLevelType.h:145
constexpr uint16_t getNumElements() const
Returns the number of elements in a vector LLT.
Definition: LowLevelType.h:159
constexpr bool isVector() const
Definition: LowLevelType.h:148
constexpr TypeSize getSizeInBits() const
Returns the total size of the type. Must only be called on sized types.
Definition: LowLevelType.h:193
constexpr bool isPointer() const
Definition: LowLevelType.h:149
constexpr unsigned getAddressSpace() const
Definition: LowLevelType.h:280
TypeSize getValue() const
Metadata node.
Definition: Metadata.h:1067
Align getObjectAlign(int ObjectIdx) const
Return the alignment of the specified stack object.
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
MachineFrameInfo & getFrameInfo()
getFrameInfo - Return the frame info object for the current function.
const LLVMTargetMachine & getTarget() const
getTarget - Return the target machine this machine code is compiled with
Representation of each machine instruction.
Definition: MachineInstr.h:69
A description of a memory reference used in the backend.
LLT getMemoryType() const
Return the memory type of the memory reference.
const MDNode * getRanges() const
Return the range tag for the memory reference.
LocationSize getSizeInBits() const
Return the size in bits of the memory reference.
MachineOperand class - Representation of each machine instruction operand.
MachineInstr * getVRegDef(Register Reg) const
getVRegDef - Return the machine instr that defines the specified virtual register or null if none is ...
LLT getType(Register Reg) const
Get the low-level type of Reg or LLT{} if Reg is not a generic (target independent) virtual register.
Wrapper class representing virtual and physical registers.
Definition: Register.h:19
constexpr bool isVirtual() const
Return true if the specified register number is in the virtual register namespace.
Definition: Register.h:91
BooleanContent getBooleanContents(bool isVec, bool isFloat) const
For targets without i1 registers, this gives the nature of the high-bits of boolean values held in ty...
virtual void computeKnownBitsForFrameIndex(int FIOp, KnownBits &Known, const MachineFunction &MF) const
Determine which of the bits of FrameIndex FIOp are known to be 0.
virtual unsigned computeNumSignBitsForTargetInstr(GISelKnownBits &Analysis, Register R, const APInt &DemandedElts, const MachineRegisterInfo &MRI, unsigned Depth=0) const
This method can be implemented by targets that want to expose additional information about sign bits ...
virtual Align computeKnownAlignForTargetInstr(GISelKnownBits &Analysis, Register R, const MachineRegisterInfo &MRI, unsigned Depth=0) const
Determine the known alignment for the pointer value R.
virtual void computeKnownBitsForTargetInstr(GISelKnownBits &Analysis, Register R, KnownBits &Known, const APInt &DemandedElts, const MachineRegisterInfo &MRI, unsigned Depth=0) const
Determine which of the bits specified in Mask are known to be either zero or one and return them in t...
CodeGenOptLevel getOptLevel() const
Returns the optimization level: None, Less, Default, or Aggressive.
std::optional< const char * > toString(const std::optional< DWARFFormValue > &V)
Take an optional DWARFFormValue and try to extract a string value from it.
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
std::optional< APInt > getIConstantVRegVal(Register VReg, const MachineRegisterInfo &MRI)
If VReg is defined by a G_CONSTANT, return the corresponding value.
Definition: Utils.cpp:293
int bit_width(T Value)
Returns the number of bits needed to represent Value if Value is nonzero.
Definition: bit.h:317
unsigned Log2_64(uint64_t Value)
Return the floor log base 2 of the specified value, -1 if the value is zero.
Definition: MathExtras.h:319
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
constexpr unsigned BitWidth
Definition: BitmaskEnum.h:191
void computeKnownBitsFromRangeMetadata(const MDNode &Ranges, KnownBits &Known)
Compute known bits from the range metadata.
This struct is a compact representation of a valid (non-zero power of two) alignment.
Definition: Alignment.h:39
static KnownBits makeConstant(const APInt &C)
Create known bits from a known constant.
Definition: KnownBits.h:297
KnownBits sextInReg(unsigned SrcBitWidth) const
Return known bits for a in-register sign extension of the value we're tracking.
Definition: KnownBits.cpp:155
static KnownBits smax(const KnownBits &LHS, const KnownBits &RHS)
Compute known bits for smax(LHS, RHS).
Definition: KnownBits.cpp:208
bool isNonNegative() const
Returns true if this value is known to be non-negative.
Definition: KnownBits.h:104
static KnownBits ashr(const KnownBits &LHS, const KnownBits &RHS, bool ShAmtNonZero=false, bool Exact=false)
Compute known bits for ashr(LHS, RHS).
Definition: KnownBits.cpp:422
bool isUnknown() const
Returns true if we don't know any bits.
Definition: KnownBits.h:63
KnownBits byteSwap() const
Definition: KnownBits.h:457
bool hasConflict() const
Returns true if there is conflicting information.
Definition: KnownBits.h:47
unsigned countMaxPopulation() const
Returns the maximum number of bits that could be one.
Definition: KnownBits.h:285
KnownBits reverseBits() const
Definition: KnownBits.h:461
unsigned getBitWidth() const
Get the bit width of this value.
Definition: KnownBits.h:40
static KnownBits umax(const KnownBits &LHS, const KnownBits &RHS)
Compute known bits for umax(LHS, RHS).
Definition: KnownBits.cpp:184
KnownBits zext(unsigned BitWidth) const
Return known bits for a zero extension of the value we're tracking.
Definition: KnownBits.h:168
static KnownBits lshr(const KnownBits &LHS, const KnownBits &RHS, bool ShAmtNonZero=false, bool Exact=false)
Compute known bits for lshr(LHS, RHS).
Definition: KnownBits.cpp:364
KnownBits extractBits(unsigned NumBits, unsigned BitPosition) const
Return a subset of the known bits from [bitPosition,bitPosition+numBits).
Definition: KnownBits.h:221
KnownBits intersectWith(const KnownBits &RHS) const
Returns KnownBits information that is known to be true for both this and RHS.
Definition: KnownBits.h:307
KnownBits sext(unsigned BitWidth) const
Return known bits for a sign extension of the value we're tracking.
Definition: KnownBits.h:176
KnownBits zextOrTrunc(unsigned BitWidth) const
Return known bits for a zero extension or truncation of the value we're tracking.
Definition: KnownBits.h:192
APInt getMaxValue() const
Return the maximal unsigned value possible given these KnownBits.
Definition: KnownBits.h:141
static KnownBits smin(const KnownBits &LHS, const KnownBits &RHS)
Compute known bits for smin(LHS, RHS).
Definition: KnownBits.cpp:221
APInt getMinValue() const
Return the minimal unsigned value possible given these KnownBits.
Definition: KnownBits.h:125
static KnownBits computeForAddSub(bool Add, bool NSW, bool NUW, const KnownBits &LHS, const KnownBits &RHS)
Compute known bits resulting from adding LHS and RHS.
Definition: KnownBits.cpp:57
bool isNegative() const
Returns true if this value is known to be negative.
Definition: KnownBits.h:101
unsigned countMaxLeadingZeros() const
Returns the maximum number of leading zero bits possible.
Definition: KnownBits.h:276
void insertBits(const KnownBits &SubBits, unsigned BitPosition)
Insert the bits from a smaller known bits starting at bitPosition.
Definition: KnownBits.h:215
static KnownBits mul(const KnownBits &LHS, const KnownBits &RHS, bool NoUndefSelfMultiply=false)
Compute known bits resulting from multiplying LHS and RHS.
Definition: KnownBits.cpp:765
KnownBits anyext(unsigned BitWidth) const
Return known bits for an "any" extension of the value we're tracking, where we don't know anything ab...
Definition: KnownBits.h:163
static KnownBits shl(const KnownBits &LHS, const KnownBits &RHS, bool NUW=false, bool NSW=false, bool ShAmtNonZero=false)
Compute known bits for shl(LHS, RHS).
Definition: KnownBits.cpp:279
static KnownBits umin(const KnownBits &LHS, const KnownBits &RHS)
Compute known bits for umin(LHS, RHS).
Definition: KnownBits.cpp:202