LLVM  9.0.0svn
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_DEMANDED_BITS_H
22 #define LLVM_ANALYSIS_DEMANDED_BITS_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 
31 namespace llvm {
32 
33 class AssumptionCache;
34 class DominatorTree;
35 class Function;
36 class Instruction;
37 struct KnownBits;
38 class raw_ostream;
39 
40 class DemandedBits {
41 public:
43  F(F), AC(AC), DT(DT) {}
44 
45  /// Return the bits demanded from instruction I.
46  ///
47  /// For vector instructions individual vector elements are not distinguished:
48  /// A bit is demanded if it is demanded for any of the vector elements. The
49  /// size of the return value corresponds to the type size in bits of the
50  /// scalar type.
51  ///
52  /// Instructions that do not have integer or vector of integer type are
53  /// accepted, but will always produce a mask with all bits set.
55 
56  /// Return true if, during analysis, I could not be reached.
58 
59  /// Return whether this use is dead by means of not having any demanded bits.
60  bool isUseDead(Use *U);
61 
62  void print(raw_ostream &OS);
63 
64 private:
65  void performAnalysis();
66  void determineLiveOperandBits(const Instruction *UserI,
67  const Value *Val, unsigned OperandNo,
68  const APInt &AOut, APInt &AB,
69  KnownBits &Known, KnownBits &Known2, bool &KnownBitsComputed);
70 
71  Function &F;
72  AssumptionCache ∾
73  DominatorTree &DT;
74 
75  bool Analyzed = false;
76 
77  // The set of visited instructions (non-integer-typed only).
80  // Uses with no demanded bits. If the user also has no demanded bits, the use
81  // might not be stored explicitly in this map, to save memory during analysis.
82  SmallPtrSet<Use *, 16> DeadUses;
83 };
84 
86 private:
87  mutable Optional<DemandedBits> DB;
88 
89 public:
90  static char ID; // Pass identification, replacement for typeid
91 
93 
94  bool runOnFunction(Function &F) override;
95  void getAnalysisUsage(AnalysisUsage &AU) const override;
96 
97  /// Clean up memory in between runs
98  void releaseMemory() override;
99 
100  DemandedBits &getDemandedBits() { return *DB; }
101 
102  void print(raw_ostream &OS, const Module *M) const override;
103 };
104 
105 /// An analysis that produces \c DemandedBits for a function.
106 class DemandedBitsAnalysis : public AnalysisInfoMixin<DemandedBitsAnalysis> {
108 
109  static AnalysisKey Key;
110 
111 public:
112  /// Provide the result type for this analysis pass.
114 
115  /// Run the analysis pass over a function and produce demanded bits
116  /// information.
118 };
119 
120 /// Printer pass for DemandedBits
121 class DemandedBitsPrinterPass : public PassInfoMixin<DemandedBitsPrinterPass> {
122  raw_ostream &OS;
123 
124 public:
125  explicit DemandedBitsPrinterPass(raw_ostream &OS) : OS(OS) {}
126 
128 };
129 
130 /// Create a demanded bits analysis pass.
132 
133 } // end namespace llvm
134 
135 #endif // LLVM_ANALYSIS_DEMANDED_BITS_H
This class represents lattice values for constants.
Definition: AllocatorList.h:23
A Module instance is used to store all the information related to an LLVM module. ...
Definition: Module.h:65
bool isInstructionDead(Instruction *I)
Return true if, during analysis, I could not be reached.
DemandedBitsPrinterPass(raw_ostream &OS)
Definition: DemandedBits.h:125
A cache of @llvm.assume calls within a function.
A Use represents the edge between a Value definition and its users.
Definition: Use.h:55
An analysis that produces DemandedBits for a function.
Definition: DemandedBits.h:106
This file implements a class to represent arbitrary precision integral constant values and operations...
Key
PAL metadata keys.
#define F(x, y, z)
Definition: MD5.cpp:55
A CRTP mix-in to automatically provide informational APIs needed for passes.
Definition: PassManager.h:372
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:144
static bool runOnFunction(Function &F, bool PostInlining)
Printer pass for DemandedBits.
Definition: DemandedBits.h:121
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:153
A CRTP mix-in that provides informational APIs needed for analysis passes.
Definition: PassManager.h:389
Represent the analysis usage information of a pass.
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:284
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
Definition: SmallPtrSet.h:417
DemandedBits & getDemandedBits()
Definition: DemandedBits.h:100
DemandedBits(Function &F, AssumptionCache &AC, DominatorTree &DT)
Definition: DemandedBits.h:42
APInt getDemandedBits(Instruction *I)
Return the bits demanded from instruction I.
Class for arbitrary precision integers.
Definition: APInt.h:69
#define I(x, y, z)
Definition: MD5.cpp:58
bool isUseDead(Use *U)
Return whether this use is dead by means of not having any demanded bits.
LLVM Value Representation.
Definition: Value.h:72
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:45
A container for analyses that lazily runs them and caches their results.
This header defines various interfaces for pass management in LLVM.
FunctionPass * createDemandedBitsWrapperPass()
Create a demanded bits analysis pass.
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition: PassManager.h:70
void print(raw_ostream &OS)