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