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