gcc/ssa-dce.c

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