1 /*
2 * Copyright (C) 2018 Alyssa Rosenzweig
3 * Copyright (C) 2019-2020 Collabora, Ltd.
4 *
5 * Permission is hereby granted, free of charge, to any person obtaining a
6 * copy of this software and associated documentation files (the "Software"),
7 * to deal in the Software without restriction, including without limitation
8 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
9 * and/or sell copies of the Software, and to permit persons to whom the
10 * Software is furnished to do so, subject to the following conditions:
11 *
12 * The above copyright notice and this permission notice (including the next
13 * paragraph) shall be included in all copies or substantial portions of the
14 * Software.
15 *
16 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
17 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
18 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
19 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
20 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
21 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
22 * SOFTWARE.
23 */
24
25 #include "util/u_memory.h"
26 #include "compiler.h"
27
28 /**
29 * A simple SSA-based dead code elimination pass.
30 * This pass assumes that no loop header phis are dead.
31 */
32
33 void
bi_opt_dce(bi_context * ctx,bool partial)34 bi_opt_dce(bi_context *ctx, bool partial)
35 {
36 BITSET_WORD *seen =
37 calloc(BITSET_WORDS(ctx->ssa_alloc), sizeof(BITSET_WORD));
38
39 bi_foreach_block(ctx, block) {
40 if (block->loop_header) {
41 bi_foreach_instr_in_block(block, I) {
42 if (I->op != BI_OPCODE_PHI) {
43 break;
44 }
45
46 bi_foreach_ssa_src(I, s) {
47 BITSET_SET(seen, I->src[s].value);
48 }
49 }
50 }
51 }
52
53 bi_foreach_block_rev(ctx, block) {
54 bi_foreach_instr_in_block_safe_rev(block, I) {
55 if (block->loop_header && I->op == BI_OPCODE_PHI)
56 break;
57
58 bool needed = false;
59
60 bi_foreach_ssa_dest(I, d) {
61 if (BITSET_TEST(seen, I->dest[d].value)) {
62 needed = true;
63 } else if (partial) {
64 I->dest[d] = bi_null();
65 }
66 }
67
68 if (!needed && !bi_side_effects(I)) {
69 bi_remove_instruction(I);
70 } else {
71 bi_foreach_ssa_src(I, s) {
72 BITSET_SET(seen, I->src[s].value);
73 }
74 }
75 }
76 }
77
78 free(seen);
79 }
80
81 /* Post-RA liveness-based dead code analysis to clean up results of bundling */
82
83 uint64_t MUST_CHECK
bi_postra_liveness_ins(uint64_t live,bi_instr * ins)84 bi_postra_liveness_ins(uint64_t live, bi_instr *ins)
85 {
86 bi_foreach_dest(ins, d) {
87 if (ins->dest[d].type == BI_INDEX_REGISTER) {
88 unsigned nr = bi_count_write_registers(ins, d);
89 unsigned reg = ins->dest[d].value;
90 live &= ~(BITFIELD64_MASK(nr) << reg);
91 }
92 }
93
94 bi_foreach_src(ins, s) {
95 if (ins->src[s].type == BI_INDEX_REGISTER) {
96 unsigned nr = bi_count_read_registers(ins, s);
97 unsigned reg = ins->src[s].value;
98 live |= (BITFIELD64_MASK(nr) << reg);
99 }
100 }
101
102 return live;
103 }
104
105 static bool
bi_postra_liveness_block(bi_block * blk)106 bi_postra_liveness_block(bi_block *blk)
107 {
108 bi_foreach_successor(blk, succ)
109 blk->reg_live_out |= succ->reg_live_in;
110
111 uint64_t live = blk->reg_live_out;
112
113 bi_foreach_instr_in_block_rev(blk, ins)
114 live = bi_postra_liveness_ins(live, ins);
115
116 bool progress = blk->reg_live_in != live;
117 blk->reg_live_in = live;
118 return progress;
119 }
120
121 /* Globally, liveness analysis uses a fixed-point algorithm based on a
122 * worklist. We initialize a work list with the exit block. We iterate the work
123 * list to compute live_in from live_out for each block on the work list,
124 * adding the predecessors of the block to the work list if we made progress.
125 */
126
127 void
bi_postra_liveness(bi_context * ctx)128 bi_postra_liveness(bi_context *ctx)
129 {
130 u_worklist worklist;
131 bi_worklist_init(ctx, &worklist);
132
133 bi_foreach_block(ctx, block) {
134 block->reg_live_out = block->reg_live_in = 0;
135
136 bi_worklist_push_tail(&worklist, block);
137 }
138
139 while (!u_worklist_is_empty(&worklist)) {
140 /* Pop off in reverse order since liveness is backwards */
141 bi_block *blk = bi_worklist_pop_tail(&worklist);
142
143 /* Update liveness information. If we made progress, we need to
144 * reprocess the predecessors
145 */
146 if (bi_postra_liveness_block(blk)) {
147 bi_foreach_predecessor(blk, pred)
148 bi_worklist_push_head(&worklist, *pred);
149 }
150 }
151
152 u_worklist_fini(&worklist);
153 }
154
155 void
bi_opt_dce_post_ra(bi_context * ctx)156 bi_opt_dce_post_ra(bi_context *ctx)
157 {
158 bi_postra_liveness(ctx);
159
160 bi_foreach_block_rev(ctx, block) {
161 uint64_t live = block->reg_live_out;
162
163 bi_foreach_instr_in_block_rev(block, ins) {
164 if (ins->op == BI_OPCODE_DTSEL_IMM)
165 ins->dest[0] = bi_null();
166
167 bi_foreach_dest(ins, d) {
168 if (ins->dest[d].type != BI_INDEX_REGISTER)
169 continue;
170
171 unsigned nr = bi_count_write_registers(ins, d);
172 unsigned reg = ins->dest[d].value;
173 uint64_t mask = (BITFIELD64_MASK(nr) << reg);
174 bool cullable = (ins->op != BI_OPCODE_BLEND);
175 cullable &= !bi_opcode_props[ins->op].sr_write;
176
177 if (!(live & mask) && cullable)
178 ins->dest[d] = bi_null();
179 }
180
181 live = bi_postra_liveness_ins(live, ins);
182 }
183 }
184 }
185