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 static 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 static 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 void free_storage(void)
 113  {
 114         int i;
 115
 116         for (i = 0; i < MAX_STORAGE_HASH; i++)
 117                 free_ptr_list(storage_hash_table + i);
 118 }
 119
 120 const char *show_storage(struct storage *s)
 121 {
 122         static char buffer[1024];
 123         if (!s)
 124                 return "none";
 125         switch (s->type) {
 126         case REG_REG:
 127                 sprintf(buffer, "reg%d (%d)", s->regno, s->name);
 128                 break;
 129         case REG_STACK:
 130                 sprintf(buffer, "%d(SP) (%d)", s->offset, s->name);
 131                 break;
 132         case REG_ARG:
 133                 sprintf(buffer, "ARG%d (%d)", s->regno, s->name);
 134                 break;
 135         default:
 136                 sprintf(buffer, "%d:%d (%d)", s->type, s->regno, s->name);
 137                 break;
 138         }
 139         return buffer;
 140 }
 141
 142 /*
 143  * Combine two storage allocations into one.
 144  *
 145  * We just randomly pick one over the other, and replace
 146  * the other uses.
 147  */
 148 static struct storage * combine_storage(struct storage *src, struct storage *dst)
 149 {
 150         struct storage **usep;
 151
 152         /* Remove uses of "src_storage", replace with "dst" */
 153         FOR_EACH_PTR(src->users, usep) {
 154                 assert(*usep == src);
 155                 *usep = dst;
 156                 add_ptr_list(&dst->users, usep);
 157         } END_FOR_EACH_PTR(usep);
 158
 159         /* Mark it unused */
 160         src->type = REG_BAD;
 161         src->users = NULL;
 162         return dst;
 163 }
 164
 165 static void set_up_bb_storage(struct basic_block *bb)
 166 {
 167         struct basic_block *child;
 168
 169         FOR_EACH_PTR(bb->children, child) {
 170                 pseudo_t pseudo;
 171                 FOR_EACH_PTR(child->needs, pseudo) {
 172                         struct storage *child_in, *parent_out;
 173
 174                         parent_out = lookup_storage(bb, pseudo, STOR_OUT);
 175                         child_in = lookup_storage(child, pseudo, STOR_IN);
 176
 177                         if (parent_out) {
 178                                 if (!child_in) {
 179                                         add_storage(parent_out, child, pseudo, STOR_IN);
 180                                         continue;
 181                                 }
 182                                 if (parent_out == child_in)
 183                                         continue;
 184                                 combine_storage(parent_out, child_in);
 185                                 continue;
 186                         }
 187                         if (child_in) {
 188                                 add_storage(child_in, bb, pseudo, STOR_OUT);
 189                                 continue;
 190                         }
 191                         parent_out = alloc_storage();
 192                         add_storage(parent_out, bb, pseudo, STOR_OUT);
 193                         add_storage(parent_out, child, pseudo, STOR_IN);
 194                 } END_FOR_EACH_PTR(pseudo);
 195         } END_FOR_EACH_PTR(child);
 196 }
 197
 198 static void set_up_argument_storage(struct entrypoint *ep, struct basic_block *bb)
 199 {
 200         pseudo_t arg;
 201
 202         FOR_EACH_PTR(bb->needs, arg) {
 203                 struct storage *storage = alloc_storage();
 204
 205                 /* FIXME! Totally made-up argument passing conventions */
 206                 if (arg->type == PSEUDO_ARG) {
 207                         storage->type = REG_ARG;
 208                         storage->regno = arg->nr;
 209                 }
 210                 add_storage(storage, bb, arg, STOR_IN);
 211         } END_FOR_EACH_PTR(arg);
 212 }
 213
 214 /*
 215  * One phi-source may feed multiple phi nodes. If so, combine
 216  * the storage output for this bb into one entry to reduce
 217  * storage pressure.
 218  */
 219 static void combine_phi_storage(struct basic_block *bb)
 220 {
 221         struct instruction *insn;
 222         FOR_EACH_PTR(bb->insns, insn) {
 223                 struct instruction *phi;
 224                 struct storage *last;
 225
 226                 if (!insn->bb || insn->opcode != OP_PHISOURCE)
 227                         continue;
 228                 last = NULL;
 229                 FOR_EACH_PTR(insn->phi_users, phi) {
 230                         struct storage *storage = lookup_storage(bb, phi->target, STOR_OUT);
 231                         if (!storage) {
 232                                 DELETE_CURRENT_PTR(phi);
 233                                 continue;
 234                         }
 235                         if (last && storage != last)
 236                                 storage = combine_storage(storage, last);
 237                         last = storage;
 238                 } END_FOR_EACH_PTR(phi);
 239                 PACK_PTR_LIST(&insn->phi_users);
 240         } END_FOR_EACH_PTR(insn);
 241 }
 242
 243 void set_up_storage(struct entrypoint *ep)
 244 {
 245         struct basic_block *bb;
 246
 247         /* First set up storage for the incoming arguments */
 248         set_up_argument_storage(ep, ep->entry->bb);
 249
 250         /* Then do a list of all the inter-bb storage */
 251         FOR_EACH_PTR(ep->bbs, bb) {
 252                 set_up_bb_storage(bb);
 253                 combine_phi_storage(bb);
 254         } END_FOR_EACH_PTR(bb);
 255
 256         name_storage();
 257 }