11f5207b7SJohn Levon #ifndef LINEARIZE_H
21f5207b7SJohn Levon #define LINEARIZE_H
31f5207b7SJohn Levon 
41f5207b7SJohn Levon #include "lib.h"
51f5207b7SJohn Levon #include "allocate.h"
61f5207b7SJohn Levon #include "token.h"
7*c85f09ccSJohn Levon #include "opcode.h"
81f5207b7SJohn Levon #include "parse.h"
91f5207b7SJohn Levon #include "symbol.h"
10*c85f09ccSJohn Levon #include "ptrmap.h"
111f5207b7SJohn Levon 
121f5207b7SJohn Levon struct instruction;
131f5207b7SJohn Levon 
141f5207b7SJohn Levon struct pseudo_user {
151f5207b7SJohn Levon 	struct instruction *insn;
161f5207b7SJohn Levon 	pseudo_t *userp;
171f5207b7SJohn Levon };
181f5207b7SJohn Levon 
191f5207b7SJohn Levon DECLARE_ALLOCATOR(pseudo_user);
201f5207b7SJohn Levon DECLARE_PTR_LIST(pseudo_user_list, struct pseudo_user);
21*c85f09ccSJohn Levon DECLARE_PTRMAP(phi_map, struct symbol *, pseudo_t);
221f5207b7SJohn Levon 
231f5207b7SJohn Levon 
241f5207b7SJohn Levon enum pseudo_type {
251f5207b7SJohn Levon 	PSEUDO_VOID,
26*c85f09ccSJohn Levon 	PSEUDO_UNDEF,
271f5207b7SJohn Levon 	PSEUDO_REG,
281f5207b7SJohn Levon 	PSEUDO_SYM,
291f5207b7SJohn Levon 	PSEUDO_VAL,
301f5207b7SJohn Levon 	PSEUDO_ARG,
311f5207b7SJohn Levon 	PSEUDO_PHI,
321f5207b7SJohn Levon };
331f5207b7SJohn Levon 
341f5207b7SJohn Levon struct pseudo {
351f5207b7SJohn Levon 	int nr;
36*c85f09ccSJohn Levon 	enum pseudo_type type;
371f5207b7SJohn Levon 	struct pseudo_user_list *users;
381f5207b7SJohn Levon 	struct ident *ident;
391f5207b7SJohn Levon 	union {
401f5207b7SJohn Levon 		struct symbol *sym;
411f5207b7SJohn Levon 		struct instruction *def;
421f5207b7SJohn Levon 		long long value;
431f5207b7SJohn Levon 	};
441f5207b7SJohn Levon 	void *priv;
451f5207b7SJohn Levon };
461f5207b7SJohn Levon 
471f5207b7SJohn Levon extern struct pseudo void_pseudo;
481f5207b7SJohn Levon 
491f5207b7SJohn Levon #define VOID (&void_pseudo)
501f5207b7SJohn Levon 
is_zero(pseudo_t pseudo)51*c85f09ccSJohn Levon static inline bool is_zero(pseudo_t pseudo)
52*c85f09ccSJohn Levon {
53*c85f09ccSJohn Levon 	return pseudo->type == PSEUDO_VAL && pseudo->value == 0;
54*c85f09ccSJohn Levon }
55*c85f09ccSJohn Levon 
is_nonzero(pseudo_t pseudo)56*c85f09ccSJohn Levon static inline bool is_nonzero(pseudo_t pseudo)
57*c85f09ccSJohn Levon {
58*c85f09ccSJohn Levon 	return pseudo->type == PSEUDO_VAL && pseudo->value != 0;
59*c85f09ccSJohn Levon }
60*c85f09ccSJohn Levon 
61*c85f09ccSJohn Levon 
621f5207b7SJohn Levon struct multijmp {
631f5207b7SJohn Levon 	struct basic_block *target;
64*c85f09ccSJohn Levon 	long long begin, end;
651f5207b7SJohn Levon };
661f5207b7SJohn Levon 
671f5207b7SJohn Levon struct asm_constraint {
681f5207b7SJohn Levon 	pseudo_t pseudo;
691f5207b7SJohn Levon 	const char *constraint;
701f5207b7SJohn Levon 	const struct ident *ident;
711f5207b7SJohn Levon };
721f5207b7SJohn Levon 
731f5207b7SJohn Levon DECLARE_ALLOCATOR(asm_constraint);
741f5207b7SJohn Levon DECLARE_PTR_LIST(asm_constraint_list, struct asm_constraint);
751f5207b7SJohn Levon 
761f5207b7SJohn Levon struct asm_rules {
771f5207b7SJohn Levon 	struct asm_constraint_list *inputs;
781f5207b7SJohn Levon 	struct asm_constraint_list *outputs;
791f5207b7SJohn Levon 	struct asm_constraint_list *clobbers;
801f5207b7SJohn Levon };
811f5207b7SJohn Levon 
821f5207b7SJohn Levon DECLARE_ALLOCATOR(asm_rules);
831f5207b7SJohn Levon 
841f5207b7SJohn Levon struct instruction {
85*c85f09ccSJohn Levon 	unsigned opcode:7,
86*c85f09ccSJohn Levon 		 tainted:1,
871f5207b7SJohn Levon 		 size:24;
881f5207b7SJohn Levon 	struct basic_block *bb;
891f5207b7SJohn Levon 	struct position pos;
901f5207b7SJohn Levon 	struct symbol *type;
91*c85f09ccSJohn Levon 	pseudo_t target;
921f5207b7SJohn Levon 	union {
931f5207b7SJohn Levon 		struct /* entrypoint */ {
941f5207b7SJohn Levon 			struct pseudo_list *arg_list;
951f5207b7SJohn Levon 		};
961f5207b7SJohn Levon 		struct /* branch */ {
97*c85f09ccSJohn Levon 			pseudo_t cond;
981f5207b7SJohn Levon 			struct basic_block *bb_true, *bb_false;
991f5207b7SJohn Levon 		};
1001f5207b7SJohn Levon 		struct /* switch */ {
101*c85f09ccSJohn Levon 			pseudo_t _cond;
1021f5207b7SJohn Levon 			struct multijmp_list *multijmp_list;
1031f5207b7SJohn Levon 		};
1041f5207b7SJohn Levon 		struct /* phi_node */ {
105*c85f09ccSJohn Levon 			pseudo_t phi_var;		// used for SSA conversion
1061f5207b7SJohn Levon 			struct pseudo_list *phi_list;
107*c85f09ccSJohn Levon 			unsigned int used:1;
1081f5207b7SJohn Levon 		};
1091f5207b7SJohn Levon 		struct /* phi source */ {
1101f5207b7SJohn Levon 			pseudo_t phi_src;
1111f5207b7SJohn Levon 			struct instruction_list *phi_users;
1121f5207b7SJohn Levon 		};
1131f5207b7SJohn Levon 		struct /* unops */ {
1141f5207b7SJohn Levon 			pseudo_t src;
1151f5207b7SJohn Levon 			struct symbol *orig_type;	/* casts */
116*c85f09ccSJohn Levon 		};
117*c85f09ccSJohn Levon 		struct /* memops */ {
118*c85f09ccSJohn Levon 			pseudo_t addr;			/* alias .src */
119*c85f09ccSJohn Levon 			unsigned int offset;
120*c85f09ccSJohn Levon 			unsigned int is_volatile:1;
1211f5207b7SJohn Levon 		};
1221f5207b7SJohn Levon 		struct /* binops and sel */ {
1231f5207b7SJohn Levon 			pseudo_t src1, src2, src3;
1241f5207b7SJohn Levon 		};
1251f5207b7SJohn Levon 		struct /* slice */ {
1261f5207b7SJohn Levon 			pseudo_t base;
1271f5207b7SJohn Levon 			unsigned from, len;
1281f5207b7SJohn Levon 		};
1291f5207b7SJohn Levon 		struct /* setval */ {
1301f5207b7SJohn Levon 			struct expression *val;
1311f5207b7SJohn Levon 		};
132*c85f09ccSJohn Levon 		struct /* setfval */ {
133*c85f09ccSJohn Levon 			long double fvalue;
134*c85f09ccSJohn Levon 		};
1351f5207b7SJohn Levon 		struct /* call */ {
1361f5207b7SJohn Levon 			pseudo_t func;
1371f5207b7SJohn Levon 			struct pseudo_list *arguments;
138*c85f09ccSJohn Levon 			struct symbol_list *fntypes;
1391f5207b7SJohn Levon 		};
1401f5207b7SJohn Levon 		struct /* context */ {
1411f5207b7SJohn Levon 			int increment;
1421f5207b7SJohn Levon 			int check;
1431f5207b7SJohn Levon 			struct expression *context_expr;
1441f5207b7SJohn Levon 		};
1451f5207b7SJohn Levon 		struct /* asm */ {
1461f5207b7SJohn Levon 			const char *string;
1471f5207b7SJohn Levon 			struct asm_rules *asm_rules;
1481f5207b7SJohn Levon 		};
1491f5207b7SJohn Levon 	};
1501f5207b7SJohn Levon };
1511f5207b7SJohn Levon 
1521f5207b7SJohn Levon struct basic_block_list;
1531f5207b7SJohn Levon struct instruction_list;
1541f5207b7SJohn Levon 
1551f5207b7SJohn Levon struct basic_block {
1561f5207b7SJohn Levon 	struct position pos;
1571f5207b7SJohn Levon 	unsigned long generation;
158*c85f09ccSJohn Levon 	union {
159*c85f09ccSJohn Levon 		int context;
160*c85f09ccSJohn Levon 		int postorder_nr;	/* postorder number */
161*c85f09ccSJohn Levon 		int dom_level;		/* level in the dominance tree */
162*c85f09ccSJohn Levon 	};
1631f5207b7SJohn Levon 	struct entrypoint *ep;
1641f5207b7SJohn Levon 	struct basic_block_list *parents; /* sources */
1651f5207b7SJohn Levon 	struct basic_block_list *children; /* destinations */
1661f5207b7SJohn Levon 	struct instruction_list *insns;	/* Linear list of instructions */
167*c85f09ccSJohn Levon 	struct basic_block *idom;	/* link to the immediate dominator */
168*c85f09ccSJohn Levon 	struct basic_block_list *doms;	/* list of BB idominated by this one */
169*c85f09ccSJohn Levon 	struct phi_map *phi_map;
1701f5207b7SJohn Levon 	struct pseudo_list *needs, *defines;
1711f5207b7SJohn Levon 	union {
1721f5207b7SJohn Levon 		unsigned int nr;	/* unique id for label's names */
1731f5207b7SJohn Levon 		void *priv;
1741f5207b7SJohn Levon 	};
1751f5207b7SJohn Levon };
1761f5207b7SJohn Levon 
1771f5207b7SJohn Levon 
178*c85f09ccSJohn Levon //
179*c85f09ccSJohn Levon // return the opcode of the instruction defining ``SRC`` if existing
180*c85f09ccSJohn Levon // and OP_BADOP if not. It also assigns the defining instruction
181*c85f09ccSJohn Levon // to ``DEF``.
182*c85f09ccSJohn Levon #define DEF_OPCODE(DEF, SRC)	\
183*c85f09ccSJohn Levon 	(((SRC)->type == PSEUDO_REG && (DEF = (SRC)->def)) ? DEF->opcode : OP_BADOP)
184*c85f09ccSJohn Levon 
185*c85f09ccSJohn Levon 
add_bb(struct basic_block_list ** list,struct basic_block * bb)1861f5207b7SJohn Levon static inline void add_bb(struct basic_block_list **list, struct basic_block *bb)
1871f5207b7SJohn Levon {
1881f5207b7SJohn Levon 	add_ptr_list(list, bb);
1891f5207b7SJohn Levon }
1901f5207b7SJohn Levon 
add_instruction(struct instruction_list ** list,struct instruction * insn)1911f5207b7SJohn Levon static inline void add_instruction(struct instruction_list **list, struct instruction *insn)
1921f5207b7SJohn Levon {
1931f5207b7SJohn Levon 	add_ptr_list(list, insn);
1941f5207b7SJohn Levon }
1951f5207b7SJohn Levon 
add_multijmp(struct multijmp_list ** list,struct multijmp * multijmp)1961f5207b7SJohn Levon static inline void add_multijmp(struct multijmp_list **list, struct multijmp *multijmp)
1971f5207b7SJohn Levon {
1981f5207b7SJohn Levon 	add_ptr_list(list, multijmp);
1991f5207b7SJohn Levon }
2001f5207b7SJohn Levon 
add_pseudo(struct pseudo_list ** list,pseudo_t pseudo)2011f5207b7SJohn Levon static inline pseudo_t *add_pseudo(struct pseudo_list **list, pseudo_t pseudo)
2021f5207b7SJohn Levon {
2031f5207b7SJohn Levon 	return add_ptr_list(list, pseudo);
2041f5207b7SJohn Levon }
2051f5207b7SJohn Levon 
remove_pseudo(struct pseudo_list ** list,pseudo_t pseudo)2061f5207b7SJohn Levon static inline int remove_pseudo(struct pseudo_list **list, pseudo_t pseudo)
2071f5207b7SJohn Levon {
2081f5207b7SJohn Levon 	return delete_ptr_list_entry((struct ptr_list **)list, pseudo, 0) != 0;
2091f5207b7SJohn Levon }
2101f5207b7SJohn Levon 
pseudo_in_list(struct pseudo_list * list,pseudo_t pseudo)211*c85f09ccSJohn Levon static inline int pseudo_in_list(struct pseudo_list *list, pseudo_t pseudo)
212*c85f09ccSJohn Levon {
213*c85f09ccSJohn Levon 	return lookup_ptr_list_entry((struct ptr_list *)list, pseudo);
214*c85f09ccSJohn Levon }
215*c85f09ccSJohn Levon 
bb_terminated(struct basic_block * bb)2161f5207b7SJohn Levon static inline int bb_terminated(struct basic_block *bb)
2171f5207b7SJohn Levon {
2181f5207b7SJohn Levon 	struct instruction *insn;
2191f5207b7SJohn Levon 	if (!bb)
2201f5207b7SJohn Levon 		return 0;
2211f5207b7SJohn Levon 	insn = last_instruction(bb->insns);
2221f5207b7SJohn Levon 	return insn && insn->opcode >= OP_TERMINATOR
2231f5207b7SJohn Levon 	            && insn->opcode <= OP_TERMINATOR_END;
2241f5207b7SJohn Levon }
2251f5207b7SJohn Levon 
bb_reachable(struct basic_block * bb)2261f5207b7SJohn Levon static inline int bb_reachable(struct basic_block *bb)
2271f5207b7SJohn Levon {
2281f5207b7SJohn Levon 	return bb != NULL;
2291f5207b7SJohn Levon }
2301f5207b7SJohn Levon 
lookup_bb(struct basic_block_list * list,struct basic_block * bb)231*c85f09ccSJohn Levon static inline int lookup_bb(struct basic_block_list *list, struct basic_block *bb)
2321f5207b7SJohn Levon {
233*c85f09ccSJohn Levon 	return lookup_ptr_list_entry((struct ptr_list *)list, bb);
2341f5207b7SJohn Levon }
2351f5207b7SJohn Levon 
236*c85f09ccSJohn Levon 
add_pseudo_user_ptr(struct pseudo_user * user,struct pseudo_user_list ** list)2371f5207b7SJohn Levon static inline void add_pseudo_user_ptr(struct pseudo_user *user, struct pseudo_user_list **list)
2381f5207b7SJohn Levon {
2391f5207b7SJohn Levon 	add_ptr_list(list, user);
2401f5207b7SJohn Levon }
2411f5207b7SJohn Levon 
has_use_list(pseudo_t p)2421f5207b7SJohn Levon static inline int has_use_list(pseudo_t p)
2431f5207b7SJohn Levon {
244*c85f09ccSJohn Levon 	return (p && p->type != PSEUDO_VOID && p->type != PSEUDO_UNDEF && p->type != PSEUDO_VAL);
245*c85f09ccSJohn Levon }
246*c85f09ccSJohn Levon 
pseudo_user_list_size(struct pseudo_user_list * list)247*c85f09ccSJohn Levon static inline int pseudo_user_list_size(struct pseudo_user_list *list)
248*c85f09ccSJohn Levon {
249*c85f09ccSJohn Levon 	return ptr_list_size((struct ptr_list *)list);
250*c85f09ccSJohn Levon }
251*c85f09ccSJohn Levon 
pseudo_user_list_empty(struct pseudo_user_list * list)252*c85f09ccSJohn Levon static inline bool pseudo_user_list_empty(struct pseudo_user_list *list)
253*c85f09ccSJohn Levon {
254*c85f09ccSJohn Levon 	return ptr_list_empty((struct ptr_list *)list);
255*c85f09ccSJohn Levon }
256*c85f09ccSJohn Levon 
has_users(pseudo_t p)257*c85f09ccSJohn Levon static inline int has_users(pseudo_t p)
258*c85f09ccSJohn Levon {
259*c85f09ccSJohn Levon 	return !pseudo_user_list_empty(p->users);
260*c85f09ccSJohn Levon }
261*c85f09ccSJohn Levon 
multi_users(pseudo_t p)262*c85f09ccSJohn Levon static inline bool multi_users(pseudo_t p)
263*c85f09ccSJohn Levon {
264*c85f09ccSJohn Levon 	return ptr_list_multiple((struct ptr_list *)(p->users));
265*c85f09ccSJohn Levon }
266*c85f09ccSJohn Levon 
nbr_users(pseudo_t p)267*c85f09ccSJohn Levon static inline int nbr_users(pseudo_t p)
268*c85f09ccSJohn Levon {
269*c85f09ccSJohn Levon 	return pseudo_user_list_size(p->users);
2701f5207b7SJohn Levon }
2711f5207b7SJohn Levon 
alloc_pseudo_user(struct instruction * insn,pseudo_t * pp)2721f5207b7SJohn Levon static inline struct pseudo_user *alloc_pseudo_user(struct instruction *insn, pseudo_t *pp)
2731f5207b7SJohn Levon {
2741f5207b7SJohn Levon 	struct pseudo_user *user = __alloc_pseudo_user(0);
2751f5207b7SJohn Levon 	user->userp = pp;
2761f5207b7SJohn Levon 	user->insn = insn;
2771f5207b7SJohn Levon 	return user;
2781f5207b7SJohn Levon }
2791f5207b7SJohn Levon 
use_pseudo(struct instruction * insn,pseudo_t p,pseudo_t * pp)2801f5207b7SJohn Levon static inline void use_pseudo(struct instruction *insn, pseudo_t p, pseudo_t *pp)
2811f5207b7SJohn Levon {
2821f5207b7SJohn Levon 	*pp = p;
2831f5207b7SJohn Levon 	if (has_use_list(p))
2841f5207b7SJohn Levon 		add_pseudo_user_ptr(alloc_pseudo_user(insn, pp), &p->users);
2851f5207b7SJohn Levon }
2861f5207b7SJohn Levon 
remove_bb_from_list(struct basic_block_list ** list,struct basic_block * entry,int count)2871f5207b7SJohn Levon static inline void remove_bb_from_list(struct basic_block_list **list, struct basic_block *entry, int count)
2881f5207b7SJohn Levon {
2891f5207b7SJohn Levon 	delete_ptr_list_entry((struct ptr_list **)list, entry, count);
2901f5207b7SJohn Levon }
2911f5207b7SJohn Levon 
replace_bb_in_list(struct basic_block_list ** list,struct basic_block * old,struct basic_block * new,int count)2921f5207b7SJohn Levon static inline void replace_bb_in_list(struct basic_block_list **list,
2931f5207b7SJohn Levon 	struct basic_block *old, struct basic_block *new, int count)
2941f5207b7SJohn Levon {
2951f5207b7SJohn Levon 	replace_ptr_list_entry((struct ptr_list **)list, old, new, count);
2961f5207b7SJohn Levon }
2971f5207b7SJohn Levon 
2981f5207b7SJohn Levon struct entrypoint {
2991f5207b7SJohn Levon 	struct symbol *name;
3001f5207b7SJohn Levon 	struct symbol_list *syms;
3011f5207b7SJohn Levon 	struct pseudo_list *accesses;
3021f5207b7SJohn Levon 	struct basic_block_list *bbs;
3031f5207b7SJohn Levon 	struct basic_block *active;
3041f5207b7SJohn Levon 	struct instruction *entry;
305*c85f09ccSJohn Levon 	unsigned int dom_levels;	/* max levels in the dom tree */
3061f5207b7SJohn Levon };
3071f5207b7SJohn Levon 
3081f5207b7SJohn Levon extern void insert_select(struct basic_block *bb, struct instruction *br, struct instruction *phi, pseudo_t if_true, pseudo_t if_false);
3091f5207b7SJohn Levon extern void insert_branch(struct basic_block *bb, struct instruction *br, struct basic_block *target);
3101f5207b7SJohn Levon 
311*c85f09ccSJohn Levon struct instruction *alloc_phisrc(pseudo_t pseudo, struct symbol *type);
312*c85f09ccSJohn Levon struct instruction *alloc_phi_node(struct basic_block *bb, struct symbol *type, struct ident *ident);
313*c85f09ccSJohn Levon struct instruction *insert_phi_node(struct basic_block *bb, struct symbol *var);
314*c85f09ccSJohn Levon void add_phi_node(struct basic_block *bb, struct instruction *phi_node);
315*c85f09ccSJohn Levon 
316*c85f09ccSJohn Levon pseudo_t alloc_phi(struct basic_block *source, pseudo_t pseudo, struct symbol *type);
3171f5207b7SJohn Levon pseudo_t alloc_pseudo(struct instruction *def);
318*c85f09ccSJohn Levon pseudo_t value_pseudo(long long val);
319*c85f09ccSJohn Levon pseudo_t undef_pseudo(void);
3201f5207b7SJohn Levon 
3211f5207b7SJohn Levon struct entrypoint *linearize_symbol(struct symbol *sym);
3221f5207b7SJohn Levon int unssa(struct entrypoint *ep);
3231f5207b7SJohn Levon void show_entry(struct entrypoint *ep);
3241f5207b7SJohn Levon const char *show_pseudo(pseudo_t pseudo);
3251f5207b7SJohn Levon void show_bb(struct basic_block *bb);
3261f5207b7SJohn Levon const char *show_instruction(struct instruction *insn);
327*c85f09ccSJohn Levon const char *show_label(struct basic_block *bb);
3281f5207b7SJohn Levon 
3291f5207b7SJohn Levon #endif /* LINEARIZE_H */
3301f5207b7SJohn Levon