OSDN Git Service

* rtl.def (PREFETCH): New rtx code.
[pf3gnuchains/gcc-fork.git] / 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 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, 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       case BARRIER:
376       case PREFETCH:
377         return !0;
378       case CODE_LABEL:
379       case NOTE:
380         return 0;
381       case JUMP_INSN:
382         return JUMP_TABLE_DATA_P (x) || computed_jump_p (x) != 0;
383       case INSN:
384         {
385           int inherently_necessary_set = 0;
386           note_stores (PATTERN (x),
387                        note_inherently_necessary_set,
388                        &inherently_necessary_set);
389
390           /* If we found an inherently necessary set or an asm
391              instruction, then we consider this insn inherently
392              necessary.  */
393           return (inherently_necessary_set
394                   || GET_CODE (PATTERN (x)) == ASM_INPUT
395                   || asm_noperands (PATTERN (x)) >= 0);
396         }
397       default:
398         /* Found an impossible insn type.  */
399         abort();
400         break;
401       }
402 }
403
404 /* Propagate necessity through REG and SUBREG operands of CURRENT_RTX.
405    This function is called with for_each_rtx () on necessary
406    instructions.  The DATA must be a varray of unprocessed
407    instructions.  */
408
409 static int
410 propagate_necessity_through_operand (current_rtx, data)
411      rtx *current_rtx;
412      void *data;
413 {
414   rtx x = *current_rtx;
415   varray_type *unprocessed_instructions = (varray_type *) data;
416
417   if (x == NULL_RTX)
418     return 0;
419   switch ( GET_CODE (x))
420     {
421     case REG:
422       if (CONVERT_REGISTER_TO_SSA_P (REGNO (x)))
423         {
424           rtx insn = VARRAY_RTX (ssa_definition, REGNO (x));
425           if (insn != NULL_RTX && UNNECESSARY_P (insn))
426             {
427               RESURRECT_INSN (insn);
428               VARRAY_PUSH_RTX (*unprocessed_instructions, insn);
429             }
430         }
431       return 0;
432
433     default:
434       return 0;
435     }
436 }
437
438 /* Indicate all insns initially assumed to be unnecessary.  */
439
440 static void
441 mark_all_insn_unnecessary ()
442 {
443   rtx insn;
444   for (insn = get_insns (); insn != NULL_RTX; insn = NEXT_INSN (insn))
445     KILL_INSN (insn);
446 }
447
448 /* Find the label beginning block BB, adding one if necessary.  */
449
450 static rtx
451 find_block_label (bb)
452      basic_block bb;
453 {
454   rtx insn = bb->head;
455   if (LABEL_P (insn))
456     return insn;
457   else
458     {
459       rtx new_label = emit_label_before (gen_label_rtx (), insn);
460       if (insn == bb->head)
461         bb->head = new_label;
462       return new_label;
463     }
464 }
465
466 /* Remove INSN, updating its basic block structure.  */
467
468 static void
469 delete_insn_bb (insn)
470      rtx insn;
471 {
472   if (!insn)
473     abort ();
474
475   /* Do not actually delete anything that is not an INSN.
476
477      We can get here because we only consider INSNs as
478      potentially necessary.  We leave it to later passes
479      to remove unnecessary notes, unused labels, etc.  */
480   if (! INSN_P (insn))
481     return;
482
483   delete_insn (insn);
484 }
485 \f
486 /* Perform the dead-code elimination.  */
487
488 void
489 ssa_eliminate_dead_code ()
490 {
491   int i;
492   rtx insn;
493   /* Necessary instructions with operands to explore.  */
494   varray_type unprocessed_instructions;
495   /* Map element (b,e) is nonzero if the block is control dependent on
496      edge.  "cdbte" abbreviates control dependent block to edge.  */
497   control_dependent_block_to_edge_map cdbte;
498  /* Element I is the immediate postdominator of block I.  */
499   int *pdom;
500   struct edge_list *el;
501
502   int max_insn_uid = get_max_uid ();
503
504   /* Initialize the data structures.  */
505   mark_all_insn_unnecessary ();
506   VARRAY_RTX_INIT (unprocessed_instructions, 64,
507                    "unprocessed instructions");
508   cdbte = control_dependent_block_to_edge_map_create (n_basic_blocks);
509
510   /* Prepare for use of BLOCK_NUM ().  */
511   connect_infinite_loops_to_exit ();
512    /* Be careful not to clear the added edges.  */
513   compute_bb_for_insn (max_insn_uid);
514
515   /* Compute control dependence.  */
516   pdom = (int *) xmalloc (n_basic_blocks * sizeof (int));
517   for (i = 0; i < n_basic_blocks; ++i)
518     pdom[i] = INVALID_BLOCK;
519   calculate_dominance_info (pdom, NULL, CDI_POST_DOMINATORS);
520   /* Assume there is a path from each node to the exit block.  */
521   for (i = 0; i < n_basic_blocks; ++i)
522     if (pdom[i] == INVALID_BLOCK)
523       pdom[i] = EXIT_BLOCK;
524   el = create_edge_list();
525   find_all_control_dependences (el, pdom, cdbte);
526
527   /* Find inherently necessary instructions.  */
528   for (insn = get_insns (); insn != NULL_RTX; insn = NEXT_INSN (insn))
529     if (find_inherently_necessary (insn))
530       {
531         RESURRECT_INSN (insn);
532         VARRAY_PUSH_RTX (unprocessed_instructions, insn);
533       }
534
535   /* Propagate necessity using the operands of necessary instructions.  */
536   while (VARRAY_ACTIVE_SIZE (unprocessed_instructions) > 0)
537     {
538       rtx current_instruction;
539       int edge_number;
540
541       current_instruction = VARRAY_TOP_RTX (unprocessed_instructions);
542       VARRAY_POP (unprocessed_instructions);
543
544       /* Make corresponding control dependent edges necessary.  */
545       /* Assume the only JUMP_INSN is the block's last insn.  It appears
546          that the last instruction of the program need not be a
547          JUMP_INSN.  */
548
549       if (INSN_P (current_instruction)
550           && !JUMP_TABLE_DATA_P (current_instruction))
551         {
552           /* Notes and labels contain no interesting operands.  */
553           EXECUTE_IF_CONTROL_DEPENDENT
554             (cdbte, current_instruction, edge_number,
555             {
556               rtx jump_insn = (INDEX_EDGE_PRED_BB (el, edge_number))->end;
557               if (GET_CODE (jump_insn) == JUMP_INSN
558                   && UNNECESSARY_P (jump_insn))
559                 {
560                   RESURRECT_INSN (jump_insn);
561                   VARRAY_PUSH_RTX (unprocessed_instructions, jump_insn);
562                 }
563             });
564
565           /* Propagate through the operands.  */
566           for_each_rtx (&current_instruction,
567                         &propagate_necessity_through_operand,
568                         (PTR) &unprocessed_instructions);
569
570           /* PHI nodes are somewhat special in that each PHI alternative
571              has data and control dependencies.  The data dependencies
572              are handled via propagate_necessity_through_operand.  We
573              handle the control dependency here.
574
575              We consider the control dependent edges leading to the
576              predecessor block associated with each PHI alternative
577              as necessary.  */
578           if (PHI_NODE_P (current_instruction))
579             {
580               rtvec phi_vec = XVEC (SET_SRC (PATTERN (current_instruction)), 0);
581               int num_elem = GET_NUM_ELEM (phi_vec);
582               int v;
583
584               for (v = num_elem - 2; v >= 0; v -= 2)
585                 {
586                   basic_block bb;
587
588                   bb = BASIC_BLOCK (INTVAL (RTVEC_ELT (phi_vec, v + 1)));
589                   EXECUTE_IF_CONTROL_DEPENDENT
590                     (cdbte, bb->end, edge_number,
591                     {
592                       rtx jump_insn;
593
594                       jump_insn = (INDEX_EDGE_PRED_BB (el, edge_number))->end;
595                       if (((GET_CODE (jump_insn) == JUMP_INSN))
596                           && UNNECESSARY_P (jump_insn))
597                         {
598                           RESURRECT_INSN (jump_insn);
599                           VARRAY_PUSH_RTX (unprocessed_instructions, jump_insn);
600                         }
601                     });
602
603                 }
604             }
605         }
606     }
607
608   /* Remove the unnecessary instructions.  */
609   EXECUTE_IF_UNNECESSARY (insn,
610   {
611     if (any_condjump_p (insn))
612       {
613         basic_block bb = BLOCK_FOR_INSN (insn);
614         basic_block pdom_bb = find_pdom (pdom, bb);
615         rtx lbl;
616         edge e;
617
618         /* Egad.  The immediate post dominator is the exit block.  We
619            would like to optimize this conditional jump to jump directly
620            to the exit block.  That can be difficult as we may not have
621            a suitable CODE_LABEL that allows us to fall unmolested into
622            the exit block.
623
624            So, we just delete the conditional branch by turning it into
625            a deleted note.   That is safe, but just not as optimal as
626            it could be.  */
627         if (pdom_bb == EXIT_BLOCK_PTR)
628           {
629             /* Since we're going to just delete the branch, we need
630                look at all the edges and remove all those which are not
631                a fallthru edge.  */
632             e = bb->succ;
633             while (e)
634               {
635                 edge temp = e;
636
637                 e = e->succ_next;
638                 if ((temp->flags & EDGE_FALLTHRU) == 0)
639                   {
640                     /* We've found a non-fallthru edge, find any PHI nodes
641                        at the target and clean them up.  */
642                     if (temp->dest != EXIT_BLOCK_PTR)
643                       {
644                         rtx insn
645                           = first_insn_after_basic_block_note (temp->dest);
646
647                         while (PHI_NODE_P (insn))
648                           {
649                             remove_phi_alternative (PATTERN (insn), temp->src);
650                             insn = NEXT_INSN (insn);
651                           }
652                       }
653
654                     remove_edge (temp);
655                   }
656               }
657
658             /* Now "delete" the conditional jump.  */
659             PUT_CODE (insn, NOTE);
660             NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
661             continue;
662           }
663
664         /* We've found a conditional branch that is unnecessary.
665
666            First, remove all outgoing edges from this block, updating
667            PHI nodes as appropriate.  */
668         e = bb->succ;
669         while (e)
670           {
671             edge temp = e;
672
673             e = e->succ_next;
674
675             if (temp->flags & EDGE_ABNORMAL)
676               continue;
677
678             /* We found an edge that is not executable.  First simplify
679                the PHI nodes in the target block.  */
680             if (temp->dest != EXIT_BLOCK_PTR)
681               {
682                 rtx insn = first_insn_after_basic_block_note (temp->dest);
683
684                 while (PHI_NODE_P (insn))
685                   {
686                     remove_phi_alternative (PATTERN (insn), temp->src);
687                     insn = NEXT_INSN (insn);
688                   }
689               }
690
691             remove_edge (temp);
692           }
693
694         /* Create an edge from this block to the post dominator.  
695            What about the PHI nodes at the target?  */
696         make_edge (bb, pdom_bb, 0);
697
698         /* Third, transform this insn into an unconditional
699            jump to the label for the immediate postdominator.  */
700         lbl = find_block_label (pdom_bb);
701         SET_SRC (PATTERN (insn)) = gen_rtx_LABEL_REF (VOIDmode, lbl);
702         INSN_CODE (insn) = -1;
703         JUMP_LABEL (insn) = lbl;
704         LABEL_NUSES (lbl)++;
705
706         /* A barrier must follow any unconditional jump.  Barriers
707            are not in basic blocks so this must occur after
708            deleting the conditional jump.  */
709         emit_barrier_after (insn);
710       }
711     else if (!JUMP_P (insn))
712       delete_insn_bb (insn);
713   });
714   
715   /* Remove fake edges from the CFG.  */
716   remove_fake_edges ();
717
718   /* Find any blocks with no successors and ensure they are followed
719      by a BARRIER.  delete_insn has the nasty habit of deleting barriers
720      when deleting insns.  */
721   for (i = 0; i < n_basic_blocks; i++)
722     {
723       basic_block bb = BASIC_BLOCK (i);
724
725       if (bb->succ == NULL)
726         {
727           rtx next = NEXT_INSN (bb->end);
728
729           if (!next || GET_CODE (next) != BARRIER)
730             emit_barrier_after (bb->end);
731         }
732     }
733   /* Release allocated memory.  */
734   for (insn = get_insns (); insn != NULL_RTX; insn = NEXT_INSN (insn))
735     RESURRECT_INSN (insn);
736   if (VARRAY_ACTIVE_SIZE (unprocessed_instructions) != 0)
737     abort ();
738   VARRAY_FREE (unprocessed_instructions);
739   control_dependent_block_to_edge_map_free (cdbte);
740   free ((PTR) pdom);
741   free_edge_list (el);
742 }