2
* Copyright (C) 2018 Alyssa Rosenzweig
3
* Copyright (C) 2019-2020 Collabora, Ltd.
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:
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
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
26
#include "util/u_memory.h"
28
/* A simple SSA-based mark-and-sweep dead code elimination pass. */
31
bi_opt_dead_code_eliminate(bi_context *ctx)
33
/* Mark live values */
34
BITSET_WORD *mark = calloc(sizeof(BITSET_WORD), BITSET_WORDS(ctx->ssa_alloc));
37
u_worklist_init(&worklist, ctx->num_blocks, NULL);
39
bi_foreach_block(ctx, block) {
40
bi_worklist_push_head(&worklist, block);
43
while(!u_worklist_is_empty(&worklist)) {
44
/* Pop in reverse order for backwards pass */
45
bi_block *blk = bi_worklist_pop_head(&worklist);
47
bool progress = false;
49
bi_foreach_instr_in_block_rev(blk, I) {
50
bool needed = bi_side_effects(I);
53
needed |= BITSET_TEST(mark, I->dest[d].value);
58
bi_foreach_ssa_src(I, s) {
59
progress |= !BITSET_TEST(mark, I->src[s].value);
60
BITSET_SET(mark, I->src[s].value);
66
bi_foreach_block(ctx, block)
67
bi_worklist_push_head(&worklist, block);
71
u_worklist_fini(&worklist);
74
bi_foreach_instr_global_safe(ctx, I) {
75
bool needed = bi_side_effects(I);
78
needed |= BITSET_TEST(mark, I->dest[d].value);
81
bi_remove_instruction(I);
87
/* Post-RA liveness-based dead code analysis to clean up results of bundling */
90
bi_postra_liveness_ins(uint64_t live, bi_instr *ins)
92
bi_foreach_dest(ins, d) {
93
if (ins->dest[d].type == BI_INDEX_REGISTER) {
94
unsigned nr = bi_count_write_registers(ins, d);
95
unsigned reg = ins->dest[d].value;
96
live &= ~(BITFIELD64_MASK(nr) << reg);
100
bi_foreach_src(ins, s) {
101
if (ins->src[s].type == BI_INDEX_REGISTER) {
102
unsigned nr = bi_count_read_registers(ins, s);
103
unsigned reg = ins->src[s].value;
104
live |= (BITFIELD64_MASK(nr) << reg);
112
bi_postra_liveness_block(bi_block *blk)
114
bi_foreach_successor(blk, succ)
115
blk->reg_live_out |= succ->reg_live_in;
117
uint64_t live = blk->reg_live_out;
119
bi_foreach_instr_in_block_rev(blk, ins)
120
live = bi_postra_liveness_ins(live, ins);
122
bool progress = blk->reg_live_in != live;
123
blk->reg_live_in = live;
127
/* Globally, liveness analysis uses a fixed-point algorithm based on a
128
* worklist. We initialize a work list with the exit block. We iterate the work
129
* list to compute live_in from live_out for each block on the work list,
130
* adding the predecessors of the block to the work list if we made progress.
134
bi_postra_liveness(bi_context *ctx)
137
bi_worklist_init(ctx, &worklist);
139
bi_foreach_block(ctx, block) {
140
block->reg_live_out = block->reg_live_in = 0;
142
bi_worklist_push_tail(&worklist, block);
145
while (!u_worklist_is_empty(&worklist)) {
146
/* Pop off in reverse order since liveness is backwards */
147
bi_block *blk = bi_worklist_pop_tail(&worklist);
149
/* Update liveness information. If we made progress, we need to
150
* reprocess the predecessors
152
if (bi_postra_liveness_block(blk)) {
153
bi_foreach_predecessor(blk, pred)
154
bi_worklist_push_head(&worklist, *pred);
158
u_worklist_fini(&worklist);
162
bi_opt_dce_post_ra(bi_context *ctx)
164
bi_postra_liveness(ctx);
166
bi_foreach_block_rev(ctx, block) {
167
uint64_t live = block->reg_live_out;
169
bi_foreach_instr_in_block_rev(block, ins) {
170
if (ins->op == BI_OPCODE_DTSEL_IMM)
171
ins->dest[0] = bi_null();
173
bi_foreach_dest(ins, d) {
174
if (ins->dest[d].type != BI_INDEX_REGISTER)
177
unsigned nr = bi_count_write_registers(ins, d);
178
unsigned reg = ins->dest[d].value;
179
uint64_t mask = (BITFIELD64_MASK(nr) << reg);
180
bool cullable = (ins->op != BI_OPCODE_BLEND);
181
cullable &= !bi_opcode_props[ins->op].sr_write;
183
if (!(live & mask) && cullable)
184
ins->dest[d] = bi_null();
187
live = bi_postra_liveness_ins(live, ins);