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
simplify_phi_node(struct instruction * phi,pseudo_t tmp)37 static 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
replace_phi_node(struct instruction * phi)63 static 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
rewrite_phi_bb(struct basic_block * bb)117 static 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
unssa(struct entrypoint * ep)133 int 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