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_DEAD_CODE_P (INSN)) {                              \
 139       CODE;                                                     \
 140     }                                                           \
 141 }
 142 /* Find the label beginning block BB.  */
 143 static rtx find_block_label
 144   PARAMS ((basic_block bb));
 145 /* Remove INSN, updating its basic block structure.  */
 146 static void delete_insn_bb
 147   PARAMS ((rtx insn));
 148 \f
 149 /* Recording which blocks are control dependent on which edges.  We
 150    expect each block to be control dependent on very few edges so we
 151    use a bitmap for each block recording its edges.  An array holds
 152    the bitmap.  Its position 0 entry holds the bitmap for block
 153    INVALID_BLOCK+1 so that all blocks, including the entry and exit
 154    blocks can participate in the data structure.  */
 155
 156 /* Create a control_dependent_block_to_edge_map, given the number
 157    NUM_BASIC_BLOCKS of non-entry, non-exit basic blocks, e.g.,
 158    n_basic_blocks.  This memory must be released using
 159    control_dependent_block_to_edge_map_free ().  */
 160
 161 static control_dependent_block_to_edge_map
 162 control_dependent_block_to_edge_map_create (num_basic_blocks)
 163      size_t num_basic_blocks;
 164 {
 165   int i;
 166   control_dependent_block_to_edge_map c
 167     = xmalloc (sizeof (control_dependent_block_to_edge_map_s));
 168   c->length = num_basic_blocks - (INVALID_BLOCK+1);
 169   c->data = xmalloc ((size_t) c->length*sizeof (bitmap));
 170   for (i = 0; i < c->length; ++i)
 171     c->data[i] = BITMAP_XMALLOC ();
 172
 173   return c;
 174 }
 175
 176 /* Indicate block BB is control dependent on an edge with index
 177    EDGE_INDEX in the mapping C of blocks to edges on which they are
 178    control-dependent.  */
 179
 180 static void
 181 set_control_dependent_block_to_edge_map_bit (c, bb, edge_index)
 182      control_dependent_block_to_edge_map c;
 183      basic_block bb;
 184      int edge_index;
 185 {
 186   if (bb->index - (INVALID_BLOCK+1) >= c->length)
 187     abort ();
 188
 189   bitmap_set_bit (c->data[bb->index - (INVALID_BLOCK+1)],
 190                   edge_index);
 191 }
 192
 193 /* Execute CODE for each edge (given number EDGE_NUMBER within the
 194    CODE) for which the block containing INSN is control dependent,
 195    returning no output.  CDBTE is the mapping of blocks to edges on
 196    which they are control-dependent.  */
 197
 198 #define EXECUTE_IF_CONTROL_DEPENDENT(CDBTE, INSN, EDGE_NUMBER, CODE) \
 199         EXECUTE_IF_SET_IN_BITMAP \
 200           (CDBTE->data[BLOCK_NUM (INSN) - (INVALID_BLOCK+1)], 0, \
 201           EDGE_NUMBER, CODE)
 202
 203 /* Destroy a control_dependent_block_to_edge_map C.  */
 204
 205 static void
 206 control_dependent_block_to_edge_map_free (c)
 207      control_dependent_block_to_edge_map c;
 208 {
 209   int i;
 210   for (i = 0; i < c->length; ++i)
 211     BITMAP_XFREE (c->data[i]);
 212   free ((PTR) c);
 213 }
 214
 215 /* Record all blocks' control dependences on all edges in the edge
 216    list EL, ala Morgan, Section 3.6.  The mapping PDOM of blocks to
 217    their postdominators are used, and results are stored in CDBTE,
 218    which should be empty.  */
 219
 220 static void
 221 find_all_control_dependences (el, pdom, cdbte)
 222    struct edge_list *el;
 223    dominance_info pdom;
 224    control_dependent_block_to_edge_map cdbte;
 225 {
 226   int i;
 227
 228   for (i = 0; i < NUM_EDGES (el); ++i)
 229     find_control_dependence (el, i, pdom, cdbte);
 230 }
 231
 232 /* Determine all blocks' control dependences on the given edge with
 233    edge_list EL index EDGE_INDEX, ala Morgan, Section 3.6.  The
 234    mapping PDOM of blocks to their postdominators are used, and
 235    results are stored in CDBTE, which is assumed to be initialized
 236    with zeros in each (block b', edge) position.  */
 237
 238 static void
 239 find_control_dependence (el, edge_index, pdom, cdbte)
 240    struct edge_list *el;
 241    int edge_index;
 242    dominance_info pdom;
 243    control_dependent_block_to_edge_map cdbte;
 244 {
 245   basic_block current_block;
 246   basic_block ending_block;
 247
 248   if (INDEX_EDGE_PRED_BB (el, edge_index) == EXIT_BLOCK_PTR)
 249     abort ();
 250   ending_block =
 251     (INDEX_EDGE_PRED_BB (el, edge_index) == ENTRY_BLOCK_PTR)
 252     ? ENTRY_BLOCK_PTR->next_bb
 253     : find_pdom (pdom, INDEX_EDGE_PRED_BB (el, edge_index));
 254
 255   for (current_block = INDEX_EDGE_SUCC_BB (el, edge_index);
 256        current_block != ending_block && current_block != EXIT_BLOCK_PTR;
 257        current_block = find_pdom (pdom, current_block))
 258     {
 259       set_control_dependent_block_to_edge_map_bit (cdbte,
 260                                                    current_block,
 261                                                    edge_index);
 262     }
 263 }
 264 \f
 265 /* Find the immediate postdominator PDOM of the specified basic block
 266    BLOCK.  This function is necessary because some blocks have
 267    negative numbers.  */
 268
 269 static basic_block
 270 find_pdom (pdom, block)
 271      dominance_info pdom;
 272      basic_block block;
 273 {
 274   if (!block)
 275     abort ();
 276   if (block->index == INVALID_BLOCK)
 277     abort ();
 278
 279   if (block == ENTRY_BLOCK_PTR)
 280     return ENTRY_BLOCK_PTR->next_bb;
 281   else if (block == EXIT_BLOCK_PTR)
 282     return EXIT_BLOCK_PTR;
 283   else
 284     {
 285       basic_block bb = get_immediate_dominator (pdom, block);
 286       if (!bb)
 287         return EXIT_BLOCK_PTR;
 288       return bb;
 289     }
 290 }
 291
 292 /* Determine if the given CURRENT_RTX uses a hard register not
 293    converted to SSA.  Returns nonzero only if it uses such a hard
 294    register.  DATA is not used.
 295
 296    The program counter (PC) is not considered inherently necessary
 297    since code should be position-independent and thus not depend on
 298    particular PC values.  */
 299
 300 static int
 301 inherently_necessary_register_1 (current_rtx, data)
 302      rtx *current_rtx;
 303      void *data ATTRIBUTE_UNUSED;
 304 {
 305   rtx x = *current_rtx;
 306
 307   if (x == NULL_RTX)
 308     return 0;
 309   switch (GET_CODE (x))
 310     {
 311     case CLOBBER:
 312       /* Do not traverse the rest of the clobber.  */
 313       return -1;
 314       break;
 315     case PC:
 316       return 0;
 317       break;
 318     case REG:
 319       if (CONVERT_REGISTER_TO_SSA_P (REGNO (x)) || x == pc_rtx)
 320         return 0;
 321       else
 322         return !0;
 323       break;
 324     default:
 325       return 0;
 326       break;
 327     }
 328 }
 329
 330 /* Return nonzero if the insn CURRENT_RTX is inherently necessary.  */
 331
 332 static int
 333 inherently_necessary_register (current_rtx)
 334      rtx current_rtx;
 335 {
 336   return for_each_rtx (&current_rtx,
 337                        &inherently_necessary_register_1, NULL);
 338 }
 339
 340
 341 /* Called via note_stores for each store in an insn.  Note whether
 342    or not a particular store is inherently necessary.  Store a
 343    nonzero value in inherently_necessary_p if such a store is found.  */
 344
 345 static void
 346 note_inherently_necessary_set (dest, set, data)
 347      rtx set ATTRIBUTE_UNUSED;
 348      rtx dest;
 349      void *data;
 350 {
 351   int *inherently_necessary_set_p = (int *) data;
 352
 353   while (GET_CODE (dest) == SUBREG
 354          || GET_CODE (dest) == STRICT_LOW_PART
 355          || GET_CODE (dest) == ZERO_EXTRACT
 356          || GET_CODE (dest) == SIGN_EXTRACT)
 357     dest = XEXP (dest, 0);
 358
 359   if (GET_CODE (dest) == MEM
 360       || GET_CODE (dest) == UNSPEC
 361       || GET_CODE (dest) == UNSPEC_VOLATILE)
 362     *inherently_necessary_set_p = 1;
 363 }
 364
 365 /* Mark X as inherently necessary if appropriate.  For example,
 366    function calls and storing values into memory are inherently
 367    necessary.  This function is to be used with for_each_rtx ().
 368    Return nonzero iff inherently necessary.  */
 369
 370 static int
 371 find_inherently_necessary (x)
 372      rtx x;
 373 {
 374   if (x == NULL_RTX)
 375     return 0;
 376   else if (inherently_necessary_register (x))
 377     return !0;
 378   else
 379     switch (GET_CODE (x))
 380       {
 381       case CALL_INSN:
 382       case BARRIER:
 383       case PREFETCH:
 384         return !0;
 385       case CODE_LABEL:
 386       case NOTE:
 387         return 0;
 388       case JUMP_INSN:
 389         return JUMP_TABLE_DATA_P (x) || computed_jump_p (x) != 0;
 390       case INSN:
 391         {
 392           int inherently_necessary_set = 0;
 393           note_stores (PATTERN (x),
 394                        note_inherently_necessary_set,
 395                        &inherently_necessary_set);
 396
 397           /* If we found an inherently necessary set or an asm
 398              instruction, then we consider this insn inherently
 399              necessary.  */
 400           return (inherently_necessary_set
 401                   || GET_CODE (PATTERN (x)) == ASM_INPUT
 402                   || asm_noperands (PATTERN (x)) >= 0);
 403         }
 404       default:
 405         /* Found an impossible insn type.  */
 406         abort ();
 407         break;
 408       }
 409 }
 410
 411 /* Propagate necessity through REG and SUBREG operands of CURRENT_RTX.
 412    This function is called with for_each_rtx () on necessary
 413    instructions.  The DATA must be a varray of unprocessed
 414    instructions.  */
 415
 416 static int
 417 propagate_necessity_through_operand (current_rtx, data)
 418      rtx *current_rtx;
 419      void *data;
 420 {
 421   rtx x = *current_rtx;
 422   varray_type *unprocessed_instructions = (varray_type *) data;
 423
 424   if (x == NULL_RTX)
 425     return 0;
 426   switch ( GET_CODE (x))
 427     {
 428     case REG:
 429       if (CONVERT_REGISTER_TO_SSA_P (REGNO (x)))
 430         {
 431           rtx insn = VARRAY_RTX (ssa_definition, REGNO (x));
 432           if (insn != NULL_RTX && UNNECESSARY_P (insn))
 433             {
 434               RESURRECT_INSN (insn);
 435               VARRAY_PUSH_RTX (*unprocessed_instructions, insn);
 436             }
 437         }
 438       return 0;
 439
 440     default:
 441       return 0;
 442     }
 443 }
 444
 445 /* Indicate all insns initially assumed to be unnecessary.  */
 446
 447 static void
 448 mark_all_insn_unnecessary ()
 449 {
 450   rtx insn;
 451   for (insn = get_insns (); insn != NULL_RTX; insn = NEXT_INSN (insn))
 452     KILL_INSN (insn);
 453 }
 454
 455 /* Find the label beginning block BB, adding one if necessary.  */
 456
 457 static rtx
 458 find_block_label (bb)
 459      basic_block bb;
 460 {
 461   rtx insn = bb->head;
 462   if (LABEL_P (insn))
 463     return insn;
 464   else
 465     {
 466       rtx new_label = emit_label_before (gen_label_rtx (), insn);
 467       if (insn == bb->head)
 468         bb->head = new_label;
 469       return new_label;
 470     }
 471 }
 472
 473 /* Remove INSN, updating its basic block structure.  */
 474
 475 static void
 476 delete_insn_bb (insn)
 477      rtx insn;
 478 {
 479   if (!insn)
 480     abort ();
 481
 482   /* Do not actually delete anything that is not an INSN.
 483
 484      We can get here because we only consider INSNs as
 485      potentially necessary.  We leave it to later passes
 486      to remove unnecessary notes, unused labels, etc.  */
 487   if (! INSN_P (insn))
 488     return;
 489
 490   delete_insn (insn);
 491 }
 492 \f
 493 /* Perform the dead-code elimination.  */
 494
 495 void
 496 ssa_eliminate_dead_code ()
 497 {
 498   rtx insn;
 499   basic_block bb;
 500   /* Necessary instructions with operands to explore.  */
 501   varray_type unprocessed_instructions;
 502   /* Map element (b,e) is nonzero if the block is control dependent on
 503      edge.  "cdbte" abbreviates control dependent block to edge.  */
 504   control_dependent_block_to_edge_map cdbte;
 505  /* Element I is the immediate postdominator of block I.  */
 506   dominance_info pdom;
 507   struct edge_list *el;
 508
 509   /* Initialize the data structures.  */
 510   mark_all_insn_unnecessary ();
 511   VARRAY_RTX_INIT (unprocessed_instructions, 64,
 512                    "unprocessed instructions");
 513   cdbte = control_dependent_block_to_edge_map_create (last_basic_block);
 514
 515   /* Prepare for use of BLOCK_NUM ().  */
 516   connect_infinite_loops_to_exit ();
 517
 518   /* Compute control dependence.  */
 519   pdom = calculate_dominance_info (CDI_POST_DOMINATORS);
 520   el = create_edge_list ();
 521   find_all_control_dependences (el, pdom, cdbte);
 522
 523   /* Find inherently necessary instructions.  */
 524   for (insn = get_insns (); insn != NULL_RTX; insn = NEXT_INSN (insn))
 525     if (find_inherently_necessary (insn))
 526       {
 527         RESURRECT_INSN (insn);
 528         VARRAY_PUSH_RTX (unprocessed_instructions, insn);
 529       }
 530
 531   /* Propagate necessity using the operands of necessary instructions.  */
 532   while (VARRAY_ACTIVE_SIZE (unprocessed_instructions) > 0)
 533     {
 534       rtx current_instruction;
 535       int edge_number;
 536
 537       current_instruction = VARRAY_TOP_RTX (unprocessed_instructions);
 538       VARRAY_POP (unprocessed_instructions);
 539
 540       /* Make corresponding control dependent edges necessary.  */
 541       /* Assume the only JUMP_INSN is the block's last insn.  It appears
 542          that the last instruction of the program need not be a
 543          JUMP_INSN.  */
 544
 545       if (INSN_P (current_instruction)
 546           && !JUMP_TABLE_DATA_P (current_instruction))
 547         {
 548           /* Notes and labels contain no interesting operands.  */
 549           EXECUTE_IF_CONTROL_DEPENDENT
 550             (cdbte, current_instruction, edge_number,
 551             {
 552               rtx jump_insn = (INDEX_EDGE_PRED_BB (el, edge_number))->end;
 553               if (GET_CODE (jump_insn) == JUMP_INSN
 554                   && UNNECESSARY_P (jump_insn))
 555                 {
 556                   RESURRECT_INSN (jump_insn);
 557                   VARRAY_PUSH_RTX (unprocessed_instructions, jump_insn);
 558                 }
 559             });
 560
 561           /* Propagate through the operands.  */
 562           for_each_rtx (&current_instruction,
 563                         &propagate_necessity_through_operand,
 564                         (PTR) &unprocessed_instructions);
 565
 566           /* PHI nodes are somewhat special in that each PHI alternative
 567              has data and control dependencies.  The data dependencies
 568              are handled via propagate_necessity_through_operand.  We
 569              handle the control dependency here.
 570
 571              We consider the control dependent edges leading to the
 572              predecessor block associated with each PHI alternative
 573              as necessary.  */
 574           if (PHI_NODE_P (current_instruction))
 575             {
 576               rtvec phi_vec = XVEC (SET_SRC (PATTERN (current_instruction)), 0);
 577               int num_elem = GET_NUM_ELEM (phi_vec);
 578               int v;
 579
 580               for (v = num_elem - 2; v >= 0; v -= 2)
 581                 {
 582                   basic_block bb;
 583
 584                   bb = BASIC_BLOCK (INTVAL (RTVEC_ELT (phi_vec, v + 1)));
 585                   EXECUTE_IF_CONTROL_DEPENDENT
 586                     (cdbte, bb->end, edge_number,
 587                     {
 588                       rtx jump_insn;
 589
 590                       jump_insn = (INDEX_EDGE_PRED_BB (el, edge_number))->end;
 591                       if (((GET_CODE (jump_insn) == JUMP_INSN))
 592                           && UNNECESSARY_P (jump_insn))
 593                         {
 594                           RESURRECT_INSN (jump_insn);
 595                           VARRAY_PUSH_RTX (unprocessed_instructions, jump_insn);
 596                         }
 597                     });
 598
 599                 }
 600             }
 601         }
 602     }
 603
 604   /* Remove the unnecessary instructions.  */
 605   EXECUTE_IF_UNNECESSARY (insn,
 606   {
 607     if (any_condjump_p (insn))
 608       {
 609         basic_block bb = BLOCK_FOR_INSN (insn);
 610         basic_block pdom_bb = find_pdom (pdom, bb);
 611         rtx lbl;
 612         edge e;
 613
 614         /* Egad.  The immediate post dominator is the exit block.  We
 615            would like to optimize this conditional jump to jump directly
 616            to the exit block.  That can be difficult as we may not have
 617            a suitable CODE_LABEL that allows us to fall unmolested into
 618            the exit block.
 619
 620            So, we just delete the conditional branch by turning it into
 621            a deleted note.   That is safe, but just not as optimal as
 622            it could be.  */
 623         if (pdom_bb == EXIT_BLOCK_PTR)
 624           {
 625             /* Since we're going to just delete the branch, we need
 626                look at all the edges and remove all those which are not
 627                a fallthru edge.  */
 628             e = bb->succ;
 629             while (e)
 630               {
 631                 edge temp = e;
 632
 633                 e = e->succ_next;
 634                 if ((temp->flags & EDGE_FALLTHRU) == 0)
 635                   {
 636                     /* We've found a non-fallthru edge, find any PHI nodes
 637                        at the target and clean them up.  */
 638                     if (temp->dest != EXIT_BLOCK_PTR)
 639                       {
 640                         rtx insn
 641                           = first_insn_after_basic_block_note (temp->dest);
 642
 643                         while (PHI_NODE_P (insn))
 644                           {
 645                             remove_phi_alternative (PATTERN (insn), temp->src);
 646                             insn = NEXT_INSN (insn);
 647                           }
 648                       }
 649
 650                     remove_edge (temp);
 651                   }
 652               }
 653
 654             /* Now "delete" the conditional jump.  */
 655             PUT_CODE (insn, NOTE);
 656             NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
 657             continue;
 658           }
 659
 660         /* We've found a conditional branch that is unnecessary.
 661
 662            First, remove all outgoing edges from this block, updating
 663            PHI nodes as appropriate.  */
 664         e = bb->succ;
 665         while (e)
 666           {
 667             edge temp = e;
 668
 669             e = e->succ_next;
 670
 671             if (temp->flags & EDGE_ABNORMAL)
 672               continue;
 673
 674             /* We found an edge that is not executable.  First simplify
 675                the PHI nodes in the target block.  */
 676             if (temp->dest != EXIT_BLOCK_PTR)
 677               {
 678                 rtx insn = first_insn_after_basic_block_note (temp->dest);
 679
 680                 while (PHI_NODE_P (insn))
 681                   {
 682                     remove_phi_alternative (PATTERN (insn), temp->src);
 683                     insn = NEXT_INSN (insn);
 684                   }
 685               }
 686
 687             remove_edge (temp);
 688           }
 689
 690         /* Create an edge from this block to the post dominator.
 691            What about the PHI nodes at the target?  */
 692         make_edge (bb, pdom_bb, 0);
 693
 694         /* Third, transform this insn into an unconditional
 695            jump to the label for the immediate postdominator.  */
 696         lbl = find_block_label (pdom_bb);
 697         SET_SRC (PATTERN (insn)) = gen_rtx_LABEL_REF (VOIDmode, lbl);
 698         INSN_CODE (insn) = -1;
 699         JUMP_LABEL (insn) = lbl;
 700         LABEL_NUSES (lbl)++;
 701
 702         /* A barrier must follow any unconditional jump.  Barriers
 703            are not in basic blocks so this must occur after
 704            deleting the conditional jump.  */
 705         emit_barrier_after (insn);
 706       }
 707     else if (!JUMP_P (insn))
 708       delete_insn_bb (insn);
 709   });
 710
 711   /* Remove fake edges from the CFG.  */
 712   remove_fake_edges ();
 713
 714   /* Find any blocks with no successors and ensure they are followed
 715      by a BARRIER.  delete_insn has the nasty habit of deleting barriers
 716      when deleting insns.  */
 717   FOR_EACH_BB (bb)
 718     {
 719       if (bb->succ == NULL)
 720         {
 721           rtx next = NEXT_INSN (bb->end);
 722
 723           if (!next || GET_CODE (next) != BARRIER)
 724             emit_barrier_after (bb->end);
 725         }
 726     }
 727   /* Release allocated memory.  */
 728   for (insn = get_insns (); insn != NULL_RTX; insn = NEXT_INSN (insn))
 729     RESURRECT_INSN (insn);
 730   if (VARRAY_ACTIVE_SIZE (unprocessed_instructions) != 0)
 731     abort ();
 732   control_dependent_block_to_edge_map_free (cdbte);
 733   free ((PTR) pdom);
 734   free_edge_list (el);
 735 }