1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
|
/* ia32-dataflow.h - ia32 dataflow analysis
* include file
*
* by scut
*
* this is an additional module which hooks into the ia32_bblock.user pointer
* to provide dataflow analysis information for a function. it provides
* def, use, in and out register and sets at instruction granularity.
*
* see chapter 10.6, pp 631 of the dragon book (live variable analysis, we do
* live register analysis, but the process is the same).
*/
#ifndef IA32_DATAFLOW_H
#define IA32_DATAFLOW_H
#include <ia32-decode.h>
#include <ia32-trace.h>
/* ia32_df_set
*
* a set describing the register behaviour of a statement. a statement could
* be a whole function, a basic block or a single instruction (or any amount
* of code). with this information you can know which registers are unused
* before (all \ in) and after (all \ out) the statement is executed, which
* ones are overwritten (gen) in the statement and which registers are used
* (use) by the statement.
*/
typedef struct {
unsigned int def;
unsigned int use;
unsigned int in;
unsigned int out;
#define IA32_DF_ALL 0xffffffff
#define IA32_DF_SET_REG(elem,regid) ((elem) | (1 << (regid)))
#define IA32_DF_GET_REG(elem,regid) (((elem) & (1 << (regid))) == (1 << (regid)))
#define IA32_DF_GET_REG_MASK(elem) ((elem) & 0xff)
#define IA32_DF_SET_FLAGS(elem,eflmask) ((elem) | ((eflmask) << 8))
#define IA32_DF_GET_FLAGS(elem) (((elem) & 0xffffff00) >> 8)
#define IA32_DF_IS_FLAGS_SET(elem,eflmask) (((elem) & ((eflmask) << 8)) == ((eflmask) << 8))
} ia32_df_set;
/* ia32_df_bblock
*
* convenience structure, holding one ia32_df_set for each instruction within
* a basic block.
*/
typedef struct {
unsigned int df_count; /* number of instructions in bblock */
ia32_df_set * df; /* dataflow sets */
} ia32_df_bblock;
/* ia32_df_abi_hook_type, used to emulate abi behaviour
*/
typedef void (* ia32_df_abi_hook_type)(ia32_instruction *, ia32_df_set *);
/* ia32_df_bbtree_live
*
* do a live variable dataflow analysis on all reachable (non-external marked)
* basic block from `root'. `func' is used for in-memory location, but does
* not take part in the analysis.
*
* return in any case.
*/
void
ia32_df_bbtree_live (ia32_function *func, ia32_bblock *root);
/* ia32_df_bblock_live
*
* do the live register analysis for one basic block `bb'. the basic block
* could be a live-variable virgin, so we fill in everything, in this case
* `last' should be set to zero. it could also be already processed and we
* will update it according to `last' mask, which should be set to the union
* of all following blocks' in set. `mem' is the first byte of the basic
* block.
*
* return zero in case the "first" set has not changed
* return non-zero in case something backpropped to change "first"
*/
int
ia32_df_bblock_live (ia32_bblock *bb, unsigned int last, unsigned char *mem);
/* ia32_df_bblock_copy
*
* create a deep copy of the dataflow basic block information `dfb'.
*
* return the copy on success
* return NULL if there was nothing to copy
*/
ia32_df_bblock *
ia32_df_bblock_copy (ia32_df_bblock *dfb);
/* ia32_df_bblock_split
*
* split the dataflow information `dfb' at the `split_point'th instruction
* into a new block. shorten `dfb' appropiatly.
*
* return the new dataflow set (lieing directly behind `dfb').
*/
ia32_df_bblock *
ia32_df_bblock_split (ia32_df_bblock *dfb, unsigned int split_point);
/* ia32_df_bblock_destroy
*
* free all memory associated with `dfb'.
*
* return in any case
*/
void
ia32_df_bblock_destroy (ia32_df_bblock *dfb);
/* ia32_df_bblock_new
*
* create a new ia32_df_bblock structure for the basic block `bb', which
* starts at `mem'.
*
* return the new structure.
*/
ia32_df_bblock *
ia32_df_bblock_new (ia32_bblock *bb, unsigned char *mem);
/* ia32_df_bblock_append_instruction
*
* append a single instruction at `mem' unconditionally to dataflow basic
* block set `dfb' as new dataflow set.
*
* return in any case
*/
void
ia32_df_bblock_append_instruction (ia32_df_bblock *dfb, unsigned char *mem);
/* ia32_df_set_new
*
* allocate a new df set. any allocations for df sets should be routed through
* this function.
*
* return a pointer to the new allocated set.
*/
ia32_df_set *
ia32_df_set_new (void);
/* ia32_df_bblock_first
*
* convenience function locating the first ia32_df_set of a basic block `bb'.
*
* return the first df set of the basic block on success
* return NULL when there is no df set
*/
ia32_df_set *
ia32_df_bblock_first (ia32_bblock *bb);
/* ia32_df_bblock_last
*
* convenience function locating the last ia32_df_set of a basic block `bb'.
*
* return the last df set of the basic block on success
* return NULL when there is no df set
*/
ia32_df_set *
ia32_df_bblock_last (ia32_bblock *bb);
/* ia32_df_set_printf
*
* print a text representation of the dataflow set `df' to stdout.
*
* return in any case
*/
void
ia32_df_set_print (ia32_df_set *df);
/* ia32_df_set_snprintf
*
* print a text representation of the dataflow set `df' into `buf', being at
* most `len' bytes long. it will always be terminated with a NUL byte.
*
* return in any case
*/
void
ia32_df_set_snprint (ia32_df_set *df, char *buf, unsigned int len);
void
ia32_df_set_snprint_single (unsigned int regmask, char *buf);
/* ia32_df_set_from_instruction
*
* generate a dataflow set for a single instruction. the instruction must be
* completely decoded and given in `inst'. when `df_place' is non-NULL, the
* ia32_df_set structure is generated there, otherwise it is mallocated. note,
* that df.in and df.out are zero in any case.
*
* return NULL on failure
* return pointer to created ia32_df_set structure on success
*/
ia32_df_set *
ia32_df_set_from_instruction (ia32_instruction *inst, ia32_df_set *df_place);
/*** ABI emulation functions, for now only i386-linux */
/* ia32_df_abi_sysvlinux
*
* handle special instructions for dataflow analysis, such as system calls and
* calling conventions.
*
* return in any case
*/
void
ia32_df_abi_sysvlinux (ia32_instruction *inst, ia32_df_set *df);
#endif
|
