LLVM  6.0.0svn
DemandedBits.cpp
Go to the documentation of this file.
1 //===- DemandedBits.cpp - Determine demanded bits -------------------------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This pass implements a demanded bits analysis. A demanded bit is one that
11 // contributes to a result; bits that are not demanded can be either zero or
12 // one without affecting control or data flow. For example in this sequence:
13 //
14 // %1 = add i32 %x, %y
15 // %2 = trunc i32 %1 to i16
16 //
17 // Only the lowest 16 bits of %1 are demanded; the rest are removed by the
18 // trunc.
19 //
20 //===----------------------------------------------------------------------===//
21 
23 #include "llvm/ADT/APInt.h"
24 #include "llvm/ADT/SmallPtrSet.h"
25 #include "llvm/ADT/SmallVector.h"
26 #include "llvm/ADT/StringExtras.h"
29 #include "llvm/IR/BasicBlock.h"
30 #include "llvm/IR/Constants.h"
31 #include "llvm/IR/DataLayout.h"
32 #include "llvm/IR/DerivedTypes.h"
33 #include "llvm/IR/Dominators.h"
34 #include "llvm/IR/InstIterator.h"
35 #include "llvm/IR/InstrTypes.h"
36 #include "llvm/IR/Instruction.h"
37 #include "llvm/IR/IntrinsicInst.h"
38 #include "llvm/IR/Intrinsics.h"
39 #include "llvm/IR/Module.h"
40 #include "llvm/IR/Operator.h"
41 #include "llvm/IR/PassManager.h"
42 #include "llvm/IR/Type.h"
43 #include "llvm/IR/Use.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 
54 #define DEBUG_TYPE "demanded-bits"
55 
57 
59  "Demanded bits analysis", false, false)
63  "Demanded bits analysis", false, false)
64 
65 DemandedBitsWrapperPass::DemandedBitsWrapperPass() : FunctionPass(ID) {
67 }
68 
70  AU.setPreservesCFG();
73  AU.setPreservesAll();
74 }
75 
77  DB->print(OS);
78 }
79 
80 static bool isAlwaysLive(Instruction *I) {
81  return isa<TerminatorInst>(I) || isa<DbgInfoIntrinsic>(I) ||
82  I->isEHPad() || I->mayHaveSideEffects();
83 }
84 
85 void DemandedBits::determineLiveOperandBits(
86  const Instruction *UserI, const Instruction *I, unsigned OperandNo,
87  const APInt &AOut, APInt &AB, KnownBits &Known, KnownBits &Known2) {
88  unsigned BitWidth = AB.getBitWidth();
89 
90  // We're called once per operand, but for some instructions, we need to
91  // compute known bits of both operands in order to determine the live bits of
92  // either (when both operands are instructions themselves). We don't,
93  // however, want to do this twice, so we cache the result in APInts that live
94  // in the caller. For the two-relevant-operands case, both operand values are
95  // provided here.
96  auto ComputeKnownBits =
97  [&](unsigned BitWidth, const Value *V1, const Value *V2) {
98  const DataLayout &DL = I->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, I, nullptr);
131  AB = APInt::getHighBitsSet(BitWidth,
132  std::min(BitWidth, Known.countMaxLeadingZeros()+1));
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, I, nullptr);
141  AB = APInt::getLowBitsSet(BitWidth,
142  std::min(BitWidth, Known.countMaxTrailingZeros()+1));
143  }
144  break;
145  }
146  break;
147  case Instruction::Add:
148  case Instruction::Sub:
149  case Instruction::Mul:
150  // Find the highest live output bit. We don't need any more input
151  // bits than that (adds, and thus subtracts, ripple only to the
152  // left).
153  AB = APInt::getLowBitsSet(BitWidth, AOut.getActiveBits());
154  break;
155  case Instruction::Shl:
156  if (OperandNo == 0)
157  if (auto *ShiftAmtC = dyn_cast<ConstantInt>(UserI->getOperand(1))) {
158  uint64_t ShiftAmt = ShiftAmtC->getLimitedValue(BitWidth - 1);
159  AB = AOut.lshr(ShiftAmt);
160 
161  // If the shift is nuw/nsw, then the high bits are not dead
162  // (because we've promised that they *must* be zero).
163  const ShlOperator *S = cast<ShlOperator>(UserI);
164  if (S->hasNoSignedWrap())
165  AB |= APInt::getHighBitsSet(BitWidth, ShiftAmt+1);
166  else if (S->hasNoUnsignedWrap())
167  AB |= APInt::getHighBitsSet(BitWidth, ShiftAmt);
168  }
169  break;
170  case Instruction::LShr:
171  if (OperandNo == 0)
172  if (auto *ShiftAmtC = dyn_cast<ConstantInt>(UserI->getOperand(1))) {
173  uint64_t ShiftAmt = ShiftAmtC->getLimitedValue(BitWidth - 1);
174  AB = AOut.shl(ShiftAmt);
175 
176  // If the shift is exact, then the low bits are not dead
177  // (they must be zero).
178  if (cast<LShrOperator>(UserI)->isExact())
179  AB |= APInt::getLowBitsSet(BitWidth, ShiftAmt);
180  }
181  break;
182  case Instruction::AShr:
183  if (OperandNo == 0)
184  if (auto *ShiftAmtC = dyn_cast<ConstantInt>(UserI->getOperand(1))) {
185  uint64_t ShiftAmt = ShiftAmtC->getLimitedValue(BitWidth - 1);
186  AB = AOut.shl(ShiftAmt);
187  // Because the high input bit is replicated into the
188  // high-order bits of the result, if we need any of those
189  // bits, then we must keep the highest input bit.
190  if ((AOut & APInt::getHighBitsSet(BitWidth, ShiftAmt))
191  .getBoolValue())
192  AB.setSignBit();
193 
194  // If the shift is exact, then the low bits are not dead
195  // (they must be zero).
196  if (cast<AShrOperator>(UserI)->isExact())
197  AB |= APInt::getLowBitsSet(BitWidth, ShiftAmt);
198  }
199  break;
200  case Instruction::And:
201  AB = AOut;
202 
203  // For bits that are known zero, the corresponding bits in the
204  // other operand are dead (unless they're both zero, in which
205  // case they can't both be dead, so just mark the LHS bits as
206  // dead).
207  if (OperandNo == 0) {
208  ComputeKnownBits(BitWidth, I, UserI->getOperand(1));
209  AB &= ~Known2.Zero;
210  } else {
211  if (!isa<Instruction>(UserI->getOperand(0)))
212  ComputeKnownBits(BitWidth, UserI->getOperand(0), I);
213  AB &= ~(Known.Zero & ~Known2.Zero);
214  }
215  break;
216  case Instruction::Or:
217  AB = AOut;
218 
219  // For bits that are known one, the corresponding bits in the
220  // other operand are dead (unless they're both one, in which
221  // case they can't both be dead, so just mark the LHS bits as
222  // dead).
223  if (OperandNo == 0) {
224  ComputeKnownBits(BitWidth, I, UserI->getOperand(1));
225  AB &= ~Known2.One;
226  } else {
227  if (!isa<Instruction>(UserI->getOperand(0)))
228  ComputeKnownBits(BitWidth, UserI->getOperand(0), I);
229  AB &= ~(Known.One & ~Known2.One);
230  }
231  break;
232  case Instruction::Xor:
233  case Instruction::PHI:
234  AB = AOut;
235  break;
236  case Instruction::Trunc:
237  AB = AOut.zext(BitWidth);
238  break;
239  case Instruction::ZExt:
240  AB = AOut.trunc(BitWidth);
241  break;
242  case Instruction::SExt:
243  AB = AOut.trunc(BitWidth);
244  // Because the high input bit is replicated into the
245  // high-order bits of the result, if we need any of those
246  // bits, then we must keep the highest input bit.
247  if ((AOut & APInt::getHighBitsSet(AOut.getBitWidth(),
248  AOut.getBitWidth() - BitWidth))
249  .getBoolValue())
250  AB.setSignBit();
251  break;
252  case Instruction::Select:
253  if (OperandNo != 0)
254  AB = AOut;
255  break;
256  }
257 }
258 
260  auto &AC = getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
261  auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
262  DB.emplace(F, AC, DT);
263  return false;
264 }
265 
267  DB.reset();
268 }
269 
270 void DemandedBits::performAnalysis() {
271  if (Analyzed)
272  // Analysis already completed for this function.
273  return;
274  Analyzed = true;
275 
276  Visited.clear();
277  AliveBits.clear();
278 
280 
281  // Collect the set of "root" instructions that are known live.
282  for (Instruction &I : instructions(F)) {
283  if (!isAlwaysLive(&I))
284  continue;
285 
286  DEBUG(dbgs() << "DemandedBits: Root: " << I << "\n");
287  // For integer-valued instructions, set up an initial empty set of alive
288  // bits and add the instruction to the work list. For other instructions
289  // add their operands to the work list (for integer values operands, mark
290  // all bits as live).
291  if (IntegerType *IT = dyn_cast<IntegerType>(I.getType())) {
292  if (AliveBits.try_emplace(&I, IT->getBitWidth(), 0).second)
293  Worklist.push_back(&I);
294 
295  continue;
296  }
297 
298  // Non-integer-typed instructions...
299  for (Use &OI : I.operands()) {
300  if (Instruction *J = dyn_cast<Instruction>(OI)) {
301  if (IntegerType *IT = dyn_cast<IntegerType>(J->getType()))
302  AliveBits[J] = APInt::getAllOnesValue(IT->getBitWidth());
303  Worklist.push_back(J);
304  }
305  }
306  // To save memory, we don't add I to the Visited set here. Instead, we
307  // check isAlwaysLive on every instruction when searching for dead
308  // instructions later (we need to check isAlwaysLive for the
309  // integer-typed instructions anyway).
310  }
311 
312  // Propagate liveness backwards to operands.
313  while (!Worklist.empty()) {
314  Instruction *UserI = Worklist.pop_back_val();
315 
316  DEBUG(dbgs() << "DemandedBits: Visiting: " << *UserI);
317  APInt AOut;
318  if (UserI->getType()->isIntegerTy()) {
319  AOut = AliveBits[UserI];
320  DEBUG(dbgs() << " Alive Out: " << AOut);
321  }
322  DEBUG(dbgs() << "\n");
323 
324  if (!UserI->getType()->isIntegerTy())
325  Visited.insert(UserI);
326 
327  KnownBits Known, Known2;
328  // Compute the set of alive bits for each operand. These are anded into the
329  // existing set, if any, and if that changes the set of alive bits, the
330  // operand is added to the work-list.
331  for (Use &OI : UserI->operands()) {
332  if (Instruction *I = dyn_cast<Instruction>(OI)) {
333  if (IntegerType *IT = dyn_cast<IntegerType>(I->getType())) {
334  unsigned BitWidth = IT->getBitWidth();
335  APInt AB = APInt::getAllOnesValue(BitWidth);
336  if (UserI->getType()->isIntegerTy() && !AOut &&
337  !isAlwaysLive(UserI)) {
338  AB = APInt(BitWidth, 0);
339  } else {
340  // If all bits of the output are dead, then all bits of the input
341  // Bits of each operand that are used to compute alive bits of the
342  // output are alive, all others are dead.
343  determineLiveOperandBits(UserI, I, OI.getOperandNo(), AOut, AB,
344  Known, Known2);
345  }
346 
347  // If we've added to the set of alive bits (or the operand has not
348  // been previously visited), then re-queue the operand to be visited
349  // again.
350  APInt ABPrev(BitWidth, 0);
351  auto ABI = AliveBits.find(I);
352  if (ABI != AliveBits.end())
353  ABPrev = ABI->second;
354 
355  APInt ABNew = AB | ABPrev;
356  if (ABNew != ABPrev || ABI == AliveBits.end()) {
357  AliveBits[I] = std::move(ABNew);
358  Worklist.push_back(I);
359  }
360  } else if (!Visited.count(I)) {
361  Worklist.push_back(I);
362  }
363  }
364  }
365  }
366 }
367 
369  performAnalysis();
370 
371  const DataLayout &DL = I->getModule()->getDataLayout();
372  auto Found = AliveBits.find(I);
373  if (Found != AliveBits.end())
374  return Found->second;
376 }
377 
379  performAnalysis();
380 
381  return !Visited.count(I) && AliveBits.find(I) == AliveBits.end() &&
382  !isAlwaysLive(I);
383 }
384 
386  performAnalysis();
387  for (auto &KV : AliveBits) {
388  OS << "DemandedBits: 0x" << utohexstr(KV.second.getLimitedValue()) << " for "
389  << *KV.first << "\n";
390  }
391 }
392 
394  return new DemandedBitsWrapperPass();
395 }
396 
397 AnalysisKey DemandedBitsAnalysis::Key;
398 
401  auto &AC = AM.getResult<AssumptionAnalysis>(F);
402  auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
403  return DemandedBits(F, AC, DT);
404 }
405 
409  return PreservedAnalyses::all();
410 }
A parsed version of the target data layout string in and methods for querying it. ...
Definition: DataLayout.h:109
void initializeDemandedBitsWrapperPassPass(PassRegistry &)
void setSignBit()
Set the sign bit to 1.
Definition: APInt.h:1392
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
static APInt getAllOnesValue(unsigned numBits)
Get the all-ones value.
Definition: APInt.h:555
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:687
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
A Module instance is used to store all the information related to an LLVM module. ...
Definition: Module.h:63
bool isInstructionDead(Instruction *I)
Return true if, during analysis, I could not be reached.
APInt zext(unsigned width) const
Zero extend to a new width.
Definition: APInt.cpp:865
static APInt getLowBitsSet(unsigned numBits, unsigned loBitsSet)
Get a value with low bits set.
Definition: APInt.h:641
An immutable pass that tracks lazily created AssumptionCache objects.
demanded bits
unsigned second
APInt trunc(unsigned width) const
Truncate to new width.
Definition: APInt.cpp:818
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:238
F(f)
unsigned countMaxTrailingZeros() const
Returns the maximum number of trailing zero bits possible.
Definition: KnownBits.h:168
This defines the Use class.
unsigned getBitWidth() const
Return the number of bits in the APInt.
Definition: APInt.h:1488
AnalysisUsage & addRequired()
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:51
const DataLayout & getDataLayout() const
Get the data layout for the module&#39;s target platform.
Definition: Module.cpp:361
APInt shl(unsigned shiftAmt) const
Left-shift function.
Definition: APInt.h:981
bool runOnFunction(Function &F) override
runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass...
A Use represents the edge between a Value definition and its users.
Definition: Use.h:56
bool isIntegerTy() const
True if this is an instance of IntegerType.
Definition: Type.h:197
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
An analysis that produces DemandedBits for a function.
Definition: DemandedBits.h:93
This file implements a class to represent arbitrary precision integral constant values and operations...
unsigned getActiveBits() const
Compute the number of active bits in the value.
Definition: APInt.h:1512
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:245
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
Definition: Instruction.h:125
DemandedBits run(Function &F, FunctionAnalysisManager &AM)
Run the analysis pass over a function and produce demanded bits information.
APInt reverseBits() const
Definition: APInt.cpp:643
Value * getOperand(unsigned i) const
Definition: User.h:154
static APInt getHighBitsSet(unsigned numBits, unsigned hiBitsSet)
Get a value with high bits set.
Definition: APInt.h:629
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:153
* if(!EatIfPresent(lltok::kw_thread_local)) return false
ParseOptionalThreadLocal := /*empty.
INITIALIZE_PASS_BEGIN(DemandedBitsWrapperPass, "demanded-bits", "Demanded bits analysis", false, false) INITIALIZE_PASS_END(DemandedBitsWrapperPass
This file contains the declarations for the subclasses of Constant, which represent the different fla...
bool mayHaveSideEffects() const
Return true if the instruction may have side effects.
Definition: Instruction.h:535
Represent the analysis usage information of a pass.
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:285
op_range operands()
Definition: User.h:222
Class to represent integer types.
Definition: DerivedTypes.h:40
demanded Demanded bits analysis
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:159
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
APInt lshr(unsigned shiftAmt) const
Logical right-shift function.
Definition: APInt.h:959
A function analysis which provides an AssumptionCache.
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
unsigned countMaxLeadingZeros() const
Returns the maximum number of leading zero bits possible.
Definition: KnownBits.h:178
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:864
Module.h This file contains the declarations for the Module class.
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:385
void setPreservesCFG()
This function should be called by the pass, iff they do not:
Definition: Pass.cpp:285
APInt getDemandedBits(Instruction *I)
Return the bits demanded from instruction I.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
const Module * getModule() const
Return the module owning the function this instruction belongs to or nullptr it the function does not...
Definition: Instruction.cpp:57
Class for arbitrary precision integers.
Definition: APInt.h:69
void setPreservesAll()
Set by analyses that do not transform their input at all.
bool hasNoSignedWrap() const
Test whether this operation is known to never undergo signed overflow, aka the nsw property...
Definition: Operator.h:96
uint64_t getTypeSizeInBits(Type *Ty) const
Size examples:
Definition: DataLayout.h:530
static cl::opt< ITMode > IT(cl::desc("IT block support"), cl::Hidden, cl::init(DefaultIT), cl::ZeroOrMore, cl::values(clEnumValN(DefaultIT, "arm-default-it", "Generate IT block based on arch"), clEnumValN(RestrictedIT, "arm-restrict-it", "Disallow deprecated IT based on ARMv8"), clEnumValN(NoRestrictedIT, "arm-no-restrict-it", "Allow IT blocks based on ARMv7")))
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:61
void print(raw_ostream &OS, const Module *M) const override
print - Print out the internal state of the pass.
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:475
#define I(x, y, z)
Definition: MD5.cpp:58
APInt byteSwap() const
Definition: APInt.cpp:617
LLVM Value Representation.
Definition: Value.h:73
static bool isAlwaysLive(Instruction *I)
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:44
#define DEBUG(X)
Definition: Debug.h:118
bool isEHPad() const
Return true if the instruction is a variety of EH-block.
Definition: Instruction.h:538
inst_range instructions(Function *F)
Definition: InstIterator.h:134
A container for analyses that lazily runs them and caches their results.
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:267
This header defines various interfaces for pass management in LLVM.
FunctionPass * createDemandedBitsWrapperPass()
Create a demanded bits analysis pass.
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)
Determine which bits of V are known to be either zero or one and return them in the KnownZero/KnownOn...
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition: PassManager.h:70
void releaseMemory() override
Clean up memory in between runs.
void print(raw_ostream &OS)
A wrapper class for inspecting calls to intrinsic functions.
Definition: IntrinsicInst.h:44
std::string utohexstr(uint64_t X, bool LowerCase=false)
Definition: StringExtras.h:76
bool hasNoUnsignedWrap() const
Test whether this operation is known to never undergo unsigned overflow, aka the nuw property...
Definition: Operator.h:90