11f5207b7SJohn Levon /*
21f5207b7SJohn Levon * UnSSA - translate the SSA back to normal form.
31f5207b7SJohn Levon *
41f5207b7SJohn Levon * For now it's done by replacing to set of copies:
51f5207b7SJohn Levon * 1) For each phi-node, replace all their phisrc by copies to a common
61f5207b7SJohn Levon * temporary.
71f5207b7SJohn Levon * 2) Replace all the phi-nodes by copies of the temporaries to the phi-node target.
81f5207b7SJohn Levon * This is node to preserve the semantic of the phi-node (they should all "execute"
91f5207b7SJohn Levon * simultaneously on entry in the basic block in which they belong).
101f5207b7SJohn Levon *
111f5207b7SJohn Levon * This is similar to the "Sreedhar method I" except that the copies to the
121f5207b7SJohn Levon * temporaries are not placed at the end of the predecessor basic blocks, but
131f5207b7SJohn Levon * at the place where the phi-node operands are defined.
141f5207b7SJohn Levon * This is particulary easy since these copies are essentialy already present
151f5207b7SJohn Levon * as the corresponding OP_PHISOURCE.
161f5207b7SJohn Levon *
171f5207b7SJohn Levon * While very simple this method create a lot more copies that really necessary.
181f5207b7SJohn Levon * We eliminate some of these copies but most probably most of them are still
191f5207b7SJohn Levon * useless.
201f5207b7SJohn Levon * Ideally, "Sreedhar method III" should be used:
211f5207b7SJohn Levon * "Translating Out of Static Single Assignment Form", V. C. Sreedhar, R. D.-C. Ju,
221f5207b7SJohn Levon * D. M. Gillies and V. Santhanam. SAS'99, Vol. 1694 of Lecture Notes in Computer
231f5207b7SJohn Levon * Science, Springer-Verlag, pp. 194-210, 1999.
241f5207b7SJohn Levon * But for this we need precise liveness, on each %phi and not only on OP_PHI's
251f5207b7SJohn Levon * target pseudos.
261f5207b7SJohn Levon *
271f5207b7SJohn Levon * Copyright (C) 2005 Luc Van Oostenryck
281f5207b7SJohn Levon */
291f5207b7SJohn Levon
301f5207b7SJohn Levon #include "lib.h"
311f5207b7SJohn Levon #include "linearize.h"
321f5207b7SJohn Levon #include "allocate.h"
331f5207b7SJohn Levon #include "flow.h"
341f5207b7SJohn Levon #include <assert.h>
351f5207b7SJohn Levon
361f5207b7SJohn Levon
simplify_phi_node(struct instruction * phi,pseudo_t tmp)371f5207b7SJohn Levon static int simplify_phi_node(struct instruction *phi, pseudo_t tmp)
381f5207b7SJohn Levon {
391f5207b7SJohn Levon pseudo_t target = phi->target;
401f5207b7SJohn Levon struct pseudo_user *pu;
411f5207b7SJohn Levon pseudo_t src;
421f5207b7SJohn Levon
431f5207b7SJohn Levon // verify if this phi can be simplified
441f5207b7SJohn Levon FOR_EACH_PTR(phi->phi_list, src) {
451f5207b7SJohn Levon struct instruction *def = src->def;
461f5207b7SJohn Levon
471f5207b7SJohn Levon if (!def)
481f5207b7SJohn Levon continue;
491f5207b7SJohn Levon if (def->bb == phi->bb)
501f5207b7SJohn Levon return 0;
511f5207b7SJohn Levon } END_FOR_EACH_PTR(src);
521f5207b7SJohn Levon
531f5207b7SJohn Levon // no need to make a copy of this one
541f5207b7SJohn Levon // -> replace the target pseudo by the tmp
551f5207b7SJohn Levon FOR_EACH_PTR(target->users, pu) {
561f5207b7SJohn Levon use_pseudo(pu->insn, tmp, pu->userp);
571f5207b7SJohn Levon } END_FOR_EACH_PTR(pu);
581f5207b7SJohn Levon
591f5207b7SJohn Levon phi->bb = NULL;
601f5207b7SJohn Levon return 1;
611f5207b7SJohn Levon }
621f5207b7SJohn Levon
replace_phi_node(struct instruction * phi)631f5207b7SJohn Levon static void replace_phi_node(struct instruction *phi)
641f5207b7SJohn Levon {
651f5207b7SJohn Levon pseudo_t tmp;
661f5207b7SJohn Levon pseudo_t p;
671f5207b7SJohn Levon
681f5207b7SJohn Levon tmp = alloc_pseudo(NULL);
691f5207b7SJohn Levon tmp->type = phi->target->type;
701f5207b7SJohn Levon tmp->ident = phi->target->ident;
711f5207b7SJohn Levon tmp->def = NULL; // defined by all the phisrc
721f5207b7SJohn Levon
731f5207b7SJohn Levon // can we avoid to make of copy?
741f5207b7SJohn Levon simplify_phi_node(phi, tmp);
751f5207b7SJohn Levon
761f5207b7SJohn Levon // rewrite all it's phi_src to copy to a new tmp
771f5207b7SJohn Levon FOR_EACH_PTR(phi->phi_list, p) {
781f5207b7SJohn Levon struct instruction *def = p->def;
791f5207b7SJohn Levon pseudo_t src;
801f5207b7SJohn Levon
811f5207b7SJohn Levon if (p == VOID)
821f5207b7SJohn Levon continue;
831f5207b7SJohn Levon
841f5207b7SJohn Levon assert(def->opcode == OP_PHISOURCE);
851f5207b7SJohn Levon
861f5207b7SJohn Levon def->opcode = OP_COPY;
871f5207b7SJohn Levon def->target = tmp;
881f5207b7SJohn Levon
891f5207b7SJohn Levon // can we eliminate the copy?
901f5207b7SJohn Levon src = def->phi_src;
911f5207b7SJohn Levon if (src->type != PSEUDO_REG)
921f5207b7SJohn Levon continue;
93*c85f09ccSJohn Levon switch (nbr_users(src)) {
941f5207b7SJohn Levon struct instruction *insn;
951f5207b7SJohn Levon case 1:
961f5207b7SJohn Levon insn = src->def;
971f5207b7SJohn Levon if (!insn)
981f5207b7SJohn Levon break;
991f5207b7SJohn Levon insn->target = tmp;
1001f5207b7SJohn Levon case 0:
1011f5207b7SJohn Levon kill_instruction(def);
1021f5207b7SJohn Levon def->bb = NULL;
1031f5207b7SJohn Levon }
1041f5207b7SJohn Levon } END_FOR_EACH_PTR(p);
1051f5207b7SJohn Levon
1061f5207b7SJohn Levon if (!phi->bb)
1071f5207b7SJohn Levon return;
1081f5207b7SJohn Levon
1091f5207b7SJohn Levon // rewrite the phi node:
1101f5207b7SJohn Levon // phi %rt, ...
1111f5207b7SJohn Levon // to:
1121f5207b7SJohn Levon // copy %rt, %tmp
1131f5207b7SJohn Levon phi->opcode = OP_COPY;
1141f5207b7SJohn Levon use_pseudo(phi, tmp, &phi->src);
1151f5207b7SJohn Levon }
1161f5207b7SJohn Levon
rewrite_phi_bb(struct basic_block * bb)1171f5207b7SJohn Levon static void rewrite_phi_bb(struct basic_block *bb)
1181f5207b7SJohn Levon {
1191f5207b7SJohn Levon struct instruction *insn;
1201f5207b7SJohn Levon
1211f5207b7SJohn Levon // Replace all the phi-nodes by copies of a temporary
1221f5207b7SJohn Levon // (which represent the set of all the %phi that feed them).
1231f5207b7SJohn Levon // The target pseudo doesn't change.
1241f5207b7SJohn Levon FOR_EACH_PTR(bb->insns, insn) {
1251f5207b7SJohn Levon if (!insn->bb)
1261f5207b7SJohn Levon continue;
1271f5207b7SJohn Levon if (insn->opcode != OP_PHI)
1281f5207b7SJohn Levon continue;
1291f5207b7SJohn Levon replace_phi_node(insn);
1301f5207b7SJohn Levon } END_FOR_EACH_PTR(insn);
1311f5207b7SJohn Levon }
1321f5207b7SJohn Levon
unssa(struct entrypoint * ep)1331f5207b7SJohn Levon int unssa(struct entrypoint *ep)
1341f5207b7SJohn Levon {
1351f5207b7SJohn Levon struct basic_block *bb;
1361f5207b7SJohn Levon
1371f5207b7SJohn Levon FOR_EACH_PTR(ep->bbs, bb) {
1381f5207b7SJohn Levon rewrite_phi_bb(bb);
1391f5207b7SJohn Levon } END_FOR_EACH_PTR(bb);
1401f5207b7SJohn Levon
1411f5207b7SJohn Levon return 0;
1421f5207b7SJohn Levon }
143