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   if (!insn)
 472     abort ();
 473
 474   /* Do not actually delete anything that is not an INSN.
 475
 476      We can get here because we only consider INSNs as
 477      potentially necessary.  We leave it to later passes
 478      to remove unnecessary notes, unused labels, etc.  */
 479   if (! INSN_P (insn))
 480     return;
 481
 482   delete_insn (insn);
 483 }
 484 \f
 485 /* Perform the dead-code elimination.  */
 486
 487 void
 488 ssa_eliminate_dead_code ()
 489 {
 490   int i;
 491   rtx insn;
 492   /* Necessary instructions with operands to explore.  */
 493   varray_type unprocessed_instructions;
 494   /* Map element (b,e) is nonzero if the block is control dependent on
 495      edge.  "cdbte" abbreviates control dependent block to edge.  */
 496   control_dependent_block_to_edge_map cdbte;
 497  /* Element I is the immediate postdominator of block I.  */
 498   int *pdom;
 499   struct edge_list *el;
 500
 501   int max_insn_uid = get_max_uid ();
 502
 503   /* Initialize the data structures.  */
 504   mark_all_insn_unnecessary ();
 505   VARRAY_RTX_INIT (unprocessed_instructions, 64,
 506                    "unprocessed instructions");
 507   cdbte = control_dependent_block_to_edge_map_create (n_basic_blocks);
 508
 509   /* Prepare for use of BLOCK_NUM ().  */
 510   connect_infinite_loops_to_exit ();
 511    /* Be careful not to clear the added edges.  */
 512   compute_bb_for_insn (max_insn_uid);
 513
 514   /* Compute control dependence.  */
 515   pdom = (int *) xmalloc (n_basic_blocks * sizeof (int));
 516   for (i = 0; i < n_basic_blocks; ++i)
 517     pdom[i] = INVALID_BLOCK;
 518   calculate_dominance_info (pdom, NULL, CDI_POST_DOMINATORS);
 519   /* Assume there is a path from each node to the exit block.  */
 520   for (i = 0; i < n_basic_blocks; ++i)
 521     if (pdom[i] == INVALID_BLOCK)
 522       pdom[i] = EXIT_BLOCK;
 523   el = create_edge_list();
 524   find_all_control_dependences (el, pdom, cdbte);
 525
 526   /* Find inherently necessary instructions.  */
 527   for (insn = get_insns (); insn != NULL_RTX; insn = NEXT_INSN (insn))
 528     if (find_inherently_necessary (insn))
 529       {
 530         RESURRECT_INSN (insn);
 531         VARRAY_PUSH_RTX (unprocessed_instructions, insn);
 532       }
 533
 534   /* Propagate necessity using the operands of necessary instructions.  */
 535   while (VARRAY_ACTIVE_SIZE (unprocessed_instructions) > 0)
 536     {
 537       rtx current_instruction;
 538       int edge_number;
 539
 540       current_instruction = VARRAY_TOP_RTX (unprocessed_instructions);
 541       VARRAY_POP (unprocessed_instructions);
 542
 543       /* Make corresponding control dependent edges necessary.  */
 544       /* Assume the only JUMP_INSN is the block's last insn.  It appears
 545          that the last instruction of the program need not be a
 546          JUMP_INSN.  */
 547
 548       if (INSN_P (current_instruction)
 549           && !JUMP_TABLE_DATA_P (current_instruction))
 550         {
 551           /* Notes and labels contain no interesting operands.  */
 552           EXECUTE_IF_CONTROL_DEPENDENT
 553             (cdbte, current_instruction, edge_number,
 554             {
 555               rtx jump_insn = (INDEX_EDGE_PRED_BB (el, edge_number))->end;
 556               if (GET_CODE (jump_insn) == JUMP_INSN
 557                   && UNNECESSARY_P (jump_insn))
 558                 {
 559                   RESURRECT_INSN (jump_insn);
 560                   VARRAY_PUSH_RTX (unprocessed_instructions, jump_insn);
 561                 }
 562             });
 563
 564           /* Propagate through the operands.  */
 565           for_each_rtx (&current_instruction,
 566                         &propagate_necessity_through_operand,
 567                         (PTR) &unprocessed_instructions);
 568
 569           /* PHI nodes are somewhat special in that each PHI alternative
 570              has data and control dependencies.  The data dependencies
 571              are handled via propagate_necessity_through_operand.  We
 572              handle the control dependency here.
 573
 574              We consider the control dependent edges leading to the
 575              predecessor block associated with each PHI alternative
 576              as necessary.  */
 577           if (PHI_NODE_P (current_instruction))
 578             {
 579               rtvec phi_vec = XVEC (SET_SRC (PATTERN (current_instruction)), 0);
 580               int num_elem = GET_NUM_ELEM (phi_vec);
 581               int v;
 582
 583               for (v = num_elem - 2; v >= 0; v -= 2)
 584                 {
 585                   basic_block bb;
 586
 587                   bb = BASIC_BLOCK (INTVAL (RTVEC_ELT (phi_vec, v + 1)));
 588                   EXECUTE_IF_CONTROL_DEPENDENT
 589                     (cdbte, bb->end, edge_number,
 590                     {
 591                       rtx jump_insn;
 592
 593                       jump_insn = (INDEX_EDGE_PRED_BB (el, edge_number))->end;
 594                       if (((GET_CODE (jump_insn) == JUMP_INSN))
 595                           && UNNECESSARY_P (jump_insn))
 596                         {
 597                           RESURRECT_INSN (jump_insn);
 598                           VARRAY_PUSH_RTX (unprocessed_instructions, jump_insn);
 599                         }
 600                     });
 601
 602                 }
 603             }
 604         }
 605     }
 606
 607   /* Remove the unnecessary instructions.  */
 608   EXECUTE_IF_UNNECESSARY (insn,
 609   {
 610     if (any_condjump_p (insn))
 611       {
 612         basic_block bb = BLOCK_FOR_INSN (insn);
 613         basic_block pdom_bb = find_pdom (pdom, bb);
 614         rtx lbl;
 615         edge e;
 616
 617         /* Egad.  The immediate post dominator is the exit block.  We
 618            would like to optimize this conditional jump to jump directly
 619            to the exit block.  That can be difficult as we may not have
 620            a suitable CODE_LABEL that allows us to fall unmolested into
 621            the exit block.
 622
 623            So, we just delete the conditional branch by turning it into
 624            a deleted note.   That is safe, but just not as optimal as
 625            it could be.  */
 626         if (pdom_bb == EXIT_BLOCK_PTR)
 627           {
 628             /* Since we're going to just delete the branch, we need
 629                look at all the edges and remove all those which are not
 630                a fallthru edge.  */
 631             e = bb->succ;
 632             while (e)
 633               {
 634                 edge temp = e;
 635
 636                 e = e->succ_next;
 637                 if ((temp->flags & EDGE_FALLTHRU) == 0)
 638                   {
 639                     /* We've found a non-fallthru edge, find any PHI nodes
 640                        at the target and clean them up.  */
 641                     if (temp->dest != EXIT_BLOCK_PTR)
 642                       {
 643                         rtx insn
 644                           = first_insn_after_basic_block_note (temp->dest);
 645
 646                         while (PHI_NODE_P (insn))
 647                           {
 648                             remove_phi_alternative (PATTERN (insn), temp->src);
 649                             insn = NEXT_INSN (insn);
 650                           }
 651                       }
 652
 653                     remove_edge (temp);
 654                   }
 655               }
 656
 657             /* Now "delete" the conditional jump.  */
 658             PUT_CODE (insn, NOTE);
 659             NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
 660             continue;
 661           }
 662
 663         /* We've found a conditional branch that is unnecessary.
 664
 665            First, remove all outgoing edges from this block, updating
 666            PHI nodes as appropriate.  */
 667         e = bb->succ;
 668         while (e)
 669           {
 670             edge temp = e;
 671
 672             e = e->succ_next;
 673
 674             if (temp->flags & EDGE_ABNORMAL)
 675               continue;
 676
 677             /* We found an edge that is not executable.  First simplify
 678                the PHI nodes in the target block.  */
 679             if (temp->dest != EXIT_BLOCK_PTR)
 680               {
 681                 rtx insn = first_insn_after_basic_block_note (temp->dest);
 682
 683                 while (PHI_NODE_P (insn))
 684                   {
 685                     remove_phi_alternative (PATTERN (insn), temp->src);
 686                     insn = NEXT_INSN (insn);
 687                   }
 688               }
 689
 690             remove_edge (temp);
 691           }
 692
 693         /* Create an edge from this block to the post dominator.
 694            What about the PHI nodes at the target?  */
 695         make_edge (bb, pdom_bb, 0);
 696
 697         /* Third, transform this insn into an unconditional
 698            jump to the label for the immediate postdominator.  */
 699         lbl = find_block_label (pdom_bb);
 700         SET_SRC (PATTERN (insn)) = gen_rtx_LABEL_REF (VOIDmode, lbl);
 701         INSN_CODE (insn) = -1;
 702         JUMP_LABEL (insn) = lbl;
 703         LABEL_NUSES (lbl)++;
 704
 705         /* A barrier must follow any unconditional jump.  Barriers
 706            are not in basic blocks so this must occur after
 707            deleting the conditional jump.  */
 708         emit_barrier_after (insn);
 709       }
 710     else if (!JUMP_P (insn))
 711       delete_insn_bb (insn);
 712   });
 713
 714   /* Remove fake edges from the CFG.  */
 715   remove_fake_edges ();
 716
 717   /* Find any blocks with no successors and ensure they are followed
 718      by a BARRIER.  delete_insn has the nasty habit of deleting barriers
 719      when deleting insns.  */
 720   for (i = 0; i < n_basic_blocks; i++)
 721     {
 722       basic_block bb = BASIC_BLOCK (i);
 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 }