flow.c

   1 /*
   2  * Flow - walk the linearized flowgraph, simplifying it as we
   3  * go along.
   4  *
   5  * Copyright (C) 2004 Linus Torvalds
   6  */
   7
   8 #include <string.h>
   9 #include <stdarg.h>
  10 #include <stdlib.h>
  11 #include <stdio.h>
  12 #include <stddef.h>
  13 #include <assert.h>
  14
  15 #include "parse.h"
  16 #include "expression.h"
  17 #include "linearize.h"
  18 #include "flow.h"
  19 #include "target.h"
  20
  21 unsigned long bb_generation;
  22
  23 /*
  24  * Dammit, if we have a phi-node followed by a conditional
  25  * branch on that phi-node, we should damn well be able to
  26  * do something about the source. Maybe.
  27  */
  28 static int rewrite_branch(struct basic_block *bb,
  29         struct basic_block **ptr,
  30         struct basic_block *old,
  31         struct basic_block *new)
  32 {
  33         if (*ptr != old || new == old)
  34                 return 0;
  35
  36         /* We might find new if-conversions or non-dominating CSEs */
  37         repeat_phase |= REPEAT_CSE;
  38         *ptr = new;
  39         replace_bb_in_list(&bb->children, old, new, 1);
  40         remove_bb_from_list(&old->parents, bb, 1);
  41         add_bb(&new->parents, bb);
  42         return 1;
  43 }
  44
  45 /*
  46  * Return the known truth value of a pseudo, or -1 if
  47  * it's not known.
  48  */
  49 static int pseudo_truth_value(pseudo_t pseudo)
  50 {
  51         switch (pseudo->type) {
  52         case PSEUDO_VAL:
  53                 return !!pseudo->value;
  54
  55         case PSEUDO_REG: {
  56                 struct instruction *insn = pseudo->def;
  57
  58                 /* A symbol address is always considered true.. */
  59                 if (insn->opcode == OP_SYMADDR && insn->target == pseudo)
  60                         return 1;
  61         }
  62                 /* Fall through */
  63         default:
  64                 return -1;
  65         }
  66 }
  67
  68 /*
  69  * Does a basic block depend on the pseudos that "src" defines?
  70  */
  71 static int bb_depends_on(struct basic_block *target, struct basic_block *src)
  72 {
  73         pseudo_t pseudo;
  74
  75         FOR_EACH_PTR(src->defines, pseudo) {
  76                 if (pseudo_in_list(target->needs, pseudo))
  77                         return 1;
  78         } END_FOR_EACH_PTR(pseudo);
  79         return 0;
  80 }
  81
  82 /*
  83  * When we reach here, we have:
  84  *  - a basic block that ends in a conditional branch and
  85  *    that has no side effects apart from the pseudos it
  86  *    may change.
  87  *  - the phi-node that the conditional branch depends on
  88  *  - full pseudo liveness information
  89  *
  90  * We need to check if any of the _sources_ of the phi-node
  91  * may be constant, and not actually need this block at all.
  92  */
  93 static int try_to_simplify_bb(struct basic_block *bb, struct instruction *first, struct instruction *second)
  94 {
  95         int changed = 0;
  96         pseudo_t phi;
  97
  98         FOR_EACH_PTR(first->phi_list, phi) {
  99                 struct instruction *def = phi->def;
 100                 struct basic_block *source, *target;
 101                 pseudo_t pseudo;
 102                 struct instruction *br;
 103                 int true;
 104
 105                 if (!def)
 106                         continue;
 107                 source = def->bb;
 108                 pseudo = def->src1;
 109                 if (!pseudo || !source)
 110                         continue;
 111                 br = last_instruction(source->insns);
 112                 if (!br)
 113                         continue;
 114                 if (br->opcode != OP_BR)
 115                         continue;
 116                 true = pseudo_truth_value(pseudo);
 117                 if (true < 0)
 118                         continue;
 119                 target = true ? second->bb_true : second->bb_false;
 120                 if (bb_depends_on(target, bb))
 121                         continue;
 122                 changed |= rewrite_branch(source, &br->bb_true, bb, target);
 123                 changed |= rewrite_branch(source, &br->bb_false, bb, target);
 124                 if (changed)
 125                         kill_use(THIS_ADDRESS(phi));
 126         } END_FOR_EACH_PTR(phi);
 127         return changed;
 128 }
 129
 130 static int bb_has_side_effects(struct basic_block *bb)
 131 {
 132         struct instruction *insn;
 133         FOR_EACH_PTR(bb->insns, insn) {
 134                 switch (insn->opcode) {
 135                 case OP_CALL:
 136                         /* FIXME! This should take "const" etc into account */
 137                         return 1;
 138
 139                 case OP_STORE:
 140                 case OP_CONTEXT:
 141                         return 1;
 142
 143                 case OP_ASM:
 144                         /* FIXME! This should take "volatile" etc into account */
 145                         return 1;
 146
 147                 default:
 148                         continue;
 149                 }
 150         } END_FOR_EACH_PTR(insn);
 151         return 0;
 152 }
 153
 154 static int simplify_phi_branch(struct basic_block *bb, struct instruction *br)
 155 {
 156         pseudo_t cond = br->cond;
 157         struct instruction *def;
 158
 159         if (cond->type != PSEUDO_REG)
 160                 return 0;
 161         def = cond->def;
 162         if (def->bb != bb || def->opcode != OP_PHI)
 163                 return 0;
 164         if (bb_has_side_effects(bb))
 165                 return 0;
 166         return try_to_simplify_bb(bb, def, br);
 167 }
 168
 169 static int simplify_branch_branch(struct basic_block *bb, struct instruction *br,
 170         struct basic_block **target_p, int true)
 171 {
 172         struct basic_block *target = *target_p, *final;
 173         struct instruction *insn;
 174         int retval;
 175
 176         if (target == bb)
 177                 return 0;
 178         insn = last_instruction(target->insns);
 179         if (!insn || insn->opcode != OP_BR || insn->cond != br->cond)
 180                 return 0;
 181         /*
 182          * Ahhah! We've found a branch to a branch on the same conditional!
 183          * Now we just need to see if we can rewrite the branch..
 184          */
 185         retval = 0;
 186         final = true ? insn->bb_true : insn->bb_false;
 187         if (bb_has_side_effects(target))
 188                 goto try_to_rewrite_target;
 189         if (bb_depends_on(final, target))
 190                 goto try_to_rewrite_target;
 191         return rewrite_branch(bb, target_p, target, final);
 192
 193 try_to_rewrite_target:
 194         /*
 195          * If we're the only parent, at least we can rewrite the
 196          * now-known second branch.
 197          */
 198         if (bb_list_size(target->parents) != 1)
 199                 return retval;
 200         insert_branch(target, insn, final);
 201         kill_instruction(insn);
 202         return 1;
 203 }
 204
 205 static int simplify_one_branch(struct basic_block *bb, struct instruction *br)
 206 {
 207         if (simplify_phi_branch(bb, br))
 208                 return 1;
 209         return simplify_branch_branch(bb, br, &br->bb_true, 1) |
 210                simplify_branch_branch(bb, br, &br->bb_false, 0);
 211 }
 212
 213 static int simplify_branch_nodes(struct entrypoint *ep)
 214 {
 215         int changed = 0;
 216         struct basic_block *bb;
 217
 218         FOR_EACH_PTR(ep->bbs, bb) {
 219                 struct instruction *br = last_instruction(bb->insns);
 220
 221                 if (!br || br->opcode != OP_BR || !br->bb_false)
 222                         continue;
 223                 changed |= simplify_one_branch(bb, br);
 224         } END_FOR_EACH_PTR(bb);
 225         return changed;
 226 }
 227
 228 /*
 229  * This is called late - when we have intra-bb liveness information..
 230  */
 231 int simplify_flow(struct entrypoint *ep)
 232 {
 233         return simplify_branch_nodes(ep);
 234 }
 235
 236 static inline void concat_user_list(struct pseudo_user_list *src, struct pseudo_user_list **dst)
 237 {
 238         concat_ptr_list((struct ptr_list *)src, (struct ptr_list **)dst);
 239 }
 240
 241 void convert_instruction_target(struct instruction *insn, pseudo_t src)
 242 {
 243         pseudo_t target;
 244         struct pseudo_user *pu;
 245         /*
 246          * Go through the "insn->users" list and replace them all..
 247          */
 248         target = insn->target;
 249         if (target == src)
 250                 return;
 251         FOR_EACH_PTR(target->users, pu) {
 252                 if (*pu->userp != VOID) {
 253                         assert(*pu->userp == target);
 254                         *pu->userp = src;
 255                 }
 256         } END_FOR_EACH_PTR(pu);
 257         concat_user_list(target->users, &src->users);
 258         target->users = NULL;
 259 }
 260
 261 void convert_load_instruction(struct instruction *insn, pseudo_t src)
 262 {
 263         convert_instruction_target(insn, src);
 264         /* Turn the load into a no-op */
 265         insn->opcode = OP_LNOP;
 266         insn->bb = NULL;
 267 }
 268
 269 static int overlapping_memop(struct instruction *a, struct instruction *b)
 270 {
 271         unsigned int a_start = bytes_to_bits(a->offset);
 272         unsigned int b_start = bytes_to_bits(b->offset);
 273         unsigned int a_size = a->size;
 274         unsigned int b_size = b->size;
 275
 276         if (a_size + a_start <= b_start)
 277                 return 0;
 278         if (b_size + b_start <= a_start)
 279                 return 0;
 280         return 1;
 281 }
 282
 283 static inline int same_memop(struct instruction *a, struct instruction *b)
 284 {
 285         return  a->offset == b->offset && a->size == b->size;
 286 }
 287
 288 /*
 289  * Return 1 if "dom" dominates the access to "pseudo"
 290  * in "insn".
 291  *
 292  * Return 0 if it doesn't, and -1 if you don't know.
 293  */
 294 int dominates(pseudo_t pseudo, struct instruction *insn, struct instruction *dom, int local)
 295 {
 296         int opcode = dom->opcode;
 297
 298         if (opcode == OP_CALL || opcode == OP_ENTRY)
 299                 return local ? 0 : -1;
 300         if (opcode != OP_LOAD && opcode != OP_STORE)
 301                 return 0;
 302         if (dom->src != pseudo) {
 303                 if (local)
 304                         return 0;
 305                 /* We don't think two explicitly different symbols ever alias */
 306                 if (dom->src->type == PSEUDO_SYM)
 307                         return 0;
 308                 /* We could try to do some alias analysis here */
 309                 return -1;
 310         }
 311         if (!same_memop(insn, dom)) {
 312                 if (dom->opcode == OP_LOAD)
 313                         return 0;
 314                 if (!overlapping_memop(insn, dom))
 315                         return 0;
 316                 return -1;
 317         }
 318         return 1;
 319 }
 320
 321 static int phisrc_in_bb(struct pseudo_list *list, struct basic_block *bb)
 322 {
 323         pseudo_t p;
 324         FOR_EACH_PTR(list, p) {
 325                 if (p->def->bb == bb)
 326                         return 1;
 327         } END_FOR_EACH_PTR(p);
 328
 329         return 0;
 330 }
 331
 332 static int find_dominating_parents(pseudo_t pseudo, struct instruction *insn,
 333         struct basic_block *bb, unsigned long generation, struct pseudo_list **dominators,
 334         int local)
 335 {
 336         struct basic_block *parent;
 337
 338         if (!bb->parents)
 339                 return !!local;
 340
 341         FOR_EACH_PTR(bb->parents, parent) {
 342                 struct instruction *one;
 343                 struct instruction *br;
 344                 pseudo_t phi;
 345
 346                 FOR_EACH_PTR_REVERSE(parent->insns, one) {
 347                         int dominance;
 348                         if (one == insn)
 349                                 goto no_dominance;
 350                         dominance = dominates(pseudo, insn, one, local);
 351                         if (dominance < 0) {
 352                                 if (one->opcode == OP_LOAD)
 353                                         continue;
 354                                 return 0;
 355                         }
 356                         if (!dominance)
 357                                 continue;
 358                         goto found_dominator;
 359                 } END_FOR_EACH_PTR_REVERSE(one);
 360 no_dominance:
 361                 if (parent->generation == generation)
 362                         continue;
 363                 parent->generation = generation;
 364
 365                 if (!find_dominating_parents(pseudo, insn, parent, generation, dominators, local))
 366                         return 0;
 367                 continue;
 368
 369 found_dominator:
 370                 if (dominators && phisrc_in_bb(*dominators, parent))
 371                         continue;
 372                 br = delete_last_instruction(&parent->insns);
 373                 phi = alloc_phi(parent, one->target, one->size);
 374                 phi->ident = phi->ident ? : pseudo->ident;
 375                 add_instruction(&parent->insns, br);
 376                 use_pseudo(insn, phi, add_pseudo(dominators, phi));
 377         } END_FOR_EACH_PTR(parent);
 378         return 1;
 379 }
 380
 381 /*
 382  * We should probably sort the phi list just to make it easier to compare
 383  * later for equality.
 384  */
 385 void rewrite_load_instruction(struct instruction *insn, struct pseudo_list *dominators)
 386 {
 387         pseudo_t new, phi;
 388
 389         /*
 390          * Check for somewhat common case of duplicate
 391          * phi nodes.
 392          */
 393         new = first_pseudo(dominators)->def->src1;
 394         FOR_EACH_PTR(dominators, phi) {
 395                 if (new != phi->def->src1)
 396                         goto complex_phi;
 397                 new->ident = new->ident ? : phi->ident;
 398         } END_FOR_EACH_PTR(phi);
 399
 400         /*
 401          * All the same pseudo - mark the phi-nodes unused
 402          * and convert the load into a LNOP and replace the
 403          * pseudo.
 404          */
 405         FOR_EACH_PTR(dominators, phi) {
 406                 kill_instruction(phi->def);
 407         } END_FOR_EACH_PTR(phi);
 408         convert_load_instruction(insn, new);
 409         return;
 410
 411 complex_phi:
 412         /* We leave symbol pseudos with a bogus usage list here */
 413         if (insn->src->type != PSEUDO_SYM)
 414                 kill_use(&insn->src);
 415         insn->opcode = OP_PHI;
 416         insn->phi_list = dominators;
 417 }
 418
 419 static int find_dominating_stores(pseudo_t pseudo, struct instruction *insn,
 420         unsigned long generation, int local)
 421 {
 422         struct basic_block *bb = insn->bb;
 423         struct instruction *one, *dom = NULL;
 424         struct pseudo_list *dominators;
 425         int partial;
 426
 427         /* Unreachable load? Undo it */
 428         if (!bb) {
 429                 insn->opcode = OP_LNOP;
 430                 return 1;
 431         }
 432
 433         partial = 0;
 434         FOR_EACH_PTR(bb->insns, one) {
 435                 int dominance;
 436                 if (one == insn)
 437                         goto found;
 438                 dominance = dominates(pseudo, insn, one, local);
 439                 if (dominance < 0) {
 440                         /* Ignore partial load dominators */
 441                         if (one->opcode == OP_LOAD)
 442                                 continue;
 443                         dom = NULL;
 444                         partial = 1;
 445                         continue;
 446                 }
 447                 if (!dominance)
 448                         continue;
 449                 dom = one;
 450                 partial = 0;
 451         } END_FOR_EACH_PTR(one);
 452         /* Whaa? */
 453         warning(pseudo->sym->pos, "unable to find symbol read");
 454         return 0;
 455 found:
 456         if (partial)
 457                 return 0;
 458
 459         if (dom) {
 460                 convert_load_instruction(insn, dom->target);
 461                 return 1;
 462         }
 463
 464         /* OK, go find the parents */
 465         bb->generation = generation;
 466
 467         dominators = NULL;
 468         if (!find_dominating_parents(pseudo, insn, bb, generation, &dominators, local))
 469                 return 0;
 470
 471         /* This happens with initial assignments to structures etc.. */
 472         if (!dominators) {
 473                 if (!local)
 474                         return 0;
 475                 check_access(insn);
 476                 convert_load_instruction(insn, value_pseudo(0));
 477                 return 1;
 478         }
 479
 480         /*
 481          * If we find just one dominating instruction, we
 482          * can turn it into a direct thing. Otherwise we'll
 483          * have to turn the load into a phi-node of the
 484          * dominators.
 485          */
 486         rewrite_load_instruction(insn, dominators);
 487         return 1;
 488 }
 489
 490 static void kill_store(struct instruction *insn)
 491 {
 492         if (insn) {
 493                 insn->bb = NULL;
 494                 insn->opcode = OP_SNOP;
 495                 kill_use(&insn->target);
 496         }
 497 }
 498
 499 /* Kill a pseudo that is dead on exit from the bb */
 500 static void kill_dead_stores(pseudo_t pseudo, unsigned long generation, struct basic_block *bb, int local)
 501 {
 502         struct instruction *insn;
 503         struct basic_block *parent;
 504
 505         if (bb->generation == generation)
 506                 return;
 507         bb->generation = generation;
 508         FOR_EACH_PTR_REVERSE(bb->insns, insn) {
 509                 int opcode = insn->opcode;
 510
 511                 if (opcode != OP_LOAD && opcode != OP_STORE) {
 512                         if (local)
 513                                 continue;
 514                         if (opcode == OP_CALL)
 515                                 return;
 516                         continue;
 517                 }
 518                 if (insn->src == pseudo) {
 519                         if (opcode == OP_LOAD)
 520                                 return;
 521                         kill_store(insn);
 522                         continue;
 523                 }
 524                 if (local)
 525                         continue;
 526                 if (insn->src->type != PSEUDO_SYM)
 527                         return;
 528         } END_FOR_EACH_PTR_REVERSE(insn);
 529
 530         FOR_EACH_PTR(bb->parents, parent) {
 531                 struct basic_block *child;
 532                 FOR_EACH_PTR(parent->children, child) {
 533                         if (child && child != bb)
 534                                 return;
 535                 } END_FOR_EACH_PTR(child);
 536                 kill_dead_stores(pseudo, generation, parent, local);
 537         } END_FOR_EACH_PTR(parent);
 538 }
 539
 540 /*
 541  * This should see if the "insn" trivially dominates some previous store, and kill the
 542  * store if unnecessary.
 543  */
 544 static void kill_dominated_stores(pseudo_t pseudo, struct instruction *insn,
 545         unsigned long generation, struct basic_block *bb, int local, int found)
 546 {
 547         struct instruction *one;
 548         struct basic_block *parent;
 549
 550         /* Unreachable store? Undo it */
 551         if (!bb) {
 552                 kill_store(insn);
 553                 return;
 554         }
 555         if (bb->generation == generation)
 556                 return;
 557         bb->generation = generation;
 558         FOR_EACH_PTR_REVERSE(bb->insns, one) {
 559                 int dominance;
 560                 if (!found) {
 561                         if (one != insn)
 562                                 continue;
 563                         found = 1;
 564                         continue;
 565                 }
 566                 dominance = dominates(pseudo, insn, one, local);
 567                 if (!dominance)
 568                         continue;
 569                 if (dominance < 0)
 570                         return;
 571                 if (one->opcode == OP_LOAD)
 572                         return;
 573                 kill_store(one);
 574         } END_FOR_EACH_PTR_REVERSE(one);
 575
 576         if (!found) {
 577                 warning(bb->pos, "Unable to find instruction");
 578                 return;
 579         }
 580
 581         FOR_EACH_PTR(bb->parents, parent) {
 582                 struct basic_block *child;
 583                 FOR_EACH_PTR(parent->children, child) {
 584                         if (child && child != bb)
 585                                 return;
 586                 } END_FOR_EACH_PTR(child);
 587                 kill_dominated_stores(pseudo, insn, generation, parent, local, found);
 588         } END_FOR_EACH_PTR(parent);
 589 }
 590
 591 void check_access(struct instruction *insn)
 592 {
 593         pseudo_t pseudo = insn->src;
 594
 595         if (insn->bb && pseudo->type == PSEUDO_SYM) {
 596                 int offset = insn->offset, bit = bytes_to_bits(offset) + insn->size;
 597                 struct symbol *sym = pseudo->sym;
 598
 599                 if (sym->bit_size > 0 && (offset < 0 || bit > sym->bit_size))
 600                         warning(insn->pos, "invalid access %s '%s' (%d %d)",
 601                                 offset < 0 ? "below" : "past the end of",
 602                                 show_ident(sym->ident), offset,
 603                                 bits_to_bytes(sym->bit_size));
 604         }
 605 }
 606
 607 static void simplify_one_symbol(struct entrypoint *ep, struct symbol *sym)
 608 {
 609         pseudo_t pseudo, src;
 610         struct pseudo_user *pu;
 611         struct instruction *def;
 612         unsigned long mod;
 613         int all, stores, complex;
 614
 615         /* Never used as a symbol? */
 616         pseudo = sym->pseudo;
 617         if (!pseudo)
 618                 return;
 619
 620         /* We don't do coverage analysis of volatiles.. */
 621         if (sym->ctype.modifiers & MOD_VOLATILE)
 622                 return;
 623
 624         /* ..and symbols with external visibility need more care */
 625         mod = sym->ctype.modifiers & (MOD_NONLOCAL | MOD_STATIC | MOD_ADDRESSABLE);
 626         if (mod)
 627                 goto external_visibility;
 628
 629         def = NULL;
 630         stores = 0;
 631         complex = 0;
 632         FOR_EACH_PTR(pseudo->users, pu) {
 633                 /* We know that the symbol-pseudo use is the "src" in the instruction */
 634                 struct instruction *insn = pu->insn;
 635
 636                 switch (insn->opcode) {
 637                 case OP_STORE:
 638                         stores++;
 639                         def = insn;
 640                         break;
 641                 case OP_LOAD:
 642                         break;
 643                 case OP_SYMADDR:
 644                         if (!insn->bb)
 645                                 continue;
 646                         mod |= MOD_ADDRESSABLE;
 647                         goto external_visibility;
 648                 case OP_NOP:
 649                 case OP_SNOP:
 650                 case OP_LNOP:
 651                 case OP_PHI:
 652                         continue;
 653                 default:
 654                         warning(sym->pos, "symbol '%s' pseudo used in unexpected way", show_ident(sym->ident));
 655                 }
 656                 complex |= insn->offset;
 657         } END_FOR_EACH_PTR(pu);
 658
 659         if (complex)
 660                 goto complex_def;
 661         if (stores > 1)
 662                 goto multi_def;
 663
 664         /*
 665          * Goodie, we have a single store (if even that) in the whole
 666          * thing. Replace all loads with moves from the pseudo,
 667          * replace the store with a def.
 668          */
 669         src = VOID;
 670         if (def)
 671                 src = def->target;
 672
 673         FOR_EACH_PTR(pseudo->users, pu) {
 674                 struct instruction *insn = pu->insn;
 675                 if (insn->opcode == OP_LOAD) {
 676                         check_access(insn);
 677                         convert_load_instruction(insn, src);
 678                 }
 679         } END_FOR_EACH_PTR(pu);
 680
 681         /* Turn the store into a no-op */
 682         kill_store(def);
 683         return;
 684
 685 multi_def:
 686 complex_def:
 687 external_visibility:
 688         all = 1;
 689         FOR_EACH_PTR_REVERSE(pseudo->users, pu) {
 690                 struct instruction *insn = pu->insn;
 691                 if (insn->opcode == OP_LOAD)
 692                         all &= find_dominating_stores(pseudo, insn, ++bb_generation, !mod);
 693         } END_FOR_EACH_PTR_REVERSE(pu);
 694
 695         /* If we converted all the loads, remove the stores. They are dead */
 696         if (all && !mod) {
 697                 FOR_EACH_PTR(pseudo->users, pu) {
 698                         struct instruction *insn = pu->insn;
 699                         if (insn->opcode == OP_STORE)
 700                                 kill_store(insn);
 701                 } END_FOR_EACH_PTR(pu);
 702         } else {
 703                 /*
 704                  * If we couldn't take the shortcut, see if we can at least kill some
 705                  * of them..
 706                  */
 707                 FOR_EACH_PTR(pseudo->users, pu) {
 708                         struct instruction *insn = pu->insn;
 709                         if (insn->opcode == OP_STORE)
 710                                 kill_dominated_stores(pseudo, insn, ++bb_generation, insn->bb, !mod, 0);
 711                 } END_FOR_EACH_PTR(pu);
 712
 713                 if (!(mod & (MOD_NONLOCAL | MOD_STATIC))) {
 714                         struct basic_block *bb;
 715                         FOR_EACH_PTR(ep->bbs, bb) {
 716                                 if (!bb->children)
 717                                         kill_dead_stores(pseudo, ++bb_generation, bb, !mod);
 718                         } END_FOR_EACH_PTR(bb);
 719                 }
 720         }
 721
 722         return;
 723 }
 724
 725 void simplify_symbol_usage(struct entrypoint *ep)
 726 {
 727         pseudo_t pseudo;
 728
 729         FOR_EACH_PTR(ep->accesses, pseudo) {
 730                 simplify_one_symbol(ep, pseudo->sym);
 731         } END_FOR_EACH_PTR(pseudo);
 732 }
 733
 734 static void mark_bb_reachable(struct basic_block *bb, unsigned long generation)
 735 {
 736         struct basic_block *child;
 737
 738         if (bb->generation == generation)
 739                 return;
 740         bb->generation = generation;
 741         FOR_EACH_PTR(bb->children, child) {
 742                 mark_bb_reachable(child, generation);
 743         } END_FOR_EACH_PTR(child);
 744 }
 745
 746 static void kill_defs(struct instruction *insn)
 747 {
 748         pseudo_t target = insn->target;
 749
 750         if (!has_use_list(target))
 751                 return;
 752         if (target->def != insn)
 753                 return;
 754
 755         convert_instruction_target(insn, VOID);
 756 }
 757
 758 void kill_bb(struct basic_block *bb)
 759 {
 760         struct instruction *insn;
 761         struct basic_block *child, *parent;
 762
 763         FOR_EACH_PTR(bb->insns, insn) {
 764                 kill_instruction_force(insn);
 765                 kill_defs(insn);
 766                 /*
 767                  * We kill unreachable instructions even if they
 768                  * otherwise aren't "killable" (e.g. volatile loads)
 769                  */
 770         } END_FOR_EACH_PTR(insn);
 771         bb->insns = NULL;
 772
 773         FOR_EACH_PTR(bb->children, child) {
 774                 remove_bb_from_list(&child->parents, bb, 0);
 775         } END_FOR_EACH_PTR(child);
 776         bb->children = NULL;
 777
 778         FOR_EACH_PTR(bb->parents, parent) {
 779                 remove_bb_from_list(&parent->children, bb, 0);
 780         } END_FOR_EACH_PTR(parent);
 781         bb->parents = NULL;
 782 }
 783
 784 void kill_unreachable_bbs(struct entrypoint *ep)
 785 {
 786         struct basic_block *bb;
 787         unsigned long generation = ++bb_generation;
 788
 789         mark_bb_reachable(ep->entry->bb, generation);
 790         FOR_EACH_PTR(ep->bbs, bb) {
 791                 if (bb->generation == generation)
 792                         continue;
 793                 /* Mark it as being dead */
 794                 kill_bb(bb);
 795                 bb->ep = NULL;
 796                 DELETE_CURRENT_PTR(bb);
 797         } END_FOR_EACH_PTR(bb);
 798         PACK_PTR_LIST(&ep->bbs);
 799 }
 800
 801 static int rewrite_parent_branch(struct basic_block *bb, struct basic_block *old, struct basic_block *new)
 802 {
 803         int changed = 0;
 804         struct instruction *insn = last_instruction(bb->insns);
 805
 806         if (!insn)
 807                 return 0;
 808
 809         /* Infinite loops: let's not "optimize" them.. */
 810         if (old == new)
 811                 return 0;
 812
 813         switch (insn->opcode) {
 814         case OP_BR:
 815                 changed |= rewrite_branch(bb, &insn->bb_true, old, new);
 816                 changed |= rewrite_branch(bb, &insn->bb_false, old, new);
 817                 assert(changed);
 818                 return changed;
 819         case OP_SWITCH: {
 820                 struct multijmp *jmp;
 821                 FOR_EACH_PTR(insn->multijmp_list, jmp) {
 822                         changed |= rewrite_branch(bb, &jmp->target, old, new);
 823                 } END_FOR_EACH_PTR(jmp);
 824                 assert(changed);
 825                 return changed;
 826         }
 827         default:
 828                 return 0;
 829         }
 830 }
 831
 832 static struct basic_block * rewrite_branch_bb(struct basic_block *bb, struct instruction *br)
 833 {
 834         struct basic_block *parent;
 835         struct basic_block *target = br->bb_true;
 836         struct basic_block *false = br->bb_false;
 837
 838         if (target && false) {
 839                 pseudo_t cond = br->cond;
 840                 if (cond->type != PSEUDO_VAL)
 841                         return NULL;
 842                 target = cond->value ? target : false;
 843         }
 844
 845         /*
 846          * We can't do FOR_EACH_PTR() here, because the parent list
 847          * may change when we rewrite the parent.
 848          */
 849         while ((parent = first_basic_block(bb->parents)) != NULL) {
 850                 if (!rewrite_parent_branch(parent, bb, target))
 851                         return NULL;
 852         }
 853         return target;
 854 }
 855
 856 static void vrfy_bb_in_list(struct basic_block *bb, struct basic_block_list *list)
 857 {
 858         if (bb) {
 859                 struct basic_block *tmp;
 860                 int no_bb_in_list = 0;
 861
 862                 FOR_EACH_PTR(list, tmp) {
 863                         if (bb == tmp)
 864                                 return;
 865                 } END_FOR_EACH_PTR(tmp);
 866                 assert(no_bb_in_list);
 867         }
 868 }
 869
 870 static void vrfy_parents(struct basic_block *bb)
 871 {
 872         struct basic_block *tmp;
 873         FOR_EACH_PTR(bb->parents, tmp) {
 874                 vrfy_bb_in_list(bb, tmp->children);
 875         } END_FOR_EACH_PTR(tmp);
 876 }
 877
 878 static void vrfy_children(struct basic_block *bb)
 879 {
 880         struct basic_block *tmp;
 881         struct instruction *br = last_instruction(bb->insns);
 882
 883         if (!br) {
 884                 assert(!bb->children);
 885                 return;
 886         }
 887         switch (br->opcode) {
 888                 struct multijmp *jmp;
 889         case OP_BR:
 890                 vrfy_bb_in_list(br->bb_true, bb->children);
 891                 vrfy_bb_in_list(br->bb_false, bb->children);
 892                 break;
 893         case OP_SWITCH:
 894         case OP_COMPUTEDGOTO:
 895                 FOR_EACH_PTR(br->multijmp_list, jmp) {
 896                         vrfy_bb_in_list(jmp->target, bb->children);
 897                 } END_FOR_EACH_PTR(jmp);
 898                 break;
 899         default:
 900                 break;
 901         }
 902
 903         FOR_EACH_PTR(bb->children, tmp) {
 904                 vrfy_bb_in_list(bb, tmp->parents);
 905         } END_FOR_EACH_PTR(tmp);
 906 }
 907
 908 static void vrfy_bb_flow(struct basic_block *bb)
 909 {
 910         vrfy_children(bb);
 911         vrfy_parents(bb);
 912 }
 913
 914 void vrfy_flow(struct entrypoint *ep)
 915 {
 916         struct basic_block *bb;
 917         struct basic_block *entry = ep->entry->bb;
 918
 919         FOR_EACH_PTR(ep->bbs, bb) {
 920                 if (bb == entry)
 921                         entry = NULL;
 922                 vrfy_bb_flow(bb);
 923         } END_FOR_EACH_PTR(bb);
 924         assert(!entry);
 925 }
 926
 927 void pack_basic_blocks(struct entrypoint *ep)
 928 {
 929         struct basic_block *bb;
 930
 931         /* See if we can merge a bb into another one.. */
 932         FOR_EACH_PTR(ep->bbs, bb) {
 933                 struct instruction *first, *insn;
 934                 struct basic_block *parent, *child, *last;
 935
 936                 if (!bb_reachable(bb))
 937                         continue;
 938
 939                 /*
 940                  * Just a branch?
 941                  */
 942                 FOR_EACH_PTR(bb->insns, first) {
 943                         if (!first->bb)
 944                                 continue;
 945                         switch (first->opcode) {
 946                         case OP_NOP: case OP_LNOP: case OP_SNOP:
 947                                 continue;
 948                         case OP_BR: {
 949                                 struct basic_block *replace;
 950                                 replace = rewrite_branch_bb(bb, first);
 951                                 if (replace) {
 952                                         kill_bb(bb);
 953                                         goto no_merge;
 954                                 }
 955                         }
 956                         /* fallthrough */
 957                         default:
 958                                 goto out;
 959                         }
 960                 } END_FOR_EACH_PTR(first);
 961
 962 out:
 963                 /*
 964                  * See if we only have one parent..
 965                  */
 966                 last = NULL;
 967                 FOR_EACH_PTR(bb->parents, parent) {
 968                         if (last) {
 969                                 if (last != parent)
 970                                         goto no_merge;
 971                                 continue;
 972                         }
 973                         last = parent;
 974                 } END_FOR_EACH_PTR(parent);
 975
 976                 parent = last;
 977                 if (!parent || parent == bb)
 978                         continue;
 979
 980                 /*
 981                  * Goodie. See if the parent can merge..
 982                  */
 983                 FOR_EACH_PTR(parent->children, child) {
 984                         if (child != bb)
 985                                 goto no_merge;
 986                 } END_FOR_EACH_PTR(child);
 987
 988                 /*
 989                  * Merge the two.
 990                  */
 991                 repeat_phase |= REPEAT_CSE;
 992
 993                 parent->children = bb->children;
 994                 bb->children = NULL;
 995                 bb->parents = NULL;
 996
 997                 FOR_EACH_PTR(parent->children, child) {
 998                         replace_bb_in_list(&child->parents, bb, parent, 0);
 999                 } END_FOR_EACH_PTR(child);
1000
1001                 kill_instruction(delete_last_instruction(&parent->insns));
1002                 FOR_EACH_PTR(bb->insns, insn) {
1003                         if (insn->bb) {
1004                                 assert(insn->bb == bb);
1005                                 insn->bb = parent;
1006                         }
1007                         add_instruction(&parent->insns, insn);
1008                 } END_FOR_EACH_PTR(insn);
1009                 bb->insns = NULL;
1010
1011         no_merge:
1012                 /* nothing to do */;
1013         } END_FOR_EACH_PTR(bb);
1014 }
1015
1016