unssa.c

/*
 * UnSSA - translate the SSA back to normal form.
 *
 * For now it's done by replacing to set of copies:
 * 1) For each phi-node, replace all their phisrc by copies to a common
 *    temporary.
 * 2) Replace all the phi-nodes by copies of the temporaries to the phi-node target.
 *    This is node to preserve the semantic of the phi-node (they should all "execute"
 *    simultaneously on entry in the basic block in which they belong).
 *
 * This is similar to the "Sreedhar method I" except that the copies to the
 * temporaries are not placed at the end of the predecessor basic blocks, but
 * at the place where the phi-node operands are defined (the same place where the
 * phisrc were present).
 * Is this a problem? 
 *
 * While very simple this method create a lot more copies that really necessary.
 * Ideally, "Sreedhar method III" should be used:
 * "Translating Out of Static Single Assignment Form", V. C. Sreedhar, R. D.-C. Ju,
 * D. M. Gillies and V. Santhanam.  SAS'99, Vol. 1694 of Lecture Notes in Computer
 * Science, Springer-Verlag, pp. 194-210, 1999.
 *
 * Copyright (C) 2005 Luc Van Oostenryck
 */

#include "lib.h"
#include "linearize.h"
#include "allocate.h"
#include "flow.h"
#include <assert.h>


static void remove_phisrc_defines(struct instruction *phisrc)
{
	struct instruction *phi;
	struct basic_block *bb = phisrc->bb;

	FOR_EACH_PTR(phisrc->phi_users, phi) {
		remove_pseudo(&bb->defines, phi->target);
	} END_FOR_EACH_PTR(phi);
}

static void replace_phi_node(struct instruction *phi)
{
	pseudo_t tmp;

	tmp = alloc_pseudo(NULL);
	tmp->type = phi->target->type;
	tmp->ident = phi->target->ident;
	tmp->def = NULL;		// defined by all the phisrc
	
	// update the current liveness
	remove_pseudo(&phi->bb->needs, phi->target);
	add_pseudo(&phi->bb->needs, tmp);
	track_phi_uses(phi);

	phi->opcode = OP_COPY;
	phi->src = tmp;

	// FIXME: free phi->phi_list;
}

static void rewrite_phi_bb(struct basic_block *bb)
{
	struct instruction *insn;

	// Replace all the phi-nodes by copies of a temporary
	// (which represent the set of all the %phi that feed them).
	// The target pseudo doesn't change.
	FOR_EACH_PTR(bb->insns, insn) {
		if (!insn->bb)
			continue;
		if (insn->opcode != OP_PHI)
			continue;
		replace_phi_node(insn);
	} END_FOR_EACH_PTR(insn);
}

static void rewrite_phisrc_bb(struct basic_block *bb)
{
	struct instruction *insn;

	// Replace all the phisrc by one or several copies to
	// the temporaries associated to each phi-node it defines.
	FOR_EACH_PTR_REVERSE(bb->insns, insn) {
		struct instruction *phi;
		int i;

		if (!insn->bb)
			continue;
		if (insn->opcode != OP_PHISOURCE)
			continue;

		i = 0;
		FOR_EACH_PTR(insn->phi_users, phi) {
			pseudo_t tmp = phi->src;
			pseudo_t src = insn->phi_src;

			if (i == 0) {	// first phi: we overwrite the phisrc
				insn->opcode = OP_COPY;
				insn->target = tmp;
				insn->src = src;
			} else {
				struct instruction *copy = __alloc_instruction(0);

				copy->bb = bb;
				copy->opcode = OP_COPY;
				copy->size = insn->size;
				copy->pos = insn->pos;
				copy->target = tmp;
				copy->src = src;

				INSERT_CURRENT(copy, insn);
			}
			// update the liveness info
			remove_phisrc_defines(insn);
			// FIXME: should really something like add_pseudo_exclusive()
			add_pseudo(&bb->defines, tmp);

			i++;
		} END_FOR_EACH_PTR(phi);

	} END_FOR_EACH_PTR_REVERSE(insn);
}

int unssa(struct entrypoint *ep)
{
	struct basic_block *bb;

	FOR_EACH_PTR(ep->bbs, bb) {
		rewrite_phi_bb(bb);
	} END_FOR_EACH_PTR(bb);

	FOR_EACH_PTR(ep->bbs, bb) {
		rewrite_phisrc_bb(bb);
	} END_FOR_EACH_PTR(bb);

	return 0;
}