LLVM  6.0.0svn
DemandedBits.h
Go to the documentation of this file.
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/ADT/APInt.h"
26 #include "llvm/ADT/DenseMap.h"
27 #include "llvm/ADT/Optional.h"
28 #include "llvm/ADT/SmallPtrSet.h"
29 #include "llvm/IR/PassManager.h"
30 #include "llvm/Pass.h"
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.
48 
49  /// Return true if, during analysis, I could not be reached.
51 
52  void print(raw_ostream &OS);
53 
54 private:
55  void performAnalysis();
56  void determineLiveOperandBits(const Instruction *UserI,
57  const Instruction *I, unsigned OperandNo,
58  const APInt &AOut, APInt &AB,
59  KnownBits &Known, KnownBits &Known2);
60 
61  Function &F;
62  AssumptionCache ∾
63  DominatorTree &DT;
64 
65  bool Analyzed = false;
66 
67  // The set of visited instructions (non-integer-typed only).
70 };
71 
73 private:
74  mutable Optional<DemandedBits> DB;
75 
76 public:
77  static char ID; // Pass identification, replacement for typeid
78 
80 
81  bool runOnFunction(Function &F) override;
82  void getAnalysisUsage(AnalysisUsage &AU) const override;
83 
84  /// Clean up memory in between runs
85  void releaseMemory() override;
86 
87  DemandedBits &getDemandedBits() { return *DB; }
88 
89  void print(raw_ostream &OS, const Module *M) const override;
90 };
91 
92 /// An analysis that produces \c DemandedBits for a function.
93 class DemandedBitsAnalysis : public AnalysisInfoMixin<DemandedBitsAnalysis> {
95 
96  static AnalysisKey Key;
97 
98 public:
99  /// \brief Provide the result type for this analysis pass.
101 
102  /// \brief Run the analysis pass over a function and produce demanded bits
103  /// information.
105 };
106 
107 /// \brief Printer pass for DemandedBits
108 class DemandedBitsPrinterPass : public PassInfoMixin<DemandedBitsPrinterPass> {
109  raw_ostream &OS;
110 
111 public:
112  explicit DemandedBitsPrinterPass(raw_ostream &OS) : OS(OS) {}
113 
115 };
116 
117 /// Create a demanded bits analysis pass.
119 
120 } // end namespace llvm
121 
122 #endif // LLVM_ANALYSIS_DEMANDED_BITS_H
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
A Module instance is used to store all the information related to an LLVM module. ...
Definition: Module.h:63
bool isInstructionDead(Instruction *I)
Return true if, during analysis, I could not be reached.
DemandedBitsPrinterPass(raw_ostream &OS)
Definition: DemandedBits.h:112
A cache of .assume calls within a function.
An analysis that produces DemandedBits for a function.
Definition: DemandedBits.h:93
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:365
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:140
static bool runOnFunction(Function &F, bool PostInlining)
Printer pass for DemandedBits.
Definition: DemandedBits.h:108
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:382
Represent the analysis usage information of a pass.
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:285
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
Definition: SmallPtrSet.h:418
DemandedBits & getDemandedBits()
Definition: DemandedBits.h:87
DemandedBits(Function &F, AssumptionCache &AC, DominatorTree &DT)
Definition: DemandedBits.h:43
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
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:44
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)