1/*
2 * UnSSA - translate the SSA back to normal form.
3 *
4 * For now it's done by replacing to set of copies:
5 * 1) For each phi-node, replace all their phisrc by copies to a common
6 *    temporary.
7 * 2) Replace all the phi-nodes by copies of the temporaries to the phi-node target.
8 *    This is node to preserve the semantic of the phi-node (they should all "execute"
9 *    simultaneously on entry in the basic block in which they belong).
10 *
11 * This is similar to the "Sreedhar method I" except that the copies to the
12 * temporaries are not placed at the end of the predecessor basic blocks, but
13 * at the place where the phi-node operands are defined.
14 * This is particulary easy since these copies are essentialy already present
15 * as the corresponding OP_PHISOURCE.
16 *
17 * While very simple this method create a lot more copies that really necessary.
18 * We eliminate some of these copies but most probably most of them are still
19 * useless.
20 * Ideally, "Sreedhar method III" should be used:
21 * "Translating Out of Static Single Assignment Form", V. C. Sreedhar, R. D.-C. Ju,
22 * D. M. Gillies and V. Santhanam.  SAS'99, Vol. 1694 of Lecture Notes in Computer
23 * Science, Springer-Verlag, pp. 194-210, 1999.
24 * But for this we need precise liveness, on each %phi and not only on OP_PHI's
25 * target pseudos.
26 *
27 * Copyright (C) 2005 Luc Van Oostenryck
28 */
29
30#include "lib.h"
31#include "linearize.h"
32#include "allocate.h"
33#include "flow.h"
34#include <assert.h>
35
36
37static int simplify_phi_node(struct instruction *phi, pseudo_t tmp)
38{
39	pseudo_t target = phi->target;
40	struct pseudo_user *pu;
41	pseudo_t src;
42
43	// verify if this phi can be simplified
44	FOR_EACH_PTR(phi->phi_list, src) {
45		struct instruction *def = src->def;
46
47		if (!def)
48			continue;
49		if (def->bb == phi->bb)
50			return 0;
51	} END_FOR_EACH_PTR(src);
52
53	// no need to make a copy of this one
54	// -> replace the target pseudo by the tmp
55	FOR_EACH_PTR(target->users, pu) {
56		use_pseudo(pu->insn, tmp, pu->userp);
57	} END_FOR_EACH_PTR(pu);
58
59	phi->bb = NULL;
60	return 1;
61}
62
63static void replace_phi_node(struct instruction *phi)
64{
65	pseudo_t tmp;
66	pseudo_t p;
67
68	tmp = alloc_pseudo(NULL);
69	tmp->type = phi->target->type;
70	tmp->ident = phi->target->ident;
71	tmp->def = NULL;		// defined by all the phisrc
72
73	// can we avoid to make of copy?
74	simplify_phi_node(phi, tmp);
75
76	// rewrite all it's phi_src to copy to a new tmp
77	FOR_EACH_PTR(phi->phi_list, p) {
78		struct instruction *def = p->def;
79		pseudo_t src;
80
81		if (p == VOID)
82			continue;
83
84		assert(def->opcode == OP_PHISOURCE);
85
86		def->opcode = OP_COPY;
87		def->target = tmp;
88
89		// can we eliminate the copy?
90		src = def->phi_src;
91		if (src->type != PSEUDO_REG)
92			continue;
93		switch (nbr_users(src)) {
94			struct instruction *insn;
95		case 1:
96			insn = src->def;
97			if (!insn)
98				break;
99			insn->target = tmp;
100		case 0:
101			kill_instruction(def);
102			def->bb = NULL;
103		}
104	} END_FOR_EACH_PTR(p);
105
106	if (!phi->bb)
107		return;
108
109	// rewrite the phi node:
110	//	phi	%rt, ...
111	// to:
112	//	copy	%rt, %tmp
113	phi->opcode = OP_COPY;
114	use_pseudo(phi, tmp, &phi->src);
115}
116
117static void rewrite_phi_bb(struct basic_block *bb)
118{
119	struct instruction *insn;
120
121	// Replace all the phi-nodes by copies of a temporary
122	// (which represent the set of all the %phi that feed them).
123	// The target pseudo doesn't change.
124	FOR_EACH_PTR(bb->insns, insn) {
125		if (!insn->bb)
126			continue;
127		if (insn->opcode != OP_PHI)
128			continue;
129		replace_phi_node(insn);
130	} END_FOR_EACH_PTR(insn);
131}
132
133int unssa(struct entrypoint *ep)
134{
135	struct basic_block *bb;
136
137	FOR_EACH_PTR(ep->bbs, bb) {
138		rewrite_phi_bb(bb);
139	} END_FOR_EACH_PTR(bb);
140
141	return 0;
142}
143