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
ppir_schedule_calc_sched_info(ppir_instr * instr)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
ppir_insert_ready_list(struct list_head * ready_list,ppir_instr * insert_instr)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
ppir_schedule_ready_list(ppir_block * block,struct list_head * ready_list)118 static 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 */
ppir_schedule_block(ppir_block * block)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
ppir_schedule_prog(ppir_compiler * comp)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 }
198