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
12struct instruction;
13
14struct pseudo_user {
15	struct instruction *insn;
16	pseudo_t *userp;
17};
18
19DECLARE_ALLOCATOR(pseudo_user);
20DECLARE_PTR_LIST(pseudo_user_list, struct pseudo_user);
21DECLARE_PTRMAP(phi_map, struct symbol *, pseudo_t);
22
23
24enum 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
34struct 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
47extern struct pseudo void_pseudo;
48
49#define VOID (&void_pseudo)
50
51static inline bool is_zero(pseudo_t pseudo)
52{
53	return pseudo->type == PSEUDO_VAL && pseudo->value == 0;
54}
55
56static inline bool is_nonzero(pseudo_t pseudo)
57{
58	return pseudo->type == PSEUDO_VAL && pseudo->value != 0;
59}
60
61
62struct multijmp {
63	struct basic_block *target;
64	long long begin, end;
65};
66
67struct asm_constraint {
68	pseudo_t pseudo;
69	const char *constraint;
70	const struct ident *ident;
71};
72
73DECLARE_ALLOCATOR(asm_constraint);
74DECLARE_PTR_LIST(asm_constraint_list, struct asm_constraint);
75
76struct asm_rules {
77	struct asm_constraint_list *inputs;
78	struct asm_constraint_list *outputs;
79	struct asm_constraint_list *clobbers;
80};
81
82DECLARE_ALLOCATOR(asm_rules);
83
84struct 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
152struct basic_block_list;
153struct instruction_list;
154
155struct 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
186static inline void add_bb(struct basic_block_list **list, struct basic_block *bb)
187{
188	add_ptr_list(list, bb);
189}
190
191static inline void add_instruction(struct instruction_list **list, struct instruction *insn)
192{
193	add_ptr_list(list, insn);
194}
195
196static inline void add_multijmp(struct multijmp_list **list, struct multijmp *multijmp)
197{
198	add_ptr_list(list, multijmp);
199}
200
201static inline pseudo_t *add_pseudo(struct pseudo_list **list, pseudo_t pseudo)
202{
203	return add_ptr_list(list, pseudo);
204}
205
206static 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
211static 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
216static 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
226static inline int bb_reachable(struct basic_block *bb)
227{
228	return bb != NULL;
229}
230
231static 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
237static inline void add_pseudo_user_ptr(struct pseudo_user *user, struct pseudo_user_list **list)
238{
239	add_ptr_list(list, user);
240}
241
242static 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
247static inline int pseudo_user_list_size(struct pseudo_user_list *list)
248{
249	return ptr_list_size((struct ptr_list *)list);
250}
251
252static inline bool pseudo_user_list_empty(struct pseudo_user_list *list)
253{
254	return ptr_list_empty((struct ptr_list *)list);
255}
256
257static inline int has_users(pseudo_t p)
258{
259	return !pseudo_user_list_empty(p->users);
260}
261
262static inline bool multi_users(pseudo_t p)
263{
264	return ptr_list_multiple((struct ptr_list *)(p->users));
265}
266
267static inline int nbr_users(pseudo_t p)
268{
269	return pseudo_user_list_size(p->users);
270}
271
272static 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
280static 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
287static 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
292static 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
298struct 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
308extern void insert_select(struct basic_block *bb, struct instruction *br, struct instruction *phi, pseudo_t if_true, pseudo_t if_false);
309extern void insert_branch(struct basic_block *bb, struct instruction *br, struct basic_block *target);
310
311struct instruction *alloc_phisrc(pseudo_t pseudo, struct symbol *type);
312struct instruction *alloc_phi_node(struct basic_block *bb, struct symbol *type, struct ident *ident);
313struct instruction *insert_phi_node(struct basic_block *bb, struct symbol *var);
314void add_phi_node(struct basic_block *bb, struct instruction *phi_node);
315
316pseudo_t alloc_phi(struct basic_block *source, pseudo_t pseudo, struct symbol *type);
317pseudo_t alloc_pseudo(struct instruction *def);
318pseudo_t value_pseudo(long long val);
319pseudo_t undef_pseudo(void);
320
321struct entrypoint *linearize_symbol(struct symbol *sym);
322int unssa(struct entrypoint *ep);
323void show_entry(struct entrypoint *ep);
324const char *show_pseudo(pseudo_t pseudo);
325void show_bb(struct basic_block *bb);
326const char *show_instruction(struct instruction *insn);
327const char *show_label(struct basic_block *bb);
328
329#endif /* LINEARIZE_H */
330
331