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
31
* Implements an analysis pass to determine the number of uses
32
* for each SSA-definition.
40
std::vector<uint16_t> uses;
41
std::vector<std::vector<bool>> live;
43
dce_ctx(Program* program)
44
: current_block(program->blocks.size() - 1), uses(program->peekAllocationId())
46
live.reserve(program->blocks.size());
47
for (Block& block : program->blocks)
48
live.emplace_back(block.instructions.size());
53
process_block(dce_ctx& ctx, Block& block)
55
std::vector<bool>& live = ctx.live[block.index];
56
assert(live.size() == block.instructions.size());
57
bool process_predecessors = false;
58
for (int idx = block.instructions.size() - 1; idx >= 0; idx--) {
62
aco_ptr<Instruction>& instr = block.instructions[idx];
63
if (!is_dead(ctx.uses, instr.get())) {
64
for (const Operand& op : instr->operands) {
66
if (ctx.uses[op.tempId()] == 0)
67
process_predecessors = true;
68
ctx.uses[op.tempId()]++;
75
if (process_predecessors) {
76
for (unsigned pred_idx : block.linear_preds)
77
ctx.current_block = std::max(ctx.current_block, (int)pred_idx);
84
is_dead(const std::vector<uint16_t>& uses, Instruction* instr)
86
if (instr->definitions.empty() || instr->isBranch())
88
if (std::any_of(instr->definitions.begin(), instr->definitions.end(),
89
[&uses](const Definition& def) { return !def.isTemp() || uses[def.tempId()]; }))
91
return !(get_sync_info(instr).semantics & (semantic_volatile | semantic_acqrel));
95
dead_code_analysis(Program* program)
100
while (ctx.current_block >= 0) {
101
unsigned next_block = ctx.current_block--;
102
process_block(ctx, program->blocks[next_block]);
105
/* add one use to exec to prevent startpgm from being removed */
106
aco_ptr<Instruction>& startpgm = program->blocks[0].instructions[0];
107
assert(startpgm->opcode == aco_opcode::p_startpgm);
108
ctx.uses[startpgm->definitions.back().tempId()]++;