1 | //===- llvm/Analysis/DemandedBits.h - Determine demanded bits ---*- C++ -*-===// |
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 | #ifndef LLVM_ANALYSIS_DEMANDEDBITS_H |
22 | #define LLVM_ANALYSIS_DEMANDEDBITS_H |
23 | |
24 | #include "llvm/ADT/APInt.h" |
25 | #include "llvm/ADT/DenseMap.h" |
26 | #include "llvm/ADT/SmallPtrSet.h" |
27 | #include "llvm/IR/PassManager.h" |
28 | |
29 | namespace llvm { |
30 | |
31 | class AssumptionCache; |
32 | class DominatorTree; |
33 | class Function; |
34 | class Instruction; |
35 | struct KnownBits; |
36 | class raw_ostream; |
37 | |
38 | class DemandedBits { |
39 | public: |
40 | DemandedBits(Function &F, AssumptionCache &AC, DominatorTree &DT) : |
41 | F(F), AC(AC), DT(DT) {} |
42 | |
43 | /// Return the bits demanded from instruction I. |
44 | /// |
45 | /// For vector instructions individual vector elements are not distinguished: |
46 | /// A bit is demanded if it is demanded for any of the vector elements. The |
47 | /// size of the return value corresponds to the type size in bits of the |
48 | /// scalar type. |
49 | /// |
50 | /// Instructions that do not have integer or vector of integer type are |
51 | /// accepted, but will always produce a mask with all bits set. |
52 | APInt getDemandedBits(Instruction *I); |
53 | |
54 | /// Return the bits demanded from use U. |
55 | APInt getDemandedBits(Use *U); |
56 | |
57 | /// Return true if, during analysis, I could not be reached. |
58 | bool isInstructionDead(Instruction *I); |
59 | |
60 | /// Return whether this use is dead by means of not having any demanded bits. |
61 | bool isUseDead(Use *U); |
62 | |
63 | void print(raw_ostream &OS); |
64 | |
65 | /// Compute alive bits of one addition operand from alive output and known |
66 | /// operand bits |
67 | static APInt determineLiveOperandBitsAdd(unsigned OperandNo, |
68 | const APInt &AOut, |
69 | const KnownBits &LHS, |
70 | const KnownBits &RHS); |
71 | |
72 | /// Compute alive bits of one subtraction operand from alive output and known |
73 | /// operand bits |
74 | static APInt determineLiveOperandBitsSub(unsigned OperandNo, |
75 | const APInt &AOut, |
76 | const KnownBits &LHS, |
77 | const KnownBits &RHS); |
78 | |
79 | private: |
80 | void performAnalysis(); |
81 | void determineLiveOperandBits(const Instruction *UserI, |
82 | const Value *Val, unsigned OperandNo, |
83 | const APInt &AOut, APInt &AB, |
84 | KnownBits &Known, KnownBits &Known2, bool &KnownBitsComputed); |
85 | |
86 | Function &F; |
87 | AssumptionCache ∾ |
88 | DominatorTree &DT; |
89 | |
90 | bool Analyzed = false; |
91 | |
92 | // The set of visited instructions (non-integer-typed only). |
93 | SmallPtrSet<Instruction*, 32> Visited; |
94 | DenseMap<Instruction *, APInt> AliveBits; |
95 | // Uses with no demanded bits. If the user also has no demanded bits, the use |
96 | // might not be stored explicitly in this map, to save memory during analysis. |
97 | SmallPtrSet<Use *, 16> DeadUses; |
98 | }; |
99 | |
100 | /// An analysis that produces \c DemandedBits for a function. |
101 | class DemandedBitsAnalysis : public AnalysisInfoMixin<DemandedBitsAnalysis> { |
102 | friend AnalysisInfoMixin<DemandedBitsAnalysis>; |
103 | |
104 | static AnalysisKey Key; |
105 | |
106 | public: |
107 | /// Provide the result type for this analysis pass. |
108 | using Result = DemandedBits; |
109 | |
110 | /// Run the analysis pass over a function and produce demanded bits |
111 | /// information. |
112 | DemandedBits run(Function &F, FunctionAnalysisManager &AM); |
113 | }; |
114 | |
115 | /// Printer pass for DemandedBits |
116 | class DemandedBitsPrinterPass : public PassInfoMixin<DemandedBitsPrinterPass> { |
117 | raw_ostream &OS; |
118 | |
119 | public: |
120 | explicit DemandedBitsPrinterPass(raw_ostream &OS) : OS(OS) {} |
121 | |
122 | PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); |
123 | |
124 | static bool isRequired() { return true; } |
125 | }; |
126 | |
127 | } // end namespace llvm |
128 | |
129 | #endif // LLVM_ANALYSIS_DEMANDEDBITS_H |
130 | |