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