storage.c

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