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     int64_t LogAlign = MI->getOperand(2).getImm();
43     return Align(1ull << LogAlign);
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 
getKnownBits(MachineInstr & MI)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 
getKnownBits(Register R)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 
getKnownBits(Register R,const APInt & DemandedElts,unsigned Depth)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 
signBitIsZero(Register R)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 
getKnownZeroes(Register R)86 APInt GISelKnownBits::getKnownZeroes(Register R) {
87   return getKnownBits(R).Zero;
88 }
89 
getKnownOnes(Register R)90 APInt GISelKnownBits::getKnownOnes(Register R) { return getKnownBits(R).One; }
91 
92 LLVM_ATTRIBUTE_UNUSED static void
dumpResult(const MachineInstr & MI,const KnownBits & Known,unsigned Depth)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
computeKnownBitsMin(Register Src0,Register Src1,KnownBits & Known,const APInt & DemandedElts,unsigned Depth)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 = KnownBits::commonBits(Known, 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.
extractBits(unsigned BitWidth,const KnownBits & SrcOpKnown,const KnownBits & OffsetKnown,const KnownBits & WidthKnown)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 
computeKnownBitsImpl(Register R,KnownBits & Known,const APInt & DemandedElts,unsigned Depth)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 = KnownBits::commonBits(Known, 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 = KnownBits::commonBits(Known, Known2);
240         // If we reach a point where we don't know anything
241         // just stop looking through the operands.
242         if (Known.One == 0 && Known.Zero == 0)
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     LLVM_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     LLVM_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 = MI.getOperand(2).getImm();
476     if (LogOfAlign == 0)
477       break;
478 
479     // TODO: Should use maximum with source
480     // If a node is guaranteed to be aligned, set low zero bits accordingly as
481     // well as clearing one bits.
482     Known.Zero.setLowBits(LogOfAlign);
483     Known.One.clearLowBits(LogOfAlign);
484     break;
485   }
486   case TargetOpcode::G_MERGE_VALUES: {
487     unsigned NumOps = MI.getNumOperands();
488     unsigned OpSize = MRI.getType(MI.getOperand(1).getReg()).getSizeInBits();
489 
490     for (unsigned I = 0; I != NumOps - 1; ++I) {
491       KnownBits SrcOpKnown;
492       computeKnownBitsImpl(MI.getOperand(I + 1).getReg(), SrcOpKnown,
493                            DemandedElts, Depth + 1);
494       Known.insertBits(SrcOpKnown, I * OpSize);
495     }
496     break;
497   }
498   case TargetOpcode::G_UNMERGE_VALUES: {
499     if (DstTy.isVector())
500       break;
501     unsigned NumOps = MI.getNumOperands();
502     Register SrcReg = MI.getOperand(NumOps - 1).getReg();
503     if (MRI.getType(SrcReg).isVector())
504       return; // TODO: Handle vectors.
505 
506     KnownBits SrcOpKnown;
507     computeKnownBitsImpl(SrcReg, SrcOpKnown, DemandedElts, Depth + 1);
508 
509     // Figure out the result operand index
510     unsigned DstIdx = 0;
511     for (; DstIdx != NumOps - 1 && MI.getOperand(DstIdx).getReg() != R;
512          ++DstIdx)
513       ;
514 
515     Known = SrcOpKnown.extractBits(BitWidth, BitWidth * DstIdx);
516     break;
517   }
518   case TargetOpcode::G_BSWAP: {
519     Register SrcReg = MI.getOperand(1).getReg();
520     computeKnownBitsImpl(SrcReg, Known, DemandedElts, Depth + 1);
521     Known = Known.byteSwap();
522     break;
523   }
524   case TargetOpcode::G_BITREVERSE: {
525     Register SrcReg = MI.getOperand(1).getReg();
526     computeKnownBitsImpl(SrcReg, Known, DemandedElts, Depth + 1);
527     Known = Known.reverseBits();
528     break;
529   }
530   case TargetOpcode::G_CTPOP: {
531     computeKnownBitsImpl(MI.getOperand(1).getReg(), Known2, DemandedElts,
532                          Depth + 1);
533     // We can bound the space the count needs.  Also, bits known to be zero can't
534     // contribute to the population.
535     unsigned BitsPossiblySet = Known2.countMaxPopulation();
536     unsigned LowBits = Log2_32(BitsPossiblySet)+1;
537     Known.Zero.setBitsFrom(LowBits);
538     // TODO: we could bound Known.One using the lower bound on the number of
539     // bits which might be set provided by popcnt KnownOne2.
540     break;
541   }
542   case TargetOpcode::G_UBFX: {
543     KnownBits SrcOpKnown, OffsetKnown, WidthKnown;
544     computeKnownBitsImpl(MI.getOperand(1).getReg(), SrcOpKnown, DemandedElts,
545                          Depth + 1);
546     computeKnownBitsImpl(MI.getOperand(2).getReg(), OffsetKnown, DemandedElts,
547                          Depth + 1);
548     computeKnownBitsImpl(MI.getOperand(3).getReg(), WidthKnown, DemandedElts,
549                          Depth + 1);
550     Known = extractBits(BitWidth, SrcOpKnown, OffsetKnown, WidthKnown);
551     break;
552   }
553   case TargetOpcode::G_SBFX: {
554     KnownBits SrcOpKnown, OffsetKnown, WidthKnown;
555     computeKnownBitsImpl(MI.getOperand(1).getReg(), SrcOpKnown, DemandedElts,
556                          Depth + 1);
557     computeKnownBitsImpl(MI.getOperand(2).getReg(), OffsetKnown, DemandedElts,
558                          Depth + 1);
559     computeKnownBitsImpl(MI.getOperand(3).getReg(), WidthKnown, DemandedElts,
560                          Depth + 1);
561     Known = extractBits(BitWidth, SrcOpKnown, OffsetKnown, WidthKnown);
562     // Sign extend the extracted value using shift left and arithmetic shift
563     // right.
564     KnownBits ExtKnown = KnownBits::makeConstant(APInt(BitWidth, BitWidth));
565     KnownBits ShiftKnown = KnownBits::computeForAddSub(
566         /*Add*/ false, /*NSW*/ false, ExtKnown, WidthKnown);
567     Known = KnownBits::ashr(KnownBits::shl(Known, ShiftKnown), ShiftKnown);
568     break;
569   }
570   case TargetOpcode::G_UADDO:
571   case TargetOpcode::G_UADDE:
572   case TargetOpcode::G_SADDO:
573   case TargetOpcode::G_SADDE:
574   case TargetOpcode::G_USUBO:
575   case TargetOpcode::G_USUBE:
576   case TargetOpcode::G_SSUBO:
577   case TargetOpcode::G_SSUBE:
578   case TargetOpcode::G_UMULO:
579   case TargetOpcode::G_SMULO: {
580     if (MI.getOperand(1).getReg() == R) {
581       // If we know the result of a compare has the top bits zero, use this
582       // info.
583       if (TL.getBooleanContents(DstTy.isVector(), false) ==
584               TargetLowering::ZeroOrOneBooleanContent &&
585           BitWidth > 1)
586         Known.Zero.setBitsFrom(1);
587     }
588     break;
589   }
590   }
591 
592   assert(!Known.hasConflict() && "Bits known to be one AND zero?");
593   LLVM_DEBUG(dumpResult(MI, Known, Depth));
594 
595   // Update the cache.
596   ComputeKnownBitsCache[R] = Known;
597 }
598 
599 /// Compute number of sign bits for the intersection of \p Src0 and \p Src1
computeNumSignBitsMin(Register Src0,Register Src1,const APInt & DemandedElts,unsigned Depth)600 unsigned GISelKnownBits::computeNumSignBitsMin(Register Src0, Register Src1,
601                                                const APInt &DemandedElts,
602                                                unsigned Depth) {
603   // Test src1 first, since we canonicalize simpler expressions to the RHS.
604   unsigned Src1SignBits = computeNumSignBits(Src1, DemandedElts, Depth);
605   if (Src1SignBits == 1)
606     return 1;
607   return std::min(computeNumSignBits(Src0, DemandedElts, Depth), Src1SignBits);
608 }
609 
computeNumSignBits(Register R,const APInt & DemandedElts,unsigned Depth)610 unsigned GISelKnownBits::computeNumSignBits(Register R,
611                                             const APInt &DemandedElts,
612                                             unsigned Depth) {
613   MachineInstr &MI = *MRI.getVRegDef(R);
614   unsigned Opcode = MI.getOpcode();
615 
616   if (Opcode == TargetOpcode::G_CONSTANT)
617     return MI.getOperand(1).getCImm()->getValue().getNumSignBits();
618 
619   if (Depth == getMaxDepth())
620     return 1;
621 
622   if (!DemandedElts)
623     return 1; // No demanded elts, better to assume we don't know anything.
624 
625   LLT DstTy = MRI.getType(R);
626   const unsigned TyBits = DstTy.getScalarSizeInBits();
627 
628   // Handle the case where this is called on a register that does not have a
629   // type constraint. This is unlikely to occur except by looking through copies
630   // but it is possible for the initial register being queried to be in this
631   // state.
632   if (!DstTy.isValid())
633     return 1;
634 
635   unsigned FirstAnswer = 1;
636   switch (Opcode) {
637   case TargetOpcode::COPY: {
638     MachineOperand &Src = MI.getOperand(1);
639     if (Src.getReg().isVirtual() && Src.getSubReg() == 0 &&
640         MRI.getType(Src.getReg()).isValid()) {
641       // Don't increment Depth for this one since we didn't do any work.
642       return computeNumSignBits(Src.getReg(), DemandedElts, Depth);
643     }
644 
645     return 1;
646   }
647   case TargetOpcode::G_SEXT: {
648     Register Src = MI.getOperand(1).getReg();
649     LLT SrcTy = MRI.getType(Src);
650     unsigned Tmp = DstTy.getScalarSizeInBits() - SrcTy.getScalarSizeInBits();
651     return computeNumSignBits(Src, DemandedElts, Depth + 1) + Tmp;
652   }
653   case TargetOpcode::G_ASSERT_SEXT:
654   case TargetOpcode::G_SEXT_INREG: {
655     // Max of the input and what this extends.
656     Register Src = MI.getOperand(1).getReg();
657     unsigned SrcBits = MI.getOperand(2).getImm();
658     unsigned InRegBits = TyBits - SrcBits + 1;
659     return std::max(computeNumSignBits(Src, DemandedElts, Depth + 1), InRegBits);
660   }
661   case TargetOpcode::G_SEXTLOAD: {
662     // FIXME: We need an in-memory type representation.
663     if (DstTy.isVector())
664       return 1;
665 
666     // e.g. i16->i32 = '17' bits known.
667     const MachineMemOperand *MMO = *MI.memoperands_begin();
668     return TyBits - MMO->getSizeInBits() + 1;
669   }
670   case TargetOpcode::G_ZEXTLOAD: {
671     // FIXME: We need an in-memory type representation.
672     if (DstTy.isVector())
673       return 1;
674 
675     // e.g. i16->i32 = '16' bits known.
676     const MachineMemOperand *MMO = *MI.memoperands_begin();
677     return TyBits - MMO->getSizeInBits();
678   }
679   case TargetOpcode::G_TRUNC: {
680     Register Src = MI.getOperand(1).getReg();
681     LLT SrcTy = MRI.getType(Src);
682 
683     // Check if the sign bits of source go down as far as the truncated value.
684     unsigned DstTyBits = DstTy.getScalarSizeInBits();
685     unsigned NumSrcBits = SrcTy.getScalarSizeInBits();
686     unsigned NumSrcSignBits = computeNumSignBits(Src, DemandedElts, Depth + 1);
687     if (NumSrcSignBits > (NumSrcBits - DstTyBits))
688       return NumSrcSignBits - (NumSrcBits - DstTyBits);
689     break;
690   }
691   case TargetOpcode::G_SELECT: {
692     return computeNumSignBitsMin(MI.getOperand(2).getReg(),
693                                  MI.getOperand(3).getReg(), DemandedElts,
694                                  Depth + 1);
695   }
696   case TargetOpcode::G_SADDO:
697   case TargetOpcode::G_SADDE:
698   case TargetOpcode::G_UADDO:
699   case TargetOpcode::G_UADDE:
700   case TargetOpcode::G_SSUBO:
701   case TargetOpcode::G_SSUBE:
702   case TargetOpcode::G_USUBO:
703   case TargetOpcode::G_USUBE:
704   case TargetOpcode::G_SMULO:
705   case TargetOpcode::G_UMULO: {
706     // If compares returns 0/-1, all bits are sign bits.
707     // We know that we have an integer-based boolean since these operations
708     // are only available for integer.
709     if (MI.getOperand(1).getReg() == R) {
710       if (TL.getBooleanContents(DstTy.isVector(), false) ==
711           TargetLowering::ZeroOrNegativeOneBooleanContent)
712         return TyBits;
713     }
714 
715     break;
716   }
717   case TargetOpcode::G_INTRINSIC:
718   case TargetOpcode::G_INTRINSIC_W_SIDE_EFFECTS:
719   default: {
720     unsigned NumBits =
721       TL.computeNumSignBitsForTargetInstr(*this, R, DemandedElts, MRI, Depth);
722     if (NumBits > 1)
723       FirstAnswer = std::max(FirstAnswer, NumBits);
724     break;
725   }
726   }
727 
728   // Finally, if we can prove that the top bits of the result are 0's or 1's,
729   // use this information.
730   KnownBits Known = getKnownBits(R, DemandedElts, Depth);
731   APInt Mask;
732   if (Known.isNonNegative()) {        // sign bit is 0
733     Mask = Known.Zero;
734   } else if (Known.isNegative()) {  // sign bit is 1;
735     Mask = Known.One;
736   } else {
737     // Nothing known.
738     return FirstAnswer;
739   }
740 
741   // Okay, we know that the sign bit in Mask is set.  Use CLO to determine
742   // the number of identical bits in the top of the input value.
743   Mask <<= Mask.getBitWidth() - TyBits;
744   return std::max(FirstAnswer, Mask.countLeadingOnes());
745 }
746 
computeNumSignBits(Register R,unsigned Depth)747 unsigned GISelKnownBits::computeNumSignBits(Register R, unsigned Depth) {
748   LLT Ty = MRI.getType(R);
749   APInt DemandedElts =
750       Ty.isVector() ? APInt::getAllOnes(Ty.getNumElements()) : APInt(1, 1);
751   return computeNumSignBits(R, DemandedElts, Depth);
752 }
753 
getAnalysisUsage(AnalysisUsage & AU) const754 void GISelKnownBitsAnalysis::getAnalysisUsage(AnalysisUsage &AU) const {
755   AU.setPreservesAll();
756   MachineFunctionPass::getAnalysisUsage(AU);
757 }
758 
runOnMachineFunction(MachineFunction & MF)759 bool GISelKnownBitsAnalysis::runOnMachineFunction(MachineFunction &MF) {
760   return false;
761 }
762