ssa.c

// SPDX-License-Identifier: MIT
//
// SSA conversion
// Copyright (C) 2005 Luc Van Oostenryck
//

#include <assert.h>
#include "ssa.h"
#include "lib.h"
#include "sset.h"
#include "dominate.h"
#include "flowgraph.h"
#include "linearize.h"
#include "flow.h"			// for convert_load_instruction()


// Is it possible and desirable for this to be promoted to a pseudo?
static inline bool is_promotable(struct symbol *type)
{
	struct symbol *member;
	int bf_seen;
	int nbr;

	if (type->type == SYM_NODE)
		type = type->ctype.base_type;
	switch (type->type) {
	case SYM_ENUM:
	case SYM_BITFIELD:
	case SYM_PTR:
	case SYM_RESTRICT:	// OK, always integer types
		return 1;
	case SYM_STRUCT:
		// we allow a single scalar field
		// but a run of bitfields count for 1
		nbr = 0;
		bf_seen = 0;
		FOR_EACH_PTR(type->symbol_list, member) {
			if (is_bitfield_type(member)) {
				if (bf_seen)
					continue;
				bf_seen = 1;
			} else {
				bf_seen = 0;
			}
			if (!is_scalar_type(member))
				return 0;
			if (nbr++)
				return 0;
		} END_FOR_EACH_PTR(member);
		if (bf_seen && (type->bit_size > long_ctype.bit_size))
			return 0;
		return 1;
	case SYM_UNION:
		// FIXME: should be like struct but has problem
		//        when used with/for type cohercion
		// -----> OK if only same sized integral types
		FOR_EACH_PTR(type->symbol_list, member) {
			if (member->bit_size != type->bit_size)
				return 0;
			if (!is_integral_type(member))
				return 0;
		} END_FOR_EACH_PTR(member);
		return 1;
	default:
		break;
	}
	if (type->ctype.base_type == &int_type)
		return 1;
	if (type->ctype.base_type == &fp_type)
		return 1;
	return 0;
}

static bool insn_before(struct instruction *a, struct instruction *b)
{
	struct basic_block *bb = a->bb;
	struct instruction *insn;

	assert(b->bb == bb);
	FOR_EACH_PTR(bb->insns, insn) {
		if (insn == a)
			return true;
		if (insn == b)
			return false;
	} END_FOR_EACH_PTR(insn);
	assert(0);
}

static void kill_store(struct instruction *insn)
{
	remove_use(&insn->src);
	remove_use(&insn->target);
	insn->bb = NULL;
}

static void rewrite_local_var(struct basic_block *bb, pseudo_t addr, int nbr_stores, int nbr_uses)
{
	struct instruction *insn;
	pseudo_t val = NULL;

	if (!bb)
		return;

	FOR_EACH_PTR(bb->insns, insn) {

		if (!insn->bb || insn->src != addr)
			continue;
		switch (insn->opcode) {
		case OP_LOAD:
			if (!val)
				val = undef_pseudo();
			convert_load_instruction(insn, val);
			break;
		case OP_STORE:
			val = insn->target;
			// can't use kill_instruction() unless
			// we add a fake user to val
			kill_store(insn);
			break;
		}
	} END_FOR_EACH_PTR(insn);
}

static bool rewrite_single_store(struct instruction *store)
{
	pseudo_t addr = store->src;
	struct pseudo_user *pu;

	FOR_EACH_PTR(addr->users, pu) {
		struct instruction *insn = pu->insn;

		if (insn->opcode != OP_LOAD)
			continue;

		// Let's try to replace the value of the load
		// by the value from the store. This is only valid
		// if the store dominate the load.

		if (insn->bb == store->bb) {
			// the load and the store are in the same BB
			// we can convert if the load is after the store.
			if (!insn_before(store, insn))
				continue;
		} else if (!domtree_dominates(store->bb, insn->bb)) {
			// we can't convert this load
			continue;
		}

		// OK, we can rewrite this load

		// undefs ?

		convert_load_instruction(insn, store->target);
	} END_FOR_EACH_PTR(pu);

	// is there some unconverted loads?
	if (pseudo_user_list_size(addr->users) > 1)
		return false;

	kill_store(store);
	return true;
}

static struct sset *processed;

// we would like to know:
// is there one or more stores?
// are all loads & stores local/done in a single block?
static void ssa_convert_one_var(struct entrypoint *ep, struct symbol *var)
{
	struct basic_block_list *alpha = NULL;
	struct basic_block_list *idf = NULL;
	struct basic_block *samebb = NULL;
	struct instruction *store = NULL;
	struct basic_block *bb;
	struct pseudo_user *pu;
	unsigned long mod = var->ctype.modifiers;
	bool local = true;
	int nbr_stores = 0;
	int nbr_uses   = 0;
	pseudo_t addr;

	/* Never used as a symbol? */
	addr = var->pseudo;
	if (!addr)
		return;

	/* We don't do coverage analysis of volatiles.. */
	if (mod & MOD_VOLATILE)
		return;

	/* ..and symbols with external visibility need more care */
	mod &= (MOD_NONLOCAL | MOD_STATIC | MOD_ADDRESSABLE);
	if (mod)
		goto external_visibility;

	if (!is_promotable(var))
		return;

	// 1) insert in the worklist all BBs that may modify var
	sset_reset(processed);
	FOR_EACH_PTR(addr->users, pu) {
		struct instruction *insn = pu->insn;
		struct basic_block *bb = insn->bb;

		switch (insn->opcode) {
		case OP_STORE:
			nbr_stores++;
			store = insn;
			if (!sset_testset(processed, bb->nr))
				add_bb(&alpha, bb);
			/* fall through */
		case OP_LOAD:
			if (local) {
				if (!samebb)
					samebb = bb;
				else if (samebb != bb)
					local = false;
			}
			nbr_uses++;
			break;
		case OP_SYMADDR:
			mod |= MOD_ADDRESSABLE;
			goto external_visibility;
		default:
			warning(var->pos, "symbol '%s' pseudo used in unexpected way",
				show_ident(var->ident));
		}
	} END_FOR_EACH_PTR(pu);

	if (nbr_stores == 1) {
		if (rewrite_single_store(store))
			return;
	}

	// if all uses are local to a single block
	// they can easily be rewritten and doesn't need phi-nodes
	// FIXME: could be done for extended BB too
	if (local) {
		rewrite_local_var(samebb, addr, nbr_stores, nbr_uses);
		return;
	}

	idf_compute(ep, &idf, alpha);
	FOR_EACH_PTR(idf, bb) {
		struct instruction *node = insert_phi_node(bb, var);
		node->phi_var = var->pseudo;
	} END_FOR_EACH_PTR(bb);
	var->torename = 1;

external_visibility:
	if (mod & (MOD_NONLOCAL | MOD_STATIC))
		return;
	kill_dead_stores(ep, addr, !mod);
}

static pseudo_t lookup_var(struct basic_block *bb, struct symbol *var)
{
	do {
		pseudo_t val = phi_map_lookup(bb->phi_map, var);
		if (val)
			return val;
	} while ((bb = bb->idom));
	return undef_pseudo();
}

static struct instruction_list *phis_all;
static struct instruction_list *phis_used;

static void ssa_rename_insn(struct basic_block *bb, struct instruction *insn)
{
	struct symbol *var;
	pseudo_t addr;
	pseudo_t val;

	switch (insn->opcode) {
	case OP_STORE:
		addr = insn->src;
		if (addr->type != PSEUDO_SYM)
			break;
		var = addr->sym;
		if (!var || !var->torename)
			break;
		phi_map_update(&bb->phi_map, var, insn->target);
		kill_store(insn);
		break;
	case OP_LOAD:
		addr = insn->src;
		if (addr->type != PSEUDO_SYM)
			break;
		var = addr->sym;
		if (!var || !var->torename)
			break;
		val = lookup_var(bb, var);
		convert_load_instruction(insn, val);
		break;
	case OP_PHI:
		var = insn->type;
		if (!var || !var->torename)
			break;
		phi_map_update(&bb->phi_map, var, insn->target);
		add_instruction(&phis_all, insn);
		break;
	}
}

static void ssa_rename_insns(struct entrypoint *ep)
{
	struct basic_block *bb;

	FOR_EACH_PTR(ep->bbs, bb) {
		struct instruction *insn;
		FOR_EACH_PTR(bb->insns, insn) {
			if (!insn->bb)
				continue;
			ssa_rename_insn(bb, insn);
		} END_FOR_EACH_PTR(insn);
	} END_FOR_EACH_PTR(bb);
}

static void mark_phi_used(pseudo_t val)
{
	struct instruction *node;

	if (val->type != PSEUDO_REG)
		return;
	node = val->def;
	if (node->opcode != OP_PHI)
		return;
	if (node->used)
		return;
	node->used = 1;
	add_instruction(&phis_used, node);
}

static void ssa_rename_phi(struct instruction *insn)
{
	struct basic_block *par;
	struct symbol *var;

	if (!insn->phi_var)
		return;
	var = insn->phi_var->sym;
	if (!var->torename)
		return;
	FOR_EACH_PTR(insn->bb->parents, par) {
		struct instruction *term = delete_last_instruction(&par->insns);
		pseudo_t val = lookup_var(par, var);
		pseudo_t phi = alloc_phi(par, val, var);
		phi->ident = var->ident;
		add_instruction(&par->insns, term);
		use_pseudo(insn, phi, add_pseudo(&insn->phi_list, phi));
		mark_phi_used(val);
	} END_FOR_EACH_PTR(par);
}

static void ssa_rename_phis(struct entrypoint *ep)
{
	struct instruction *phi;

	phis_used = NULL;
	FOR_EACH_PTR(phis_all, phi) {
		if (has_users(phi->target)) {
			phi->used = 1;
			add_instruction(&phis_used, phi);
		}
	} END_FOR_EACH_PTR(phi);

	FOR_EACH_PTR(phis_used, phi) {
		if (!phi->bb)
			continue;
		ssa_rename_phi(phi);
	} END_FOR_EACH_PTR(phi);
}

void ssa_convert(struct entrypoint *ep)
{
	struct basic_block *bb;
	pseudo_t pseudo;
	int first, last;

	// calculate the number of BBs
	first = ep->entry->bb->nr;
	last = first;
	FOR_EACH_PTR(ep->bbs, bb) {
		int nr = bb->nr;
		if (nr > last)
			last = nr;
	} END_FOR_EACH_PTR(bb);

	processed = sset_init(first, last);

	// try to promote memory accesses to pseudos
	FOR_EACH_PTR(ep->accesses, pseudo) {
		ssa_convert_one_var(ep, pseudo->sym);
	} END_FOR_EACH_PTR(pseudo);

	// rename the converted accesses
	phis_all = phis_used = NULL;
	ssa_rename_insns(ep);
	ssa_rename_phis(ep);
}