1 /*
2 * Copyright © 2019 Valve Corporation
3 *
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:
10 *
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
13 * Software.
14 *
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
21 * IN THE SOFTWARE.
22 *
23 */
24
25 #include "aco_ir.h"
26
27 #include <algorithm>
28
29 /*
30 * Implements an analysis pass to determine the number of uses
31 * for each SSA-definition.
32 */
33
34 namespace aco {
35 namespace {
36
37 struct dce_ctx {
38 int current_block;
39 std::vector<uint16_t> uses;
40 std::vector<std::vector<bool>> live;
41
dce_ctxaco::__anon0ccd9fed0111::dce_ctx42 dce_ctx(Program* program) : current_block(program->blocks.size() - 1), uses(program->peekAllocationId())
43 {
44 live.reserve(program->blocks.size());
45 for (Block& block : program->blocks)
46 live.emplace_back(block.instructions.size());
47 }
48 };
49
process_block(dce_ctx & ctx,Block & block)50 void process_block(dce_ctx& ctx, Block& block)
51 {
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--) {
56 if (live[idx])
57 continue;
58
59 aco_ptr<Instruction>& instr = block.instructions[idx];
60 if (!is_dead(ctx.uses, instr.get())) {
61 for (const Operand& op : instr->operands) {
62 if (op.isTemp()) {
63 if (ctx.uses[op.tempId()] == 0)
64 process_predecessors = true;
65 ctx.uses[op.tempId()]++;
66 }
67 }
68 live[idx] = true;
69 }
70 }
71
72 if (process_predecessors) {
73 for (unsigned pred_idx : block.linear_preds)
74 ctx.current_block = std::max(ctx.current_block, (int) pred_idx);
75 }
76 }
77
78 } /* end namespace */
79
is_dead(const std::vector<uint16_t> & uses,Instruction * instr)80 bool is_dead(const std::vector<uint16_t>& uses, Instruction *instr)
81 {
82 if (instr->definitions.empty() || instr->format == Format::PSEUDO_BRANCH)
83 return false;
84 if (std::any_of(instr->definitions.begin(), instr->definitions.end(),
85 [&uses] (const Definition& def) { return uses[def.tempId()];}))
86 return false;
87 return !(get_sync_info(instr).semantics & (semantic_volatile | semantic_acqrel));
88 }
89
dead_code_analysis(Program * program)90 std::vector<uint16_t> dead_code_analysis(Program *program) {
91
92 dce_ctx ctx(program);
93
94 while (ctx.current_block >= 0) {
95 unsigned next_block = ctx.current_block--;
96 process_block(ctx, program->blocks[next_block]);
97 }
98
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()]++;
103
104 return ctx.uses;
105 }
106
107 }
108
109