← Back to branch summary

~mmach/netext73/mesa_2004

« back to all changes in this revision

Viewing changes to src/gallium/drivers/lima/ir/pp/liveness.c

  • Committer: mmach
  • Date: 2022-09-22 20:00:35 UTC
  • Revision ID: netbit73@gmail.com-20220922200035-j2mt0pv92d002zy3
2022-09-22 21:17:58

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/gallium/drivers/lima/ir/pp/liveness.c
 
1
/*
 
2
 * Copyright (c) 2019 Lima Project
 
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, sub license,
 
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
 
12
 * next paragraph) shall be included in all copies or substantial portions
 
13
 * of the 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 NON-INFRINGEMENT. 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
 
20
 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
 
21
 * DEALINGS IN THE SOFTWARE.
 
22
 *
 
23
 */
 
24
 
 
25
#include "ppir.h"
 
26
 
 
27
/* Propagates liveness from a liveness set to another by performing the
 
28
 * union between sets. */
 
29
static void
 
30
ppir_liveness_propagate(ppir_compiler *comp,
 
31
                        BITSET_WORD *dest_set, BITSET_WORD *src_set,
 
32
                        uint8_t *dest_mask, uint8_t *src_mask)
 
33
{
 
34
   for (int i = 0; i < BITSET_WORDS(comp->reg_num); i++)
 
35
      dest_set[i] |= src_set[i];
 
36
 
 
37
   for (int i = 0; i < reg_mask_size(comp->reg_num); i++)
 
38
      dest_mask[i] |= src_mask[i];
 
39
}
 
40
 
 
41
/* Check whether two liveness sets are equal. */
 
42
static bool
 
43
ppir_liveness_set_equal(ppir_compiler *comp,
 
44
                        BITSET_WORD *set1, BITSET_WORD *set2,
 
45
                        uint8_t *mask1, uint8_t *mask2)
 
46
{
 
47
   for (int i = 0; i < BITSET_WORDS(comp->reg_num); i++)
 
48
      if (set1[i] != set2[i])
 
49
         return false;
 
50
 
 
51
   for (int i = 0; i < reg_mask_size(comp->reg_num); i++)
 
52
      if (mask1[i] != mask2[i])
 
53
         return false;
 
54
 
 
55
   return true;
 
56
}
 
57
 
 
58
/* Update the liveness information of the instruction by adding its srcs
 
59
 * as live registers to the live_in set. */
 
60
static void
 
61
ppir_liveness_instr_srcs(ppir_compiler *comp, ppir_instr *instr)
 
62
{
 
63
   for (int i = PPIR_INSTR_SLOT_NUM-1; i >= 0; i--) {
 
64
      ppir_node *node = instr->slots[i];
 
65
      if (!node)
 
66
         continue;
 
67
 
 
68
      switch(node->op) {
 
69
         case ppir_op_const:
 
70
         case ppir_op_undef:
 
71
            continue;
 
72
         default:
 
73
            break;
 
74
      }
 
75
 
 
76
      for (int i = 0; i < ppir_node_get_src_num(node); i++) {
 
77
         ppir_src *src = ppir_node_get_src(node, i);
 
78
         if (!src || src->type == ppir_target_pipeline)
 
79
            continue;
 
80
 
 
81
         ppir_reg *reg = ppir_src_get_reg(src);
 
82
         if (!reg || reg->undef)
 
83
            continue;
 
84
 
 
85
         unsigned int index = reg->regalloc_index;
 
86
 
 
87
         /* if some other op on this same instruction is writing,
 
88
          * we just need to reserve a register for this particular
 
89
          * instruction. */
 
90
         if (src->node && src->node->instr == instr) {
 
91
            BITSET_SET(instr->live_internal, index);
 
92
            continue;
 
93
         }
 
94
 
 
95
         bool live = BITSET_TEST(instr->live_set, index);
 
96
         if (src->type == ppir_target_ssa) {
 
97
            /* reg is read, needs to be live before instr */
 
98
            if (live)
 
99
               continue;
 
100
 
 
101
            BITSET_SET(instr->live_set, index);
 
102
         }
 
103
         else {
 
104
            unsigned int mask = ppir_src_get_mask(src);
 
105
            uint8_t live_mask = get_reg_mask(instr->live_mask, index);
 
106
 
 
107
            /* read reg is type register, need to check if this sets
 
108
             * any additional bits in the current mask */
 
109
            if (live && (live_mask == (live_mask | mask)))
 
110
               continue;
 
111
 
 
112
            /* some new components */
 
113
            set_reg_mask(instr->live_mask, index, (live_mask | mask));
 
114
            BITSET_SET(instr->live_set, index);
 
115
         }
 
116
      }
 
117
   }
 
118
}
 
119
 
 
120
 
 
121
/* Update the liveness information of the instruction by removing its
 
122
 * dests from the live_in set. */
 
123
static void
 
124
ppir_liveness_instr_dest(ppir_compiler *comp, ppir_instr *instr, ppir_instr *last)
 
125
{
 
126
   for (int i = PPIR_INSTR_SLOT_NUM-1; i >= 0; i--) {
 
127
      ppir_node *node = instr->slots[i];
 
128
      if (!node)
 
129
         continue;
 
130
 
 
131
      switch(node->op) {
 
132
         case ppir_op_const:
 
133
         case ppir_op_undef:
 
134
            continue;
 
135
         default:
 
136
            break;
 
137
      }
 
138
 
 
139
      ppir_dest *dest = ppir_node_get_dest(node);
 
140
      if (!dest || dest->type == ppir_target_pipeline)
 
141
         continue;
 
142
      ppir_reg *reg = ppir_dest_get_reg(dest);
 
143
      if (!reg || reg->undef)
 
144
         continue;
 
145
 
 
146
      unsigned int index = reg->regalloc_index;
 
147
      bool live = BITSET_TEST(instr->live_set, index);
 
148
 
 
149
      /* If it's an out reg, it's alive till the end of the block, so add it
 
150
       * to live_set of the last instruction */
 
151
      if (!live && reg->out_reg && (instr != last)) {
 
152
         BITSET_SET(last->live_set, index);
 
153
         BITSET_CLEAR(instr->live_set, index);
 
154
         continue;
 
155
      }
 
156
 
 
157
      /* If a register is written but wasn't read in a later instruction, it is
 
158
       * either an output register in last instruction, dead code or a bug.
 
159
       * For now, assign an interference to it to ensure it doesn't get assigned
 
160
       * a live register and overwrites it. */
 
161
      if (!live) {
 
162
         BITSET_SET(instr->live_internal, index);
 
163
         continue;
 
164
      }
 
165
 
 
166
      if (dest->type == ppir_target_ssa) {
 
167
         /* reg is written and ssa, is not live before instr */
 
168
         BITSET_CLEAR(instr->live_set, index);
 
169
      }
 
170
      else {
 
171
         unsigned int mask = dest->write_mask;
 
172
         uint8_t live_mask = get_reg_mask(instr->live_mask, index);
 
173
         /* written reg is type register, need to check if this clears
 
174
          * the remaining mask to remove it from the live set */
 
175
         if (live_mask == (live_mask & ~mask))
 
176
            continue;
 
177
 
 
178
         set_reg_mask(instr->live_mask, index, (live_mask & ~mask));
 
179
         /* unset reg if all remaining bits were cleared */
 
180
         if ((live_mask & ~mask) == 0) {
 
181
            BITSET_CLEAR(instr->live_set, index);
 
182
         }
 
183
      }
 
184
   }
 
185
}
 
186
 
 
187
/* Main loop, iterate blocks/instructions/ops backwards, propagate
 
188
 * livenss and update liveness of each instruction. */
 
189
static bool
 
190
ppir_liveness_compute_live_sets(ppir_compiler *comp)
 
191
{
 
192
   uint8_t temp_live_mask[reg_mask_size(comp->reg_num)];
 
193
   BITSET_DECLARE(temp_live_set, comp->reg_num);
 
194
   bool cont = false;
 
195
   list_for_each_entry_rev(ppir_block, block, &comp->block_list, list) {
 
196
      if (list_is_empty(&block->instr_list))
 
197
         continue;
 
198
 
 
199
      ppir_instr *last = list_last_entry(&block->instr_list, ppir_instr, list);
 
200
      assert(last);
 
201
 
 
202
      list_for_each_entry_rev(ppir_instr, instr, &block->instr_list, list) {
 
203
         /* initial copy to check for changes */
 
204
         memset(temp_live_mask, 0, sizeof(temp_live_mask));
 
205
         memset(temp_live_set, 0, sizeof(temp_live_set));
 
206
 
 
207
         ppir_liveness_propagate(comp,
 
208
                                 temp_live_set, instr->live_set,
 
209
                                 temp_live_mask, instr->live_mask);
 
210
 
 
211
         /* inherit (or-) live variables from next instr or block */
 
212
         if (instr == last) {
 
213
            ppir_instr *next_instr;
 
214
            /* inherit liveness from the first instruction in the next blocks */
 
215
            for (int i = 0; i < 2; i++) {
 
216
               ppir_block *succ = block->successors[i];
 
217
               if (!succ)
 
218
                  continue;
 
219
 
 
220
               /* if the block is empty, go for the next-next until a non-empty
 
221
                * one is found */
 
222
               while (list_is_empty(&succ->instr_list)) {
 
223
                  assert(succ->successors[0] && !succ->successors[1]);
 
224
                  succ = succ->successors[0];
 
225
               }
 
226
 
 
227
               next_instr = list_first_entry(&succ->instr_list, ppir_instr, list);
 
228
               assert(next_instr);
 
229
 
 
230
               ppir_liveness_propagate(comp,
 
231
                                       instr->live_set, next_instr->live_set,
 
232
                                       instr->live_mask, next_instr->live_mask);
 
233
            }
 
234
         }
 
235
         else {
 
236
            ppir_instr *next_instr = list_entry(instr->list.next, ppir_instr, list);
 
237
            ppir_liveness_propagate(comp,
 
238
                                    instr->live_set, next_instr->live_set,
 
239
                                    instr->live_mask, next_instr->live_mask);
 
240
         }
 
241
 
 
242
         ppir_liveness_instr_dest(comp, instr, last);
 
243
         ppir_liveness_instr_srcs(comp, instr);
 
244
 
 
245
         cont |= !ppir_liveness_set_equal(comp,
 
246
                                          temp_live_set, instr->live_set,
 
247
                                          temp_live_mask, instr->live_mask);
 
248
      }
 
249
   }
 
250
 
 
251
   return cont;
 
252
}
 
253
 
 
254
/*
 
255
 * Liveness analysis is based on https://en.wikipedia.org/wiki/Live_variable_analysis
 
256
 * This implementation calculates liveness for each instruction.
 
257
 * The liveness set in this implementation is defined as the set of
 
258
 * registers live before the instruction executes.
 
259
 * Blocks/instructions/ops are iterated backwards so register reads are
 
260
 * propagated up to the instruction that writes it.
 
261
 *
 
262
 * 1) Before computing liveness for an instruction, propagate liveness
 
263
 *    from the next instruction. If it is the last instruction in a
 
264
 *    block, propagate liveness from all possible next instructions in
 
265
 *    the successor blocks.
 
266
 * 2) Calculate the live set for the instruction. The initial live set
 
267
 *    is a propagated set of the live set from the next instructions.
 
268
 *    - Registers which aren't touched by this instruction are kept
 
269
 *    intact.
 
270
 *    - If a register is written by this instruction, it no longer needs
 
271
 *    to be live before the instruction, so it is removed from the live
 
272
 *    set of that instruction.
 
273
 *    - If a register is read by this instruction, it needs to be live
 
274
 *    before its execution, so add it to its live set.
 
275
 *    - Non-ssa registers are a special case. For this, the algorithm
 
276
 *    keeps and updates the mask of live components following the same
 
277
 *    logic as above. The register is only removed from the live set of
 
278
 *    the instruction when no live components are left.
 
279
 *    - If a non-ssa register is written and read in the same
 
280
 *    instruction, it stays in the live set.
 
281
 *    - Another special case is when a register is only written and read
 
282
 *    within a single instruciton. In this case a register needs to be
 
283
 *    reserved but not propagated. The algorithm adds it to the
 
284
 *    live_internal set so that the register allocator properly assigns
 
285
 *    an interference for it.
 
286
 * 3) The algorithm must run over the entire program until it converges,
 
287
 *    i.e. a full run happens without changes. This is because blocks
 
288
 *    are updated sequentially and updates in a block may need to be
 
289
 *    propagated to parent blocks that were already calculated in the
 
290
 *    current run.
 
291
 */
 
292
void
 
293
ppir_liveness_analysis(ppir_compiler *comp)
 
294
{
 
295
   while (ppir_liveness_compute_live_sets(comp))
 
296
      ;
 
297
}