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