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 /** @file brw_fs_copy_propagation.cpp
26 * Support for global copy propagation in two passes: A local pass that does
27 * intra-block copy (and constant) propagation, and a global pass that uses
28 * dataflow analysis on the copies available at the end of each block to re-do
29 * local copy propagation with more copies available.
31 * See Muchnick's Advanced Compiler Design and Implementation, section
35 #define ACP_HASH_SIZE 16
37 #include "main/bitset.h"
41 namespace { /* avoid conflict with opt_copy_propagation_elements */
42 struct acp_entry
: public exec_node
{
49 * Which entries in the fs_copy_prop_dataflow acp table are live at the
50 * start of this block. This is the useful output of the analysis, since
51 * it lets us plug those into the local copy propagation on the second
57 * Which entries in the fs_copy_prop_dataflow acp table are live at the end
58 * of this block. This is done in initial setup from the per-block acps
59 * returned by the first local copy prop pass.
64 * Which entries in the fs_copy_prop_dataflow acp table are generated by
65 * instructions in this block which reach the end of the block without
71 * Which entries in the fs_copy_prop_dataflow acp table are killed over the
72 * course of this block.
77 class fs_copy_prop_dataflow
80 fs_copy_prop_dataflow(void *mem_ctx
, cfg_t
*cfg
,
81 exec_list
*out_acp
[ACP_HASH_SIZE
]);
83 void setup_initial_values();
86 void dump_block_data() const;
95 struct block_data
*bd
;
97 } /* anonymous namespace */
99 fs_copy_prop_dataflow::fs_copy_prop_dataflow(void *mem_ctx
, cfg_t
*cfg
,
100 exec_list
*out_acp
[ACP_HASH_SIZE
])
101 : mem_ctx(mem_ctx
), cfg(cfg
)
103 bd
= rzalloc_array(mem_ctx
, struct block_data
, cfg
->num_blocks
);
106 for (int b
= 0; b
< cfg
->num_blocks
; b
++) {
107 for (int i
= 0; i
< ACP_HASH_SIZE
; i
++) {
108 foreach_list(entry_node
, &out_acp
[b
][i
]) {
114 acp
= rzalloc_array(mem_ctx
, struct acp_entry
*, num_acp
);
116 bitset_words
= BITSET_WORDS(num_acp
);
119 for (int b
= 0; b
< cfg
->num_blocks
; b
++) {
120 bd
[b
].livein
= rzalloc_array(bd
, BITSET_WORD
, bitset_words
);
121 bd
[b
].liveout
= rzalloc_array(bd
, BITSET_WORD
, bitset_words
);
122 bd
[b
].copy
= rzalloc_array(bd
, BITSET_WORD
, bitset_words
);
123 bd
[b
].kill
= rzalloc_array(bd
, BITSET_WORD
, bitset_words
);
125 for (int i
= 0; i
< ACP_HASH_SIZE
; i
++) {
126 foreach_list(entry_node
, &out_acp
[b
][i
]) {
127 acp_entry
*entry
= (acp_entry
*)entry_node
;
129 acp
[next_acp
] = entry
;
131 /* opt_copy_propagate_local populates out_acp with copies created
132 * in a block which are still live at the end of the block. This
133 * is exactly what we want in the COPY set.
135 BITSET_SET(bd
[b
].copy
, next_acp
);
142 assert(next_acp
== num_acp
);
144 setup_initial_values();
149 * Set up initial values for each of the data flow sets, prior to running
150 * the fixed-point algorithm.
153 fs_copy_prop_dataflow::setup_initial_values()
155 /* Initialize the COPY and KILL sets. */
156 for (int b
= 0; b
< cfg
->num_blocks
; b
++) {
157 bblock_t
*block
= cfg
->blocks
[b
];
159 for (fs_inst
*inst
= (fs_inst
*)block
->start
;
160 inst
!= block
->end
->next
;
161 inst
= (fs_inst
*)inst
->next
) {
162 if (inst
->dst
.file
!= GRF
)
165 /* Mark ACP entries which are killed by this instruction. */
166 for (int i
= 0; i
< num_acp
; i
++) {
167 if (inst
->overwrites_reg(acp
[i
]->dst
) ||
168 inst
->overwrites_reg(acp
[i
]->src
)) {
169 BITSET_SET(bd
[b
].kill
, i
);
175 /* Populate the initial values for the livein and liveout sets. For the
176 * block at the start of the program, livein = 0 and liveout = copy.
177 * For the others, set liveout to 0 (the empty set) and livein to ~0
178 * (the universal set).
180 for (int b
= 0; b
< cfg
->num_blocks
; b
++) {
181 bblock_t
*block
= cfg
->blocks
[b
];
182 if (block
->parents
.is_empty()) {
183 for (int i
= 0; i
< bitset_words
; i
++) {
184 bd
[b
].livein
[i
] = 0u;
185 bd
[b
].liveout
[i
] = bd
[b
].copy
[i
];
188 for (int i
= 0; i
< bitset_words
; i
++) {
189 bd
[b
].liveout
[i
] = 0u;
190 bd
[b
].livein
[i
] = ~0u;
197 * Walk the set of instructions in the block, marking which entries in the acp
198 * are killed by the block.
201 fs_copy_prop_dataflow::run()
208 /* Update liveout for all blocks. */
209 for (int b
= 0; b
< cfg
->num_blocks
; b
++) {
210 if (cfg
->blocks
[b
]->parents
.is_empty())
213 for (int i
= 0; i
< bitset_words
; i
++) {
214 const BITSET_WORD old_liveout
= bd
[b
].liveout
[i
];
217 bd
[b
].copy
[i
] | (bd
[b
].livein
[i
] & ~bd
[b
].kill
[i
]);
219 if (old_liveout
!= bd
[b
].liveout
[i
])
224 /* Update livein for all blocks. If a copy is live out of all parent
225 * blocks, it's live coming in to this block.
227 for (int b
= 0; b
< cfg
->num_blocks
; b
++) {
228 if (cfg
->blocks
[b
]->parents
.is_empty())
231 for (int i
= 0; i
< bitset_words
; i
++) {
232 const BITSET_WORD old_livein
= bd
[b
].livein
[i
];
234 bd
[b
].livein
[i
] = ~0u;
235 foreach_list(block_node
, &cfg
->blocks
[b
]->parents
) {
236 bblock_link
*link
= (bblock_link
*)block_node
;
237 bblock_t
*block
= link
->block
;
238 bd
[b
].livein
[i
] &= bd
[block
->block_num
].liveout
[i
];
241 if (old_livein
!= bd
[b
].livein
[i
])
249 fs_copy_prop_dataflow::dump_block_data() const
251 for (int b
= 0; b
< cfg
->num_blocks
; b
++) {
252 bblock_t
*block
= cfg
->blocks
[b
];
253 printf("Block %d [%d, %d] (parents ", block
->block_num
,
254 block
->start_ip
, block
->end_ip
);
255 foreach_list(block_node
, &block
->parents
) {
256 bblock_t
*parent
= ((bblock_link
*) block_node
)->block
;
257 printf("%d ", parent
->block_num
);
260 printf(" livein = 0x");
261 for (int i
= 0; i
< bitset_words
; i
++)
262 printf("%08x", bd
[b
].livein
[i
]);
263 printf(", liveout = 0x");
264 for (int i
= 0; i
< bitset_words
; i
++)
265 printf("%08x", bd
[b
].liveout
[i
]);
266 printf(",\n copy = 0x");
267 for (int i
= 0; i
< bitset_words
; i
++)
268 printf("%08x", bd
[b
].copy
[i
]);
269 printf(", kill = 0x");
270 for (int i
= 0; i
< bitset_words
; i
++)
271 printf("%08x", bd
[b
].kill
[i
]);
277 fs_visitor::try_copy_propagate(fs_inst
*inst
, int arg
, acp_entry
*entry
)
279 if (entry
->src
.file
== IMM
)
282 if (inst
->regs_read(this, arg
) > 1)
285 if (inst
->src
[arg
].file
!= entry
->dst
.file
||
286 inst
->src
[arg
].reg
!= entry
->dst
.reg
||
287 inst
->src
[arg
].reg_offset
!= entry
->dst
.reg_offset
) {
291 /* See resolve_ud_negate() and comment in brw_fs_emit.cpp. */
292 if (inst
->conditional_mod
&&
293 inst
->src
[arg
].type
== BRW_REGISTER_TYPE_UD
&&
297 bool has_source_modifiers
= entry
->src
.abs
|| entry
->src
.negate
;
299 if ((has_source_modifiers
|| entry
->src
.file
== UNIFORM
||
300 entry
->src
.smear
!= -1) && !can_do_source_mods(inst
))
303 if (has_source_modifiers
&& entry
->dst
.type
!= inst
->src
[arg
].type
)
306 inst
->src
[arg
].file
= entry
->src
.file
;
307 inst
->src
[arg
].reg
= entry
->src
.reg
;
308 inst
->src
[arg
].reg_offset
= entry
->src
.reg_offset
;
309 if (entry
->src
.smear
!= -1)
310 inst
->src
[arg
].smear
= entry
->src
.smear
;
312 if (!inst
->src
[arg
].abs
) {
313 inst
->src
[arg
].abs
= entry
->src
.abs
;
314 inst
->src
[arg
].negate
^= entry
->src
.negate
;
322 fs_visitor::try_constant_propagate(fs_inst
*inst
, acp_entry
*entry
)
324 bool progress
= false;
326 if (entry
->src
.file
!= IMM
)
329 for (int i
= 2; i
>= 0; i
--) {
330 if (inst
->src
[i
].file
!= entry
->dst
.file
||
331 inst
->src
[i
].reg
!= entry
->dst
.reg
||
332 inst
->src
[i
].reg_offset
!= entry
->dst
.reg_offset
)
335 /* Don't bother with cases that should have been taken care of by the
336 * GLSL compiler's constant folding pass.
338 if (inst
->src
[i
].negate
|| inst
->src
[i
].abs
)
341 switch (inst
->opcode
) {
343 inst
->src
[i
] = entry
->src
;
349 case BRW_OPCODE_ADDC
:
350 case BRW_OPCODE_SUBB
:
352 inst
->src
[i
] = entry
->src
;
357 case BRW_OPCODE_MACH
:
364 inst
->src
[i
] = entry
->src
;
366 } else if (i
== 0 && inst
->src
[1].file
!= IMM
) {
367 /* Fit this constant in by commuting the operands.
368 * Exception: we can't do this for 32-bit integer MUL/MACH
369 * because it's asymmetric.
371 if ((inst
->opcode
== BRW_OPCODE_MUL
||
372 inst
->opcode
== BRW_OPCODE_MACH
) &&
373 (inst
->src
[1].type
== BRW_REGISTER_TYPE_D
||
374 inst
->src
[1].type
== BRW_REGISTER_TYPE_UD
))
376 inst
->src
[0] = inst
->src
[1];
377 inst
->src
[1] = entry
->src
;
385 inst
->src
[i
] = entry
->src
;
387 } else if (i
== 0 && inst
->src
[1].file
!= IMM
) {
390 new_cmod
= brw_swap_cmod(inst
->conditional_mod
);
391 if (new_cmod
!= ~0u) {
392 /* Fit this constant in by swapping the operands and
395 inst
->src
[0] = inst
->src
[1];
396 inst
->src
[1] = entry
->src
;
397 inst
->conditional_mod
= new_cmod
;
405 inst
->src
[i
] = entry
->src
;
407 } else if (i
== 0 && inst
->src
[1].file
!= IMM
) {
408 inst
->src
[0] = inst
->src
[1];
409 inst
->src
[1] = entry
->src
;
411 /* If this was predicated, flipping operands means
412 * we also need to flip the predicate.
414 if (inst
->conditional_mod
== BRW_CONDITIONAL_NONE
) {
415 inst
->predicate_inverse
=
416 !inst
->predicate_inverse
;
422 case SHADER_OPCODE_RCP
:
423 /* The hardware doesn't do math on immediate values
424 * (because why are you doing that, seriously?), but
425 * the correct answer is to just constant fold it
429 if (inst
->src
[0].imm
.f
!= 0.0f
) {
430 inst
->opcode
= BRW_OPCODE_MOV
;
431 inst
->src
[0] = entry
->src
;
432 inst
->src
[0].imm
.f
= 1.0f
/ inst
->src
[0].imm
.f
;
437 case FS_OPCODE_UNIFORM_PULL_CONSTANT_LOAD
:
438 inst
->src
[i
] = entry
->src
;
449 /* Walks a basic block and does copy propagation on it using the acp
453 fs_visitor::opt_copy_propagate_local(void *mem_ctx
, bblock_t
*block
,
456 bool progress
= false;
458 for (fs_inst
*inst
= (fs_inst
*)block
->start
;
459 inst
!= block
->end
->next
;
460 inst
= (fs_inst
*)inst
->next
) {
462 /* Try propagating into this instruction. */
463 for (int i
= 0; i
< 3; i
++) {
464 if (inst
->src
[i
].file
!= GRF
)
467 foreach_list(entry_node
, &acp
[inst
->src
[i
].reg
% ACP_HASH_SIZE
]) {
468 acp_entry
*entry
= (acp_entry
*)entry_node
;
470 if (try_constant_propagate(inst
, entry
))
473 if (try_copy_propagate(inst
, i
, entry
))
478 /* kill the destination from the ACP */
479 if (inst
->dst
.file
== GRF
) {
480 foreach_list_safe(entry_node
, &acp
[inst
->dst
.reg
% ACP_HASH_SIZE
]) {
481 acp_entry
*entry
= (acp_entry
*)entry_node
;
483 if (inst
->overwrites_reg(entry
->dst
)) {
488 /* Oops, we only have the chaining hash based on the destination, not
489 * the source, so walk across the entire table.
491 for (int i
= 0; i
< ACP_HASH_SIZE
; i
++) {
492 foreach_list_safe(entry_node
, &acp
[i
]) {
493 acp_entry
*entry
= (acp_entry
*)entry_node
;
494 if (inst
->overwrites_reg(entry
->src
))
500 /* If this instruction's source could potentially be folded into the
501 * operand of another instruction, add it to the ACP.
503 if (inst
->opcode
== BRW_OPCODE_MOV
&&
504 inst
->dst
.file
== GRF
&&
505 ((inst
->src
[0].file
== GRF
&&
506 (inst
->src
[0].reg
!= inst
->dst
.reg
||
507 inst
->src
[0].reg_offset
!= inst
->dst
.reg_offset
)) ||
508 inst
->src
[0].file
== UNIFORM
||
509 inst
->src
[0].file
== IMM
) &&
510 inst
->src
[0].type
== inst
->dst
.type
&&
512 !inst
->is_partial_write()) {
513 acp_entry
*entry
= ralloc(mem_ctx
, acp_entry
);
514 entry
->dst
= inst
->dst
;
515 entry
->src
= inst
->src
[0];
516 acp
[entry
->dst
.reg
% ACP_HASH_SIZE
].push_tail(entry
);
524 fs_visitor::opt_copy_propagate()
526 bool progress
= false;
527 void *mem_ctx
= ralloc_context(this->mem_ctx
);
529 exec_list
*out_acp
[cfg
.num_blocks
];
530 for (int i
= 0; i
< cfg
.num_blocks
; i
++)
531 out_acp
[i
] = new exec_list
[ACP_HASH_SIZE
];
533 /* First, walk through each block doing local copy propagation and getting
534 * the set of copies available at the end of the block.
536 for (int b
= 0; b
< cfg
.num_blocks
; b
++) {
537 bblock_t
*block
= cfg
.blocks
[b
];
539 progress
= opt_copy_propagate_local(mem_ctx
, block
,
540 out_acp
[b
]) || progress
;
543 /* Do dataflow analysis for those available copies. */
544 fs_copy_prop_dataflow
dataflow(mem_ctx
, &cfg
, out_acp
);
546 /* Next, re-run local copy propagation, this time with the set of copies
547 * provided by the dataflow analysis available at the start of a block.
549 for (int b
= 0; b
< cfg
.num_blocks
; b
++) {
550 bblock_t
*block
= cfg
.blocks
[b
];
551 exec_list in_acp
[ACP_HASH_SIZE
];
553 for (int i
= 0; i
< dataflow
.num_acp
; i
++) {
554 if (BITSET_TEST(dataflow
.bd
[b
].livein
, i
)) {
555 struct acp_entry
*entry
= dataflow
.acp
[i
];
556 in_acp
[entry
->dst
.reg
% ACP_HASH_SIZE
].push_tail(entry
);
560 progress
= opt_copy_propagate_local(mem_ctx
, block
, in_acp
) || progress
;
563 for (int i
= 0; i
< cfg
.num_blocks
; i
++)
564 delete [] out_acp
[i
];
565 ralloc_free(mem_ctx
);
568 invalidate_live_intervals();