retdec
reaching_definitions.h
Go to the documentation of this file.
1 
11 #ifndef RETDEC_BIN2LLVMIR_ANALYSES_REACHING_DEFINITIONS_H
12 #define RETDEC_BIN2LLVMIR_ANALYSES_REACHING_DEFINITIONS_H
13 
14 #include <map>
15 #include <set>
16 #include <unordered_map>
17 #include <unordered_set>
18 #include <vector>
19 
20 #include <llvm/ADT/SmallPtrSet.h>
21 #include <llvm/IR/Module.h>
22 
25 
26 namespace retdec {
27 namespace bin2llvmir {
28 
29 class Definition;
30 class Use;
31 class BasicBlockEntry;
32 class ReachingDefinitionsAnalysis;
33 
34 using Changed = bool;
35 
36 using BBEntrySet = std::unordered_set<BasicBlockEntry*>;
37 
38 using DefSet = std::unordered_set<Definition*>;
39 using UseSet = std::unordered_set<Use*>;
40 
41 using DefVector = std::vector<Definition>;
42 using UseVector = std::vector<Use>;
43 
45 {
46  public:
47  Definition(llvm::Instruction* d, llvm::Value* s, unsigned bbPos);
48  bool operator==(const Definition& o) const;
49 
50  llvm::Value* getSource();
51  bool dominates(const Use* use) const;
52 
53  public:
55  llvm::Instruction* def;
57  llvm::Value* src;
61  unsigned posInBb = 0;
62 };
63 
64 class Use
65 {
66  public:
67  Use(llvm::Instruction* u, llvm::Value* s, unsigned bbPos);
68  bool operator==(const Use &o) const;
69 
70  bool isUndef() const;
71 
72  public:
74  llvm::Instruction* use;
76  llvm::Value* src;
80  unsigned posInBb = 0;
81 };
82 
84 {
85  public:
86  BasicBlockEntry(const llvm::BasicBlock* b = nullptr, std::size_t _id = 0);
87 
88  std::string getName() const;
89  friend std::ostream& operator<<(
90  std::ostream& out,
91  const BasicBlockEntry& bbe);
92 
93  void initializeKillDefSets();
95 
96  const DefSet& defsFromUse(const llvm::Instruction* I) const;
97  const UseSet& usesFromDef(const llvm::Instruction* I) const;
98  const Definition* getDef(const llvm::Instruction* I) const;
99  const Use* getUse(const llvm::Instruction* I) const;
100 
101  public:
102  const llvm::BasicBlock* bb;
103 
106 
108 
109  // defsIn is union of prevBBs' defsOuts
112  std::unordered_set<llvm::Value*> killDefs;
113 
114  bool changed = false;
115 
116  private:
117  unsigned id;
118 };
119 
121 {
122  public:
123  bool runOnModule(
124  llvm::Module& M,
125  Abi* abi = nullptr,
126  bool trackFlagRegs = false);
127  bool runOnFunction(
128  llvm::Function& F,
129  Abi* abi = nullptr,
130  bool trackFlagRegs = false);
131  void clear();
132  bool wasRun() const;
133 
134  // Full instance interface.
135  //
136  public:
137  const DefSet& defsFromUse(const llvm::Instruction* I) const;
138  const UseSet& usesFromDef(const llvm::Instruction* I) const;
139  const Definition* getDef(const llvm::Instruction* I) const;
140  const Use* getUse(const llvm::Instruction* I) const;
141 
142  friend std::ostream& operator<<(
143  std::ostream& out,
144  const ReachingDefinitionsAnalysis& rda);
145 
146  // On-demand static interface.
147  //
148  public:
149  static std::set<llvm::Instruction*> defsFromUse_onDemand(
150  llvm::Instruction* I);
151  static std::set<llvm::Instruction*> usesFromDef_onDemand(
152  llvm::Instruction* I);
153 
154  private:
155  void run();
156  const BasicBlockEntry& getBasicBlockEntry(const llvm::Instruction* I) const;
157  void initializeBasicBlocks(llvm::Module& M);
158  void initializeBasicBlocks(llvm::Function& F);
160  void initializeKillGenSets();
161  void propagate();
162  void initializeDefsAndUses();
163  void clearInternal();
164 
165  private:
166  std::map<const llvm::Function*, std::map<const llvm::BasicBlock*, BasicBlockEntry>> bbMap;
167  bool _trackFlagRegs = false;
168  const llvm::GlobalVariable* _specialGlobal = nullptr;
169  bool _run = false;
170  Abi* _abi = nullptr;
171 };
172 
173 } // namespace bin2llvmir
174 } // namespace retdec
175 
176 #endif
ABI information.
Debugging utilities.
Definition: abi.h:27
Definition: reaching_definitions.h:84
DefVector defs
Definition: reaching_definitions.h:104
const Use * getUse(const llvm::Instruction *I) const
Definition: reaching_definitions.cpp:476
bool changed
Definition: reaching_definitions.h:114
const UseSet & usesFromDef(const llvm::Instruction *I) const
Definition: reaching_definitions.cpp:460
DefSet defsOut
Definition: reaching_definitions.h:110
DefSet genDefs
Definition: reaching_definitions.h:111
const DefSet & defsFromUse(const llvm::Instruction *I) const
Definition: reaching_definitions.cpp:453
unsigned id
Definition: reaching_definitions.h:117
std::unordered_set< llvm::Value * > killDefs
Definition: reaching_definitions.h:112
UseVector uses
Definition: reaching_definitions.h:105
const llvm::BasicBlock * bb
Definition: reaching_definitions.h:102
std::string getName() const
Definition: reaching_definitions.cpp:442
BasicBlockEntry(const llvm::BasicBlock *b=nullptr, std::size_t _id=0)
Definition: reaching_definitions.cpp:387
void initializeKillDefSets()
Definition: reaching_definitions.cpp:394
BBEntrySet prevBBs
Definition: reaching_definitions.h:107
Changed initDefsOut()
Definition: reaching_definitions.cpp:415
friend std::ostream & operator<<(std::ostream &out, const BasicBlockEntry &bbe)
Definition: reaching_definitions.cpp:485
const Definition * getDef(const llvm::Instruction *I) const
Definition: reaching_definitions.cpp:467
Definition: reaching_definitions.h:45
llvm::Instruction * def
Definition instruction – store or alloca.
Definition: reaching_definitions.h:55
llvm::Value * getSource()
Definition: reaching_definitions.cpp:536
UseSet uses
Definition: reaching_definitions.h:58
bool dominates(const Use *use) const
Definition: reaching_definitions.cpp:546
unsigned posInBb
Definition: reaching_definitions.h:61
Definition(llvm::Instruction *d, llvm::Value *s, unsigned bbPos)
Definition: reaching_definitions.cpp:523
llvm::Value * src
Defined value – store's pointer operand or alloca itself.
Definition: reaching_definitions.h:57
bool operator==(const Definition &o) const
Definition: reaching_definitions.cpp:531
Definition: reaching_definitions.h:121
const Use * getUse(const llvm::Instruction *I) const
Definition: reaching_definitions.cpp:366
void initializeDefsAndUses()
Definition: reaching_definitions.cpp:295
static std::set< llvm::Instruction * > usesFromDef_onDemand(llvm::Instruction *I)
Definition: reaching_definitions.cpp:726
void clearInternal()
Definition: reaching_definitions.cpp:222
void run()
Definition: reaching_definitions.cpp:72
void propagate()
Definition: reaching_definitions.cpp:263
const UseSet & usesFromDef(const llvm::Instruction *I) const
Definition: reaching_definitions.cpp:356
Abi * _abi
Definition: reaching_definitions.h:170
bool wasRun() const
Definition: reaching_definitions.cpp:213
static std::set< llvm::Instruction * > defsFromUse_onDemand(llvm::Instruction *I)
Definition: reaching_definitions.cpp:666
const Definition * getDef(const llvm::Instruction *I) const
Definition: reaching_definitions.cpp:361
friend std::ostream & operator<<(std::ostream &out, const ReachingDefinitionsAnalysis &rda)
Definition: reaching_definitions.cpp:371
void clear()
Definition: reaching_definitions.cpp:207
void initializeKillGenSets()
Definition: reaching_definitions.cpp:254
const BasicBlockEntry & getBasicBlockEntry(const llvm::Instruction *I) const
Definition: reaching_definitions.cpp:337
bool runOnFunction(llvm::Function &F, Abi *abi=nullptr, bool trackFlagRegs=false)
Definition: reaching_definitions.cpp:55
void initializeBasicBlocksPrev()
Definition: reaching_definitions.cpp:234
bool _run
Definition: reaching_definitions.h:169
const DefSet & defsFromUse(const llvm::Instruction *I) const
Definition: reaching_definitions.cpp:351
bool _trackFlagRegs
Definition: reaching_definitions.h:167
std::map< const llvm::Function *, std::map< const llvm::BasicBlock *, BasicBlockEntry > > bbMap
Definition: reaching_definitions.h:166
const llvm::GlobalVariable * _specialGlobal
Definition: reaching_definitions.h:168
bool runOnModule(llvm::Module &M, Abi *abi=nullptr, bool trackFlagRegs=false)
Definition: reaching_definitions.cpp:38
void initializeBasicBlocks(llvm::Module &M)
Definition: reaching_definitions.cpp:84
Definition: reaching_definitions.h:65
bool isUndef() const
Definition: reaching_definitions.cpp:570
Use(llvm::Instruction *u, llvm::Value *s, unsigned bbPos)
Definition: reaching_definitions.cpp:557
llvm::Instruction * use
Use instruction – load or call.
Definition: reaching_definitions.h:74
bool operator==(const Use &o) const
Definition: reaching_definitions.cpp:565
llvm::Value * src
Used value – load's pointer operand, call's argument operand.
Definition: reaching_definitions.h:76
DefSet defs
Definition: reaching_definitions.h:77
unsigned posInBb
Definition: reaching_definitions.h:80
The frontend-end part of the decompiler.
std::unordered_set< BasicBlockEntry * > BBEntrySet
Definition: reaching_definitions.h:36
std::unordered_set< Definition * > DefSet
Definition: reaching_definitions.h:38
std::unordered_set< Use * > UseSet
Definition: reaching_definitions.h:39
std::vector< Use > UseVector
Definition: reaching_definitions.h:42
bool Changed
Definition: reaching_definitions.h:34
std::vector< Definition > DefVector
Definition: reaching_definitions.h:41
Definition: archive_wrapper.h:19