1 //===- lib/CodeGen/GlobalISel/GISelKnownBits.cpp --------------*- C++ *-===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 /// Provides analysis for querying information about KnownBits during GISel
10 /// passes.
11 //
12 //===------------------
13 #include "llvm/CodeGen/GlobalISel/GISelKnownBits.h"
14 #include "llvm/Analysis/ValueTracking.h"
15 #include "llvm/CodeGen/GlobalISel/Utils.h"
16 #include "llvm/CodeGen/MachineFrameInfo.h"
17 #include "llvm/CodeGen/MachineRegisterInfo.h"
18 #include "llvm/CodeGen/TargetLowering.h"
19 #include "llvm/CodeGen/TargetOpcodes.h"
20 
21 #define DEBUG_TYPE "gisel-known-bits"
22 
23 using namespace llvm;
24 
25 char llvm::GISelKnownBitsAnalysis::ID = 0;
26 
27 INITIALIZE_PASS_BEGIN(GISelKnownBitsAnalysis, DEBUG_TYPE,
28                       "Analysis for ComputingKnownBits", false, true)
29 INITIALIZE_PASS_END(GISelKnownBitsAnalysis, DEBUG_TYPE,
30                     "Analysis for ComputingKnownBits", false, true)
31 
32 GISelKnownBits::GISelKnownBits(MachineFunction &MF)
33     : MF(MF), MRI(MF.getRegInfo()), TL(*MF.getSubtarget().getTargetLowering()),
34       DL(MF.getFunction().getParent()->getDataLayout()) {}
35 
36 unsigned GISelKnownBits::inferAlignmentForFrameIdx(int FrameIdx, int Offset,
37                                                    const MachineFunction &MF) {
38   const MachineFrameInfo &MFI = MF.getFrameInfo();
39   return MinAlign(Offset, MFI.getObjectAlignment(FrameIdx));
40   // TODO: How to handle cases with Base + Offset?
41 }
42 
43 unsigned GISelKnownBits::inferPtrAlignment(const MachineInstr &MI) {
44   if (MI.getOpcode() == TargetOpcode::G_FRAME_INDEX) {
45     int FrameIdx = MI.getOperand(1).getIndex();
46     return inferAlignmentForFrameIdx(FrameIdx, 0, *MI.getMF());
47   }
48   return 0;
49 }
50 
51 void GISelKnownBits::computeKnownBitsForFrameIndex(Register R, KnownBits &Known,
52                                                    const APInt &DemandedElts,
53                                                    unsigned Depth) {
54   const MachineInstr &MI = *MRI.getVRegDef(R);
55   computeKnownBitsForAlignment(Known, inferPtrAlignment(MI));
56 }
57 
58 void GISelKnownBits::computeKnownBitsForAlignment(KnownBits &Known,
59                                                   unsigned Align) {
60   if (Align)
61     // The low bits are known zero if the pointer is aligned.
62     Known.Zero.setLowBits(Log2_32(Align));
63 }
64 
65 KnownBits GISelKnownBits::getKnownBits(MachineInstr &MI) {
66   return getKnownBits(MI.getOperand(0).getReg());
67 }
68 
69 KnownBits GISelKnownBits::getKnownBits(Register R) {
70   KnownBits Known;
71   LLT Ty = MRI.getType(R);
72   APInt DemandedElts =
73       Ty.isVector() ? APInt::getAllOnesValue(Ty.getNumElements()) : APInt(1, 1);
74   computeKnownBitsImpl(R, Known, DemandedElts);
75   return Known;
76 }
77 
78 APInt GISelKnownBits::getKnownZeroes(Register R) {
79   return getKnownBits(R).Zero;
80 }
81 
82 APInt GISelKnownBits::getKnownOnes(Register R) { return getKnownBits(R).One; }
83 
84 void GISelKnownBits::computeKnownBitsImpl(Register R, KnownBits &Known,
85                                           const APInt &DemandedElts,
86                                           unsigned Depth) {
87   MachineInstr &MI = *MRI.getVRegDef(R);
88   unsigned Opcode = MI.getOpcode();
89   LLT DstTy = MRI.getType(R);
90 
91   unsigned BitWidth = DstTy.getSizeInBits();
92   Known = KnownBits(BitWidth); // Don't know anything
93 
94   if (DstTy.isVector())
95     return; // TODO: Handle vectors.
96 
97   if (Depth == getMaxDepth())
98     return;
99 
100   if (!DemandedElts)
101     return; // No demanded elts, better to assume we don't know anything.
102 
103   KnownBits Known2;
104 
105   switch (Opcode) {
106   default:
107     TL.computeKnownBitsForTargetInstr(R, Known, DemandedElts, MRI, Depth);
108     break;
109   case TargetOpcode::G_CONSTANT: {
110     auto CstVal = getConstantVRegVal(R, MRI);
111     Known.One = *CstVal;
112     Known.Zero = ~Known.One;
113     break;
114   }
115   case TargetOpcode::G_FRAME_INDEX: {
116     computeKnownBitsForFrameIndex(R, Known, DemandedElts);
117     break;
118   }
119   case TargetOpcode::G_SUB: {
120     // If low bits are known to be zero in both operands, then we know they are
121     // going to be 0 in the result. Both addition and complement operations
122     // preserve the low zero bits.
123     computeKnownBitsImpl(MI.getOperand(1).getReg(), Known2, DemandedElts,
124                          Depth + 1);
125     unsigned KnownZeroLow = Known2.countMinTrailingZeros();
126     if (KnownZeroLow == 0)
127       break;
128     computeKnownBitsImpl(MI.getOperand(2).getReg(), Known2, DemandedElts,
129                          Depth + 1);
130     KnownZeroLow = std::min(KnownZeroLow, Known2.countMinTrailingZeros());
131     Known.Zero.setLowBits(KnownZeroLow);
132     break;
133   }
134   case TargetOpcode::G_XOR: {
135     computeKnownBitsImpl(MI.getOperand(2).getReg(), Known, DemandedElts,
136                          Depth + 1);
137     computeKnownBitsImpl(MI.getOperand(1).getReg(), Known2, DemandedElts,
138                          Depth + 1);
139 
140     // Output known-0 bits are known if clear or set in both the LHS & RHS.
141     APInt KnownZeroOut = (Known.Zero & Known2.Zero) | (Known.One & Known2.One);
142     // Output known-1 are known to be set if set in only one of the LHS, RHS.
143     Known.One = (Known.Zero & Known2.One) | (Known.One & Known2.Zero);
144     Known.Zero = KnownZeroOut;
145     break;
146   }
147   // G_GEP is like G_ADD. FIXME: Is this true for all targets?
148   case TargetOpcode::G_GEP:
149   case TargetOpcode::G_ADD: {
150     // Output known-0 bits are known if clear or set in both the low clear bits
151     // common to both LHS & RHS.  For example, 8+(X<<3) is known to have the
152     // low 3 bits clear.
153     // Output known-0 bits are also known if the top bits of each input are
154     // known to be clear. For example, if one input has the top 10 bits clear
155     // and the other has the top 8 bits clear, we know the top 7 bits of the
156     // output must be clear.
157     computeKnownBitsImpl(MI.getOperand(1).getReg(), Known2, DemandedElts,
158                          Depth + 1);
159     unsigned KnownZeroHigh = Known2.countMinLeadingZeros();
160     unsigned KnownZeroLow = Known2.countMinTrailingZeros();
161     computeKnownBitsImpl(MI.getOperand(2).getReg(), Known2, DemandedElts,
162                          Depth + 1);
163     KnownZeroHigh = std::min(KnownZeroHigh, Known2.countMinLeadingZeros());
164     KnownZeroLow = std::min(KnownZeroLow, Known2.countMinTrailingZeros());
165     Known.Zero.setLowBits(KnownZeroLow);
166     if (KnownZeroHigh > 1)
167       Known.Zero.setHighBits(KnownZeroHigh - 1);
168     break;
169   }
170   case TargetOpcode::G_AND: {
171     // If either the LHS or the RHS are Zero, the result is zero.
172     computeKnownBitsImpl(MI.getOperand(2).getReg(), Known, DemandedElts,
173                          Depth + 1);
174     computeKnownBitsImpl(MI.getOperand(1).getReg(), Known2, DemandedElts,
175                          Depth + 1);
176 
177     // Output known-1 bits are only known if set in both the LHS & RHS.
178     Known.One &= Known2.One;
179     // Output known-0 are known to be clear if zero in either the LHS | RHS.
180     Known.Zero |= Known2.Zero;
181     break;
182   }
183   case TargetOpcode::G_OR: {
184     // If either the LHS or the RHS are Zero, the result is zero.
185     computeKnownBitsImpl(MI.getOperand(2).getReg(), Known, DemandedElts,
186                          Depth + 1);
187     computeKnownBitsImpl(MI.getOperand(1).getReg(), Known2, DemandedElts,
188                          Depth + 1);
189 
190     // Output known-0 bits are only known if clear in both the LHS & RHS.
191     Known.Zero &= Known2.Zero;
192     // Output known-1 are known to be set if set in either the LHS | RHS.
193     Known.One |= Known2.One;
194     break;
195   }
196   case TargetOpcode::G_MUL: {
197     computeKnownBitsImpl(MI.getOperand(2).getReg(), Known, DemandedElts,
198                          Depth + 1);
199     computeKnownBitsImpl(MI.getOperand(1).getReg(), Known2, DemandedElts,
200                          Depth + 1);
201     // If low bits are zero in either operand, output low known-0 bits.
202     // Also compute a conservative estimate for high known-0 bits.
203     // More trickiness is possible, but this is sufficient for the
204     // interesting case of alignment computation.
205     unsigned TrailZ =
206         Known.countMinTrailingZeros() + Known2.countMinTrailingZeros();
207     unsigned LeadZ =
208         std::max(Known.countMinLeadingZeros() + Known2.countMinLeadingZeros(),
209                  BitWidth) -
210         BitWidth;
211 
212     Known.resetAll();
213     Known.Zero.setLowBits(std::min(TrailZ, BitWidth));
214     Known.Zero.setHighBits(std::min(LeadZ, BitWidth));
215     break;
216   }
217   case TargetOpcode::G_SELECT: {
218     computeKnownBitsImpl(MI.getOperand(3).getReg(), Known, DemandedElts,
219                          Depth + 1);
220     // If we don't know any bits, early out.
221     if (Known.isUnknown())
222       break;
223     computeKnownBitsImpl(MI.getOperand(2).getReg(), Known2, DemandedElts,
224                          Depth + 1);
225     // Only known if known in both the LHS and RHS.
226     Known.One &= Known2.One;
227     Known.Zero &= Known2.Zero;
228     break;
229   }
230   case TargetOpcode::G_FCMP:
231   case TargetOpcode::G_ICMP: {
232     if (TL.getBooleanContents(DstTy.isVector(),
233                               Opcode == TargetOpcode::G_FCMP) ==
234             TargetLowering::ZeroOrOneBooleanContent &&
235         BitWidth > 1)
236       Known.Zero.setBitsFrom(1);
237     break;
238   }
239   case TargetOpcode::G_SEXT: {
240     computeKnownBitsImpl(MI.getOperand(1).getReg(), Known, DemandedElts,
241                          Depth + 1);
242     // If the sign bit is known to be zero or one, then sext will extend
243     // it to the top bits, else it will just zext.
244     Known = Known.sext(BitWidth);
245     break;
246   }
247   case TargetOpcode::G_ANYEXT: {
248     computeKnownBitsImpl(MI.getOperand(1).getReg(), Known, DemandedElts,
249                          Depth + 1);
250     Known = Known.zext(BitWidth, true /* ExtendedBitsAreKnownZero */);
251     break;
252   }
253   case TargetOpcode::G_LOAD: {
254     if (MI.hasOneMemOperand()) {
255       const MachineMemOperand *MMO = *MI.memoperands_begin();
256       if (const MDNode *Ranges = MMO->getRanges()) {
257         computeKnownBitsFromRangeMetadata(*Ranges, Known);
258       }
259     }
260     break;
261   }
262   case TargetOpcode::G_ZEXTLOAD: {
263     // Everything above the retrieved bits is zero
264     if (MI.hasOneMemOperand())
265       Known.Zero.setBitsFrom((*MI.memoperands_begin())->getSizeInBits());
266     break;
267   }
268   case TargetOpcode::G_ASHR:
269   case TargetOpcode::G_LSHR:
270   case TargetOpcode::G_SHL: {
271     KnownBits RHSKnown;
272     computeKnownBitsImpl(MI.getOperand(2).getReg(), RHSKnown, DemandedElts,
273                          Depth + 1);
274     if (!RHSKnown.isConstant()) {
275       LLVM_DEBUG(
276           MachineInstr *RHSMI = MRI.getVRegDef(MI.getOperand(2).getReg());
277           dbgs() << '[' << Depth << "] Shift not known constant: " << *RHSMI);
278       break;
279     }
280     uint64_t Shift = RHSKnown.getConstant().getZExtValue();
281     LLVM_DEBUG(dbgs() << '[' << Depth << "] Shift is " << Shift << '\n');
282 
283     computeKnownBitsImpl(MI.getOperand(1).getReg(), Known, DemandedElts,
284                          Depth + 1);
285 
286     switch (Opcode) {
287     case TargetOpcode::G_ASHR:
288       Known.Zero = Known.Zero.ashr(Shift);
289       Known.One = Known.One.ashr(Shift);
290       break;
291     case TargetOpcode::G_LSHR:
292       Known.Zero = Known.Zero.lshr(Shift);
293       Known.One = Known.One.lshr(Shift);
294       Known.Zero.setBitsFrom(Known.Zero.getBitWidth() - Shift);
295       break;
296     case TargetOpcode::G_SHL:
297       Known.Zero = Known.Zero.shl(Shift);
298       Known.One = Known.One.shl(Shift);
299       Known.Zero.setBits(0, Shift);
300       break;
301     }
302     break;
303   }
304   case TargetOpcode::G_INTTOPTR:
305   case TargetOpcode::G_PTRTOINT:
306     // Fall through and handle them the same as zext/trunc.
307     LLVM_FALLTHROUGH;
308   case TargetOpcode::G_ZEXT:
309   case TargetOpcode::G_TRUNC: {
310     Register SrcReg = MI.getOperand(1).getReg();
311     LLT SrcTy = MRI.getType(SrcReg);
312     unsigned SrcBitWidth = SrcTy.isPointer()
313                                ? DL.getIndexSizeInBits(SrcTy.getAddressSpace())
314                                : SrcTy.getSizeInBits();
315     assert(SrcBitWidth && "SrcBitWidth can't be zero");
316     Known = Known.zextOrTrunc(SrcBitWidth, true);
317     computeKnownBitsImpl(SrcReg, Known, DemandedElts, Depth + 1);
318     Known = Known.zextOrTrunc(BitWidth, true);
319     if (BitWidth > SrcBitWidth)
320       Known.Zero.setBitsFrom(SrcBitWidth);
321     break;
322   }
323   }
324 
325   assert(!Known.hasConflict() && "Bits known to be one AND zero?");
326   LLVM_DEBUG(dbgs() << "[" << Depth << "] Compute known bits: " << MI << "["
327                     << Depth << "] Computed for: " << MI << "[" << Depth
328                     << "] Known: 0x"
329                     << (Known.Zero | Known.One).toString(16, false) << "\n"
330                     << "[" << Depth << "] Zero: 0x"
331                     << Known.Zero.toString(16, false) << "\n"
332                     << "[" << Depth << "] One:  0x"
333                     << Known.One.toString(16, false) << "\n");
334 }
335 
336 void GISelKnownBitsAnalysis::getAnalysisUsage(AnalysisUsage &AU) const {
337   AU.setPreservesAll();
338   MachineFunctionPass::getAnalysisUsage(AU);
339 }
340 
341 bool GISelKnownBitsAnalysis::runOnMachineFunction(MachineFunction &MF) {
342   return false;
343 }
344