Home | History | Annotate | Line # | Download | only in util 
      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 }
    175