2 * Register - track pseudo usage, maybe eventually try to do register
5 * Copyright (C) 2004 Linus Torvalds
11 #include "expression.h"
12 #include "linearize.h"
15 static void phi_defines(struct instruction
* phi_node
, pseudo_t target
,
16 void (*defines
)(struct basic_block
*, struct instruction
*, pseudo_t
))
19 FOR_EACH_PTR(phi_node
->phi_list
, phi
) {
20 struct instruction
*def
;
26 if (def
->opcode
== OP_PHI
) {
27 phi_defines(def
, target
, defines
);
30 defines(def
->bb
, phi
->def
, target
);
31 } END_FOR_EACH_PTR(phi
);
34 static void track_instruction_usage(struct basic_block
*bb
, struct instruction
*insn
,
35 void (*def
)(struct basic_block
*, struct instruction
*, pseudo_t
),
36 void (*use
)(struct basic_block
*, struct instruction
*, pseudo_t
))
40 #define USES(x) use(bb, insn, insn->x)
41 #define DEFINES(x) def(bb, insn, insn->x)
43 switch (insn
->opcode
) {
48 case OP_BR
: case OP_SWITCH
:
57 case OP_BINARY
... OP_BINARY_END
:
58 case OP_BINCMP
... OP_BINCMP_END
:
59 USES(src1
); USES(src2
); DEFINES(target
);
63 case OP_NOT
: case OP_NEG
:
64 USES(src1
); DEFINES(target
);
68 USES(src1
); USES(src2
); USES(src3
); DEFINES(target
);
73 USES(src
); DEFINES(target
);
77 USES(src
); USES(target
);
81 USES(symbol
); DEFINES(target
);
86 /* Phi-nodes are "backwards" nodes. Their def doesn't matter */
87 phi_defines(insn
, insn
->target
, def
);
92 * We don't care about the phi-source define, they get set
93 * up and expanded by the OP_PHI
100 USES(src
); DEFINES(target
);
105 if (insn
->target
!= VOID
)
107 FOR_EACH_PTR(insn
->arguments
, pseudo
) {
108 use(bb
, insn
, pseudo
);
109 } END_FOR_EACH_PTR(pseudo
);
113 USES(base
); DEFINES(target
);
117 FOR_EACH_PTR(insn
->inputs
, pseudo
) {
118 use(bb
, insn
, pseudo
);
119 } END_FOR_EACH_PTR(pseudo
);
121 FOR_EACH_PTR(insn
->outputs
, pseudo
) {
122 def(bb
, insn
, pseudo
);
123 } END_FOR_EACH_PTR(pseudo
);
132 case OP_GET_ELEMENT_PTR
:
143 int pseudo_in_list(struct pseudo_list
*list
, pseudo_t pseudo
)
146 FOR_EACH_PTR(list
,old
) {
149 } END_FOR_EACH_PTR(old
);
153 static int liveness_changed
;
155 static void add_pseudo_exclusive(struct pseudo_list
**list
, pseudo_t pseudo
)
157 if (!pseudo_in_list(*list
, pseudo
)) {
158 liveness_changed
= 1;
159 add_pseudo(list
, pseudo
);
163 static inline int trackable_pseudo(pseudo_t pseudo
)
165 return pseudo
&& (pseudo
->type
== PSEUDO_REG
|| pseudo
->type
== PSEUDO_PHI
|| pseudo
->type
== PSEUDO_ARG
);
168 static void insn_uses(struct basic_block
*bb
, struct instruction
*insn
, pseudo_t pseudo
)
170 if (trackable_pseudo(pseudo
))
171 add_pseudo_exclusive(&bb
->needs
, pseudo
);
174 static void insn_defines(struct basic_block
*bb
, struct instruction
*insn
, pseudo_t pseudo
)
176 assert(trackable_pseudo(pseudo
));
177 add_pseudo(&bb
->defines
, pseudo
);
180 static void track_bb_liveness(struct basic_block
*bb
)
184 FOR_EACH_PTR(bb
->needs
, needs
) {
185 if (!pseudo_in_list(bb
->defines
, needs
)) {
186 struct basic_block
*parent
;
187 FOR_EACH_PTR(bb
->parents
, parent
) {
188 if (!pseudo_in_list(parent
->defines
, needs
)) {
189 add_pseudo_exclusive(&parent
->needs
, needs
);
191 } END_FOR_EACH_PTR(parent
);
193 } END_FOR_EACH_PTR(needs
);
196 static inline void remove_pseudo(struct pseudo_list
**list
, pseudo_t pseudo
)
198 delete_ptr_list_entry((struct ptr_list
**)list
, pseudo
, 0);
202 * We need to clear the liveness information if we
203 * are going to re-run it.
205 void clear_liveness(struct entrypoint
*ep
)
207 struct basic_block
*bb
;
209 FOR_EACH_PTR(ep
->bbs
, bb
) {
210 free_ptr_list(&bb
->needs
);
211 free_ptr_list(&bb
->defines
);
212 } END_FOR_EACH_PTR(bb
);
216 * Track inter-bb pseudo liveness. The intra-bb case
217 * is purely local information.
219 void track_pseudo_liveness(struct entrypoint
*ep
)
221 struct basic_block
*bb
;
223 /* Add all the bb pseudo usage */
224 FOR_EACH_PTR(ep
->bbs
, bb
) {
225 struct instruction
*insn
;
226 FOR_EACH_PTR(bb
->insns
, insn
) {
229 assert(insn
->bb
== bb
);
230 track_instruction_usage(bb
, insn
, insn_defines
, insn_uses
);
231 } END_FOR_EACH_PTR(insn
);
232 } END_FOR_EACH_PTR(bb
);
234 /* Remove the pseudos from the "need" list that are defined internally */
235 FOR_EACH_PTR(ep
->bbs
, bb
) {
237 FOR_EACH_PTR(bb
->defines
, def
) {
238 remove_pseudo(&bb
->needs
, def
);
239 } END_FOR_EACH_PTR(def
);
240 } END_FOR_EACH_PTR(bb
);
242 /* Calculate liveness.. */
244 liveness_changed
= 0;
245 FOR_EACH_PTR_REVERSE(ep
->bbs
, bb
) {
246 track_bb_liveness(bb
);
247 } END_FOR_EACH_PTR_REVERSE(bb
);
248 } while (liveness_changed
);
250 /* Remove the pseudos from the "defines" list that are used internally */
251 FOR_EACH_PTR(ep
->bbs
, bb
) {
253 FOR_EACH_PTR(bb
->defines
, def
) {
254 struct basic_block
*child
;
255 FOR_EACH_PTR(bb
->children
, child
) {
256 if (pseudo_in_list(child
->needs
, def
))
258 } END_FOR_EACH_PTR(child
);
259 DELETE_CURRENT_PTR(def
);
262 } END_FOR_EACH_PTR(def
);
263 PACK_PTR_LIST(&bb
->defines
);
264 } END_FOR_EACH_PTR(bb
);
267 static void merge_pseudo_list(struct pseudo_list
*src
, struct pseudo_list
**dest
)
270 FOR_EACH_PTR(src
, pseudo
) {
271 add_pseudo_exclusive(dest
, pseudo
);
272 } END_FOR_EACH_PTR(pseudo
);
275 static void track_phi_uses(struct instruction
*insn
)
278 FOR_EACH_PTR(insn
->phi_list
, phi
) {
279 struct instruction
*def
;
280 if (phi
== VOID
|| !phi
->def
)
283 assert(def
->opcode
== OP_PHISOURCE
);
284 add_ptr_list(&def
->phi_users
, insn
);
285 } END_FOR_EACH_PTR(phi
);
288 static struct pseudo_list
**live_list
;
289 static struct pseudo_list
*dead_list
;
291 static void death_def(struct basic_block
*bb
, struct instruction
*insn
, pseudo_t pseudo
)
295 static void death_use(struct basic_block
*bb
, struct instruction
*insn
, pseudo_t pseudo
)
297 if (trackable_pseudo(pseudo
) && !pseudo_in_list(*live_list
, pseudo
)) {
298 add_pseudo(&dead_list
, pseudo
);
299 add_pseudo(live_list
, pseudo
);
303 static void track_pseudo_death_bb(struct basic_block
*bb
)
305 struct pseudo_list
*live
= NULL
;
306 struct basic_block
*child
;
307 struct instruction
*insn
;
309 FOR_EACH_PTR(bb
->children
, child
) {
310 merge_pseudo_list(child
->needs
, &live
);
311 } END_FOR_EACH_PTR(child
);
314 FOR_EACH_PTR_REVERSE(bb
->insns
, insn
) {
317 if (insn
->opcode
== OP_PHI
)
318 track_phi_uses(insn
);
320 track_instruction_usage(bb
, insn
, death_def
, death_use
);
323 FOR_EACH_PTR(dead_list
, dead
) {
324 struct instruction
*deathnote
= __alloc_instruction(0);
326 deathnote
->opcode
= OP_DEATHNOTE
;
327 deathnote
->target
= dead
;
328 INSERT_CURRENT(deathnote
, insn
);
329 } END_FOR_EACH_PTR(dead
);
330 free_ptr_list(&dead_list
);
332 } END_FOR_EACH_PTR_REVERSE(insn
);
333 free_ptr_list(&live
);
336 void track_pseudo_death(struct entrypoint
*ep
)
338 struct basic_block
*bb
;
340 FOR_EACH_PTR(ep
->bbs
, bb
) {
341 track_pseudo_death_bb(bb
);
342 } END_FOR_EACH_PTR(bb
);