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