src/freedreno/ir3/ir3_sun.c

   1 /*
   2  * Copyright (C) 2018 Rob Clark <robclark@freedesktop.org>
   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  * Authors:
  24  *    Rob Clark <robclark@freedesktop.org>
  25  */
  26
  27
  28 #include "util/u_math.h"
  29
  30 #include "ir3.h"
  31
  32 /*
  33  * A simple pass to do Sethi–Ullman numbering, as described in "Generalizations
  34  * of the Sethi-Ullman algorithm for register allocation"[1].  This is used by
  35  * the scheduler pass.
  36  *
  37  * TODO this could probably be more clever about flow control, ie. if a src
  38  * is computed in multiple paths into a block, I think we should only have to
  39  * consider the worst-case.
  40  *
  41  * [1] https://www.cs.princeton.edu/~appel/papers/sun.pdf
  42  */
  43
  44 static unsigned
  45 number_instr(struct ir3_instruction *instr)
  46 {
  47         if (ir3_instr_check_mark(instr))
  48                 return instr->sun;
  49
  50         struct ir3_instruction *src;
  51         const unsigned n = __ssa_src_cnt(instr);
  52         unsigned a[n];
  53         unsigned b[n];
  54         unsigned i = 0;
  55
  56         /* TODO I think including false-deps in the calculation is the right
  57          * thing to do:
  58          */
  59         foreach_ssa_src_n (src, n, instr) {
  60                 if (__is_false_dep(instr, n))
  61                         continue;
  62                 if (src->block != instr->block) {
  63                         a[i] = 1;
  64                 } else {
  65                         a[i] = number_instr(src);
  66                 }
  67                 b[i] = dest_regs(src);
  68                 i++;
  69         }
  70
  71         /*
  72          * Rπ = max(aπ(1), bπ(1) + max(aπ(2), bπ(2) + max(..., bπ(k−1) + max(aπ(k), bπ(k)))...):
  73          */
  74         unsigned last_r = 0;
  75
  76         for (int k = i - 1; k >= 0; k--) {
  77                 unsigned r = MAX2(a[k], b[k] + last_r);
  78
  79                 if (k > 0)
  80                         r += b[k-1];
  81
  82                 last_r = r;
  83         }
  84
  85         last_r = MAX2(last_r, dest_regs(instr));
  86
  87         instr->sun = last_r;
  88
  89         return instr->sun;
  90 }
  91
  92 void
  93 ir3_sun(struct ir3 *ir)
  94 {
  95         unsigned max = 0;
  96
  97         ir3_clear_mark(ir);
  98
  99         struct ir3_instruction *out;
 100         foreach_output (out, ir)
 101                 max = MAX2(max, number_instr(out));
 102
 103         foreach_block (block, &ir->block_list) {
 104                 for (unsigned i = 0; i < block->keeps_count; i++)
 105                         max = MAX2(max, number_instr(block->keeps[i]));
 106                 if (block->condition)
 107                         max = MAX2(max, number_instr(block->condition));
 108         }
 109
 110         ir->max_sun = max;
 111 }