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