2 * Copyright © 2019 Valve 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
30 * Implements an analysis pass to determine the number of uses
31 * for each SSA-definition.
39 std::vector
<uint16_t> uses
;
40 std::vector
<std::vector
<bool>> live
;
42 dce_ctx(Program
* program
) : current_block(program
->blocks
.size() - 1), uses(program
->peekAllocationId())
44 live
.reserve(program
->blocks
.size());
45 for (Block
& block
: program
->blocks
)
46 live
.emplace_back(block
.instructions
.size());
50 void process_block(dce_ctx
& ctx
, Block
& block
)
52 std::vector
<bool>& live
= ctx
.live
[block
.index
];
53 assert(live
.size() == block
.instructions
.size());
54 bool process_predecessors
= false;
55 for (int idx
= block
.instructions
.size() - 1; idx
>= 0; idx
--) {
59 aco_ptr
<Instruction
>& instr
= block
.instructions
[idx
];
60 if (!is_dead(ctx
.uses
, instr
.get())) {
61 for (const Operand
& op
: instr
->operands
) {
63 if (ctx
.uses
[op
.tempId()] == 0)
64 process_predecessors
= true;
65 ctx
.uses
[op
.tempId()]++;
72 if (process_predecessors
) {
73 for (unsigned pred_idx
: block
.linear_preds
)
74 ctx
.current_block
= std::max(ctx
.current_block
, (int) pred_idx
);
80 bool is_dead(const std::vector
<uint16_t>& uses
, Instruction
*instr
)
82 if (instr
->definitions
.empty())
84 if (std::any_of(instr
->definitions
.begin(), instr
->definitions
.end(),
85 [&uses
] (const Definition
& def
) { return uses
[def
.tempId()];}))
87 return !instr_info
.is_atomic
[(int)instr
->opcode
];
90 std::vector
<uint16_t> dead_code_analysis(Program
*program
) {
94 while (ctx
.current_block
>= 0) {
95 unsigned next_block
= ctx
.current_block
--;
96 process_block(ctx
, program
->blocks
[next_block
]);
99 /* add one use to exec to prevent startpgm from being removed */
100 aco_ptr
<Instruction
>& startpgm
= program
->blocks
[0].instructions
[0];
101 assert(startpgm
->opcode
== aco_opcode::p_startpgm
);
102 ctx
.uses
[startpgm
->definitions
.back().tempId()]++;