flow.c

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