1 //===-- llvm/Analysis/DemandedBits.h - Determine demanded bits --*- C++ -*-===//
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 
22 #ifndef LLVM_ANALYSIS_DEMANDED_BITS_H
23 #define LLVM_ANALYSIS_DEMANDED_BITS_H
24 
25 #include "llvm/Pass.h"
26 #include "llvm/ADT/APInt.h"
27 #include "llvm/ADT/DenseMap.h"
28 #include "llvm/ADT/SmallPtrSet.h"
29 
30 namespace llvm {
31 
32 class FunctionPass;
33 class Function;
34 class Instruction;
35 class DominatorTree;
36 class AssumptionCache;
37 
38 struct DemandedBits : public FunctionPass {
39   static char ID; // Pass identification, replacement for typeid
40   DemandedBits();
41 
42   bool runOnFunction(Function& F) override;
43   void getAnalysisUsage(AnalysisUsage& AU) const override;
44   void print(raw_ostream &OS, const Module *M) const override;
45 
46   /// Return the bits demanded from instruction I.
47   APInt getDemandedBits(Instruction *I);
48 
49   /// Return true if, during analysis, I could not be reached.
50   bool isInstructionDead(Instruction *I);
51 
52 private:
53   void performAnalysis();
54   void determineLiveOperandBits(const Instruction *UserI,
55                                 const Instruction *I, unsigned OperandNo,
56                                 const APInt &AOut, APInt &AB,
57                                 APInt &KnownZero, APInt &KnownOne,
58                                 APInt &KnownZero2, APInt &KnownOne2);
59 
60   AssumptionCache *AC;
61   DominatorTree *DT;
62   Function *F;
63   bool Analyzed;
64 
65   // The set of visited instructions (non-integer-typed only).
66   SmallPtrSet<Instruction*, 128> Visited;
67   DenseMap<Instruction *, APInt> AliveBits;
68 };
69 
70 /// Create a demanded bits analysis pass.
71 FunctionPass *createDemandedBitsPass();
72 
73 } // End llvm namespace
74 
75 #endif
76