src/panfrost/util/pan_liveness.c

   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
  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
  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
  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
  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
  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 static inline pan_block *
 108 pan_exit_block(struct list_head *blocks)
 109 {
 110         pan_block *last = list_last_entry(blocks, pan_block, link);
 111         assert(last->nr_successors == 0);
 112         return last;
 113 }
 114
 115 void
 116 pan_compute_liveness(
 117                 struct list_head *blocks,
 118                 unsigned temp_count,
 119                 pan_liveness_update callback)
 120 {
 121
 122         /* Set of pan_block */
 123         struct set *work_list = _mesa_set_create(NULL,
 124                         _mesa_hash_pointer,
 125                         _mesa_key_pointer_equal);
 126
 127         struct set *visited = _mesa_set_create(NULL,
 128                         _mesa_hash_pointer,
 129                         _mesa_key_pointer_equal);
 130
 131         /* Allocate */
 132
 133         list_for_each_entry(pan_block, block, blocks, link) {
 134                 block->live_in = rzalloc_array(NULL, uint16_t, temp_count);
 135                 block->live_out = rzalloc_array(NULL, uint16_t, temp_count);
 136         }
 137
 138         /* Initialize the work list with the exit block */
 139         struct set_entry *cur;
 140
 141         cur = _mesa_set_add(work_list, pan_exit_block(blocks));
 142
 143         /* Iterate the work list */
 144
 145         do {
 146                 /* Pop off a block */
 147                 pan_block *blk = (struct pan_block *) cur->key;
 148                 _mesa_set_remove(work_list, cur);
 149
 150                 /* Update its liveness information */
 151                 bool progress = liveness_block_update(blk, temp_count, callback);
 152
 153                 /* If we made progress, we need to process the predecessors */
 154
 155                 if (progress || !_mesa_set_search(visited, blk)) {
 156                         pan_foreach_predecessor(blk, pred)
 157                                 _mesa_set_add(work_list, pred);
 158                 }
 159
 160                 _mesa_set_add(visited, blk);
 161         } while((cur = _mesa_set_next_entry(work_list, NULL)) != NULL);
 162
 163         _mesa_set_destroy(visited, NULL);
 164         _mesa_set_destroy(work_list, NULL);
 165 }
 166
 167 void
 168 pan_free_liveness(struct list_head *blocks)
 169 {
 170         list_for_each_entry(pan_block, block, blocks, link) {
 171                 if (block->live_in)
 172                         ralloc_free(block->live_in);
 173
 174                 if (block->live_out)
 175                         ralloc_free(block->live_out);
 176
 177                 block->live_in = NULL;
 178                 block->live_out = NULL;
 179         }
 180 }