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 struct instruction
*def
= pseudo
->def
;
172 if (pseudo
->type
!= PSEUDO_REG
|| def
->bb
!= bb
|| def
->opcode
== OP_PHI
)
173 add_pseudo_exclusive(&bb
->needs
, pseudo
);
177 static void insn_defines(struct basic_block
*bb
, struct instruction
*insn
, pseudo_t pseudo
)
179 assert(trackable_pseudo(pseudo
));
180 add_pseudo(&bb
->defines
, pseudo
);
183 static void track_bb_liveness(struct basic_block
*bb
)
187 FOR_EACH_PTR(bb
->needs
, needs
) {
188 struct basic_block
*parent
;
189 FOR_EACH_PTR(bb
->parents
, parent
) {
190 if (!pseudo_in_list(parent
->defines
, needs
)) {
191 add_pseudo_exclusive(&parent
->needs
, needs
);
193 } END_FOR_EACH_PTR(parent
);
194 } END_FOR_EACH_PTR(needs
);
197 static inline void remove_pseudo(struct pseudo_list
**list
, pseudo_t pseudo
)
199 delete_ptr_list_entry((struct ptr_list
**)list
, pseudo
, 0);
203 * We need to clear the liveness information if we
204 * are going to re-run it.
206 void clear_liveness(struct entrypoint
*ep
)
208 struct basic_block
*bb
;
210 FOR_EACH_PTR(ep
->bbs
, bb
) {
211 free_ptr_list(&bb
->needs
);
212 free_ptr_list(&bb
->defines
);
213 } END_FOR_EACH_PTR(bb
);
217 * Track inter-bb pseudo liveness. The intra-bb case
218 * is purely local information.
220 void track_pseudo_liveness(struct entrypoint
*ep
)
222 struct basic_block
*bb
;
224 /* Add all the bb pseudo usage */
225 FOR_EACH_PTR(ep
->bbs
, bb
) {
226 struct instruction
*insn
;
227 FOR_EACH_PTR(bb
->insns
, insn
) {
230 assert(insn
->bb
== bb
);
231 track_instruction_usage(bb
, insn
, insn_defines
, insn_uses
);
232 } END_FOR_EACH_PTR(insn
);
233 } END_FOR_EACH_PTR(bb
);
235 /* Calculate liveness.. */
237 liveness_changed
= 0;
238 FOR_EACH_PTR_REVERSE(ep
->bbs
, bb
) {
239 track_bb_liveness(bb
);
240 } END_FOR_EACH_PTR_REVERSE(bb
);
241 } while (liveness_changed
);
243 /* Remove the pseudos from the "defines" list that are used internally */
244 FOR_EACH_PTR(ep
->bbs
, bb
) {
246 FOR_EACH_PTR(bb
->defines
, def
) {
247 struct basic_block
*child
;
248 FOR_EACH_PTR(bb
->children
, child
) {
249 if (pseudo_in_list(child
->needs
, def
))
251 } END_FOR_EACH_PTR(child
);
252 DELETE_CURRENT_PTR(def
);
255 } END_FOR_EACH_PTR(def
);
256 PACK_PTR_LIST(&bb
->defines
);
257 } END_FOR_EACH_PTR(bb
);
260 static void merge_pseudo_list(struct pseudo_list
*src
, struct pseudo_list
**dest
)
263 FOR_EACH_PTR(src
, pseudo
) {
264 add_pseudo_exclusive(dest
, pseudo
);
265 } END_FOR_EACH_PTR(pseudo
);
268 static void track_phi_uses(struct instruction
*insn
)
271 FOR_EACH_PTR(insn
->phi_list
, phi
) {
272 struct instruction
*def
;
273 if (phi
== VOID
|| !phi
->def
)
276 assert(def
->opcode
== OP_PHISOURCE
);
277 add_ptr_list(&def
->phi_users
, insn
);
278 } END_FOR_EACH_PTR(phi
);
281 static struct pseudo_list
**live_list
;
282 static struct pseudo_list
*dead_list
;
284 static void death_def(struct basic_block
*bb
, struct instruction
*insn
, pseudo_t pseudo
)
288 static void death_use(struct basic_block
*bb
, struct instruction
*insn
, pseudo_t pseudo
)
290 if (trackable_pseudo(pseudo
) && !pseudo_in_list(*live_list
, pseudo
)) {
291 add_pseudo(&dead_list
, pseudo
);
292 add_pseudo(live_list
, pseudo
);
296 static void track_pseudo_death_bb(struct basic_block
*bb
)
298 struct pseudo_list
*live
= NULL
;
299 struct basic_block
*child
;
300 struct instruction
*insn
;
302 FOR_EACH_PTR(bb
->children
, child
) {
303 merge_pseudo_list(child
->needs
, &live
);
304 } END_FOR_EACH_PTR(child
);
307 FOR_EACH_PTR_REVERSE(bb
->insns
, insn
) {
310 if (insn
->opcode
== OP_PHI
)
311 track_phi_uses(insn
);
313 track_instruction_usage(bb
, insn
, death_def
, death_use
);
316 FOR_EACH_PTR(dead_list
, dead
) {
317 struct instruction
*deathnote
= __alloc_instruction(0);
319 deathnote
->opcode
= OP_DEATHNOTE
;
320 deathnote
->target
= dead
;
321 INSERT_CURRENT(deathnote
, insn
);
322 } END_FOR_EACH_PTR(dead
);
323 free_ptr_list(&dead_list
);
325 } END_FOR_EACH_PTR_REVERSE(insn
);
326 free_ptr_list(&live
);
329 void track_pseudo_death(struct entrypoint
*ep
)
331 struct basic_block
*bb
;
333 FOR_EACH_PTR(ep
->bbs
, bb
) {
334 track_pseudo_death_bb(bb
);
335 } END_FOR_EACH_PTR(bb
);