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