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 const bool is_live
= instr
->definitions
.empty() ||
61 std::any_of(instr
->definitions
.begin(), instr
->definitions
.end(),
62 [&ctx
] (const Definition
& def
) { return !def
.isTemp() || ctx
.uses
[def
.tempId()];});
65 for (const Operand
& op
: instr
->operands
) {
67 if (ctx
.uses
[op
.tempId()] == 0)
68 process_predecessors
= true;
69 ctx
.uses
[op
.tempId()]++;
76 if (process_predecessors
) {
77 for (unsigned pred_idx
: block
.linear_preds
)
78 ctx
.current_block
= std::max(ctx
.current_block
, (int) pred_idx
);
84 std::vector
<uint16_t> dead_code_analysis(Program
*program
) {
88 while (ctx
.current_block
>= 0) {
89 unsigned next_block
= ctx
.current_block
--;
90 process_block(ctx
, program
->blocks
[next_block
]);
93 /* add one use to exec to prevent startpgm from being removed */
94 aco_ptr
<Instruction
>& startpgm
= program
->blocks
[0].instructions
[0];
95 assert(startpgm
->opcode
== aco_opcode::p_startpgm
);
96 ctx
.uses
[startpgm
->definitions
.back().tempId()]++;