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                         struct ppir_liveness *dest, struct ppir_liveness *src,
  32                         struct set *dest_set, struct set *src_set)
  33 {
  34    set_foreach(src_set, entry_src) {
  35       const struct ppir_liveness *s = entry_src->key;
  36       assert(s);
  37
  38       unsigned int regalloc_index = s->reg->regalloc_index;
  39
  40       dest[regalloc_index].reg = src[regalloc_index].reg;
  41       dest[regalloc_index].mask |= src[regalloc_index].mask;
  42       _mesa_set_add(dest_set, &dest[regalloc_index]);
  43    }
  44 }
  45
  46 /* Clone a liveness set (without propagation) */
  47 static void
  48 ppir_liveness_set_clone(ppir_compiler *comp,
  49                         struct ppir_liveness *dest, struct ppir_liveness *src,
  50                         struct set *dest_set, struct set *src_set)
  51 {
  52    _mesa_set_clear(dest_set, NULL);
  53    memset(dest, 0, list_length(&comp->reg_list) * sizeof(struct ppir_liveness));
  54    memcpy(dest, src,
  55           list_length(&comp->reg_list) * sizeof(struct ppir_liveness));
  56
  57    set_foreach(src_set, entry_src) {
  58       const struct ppir_liveness *s = entry_src->key;
  59       assert(s);
  60
  61       unsigned int regalloc_index = s->reg->regalloc_index;
  62       dest[regalloc_index].reg = src[regalloc_index].reg;
  63       dest[regalloc_index].mask = src[regalloc_index].mask;
  64       _mesa_set_add(dest_set, &dest[regalloc_index]);
  65    }
  66 }
  67
  68 /* Check whether two liveness sets are equal. */
  69 static bool
  70 ppir_liveness_set_equal(ppir_compiler *comp,
  71                         struct ppir_liveness *l1, struct ppir_liveness *l2,
  72                         struct set *set1, struct set *set2)
  73 {
  74    set_foreach(set1, entry1) {
  75       const struct ppir_liveness *k1 = entry1->key;
  76       unsigned int regalloc_index = k1->reg->regalloc_index;
  77
  78       struct set_entry *entry2 = _mesa_set_search(set2, &l2[regalloc_index]);
  79       if (!entry2)
  80          return false;
  81
  82       const struct ppir_liveness *k2 = entry2->key;
  83
  84       if (k1->mask != k2->mask)
  85          return false;
  86    }
  87    set_foreach(set2, entry2) {
  88       const struct ppir_liveness *k2 = entry2->key;
  89       unsigned int regalloc_index = k2->reg->regalloc_index;
  90
  91       struct set_entry *entry1 = _mesa_set_search(set1, &l1[regalloc_index]);
  92       if (!entry1)
  93          return false;
  94
  95       const struct ppir_liveness *k1 = entry1->key;
  96
  97       if (k2->mask != k1->mask)
  98          return false;
  99    }
 100    return true;
 101 }
 102
 103 /* Update the liveness information of the instruction by adding its srcs
 104  * as live registers to the live_in set. */
 105 static void
 106 ppir_liveness_instr_srcs(ppir_compiler *comp, ppir_instr *instr)
 107 {
 108    for (int i = PPIR_INSTR_SLOT_NUM-1; i >= 0; i--) {
 109       ppir_node *node = instr->slots[i];
 110       if (!node)
 111          continue;
 112
 113       switch(node->op) {
 114          case ppir_op_const:
 115          case ppir_op_undef:
 116             continue;
 117          default:
 118             break;
 119       }
 120
 121       for (int i = 0; i < ppir_node_get_src_num(node); i++) {
 122          ppir_src *src = ppir_node_get_src(node, i);
 123          if (!src || src->type == ppir_target_pipeline)
 124             continue;
 125
 126          ppir_reg *reg = ppir_src_get_reg(src);
 127          if (!reg || reg->undef)
 128             continue;
 129
 130          /* if some other op on this same instruction is writing,
 131           * we just need to reserve a register for this particular
 132           * instruction. */
 133          if (src->node && src->node->instr == instr) {
 134             instr->live_internal[reg->regalloc_index].reg = reg;
 135             _mesa_set_add(instr->live_internal_set, &instr->live_internal[reg->regalloc_index]);
 136             continue;
 137          }
 138
 139          struct set_entry *live = _mesa_set_search(instr->live_in_set,
 140                                                    &instr->live_in[reg->regalloc_index]);
 141          if (src->type == ppir_target_ssa) {
 142             /* reg is read, needs to be live before instr */
 143             if (live)
 144                continue;
 145
 146             instr->live_in[reg->regalloc_index].reg = reg;
 147             _mesa_set_add(instr->live_in_set, &instr->live_in[reg->regalloc_index]);
 148          }
 149          else {
 150             unsigned int mask = ppir_src_get_mask(src);
 151
 152             /* read reg is type register, need to check if this sets
 153              * any additional bits in the current mask */
 154             if (live && (instr->live_in[reg->regalloc_index].mask ==
 155                         (instr->live_in[reg->regalloc_index].mask | mask)))
 156                continue;
 157
 158             /* some new components */
 159             instr->live_in[reg->regalloc_index].reg = reg;
 160             instr->live_in[reg->regalloc_index].mask |= mask;
 161             _mesa_set_add(instr->live_in_set, &instr->live_in[reg->regalloc_index]);
 162          }
 163       }
 164    }
 165 }
 166
 167
 168 /* Update the liveness information of the instruction by removing its
 169  * dests from the live_in set. */
 170 static void
 171 ppir_liveness_instr_dest(ppir_compiler *comp, ppir_instr *instr)
 172 {
 173    for (int i = PPIR_INSTR_SLOT_NUM-1; i >= 0; i--) {
 174       ppir_node *node = instr->slots[i];
 175       if (!node)
 176          continue;
 177
 178       switch(node->op) {
 179          case ppir_op_const:
 180          case ppir_op_undef:
 181          case ppir_op_store_color: /* never clear dest if its store output */
 182             continue;
 183          default:
 184             break;
 185       }
 186
 187       ppir_dest *dest = ppir_node_get_dest(node);
 188       if (!dest || dest->type == ppir_target_pipeline)
 189          continue;
 190       ppir_reg *reg = ppir_dest_get_reg(dest);
 191       if (!reg || reg->undef)
 192          continue;
 193
 194       struct set_entry *live = _mesa_set_search(instr->live_in_set,
 195                                                 &instr->live_in[reg->regalloc_index]);
 196
 197       /* If a register is written but wasn't read in a later instruction, it is
 198        * either dead code or a bug. For now, assign an interference to it to
 199        * ensure it doesn't get assigned a live register and overwrites it. */
 200       if (!live) {
 201          instr->live_internal[reg->regalloc_index].reg = reg;
 202          _mesa_set_add(instr->live_internal_set, &instr->live_internal[reg->regalloc_index]);
 203          continue;
 204       }
 205
 206       if (dest->type == ppir_target_ssa) {
 207          /* reg is written and ssa, is not live before instr */
 208          _mesa_set_remove_key(instr->live_in_set, &instr->live_in[reg->regalloc_index]);
 209       }
 210       else {
 211          unsigned int mask = dest->write_mask;
 212          /* written reg is type register, need to check if this clears
 213           * the remaining mask to remove it from the live set */
 214          if (instr->live_in[reg->regalloc_index].mask ==
 215              (instr->live_in[reg->regalloc_index].mask & ~mask))
 216             continue;
 217
 218          instr->live_in[reg->regalloc_index].mask &= ~mask;
 219          /* unset reg if all remaining bits were cleared */
 220          if (!instr->live_in[reg->regalloc_index].mask) {
 221             _mesa_set_remove_key(instr->live_in_set, &instr->live_in[reg->regalloc_index]);
 222          }
 223       }
 224    }
 225 }
 226
 227 /* Main loop, iterate blocks/instructions/ops backwards, propagate
 228  * livenss and update liveness of each instruction. */
 229 static bool
 230 ppir_liveness_compute_live_sets(ppir_compiler *comp)
 231 {
 232    bool cont = false;
 233    list_for_each_entry_rev(ppir_block, block, &comp->block_list, list) {
 234       ppir_instr *first = list_first_entry(&block->instr_list, ppir_instr, list);
 235       ppir_instr *last = list_last_entry(&block->instr_list, ppir_instr, list);
 236
 237       /* inherit live_out from the other blocks live_in */
 238       for (int i = 0; i < 2; i++) {
 239          ppir_block *succ = block->successors[i];
 240          if (!succ)
 241             continue;
 242
 243          ppir_liveness_propagate(comp, block->live_out, succ->live_in,
 244                                  block->live_out_set, succ->live_in_set);
 245       }
 246
 247       list_for_each_entry_rev(ppir_instr, instr, &block->instr_list, list) {
 248          /* inherit (or-) live variables from next instr or block */
 249          if (instr == last) {
 250             ppir_liveness_set_clone(comp,
 251                                     instr->live_out, block->live_out,
 252                                     instr->live_out_set, block->live_out_set);
 253          }
 254          else {
 255             ppir_instr *next_instr = LIST_ENTRY(ppir_instr, instr->list.next, list);
 256             ppir_liveness_set_clone(comp,
 257                                     instr->live_out, next_instr->live_in,
 258                                     instr->live_out_set, next_instr->live_in_set);
 259          }
 260          /* initial copy to check for changes */
 261          struct set *temp_live_in_set = _mesa_set_create(comp,
 262                                                          _mesa_hash_pointer,
 263                                                          _mesa_key_pointer_equal);
 264          struct ppir_liveness temp_live_in[list_length(&comp->reg_list)];
 265          ppir_liveness_set_clone(comp,
 266                temp_live_in, instr->live_in,
 267                temp_live_in_set, instr->live_in_set);
 268
 269          /* initialize live_in for potential changes */
 270          ppir_liveness_propagate(comp, instr->live_in, instr->live_out,
 271                                  instr->live_in_set, instr->live_out_set);
 272
 273          ppir_liveness_instr_dest(comp, instr);
 274          ppir_liveness_instr_srcs(comp, instr);
 275
 276          cont |= !ppir_liveness_set_equal(comp, temp_live_in, instr->live_in,
 277                temp_live_in_set, instr->live_in_set);
 278       }
 279
 280       /* inherit live_in from the first instruction in the block,
 281        * or live_out if it is empty */
 282       if (!list_is_empty(&block->instr_list) && first && first->scheduled)
 283          ppir_liveness_set_clone(comp, block->live_in, first->live_in,
 284                block->live_in_set, first->live_in_set);
 285       else
 286          ppir_liveness_set_clone(comp, block->live_in, block->live_out,
 287                block->live_in_set, block->live_out_set);
 288    }
 289
 290    return cont;
 291 }
 292
 293 /*
 294  * Liveness analysis is based on https://en.wikipedia.org/wiki/Live_variable_analysis
 295  * This implementation calculates liveness before/after each
 296  * instruction. Aggregated block liveness information is stored
 297  * before/after blocks for conveniency (handle e.g. empty blocks).
 298  * Blocks/instructions/ops are iterated backwards so register reads are
 299  * propagated up to the instruction that writes it.
 300  *
 301  * 1) Before computing liveness for each instruction, propagate live_out
 302  *    from the next instruction. If it is the last instruction in a
 303  *    block, propagate liveness from all possible next instructions
 304  *    (in this case, this information comes from the live_out of the
 305  *    block itself).
 306  * 2) Calculate live_in for the each instruction. The initial live_in is
 307  *    a copy of its live_out so registers who aren't touched by this
 308  *    instruction are kept intact.
 309  *    - If a register is written by this instruction, it no longer needs
 310  *    to be live before the instruction, so it is removed from live_in.
 311  *    - If a register is read by this instruction, it needs to be live
 312  *    before its execution, so add it to live_in.
 313  *    - Non-ssa registers are a special case. For this, the algorithm
 314  *    keeps and updates the mask of live components following the same
 315  *    logic as above. The register is only removed from the live set
 316  *    when no live components are left.
 317  *    - If a non-ssa register is written and read in the same
 318  *    instruction, it stays in live_in.
 319  *    - Another special case is a ssa register that is written by an
 320  *    early op in the instruction, and read by a later op. In this case,
 321  *    the algorithm adds it to the live_out set so that the register
 322  *    allocator properly assigns an interference for it.
 323  * 3) The algorithm must run over the entire program until it converges,
 324  *    i.e. a full run happens without changes. This is because blocks
 325  *    are updated sequentially and updates in a block may need to be
 326  *    propagated to parent blocks that were already calculated in the
 327  *    current run.
 328  */
 329 void
 330 ppir_liveness_analysis(ppir_compiler *comp)
 331 {
 332    while (ppir_liveness_compute_live_sets(comp))
 333       ;
 334 }