gcc/ssa-dce.c

   1 /* Dead-code elimination pass for the GNU compiler.
   2    Copyright (C) 2000, 2001, 2002 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     ? ENTRY_BLOCK_PTR->next_bb
 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 ENTRY_BLOCK_PTR->next_bb;
 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       case PREFETCH:
 377         return !0;
 378       case CODE_LABEL:
 379       case NOTE:
 380         return 0;
 381       case JUMP_INSN:
 382         return JUMP_TABLE_DATA_P (x) || computed_jump_p (x) != 0;
 383       case INSN:
 384         {
 385           int inherently_necessary_set = 0;
 386           note_stores (PATTERN (x),
 387                        note_inherently_necessary_set,
 388                        &inherently_necessary_set);
 389
 390           /* If we found an inherently necessary set or an asm
 391              instruction, then we consider this insn inherently
 392              necessary.  */
 393           return (inherently_necessary_set
 394                   || GET_CODE (PATTERN (x)) == ASM_INPUT
 395                   || asm_noperands (PATTERN (x)) >= 0);
 396         }
 397       default:
 398         /* Found an impossible insn type.  */
 399         abort ();
 400         break;
 401       }
 402 }
 403
 404 /* Propagate necessity through REG and SUBREG operands of CURRENT_RTX.
 405    This function is called with for_each_rtx () on necessary
 406    instructions.  The DATA must be a varray of unprocessed
 407    instructions.  */
 408
 409 static int
 410 propagate_necessity_through_operand (current_rtx, data)
 411      rtx *current_rtx;
 412      void *data;
 413 {
 414   rtx x = *current_rtx;
 415   varray_type *unprocessed_instructions = (varray_type *) data;
 416
 417   if (x == NULL_RTX)
 418     return 0;
 419   switch ( GET_CODE (x))
 420     {
 421     case REG:
 422       if (CONVERT_REGISTER_TO_SSA_P (REGNO (x)))
 423         {
 424           rtx insn = VARRAY_RTX (ssa_definition, REGNO (x));
 425           if (insn != NULL_RTX && UNNECESSARY_P (insn))
 426             {
 427               RESURRECT_INSN (insn);
 428               VARRAY_PUSH_RTX (*unprocessed_instructions, insn);
 429             }
 430         }
 431       return 0;
 432
 433     default:
 434       return 0;
 435     }
 436 }
 437
 438 /* Indicate all insns initially assumed to be unnecessary.  */
 439
 440 static void
 441 mark_all_insn_unnecessary ()
 442 {
 443   rtx insn;
 444   for (insn = get_insns (); insn != NULL_RTX; insn = NEXT_INSN (insn))
 445     KILL_INSN (insn);
 446 }
 447
 448 /* Find the label beginning block BB, adding one if necessary.  */
 449
 450 static rtx
 451 find_block_label (bb)
 452      basic_block bb;
 453 {
 454   rtx insn = bb->head;
 455   if (LABEL_P (insn))
 456     return insn;
 457   else
 458     {
 459       rtx new_label = emit_label_before (gen_label_rtx (), insn);
 460       if (insn == bb->head)
 461         bb->head = new_label;
 462       return new_label;
 463     }
 464 }
 465
 466 /* Remove INSN, updating its basic block structure.  */
 467
 468 static void
 469 delete_insn_bb (insn)
 470      rtx insn;
 471 {
 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   delete_insn (insn);
 484 }
 485 \f
 486 /* Perform the dead-code elimination.  */
 487
 488 void
 489 ssa_eliminate_dead_code ()
 490 {
 491   int i;
 492   rtx insn;
 493   basic_block bb;
 494   /* Necessary instructions with operands to explore.  */
 495   varray_type unprocessed_instructions;
 496   /* Map element (b,e) is nonzero if the block is control dependent on
 497      edge.  "cdbte" abbreviates control dependent block to edge.  */
 498   control_dependent_block_to_edge_map cdbte;
 499  /* Element I is the immediate postdominator of block I.  */
 500   int *pdom;
 501   struct edge_list *el;
 502
 503   int max_insn_uid = get_max_uid ();
 504
 505   /* Initialize the data structures.  */
 506   mark_all_insn_unnecessary ();
 507   VARRAY_RTX_INIT (unprocessed_instructions, 64,
 508                    "unprocessed instructions");
 509   cdbte = control_dependent_block_to_edge_map_create (last_basic_block);
 510
 511   /* Prepare for use of BLOCK_NUM ().  */
 512   connect_infinite_loops_to_exit ();
 513    /* Be careful not to clear the added edges.  */
 514   compute_bb_for_insn (max_insn_uid);
 515
 516   /* Compute control dependence.  */
 517   pdom = (int *) xmalloc (last_basic_block * sizeof (int));
 518   for (i = 0; i < last_basic_block; ++i)
 519     pdom[i] = INVALID_BLOCK;
 520   calculate_dominance_info (pdom, NULL, CDI_POST_DOMINATORS);
 521   /* Assume there is a path from each node to the exit block.  */
 522   for (i = 0; i < last_basic_block; ++i)
 523     if (pdom[i] == INVALID_BLOCK)
 524       pdom[i] = EXIT_BLOCK;
 525   el = create_edge_list ();
 526   find_all_control_dependences (el, pdom, cdbte);
 527
 528   /* Find inherently necessary instructions.  */
 529   for (insn = get_insns (); insn != NULL_RTX; insn = NEXT_INSN (insn))
 530     if (find_inherently_necessary (insn))
 531       {
 532         RESURRECT_INSN (insn);
 533         VARRAY_PUSH_RTX (unprocessed_instructions, insn);
 534       }
 535
 536   /* Propagate necessity using the operands of necessary instructions.  */
 537   while (VARRAY_ACTIVE_SIZE (unprocessed_instructions) > 0)
 538     {
 539       rtx current_instruction;
 540       int edge_number;
 541
 542       current_instruction = VARRAY_TOP_RTX (unprocessed_instructions);
 543       VARRAY_POP (unprocessed_instructions);
 544
 545       /* Make corresponding control dependent edges necessary.  */
 546       /* Assume the only JUMP_INSN is the block's last insn.  It appears
 547          that the last instruction of the program need not be a
 548          JUMP_INSN.  */
 549
 550       if (INSN_P (current_instruction)
 551           && !JUMP_TABLE_DATA_P (current_instruction))
 552         {
 553           /* Notes and labels contain no interesting operands.  */
 554           EXECUTE_IF_CONTROL_DEPENDENT
 555             (cdbte, current_instruction, edge_number,
 556             {
 557               rtx jump_insn = (INDEX_EDGE_PRED_BB (el, edge_number))->end;
 558               if (GET_CODE (jump_insn) == JUMP_INSN
 559                   && UNNECESSARY_P (jump_insn))
 560                 {
 561                   RESURRECT_INSN (jump_insn);
 562                   VARRAY_PUSH_RTX (unprocessed_instructions, jump_insn);
 563                 }
 564             });
 565
 566           /* Propagate through the operands.  */
 567           for_each_rtx (&current_instruction,
 568                         &propagate_necessity_through_operand,
 569                         (PTR) &unprocessed_instructions);
 570
 571           /* PHI nodes are somewhat special in that each PHI alternative
 572              has data and control dependencies.  The data dependencies
 573              are handled via propagate_necessity_through_operand.  We
 574              handle the control dependency here.
 575
 576              We consider the control dependent edges leading to the
 577              predecessor block associated with each PHI alternative
 578              as necessary.  */
 579           if (PHI_NODE_P (current_instruction))
 580             {
 581               rtvec phi_vec = XVEC (SET_SRC (PATTERN (current_instruction)), 0);
 582               int num_elem = GET_NUM_ELEM (phi_vec);
 583               int v;
 584
 585               for (v = num_elem - 2; v >= 0; v -= 2)
 586                 {
 587                   basic_block bb;
 588
 589                   bb = BASIC_BLOCK (INTVAL (RTVEC_ELT (phi_vec, v + 1)));
 590                   EXECUTE_IF_CONTROL_DEPENDENT
 591                     (cdbte, bb->end, edge_number,
 592                     {
 593                       rtx jump_insn;
 594
 595                       jump_insn = (INDEX_EDGE_PRED_BB (el, edge_number))->end;
 596                       if (((GET_CODE (jump_insn) == JUMP_INSN))
 597                           && UNNECESSARY_P (jump_insn))
 598                         {
 599                           RESURRECT_INSN (jump_insn);
 600                           VARRAY_PUSH_RTX (unprocessed_instructions, jump_insn);
 601                         }
 602                     });
 603
 604                 }
 605             }
 606         }
 607     }
 608
 609   /* Remove the unnecessary instructions.  */
 610   EXECUTE_IF_UNNECESSARY (insn,
 611   {
 612     if (any_condjump_p (insn))
 613       {
 614         basic_block bb = BLOCK_FOR_INSN (insn);
 615         basic_block pdom_bb = find_pdom (pdom, bb);
 616         rtx lbl;
 617         edge e;
 618
 619         /* Egad.  The immediate post dominator is the exit block.  We
 620            would like to optimize this conditional jump to jump directly
 621            to the exit block.  That can be difficult as we may not have
 622            a suitable CODE_LABEL that allows us to fall unmolested into
 623            the exit block.
 624
 625            So, we just delete the conditional branch by turning it into
 626            a deleted note.   That is safe, but just not as optimal as
 627            it could be.  */
 628         if (pdom_bb == EXIT_BLOCK_PTR)
 629           {
 630             /* Since we're going to just delete the branch, we need
 631                look at all the edges and remove all those which are not
 632                a fallthru edge.  */
 633             e = bb->succ;
 634             while (e)
 635               {
 636                 edge temp = e;
 637
 638                 e = e->succ_next;
 639                 if ((temp->flags & EDGE_FALLTHRU) == 0)
 640                   {
 641                     /* We've found a non-fallthru edge, find any PHI nodes
 642                        at the target and clean them up.  */
 643                     if (temp->dest != EXIT_BLOCK_PTR)
 644                       {
 645                         rtx insn
 646                           = first_insn_after_basic_block_note (temp->dest);
 647
 648                         while (PHI_NODE_P (insn))
 649                           {
 650                             remove_phi_alternative (PATTERN (insn), temp->src);
 651                             insn = NEXT_INSN (insn);
 652                           }
 653                       }
 654
 655                     remove_edge (temp);
 656                   }
 657               }
 658
 659             /* Now "delete" the conditional jump.  */
 660             PUT_CODE (insn, NOTE);
 661             NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
 662             continue;
 663           }
 664
 665         /* We've found a conditional branch that is unnecessary.
 666
 667            First, remove all outgoing edges from this block, updating
 668            PHI nodes as appropriate.  */
 669         e = bb->succ;
 670         while (e)
 671           {
 672             edge temp = e;
 673
 674             e = e->succ_next;
 675
 676             if (temp->flags & EDGE_ABNORMAL)
 677               continue;
 678
 679             /* We found an edge that is not executable.  First simplify
 680                the PHI nodes in the target block.  */
 681             if (temp->dest != EXIT_BLOCK_PTR)
 682               {
 683                 rtx insn = first_insn_after_basic_block_note (temp->dest);
 684
 685                 while (PHI_NODE_P (insn))
 686                   {
 687                     remove_phi_alternative (PATTERN (insn), temp->src);
 688                     insn = NEXT_INSN (insn);
 689                   }
 690               }
 691
 692             remove_edge (temp);
 693           }
 694
 695         /* Create an edge from this block to the post dominator.
 696            What about the PHI nodes at the target?  */
 697         make_edge (bb, pdom_bb, 0);
 698
 699         /* Third, transform this insn into an unconditional
 700            jump to the label for the immediate postdominator.  */
 701         lbl = find_block_label (pdom_bb);
 702         SET_SRC (PATTERN (insn)) = gen_rtx_LABEL_REF (VOIDmode, lbl);
 703         INSN_CODE (insn) = -1;
 704         JUMP_LABEL (insn) = lbl;
 705         LABEL_NUSES (lbl)++;
 706
 707         /* A barrier must follow any unconditional jump.  Barriers
 708            are not in basic blocks so this must occur after
 709            deleting the conditional jump.  */
 710         emit_barrier_after (insn);
 711       }
 712     else if (!JUMP_P (insn))
 713       delete_insn_bb (insn);
 714   });
 715
 716   /* Remove fake edges from the CFG.  */
 717   remove_fake_edges ();
 718
 719   /* Find any blocks with no successors and ensure they are followed
 720      by a BARRIER.  delete_insn has the nasty habit of deleting barriers
 721      when deleting insns.  */
 722   FOR_EACH_BB (bb)
 723     {
 724       if (bb->succ == NULL)
 725         {
 726           rtx next = NEXT_INSN (bb->end);
 727
 728           if (!next || GET_CODE (next) != BARRIER)
 729             emit_barrier_after (bb->end);
 730         }
 731     }
 732   /* Release allocated memory.  */
 733   for (insn = get_insns (); insn != NULL_RTX; insn = NEXT_INSN (insn))
 734     RESURRECT_INSN (insn);
 735   if (VARRAY_ACTIVE_SIZE (unprocessed_instructions) != 0)
 736     abort ();
 737   VARRAY_FREE (unprocessed_instructions);
 738   control_dependent_block_to_edge_map_free (cdbte);
 739   free ((PTR) pdom);
 740   free_edge_list (el);
 741 }