LLVM  16.0.0git
DemandedBits.h
Go to the documentation of this file.
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/Optional.h"
27 #include "llvm/ADT/SmallPtrSet.h"
28 #include "llvm/IR/PassManager.h"
29 #include "llvm/Pass.h"
30 #include <optional>
31 
32 namespace llvm {
33 
34 class AssumptionCache;
35 class DominatorTree;
36 class Function;
37 class Instruction;
38 struct KnownBits;
39 class raw_ostream;
40 
41 class DemandedBits {
42 public:
44  F(F), AC(AC), DT(DT) {}
45 
46  /// Return the bits demanded from instruction I.
47  ///
48  /// For vector instructions individual vector elements are not distinguished:
49  /// A bit is demanded if it is demanded for any of the vector elements. The
50  /// size of the return value corresponds to the type size in bits of the
51  /// scalar type.
52  ///
53  /// Instructions that do not have integer or vector of integer type are
54  /// accepted, but will always produce a mask with all bits set.
56 
57  /// Return the bits demanded from use U.
59 
60  /// Return true if, during analysis, I could not be reached.
62 
63  /// Return whether this use is dead by means of not having any demanded bits.
64  bool isUseDead(Use *U);
65 
66  void print(raw_ostream &OS);
67 
68  /// Compute alive bits of one addition operand from alive output and known
69  /// operand bits
70  static APInt determineLiveOperandBitsAdd(unsigned OperandNo,
71  const APInt &AOut,
72  const KnownBits &LHS,
73  const KnownBits &RHS);
74 
75  /// Compute alive bits of one subtraction operand from alive output and known
76  /// operand bits
77  static APInt determineLiveOperandBitsSub(unsigned OperandNo,
78  const APInt &AOut,
79  const KnownBits &LHS,
80  const KnownBits &RHS);
81 
82 private:
83  void performAnalysis();
84  void determineLiveOperandBits(const Instruction *UserI,
85  const Value *Val, unsigned OperandNo,
86  const APInt &AOut, APInt &AB,
87  KnownBits &Known, KnownBits &Known2, bool &KnownBitsComputed);
88 
89  Function &F;
90  AssumptionCache &AC;
91  DominatorTree &DT;
92 
93  bool Analyzed = false;
94 
95  // The set of visited instructions (non-integer-typed only).
98  // Uses with no demanded bits. If the user also has no demanded bits, the use
99  // might not be stored explicitly in this map, to save memory during analysis.
100  SmallPtrSet<Use *, 16> DeadUses;
101 };
102 
104 private:
105  mutable std::optional<DemandedBits> DB;
106 
107 public:
108  static char ID; // Pass identification, replacement for typeid
109 
111 
112  bool runOnFunction(Function &F) override;
113  void getAnalysisUsage(AnalysisUsage &AU) const override;
114 
115  /// Clean up memory in between runs
116  void releaseMemory() override;
117 
118  DemandedBits &getDemandedBits() { return *DB; }
119 
120  void print(raw_ostream &OS, const Module *M) const override;
121 };
122 
123 /// An analysis that produces \c DemandedBits for a function.
124 class DemandedBitsAnalysis : public AnalysisInfoMixin<DemandedBitsAnalysis> {
126 
127  static AnalysisKey Key;
128 
129 public:
130  /// Provide the result type for this analysis pass.
132 
133  /// Run the analysis pass over a function and produce demanded bits
134  /// information.
136 };
137 
138 /// Printer pass for DemandedBits
139 class DemandedBitsPrinterPass : public PassInfoMixin<DemandedBitsPrinterPass> {
140  raw_ostream &OS;
141 
142 public:
143  explicit DemandedBitsPrinterPass(raw_ostream &OS) : OS(OS) {}
144 
146 };
147 
148 /// Create a demanded bits analysis pass.
149 FunctionPass *createDemandedBitsWrapperPass();
150 
151 } // end namespace llvm
152 
153 #endif // LLVM_ANALYSIS_DEMANDEDBITS_H
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:152
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
Optional.h
llvm::PassInfoMixin
A CRTP mix-in to automatically provide informational APIs needed for passes.
Definition: PassManager.h:371
llvm::Function
Definition: Function.h:60
Pass.h
llvm::DemandedBitsPrinterPass
Printer pass for DemandedBits.
Definition: DemandedBits.h:139
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:166
APInt.h
llvm::DemandedBitsAnalysis
An analysis that produces DemandedBits for a function.
Definition: DemandedBits.h:124
DenseMap.h
llvm::SmallPtrSet
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:450
RHS
Value * RHS
Definition: X86PartialReduction.cpp:76
F
#define F(x, y, z)
Definition: MD5.cpp:55
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:313
LHS
Value * LHS
Definition: X86PartialReduction.cpp:75
llvm::DemandedBitsPrinterPass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: DemandedBits.cpp:622
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:71
llvm::createDemandedBitsWrapperPass
FunctionPass * createDemandedBitsWrapperPass()
Create a demanded bits analysis pass.
Definition: DemandedBits.cpp:609
llvm::Instruction
Definition: Instruction.h:42
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:53
SmallPtrSet.h
llvm::DemandedBitsWrapperPass::ID
static char ID
Definition: DemandedBits.h:108
llvm::DemandedBits::print
void print(raw_ostream &OS)
Definition: DemandedBits.cpp:507
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:598
llvm::DenseMap
Definition: DenseMap.h:714
llvm::AnalysisKey
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition: PassManager.h:69
llvm::DemandedBits
Definition: DemandedBits.h:41
llvm::DemandedBits::DemandedBits
DemandedBits(Function &F, AssumptionCache &AC, DominatorTree &DT)
Definition: DemandedBits.h:43
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::Module
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:66
llvm::AnalysisInfoMixin
A CRTP mix-in that provides informational APIs needed for analysis passes.
Definition: PassManager.h:394
llvm::APInt
Class for arbitrary precision integers.
Definition: APInt.h:75
llvm::AssumptionCache
A cache of @llvm.assume calls within a function.
Definition: AssumptionCache.h:42
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:64
llvm::DemandedBits::isInstructionDead
bool isInstructionDead(Instruction *I)
Return true if, during analysis, I could not be reached.
Definition: DemandedBits.cpp:475
llvm::KnownBits
Definition: KnownBits.h:23
llvm::DemandedBitsWrapperPass
Definition: DemandedBits.h:103
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:590
PassManager.h
llvm::DemandedBitsWrapperPass::DemandedBitsWrapperPass
DemandedBitsWrapperPass()
Definition: DemandedBits.cpp:60
llvm::DemandedBitsWrapperPass::releaseMemory
void releaseMemory() override
Clean up memory in between runs.
Definition: DemandedBits.cpp:320
llvm::DemandedBits::getDemandedBits
APInt getDemandedBits(Instruction *I)
Return the bits demanded from instruction I.
Definition: DemandedBits.cpp:437
llvm::DemandedBitsWrapperPass::getDemandedBits
DemandedBits & getDemandedBits()
Definition: DemandedBits.h:118
llvm::DemandedBits::isUseDead
bool isUseDead(Use *U)
Return whether this use is dead by means of not having any demanded bits.
Definition: DemandedBits.cpp:482
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:42
llvm::FunctionPass
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:308
llvm::DemandedBitsAnalysis::run
DemandedBits run(Function &F, FunctionAnalysisManager &AM)
Run the analysis pass over a function and produce demanded bits information.
Definition: DemandedBits.cpp:615
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
llvm::codeview::PublicSymFlags::Function
@ Function
llvm::DemandedBitsPrinterPass::DemandedBitsPrinterPass
DemandedBitsPrinterPass(raw_ostream &OS)
Definition: DemandedBits.h:143
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43