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_fs_live_variables.h"
33 #define MAX_INSTRUCTION (1 << 30)
35 /** @file brw_fs_live_variables.cpp
37 * Support for calculating liveness information about virtual GRFs.
39 * This produces a live interval for each whole virtual GRF. We could
40 * choose to expose per-component live intervals for VGRFs of size > 1,
41 * but we currently do not. It is easier for the consumers of this
42 * information to work with whole VGRFs.
44 * However, we internally track use/def information at the per-GRF level for
45 * greater accuracy. Large VGRFs may be accessed piecemeal over many
46 * (possibly non-adjacent) instructions. In this case, examining a single
47 * instruction is insufficient to decide whether a whole VGRF is ultimately
48 * used or defined. Tracking individual components allows us to easily
49 * assemble this information.
51 * See Muchnick's Advanced Compiler Design and Implementation, section
56 fs_live_variables::setup_one_read(struct block_data
*bd
, fs_inst
*inst
,
57 int ip
, const fs_reg
®
)
59 int var
= var_from_reg(reg
);
60 assert(var
< num_vars
);
62 start
[var
] = MIN2(start
[var
], ip
);
63 end
[var
] = MAX2(end
[var
], ip
);
65 /* The use[] bitset marks when the block makes use of a variable (VGRF
66 * channel) without having completely defined that variable within the
69 if (!BITSET_TEST(bd
->def
, var
))
70 BITSET_SET(bd
->use
, var
);
74 fs_live_variables::setup_one_write(struct block_data
*bd
, fs_inst
*inst
,
75 int ip
, const fs_reg
®
)
77 int var
= var_from_reg(reg
);
78 assert(var
< num_vars
);
80 start
[var
] = MIN2(start
[var
], ip
);
81 end
[var
] = MAX2(end
[var
], ip
);
83 /* The def[] bitset marks when an initialization in a block completely
84 * screens off previous updates of that variable (VGRF channel).
86 if (inst
->dst
.file
== VGRF
) {
87 if (!inst
->is_partial_write() && !BITSET_TEST(bd
->use
, var
))
88 BITSET_SET(bd
->def
, var
);
90 BITSET_SET(bd
->defout
, var
);
95 * Sets up the use[] and def[] bitsets.
97 * The basic-block-level live variable analysis needs to know which
98 * variables get used before they're completely defined, and which
99 * variables are completely defined before they're used.
101 * These are tracked at the per-component level, rather than whole VGRFs.
104 fs_live_variables::setup_def_use()
108 foreach_block (block
, cfg
) {
109 assert(ip
== block
->start_ip
);
111 assert(cfg
->blocks
[block
->num
- 1]->end_ip
== ip
- 1);
113 struct block_data
*bd
= &block_data
[block
->num
];
115 foreach_inst_in_block(fs_inst
, inst
, block
) {
116 /* Set use[] for this instruction */
117 for (unsigned int i
= 0; i
< inst
->sources
; i
++) {
118 fs_reg reg
= inst
->src
[i
];
120 if (reg
.file
!= VGRF
)
123 for (unsigned j
= 0; j
< regs_read(inst
, i
); j
++) {
124 setup_one_read(bd
, inst
, ip
, reg
);
125 reg
.offset
+= REG_SIZE
;
129 bd
->flag_use
[0] |= inst
->flags_read(devinfo
) & ~bd
->flag_def
[0];
131 /* Set def[] for this instruction */
132 if (inst
->dst
.file
== VGRF
) {
133 fs_reg reg
= inst
->dst
;
134 for (unsigned j
= 0; j
< regs_written(inst
); j
++) {
135 setup_one_write(bd
, inst
, ip
, reg
);
136 reg
.offset
+= REG_SIZE
;
140 if (!inst
->predicate
&& inst
->exec_size
>= 8)
141 bd
->flag_def
[0] |= inst
->flags_written() & ~bd
->flag_use
[0];
149 * The algorithm incrementally sets bits in liveout and livein,
150 * propagating it through control flow. It will eventually terminate
151 * because it only ever adds bits, and stops when no bits are added in
155 fs_live_variables::compute_live_variables()
162 foreach_block_reverse (block
, cfg
) {
163 struct block_data
*bd
= &block_data
[block
->num
];
166 foreach_list_typed(bblock_link
, child_link
, link
, &block
->children
) {
167 struct block_data
*child_bd
= &block_data
[child_link
->block
->num
];
169 for (int i
= 0; i
< bitset_words
; i
++) {
170 BITSET_WORD new_liveout
= (child_bd
->livein
[i
] &
173 bd
->liveout
[i
] |= new_liveout
;
177 BITSET_WORD new_liveout
= (child_bd
->flag_livein
[0] &
178 ~bd
->flag_liveout
[0]);
180 bd
->flag_liveout
[0] |= new_liveout
;
186 for (int i
= 0; i
< bitset_words
; i
++) {
187 BITSET_WORD new_livein
= (bd
->use
[i
] |
190 if (new_livein
& ~bd
->livein
[i
]) {
191 bd
->livein
[i
] |= new_livein
;
195 BITSET_WORD new_livein
= (bd
->flag_use
[0] |
196 (bd
->flag_liveout
[0] &
198 if (new_livein
& ~bd
->flag_livein
[0]) {
199 bd
->flag_livein
[0] |= new_livein
;
205 /* Propagate defin and defout down the CFG to calculate the union of live
206 * variables potentially defined along any possible control flow path.
211 foreach_block (block
, cfg
) {
212 const struct block_data
*bd
= &block_data
[block
->num
];
214 foreach_list_typed(bblock_link
, child_link
, link
, &block
->children
) {
215 struct block_data
*child_bd
= &block_data
[child_link
->block
->num
];
217 for (int i
= 0; i
< bitset_words
; i
++) {
218 const BITSET_WORD new_def
= bd
->defout
[i
] & ~child_bd
->defin
[i
];
219 child_bd
->defin
[i
] |= new_def
;
220 child_bd
->defout
[i
] |= new_def
;
229 * Extend the start/end ranges for each variable to account for the
230 * new information calculated from control flow.
233 fs_live_variables::compute_start_end()
235 foreach_block (block
, cfg
) {
236 struct block_data
*bd
= &block_data
[block
->num
];
238 for (int w
= 0; w
< bitset_words
; w
++) {
239 BITSET_WORD livedefin
= bd
->livein
[w
] & bd
->defin
[w
];
240 BITSET_WORD livedefout
= bd
->liveout
[w
] & bd
->defout
[w
];
241 BITSET_WORD livedefinout
= livedefin
| livedefout
;
242 while (livedefinout
) {
243 unsigned b
= u_bit_scan(&livedefinout
);
244 unsigned i
= w
* BITSET_WORDBITS
+ b
;
245 if (livedefin
& (1u << b
)) {
246 start
[i
] = MIN2(start
[i
], block
->start_ip
);
247 end
[i
] = MAX2(end
[i
], block
->start_ip
);
249 if (livedefout
& (1u << b
)) {
250 start
[i
] = MIN2(start
[i
], block
->end_ip
);
251 end
[i
] = MAX2(end
[i
], block
->end_ip
);
258 fs_live_variables::fs_live_variables(const backend_shader
*s
)
259 : devinfo(s
->devinfo
), cfg(s
->cfg
)
261 mem_ctx
= ralloc_context(NULL
);
263 num_vgrfs
= s
->alloc
.count
;
265 var_from_vgrf
= rzalloc_array(mem_ctx
, int, num_vgrfs
);
266 for (int i
= 0; i
< num_vgrfs
; i
++) {
267 var_from_vgrf
[i
] = num_vars
;
268 num_vars
+= s
->alloc
.sizes
[i
];
271 vgrf_from_var
= rzalloc_array(mem_ctx
, int, num_vars
);
272 for (int i
= 0; i
< num_vgrfs
; i
++) {
273 for (unsigned j
= 0; j
< s
->alloc
.sizes
[i
]; j
++) {
274 vgrf_from_var
[var_from_vgrf
[i
] + j
] = i
;
278 start
= ralloc_array(mem_ctx
, int, num_vars
);
279 end
= rzalloc_array(mem_ctx
, int, num_vars
);
280 for (int i
= 0; i
< num_vars
; i
++) {
281 start
[i
] = MAX_INSTRUCTION
;
285 vgrf_start
= ralloc_array(mem_ctx
, int, num_vgrfs
);
286 vgrf_end
= ralloc_array(mem_ctx
, int, num_vgrfs
);
287 for (int i
= 0; i
< num_vgrfs
; i
++) {
288 vgrf_start
[i
] = MAX_INSTRUCTION
;
292 block_data
= rzalloc_array(mem_ctx
, struct block_data
, cfg
->num_blocks
);
294 bitset_words
= BITSET_WORDS(num_vars
);
295 for (int i
= 0; i
< cfg
->num_blocks
; i
++) {
296 block_data
[i
].def
= rzalloc_array(mem_ctx
, BITSET_WORD
, bitset_words
);
297 block_data
[i
].use
= rzalloc_array(mem_ctx
, BITSET_WORD
, bitset_words
);
298 block_data
[i
].livein
= rzalloc_array(mem_ctx
, BITSET_WORD
, bitset_words
);
299 block_data
[i
].liveout
= rzalloc_array(mem_ctx
, BITSET_WORD
, bitset_words
);
300 block_data
[i
].defin
= rzalloc_array(mem_ctx
, BITSET_WORD
, bitset_words
);
301 block_data
[i
].defout
= rzalloc_array(mem_ctx
, BITSET_WORD
, bitset_words
);
303 block_data
[i
].flag_def
[0] = 0;
304 block_data
[i
].flag_use
[0] = 0;
305 block_data
[i
].flag_livein
[0] = 0;
306 block_data
[i
].flag_liveout
[0] = 0;
310 compute_live_variables();
313 /* Merge the per-component live ranges to whole VGRF live ranges. */
314 for (int i
= 0; i
< num_vars
; i
++) {
315 const unsigned vgrf
= vgrf_from_var
[i
];
316 vgrf_start
[vgrf
] = MIN2(vgrf_start
[vgrf
], start
[i
]);
317 vgrf_end
[vgrf
] = MAX2(vgrf_end
[vgrf
], end
[i
]);
321 fs_live_variables::~fs_live_variables()
323 ralloc_free(mem_ctx
);
327 fs_visitor::invalidate_live_intervals()
329 ralloc_free(live_intervals
);
330 live_intervals
= NULL
;
334 * Compute the live intervals for each virtual GRF.
336 * This uses the per-component use/def data, but combines it to produce
337 * information about whole VGRFs.
340 fs_visitor::calculate_live_intervals()
342 if (this->live_intervals
)
345 this->live_intervals
= new(mem_ctx
) fs_live_variables(this);
349 fs_live_variables::vars_interfere(int a
, int b
) const
351 return !(end
[b
] <= start
[a
] ||
356 fs_live_variables::vgrfs_interfere(int a
, int b
) const
358 return !(vgrf_end
[a
] <= vgrf_start
[b
] ||
359 vgrf_end
[b
] <= vgrf_start
[a
]);