gcc/ssa-dce.c

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