1//===- DemandedBits.cpp - Determine demanded bits -------------------------===//
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// This pass implements a demanded bits analysis. A demanded bit is one that
10// contributes to a result; bits that are not demanded can be either zero or
11// one without affecting control or data flow. For example in this sequence:
12//
13// %1 = add i32 %x, %y
14// %2 = trunc i32 %1 to i16
15//
16// Only the lowest 16 bits of %1 are demanded; the rest are removed by the
17// trunc.
18//
19//===----------------------------------------------------------------------===//
20
21#include "llvm/Analysis/DemandedBits.h"
22#include "llvm/ADT/APInt.h"
23#include "llvm/ADT/SetVector.h"
24#include "llvm/Analysis/AssumptionCache.h"
25#include "llvm/Analysis/ValueTracking.h"
26#include "llvm/IR/DataLayout.h"
27#include "llvm/IR/Dominators.h"
28#include "llvm/IR/InstIterator.h"
29#include "llvm/IR/Instruction.h"
30#include "llvm/IR/IntrinsicInst.h"
31#include "llvm/IR/Operator.h"
32#include "llvm/IR/PassManager.h"
33#include "llvm/IR/PatternMatch.h"
34#include "llvm/IR/Type.h"
35#include "llvm/IR/Use.h"
36#include "llvm/Support/Casting.h"
37#include "llvm/Support/Debug.h"
38#include "llvm/Support/KnownBits.h"
39#include "llvm/Support/raw_ostream.h"
40#include <algorithm>
41#include <cstdint>
42
43using namespace llvm;
44using namespace llvm::PatternMatch;
45
46#define DEBUG_TYPE "demanded-bits"
47
48static bool isAlwaysLive(Instruction *I) {
49 return I->isTerminator() || I->isEHPad() || I->mayHaveSideEffects();
50}
51
52void DemandedBits::determineLiveOperandBits(
53 const Instruction *UserI, const Value *Val, unsigned OperandNo,
54 const APInt &AOut, APInt &AB, KnownBits &Known, KnownBits &Known2,
55 bool &KnownBitsComputed) {
56 unsigned BitWidth = AB.getBitWidth();
57
58 // We're called once per operand, but for some instructions, we need to
59 // compute known bits of both operands in order to determine the live bits of
60 // either (when both operands are instructions themselves). We don't,
61 // however, want to do this twice, so we cache the result in APInts that live
62 // in the caller. For the two-relevant-operands case, both operand values are
63 // provided here.
64 auto ComputeKnownBits =
65 [&](unsigned BitWidth, const Value *V1, const Value *V2) {
66 if (KnownBitsComputed)
67 return;
68 KnownBitsComputed = true;
69
70 const DataLayout &DL = UserI->getDataLayout();
71 Known = KnownBits(BitWidth);
72 computeKnownBits(V: V1, Known, DL, AC: &AC, CxtI: UserI, DT: &DT);
73
74 if (V2) {
75 Known2 = KnownBits(BitWidth);
76 computeKnownBits(V: V2, Known&: Known2, DL, AC: &AC, CxtI: UserI, DT: &DT);
77 }
78 };
79 auto GetShiftedRange = [&](uint64_t Min, uint64_t Max, bool ShiftLeft) {
80 auto ShiftF = [ShiftLeft](const APInt &Mask, unsigned ShiftAmnt) {
81 return ShiftLeft ? Mask.shl(shiftAmt: ShiftAmnt) : Mask.lshr(shiftAmt: ShiftAmnt);
82 };
83 AB = APInt::getZero(numBits: BitWidth);
84 uint64_t LoopRange = Max - Min;
85 APInt Mask = AOut;
86 APInt Shifted = AOut; // AOut | (AOut << 1) | ... | (AOut << (ShiftAmnt - 1)
87 for (unsigned ShiftAmnt = 1; ShiftAmnt <= LoopRange; ShiftAmnt <<= 1) {
88 if (LoopRange & ShiftAmnt) {
89 // Account for (LoopRange - ShiftAmnt, LoopRange]
90 Mask |= ShiftF(Shifted, LoopRange - ShiftAmnt + 1);
91 // Clears the low bit.
92 LoopRange -= ShiftAmnt;
93 }
94 // [0, ShiftAmnt) -> [0, ShiftAmnt * 2)
95 Shifted |= ShiftF(Shifted, ShiftAmnt);
96 }
97 AB = ShiftF(Mask, Min);
98 };
99
100 switch (UserI->getOpcode()) {
101 default: break;
102 case Instruction::Call:
103 case Instruction::Invoke:
104 if (const auto *II = dyn_cast<IntrinsicInst>(Val: UserI)) {
105 switch (II->getIntrinsicID()) {
106 default: break;
107 case Intrinsic::bswap:
108 // The alive bits of the input are the swapped alive bits of
109 // the output.
110 AB = AOut.byteSwap();
111 break;
112 case Intrinsic::bitreverse:
113 // The alive bits of the input are the reversed alive bits of
114 // the output.
115 AB = AOut.reverseBits();
116 break;
117 case Intrinsic::ctlz:
118 if (OperandNo == 0) {
119 // We need some output bits, so we need all bits of the
120 // input to the left of, and including, the leftmost bit
121 // known to be one.
122 ComputeKnownBits(BitWidth, Val, nullptr);
123 AB = APInt::getHighBitsSet(numBits: BitWidth,
124 hiBitsSet: std::min(a: BitWidth, b: Known.countMaxLeadingZeros()+1));
125 }
126 break;
127 case Intrinsic::cttz:
128 if (OperandNo == 0) {
129 // We need some output bits, so we need all bits of the
130 // input to the right of, and including, the rightmost bit
131 // known to be one.
132 ComputeKnownBits(BitWidth, Val, nullptr);
133 AB = APInt::getLowBitsSet(numBits: BitWidth,
134 loBitsSet: std::min(a: BitWidth, b: Known.countMaxTrailingZeros()+1));
135 }
136 break;
137 case Intrinsic::fshl:
138 case Intrinsic::fshr: {
139 const APInt *SA;
140 if (OperandNo == 2) {
141 // Shift amount is modulo the bitwidth. For powers of two we have
142 // SA % BW == SA & (BW - 1).
143 if (isPowerOf2_32(Value: BitWidth))
144 AB = BitWidth - 1;
145 } else if (match(V: II->getOperand(i_nocapture: 2), P: m_APInt(Res&: SA))) {
146 // Normalize to funnel shift left. APInt shifts of BitWidth are well-
147 // defined, so no need to special-case zero shifts here.
148 uint64_t ShiftAmt = SA->urem(RHS: BitWidth);
149 if (II->getIntrinsicID() == Intrinsic::fshr)
150 ShiftAmt = BitWidth - ShiftAmt;
151
152 if (OperandNo == 0)
153 AB = AOut.lshr(shiftAmt: ShiftAmt);
154 else if (OperandNo == 1)
155 AB = AOut.shl(shiftAmt: BitWidth - ShiftAmt);
156 }
157 break;
158 }
159 case Intrinsic::umax:
160 case Intrinsic::umin:
161 case Intrinsic::smax:
162 case Intrinsic::smin:
163 // If low bits of result are not demanded, they are also not demanded
164 // for the min/max operands.
165 AB = APInt::getBitsSetFrom(numBits: BitWidth, loBit: AOut.countr_zero());
166 break;
167 }
168 }
169 break;
170 case Instruction::Add:
171 if (AOut.isMask()) {
172 AB = AOut;
173 } else {
174 ComputeKnownBits(BitWidth, UserI->getOperand(i: 0), UserI->getOperand(i: 1));
175 AB = determineLiveOperandBitsAdd(OperandNo, AOut, LHS: Known, RHS: Known2);
176 }
177 break;
178 case Instruction::Sub:
179 if (AOut.isMask()) {
180 AB = AOut;
181 } else {
182 ComputeKnownBits(BitWidth, UserI->getOperand(i: 0), UserI->getOperand(i: 1));
183 AB = determineLiveOperandBitsSub(OperandNo, AOut, LHS: Known, RHS: Known2);
184 }
185 break;
186 case Instruction::Mul:
187 // Find the highest live output bit. We don't need any more input
188 // bits than that (adds, and thus subtracts, ripple only to the
189 // left).
190 AB = APInt::getLowBitsSet(numBits: BitWidth, loBitsSet: AOut.getActiveBits());
191 break;
192 case Instruction::Shl:
193 if (OperandNo == 0) {
194 const APInt *ShiftAmtC;
195 if (match(V: UserI->getOperand(i: 1), P: m_APInt(Res&: ShiftAmtC))) {
196 uint64_t ShiftAmt = ShiftAmtC->getLimitedValue(Limit: BitWidth - 1);
197 AB = AOut.lshr(shiftAmt: ShiftAmt);
198
199 // If the shift is nuw/nsw, then the high bits are not dead
200 // (because we've promised that they *must* be zero).
201 const auto *S = cast<ShlOperator>(Val: UserI);
202 if (S->hasNoSignedWrap())
203 AB |= APInt::getHighBitsSet(numBits: BitWidth, hiBitsSet: ShiftAmt+1);
204 else if (S->hasNoUnsignedWrap())
205 AB |= APInt::getHighBitsSet(numBits: BitWidth, hiBitsSet: ShiftAmt);
206 } else {
207 ComputeKnownBits(BitWidth, UserI->getOperand(i: 1), nullptr);
208 uint64_t Min = Known.getMinValue().getLimitedValue(Limit: BitWidth - 1);
209 uint64_t Max = Known.getMaxValue().getLimitedValue(Limit: BitWidth - 1);
210 // similar to Lshr case
211 GetShiftedRange(Min, Max, /*ShiftLeft=*/false);
212 const auto *S = cast<ShlOperator>(Val: UserI);
213 if (S->hasNoSignedWrap())
214 AB |= APInt::getHighBitsSet(numBits: BitWidth, hiBitsSet: Max + 1);
215 else if (S->hasNoUnsignedWrap())
216 AB |= APInt::getHighBitsSet(numBits: BitWidth, hiBitsSet: Max);
217 }
218 }
219 break;
220 case Instruction::LShr:
221 if (OperandNo == 0) {
222 const APInt *ShiftAmtC;
223 if (match(V: UserI->getOperand(i: 1), P: m_APInt(Res&: ShiftAmtC))) {
224 uint64_t ShiftAmt = ShiftAmtC->getLimitedValue(Limit: BitWidth - 1);
225 AB = AOut.shl(shiftAmt: ShiftAmt);
226
227 // If the shift is exact, then the low bits are not dead
228 // (they must be zero).
229 if (cast<LShrOperator>(Val: UserI)->isExact())
230 AB |= APInt::getLowBitsSet(numBits: BitWidth, loBitsSet: ShiftAmt);
231 } else {
232 ComputeKnownBits(BitWidth, UserI->getOperand(i: 1), nullptr);
233 uint64_t Min = Known.getMinValue().getLimitedValue(Limit: BitWidth - 1);
234 uint64_t Max = Known.getMaxValue().getLimitedValue(Limit: BitWidth - 1);
235 // Suppose AOut == 0b0000 0001
236 // [min, max] = [1, 3]
237 // iteration 1 shift by 1 mask is 0b0000 0011
238 // iteration 2 shift by 2 mask is 0b0000 1111
239 // iteration 3, shiftAmnt = 4 > max - min, we stop.
240 //
241 // After the iterations we need one more shift by min,
242 // to move from 0b0000 1111 to --> 0b0001 1110.
243 // The loop populates the mask relative to (0,...,max-min),
244 // but we need coverage from (min, max).
245 // This is why the shift by min is needed.
246 GetShiftedRange(Min, Max, /*ShiftLeft=*/true);
247 if (cast<LShrOperator>(Val: UserI)->isExact())
248 AB |= APInt::getLowBitsSet(numBits: BitWidth, loBitsSet: Max);
249 }
250 }
251 break;
252 case Instruction::AShr:
253 if (OperandNo == 0) {
254 const APInt *ShiftAmtC;
255 if (match(V: UserI->getOperand(i: 1), P: m_APInt(Res&: ShiftAmtC))) {
256 uint64_t ShiftAmt = ShiftAmtC->getLimitedValue(Limit: BitWidth - 1);
257 AB = AOut.shl(shiftAmt: ShiftAmt);
258 // Because the high input bit is replicated into the
259 // high-order bits of the result, if we need any of those
260 // bits, then we must keep the highest input bit.
261 if ((AOut & APInt::getHighBitsSet(numBits: BitWidth, hiBitsSet: ShiftAmt))
262 .getBoolValue())
263 AB.setSignBit();
264
265 // If the shift is exact, then the low bits are not dead
266 // (they must be zero).
267 if (cast<AShrOperator>(Val: UserI)->isExact())
268 AB |= APInt::getLowBitsSet(numBits: BitWidth, loBitsSet: ShiftAmt);
269 } else {
270 ComputeKnownBits(BitWidth, UserI->getOperand(i: 1), nullptr);
271 uint64_t Min = Known.getMinValue().getLimitedValue(Limit: BitWidth - 1);
272 uint64_t Max = Known.getMaxValue().getLimitedValue(Limit: BitWidth - 1);
273 GetShiftedRange(Min, Max, /*ShiftLeft=*/true);
274 if (Max &&
275 (AOut & APInt::getHighBitsSet(numBits: BitWidth, hiBitsSet: Max)).getBoolValue()) {
276 // Suppose AOut = 0011 1100
277 // [min, max] = [1, 3]
278 // ShiftAmount = 1 : Mask is 1000 0000
279 // ShiftAmount = 2 : Mask is 1100 0000
280 // ShiftAmount = 3 : Mask is 1110 0000
281 // The Mask with Max covers every case in [min, max],
282 // so we are done
283 AB.setSignBit();
284 }
285 // If the shift is exact, then the low bits are not dead
286 // (they must be zero).
287 if (cast<AShrOperator>(Val: UserI)->isExact())
288 AB |= APInt::getLowBitsSet(numBits: BitWidth, loBitsSet: Max);
289 }
290 }
291 break;
292 case Instruction::And:
293 AB = AOut;
294
295 // For bits that are known zero, the corresponding bits in the
296 // other operand are dead (unless they're both zero, in which
297 // case they can't both be dead, so just mark the LHS bits as
298 // dead).
299 ComputeKnownBits(BitWidth, UserI->getOperand(i: 0), UserI->getOperand(i: 1));
300 if (OperandNo == 0)
301 AB &= ~Known2.Zero;
302 else
303 AB &= ~(Known.Zero & ~Known2.Zero);
304 break;
305 case Instruction::Or:
306 AB = AOut;
307
308 // For bits that are known one, the corresponding bits in the
309 // other operand are dead (unless they're both one, in which
310 // case they can't both be dead, so just mark the LHS bits as
311 // dead).
312 ComputeKnownBits(BitWidth, UserI->getOperand(i: 0), UserI->getOperand(i: 1));
313 if (OperandNo == 0)
314 AB &= ~Known2.One;
315 else
316 AB &= ~(Known.One & ~Known2.One);
317 break;
318 case Instruction::Xor:
319 case Instruction::PHI:
320 AB = AOut;
321 break;
322 case Instruction::Trunc:
323 AB = AOut.zext(width: BitWidth);
324 break;
325 case Instruction::ZExt:
326 AB = AOut.trunc(width: BitWidth);
327 break;
328 case Instruction::SExt:
329 AB = AOut.trunc(width: BitWidth);
330 // Because the high input bit is replicated into the
331 // high-order bits of the result, if we need any of those
332 // bits, then we must keep the highest input bit.
333 if ((AOut & APInt::getHighBitsSet(numBits: AOut.getBitWidth(),
334 hiBitsSet: AOut.getBitWidth() - BitWidth))
335 .getBoolValue())
336 AB.setSignBit();
337 break;
338 case Instruction::Select:
339 if (OperandNo != 0)
340 AB = AOut;
341 break;
342 case Instruction::ExtractElement:
343 if (OperandNo == 0)
344 AB = AOut;
345 break;
346 case Instruction::InsertElement:
347 case Instruction::ShuffleVector:
348 if (OperandNo == 0 || OperandNo == 1)
349 AB = AOut;
350 break;
351 }
352}
353
354void DemandedBits::performAnalysis() {
355 if (Analyzed)
356 // Analysis already completed for this function.
357 return;
358 Analyzed = true;
359
360 Visited.clear();
361 AliveBits.clear();
362 DeadUses.clear();
363
364 SmallSetVector<Instruction*, 16> Worklist;
365
366 // Collect the set of "root" instructions that are known live.
367 for (Instruction &I : instructions(F)) {
368 if (!isAlwaysLive(I: &I))
369 continue;
370
371 LLVM_DEBUG(dbgs() << "DemandedBits: Root: " << I << "\n");
372 // For integer-valued instructions, set up an initial empty set of alive
373 // bits and add the instruction to the work list. For other instructions
374 // add their operands to the work list (for integer values operands, mark
375 // all bits as live).
376 Type *T = I.getType();
377 if (T->isIntOrIntVectorTy()) {
378 if (AliveBits.try_emplace(Key: &I, Args: T->getScalarSizeInBits(), Args: 0).second)
379 Worklist.insert(X: &I);
380
381 continue;
382 }
383
384 // Non-integer-typed instructions...
385 for (Use &OI : I.operands()) {
386 if (auto *J = dyn_cast<Instruction>(Val&: OI)) {
387 Type *T = J->getType();
388 if (T->isIntOrIntVectorTy())
389 AliveBits[J] = APInt::getAllOnes(numBits: T->getScalarSizeInBits());
390 else
391 Visited.insert(Ptr: J);
392 Worklist.insert(X: J);
393 }
394 }
395 // To save memory, we don't add I to the Visited set here. Instead, we
396 // check isAlwaysLive on every instruction when searching for dead
397 // instructions later (we need to check isAlwaysLive for the
398 // integer-typed instructions anyway).
399 }
400
401 // Propagate liveness backwards to operands.
402 while (!Worklist.empty()) {
403 Instruction *UserI = Worklist.pop_back_val();
404
405 LLVM_DEBUG(dbgs() << "DemandedBits: Visiting: " << *UserI);
406 APInt AOut;
407 bool InputIsKnownDead = false;
408 if (UserI->getType()->isIntOrIntVectorTy()) {
409 AOut = AliveBits[UserI];
410 LLVM_DEBUG(dbgs() << " Alive Out: 0x"
411 << Twine::utohexstr(AOut.getLimitedValue()));
412
413 // If all bits of the output are dead, then all bits of the input
414 // are also dead.
415 InputIsKnownDead = !AOut && !isAlwaysLive(I: UserI);
416 }
417 LLVM_DEBUG(dbgs() << "\n");
418
419 KnownBits Known, Known2;
420 bool KnownBitsComputed = false;
421 // Compute the set of alive bits for each operand. These are anded into the
422 // existing set, if any, and if that changes the set of alive bits, the
423 // operand is added to the work-list.
424 for (Use &OI : UserI->operands()) {
425 // We also want to detect dead uses of arguments, but will only store
426 // demanded bits for instructions.
427 auto *I = dyn_cast<Instruction>(Val&: OI);
428 if (!I && !isa<Argument>(Val: OI))
429 continue;
430
431 Type *T = OI->getType();
432 if (T->isIntOrIntVectorTy()) {
433 unsigned BitWidth = T->getScalarSizeInBits();
434 APInt AB = APInt::getAllOnes(numBits: BitWidth);
435 if (InputIsKnownDead) {
436 AB = APInt(BitWidth, 0);
437 } else {
438 // Bits of each operand that are used to compute alive bits of the
439 // output are alive, all others are dead.
440 determineLiveOperandBits(UserI, Val: OI, OperandNo: OI.getOperandNo(), AOut, AB,
441 Known, Known2, KnownBitsComputed);
442
443 // Keep track of uses which have no demanded bits.
444 if (AB.isZero())
445 DeadUses.insert(Ptr: &OI);
446 else
447 DeadUses.erase(Ptr: &OI);
448 }
449
450 if (I) {
451 // If we've added to the set of alive bits (or the operand has not
452 // been previously visited), then re-queue the operand to be visited
453 // again.
454 auto Res = AliveBits.try_emplace(Key: I);
455 if (Res.second || (AB |= Res.first->second) != Res.first->second) {
456 Res.first->second = std::move(AB);
457 Worklist.insert(X: I);
458 }
459 }
460 } else if (I && Visited.insert(Ptr: I).second) {
461 Worklist.insert(X: I);
462 }
463 }
464 }
465}
466
467APInt DemandedBits::getDemandedBits(Instruction *I) {
468 performAnalysis();
469
470 auto Found = AliveBits.find(Val: I);
471 if (Found != AliveBits.end())
472 return Found->second;
473
474 const DataLayout &DL = I->getDataLayout();
475 return APInt::getAllOnes(numBits: DL.getTypeSizeInBits(Ty: I->getType()->getScalarType()));
476}
477
478APInt DemandedBits::getDemandedBits(Use *U) {
479 Type *T = (*U)->getType();
480 auto *UserI = cast<Instruction>(Val: U->getUser());
481 const DataLayout &DL = UserI->getDataLayout();
482 unsigned BitWidth = DL.getTypeSizeInBits(Ty: T->getScalarType());
483
484 // We only track integer uses, everything else produces a mask with all bits
485 // set
486 if (!T->isIntOrIntVectorTy())
487 return APInt::getAllOnes(numBits: BitWidth);
488
489 if (isUseDead(U))
490 return APInt(BitWidth, 0);
491
492 performAnalysis();
493
494 APInt AOut = getDemandedBits(I: UserI);
495 APInt AB = APInt::getAllOnes(numBits: BitWidth);
496 KnownBits Known, Known2;
497 bool KnownBitsComputed = false;
498
499 determineLiveOperandBits(UserI, Val: *U, OperandNo: U->getOperandNo(), AOut, AB, Known,
500 Known2, KnownBitsComputed);
501
502 return AB;
503}
504
505bool DemandedBits::isInstructionDead(Instruction *I) {
506 performAnalysis();
507
508 return !Visited.count(Ptr: I) && !AliveBits.contains(Val: I) && !isAlwaysLive(I);
509}
510
511bool DemandedBits::isUseDead(Use *U) {
512 // We only track integer uses, everything else is assumed live.
513 if (!(*U)->getType()->isIntOrIntVectorTy())
514 return false;
515
516 // Uses by always-live instructions are never dead.
517 auto *UserI = cast<Instruction>(Val: U->getUser());
518 if (isAlwaysLive(I: UserI))
519 return false;
520
521 performAnalysis();
522 if (DeadUses.count(Ptr: U))
523 return true;
524
525 // If no output bits are demanded, no input bits are demanded and the use
526 // is dead. These uses might not be explicitly present in the DeadUses map.
527 if (UserI->getType()->isIntOrIntVectorTy()) {
528 auto Found = AliveBits.find(Val: UserI);
529 if (Found != AliveBits.end() && Found->second.isZero())
530 return true;
531 }
532
533 return false;
534}
535
536void DemandedBits::print(raw_ostream &OS) {
537 auto PrintDB = [&](const Instruction *I, const APInt &A, Value *V = nullptr) {
538 OS << "DemandedBits: 0x" << Twine::utohexstr(Val: A.getLimitedValue())
539 << " for ";
540 if (V) {
541 V->printAsOperand(O&: OS, PrintType: false);
542 OS << " in ";
543 }
544 OS << *I << '\n';
545 };
546
547 OS << "Printing analysis 'Demanded Bits Analysis' for function '" << F.getName() << "':\n";
548 performAnalysis();
549 for (auto &KV : AliveBits) {
550 Instruction *I = KV.first;
551 PrintDB(I, KV.second);
552
553 for (Use &OI : I->operands()) {
554 PrintDB(I, getDemandedBits(U: &OI), OI);
555 }
556 }
557}
558
559static APInt determineLiveOperandBitsAddCarry(unsigned OperandNo,
560 const APInt &AOut,
561 const KnownBits &LHS,
562 const KnownBits &RHS,
563 bool CarryZero, bool CarryOne) {
564 assert(!(CarryZero && CarryOne) &&
565 "Carry can't be zero and one at the same time");
566
567 // The following check should be done by the caller, as it also indicates
568 // that LHS and RHS don't need to be computed.
569 //
570 // if (AOut.isMask())
571 // return AOut;
572
573 // Boundary bits' carry out is unaffected by their carry in.
574 APInt Bound = (LHS.Zero & RHS.Zero) | (LHS.One & RHS.One);
575
576 // First, the alive carry bits are determined from the alive output bits:
577 // Let demand ripple to the right but only up to any set bit in Bound.
578 // AOut = -1----
579 // Bound = ----1-
580 // ACarry&~AOut = --111-
581 APInt RBound = Bound.reverseBits();
582 APInt RAOut = AOut.reverseBits();
583 APInt RProp = RAOut + (RAOut | ~RBound);
584 APInt RACarry = RProp ^ ~RBound;
585 APInt ACarry = RACarry.reverseBits();
586
587 // Then, the alive input bits are determined from the alive carry bits:
588 APInt NeededToMaintainCarryZero;
589 APInt NeededToMaintainCarryOne;
590 if (OperandNo == 0) {
591 NeededToMaintainCarryZero = LHS.Zero | ~RHS.Zero;
592 NeededToMaintainCarryOne = LHS.One | ~RHS.One;
593 } else {
594 NeededToMaintainCarryZero = RHS.Zero | ~LHS.Zero;
595 NeededToMaintainCarryOne = RHS.One | ~LHS.One;
596 }
597
598 // As in computeForAddCarry
599 APInt PossibleSumZero = ~LHS.Zero + ~RHS.Zero + !CarryZero;
600 APInt PossibleSumOne = LHS.One + RHS.One + CarryOne;
601
602 // The below is simplified from
603 //
604 // APInt CarryKnownZero = ~(PossibleSumZero ^ LHS.Zero ^ RHS.Zero);
605 // APInt CarryKnownOne = PossibleSumOne ^ LHS.One ^ RHS.One;
606 // APInt CarryUnknown = ~(CarryKnownZero | CarryKnownOne);
607 //
608 // APInt NeededToMaintainCarry =
609 // (CarryKnownZero & NeededToMaintainCarryZero) |
610 // (CarryKnownOne & NeededToMaintainCarryOne) |
611 // CarryUnknown;
612
613 APInt NeededToMaintainCarry = (~PossibleSumZero | NeededToMaintainCarryZero) &
614 (PossibleSumOne | NeededToMaintainCarryOne);
615
616 APInt AB = AOut | (ACarry & NeededToMaintainCarry);
617 return AB;
618}
619
620APInt DemandedBits::determineLiveOperandBitsAdd(unsigned OperandNo,
621 const APInt &AOut,
622 const KnownBits &LHS,
623 const KnownBits &RHS) {
624 return determineLiveOperandBitsAddCarry(OperandNo, AOut, LHS, RHS, CarryZero: true,
625 CarryOne: false);
626}
627
628APInt DemandedBits::determineLiveOperandBitsSub(unsigned OperandNo,
629 const APInt &AOut,
630 const KnownBits &LHS,
631 const KnownBits &RHS) {
632 KnownBits NRHS;
633 NRHS.Zero = RHS.One;
634 NRHS.One = RHS.Zero;
635 return determineLiveOperandBitsAddCarry(OperandNo, AOut, LHS, RHS: NRHS, CarryZero: false,
636 CarryOne: true);
637}
638
639AnalysisKey DemandedBitsAnalysis::Key;
640
641DemandedBits DemandedBitsAnalysis::run(Function &F,
642 FunctionAnalysisManager &AM) {
643 auto &AC = AM.getResult<AssumptionAnalysis>(IR&: F);
644 auto &DT = AM.getResult<DominatorTreeAnalysis>(IR&: F);
645 return DemandedBits(F, AC, DT);
646}
647
648PreservedAnalyses DemandedBitsPrinterPass::run(Function &F,
649 FunctionAnalysisManager &AM) {
650 AM.getResult<DemandedBitsAnalysis>(IR&: F).print(OS);
651 return PreservedAnalyses::all();
652}
653