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
{
50 * Which entries in the fs_copy_prop_dataflow acp table are live at the
51 * start of this block. This is the useful output of the analysis, since
52 * it lets us plug those into the local copy propagation on the second
58 * Which entries in the fs_copy_prop_dataflow acp table are live at the end
59 * of this block. This is done in initial setup from the per-block acps
60 * returned by the first local copy prop pass.
65 * Which entries in the fs_copy_prop_dataflow acp table are generated by
66 * instructions in this block which reach the end of the block without
72 * Which entries in the fs_copy_prop_dataflow acp table are killed over the
73 * course of this block.
78 class fs_copy_prop_dataflow
81 fs_copy_prop_dataflow(void *mem_ctx
, cfg_t
*cfg
,
82 exec_list
*out_acp
[ACP_HASH_SIZE
]);
84 void setup_initial_values();
87 void dump_block_data() const;
96 struct block_data
*bd
;
98 } /* anonymous namespace */
100 fs_copy_prop_dataflow::fs_copy_prop_dataflow(void *mem_ctx
, cfg_t
*cfg
,
101 exec_list
*out_acp
[ACP_HASH_SIZE
])
102 : mem_ctx(mem_ctx
), cfg(cfg
)
104 bd
= rzalloc_array(mem_ctx
, struct block_data
, cfg
->num_blocks
);
107 for (int b
= 0; b
< cfg
->num_blocks
; b
++) {
108 for (int i
= 0; i
< ACP_HASH_SIZE
; i
++) {
109 num_acp
+= out_acp
[b
][i
].length();
113 acp
= rzalloc_array(mem_ctx
, struct acp_entry
*, num_acp
);
115 bitset_words
= BITSET_WORDS(num_acp
);
118 for (int b
= 0; b
< cfg
->num_blocks
; b
++) {
119 bd
[b
].livein
= rzalloc_array(bd
, BITSET_WORD
, bitset_words
);
120 bd
[b
].liveout
= rzalloc_array(bd
, BITSET_WORD
, bitset_words
);
121 bd
[b
].copy
= rzalloc_array(bd
, BITSET_WORD
, bitset_words
);
122 bd
[b
].kill
= rzalloc_array(bd
, BITSET_WORD
, bitset_words
);
124 for (int i
= 0; i
< ACP_HASH_SIZE
; i
++) {
125 foreach_in_list(acp_entry
, entry
, &out_acp
[b
][i
]) {
126 acp
[next_acp
] = entry
;
128 /* opt_copy_propagate_local populates out_acp with copies created
129 * in a block which are still live at the end of the block. This
130 * is exactly what we want in the COPY set.
132 BITSET_SET(bd
[b
].copy
, next_acp
);
139 assert(next_acp
== num_acp
);
141 setup_initial_values();
146 * Set up initial values for each of the data flow sets, prior to running
147 * the fixed-point algorithm.
150 fs_copy_prop_dataflow::setup_initial_values()
152 /* Initialize the COPY and KILL sets. */
153 for (int b
= 0; b
< cfg
->num_blocks
; b
++) {
154 bblock_t
*block
= cfg
->blocks
[b
];
156 foreach_inst_in_block(fs_inst
, inst
, block
) {
157 if (inst
->dst
.file
!= GRF
)
160 /* Mark ACP entries which are killed by this instruction. */
161 for (int i
= 0; i
< num_acp
; i
++) {
162 if (inst
->overwrites_reg(acp
[i
]->dst
) ||
163 inst
->overwrites_reg(acp
[i
]->src
)) {
164 BITSET_SET(bd
[b
].kill
, i
);
170 /* Populate the initial values for the livein and liveout sets. For the
171 * block at the start of the program, livein = 0 and liveout = copy.
172 * For the others, set liveout to 0 (the empty set) and livein to ~0
173 * (the universal set).
175 for (int b
= 0; b
< cfg
->num_blocks
; b
++) {
176 bblock_t
*block
= cfg
->blocks
[b
];
177 if (block
->parents
.is_empty()) {
178 for (int i
= 0; i
< bitset_words
; i
++) {
179 bd
[b
].livein
[i
] = 0u;
180 bd
[b
].liveout
[i
] = bd
[b
].copy
[i
];
183 for (int i
= 0; i
< bitset_words
; i
++) {
184 bd
[b
].liveout
[i
] = 0u;
185 bd
[b
].livein
[i
] = ~0u;
192 * Walk the set of instructions in the block, marking which entries in the acp
193 * are killed by the block.
196 fs_copy_prop_dataflow::run()
203 /* Update liveout for all blocks. */
204 for (int b
= 0; b
< cfg
->num_blocks
; b
++) {
205 if (cfg
->blocks
[b
]->parents
.is_empty())
208 for (int i
= 0; i
< bitset_words
; i
++) {
209 const BITSET_WORD old_liveout
= bd
[b
].liveout
[i
];
212 bd
[b
].copy
[i
] | (bd
[b
].livein
[i
] & ~bd
[b
].kill
[i
]);
214 if (old_liveout
!= bd
[b
].liveout
[i
])
219 /* Update livein for all blocks. If a copy is live out of all parent
220 * blocks, it's live coming in to this block.
222 for (int b
= 0; b
< cfg
->num_blocks
; b
++) {
223 if (cfg
->blocks
[b
]->parents
.is_empty())
226 for (int i
= 0; i
< bitset_words
; i
++) {
227 const BITSET_WORD old_livein
= bd
[b
].livein
[i
];
229 bd
[b
].livein
[i
] = ~0u;
230 foreach_list_typed(bblock_link
, link
, link
, &cfg
->blocks
[b
]->parents
) {
231 bblock_t
*block
= link
->block
;
232 bd
[b
].livein
[i
] &= bd
[block
->block_num
].liveout
[i
];
235 if (old_livein
!= bd
[b
].livein
[i
])
243 fs_copy_prop_dataflow::dump_block_data() const
245 for (int b
= 0; b
< cfg
->num_blocks
; b
++) {
246 bblock_t
*block
= cfg
->blocks
[b
];
247 fprintf(stderr
, "Block %d [%d, %d] (parents ", block
->block_num
,
248 block
->start_ip
, block
->end_ip
);
249 foreach_list_typed(bblock_link
, link
, link
, &block
->parents
) {
250 bblock_t
*parent
= link
->block
;
251 fprintf(stderr
, "%d ", parent
->block_num
);
253 fprintf(stderr
, "):\n");
254 fprintf(stderr
, " livein = 0x");
255 for (int i
= 0; i
< bitset_words
; i
++)
256 fprintf(stderr
, "%08x", bd
[b
].livein
[i
]);
257 fprintf(stderr
, ", liveout = 0x");
258 for (int i
= 0; i
< bitset_words
; i
++)
259 fprintf(stderr
, "%08x", bd
[b
].liveout
[i
]);
260 fprintf(stderr
, ",\n copy = 0x");
261 for (int i
= 0; i
< bitset_words
; i
++)
262 fprintf(stderr
, "%08x", bd
[b
].copy
[i
]);
263 fprintf(stderr
, ", kill = 0x");
264 for (int i
= 0; i
< bitset_words
; i
++)
265 fprintf(stderr
, "%08x", bd
[b
].kill
[i
]);
266 fprintf(stderr
, "\n");
271 is_logic_op(enum opcode opcode
)
273 return (opcode
== BRW_OPCODE_AND
||
274 opcode
== BRW_OPCODE_OR
||
275 opcode
== BRW_OPCODE_XOR
||
276 opcode
== BRW_OPCODE_NOT
);
280 fs_visitor::try_copy_propagate(fs_inst
*inst
, int arg
, acp_entry
*entry
)
282 if (entry
->src
.file
== IMM
)
285 if (entry
->opcode
== SHADER_OPCODE_LOAD_PAYLOAD
&&
286 inst
->opcode
== SHADER_OPCODE_LOAD_PAYLOAD
)
289 /* Bail if inst is reading more than entry is writing. */
290 if ((inst
->regs_read(this, arg
) * inst
->src
[arg
].stride
*
291 type_sz(inst
->src
[arg
].type
)) > type_sz(entry
->dst
.type
))
294 if (inst
->src
[arg
].file
!= entry
->dst
.file
||
295 inst
->src
[arg
].reg
!= entry
->dst
.reg
||
296 inst
->src
[arg
].reg_offset
!= entry
->dst
.reg_offset
||
297 inst
->src
[arg
].subreg_offset
!= entry
->dst
.subreg_offset
) {
301 /* See resolve_ud_negate() and comment in brw_fs_emit.cpp. */
302 if (inst
->conditional_mod
&&
303 inst
->src
[arg
].type
== BRW_REGISTER_TYPE_UD
&&
307 bool has_source_modifiers
= entry
->src
.abs
|| entry
->src
.negate
;
309 if ((has_source_modifiers
|| entry
->src
.file
== UNIFORM
||
310 !entry
->src
.is_contiguous()) &&
311 !inst
->can_do_source_mods(brw
))
314 if (has_source_modifiers
&&
315 inst
->opcode
== SHADER_OPCODE_GEN4_SCRATCH_WRITE
)
318 /* Bail if the result of composing both strides would exceed the
321 if (entry
->src
.stride
* inst
->src
[arg
].stride
> 4)
324 /* Bail if the result of composing both strides cannot be expressed
325 * as another stride. This avoids, for example, trying to transform
328 * MOV (8) rX<1>UD rY<0;1,0>UD
329 * FOO (8) ... rX<8;8,1>UW
333 * FOO (8) ... rY<0;1,0>UW
335 * Which would have different semantics.
337 if (entry
->src
.stride
!= 1 &&
338 (inst
->src
[arg
].stride
*
339 type_sz(inst
->src
[arg
].type
)) % type_sz(entry
->src
.type
) != 0)
342 if (has_source_modifiers
&& entry
->dst
.type
!= inst
->src
[arg
].type
)
345 if (brw
->gen
>= 8 && (entry
->src
.negate
|| entry
->src
.abs
) &&
346 is_logic_op(inst
->opcode
)) {
350 inst
->src
[arg
].file
= entry
->src
.file
;
351 inst
->src
[arg
].reg
= entry
->src
.reg
;
352 inst
->src
[arg
].reg_offset
= entry
->src
.reg_offset
;
353 inst
->src
[arg
].subreg_offset
= entry
->src
.subreg_offset
;
354 inst
->src
[arg
].stride
*= entry
->src
.stride
;
356 if (!inst
->src
[arg
].abs
) {
357 inst
->src
[arg
].abs
= entry
->src
.abs
;
358 inst
->src
[arg
].negate
^= entry
->src
.negate
;
366 try_constant_propagate(struct brw_context
*brw
, fs_inst
*inst
,
369 bool progress
= false;
371 if (entry
->src
.file
!= IMM
)
374 for (int i
= inst
->sources
- 1; i
>= 0; i
--) {
375 if (inst
->src
[i
].file
!= entry
->dst
.file
||
376 inst
->src
[i
].reg
!= entry
->dst
.reg
||
377 inst
->src
[i
].reg_offset
!= entry
->dst
.reg_offset
||
378 inst
->src
[i
].subreg_offset
!= entry
->dst
.subreg_offset
||
379 inst
->src
[i
].type
!= entry
->dst
.type
||
380 inst
->src
[i
].stride
> 1)
383 /* Don't bother with cases that should have been taken care of by the
384 * GLSL compiler's constant folding pass.
386 if (inst
->src
[i
].negate
|| inst
->src
[i
].abs
)
389 switch (inst
->opcode
) {
391 inst
->src
[i
] = entry
->src
;
395 case SHADER_OPCODE_POW
:
396 case SHADER_OPCODE_INT_QUOTIENT
:
397 case SHADER_OPCODE_INT_REMAINDER
:
401 case BRW_OPCODE_BFI1
:
405 case BRW_OPCODE_SUBB
:
407 inst
->src
[i
] = entry
->src
;
412 case BRW_OPCODE_MACH
:
418 case BRW_OPCODE_ADDC
:
420 inst
->src
[i
] = entry
->src
;
422 } else if (i
== 0 && inst
->src
[1].file
!= IMM
) {
423 /* Fit this constant in by commuting the operands.
424 * Exception: we can't do this for 32-bit integer MUL/MACH
425 * because it's asymmetric.
427 if ((inst
->opcode
== BRW_OPCODE_MUL
||
428 inst
->opcode
== BRW_OPCODE_MACH
) &&
429 (inst
->src
[1].type
== BRW_REGISTER_TYPE_D
||
430 inst
->src
[1].type
== BRW_REGISTER_TYPE_UD
))
432 inst
->src
[0] = inst
->src
[1];
433 inst
->src
[1] = entry
->src
;
441 inst
->src
[i
] = entry
->src
;
443 } else if (i
== 0 && inst
->src
[1].file
!= IMM
) {
444 enum brw_conditional_mod new_cmod
;
446 new_cmod
= brw_swap_cmod(inst
->conditional_mod
);
447 if (new_cmod
!= BRW_CONDITIONAL_NONE
) {
448 /* Fit this constant in by swapping the operands and
451 inst
->src
[0] = inst
->src
[1];
452 inst
->src
[1] = entry
->src
;
453 inst
->conditional_mod
= new_cmod
;
461 inst
->src
[i
] = entry
->src
;
463 } else if (i
== 0 && inst
->src
[1].file
!= IMM
) {
464 inst
->src
[0] = inst
->src
[1];
465 inst
->src
[1] = entry
->src
;
467 /* If this was predicated, flipping operands means
468 * we also need to flip the predicate.
470 if (inst
->conditional_mod
== BRW_CONDITIONAL_NONE
) {
471 inst
->predicate_inverse
=
472 !inst
->predicate_inverse
;
478 case SHADER_OPCODE_RCP
:
479 /* The hardware doesn't do math on immediate values
480 * (because why are you doing that, seriously?), but
481 * the correct answer is to just constant fold it
485 if (inst
->src
[0].fixed_hw_reg
.dw1
.f
!= 0.0f
) {
486 inst
->opcode
= BRW_OPCODE_MOV
;
487 inst
->src
[0] = entry
->src
;
488 inst
->src
[0].fixed_hw_reg
.dw1
.f
= 1.0f
/ inst
->src
[0].fixed_hw_reg
.dw1
.f
;
493 case FS_OPCODE_UNIFORM_PULL_CONSTANT_LOAD
:
494 inst
->src
[i
] = entry
->src
;
507 can_propagate_from(fs_inst
*inst
)
509 return (inst
->opcode
== BRW_OPCODE_MOV
&&
510 inst
->dst
.file
== GRF
&&
511 ((inst
->src
[0].file
== GRF
&&
512 (inst
->src
[0].reg
!= inst
->dst
.reg
||
513 inst
->src
[0].reg_offset
!= inst
->dst
.reg_offset
)) ||
514 inst
->src
[0].file
== UNIFORM
||
515 inst
->src
[0].file
== IMM
) &&
516 inst
->src
[0].type
== inst
->dst
.type
&&
518 !inst
->is_partial_write());
521 /* Walks a basic block and does copy propagation on it using the acp
525 fs_visitor::opt_copy_propagate_local(void *copy_prop_ctx
, bblock_t
*block
,
528 bool progress
= false;
530 foreach_inst_in_block(fs_inst
, inst
, block
) {
531 /* Try propagating into this instruction. */
532 for (int i
= 0; i
< inst
->sources
; i
++) {
533 if (inst
->src
[i
].file
!= GRF
)
536 foreach_in_list(acp_entry
, entry
, &acp
[inst
->src
[i
].reg
% ACP_HASH_SIZE
]) {
537 if (try_constant_propagate(brw
, inst
, entry
))
540 if (try_copy_propagate(inst
, i
, entry
))
545 /* kill the destination from the ACP */
546 if (inst
->dst
.file
== GRF
) {
547 foreach_in_list_safe(acp_entry
, entry
, &acp
[inst
->dst
.reg
% ACP_HASH_SIZE
]) {
548 if (inst
->overwrites_reg(entry
->dst
)) {
553 /* Oops, we only have the chaining hash based on the destination, not
554 * the source, so walk across the entire table.
556 for (int i
= 0; i
< ACP_HASH_SIZE
; i
++) {
557 foreach_in_list_safe(acp_entry
, entry
, &acp
[i
]) {
558 if (inst
->overwrites_reg(entry
->src
))
564 /* If this instruction's source could potentially be folded into the
565 * operand of another instruction, add it to the ACP.
567 if (can_propagate_from(inst
)) {
568 acp_entry
*entry
= ralloc(copy_prop_ctx
, acp_entry
);
569 entry
->dst
= inst
->dst
;
570 entry
->src
= inst
->src
[0];
571 entry
->opcode
= inst
->opcode
;
572 acp
[entry
->dst
.reg
% ACP_HASH_SIZE
].push_tail(entry
);
573 } else if (inst
->opcode
== SHADER_OPCODE_LOAD_PAYLOAD
&&
574 inst
->dst
.file
== GRF
) {
575 for (int i
= 0; i
< inst
->sources
; i
++) {
576 if (inst
->src
[i
].file
== GRF
) {
577 acp_entry
*entry
= ralloc(copy_prop_ctx
, acp_entry
);
578 entry
->dst
= inst
->dst
;
579 entry
->dst
.reg_offset
= i
;
580 entry
->src
= inst
->src
[i
];
581 entry
->opcode
= inst
->opcode
;
582 if (!entry
->dst
.equals(inst
->src
[i
])) {
583 acp
[entry
->dst
.reg
% ACP_HASH_SIZE
].push_tail(entry
);
596 fs_visitor::opt_copy_propagate()
600 bool progress
= false;
601 void *copy_prop_ctx
= ralloc_context(NULL
);
602 exec_list
*out_acp
[cfg
->num_blocks
];
604 for (int i
= 0; i
< cfg
->num_blocks
; i
++)
605 out_acp
[i
] = new exec_list
[ACP_HASH_SIZE
];
607 /* First, walk through each block doing local copy propagation and getting
608 * the set of copies available at the end of the block.
610 for (int b
= 0; b
< cfg
->num_blocks
; b
++) {
611 bblock_t
*block
= cfg
->blocks
[b
];
613 progress
= opt_copy_propagate_local(copy_prop_ctx
, block
,
614 out_acp
[b
]) || progress
;
617 /* Do dataflow analysis for those available copies. */
618 fs_copy_prop_dataflow
dataflow(copy_prop_ctx
, cfg
, out_acp
);
620 /* Next, re-run local copy propagation, this time with the set of copies
621 * provided by the dataflow analysis available at the start of a block.
623 for (int b
= 0; b
< cfg
->num_blocks
; b
++) {
624 bblock_t
*block
= cfg
->blocks
[b
];
625 exec_list in_acp
[ACP_HASH_SIZE
];
627 for (int i
= 0; i
< dataflow
.num_acp
; i
++) {
628 if (BITSET_TEST(dataflow
.bd
[b
].livein
, i
)) {
629 struct acp_entry
*entry
= dataflow
.acp
[i
];
630 in_acp
[entry
->dst
.reg
% ACP_HASH_SIZE
].push_tail(entry
);
634 progress
= opt_copy_propagate_local(copy_prop_ctx
, block
, in_acp
) || progress
;
637 for (int i
= 0; i
< cfg
->num_blocks
; i
++)
638 delete [] out_acp
[i
];
639 ralloc_free(copy_prop_ctx
);
642 invalidate_live_intervals();