ca60aa235fe059161d1b399816afd43cfb865893
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 /** @file brw_fs_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 Muchnik's Advanced Compiler Design and Implementation, section
43 * Sets up the use[] and def[] bitsets.
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.
50 fs_live_variables::setup_def_use()
54 for (int b
= 0; b
< cfg
->num_blocks
; b
++) {
55 bblock_t
*block
= cfg
->blocks
[b
];
57 assert(ip
== block
->start_ip
);
59 assert(cfg
->blocks
[b
- 1]->end_ip
== ip
- 1);
61 for (fs_inst
*inst
= (fs_inst
*)block
->start
;
62 inst
!= block
->end
->next
;
63 inst
= (fs_inst
*)inst
->next
) {
65 /* Set use[] for this instruction */
66 for (unsigned int i
= 0; i
< 3; i
++) {
67 if (inst
->src
[i
].file
== GRF
) {
68 int reg
= inst
->src
[i
].reg
;
70 if (!BITSET_TEST(bd
[b
].def
, reg
))
71 BITSET_SET(bd
[b
].use
, reg
);
75 /* Check for unconditional writes to whole registers. These
76 * are the things that screen off preceding definitions of a
77 * variable, and thus qualify for being in def[].
79 if (inst
->dst
.file
== GRF
&&
80 inst
->regs_written
== v
->virtual_grf_sizes
[inst
->dst
.reg
] &&
82 !inst
->force_uncompressed
&&
83 !inst
->force_sechalf
) {
84 int reg
= inst
->dst
.reg
;
85 if (!BITSET_TEST(bd
[b
].use
, reg
))
86 BITSET_SET(bd
[b
].def
, reg
);
95 * The algorithm incrementally sets bits in liveout and livein,
96 * propagating it through control flow. It will eventually terminate
97 * because it only ever adds bits, and stops when no bits are added in
101 fs_live_variables::compute_live_variables()
108 for (int b
= 0; b
< cfg
->num_blocks
; b
++) {
110 for (int i
= 0; i
< bitset_words
; i
++) {
111 BITSET_WORD new_livein
= (bd
[b
].use
[i
] |
112 (bd
[b
].liveout
[i
] & ~bd
[b
].def
[i
]));
113 if (new_livein
& ~bd
[b
].livein
[i
]) {
114 bd
[b
].livein
[i
] |= new_livein
;
120 foreach_list(block_node
, &cfg
->blocks
[b
]->children
) {
121 bblock_link
*link
= (bblock_link
*)block_node
;
122 bblock_t
*block
= link
->block
;
124 for (int i
= 0; i
< bitset_words
; i
++) {
125 BITSET_WORD new_liveout
= (bd
[block
->block_num
].livein
[i
] &
128 bd
[b
].liveout
[i
] |= new_liveout
;
137 fs_live_variables::fs_live_variables(fs_visitor
*v
, cfg_t
*cfg
)
140 mem_ctx
= ralloc_context(cfg
->mem_ctx
);
142 num_vars
= v
->virtual_grf_count
;
143 bd
= rzalloc_array(mem_ctx
, struct block_data
, cfg
->num_blocks
);
145 bitset_words
= BITSET_WORDS(v
->virtual_grf_count
);
146 for (int i
= 0; i
< cfg
->num_blocks
; i
++) {
147 bd
[i
].def
= rzalloc_array(mem_ctx
, BITSET_WORD
, bitset_words
);
148 bd
[i
].use
= rzalloc_array(mem_ctx
, BITSET_WORD
, bitset_words
);
149 bd
[i
].livein
= rzalloc_array(mem_ctx
, BITSET_WORD
, bitset_words
);
150 bd
[i
].liveout
= rzalloc_array(mem_ctx
, BITSET_WORD
, bitset_words
);
154 compute_live_variables();
157 fs_live_variables::~fs_live_variables()
159 ralloc_free(mem_ctx
);
162 #define MAX_INSTRUCTION (1 << 30)
165 fs_visitor::calculate_live_intervals()
167 int num_vars
= this->virtual_grf_count
;
169 if (this->live_intervals_valid
)
172 int *def
= ralloc_array(mem_ctx
, int, num_vars
);
173 int *use
= ralloc_array(mem_ctx
, int, num_vars
);
174 ralloc_free(this->virtual_grf_def
);
175 ralloc_free(this->virtual_grf_use
);
176 this->virtual_grf_def
= def
;
177 this->virtual_grf_use
= use
;
179 for (int i
= 0; i
< num_vars
; i
++) {
180 def
[i
] = MAX_INSTRUCTION
;
184 /* Start by setting up the intervals with no knowledge of control
188 foreach_list(node
, &this->instructions
) {
189 fs_inst
*inst
= (fs_inst
*)node
;
191 for (unsigned int i
= 0; i
< 3; i
++) {
192 if (inst
->src
[i
].file
== GRF
) {
193 int reg
= inst
->src
[i
].reg
;
197 /* In most cases, a register can be written over safely by the
198 * same instruction that is its last use. For a single
199 * instruction, the sources are dereferenced before writing of the
200 * destination starts (naturally). This gets more complicated for
201 * simd16, because the instruction:
203 * mov(16) g4<1>F g4<8,8,1>F g6<8,8,1>F
205 * is actually decoded in hardware as:
207 * mov(8) g4<1>F g4<8,8,1>F g6<8,8,1>F
208 * mov(8) g5<1>F g5<8,8,1>F g7<8,8,1>F
210 * Which is safe. However, if we have uniform accesses
211 * happening, we get into trouble:
213 * mov(8) g4<1>F g4<0,1,0>F g6<8,8,1>F
214 * mov(8) g5<1>F g4<0,1,0>F g7<8,8,1>F
216 * Now our destination for the first instruction overwrote the
217 * second instruction's src0, and we get garbage for those 8
218 * pixels. There's a similar issue for the pre-gen6
219 * pixel_x/pixel_y, which are registers of 16-bit values and thus
220 * would get stomped by the first decode as well.
222 if (dispatch_width
== 16 && (inst
->src
[i
].smear
||
223 (this->pixel_x
.reg
== reg
||
224 this->pixel_y
.reg
== reg
))) {
230 if (inst
->dst
.file
== GRF
) {
231 int reg
= inst
->dst
.reg
;
233 def
[reg
] = MIN2(def
[reg
], ip
);
239 /* Now, extend those intervals using our analysis of control flow. */
241 fs_live_variables
livevars(this, &cfg
);
243 for (int b
= 0; b
< cfg
.num_blocks
; b
++) {
244 for (int i
= 0; i
< num_vars
; i
++) {
245 if (BITSET_TEST(livevars
.bd
[b
].livein
, i
)) {
246 def
[i
] = MIN2(def
[i
], cfg
.blocks
[b
]->start_ip
);
247 use
[i
] = MAX2(use
[i
], cfg
.blocks
[b
]->start_ip
);
250 if (BITSET_TEST(livevars
.bd
[b
].liveout
, i
)) {
251 def
[i
] = MIN2(def
[i
], cfg
.blocks
[b
]->end_ip
);
252 use
[i
] = MAX2(use
[i
], cfg
.blocks
[b
]->end_ip
);
257 this->live_intervals_valid
= true;
259 /* Note in the non-control-flow code above, that we only take def[] as the
260 * first store, and use[] as the last use. We use this in dead code
261 * elimination, to determine when a store never gets used. However, we
262 * also use these arrays to answer the virtual_grf_interferes() question
263 * (live interval analysis), which is used for register coalescing and
264 * register allocation.
266 * So, there's a conflict over what the array should mean: if use[]
267 * considers a def after the last use, then the dead code elimination pass
268 * never does anything (and it's an important pass!). But if we don't
269 * include dead code, then virtual_grf_interferes() lies and we'll do
270 * horrible things like coalesce the register that is dead-code-written
271 * into another register that was live across the dead write (causing the
272 * use of the second register to take the dead write's source value instead
273 * of the coalesced MOV's source value).
275 * To resolve the conflict, immediately after calculating live intervals,
276 * detect dead code, nuke it, and if we changed anything, calculate again
277 * before returning to the caller. Now we happen to produce def[] and
278 * use[] arrays that will work for virtual_grf_interferes().
280 if (dead_code_eliminate())
281 calculate_live_intervals();
285 fs_visitor::virtual_grf_interferes(int a
, int b
)
287 int a_def
= this->virtual_grf_def
[a
], a_use
= this->virtual_grf_use
[a
];
288 int b_def
= this->virtual_grf_def
[b
], b_use
= this->virtual_grf_use
[b
];
290 /* If there's dead code (def but not use), it would break our test
291 * unless we consider it used.
293 if ((a_use
== -1 && a_def
!= MAX_INSTRUCTION
) ||
294 (b_use
== -1 && b_def
!= MAX_INSTRUCTION
)) {
298 int start
= MAX2(a_def
, b_def
);
299 int end
= MIN2(a_use
, b_use
);