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 /* A simple SSA-based mark-and-sweep dead code elimination pass. */
29
30 void
bi_opt_dead_code_eliminate(bi_context * ctx)31 bi_opt_dead_code_eliminate(bi_context *ctx)
32 {
33 /* Mark live values */
34 BITSET_WORD *mark =
35 calloc(sizeof(BITSET_WORD), BITSET_WORDS(ctx->ssa_alloc));
36
37 u_worklist worklist;
38 u_worklist_init(&worklist, ctx->num_blocks, NULL);
39
40 bi_foreach_block(ctx, block) {
41 bi_worklist_push_head(&worklist, block);
42 }
43
44 while (!u_worklist_is_empty(&worklist)) {
45 /* Pop in reverse order for backwards pass */
46 bi_block *blk = bi_worklist_pop_head(&worklist);
47
48 bool progress = false;
49
50 bi_foreach_instr_in_block_rev(blk, I) {
51 bool needed = bi_side_effects(I);
52
53 bi_foreach_dest(I, d)
54 needed |= BITSET_TEST(mark, I->dest[d].value);
55
56 if (!needed)
57 continue;
58
59 bi_foreach_ssa_src(I, s) {
60 progress |= !BITSET_TEST(mark, I->src[s].value);
61 BITSET_SET(mark, I->src[s].value);
62 }
63 }
64
65 /* XXX: slow */
66 if (progress) {
67 bi_foreach_block(ctx, block)
68 bi_worklist_push_head(&worklist, block);
69 }
70 }
71
72 u_worklist_fini(&worklist);
73
74 /* Sweep */
75 bi_foreach_instr_global_safe(ctx, I) {
76 bool needed = bi_side_effects(I);
77
78 bi_foreach_dest(I, d)
79 needed |= BITSET_TEST(mark, I->dest[d].value);
80
81 if (!needed)
82 bi_remove_instruction(I);
83 }
84
85 free(mark);
86 }
87
88 /* Post-RA liveness-based dead code analysis to clean up results of bundling */
89
90 uint64_t MUST_CHECK
bi_postra_liveness_ins(uint64_t live,bi_instr * ins)91 bi_postra_liveness_ins(uint64_t live, bi_instr *ins)
92 {
93 bi_foreach_dest(ins, d) {
94 if (ins->dest[d].type == BI_INDEX_REGISTER) {
95 unsigned nr = bi_count_write_registers(ins, d);
96 unsigned reg = ins->dest[d].value;
97 live &= ~(BITFIELD64_MASK(nr) << reg);
98 }
99 }
100
101 bi_foreach_src(ins, s) {
102 if (ins->src[s].type == BI_INDEX_REGISTER) {
103 unsigned nr = bi_count_read_registers(ins, s);
104 unsigned reg = ins->src[s].value;
105 live |= (BITFIELD64_MASK(nr) << reg);
106 }
107 }
108
109 return live;
110 }
111
112 static bool
bi_postra_liveness_block(bi_block * blk)113 bi_postra_liveness_block(bi_block *blk)
114 {
115 bi_foreach_successor(blk, succ)
116 blk->reg_live_out |= succ->reg_live_in;
117
118 uint64_t live = blk->reg_live_out;
119
120 bi_foreach_instr_in_block_rev(blk, ins)
121 live = bi_postra_liveness_ins(live, ins);
122
123 bool progress = blk->reg_live_in != live;
124 blk->reg_live_in = live;
125 return progress;
126 }
127
128 /* Globally, liveness analysis uses a fixed-point algorithm based on a
129 * worklist. We initialize a work list with the exit block. We iterate the work
130 * list to compute live_in from live_out for each block on the work list,
131 * adding the predecessors of the block to the work list if we made progress.
132 */
133
134 void
bi_postra_liveness(bi_context * ctx)135 bi_postra_liveness(bi_context *ctx)
136 {
137 u_worklist worklist;
138 bi_worklist_init(ctx, &worklist);
139
140 bi_foreach_block(ctx, block) {
141 block->reg_live_out = block->reg_live_in = 0;
142
143 bi_worklist_push_tail(&worklist, block);
144 }
145
146 while (!u_worklist_is_empty(&worklist)) {
147 /* Pop off in reverse order since liveness is backwards */
148 bi_block *blk = bi_worklist_pop_tail(&worklist);
149
150 /* Update liveness information. If we made progress, we need to
151 * reprocess the predecessors
152 */
153 if (bi_postra_liveness_block(blk)) {
154 bi_foreach_predecessor(blk, pred)
155 bi_worklist_push_head(&worklist, *pred);
156 }
157 }
158
159 u_worklist_fini(&worklist);
160 }
161
162 void
bi_opt_dce_post_ra(bi_context * ctx)163 bi_opt_dce_post_ra(bi_context *ctx)
164 {
165 bi_postra_liveness(ctx);
166
167 bi_foreach_block_rev(ctx, block) {
168 uint64_t live = block->reg_live_out;
169
170 bi_foreach_instr_in_block_rev(block, ins) {
171 if (ins->op == BI_OPCODE_DTSEL_IMM)
172 ins->dest[0] = bi_null();
173
174 bi_foreach_dest(ins, d) {
175 if (ins->dest[d].type != BI_INDEX_REGISTER)
176 continue;
177
178 unsigned nr = bi_count_write_registers(ins, d);
179 unsigned reg = ins->dest[d].value;
180 uint64_t mask = (BITFIELD64_MASK(nr) << reg);
181 bool cullable = (ins->op != BI_OPCODE_BLEND);
182 cullable &= !bi_opcode_props[ins->op].sr_write;
183
184 if (!(live & mask) && cullable)
185 ins->dest[d] = bi_null();
186 }
187
188 live = bi_postra_liveness_ins(live, ins);
189 }
190 }
191 }
192