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
331