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
30static 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
98static 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
118static void ppir_schedule_ready_list(ppir_block *block,
119                                     struct list_head *ready_list)
120{
121   if (list_is_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 */
157static 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
190bool 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}
198