2 * Copyright 2010 Christoph Bumiller
4 * Permission is hereby granted, free of charge, to any person obtaining a
5 * copy of this software and associated documentation files (the "Software"),
6 * to deal in the Software without restriction, including without limitation
7 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
8 * and/or sell copies of the Software, and to permit persons to whom the
9 * Software is furnished to do so, subject to the following conditions:
11 * The above copyright notice and this permission notice shall be included in
12 * all copies or substantial portions of the Software.
14 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
15 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
16 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
17 * THE AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
18 * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF
19 * OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
23 /* #define NV50PC_DEBUG */
25 /* #define NV50_RA_DEBUG_LIVEI */
26 /* #define NV50_RA_DEBUG_LIVE_SETS */
27 /* #define NV50_RA_DEBUG_JOIN */
29 #include "nv50_context.h"
32 #include "util/u_simple_list.h"
34 #define NUM_REGISTER_FILES 4
39 uint32_t last
[NUM_REGISTER_FILES
];
40 uint32_t bits
[NUM_REGISTER_FILES
][8];
46 struct nv_instruction
**insns
;
53 ranges_coalesce(struct nv_range
*range
)
55 while (range
->next
&& range
->end
>= range
->next
->bgn
) {
56 struct nv_range
*rnn
= range
->next
->next
;
57 assert(range
->bgn
<= range
->next
->bgn
);
58 range
->end
= MAX2(range
->end
, range
->next
->end
);
65 add_range_ex(struct nv_value
*val
, int bgn
, int end
, struct nv_range
*new_range
)
67 struct nv_range
*range
, **nextp
= &val
->livei
;
69 for (range
= val
->livei
; range
; range
= range
->next
) {
71 break; /* insert before */
73 if (bgn
> range
->end
) {
75 continue; /* insert after */
79 if (bgn
< range
->bgn
) {
83 ranges_coalesce(range
);
86 if (end
> range
->end
) {
88 ranges_coalesce(range
);
91 assert(bgn
>= range
->bgn
);
92 assert(end
<= range
->end
);
97 new_range
= CALLOC_STRUCT(nv_range
);
100 new_range
->end
= end
;
101 new_range
->next
= range
;
102 *(nextp
) = new_range
;
107 add_range(struct nv_value
*val
, struct nv_basic_block
*b
, int end
)
111 if (!val
->insn
) /* ignore non-def values */
113 assert(b
->entry
->serial
<= b
->exit
->serial
);
114 assert(b
->phi
->serial
<= end
);
115 assert(b
->exit
->serial
+ 1 >= end
);
117 bgn
= val
->insn
->serial
;
118 if (bgn
< b
->entry
->serial
|| bgn
> b
->exit
->serial
)
119 bgn
= b
->entry
->serial
;
123 add_range_ex(val
, bgn
, end
, NULL
);
126 #if defined(NV50_RA_DEBUG_JOIN) || defined(NV50_RA_DEBUG_LIVEI)
128 livei_print(struct nv_value
*a
)
130 struct nv_range
*r
= a
->livei
;
132 debug_printf("livei %i: ", a
->n
);
134 debug_printf("[%i, %i) ", r
->bgn
, r
->end
);
142 livei_unify(struct nv_value
*dst
, struct nv_value
*src
)
144 struct nv_range
*range
, *next
;
146 for (range
= src
->livei
; range
; range
= next
) {
148 if (add_range_ex(dst
, range
->bgn
, range
->end
, range
))
155 livei_release(struct nv_value
*val
)
157 struct nv_range
*range
, *next
;
159 for (range
= val
->livei
; range
; range
= next
) {
166 livei_have_overlap(struct nv_value
*a
, struct nv_value
*b
)
168 struct nv_range
*r_a
, *r_b
;
170 for (r_a
= a
->livei
; r_a
; r_a
= r_a
->next
) {
171 for (r_b
= b
->livei
; r_b
; r_b
= r_b
->next
) {
172 if (r_b
->bgn
< r_a
->end
&&
181 livei_end(struct nv_value
*a
)
183 struct nv_range
*r
= a
->livei
;
192 livei_contains(struct nv_value
*a
, int pos
)
196 for (r
= a
->livei
; r
&& r
->bgn
<= pos
; r
= r
->next
)
203 reg_assign(struct register_set
*set
, struct nv_value
**def
, int n
)
207 int f
= def
[0]->reg
.file
;
209 s
= n
<< (nv_type_order(def
[0]->reg
.type
) - 1);
214 for (i
= 0; i
* 32 < set
->last
[f
]; ++i
) {
215 if (set
->bits
[f
][i
] == 0xffffffff)
218 for (id
= 0; id
< 32; id
+= s
)
219 if (!(set
->bits
[f
][i
] & (m
<< id
)))
224 if (i
* 32 + id
> set
->last
[f
])
227 set
->bits
[f
][i
] |= m
<< id
;
231 set
->pc
->max_reg
[f
] = MAX2(set
->pc
->max_reg
[f
], id
+ s
- 1);
233 id
>>= nv_type_order(def
[0]->reg
.type
) - 1;
235 for (i
= 0; i
< n
; ++i
)
237 def
[i
]->reg
.id
= id
++;
243 reg_occupy(struct register_set
*set
, struct nv_value
*val
)
245 int s
, id
= val
->reg
.id
, f
= val
->reg
.file
;
250 s
= nv_type_order(val
->reg
.type
) - 1;
252 m
= (1 << (1 << s
)) - 1;
254 set
->bits
[f
][id
/ 32] |= m
<< (id
% 32);
256 if (set
->pc
->max_reg
[f
] < id
)
257 set
->pc
->max_reg
[f
] = id
;
261 reg_release(struct register_set
*set
, struct nv_value
*val
)
263 int s
, id
= val
->reg
.id
, f
= val
->reg
.file
;
269 s
= nv_type_order(val
->reg
.type
) - 1;
271 m
= (1 << (1 << s
)) - 1;
273 set
->bits
[f
][id
/ 32] &= ~(m
<< (id
% 32));
276 static INLINE boolean
277 join_allowed(struct nv_pc_pass
*ctx
, struct nv_value
*a
, struct nv_value
*b
)
280 struct nv_value
*val
;
282 if (a
->reg
.file
!= b
->reg
.file
||
283 nv_type_sizeof(a
->reg
.type
) != nv_type_sizeof(b
->reg
.type
))
286 if (a
->join
->reg
.id
== b
->join
->reg
.id
)
290 /* either a or b or both have been assigned */
292 if (a
->join
->reg
.id
>= 0 && b
->join
->reg
.id
>= 0)
295 if (b
->join
->reg
.id
>= 0) {
296 if (a
->join
->reg
.id
>= 0)
303 for (i
= 0; i
< ctx
->pc
->num_values
; ++i
) {
304 val
= &ctx
->pc
->values
[i
];
306 if (val
->join
->reg
.id
!= a
->join
->reg
.id
)
308 if (val
->join
!= a
->join
&& livei_have_overlap(val
->join
, b
->join
))
317 do_join_values(struct nv_pc_pass
*ctx
, struct nv_value
*a
, struct nv_value
*b
)
320 struct nv_value
*bjoin
= b
->join
;
322 if (b
->join
->reg
.id
>= 0)
323 a
->join
->reg
.id
= b
->join
->reg
.id
;
325 livei_unify(a
->join
, b
->join
);
327 #ifdef NV50_RA_DEBUG_JOIN
328 debug_printf("joining %i to %i\n", b
->n
, a
->n
);
331 /* make a->join the new representative */
332 for (j
= 0; j
< ctx
->pc
->num_values
; ++j
)
333 if (ctx
->pc
->values
[j
].join
== bjoin
)
334 ctx
->pc
->values
[j
].join
= a
->join
;
336 assert(b
->join
== a
->join
);
340 try_join_values(struct nv_pc_pass
*ctx
, struct nv_value
*a
, struct nv_value
*b
)
342 if (!join_allowed(ctx
, a
, b
)) {
343 #ifdef NV50_RA_DEBUG_JOIN
344 debug_printf("cannot join %i to %i: not allowed\n", b
->n
, a
->n
);
348 if (livei_have_overlap(a
->join
, b
->join
)) {
349 #ifdef NV50_RA_DEBUG_JOIN
350 debug_printf("cannot join %i to %i: livei overlap\n", b
->n
, a
->n
);
357 do_join_values(ctx
, a
, b
);
360 static INLINE boolean
361 need_new_else_block(struct nv_basic_block
*b
, struct nv_basic_block
*p
)
366 if (p
->out
[i
] && !IS_LOOP_EDGE(p
->out_kind
[i
]))
369 return (b
->num_in
> 1) && (n
== 2);
373 phi_opnd_for_bb(struct nv_instruction
*phi
, struct nv_basic_block
*b
,
374 struct nv_basic_block
*tb
)
378 for (j
= -1, i
= 0; i
< 4 && phi
->src
[i
]; ++i
) {
379 if (!nvbb_reachable_by(b
, phi
->src
[i
]->value
->insn
->bb
, tb
))
381 /* NOTE: back-edges are ignored by the reachable-by check */
382 if (j
< 0 || !nvbb_reachable_by(phi
->src
[j
]->value
->insn
->bb
,
383 phi
->src
[i
]->value
->insn
->bb
, tb
))
389 /* For each operand of each PHI in b, generate a new value by inserting a MOV
390 * at the end of the block it is coming from and replace the operand with its
391 * result. This eliminates liveness conflicts and enables us to let values be
392 * copied to the right register if such a conflict exists nonetheless.
394 * These MOVs are also crucial in making sure the live intervals of phi srces
395 * are extended until the end of the loop, since they are not included in the
399 pass_generate_phi_movs(struct nv_pc_pass
*ctx
, struct nv_basic_block
*b
)
401 struct nv_instruction
*i
, *ni
;
402 struct nv_value
*val
;
403 struct nv_basic_block
*p
, *pn
;
406 b
->pass_seq
= ctx
->pc
->pass_seq
;
408 for (n
= 0; n
< b
->num_in
; ++n
) {
412 if (need_new_else_block(b
, p
)) {
413 pn
= new_basic_block(ctx
->pc
);
420 if (p
->exit
->target
== b
) /* target to new else-block */
421 p
->exit
->target
= pn
;
429 ctx
->pc
->current_block
= pn
;
431 for (i
= b
->phi
; i
&& i
->opcode
== NV_OP_PHI
; i
= i
->next
) {
432 if ((j
= phi_opnd_for_bb(i
, p
, b
)) < 0)
434 val
= i
->src
[j
]->value
;
436 if (i
->src
[j
]->flags
) {
437 val
= val
->insn
->src
[0]->value
;
438 while (j
< 4 && i
->src
[j
])
443 ni
= new_instruction(ctx
->pc
, NV_OP_MOV
);
445 /* TODO: insert instruction at correct position in the first place */
446 if (ni
->prev
&& ni
->prev
->target
)
447 nv_nvi_permute(ni
->prev
, ni
);
449 ni
->def
[0] = new_value(ctx
->pc
, val
->reg
.file
, val
->reg
.type
);
450 ni
->def
[0]->insn
= ni
;
451 ni
->src
[0] = new_ref(ctx
->pc
, val
);
453 nv_reference(ctx
->pc
, &i
->src
[j
], ni
->def
[0]);
455 i
->src
[j
]->flags
= 1;
458 if (pn
!= p
&& pn
->exit
) {
459 ctx
->pc
->current_block
= b
->in
[n
? 0 : 1];
460 ni
= new_instruction(ctx
->pc
, NV_OP_BRA
);
462 ni
->is_terminator
= 1;
466 for (j
= 0; j
< 2; ++j
)
467 if (b
->out
[j
] && b
->out
[j
]->pass_seq
< ctx
->pc
->pass_seq
)
468 pass_generate_phi_movs(ctx
, b
->out
[j
]);
474 pass_join_values(struct nv_pc_pass
*ctx
, int iter
)
478 for (n
= 0; n
< ctx
->num_insns
; ++n
) {
479 struct nv_instruction
*i
= ctx
->insns
[n
];
485 for (c
= 0; c
< 4 && i
->src
[c
]; ++c
)
486 try_join_values(ctx
, i
->def
[0], i
->src
[c
]->value
);
489 if ((iter
== 2) && i
->src
[0]->value
->insn
&&
490 !nv_is_vector_op(i
->src
[0]->value
->join
->insn
->opcode
))
491 try_join_values(ctx
, i
->def
[0], i
->src
[0]->value
);
496 for (c
= 0; c
< 4 && i
->src
[c
]; ++c
) {
497 assert(join_allowed(ctx
, i
->def
[0], i
->src
[c
]->value
));
498 do_join_values(ctx
, i
->def
[0], i
->src
[c
]->value
);
507 for (c
= 0; c
< 4; ++c
) {
510 do_join_values(ctx
, i
->def
[c
], i
->src
[c
]->value
);
520 /* Order the instructions so that live intervals can be expressed in numbers. */
522 pass_order_instructions(void *priv
, struct nv_basic_block
*b
)
524 struct nv_pc_pass
*ctx
= (struct nv_pc_pass
*)priv
;
525 struct nv_instruction
*i
;
527 b
->pass_seq
= ctx
->pc
->pass_seq
;
529 assert(!b
->exit
|| !b
->exit
->next
);
530 for (i
= b
->phi
; i
; i
= i
->next
) {
531 i
->serial
= ctx
->num_insns
;
532 ctx
->insns
[ctx
->num_insns
++] = i
;
537 bb_live_set_print(struct nv_pc
*pc
, struct nv_basic_block
*b
)
539 #ifdef NV50_RA_DEBUG_LIVE_SETS
541 struct nv_value
*val
;
543 debug_printf("LIVE-INs of BB:%i: ", b
->id
);
545 for (j
= 0; j
< pc
->num_values
; ++j
) {
546 if (!(b
->live_set
[j
/ 32] & (1 << (j
% 32))))
548 val
= &pc
->values
[j
];
551 debug_printf("%i ", val
->n
);
558 live_set_add(struct nv_basic_block
*b
, struct nv_value
*val
)
560 if (!val
->insn
) /* don't add non-def values */
562 b
->live_set
[val
->n
/ 32] |= 1 << (val
->n
% 32);
566 live_set_rem(struct nv_basic_block
*b
, struct nv_value
*val
)
568 b
->live_set
[val
->n
/ 32] &= ~(1 << (val
->n
% 32));
571 static INLINE boolean
572 live_set_test(struct nv_basic_block
*b
, struct nv_ref
*ref
)
574 int n
= ref
->value
->n
;
575 return b
->live_set
[n
/ 32] & (1 << (n
% 32));
578 /* The live set of a block contains those values that are live immediately
579 * before the beginning of the block, so do a backwards scan.
582 pass_build_live_sets(struct nv_pc_pass
*ctx
, struct nv_basic_block
*b
)
584 struct nv_instruction
*i
;
587 if (b
->pass_seq
>= ctx
->pc
->pass_seq
)
589 b
->pass_seq
= ctx
->pc
->pass_seq
;
591 /* slight hack for undecidedness: set phi = entry if it's undefined */
595 for (n
= 0; n
< 2; ++n
) {
596 if (!b
->out
[n
] || b
->out
[n
] == b
)
598 ret
= pass_build_live_sets(ctx
, b
->out
[n
]);
603 for (j
= 0; j
< (ctx
->pc
->num_values
+ 31) / 32; ++j
)
604 b
->live_set
[j
] = b
->out
[n
]->live_set
[j
];
606 for (j
= 0; j
< (ctx
->pc
->num_values
+ 31) / 32; ++j
)
607 b
->live_set
[j
] |= b
->out
[n
]->live_set
[j
];
614 bb_live_set_print(ctx
->pc
, b
);
616 for (i
= b
->exit
; i
!= b
->entry
->prev
; i
= i
->prev
) {
617 for (j
= 0; j
< 4; j
++) {
620 live_set_rem(b
, i
->def
[j
]);
622 for (j
= 0; j
< 4; j
++) {
625 live_set_add(b
, i
->src
[j
]->value
);
628 live_set_add(b
, i
->src
[4]->value
);
630 live_set_rem(b
, i
->flags_def
);
632 live_set_add(b
, i
->flags_src
->value
);
634 for (i
= b
->phi
; i
&& i
->opcode
== NV_OP_PHI
; i
= i
->next
)
635 live_set_rem(b
, i
->def
[0]);
637 bb_live_set_print(ctx
->pc
, b
);
642 static void collect_live_values(struct nv_basic_block
*b
, const int n
)
647 if (b
->out
[1]) { /* what to do about back-edges ? */
648 for (i
= 0; i
< n
; ++i
)
649 b
->live_set
[i
] = b
->out
[0]->live_set
[i
] | b
->out
[1]->live_set
[i
];
651 memcpy(b
->live_set
, b
->out
[0]->live_set
, n
* sizeof(uint32_t));
655 memcpy(b
->live_set
, b
->out
[1]->live_set
, n
* sizeof(uint32_t));
657 memset(b
->live_set
, 0, n
* sizeof(uint32_t));
661 /* NOTE: the live intervals of phi functions start at the first non-phi insn. */
663 pass_build_intervals(struct nv_pc_pass
*ctx
, struct nv_basic_block
*b
)
665 struct nv_instruction
*i
, *i_stop
;
667 const int n
= (ctx
->pc
->num_values
+ 31) / 32;
669 /* verify that first block does not have live-in values */
671 for (j
= 0; j
< n
; ++j
)
672 assert(b
->live_set
[j
] == 0);
674 collect_live_values(b
, n
);
676 /* remove live-outs def'd in a parallel block, hopefully they're all phi'd */
677 for (j
= 0; j
< 2; ++j
) {
678 if (!b
->out
[j
] || !b
->out
[j
]->phi
)
680 for (i
= b
->out
[j
]->phi
; i
->opcode
== NV_OP_PHI
; i
= i
->next
) {
681 live_set_rem(b
, i
->def
[0]);
683 for (s
= 0; s
< 4; ++s
) {
686 assert(i
->src
[s
]->value
->insn
);
687 if (nvbb_reachable_by(b
, i
->src
[s
]->value
->insn
->bb
, b
->out
[j
]))
688 live_set_add(b
, i
->src
[s
]->value
);
690 live_set_rem(b
, i
->src
[s
]->value
);
695 /* remaining live-outs are live until the end */
697 for (j
= 0; j
< ctx
->pc
->num_values
; ++j
) {
698 if (!(b
->live_set
[j
/ 32] & (1 << (j
% 32))))
700 add_range(&ctx
->pc
->values
[j
], b
, b
->exit
->serial
+ 1);
701 #ifdef NV50_RA_DEBUG_LIVEI
702 debug_printf("adding range for live value %i: ", j
);
703 livei_print(&ctx
->pc
->values
[j
]);
709 i_stop
= b
->entry
? b
->entry
->prev
: NULL
;
711 /* don't have to include phi functions here (will have 0 live range) */
712 for (i
= b
->exit
; i
!= i_stop
; i
= i
->prev
) {
713 assert(i
->serial
>= b
->phi
->serial
&& i
->serial
<= b
->exit
->serial
);
714 for (j
= 0; j
< 4; ++j
) {
716 live_set_rem(b
, i
->def
[j
]);
719 live_set_rem(b
, i
->flags_def
);
721 for (j
= 0; j
< 5; ++j
) {
722 if (i
->src
[j
] && !live_set_test(b
, i
->src
[j
])) {
723 live_set_add(b
, i
->src
[j
]->value
);
724 add_range(i
->src
[j
]->value
, b
, i
->serial
);
725 #ifdef NV50_RA_DEBUG_LIVEI
726 debug_printf("adding range for source %i (ends living): ",
727 i
->src
[j
]->value
->n
);
728 livei_print(i
->src
[j
]->value
);
732 if (i
->flags_src
&& !live_set_test(b
, i
->flags_src
)) {
733 live_set_add(b
, i
->flags_src
->value
);
734 add_range(i
->flags_src
->value
, b
, i
->serial
);
735 #ifdef NV50_RA_DEBUG_LIVEI
736 debug_printf("adding range for source %i (ends living): ",
737 i
->flags_src
->value
->n
);
738 livei_print(i
->flags_src
->value
);
743 b
->pass_seq
= ctx
->pc
->pass_seq
;
745 if (b
->out
[0] && b
->out
[0]->pass_seq
< ctx
->pc
->pass_seq
)
746 pass_build_intervals(ctx
, b
->out
[0]);
748 if (b
->out
[1] && b
->out
[1]->pass_seq
< ctx
->pc
->pass_seq
)
749 pass_build_intervals(ctx
, b
->out
[1]);
755 nv50_ctor_register_set(struct nv_pc
*pc
, struct register_set
*set
)
757 memset(set
, 0, sizeof(*set
));
759 set
->last
[NV_FILE_GPR
] = 255;
760 set
->last
[NV_FILE_OUT
] = 127;
761 set
->last
[NV_FILE_FLAGS
] = 4;
762 set
->last
[NV_FILE_ADDR
] = 4;
768 insert_ordered_tail(struct nv_value
*list
, struct nv_value
*nval
)
770 struct nv_value
*elem
;
772 for (elem
= list
->prev
;
773 elem
!= list
&& elem
->livei
->bgn
> nval
->livei
->bgn
;
775 /* now elem begins before or at the same time as val */
778 nval
->next
= elem
->next
;
779 elem
->next
->prev
= nval
;
784 pass_linear_scan(struct nv_pc_pass
*ctx
, int iter
)
786 struct nv_instruction
*i
;
787 struct register_set f
, free
;
789 struct nv_value
*cur
, *val
, *tmp
[2];
790 struct nv_value active
, inactive
, handled
, unhandled
;
792 make_empty_list(&active
);
793 make_empty_list(&inactive
);
794 make_empty_list(&handled
);
795 make_empty_list(&unhandled
);
797 nv50_ctor_register_set(ctx
->pc
, &free
);
799 /* joined values should have range = NULL and thus not be added;
800 * also, fixed memory values won't be added because they're not
803 for (n
= 0; n
< ctx
->num_insns
; ++n
) {
806 for (k
= 0; k
< 4; ++k
) {
807 if (i
->def
[k
] && i
->def
[k
]->livei
)
808 insert_ordered_tail(&unhandled
, i
->def
[k
]);
811 debug_printf("skipping def'd value %i: no livei\n", i
->def
[k
]->n
);
813 if (i
->flags_def
&& i
->flags_def
->livei
)
814 insert_ordered_tail(&unhandled
, i
->flags_def
);
817 for (val
= unhandled
.next
; val
!= unhandled
.prev
; val
= val
->next
) {
818 assert(val
->join
== val
);
819 assert(val
->livei
->bgn
<= val
->next
->livei
->bgn
);
822 foreach_s(cur
, tmp
[0], &unhandled
) {
823 remove_from_list(cur
);
825 foreach_s(val
, tmp
[1], &active
) {
826 if (livei_end(val
) <= cur
->livei
->bgn
) {
827 reg_release(&free
, val
);
828 move_to_head(&handled
, val
);
830 if (!livei_contains(val
, cur
->livei
->bgn
)) {
831 reg_release(&free
, val
);
832 move_to_head(&inactive
, val
);
836 foreach_s(val
, tmp
[1], &inactive
) {
837 if (livei_end(val
) <= cur
->livei
->bgn
)
838 move_to_head(&handled
, val
);
840 if (livei_contains(val
, cur
->livei
->bgn
)) {
841 reg_occupy(&free
, val
);
842 move_to_head(&active
, val
);
848 foreach(val
, &inactive
)
849 if (livei_have_overlap(val
, cur
))
852 foreach(val
, &unhandled
)
853 if (val
->reg
.id
>= 0 && livei_have_overlap(val
, cur
))
856 if (cur
->reg
.id
< 0) {
859 if (nv_is_vector_op(cur
->insn
->opcode
))
860 mem
= !reg_assign(&f
, &cur
->insn
->def
[0], 4);
863 mem
= !reg_assign(&f
, &cur
, 1);
866 NOUVEAU_ERR("out of registers\n");
870 insert_at_head(&active
, cur
);
871 reg_occupy(&free
, cur
);
878 nv_pc_pass1(struct nv_pc
*pc
, struct nv_basic_block
*root
)
880 struct nv_pc_pass
*ctx
;
883 NV50_DBGMSG("REGISTER ALLOCATION - entering\n");
885 ctx
= CALLOC_STRUCT(nv_pc_pass
);
890 ctx
->insns
= CALLOC(NV_PC_MAX_INSTRUCTIONS
, sizeof(struct nv_instruction
*));
897 ret
= pass_generate_phi_movs(ctx
, root
);
900 for (i
= 0; i
< pc
->loop_nesting_bound
; ++i
) {
902 ret
= pass_build_live_sets(ctx
, root
);
903 assert(!ret
&& "live sets");
905 NOUVEAU_ERR("failed to build live sets (iteration %d)\n", i
);
911 nv_pc_pass_in_order(root
, pass_order_instructions
, ctx
);
914 ret
= pass_build_intervals(ctx
, root
);
915 assert(!ret
&& "build intervals");
917 NOUVEAU_ERR("failed to build live intervals\n");
921 #ifdef NV50_RA_DEBUG_LIVEI
922 for (i
= 0; i
< pc
->num_values
; ++i
)
923 livei_print(&pc
->values
[i
]);
926 ret
= pass_join_values(ctx
, 0);
929 ret
= pass_linear_scan(ctx
, 0);
932 ret
= pass_join_values(ctx
, 1);
935 ret
= pass_join_values(ctx
, 2);
938 ret
= pass_linear_scan(ctx
, 1);
942 for (i
= 0; i
< pc
->num_values
; ++i
)
943 livei_release(&pc
->values
[i
]);
945 NV50_DBGMSG("REGISTER ALLOCATION - leaving\n");
954 nv_pc_exec_pass1(struct nv_pc
*pc
)
958 for (i
= 0; i
< pc
->num_subroutines
+ 1; ++i
)
959 if (pc
->root
[i
] && (ret
= nv_pc_pass1(pc
, pc
->root
[i
])))