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:
DemandedBits(Function & F,AssumptionCache & AC,DominatorTree & DT)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:
DemandedBitsPrinterPass(raw_ostream & OS)120   explicit DemandedBitsPrinterPass(raw_ostream &OS) : OS(OS) {}
121 
122   PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
123 
isRequired()124   static bool isRequired() { return true; }
125 };
126 
127 } // end namespace llvm
128 
129 #endif // LLVM_ANALYSIS_DEMANDEDBITS_H
130