path: root/linearize.h

#ifndef LINEARIZE_H
#define LINEARIZE_H

#include "lib.h"
#include "allocate.h"
#include "token.h"
#include "opcode.h"
#include "parse.h"
#include "symbol.h"
#include "ptrmap.h"

struct instruction;

struct pseudo_user {
	struct instruction *insn;
	pseudo_t *userp;
};

DECLARE_ALLOCATOR(pseudo_user);
DECLARE_PTR_LIST(pseudo_user_list, struct pseudo_user);
DECLARE_PTRMAP(phi_map, struct symbol *, struct instruction *);


enum pseudo_type {
	PSEUDO_VOID,
	PSEUDO_UNDEF,
	PSEUDO_PHI,
	PSEUDO_REG,
	PSEUDO_ARG,
	PSEUDO_SYM,
	PSEUDO_VAL,
};

struct pseudo {
	int nr;
	enum pseudo_type type;
	struct pseudo_user_list *users;
	struct ident *ident;
	union {
		struct symbol *sym;
		struct instruction *def;
		long long value;
	};
	void *priv;
};

extern struct pseudo void_pseudo;

#define VOID (&void_pseudo)

static inline bool is_zero(pseudo_t pseudo)
{
	return pseudo->type == PSEUDO_VAL && pseudo->value == 0;
}

static inline bool is_nonzero(pseudo_t pseudo)
{
	return pseudo->type == PSEUDO_VAL && pseudo->value != 0;
}

static inline bool is_positive(pseudo_t pseudo, unsigned size)
{
	return pseudo->type == PSEUDO_VAL && !(pseudo->value & sign_bit(size));
}


struct multijmp {
	struct basic_block *target;
	long long begin, end;
};

struct asm_constraint {
	pseudo_t pseudo;
	const char *constraint;
	const struct ident *ident;
	unsigned int is_memory:1;
};

DECLARE_ALLOCATOR(asm_constraint);
DECLARE_PTR_LIST(asm_constraint_list, struct asm_constraint);

struct asm_rules {
	struct asm_constraint_list *inputs;
	struct asm_constraint_list *outputs;
	struct asm_constraint_list *clobbers;
};

DECLARE_ALLOCATOR(asm_rules);

struct instruction {
	unsigned opcode:7,
		 tainted:1,
		 size:24;
	struct basic_block *bb;
	struct position pos;
	struct symbol *type;
	pseudo_t target;
	union {
		struct /* entrypoint */ {
			struct pseudo_list *arg_list;
		};
		struct /* branch */ {
			pseudo_t cond;
			struct basic_block *bb_true, *bb_false;
		};
		struct /* switch */ {
			pseudo_t _cond;
			struct multijmp_list *multijmp_list;
		};
		struct /* phi_node */ {
			pseudo_t phi_var;		// used for SSA conversion
			struct pseudo_list *phi_list;
			unsigned int used:1;
		};
		struct /* phi source */ {
			pseudo_t phi_src;
			struct instruction *phi_node;
		};
		struct /* unops */ {
			pseudo_t src;
			unsigned from;			/* slice */
			struct symbol *orig_type;	/* casts */
		};
		struct /* memops */ {
			pseudo_t addr;			/* alias .src */
			long long offset;
			unsigned int is_volatile:1;
		};
		struct /* binops and sel */ {
			pseudo_t src1, src2, src3;
		};
		struct /* compare */ {
			pseudo_t _src1, _src2;		// alias .src[12]
			struct symbol *itype;		// input operands' type
		};
		struct /* setval */ {
			struct expression *val;
		};
		struct /* setfval */ {
			long double fvalue;
		};
		struct /* call */ {
			pseudo_t func;
			struct pseudo_list *arguments;
			struct symbol_list *fntypes;
		};
		struct /* context */ {
			int increment;
			int check;
			struct expression *context_expr;
		};
		struct /* asm */ {
			const char *string;
			struct asm_rules *asm_rules;
			unsigned int clobber_memory:1;
			unsigned int output_memory:1;
		};
	};
};

struct basic_block_list;
struct instruction_list;

struct basic_block {
	struct position pos;
	unsigned long generation;
	struct entrypoint *ep;
	struct basic_block_list *parents; /* sources */
	struct basic_block_list *children; /* destinations */
	struct instruction_list *insns;	/* Linear list of instructions */
	struct basic_block *idom;	/* link to the immediate dominator */
	unsigned int nr;		/* unique id for label's names */
	int dom_level;			/* level in the dominance tree */
	struct basic_block_list *doms;	/* list of BB idominated by this one */
	struct pseudo_list *needs, *defines;
	union {
		struct phi_map *phi_map;/* needed during SSA conversion */
		int postorder_nr;	/* postorder number */
		int context;		/* needed during context checking */
		void *priv;
	};
};


//
// return the opcode of the instruction defining ``SRC`` if existing
// and OP_BADOP if not. It also assigns the defining instruction
// to ``DEF``.
#define DEF_OPCODE(DEF, SRC)	\
	(((SRC)->type == PSEUDO_REG && (DEF = (SRC)->def)) ? DEF->opcode : OP_BADOP)


static inline void add_bb(struct basic_block_list **list, struct basic_block *bb)
{
	add_ptr_list(list, bb);
}

static inline void add_instruction(struct instruction_list **list, struct instruction *insn)
{
	add_ptr_list(list, insn);
}

static inline void insert_last_instruction(struct basic_block *bb, struct instruction *insn)
{
	struct instruction *last = delete_last_instruction(&bb->insns);
	add_instruction(&bb->insns, insn);
	add_instruction(&bb->insns, last);
	insn->bb = bb;
}

static inline void add_multijmp(struct multijmp_list **list, struct multijmp *multijmp)
{
	add_ptr_list(list, multijmp);
}

static inline pseudo_t *add_pseudo(struct pseudo_list **list, pseudo_t pseudo)
{
	return add_ptr_list(list, pseudo);
}

static inline int remove_pseudo(struct pseudo_list **list, pseudo_t pseudo)
{
	return delete_ptr_list_entry((struct ptr_list **)list, pseudo, 0) != 0;
}

static inline int pseudo_in_list(struct pseudo_list *list, pseudo_t pseudo)
{
	return lookup_ptr_list_entry((struct ptr_list *)list, pseudo);
}

static inline int bb_terminated(struct basic_block *bb)
{
	struct instruction *insn;
	if (!bb)
		return 0;
	insn = last_instruction(bb->insns);
	return insn && insn->opcode >= OP_TERMINATOR
	            && insn->opcode <= OP_TERMINATOR_END;
}

static inline int bb_reachable(struct basic_block *bb)
{
	return bb != NULL;
}

static inline int lookup_bb(struct basic_block_list *list, struct basic_block *bb)
{
	return lookup_ptr_list_entry((struct ptr_list *)list, bb);
}


static inline void add_pseudo_user_ptr(struct pseudo_user *user, struct pseudo_user_list **list)
{
	add_ptr_list(list, user);
}

static inline int has_use_list(pseudo_t p)
{
	return (p && p->type != PSEUDO_VOID && p->type != PSEUDO_UNDEF && p->type != PSEUDO_VAL);
}

static inline bool has_definition(pseudo_t p)
{
	return p->type == PSEUDO_REG || p->type == PSEUDO_PHI;
}

static inline int pseudo_user_list_size(struct pseudo_user_list *list)
{
	return ptr_list_size((struct ptr_list *)list);
}

static inline bool pseudo_user_list_empty(struct pseudo_user_list *list)
{
	return ptr_list_empty((struct ptr_list *)list);
}

static inline int has_users(pseudo_t p)
{
	return !pseudo_user_list_empty(p->users);
}

static inline bool one_use(pseudo_t p)
{
	return !ptr_list_multiple((struct ptr_list *)(p->users));
}

static inline int nbr_users(pseudo_t p)
{
	return pseudo_user_list_size(p->users);
}

static inline struct pseudo_user *alloc_pseudo_user(struct instruction *insn, pseudo_t *pp)
{
	struct pseudo_user *user = __alloc_pseudo_user(0);
	user->userp = pp;
	user->insn = insn;
	return user;
}

static inline void use_pseudo(struct instruction *insn, pseudo_t p, pseudo_t *pp)
{
	*pp = p;
	if (has_use_list(p))
		add_pseudo_user_ptr(alloc_pseudo_user(insn, pp), &p->users);
}

static inline void link_phi(struct instruction *node, pseudo_t phi)
{
	use_pseudo(node, phi, add_pseudo(&node->phi_list, phi));
	phi->def->phi_node = node;
}

static inline void remove_bb_from_list(struct basic_block_list **list, struct basic_block *entry, int count)
{
	delete_ptr_list_entry((struct ptr_list **)list, entry, count);
}

static inline void replace_bb_in_list(struct basic_block_list **list,
	struct basic_block *old, struct basic_block *new, int count)
{
	replace_ptr_list_entry((struct ptr_list **)list, old, new, count);
}

struct entrypoint {
	struct symbol *name;
	struct symbol_list *syms;
	struct pseudo_list *accesses;
	struct basic_block_list *bbs;
	struct basic_block *active;
	struct instruction *entry;
	unsigned int dom_levels;	/* max levels in the dom tree */
};

extern void insert_select(struct basic_block *bb, struct instruction *br, struct instruction *phi, pseudo_t if_true, pseudo_t if_false);

struct instruction *alloc_phisrc(pseudo_t pseudo, struct symbol *type);
struct instruction *alloc_phi_node(struct basic_block *bb, struct symbol *type, struct ident *ident);
struct instruction *insert_phi_node(struct basic_block *bb, struct symbol *var);
void add_phi_node(struct basic_block *bb, struct instruction *phi_node);

pseudo_t alloc_phi(struct basic_block *source, pseudo_t pseudo, struct symbol *type);
pseudo_t alloc_pseudo(struct instruction *def);
pseudo_t value_pseudo(long long val);
pseudo_t undef_pseudo(void);

struct entrypoint *linearize_symbol(struct symbol *sym);
int unssa(struct entrypoint *ep);
void show_entry(struct entrypoint *ep);
void show_insn_entry(struct instruction *insn);
const char *show_pseudo(pseudo_t pseudo);
void show_bb(struct basic_block *bb);
void show_insn_bb(struct instruction *insn);
const char *show_instruction(struct instruction *insn);
const char *show_label(struct basic_block *bb);

#endif /* LINEARIZE_H */