1/*
2 * Copyright (C) 2019-2020 Collabora, Ltd.
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 "pan_ir.h"
25#include "util/u_memory.h"
26#include "util/list.h"
27#include "util/set.h"
28
29/* Routines for liveness analysis. Liveness is tracked per byte per node. Per
30 * byte granularity is necessary for proper handling of int8 */
31
32void
33pan_liveness_gen(uint16_t *live, unsigned node, unsigned max, uint16_t mask)
34{
35        if (node >= max)
36                return;
37
38        live[node] |= mask;
39}
40
41void
42pan_liveness_kill(uint16_t *live, unsigned node, unsigned max, uint16_t mask)
43{
44        if (node >= max)
45                return;
46
47        live[node] &= ~mask;
48}
49
50bool
51pan_liveness_get(uint16_t *live, unsigned node, uint16_t max)
52{
53        if (node >= max)
54                return false;
55
56        return live[node];
57}
58
59/* live_out[s] = sum { p in succ[s] } ( live_in[p] ) */
60
61static void
62liveness_block_live_out(pan_block *blk, unsigned temp_count)
63{
64        pan_foreach_successor(blk, succ) {
65                for (unsigned i = 0; i < temp_count; ++i)
66                        blk->live_out[i] |= succ->live_in[i];
67        }
68}
69
70/* Liveness analysis is a backwards-may dataflow analysis pass. Within a block,
71 * we compute live_out from live_in. The intrablock pass is linear-time. It
72 * returns whether progress was made. */
73
74static bool
75liveness_block_update(
76                pan_block *blk, unsigned temp_count,
77                pan_liveness_update callback)
78{
79        bool progress = false;
80
81        liveness_block_live_out(blk, temp_count);
82
83        uint16_t *live = ralloc_array(blk, uint16_t, temp_count);
84        memcpy(live, blk->live_out, temp_count * sizeof(uint16_t));
85
86        pan_foreach_instr_in_block_rev(blk, ins)
87                callback(live, (void *) ins, temp_count);
88
89        /* To figure out progress, diff live_in */
90
91        for (unsigned i = 0; (i < temp_count) && !progress; ++i)
92                progress |= (blk->live_in[i] != live[i]);
93
94        ralloc_free(blk->live_in);
95        blk->live_in = live;
96
97        return progress;
98}
99
100
101/* Globally, liveness analysis uses a fixed-point algorithm based on a
102 * worklist. We initialize a work list with the exit block. We iterate the work
103 * list to compute live_in from live_out for each block on the work list,
104 * adding the predecessors of the block to the work list if we made progress.
105 */
106
107void
108pan_compute_liveness(
109                struct list_head *blocks,
110                unsigned temp_count,
111                pan_liveness_update callback)
112{
113
114        /* Set of pan_block */
115        struct set *work_list = _mesa_set_create(NULL,
116                        _mesa_hash_pointer,
117                        _mesa_key_pointer_equal);
118
119        struct set *visited = _mesa_set_create(NULL,
120                        _mesa_hash_pointer,
121                        _mesa_key_pointer_equal);
122
123        /* Free any previous liveness, and allocate */
124
125        pan_free_liveness(blocks);
126
127        list_for_each_entry(pan_block, block, blocks, link) {
128                block->live_in = rzalloc_array(block, uint16_t, temp_count);
129                block->live_out = rzalloc_array(block, uint16_t, temp_count);
130        }
131
132        /* Initialize the work list with the exit block */
133        struct set_entry *cur;
134
135        cur = _mesa_set_add(work_list, pan_exit_block(blocks));
136
137        /* Iterate the work list */
138
139        do {
140                /* Pop off a block */
141                pan_block *blk = (struct pan_block *) cur->key;
142                _mesa_set_remove(work_list, cur);
143
144                /* Update its liveness information */
145                bool progress = liveness_block_update(blk, temp_count, callback);
146
147                /* If we made progress, we need to process the predecessors */
148
149                if (progress || !_mesa_set_search(visited, blk)) {
150                        pan_foreach_predecessor(blk, pred)
151                                _mesa_set_add(work_list, pred);
152                }
153
154                _mesa_set_add(visited, blk);
155        } while((cur = _mesa_set_next_entry(work_list, NULL)) != NULL);
156
157        _mesa_set_destroy(visited, NULL);
158        _mesa_set_destroy(work_list, NULL);
159}
160
161void
162pan_free_liveness(struct list_head *blocks)
163{
164        list_for_each_entry(pan_block, block, blocks, link) {
165                if (block->live_in)
166                        ralloc_free(block->live_in);
167
168                if (block->live_out)
169                        ralloc_free(block->live_out);
170
171                block->live_in = NULL;
172                block->live_out = NULL;
173        }
174}
175