gcc/ssa-dce.c

   1 /* Dead-code elimination pass for the GNU compiler.
   2    Copyright (C) 2000, 2001 Free Software Foundation, Inc.
   3    Written by Jeffrey D. Oldham <oldham@codesourcery.com>.
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify it under
   8 the terms of the GNU General Public License as published by the Free
   9 Software Foundation; either version 2, or (at your option) any later
  10 version.
  11
  12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  15 for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; see the file COPYING.  If not, write to the Free
  19 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
  20 02111-1307, USA.  */
  21
  22 /* Dead-code elimination is the removal of instructions which have no
  23    impact on the program's output.  "Dead instructions" have no impact
  24    on the program's output, while "necessary instructions" may have
  25    impact on the output.
  26
  27    The algorithm consists of three phases:
  28    1) marking as necessary all instructions known to be necessary,
  29       e.g., writing a value to memory,
  30    2) propagating necessary instructions, e.g., the instructions
  31       giving values to operands in necessary instructions, and
  32    3) removing dead instructions (except replacing dead conditionals
  33       with unconditional jumps).
  34
  35    Side Effects:
  36    The last step can require adding labels, deleting insns, and
  37    modifying basic block structures.  Some conditional jumps may be
  38    converted to unconditional jumps so the control-flow graph may be
  39    out-of-date.
  40
  41    Edges from some infinite loops to the exit block can be added to
  42    the control-flow graph, but will be removed after this pass is
  43    complete.
  44
  45    It Does Not Perform:
  46    We decided to not simultaneously perform jump optimization and dead
  47    loop removal during dead-code elimination.  Thus, all jump
  48    instructions originally present remain after dead-code elimination
  49    but 1) unnecessary conditional jump instructions are changed to
  50    unconditional jump instructions and 2) all unconditional jump
  51    instructions remain.
  52
  53    Assumptions:
  54    1) SSA has been performed.
  55    2) The basic block and control-flow graph structures are accurate.
  56    3) The flow graph permits constructing an edge_list.
  57    4) note rtxes should be saved.
  58
  59    Unfinished:
  60    When replacing unnecessary conditional jumps with unconditional
  61    jumps, the control-flow graph is not updated.  It should be.
  62
  63    References:
  64    Building an Optimizing Compiler
  65    Robert Morgan
  66    Butterworth-Heinemann, 1998
  67    Section 8.9
  68 */
  69
  70 #include "config.h"
  71 #include "system.h"
  72
  73 #include "rtl.h"
  74 #include "hard-reg-set.h"
  75 #include "basic-block.h"
  76 #include "ssa.h"
  77 #include "insn-config.h"
  78 #include "recog.h"
  79 #include "output.h"
  80
  81 \f
  82 /* A map from blocks to the edges on which they are control dependent.  */
  83 typedef struct {
  84   /* An dynamically allocated array.  The Nth element corresponds to
  85      the block with index N + 2.  The Ith bit in the bitmap is set if
  86      that block is dependent on the Ith edge.  */
  87   bitmap *data;
  88   /* The number of elements in the array.  */
  89   int length;
  90 } control_dependent_block_to_edge_map_s, *control_dependent_block_to_edge_map;
  91
  92 /* Local function prototypes.  */
  93 static control_dependent_block_to_edge_map control_dependent_block_to_edge_map_create
  94   PARAMS((size_t num_basic_blocks));
  95 static void set_control_dependent_block_to_edge_map_bit
  96   PARAMS ((control_dependent_block_to_edge_map c, basic_block bb,
  97            int edge_index));
  98 static void control_dependent_block_to_edge_map_free
  99   PARAMS ((control_dependent_block_to_edge_map c));
 100 static void find_all_control_dependences
 101   PARAMS ((struct edge_list *el, int *pdom,
 102            control_dependent_block_to_edge_map cdbte));
 103 static void find_control_dependence
 104   PARAMS ((struct edge_list *el, int edge_index, int *pdom,
 105            control_dependent_block_to_edge_map cdbte));
 106 static basic_block find_pdom
 107   PARAMS ((int *pdom, basic_block block));
 108 static int inherently_necessary_register_1
 109   PARAMS ((rtx *current_rtx, void *data));
 110 static int inherently_necessary_register
 111   PARAMS ((rtx current_rtx));
 112 static int find_inherently_necessary
 113   PARAMS ((rtx current_rtx));
 114 static int propagate_necessity_through_operand
 115   PARAMS ((rtx *current_rtx, void *data));
 116 static void note_inherently_necessary_set
 117   PARAMS ((rtx, rtx, void *));
 118 \f
 119 /* Unnecessary insns are indicated using insns' in_struct bit.  */
 120
 121 /* Indicate INSN is dead-code; returns nothing.  */
 122 #define KILL_INSN(INSN)         INSN_DEAD_CODE_P(INSN) = 1
 123 /* Indicate INSN is necessary, i.e., not dead-code; returns nothing.  */
 124 #define RESURRECT_INSN(INSN)    INSN_DEAD_CODE_P(INSN) = 0
 125 /* Return nonzero if INSN is unnecessary.  */
 126 #define UNNECESSARY_P(INSN)     INSN_DEAD_CODE_P(INSN)
 127 static void mark_all_insn_unnecessary
 128   PARAMS ((void));
 129 /* Execute CODE with free variable INSN for all unnecessary insns in
 130    an unspecified order, producing no output.  */
 131 #define EXECUTE_IF_UNNECESSARY(INSN, CODE)      \
 132 {                                                               \
 133   rtx INSN;                                                     \
 134                                                                 \
 135   for (INSN = get_insns (); INSN != NULL_RTX; INSN = NEXT_INSN (INSN))  \
 136     if (INSN_DEAD_CODE_P (INSN)) {                              \
 137       CODE;                                                     \
 138     }                                                           \
 139 }
 140 /* Find the label beginning block BB.  */
 141 static rtx find_block_label
 142   PARAMS ((basic_block bb));
 143 /* Remove INSN, updating its basic block structure.  */
 144 static void delete_insn_bb
 145   PARAMS ((rtx insn));
 146 \f
 147 /* Recording which blocks are control dependent on which edges.  We
 148    expect each block to be control dependent on very few edges so we
 149    use a bitmap for each block recording its edges.  An array holds
 150    the bitmap.  Its position 0 entry holds the bitmap for block
 151    INVALID_BLOCK+1 so that all blocks, including the entry and exit
 152    blocks can participate in the data structure.  */
 153
 154 /* Create a control_dependent_block_to_edge_map, given the number
 155    NUM_BASIC_BLOCKS of non-entry, non-exit basic blocks, e.g.,
 156    n_basic_blocks.  This memory must be released using
 157    control_dependent_block_to_edge_map_free ().  */
 158
 159 static control_dependent_block_to_edge_map
 160 control_dependent_block_to_edge_map_create (num_basic_blocks)
 161      size_t num_basic_blocks;
 162 {
 163   int i;
 164   control_dependent_block_to_edge_map c
 165     = xmalloc (sizeof (control_dependent_block_to_edge_map_s));
 166   c->length = num_basic_blocks - (INVALID_BLOCK+1);
 167   c->data = xmalloc ((size_t) c->length*sizeof (bitmap));
 168   for (i = 0; i < c->length; ++i)
 169     c->data[i] = BITMAP_XMALLOC ();
 170
 171   return c;
 172 }
 173
 174 /* Indicate block BB is control dependent on an edge with index
 175    EDGE_INDEX in the mapping C of blocks to edges on which they are
 176    control-dependent.  */
 177
 178 static void
 179 set_control_dependent_block_to_edge_map_bit (c, bb, edge_index)
 180      control_dependent_block_to_edge_map c;
 181      basic_block bb;
 182      int edge_index;
 183 {
 184   if (bb->index - (INVALID_BLOCK+1) >= c->length)
 185     abort ();
 186
 187   bitmap_set_bit (c->data[bb->index - (INVALID_BLOCK+1)],
 188                   edge_index);
 189 }
 190
 191 /* Execute CODE for each edge (given number EDGE_NUMBER within the
 192    CODE) for which the block containing INSN is control dependent,
 193    returning no output.  CDBTE is the mapping of blocks to edges on
 194    which they are control-dependent.  */
 195
 196 #define EXECUTE_IF_CONTROL_DEPENDENT(CDBTE, INSN, EDGE_NUMBER, CODE) \
 197         EXECUTE_IF_SET_IN_BITMAP \
 198           (CDBTE->data[BLOCK_NUM (INSN) - (INVALID_BLOCK+1)], 0, \
 199           EDGE_NUMBER, CODE)
 200
 201 /* Destroy a control_dependent_block_to_edge_map C.  */
 202
 203 static void
 204 control_dependent_block_to_edge_map_free (c)
 205      control_dependent_block_to_edge_map c;
 206 {
 207   int i;
 208   for (i = 0; i < c->length; ++i)
 209     BITMAP_XFREE (c->data[i]);
 210   free ((PTR) c);
 211 }
 212
 213 /* Record all blocks' control dependences on all edges in the edge
 214    list EL, ala Morgan, Section 3.6.  The mapping PDOM of blocks to
 215    their postdominators are used, and results are stored in CDBTE,
 216    which should be empty.  */
 217
 218 static void
 219 find_all_control_dependences (el, pdom, cdbte)
 220    struct edge_list *el;
 221    int *pdom;
 222    control_dependent_block_to_edge_map cdbte;
 223 {
 224   int i;
 225
 226   for (i = 0; i < NUM_EDGES (el); ++i)
 227     find_control_dependence (el, i, pdom, cdbte);
 228 }
 229
 230 /* Determine all blocks' control dependences on the given edge with
 231    edge_list EL index EDGE_INDEX, ala Morgan, Section 3.6.  The
 232    mapping PDOM of blocks to their postdominators are used, and
 233    results are stored in CDBTE, which is assumed to be initialized
 234    with zeros in each (block b', edge) position.  */
 235
 236 static void
 237 find_control_dependence (el, edge_index, pdom, cdbte)
 238    struct edge_list *el;
 239    int edge_index;
 240    int *pdom;
 241    control_dependent_block_to_edge_map cdbte;
 242 {
 243   basic_block current_block;
 244   basic_block ending_block;
 245
 246   if (INDEX_EDGE_PRED_BB (el, edge_index) == EXIT_BLOCK_PTR)
 247     abort ();
 248   ending_block =
 249     (INDEX_EDGE_PRED_BB (el, edge_index) == ENTRY_BLOCK_PTR)
 250     ? BASIC_BLOCK (0)
 251     : find_pdom (pdom, INDEX_EDGE_PRED_BB (el, edge_index));
 252
 253   for (current_block = INDEX_EDGE_SUCC_BB (el, edge_index);
 254        current_block != ending_block && current_block != EXIT_BLOCK_PTR;
 255        current_block = find_pdom (pdom, current_block))
 256     {
 257       set_control_dependent_block_to_edge_map_bit (cdbte,
 258                                                    current_block,
 259                                                    edge_index);
 260     }
 261 }
 262 \f
 263 /* Find the immediate postdominator PDOM of the specified basic block
 264    BLOCK.  This function is necessary because some blocks have
 265    negative numbers.  */
 266
 267 static basic_block
 268 find_pdom (pdom, block)
 269      int *pdom;
 270      basic_block block;
 271 {
 272   if (!block)
 273     abort ();
 274   if (block->index == INVALID_BLOCK)
 275     abort ();
 276
 277   if (block == ENTRY_BLOCK_PTR)
 278     return BASIC_BLOCK (0);
 279   else if (block == EXIT_BLOCK_PTR || pdom[block->index] == EXIT_BLOCK)
 280     return EXIT_BLOCK_PTR;
 281   else
 282     return BASIC_BLOCK (pdom[block->index]);
 283 }
 284
 285 /* Determine if the given CURRENT_RTX uses a hard register not
 286    converted to SSA.  Returns nonzero only if it uses such a hard
 287    register.  DATA is not used.
 288
 289    The program counter (PC) is not considered inherently necessary
 290    since code should be position-independent and thus not depend on
 291    particular PC values.  */
 292
 293 static int
 294 inherently_necessary_register_1 (current_rtx, data)
 295      rtx *current_rtx;
 296      void *data ATTRIBUTE_UNUSED;
 297 {
 298   rtx x = *current_rtx;
 299
 300   if (x == NULL_RTX)
 301     return 0;
 302   switch (GET_CODE (x))
 303     {
 304     case CLOBBER:
 305       /* Do not traverse the rest of the clobber.  */
 306       return -1;
 307       break;
 308     case PC:
 309       return 0;
 310       break;
 311     case REG:
 312       if (CONVERT_REGISTER_TO_SSA_P (REGNO (x)) || x == pc_rtx)
 313         return 0;
 314       else
 315         return !0;
 316       break;
 317     default:
 318       return 0;
 319       break;
 320     }
 321 }
 322
 323 /* Return nonzero if the insn CURRENT_RTX is inherently necessary.  */
 324
 325 static int
 326 inherently_necessary_register (current_rtx)
 327      rtx current_rtx;
 328 {
 329   return for_each_rtx (&current_rtx,
 330                        &inherently_necessary_register_1, NULL);
 331 }
 332
 333
 334 /* Called via note_stores for each store in an insn.  Note whether
 335    or not a particular store is inherently necessary.  Store a
 336    nonzero value in inherently_necessary_p if such a store is found.  */
 337
 338 static void
 339 note_inherently_necessary_set (dest, set, data)
 340      rtx set ATTRIBUTE_UNUSED;
 341      rtx dest;
 342      void *data;
 343 {
 344   int *inherently_necessary_set_p = (int *)data;
 345
 346   while (GET_CODE (dest) == SUBREG
 347          || GET_CODE (dest) == STRICT_LOW_PART
 348          || GET_CODE (dest) == ZERO_EXTRACT
 349          || GET_CODE (dest) == SIGN_EXTRACT)
 350     dest = XEXP (dest, 0);
 351
 352   if (GET_CODE (dest) == MEM
 353       || GET_CODE (dest) == UNSPEC
 354       || GET_CODE (dest) == UNSPEC_VOLATILE)
 355     *inherently_necessary_set_p = 1;
 356 }
 357
 358 /* Mark X as inherently necessary if appropriate.  For example,
 359    function calls and storing values into memory are inherently
 360    necessary.  This function is to be used with for_each_rtx ().
 361    Return nonzero iff inherently necessary.  */
 362
 363 static int
 364 find_inherently_necessary (x)
 365      rtx x;
 366 {
 367   if (x == NULL_RTX)
 368     return 0;
 369   else if (inherently_necessary_register (x))
 370     return !0;
 371   else
 372     switch (GET_CODE (x))
 373       {
 374       case CALL_INSN:
 375       case BARRIER:
 376         return !0;
 377       case CODE_LABEL:
 378       case NOTE:
 379         return 0;
 380       case JUMP_INSN:
 381         return JUMP_TABLE_DATA_P (x) || computed_jump_p (x) != 0;
 382       case INSN:
 383         {
 384           int inherently_necessary_set = 0;
 385           note_stores (PATTERN (x),
 386                        note_inherently_necessary_set,
 387                        &inherently_necessary_set);
 388
 389           /* If we found an inherently necessary set or an asm
 390              instruction, then we consider this insn inherently
 391              necessary.  */
 392           return (inherently_necessary_set
 393                   || GET_CODE (PATTERN (x)) == ASM_INPUT
 394                   || asm_noperands (PATTERN (x)) >= 0);
 395         }
 396       default:
 397         /* Found an impossible insn type.  */
 398         abort();
 399         break;
 400       }
 401 }
 402
 403 /* Propagate necessity through REG and SUBREG operands of CURRENT_RTX.
 404    This function is called with for_each_rtx () on necessary
 405    instructions.  The DATA must be a varray of unprocessed
 406    instructions.  */
 407
 408 static int
 409 propagate_necessity_through_operand (current_rtx, data)
 410      rtx *current_rtx;
 411      void *data;
 412 {
 413   rtx x = *current_rtx;
 414   varray_type *unprocessed_instructions = (varray_type *) data;
 415
 416   if (x == NULL_RTX)
 417     return 0;
 418   switch ( GET_CODE (x))
 419     {
 420     case REG:
 421       if (CONVERT_REGISTER_TO_SSA_P (REGNO (x)))
 422         {
 423           rtx insn = VARRAY_RTX (ssa_definition, REGNO (x));
 424           if (insn != NULL_RTX && UNNECESSARY_P (insn))
 425             {
 426               RESURRECT_INSN (insn);
 427               VARRAY_PUSH_RTX (*unprocessed_instructions, insn);
 428             }
 429         }
 430       return 0;
 431
 432     default:
 433       return 0;
 434     }
 435 }
 436
 437 /* Indicate all insns initially assumed to be unnecessary.  */
 438
 439 static void
 440 mark_all_insn_unnecessary ()
 441 {
 442   rtx insn;
 443   for (insn = get_insns (); insn != NULL_RTX; insn = NEXT_INSN (insn))
 444     KILL_INSN (insn);
 445 }
 446
 447 /* Find the label beginning block BB, adding one if necessary.  */
 448
 449 static rtx
 450 find_block_label (bb)
 451      basic_block bb;
 452 {
 453   rtx insn = bb->head;
 454   if (LABEL_P (insn))
 455     return insn;
 456   else
 457     {
 458       rtx new_label = emit_label_before (gen_label_rtx (), insn);
 459       if (insn == bb->head)
 460         bb->head = new_label;
 461       return new_label;
 462     }
 463 }
 464
 465 /* Remove INSN, updating its basic block structure.  */
 466
 467 static void
 468 delete_insn_bb (insn)
 469      rtx insn;
 470 {
 471   basic_block bb;
 472   if (!insn)
 473     abort ();
 474
 475   /* Do not actually delete anything that is not an INSN.
 476
 477      We can get here because we only consider INSNs as
 478      potentially necessary.  We leave it to later passes
 479      to remove unnecessary notes, unused labels, etc.  */
 480   if (! INSN_P (insn))
 481     return;
 482
 483   bb = BLOCK_FOR_INSN (insn);
 484   if (!bb)
 485     abort ();
 486   if (bb->head == bb->end)
 487     {
 488       /* Delete the insn by converting it to a note.  */
 489       PUT_CODE (insn, NOTE);
 490       NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
 491       return;
 492     }
 493   else if (insn == bb->head)
 494     bb->head = NEXT_INSN (insn);
 495   else if (insn == bb->end)
 496     bb->end = PREV_INSN (insn);
 497   delete_insn (insn);
 498 }
 499 \f
 500 /* Perform the dead-code elimination.  */
 501
 502 void
 503 ssa_eliminate_dead_code ()
 504 {
 505   int i;
 506   rtx insn;
 507   /* Necessary instructions with operands to explore.  */
 508   varray_type unprocessed_instructions;
 509   /* Map element (b,e) is nonzero if the block is control dependent on
 510      edge.  "cdbte" abbreviates control dependent block to edge.  */
 511   control_dependent_block_to_edge_map cdbte;
 512  /* Element I is the immediate postdominator of block I.  */
 513   int *pdom;
 514   struct edge_list *el;
 515
 516   int max_insn_uid = get_max_uid ();
 517
 518   /* Initialize the data structures.  */
 519   mark_all_insn_unnecessary ();
 520   VARRAY_RTX_INIT (unprocessed_instructions, 64,
 521                    "unprocessed instructions");
 522   cdbte = control_dependent_block_to_edge_map_create (n_basic_blocks);
 523
 524   /* Prepare for use of BLOCK_NUM ().  */
 525   connect_infinite_loops_to_exit ();
 526    /* Be careful not to clear the added edges.  */
 527   compute_bb_for_insn (max_insn_uid);
 528
 529   /* Compute control dependence.  */
 530   pdom = (int *) xmalloc (n_basic_blocks * sizeof (int));
 531   for (i = 0; i < n_basic_blocks; ++i)
 532     pdom[i] = INVALID_BLOCK;
 533   calculate_dominance_info (pdom, NULL, CDI_POST_DOMINATORS);
 534   /* Assume there is a path from each node to the exit block.  */
 535   for (i = 0; i < n_basic_blocks; ++i)
 536     if (pdom[i] == INVALID_BLOCK)
 537       pdom[i] = EXIT_BLOCK;
 538   el = create_edge_list();
 539   find_all_control_dependences (el, pdom, cdbte);
 540
 541   /* Find inherently necessary instructions.  */
 542   for (insn = get_insns (); insn != NULL_RTX; insn = NEXT_INSN (insn))
 543     if (find_inherently_necessary (insn))
 544       {
 545         RESURRECT_INSN (insn);
 546         VARRAY_PUSH_RTX (unprocessed_instructions, insn);
 547       }
 548
 549   /* Propagate necessity using the operands of necessary instructions.  */
 550   while (VARRAY_ACTIVE_SIZE (unprocessed_instructions) > 0)
 551     {
 552       rtx current_instruction;
 553       int edge_number;
 554
 555       current_instruction = VARRAY_TOP_RTX (unprocessed_instructions);
 556       VARRAY_POP (unprocessed_instructions);
 557
 558       /* Make corresponding control dependent edges necessary.  */
 559       /* Assume the only JUMP_INSN is the block's last insn.  It appears
 560          that the last instruction of the program need not be a
 561          JUMP_INSN.  */
 562
 563       if (INSN_P (current_instruction)
 564           && !JUMP_TABLE_DATA_P (current_instruction))
 565         {
 566           /* Notes and labels contain no interesting operands.  */
 567           EXECUTE_IF_CONTROL_DEPENDENT
 568             (cdbte, current_instruction, edge_number,
 569             {
 570               rtx jump_insn = (INDEX_EDGE_PRED_BB (el, edge_number))->end;
 571               if (GET_CODE (jump_insn) == JUMP_INSN
 572                   && UNNECESSARY_P (jump_insn))
 573                 {
 574                   RESURRECT_INSN (jump_insn);
 575                   VARRAY_PUSH_RTX (unprocessed_instructions, jump_insn);
 576                 }
 577             });
 578
 579           /* Propagate through the operands.  */
 580           for_each_rtx (&current_instruction,
 581                         &propagate_necessity_through_operand,
 582                         (PTR) &unprocessed_instructions);
 583
 584           /* PHI nodes are somewhat special in that each PHI alternative
 585              has data and control dependencies.  The data dependencies
 586              are handled via propagate_necessity_through_operand.  We
 587              handle the control dependency here.
 588
 589              We consider the control dependent edges leading to the
 590              predecessor block associated with each PHI alternative
 591              as necessary.  */
 592           if (PHI_NODE_P (current_instruction))
 593             {
 594               rtvec phi_vec = XVEC (SET_SRC (PATTERN (current_instruction)), 0);
 595               int num_elem = GET_NUM_ELEM (phi_vec);
 596               int v;
 597
 598               for (v = num_elem - 2; v >= 0; v -= 2)
 599                 {
 600                   basic_block bb;
 601
 602                   bb = BASIC_BLOCK (INTVAL (RTVEC_ELT (phi_vec, v + 1)));
 603                   EXECUTE_IF_CONTROL_DEPENDENT
 604                     (cdbte, bb->end, edge_number,
 605                     {
 606                       rtx jump_insn;
 607
 608                       jump_insn = (INDEX_EDGE_PRED_BB (el, edge_number))->end;
 609                       if (((GET_CODE (jump_insn) == JUMP_INSN))
 610                           && UNNECESSARY_P (jump_insn))
 611                         {
 612                           RESURRECT_INSN (jump_insn);
 613                           VARRAY_PUSH_RTX (unprocessed_instructions, jump_insn);
 614                         }
 615                     });
 616
 617                 }
 618             }
 619         }
 620     }
 621
 622   /* Remove the unnecessary instructions.  */
 623   EXECUTE_IF_UNNECESSARY (insn,
 624   {
 625     if (any_condjump_p (insn))
 626       {
 627         basic_block bb = BLOCK_FOR_INSN (insn);
 628         basic_block pdom_bb = find_pdom (pdom, bb);
 629         rtx lbl;
 630         edge e;
 631
 632         /* Egad.  The immediate post dominator is the exit block.  We
 633            would like to optimize this conditional jump to jump directly
 634            to the exit block.  That can be difficult as we may not have
 635            a suitable CODE_LABEL that allows us to fall unmolested into
 636            the exit block.
 637
 638            So, we just delete the conditional branch by turning it into
 639            a deleted note.   That is safe, but just not as optimal as
 640            it could be.  */
 641         if (pdom_bb == EXIT_BLOCK_PTR)
 642           {
 643             /* Since we're going to just delete the branch, we need
 644                look at all the edges and remove all those which are not
 645                a fallthru edge.  */
 646             e = bb->succ;
 647             while (e)
 648               {
 649                 edge temp = e;
 650
 651                 e = e->succ_next;
 652                 if ((temp->flags & EDGE_FALLTHRU) == 0)
 653                   {
 654                     /* We've found a non-fallthru edge, find any PHI nodes
 655                        at the target and clean them up.  */
 656                     if (temp->dest != EXIT_BLOCK_PTR)
 657                       {
 658                         rtx insn
 659                           = first_insn_after_basic_block_note (temp->dest);
 660
 661                         while (PHI_NODE_P (insn))
 662                           {
 663                             remove_phi_alternative (PATTERN (insn), temp->src);
 664                             insn = NEXT_INSN (insn);
 665                           }
 666                       }
 667
 668                     remove_edge (temp);
 669                   }
 670               }
 671
 672             /* Now "delete" the conditional jump.  */
 673             PUT_CODE (insn, NOTE);
 674             NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
 675             continue;
 676           }
 677
 678         /* We've found a conditional branch that is unnecessary.
 679
 680            First, remove all outgoing edges from this block, updating
 681            PHI nodes as appropriate.  */
 682         e = bb->succ;
 683         while (e)
 684           {
 685             edge temp = e;
 686
 687             e = e->succ_next;
 688
 689             if (temp->flags & EDGE_ABNORMAL)
 690               continue;
 691
 692             /* We found an edge that is not executable.  First simplify
 693                the PHI nodes in the target block.  */
 694             if (temp->dest != EXIT_BLOCK_PTR)
 695               {
 696                 rtx insn = first_insn_after_basic_block_note (temp->dest);
 697
 698                 while (PHI_NODE_P (insn))
 699                   {
 700                     remove_phi_alternative (PATTERN (insn), temp->src);
 701                     insn = NEXT_INSN (insn);
 702                   }
 703               }
 704
 705             remove_edge (temp);
 706           }
 707
 708         /* Create an edge from this block to the post dominator.
 709            What about the PHI nodes at the target?  */
 710         make_edge (NULL, bb, pdom_bb, 0);
 711
 712         /* Third, transform this insn into an unconditional
 713            jump to the label for the immediate postdominator.  */
 714         lbl = find_block_label (pdom_bb);
 715         SET_SRC (PATTERN (insn)) = gen_rtx_LABEL_REF (VOIDmode, lbl);
 716         INSN_CODE (insn) = -1;
 717         JUMP_LABEL (insn) = lbl;
 718         LABEL_NUSES (lbl)++;
 719
 720         /* A barrier must follow any unconditional jump.  Barriers
 721            are not in basic blocks so this must occur after
 722            deleting the conditional jump.  */
 723         emit_barrier_after (insn);
 724       }
 725     else if (!JUMP_P (insn))
 726       delete_insn_bb (insn);
 727   });
 728
 729   /* Remove fake edges from the CFG.  */
 730   remove_fake_edges ();
 731
 732   /* Find any blocks with no successors and ensure they are followed
 733      by a BARRIER.  delete_insn has the nasty habit of deleting barriers
 734      when deleting insns.  */
 735   for (i = 0; i < n_basic_blocks; i++)
 736     {
 737       basic_block bb = BASIC_BLOCK (i);
 738
 739       if (bb->succ == NULL)
 740         {
 741           rtx next = NEXT_INSN (bb->end);
 742
 743           if (!next || GET_CODE (next) != BARRIER)
 744             emit_barrier_after (bb->end);
 745         }
 746     }
 747   /* Release allocated memory.  */
 748   for (insn = get_insns (); insn != NULL_RTX; insn = NEXT_INSN (insn))
 749     RESURRECT_INSN (insn);
 750   if (VARRAY_ACTIVE_SIZE (unprocessed_instructions) != 0)
 751     abort ();
 752   VARRAY_FREE (unprocessed_instructions);
 753   control_dependent_block_to_edge_map_free (cdbte);
 754   free ((PTR) pdom);
 755   free_edge_list (el);
 756 }