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-component
45 * (reg_offset) level for greater accuracy. Large VGRFs may be accessed
46 * piecemeal over many (possibly non-adjacent) instructions. In this case,
47 * examining a single instruction is insufficient to decide whether a whole
48 * VGRF is ultimately used or defined. Tracking individual components
49 * allows us to easily assemble this information.
51 * See Muchnick's Advanced Compiler Design and Implementation, section
56 fs_live_variables::setup_one_read(bblock_t
*block
, fs_inst
*inst
,
59 int var
= var_from_vgrf
[reg
.reg
] + reg
.reg_offset
;
60 assert(var
< num_vars
);
62 /* In most cases, a register can be written over safely by the
63 * same instruction that is its last use. For a single
64 * instruction, the sources are dereferenced before writing of the
65 * destination starts (naturally). This gets more complicated for
66 * simd16, because the instruction:
68 * add(16) g4<1>F g4<8,8,1>F g6<8,8,1>F
70 * is actually decoded in hardware as:
72 * add(8) g4<1>F g4<8,8,1>F g6<8,8,1>F
73 * add(8) g5<1>F g5<8,8,1>F g7<8,8,1>F
75 * Which is safe. However, if we have uniform accesses
76 * happening, we get into trouble:
78 * add(8) g4<1>F g4<0,1,0>F g6<8,8,1>F
79 * add(8) g5<1>F g4<0,1,0>F g7<8,8,1>F
81 * Now our destination for the first instruction overwrote the
82 * second instruction's src0, and we get garbage for those 8
83 * pixels. There's a similar issue for the pre-gen6
84 * pixel_x/pixel_y, which are registers of 16-bit values and thus
85 * would get stomped by the first decode as well.
88 if (v
->dispatch_width
== 16 && (reg
.stride
== 0 ||
89 (v
->pixel_x
.reg
== reg
.reg
||
90 v
->pixel_y
.reg
== reg
.reg
))) {
94 start
[var
] = MIN2(start
[var
], ip
);
95 end
[var
] = MAX2(end
[var
], end_ip
);
97 /* The use[] bitset marks when the block makes use of a variable (VGRF
98 * channel) without having completely defined that variable within the
101 if (!BITSET_TEST(bd
[block
->block_num
].def
, var
))
102 BITSET_SET(bd
[block
->block_num
].use
, var
);
106 fs_live_variables::setup_one_write(bblock_t
*block
, fs_inst
*inst
,
109 int var
= var_from_vgrf
[reg
.reg
] + reg
.reg_offset
;
110 assert(var
< num_vars
);
112 start
[var
] = MIN2(start
[var
], ip
);
113 end
[var
] = MAX2(end
[var
], ip
);
115 /* The def[] bitset marks when an initialization in a block completely
116 * screens off previous updates of that variable (VGRF channel).
118 if (inst
->dst
.file
== GRF
&& !inst
->is_partial_write()) {
119 if (!BITSET_TEST(bd
[block
->block_num
].use
, var
))
120 BITSET_SET(bd
[block
->block_num
].def
, var
);
125 * Sets up the use[] and def[] bitsets.
127 * The basic-block-level live variable analysis needs to know which
128 * variables get used before they're completely defined, and which
129 * variables are completely defined before they're used.
131 * These are tracked at the per-component level, rather than whole VGRFs.
134 fs_live_variables::setup_def_use()
138 for (int b
= 0; b
< cfg
->num_blocks
; b
++) {
139 bblock_t
*block
= cfg
->blocks
[b
];
141 assert(ip
== block
->start_ip
);
143 assert(cfg
->blocks
[b
- 1]->end_ip
== ip
- 1);
145 for (fs_inst
*inst
= (fs_inst
*)block
->start
;
146 inst
!= block
->end
->next
;
147 inst
= (fs_inst
*)inst
->next
) {
149 /* Set use[] for this instruction */
150 for (unsigned int i
= 0; i
< 3; i
++) {
151 fs_reg reg
= inst
->src
[i
];
156 for (int j
= 0; j
< inst
->regs_read(v
, i
); j
++) {
157 setup_one_read(block
, inst
, ip
, reg
);
162 /* Set def[] for this instruction */
163 if (inst
->dst
.file
== GRF
) {
164 fs_reg reg
= inst
->dst
;
165 for (int j
= 0; j
< inst
->regs_written
; j
++) {
166 setup_one_write(block
, inst
, ip
, reg
);
177 * The algorithm incrementally sets bits in liveout and livein,
178 * propagating it through control flow. It will eventually terminate
179 * because it only ever adds bits, and stops when no bits are added in
183 fs_live_variables::compute_live_variables()
190 for (int b
= 0; b
< cfg
->num_blocks
; b
++) {
192 for (int i
= 0; i
< bitset_words
; i
++) {
193 BITSET_WORD new_livein
= (bd
[b
].use
[i
] |
194 (bd
[b
].liveout
[i
] & ~bd
[b
].def
[i
]));
195 if (new_livein
& ~bd
[b
].livein
[i
]) {
196 bd
[b
].livein
[i
] |= new_livein
;
202 foreach_list(block_node
, &cfg
->blocks
[b
]->children
) {
203 bblock_link
*link
= (bblock_link
*)block_node
;
204 bblock_t
*block
= link
->block
;
206 for (int i
= 0; i
< bitset_words
; i
++) {
207 BITSET_WORD new_liveout
= (bd
[block
->block_num
].livein
[i
] &
210 bd
[b
].liveout
[i
] |= new_liveout
;
220 * Extend the start/end ranges for each variable to account for the
221 * new information calculated from control flow.
224 fs_live_variables::compute_start_end()
226 for (int b
= 0; b
< cfg
->num_blocks
; b
++) {
227 for (int i
= 0; i
< num_vars
; i
++) {
228 if (BITSET_TEST(bd
[b
].livein
, i
)) {
229 start
[i
] = MIN2(start
[i
], cfg
->blocks
[b
]->start_ip
);
230 end
[i
] = MAX2(end
[i
], cfg
->blocks
[b
]->start_ip
);
233 if (BITSET_TEST(bd
[b
].liveout
, i
)) {
234 start
[i
] = MIN2(start
[i
], cfg
->blocks
[b
]->end_ip
);
235 end
[i
] = MAX2(end
[i
], cfg
->blocks
[b
]->end_ip
);
243 fs_live_variables::var_from_reg(fs_reg
*reg
)
245 return var_from_vgrf
[reg
->reg
] + reg
->reg_offset
;
248 fs_live_variables::fs_live_variables(fs_visitor
*v
, cfg_t
*cfg
)
251 mem_ctx
= ralloc_context(NULL
);
253 num_vgrfs
= v
->virtual_grf_count
;
255 var_from_vgrf
= rzalloc_array(mem_ctx
, int, num_vgrfs
);
256 for (int i
= 0; i
< num_vgrfs
; i
++) {
257 var_from_vgrf
[i
] = num_vars
;
258 num_vars
+= v
->virtual_grf_sizes
[i
];
261 vgrf_from_var
= rzalloc_array(mem_ctx
, int, num_vars
);
262 for (int i
= 0; i
< num_vgrfs
; i
++) {
263 for (int j
= 0; j
< v
->virtual_grf_sizes
[i
]; j
++) {
264 vgrf_from_var
[var_from_vgrf
[i
] + j
] = i
;
268 start
= ralloc_array(mem_ctx
, int, num_vars
);
269 end
= rzalloc_array(mem_ctx
, int, num_vars
);
270 for (int i
= 0; i
< num_vars
; i
++) {
271 start
[i
] = MAX_INSTRUCTION
;
275 bd
= rzalloc_array(mem_ctx
, struct block_data
, cfg
->num_blocks
);
277 bitset_words
= BITSET_WORDS(num_vars
);
278 for (int i
= 0; i
< cfg
->num_blocks
; i
++) {
279 bd
[i
].def
= rzalloc_array(mem_ctx
, BITSET_WORD
, bitset_words
);
280 bd
[i
].use
= rzalloc_array(mem_ctx
, BITSET_WORD
, bitset_words
);
281 bd
[i
].livein
= rzalloc_array(mem_ctx
, BITSET_WORD
, bitset_words
);
282 bd
[i
].liveout
= rzalloc_array(mem_ctx
, BITSET_WORD
, bitset_words
);
286 compute_live_variables();
290 fs_live_variables::~fs_live_variables()
292 ralloc_free(mem_ctx
);
296 fs_visitor::invalidate_live_intervals()
298 ralloc_free(live_intervals
);
299 live_intervals
= NULL
;
303 * Compute the live intervals for each virtual GRF.
305 * This uses the per-component use/def data, but combines it to produce
306 * information about whole VGRFs.
309 fs_visitor::calculate_live_intervals()
311 if (this->live_intervals
)
314 int num_vgrfs
= this->virtual_grf_count
;
315 ralloc_free(this->virtual_grf_start
);
316 ralloc_free(this->virtual_grf_end
);
317 virtual_grf_start
= ralloc_array(mem_ctx
, int, num_vgrfs
);
318 virtual_grf_end
= ralloc_array(mem_ctx
, int, num_vgrfs
);
320 for (int i
= 0; i
< num_vgrfs
; i
++) {
321 virtual_grf_start
[i
] = MAX_INSTRUCTION
;
322 virtual_grf_end
[i
] = -1;
325 cfg_t
cfg(&instructions
);
326 this->live_intervals
= new(mem_ctx
) fs_live_variables(this, &cfg
);
328 /* Merge the per-component live ranges to whole VGRF live ranges. */
329 for (int i
= 0; i
< live_intervals
->num_vars
; i
++) {
330 int vgrf
= live_intervals
->vgrf_from_var
[i
];
331 virtual_grf_start
[vgrf
] = MIN2(virtual_grf_start
[vgrf
],
332 live_intervals
->start
[i
]);
333 virtual_grf_end
[vgrf
] = MAX2(virtual_grf_end
[vgrf
],
334 live_intervals
->end
[i
]);
339 fs_live_variables::vars_interfere(int a
, int b
)
341 return !(end
[b
] <= start
[a
] ||
346 fs_visitor::virtual_grf_interferes(int a
, int b
)
348 return !(virtual_grf_end
[a
] <= virtual_grf_start
[b
] ||
349 virtual_grf_end
[b
] <= virtual_grf_start
[a
]);