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