LLVM  13.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"
24 #include "llvm/ADT/StringExtras.h"
27 #include "llvm/IR/BasicBlock.h"
28 #include "llvm/IR/Constants.h"
29 #include "llvm/IR/DataLayout.h"
30 #include "llvm/IR/DerivedTypes.h"
31 #include "llvm/IR/Dominators.h"
32 #include "llvm/IR/InstIterator.h"
33 #include "llvm/IR/InstrTypes.h"
34 #include "llvm/IR/Instruction.h"
35 #include "llvm/IR/IntrinsicInst.h"
36 #include "llvm/IR/Intrinsics.h"
37 #include "llvm/IR/Module.h"
38 #include "llvm/IR/Operator.h"
39 #include "llvm/IR/PassManager.h"
40 #include "llvm/IR/PatternMatch.h"
41 #include "llvm/IR/Type.h"
42 #include "llvm/IR/Use.h"
43 #include "llvm/InitializePasses.h"
44 #include "llvm/Pass.h"
45 #include "llvm/Support/Casting.h"
46 #include "llvm/Support/Debug.h"
47 #include "llvm/Support/KnownBits.h"
49 #include <algorithm>
50 #include <cstdint>
51 
52 using namespace llvm;
53 using namespace llvm::PatternMatch;
54 
55 #define DEBUG_TYPE "demanded-bits"
56 
58 
60  "Demanded bits analysis", false, false)
64  "Demanded bits analysis", false, false)
65 
68 }
69 
71  AU.setPreservesCFG();
74  AU.setPreservesAll();
75 }
76 
78  DB->print(OS);
79 }
80 
81 static bool isAlwaysLive(Instruction *I) {
82  return I->isTerminator() || isa<DbgInfoIntrinsic>(I) || I->isEHPad() ||
83  I->mayHaveSideEffects() || !I->willReturn();
84 }
85 
86 void DemandedBits::determineLiveOperandBits(
87  const Instruction *UserI, const Value *Val, unsigned OperandNo,
88  const APInt &AOut, APInt &AB, KnownBits &Known, KnownBits &Known2,
89  bool &KnownBitsComputed) {
90  unsigned BitWidth = AB.getBitWidth();
91 
92  // We're called once per operand, but for some instructions, we need to
93  // compute known bits of both operands in order to determine the live bits of
94  // either (when both operands are instructions themselves). We don't,
95  // however, want to do this twice, so we cache the result in APInts that live
96  // in the caller. For the two-relevant-operands case, both operand values are
97  // provided here.
98  auto ComputeKnownBits =
99  [&](unsigned BitWidth, const Value *V1, const Value *V2) {
100  if (KnownBitsComputed)
101  return;
102  KnownBitsComputed = true;
103 
104  const DataLayout &DL = UserI->getModule()->getDataLayout();
105  Known = KnownBits(BitWidth);
106  computeKnownBits(V1, Known, DL, 0, &AC, UserI, &DT);
107 
108  if (V2) {
109  Known2 = KnownBits(BitWidth);
110  computeKnownBits(V2, Known2, DL, 0, &AC, UserI, &DT);
111  }
112  };
113 
114  switch (UserI->getOpcode()) {
115  default: break;
116  case Instruction::Call:
117  case Instruction::Invoke:
118  if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(UserI)) {
119  switch (II->getIntrinsicID()) {
120  default: break;
121  case Intrinsic::bswap:
122  // The alive bits of the input are the swapped alive bits of
123  // the output.
124  AB = AOut.byteSwap();
125  break;
126  case Intrinsic::bitreverse:
127  // The alive bits of the input are the reversed alive bits of
128  // the output.
129  AB = AOut.reverseBits();
130  break;
131  case Intrinsic::ctlz:
132  if (OperandNo == 0) {
133  // We need some output bits, so we need all bits of the
134  // input to the left of, and including, the leftmost bit
135  // known to be one.
136  ComputeKnownBits(BitWidth, Val, nullptr);
139  }
140  break;
141  case Intrinsic::cttz:
142  if (OperandNo == 0) {
143  // We need some output bits, so we need all bits of the
144  // input to the right of, and including, the rightmost bit
145  // known to be one.
146  ComputeKnownBits(BitWidth, Val, nullptr);
149  }
150  break;
151  case Intrinsic::fshl:
152  case Intrinsic::fshr: {
153  const APInt *SA;
154  if (OperandNo == 2) {
155  // Shift amount is modulo the bitwidth. For powers of two we have
156  // SA % BW == SA & (BW - 1).
157  if (isPowerOf2_32(BitWidth))
158  AB = BitWidth - 1;
159  } else if (match(II->getOperand(2), m_APInt(SA))) {
160  // Normalize to funnel shift left. APInt shifts of BitWidth are well-
161  // defined, so no need to special-case zero shifts here.
162  uint64_t ShiftAmt = SA->urem(BitWidth);
163  if (II->getIntrinsicID() == Intrinsic::fshr)
164  ShiftAmt = BitWidth - ShiftAmt;
165 
166  if (OperandNo == 0)
167  AB = AOut.lshr(ShiftAmt);
168  else if (OperandNo == 1)
169  AB = AOut.shl(BitWidth - ShiftAmt);
170  }
171  break;
172  }
173  case Intrinsic::umax:
174  case Intrinsic::umin:
175  case Intrinsic::smax:
176  case Intrinsic::smin:
177  // If low bits of result are not demanded, they are also not demanded
178  // for the min/max operands.
180  break;
181  }
182  }
183  break;
184  case Instruction::Add:
185  if (AOut.isMask()) {
186  AB = AOut;
187  } else {
188  ComputeKnownBits(BitWidth, UserI->getOperand(0), UserI->getOperand(1));
189  AB = determineLiveOperandBitsAdd(OperandNo, AOut, Known, Known2);
190  }
191  break;
192  case Instruction::Sub:
193  if (AOut.isMask()) {
194  AB = AOut;
195  } else {
196  ComputeKnownBits(BitWidth, UserI->getOperand(0), UserI->getOperand(1));
197  AB = determineLiveOperandBitsSub(OperandNo, AOut, Known, Known2);
198  }
199  break;
200  case Instruction::Mul:
201  // Find the highest live output bit. We don't need any more input
202  // bits than that (adds, and thus subtracts, ripple only to the
203  // left).
205  break;
206  case Instruction::Shl:
207  if (OperandNo == 0) {
208  const APInt *ShiftAmtC;
209  if (match(UserI->getOperand(1), m_APInt(ShiftAmtC))) {
210  uint64_t ShiftAmt = ShiftAmtC->getLimitedValue(BitWidth - 1);
211  AB = AOut.lshr(ShiftAmt);
212 
213  // If the shift is nuw/nsw, then the high bits are not dead
214  // (because we've promised that they *must* be zero).
215  const ShlOperator *S = cast<ShlOperator>(UserI);
216  if (S->hasNoSignedWrap())
217  AB |= APInt::getHighBitsSet(BitWidth, ShiftAmt+1);
218  else if (S->hasNoUnsignedWrap())
219  AB |= APInt::getHighBitsSet(BitWidth, ShiftAmt);
220  }
221  }
222  break;
223  case Instruction::LShr:
224  if (OperandNo == 0) {
225  const APInt *ShiftAmtC;
226  if (match(UserI->getOperand(1), m_APInt(ShiftAmtC))) {
227  uint64_t ShiftAmt = ShiftAmtC->getLimitedValue(BitWidth - 1);
228  AB = AOut.shl(ShiftAmt);
229 
230  // If the shift is exact, then the low bits are not dead
231  // (they must be zero).
232  if (cast<LShrOperator>(UserI)->isExact())
233  AB |= APInt::getLowBitsSet(BitWidth, ShiftAmt);
234  }
235  }
236  break;
237  case Instruction::AShr:
238  if (OperandNo == 0) {
239  const APInt *ShiftAmtC;
240  if (match(UserI->getOperand(1), m_APInt(ShiftAmtC))) {
241  uint64_t ShiftAmt = ShiftAmtC->getLimitedValue(BitWidth - 1);
242  AB = AOut.shl(ShiftAmt);
243  // Because the high input bit is replicated into the
244  // high-order bits of the result, if we need any of those
245  // bits, then we must keep the highest input bit.
246  if ((AOut & APInt::getHighBitsSet(BitWidth, ShiftAmt))
247  .getBoolValue())
248  AB.setSignBit();
249 
250  // If the shift is exact, then the low bits are not dead
251  // (they must be zero).
252  if (cast<AShrOperator>(UserI)->isExact())
253  AB |= APInt::getLowBitsSet(BitWidth, ShiftAmt);
254  }
255  }
256  break;
257  case Instruction::And:
258  AB = AOut;
259 
260  // For bits that are known zero, the corresponding bits in the
261  // other operand are dead (unless they're both zero, in which
262  // case they can't both be dead, so just mark the LHS bits as
263  // dead).
264  ComputeKnownBits(BitWidth, UserI->getOperand(0), UserI->getOperand(1));
265  if (OperandNo == 0)
266  AB &= ~Known2.Zero;
267  else
268  AB &= ~(Known.Zero & ~Known2.Zero);
269  break;
270  case Instruction::Or:
271  AB = AOut;
272 
273  // For bits that are known one, the corresponding bits in the
274  // other operand are dead (unless they're both one, in which
275  // case they can't both be dead, so just mark the LHS bits as
276  // dead).
277  ComputeKnownBits(BitWidth, UserI->getOperand(0), UserI->getOperand(1));
278  if (OperandNo == 0)
279  AB &= ~Known2.One;
280  else
281  AB &= ~(Known.One & ~Known2.One);
282  break;
283  case Instruction::Xor:
284  case Instruction::PHI:
285  AB = AOut;
286  break;
287  case Instruction::Trunc:
288  AB = AOut.zext(BitWidth);
289  break;
290  case Instruction::ZExt:
291  AB = AOut.trunc(BitWidth);
292  break;
293  case Instruction::SExt:
294  AB = AOut.trunc(BitWidth);
295  // Because the high input bit is replicated into the
296  // high-order bits of the result, if we need any of those
297  // bits, then we must keep the highest input bit.
298  if ((AOut & APInt::getHighBitsSet(AOut.getBitWidth(),
299  AOut.getBitWidth() - BitWidth))
300  .getBoolValue())
301  AB.setSignBit();
302  break;
303  case Instruction::Select:
304  if (OperandNo != 0)
305  AB = AOut;
306  break;
307  case Instruction::ExtractElement:
308  if (OperandNo == 0)
309  AB = AOut;
310  break;
311  case Instruction::InsertElement:
312  case Instruction::ShuffleVector:
313  if (OperandNo == 0 || OperandNo == 1)
314  AB = AOut;
315  break;
316  }
317 }
318 
320  auto &AC = getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
321  auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
322  DB.emplace(F, AC, DT);
323  return false;
324 }
325 
327  DB.reset();
328 }
329 
330 void DemandedBits::performAnalysis() {
331  if (Analyzed)
332  // Analysis already completed for this function.
333  return;
334  Analyzed = true;
335 
336  Visited.clear();
337  AliveBits.clear();
338  DeadUses.clear();
339 
341 
342  // Collect the set of "root" instructions that are known live.
343  for (Instruction &I : instructions(F)) {
344  if (!isAlwaysLive(&I))
345  continue;
346 
347  LLVM_DEBUG(dbgs() << "DemandedBits: Root: " << I << "\n");
348  // For integer-valued instructions, set up an initial empty set of alive
349  // bits and add the instruction to the work list. For other instructions
350  // add their operands to the work list (for integer values operands, mark
351  // all bits as live).
352  Type *T = I.getType();
353  if (T->isIntOrIntVectorTy()) {
354  if (AliveBits.try_emplace(&I, T->getScalarSizeInBits(), 0).second)
355  Worklist.insert(&I);
356 
357  continue;
358  }
359 
360  // Non-integer-typed instructions...
361  for (Use &OI : I.operands()) {
362  if (Instruction *J = dyn_cast<Instruction>(OI)) {
363  Type *T = J->getType();
364  if (T->isIntOrIntVectorTy())
365  AliveBits[J] = APInt::getAllOnesValue(T->getScalarSizeInBits());
366  else
367  Visited.insert(J);
368  Worklist.insert(J);
369  }
370  }
371  // To save memory, we don't add I to the Visited set here. Instead, we
372  // check isAlwaysLive on every instruction when searching for dead
373  // instructions later (we need to check isAlwaysLive for the
374  // integer-typed instructions anyway).
375  }
376 
377  // Propagate liveness backwards to operands.
378  while (!Worklist.empty()) {
379  Instruction *UserI = Worklist.pop_back_val();
380 
381  LLVM_DEBUG(dbgs() << "DemandedBits: Visiting: " << *UserI);
382  APInt AOut;
383  bool InputIsKnownDead = false;
384  if (UserI->getType()->isIntOrIntVectorTy()) {
385  AOut = AliveBits[UserI];
386  LLVM_DEBUG(dbgs() << " Alive Out: 0x"
387  << Twine::utohexstr(AOut.getLimitedValue()));
388 
389  // If all bits of the output are dead, then all bits of the input
390  // are also dead.
391  InputIsKnownDead = !AOut && !isAlwaysLive(UserI);
392  }
393  LLVM_DEBUG(dbgs() << "\n");
394 
395  KnownBits Known, Known2;
396  bool KnownBitsComputed = false;
397  // Compute the set of alive bits for each operand. These are anded into the
398  // existing set, if any, and if that changes the set of alive bits, the
399  // operand is added to the work-list.
400  for (Use &OI : UserI->operands()) {
401  // We also want to detect dead uses of arguments, but will only store
402  // demanded bits for instructions.
403  Instruction *I = dyn_cast<Instruction>(OI);
404  if (!I && !isa<Argument>(OI))
405  continue;
406 
407  Type *T = OI->getType();
408  if (T->isIntOrIntVectorTy()) {
409  unsigned BitWidth = T->getScalarSizeInBits();
411  if (InputIsKnownDead) {
412  AB = APInt(BitWidth, 0);
413  } else {
414  // Bits of each operand that are used to compute alive bits of the
415  // output are alive, all others are dead.
416  determineLiveOperandBits(UserI, OI, OI.getOperandNo(), AOut, AB,
417  Known, Known2, KnownBitsComputed);
418 
419  // Keep track of uses which have no demanded bits.
420  if (AB.isNullValue())
421  DeadUses.insert(&OI);
422  else
423  DeadUses.erase(&OI);
424  }
425 
426  if (I) {
427  // If we've added to the set of alive bits (or the operand has not
428  // been previously visited), then re-queue the operand to be visited
429  // again.
430  auto Res = AliveBits.try_emplace(I);
431  if (Res.second || (AB |= Res.first->second) != Res.first->second) {
432  Res.first->second = std::move(AB);
433  Worklist.insert(I);
434  }
435  }
436  } else if (I && Visited.insert(I).second) {
437  Worklist.insert(I);
438  }
439  }
440  }
441 }
442 
444  performAnalysis();
445 
446  auto Found = AliveBits.find(I);
447  if (Found != AliveBits.end())
448  return Found->second;
449 
450  const DataLayout &DL = I->getModule()->getDataLayout();
451  return APInt::getAllOnesValue(
452  DL.getTypeSizeInBits(I->getType()->getScalarType()));
453 }
454 
456  performAnalysis();
457 
458  return !Visited.count(I) && AliveBits.find(I) == AliveBits.end() &&
459  !isAlwaysLive(I);
460 }
461 
463  // We only track integer uses, everything else is assumed live.
464  if (!(*U)->getType()->isIntOrIntVectorTy())
465  return false;
466 
467  // Uses by always-live instructions are never dead.
468  Instruction *UserI = cast<Instruction>(U->getUser());
469  if (isAlwaysLive(UserI))
470  return false;
471 
472  performAnalysis();
473  if (DeadUses.count(U))
474  return true;
475 
476  // If no output bits are demanded, no input bits are demanded and the use
477  // is dead. These uses might not be explicitly present in the DeadUses map.
478  if (UserI->getType()->isIntOrIntVectorTy()) {
479  auto Found = AliveBits.find(UserI);
480  if (Found != AliveBits.end() && Found->second.isNullValue())
481  return true;
482  }
483 
484  return false;
485 }
486 
488  performAnalysis();
489  for (auto &KV : AliveBits) {
490  OS << "DemandedBits: 0x" << Twine::utohexstr(KV.second.getLimitedValue())
491  << " for " << *KV.first << '\n';
492  }
493 }
494 
495 static APInt determineLiveOperandBitsAddCarry(unsigned OperandNo,
496  const APInt &AOut,
497  const KnownBits &LHS,
498  const KnownBits &RHS,
499  bool CarryZero, bool CarryOne) {
500  assert(!(CarryZero && CarryOne) &&
501  "Carry can't be zero and one at the same time");
502 
503  // The following check should be done by the caller, as it also indicates
504  // that LHS and RHS don't need to be computed.
505  //
506  // if (AOut.isMask())
507  // return AOut;
508 
509  // Boundary bits' carry out is unaffected by their carry in.
510  APInt Bound = (LHS.Zero & RHS.Zero) | (LHS.One & RHS.One);
511 
512  // First, the alive carry bits are determined from the alive output bits:
513  // Let demand ripple to the right but only up to any set bit in Bound.
514  // AOut = -1----
515  // Bound = ----1-
516  // ACarry&~AOut = --111-
517  APInt RBound = Bound.reverseBits();
518  APInt RAOut = AOut.reverseBits();
519  APInt RProp = RAOut + (RAOut | ~RBound);
520  APInt RACarry = RProp ^ ~RBound;
521  APInt ACarry = RACarry.reverseBits();
522 
523  // Then, the alive input bits are determined from the alive carry bits:
524  APInt NeededToMaintainCarryZero;
525  APInt NeededToMaintainCarryOne;
526  if (OperandNo == 0) {
527  NeededToMaintainCarryZero = LHS.Zero | ~RHS.Zero;
528  NeededToMaintainCarryOne = LHS.One | ~RHS.One;
529  } else {
530  NeededToMaintainCarryZero = RHS.Zero | ~LHS.Zero;
531  NeededToMaintainCarryOne = RHS.One | ~LHS.One;
532  }
533 
534  // As in computeForAddCarry
535  APInt PossibleSumZero = ~LHS.Zero + ~RHS.Zero + !CarryZero;
536  APInt PossibleSumOne = LHS.One + RHS.One + CarryOne;
537 
538  // The below is simplified from
539  //
540  // APInt CarryKnownZero = ~(PossibleSumZero ^ LHS.Zero ^ RHS.Zero);
541  // APInt CarryKnownOne = PossibleSumOne ^ LHS.One ^ RHS.One;
542  // APInt CarryUnknown = ~(CarryKnownZero | CarryKnownOne);
543  //
544  // APInt NeededToMaintainCarry =
545  // (CarryKnownZero & NeededToMaintainCarryZero) |
546  // (CarryKnownOne & NeededToMaintainCarryOne) |
547  // CarryUnknown;
548 
549  APInt NeededToMaintainCarry = (~PossibleSumZero | NeededToMaintainCarryZero) &
550  (PossibleSumOne | NeededToMaintainCarryOne);
551 
552  APInt AB = AOut | (ACarry & NeededToMaintainCarry);
553  return AB;
554 }
555 
557  const APInt &AOut,
558  const KnownBits &LHS,
559  const KnownBits &RHS) {
560  return determineLiveOperandBitsAddCarry(OperandNo, AOut, LHS, RHS, true,
561  false);
562 }
563 
565  const APInt &AOut,
566  const KnownBits &LHS,
567  const KnownBits &RHS) {
568  KnownBits NRHS;
569  NRHS.Zero = RHS.One;
570  NRHS.One = RHS.Zero;
571  return determineLiveOperandBitsAddCarry(OperandNo, AOut, LHS, NRHS, false,
572  true);
573 }
574 
576  return new DemandedBitsWrapperPass();
577 }
578 
579 AnalysisKey DemandedBitsAnalysis::Key;
580 
583  auto &AC = AM.getResult<AssumptionAnalysis>(F);
584  auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
585  return DemandedBits(F, AC, DT);
586 }
587 
591  return PreservedAnalyses::all();
592 }
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:155
llvm::APInt::reverseBits
APInt reverseBits() const
Definition: APInt.cpp:691
AssumptionCache.h
llvm
Definition: AllocatorList.h:23
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:66
llvm::APInt::byteSwap
APInt byteSwap() const
Definition: APInt.cpp:669
llvm::DataLayout
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:112
print
static void print(raw_ostream &Out, object::Archive::Kind Kind, T Val)
Definition: ArchiveWriter.cpp:147
llvm::User::operands
op_range operands()
Definition: User.h:242
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:785
InstIterator.h
llvm::APInt::isMask
bool isMask(unsigned numBits) const
Definition: APInt.h:501
llvm::Function
Definition: Function.h:61
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:120
llvm::Type
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:46
llvm::APInt::getBitWidth
unsigned getBitWidth() const
Return the number of bits in the APInt.
Definition: APInt.h:1582
Module.h
T
#define T
Definition: Mips16ISelLowering.cpp:341
isAlwaysLive
static bool isAlwaysLive(Instruction *I)
Definition: DemandedBits.cpp:81
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:988
llvm::isPowerOf2_32
constexpr bool isPowerOf2_32(uint32_t Value)
Return true if the argument is a power of two > 0.
Definition: MathExtras.h:491
INITIALIZE_PASS_END
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
Definition: RegBankSelect.cpp:69
Use.h
llvm::APIntOps::umin
const APInt & umin(const APInt &A, const APInt &B)
Determine the smaller of two APInts considered to be signed.
Definition: APInt.h:2184
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:122
F
#define F(x, y, z)
Definition: MD5.cpp:56
KnownBits.h
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
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:319
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:270
llvm::Instruction::getOpcode
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
Definition: Instruction.h:160
llvm::PassRegistry::getPassRegistry
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Definition: PassRegistry.cpp:31
Constants.h
bits
demanded bits
Definition: DemandedBits.cpp:63
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:588
Intrinsics.h
InstrTypes.h
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:77
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:488
false
Definition: StackSlotColoring.cpp:142
llvm::ShlOperator
Definition: Operator.h:438
llvm::createDemandedBitsWrapperPass
FunctionPass * createDemandedBitsWrapperPass()
Create a demanded bits analysis pass.
Definition: DemandedBits.cpp:575
llvm::Instruction
Definition: Instruction.h:45
llvm::DominatorTreeWrapperPass
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:281
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:50
llvm::APInt::getHighBitsSet
static APInt getHighBitsSet(unsigned numBits, unsigned hiBitsSet)
Get a value with high bits set.
Definition: APInt.h:656
analysis
demanded Demanded bits analysis
Definition: DemandedBits.cpp:64
determineLiveOperandBitsAddCarry
static APInt determineLiveOperandBitsAddCarry(unsigned OperandNo, const APInt &AOut, const KnownBits &LHS, const KnownBits &RHS, bool CarryZero, bool CarryOne)
Definition: DemandedBits.cpp:495
PatternMatch.h
llvm::APInt::countTrailingZeros
unsigned countTrailingZeros() const
Count the number of trailing zero bits.
Definition: APInt.h:1701
llvm::MCID::Call
@ Call
Definition: MCInstrDesc.h:154
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
Type.h
llvm::DemandedBitsWrapperPass::ID
static char ID
Definition: DemandedBits.h:104
llvm::DemandedBits::print
void print(raw_ostream &OS)
Definition: DemandedBits.cpp:487
BasicBlock.h
llvm::instructions
inst_range instructions(Function *F)
Definition: InstIterator.h:133
llvm::Twine::utohexstr
static Twine utohexstr(const uint64_t &Val)
Definition: Twine.h:387
llvm::AssumptionAnalysis
A function analysis which provides an AssumptionCache.
Definition: AssumptionCache.h:169
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:564
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:72
llvm::DemandedBits
Definition: DemandedBits.h:40
I
#define I(x, y, z)
Definition: MD5.cpp:59
StringExtras.h
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:211
llvm::KnownBits::countMaxLeadingZeros
unsigned countMaxLeadingZeros() const
Returns the maximum number of leading zero bits possible.
Definition: KnownBits.h:259
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:249
llvm::Module
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:67
llvm::APInt::urem
APInt urem(const APInt &RHS) const
Unsigned remainder operation.
Definition: APInt.cpp:1693
llvm::APInt
Class for arbitrary precision integers.
Definition: APInt.h:71
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::APIntOps::smin
const APInt & smin(const APInt &A, const APInt &B)
Determine the smaller of two APInts considered to be signed.
Definition: APInt.h:2174
llvm::AssumptionCacheTracker
An immutable pass that tracks lazily created AssumptionCache objects.
Definition: AssumptionCache.h:200
llvm::APInt::getAllOnesValue
static APInt getAllOnesValue(unsigned numBits)
Get the all-ones value.
Definition: APInt.h:568
llvm::min
Expected< ExpressionValue > min(const ExpressionValue &Lhs, const ExpressionValue &Rhs)
Definition: FileCheck.cpp:357
DataLayout.h
llvm::AnalysisUsage::setPreservesCFG
void setPreservesCFG()
This function should be called by the pass, iff they do not:
Definition: Pass.cpp:253
llvm::Value::getType
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:256
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:930
llvm::MCID::Select
@ Select
Definition: MCInstrDesc.h:163
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:70
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:2189
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:455
llvm::APInt::trunc
APInt trunc(unsigned width) const
Truncate to new width.
Definition: APInt.cpp:858
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:99
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:556
llvm::PreservedAnalyses::all
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:161
llvm::Type::isIntOrIntVectorTy
bool isIntOrIntVectorTy() const
Return true if this is an integer type or a vector of integer types.
Definition: Type.h:208
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:326
llvm::DemandedBits::getDemandedBits
APInt getDemandedBits(Instruction *I)
Return the bits demanded from instruction I.
Definition: DemandedBits.cpp:443
llvm::MCID::Add
@ Add
Definition: MCInstrDesc.h:184
llvm::IntrinsicInst
A wrapper class for inspecting calls to intrinsic functions.
Definition: IntrinsicInst.h:45
llvm::DominatorTreeAnalysis
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:252
Dominators.h
llvm::APInt::getActiveBits
unsigned getActiveBits() const
Compute the number of active bits in the value.
Definition: APInt.h:1606
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:462
llvm::Module::getDataLayout
const DataLayout & getDataLayout() const
Get the data layout for the module's target platform.
Definition: Module.cpp:397
DerivedTypes.h
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:44
llvm::APInt::getLowBitsSet
static APInt getLowBitsSet(unsigned numBits, unsigned loBitsSet)
Get a value with low bits set.
Definition: APInt.h:668
llvm::FunctionPass
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:298
llvm::DemandedBitsAnalysis::run
DemandedBits run(Function &F, FunctionAnalysisManager &AM)
Run the analysis pass over a function and produce demanded bits information.
Definition: DemandedBits.cpp:581
llvm::AnalysisUsage::addRequired
AnalysisUsage & addRequired()
Definition: PassAnalysisSupport.h:75
llvm::APInt::getBitsSetFrom
static APInt getBitsSetFrom(unsigned numBits, unsigned loBit)
Get a value with upper bits starting at loBit set.
Definition: APInt.h:644
llvm::APInt::shl
APInt shl(unsigned shiftAmt) const
Left-shift function.
Definition: APInt.h:1010
llvm::User::getOperand
Value * getOperand(unsigned i) const
Definition: User.h:169
raw_ostream.h
InitializePasses.h
llvm::SetVector< T, SmallVector< T, N >, SmallDenseSet< T, N > >::pop_back_val
LLVM_NODISCARD T pop_back_val()
Definition: SetVector.h:232
llvm::Value
LLVM Value Representation.
Definition: Value.h:75
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:2179
SetVector.h
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:44
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:38