2 * Copyright © 2012 Intel Corporation
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 (including the next
12 * paragraph) shall be included in all copies or substantial portions of the
15 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
16 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
17 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
18 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
19 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
20 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
24 * Eric Anholt <eric@anholt.net>
29 #include "brw_vec4_live_variables.h"
33 /** @file brw_vec4_live_variables.cpp
35 * Support for computing at the basic block level which variables
36 * (virtual GRFs in our case) are live at entry and exit.
38 * See Muchnick's Advanced Compiler Design and Implementation, section
43 * Sets up the use[] and def[] arrays.
45 * The basic-block-level live variable analysis needs to know which
46 * variables get used before they're completely defined, and which
47 * variables are completely defined before they're used.
49 * We independently track each channel of a vec4. This is because we need to
50 * be able to recognize a sequence like:
55 * MUL result.xy tmp.xy e.xy
58 * as having tmp live only across that sequence (assuming it's used nowhere
59 * else), because it's a common pattern. A more conservative approach that
60 * doesn't get tmp marked a deffed in this block will tend to result in
64 vec4_live_variables::setup_def_use()
68 for (int b
= 0; b
< cfg
->num_blocks
; b
++) {
69 bblock_t
*block
= cfg
->blocks
[b
];
71 assert(ip
== block
->start_ip
);
73 assert(cfg
->blocks
[b
- 1]->end_ip
== ip
- 1);
75 foreach_inst_in_block(vec4_instruction
, inst
, block
) {
76 /* Set use[] for this instruction */
77 for (unsigned int i
= 0; i
< 3; i
++) {
78 if (inst
->src
[i
].file
== GRF
) {
79 int reg
= inst
->src
[i
].reg
;
81 for (int j
= 0; j
< 4; j
++) {
82 int c
= BRW_GET_SWZ(inst
->src
[i
].swizzle
, j
);
83 if (!BITSET_TEST(bd
[b
].def
, reg
* 4 + c
))
84 BITSET_SET(bd
[b
].use
, reg
* 4 + c
);
89 /* Check for unconditional writes to whole registers. These
90 * are the things that screen off preceding definitions of a
91 * variable, and thus qualify for being in def[].
93 if (inst
->dst
.file
== GRF
&&
94 v
->virtual_grf_sizes
[inst
->dst
.reg
] == 1 &&
96 for (int c
= 0; c
< 4; c
++) {
97 if (inst
->dst
.writemask
& (1 << c
)) {
98 int reg
= inst
->dst
.reg
;
99 if (!BITSET_TEST(bd
[b
].use
, reg
* 4 + c
))
100 BITSET_SET(bd
[b
].def
, reg
* 4 + c
);
111 * The algorithm incrementally sets bits in liveout and livein,
112 * propagating it through control flow. It will eventually terminate
113 * because it only ever adds bits, and stops when no bits are added in
117 vec4_live_variables::compute_live_variables()
124 for (int b
= 0; b
< cfg
->num_blocks
; b
++) {
126 for (int i
= 0; i
< bitset_words
; i
++) {
127 BITSET_WORD new_livein
= (bd
[b
].use
[i
] |
128 (bd
[b
].liveout
[i
] & ~bd
[b
].def
[i
]));
129 if (new_livein
& ~bd
[b
].livein
[i
]) {
130 bd
[b
].livein
[i
] |= new_livein
;
136 foreach_list_typed(bblock_link
, link
, link
, &cfg
->blocks
[b
]->children
) {
137 bblock_t
*block
= link
->block
;
139 for (int i
= 0; i
< bitset_words
; i
++) {
140 BITSET_WORD new_liveout
= (bd
[block
->block_num
].livein
[i
] &
143 bd
[b
].liveout
[i
] |= new_liveout
;
152 vec4_live_variables::vec4_live_variables(vec4_visitor
*v
, cfg_t
*cfg
)
155 mem_ctx
= ralloc_context(NULL
);
157 num_vars
= v
->virtual_grf_count
* 4;
158 bd
= rzalloc_array(mem_ctx
, struct block_data
, cfg
->num_blocks
);
160 bitset_words
= BITSET_WORDS(num_vars
);
161 for (int i
= 0; i
< cfg
->num_blocks
; i
++) {
162 bd
[i
].def
= rzalloc_array(mem_ctx
, BITSET_WORD
, bitset_words
);
163 bd
[i
].use
= rzalloc_array(mem_ctx
, BITSET_WORD
, bitset_words
);
164 bd
[i
].livein
= rzalloc_array(mem_ctx
, BITSET_WORD
, bitset_words
);
165 bd
[i
].liveout
= rzalloc_array(mem_ctx
, BITSET_WORD
, bitset_words
);
169 compute_live_variables();
172 vec4_live_variables::~vec4_live_variables()
174 ralloc_free(mem_ctx
);
177 #define MAX_INSTRUCTION (1 << 30)
180 * Computes a conservative start/end of the live intervals for each virtual GRF.
182 * We could expose per-channel live intervals to the consumer based on the
183 * information we computed in vec4_live_variables, except that our only
184 * current user is virtual_grf_interferes(). So we instead union the
185 * per-channel ranges into a per-vgrf range for virtual_grf_start[] and
188 * We could potentially have virtual_grf_interferes() do the test per-channel,
189 * which would let some interesting register allocation occur (particularly on
190 * code-generated GLSL sequences from the Cg compiler which does register
191 * allocation at the GLSL level and thus reuses components of the variable
192 * with distinct lifetimes). But right now the complexity of doing so doesn't
193 * seem worth it, since having virtual_grf_interferes() be cheap is important
194 * for register allocation performance.
197 vec4_visitor::calculate_live_intervals()
199 if (this->live_intervals_valid
)
202 int *start
= ralloc_array(mem_ctx
, int, this->virtual_grf_count
* 4);
203 int *end
= ralloc_array(mem_ctx
, int, this->virtual_grf_count
* 4);
204 ralloc_free(this->virtual_grf_start
);
205 ralloc_free(this->virtual_grf_end
);
206 this->virtual_grf_start
= start
;
207 this->virtual_grf_end
= end
;
209 for (int i
= 0; i
< this->virtual_grf_count
* 4; i
++) {
210 start
[i
] = MAX_INSTRUCTION
;
214 /* Start by setting up the intervals with no knowledge of control
218 foreach_in_list(vec4_instruction
, inst
, &instructions
) {
219 for (unsigned int i
= 0; i
< 3; i
++) {
220 if (inst
->src
[i
].file
== GRF
) {
221 int reg
= inst
->src
[i
].reg
;
223 for (int j
= 0; j
< 4; j
++) {
224 int c
= BRW_GET_SWZ(inst
->src
[i
].swizzle
, j
);
226 start
[reg
* 4 + c
] = MIN2(start
[reg
* 4 + c
], ip
);
227 end
[reg
* 4 + c
] = ip
;
232 if (inst
->dst
.file
== GRF
) {
233 int reg
= inst
->dst
.reg
;
235 for (int c
= 0; c
< 4; c
++) {
236 if (inst
->dst
.writemask
& (1 << c
)) {
237 start
[reg
* 4 + c
] = MIN2(start
[reg
* 4 + c
], ip
);
238 end
[reg
* 4 + c
] = ip
;
246 /* Now, extend those intervals using our analysis of control flow.
248 * The control flow-aware analysis was done at a channel level, while at
249 * this point we're distilling it down to vgrfs.
252 vec4_live_variables
livevars(this, cfg
);
254 for (int b
= 0; b
< cfg
->num_blocks
; b
++) {
255 for (int i
= 0; i
< livevars
.num_vars
; i
++) {
256 if (BITSET_TEST(livevars
.bd
[b
].livein
, i
)) {
257 start
[i
] = MIN2(start
[i
], cfg
->blocks
[b
]->start_ip
);
258 end
[i
] = MAX2(end
[i
], cfg
->blocks
[b
]->start_ip
);
261 if (BITSET_TEST(livevars
.bd
[b
].liveout
, i
)) {
262 start
[i
] = MIN2(start
[i
], cfg
->blocks
[b
]->end_ip
);
263 end
[i
] = MAX2(end
[i
], cfg
->blocks
[b
]->end_ip
);
268 this->live_intervals_valid
= true;
272 vec4_visitor::invalidate_live_intervals()
274 live_intervals_valid
= false;
280 vec4_visitor::virtual_grf_interferes(int a
, int b
)
282 int start_a
= MIN2(MIN2(virtual_grf_start
[a
* 4 + 0],
283 virtual_grf_start
[a
* 4 + 1]),
284 MIN2(virtual_grf_start
[a
* 4 + 2],
285 virtual_grf_start
[a
* 4 + 3]));
286 int start_b
= MIN2(MIN2(virtual_grf_start
[b
* 4 + 0],
287 virtual_grf_start
[b
* 4 + 1]),
288 MIN2(virtual_grf_start
[b
* 4 + 2],
289 virtual_grf_start
[b
* 4 + 3]));
290 int end_a
= MAX2(MAX2(virtual_grf_end
[a
* 4 + 0],
291 virtual_grf_end
[a
* 4 + 1]),
292 MAX2(virtual_grf_end
[a
* 4 + 2],
293 virtual_grf_end
[a
* 4 + 3]));
294 int end_b
= MAX2(MAX2(virtual_grf_end
[b
* 4 + 0],
295 virtual_grf_end
[b
* 4 + 1]),
296 MAX2(virtual_grf_end
[b
* 4 + 2],
297 virtual_grf_end
[b
* 4 + 3]));
298 return !(end_a
<= start_b
||