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