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_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 
getKnownBits(MachineInstr & MI)55 KnownBits GISelKnownBits::getKnownBits(MachineInstr &MI) {
56   assert(MI.getNumExplicitDefs() == 1 &&
57          "expected single return generic instruction");
58   return getKnownBits(MI.getOperand(0).getReg());
59 }
60 
getKnownBits(Register R)61 KnownBits GISelKnownBits::getKnownBits(Register R) {
62   const LLT Ty = MRI.getType(R);
63   APInt DemandedElts =
64       Ty.isVector() ? APInt::getAllOnes(Ty.getNumElements()) : APInt(1, 1);
65   return getKnownBits(R, DemandedElts);
66 }
67 
getKnownBits(Register R,const APInt & DemandedElts,unsigned Depth)68 KnownBits GISelKnownBits::getKnownBits(Register R, const APInt &DemandedElts,
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 
signBitIsZero(Register R)79 bool GISelKnownBits::signBitIsZero(Register R) {
80   LLT Ty = MRI.getType(R);
81   unsigned BitWidth = Ty.getScalarSizeInBits();
82   return maskedValueIsZero(R, APInt::getSignMask(BitWidth));
83 }
84 
getKnownZeroes(Register R)85 APInt GISelKnownBits::getKnownZeroes(Register R) {
86   return getKnownBits(R).Zero;
87 }
88 
getKnownOnes(Register R)89 APInt GISelKnownBits::getKnownOnes(Register R) { return getKnownBits(R).One; }
90 
91 LLVM_ATTRIBUTE_UNUSED static void
dumpResult(const MachineInstr & MI,const KnownBits & Known,unsigned Depth)92 dumpResult(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
computeKnownBitsMin(Register Src0,Register Src1,KnownBits & Known,const APInt & DemandedElts,unsigned Depth)103 void 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.
extractBits(unsigned BitWidth,const KnownBits & SrcOpKnown,const KnownBits & OffsetKnown,const KnownBits & WidthKnown)124 static KnownBits extractBits(unsigned BitWidth, const KnownBits &SrcOpKnown,
125                              const KnownBits &OffsetKnown,
126                              const KnownBits &WidthKnown) {
127   KnownBits Mask(BitWidth);
128   Mask.Zero = APInt::getBitsSetFrom(
129       BitWidth, WidthKnown.getMaxValue().getLimitedValue(BitWidth));
130   Mask.One = APInt::getLowBitsSet(
131       BitWidth, WidthKnown.getMinValue().getLimitedValue(BitWidth));
132   return KnownBits::lshr(SrcOpKnown, OffsetKnown) & Mask;
133 }
134 
computeKnownBitsImpl(Register R,KnownBits & Known,const APInt & DemandedElts,unsigned Depth)135 void GISelKnownBits::computeKnownBitsImpl(Register R, KnownBits &Known,
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: {
205     Known.One = APInt::getAllOnes(BitWidth);
206     Known.Zero = APInt::getAllOnes(BitWidth);
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());
286     if (DL.isNonIntegralAddressSpace(Ty.getAddressSpace()))
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) ==
376             TargetLowering::ZeroOrOneBooleanContent &&
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()
462                         ? DL.getIndexSizeInBits(SrcTy.getAddressSpace())
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.
561     KnownBits ExtKnown = KnownBits::makeConstant(APInt(BitWidth, BitWidth));
562     KnownBits ShiftKnown = KnownBits::computeForAddSub(
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) ==
581               TargetLowering::ZeroOrOneBooleanContent &&
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
computeNumSignBitsMin(Register Src0,Register Src1,const APInt & DemandedElts,unsigned Depth)597 unsigned 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 
computeNumSignBits(Register R,const APInt & DemandedElts,unsigned Depth)607 unsigned GISelKnownBits::computeNumSignBits(Register R,
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) ==
708           TargetLowering::ZeroOrNegativeOneBooleanContent)
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);
720     if (BC == TargetLoweringBase::ZeroOrNegativeOneBooleanContent)
721       return TyBits; // All bits are sign bits.
722     if (BC == TargetLowering::ZeroOrOneBooleanContent)
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.countLeadingOnes());
754 }
755 
computeNumSignBits(Register R,unsigned Depth)756 unsigned GISelKnownBits::computeNumSignBits(Register R, unsigned Depth) {
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 
getAnalysisUsage(AnalysisUsage & AU) const763 void GISelKnownBitsAnalysis::getAnalysisUsage(AnalysisUsage &AU) const {
764   AU.setPreservesAll();
765   MachineFunctionPass::getAnalysisUsage(AU);
766 }
767 
runOnMachineFunction(MachineFunction & MF)768 bool GISelKnownBitsAnalysis::runOnMachineFunction(MachineFunction &MF) {
769   return false;
770 }
771