LLVM  16.0.0git
DemandedBits.cpp
Go to the documentation of this file.
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 
22 #include "llvm/ADT/APInt.h"
23 #include "llvm/ADT/SetVector.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/Module.h"
32 #include "llvm/IR/Operator.h"
33 #include "llvm/IR/PassManager.h"
34 #include "llvm/IR/PatternMatch.h"
35 #include "llvm/IR/Type.h"
36 #include "llvm/IR/Use.h"
37 #include "llvm/InitializePasses.h"
38 #include "llvm/Pass.h"
39 #include "llvm/Support/Casting.h"
40 #include "llvm/Support/Debug.h"
41 #include "llvm/Support/KnownBits.h"
43 #include <algorithm>
44 #include <cstdint>
45 
46 using namespace llvm;
47 using namespace llvm::PatternMatch;
48 
49 #define DEBUG_TYPE "demanded-bits"
50 
52 
54  "Demanded bits analysis", false, false)
58  "Demanded bits analysis", false, false)
59 
62 }
63 
65  AU.setPreservesCFG();
68  AU.setPreservesAll();
69 }
70 
72  DB->print(OS);
73 }
74 
75 static bool isAlwaysLive(Instruction *I) {
76  return I->isTerminator() || isa<DbgInfoIntrinsic>(I) || I->isEHPad() ||
77  I->mayHaveSideEffects();
78 }
79 
80 void DemandedBits::determineLiveOperandBits(
81  const Instruction *UserI, const Value *Val, unsigned OperandNo,
82  const APInt &AOut, APInt &AB, KnownBits &Known, KnownBits &Known2,
83  bool &KnownBitsComputed) {
84  unsigned BitWidth = AB.getBitWidth();
85 
86  // We're called once per operand, but for some instructions, we need to
87  // compute known bits of both operands in order to determine the live bits of
88  // either (when both operands are instructions themselves). We don't,
89  // however, want to do this twice, so we cache the result in APInts that live
90  // in the caller. For the two-relevant-operands case, both operand values are
91  // provided here.
92  auto ComputeKnownBits =
93  [&](unsigned BitWidth, const Value *V1, const Value *V2) {
94  if (KnownBitsComputed)
95  return;
96  KnownBitsComputed = true;
97 
98  const DataLayout &DL = UserI->getModule()->getDataLayout();
99  Known = KnownBits(BitWidth);
100  computeKnownBits(V1, Known, DL, 0, &AC, UserI, &DT);
101 
102  if (V2) {
103  Known2 = KnownBits(BitWidth);
104  computeKnownBits(V2, Known2, DL, 0, &AC, UserI, &DT);
105  }
106  };
107 
108  switch (UserI->getOpcode()) {
109  default: break;
110  case Instruction::Call:
111  case Instruction::Invoke:
112  if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(UserI)) {
113  switch (II->getIntrinsicID()) {
114  default: break;
115  case Intrinsic::bswap:
116  // The alive bits of the input are the swapped alive bits of
117  // the output.
118  AB = AOut.byteSwap();
119  break;
120  case Intrinsic::bitreverse:
121  // The alive bits of the input are the reversed alive bits of
122  // the output.
123  AB = AOut.reverseBits();
124  break;
125  case Intrinsic::ctlz:
126  if (OperandNo == 0) {
127  // We need some output bits, so we need all bits of the
128  // input to the left of, and including, the leftmost bit
129  // known to be one.
130  ComputeKnownBits(BitWidth, Val, nullptr);
133  }
134  break;
135  case Intrinsic::cttz:
136  if (OperandNo == 0) {
137  // We need some output bits, so we need all bits of the
138  // input to the right of, and including, the rightmost bit
139  // known to be one.
140  ComputeKnownBits(BitWidth, Val, nullptr);
143  }
144  break;
145  case Intrinsic::fshl:
146  case Intrinsic::fshr: {
147  const APInt *SA;
148  if (OperandNo == 2) {
149  // Shift amount is modulo the bitwidth. For powers of two we have
150  // SA % BW == SA & (BW - 1).
151  if (isPowerOf2_32(BitWidth))
152  AB = BitWidth - 1;
153  } else if (match(II->getOperand(2), m_APInt(SA))) {
154  // Normalize to funnel shift left. APInt shifts of BitWidth are well-
155  // defined, so no need to special-case zero shifts here.
156  uint64_t ShiftAmt = SA->urem(BitWidth);
157  if (II->getIntrinsicID() == Intrinsic::fshr)
158  ShiftAmt = BitWidth - ShiftAmt;
159 
160  if (OperandNo == 0)
161  AB = AOut.lshr(ShiftAmt);
162  else if (OperandNo == 1)
163  AB = AOut.shl(BitWidth - ShiftAmt);
164  }
165  break;
166  }
167  case Intrinsic::umax:
168  case Intrinsic::umin:
169  case Intrinsic::smax:
170  case Intrinsic::smin:
171  // If low bits of result are not demanded, they are also not demanded
172  // for the min/max operands.
174  break;
175  }
176  }
177  break;
178  case Instruction::Add:
179  if (AOut.isMask()) {
180  AB = AOut;
181  } else {
182  ComputeKnownBits(BitWidth, UserI->getOperand(0), UserI->getOperand(1));
183  AB = determineLiveOperandBitsAdd(OperandNo, AOut, Known, Known2);
184  }
185  break;
186  case Instruction::Sub:
187  if (AOut.isMask()) {
188  AB = AOut;
189  } else {
190  ComputeKnownBits(BitWidth, UserI->getOperand(0), UserI->getOperand(1));
191  AB = determineLiveOperandBitsSub(OperandNo, AOut, Known, Known2);
192  }
193  break;
194  case Instruction::Mul:
195  // Find the highest live output bit. We don't need any more input
196  // bits than that (adds, and thus subtracts, ripple only to the
197  // left).
199  break;
200  case Instruction::Shl:
201  if (OperandNo == 0) {
202  const APInt *ShiftAmtC;
203  if (match(UserI->getOperand(1), m_APInt(ShiftAmtC))) {
204  uint64_t ShiftAmt = ShiftAmtC->getLimitedValue(BitWidth - 1);
205  AB = AOut.lshr(ShiftAmt);
206 
207  // If the shift is nuw/nsw, then the high bits are not dead
208  // (because we've promised that they *must* be zero).
209  const ShlOperator *S = cast<ShlOperator>(UserI);
210  if (S->hasNoSignedWrap())
211  AB |= APInt::getHighBitsSet(BitWidth, ShiftAmt+1);
212  else if (S->hasNoUnsignedWrap())
213  AB |= APInt::getHighBitsSet(BitWidth, ShiftAmt);
214  }
215  }
216  break;
217  case Instruction::LShr:
218  if (OperandNo == 0) {
219  const APInt *ShiftAmtC;
220  if (match(UserI->getOperand(1), m_APInt(ShiftAmtC))) {
221  uint64_t ShiftAmt = ShiftAmtC->getLimitedValue(BitWidth - 1);
222  AB = AOut.shl(ShiftAmt);
223 
224  // If the shift is exact, then the low bits are not dead
225  // (they must be zero).
226  if (cast<LShrOperator>(UserI)->isExact())
227  AB |= APInt::getLowBitsSet(BitWidth, ShiftAmt);
228  }
229  }
230  break;
231  case Instruction::AShr:
232  if (OperandNo == 0) {
233  const APInt *ShiftAmtC;
234  if (match(UserI->getOperand(1), m_APInt(ShiftAmtC))) {
235  uint64_t ShiftAmt = ShiftAmtC->getLimitedValue(BitWidth - 1);
236  AB = AOut.shl(ShiftAmt);
237  // Because the high input bit is replicated into the
238  // high-order bits of the result, if we need any of those
239  // bits, then we must keep the highest input bit.
240  if ((AOut & APInt::getHighBitsSet(BitWidth, ShiftAmt))
241  .getBoolValue())
242  AB.setSignBit();
243 
244  // If the shift is exact, then the low bits are not dead
245  // (they must be zero).
246  if (cast<AShrOperator>(UserI)->isExact())
247  AB |= APInt::getLowBitsSet(BitWidth, ShiftAmt);
248  }
249  }
250  break;
251  case Instruction::And:
252  AB = AOut;
253 
254  // For bits that are known zero, the corresponding bits in the
255  // other operand are dead (unless they're both zero, in which
256  // case they can't both be dead, so just mark the LHS bits as
257  // dead).
258  ComputeKnownBits(BitWidth, UserI->getOperand(0), UserI->getOperand(1));
259  if (OperandNo == 0)
260  AB &= ~Known2.Zero;
261  else
262  AB &= ~(Known.Zero & ~Known2.Zero);
263  break;
264  case Instruction::Or:
265  AB = AOut;
266 
267  // For bits that are known one, the corresponding bits in the
268  // other operand are dead (unless they're both one, in which
269  // case they can't both be dead, so just mark the LHS bits as
270  // dead).
271  ComputeKnownBits(BitWidth, UserI->getOperand(0), UserI->getOperand(1));
272  if (OperandNo == 0)
273  AB &= ~Known2.One;
274  else
275  AB &= ~(Known.One & ~Known2.One);
276  break;
277  case Instruction::Xor:
278  case Instruction::PHI:
279  AB = AOut;
280  break;
281  case Instruction::Trunc:
282  AB = AOut.zext(BitWidth);
283  break;
284  case Instruction::ZExt:
285  AB = AOut.trunc(BitWidth);
286  break;
287  case Instruction::SExt:
288  AB = AOut.trunc(BitWidth);
289  // Because the high input bit is replicated into the
290  // high-order bits of the result, if we need any of those
291  // bits, then we must keep the highest input bit.
292  if ((AOut & APInt::getHighBitsSet(AOut.getBitWidth(),
293  AOut.getBitWidth() - BitWidth))
294  .getBoolValue())
295  AB.setSignBit();
296  break;
297  case Instruction::Select:
298  if (OperandNo != 0)
299  AB = AOut;
300  break;
301  case Instruction::ExtractElement:
302  if (OperandNo == 0)
303  AB = AOut;
304  break;
305  case Instruction::InsertElement:
306  case Instruction::ShuffleVector:
307  if (OperandNo == 0 || OperandNo == 1)
308  AB = AOut;
309  break;
310  }
311 }
312 
314  auto &AC = getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
315  auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
316  DB.emplace(F, AC, DT);
317  return false;
318 }
319 
321  DB.reset();
322 }
323 
324 void DemandedBits::performAnalysis() {
325  if (Analyzed)
326  // Analysis already completed for this function.
327  return;
328  Analyzed = true;
329 
330  Visited.clear();
331  AliveBits.clear();
332  DeadUses.clear();
333 
335 
336  // Collect the set of "root" instructions that are known live.
337  for (Instruction &I : instructions(F)) {
338  if (!isAlwaysLive(&I))
339  continue;
340 
341  LLVM_DEBUG(dbgs() << "DemandedBits: Root: " << I << "\n");
342  // For integer-valued instructions, set up an initial empty set of alive
343  // bits and add the instruction to the work list. For other instructions
344  // add their operands to the work list (for integer values operands, mark
345  // all bits as live).
346  Type *T = I.getType();
347  if (T->isIntOrIntVectorTy()) {
348  if (AliveBits.try_emplace(&I, T->getScalarSizeInBits(), 0).second)
349  Worklist.insert(&I);
350 
351  continue;
352  }
353 
354  // Non-integer-typed instructions...
355  for (Use &OI : I.operands()) {
356  if (Instruction *J = dyn_cast<Instruction>(OI)) {
357  Type *T = J->getType();
358  if (T->isIntOrIntVectorTy())
359  AliveBits[J] = APInt::getAllOnes(T->getScalarSizeInBits());
360  else
361  Visited.insert(J);
362  Worklist.insert(J);
363  }
364  }
365  // To save memory, we don't add I to the Visited set here. Instead, we
366  // check isAlwaysLive on every instruction when searching for dead
367  // instructions later (we need to check isAlwaysLive for the
368  // integer-typed instructions anyway).
369  }
370 
371  // Propagate liveness backwards to operands.
372  while (!Worklist.empty()) {
373  Instruction *UserI = Worklist.pop_back_val();
374 
375  LLVM_DEBUG(dbgs() << "DemandedBits: Visiting: " << *UserI);
376  APInt AOut;
377  bool InputIsKnownDead = false;
378  if (UserI->getType()->isIntOrIntVectorTy()) {
379  AOut = AliveBits[UserI];
380  LLVM_DEBUG(dbgs() << " Alive Out: 0x"
381  << Twine::utohexstr(AOut.getLimitedValue()));
382 
383  // If all bits of the output are dead, then all bits of the input
384  // are also dead.
385  InputIsKnownDead = !AOut && !isAlwaysLive(UserI);
386  }
387  LLVM_DEBUG(dbgs() << "\n");
388 
389  KnownBits Known, Known2;
390  bool KnownBitsComputed = false;
391  // Compute the set of alive bits for each operand. These are anded into the
392  // existing set, if any, and if that changes the set of alive bits, the
393  // operand is added to the work-list.
394  for (Use &OI : UserI->operands()) {
395  // We also want to detect dead uses of arguments, but will only store
396  // demanded bits for instructions.
397  Instruction *I = dyn_cast<Instruction>(OI);
398  if (!I && !isa<Argument>(OI))
399  continue;
400 
401  Type *T = OI->getType();
402  if (T->isIntOrIntVectorTy()) {
403  unsigned BitWidth = T->getScalarSizeInBits();
405  if (InputIsKnownDead) {
406  AB = APInt(BitWidth, 0);
407  } else {
408  // Bits of each operand that are used to compute alive bits of the
409  // output are alive, all others are dead.
410  determineLiveOperandBits(UserI, OI, OI.getOperandNo(), AOut, AB,
411  Known, Known2, KnownBitsComputed);
412 
413  // Keep track of uses which have no demanded bits.
414  if (AB.isZero())
415  DeadUses.insert(&OI);
416  else
417  DeadUses.erase(&OI);
418  }
419 
420  if (I) {
421  // If we've added to the set of alive bits (or the operand has not
422  // been previously visited), then re-queue the operand to be visited
423  // again.
424  auto Res = AliveBits.try_emplace(I);
425  if (Res.second || (AB |= Res.first->second) != Res.first->second) {
426  Res.first->second = std::move(AB);
427  Worklist.insert(I);
428  }
429  }
430  } else if (I && Visited.insert(I).second) {
431  Worklist.insert(I);
432  }
433  }
434  }
435 }
436 
438  performAnalysis();
439 
440  auto Found = AliveBits.find(I);
441  if (Found != AliveBits.end())
442  return Found->second;
443 
444  const DataLayout &DL = I->getModule()->getDataLayout();
445  return APInt::getAllOnes(DL.getTypeSizeInBits(I->getType()->getScalarType()));
446 }
447 
449  Type *T = (*U)->getType();
450  Instruction *UserI = cast<Instruction>(U->getUser());
451  const DataLayout &DL = UserI->getModule()->getDataLayout();
452  unsigned BitWidth = DL.getTypeSizeInBits(T->getScalarType());
453 
454  // We only track integer uses, everything else produces a mask with all bits
455  // set
456  if (!T->isIntOrIntVectorTy())
457  return APInt::getAllOnes(BitWidth);
458 
459  if (isUseDead(U))
460  return APInt(BitWidth, 0);
461 
462  performAnalysis();
463 
464  APInt AOut = getDemandedBits(UserI);
466  KnownBits Known, Known2;
467  bool KnownBitsComputed = false;
468 
469  determineLiveOperandBits(UserI, *U, U->getOperandNo(), AOut, AB, Known,
470  Known2, KnownBitsComputed);
471 
472  return AB;
473 }
474 
476  performAnalysis();
477 
478  return !Visited.count(I) && AliveBits.find(I) == AliveBits.end() &&
479  !isAlwaysLive(I);
480 }
481 
483  // We only track integer uses, everything else is assumed live.
484  if (!(*U)->getType()->isIntOrIntVectorTy())
485  return false;
486 
487  // Uses by always-live instructions are never dead.
488  Instruction *UserI = cast<Instruction>(U->getUser());
489  if (isAlwaysLive(UserI))
490  return false;
491 
492  performAnalysis();
493  if (DeadUses.count(U))
494  return true;
495 
496  // If no output bits are demanded, no input bits are demanded and the use
497  // is dead. These uses might not be explicitly present in the DeadUses map.
498  if (UserI->getType()->isIntOrIntVectorTy()) {
499  auto Found = AliveBits.find(UserI);
500  if (Found != AliveBits.end() && Found->second.isZero())
501  return true;
502  }
503 
504  return false;
505 }
506 
508  auto PrintDB = [&](const Instruction *I, const APInt &A, Value *V = nullptr) {
509  OS << "DemandedBits: 0x" << Twine::utohexstr(A.getLimitedValue())
510  << " for ";
511  if (V) {
512  V->printAsOperand(OS, false);
513  OS << " in ";
514  }
515  OS << *I << '\n';
516  };
517 
518  performAnalysis();
519  for (auto &KV : AliveBits) {
520  Instruction *I = KV.first;
521  PrintDB(I, KV.second);
522 
523  for (Use &OI : I->operands()) {
524  PrintDB(I, getDemandedBits(&OI), OI);
525  }
526  }
527 }
528 
529 static APInt determineLiveOperandBitsAddCarry(unsigned OperandNo,
530  const APInt &AOut,
531  const KnownBits &LHS,
532  const KnownBits &RHS,
533  bool CarryZero, bool CarryOne) {
534  assert(!(CarryZero && CarryOne) &&
535  "Carry can't be zero and one at the same time");
536 
537  // The following check should be done by the caller, as it also indicates
538  // that LHS and RHS don't need to be computed.
539  //
540  // if (AOut.isMask())
541  // return AOut;
542 
543  // Boundary bits' carry out is unaffected by their carry in.
544  APInt Bound = (LHS.Zero & RHS.Zero) | (LHS.One & RHS.One);
545 
546  // First, the alive carry bits are determined from the alive output bits:
547  // Let demand ripple to the right but only up to any set bit in Bound.
548  // AOut = -1----
549  // Bound = ----1-
550  // ACarry&~AOut = --111-
551  APInt RBound = Bound.reverseBits();
552  APInt RAOut = AOut.reverseBits();
553  APInt RProp = RAOut + (RAOut | ~RBound);
554  APInt RACarry = RProp ^ ~RBound;
555  APInt ACarry = RACarry.reverseBits();
556 
557  // Then, the alive input bits are determined from the alive carry bits:
558  APInt NeededToMaintainCarryZero;
559  APInt NeededToMaintainCarryOne;
560  if (OperandNo == 0) {
561  NeededToMaintainCarryZero = LHS.Zero | ~RHS.Zero;
562  NeededToMaintainCarryOne = LHS.One | ~RHS.One;
563  } else {
564  NeededToMaintainCarryZero = RHS.Zero | ~LHS.Zero;
565  NeededToMaintainCarryOne = RHS.One | ~LHS.One;
566  }
567 
568  // As in computeForAddCarry
569  APInt PossibleSumZero = ~LHS.Zero + ~RHS.Zero + !CarryZero;
570  APInt PossibleSumOne = LHS.One + RHS.One + CarryOne;
571 
572  // The below is simplified from
573  //
574  // APInt CarryKnownZero = ~(PossibleSumZero ^ LHS.Zero ^ RHS.Zero);
575  // APInt CarryKnownOne = PossibleSumOne ^ LHS.One ^ RHS.One;
576  // APInt CarryUnknown = ~(CarryKnownZero | CarryKnownOne);
577  //
578  // APInt NeededToMaintainCarry =
579  // (CarryKnownZero & NeededToMaintainCarryZero) |
580  // (CarryKnownOne & NeededToMaintainCarryOne) |
581  // CarryUnknown;
582 
583  APInt NeededToMaintainCarry = (~PossibleSumZero | NeededToMaintainCarryZero) &
584  (PossibleSumOne | NeededToMaintainCarryOne);
585 
586  APInt AB = AOut | (ACarry & NeededToMaintainCarry);
587  return AB;
588 }
589 
591  const APInt &AOut,
592  const KnownBits &LHS,
593  const KnownBits &RHS) {
594  return determineLiveOperandBitsAddCarry(OperandNo, AOut, LHS, RHS, true,
595  false);
596 }
597 
599  const APInt &AOut,
600  const KnownBits &LHS,
601  const KnownBits &RHS) {
602  KnownBits NRHS;
603  NRHS.Zero = RHS.One;
604  NRHS.One = RHS.Zero;
605  return determineLiveOperandBitsAddCarry(OperandNo, AOut, LHS, NRHS, false,
606  true);
607 }
608 
610  return new DemandedBitsWrapperPass();
611 }
612 
613 AnalysisKey DemandedBitsAnalysis::Key;
614 
617  auto &AC = AM.getResult<AssumptionAnalysis>(F);
618  auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
619  return DemandedBits(F, AC, DT);
620 }
621 
625  return PreservedAnalyses::all();
626 }
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:152
llvm::APInt::reverseBits
APInt reverseBits() const
Definition: APInt.cpp:729
AssumptionCache.h
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
llvm::Instruction::getModule
const Module * getModule() const
Return the module owning the function this instruction belongs to or nullptr it the function does not...
Definition: Instruction.cpp:69
llvm::APInt::byteSwap
APInt byteSwap() const
Definition: APInt.cpp:707
llvm::DataLayout
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:113
llvm::User::operands
op_range operands()
Definition: User.h:242
PHI
Rewrite undef for PHI
Definition: AMDGPURewriteUndefForPHI.cpp:101
IntrinsicInst.h
llvm::AnalysisManager::getResult
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:774
InstIterator.h
llvm::APInt::isMask
bool isMask(unsigned numBits) const
Definition: APInt.h:469
llvm::Function
Definition: Function.h:60
Pass.h
llvm::KnownBits::Zero
APInt Zero
Definition: KnownBits.h:24
llvm::X86::SecondMacroFusionInstKind::AB
@ AB
ValueTracking.h
APInt.h
llvm::DemandedBitsAnalysis
An analysis that produces DemandedBits for a function.
Definition: DemandedBits.h:124
llvm::Type
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
llvm::APInt::getBitWidth
unsigned getBitWidth() const
Return the number of bits in the APInt.
Definition: APInt.h:1431
Module.h
T
#define T
Definition: Mips16ISelLowering.cpp:341
isAlwaysLive
static bool isAlwaysLive(Instruction *I)
Definition: DemandedBits.cpp:75
Operator.h
INITIALIZE_PASS_BEGIN
INITIALIZE_PASS_BEGIN(DemandedBitsWrapperPass, "demanded-bits", "Demanded bits analysis", false, false) INITIALIZE_PASS_END(DemandedBitsWrapperPass
llvm::APInt::lshr
APInt lshr(unsigned shiftAmt) const
Logical right-shift function.
Definition: APInt.h:832
RHS
Value * RHS
Definition: X86PartialReduction.cpp:76
llvm::isPowerOf2_32
constexpr bool isPowerOf2_32(uint32_t Value)
Return true if the argument is a power of two > 0.
Definition: MathExtras.h:458
Use.h
llvm::APIntOps::umin
const APInt & umin(const APInt &A, const APInt &B)
Determine the smaller of two APInts considered to be unsigned.
Definition: APInt.h:2157
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
F
#define F(x, y, z)
Definition: MD5.cpp:55
KnownBits.h
llvm::AArch64PACKey::DB
@ DB
Definition: AArch64BaseInfo.h:822
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
llvm::DemandedBitsWrapperPass::runOnFunction
bool runOnFunction(Function &F) override
runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass.
Definition: DemandedBits.cpp:313
Instruction.h
llvm::PatternMatch::m_APInt
apint_match m_APInt(const APInt *&Res)
Match a ConstantInt or splatted ConstantVector, binding the specified pointer to the contained APInt.
Definition: PatternMatch.h:278
LHS
Value * LHS
Definition: X86PartialReduction.cpp:75
llvm::Instruction::getOpcode
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
Definition: Instruction.h:169
llvm::PassRegistry::getPassRegistry
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Definition: PassRegistry.cpp:24
bits
demanded bits
Definition: DemandedBits.cpp:57
llvm::PatternMatch::match
bool match(Val *V, const Pattern &P)
Definition: PatternMatch.h:49
llvm::DemandedBitsPrinterPass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: DemandedBits.cpp:622
llvm::KnownBits::One
APInt One
Definition: KnownBits.h:25
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
llvm::DemandedBitsWrapperPass::print
void print(raw_ostream &OS, const Module *M) const override
print - Print out the internal state of the pass.
Definition: DemandedBits.cpp:71
llvm::APInt::getAllOnes
static APInt getAllOnes(unsigned numBits)
Return an APInt of a specified width with all bits set.
Definition: APInt.h:214
llvm::APInt::getLimitedValue
uint64_t getLimitedValue(uint64_t Limit=UINT64_MAX) const
If this value is smaller than the specified limit, return it, otherwise return the limit value.
Definition: APInt.h:456
false
Definition: StackSlotColoring.cpp:141
llvm::ShlOperator
Definition: Operator.h:356
llvm::createDemandedBitsWrapperPass
FunctionPass * createDemandedBitsWrapperPass()
Create a demanded bits analysis pass.
Definition: DemandedBits.cpp:609
llvm::Instruction
Definition: Instruction.h:42
llvm::DominatorTreeWrapperPass
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:302
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:53
llvm::APInt::getHighBitsSet
static APInt getHighBitsSet(unsigned numBits, unsigned hiBitsSet)
Constructs an APInt value that has the top hiBitsSet bits set.
Definition: APInt.h:279
analysis
demanded Demanded bits analysis
Definition: DemandedBits.cpp:58
determineLiveOperandBitsAddCarry
static APInt determineLiveOperandBitsAddCarry(unsigned OperandNo, const APInt &AOut, const KnownBits &LHS, const KnownBits &RHS, bool CarryZero, bool CarryOne)
Definition: DemandedBits.cpp:529
PatternMatch.h
llvm::APInt::countTrailingZeros
unsigned countTrailingZeros() const
Count the number of trailing zero bits.
Definition: APInt.h:1563
llvm::MCID::Call
@ Call
Definition: MCInstrDesc.h:155
llvm::SetVector< T, SmallVector< T, N >, SmallDenseSet< T, N > >::empty
bool empty() const
Determine if the SetVector is empty or not.
Definition: SetVector.h:72
llvm::CallingConv::ID
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
Type.h
INITIALIZE_PASS_END
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:58
llvm::DemandedBitsWrapperPass::ID
static char ID
Definition: DemandedBits.h:108
llvm::DemandedBits::print
void print(raw_ostream &OS)
Definition: DemandedBits.cpp:507
llvm::instructions
inst_range instructions(Function *F)
Definition: InstIterator.h:133
llvm::Twine::utohexstr
static Twine utohexstr(const uint64_t &Val)
Definition: Twine.h:404
uint64_t
llvm::AssumptionAnalysis
A function analysis which provides an AssumptionCache.
Definition: AssumptionCache.h:173
INITIALIZE_PASS_DEPENDENCY
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
llvm::DemandedBits::determineLiveOperandBitsSub
static APInt determineLiveOperandBitsSub(unsigned OperandNo, const APInt &AOut, const KnownBits &LHS, const KnownBits &RHS)
Compute alive bits of one subtraction operand from alive output and known operand bits.
Definition: DemandedBits.cpp:598
move
compiles ldr LCPI1_0 ldr ldr mov lsr tst moveq r1 ldr LCPI1_1 and r0 bx lr It would be better to do something like to fold the shift into the conditional move
Definition: README.txt:546
llvm::AnalysisKey
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition: PassManager.h:69
llvm::DemandedBits
Definition: DemandedBits.h:41
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::computeKnownBits
void computeKnownBits(const Value *V, KnownBits &Known, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, OptimizationRemarkEmitter *ORE=nullptr, bool UseInstrInfo=true)
Determine which bits of V are known to be either zero or one and return them in the KnownZero/KnownOn...
Definition: ValueTracking.cpp:197
llvm::KnownBits::countMaxLeadingZeros
unsigned countMaxLeadingZeros() const
Returns the maximum number of leading zero bits possible.
Definition: KnownBits.h:283
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::KnownBits::countMaxTrailingZeros
unsigned countMaxTrailingZeros() const
Returns the maximum number of trailing zero bits possible.
Definition: KnownBits.h:273
llvm::Module
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:65
llvm::APInt::urem
APInt urem(const APInt &RHS) const
Unsigned remainder operation.
Definition: APInt.cpp:1664
llvm::APInt
Class for arbitrary precision integers.
Definition: APInt.h:75
llvm::SetVector< T, SmallVector< T, N >, SmallDenseSet< T, N > >::insert
bool insert(const value_type &X)
Insert a new element into the SetVector.
Definition: SetVector.h:141
llvm::print
Printable print(const GCNRegPressure &RP, const GCNSubtarget *ST=nullptr)
Definition: GCNRegPressure.cpp:138
llvm::APIntOps::smin
const APInt & smin(const APInt &A, const APInt &B)
Determine the smaller of two APInts considered to be signed.
Definition: APInt.h:2147
llvm::AssumptionCacheTracker
An immutable pass that tracks lazily created AssumptionCache objects.
Definition: AssumptionCache.h:202
llvm::SetVector< T, SmallVector< T, N >, SmallDenseSet< T, N > >::pop_back_val
T pop_back_val()
Definition: SetVector.h:232
llvm::min
Expected< ExpressionValue > min(const ExpressionValue &Lhs, const ExpressionValue &Rhs)
Definition: FileCheck.cpp:357
Mul
BinaryOperator * Mul
Definition: X86PartialReduction.cpp:70
DataLayout.h
llvm::AnalysisUsage::setPreservesCFG
void setPreservesCFG()
This function should be called by the pass, iff they do not:
Definition: Pass.cpp:265
llvm::Value::getType
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:255
DL
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Definition: AArch64SLSHardening.cpp:76
S
add sub stmia L5 ldr r0 bl L_printf $stub Instead of a and a wouldn t it be better to do three moves *Return an aggregate type is even return S
Definition: README.txt:210
DemandedBits.h
llvm::APInt::zext
APInt zext(unsigned width) const
Zero extend to a new width.
Definition: APInt.cpp:973
llvm::MCID::Select
@ Select
Definition: MCInstrDesc.h:164
llvm::DemandedBitsWrapperPass::getAnalysisUsage
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
Definition: DemandedBits.cpp:64
llvm::APIntOps::umax
const APInt & umax(const APInt &A, const APInt &B)
Determine the larger of two APInts considered to be unsigned.
Definition: APInt.h:2162
llvm::NVPTX::PTXLdStInstCode::V2
@ V2
Definition: NVPTX.h:123
llvm::DemandedBits::isInstructionDead
bool isInstructionDead(Instruction *I)
Return true if, during analysis, I could not be reached.
Definition: DemandedBits.cpp:475
llvm::APInt::trunc
APInt trunc(unsigned width) const
Truncate to new width.
Definition: APInt.cpp:898
llvm::KnownBits
Definition: KnownBits.h:23
llvm::AnalysisUsage::setPreservesAll
void setPreservesAll()
Set by analyses that do not transform their input at all.
Definition: PassAnalysisSupport.h:130
llvm::DemandedBitsWrapperPass
Definition: DemandedBits.h:103
llvm::DemandedBits::determineLiveOperandBitsAdd
static APInt determineLiveOperandBitsAdd(unsigned OperandNo, const APInt &AOut, const KnownBits &LHS, const KnownBits &RHS)
Compute alive bits of one addition operand from alive output and known operand bits.
Definition: DemandedBits.cpp:590
llvm::PreservedAnalyses::all
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:158
llvm::Type::isIntOrIntVectorTy
bool isIntOrIntVectorTy() const
Return true if this is an integer type or a vector of integer types.
Definition: Type.h:216
Casting.h
llvm::BitWidth
constexpr unsigned BitWidth
Definition: BitmaskEnum.h:147
PassManager.h
llvm::DemandedBitsWrapperPass::releaseMemory
void releaseMemory() override
Clean up memory in between runs.
Definition: DemandedBits.cpp:320
llvm::DemandedBits::getDemandedBits
APInt getDemandedBits(Instruction *I)
Return the bits demanded from instruction I.
Definition: DemandedBits.cpp:437
llvm::MCID::Add
@ Add
Definition: MCInstrDesc.h:185
llvm::IntrinsicInst
A wrapper class for inspecting calls to intrinsic functions.
Definition: IntrinsicInst.h:46
llvm::DominatorTreeAnalysis
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:267
Dominators.h
llvm::APInt::getActiveBits
unsigned getActiveBits() const
Compute the number of active bits in the value.
Definition: APInt.h:1455
llvm::PatternMatch
Definition: PatternMatch.h:47
llvm::initializeDemandedBitsWrapperPassPass
void initializeDemandedBitsWrapperPassPass(PassRegistry &)
llvm::DemandedBits::isUseDead
bool isUseDead(Use *U)
Return whether this use is dead by means of not having any demanded bits.
Definition: DemandedBits.cpp:482
llvm::Module::getDataLayout
const DataLayout & getDataLayout() const
Get the data layout for the module's target platform.
Definition: Module.cpp:399
llvm::SmallSetVector
A SetVector that performs no allocations if smaller than a certain size.
Definition: SetVector.h:307
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:42
llvm::APInt::getLowBitsSet
static APInt getLowBitsSet(unsigned numBits, unsigned loBitsSet)
Constructs an APInt value that has the bottom loBitsSet bits set.
Definition: APInt.h:289
llvm::FunctionPass
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:308
llvm::DemandedBitsAnalysis::run
DemandedBits run(Function &F, FunctionAnalysisManager &AM)
Run the analysis pass over a function and produce demanded bits information.
Definition: DemandedBits.cpp:615
llvm::AnalysisUsage::addRequired
AnalysisUsage & addRequired()
Definition: PassAnalysisSupport.h:75
llvm::APInt::getBitsSetFrom
static APInt getBitsSetFrom(unsigned numBits, unsigned loBit)
Constructs an APInt value that has a contiguous range of bits set.
Definition: APInt.h:269
llvm::APInt::shl
APInt shl(unsigned shiftAmt) const
Left-shift function.
Definition: APInt.h:854
llvm::User::getOperand
Value * getOperand(unsigned i) const
Definition: User.h:169
raw_ostream.h
InitializePasses.h
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
Debug.h
llvm::APIntOps::smax
const APInt & smax(const APInt &A, const APInt &B)
Determine the larger of two APInts considered to be signed.
Definition: APInt.h:2152
SetVector.h
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43