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 } 308