← Back to branch summary

~mmach/netext73/mesa-haswell

« back to all changes in this revision

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

  • Committer: mmach
  • Date: 2022-09-22 19:56:13 UTC
  • Revision ID: netbit73@gmail.com-20220922195613-wtik9mmy20tmor0i
2022-09-22 21:17:09

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(ppir_instr, instr->list.next, 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
 
}