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 GNU CC.
   6
   7 GNU CC is free software; you can redistribute it and/or modify it
   8 under the terms of the GNU General Public License as published by the
   9 Free Software Foundation; either version 2, or (at your option) any
  10 later version.
  11
  12 GNU CC is distributed in the hope that it will be useful, but WITHOUT
  13 ANY 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 GNU CC; 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         return !0;
 376       case CODE_LABEL:
 377       case NOTE:
 378       case BARRIER:
 379         return 0;
 380         break;
 381       case JUMP_INSN:
 382         return JUMP_TABLE_DATA_P (x) || computed_jump_p (x) != 0;
 383         break;
 384       case INSN:
 385         {
 386           int inherently_necessary_set = 0;
 387           note_stores (PATTERN (x),
 388                        note_inherently_necessary_set,
 389                        &inherently_necessary_set);
 390
 391           /* If we found an inherently necessary set or an asm
 392              instruction, then we consider this insn inherently
 393              necessary.  */
 394           return (inherently_necessary_set
 395                   || GET_CODE (PATTERN (x)) == ASM_INPUT
 396                   || asm_noperands (PATTERN (x)) >= 0);
 397         }
 398       default:
 399         /* Found an impossible insn type.  */
 400         abort();
 401         break;
 402       }
 403 }
 404
 405 /* Propagate necessity through REG and SUBREG operands of CURRENT_RTX.
 406    This function is called with for_each_rtx () on necessary
 407    instructions.  The DATA must be a varray of unprocessed
 408    instructions.  */
 409
 410 static int
 411 propagate_necessity_through_operand (current_rtx, data)
 412      rtx *current_rtx;
 413      void *data;
 414 {
 415   rtx x = *current_rtx;
 416   varray_type *unprocessed_instructions = (varray_type *) data;
 417
 418   if (x == NULL_RTX)
 419     return 0;
 420   switch ( GET_CODE (x))
 421     {
 422     case REG:
 423       if (CONVERT_REGISTER_TO_SSA_P (REGNO (x)))
 424         {
 425           rtx insn = VARRAY_RTX (ssa_definition, REGNO (x));
 426           if (insn != NULL_RTX && UNNECESSARY_P (insn))
 427             {
 428               RESURRECT_INSN (insn);
 429               VARRAY_PUSH_RTX (*unprocessed_instructions, insn);
 430             }
 431         }
 432       return 0;
 433
 434     default:
 435       return 0;
 436     }
 437 }
 438
 439 /* Indicate all insns initially assumed to be unnecessary.  */
 440
 441 static void
 442 mark_all_insn_unnecessary ()
 443 {
 444   rtx insn;
 445   for (insn = get_insns (); insn != NULL_RTX; insn = NEXT_INSN (insn))
 446     KILL_INSN (insn);
 447 }
 448
 449 /* Find the label beginning block BB, adding one if necessary.  */
 450
 451 static rtx
 452 find_block_label (bb)
 453      basic_block bb;
 454 {
 455   rtx insn = bb->head;
 456   if (LABEL_P (insn))
 457     return insn;
 458   else
 459     {
 460       rtx new_label = emit_label_before (gen_label_rtx (), insn);
 461       if (insn == bb->head)
 462         bb->head = new_label;
 463       return new_label;
 464     }
 465 }
 466
 467 /* Remove INSN, updating its basic block structure.  */
 468
 469 static void
 470 delete_insn_bb (insn)
 471      rtx insn;
 472 {
 473   basic_block bb;
 474   if (!insn)
 475     abort ();
 476
 477   /* Do not actually delete anything that is not an INSN.
 478
 479      We can get here because we only consider INSNs as
 480      potentially necessary.  We leave it to later passes
 481      to remove unnecessary notes, unused labels, etc.  */
 482   if (! INSN_P (insn))
 483     return;
 484
 485   bb = BLOCK_FOR_INSN (insn);
 486   if (!bb)
 487     abort ();
 488   if (bb->head == bb->end)
 489     {
 490       /* Delete the insn by converting it to a note.  */
 491       PUT_CODE (insn, NOTE);
 492       NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
 493       return;
 494     }
 495   else if (insn == bb->head)
 496     bb->head = NEXT_INSN (insn);
 497   else if (insn == bb->end)
 498     bb->end = PREV_INSN (insn);
 499   delete_insn (insn);
 500 }
 501 \f
 502 /* Perform the dead-code elimination.  */
 503
 504 void
 505 ssa_eliminate_dead_code ()
 506 {
 507   int i;
 508   rtx insn;
 509   /* Necessary instructions with operands to explore.  */
 510   varray_type unprocessed_instructions;
 511   /* Map element (b,e) is nonzero if the block is control dependent on
 512      edge.  "cdbte" abbreviates control dependent block to edge.  */
 513   control_dependent_block_to_edge_map cdbte;
 514  /* Element I is the immediate postdominator of block I.  */
 515   int *pdom;
 516   struct edge_list *el;
 517
 518   int max_insn_uid = get_max_uid ();
 519
 520   /* Initialize the data structures.  */
 521   mark_all_insn_unnecessary ();
 522   VARRAY_RTX_INIT (unprocessed_instructions, 64,
 523                    "unprocessed instructions");
 524   cdbte = control_dependent_block_to_edge_map_create (n_basic_blocks);
 525
 526   /* Prepare for use of BLOCK_NUM ().  */
 527   connect_infinite_loops_to_exit ();
 528    /* Be careful not to clear the added edges.  */
 529   compute_bb_for_insn (max_insn_uid);
 530
 531   /* Compute control dependence.  */
 532   pdom = (int *) xmalloc (n_basic_blocks * sizeof (int));
 533   for (i = 0; i < n_basic_blocks; ++i)
 534     pdom[i] = INVALID_BLOCK;
 535   calculate_dominance_info (pdom, NULL, CDI_POST_DOMINATORS);
 536   /* Assume there is a path from each node to the exit block.  */
 537   for (i = 0; i < n_basic_blocks; ++i)
 538     if (pdom[i] == INVALID_BLOCK)
 539       pdom[i] = EXIT_BLOCK;
 540   el = create_edge_list();
 541   find_all_control_dependences (el, pdom, cdbte);
 542
 543   /* Find inherently necessary instructions.  */
 544   for (insn = get_insns (); insn != NULL_RTX; insn = NEXT_INSN (insn))
 545     if (find_inherently_necessary (insn))
 546       {
 547         RESURRECT_INSN (insn);
 548         VARRAY_PUSH_RTX (unprocessed_instructions, insn);
 549       }
 550
 551   /* Propagate necessity using the operands of necessary instructions.  */
 552   while (VARRAY_ACTIVE_SIZE (unprocessed_instructions) > 0)
 553     {
 554       rtx current_instruction;
 555       int edge_number;
 556
 557       current_instruction = VARRAY_TOP_RTX (unprocessed_instructions);
 558       VARRAY_POP (unprocessed_instructions);
 559
 560       /* Make corresponding control dependent edges necessary.  */
 561       /* Assume the only JUMP_INSN is the block's last insn.  It appears
 562          that the last instruction of the program need not be a
 563          JUMP_INSN.  */
 564
 565       if (INSN_P (current_instruction)
 566           && !JUMP_TABLE_DATA_P (current_instruction))
 567         {
 568           /* Notes and labels contain no interesting operands.  */
 569           EXECUTE_IF_CONTROL_DEPENDENT
 570             (cdbte, current_instruction, edge_number,
 571             {
 572               rtx jump_insn = (INDEX_EDGE_PRED_BB (el, edge_number))->end;
 573               if (GET_CODE (jump_insn) == JUMP_INSN
 574                   && UNNECESSARY_P (jump_insn))
 575                 {
 576                   RESURRECT_INSN (jump_insn);
 577                   VARRAY_PUSH_RTX (unprocessed_instructions, jump_insn);
 578                 }
 579             });
 580
 581           /* Propagate through the operands.  */
 582           for_each_rtx (&current_instruction,
 583                         &propagate_necessity_through_operand,
 584                         (PTR) &unprocessed_instructions);
 585
 586           /* PHI nodes are somewhat special in that each PHI alternative
 587              has data and control dependencies.  The data dependencies
 588              are handled via propagate_necessity_through_operand.  We
 589              handle the control dependency here.
 590
 591              We consider the control dependent edges leading to the
 592              predecessor block associated with each PHI alternative
 593              as necessary.  */
 594           if (PHI_NODE_P (current_instruction))
 595             {
 596               rtvec phi_vec = XVEC (SET_SRC (PATTERN (current_instruction)), 0);
 597               int num_elem = GET_NUM_ELEM (phi_vec);
 598               int v;
 599
 600               for (v = num_elem - 2; v >= 0; v -= 2)
 601                 {
 602                   basic_block bb;
 603
 604                   bb = BASIC_BLOCK (INTVAL (RTVEC_ELT (phi_vec, v + 1)));
 605                   EXECUTE_IF_CONTROL_DEPENDENT
 606                     (cdbte, bb->end, edge_number,
 607                     {
 608                       rtx jump_insn;
 609
 610                       jump_insn = (INDEX_EDGE_PRED_BB (el, edge_number))->end;
 611                       if (((GET_CODE (jump_insn) == JUMP_INSN))
 612                           && UNNECESSARY_P (jump_insn))
 613                         {
 614                           RESURRECT_INSN (jump_insn);
 615                           VARRAY_PUSH_RTX (unprocessed_instructions, jump_insn);
 616                         }
 617                     });
 618
 619                 }
 620             }
 621         }
 622     }
 623
 624   /* Remove the unnecessary instructions.  */
 625   EXECUTE_IF_UNNECESSARY (insn,
 626   {
 627     if (any_condjump_p (insn))
 628       {
 629       /* Convert unnecessary conditional insn to an unconditional
 630          jump to immediate postdominator block.  */
 631         rtx old_label = JUMP_LABEL (insn);
 632         int pdom_block_number =
 633           find_pdom (pdom, BLOCK_FOR_INSN (insn))->index;
 634
 635         /* Prevent the conditional jump's label from being deleted so
 636            we do not have to modify the basic block structure.  */
 637         ++LABEL_NUSES (old_label);
 638
 639         if (pdom_block_number != EXIT_BLOCK
 640             && pdom_block_number != INVALID_BLOCK)
 641           {
 642             rtx lbl = find_block_label (BASIC_BLOCK (pdom_block_number));
 643             rtx new_jump = emit_jump_insn_before (gen_jump (lbl), insn);
 644
 645             /* Let jump know that label is in use.  */
 646             JUMP_LABEL (new_jump) = lbl;
 647             ++LABEL_NUSES (lbl);
 648
 649             delete_insn_bb (insn);
 650
 651             /* A conditional branch is unnecessary if and only if any
 652                block control-dependent on it is unnecessary.  Thus,
 653                any phi nodes in these unnecessary blocks are also
 654                removed and these nodes need not be updated.  */
 655
 656             /* A barrier must follow any unconditional jump.  Barriers
 657                are not in basic blocks so this must occur after
 658                deleting the conditional jump.  */
 659             emit_barrier_after (new_jump);
 660           }
 661         else
 662           /* The block drops off the end of the function and the
 663              ending conditional jump is not needed.  */
 664           delete_insn_bb (insn);
 665       }
 666     else if (!JUMP_P (insn))
 667       delete_insn_bb (insn);
 668   });
 669
 670   /* Remove fake edges from the CFG.  */
 671   remove_fake_edges ();
 672
 673   /* Release allocated memory.  */
 674   for (insn = get_insns (); insn != NULL_RTX; insn = NEXT_INSN (insn))
 675     RESURRECT_INSN (insn);
 676   if (VARRAY_ACTIVE_SIZE (unprocessed_instructions) != 0)
 677     abort ();
 678   VARRAY_FREE (unprocessed_instructions);
 679   control_dependent_block_to_edge_map_free (cdbte);
 680   free ((PTR) pdom);
 681   free_edge_list (el);
 682 }