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 
is_zero(pseudo_t pseudo)51 static inline bool is_zero(pseudo_t pseudo)
52 {
53 	return pseudo->type == PSEUDO_VAL && pseudo->value == 0;
54 }
55 
is_nonzero(pseudo_t pseudo)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 
add_bb(struct basic_block_list ** list,struct basic_block * bb)186 static inline void add_bb(struct basic_block_list **list, struct basic_block *bb)
187 {
188 	add_ptr_list(list, bb);
189 }
190 
add_instruction(struct instruction_list ** list,struct instruction * insn)191 static inline void add_instruction(struct instruction_list **list, struct instruction *insn)
192 {
193 	add_ptr_list(list, insn);
194 }
195 
add_multijmp(struct multijmp_list ** list,struct multijmp * multijmp)196 static inline void add_multijmp(struct multijmp_list **list, struct multijmp *multijmp)
197 {
198 	add_ptr_list(list, multijmp);
199 }
200 
add_pseudo(struct pseudo_list ** list,pseudo_t pseudo)201 static inline pseudo_t *add_pseudo(struct pseudo_list **list, pseudo_t pseudo)
202 {
203 	return add_ptr_list(list, pseudo);
204 }
205 
remove_pseudo(struct pseudo_list ** list,pseudo_t pseudo)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 
pseudo_in_list(struct pseudo_list * list,pseudo_t pseudo)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 
bb_terminated(struct basic_block * bb)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 
bb_reachable(struct basic_block * bb)226 static inline int bb_reachable(struct basic_block *bb)
227 {
228 	return bb != NULL;
229 }
230 
lookup_bb(struct basic_block_list * list,struct basic_block * bb)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 
add_pseudo_user_ptr(struct pseudo_user * user,struct pseudo_user_list ** list)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 
has_use_list(pseudo_t p)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 
pseudo_user_list_size(struct pseudo_user_list * list)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 
pseudo_user_list_empty(struct pseudo_user_list * list)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 
has_users(pseudo_t p)257 static inline int has_users(pseudo_t p)
258 {
259 	return !pseudo_user_list_empty(p->users);
260 }
261 
multi_users(pseudo_t p)262 static inline bool multi_users(pseudo_t p)
263 {
264 	return ptr_list_multiple((struct ptr_list *)(p->users));
265 }
266 
nbr_users(pseudo_t p)267 static inline int nbr_users(pseudo_t p)
268 {
269 	return pseudo_user_list_size(p->users);
270 }
271 
alloc_pseudo_user(struct instruction * insn,pseudo_t * pp)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 
use_pseudo(struct instruction * insn,pseudo_t p,pseudo_t * pp)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 
remove_bb_from_list(struct basic_block_list ** list,struct basic_block * entry,int count)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 
replace_bb_in_list(struct basic_block_list ** list,struct basic_block * old,struct basic_block * new,int count)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 
331