flow.c

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