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