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 void
 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
 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 }