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/Analysis/ValueTracking.h"
15 #include "llvm/CodeGen/GlobalISel/Utils.h"
16 #include "llvm/CodeGen/MachineFrameInfo.h"
17 #include "llvm/CodeGen/MachineRegisterInfo.h"
18 #include "llvm/CodeGen/TargetLowering.h"
19 #include "llvm/CodeGen/TargetOpcodes.h"
20 
21 #define DEBUG_TYPE "gisel-known-bits"
22 
23 using namespace llvm;
24 
25 char llvm::GISelKnownBitsAnalysis::ID = 0;
26 
27 INITIALIZE_PASS(GISelKnownBitsAnalysis, DEBUG_TYPE,
28                 "Analysis for ComputingKnownBits", false, true)
29 
30 GISelKnownBits::GISelKnownBits(MachineFunction &MF, unsigned MaxDepth)
31     : MF(MF), MRI(MF.getRegInfo()), TL(*MF.getSubtarget().getTargetLowering()),
32       DL(MF.getFunction().getParent()->getDataLayout()), MaxDepth(MaxDepth) {}
33 
34 Align GISelKnownBits::computeKnownAlignment(Register R, unsigned Depth) {
35   const MachineInstr *MI = MRI.getVRegDef(R);
36   switch (MI->getOpcode()) {
37   case TargetOpcode::COPY:
38     return computeKnownAlignment(MI->getOperand(1).getReg(), Depth);
39   case TargetOpcode::G_FRAME_INDEX: {
40     int FrameIdx = MI->getOperand(1).getIndex();
41     return MF.getFrameInfo().getObjectAlign(FrameIdx);
42   }
43   case TargetOpcode::G_INTRINSIC:
44   case TargetOpcode::G_INTRINSIC_W_SIDE_EFFECTS:
45   default:
46     return TL.computeKnownAlignForTargetInstr(*this, R, MRI, Depth + 1);
47   }
48 }
49 
50 KnownBits GISelKnownBits::getKnownBits(MachineInstr &MI) {
51   assert(MI.getNumExplicitDefs() == 1 &&
52          "expected single return generic instruction");
53   return getKnownBits(MI.getOperand(0).getReg());
54 }
55 
56 KnownBits GISelKnownBits::getKnownBits(Register R) {
57   const LLT Ty = MRI.getType(R);
58   APInt DemandedElts =
59       Ty.isVector() ? APInt::getAllOnesValue(Ty.getNumElements()) : APInt(1, 1);
60   return getKnownBits(R, DemandedElts);
61 }
62 
63 KnownBits GISelKnownBits::getKnownBits(Register R, const APInt &DemandedElts,
64                                        unsigned Depth) {
65   // For now, we only maintain the cache during one request.
66   assert(ComputeKnownBitsCache.empty() && "Cache should have been cleared");
67 
68   KnownBits Known;
69   computeKnownBitsImpl(R, Known, DemandedElts);
70   ComputeKnownBitsCache.clear();
71   return Known;
72 }
73 
74 bool GISelKnownBits::signBitIsZero(Register R) {
75   LLT Ty = MRI.getType(R);
76   unsigned BitWidth = Ty.getScalarSizeInBits();
77   return maskedValueIsZero(R, APInt::getSignMask(BitWidth));
78 }
79 
80 APInt GISelKnownBits::getKnownZeroes(Register R) {
81   return getKnownBits(R).Zero;
82 }
83 
84 APInt GISelKnownBits::getKnownOnes(Register R) { return getKnownBits(R).One; }
85 
86 LLVM_ATTRIBUTE_UNUSED static void
87 dumpResult(const MachineInstr &MI, const KnownBits &Known, unsigned Depth) {
88   dbgs() << "[" << Depth << "] Compute known bits: " << MI << "[" << Depth
89          << "] Computed for: " << MI << "[" << Depth << "] Known: 0x"
90          << (Known.Zero | Known.One).toString(16, false) << "\n"
91          << "[" << Depth << "] Zero: 0x" << Known.Zero.toString(16, false)
92          << "\n"
93          << "[" << Depth << "] One:  0x" << Known.One.toString(16, false)
94          << "\n";
95 }
96 
97 /// Compute known bits for the intersection of \p Src0 and \p Src1
98 void GISelKnownBits::computeKnownBitsMin(Register Src0, Register Src1,
99                                          KnownBits &Known,
100                                          const APInt &DemandedElts,
101                                          unsigned Depth) {
102   // Test src1 first, since we canonicalize simpler expressions to the RHS.
103   computeKnownBitsImpl(Src1, Known, DemandedElts, Depth);
104 
105   // If we don't know any bits, early out.
106   if (Known.isUnknown())
107     return;
108 
109   KnownBits Known2;
110   computeKnownBitsImpl(Src0, Known2, DemandedElts, Depth);
111 
112   // Only known if known in both the LHS and RHS.
113   Known = KnownBits::commonBits(Known, Known2);
114 }
115 
116 void GISelKnownBits::computeKnownBitsImpl(Register R, KnownBits &Known,
117                                           const APInt &DemandedElts,
118                                           unsigned Depth) {
119   MachineInstr &MI = *MRI.getVRegDef(R);
120   unsigned Opcode = MI.getOpcode();
121   LLT DstTy = MRI.getType(R);
122 
123   // Handle the case where this is called on a register that does not have a
124   // type constraint (i.e. it has a register class constraint instead). This is
125   // unlikely to occur except by looking through copies but it is possible for
126   // the initial register being queried to be in this state.
127   if (!DstTy.isValid()) {
128     Known = KnownBits();
129     return;
130   }
131 
132   unsigned BitWidth = DstTy.getSizeInBits();
133   auto CacheEntry = ComputeKnownBitsCache.find(R);
134   if (CacheEntry != ComputeKnownBitsCache.end()) {
135     Known = CacheEntry->second;
136     LLVM_DEBUG(dbgs() << "Cache hit at ");
137     LLVM_DEBUG(dumpResult(MI, Known, Depth));
138     assert(Known.getBitWidth() == BitWidth && "Cache entry size doesn't match");
139     return;
140   }
141   Known = KnownBits(BitWidth); // Don't know anything
142 
143   if (DstTy.isVector())
144     return; // TODO: Handle vectors.
145 
146   // Depth may get bigger than max depth if it gets passed to a different
147   // GISelKnownBits object.
148   // This may happen when say a generic part uses a GISelKnownBits object
149   // with some max depth, but then we hit TL.computeKnownBitsForTargetInstr
150   // which creates a new GISelKnownBits object with a different and smaller
151   // depth. If we just check for equality, we would never exit if the depth
152   // that is passed down to the target specific GISelKnownBits object is
153   // already bigger than its max depth.
154   if (Depth >= getMaxDepth())
155     return;
156 
157   if (!DemandedElts)
158     return; // No demanded elts, better to assume we don't know anything.
159 
160   KnownBits Known2;
161 
162   switch (Opcode) {
163   default:
164     TL.computeKnownBitsForTargetInstr(*this, R, Known, DemandedElts, MRI,
165                                       Depth);
166     break;
167   case TargetOpcode::COPY:
168   case TargetOpcode::G_PHI:
169   case TargetOpcode::PHI: {
170     Known.One = APInt::getAllOnesValue(BitWidth);
171     Known.Zero = APInt::getAllOnesValue(BitWidth);
172     // Destination registers should not have subregisters at this
173     // point of the pipeline, otherwise the main live-range will be
174     // defined more than once, which is against SSA.
175     assert(MI.getOperand(0).getSubReg() == 0 && "Is this code in SSA?");
176     // Record in the cache that we know nothing for MI.
177     // This will get updated later and in the meantime, if we reach that
178     // phi again, because of a loop, we will cut the search thanks to this
179     // cache entry.
180     // We could actually build up more information on the phi by not cutting
181     // the search, but that additional information is more a side effect
182     // than an intended choice.
183     // Therefore, for now, save on compile time until we derive a proper way
184     // to derive known bits for PHIs within loops.
185     ComputeKnownBitsCache[R] = KnownBits(BitWidth);
186     // PHI's operand are a mix of registers and basic blocks interleaved.
187     // We only care about the register ones.
188     for (unsigned Idx = 1; Idx < MI.getNumOperands(); Idx += 2) {
189       const MachineOperand &Src = MI.getOperand(Idx);
190       Register SrcReg = Src.getReg();
191       // Look through trivial copies and phis but don't look through trivial
192       // copies or phis of the form `%1:(s32) = OP %0:gpr32`, known-bits
193       // analysis is currently unable to determine the bit width of a
194       // register class.
195       //
196       // We can't use NoSubRegister by name as it's defined by each target but
197       // it's always defined to be 0 by tablegen.
198       if (SrcReg.isVirtual() && Src.getSubReg() == 0 /*NoSubRegister*/ &&
199           MRI.getType(SrcReg).isValid()) {
200         // For COPYs we don't do anything, don't increase the depth.
201         computeKnownBitsImpl(SrcReg, Known2, DemandedElts,
202                              Depth + (Opcode != TargetOpcode::COPY));
203         Known = KnownBits::commonBits(Known, Known2);
204         // If we reach a point where we don't know anything
205         // just stop looking through the operands.
206         if (Known.One == 0 && Known.Zero == 0)
207           break;
208       } else {
209         // We know nothing.
210         Known = KnownBits(BitWidth);
211         break;
212       }
213     }
214     break;
215   }
216   case TargetOpcode::G_CONSTANT: {
217     auto CstVal = getConstantVRegVal(R, MRI);
218     if (!CstVal)
219       break;
220     Known = KnownBits::makeConstant(*CstVal);
221     break;
222   }
223   case TargetOpcode::G_FRAME_INDEX: {
224     int FrameIdx = MI.getOperand(1).getIndex();
225     TL.computeKnownBitsForFrameIndex(FrameIdx, Known, MF);
226     break;
227   }
228   case TargetOpcode::G_SUB: {
229     computeKnownBitsImpl(MI.getOperand(1).getReg(), Known, DemandedElts,
230                          Depth + 1);
231     computeKnownBitsImpl(MI.getOperand(2).getReg(), Known2, DemandedElts,
232                          Depth + 1);
233     Known = KnownBits::computeForAddSub(/*Add*/ false, /*NSW*/ false, Known,
234                                         Known2);
235     break;
236   }
237   case TargetOpcode::G_XOR: {
238     computeKnownBitsImpl(MI.getOperand(2).getReg(), Known, DemandedElts,
239                          Depth + 1);
240     computeKnownBitsImpl(MI.getOperand(1).getReg(), Known2, DemandedElts,
241                          Depth + 1);
242 
243     Known ^= Known2;
244     break;
245   }
246   case TargetOpcode::G_PTR_ADD: {
247     // G_PTR_ADD is like G_ADD. FIXME: Is this true for all targets?
248     LLT Ty = MRI.getType(MI.getOperand(1).getReg());
249     if (DL.isNonIntegralAddressSpace(Ty.getAddressSpace()))
250       break;
251     LLVM_FALLTHROUGH;
252   }
253   case TargetOpcode::G_ADD: {
254     computeKnownBitsImpl(MI.getOperand(1).getReg(), Known, DemandedElts,
255                          Depth + 1);
256     computeKnownBitsImpl(MI.getOperand(2).getReg(), Known2, DemandedElts,
257                          Depth + 1);
258     Known =
259         KnownBits::computeForAddSub(/*Add*/ true, /*NSW*/ false, Known, Known2);
260     break;
261   }
262   case TargetOpcode::G_AND: {
263     // If either the LHS or the RHS are Zero, the result is zero.
264     computeKnownBitsImpl(MI.getOperand(2).getReg(), Known, DemandedElts,
265                          Depth + 1);
266     computeKnownBitsImpl(MI.getOperand(1).getReg(), Known2, DemandedElts,
267                          Depth + 1);
268 
269     Known &= Known2;
270     break;
271   }
272   case TargetOpcode::G_OR: {
273     // If either the LHS or the RHS are Zero, the result is zero.
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_MUL: {
283     computeKnownBitsImpl(MI.getOperand(2).getReg(), Known, DemandedElts,
284                          Depth + 1);
285     computeKnownBitsImpl(MI.getOperand(1).getReg(), Known2, DemandedElts,
286                          Depth + 1);
287     Known = KnownBits::computeForMul(Known, Known2);
288     break;
289   }
290   case TargetOpcode::G_SELECT: {
291     computeKnownBitsMin(MI.getOperand(2).getReg(), MI.getOperand(3).getReg(),
292                         Known, DemandedElts, Depth + 1);
293     break;
294   }
295   case TargetOpcode::G_SMIN: {
296     // TODO: Handle clamp pattern with number of sign bits
297     KnownBits KnownRHS;
298     computeKnownBitsImpl(MI.getOperand(1).getReg(), Known, DemandedElts,
299                          Depth + 1);
300     computeKnownBitsImpl(MI.getOperand(2).getReg(), KnownRHS, DemandedElts,
301                          Depth + 1);
302     Known = KnownBits::smin(Known, KnownRHS);
303     break;
304   }
305   case TargetOpcode::G_SMAX: {
306     // TODO: Handle clamp pattern with number of sign bits
307     KnownBits KnownRHS;
308     computeKnownBitsImpl(MI.getOperand(1).getReg(), Known, DemandedElts,
309                          Depth + 1);
310     computeKnownBitsImpl(MI.getOperand(2).getReg(), KnownRHS, DemandedElts,
311                          Depth + 1);
312     Known = KnownBits::smax(Known, KnownRHS);
313     break;
314   }
315   case TargetOpcode::G_UMIN: {
316     KnownBits KnownRHS;
317     computeKnownBitsImpl(MI.getOperand(1).getReg(), Known,
318                          DemandedElts, Depth + 1);
319     computeKnownBitsImpl(MI.getOperand(2).getReg(), KnownRHS,
320                          DemandedElts, Depth + 1);
321     Known = KnownBits::umin(Known, KnownRHS);
322     break;
323   }
324   case TargetOpcode::G_UMAX: {
325     KnownBits KnownRHS;
326     computeKnownBitsImpl(MI.getOperand(1).getReg(), Known,
327                          DemandedElts, Depth + 1);
328     computeKnownBitsImpl(MI.getOperand(2).getReg(), KnownRHS,
329                          DemandedElts, Depth + 1);
330     Known = KnownBits::umax(Known, KnownRHS);
331     break;
332   }
333   case TargetOpcode::G_FCMP:
334   case TargetOpcode::G_ICMP: {
335     if (TL.getBooleanContents(DstTy.isVector(),
336                               Opcode == TargetOpcode::G_FCMP) ==
337             TargetLowering::ZeroOrOneBooleanContent &&
338         BitWidth > 1)
339       Known.Zero.setBitsFrom(1);
340     break;
341   }
342   case TargetOpcode::G_SEXT: {
343     computeKnownBitsImpl(MI.getOperand(1).getReg(), Known, DemandedElts,
344                          Depth + 1);
345     // If the sign bit is known to be zero or one, then sext will extend
346     // it to the top bits, else it will just zext.
347     Known = Known.sext(BitWidth);
348     break;
349   }
350   case TargetOpcode::G_SEXT_INREG: {
351     computeKnownBitsImpl(MI.getOperand(1).getReg(), Known, DemandedElts,
352                          Depth + 1);
353     Known = Known.sextInReg(MI.getOperand(2).getImm());
354     break;
355   }
356   case TargetOpcode::G_ANYEXT: {
357     computeKnownBitsImpl(MI.getOperand(1).getReg(), Known, DemandedElts,
358                          Depth + 1);
359     Known = Known.anyext(BitWidth);
360     break;
361   }
362   case TargetOpcode::G_LOAD: {
363     const MachineMemOperand *MMO = *MI.memoperands_begin();
364     if (const MDNode *Ranges = MMO->getRanges()) {
365       computeKnownBitsFromRangeMetadata(*Ranges, Known);
366     }
367 
368     break;
369   }
370   case TargetOpcode::G_ZEXTLOAD: {
371     // Everything above the retrieved bits is zero
372     Known.Zero.setBitsFrom((*MI.memoperands_begin())->getSizeInBits());
373     break;
374   }
375   case TargetOpcode::G_ASHR: {
376     KnownBits LHSKnown, RHSKnown;
377     computeKnownBitsImpl(MI.getOperand(1).getReg(), LHSKnown, DemandedElts,
378                          Depth + 1);
379     computeKnownBitsImpl(MI.getOperand(2).getReg(), RHSKnown, DemandedElts,
380                          Depth + 1);
381     Known = KnownBits::ashr(LHSKnown, RHSKnown);
382     break;
383   }
384   case TargetOpcode::G_LSHR: {
385     KnownBits LHSKnown, RHSKnown;
386     computeKnownBitsImpl(MI.getOperand(1).getReg(), LHSKnown, DemandedElts,
387                          Depth + 1);
388     computeKnownBitsImpl(MI.getOperand(2).getReg(), RHSKnown, DemandedElts,
389                          Depth + 1);
390     Known = KnownBits::lshr(LHSKnown, RHSKnown);
391     break;
392   }
393   case TargetOpcode::G_SHL: {
394     KnownBits LHSKnown, RHSKnown;
395     computeKnownBitsImpl(MI.getOperand(1).getReg(), LHSKnown, DemandedElts,
396                          Depth + 1);
397     computeKnownBitsImpl(MI.getOperand(2).getReg(), RHSKnown, DemandedElts,
398                          Depth + 1);
399     Known = KnownBits::shl(LHSKnown, RHSKnown);
400     break;
401   }
402   case TargetOpcode::G_INTTOPTR:
403   case TargetOpcode::G_PTRTOINT:
404     // Fall through and handle them the same as zext/trunc.
405     LLVM_FALLTHROUGH;
406   case TargetOpcode::G_ZEXT:
407   case TargetOpcode::G_TRUNC: {
408     Register SrcReg = MI.getOperand(1).getReg();
409     LLT SrcTy = MRI.getType(SrcReg);
410     unsigned SrcBitWidth = SrcTy.isPointer()
411                                ? DL.getIndexSizeInBits(SrcTy.getAddressSpace())
412                                : SrcTy.getSizeInBits();
413     assert(SrcBitWidth && "SrcBitWidth can't be zero");
414     Known = Known.zextOrTrunc(SrcBitWidth);
415     computeKnownBitsImpl(SrcReg, Known, DemandedElts, Depth + 1);
416     Known = Known.zextOrTrunc(BitWidth);
417     if (BitWidth > SrcBitWidth)
418       Known.Zero.setBitsFrom(SrcBitWidth);
419     break;
420   }
421   case TargetOpcode::G_MERGE_VALUES: {
422     unsigned NumOps = MI.getNumOperands();
423     unsigned OpSize = MRI.getType(MI.getOperand(1).getReg()).getSizeInBits();
424 
425     for (unsigned I = 0; I != NumOps - 1; ++I) {
426       KnownBits SrcOpKnown;
427       computeKnownBitsImpl(MI.getOperand(I + 1).getReg(), SrcOpKnown,
428                            DemandedElts, Depth + 1);
429       Known.insertBits(SrcOpKnown, I * OpSize);
430     }
431     break;
432   }
433   case TargetOpcode::G_UNMERGE_VALUES: {
434     unsigned NumOps = MI.getNumOperands();
435     Register SrcReg = MI.getOperand(NumOps - 1).getReg();
436     if (MRI.getType(SrcReg).isVector())
437       return; // TODO: Handle vectors.
438 
439     KnownBits SrcOpKnown;
440     computeKnownBitsImpl(SrcReg, SrcOpKnown, DemandedElts, Depth + 1);
441 
442     // Figure out the result operand index
443     unsigned DstIdx = 0;
444     for (; DstIdx != NumOps - 1 && MI.getOperand(DstIdx).getReg() != R;
445          ++DstIdx)
446       ;
447 
448     Known = SrcOpKnown.extractBits(BitWidth, BitWidth * DstIdx);
449     break;
450   }
451   case TargetOpcode::G_BSWAP: {
452     Register SrcReg = MI.getOperand(1).getReg();
453     computeKnownBitsImpl(SrcReg, Known, DemandedElts, Depth + 1);
454     Known.byteSwap();
455     break;
456   }
457   case TargetOpcode::G_BITREVERSE: {
458     Register SrcReg = MI.getOperand(1).getReg();
459     computeKnownBitsImpl(SrcReg, Known, DemandedElts, Depth + 1);
460     Known.reverseBits();
461     break;
462   }
463   }
464 
465   assert(!Known.hasConflict() && "Bits known to be one AND zero?");
466   LLVM_DEBUG(dumpResult(MI, Known, Depth));
467 
468   // Update the cache.
469   ComputeKnownBitsCache[R] = Known;
470 }
471 
472 /// Compute number of sign bits for the intersection of \p Src0 and \p Src1
473 unsigned GISelKnownBits::computeNumSignBitsMin(Register Src0, Register Src1,
474                                                const APInt &DemandedElts,
475                                                unsigned Depth) {
476   // Test src1 first, since we canonicalize simpler expressions to the RHS.
477   unsigned Src1SignBits = computeNumSignBits(Src1, DemandedElts, Depth);
478   if (Src1SignBits == 1)
479     return 1;
480   return std::min(computeNumSignBits(Src0, DemandedElts, Depth), Src1SignBits);
481 }
482 
483 unsigned GISelKnownBits::computeNumSignBits(Register R,
484                                             const APInt &DemandedElts,
485                                             unsigned Depth) {
486   MachineInstr &MI = *MRI.getVRegDef(R);
487   unsigned Opcode = MI.getOpcode();
488 
489   if (Opcode == TargetOpcode::G_CONSTANT)
490     return MI.getOperand(1).getCImm()->getValue().getNumSignBits();
491 
492   if (Depth == getMaxDepth())
493     return 1;
494 
495   if (!DemandedElts)
496     return 1; // No demanded elts, better to assume we don't know anything.
497 
498   LLT DstTy = MRI.getType(R);
499   const unsigned TyBits = DstTy.getScalarSizeInBits();
500 
501   // Handle the case where this is called on a register that does not have a
502   // type constraint. This is unlikely to occur except by looking through copies
503   // but it is possible for the initial register being queried to be in this
504   // state.
505   if (!DstTy.isValid())
506     return 1;
507 
508   unsigned FirstAnswer = 1;
509   switch (Opcode) {
510   case TargetOpcode::COPY: {
511     MachineOperand &Src = MI.getOperand(1);
512     if (Src.getReg().isVirtual() && Src.getSubReg() == 0 &&
513         MRI.getType(Src.getReg()).isValid()) {
514       // Don't increment Depth for this one since we didn't do any work.
515       return computeNumSignBits(Src.getReg(), DemandedElts, Depth);
516     }
517 
518     return 1;
519   }
520   case TargetOpcode::G_SEXT: {
521     Register Src = MI.getOperand(1).getReg();
522     LLT SrcTy = MRI.getType(Src);
523     unsigned Tmp = DstTy.getScalarSizeInBits() - SrcTy.getScalarSizeInBits();
524     return computeNumSignBits(Src, DemandedElts, Depth + 1) + Tmp;
525   }
526   case TargetOpcode::G_SEXT_INREG: {
527     // Max of the input and what this extends.
528     Register Src = MI.getOperand(1).getReg();
529     unsigned SrcBits = MI.getOperand(2).getImm();
530     unsigned InRegBits = TyBits - SrcBits + 1;
531     return std::max(computeNumSignBits(Src, DemandedElts, Depth + 1), InRegBits);
532   }
533   case TargetOpcode::G_SEXTLOAD: {
534     // FIXME: We need an in-memory type representation.
535     if (DstTy.isVector())
536       return 1;
537 
538     // e.g. i16->i32 = '17' bits known.
539     const MachineMemOperand *MMO = *MI.memoperands_begin();
540     return TyBits - MMO->getSizeInBits() + 1;
541   }
542   case TargetOpcode::G_ZEXTLOAD: {
543     // FIXME: We need an in-memory type representation.
544     if (DstTy.isVector())
545       return 1;
546 
547     // e.g. i16->i32 = '16' bits known.
548     const MachineMemOperand *MMO = *MI.memoperands_begin();
549     return TyBits - MMO->getSizeInBits();
550   }
551   case TargetOpcode::G_TRUNC: {
552     Register Src = MI.getOperand(1).getReg();
553     LLT SrcTy = MRI.getType(Src);
554 
555     // Check if the sign bits of source go down as far as the truncated value.
556     unsigned DstTyBits = DstTy.getScalarSizeInBits();
557     unsigned NumSrcBits = SrcTy.getScalarSizeInBits();
558     unsigned NumSrcSignBits = computeNumSignBits(Src, DemandedElts, Depth + 1);
559     if (NumSrcSignBits > (NumSrcBits - DstTyBits))
560       return NumSrcSignBits - (NumSrcBits - DstTyBits);
561     break;
562   }
563   case TargetOpcode::G_SELECT: {
564     return computeNumSignBitsMin(MI.getOperand(2).getReg(),
565                                  MI.getOperand(3).getReg(), DemandedElts,
566                                  Depth + 1);
567   }
568   case TargetOpcode::G_INTRINSIC:
569   case TargetOpcode::G_INTRINSIC_W_SIDE_EFFECTS:
570   default: {
571     unsigned NumBits =
572       TL.computeNumSignBitsForTargetInstr(*this, R, DemandedElts, MRI, Depth);
573     if (NumBits > 1)
574       FirstAnswer = std::max(FirstAnswer, NumBits);
575     break;
576   }
577   }
578 
579   // Finally, if we can prove that the top bits of the result are 0's or 1's,
580   // use this information.
581   KnownBits Known = getKnownBits(R, DemandedElts, Depth);
582   APInt Mask;
583   if (Known.isNonNegative()) {        // sign bit is 0
584     Mask = Known.Zero;
585   } else if (Known.isNegative()) {  // sign bit is 1;
586     Mask = Known.One;
587   } else {
588     // Nothing known.
589     return FirstAnswer;
590   }
591 
592   // Okay, we know that the sign bit in Mask is set.  Use CLO to determine
593   // the number of identical bits in the top of the input value.
594   Mask <<= Mask.getBitWidth() - TyBits;
595   return std::max(FirstAnswer, Mask.countLeadingOnes());
596 }
597 
598 unsigned GISelKnownBits::computeNumSignBits(Register R, unsigned Depth) {
599   LLT Ty = MRI.getType(R);
600   APInt DemandedElts = Ty.isVector()
601                            ? APInt::getAllOnesValue(Ty.getNumElements())
602                            : APInt(1, 1);
603   return computeNumSignBits(R, DemandedElts, Depth);
604 }
605 
606 void GISelKnownBitsAnalysis::getAnalysisUsage(AnalysisUsage &AU) const {
607   AU.setPreservesAll();
608   MachineFunctionPass::getAnalysisUsage(AU);
609 }
610 
611 bool GISelKnownBitsAnalysis::runOnMachineFunction(MachineFunction &MF) {
612   return false;
613 }
614