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