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
);
122 case OP_GET_ELEMENT_PTR
:
133 int pseudo_in_list(struct pseudo_list
*list
, pseudo_t pseudo
)
136 FOR_EACH_PTR(list
,old
) {
139 } END_FOR_EACH_PTR(old
);
143 static int liveness_changed
;
145 static void add_pseudo_exclusive(struct pseudo_list
**list
, pseudo_t pseudo
)
147 if (!pseudo_in_list(*list
, pseudo
)) {
148 liveness_changed
= 1;
149 add_pseudo(list
, pseudo
);
153 static inline int trackable_pseudo(pseudo_t pseudo
)
155 return pseudo
&& (pseudo
->type
== PSEUDO_REG
|| pseudo
->type
== PSEUDO_PHI
|| pseudo
->type
== PSEUDO_ARG
);
158 static void insn_uses(struct basic_block
*bb
, struct instruction
*insn
, pseudo_t pseudo
)
160 if (trackable_pseudo(pseudo
))
161 add_pseudo_exclusive(&bb
->needs
, pseudo
);
164 static void insn_defines(struct basic_block
*bb
, struct instruction
*insn
, pseudo_t pseudo
)
166 assert(trackable_pseudo(pseudo
));
167 add_pseudo(&bb
->defines
, pseudo
);
170 static void track_bb_liveness(struct basic_block
*bb
)
174 FOR_EACH_PTR(bb
->needs
, needs
) {
175 if (!pseudo_in_list(bb
->defines
, needs
)) {
176 struct basic_block
*parent
;
177 FOR_EACH_PTR(bb
->parents
, parent
) {
178 if (!pseudo_in_list(parent
->defines
, needs
)) {
179 add_pseudo_exclusive(&parent
->needs
, needs
);
181 } END_FOR_EACH_PTR(parent
);
183 } END_FOR_EACH_PTR(needs
);
186 static inline void remove_pseudo(struct pseudo_list
**list
, pseudo_t pseudo
)
188 delete_ptr_list_entry((struct ptr_list
**)list
, pseudo
, 0);
192 * We need to clear the liveness information if we
193 * are going to re-run it.
195 void clear_liveness(struct entrypoint
*ep
)
197 struct basic_block
*bb
;
199 FOR_EACH_PTR(ep
->bbs
, bb
) {
200 free_ptr_list(&bb
->needs
);
201 free_ptr_list(&bb
->defines
);
202 } END_FOR_EACH_PTR(bb
);
206 * Track inter-bb pseudo liveness. The intra-bb case
207 * is purely local information.
209 void track_pseudo_liveness(struct entrypoint
*ep
)
211 struct basic_block
*bb
;
213 /* Add all the bb pseudo usage */
214 FOR_EACH_PTR(ep
->bbs
, bb
) {
215 struct instruction
*insn
;
216 FOR_EACH_PTR(bb
->insns
, insn
) {
219 assert(insn
->bb
== bb
);
220 track_instruction_usage(bb
, insn
, insn_defines
, insn_uses
);
221 } END_FOR_EACH_PTR(insn
);
222 } END_FOR_EACH_PTR(bb
);
224 /* Remove the pseudos from the "need" list that are defined internally */
225 FOR_EACH_PTR(ep
->bbs
, bb
) {
227 FOR_EACH_PTR(bb
->defines
, def
) {
228 remove_pseudo(&bb
->needs
, def
);
229 } END_FOR_EACH_PTR(def
);
230 } END_FOR_EACH_PTR(bb
);
232 /* Calculate liveness.. */
234 liveness_changed
= 0;
235 FOR_EACH_PTR_REVERSE(ep
->bbs
, bb
) {
236 track_bb_liveness(bb
);
237 } END_FOR_EACH_PTR_REVERSE(bb
);
238 } while (liveness_changed
);
240 /* Remove the pseudos from the "defines" list that are used internally */
241 FOR_EACH_PTR(ep
->bbs
, bb
) {
243 FOR_EACH_PTR(bb
->defines
, def
) {
244 struct basic_block
*child
;
245 FOR_EACH_PTR(bb
->children
, child
) {
246 if (pseudo_in_list(child
->needs
, def
))
248 } END_FOR_EACH_PTR(child
);
249 DELETE_CURRENT_PTR(def
);
252 } END_FOR_EACH_PTR(def
);
253 PACK_PTR_LIST(&bb
->defines
);
254 } END_FOR_EACH_PTR(bb
);
257 static void merge_pseudo_list(struct pseudo_list
*src
, struct pseudo_list
**dest
)
260 FOR_EACH_PTR(src
, pseudo
) {
261 add_pseudo_exclusive(dest
, pseudo
);
262 } END_FOR_EACH_PTR(pseudo
);
265 static struct pseudo_list
**live_list
;
266 static struct pseudo_list
*dead_list
;
268 static void death_def(struct basic_block
*bb
, struct instruction
*insn
, pseudo_t pseudo
)
272 static void death_use(struct basic_block
*bb
, struct instruction
*insn
, pseudo_t pseudo
)
274 if (trackable_pseudo(pseudo
) && !pseudo_in_list(*live_list
, pseudo
)) {
275 add_pseudo(&dead_list
, pseudo
);
276 add_pseudo(live_list
, pseudo
);
280 static void track_pseudo_death_bb(struct basic_block
*bb
)
282 struct pseudo_list
*live
= NULL
;
283 struct basic_block
*child
;
284 struct instruction
*insn
;
286 FOR_EACH_PTR(bb
->children
, child
) {
287 merge_pseudo_list(child
->needs
, &live
);
288 } END_FOR_EACH_PTR(child
);
291 FOR_EACH_PTR_REVERSE(bb
->insns
, insn
) {
295 track_instruction_usage(bb
, insn
, death_def
, death_use
);
298 FOR_EACH_PTR(dead_list
, dead
) {
299 struct instruction
*deathnote
= __alloc_instruction(0);
301 deathnote
->opcode
= OP_DEATHNOTE
;
302 deathnote
->target
= dead
;
303 INSERT_CURRENT(deathnote
, insn
);
304 } END_FOR_EACH_PTR(dead
);
305 free_ptr_list(&dead_list
);
307 } END_FOR_EACH_PTR_REVERSE(insn
);
308 free_ptr_list(&live
);
311 void track_pseudo_death(struct entrypoint
*ep
)
313 struct basic_block
*bb
;
315 FOR_EACH_PTR(ep
->bbs
, bb
) {
316 track_pseudo_death_bb(bb
);
317 } END_FOR_EACH_PTR(bb
);