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
32 void
pan_liveness_gen(uint16_t * live,unsigned node,unsigned max,uint16_t mask)33 pan_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
41 void
pan_liveness_kill(uint16_t * live,unsigned node,unsigned max,uint16_t mask)42 pan_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
50 bool
pan_liveness_get(uint16_t * live,unsigned node,uint16_t max)51 pan_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
61 static void
liveness_block_live_out(pan_block * blk,unsigned temp_count)62 liveness_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
74 static bool
liveness_block_update(pan_block * blk,unsigned temp_count,pan_liveness_update callback)75 liveness_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
107 void
pan_compute_liveness(struct list_head * blocks,unsigned temp_count,pan_liveness_update callback)108 pan_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
161 void
pan_free_liveness(struct list_head * blocks)162 pan_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