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