1 /*
2  * Copyright (C) 2021 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 FROM,
20  * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
21  * SOFTWARE.
22  */
23 
24 #include "ir3_ra.h"
25 #include "ir3_shader.h"
26 #include "ralloc.h"
27 
28 /* A note on how phi node uses are handled:
29  *
30  * - Phi node sources are considered to happen after the end of the
31  *   predecessor block, so the live_out for that block contains phi sources.
32  * - On the other hand, phi destinations are considered to happen at the start
33  *   of the block, so that live_in does *not* contain phi destinations. This
34  *   is mainly because phi destinations and live-through values have to be
35  *   treated very differently by RA at the beginning of a block.
36  */
37 
38 static bool
compute_block_liveness(struct ir3_liveness * live,struct ir3_block * block,BITSET_WORD * tmp_live,unsigned bitset_words)39 compute_block_liveness(struct ir3_liveness *live, struct ir3_block *block,
40                        BITSET_WORD *tmp_live, unsigned bitset_words)
41 {
42    memcpy(tmp_live, live->live_out[block->index],
43           bitset_words * sizeof(BITSET_WORD));
44 
45    /* Process instructions */
46    foreach_instr_rev (instr, &block->instr_list) {
47       ra_foreach_dst (dst, instr) {
48          if (BITSET_TEST(tmp_live, dst->name))
49             dst->flags &= ~IR3_REG_UNUSED;
50          else
51             dst->flags |= IR3_REG_UNUSED;
52          BITSET_CLEAR(tmp_live, dst->name);
53       }
54 
55       /* Phi node uses occur after the predecessor block */
56       if (instr->opc != OPC_META_PHI) {
57          ra_foreach_src (src, instr) {
58             if (BITSET_TEST(tmp_live, src->def->name))
59                src->flags &= ~IR3_REG_KILL;
60             else
61                src->flags |= IR3_REG_KILL;
62          }
63 
64          ra_foreach_src (src, instr) {
65             if (BITSET_TEST(tmp_live, src->def->name))
66                src->flags &= ~IR3_REG_FIRST_KILL;
67             else
68                src->flags |= IR3_REG_FIRST_KILL;
69             BITSET_SET(tmp_live, src->def->name);
70          }
71       }
72    }
73 
74    memcpy(live->live_in[block->index], tmp_live,
75           bitset_words * sizeof(BITSET_WORD));
76 
77    bool progress = false;
78    for (unsigned i = 0; i < block->predecessors_count; i++) {
79       const struct ir3_block *pred = block->predecessors[i];
80       for (unsigned j = 0; j < bitset_words; j++) {
81          if (tmp_live[j] & ~live->live_out[pred->index][j])
82             progress = true;
83          live->live_out[pred->index][j] |= tmp_live[j];
84       }
85 
86       /* Process phi sources. */
87       foreach_instr (phi, &block->instr_list) {
88          if (phi->opc != OPC_META_PHI)
89             break;
90          if (!phi->srcs[i]->def)
91             continue;
92          unsigned name = phi->srcs[i]->def->name;
93          if (!BITSET_TEST(live->live_out[pred->index], name)) {
94             progress = true;
95             BITSET_SET(live->live_out[pred->index], name);
96          }
97       }
98    }
99 
100    for (unsigned i = 0; i < block->physical_predecessors_count; i++) {
101       const struct ir3_block *pred = block->physical_predecessors[i];
102       unsigned name;
103       BITSET_FOREACH_SET (name, tmp_live, live->definitions_count) {
104          struct ir3_register *reg = live->definitions[name];
105          if (!(reg->flags & IR3_REG_SHARED))
106             continue;
107          if (!BITSET_TEST(live->live_out[pred->index], name)) {
108             progress = true;
109             BITSET_SET(live->live_out[pred->index], name);
110          }
111       }
112    }
113 
114    return progress;
115 }
116 
117 struct ir3_liveness *
ir3_calc_liveness(void * mem_ctx,struct ir3 * ir)118 ir3_calc_liveness(void *mem_ctx, struct ir3 *ir)
119 {
120    struct ir3_liveness *live = rzalloc(mem_ctx, struct ir3_liveness);
121 
122    /* Reserve name 0 to mean "doesn't have a name yet" to make the debug
123     * output nicer.
124     */
125    array_insert(live, live->definitions, NULL);
126 
127    /* Build definition <-> name mapping */
128    unsigned block_count = 0;
129    foreach_block (block, &ir->block_list) {
130       block->index = block_count++;
131       foreach_instr (instr, &block->instr_list) {
132          ra_foreach_dst (dst, instr) {
133             dst->name = live->definitions_count;
134             array_insert(live, live->definitions, dst);
135          }
136       }
137    }
138 
139    live->block_count = block_count;
140 
141    unsigned bitset_words = BITSET_WORDS(live->definitions_count);
142    BITSET_WORD *tmp_live = ralloc_array(live, BITSET_WORD, bitset_words);
143    live->live_in = ralloc_array(live, BITSET_WORD *, block_count);
144    live->live_out = ralloc_array(live, BITSET_WORD *, block_count);
145    unsigned i = 0;
146    foreach_block (block, &ir->block_list) {
147       block->index = i++;
148       live->live_in[block->index] =
149          rzalloc_array(live, BITSET_WORD, bitset_words);
150       live->live_out[block->index] =
151          rzalloc_array(live, BITSET_WORD, bitset_words);
152    }
153 
154    bool progress = true;
155    while (progress) {
156       progress = false;
157       foreach_block_rev (block, &ir->block_list) {
158          progress |=
159             compute_block_liveness(live, block, tmp_live, bitset_words);
160       }
161    }
162 
163    return live;
164 }
165 
166 /* Return true if "def" is live after "instr". It's assumed that "def"
167  * dominates "instr".
168  */
169 bool
ir3_def_live_after(struct ir3_liveness * live,struct ir3_register * def,struct ir3_instruction * instr)170 ir3_def_live_after(struct ir3_liveness *live, struct ir3_register *def,
171                    struct ir3_instruction *instr)
172 {
173    /* If it's live out then it's definitely live at the instruction. */
174    if (BITSET_TEST(live->live_out[instr->block->index], def->name))
175       return true;
176 
177    /* If it's not live in and not defined in the same block then the live
178     * range can't extend to the instruction.
179     */
180    if (def->instr->block != instr->block &&
181        !BITSET_TEST(live->live_in[instr->block->index], def->name))
182       return false;
183 
184    /* Ok, now comes the tricky case, where "def" is killed somewhere in
185     * "instr"'s block and we have to check if it's before or after.
186     */
187    foreach_instr_rev (test_instr, &instr->block->instr_list) {
188       if (test_instr == instr)
189          break;
190 
191       for (unsigned i = 0; i < test_instr->srcs_count; i++) {
192          if (test_instr->srcs[i]->def == def)
193             return true;
194       }
195    }
196 
197    return false;
198 }
199