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 asm_liveness(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
))
38 struct asm_constraint
*entry
;
40 FOR_EACH_PTR(insn
->asm_rules
->inputs
, entry
) {
41 use(bb
, insn
, entry
->pseudo
);
42 } END_FOR_EACH_PTR(entry
);
44 FOR_EACH_PTR(insn
->asm_rules
->outputs
, entry
) {
45 def(bb
, insn
, entry
->pseudo
);
46 } END_FOR_EACH_PTR(entry
);
49 static void track_instruction_usage(struct basic_block
*bb
, struct instruction
*insn
,
50 void (*def
)(struct basic_block
*, struct instruction
*, pseudo_t
),
51 void (*use
)(struct basic_block
*, struct instruction
*, pseudo_t
))
55 #define USES(x) use(bb, insn, insn->x)
56 #define DEFINES(x) def(bb, insn, insn->x)
58 switch (insn
->opcode
) {
63 case OP_BR
: case OP_SWITCH
:
72 case OP_BINARY
... OP_BINARY_END
:
73 case OP_BINCMP
... OP_BINCMP_END
:
74 USES(src1
); USES(src2
); DEFINES(target
);
78 case OP_NOT
: case OP_NEG
:
79 USES(src1
); DEFINES(target
);
83 USES(src1
); USES(src2
); USES(src3
); DEFINES(target
);
88 USES(src
); DEFINES(target
);
92 USES(src
); USES(target
);
96 USES(symbol
); DEFINES(target
);
101 /* Phi-nodes are "backwards" nodes. Their def doesn't matter */
102 phi_defines(insn
, insn
->target
, def
);
107 * We don't care about the phi-source define, they get set
108 * up and expanded by the OP_PHI
115 USES(src
); DEFINES(target
);
120 if (insn
->target
!= VOID
)
122 FOR_EACH_PTR(insn
->arguments
, pseudo
) {
123 use(bb
, insn
, pseudo
);
124 } END_FOR_EACH_PTR(pseudo
);
128 USES(base
); DEFINES(target
);
132 asm_liveness(bb
, insn
, def
, use
);
141 case OP_GET_ELEMENT_PTR
:
152 int pseudo_in_list(struct pseudo_list
*list
, pseudo_t pseudo
)
155 FOR_EACH_PTR(list
,old
) {
158 } END_FOR_EACH_PTR(old
);
162 static int liveness_changed
;
164 static void add_pseudo_exclusive(struct pseudo_list
**list
, pseudo_t pseudo
)
166 if (!pseudo_in_list(*list
, pseudo
)) {
167 liveness_changed
= 1;
168 add_pseudo(list
, pseudo
);
172 static inline int trackable_pseudo(pseudo_t pseudo
)
174 return pseudo
&& (pseudo
->type
== PSEUDO_REG
|| pseudo
->type
== PSEUDO_ARG
);
177 static void insn_uses(struct basic_block
*bb
, struct instruction
*insn
, pseudo_t pseudo
)
179 if (trackable_pseudo(pseudo
)) {
180 struct instruction
*def
= pseudo
->def
;
181 if (pseudo
->type
!= PSEUDO_REG
|| def
->bb
!= bb
|| def
->opcode
== OP_PHI
)
182 add_pseudo_exclusive(&bb
->needs
, pseudo
);
186 static void insn_defines(struct basic_block
*bb
, struct instruction
*insn
, pseudo_t pseudo
)
188 assert(trackable_pseudo(pseudo
));
189 add_pseudo(&bb
->defines
, pseudo
);
192 static void track_bb_liveness(struct basic_block
*bb
)
196 FOR_EACH_PTR(bb
->needs
, needs
) {
197 struct basic_block
*parent
;
198 FOR_EACH_PTR(bb
->parents
, parent
) {
199 if (!pseudo_in_list(parent
->defines
, needs
)) {
200 add_pseudo_exclusive(&parent
->needs
, needs
);
202 } END_FOR_EACH_PTR(parent
);
203 } END_FOR_EACH_PTR(needs
);
207 * We need to clear the liveness information if we
208 * are going to re-run it.
210 void clear_liveness(struct entrypoint
*ep
)
212 struct basic_block
*bb
;
214 FOR_EACH_PTR(ep
->bbs
, bb
) {
215 free_ptr_list(&bb
->needs
);
216 free_ptr_list(&bb
->defines
);
217 } END_FOR_EACH_PTR(bb
);
221 * Track inter-bb pseudo liveness. The intra-bb case
222 * is purely local information.
224 void track_pseudo_liveness(struct entrypoint
*ep
)
226 struct basic_block
*bb
;
228 /* Add all the bb pseudo usage */
229 FOR_EACH_PTR(ep
->bbs
, bb
) {
230 struct instruction
*insn
;
231 FOR_EACH_PTR(bb
->insns
, insn
) {
234 assert(insn
->bb
== bb
);
235 track_instruction_usage(bb
, insn
, insn_defines
, insn_uses
);
236 } END_FOR_EACH_PTR(insn
);
237 } END_FOR_EACH_PTR(bb
);
239 /* Calculate liveness.. */
241 liveness_changed
= 0;
242 FOR_EACH_PTR_REVERSE(ep
->bbs
, bb
) {
243 track_bb_liveness(bb
);
244 } END_FOR_EACH_PTR_REVERSE(bb
);
245 } while (liveness_changed
);
247 /* Remove the pseudos from the "defines" list that are used internally */
248 FOR_EACH_PTR(ep
->bbs
, bb
) {
250 FOR_EACH_PTR(bb
->defines
, def
) {
251 struct basic_block
*child
;
252 FOR_EACH_PTR(bb
->children
, child
) {
253 if (pseudo_in_list(child
->needs
, def
))
255 } END_FOR_EACH_PTR(child
);
256 DELETE_CURRENT_PTR(def
);
259 } END_FOR_EACH_PTR(def
);
260 PACK_PTR_LIST(&bb
->defines
);
261 } END_FOR_EACH_PTR(bb
);
264 static void merge_pseudo_list(struct pseudo_list
*src
, struct pseudo_list
**dest
)
267 FOR_EACH_PTR(src
, pseudo
) {
268 add_pseudo_exclusive(dest
, pseudo
);
269 } END_FOR_EACH_PTR(pseudo
);
272 static void track_phi_uses(struct instruction
*insn
)
275 FOR_EACH_PTR(insn
->phi_list
, phi
) {
276 struct instruction
*def
;
277 if (phi
== VOID
|| !phi
->def
)
280 assert(def
->opcode
== OP_PHISOURCE
);
281 add_ptr_list(&def
->phi_users
, insn
);
282 } END_FOR_EACH_PTR(phi
);
285 static void track_bb_phi_uses(struct basic_block
*bb
)
287 struct instruction
*insn
;
288 FOR_EACH_PTR(bb
->insns
, insn
) {
289 if (insn
->bb
&& insn
->opcode
== OP_PHI
)
290 track_phi_uses(insn
);
291 } END_FOR_EACH_PTR(insn
);
294 static struct pseudo_list
**live_list
;
295 static struct pseudo_list
*dead_list
;
297 static void death_def(struct basic_block
*bb
, struct instruction
*insn
, pseudo_t pseudo
)
301 static void death_use(struct basic_block
*bb
, struct instruction
*insn
, pseudo_t pseudo
)
303 if (trackable_pseudo(pseudo
) && !pseudo_in_list(*live_list
, pseudo
)) {
304 add_pseudo(&dead_list
, pseudo
);
305 add_pseudo(live_list
, pseudo
);
309 static void track_pseudo_death_bb(struct basic_block
*bb
)
311 struct pseudo_list
*live
= NULL
;
312 struct basic_block
*child
;
313 struct instruction
*insn
;
315 FOR_EACH_PTR(bb
->children
, child
) {
316 merge_pseudo_list(child
->needs
, &live
);
317 } END_FOR_EACH_PTR(child
);
320 FOR_EACH_PTR_REVERSE(bb
->insns
, insn
) {
325 * A "def" of a pseudo removes it from the liveness
326 * list. However, we only bother doing that for
327 * phi-nodes, since no other pseudos should ever
328 * be even used before they are def'ed.
330 if (insn
->opcode
== OP_PHISOURCE
) {
331 struct instruction
*phi
;
332 FOR_EACH_PTR(insn
->phi_users
, phi
) {
333 remove_pseudo(live_list
, phi
->target
);
334 } END_FOR_EACH_PTR(phi
);
338 track_instruction_usage(bb
, insn
, death_def
, death_use
);
341 FOR_EACH_PTR(dead_list
, dead
) {
342 struct instruction
*deathnote
= __alloc_instruction(0);
344 deathnote
->opcode
= OP_DEATHNOTE
;
345 deathnote
->target
= dead
;
346 INSERT_CURRENT(deathnote
, insn
);
347 } END_FOR_EACH_PTR(dead
);
348 free_ptr_list(&dead_list
);
350 } END_FOR_EACH_PTR_REVERSE(insn
);
351 free_ptr_list(&live
);
354 void track_pseudo_death(struct entrypoint
*ep
)
356 struct basic_block
*bb
;
358 FOR_EACH_PTR(ep
->bbs
, bb
) {
359 track_bb_phi_uses(bb
);
360 } END_FOR_EACH_PTR(bb
);
362 FOR_EACH_PTR(ep
->bbs
, bb
) {
363 track_pseudo_death_bb(bb
);
364 } END_FOR_EACH_PTR(bb
);