ssa.c

   1 // SPDX-License-Identifier: MIT
   2 //
   3 // SSA conversion
   4 // Copyright (C) 2005 Luc Van Oostenryck
   5 //
   6
   7 #include <assert.h>
   8 #include "ssa.h"
   9 #include "lib.h"
  10 #include "dominate.h"
  11 #include "flowgraph.h"
  12 #include "linearize.h"
  13 #include "simplify.h"
  14 #include "flow.h"
  15
  16
  17 // Is it possible and desirable for this to be promoted to a pseudo?
  18 static inline bool is_promotable(struct symbol *type)
  19 {
  20         struct symbol *member;
  21         int bf_seen;
  22         int nbr;
  23
  24         if (type->type == SYM_NODE)
  25                 type = type->ctype.base_type;
  26         switch (type->type) {
  27         case SYM_ENUM:
  28         case SYM_BITFIELD:
  29         case SYM_PTR:
  30         case SYM_RESTRICT:      // OK, always integer types
  31                 return 1;
  32         case SYM_STRUCT:
  33                 // we allow a single scalar field
  34                 // but a run of bitfields count for 1
  35                 // (and packed bifields are excluded).
  36                 if (type->packed)
  37                         return 0;
  38                 nbr = 0;
  39                 bf_seen = 0;
  40                 FOR_EACH_PTR(type->symbol_list, member) {
  41                         if (is_bitfield_type(member)) {
  42                                 if (bf_seen)
  43                                         continue;
  44                                 bf_seen = 1;
  45                         } else {
  46                                 bf_seen = 0;
  47                         }
  48                         if (!is_scalar_type(member))
  49                                 return 0;
  50                         if (nbr++)
  51                                 return 0;
  52                 } END_FOR_EACH_PTR(member);
  53                 if (bf_seen && (type->bit_size > long_ctype.bit_size))
  54                         return 0;
  55                 return 1;
  56         case SYM_UNION:
  57                 // FIXME: should be like struct but has problem
  58                 //        when used with/for type cohercion
  59                 // -----> OK if only same sized integral types
  60                 FOR_EACH_PTR(type->symbol_list, member) {
  61                         if (member->bit_size != type->bit_size)
  62                                 return 0;
  63                         if (!is_integral_type(member))
  64                                 return 0;
  65                 } END_FOR_EACH_PTR(member);
  66                 return 1;
  67         default:
  68                 break;
  69         }
  70         if (type->ctype.base_type == &int_type)
  71                 return 1;
  72         if (type->ctype.base_type == &fp_type)
  73                 return 1;
  74         return 0;
  75 }
  76
  77 static void kill_store(struct instruction *insn)
  78 {
  79         remove_use(&insn->src);
  80         remove_use(&insn->target);
  81         insn->bb = NULL;
  82 }
  83
  84 static bool same_memop(struct instruction *a, struct instruction *b)
  85 {
  86         if (a->size != b->size || a->offset != b->offset)
  87                 return false;
  88         if (is_integral_type(a->type) && is_float_type(b->type))
  89                 return false;
  90         if (is_float_type(a->type) && is_integral_type(b->type))
  91                 return false;
  92         return true;
  93 }
  94
  95 static void rewrite_local_var(struct basic_block *bb, pseudo_t addr, int nbr_stores, int nbr_uses)
  96 {
  97         struct instruction *store = NULL;
  98         struct instruction *insn;
  99         bool remove = false;
 100
 101         if (!bb)
 102                 return;
 103
 104         FOR_EACH_PTR(bb->insns, insn) {
 105
 106                 if (!insn->bb || insn->src != addr)
 107                         continue;
 108                 switch (insn->opcode) {
 109                 case OP_LOAD:
 110                         if (!store)
 111                                 replace_with_pseudo(insn, undef_pseudo());
 112                         else if (same_memop(store, insn))
 113                                 replace_with_pseudo(insn, store->target);
 114                         else
 115                                 remove = false;
 116                         break;
 117                 case OP_STORE:
 118                         store = insn;
 119                         remove = true;
 120                         break;
 121                 }
 122         } END_FOR_EACH_PTR(insn);
 123         if (remove)
 124                 kill_store(store);
 125 }
 126
 127 // we would like to know:
 128 // is there one or more stores?
 129 // are all loads & stores local/done in a single block?
 130 static void ssa_convert_one_var(struct entrypoint *ep, struct symbol *var)
 131 {
 132         unsigned long generation = ++bb_generation;
 133         struct basic_block_list *alpha = NULL;
 134         struct basic_block_list *idf = NULL;
 135         struct basic_block *samebb = NULL;
 136         struct basic_block *bb;
 137         struct pseudo_user *pu;
 138         unsigned long mod = var->ctype.modifiers;
 139         bool local = true;
 140         int nbr_stores = 0;
 141         int nbr_uses   = 0;
 142         pseudo_t addr;
 143
 144         /* Never used as a symbol? */
 145         addr = var->pseudo;
 146         if (!addr)
 147                 return;
 148
 149         /* We don't do coverage analysis of volatiles.. */
 150         if (mod & MOD_VOLATILE)
 151                 return;
 152
 153         /* ..and symbols with external visibility need more care */
 154         mod &= (MOD_NONLOCAL | MOD_STATIC | MOD_ADDRESSABLE);
 155         if (mod)
 156                 goto external_visibility;
 157
 158         if (!is_promotable(var))
 159                 return;
 160
 161         // 1) insert in the worklist all BBs that may modify var
 162         FOR_EACH_PTR(addr->users, pu) {
 163                 struct instruction *insn = pu->insn;
 164                 struct basic_block *bb = insn->bb;
 165
 166                 switch (insn->opcode) {
 167                 case OP_STORE:
 168                         nbr_stores++;
 169                         if (bb->generation != generation) {
 170                                 bb->generation = generation;
 171                                 add_bb(&alpha, bb);
 172                         }
 173                         /* fall through */
 174                 case OP_LOAD:
 175                         if (local) {
 176                                 if (!samebb)
 177                                         samebb = bb;
 178                                 else if (samebb != bb)
 179                                         local = false;
 180                         }
 181                         nbr_uses++;
 182                         break;
 183                 case OP_SYMADDR:
 184                         mod |= MOD_ADDRESSABLE;
 185                         goto external_visibility;
 186                 default:
 187                         warning(var->pos, "symbol '%s' pseudo used in unexpected way",
 188                                 show_ident(var->ident));
 189                 }
 190         } END_FOR_EACH_PTR(pu);
 191
 192         // if all uses are local to a single block
 193         // they can easily be rewritten and doesn't need phi-nodes
 194         // FIXME: could be done for extended BB too
 195         if (local) {
 196                 rewrite_local_var(samebb, addr, nbr_stores, nbr_uses);
 197                 return;
 198         }
 199
 200         idf_compute(ep, &idf, alpha);
 201         FOR_EACH_PTR(idf, bb) {
 202                 struct instruction *node = insert_phi_node(bb, var);
 203                 node->phi_var = var->pseudo;
 204         } END_FOR_EACH_PTR(bb);
 205         var->torename = 1;
 206
 207 external_visibility:
 208         if (mod & (MOD_NONLOCAL | MOD_STATIC))
 209                 return;
 210         kill_dead_stores(ep, addr, !mod);
 211 }
 212
 213 static struct instruction *lookup_var(struct basic_block *bb, struct symbol *var)
 214 {
 215         do {
 216                 struct instruction *insn = phi_map_lookup(bb->phi_map, var);
 217                 if (insn)
 218                         return insn;
 219         } while ((bb = bb->idom));
 220         return NULL;
 221 }
 222
 223 static struct instruction_list *phis_all;
 224 static struct instruction_list *phis_used;
 225 static struct instruction_list *stores;
 226
 227 static bool matching_load(struct instruction *def, struct instruction *insn)
 228 {
 229         if (insn->size != def->size)
 230                 return false;
 231         switch (def->opcode) {
 232         case OP_STORE:
 233         case OP_LOAD:
 234                 if (insn->offset != def->offset)
 235                         return false;
 236         case OP_PHI:
 237                 break;
 238         default:
 239                 return false;
 240         }
 241         return true;
 242 }
 243
 244 static void ssa_rename_insn(struct basic_block *bb, struct instruction *insn)
 245 {
 246         struct instruction *def;
 247         struct symbol *var;
 248         pseudo_t addr;
 249         pseudo_t val;
 250
 251         switch (insn->opcode) {
 252         case OP_STORE:
 253                 addr = insn->src;
 254                 if (addr->type != PSEUDO_SYM)
 255                         break;
 256                 var = addr->sym;
 257                 if (!var || !var->torename)
 258                         break;
 259                 phi_map_update(&bb->phi_map, var, insn);
 260                 add_instruction(&stores, insn);
 261                 break;
 262         case OP_LOAD:
 263                 addr = insn->src;
 264                 if (addr->type != PSEUDO_SYM)
 265                         break;
 266                 var = addr->sym;
 267                 if (!var || !var->torename)
 268                         break;
 269                 def = lookup_var(bb, var);
 270                 if (!def) {
 271                         val = undef_pseudo();
 272                 } else if (!matching_load(def, insn)) {
 273                         var->torename = false;
 274                         break;
 275                 } else {
 276                         val = def->target;
 277                 }
 278                 replace_with_pseudo(insn, val);
 279                 break;
 280         case OP_PHI:
 281                 var = insn->type;
 282                 if (!var || !var->torename)
 283                         break;
 284                 phi_map_update(&bb->phi_map, var, insn);
 285                 add_instruction(&phis_all, insn);
 286                 break;
 287         }
 288 }
 289
 290 static void ssa_rename_insns(struct entrypoint *ep)
 291 {
 292         struct basic_block *bb;
 293
 294         FOR_EACH_PTR(ep->bbs, bb) {
 295                 struct instruction *insn;
 296                 FOR_EACH_PTR(bb->insns, insn) {
 297                         if (!insn->bb)
 298                                 continue;
 299                         ssa_rename_insn(bb, insn);
 300                 } END_FOR_EACH_PTR(insn);
 301         } END_FOR_EACH_PTR(bb);
 302 }
 303
 304 static void mark_phi_used(pseudo_t val)
 305 {
 306         struct instruction *node;
 307
 308         if (val->type != PSEUDO_REG)
 309                 return;
 310         node = val->def;
 311         if (node->opcode != OP_PHI)
 312                 return;
 313         if (node->used)
 314                 return;
 315         node->used = 1;
 316         add_instruction(&phis_used, node);
 317 }
 318
 319 static void ssa_rename_phi(struct instruction *insn)
 320 {
 321         struct basic_block *par;
 322         struct symbol *var;
 323
 324         if (!insn->phi_var)
 325                 return;
 326         var = insn->phi_var->sym;
 327         if (!var->torename)
 328                 return;
 329         FOR_EACH_PTR(insn->bb->parents, par) {
 330                 struct instruction *def = lookup_var(par, var);
 331                 pseudo_t val = def ? def->target : undef_pseudo();
 332                 struct instruction *phisrc = alloc_phisrc(val, var);
 333                 pseudo_t phi = phisrc->target;
 334                 phi->ident = var->ident;
 335                 insert_last_instruction(par, phisrc);
 336                 link_phi(insn, phi);
 337                 mark_phi_used(val);
 338         } END_FOR_EACH_PTR(par);
 339 }
 340
 341 static void ssa_rename_phis(struct entrypoint *ep)
 342 {
 343         struct instruction *phi;
 344
 345         phis_used = NULL;
 346         FOR_EACH_PTR(phis_all, phi) {
 347                 if (has_users(phi->target)) {
 348                         phi->used = 1;
 349                         add_instruction(&phis_used, phi);
 350                 }
 351         } END_FOR_EACH_PTR(phi);
 352
 353         FOR_EACH_PTR(phis_used, phi) {
 354                 if (!phi->bb)
 355                         continue;
 356                 ssa_rename_phi(phi);
 357         } END_FOR_EACH_PTR(phi);
 358 }
 359
 360 static void remove_dead_stores(struct instruction_list *stores)
 361 {
 362         struct instruction *store;
 363
 364         FOR_EACH_PTR(stores, store) {
 365                 struct symbol *var = store->addr->sym;
 366
 367                 if (var->torename)
 368                         kill_store(store);
 369         } END_FOR_EACH_PTR(store);
 370 }
 371
 372 void ssa_convert(struct entrypoint *ep)
 373 {
 374         struct basic_block *bb;
 375         pseudo_t pseudo;
 376         int first, last;
 377
 378         // calculate the number of BBs
 379         first = ep->entry->bb->nr;
 380         last = first;
 381         FOR_EACH_PTR(ep->bbs, bb) {
 382                 int nr = bb->nr;
 383                 if (nr > last)
 384                         last = nr;
 385                 bb->phi_map = NULL;
 386         } END_FOR_EACH_PTR(bb);
 387
 388         // try to promote memory accesses to pseudos
 389         stores = NULL;
 390         FOR_EACH_PTR(ep->accesses, pseudo) {
 391                 ssa_convert_one_var(ep, pseudo->sym);
 392         } END_FOR_EACH_PTR(pseudo);
 393
 394         // rename the converted accesses
 395         phis_all = phis_used = NULL;
 396         ssa_rename_insns(ep);
 397         ssa_rename_phis(ep);
 398
 399         // remove now dead stores
 400         remove_dead_stores(stores);
 401 }