src/panfrost/bifrost/bi_layout.c

   1 /*
   2  * Copyright (C) 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 "compiler.h"
  25
  26 /* The scheduler packs multiple instructions into a clause (grouped as bundle),
  27  * and the packing code takes in a clause and emits it to the wire. During
  28  * scheduling, we need to lay out the instructions (bundles) and constants
  29  * within the clause so constraints can be resolved during scheduling instead
  30  * of failing packing. These routines will help building clauses from
  31  * instructions so the scheduler can focus on the high-level algorithm, and
  32  * manipulating clause layouts.
  33  */
  34
  35 /* Helper to see if a bundle can be inserted. We must satisfy the invariant:
  36  *
  37  *      constant_count + bundle_count <= 13
  38  *
  39  * ...which is equivalent to the clause ending up with 8 or fewer quardwords.
  40  * Inserting a bundle increases bundle_count by one, and if it reads a unique
  41  * constant, it increases constant_count by one.
  42  */
  43
  44 bool
  45 bi_can_insert_bundle(bi_clause *clause, bool constant)
  46 {
  47         unsigned constant_count = clause->constant_count + (constant ? 1 : 0);
  48         unsigned bundle_count = clause->bundle_count + 1;
  49
  50         return (constant_count + bundle_count) <= 13;
  51 }
  52
  53 /* Helper to calculate the number of quadwords in a clause. This is a function
  54  * of the number of instructions and constants; it doesn't require actually
  55  * packing, which is useful for branch offsets.
  56  *
  57  * Table of instruction count to instruction quadwords, per the packing
  58  * algorithm, where * indicates a constant is packed for free:
  59  *
  60  *   X | Y
  61  *  ---|---
  62  *   1 | 1
  63  *   2 | 2
  64  *   3 | 3*
  65  *   4 | 3
  66  *   5 | 4*
  67  *   6 | 5*
  68  *   7 | 5
  69  *   8 | 6*
  70  *
  71  * Y = { X      if X <= 3
  72  *     { X - 1  if 4 <= X <= 6
  73  *     { X - 2  if 7 <= X <= 8
  74  *
  75  * and there is a constant for free if X is in {3, 5, 6, 8}. The remaining
  76  * constants are packed two-by-two as constant quadwords.
  77  */
  78
  79 unsigned
  80 bi_clause_quadwords(bi_clause *clause)
  81 {
  82         unsigned X = clause->bundle_count;
  83         unsigned Y = X - ((X >= 7) ? 2 : (X >= 4) ? 1 : 0);
  84
  85         unsigned constants = clause->constant_count;
  86
  87         if ((X != 4) && (X != 7) && (X >= 3) && constants)
  88                 constants--;
  89
  90         return Y + DIV_ROUND_UP(constants, 2);
  91 }
  92
  93 /* Measures the number of quadwords a branch jumps. Bifrost relative offsets
  94  * are from the beginning of a clause so to jump forward we count the current
  95  * clause length, but to jump backwards we do not. */
  96
  97 signed
  98 bi_block_offset(bi_context *ctx, bi_clause *start, bi_block *target)
  99 {
 100         /* Signed since we might jump backwards */
 101         signed ret = 0;
 102
 103         /* Determine if the block we're branching to is strictly greater in
 104          * source order */
 105         bool forwards = target->base.name > start->block->base.name;
 106
 107         if (forwards) {
 108                 /* We have to jump through this block from the start of this
 109                  * clause to the end */
 110                 bi_foreach_clause_in_block_from(start->block, clause, start) {
 111                         ret += bi_clause_quadwords(clause);
 112                 }
 113
 114                 /* We then need to jump through every clause of every following
 115                  * block until the target */
 116                 bi_foreach_block_from(ctx, start->block, _blk) {
 117                         bi_block *blk = (bi_block *) _blk;
 118
 119                         /* Don't double-count the first block */
 120                         if (blk == start->block)
 121                                 continue;
 122
 123                         /* End just before the target */
 124                         if (blk == target)
 125                                 break;
 126
 127                         /* Count every clause in the block */
 128                         bi_foreach_clause_in_block(blk, clause) {
 129                                 ret += bi_clause_quadwords(clause);
 130                         }
 131                 }
 132         } else {
 133                 /* We start at the beginning of the clause but have to jump
 134                  * through the clauses before us in the block */
 135                 bi_foreach_clause_in_block_from_rev(start->block, clause, start) {
 136                         if (clause == start)
 137                                 continue;
 138
 139                         ret -= bi_clause_quadwords(clause);
 140                 }
 141
 142                 /* And jump back every clause of preceding blocks up through
 143                  * and including the target to get to the beginning of the
 144                  * target */
 145                 bi_foreach_block_from_rev(ctx, start->block, _blk) {
 146                         bi_block *blk = (bi_block *) _blk;
 147
 148                         if (blk == start->block)
 149                                 continue;
 150
 151                         bi_foreach_clause_in_block(blk, clause) {
 152                                 ret -= bi_clause_quadwords(clause);
 153                         }
 154
 155                         /* End just after the target */
 156                         if (blk == target)
 157                                 break;
 158                 }
 159         }
 160
 161         return ret;
 162 }