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 #include "coretypes.h"
  73 #include "tm.h"
  74
  75 #include "rtl.h"
  76 #include "hard-reg-set.h"
  77 #include "basic-block.h"
  78 #include "ssa.h"
  79 #include "insn-config.h"
  80 #include "recog.h"
  81 #include "output.h"
  82
  83 \f
  84 /* A map from blocks to the edges on which they are control dependent.  */
  85 typedef struct {
  86   /* An dynamically allocated array.  The Nth element corresponds to
  87      the block with index N + 2.  The Ith bit in the bitmap is set if
  88      that block is dependent on the Ith edge.  */
  89   bitmap *data;
  90   /* The number of elements in the array.  */
  91   int length;
  92 } control_dependent_block_to_edge_map_s, *control_dependent_block_to_edge_map;
  93
  94 /* Local function prototypes.  */
  95 static control_dependent_block_to_edge_map control_dependent_block_to_edge_map_create
  96   PARAMS((size_t num_basic_blocks));
  97 static void set_control_dependent_block_to_edge_map_bit
  98   PARAMS ((control_dependent_block_to_edge_map c, basic_block bb,
  99            int edge_index));
 100 static void control_dependent_block_to_edge_map_free
 101   PARAMS ((control_dependent_block_to_edge_map c));
 102 static void find_all_control_dependences
 103   PARAMS ((struct edge_list *el, dominance_info pdom,
 104            control_dependent_block_to_edge_map cdbte));
 105 static void find_control_dependence
 106   PARAMS ((struct edge_list *el, int edge_index, dominance_info pdom,
 107            control_dependent_block_to_edge_map cdbte));
 108 static basic_block find_pdom
 109   PARAMS ((dominance_info pdom, basic_block block));
 110 static int inherently_necessary_register_1
 111   PARAMS ((rtx *current_rtx, void *data));
 112 static int inherently_necessary_register
 113   PARAMS ((rtx current_rtx));
 114 static int find_inherently_necessary
 115   PARAMS ((rtx current_rtx));
 116 static int propagate_necessity_through_operand
 117   PARAMS ((rtx *current_rtx, void *data));
 118 static void note_inherently_necessary_set
 119   PARAMS ((rtx, rtx, void *));
 120 \f
 121 /* Unnecessary insns are indicated using insns' in_struct bit.  */
 122
 123 /* Indicate INSN is dead-code; returns nothing.  */
 124 #define KILL_INSN(INSN)         INSN_DEAD_CODE_P(INSN) = 1
 125 /* Indicate INSN is necessary, i.e., not dead-code; returns nothing.  */
 126 #define RESURRECT_INSN(INSN)    INSN_DEAD_CODE_P(INSN) = 0
 127 /* Return nonzero if INSN is unnecessary.  */
 128 #define UNNECESSARY_P(INSN)     INSN_DEAD_CODE_P(INSN)
 129 static void mark_all_insn_unnecessary
 130   PARAMS ((void));
 131 /* Execute CODE with free variable INSN for all unnecessary insns in
 132    an unspecified order, producing no output.  */
 133 #define EXECUTE_IF_UNNECESSARY(INSN, CODE)      \
 134 {                                                               \
 135   rtx INSN;                                                     \
 136                                                                 \
 137   for (INSN = get_insns (); INSN != NULL_RTX; INSN = NEXT_INSN (INSN))  \
 138     if (INSN_P (insn) && INSN_DEAD_CODE_P (INSN))               \
 139       {                                                         \
 140         CODE;                                                   \
 141       }                                                         \
 142 }
 143
 144 /* Find the label beginning block BB.  */
 145 static rtx find_block_label
 146   PARAMS ((basic_block bb));
 147 /* Remove INSN, updating its basic block structure.  */
 148 static void delete_insn_bb
 149   PARAMS ((rtx insn));
 150 \f
 151 /* Recording which blocks are control dependent on which edges.  We
 152    expect each block to be control dependent on very few edges so we
 153    use a bitmap for each block recording its edges.  An array holds
 154    the bitmap.  Its position 0 entry holds the bitmap for block
 155    INVALID_BLOCK+1 so that all blocks, including the entry and exit
 156    blocks can participate in the data structure.  */
 157
 158 /* Create a control_dependent_block_to_edge_map, given the number
 159    NUM_BASIC_BLOCKS of non-entry, non-exit basic blocks, e.g.,
 160    n_basic_blocks.  This memory must be released using
 161    control_dependent_block_to_edge_map_free ().  */
 162
 163 static control_dependent_block_to_edge_map
 164 control_dependent_block_to_edge_map_create (num_basic_blocks)
 165      size_t num_basic_blocks;
 166 {
 167   int i;
 168   control_dependent_block_to_edge_map c
 169     = xmalloc (sizeof (control_dependent_block_to_edge_map_s));
 170   c->length = num_basic_blocks - (INVALID_BLOCK+1);
 171   c->data = xmalloc ((size_t) c->length*sizeof (bitmap));
 172   for (i = 0; i < c->length; ++i)
 173     c->data[i] = BITMAP_XMALLOC ();
 174
 175   return c;
 176 }
 177
 178 /* Indicate block BB is control dependent on an edge with index
 179    EDGE_INDEX in the mapping C of blocks to edges on which they are
 180    control-dependent.  */
 181
 182 static void
 183 set_control_dependent_block_to_edge_map_bit (c, bb, edge_index)
 184      control_dependent_block_to_edge_map c;
 185      basic_block bb;
 186      int edge_index;
 187 {
 188   if (bb->index - (INVALID_BLOCK+1) >= c->length)
 189     abort ();
 190
 191   bitmap_set_bit (c->data[bb->index - (INVALID_BLOCK+1)],
 192                   edge_index);
 193 }
 194
 195 /* Execute CODE for each edge (given number EDGE_NUMBER within the
 196    CODE) for which the block containing INSN is control dependent,
 197    returning no output.  CDBTE is the mapping of blocks to edges on
 198    which they are control-dependent.  */
 199
 200 #define EXECUTE_IF_CONTROL_DEPENDENT(CDBTE, INSN, EDGE_NUMBER, CODE) \
 201         EXECUTE_IF_SET_IN_BITMAP \
 202           (CDBTE->data[BLOCK_NUM (INSN) - (INVALID_BLOCK+1)], 0, \
 203           EDGE_NUMBER, CODE)
 204
 205 /* Destroy a control_dependent_block_to_edge_map C.  */
 206
 207 static void
 208 control_dependent_block_to_edge_map_free (c)
 209      control_dependent_block_to_edge_map c;
 210 {
 211   int i;
 212   for (i = 0; i < c->length; ++i)
 213     BITMAP_XFREE (c->data[i]);
 214   free ((PTR) c);
 215 }
 216
 217 /* Record all blocks' control dependences on all edges in the edge
 218    list EL, ala Morgan, Section 3.6.  The mapping PDOM of blocks to
 219    their postdominators are used, and results are stored in CDBTE,
 220    which should be empty.  */
 221
 222 static void
 223 find_all_control_dependences (el, pdom, cdbte)
 224    struct edge_list *el;
 225    dominance_info pdom;
 226    control_dependent_block_to_edge_map cdbte;
 227 {
 228   int i;
 229
 230   for (i = 0; i < NUM_EDGES (el); ++i)
 231     find_control_dependence (el, i, pdom, cdbte);
 232 }
 233
 234 /* Determine all blocks' control dependences on the given edge with
 235    edge_list EL index EDGE_INDEX, ala Morgan, Section 3.6.  The
 236    mapping PDOM of blocks to their postdominators are used, and
 237    results are stored in CDBTE, which is assumed to be initialized
 238    with zeros in each (block b', edge) position.  */
 239
 240 static void
 241 find_control_dependence (el, edge_index, pdom, cdbte)
 242    struct edge_list *el;
 243    int edge_index;
 244    dominance_info pdom;
 245    control_dependent_block_to_edge_map cdbte;
 246 {
 247   basic_block current_block;
 248   basic_block ending_block;
 249
 250   if (INDEX_EDGE_PRED_BB (el, edge_index) == EXIT_BLOCK_PTR)
 251     abort ();
 252   ending_block =
 253     (INDEX_EDGE_PRED_BB (el, edge_index) == ENTRY_BLOCK_PTR)
 254     ? ENTRY_BLOCK_PTR->next_bb
 255     : find_pdom (pdom, INDEX_EDGE_PRED_BB (el, edge_index));
 256
 257   for (current_block = INDEX_EDGE_SUCC_BB (el, edge_index);
 258        current_block != ending_block && current_block != EXIT_BLOCK_PTR;
 259        current_block = find_pdom (pdom, current_block))
 260     {
 261       set_control_dependent_block_to_edge_map_bit (cdbte,
 262                                                    current_block,
 263                                                    edge_index);
 264     }
 265 }
 266 \f
 267 /* Find the immediate postdominator PDOM of the specified basic block
 268    BLOCK.  This function is necessary because some blocks have
 269    negative numbers.  */
 270
 271 static basic_block
 272 find_pdom (pdom, block)
 273      dominance_info pdom;
 274      basic_block block;
 275 {
 276   if (!block)
 277     abort ();
 278   if (block->index == INVALID_BLOCK)
 279     abort ();
 280
 281   if (block == ENTRY_BLOCK_PTR)
 282     return ENTRY_BLOCK_PTR->next_bb;
 283   else if (block == EXIT_BLOCK_PTR)
 284     return EXIT_BLOCK_PTR;
 285   else
 286     {
 287       basic_block bb = get_immediate_dominator (pdom, block);
 288       if (!bb)
 289         return EXIT_BLOCK_PTR;
 290       return bb;
 291     }
 292 }
 293
 294 /* Determine if the given CURRENT_RTX uses a hard register not
 295    converted to SSA.  Returns nonzero only if it uses such a hard
 296    register.  DATA is not used.
 297
 298    The program counter (PC) is not considered inherently necessary
 299    since code should be position-independent and thus not depend on
 300    particular PC values.  */
 301
 302 static int
 303 inherently_necessary_register_1 (current_rtx, data)
 304      rtx *current_rtx;
 305      void *data ATTRIBUTE_UNUSED;
 306 {
 307   rtx x = *current_rtx;
 308
 309   if (x == NULL_RTX)
 310     return 0;
 311   switch (GET_CODE (x))
 312     {
 313     case CLOBBER:
 314       /* Do not traverse the rest of the clobber.  */
 315       return -1;
 316       break;
 317     case PC:
 318       return 0;
 319       break;
 320     case REG:
 321       if (CONVERT_REGISTER_TO_SSA_P (REGNO (x)) || x == pc_rtx)
 322         return 0;
 323       else
 324         return !0;
 325       break;
 326     default:
 327       return 0;
 328       break;
 329     }
 330 }
 331
 332 /* Return nonzero if the insn CURRENT_RTX is inherently necessary.  */
 333
 334 static int
 335 inherently_necessary_register (current_rtx)
 336      rtx current_rtx;
 337 {
 338   return for_each_rtx (&current_rtx,
 339                        &inherently_necessary_register_1, NULL);
 340 }
 341
 342
 343 /* Called via note_stores for each store in an insn.  Note whether
 344    or not a particular store is inherently necessary.  Store a
 345    nonzero value in inherently_necessary_p if such a store is found.  */
 346
 347 static void
 348 note_inherently_necessary_set (dest, set, data)
 349      rtx set ATTRIBUTE_UNUSED;
 350      rtx dest;
 351      void *data;
 352 {
 353   int *inherently_necessary_set_p = (int *) data;
 354
 355   while (GET_CODE (dest) == SUBREG
 356          || GET_CODE (dest) == STRICT_LOW_PART
 357          || GET_CODE (dest) == ZERO_EXTRACT
 358          || GET_CODE (dest) == SIGN_EXTRACT)
 359     dest = XEXP (dest, 0);
 360
 361   if (GET_CODE (dest) == MEM
 362       || GET_CODE (dest) == UNSPEC
 363       || GET_CODE (dest) == UNSPEC_VOLATILE)
 364     *inherently_necessary_set_p = 1;
 365 }
 366
 367 /* Mark X as inherently necessary if appropriate.  For example,
 368    function calls and storing values into memory are inherently
 369    necessary.  This function is to be used with for_each_rtx ().
 370    Return nonzero iff inherently necessary.  */
 371
 372 static int
 373 find_inherently_necessary (x)
 374      rtx x;
 375 {
 376   if (x == NULL_RTX)
 377     return 0;
 378   else if (inherently_necessary_register (x))
 379     return !0;
 380   else
 381     switch (GET_CODE (x))
 382       {
 383       case CALL_INSN:
 384       case BARRIER:
 385       case PREFETCH:
 386         return !0;
 387       case CODE_LABEL:
 388       case NOTE:
 389         return 0;
 390       case JUMP_INSN:
 391         return JUMP_TABLE_DATA_P (x) || computed_jump_p (x) != 0;
 392       case INSN:
 393         {
 394           int inherently_necessary_set = 0;
 395           note_stores (PATTERN (x),
 396                        note_inherently_necessary_set,
 397                        &inherently_necessary_set);
 398
 399           /* If we found an inherently necessary set or an asm
 400              instruction, then we consider this insn inherently
 401              necessary.  */
 402           return (inherently_necessary_set
 403                   || GET_CODE (PATTERN (x)) == ASM_INPUT
 404                   || asm_noperands (PATTERN (x)) >= 0);
 405         }
 406       default:
 407         /* Found an impossible insn type.  */
 408         abort ();
 409         break;
 410       }
 411 }
 412
 413 /* Propagate necessity through REG and SUBREG operands of CURRENT_RTX.
 414    This function is called with for_each_rtx () on necessary
 415    instructions.  The DATA must be a varray of unprocessed
 416    instructions.  */
 417
 418 static int
 419 propagate_necessity_through_operand (current_rtx, data)
 420      rtx *current_rtx;
 421      void *data;
 422 {
 423   rtx x = *current_rtx;
 424   varray_type *unprocessed_instructions = (varray_type *) data;
 425
 426   if (x == NULL_RTX)
 427     return 0;
 428   switch ( GET_CODE (x))
 429     {
 430     case REG:
 431       if (CONVERT_REGISTER_TO_SSA_P (REGNO (x)))
 432         {
 433           rtx insn = VARRAY_RTX (ssa_definition, REGNO (x));
 434           if (insn != NULL_RTX && UNNECESSARY_P (insn))
 435             {
 436               RESURRECT_INSN (insn);
 437               VARRAY_PUSH_RTX (*unprocessed_instructions, insn);
 438             }
 439         }
 440       return 0;
 441
 442     default:
 443       return 0;
 444     }
 445 }
 446
 447 /* Indicate all insns initially assumed to be unnecessary.  */
 448
 449 static void
 450 mark_all_insn_unnecessary ()
 451 {
 452   rtx insn;
 453   for (insn = get_insns (); insn != NULL_RTX; insn = NEXT_INSN (insn)) {
 454     if (INSN_P (insn))
 455       KILL_INSN (insn);
 456   }
 457
 458 }
 459
 460 /* Find the label beginning block BB, adding one if necessary.  */
 461
 462 static rtx
 463 find_block_label (bb)
 464      basic_block bb;
 465 {
 466   rtx insn = bb->head;
 467   if (LABEL_P (insn))
 468     return insn;
 469   else
 470     {
 471       rtx new_label = emit_label_before (gen_label_rtx (), insn);
 472       if (insn == bb->head)
 473         bb->head = new_label;
 474       return new_label;
 475     }
 476 }
 477
 478 /* Remove INSN, updating its basic block structure.  */
 479
 480 static void
 481 delete_insn_bb (insn)
 482      rtx insn;
 483 {
 484   if (!insn)
 485     abort ();
 486
 487   /* Do not actually delete anything that is not an INSN.
 488
 489      We can get here because we only consider INSNs as
 490      potentially necessary.  We leave it to later passes
 491      to remove unnecessary notes, unused labels, etc.  */
 492   if (! INSN_P (insn))
 493     return;
 494
 495   delete_insn (insn);
 496 }
 497 \f
 498 /* Perform the dead-code elimination.  */
 499
 500 void
 501 ssa_eliminate_dead_code ()
 502 {
 503   rtx insn;
 504   basic_block bb;
 505   /* Necessary instructions with operands to explore.  */
 506   varray_type unprocessed_instructions;
 507   /* Map element (b,e) is nonzero if the block is control dependent on
 508      edge.  "cdbte" abbreviates control dependent block to edge.  */
 509   control_dependent_block_to_edge_map cdbte;
 510  /* Element I is the immediate postdominator of block I.  */
 511   dominance_info pdom;
 512   struct edge_list *el;
 513
 514   /* Initialize the data structures.  */
 515   mark_all_insn_unnecessary ();
 516   VARRAY_RTX_INIT (unprocessed_instructions, 64,
 517                    "unprocessed instructions");
 518   cdbte = control_dependent_block_to_edge_map_create (last_basic_block);
 519
 520   /* Prepare for use of BLOCK_NUM ().  */
 521   connect_infinite_loops_to_exit ();
 522
 523   /* Compute control dependence.  */
 524   pdom = calculate_dominance_info (CDI_POST_DOMINATORS);
 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) && INSN_P (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     if (INSN_P (insn))
 735       RESURRECT_INSN (insn);
 736   }
 737
 738   if (VARRAY_ACTIVE_SIZE (unprocessed_instructions) != 0)
 739     abort ();
 740   control_dependent_block_to_edge_map_free (cdbte);
 741   free ((PTR) pdom);
 742   free_edge_list (el);
 743 }