1 /*
2 * Storage - associate pseudos with "storage" that keeps them alive
3 * between basic blocks. The aim is to be able to turn as much of
4 * the global storage allocation problem as possible into a local
5 * per-basic-block one.
6 *
7 * Copyright (C) 2004 Linus Torvalds
8 */
9 #include <stdio.h>
10 #include <stdlib.h>
11 #include <assert.h>
12
13 #include "symbol.h"
14 #include "expression.h"
15 #include "linearize.h"
16 #include "storage.h"
17
18 ALLOCATOR(storage, "storages");
19 ALLOCATOR(storage_hash, "storage hash");
20
21 #define MAX_STORAGE_HASH 64
22 static struct storage_hash_list *storage_hash_table[MAX_STORAGE_HASH];
23
24 static inline unsigned int storage_hash(struct basic_block *bb, pseudo_t pseudo, enum inout_enum inout)
25 {
26 unsigned hash = hashval(bb) + hashval(pseudo) + hashval(inout);
27 hash += hash / MAX_STORAGE_HASH;
28 return hash & (MAX_STORAGE_HASH-1);
29 }
30
31 static int hash_list_cmp(const void *_a, const void *_b)
32 {
33 const struct storage_hash *a = _a;
34 const struct storage_hash *b = _b;
35 if (a->pseudo != b->pseudo)
36 return a->pseudo < b->pseudo ? -1 : 1;
37 return 0;
38 }
39
40 static void sort_hash_list(struct storage_hash_list **listp)
41 {
42 sort_list((struct ptr_list **)listp, hash_list_cmp);
43 }
44
45 struct storage_hash_list *gather_storage(struct basic_block *bb, enum inout_enum inout)
46 {
47 int i;
48 struct storage_hash *entry, *prev;
49 struct storage_hash_list *list = NULL;
50
51 for (i = 0; i < MAX_STORAGE_HASH; i++) {
52 struct storage_hash *hash;
53 FOR_EACH_PTR(storage_hash_table[i], hash) {
54 if (hash->bb == bb && hash->inout == inout)
55 add_ptr_list(&list, hash);
56 } END_FOR_EACH_PTR(hash);
57 }
58 sort_hash_list(&list);
59
60 prev = NULL;
61 FOR_EACH_PTR(list, entry) {
62 if (prev && entry->pseudo == prev->pseudo) {
63 assert(entry == prev);
64 DELETE_CURRENT_PTR(entry);
65 }
66 prev = entry;
67 } END_FOR_EACH_PTR(entry);
68 PACK_PTR_LIST(&list);
69 return list;
70 }
71
72 static void name_storage(void)
73 {
74 int i;
75 int name = 0;
76
77 for (i = 0; i < MAX_STORAGE_HASH; i++) {
78 struct storage_hash *hash;
79 FOR_EACH_PTR(storage_hash_table[i], hash) {
80 struct storage *storage = hash->storage;
81 if (storage->name)
82 continue;
83 storage->name = ++name;
84 } END_FOR_EACH_PTR(hash);
85 }
86 }
87
88 struct storage *lookup_storage(struct basic_block *bb, pseudo_t pseudo, enum inout_enum inout)
89 {
90 struct storage_hash_list *list = storage_hash_table[storage_hash(bb,pseudo,inout)];
91 struct storage_hash *hash;
92
93 FOR_EACH_PTR(list, hash) {
94 if (hash->bb == bb && hash->pseudo == pseudo && hash->inout == inout)
95 return hash->storage;
96 } END_FOR_EACH_PTR(hash);
97 return NULL;
98 }
99
100 void add_storage(struct storage *storage, struct basic_block *bb, pseudo_t pseudo, enum inout_enum inout)
101 {
102 struct storage_hash_list **listp = storage_hash_table + storage_hash(bb,pseudo,inout);
103 struct storage_hash *hash = alloc_storage_hash(storage);
104
105 hash->bb = bb;
106 hash->pseudo = pseudo;
107 hash->inout = inout;
108
109 add_ptr_list(listp, hash);
110 }
111
112
113 static int storage_hash_cmp(const void *_a, const void *_b)
114 {
115 const struct storage_hash *a = _a;
116 const struct storage_hash *b = _b;
117 struct storage *aa = a->storage;
118 struct storage *bb = b->storage;
119
120 if (a->bb != b->bb)
121 return a->bb < b->bb ? -1 : 1;
122 if (a->inout != b->inout)
123 return a->inout < b->inout ? -1 : 1;
124 if (aa->type != bb->type)
125 return aa->type < bb->type ? -1 : 1;
126 if (aa->regno != bb->regno)
127 return aa->regno < bb->regno ? -1 : 1;
128 return 0;
129 }
130
131 static void vrfy_storage(struct storage_hash_list **listp)
132 {
133 struct storage_hash *entry, *last;
134
135 sort_list((struct ptr_list **)listp, storage_hash_cmp);
136 last = NULL;
137 FOR_EACH_PTR(*listp, entry) {
138 if (last) {
139 struct storage *a = last->storage;
140 struct storage *b = entry->storage;
141 if (a == b)
142 continue;
143 if (last->bb == entry->bb
144 && last->inout == entry->inout
145 && a->type != REG_UDEF
146 && a->type == b->type
147 && a->regno == b->regno) {
148 printf("\t BAD: same storage as %s in %p: %s (%s and %s)\n",
149 last->inout == STOR_IN ? "input" : "output",
150 last->bb,
151 show_storage(a),
152 show_pseudo(last->pseudo),
153 show_pseudo(entry->pseudo));
154 }
155 }
156 last = entry;
157 } END_FOR_EACH_PTR(entry);
158 }
159
160 void free_storage(void)
161 {
162 int i;
163
164 for (i = 0; i < MAX_STORAGE_HASH; i++) {
165 vrfy_storage(storage_hash_table + i);
166 free_ptr_list(storage_hash_table + i);
167 }
168 }
169
170 const char *show_storage(struct storage *s)
171 {
172 static char buffer[1024];
173 if (!s)
174 return "none";
175 switch (s->type) {
176 case REG_REG:
177 sprintf(buffer, "reg%d (%d)", s->regno, s->name);
178 break;
179 case REG_STACK:
180 sprintf(buffer, "%d(SP) (%d)", s->offset, s->name);
181 break;
182 case REG_ARG:
183 sprintf(buffer, "ARG%d (%d)", s->regno, s->name);
184 break;
185 default:
186 sprintf(buffer, "%d:%d (%d)", s->type, s->regno, s->name);
187 break;
188 }
189 return buffer;
190 }
191
192 /*
193 * Combine two storage allocations into one.
194 *
195 * We just randomly pick one over the other, and replace
196 * the other uses.
197 */
198 static struct storage * combine_storage(struct storage *src, struct storage *dst)
199 {
200 struct storage **usep;
201
202 /* Remove uses of "src_storage", replace with "dst" */
203 FOR_EACH_PTR(src->users, usep) {
204 assert(*usep == src);
205 *usep = dst;
206 add_ptr_list(&dst->users, usep);
207 } END_FOR_EACH_PTR(usep);
208
209 /* Mark it unused */
210 src->type = REG_BAD;
211 src->users = NULL;
212 return dst;
213 }
214
215 static void set_up_bb_storage(struct basic_block *bb)
216 {
217 struct basic_block *child;
218
219 FOR_EACH_PTR(bb->children, child) {
220 pseudo_t pseudo;
221 FOR_EACH_PTR(child->needs, pseudo) {
222 struct storage *child_in, *parent_out;
223
224 parent_out = lookup_storage(bb, pseudo, STOR_OUT);
225 child_in = lookup_storage(child, pseudo, STOR_IN);
226
227 if (parent_out) {
228 if (!child_in) {
229 add_storage(parent_out, child, pseudo, STOR_IN);
230 continue;
231 }
232 if (parent_out == child_in)
233 continue;
234 combine_storage(parent_out, child_in);
235 continue;
236 }
237 if (child_in) {
238 add_storage(child_in, bb, pseudo, STOR_OUT);
239 continue;
240 }
241 parent_out = alloc_storage();
242 add_storage(parent_out, bb, pseudo, STOR_OUT);
243 add_storage(parent_out, child, pseudo, STOR_IN);
244 } END_FOR_EACH_PTR(pseudo);
245 } END_FOR_EACH_PTR(child);
246 }
247
248 static void set_up_argument_storage(struct entrypoint *ep, struct basic_block *bb)
249 {
250 pseudo_t arg;
251
252 FOR_EACH_PTR(bb->needs, arg) {
253 struct storage *storage = alloc_storage();
254
255 /* FIXME! Totally made-up argument passing conventions */
256 if (arg->type == PSEUDO_ARG) {
257 storage->type = REG_ARG;
258 storage->regno = arg->nr;
259 }
260 add_storage(storage, bb, arg, STOR_IN);
261 } END_FOR_EACH_PTR(arg);
262 }
263
264 /*
265 * One phi-source may feed multiple phi nodes. If so, combine
266 * the storage output for this bb into one entry to reduce
267 * storage pressure.
268 */
269 static void combine_phi_storage(struct basic_block *bb)
270 {
271 struct instruction *insn;
272 FOR_EACH_PTR(bb->insns, insn) {
273 struct instruction *phi;
274 struct storage *last;
275
276 if (!insn->bb || insn->opcode != OP_PHISOURCE)
277 continue;
278 last = NULL;
279 FOR_EACH_PTR(insn->phi_users, phi) {
280 struct storage *storage = lookup_storage(bb, phi->target, STOR_OUT);
281 if (!storage) {
282 DELETE_CURRENT_PTR(phi);
283 continue;
284 }
285 if (last && storage != last)
286 storage = combine_storage(storage, last);
287 last = storage;
288 } END_FOR_EACH_PTR(phi);
289 PACK_PTR_LIST(&insn->phi_users);
290 } END_FOR_EACH_PTR(insn);
291 }
292
293 void set_up_storage(struct entrypoint *ep)
294 {
295 struct basic_block *bb;
296
297 /* First set up storage for the incoming arguments */
298 set_up_argument_storage(ep, ep->entry->bb);
299
300 /* Then do a list of all the inter-bb storage */
301 FOR_EACH_PTR(ep->bbs, bb) {
302 set_up_bb_storage(bb);
303 combine_phi_storage(bb);
304 } END_FOR_EACH_PTR(bb);
305
306 name_storage();
307 }