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 "util/bitset.h"
41 namespace { /* avoid conflict with opt_copy_propagation_elements */
42 struct acp_entry
: public exec_node
{
52 * Which entries in the fs_copy_prop_dataflow acp table are live at the
53 * start of this block. This is the useful output of the analysis, since
54 * it lets us plug those into the local copy propagation on the second
60 * Which entries in the fs_copy_prop_dataflow acp table are live at the end
61 * of this block. This is done in initial setup from the per-block acps
62 * returned by the first local copy prop pass.
67 * Which entries in the fs_copy_prop_dataflow acp table are generated by
68 * instructions in this block which reach the end of the block without
74 * Which entries in the fs_copy_prop_dataflow acp table are killed over the
75 * course of this block.
80 class fs_copy_prop_dataflow
83 fs_copy_prop_dataflow(void *mem_ctx
, cfg_t
*cfg
,
84 exec_list
*out_acp
[ACP_HASH_SIZE
]);
86 void setup_initial_values();
89 void dump_block_data() const;
98 struct block_data
*bd
;
100 } /* anonymous namespace */
102 fs_copy_prop_dataflow::fs_copy_prop_dataflow(void *mem_ctx
, cfg_t
*cfg
,
103 exec_list
*out_acp
[ACP_HASH_SIZE
])
104 : mem_ctx(mem_ctx
), cfg(cfg
)
106 bd
= rzalloc_array(mem_ctx
, struct block_data
, cfg
->num_blocks
);
109 foreach_block (block
, cfg
) {
110 for (int i
= 0; i
< ACP_HASH_SIZE
; i
++) {
111 num_acp
+= out_acp
[block
->num
][i
].length();
115 acp
= rzalloc_array(mem_ctx
, struct acp_entry
*, num_acp
);
117 bitset_words
= BITSET_WORDS(num_acp
);
120 foreach_block (block
, cfg
) {
121 bd
[block
->num
].livein
= rzalloc_array(bd
, BITSET_WORD
, bitset_words
);
122 bd
[block
->num
].liveout
= rzalloc_array(bd
, BITSET_WORD
, bitset_words
);
123 bd
[block
->num
].copy
= rzalloc_array(bd
, BITSET_WORD
, bitset_words
);
124 bd
[block
->num
].kill
= rzalloc_array(bd
, BITSET_WORD
, bitset_words
);
126 for (int i
= 0; i
< ACP_HASH_SIZE
; i
++) {
127 foreach_in_list(acp_entry
, entry
, &out_acp
[block
->num
][i
]) {
128 acp
[next_acp
] = entry
;
130 /* opt_copy_propagate_local populates out_acp with copies created
131 * in a block which are still live at the end of the block. This
132 * is exactly what we want in the COPY set.
134 BITSET_SET(bd
[block
->num
].copy
, next_acp
);
141 assert(next_acp
== num_acp
);
143 setup_initial_values();
148 * Set up initial values for each of the data flow sets, prior to running
149 * the fixed-point algorithm.
152 fs_copy_prop_dataflow::setup_initial_values()
154 /* Initialize the COPY and KILL sets. */
155 foreach_block (block
, cfg
) {
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
[block
->num
].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 foreach_block (block
, cfg
) {
176 if (block
->parents
.is_empty()) {
177 for (int i
= 0; i
< bitset_words
; i
++) {
178 bd
[block
->num
].livein
[i
] = 0u;
179 bd
[block
->num
].liveout
[i
] = bd
[block
->num
].copy
[i
];
182 for (int i
= 0; i
< bitset_words
; i
++) {
183 bd
[block
->num
].liveout
[i
] = 0u;
184 bd
[block
->num
].livein
[i
] = ~0u;
191 * Walk the set of instructions in the block, marking which entries in the acp
192 * are killed by the block.
195 fs_copy_prop_dataflow::run()
202 /* Update liveout for all blocks. */
203 foreach_block (block
, cfg
) {
204 if (block
->parents
.is_empty())
207 for (int i
= 0; i
< bitset_words
; i
++) {
208 const BITSET_WORD old_liveout
= bd
[block
->num
].liveout
[i
];
210 bd
[block
->num
].liveout
[i
] =
211 bd
[block
->num
].copy
[i
] | (bd
[block
->num
].livein
[i
] &
212 ~bd
[block
->num
].kill
[i
]);
214 if (old_liveout
!= bd
[block
->num
].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 foreach_block (block
, cfg
) {
223 if (block
->parents
.is_empty())
226 for (int i
= 0; i
< bitset_words
; i
++) {
227 const BITSET_WORD old_livein
= bd
[block
->num
].livein
[i
];
229 bd
[block
->num
].livein
[i
] = ~0u;
230 foreach_list_typed(bblock_link
, parent_link
, link
, &block
->parents
) {
231 bblock_t
*parent
= parent_link
->block
;
232 bd
[block
->num
].livein
[i
] &= bd
[parent
->num
].liveout
[i
];
235 if (old_livein
!= bd
[block
->num
].livein
[i
])
243 fs_copy_prop_dataflow::dump_block_data() const
245 foreach_block (block
, cfg
) {
246 fprintf(stderr
, "Block %d [%d, %d] (parents ", block
->num
,
247 block
->start_ip
, block
->end_ip
);
248 foreach_list_typed(bblock_link
, link
, link
, &block
->parents
) {
249 bblock_t
*parent
= link
->block
;
250 fprintf(stderr
, "%d ", parent
->num
);
252 fprintf(stderr
, "):\n");
253 fprintf(stderr
, " livein = 0x");
254 for (int i
= 0; i
< bitset_words
; i
++)
255 fprintf(stderr
, "%08x", bd
[block
->num
].livein
[i
]);
256 fprintf(stderr
, ", liveout = 0x");
257 for (int i
= 0; i
< bitset_words
; i
++)
258 fprintf(stderr
, "%08x", bd
[block
->num
].liveout
[i
]);
259 fprintf(stderr
, ",\n copy = 0x");
260 for (int i
= 0; i
< bitset_words
; i
++)
261 fprintf(stderr
, "%08x", bd
[block
->num
].copy
[i
]);
262 fprintf(stderr
, ", kill = 0x");
263 for (int i
= 0; i
< bitset_words
; i
++)
264 fprintf(stderr
, "%08x", bd
[block
->num
].kill
[i
]);
265 fprintf(stderr
, "\n");
270 is_logic_op(enum opcode opcode
)
272 return (opcode
== BRW_OPCODE_AND
||
273 opcode
== BRW_OPCODE_OR
||
274 opcode
== BRW_OPCODE_XOR
||
275 opcode
== BRW_OPCODE_NOT
);
279 can_change_source_types(fs_inst
*inst
)
281 return !inst
->src
[0].abs
&& !inst
->src
[0].negate
&&
282 (inst
->opcode
== BRW_OPCODE_MOV
||
283 (inst
->opcode
== BRW_OPCODE_SEL
&&
284 inst
->predicate
!= BRW_PREDICATE_NONE
&&
285 !inst
->src
[1].abs
&& !inst
->src
[1].negate
));
289 fs_visitor::try_copy_propagate(fs_inst
*inst
, int arg
, acp_entry
*entry
)
291 if (inst
->src
[arg
].file
!= GRF
)
294 if (entry
->src
.file
== IMM
)
296 assert(entry
->src
.file
== GRF
|| entry
->src
.file
== UNIFORM
||
297 entry
->src
.file
== ATTR
);
299 if (entry
->opcode
== SHADER_OPCODE_LOAD_PAYLOAD
&&
300 inst
->opcode
== SHADER_OPCODE_LOAD_PAYLOAD
)
303 assert(entry
->dst
.file
== GRF
);
304 if (inst
->src
[arg
].reg
!= entry
->dst
.reg
)
307 /* Bail if inst is reading a range that isn't contained in the range
308 * that entry is writing.
310 if (inst
->src
[arg
].reg_offset
< entry
->dst
.reg_offset
||
311 (inst
->src
[arg
].reg_offset
* 32 + inst
->src
[arg
].subreg_offset
+
312 inst
->regs_read(arg
) * inst
->src
[arg
].stride
* 32) >
313 (entry
->dst
.reg_offset
+ entry
->regs_written
) * 32)
316 /* we can't generally copy-propagate UD negations because we
317 * can end up accessing the resulting values as signed integers
318 * instead. See also resolve_ud_negate() and comment in
319 * fs_generator::generate_code.
321 if (entry
->src
.type
== BRW_REGISTER_TYPE_UD
&&
325 bool has_source_modifiers
= entry
->src
.abs
|| entry
->src
.negate
;
327 if ((has_source_modifiers
|| entry
->src
.file
== UNIFORM
||
328 !entry
->src
.is_contiguous()) &&
329 !inst
->can_do_source_mods(devinfo
))
332 if (has_source_modifiers
&&
333 inst
->opcode
== SHADER_OPCODE_GEN4_SCRATCH_WRITE
)
336 /* Bail if the result of composing both strides would exceed the
339 if (entry
->src
.stride
* inst
->src
[arg
].stride
> 4)
342 /* Bail if the result of composing both strides cannot be expressed
343 * as another stride. This avoids, for example, trying to transform
346 * MOV (8) rX<1>UD rY<0;1,0>UD
347 * FOO (8) ... rX<8;8,1>UW
351 * FOO (8) ... rY<0;1,0>UW
353 * Which would have different semantics.
355 if (entry
->src
.stride
!= 1 &&
356 (inst
->src
[arg
].stride
*
357 type_sz(inst
->src
[arg
].type
)) % type_sz(entry
->src
.type
) != 0)
360 if (has_source_modifiers
&&
361 entry
->dst
.type
!= inst
->src
[arg
].type
&&
362 !can_change_source_types(inst
))
365 if (devinfo
->gen
>= 8 && (entry
->src
.negate
|| entry
->src
.abs
) &&
366 is_logic_op(inst
->opcode
)) {
370 if (entry
->saturate
) {
371 switch(inst
->opcode
) {
373 if (inst
->src
[1].file
!= IMM
||
374 inst
->src
[1].fixed_hw_reg
.dw1
.f
< 0.0 ||
375 inst
->src
[1].fixed_hw_reg
.dw1
.f
> 1.0) {
384 inst
->src
[arg
].file
= entry
->src
.file
;
385 inst
->src
[arg
].reg
= entry
->src
.reg
;
386 inst
->src
[arg
].stride
*= entry
->src
.stride
;
387 inst
->saturate
= inst
->saturate
|| entry
->saturate
;
389 switch (entry
->src
.file
) {
391 assert(entry
->src
.width
== 1);
394 inst
->src
[arg
].width
= entry
->src
.width
;
395 inst
->src
[arg
].reg_offset
= entry
->src
.reg_offset
;
396 inst
->src
[arg
].subreg_offset
= entry
->src
.subreg_offset
;
401 assert(entry
->src
.width
% inst
->src
[arg
].width
== 0);
402 /* In this case, we'll just leave the width alone. The source
403 * register could have different widths depending on how it is
404 * being used. For instance, if only half of the register was
405 * used then we want to preserve that and continue to only use
408 * Also, we have to deal with mapping parts of vgrfs to other
409 * parts of vgrfs so we have to do some reg_offset magic.
412 /* Compute the offset of inst->src[arg] relative to inst->dst */
413 assert(entry
->dst
.subreg_offset
== 0);
414 int rel_offset
= inst
->src
[arg
].reg_offset
- entry
->dst
.reg_offset
;
415 int rel_suboffset
= inst
->src
[arg
].subreg_offset
;
417 /* Compute the final register offset (in bytes) */
418 int offset
= entry
->src
.reg_offset
* 32 + entry
->src
.subreg_offset
;
419 offset
+= rel_offset
* 32 + rel_suboffset
;
420 inst
->src
[arg
].reg_offset
= offset
/ 32;
421 inst
->src
[arg
].subreg_offset
= offset
% 32;
425 unreachable("Invalid register file");
429 if (has_source_modifiers
) {
430 if (entry
->dst
.type
!= inst
->src
[arg
].type
) {
431 /* We are propagating source modifiers from a MOV with a different
432 * type. If we got here, then we can just change the source and
433 * destination types of the instruction and keep going.
435 assert(can_change_source_types(inst
));
436 for (int i
= 0; i
< inst
->sources
; i
++) {
437 inst
->src
[i
].type
= entry
->dst
.type
;
439 inst
->dst
.type
= entry
->dst
.type
;
442 if (!inst
->src
[arg
].abs
) {
443 inst
->src
[arg
].abs
= entry
->src
.abs
;
444 inst
->src
[arg
].negate
^= entry
->src
.negate
;
453 fs_visitor::try_constant_propagate(fs_inst
*inst
, acp_entry
*entry
)
455 bool progress
= false;
457 if (entry
->src
.file
!= IMM
)
462 for (int i
= inst
->sources
- 1; i
>= 0; i
--) {
463 if (inst
->src
[i
].file
!= GRF
)
466 assert(entry
->dst
.file
== GRF
);
467 if (inst
->src
[i
].reg
!= entry
->dst
.reg
)
470 /* Bail if inst is reading a range that isn't contained in the range
471 * that entry is writing.
473 if (inst
->src
[i
].reg_offset
< entry
->dst
.reg_offset
||
474 (inst
->src
[i
].reg_offset
* 32 + inst
->src
[i
].subreg_offset
+
475 inst
->regs_read(i
) * inst
->src
[i
].stride
* 32) >
476 (entry
->dst
.reg_offset
+ entry
->regs_written
) * 32)
479 fs_reg val
= entry
->src
;
480 val
.type
= inst
->src
[i
].type
;
482 if (inst
->src
[i
].abs
) {
483 if ((devinfo
->gen
>= 8 && is_logic_op(inst
->opcode
)) ||
484 !brw_abs_immediate(val
.type
, &val
.fixed_hw_reg
)) {
489 if (inst
->src
[i
].negate
) {
490 if ((devinfo
->gen
>= 8 && is_logic_op(inst
->opcode
)) ||
491 !brw_negate_immediate(val
.type
, &val
.fixed_hw_reg
)) {
496 switch (inst
->opcode
) {
498 case SHADER_OPCODE_LOAD_PAYLOAD
:
503 case SHADER_OPCODE_INT_QUOTIENT
:
504 case SHADER_OPCODE_INT_REMAINDER
:
505 /* FINISHME: Promote non-float constants and remove this. */
506 if (devinfo
->gen
< 8)
509 case SHADER_OPCODE_POW
:
510 /* Allow constant propagation into src1 (except on Gen 6), and let
511 * constant combining promote the constant on Gen < 8.
513 * While Gen 6 MATH can take a scalar source, its source and
514 * destination offsets must be equal and we cannot ensure that.
516 if (devinfo
->gen
== 6)
519 case BRW_OPCODE_BFI1
:
523 case BRW_OPCODE_SUBB
:
530 case BRW_OPCODE_MACH
:
536 case BRW_OPCODE_ADDC
:
540 } else if (i
== 0 && inst
->src
[1].file
!= IMM
) {
541 /* Fit this constant in by commuting the operands.
542 * Exception: we can't do this for 32-bit integer MUL/MACH
543 * because it's asymmetric.
545 if ((inst
->opcode
== BRW_OPCODE_MUL
||
546 inst
->opcode
== BRW_OPCODE_MACH
) &&
547 (inst
->src
[1].type
== BRW_REGISTER_TYPE_D
||
548 inst
->src
[1].type
== BRW_REGISTER_TYPE_UD
))
550 inst
->src
[0] = inst
->src
[1];
561 } else if (i
== 0 && inst
->src
[1].file
!= IMM
) {
562 enum brw_conditional_mod new_cmod
;
564 new_cmod
= brw_swap_cmod(inst
->conditional_mod
);
565 if (new_cmod
!= BRW_CONDITIONAL_NONE
) {
566 /* Fit this constant in by swapping the operands and
569 inst
->src
[0] = inst
->src
[1];
571 inst
->conditional_mod
= new_cmod
;
581 } else if (i
== 0 && inst
->src
[1].file
!= IMM
) {
582 inst
->src
[0] = inst
->src
[1];
585 /* If this was predicated, flipping operands means
586 * we also need to flip the predicate.
588 if (inst
->conditional_mod
== BRW_CONDITIONAL_NONE
) {
589 inst
->predicate_inverse
=
590 !inst
->predicate_inverse
;
596 case SHADER_OPCODE_RCP
:
597 /* The hardware doesn't do math on immediate values
598 * (because why are you doing that, seriously?), but
599 * the correct answer is to just constant fold it
603 if (inst
->src
[0].fixed_hw_reg
.dw1
.f
!= 0.0f
) {
604 inst
->opcode
= BRW_OPCODE_MOV
;
606 inst
->src
[0].fixed_hw_reg
.dw1
.f
= 1.0f
/ inst
->src
[0].fixed_hw_reg
.dw1
.f
;
611 case FS_OPCODE_UNIFORM_PULL_CONSTANT_LOAD
:
612 case SHADER_OPCODE_BROADCAST
:
632 can_propagate_from(fs_inst
*inst
)
634 return (inst
->opcode
== BRW_OPCODE_MOV
&&
635 inst
->dst
.file
== GRF
&&
636 ((inst
->src
[0].file
== GRF
&&
637 (inst
->src
[0].reg
!= inst
->dst
.reg
||
638 inst
->src
[0].reg_offset
!= inst
->dst
.reg_offset
)) ||
639 inst
->src
[0].file
== ATTR
||
640 inst
->src
[0].file
== UNIFORM
||
641 inst
->src
[0].file
== IMM
) &&
642 inst
->src
[0].type
== inst
->dst
.type
&&
643 !inst
->is_partial_write());
646 /* Walks a basic block and does copy propagation on it using the acp
650 fs_visitor::opt_copy_propagate_local(void *copy_prop_ctx
, bblock_t
*block
,
653 bool progress
= false;
655 foreach_inst_in_block(fs_inst
, inst
, block
) {
656 /* Try propagating into this instruction. */
657 for (int i
= 0; i
< inst
->sources
; i
++) {
658 if (inst
->src
[i
].file
!= GRF
)
661 foreach_in_list(acp_entry
, entry
, &acp
[inst
->src
[i
].reg
% ACP_HASH_SIZE
]) {
662 if (try_constant_propagate(inst
, entry
))
665 if (try_copy_propagate(inst
, i
, entry
))
670 /* kill the destination from the ACP */
671 if (inst
->dst
.file
== GRF
) {
672 foreach_in_list_safe(acp_entry
, entry
, &acp
[inst
->dst
.reg
% ACP_HASH_SIZE
]) {
673 if (inst
->overwrites_reg(entry
->dst
)) {
678 /* Oops, we only have the chaining hash based on the destination, not
679 * the source, so walk across the entire table.
681 for (int i
= 0; i
< ACP_HASH_SIZE
; i
++) {
682 foreach_in_list_safe(acp_entry
, entry
, &acp
[i
]) {
683 if (inst
->overwrites_reg(entry
->src
))
689 /* If this instruction's source could potentially be folded into the
690 * operand of another instruction, add it to the ACP.
692 if (can_propagate_from(inst
)) {
693 acp_entry
*entry
= ralloc(copy_prop_ctx
, acp_entry
);
694 entry
->dst
= inst
->dst
;
695 entry
->src
= inst
->src
[0];
696 entry
->regs_written
= inst
->regs_written
;
697 entry
->opcode
= inst
->opcode
;
698 entry
->saturate
= inst
->saturate
;
699 acp
[entry
->dst
.reg
% ACP_HASH_SIZE
].push_tail(entry
);
700 } else if (inst
->opcode
== SHADER_OPCODE_LOAD_PAYLOAD
&&
701 inst
->dst
.file
== GRF
) {
703 for (int i
= 0; i
< inst
->sources
; i
++) {
704 int effective_width
= i
< inst
->header_size
? 8 : inst
->exec_size
;
705 int regs_written
= effective_width
/ 8;
706 if (inst
->src
[i
].file
== GRF
) {
707 acp_entry
*entry
= ralloc(copy_prop_ctx
, acp_entry
);
708 entry
->dst
= inst
->dst
;
709 entry
->dst
.reg_offset
= offset
;
710 entry
->dst
.width
= effective_width
;
711 entry
->src
= inst
->src
[i
];
712 entry
->regs_written
= regs_written
;
713 entry
->opcode
= inst
->opcode
;
714 if (!entry
->dst
.equals(inst
->src
[i
])) {
715 acp
[entry
->dst
.reg
% ACP_HASH_SIZE
].push_tail(entry
);
720 offset
+= regs_written
;
729 fs_visitor::opt_copy_propagate()
731 bool progress
= false;
732 void *copy_prop_ctx
= ralloc_context(NULL
);
733 exec_list
*out_acp
[cfg
->num_blocks
];
735 for (int i
= 0; i
< cfg
->num_blocks
; i
++)
736 out_acp
[i
] = new exec_list
[ACP_HASH_SIZE
];
738 /* First, walk through each block doing local copy propagation and getting
739 * the set of copies available at the end of the block.
741 foreach_block (block
, cfg
) {
742 progress
= opt_copy_propagate_local(copy_prop_ctx
, block
,
743 out_acp
[block
->num
]) || progress
;
746 /* Do dataflow analysis for those available copies. */
747 fs_copy_prop_dataflow
dataflow(copy_prop_ctx
, cfg
, out_acp
);
749 /* Next, re-run local copy propagation, this time with the set of copies
750 * provided by the dataflow analysis available at the start of a block.
752 foreach_block (block
, cfg
) {
753 exec_list in_acp
[ACP_HASH_SIZE
];
755 for (int i
= 0; i
< dataflow
.num_acp
; i
++) {
756 if (BITSET_TEST(dataflow
.bd
[block
->num
].livein
, i
)) {
757 struct acp_entry
*entry
= dataflow
.acp
[i
];
758 in_acp
[entry
->dst
.reg
% ACP_HASH_SIZE
].push_tail(entry
);
762 progress
= opt_copy_propagate_local(copy_prop_ctx
, block
, in_acp
) || progress
;
765 for (int i
= 0; i
< cfg
->num_blocks
; i
++)
766 delete [] out_acp
[i
];
767 ralloc_free(copy_prop_ctx
);
770 invalidate_live_intervals();