1 #ifndef LINEARIZE_H
2 #define LINEARIZE_H
3
4 #include "lib.h"
5 #include "allocate.h"
6 #include "token.h"
7 #include "parse.h"
8 #include "symbol.h"
9
10 struct instruction;
11 DECLARE_PTR_LIST(pseudo_ptr_list, pseudo_t);
12
13 struct pseudo_user {
14 struct instruction *insn;
15 pseudo_t *userp;
16 };
17
18 DECLARE_ALLOCATOR(pseudo_user);
19 DECLARE_PTR_LIST(pseudo_user_list, struct pseudo_user);
20
21
22 enum pseudo_type {
23 PSEUDO_VOID,
24 PSEUDO_REG,
25 PSEUDO_SYM,
26 PSEUDO_VAL,
27 PSEUDO_ARG,
28 PSEUDO_PHI,
29 };
30
31 struct pseudo {
32 int nr;
33 int size:16; /* OP_SETVAL only */
34 enum pseudo_type type:8;
35 struct pseudo_user_list *users;
36 struct ident *ident;
37 union {
38 struct symbol *sym;
39 struct instruction *def;
40 long long value;
41 };
42 void *priv;
43 };
44
45 extern struct pseudo void_pseudo;
46
47 #define VOID (&void_pseudo)
48
49 struct multijmp {
50 struct basic_block *target;
51 int begin, end;
52 };
53
54 struct asm_constraint {
55 pseudo_t pseudo;
56 const char *constraint;
57 const struct ident *ident;
58 };
59
60 DECLARE_ALLOCATOR(asm_constraint);
61 DECLARE_PTR_LIST(asm_constraint_list, struct asm_constraint);
62
63 struct asm_rules {
64 struct asm_constraint_list *inputs;
65 struct asm_constraint_list *outputs;
66 struct asm_constraint_list *clobbers;
67 };
68
69 DECLARE_ALLOCATOR(asm_rules);
70
71 struct instruction {
72 unsigned opcode:8,
73 size:24;
74 struct basic_block *bb;
75 struct position pos;
76 struct symbol *type;
77 union {
78 pseudo_t target;
79 pseudo_t cond; /* for branch and switch */
80 };
81 union {
82 struct /* entrypoint */ {
83 struct pseudo_list *arg_list;
84 };
85 struct /* branch */ {
86 struct basic_block *bb_true, *bb_false;
87 };
88 struct /* switch */ {
89 struct multijmp_list *multijmp_list;
90 };
91 struct /* phi_node */ {
92 struct pseudo_list *phi_list;
93 };
94 struct /* phi source */ {
95 pseudo_t phi_src;
96 struct instruction_list *phi_users;
97 };
98 struct /* unops */ {
99 pseudo_t src;
100 struct symbol *orig_type; /* casts */
101 unsigned int offset; /* memops */
102 };
103 struct /* binops and sel */ {
104 pseudo_t src1, src2, src3;
105 };
106 struct /* slice */ {
107 pseudo_t base;
108 unsigned from, len;
109 };
110 struct /* setval */ {
111 pseudo_t symbol; /* Subtle: same offset as "src" !! */
112 struct expression *val;
113 };
114 struct /* call */ {
115 pseudo_t func;
116 struct pseudo_list *arguments;
117 struct symbol *fntype;
118 };
119 struct /* context */ {
120 int increment;
121 int check;
122 struct expression *context_expr;
123 };
124 struct /* asm */ {
125 const char *string;
126 struct asm_rules *asm_rules;
127 };
128 };
129 };
130
131 enum opcode {
132 OP_BADOP,
133
134 /* Entry */
135 OP_ENTRY,
136
137 /* Terminator */
138 OP_TERMINATOR,
139 OP_RET = OP_TERMINATOR,
140 OP_BR,
141 OP_CBR,
142 OP_SWITCH,
143 OP_INVOKE,
144 OP_COMPUTEDGOTO,
145 OP_UNWIND,
146 OP_TERMINATOR_END = OP_UNWIND,
147
148 /* Binary */
149 OP_BINARY,
150 OP_ADD = OP_BINARY,
151 OP_SUB,
152 OP_MULU, OP_MULS,
153 OP_DIVU, OP_DIVS,
154 OP_MODU, OP_MODS,
155 OP_SHL,
156 OP_LSR, OP_ASR,
157
158 /* Logical */
159 OP_AND,
160 OP_OR,
161 OP_XOR,
162 OP_AND_BOOL,
163 OP_OR_BOOL,
164 OP_BINARY_END = OP_OR_BOOL,
165
166 /* Binary comparison */
167 OP_BINCMP,
168 OP_SET_EQ = OP_BINCMP,
169 OP_SET_NE,
170 OP_SET_LE,
171 OP_SET_GE,
172 OP_SET_LT,
173 OP_SET_GT,
174 OP_SET_B,
175 OP_SET_A,
176 OP_SET_BE,
177 OP_SET_AE,
178 OP_BINCMP_END = OP_SET_AE,
179
180 /* Uni */
181 OP_NOT,
182 OP_NEG,
183
184 /* Select - three input values */
185 OP_SEL,
186
187 /* Memory */
188 OP_MALLOC,
189 OP_FREE,
190 OP_ALLOCA,
191 OP_LOAD,
192 OP_STORE,
193 OP_SETVAL,
194 OP_SYMADDR,
195 OP_GET_ELEMENT_PTR,
196
197 /* Other */
198 OP_PHI,
199 OP_PHISOURCE,
200 OP_CAST,
201 OP_SCAST,
202 OP_FPCAST,
203 OP_PTRCAST,
204 OP_INLINED_CALL,
205 OP_CALL,
206 OP_VANEXT,
207 OP_VAARG,
208 OP_SLICE,
209 OP_SNOP,
210 OP_LNOP,
211 OP_NOP,
212 OP_DEATHNOTE,
213 OP_ASM,
214
215 /* Sparse tagging (line numbers, context, whatever) */
216 OP_CONTEXT,
217 OP_RANGE,
218
219 /* Needed to translate SSA back to normal form */
220 OP_COPY,
221 };
222
223 struct basic_block_list;
224 struct instruction_list;
225
226 struct basic_block {
227 struct position pos;
228 unsigned long generation;
229 int context;
230 struct entrypoint *ep;
231 struct basic_block_list *parents; /* sources */
232 struct basic_block_list *children; /* destinations */
233 struct instruction_list *insns; /* Linear list of instructions */
234 struct pseudo_list *needs, *defines;
235 union {
236 unsigned int nr; /* unique id for label's names */
237 void *priv;
238 };
239 };
240
241
242 static inline void add_bb(struct basic_block_list **list, struct basic_block *bb)
243 {
244 add_ptr_list(list, bb);
245 }
246
247 static inline void add_instruction(struct instruction_list **list, struct instruction *insn)
248 {
249 add_ptr_list(list, insn);
250 }
251
252 static inline void add_multijmp(struct multijmp_list **list, struct multijmp *multijmp)
253 {
254 add_ptr_list(list, multijmp);
255 }
256
257 static inline pseudo_t *add_pseudo(struct pseudo_list **list, pseudo_t pseudo)
258 {
259 return add_ptr_list(list, pseudo);
260 }
261
262 static inline int remove_pseudo(struct pseudo_list **list, pseudo_t pseudo)
263 {
264 return delete_ptr_list_entry((struct ptr_list **)list, pseudo, 0) != 0;
265 }
266
267 static inline int bb_terminated(struct basic_block *bb)
268 {
269 struct instruction *insn;
270 if (!bb)
271 return 0;
272 insn = last_instruction(bb->insns);
273 return insn && insn->opcode >= OP_TERMINATOR
274 && insn->opcode <= OP_TERMINATOR_END;
275 }
276
277 static inline int bb_reachable(struct basic_block *bb)
278 {
279 return bb != NULL;
280 }
281
282 static inline void add_pseudo_ptr(pseudo_t *ptr, struct pseudo_ptr_list **list)
283 {
284 add_ptr_list(list, ptr);
285 }
286
287 static inline void add_pseudo_user_ptr(struct pseudo_user *user, struct pseudo_user_list **list)
288 {
289 add_ptr_list(list, user);
290 }
291
292 static inline int has_use_list(pseudo_t p)
293 {
294 return (p && p->type != PSEUDO_VOID && p->type != PSEUDO_VAL);
295 }
296
297 static inline struct pseudo_user *alloc_pseudo_user(struct instruction *insn, pseudo_t *pp)
298 {
299 struct pseudo_user *user = __alloc_pseudo_user(0);
300 user->userp = pp;
301 user->insn = insn;
302 return user;
303 }
304
305 static inline void use_pseudo(struct instruction *insn, pseudo_t p, pseudo_t *pp)
306 {
307 *pp = p;
308 if (has_use_list(p))
309 add_pseudo_user_ptr(alloc_pseudo_user(insn, pp), &p->users);
310 }
311
312 static inline void remove_bb_from_list(struct basic_block_list **list, struct basic_block *entry, int count)
313 {
314 delete_ptr_list_entry((struct ptr_list **)list, entry, count);
315 }
316
317 static inline void replace_bb_in_list(struct basic_block_list **list,
318 struct basic_block *old, struct basic_block *new, int count)
319 {
320 replace_ptr_list_entry((struct ptr_list **)list, old, new, count);
321 }
322
323 struct entrypoint {
324 struct symbol *name;
325 struct symbol_list *syms;
326 struct pseudo_list *accesses;
327 struct basic_block_list *bbs;
328 struct basic_block *active;
329 struct instruction *entry;
330 };
331
332 extern void insert_select(struct basic_block *bb, struct instruction *br, struct instruction *phi, pseudo_t if_true, pseudo_t if_false);
333 extern void insert_branch(struct basic_block *bb, struct instruction *br, struct basic_block *target);
334
335 pseudo_t alloc_phi(struct basic_block *source, pseudo_t pseudo, int size);
336 pseudo_t alloc_pseudo(struct instruction *def);
337 pseudo_t value_pseudo(struct symbol *type, long long val);
338 unsigned int value_size(long long value);
339
340 struct entrypoint *linearize_symbol(struct symbol *sym);
341 int unssa(struct entrypoint *ep);
342 void show_entry(struct entrypoint *ep);
343 const char *show_pseudo(pseudo_t pseudo);
344 void show_bb(struct basic_block *bb);
345 const char *show_instruction(struct instruction *insn);
346
347 #endif /* LINEARIZE_H */
348
|
1 #ifndef LINEARIZE_H
2 #define LINEARIZE_H
3
4 #include "lib.h"
5 #include "allocate.h"
6 #include "token.h"
7 #include "opcode.h"
8 #include "parse.h"
9 #include "symbol.h"
10 #include "ptrmap.h"
11
12 struct instruction;
13
14 struct pseudo_user {
15 struct instruction *insn;
16 pseudo_t *userp;
17 };
18
19 DECLARE_ALLOCATOR(pseudo_user);
20 DECLARE_PTR_LIST(pseudo_user_list, struct pseudo_user);
21 DECLARE_PTRMAP(phi_map, struct symbol *, pseudo_t);
22
23
24 enum pseudo_type {
25 PSEUDO_VOID,
26 PSEUDO_UNDEF,
27 PSEUDO_REG,
28 PSEUDO_SYM,
29 PSEUDO_VAL,
30 PSEUDO_ARG,
31 PSEUDO_PHI,
32 };
33
34 struct pseudo {
35 int nr;
36 enum pseudo_type type;
37 struct pseudo_user_list *users;
38 struct ident *ident;
39 union {
40 struct symbol *sym;
41 struct instruction *def;
42 long long value;
43 };
44 void *priv;
45 };
46
47 extern struct pseudo void_pseudo;
48
49 #define VOID (&void_pseudo)
50
51 static inline bool is_zero(pseudo_t pseudo)
52 {
53 return pseudo->type == PSEUDO_VAL && pseudo->value == 0;
54 }
55
56 static inline bool is_nonzero(pseudo_t pseudo)
57 {
58 return pseudo->type == PSEUDO_VAL && pseudo->value != 0;
59 }
60
61
62 struct multijmp {
63 struct basic_block *target;
64 long long begin, end;
65 };
66
67 struct asm_constraint {
68 pseudo_t pseudo;
69 const char *constraint;
70 const struct ident *ident;
71 };
72
73 DECLARE_ALLOCATOR(asm_constraint);
74 DECLARE_PTR_LIST(asm_constraint_list, struct asm_constraint);
75
76 struct asm_rules {
77 struct asm_constraint_list *inputs;
78 struct asm_constraint_list *outputs;
79 struct asm_constraint_list *clobbers;
80 };
81
82 DECLARE_ALLOCATOR(asm_rules);
83
84 struct instruction {
85 unsigned opcode:7,
86 tainted:1,
87 size:24;
88 struct basic_block *bb;
89 struct position pos;
90 struct symbol *type;
91 pseudo_t target;
92 union {
93 struct /* entrypoint */ {
94 struct pseudo_list *arg_list;
95 };
96 struct /* branch */ {
97 pseudo_t cond;
98 struct basic_block *bb_true, *bb_false;
99 };
100 struct /* switch */ {
101 pseudo_t _cond;
102 struct multijmp_list *multijmp_list;
103 };
104 struct /* phi_node */ {
105 pseudo_t phi_var; // used for SSA conversion
106 struct pseudo_list *phi_list;
107 unsigned int used:1;
108 };
109 struct /* phi source */ {
110 pseudo_t phi_src;
111 struct instruction_list *phi_users;
112 };
113 struct /* unops */ {
114 pseudo_t src;
115 struct symbol *orig_type; /* casts */
116 };
117 struct /* memops */ {
118 pseudo_t addr; /* alias .src */
119 unsigned int offset;
120 unsigned int is_volatile:1;
121 };
122 struct /* binops and sel */ {
123 pseudo_t src1, src2, src3;
124 };
125 struct /* slice */ {
126 pseudo_t base;
127 unsigned from, len;
128 };
129 struct /* setval */ {
130 struct expression *val;
131 };
132 struct /* setfval */ {
133 long double fvalue;
134 };
135 struct /* call */ {
136 pseudo_t func;
137 struct pseudo_list *arguments;
138 struct symbol_list *fntypes;
139 };
140 struct /* context */ {
141 int increment;
142 int check;
143 struct expression *context_expr;
144 };
145 struct /* asm */ {
146 const char *string;
147 struct asm_rules *asm_rules;
148 };
149 };
150 };
151
152 struct basic_block_list;
153 struct instruction_list;
154
155 struct basic_block {
156 struct position pos;
157 unsigned long generation;
158 union {
159 int context;
160 int postorder_nr; /* postorder number */
161 int dom_level; /* level in the dominance tree */
162 };
163 struct entrypoint *ep;
164 struct basic_block_list *parents; /* sources */
165 struct basic_block_list *children; /* destinations */
166 struct instruction_list *insns; /* Linear list of instructions */
167 struct basic_block *idom; /* link to the immediate dominator */
168 struct basic_block_list *doms; /* list of BB idominated by this one */
169 struct phi_map *phi_map;
170 struct pseudo_list *needs, *defines;
171 union {
172 unsigned int nr; /* unique id for label's names */
173 void *priv;
174 };
175 };
176
177
178 //
179 // return the opcode of the instruction defining ``SRC`` if existing
180 // and OP_BADOP if not. It also assigns the defining instruction
181 // to ``DEF``.
182 #define DEF_OPCODE(DEF, SRC) \
183 (((SRC)->type == PSEUDO_REG && (DEF = (SRC)->def)) ? DEF->opcode : OP_BADOP)
184
185
186 static inline void add_bb(struct basic_block_list **list, struct basic_block *bb)
187 {
188 add_ptr_list(list, bb);
189 }
190
191 static inline void add_instruction(struct instruction_list **list, struct instruction *insn)
192 {
193 add_ptr_list(list, insn);
194 }
195
196 static inline void add_multijmp(struct multijmp_list **list, struct multijmp *multijmp)
197 {
198 add_ptr_list(list, multijmp);
199 }
200
201 static inline pseudo_t *add_pseudo(struct pseudo_list **list, pseudo_t pseudo)
202 {
203 return add_ptr_list(list, pseudo);
204 }
205
206 static inline int remove_pseudo(struct pseudo_list **list, pseudo_t pseudo)
207 {
208 return delete_ptr_list_entry((struct ptr_list **)list, pseudo, 0) != 0;
209 }
210
211 static inline int pseudo_in_list(struct pseudo_list *list, pseudo_t pseudo)
212 {
213 return lookup_ptr_list_entry((struct ptr_list *)list, pseudo);
214 }
215
216 static inline int bb_terminated(struct basic_block *bb)
217 {
218 struct instruction *insn;
219 if (!bb)
220 return 0;
221 insn = last_instruction(bb->insns);
222 return insn && insn->opcode >= OP_TERMINATOR
223 && insn->opcode <= OP_TERMINATOR_END;
224 }
225
226 static inline int bb_reachable(struct basic_block *bb)
227 {
228 return bb != NULL;
229 }
230
231 static inline int lookup_bb(struct basic_block_list *list, struct basic_block *bb)
232 {
233 return lookup_ptr_list_entry((struct ptr_list *)list, bb);
234 }
235
236
237 static inline void add_pseudo_user_ptr(struct pseudo_user *user, struct pseudo_user_list **list)
238 {
239 add_ptr_list(list, user);
240 }
241
242 static inline int has_use_list(pseudo_t p)
243 {
244 return (p && p->type != PSEUDO_VOID && p->type != PSEUDO_UNDEF && p->type != PSEUDO_VAL);
245 }
246
247 static inline int pseudo_user_list_size(struct pseudo_user_list *list)
248 {
249 return ptr_list_size((struct ptr_list *)list);
250 }
251
252 static inline bool pseudo_user_list_empty(struct pseudo_user_list *list)
253 {
254 return ptr_list_empty((struct ptr_list *)list);
255 }
256
257 static inline int has_users(pseudo_t p)
258 {
259 return !pseudo_user_list_empty(p->users);
260 }
261
262 static inline bool multi_users(pseudo_t p)
263 {
264 return ptr_list_multiple((struct ptr_list *)(p->users));
265 }
266
267 static inline int nbr_users(pseudo_t p)
268 {
269 return pseudo_user_list_size(p->users);
270 }
271
272 static inline struct pseudo_user *alloc_pseudo_user(struct instruction *insn, pseudo_t *pp)
273 {
274 struct pseudo_user *user = __alloc_pseudo_user(0);
275 user->userp = pp;
276 user->insn = insn;
277 return user;
278 }
279
280 static inline void use_pseudo(struct instruction *insn, pseudo_t p, pseudo_t *pp)
281 {
282 *pp = p;
283 if (has_use_list(p))
284 add_pseudo_user_ptr(alloc_pseudo_user(insn, pp), &p->users);
285 }
286
287 static inline void remove_bb_from_list(struct basic_block_list **list, struct basic_block *entry, int count)
288 {
289 delete_ptr_list_entry((struct ptr_list **)list, entry, count);
290 }
291
292 static inline void replace_bb_in_list(struct basic_block_list **list,
293 struct basic_block *old, struct basic_block *new, int count)
294 {
295 replace_ptr_list_entry((struct ptr_list **)list, old, new, count);
296 }
297
298 struct entrypoint {
299 struct symbol *name;
300 struct symbol_list *syms;
301 struct pseudo_list *accesses;
302 struct basic_block_list *bbs;
303 struct basic_block *active;
304 struct instruction *entry;
305 unsigned int dom_levels; /* max levels in the dom tree */
306 };
307
308 extern void insert_select(struct basic_block *bb, struct instruction *br, struct instruction *phi, pseudo_t if_true, pseudo_t if_false);
309 extern void insert_branch(struct basic_block *bb, struct instruction *br, struct basic_block *target);
310
311 struct instruction *alloc_phisrc(pseudo_t pseudo, struct symbol *type);
312 struct instruction *alloc_phi_node(struct basic_block *bb, struct symbol *type, struct ident *ident);
313 struct instruction *insert_phi_node(struct basic_block *bb, struct symbol *var);
314 void add_phi_node(struct basic_block *bb, struct instruction *phi_node);
315
316 pseudo_t alloc_phi(struct basic_block *source, pseudo_t pseudo, struct symbol *type);
317 pseudo_t alloc_pseudo(struct instruction *def);
318 pseudo_t value_pseudo(long long val);
319 pseudo_t undef_pseudo(void);
320
321 struct entrypoint *linearize_symbol(struct symbol *sym);
322 int unssa(struct entrypoint *ep);
323 void show_entry(struct entrypoint *ep);
324 const char *show_pseudo(pseudo_t pseudo);
325 void show_bb(struct basic_block *bb);
326 const char *show_instruction(struct instruction *insn);
327 const char *show_label(struct basic_block *bb);
328
329 #endif /* LINEARIZE_H */
330
|