1 /***************************************************************************
2 * Copyright (C) 2006 by Matteo Franchin *
3 * fnch@libero.it *
4 * *
5 * This program is free software; you can redistribute it and/or modify *
6 * it under the terms of the GNU General Public License as published by *
7 * the Free Software Foundation; either version 2 of the License, or *
8 * (at your option) any later version. *
9 * *
10 * This program is distributed in the hope that it will be useful, *
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of *
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the *
13 * GNU General Public License for more details. *
14 * *
15 * You should have received a copy of the GNU General Public License *
16 * along with this program; if not, write to the *
17 * Free Software Foundation, Inc., *
18 * 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. *
19 ***************************************************************************/
20
21 /* registers.c, agosto 2004
22 *
23 * Questo file contiene le funzioni necessarie per tener conto dei registri
24 * temporanei occupati dal parser nella fase di compilazione.
25 */
26
27 /*#define DEBUG*/
28
29 #include <stdlib.h>
30 #include <stdio.h>
31 #include <assert.h>
32
33 #include "types.h"
34 #include "defaults.h"
35 #include "messages.h"
36 #include "array.h"
37 #include "registers.h"
38 #include "vm_priv.h"
39
40 #define END_OF_CHAIN -1
41 #define OCCUPIED 0
42
43 /****************************************************************************
44 * Here we implement the logic to associate registers to variables. *
45 ****************************************************************************/
46
47 /*
48 This is what we want to do:
49
50 a = 1 --> a:vr1
51 [b = 2] --> b:vr2
52 c = 3 --> c:vr3
53 [[d = 4], [e = 5]] --> d:vr4, e:vr4
54
55 */
56 typedef struct {
57 BoxInt level, /**< scope level of the variable */
58 chain; /**< 0 means occupied, otherwise contain a link to the next
59 register in the chain of non occupied registers. */
60 } VarItem;
61
Reg_Type(BoxTypeId type)62 static BoxTypeId Reg_Type(BoxTypeId type) {
63 assert(type >= 0);
64 return (type >= NUM_TYPES) ? BOXTYPEID_PTR : type;
65 }
66
VarFrame_Init(VarFrame * vf)67 static void VarFrame_Init(VarFrame *vf) {
68 BoxArr_Init(& vf->regs, sizeof(VarItem), 32);
69 vf->chain = END_OF_CHAIN;
70 vf->max = 0;
71 }
72
VarFrame_Finish(VarFrame * vf)73 static void VarFrame_Finish(VarFrame *vf) {
74 BoxArr_Finish(& vf->regs);
75 }
76
77 /* See Var_Occupy */
VarFrame_Occupy(VarFrame * vf,BoxUInt level)78 static BoxInt VarFrame_Occupy(VarFrame *vf, BoxUInt level) {
79 BoxArr *regs = & vf->regs;
80 VarItem *vi, *last_vi;
81 BoxInt idx;
82
83 /* Scorro la catena delle variabili libere finche'
84 * non ne trovo una di livello non inferiore a level
85 */
86 last_vi = NULL;
87 for (idx = vf->chain; idx != END_OF_CHAIN;) {
88 vi = (VarItem *) BoxArr_Item_Ptr(regs, idx);
89 if (vi->level <= level) {
90 /* Ho trovato quel che cercavo! */
91 /* La variabile non e' piu' libera: la tolgo dalla catena! */
92 if (last_vi == NULL) {
93 vf->chain = vi->chain;
94 vi->chain = OCCUPIED;
95 return idx;
96
97 } else {
98 last_vi->chain = vi->chain;
99 vi->chain = OCCUPIED;
100 return idx;
101 }
102 }
103 idx = vi->chain;
104 last_vi = vi;
105 }
106
107 /* Se la catena delle variabili libere non si puo' sfruttare non resta che
108 * creare una nuova variabile, contrassegnarla come occupata e restituirla.
109 */
110 vi = BoxArr_Push(regs, NULL);
111 vi->chain = OCCUPIED;
112 vi->level = level;
113
114 idx = BoxArr_Num_Items(regs);
115 if (idx > vf->max) vf->max = idx;
116 return idx;
117 }
118
119 /* See Var_Release */
VarFrame_Release(VarFrame * vf,BoxInt idx)120 static void VarFrame_Release(VarFrame *vf, BoxInt idx) {
121 BoxArr *regs = & vf->regs;
122 VarItem *vi = (VarItem *) BoxArr_Item_Ptr(regs, idx);
123 vi->chain = vf->chain;
124 vf->chain = idx;
125 }
126
127 /******************************************************************************
128 * Le procedure che seguono servono a gestire le liste di occupazione dei *
129 * registri. Tali liste servono per compilare le espressioni matematiche e *
130 * dicono quali registri sono occupati (cioe' contengono un valore che serve *
131 * al compilatore) e quali invece sono liberi. *
132 ******************************************************************************/
133
RegFrame_Init(RegFrame * rf)134 static void RegFrame_Init(RegFrame *rf) {
135 int i;
136 for(i = 0; i < NUM_TYPES; i++) {
137 BoxOcc_Init(& rf->reg_occ[i], 0, REG_OCC_TYP_SIZE);
138 VarFrame_Init(& rf->lvar[i]);
139 }
140 }
141
RegFrame_Finish(void * rf_ptr)142 static void RegFrame_Finish(void *rf_ptr) {
143 RegFrame *rf = (RegFrame *) rf_ptr;
144 int i;
145 for(i = 0; i < NUM_TYPES; i++) {
146 BoxOcc_Finish(& rf->reg_occ[i]);
147 VarFrame_Finish(& rf->lvar[i]);
148 }
149 }
150
151 /* Inizializza gli array che tengono nota dei registri occupati
152 * e setta la loro "dimensione a riposo". Questa quantita'(per ciascun
153 * tipo di registro) deve essere piu' grande del numero di registri che
154 * ci si aspetta saranno occupati contemporanemente, in questo modo saranno
155 * eseguite poche realloc.
156 */
Reg_Init(RegAlloc * ra)157 void Reg_Init(RegAlloc *ra) {
158 int i;
159 BoxArr_Init(& ra->reg_frame, sizeof(RegFrame), 2);
160 BoxArr_Set_Finalizer(& ra->reg_frame, RegFrame_Finish);
161 Reg_Frame_Push(ra);
162 for(i = 0; i < NUM_TYPES; i++)
163 VarFrame_Init(& ra->gvar[i]);
164 }
165
Reg_Finish(RegAlloc * ra)166 void Reg_Finish(RegAlloc *ra) {
167 int i;
168 BoxArr_Finish(& ra->reg_frame);
169 for(i = 0; i < NUM_TYPES; i++)
170 VarFrame_Finish(& ra->gvar[i]);
171 }
172
Reg_Frame_Push(RegAlloc * ra)173 void Reg_Frame_Push(RegAlloc *ra) {
174 RegFrame *new_frame = BoxArr_Push(& ra->reg_frame, NULL);
175 RegFrame_Init(new_frame);
176 }
177
Reg_Frame_Pop(RegAlloc * ra)178 void Reg_Frame_Pop(RegAlloc *ra) {
179 BoxArr_Pop(& ra->reg_frame, NULL);
180 }
181
Reg_Frame_Get(RegAlloc * ra)182 BoxInt Reg_Frame_Get(RegAlloc *ra) {
183 return BoxArr_Num_Items(& ra->reg_frame);
184 }
185
186 /* Restituisce un numero di registro libero e lo occupa,
187 * in modo tale che questo numero di registro non venga piu' restituito
188 * nelle prossime chiamate a Reg_Occupy, a meno che il registro
189 * non venga liberato con Reg_Release.
190 * t e' il tipo di registro, per ciascuno dei tipi di registro
191 * Reg_Occupy funziona in maniera indipendente.
192 * NOTA: Il numero di registro restituito e' sempre maggiore di 1,
193 * viene restituito 0 solo in caso di errori.
194 */
Reg_Occupy(RegAlloc * ra,BoxTypeId t)195 BoxInt Reg_Occupy(RegAlloc *ra, BoxTypeId t) {
196 RegFrame *rf = (RegFrame *) BoxArr_Last_Item_Ptr(& ra->reg_frame);
197 if (t == BOXTYPEID_VOID)
198 return 0;
199 else
200 return (BoxInt) BoxOcc_Occupy(& rf->reg_occ[Reg_Type(t)], NULL);
201 }
202
203 /* Vedi Reg_Occupy.
204 */
Reg_Release(RegAlloc * ra,BoxInt t,BoxUInt reg_num)205 void Reg_Release(RegAlloc *ra, BoxInt t, BoxUInt reg_num) {
206 RegFrame *rf = (RegFrame *) BoxArr_Last_Item_Ptr(& ra->reg_frame);
207 BoxOcc_Release(& rf->reg_occ[Reg_Type(t)], reg_num);
208 }
209
210 /* Restituisce il numero di registro massimo fin'ora utilizzato. */
Reg_Num(RegAlloc * ra,BoxInt t)211 BoxInt Reg_Num(RegAlloc *ra, BoxInt t) {
212 RegFrame *rf = (RegFrame *) BoxArr_Last_Item_Ptr(& ra->reg_frame);
213 return BoxOcc_Max_Index(& rf->reg_occ[Reg_Type(t)]);
214 }
215
Cur_RegFrame(RegAlloc * ra)216 static RegFrame *Cur_RegFrame(RegAlloc *ra) {
217 return (RegFrame *) BoxArr_Last_Item_Ptr(& ra->reg_frame);
218 }
219
220 /* Restituisce un numero di variabile libera e lo occupa.
221 * Questo numero non verra' piu' restituito fino a quando la variabile verra'
222 * liberata con una chiamata a Var_Release.
223 * Se la variabile e' libera Var_Occupy puo' restituirla a patto che
224 * il suo precedente livello (il livello che essa possedeva al momento
225 * dell'ultima liberazione con Var_Release) sia superiore a level.
226 * t e' il tipo di registro, per ciascuno dei tipi di registro
227 * Var_Occupy funziona in maniera indipendente.
228 * NOTA: Il numero di registro restituito e' sempre maggiore di 1,
229 * viene restituito 0 solo in caso di errori.
230 */
Var_Occupy(RegAlloc * ra,BoxTypeId type,BoxInt level)231 BoxInt Var_Occupy(RegAlloc *ra, BoxTypeId type, BoxInt level) {
232 if (type == BOXTYPEID_VOID)
233 return 0;
234
235 else {
236 BoxTypeId t = Reg_Type(type);
237 return VarFrame_Occupy(& Cur_RegFrame(ra)->lvar[t], level);
238 }
239 }
240
241 /* Vedi Var_Occupy. */
Var_Release(RegAlloc * ra,BoxInt type,BoxUInt varnum)242 void Var_Release(RegAlloc *ra, BoxInt type, BoxUInt varnum) {
243 BoxInt t = Reg_Type(type);
244 VarFrame_Release(& Cur_RegFrame(ra)->lvar[t], varnum);
245 }
246
247 /* Restituisce il numero di variabile massimo fin'ora utilizzato.
248 */
Var_Num(RegAlloc * ra,BoxInt type)249 BoxInt Var_Num(RegAlloc *ra, BoxInt type) {
250 return Cur_RegFrame(ra)->lvar[Reg_Type(type)].max;
251 }
252
GVar_Occupy(RegAlloc * ra,BoxTypeId type)253 BoxInt GVar_Occupy(RegAlloc *ra, BoxTypeId type) {
254 if (type == BOXTYPEID_VOID)
255 return 0;
256 else
257 return VarFrame_Occupy(& ra->gvar[Reg_Type(type)], 0);
258 }
259
260 /* Vedi Var_Occupy. */
GVar_Release(RegAlloc * ra,BoxInt type,BoxUInt varnum)261 void GVar_Release(RegAlloc *ra, BoxInt type, BoxUInt varnum) {
262 VarFrame_Release(& ra->gvar[Reg_Type(type)], varnum);
263 }
264
GReg_Num(RegAlloc * ra,BoxInt type)265 BoxInt GReg_Num(RegAlloc *ra, BoxInt type) {
266 switch(type) {
267 case BOXTYPEID_PTR:
268 return 2;
269 default:
270 return 0;
271 }
272 }
273
274
275 /* Restituisce il numero di variabile massimo fin'ora utilizzato.
276 */
GVar_Num(RegAlloc * ra,BoxInt type)277 BoxInt GVar_Num(RegAlloc *ra, BoxInt type) {
278 return ra->gvar[Reg_Type(type)].max;
279 }
280
281 /* This function writes (starting at the address num_var)
282 * an array of BoxInt with the number of used variables, and (address num_reg)
283 * an array of BoxInt with the number of used registers.
284 */
Reg_Get_Local_Nums(RegAlloc * ra,BoxInt * num_regs,BoxInt * num_vars)285 void Reg_Get_Local_Nums(RegAlloc *ra, BoxInt *num_regs, BoxInt *num_vars) {
286 int i;
287 if (num_regs != NULL)
288 for (i = 0; i < NUM_TYPES; i++)
289 *(num_regs++) = Reg_Num(ra, i);
290
291 if (num_vars != NULL)
292 for (i = 0; i < NUM_TYPES; i++)
293 *(num_vars++) = Var_Num(ra, i);
294 }
295
Reg_Get_Global_Nums(RegAlloc * ra,BoxInt * num_regs,BoxInt * num_vars)296 void Reg_Get_Global_Nums(RegAlloc *ra, BoxInt *num_regs, BoxInt *num_vars) {
297 int i;
298 if (num_regs != NULL)
299 for (i = 0; i < NUM_TYPES; i++)
300 *(num_regs++) = GReg_Num(ra, i);
301
302 if (num_vars != NULL)
303 for (i = 0; i < NUM_TYPES; i++)
304 *(num_vars++) = GVar_Num(ra, i);
305 }
306