src/gallium/drivers/lima/ir/pp/scheduler.c

   1 /*
   2  * Copyright (c) 2017 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 <limits.h>
  26
  27 #include "ppir.h"
  28
  29
  30 static void ppir_schedule_calc_sched_info(ppir_instr *instr)
  31 {
  32    int n = 0;
  33    float extra_reg = 1.0;
  34
  35    /* update all children's sched info */
  36    ppir_instr_foreach_pred(instr, dep) {
  37       ppir_instr *pred = dep->pred;
  38
  39       if (pred->reg_pressure < 0)
  40          ppir_schedule_calc_sched_info(pred);
  41
  42       if (instr->est < pred->est + 1)
  43          instr->est = pred->est + 1;
  44
  45       float reg_weight = 1.0 - 1.0 / list_length(&pred->succ_list);
  46       if (extra_reg > reg_weight)
  47          extra_reg = reg_weight;
  48
  49       n++;
  50    }
  51
  52    /* leaf instr */
  53    if (!n) {
  54       instr->reg_pressure = 0;
  55       return;
  56    }
  57
  58    int i = 0, reg[n];
  59    ppir_instr_foreach_pred(instr, dep) {
  60       ppir_instr *pred = dep->pred;
  61       reg[i++] = pred->reg_pressure;
  62    }
  63
  64    /* sort */
  65    for (i = 0; i < n - 1; i++) {
  66       for (int j = 0; j < n - i - 1; j++) {
  67          if (reg[j] > reg[j + 1]) {
  68             int tmp = reg[j + 1];
  69             reg[j + 1] = reg[j];
  70             reg[j] = tmp;
  71          }
  72       }
  73    }
  74
  75    for (i = 0; i < n; i++) {
  76       int pressure = reg[i] + n - (i + 1);
  77       if (pressure > instr->reg_pressure)
  78          instr->reg_pressure = pressure;
  79    }
  80
  81    /* If all children of this instr have multi parents, then this
  82     * instr need an extra reg to store its result. For example,
  83     * it's not fair for parent has the same reg pressure as child
  84     * if n==1 and child's successor>1, because we need 2 reg for
  85     * this.
  86     *
  87     * But we can't add a full reg to the reg_pressure, because the
  88     * last parent of a multi-successor child doesn't need an extra
  89     * reg. For example, a single child (with multi successor) instr
  90     * should has less reg pressure than a two children (with single
  91     * successor) instr.
  92     *
  93     * extra reg = min(all child)(1.0 - 1.0 / num successor)
  94     */
  95    instr->reg_pressure += extra_reg;
  96 }
  97
  98 static void ppir_insert_ready_list(struct list_head *ready_list,
  99                                    ppir_instr *insert_instr)
 100 {
 101    struct list_head *insert_pos = ready_list;
 102
 103    list_for_each_entry(ppir_instr, instr, ready_list, list) {
 104       if (insert_instr->parent_index < instr->parent_index ||
 105           (insert_instr->parent_index == instr->parent_index &&
 106            (insert_instr->reg_pressure < instr->reg_pressure ||
 107             (insert_instr->reg_pressure == instr->reg_pressure &&
 108              (insert_instr->est >= instr->est))))) {
 109          insert_pos = &instr->list;
 110          break;
 111       }
 112    }
 113
 114    list_del(&insert_instr->list);
 115    list_addtail(&insert_instr->list, insert_pos);
 116 }
 117
 118 static void ppir_schedule_ready_list(ppir_block *block,
 119                                      struct list_head *ready_list)
 120 {
 121    if (list_empty(ready_list))
 122       return;
 123
 124    ppir_instr *instr = list_first_entry(ready_list, ppir_instr, list);
 125    list_del(&instr->list);
 126
 127    /* schedule the instr to the block instr list */
 128    list_add(&instr->list, &block->instr_list);
 129    instr->scheduled = true;
 130    block->sched_instr_index--;
 131    instr->seq = block->sched_instr_base + block->sched_instr_index;
 132
 133    ppir_instr_foreach_pred(instr, dep) {
 134       ppir_instr *pred = dep->pred;
 135       pred->parent_index = block->sched_instr_index;
 136
 137       bool ready = true;
 138       ppir_instr_foreach_succ(pred, dep) {
 139          ppir_instr *succ = dep->succ;
 140          if (!succ->scheduled) {
 141             ready = false;
 142             break;
 143          }
 144       }
 145       /* all successor have been scheduled */
 146       if (ready)
 147          ppir_insert_ready_list(ready_list, pred);
 148    }
 149
 150    ppir_schedule_ready_list(block, ready_list);
 151 }
 152
 153 /* Register sensitive schedule algorithm from paper:
 154  * "Register-Sensitive Selection, Duplication, and Sequencing of Instructions"
 155  * Author: Vivek Sarkar,  Mauricio J. Serrano,  Barbara B. Simons
 156  */
 157 static void ppir_schedule_block(ppir_block *block)
 158 {
 159    /* move all instr to instr_list, block->instr_list will
 160     * contain schedule result */
 161    struct list_head instr_list;
 162    list_replace(&block->instr_list, &instr_list);
 163    list_inithead(&block->instr_list);
 164
 165    /* step 2 & 3 */
 166    list_for_each_entry(ppir_instr, instr, &instr_list, list) {
 167       if (ppir_instr_is_root(instr))
 168          ppir_schedule_calc_sched_info(instr);
 169       block->sched_instr_index++;
 170    }
 171    block->sched_instr_base = block->comp->sched_instr_base;
 172    block->comp->sched_instr_base += block->sched_instr_index;
 173
 174    /* step 4 */
 175    struct list_head ready_list;
 176    list_inithead(&ready_list);
 177
 178    /* step 5 */
 179    list_for_each_entry_safe(ppir_instr, instr, &instr_list, list) {
 180       if (ppir_instr_is_root(instr)) {
 181          instr->parent_index = INT_MAX;
 182          ppir_insert_ready_list(&ready_list, instr);
 183       }
 184    }
 185
 186    /* step 6 */
 187    ppir_schedule_ready_list(block, &ready_list);
 188 }
 189
 190 bool ppir_schedule_prog(ppir_compiler *comp)
 191 {
 192    list_for_each_entry(ppir_block, block, &comp->block_list, list) {
 193       ppir_schedule_block(block);
 194    }
 195
 196    return true;
 197 }