blob: cd183132f02bd2cc8499694c41ff4d571dfbedcf [file] [log] [blame]
/*
* 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 <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);
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;
}