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
37 static inline int nbr_pseudo_users(pseudo_t p)
38 {
39 return ptr_list_size((struct ptr_list *)p->users);
40 }
41
42 static int simplify_phi_node(struct instruction *phi, pseudo_t tmp)
43 {
44 pseudo_t target = phi->target;
45 struct pseudo_user *pu;
46 pseudo_t src;
47
48 // verify if this phi can be simplified
49 FOR_EACH_PTR(phi->phi_list, src) {
50 struct instruction *def = src->def;
51
52 if (!def)
53 continue;
54 if (def->bb == phi->bb)
55 return 0;
56 } END_FOR_EACH_PTR(src);
57
58 // no need to make a copy of this one
59 // -> replace the target pseudo by the tmp
60 FOR_EACH_PTR(target->users, pu) {
61 use_pseudo(pu->insn, tmp, pu->userp);
78 // can we avoid to make of copy?
79 simplify_phi_node(phi, tmp);
80
81 // rewrite all it's phi_src to copy to a new tmp
82 FOR_EACH_PTR(phi->phi_list, p) {
83 struct instruction *def = p->def;
84 pseudo_t src;
85
86 if (p == VOID)
87 continue;
88
89 assert(def->opcode == OP_PHISOURCE);
90
91 def->opcode = OP_COPY;
92 def->target = tmp;
93
94 // can we eliminate the copy?
95 src = def->phi_src;
96 if (src->type != PSEUDO_REG)
97 continue;
98 switch (nbr_pseudo_users(src)) {
99 struct instruction *insn;
100 case 1:
101 insn = src->def;
102 if (!insn)
103 break;
104 insn->target = tmp;
105 case 0:
106 kill_instruction(def);
107 def->bb = NULL;
108 }
109 } END_FOR_EACH_PTR(p);
110
111 if (!phi->bb)
112 return;
113
114 // rewrite the phi node:
115 // phi %rt, ...
116 // to:
117 // copy %rt, %tmp
118 phi->opcode = OP_COPY;
|
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
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);
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;
|