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