2 * Copyright © 2012 Intel Corporation
3 * Copyright © 2016 Broadcom
5 * Permission is hereby granted, free of charge, to any person obtaining a
6 * copy of this software and associated documentation files (the "Software"),
7 * to deal in the Software without restriction, including without limitation
8 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
9 * and/or sell copies of the Software, and to permit persons to whom the
10 * Software is furnished to do so, subject to the following conditions:
12 * The above copyright notice and this permission notice (including the next
13 * paragraph) shall be included in all copies or substantial portions of the
16 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
17 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
18 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
19 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
20 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
21 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
25 #define MAX_INSTRUCTION (1 << 30)
27 #include "util/ralloc.h"
28 #include "util/register_allocate.h"
29 #include "vc4_context.h"
32 struct partial_update_state
{
33 struct qinst
*insts
[4];
38 int_hash(const void *key
)
40 return _mesa_hash_data(key
, sizeof(int));
44 int_compare(const void *key1
, const void *key2
)
46 return *(const int *)key1
== *(const int *)key2
;
50 qir_reg_to_var(struct qreg reg
)
52 if (reg
.file
== QFILE_TEMP
)
59 qir_setup_use(struct vc4_compile
*c
, struct qblock
*block
, int ip
,
62 int var
= qir_reg_to_var(src
);
66 c
->temp_start
[var
] = MIN2(c
->temp_start
[var
], ip
);
67 c
->temp_end
[var
] = MAX2(c
->temp_end
[var
], ip
);
69 /* The use[] bitset marks when the block makes
70 * use of a variable without having completely
71 * defined that variable within the block.
73 if (!BITSET_TEST(block
->def
, var
))
74 BITSET_SET(block
->use
, var
);
77 static struct partial_update_state
*
78 get_partial_update_state(struct hash_table
*partial_update_ht
,
81 struct hash_entry
*entry
=
82 _mesa_hash_table_search(partial_update_ht
,
87 struct partial_update_state
*state
=
88 rzalloc(partial_update_ht
, struct partial_update_state
);
90 _mesa_hash_table_insert(partial_update_ht
, &inst
->dst
.index
, state
);
96 qir_setup_def(struct vc4_compile
*c
, struct qblock
*block
, int ip
,
97 struct hash_table
*partial_update_ht
, struct qinst
*inst
)
99 /* The def[] bitset marks when an initialization in a
100 * block completely screens off previous updates of
103 int var
= qir_reg_to_var(inst
->dst
);
107 c
->temp_start
[var
] = MIN2(c
->temp_start
[var
], ip
);
108 c
->temp_end
[var
] = MAX2(c
->temp_end
[var
], ip
);
110 /* If we've already tracked this as a def, or already used it within
111 * the block, there's nothing to do.
113 if (BITSET_TEST(block
->use
, var
) || BITSET_TEST(block
->def
, var
))
116 /* Easy, common case: unconditional full register update. */
117 if (inst
->cond
== QPU_COND_ALWAYS
&& !inst
->dst
.pack
) {
118 BITSET_SET(block
->def
, var
);
122 /* Finally, look at the condition code and packing and mark it as a
123 * def. We need to make sure that we understand sequences
136 * as defining the temp within the block, because otherwise dst's live
137 * range will get extended up the control flow to the top of the
140 struct partial_update_state
*state
=
141 get_partial_update_state(partial_update_ht
, inst
);
142 uint8_t mask
= qir_channels_written(inst
);
144 if (inst
->cond
== QPU_COND_ALWAYS
) {
145 state
->channels
|= mask
;
147 for (int i
= 0; i
< 4; i
++) {
148 if (!(mask
& (1 << i
)))
151 if (state
->insts
[i
] &&
152 state
->insts
[i
]->cond
==
153 qpu_cond_complement(inst
->cond
))
154 state
->channels
|= 1 << i
;
156 state
->insts
[i
] = inst
;
160 if (state
->channels
== 0xf)
161 BITSET_SET(block
->def
, var
);
165 sf_state_clear(struct hash_table
*partial_update_ht
)
167 struct hash_entry
*entry
;
169 hash_table_foreach(partial_update_ht
, entry
) {
170 struct partial_update_state
*state
= entry
->data
;
172 for (int i
= 0; i
< 4; i
++) {
173 if (state
->insts
[i
] && state
->insts
[i
]->cond
)
174 state
->insts
[i
] = NULL
;
179 /* Sets up the def/use arrays for when variables are used-before-defined or
180 * defined-before-used in the block.
182 * Also initializes the temp_start/temp_end to cover just the instruction IPs
183 * where the variable is used, which will be extended later in
184 * qir_compute_start_end().
187 qir_setup_def_use(struct vc4_compile
*c
)
189 struct hash_table
*partial_update_ht
=
190 _mesa_hash_table_create(c
, int_hash
, int_compare
);
193 qir_for_each_block(block
, c
) {
194 block
->start_ip
= ip
;
196 _mesa_hash_table_clear(partial_update_ht
, NULL
);
198 qir_for_each_inst(inst
, block
) {
199 for (int i
= 0; i
< qir_get_op_nsrc(inst
->op
); i
++)
200 qir_setup_use(c
, block
, ip
, inst
->src
[i
]);
202 qir_setup_def(c
, block
, ip
, partial_update_ht
, inst
);
205 sf_state_clear(partial_update_ht
);
210 /* The payload registers have values
211 * implicitly loaded at the start of the
214 if (inst
->dst
.file
== QFILE_TEMP
)
215 c
->temp_start
[inst
->dst
.index
] = 0;
225 _mesa_hash_table_destroy(partial_update_ht
, NULL
);
229 qir_live_variables_dataflow(struct vc4_compile
*c
, int bitset_words
)
233 qir_for_each_block_rev(block
, c
) {
234 /* Update live_out: Any successor using the variable
235 * on entrance needs us to have the variable live on
238 qir_for_each_successor(succ
, block
) {
239 for (int i
= 0; i
< bitset_words
; i
++) {
240 BITSET_WORD new_live_out
= (succ
->live_in
[i
] &
241 ~block
->live_out
[i
]);
243 block
->live_out
[i
] |= new_live_out
;
250 for (int i
= 0; i
< bitset_words
; i
++) {
251 BITSET_WORD new_live_in
= (block
->use
[i
] |
252 (block
->live_out
[i
] &
254 if (new_live_in
& ~block
->live_in
[i
]) {
255 block
->live_in
[i
] |= new_live_in
;
265 * Extend the start/end ranges for each variable to account for the
266 * new information calculated from control flow.
269 qir_compute_start_end(struct vc4_compile
*c
, int num_vars
)
271 qir_for_each_block(block
, c
) {
272 for (int i
= 0; i
< num_vars
; i
++) {
273 if (BITSET_TEST(block
->live_in
, i
)) {
274 c
->temp_start
[i
] = MIN2(c
->temp_start
[i
],
276 c
->temp_end
[i
] = MAX2(c
->temp_end
[i
],
280 if (BITSET_TEST(block
->live_out
, i
)) {
281 c
->temp_start
[i
] = MIN2(c
->temp_start
[i
],
283 c
->temp_end
[i
] = MAX2(c
->temp_end
[i
],
291 qir_calculate_live_intervals(struct vc4_compile
*c
)
293 int bitset_words
= BITSET_WORDS(c
->num_temps
);
295 c
->temp_start
= reralloc(c
, c
->temp_start
, int, c
->num_temps
);
296 c
->temp_end
= reralloc(c
, c
->temp_end
, int, c
->num_temps
);
298 for (int i
= 0; i
< c
->num_temps
; i
++) {
299 c
->temp_start
[i
] = MAX_INSTRUCTION
;
303 qir_for_each_block(block
, c
) {
304 block
->def
= reralloc(c
, block
->def
, BITSET_WORD
, bitset_words
);
305 block
->use
= reralloc(c
, block
->use
, BITSET_WORD
, bitset_words
);
306 block
->live_in
= reralloc(c
, block
->live_in
, BITSET_WORD
, bitset_words
);
307 block
->live_out
= reralloc(c
, block
->live_out
, BITSET_WORD
, bitset_words
);
310 qir_setup_def_use(c
);
312 while (qir_live_variables_dataflow(c
, bitset_words
))
315 qir_compute_start_end(c
, c
->num_temps
);