1 /*
2 * Register - track pseudo usage, maybe eventually try to do register
3 * allocation.
4 *
5 * Copyright (C) 2004 Linus Torvalds
6 */
7
8 #include <assert.h>
9
10 #include "parse.h"
11 #include "expression.h"
12 #include "linearize.h"
13 #include "flow.h"
14
15 static void phi_defines(struct instruction * phi_node, pseudo_t target,
16 void (*defines)(struct basic_block *, pseudo_t))
17 {
18 pseudo_t phi;
19 FOR_EACH_PTR(phi_node->phi_list, phi) {
20 struct instruction *def;
21 if (phi == VOID)
22 continue;
23 def = phi->def;
24 if (!def || !def->bb)
25 continue;
26 defines(def->bb, target);
27 } END_FOR_EACH_PTR(phi);
28 }
29
36 FOR_EACH_PTR(insn->asm_rules->inputs, entry) {
37 use(bb, entry->pseudo);
38 } END_FOR_EACH_PTR(entry);
39
40 FOR_EACH_PTR(insn->asm_rules->outputs, entry) {
41 def(bb, entry->pseudo);
42 } END_FOR_EACH_PTR(entry);
43 }
44
45 static void track_instruction_usage(struct basic_block *bb, struct instruction *insn,
46 void (*def)(struct basic_block *, pseudo_t),
47 void (*use)(struct basic_block *, pseudo_t))
48 {
49 pseudo_t pseudo;
50
51 #define USES(x) use(bb, insn->x)
52 #define DEFINES(x) def(bb, insn->x)
53
54 switch (insn->opcode) {
55 case OP_RET:
56 USES(src);
57 break;
58
59 case OP_CBR:
60 case OP_SWITCH:
61 USES(cond);
62 break;
63
64 case OP_COMPUTEDGOTO:
65 USES(target);
66 break;
67
68 /* Binary */
69 case OP_BINARY ... OP_BINARY_END:
70 case OP_BINCMP ... OP_BINCMP_END:
71 USES(src1); USES(src2); DEFINES(target);
72 break;
73
74 /* Uni */
75 case OP_NOT: case OP_NEG:
76 USES(src1); DEFINES(target);
77 break;
78
79 case OP_SEL:
80 USES(src1); USES(src2); USES(src3); DEFINES(target);
81 break;
82
83 /* Memory */
84 case OP_LOAD:
85 USES(src); DEFINES(target);
86 break;
87
88 case OP_STORE:
89 USES(src); USES(target);
90 break;
91
92 case OP_SETVAL:
93 DEFINES(target);
94 break;
95
96 case OP_SYMADDR:
97 USES(symbol); DEFINES(target);
98 break;
99
100 /* Other */
101 case OP_PHI:
102 /* Phi-nodes are "backwards" nodes. Their def doesn't matter */
103 phi_defines(insn, insn->target, def);
104 break;
105
106 case OP_PHISOURCE:
107 /*
108 * We don't care about the phi-source define, they get set
109 * up and expanded by the OP_PHI
110 */
111 USES(phi_src);
112 break;
113
114 case OP_CAST:
115 case OP_SCAST:
116 case OP_FPCAST:
117 case OP_PTRCAST:
118 USES(src); DEFINES(target);
119 break;
120
121 case OP_CALL:
122 USES(func);
123 if (insn->target != VOID)
124 DEFINES(target);
125 FOR_EACH_PTR(insn->arguments, pseudo) {
126 use(bb, pseudo);
127 } END_FOR_EACH_PTR(pseudo);
128 break;
129
130 case OP_SLICE:
131 USES(base); DEFINES(target);
132 break;
133
134 case OP_ASM:
135 asm_liveness(bb, insn, def, use);
136 break;
137
138 case OP_RANGE:
139 USES(src1); USES(src2); USES(src3);
140 break;
141
142 case OP_BADOP:
143 case OP_INVOKE:
144 case OP_UNWIND:
145 case OP_MALLOC:
146 case OP_FREE:
147 case OP_ALLOCA:
148 case OP_GET_ELEMENT_PTR:
149 case OP_VANEXT:
150 case OP_VAARG:
151 case OP_SNOP:
152 case OP_LNOP:
153 case OP_NOP:
154 case OP_CONTEXT:
155 break;
156 }
157 }
158
159 int pseudo_in_list(struct pseudo_list *list, pseudo_t pseudo)
160 {
161 pseudo_t old;
162 FOR_EACH_PTR(list,old) {
163 if (old == pseudo)
164 return 1;
165 } END_FOR_EACH_PTR(old);
166 return 0;
167 }
168
169 static int liveness_changed;
170
171 static void add_pseudo_exclusive(struct pseudo_list **list, pseudo_t pseudo)
172 {
173 if (!pseudo_in_list(*list, pseudo)) {
174 liveness_changed = 1;
175 add_pseudo(list, pseudo);
176 }
177 }
178
179 static inline int trackable_pseudo(pseudo_t pseudo)
180 {
181 return pseudo && (pseudo->type == PSEUDO_REG || pseudo->type == PSEUDO_ARG);
182 }
183
184 static void insn_uses(struct basic_block *bb, pseudo_t pseudo)
185 {
186 if (trackable_pseudo(pseudo)) {
187 struct instruction *def = pseudo->def;
259 FOR_EACH_PTR(bb->children, child) {
260 if (pseudo_in_list(child->needs, def))
261 goto is_used;
262 } END_FOR_EACH_PTR(child);
263 DELETE_CURRENT_PTR(def);
264 is_used:
265 ;
266 } END_FOR_EACH_PTR(def);
267 PACK_PTR_LIST(&bb->defines);
268 } END_FOR_EACH_PTR(bb);
269 }
270
271 static void merge_pseudo_list(struct pseudo_list *src, struct pseudo_list **dest)
272 {
273 pseudo_t pseudo;
274 FOR_EACH_PTR(src, pseudo) {
275 add_pseudo_exclusive(dest, pseudo);
276 } END_FOR_EACH_PTR(pseudo);
277 }
278
279 void track_phi_uses(struct instruction *insn)
280 {
281 pseudo_t phi;
282 FOR_EACH_PTR(insn->phi_list, phi) {
283 struct instruction *def;
284 if (phi == VOID || !phi->def)
285 continue;
286 def = phi->def;
287 assert(def->opcode == OP_PHISOURCE);
288 add_ptr_list(&def->phi_users, insn);
289 } END_FOR_EACH_PTR(phi);
290 }
291
292 static void track_bb_phi_uses(struct basic_block *bb)
293 {
294 struct instruction *insn;
295 FOR_EACH_PTR(bb->insns, insn) {
296 if (insn->bb && insn->opcode == OP_PHI)
297 track_phi_uses(insn);
298 } END_FOR_EACH_PTR(insn);
299 }
|
1 /*
2 * Register - track pseudo usage, maybe eventually try to do register
3 * allocation.
4 *
5 * Copyright (C) 2004 Linus Torvalds
6 */
7
8 #include <assert.h>
9
10 #include "liveness.h"
11 #include "parse.h"
12 #include "expression.h"
13 #include "linearize.h"
14 #include "flow.h"
15
16 static void phi_defines(struct instruction * phi_node, pseudo_t target,
17 void (*defines)(struct basic_block *, pseudo_t))
18 {
19 pseudo_t phi;
20 FOR_EACH_PTR(phi_node->phi_list, phi) {
21 struct instruction *def;
22 if (phi == VOID)
23 continue;
24 def = phi->def;
25 if (!def || !def->bb)
26 continue;
27 defines(def->bb, target);
28 } END_FOR_EACH_PTR(phi);
29 }
30
37 FOR_EACH_PTR(insn->asm_rules->inputs, entry) {
38 use(bb, entry->pseudo);
39 } END_FOR_EACH_PTR(entry);
40
41 FOR_EACH_PTR(insn->asm_rules->outputs, entry) {
42 def(bb, entry->pseudo);
43 } END_FOR_EACH_PTR(entry);
44 }
45
46 static void track_instruction_usage(struct basic_block *bb, struct instruction *insn,
47 void (*def)(struct basic_block *, pseudo_t),
48 void (*use)(struct basic_block *, pseudo_t))
49 {
50 pseudo_t pseudo;
51
52 #define USES(x) use(bb, insn->x)
53 #define DEFINES(x) def(bb, insn->x)
54
55 switch (insn->opcode) {
56 case OP_RET:
57 case OP_COMPUTEDGOTO:
58 USES(src);
59 break;
60
61 case OP_CBR:
62 case OP_SWITCH:
63 USES(cond);
64 break;
65
66 /* Binary */
67 case OP_BINARY ... OP_BINARY_END:
68 case OP_FPCMP ... OP_FPCMP_END:
69 case OP_BINCMP ... OP_BINCMP_END:
70 USES(src1); USES(src2); DEFINES(target);
71 break;
72
73 /* Uni */
74 case OP_UNOP ... OP_UNOP_END:
75 case OP_SYMADDR:
76 USES(src1); DEFINES(target);
77 break;
78
79 case OP_SEL:
80 USES(src1); USES(src2); USES(src3); DEFINES(target);
81 break;
82
83 /* Memory */
84 case OP_LOAD:
85 USES(src); DEFINES(target);
86 break;
87
88 case OP_STORE:
89 USES(src); USES(target);
90 break;
91
92 case OP_SETVAL:
93 case OP_SETFVAL:
94 DEFINES(target);
95 break;
96
97 /* Other */
98 case OP_PHI:
99 /* Phi-nodes are "backwards" nodes. Their def doesn't matter */
100 phi_defines(insn, insn->target, def);
101 break;
102
103 case OP_PHISOURCE:
104 /*
105 * We don't care about the phi-source define, they get set
106 * up and expanded by the OP_PHI
107 */
108 USES(phi_src);
109 break;
110
111 case OP_CALL:
112 USES(func);
113 if (insn->target != VOID)
114 DEFINES(target);
115 FOR_EACH_PTR(insn->arguments, pseudo) {
116 use(bb, pseudo);
117 } END_FOR_EACH_PTR(pseudo);
118 break;
119
120 case OP_SLICE:
121 USES(base); DEFINES(target);
122 break;
123
124 case OP_ASM:
125 asm_liveness(bb, insn, def, use);
126 break;
127
128 case OP_RANGE:
129 USES(src1); USES(src2); USES(src3);
130 break;
131
132 case OP_BADOP:
133 case OP_NOP:
134 case OP_CONTEXT:
135 break;
136 }
137 }
138
139
140 static int liveness_changed;
141
142 static void add_pseudo_exclusive(struct pseudo_list **list, pseudo_t pseudo)
143 {
144 if (!pseudo_in_list(*list, pseudo)) {
145 liveness_changed = 1;
146 add_pseudo(list, pseudo);
147 }
148 }
149
150 static inline int trackable_pseudo(pseudo_t pseudo)
151 {
152 return pseudo && (pseudo->type == PSEUDO_REG || pseudo->type == PSEUDO_ARG);
153 }
154
155 static void insn_uses(struct basic_block *bb, pseudo_t pseudo)
156 {
157 if (trackable_pseudo(pseudo)) {
158 struct instruction *def = pseudo->def;
230 FOR_EACH_PTR(bb->children, child) {
231 if (pseudo_in_list(child->needs, def))
232 goto is_used;
233 } END_FOR_EACH_PTR(child);
234 DELETE_CURRENT_PTR(def);
235 is_used:
236 ;
237 } END_FOR_EACH_PTR(def);
238 PACK_PTR_LIST(&bb->defines);
239 } END_FOR_EACH_PTR(bb);
240 }
241
242 static void merge_pseudo_list(struct pseudo_list *src, struct pseudo_list **dest)
243 {
244 pseudo_t pseudo;
245 FOR_EACH_PTR(src, pseudo) {
246 add_pseudo_exclusive(dest, pseudo);
247 } END_FOR_EACH_PTR(pseudo);
248 }
249
250 static void track_phi_uses(struct instruction *insn)
251 {
252 pseudo_t phi;
253 FOR_EACH_PTR(insn->phi_list, phi) {
254 struct instruction *def;
255 if (phi == VOID || !phi->def)
256 continue;
257 def = phi->def;
258 assert(def->opcode == OP_PHISOURCE);
259 add_ptr_list(&def->phi_users, insn);
260 } END_FOR_EACH_PTR(phi);
261 }
262
263 static void track_bb_phi_uses(struct basic_block *bb)
264 {
265 struct instruction *insn;
266 FOR_EACH_PTR(bb->insns, insn) {
267 if (insn->bb && insn->opcode == OP_PHI)
268 track_phi_uses(insn);
269 } END_FOR_EACH_PTR(insn);
270 }
|