OSDN Git Service

73cb173ba81fe25f7fd4f77ddbbe0705a884d340
[pf3gnuchains/gcc-fork.git] / gcc / flow.c
1 /* Data flow analysis for GNU compiler.
2    Copyright (C) 1987, 1988, 1992, 1993, 1994, 1995, 1996, 1997, 1998, 
3    1999, 2000 Free Software Foundation, Inc.
4
5 This file is part of GNU CC.
6
7 GNU CC is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 2, or (at your option)
10 any later version.
11
12 GNU CC is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15 GNU General Public License 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
19 the Free Software Foundation, 59 Temple Place - Suite 330,
20 Boston, MA 02111-1307, USA.  */
21
22
23 /* This file contains the data flow analysis pass of the compiler.  It
24    computes data flow information which tells combine_instructions
25    which insns to consider combining and controls register allocation.
26
27    Additional data flow information that is too bulky to record is
28    generated during the analysis, and is used at that time to create
29    autoincrement and autodecrement addressing.
30
31    The first step is dividing the function into basic blocks.
32    find_basic_blocks does this.  Then life_analysis determines
33    where each register is live and where it is dead.
34
35    ** find_basic_blocks **
36
37    find_basic_blocks divides the current function's rtl into basic
38    blocks and constructs the CFG.  The blocks are recorded in the
39    basic_block_info array; the CFG exists in the edge structures
40    referenced by the blocks.
41
42    find_basic_blocks also finds any unreachable loops and deletes them.
43
44    ** life_analysis **
45
46    life_analysis is called immediately after find_basic_blocks.
47    It uses the basic block information to determine where each
48    hard or pseudo register is live.
49
50    ** live-register info **
51
52    The information about where each register is live is in two parts:
53    the REG_NOTES of insns, and the vector basic_block->global_live_at_start.
54
55    basic_block->global_live_at_start has an element for each basic
56    block, and the element is a bit-vector with a bit for each hard or
57    pseudo register.  The bit is 1 if the register is live at the
58    beginning of the basic block.
59
60    Two types of elements can be added to an insn's REG_NOTES.  
61    A REG_DEAD note is added to an insn's REG_NOTES for any register
62    that meets both of two conditions:  The value in the register is not
63    needed in subsequent insns and the insn does not replace the value in
64    the register (in the case of multi-word hard registers, the value in
65    each register must be replaced by the insn to avoid a REG_DEAD note).
66
67    In the vast majority of cases, an object in a REG_DEAD note will be
68    used somewhere in the insn.  The (rare) exception to this is if an
69    insn uses a multi-word hard register and only some of the registers are
70    needed in subsequent insns.  In that case, REG_DEAD notes will be
71    provided for those hard registers that are not subsequently needed.
72    Partial REG_DEAD notes of this type do not occur when an insn sets
73    only some of the hard registers used in such a multi-word operand;
74    omitting REG_DEAD notes for objects stored in an insn is optional and
75    the desire to do so does not justify the complexity of the partial
76    REG_DEAD notes.
77
78    REG_UNUSED notes are added for each register that is set by the insn
79    but is unused subsequently (if every register set by the insn is unused
80    and the insn does not reference memory or have some other side-effect,
81    the insn is deleted instead).  If only part of a multi-word hard
82    register is used in a subsequent insn, REG_UNUSED notes are made for
83    the parts that will not be used.
84
85    To determine which registers are live after any insn, one can
86    start from the beginning of the basic block and scan insns, noting
87    which registers are set by each insn and which die there.
88
89    ** Other actions of life_analysis **
90
91    life_analysis sets up the LOG_LINKS fields of insns because the
92    information needed to do so is readily available.
93
94    life_analysis deletes insns whose only effect is to store a value
95    that is never used.
96
97    life_analysis notices cases where a reference to a register as
98    a memory address can be combined with a preceding or following
99    incrementation or decrementation of the register.  The separate
100    instruction to increment or decrement is deleted and the address
101    is changed to a POST_INC or similar rtx.
102
103    Each time an incrementing or decrementing address is created,
104    a REG_INC element is added to the insn's REG_NOTES list.
105
106    life_analysis fills in certain vectors containing information about
107    register usage: REG_N_REFS, REG_N_DEATHS, REG_N_SETS, REG_LIVE_LENGTH,
108    REG_N_CALLS_CROSSED and REG_BASIC_BLOCK.
109
110    life_analysis sets current_function_sp_is_unchanging if the function
111    doesn't modify the stack pointer.  */
112
113 /* TODO: 
114
115    Split out from life_analysis:
116         - local property discovery (bb->local_live, bb->local_set)
117         - global property computation
118         - log links creation
119         - pre/post modify transformation
120 */
121 \f
122 #include "config.h"
123 #include "system.h"
124 #include "tree.h"
125 #include "rtl.h"
126 #include "tm_p.h"
127 #include "basic-block.h"
128 #include "insn-config.h"
129 #include "regs.h"
130 #include "hard-reg-set.h"
131 #include "flags.h"
132 #include "output.h"
133 #include "function.h"
134 #include "except.h"
135 #include "toplev.h"
136 #include "recog.h"
137 #include "insn-flags.h"
138 #include "expr.h"
139
140 #include "obstack.h"
141 #include "splay-tree.h"
142
143 #define obstack_chunk_alloc xmalloc
144 #define obstack_chunk_free free
145
146
147 /* EXIT_IGNORE_STACK should be nonzero if, when returning from a function,
148    the stack pointer does not matter.  The value is tested only in
149    functions that have frame pointers.
150    No definition is equivalent to always zero.  */
151 #ifndef EXIT_IGNORE_STACK
152 #define EXIT_IGNORE_STACK 0
153 #endif
154
155 #ifndef HAVE_epilogue
156 #define HAVE_epilogue 0
157 #endif
158 #ifndef HAVE_prologue
159 #define HAVE_prologue 0
160 #endif
161 #ifndef HAVE_sibcall_epilogue
162 #define HAVE_sibcall_epilogue 0
163 #endif
164
165 /* The contents of the current function definition are allocated
166    in this obstack, and all are freed at the end of the function.
167    For top-level functions, this is temporary_obstack.
168    Separate obstacks are made for nested functions.  */
169
170 extern struct obstack *function_obstack;
171
172 /* Number of basic blocks in the current function.  */
173
174 int n_basic_blocks;
175
176 /* Number of edges in the current function.  */
177
178 int n_edges;
179
180 /* The basic block array.  */
181
182 varray_type basic_block_info;
183
184 /* The special entry and exit blocks.  */
185
186 struct basic_block_def entry_exit_blocks[2]
187 = {{NULL,                       /* head */
188     NULL,                       /* end */
189     NULL,                       /* pred */
190     NULL,                       /* succ */
191     NULL,                       /* local_set */
192     NULL,                       /* global_live_at_start */
193     NULL,                       /* global_live_at_end */
194     NULL,                       /* aux */
195     ENTRY_BLOCK,                /* index */
196     0,                          /* loop_depth */
197     -1, -1                      /* eh_beg, eh_end */
198   },
199   {
200     NULL,                       /* head */
201     NULL,                       /* end */
202     NULL,                       /* pred */
203     NULL,                       /* succ */
204     NULL,                       /* local_set */
205     NULL,                       /* global_live_at_start */
206     NULL,                       /* global_live_at_end */
207     NULL,                       /* aux */
208     EXIT_BLOCK,                 /* index */
209     0,                          /* loop_depth */
210     -1, -1                      /* eh_beg, eh_end */
211   }
212 };
213
214 /* Nonzero if the second flow pass has completed.  */
215 int flow2_completed;
216
217 /* Maximum register number used in this function, plus one.  */
218
219 int max_regno;
220
221 /* Indexed by n, giving various register information */
222
223 varray_type reg_n_info;
224
225 /* Size of a regset for the current function,
226    in (1) bytes and (2) elements.  */
227
228 int regset_bytes;
229 int regset_size;
230
231 /* Regset of regs live when calls to `setjmp'-like functions happen.  */
232 /* ??? Does this exist only for the setjmp-clobbered warning message?  */
233
234 regset regs_live_at_setjmp;
235
236 /* List made of EXPR_LIST rtx's which gives pairs of pseudo registers
237    that have to go in the same hard reg.
238    The first two regs in the list are a pair, and the next two
239    are another pair, etc.  */
240 rtx regs_may_share;
241
242 /* Set of registers that may be eliminable.  These are handled specially
243    in updating regs_ever_live.  */
244
245 static HARD_REG_SET elim_reg_set;
246
247 /* The basic block structure for every insn, indexed by uid.  */
248
249 varray_type basic_block_for_insn;
250
251 /* The labels mentioned in non-jump rtl.  Valid during find_basic_blocks.  */
252 /* ??? Should probably be using LABEL_NUSES instead.  It would take a 
253    bit of surgery to be able to use or co-opt the routines in jump.  */
254
255 static rtx label_value_list;
256
257 /* Holds information for tracking conditional register life information.  */
258 struct reg_cond_life_info
259 {
260   /* An EXPR_LIST of conditions under which a register is dead.  */
261   rtx condition;
262
263   /* ??? Could store mask of bytes that are dead, so that we could finally
264      track lifetimes of multi-word registers accessed via subregs.  */
265 };
266
267 /* For use in communicating between propagate_block and its subroutines.
268    Holds all information needed to compute life and def-use information.  */
269
270 struct propagate_block_info
271 {
272   /* The basic block we're considering.  */
273   basic_block bb;
274
275   /* Bit N is set if register N is conditionally or unconditionally live.  */
276   regset reg_live;
277
278   /* Bit N is set if register N is set this insn.  */
279   regset new_set;
280
281   /* Element N is the next insn that uses (hard or pseudo) register N
282      within the current basic block; or zero, if there is no such insn.  */
283   rtx *reg_next_use;
284
285   /* Contains a list of all the MEMs we are tracking for dead store
286      elimination.  */
287   rtx mem_set_list;
288
289   /* If non-null, record the set of registers set in the basic block.  */
290   regset local_set;
291
292 #ifdef HAVE_conditional_execution
293   /* Indexed by register number, holds a reg_cond_life_info for each
294      register that is not unconditionally live or dead.  */
295   splay_tree reg_cond_dead;
296
297   /* Bit N is set if register N is in an expression in reg_cond_dead.  */
298   regset reg_cond_reg;
299 #endif
300
301   /* Non-zero if the value of CC0 is live.  */
302   int cc0_live;
303
304   /* Flags controling the set of information propagate_block collects.  */
305   int flags;
306 };
307
308 /* Forward declarations */
309 static int count_basic_blocks           PARAMS ((rtx));
310 static rtx find_basic_blocks_1          PARAMS ((rtx));
311 static void clear_edges                 PARAMS ((void));
312 static void make_edges                  PARAMS ((rtx));
313 static void make_label_edge             PARAMS ((sbitmap *, basic_block,
314                                                  rtx, int));
315 static void make_eh_edge                PARAMS ((sbitmap *, eh_nesting_info *,
316                                                  basic_block, rtx, int));
317 static void mark_critical_edges         PARAMS ((void));
318 static void move_stray_eh_region_notes  PARAMS ((void));
319 static void record_active_eh_regions    PARAMS ((rtx));
320
321 static void commit_one_edge_insertion   PARAMS ((edge));
322
323 static void delete_unreachable_blocks   PARAMS ((void));
324 static void delete_eh_regions           PARAMS ((void));
325 static int can_delete_note_p            PARAMS ((rtx));
326 static void expunge_block               PARAMS ((basic_block));
327 static int can_delete_label_p           PARAMS ((rtx));
328 static int merge_blocks_move_predecessor_nojumps PARAMS ((basic_block,
329                                                           basic_block));
330 static int merge_blocks_move_successor_nojumps PARAMS ((basic_block,
331                                                         basic_block));
332 static int merge_blocks                 PARAMS ((edge,basic_block,basic_block));
333 static void try_merge_blocks            PARAMS ((void));
334 static void tidy_fallthru_edges         PARAMS ((void));
335 static int verify_wide_reg_1            PARAMS ((rtx *, void *));
336 static void verify_wide_reg             PARAMS ((int, rtx, rtx));
337 static void verify_local_live_at_start  PARAMS ((regset, basic_block));
338 static int set_noop_p                   PARAMS ((rtx));
339 static int noop_move_p                  PARAMS ((rtx));
340 static void delete_noop_moves           PARAMS ((rtx));
341 static void notice_stack_pointer_modification_1 PARAMS ((rtx, rtx, void *));
342 static void notice_stack_pointer_modification PARAMS ((rtx));
343 static void mark_reg                    PARAMS ((rtx, void *));
344 static void mark_regs_live_at_end       PARAMS ((regset));
345 static int set_phi_alternative_reg      PARAMS ((rtx, int, int, void *));
346 static void calculate_global_regs_live  PARAMS ((sbitmap, sbitmap, int));
347 static void propagate_block_delete_insn PARAMS ((basic_block, rtx));
348 static rtx propagate_block_delete_libcall PARAMS ((basic_block, rtx, rtx));
349 static int insn_dead_p                  PARAMS ((struct propagate_block_info *,
350                                                  rtx, int, rtx));
351 static int libcall_dead_p               PARAMS ((struct propagate_block_info *,
352                                                  rtx, rtx, rtx));
353 static void mark_set_regs               PARAMS ((struct propagate_block_info *,
354                                                  rtx, rtx));
355 static void mark_set_1                  PARAMS ((struct propagate_block_info *,
356                                                  enum rtx_code, rtx, rtx,
357                                                  rtx, int));
358 #ifdef HAVE_conditional_execution
359 static int mark_regno_cond_dead         PARAMS ((struct propagate_block_info *,
360                                                  int, rtx));
361 static void free_reg_cond_life_info     PARAMS ((splay_tree_value));
362 static int flush_reg_cond_reg_1         PARAMS ((splay_tree_node, void *));
363 static void flush_reg_cond_reg          PARAMS ((struct propagate_block_info *,
364                                                  int));
365 static rtx ior_reg_cond                 PARAMS ((rtx, rtx));
366 static rtx not_reg_cond                 PARAMS ((rtx));
367 static rtx nand_reg_cond                PARAMS ((rtx, rtx));
368 #endif
369 #ifdef AUTO_INC_DEC
370 static void find_auto_inc               PARAMS ((struct propagate_block_info *,
371                                                  rtx, rtx));
372 static int try_pre_increment_1          PARAMS ((struct propagate_block_info *,
373                                                  rtx));
374 static int try_pre_increment            PARAMS ((rtx, rtx, HOST_WIDE_INT));
375 #endif
376 static void mark_used_reg               PARAMS ((struct propagate_block_info *,
377                                                  rtx, rtx, rtx));
378 static void mark_used_regs              PARAMS ((struct propagate_block_info *,
379                                                  rtx, rtx, rtx));
380 void dump_flow_info                     PARAMS ((FILE *));
381 void debug_flow_info                    PARAMS ((void));
382 static void dump_edge_info              PARAMS ((FILE *, edge, int));
383
384 static void invalidate_mems_from_autoinc PARAMS ((struct propagate_block_info *,
385                                                   rtx));
386 static void remove_fake_successors      PARAMS ((basic_block));
387 static void flow_nodes_print    PARAMS ((const char *, const sbitmap, FILE *));
388 static void flow_exits_print PARAMS ((const char *, const edge *, int, FILE *));
389 static void flow_loops_cfg_dump         PARAMS ((const struct loops *, FILE *));
390 static int flow_loop_nested_p           PARAMS ((struct loop *, struct loop *));
391 static int flow_loop_exits_find         PARAMS ((const sbitmap, edge **));
392 static int flow_loop_nodes_find PARAMS ((basic_block, basic_block, sbitmap));
393 static int flow_depth_first_order_compute PARAMS ((int *));
394 static basic_block flow_loop_pre_header_find PARAMS ((basic_block, const sbitmap *));
395 static void flow_loop_tree_node_add     PARAMS ((struct loop *, struct loop *));
396 static void flow_loops_tree_build       PARAMS ((struct loops *));
397 static int flow_loop_level_compute      PARAMS ((struct loop *, int));
398 static int flow_loops_level_compute     PARAMS ((struct loops *));
399 \f
400 /* Find basic blocks of the current function.
401    F is the first insn of the function and NREGS the number of register
402    numbers in use.  */
403
404 void
405 find_basic_blocks (f, nregs, file)
406      rtx f;
407      int nregs ATTRIBUTE_UNUSED;
408      FILE *file ATTRIBUTE_UNUSED;
409 {
410   int max_uid;
411
412   /* Flush out existing data.  */
413   if (basic_block_info != NULL)
414     {
415       int i;
416
417       clear_edges ();
418
419       /* Clear bb->aux on all extant basic blocks.  We'll use this as a 
420          tag for reuse during create_basic_block, just in case some pass
421          copies around basic block notes improperly.  */
422       for (i = 0; i < n_basic_blocks; ++i)
423         BASIC_BLOCK (i)->aux = NULL;
424
425       VARRAY_FREE (basic_block_info);
426     }
427
428   n_basic_blocks = count_basic_blocks (f);
429
430   /* Size the basic block table.  The actual structures will be allocated
431      by find_basic_blocks_1, since we want to keep the structure pointers
432      stable across calls to find_basic_blocks.  */
433   /* ??? This whole issue would be much simpler if we called find_basic_blocks
434      exactly once, and thereafter we don't have a single long chain of 
435      instructions at all until close to the end of compilation when we
436      actually lay them out.  */
437
438   VARRAY_BB_INIT (basic_block_info, n_basic_blocks, "basic_block_info");
439
440   label_value_list = find_basic_blocks_1 (f);
441   
442   /* Record the block to which an insn belongs.  */
443   /* ??? This should be done another way, by which (perhaps) a label is
444      tagged directly with the basic block that it starts.  It is used for
445      more than that currently, but IMO that is the only valid use.  */
446
447   max_uid = get_max_uid ();
448 #ifdef AUTO_INC_DEC
449   /* Leave space for insns life_analysis makes in some cases for auto-inc.
450      These cases are rare, so we don't need too much space.  */
451   max_uid += max_uid / 10;
452 #endif
453
454   compute_bb_for_insn (max_uid);
455
456   /* Discover the edges of our cfg.  */
457   record_active_eh_regions (f);
458   make_edges (label_value_list);
459
460   /* Do very simple cleanup now, for the benefit of code that runs between
461      here and cleanup_cfg, e.g. thread_prologue_and_epilogue_insns.  */
462   tidy_fallthru_edges ();
463
464   mark_critical_edges ();
465
466 #ifdef ENABLE_CHECKING
467   verify_flow_info ();
468 #endif
469 }
470
471 /* Count the basic blocks of the function.  */
472
473 static int 
474 count_basic_blocks (f)
475      rtx f;
476 {
477   register rtx insn;
478   register RTX_CODE prev_code;
479   register int count = 0;
480   int eh_region = 0;
481   int call_had_abnormal_edge = 0;
482
483   prev_code = JUMP_INSN;
484   for (insn = f; insn; insn = NEXT_INSN (insn))
485     {
486       register RTX_CODE code = GET_CODE (insn);
487
488       if (code == CODE_LABEL
489           || (GET_RTX_CLASS (code) == 'i'
490               && (prev_code == JUMP_INSN
491                   || prev_code == BARRIER
492                   || (prev_code == CALL_INSN && call_had_abnormal_edge))))
493         count++;
494
495       /* Record whether this call created an edge.  */
496       if (code == CALL_INSN)
497         {
498           rtx note = find_reg_note (insn, REG_EH_REGION, NULL_RTX);
499           int region = (note ? INTVAL (XEXP (note, 0)) : 1);
500
501           call_had_abnormal_edge = 0;
502
503           /* If there is an EH region or rethrow, we have an edge.  */
504           if ((eh_region && region > 0)
505               || find_reg_note (insn, REG_EH_RETHROW, NULL_RTX))
506             call_had_abnormal_edge = 1;
507           else if (nonlocal_goto_handler_labels && region >= 0)
508             /* If there is a nonlocal goto label and the specified
509                region number isn't -1, we have an edge. (0 means
510                no throw, but might have a nonlocal goto).  */
511             call_had_abnormal_edge = 1;
512         }
513
514       if (code != NOTE)
515         prev_code = code;
516       else if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_BEG)
517         ++eh_region;
518       else if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_END)
519         --eh_region;
520     }
521
522   /* The rest of the compiler works a bit smoother when we don't have to
523      check for the edge case of do-nothing functions with no basic blocks.  */
524   if (count == 0)
525     {
526       emit_insn (gen_rtx_USE (VOIDmode, const0_rtx));
527       count = 1;
528     }
529
530   return count;
531 }
532
533 /* Find all basic blocks of the function whose first insn is F.
534
535    Collect and return a list of labels whose addresses are taken.  This
536    will be used in make_edges for use with computed gotos.  */
537
538 static rtx
539 find_basic_blocks_1 (f)
540      rtx f;
541 {
542   register rtx insn, next;
543   int i = 0;
544   rtx bb_note = NULL_RTX;
545   rtx eh_list = NULL_RTX;
546   rtx label_value_list = NULL_RTX;
547   rtx head = NULL_RTX;
548   rtx end = NULL_RTX;
549   
550   /* We process the instructions in a slightly different way than we did
551      previously.  This is so that we see a NOTE_BASIC_BLOCK after we have
552      closed out the previous block, so that it gets attached at the proper
553      place.  Since this form should be equivalent to the previous,
554      count_basic_blocks continues to use the old form as a check.  */
555
556   for (insn = f; insn; insn = next)
557     {
558       enum rtx_code code = GET_CODE (insn);
559
560       next = NEXT_INSN (insn);
561
562       switch (code)
563         {
564         case NOTE:
565           {
566             int kind = NOTE_LINE_NUMBER (insn);
567
568             /* Keep a LIFO list of the currently active exception notes.  */
569             if (kind == NOTE_INSN_EH_REGION_BEG)
570               eh_list = alloc_INSN_LIST (insn, eh_list);
571             else if (kind == NOTE_INSN_EH_REGION_END)
572               {
573                 rtx t = eh_list;
574
575                 eh_list = XEXP (eh_list, 1);
576                 free_INSN_LIST_node (t);
577               }
578
579             /* Look for basic block notes with which to keep the 
580                basic_block_info pointers stable.  Unthread the note now;
581                we'll put it back at the right place in create_basic_block.
582                Or not at all if we've already found a note in this block.  */
583             else if (kind == NOTE_INSN_BASIC_BLOCK)
584               {
585                 if (bb_note == NULL_RTX)
586                   bb_note = insn;
587
588                 next = flow_delete_insn (insn);
589               }
590             break;
591           }
592
593         case CODE_LABEL:
594           /* A basic block starts at a label.  If we've closed one off due 
595              to a barrier or some such, no need to do it again.  */
596           if (head != NULL_RTX)
597             {
598               /* While we now have edge lists with which other portions of
599                  the compiler might determine a call ending a basic block
600                  does not imply an abnormal edge, it will be a bit before
601                  everything can be updated.  So continue to emit a noop at
602                  the end of such a block.  */
603               if (GET_CODE (end) == CALL_INSN && ! SIBLING_CALL_P (end))
604                 {
605                   rtx nop = gen_rtx_USE (VOIDmode, const0_rtx);
606                   end = emit_insn_after (nop, end);
607                 }
608
609               create_basic_block (i++, head, end, bb_note);
610               bb_note = NULL_RTX;
611             }
612
613           head = end = insn;
614           break;
615
616         case JUMP_INSN:
617           /* A basic block ends at a jump.  */
618           if (head == NULL_RTX)
619             head = insn;
620           else
621             {
622               /* ??? Make a special check for table jumps.  The way this 
623                  happens is truly and amazingly gross.  We are about to
624                  create a basic block that contains just a code label and
625                  an addr*vec jump insn.  Worse, an addr_diff_vec creates
626                  its own natural loop.
627
628                  Prevent this bit of brain damage, pasting things together
629                  correctly in make_edges.  
630
631                  The correct solution involves emitting the table directly
632                  on the tablejump instruction as a note, or JUMP_LABEL.  */
633
634               if (GET_CODE (PATTERN (insn)) == ADDR_VEC
635                   || GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC)
636                 {
637                   head = end = NULL;
638                   n_basic_blocks--;
639                   break;
640                 }
641             }
642           end = insn;
643           goto new_bb_inclusive;
644
645         case BARRIER:
646           /* A basic block ends at a barrier.  It may be that an unconditional
647              jump already closed the basic block -- no need to do it again.  */
648           if (head == NULL_RTX)
649             break;
650
651           /* While we now have edge lists with which other portions of the
652              compiler might determine a call ending a basic block does not
653              imply an abnormal edge, it will be a bit before everything can
654              be updated.  So continue to emit a noop at the end of such a
655              block.  */
656           if (GET_CODE (end) == CALL_INSN && ! SIBLING_CALL_P (end))
657             {
658               rtx nop = gen_rtx_USE (VOIDmode, const0_rtx);
659               end = emit_insn_after (nop, end);
660             }
661           goto new_bb_exclusive;
662
663         case CALL_INSN:
664           {
665             /* Record whether this call created an edge.  */
666             rtx note = find_reg_note (insn, REG_EH_REGION, NULL_RTX);
667             int region = (note ? INTVAL (XEXP (note, 0)) : 1);
668             int call_has_abnormal_edge = 0;
669
670             /* If there is an EH region or rethrow, we have an edge.  */
671             if ((eh_list && region > 0)
672                 || find_reg_note (insn, REG_EH_RETHROW, NULL_RTX))
673               call_has_abnormal_edge = 1;
674             else if (nonlocal_goto_handler_labels && region >= 0)
675               /* If there is a nonlocal goto label and the specified
676                  region number isn't -1, we have an edge. (0 means
677                  no throw, but might have a nonlocal goto).  */
678               call_has_abnormal_edge = 1;
679
680             /* A basic block ends at a call that can either throw or
681                do a non-local goto.  */
682             if (call_has_abnormal_edge)
683               {
684               new_bb_inclusive:
685                 if (head == NULL_RTX)
686                   head = insn;
687                 end = insn;
688
689               new_bb_exclusive:
690                 create_basic_block (i++, head, end, bb_note);
691                 head = end = NULL_RTX;
692                 bb_note = NULL_RTX;
693                 break;
694               }
695             }
696           /* FALLTHRU */
697
698         default:
699           if (GET_RTX_CLASS (code) == 'i')
700             {
701               if (head == NULL_RTX)
702                 head = insn;
703               end = insn;
704             }
705           break;
706         }
707
708       if (GET_RTX_CLASS (code) == 'i')
709         {
710           rtx note;
711
712           /* Make a list of all labels referred to other than by jumps
713              (which just don't have the REG_LABEL notes). 
714
715              Make a special exception for labels followed by an ADDR*VEC,
716              as this would be a part of the tablejump setup code. 
717
718              Make a special exception for the eh_return_stub_label, which
719              we know isn't part of any otherwise visible control flow.  */
720              
721           for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
722             if (REG_NOTE_KIND (note) == REG_LABEL)
723               {
724                 rtx lab = XEXP (note, 0), next;
725
726                 if (lab == eh_return_stub_label)
727                     ;
728                 else if ((next = next_nonnote_insn (lab)) != NULL
729                          && GET_CODE (next) == JUMP_INSN
730                          && (GET_CODE (PATTERN (next)) == ADDR_VEC
731                              || GET_CODE (PATTERN (next)) == ADDR_DIFF_VEC))
732                   ;
733                 else
734                   label_value_list
735                     = alloc_EXPR_LIST (0, XEXP (note, 0), label_value_list);
736               }
737         }
738     }
739
740   if (head != NULL_RTX)
741     create_basic_block (i++, head, end, bb_note);
742
743   if (i != n_basic_blocks)
744     abort ();
745
746   return label_value_list;
747 }
748
749 /* Tidy the CFG by deleting unreachable code and whatnot.  */
750
751 void
752 cleanup_cfg (f)
753      rtx f;
754 {
755   delete_unreachable_blocks ();
756   move_stray_eh_region_notes ();
757   record_active_eh_regions (f);
758   try_merge_blocks ();
759   mark_critical_edges ();
760
761   /* Kill the data we won't maintain.  */
762   label_value_list = NULL_RTX;
763 }
764
765 /* Create a new basic block consisting of the instructions between
766    HEAD and END inclusive.  Reuses the note and basic block struct
767    in BB_NOTE, if any.  */
768
769 void
770 create_basic_block (index, head, end, bb_note)
771      int index;
772      rtx head, end, bb_note;
773 {
774   basic_block bb;
775
776   if (bb_note
777       && ! RTX_INTEGRATED_P (bb_note)
778       && (bb = NOTE_BASIC_BLOCK (bb_note)) != NULL
779       && bb->aux == NULL)
780     {
781       /* If we found an existing note, thread it back onto the chain.  */
782
783       if (GET_CODE (head) == CODE_LABEL)
784         add_insn_after (bb_note, head);
785       else
786         {
787           add_insn_before (bb_note, head);
788           head = bb_note;
789         }
790     }
791   else
792     {
793       /* Otherwise we must create a note and a basic block structure.
794          Since we allow basic block structs in rtl, give the struct
795          the same lifetime by allocating it off the function obstack
796          rather than using malloc.  */
797
798       bb = (basic_block) obstack_alloc (function_obstack, sizeof (*bb));
799       memset (bb, 0, sizeof (*bb));
800
801       if (GET_CODE (head) == CODE_LABEL)
802         bb_note = emit_note_after (NOTE_INSN_BASIC_BLOCK, head);
803       else
804         {
805           bb_note = emit_note_before (NOTE_INSN_BASIC_BLOCK, head);
806           head = bb_note;
807         }
808       NOTE_BASIC_BLOCK (bb_note) = bb;
809     }
810
811   /* Always include the bb note in the block.  */
812   if (NEXT_INSN (end) == bb_note)
813     end = bb_note;
814
815   bb->head = head;
816   bb->end = end;
817   bb->index = index;
818   BASIC_BLOCK (index) = bb;
819
820   /* Tag the block so that we know it has been used when considering
821      other basic block notes.  */
822   bb->aux = bb;
823 }
824 \f
825 /* Records the basic block struct in BB_FOR_INSN, for every instruction
826    indexed by INSN_UID.  MAX is the size of the array.  */
827
828 void
829 compute_bb_for_insn (max)
830      int max;
831 {
832   int i;
833
834   if (basic_block_for_insn)
835     VARRAY_FREE (basic_block_for_insn);
836   VARRAY_BB_INIT (basic_block_for_insn, max, "basic_block_for_insn");
837
838   for (i = 0; i < n_basic_blocks; ++i)
839     {
840       basic_block bb = BASIC_BLOCK (i);
841       rtx insn, end;
842
843       end = bb->end;
844       insn = bb->head;
845       while (1)
846         {
847           int uid = INSN_UID (insn);
848           if (uid < max)
849             VARRAY_BB (basic_block_for_insn, uid) = bb;
850           if (insn == end)
851             break;
852           insn = NEXT_INSN (insn);
853         }
854     }
855 }
856
857 /* Free the memory associated with the edge structures.  */
858
859 static void
860 clear_edges ()
861 {
862   int i;
863   edge n, e;
864
865   for (i = 0; i < n_basic_blocks; ++i)
866     {
867       basic_block bb = BASIC_BLOCK (i);
868
869       for (e = bb->succ; e ; e = n)
870         {
871           n = e->succ_next;
872           free (e);
873         }
874
875       bb->succ = 0;
876       bb->pred = 0;
877     }
878
879   for (e = ENTRY_BLOCK_PTR->succ; e ; e = n)
880     {
881       n = e->succ_next;
882       free (e);
883     }
884
885   ENTRY_BLOCK_PTR->succ = 0;
886   EXIT_BLOCK_PTR->pred = 0;
887
888   n_edges = 0;
889 }
890
891 /* Identify the edges between basic blocks.
892
893    NONLOCAL_LABEL_LIST is a list of non-local labels in the function.  Blocks
894    that are otherwise unreachable may be reachable with a non-local goto.
895
896    BB_EH_END is an array indexed by basic block number in which we record 
897    the list of exception regions active at the end of the basic block.  */
898
899 static void
900 make_edges (label_value_list)
901      rtx label_value_list;
902 {
903   int i;
904   eh_nesting_info *eh_nest_info = init_eh_nesting_info ();
905   sbitmap *edge_cache = NULL;
906
907   /* Assume no computed jump; revise as we create edges.  */
908   current_function_has_computed_jump = 0;
909
910   /* Heavy use of computed goto in machine-generated code can lead to
911      nearly fully-connected CFGs.  In that case we spend a significant
912      amount of time searching the edge lists for duplicates.  */
913   if (forced_labels || label_value_list)
914     {
915       edge_cache = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks);
916       sbitmap_vector_zero (edge_cache, n_basic_blocks);
917     }
918
919   /* By nature of the way these get numbered, block 0 is always the entry.  */
920   make_edge (edge_cache, ENTRY_BLOCK_PTR, BASIC_BLOCK (0), EDGE_FALLTHRU);
921
922   for (i = 0; i < n_basic_blocks; ++i)
923     {
924       basic_block bb = BASIC_BLOCK (i);
925       rtx insn, x;
926       enum rtx_code code;
927       int force_fallthru = 0;
928
929       /* Examine the last instruction of the block, and discover the
930          ways we can leave the block.  */
931
932       insn = bb->end;
933       code = GET_CODE (insn);
934
935       /* A branch.  */
936       if (code == JUMP_INSN)
937         {
938           rtx tmp;
939
940           /* ??? Recognize a tablejump and do the right thing.  */
941           if ((tmp = JUMP_LABEL (insn)) != NULL_RTX
942               && (tmp = NEXT_INSN (tmp)) != NULL_RTX
943               && GET_CODE (tmp) == JUMP_INSN
944               && (GET_CODE (PATTERN (tmp)) == ADDR_VEC
945                   || GET_CODE (PATTERN (tmp)) == ADDR_DIFF_VEC))
946             {
947               rtvec vec;
948               int j;
949
950               if (GET_CODE (PATTERN (tmp)) == ADDR_VEC)
951                 vec = XVEC (PATTERN (tmp), 0);
952               else
953                 vec = XVEC (PATTERN (tmp), 1);
954
955               for (j = GET_NUM_ELEM (vec) - 1; j >= 0; --j)
956                 make_label_edge (edge_cache, bb,
957                                  XEXP (RTVEC_ELT (vec, j), 0), 0);
958
959               /* Some targets (eg, ARM) emit a conditional jump that also
960                  contains the out-of-range target.  Scan for these and
961                  add an edge if necessary.  */
962               if ((tmp = single_set (insn)) != NULL
963                   && SET_DEST (tmp) == pc_rtx
964                   && GET_CODE (SET_SRC (tmp)) == IF_THEN_ELSE
965                   && GET_CODE (XEXP (SET_SRC (tmp), 2)) == LABEL_REF)
966                 make_label_edge (edge_cache, bb,
967                                  XEXP (XEXP (SET_SRC (tmp), 2), 0), 0);
968
969 #ifdef CASE_DROPS_THROUGH
970               /* Silly VAXen.  The ADDR_VEC is going to be in the way of
971                  us naturally detecting fallthru into the next block.  */
972               force_fallthru = 1;
973 #endif
974             }
975
976           /* If this is a computed jump, then mark it as reaching
977              everything on the label_value_list and forced_labels list.  */
978           else if (computed_jump_p (insn))
979             {
980               current_function_has_computed_jump = 1;
981
982               for (x = label_value_list; x; x = XEXP (x, 1))
983                 make_label_edge (edge_cache, bb, XEXP (x, 0), EDGE_ABNORMAL);
984               
985               for (x = forced_labels; x; x = XEXP (x, 1))
986                 make_label_edge (edge_cache, bb, XEXP (x, 0), EDGE_ABNORMAL);
987             }
988
989           /* Returns create an exit out.  */
990           else if (returnjump_p (insn))
991             make_edge (edge_cache, bb, EXIT_BLOCK_PTR, 0);
992
993           /* Otherwise, we have a plain conditional or unconditional jump.  */
994           else
995             {
996               if (! JUMP_LABEL (insn))
997                 abort ();
998               make_label_edge (edge_cache, bb, JUMP_LABEL (insn), 0);
999             }
1000         }
1001
1002       /* If this is a sibling call insn, then this is in effect a 
1003          combined call and return, and so we need an edge to the
1004          exit block.  No need to worry about EH edges, since we
1005          wouldn't have created the sibling call in the first place.  */
1006
1007       if (code == CALL_INSN && SIBLING_CALL_P (insn))
1008         make_edge (edge_cache, bb, EXIT_BLOCK_PTR, 0);
1009       else
1010
1011       /* If this is a CALL_INSN, then mark it as reaching the active EH
1012          handler for this CALL_INSN.  If we're handling asynchronous
1013          exceptions then any insn can reach any of the active handlers.
1014
1015          Also mark the CALL_INSN as reaching any nonlocal goto handler.  */
1016
1017       if (code == CALL_INSN || asynchronous_exceptions)
1018         {
1019           /* Add any appropriate EH edges.  We do this unconditionally
1020              since there may be a REG_EH_REGION or REG_EH_RETHROW note
1021              on the call, and this needn't be within an EH region.  */
1022           make_eh_edge (edge_cache, eh_nest_info, bb, insn, bb->eh_end);
1023
1024           /* If we have asynchronous exceptions, do the same for *all*
1025              exception regions active in the block.  */
1026           if (asynchronous_exceptions
1027               && bb->eh_beg != bb->eh_end)
1028             {
1029               if (bb->eh_beg >= 0)
1030                 make_eh_edge (edge_cache, eh_nest_info, bb,
1031                               NULL_RTX, bb->eh_beg);
1032
1033               for (x = bb->head; x != bb->end; x = NEXT_INSN (x))
1034                 if (GET_CODE (x) == NOTE
1035                     && (NOTE_LINE_NUMBER (x) == NOTE_INSN_EH_REGION_BEG
1036                         || NOTE_LINE_NUMBER (x) == NOTE_INSN_EH_REGION_END))
1037                   {
1038                     int region = NOTE_EH_HANDLER (x);
1039                     make_eh_edge (edge_cache, eh_nest_info, bb,
1040                                   NULL_RTX, region);
1041                   }
1042             }
1043
1044           if (code == CALL_INSN && nonlocal_goto_handler_labels)
1045             {
1046               /* ??? This could be made smarter: in some cases it's possible
1047                  to tell that certain calls will not do a nonlocal goto.
1048
1049                  For example, if the nested functions that do the nonlocal
1050                  gotos do not have their addresses taken, then only calls to
1051                  those functions or to other nested functions that use them
1052                  could possibly do nonlocal gotos.  */
1053               /* We do know that a REG_EH_REGION note with a value less
1054                  than 0 is guaranteed not to perform a non-local goto.  */
1055               rtx note = find_reg_note (insn, REG_EH_REGION, NULL_RTX);
1056               if (!note || INTVAL (XEXP (note, 0)) >=  0)
1057                 for (x = nonlocal_goto_handler_labels; x ; x = XEXP (x, 1))
1058                   make_label_edge (edge_cache, bb, XEXP (x, 0),
1059                                    EDGE_ABNORMAL | EDGE_ABNORMAL_CALL);
1060             }
1061         }
1062
1063       /* We know something about the structure of the function __throw in
1064          libgcc2.c.  It is the only function that ever contains eh_stub
1065          labels.  It modifies its return address so that the last block
1066          returns to one of the eh_stub labels within it.  So we have to
1067          make additional edges in the flow graph.  */
1068       if (i + 1 == n_basic_blocks && eh_return_stub_label != 0)
1069         make_label_edge (edge_cache, bb, eh_return_stub_label, EDGE_EH);
1070
1071       /* Find out if we can drop through to the next block.  */
1072       insn = next_nonnote_insn (insn);
1073       if (!insn || (i + 1 == n_basic_blocks && force_fallthru))
1074         make_edge (edge_cache, bb, EXIT_BLOCK_PTR, EDGE_FALLTHRU);
1075       else if (i + 1 < n_basic_blocks)
1076         {
1077           rtx tmp = BLOCK_HEAD (i + 1);
1078           if (GET_CODE (tmp) == NOTE)
1079             tmp = next_nonnote_insn (tmp);
1080           if (force_fallthru || insn == tmp)
1081             make_edge (edge_cache, bb, BASIC_BLOCK (i + 1), EDGE_FALLTHRU);
1082         }
1083     }
1084
1085   free_eh_nesting_info (eh_nest_info);
1086   if (edge_cache)
1087     sbitmap_vector_free (edge_cache);
1088 }
1089
1090 /* Create an edge between two basic blocks.  FLAGS are auxiliary information
1091    about the edge that is accumulated between calls.  */
1092
1093 void
1094 make_edge (edge_cache, src, dst, flags)
1095      sbitmap *edge_cache;
1096      basic_block src, dst;
1097      int flags;
1098 {
1099   int use_edge_cache;
1100   edge e;
1101
1102   /* Don't bother with edge cache for ENTRY or EXIT; there aren't that
1103      many edges to them, and we didn't allocate memory for it.  */
1104   use_edge_cache = (edge_cache
1105                     && src != ENTRY_BLOCK_PTR
1106                     && dst != EXIT_BLOCK_PTR);
1107
1108   /* Make sure we don't add duplicate edges.  */
1109   if (! use_edge_cache || TEST_BIT (edge_cache[src->index], dst->index))
1110     for (e = src->succ; e ; e = e->succ_next)
1111       if (e->dest == dst)
1112         {
1113           e->flags |= flags;
1114           return;
1115         }
1116
1117   e = (edge) xcalloc (1, sizeof (*e));
1118   n_edges++;
1119
1120   e->succ_next = src->succ;
1121   e->pred_next = dst->pred;
1122   e->src = src;
1123   e->dest = dst;
1124   e->flags = flags;
1125
1126   src->succ = e;
1127   dst->pred = e;
1128
1129   if (use_edge_cache)
1130     SET_BIT (edge_cache[src->index], dst->index);
1131 }
1132
1133 /* Create an edge from a basic block to a label.  */
1134
1135 static void
1136 make_label_edge (edge_cache, src, label, flags)
1137      sbitmap *edge_cache;
1138      basic_block src;
1139      rtx label;
1140      int flags;
1141 {
1142   if (GET_CODE (label) != CODE_LABEL)
1143     abort ();
1144
1145   /* If the label was never emitted, this insn is junk, but avoid a
1146      crash trying to refer to BLOCK_FOR_INSN (label).  This can happen
1147      as a result of a syntax error and a diagnostic has already been
1148      printed.  */
1149
1150   if (INSN_UID (label) == 0)
1151     return;
1152
1153   make_edge (edge_cache, src, BLOCK_FOR_INSN (label), flags);
1154 }
1155
1156 /* Create the edges generated by INSN in REGION.  */
1157
1158 static void
1159 make_eh_edge (edge_cache, eh_nest_info, src, insn, region)
1160      sbitmap *edge_cache;
1161      eh_nesting_info *eh_nest_info;
1162      basic_block src;
1163      rtx insn;
1164      int region;
1165 {
1166   handler_info **handler_list;
1167   int num, is_call;
1168
1169   is_call = (insn && GET_CODE (insn) == CALL_INSN ? EDGE_ABNORMAL_CALL : 0);
1170   num = reachable_handlers (region, eh_nest_info, insn, &handler_list);
1171   while (--num >= 0)
1172     {
1173       make_label_edge (edge_cache, src, handler_list[num]->handler_label,
1174                        EDGE_ABNORMAL | EDGE_EH | is_call);
1175     }
1176 }
1177
1178 /* EH_REGION notes appearing between basic blocks is ambiguous, and even
1179    dangerous if we intend to move basic blocks around.  Move such notes
1180    into the following block.  */
1181
1182 static void
1183 move_stray_eh_region_notes ()
1184 {
1185   int i;
1186   basic_block b1, b2;
1187
1188   if (n_basic_blocks < 2)
1189     return;
1190
1191   b2 = BASIC_BLOCK (n_basic_blocks - 1);
1192   for (i = n_basic_blocks - 2; i >= 0; --i, b2 = b1)
1193     {
1194       rtx insn, next, list = NULL_RTX;
1195
1196       b1 = BASIC_BLOCK (i);
1197       for (insn = NEXT_INSN (b1->end); insn != b2->head; insn = next)
1198         {
1199           next = NEXT_INSN (insn);
1200           if (GET_CODE (insn) == NOTE
1201               && (NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_BEG
1202                   || NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_END))
1203             {
1204               /* Unlink from the insn chain.  */
1205               NEXT_INSN (PREV_INSN (insn)) = next;
1206               PREV_INSN (next) = PREV_INSN (insn);
1207
1208               /* Queue it.  */
1209               NEXT_INSN (insn) = list;
1210               list = insn;
1211             }
1212         }
1213
1214       if (list == NULL_RTX)
1215         continue;
1216
1217       /* Find where to insert these things.  */
1218       insn = b2->head;
1219       if (GET_CODE (insn) == CODE_LABEL)
1220         insn = NEXT_INSN (insn);
1221
1222       while (list)
1223         {
1224           next = NEXT_INSN (list);
1225           add_insn_after (list, insn);
1226           list = next;
1227         }
1228     }
1229 }
1230
1231 /* Recompute eh_beg/eh_end for each basic block.  */
1232
1233 static void
1234 record_active_eh_regions (f)
1235      rtx f;
1236 {
1237   rtx insn, eh_list = NULL_RTX;
1238   int i = 0;
1239   basic_block bb = BASIC_BLOCK (0);
1240
1241   for (insn = f; insn ; insn = NEXT_INSN (insn))
1242     {
1243       if (bb->head == insn)
1244         bb->eh_beg = (eh_list ? NOTE_EH_HANDLER (XEXP (eh_list, 0)) : -1);
1245
1246       if (GET_CODE (insn) == NOTE)
1247         {
1248           int kind = NOTE_LINE_NUMBER (insn);
1249           if (kind == NOTE_INSN_EH_REGION_BEG)
1250             eh_list = alloc_INSN_LIST (insn, eh_list);
1251           else if (kind == NOTE_INSN_EH_REGION_END)
1252             {
1253               rtx t = XEXP (eh_list, 1);
1254               free_INSN_LIST_node (eh_list);
1255               eh_list = t;
1256             }
1257         }
1258
1259       if (bb->end == insn)
1260         {
1261           bb->eh_end = (eh_list ? NOTE_EH_HANDLER (XEXP (eh_list, 0)) : -1);
1262           i += 1;
1263           if (i == n_basic_blocks)
1264             break;
1265           bb = BASIC_BLOCK (i);
1266         }
1267     }
1268 }
1269
1270 /* Identify critical edges and set the bits appropriately.  */
1271
1272 static void
1273 mark_critical_edges ()
1274 {
1275   int i, n = n_basic_blocks;
1276   basic_block bb;
1277
1278   /* We begin with the entry block.  This is not terribly important now,
1279      but could be if a front end (Fortran) implemented alternate entry
1280      points.  */
1281   bb = ENTRY_BLOCK_PTR;
1282   i = -1;
1283
1284   while (1)
1285     {
1286       edge e;
1287
1288       /* (1) Critical edges must have a source with multiple successors.  */
1289       if (bb->succ && bb->succ->succ_next)
1290         {
1291           for (e = bb->succ; e ; e = e->succ_next)
1292             {
1293               /* (2) Critical edges must have a destination with multiple
1294                  predecessors.  Note that we know there is at least one
1295                  predecessor -- the edge we followed to get here.  */
1296               if (e->dest->pred->pred_next)
1297                 e->flags |= EDGE_CRITICAL;
1298               else
1299                 e->flags &= ~EDGE_CRITICAL;
1300             }
1301         }
1302       else
1303         {
1304           for (e = bb->succ; e ; e = e->succ_next)
1305             e->flags &= ~EDGE_CRITICAL;
1306         }
1307
1308       if (++i >= n)
1309         break;
1310       bb = BASIC_BLOCK (i);
1311     }
1312 }
1313 \f
1314 /* Split a (typically critical) edge.  Return the new block.
1315    Abort on abnormal edges. 
1316
1317    ??? The code generally expects to be called on critical edges.
1318    The case of a block ending in an unconditional jump to a 
1319    block with multiple predecessors is not handled optimally.  */
1320
1321 basic_block
1322 split_edge (edge_in)
1323      edge edge_in;
1324 {
1325   basic_block old_pred, bb, old_succ;
1326   edge edge_out;
1327   rtx bb_note;
1328   int i, j;
1329  
1330   /* Abnormal edges cannot be split.  */
1331   if ((edge_in->flags & EDGE_ABNORMAL) != 0)
1332     abort ();
1333
1334   old_pred = edge_in->src;
1335   old_succ = edge_in->dest;
1336
1337   /* Remove the existing edge from the destination's pred list.  */
1338   {
1339     edge *pp;
1340     for (pp = &old_succ->pred; *pp != edge_in; pp = &(*pp)->pred_next)
1341       continue;
1342     *pp = edge_in->pred_next;
1343     edge_in->pred_next = NULL;
1344   }
1345
1346   /* Create the new structures.  */
1347   bb = (basic_block) obstack_alloc (function_obstack, sizeof (*bb));
1348   edge_out = (edge) xcalloc (1, sizeof (*edge_out));
1349   n_edges++;
1350
1351   memset (bb, 0, sizeof (*bb));
1352   bb->global_live_at_start = OBSTACK_ALLOC_REG_SET (function_obstack);
1353   bb->global_live_at_end = OBSTACK_ALLOC_REG_SET (function_obstack);
1354
1355   /* ??? This info is likely going to be out of date very soon.  */
1356   if (old_succ->global_live_at_start)
1357     {
1358       COPY_REG_SET (bb->global_live_at_start, old_succ->global_live_at_start);
1359       COPY_REG_SET (bb->global_live_at_end, old_succ->global_live_at_start);
1360     }
1361   else
1362     {
1363       CLEAR_REG_SET (bb->global_live_at_start);
1364       CLEAR_REG_SET (bb->global_live_at_end);
1365     }
1366
1367   /* Wire them up.  */
1368   bb->pred = edge_in;
1369   bb->succ = edge_out;
1370
1371   edge_in->dest = bb;
1372   edge_in->flags &= ~EDGE_CRITICAL;
1373
1374   edge_out->pred_next = old_succ->pred;
1375   edge_out->succ_next = NULL;
1376   edge_out->src = bb;
1377   edge_out->dest = old_succ;
1378   edge_out->flags = EDGE_FALLTHRU;
1379   edge_out->probability = REG_BR_PROB_BASE;
1380
1381   old_succ->pred = edge_out;
1382
1383   /* Tricky case -- if there existed a fallthru into the successor
1384      (and we're not it) we must add a new unconditional jump around
1385      the new block we're actually interested in. 
1386
1387      Further, if that edge is critical, this means a second new basic
1388      block must be created to hold it.  In order to simplify correct
1389      insn placement, do this before we touch the existing basic block
1390      ordering for the block we were really wanting.  */
1391   if ((edge_in->flags & EDGE_FALLTHRU) == 0)
1392     {
1393       edge e;
1394       for (e = edge_out->pred_next; e ; e = e->pred_next)
1395         if (e->flags & EDGE_FALLTHRU)
1396           break;
1397
1398       if (e)
1399         {
1400           basic_block jump_block;
1401           rtx pos;
1402
1403           if ((e->flags & EDGE_CRITICAL) == 0
1404               && e->src != ENTRY_BLOCK_PTR)
1405             {
1406               /* Non critical -- we can simply add a jump to the end
1407                  of the existing predecessor.  */
1408               jump_block = e->src;
1409             }
1410           else
1411             {
1412               /* We need a new block to hold the jump.  The simplest
1413                  way to do the bulk of the work here is to recursively
1414                  call ourselves.  */
1415               jump_block = split_edge (e);
1416               e = jump_block->succ;
1417             }
1418
1419           /* Now add the jump insn ...  */
1420           pos = emit_jump_insn_after (gen_jump (old_succ->head),
1421                                       jump_block->end);
1422           jump_block->end = pos;
1423           if (basic_block_for_insn)
1424             set_block_for_insn (pos, jump_block);
1425           emit_barrier_after (pos);
1426
1427           /* ... let jump know that label is in use, ...  */
1428           JUMP_LABEL (pos) = old_succ->head;
1429           ++LABEL_NUSES (old_succ->head);
1430           
1431           /* ... and clear fallthru on the outgoing edge.  */
1432           e->flags &= ~EDGE_FALLTHRU;
1433
1434           /* Continue splitting the interesting edge.  */
1435         }
1436     }
1437
1438   /* Place the new block just in front of the successor.  */
1439   VARRAY_GROW (basic_block_info, ++n_basic_blocks);
1440   if (old_succ == EXIT_BLOCK_PTR)
1441     j = n_basic_blocks - 1;
1442   else
1443     j = old_succ->index;
1444   for (i = n_basic_blocks - 1; i > j; --i)
1445     {
1446       basic_block tmp = BASIC_BLOCK (i - 1);
1447       BASIC_BLOCK (i) = tmp;
1448       tmp->index = i;
1449     }
1450   BASIC_BLOCK (i) = bb;
1451   bb->index = i;
1452
1453   /* Create the basic block note. 
1454
1455      Where we place the note can have a noticable impact on the generated
1456      code.  Consider this cfg: 
1457         
1458
1459                         E
1460                         |
1461                         0
1462                        / \
1463                    +->1-->2--->E
1464                    |  |
1465                    +--+
1466
1467       If we need to insert an insn on the edge from block 0 to block 1,
1468       we want to ensure the instructions we insert are outside of any
1469       loop notes that physically sit between block 0 and block 1.  Otherwise
1470       we confuse the loop optimizer into thinking the loop is a phony.  */
1471   if (old_succ != EXIT_BLOCK_PTR
1472       && PREV_INSN (old_succ->head)
1473       && GET_CODE (PREV_INSN (old_succ->head)) == NOTE
1474       && NOTE_LINE_NUMBER (PREV_INSN (old_succ->head)) == NOTE_INSN_LOOP_BEG)
1475     bb_note = emit_note_before (NOTE_INSN_BASIC_BLOCK,
1476                                 PREV_INSN (old_succ->head));
1477   else if (old_succ != EXIT_BLOCK_PTR)
1478     bb_note = emit_note_before (NOTE_INSN_BASIC_BLOCK, old_succ->head);
1479   else
1480     bb_note = emit_note_after (NOTE_INSN_BASIC_BLOCK, get_last_insn ());
1481   NOTE_BASIC_BLOCK (bb_note) = bb;
1482   bb->head = bb->end = bb_note;
1483
1484   /* Not quite simple -- for non-fallthru edges, we must adjust the
1485      predecessor's jump instruction to target our new block.  */
1486   if ((edge_in->flags & EDGE_FALLTHRU) == 0)
1487     {
1488       rtx tmp, insn = old_pred->end;
1489       rtx old_label = old_succ->head;
1490       rtx new_label = gen_label_rtx ();
1491
1492       if (GET_CODE (insn) != JUMP_INSN)
1493         abort ();
1494
1495       /* ??? Recognize a tablejump and adjust all matching cases.  */
1496       if ((tmp = JUMP_LABEL (insn)) != NULL_RTX
1497           && (tmp = NEXT_INSN (tmp)) != NULL_RTX
1498           && GET_CODE (tmp) == JUMP_INSN
1499           && (GET_CODE (PATTERN (tmp)) == ADDR_VEC
1500               || GET_CODE (PATTERN (tmp)) == ADDR_DIFF_VEC))
1501         {
1502           rtvec vec;
1503           int j;
1504
1505           if (GET_CODE (PATTERN (tmp)) == ADDR_VEC)
1506             vec = XVEC (PATTERN (tmp), 0);
1507           else
1508             vec = XVEC (PATTERN (tmp), 1);
1509
1510           for (j = GET_NUM_ELEM (vec) - 1; j >= 0; --j)
1511             if (XEXP (RTVEC_ELT (vec, j), 0) == old_label)
1512               {
1513                 RTVEC_ELT (vec, j) = gen_rtx_LABEL_REF (VOIDmode, new_label);
1514                 --LABEL_NUSES (old_label);
1515                 ++LABEL_NUSES (new_label);
1516               }
1517
1518           /* Handle casesi dispatch insns */
1519           if ((tmp = single_set (insn)) != NULL
1520               && SET_DEST (tmp) == pc_rtx
1521               && GET_CODE (SET_SRC (tmp)) == IF_THEN_ELSE
1522               && GET_CODE (XEXP (SET_SRC (tmp), 2)) == LABEL_REF
1523               && XEXP (XEXP (SET_SRC (tmp), 2), 0) == old_label)
1524             {
1525               XEXP (SET_SRC (tmp), 2) = gen_rtx_LABEL_REF (VOIDmode, 
1526                                                            new_label);
1527               --LABEL_NUSES (old_label);
1528               ++LABEL_NUSES (new_label);
1529             }
1530         }
1531       else
1532         {
1533           /* This would have indicated an abnormal edge.  */
1534           if (computed_jump_p (insn))
1535             abort ();
1536
1537           /* A return instruction can't be redirected.  */
1538           if (returnjump_p (insn))
1539             abort ();
1540
1541           /* If the insn doesn't go where we think, we're confused.  */
1542           if (JUMP_LABEL (insn) != old_label)
1543             abort ();
1544
1545           redirect_jump (insn, new_label);
1546         }
1547
1548       emit_label_before (new_label, bb_note);
1549       bb->head = new_label;
1550     }
1551
1552   return bb;
1553 }
1554
1555 /* Queue instructions for insertion on an edge between two basic blocks.
1556    The new instructions and basic blocks (if any) will not appear in the
1557    CFG until commit_edge_insertions is called.  */
1558
1559 void
1560 insert_insn_on_edge (pattern, e)
1561      rtx pattern;
1562      edge e;
1563 {
1564   /* We cannot insert instructions on an abnormal critical edge.
1565      It will be easier to find the culprit if we die now.  */
1566   if ((e->flags & (EDGE_ABNORMAL|EDGE_CRITICAL))
1567       == (EDGE_ABNORMAL|EDGE_CRITICAL))
1568     abort ();
1569
1570   if (e->insns == NULL_RTX)
1571     start_sequence ();
1572   else
1573     push_to_sequence (e->insns);
1574
1575   emit_insn (pattern);
1576
1577   e->insns = get_insns ();
1578   end_sequence();
1579 }
1580
1581 /* Update the CFG for the instructions queued on edge E.  */
1582
1583 static void
1584 commit_one_edge_insertion (e)
1585      edge e;
1586 {
1587   rtx before = NULL_RTX, after = NULL_RTX, insns, tmp;
1588   basic_block bb;
1589
1590   /* Pull the insns off the edge now since the edge might go away.  */
1591   insns = e->insns;
1592   e->insns = NULL_RTX;
1593
1594   /* Figure out where to put these things.  If the destination has
1595      one predecessor, insert there.  Except for the exit block.  */
1596   if (e->dest->pred->pred_next == NULL
1597       && e->dest != EXIT_BLOCK_PTR)
1598     {
1599       bb = e->dest;
1600
1601       /* Get the location correct wrt a code label, and "nice" wrt
1602          a basic block note, and before everything else.  */
1603       tmp = bb->head;
1604       if (GET_CODE (tmp) == CODE_LABEL)
1605         tmp = NEXT_INSN (tmp);
1606       if (GET_CODE (tmp) == NOTE
1607           && NOTE_LINE_NUMBER (tmp) == NOTE_INSN_BASIC_BLOCK)
1608         tmp = NEXT_INSN (tmp);
1609       if (tmp == bb->head)
1610         before = tmp;
1611       else
1612         after = PREV_INSN (tmp);
1613     }
1614   
1615   /* If the source has one successor and the edge is not abnormal,
1616      insert there.  Except for the entry block.  */
1617   else if ((e->flags & EDGE_ABNORMAL) == 0
1618            && e->src->succ->succ_next == NULL
1619            && e->src != ENTRY_BLOCK_PTR)
1620     {
1621       bb = e->src;
1622       /* It is possible to have a non-simple jump here.  Consider a target
1623          where some forms of unconditional jumps clobber a register.  This
1624          happens on the fr30 for example. 
1625
1626          We know this block has a single successor, so we can just emit
1627          the queued insns before the jump.  */
1628       if (GET_CODE (bb->end) == JUMP_INSN)
1629         {
1630           before = bb->end;
1631         }
1632       else
1633         {
1634           /* We'd better be fallthru, or we've lost track of what's what.  */
1635           if ((e->flags & EDGE_FALLTHRU) == 0)
1636             abort ();
1637
1638           after = bb->end;
1639         }
1640     }
1641
1642   /* Otherwise we must split the edge.  */
1643   else
1644     {
1645       bb = split_edge (e);
1646       after = bb->end;
1647     }
1648
1649   /* Now that we've found the spot, do the insertion.  */
1650
1651   /* Set the new block number for these insns, if structure is allocated.  */
1652   if (basic_block_for_insn)
1653     {
1654       rtx i;
1655       for (i = insns; i != NULL_RTX; i = NEXT_INSN (i))
1656         set_block_for_insn (i, bb);
1657     }
1658
1659   if (before)
1660     {
1661       emit_insns_before (insns, before);
1662       if (before == bb->head)
1663         bb->head = insns;
1664     }
1665   else
1666     {
1667       rtx last = emit_insns_after (insns, after);
1668       if (after == bb->end)
1669         {
1670           bb->end = last;
1671
1672           if (GET_CODE (last) == JUMP_INSN)
1673             {
1674               if (returnjump_p (last))
1675                 {
1676                   /* ??? Remove all outgoing edges from BB and add one
1677                      for EXIT.  This is not currently a problem because
1678                      this only happens for the (single) epilogue, which
1679                      already has a fallthru edge to EXIT.  */
1680
1681                   e = bb->succ;
1682                   if (e->dest != EXIT_BLOCK_PTR
1683                       || e->succ_next != NULL
1684                       || (e->flags & EDGE_FALLTHRU) == 0)
1685                     abort ();
1686                   e->flags &= ~EDGE_FALLTHRU;
1687
1688                   emit_barrier_after (last);
1689                 }
1690               else
1691                 abort ();
1692             }
1693         }
1694     }
1695 }
1696
1697 /* Update the CFG for all queued instructions.  */
1698
1699 void
1700 commit_edge_insertions ()
1701 {
1702   int i;
1703   basic_block bb;
1704
1705 #ifdef ENABLE_CHECKING
1706   verify_flow_info ();
1707 #endif
1708  
1709   i = -1;
1710   bb = ENTRY_BLOCK_PTR;
1711   while (1)
1712     {
1713       edge e, next;
1714
1715       for (e = bb->succ; e ; e = next)
1716         {
1717           next = e->succ_next;
1718           if (e->insns)
1719             commit_one_edge_insertion (e);
1720         }
1721
1722       if (++i >= n_basic_blocks)
1723         break;
1724       bb = BASIC_BLOCK (i);
1725     }
1726 }
1727 \f
1728 /* Delete all unreachable basic blocks.   */
1729
1730 static void
1731 delete_unreachable_blocks ()
1732 {
1733   basic_block *worklist, *tos;
1734   int deleted_handler;
1735   edge e;
1736   int i, n;
1737
1738   n = n_basic_blocks;
1739   tos = worklist = (basic_block *) xmalloc (sizeof (basic_block) * n);
1740
1741   /* Use basic_block->aux as a marker.  Clear them all.  */
1742
1743   for (i = 0; i < n; ++i)
1744     BASIC_BLOCK (i)->aux = NULL;
1745
1746   /* Add our starting points to the worklist.  Almost always there will
1747      be only one.  It isn't inconcievable that we might one day directly
1748      support Fortran alternate entry points.  */
1749
1750   for (e = ENTRY_BLOCK_PTR->succ; e ; e = e->succ_next)
1751     {
1752       *tos++ = e->dest;
1753
1754       /* Mark the block with a handy non-null value.  */
1755       e->dest->aux = e;
1756     }
1757       
1758   /* Iterate: find everything reachable from what we've already seen.  */
1759
1760   while (tos != worklist)
1761     {
1762       basic_block b = *--tos;
1763
1764       for (e = b->succ; e ; e = e->succ_next)
1765         if (!e->dest->aux)
1766           {
1767             *tos++ = e->dest;
1768             e->dest->aux = e;
1769           }
1770     }
1771
1772   /* Delete all unreachable basic blocks.  Count down so that we don't
1773      interfere with the block renumbering that happens in flow_delete_block. */
1774
1775   deleted_handler = 0;
1776
1777   for (i = n - 1; i >= 0; --i)
1778     {
1779       basic_block b = BASIC_BLOCK (i);
1780
1781       if (b->aux != NULL)
1782         /* This block was found.  Tidy up the mark.  */
1783         b->aux = NULL;
1784       else
1785         deleted_handler |= flow_delete_block (b);
1786     }
1787
1788   tidy_fallthru_edges ();
1789
1790   /* If we deleted an exception handler, we may have EH region begin/end
1791      blocks to remove as well. */
1792   if (deleted_handler)
1793     delete_eh_regions ();
1794
1795   free (worklist);
1796 }
1797
1798 /* Find EH regions for which there is no longer a handler, and delete them.  */
1799
1800 static void
1801 delete_eh_regions ()
1802 {
1803   rtx insn;
1804
1805   update_rethrow_references ();
1806
1807   for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
1808     if (GET_CODE (insn) == NOTE)
1809       {
1810         if ((NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_BEG) ||
1811             (NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_END)) 
1812           {
1813             int num = NOTE_EH_HANDLER (insn);
1814             /* A NULL handler indicates a region is no longer needed,
1815                as long as its rethrow label isn't used.  */
1816             if (get_first_handler (num) == NULL && ! rethrow_used (num))
1817               {
1818                 NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
1819                 NOTE_SOURCE_FILE (insn) = 0;
1820               }
1821           }
1822       }
1823 }
1824
1825 /* Return true if NOTE is not one of the ones that must be kept paired,
1826    so that we may simply delete them.  */
1827
1828 static int
1829 can_delete_note_p (note)
1830      rtx note;
1831 {
1832   return (NOTE_LINE_NUMBER (note) == NOTE_INSN_DELETED
1833           || NOTE_LINE_NUMBER (note) == NOTE_INSN_BASIC_BLOCK);
1834 }
1835
1836 /* Unlink a chain of insns between START and FINISH, leaving notes
1837    that must be paired.  */
1838
1839 void
1840 flow_delete_insn_chain (start, finish)
1841      rtx start, finish;
1842 {
1843   /* Unchain the insns one by one.  It would be quicker to delete all
1844      of these with a single unchaining, rather than one at a time, but
1845      we need to keep the NOTE's.  */
1846
1847   rtx next;
1848
1849   while (1)
1850     {
1851       next = NEXT_INSN (start);
1852       if (GET_CODE (start) == NOTE && !can_delete_note_p (start))
1853         ;
1854       else if (GET_CODE (start) == CODE_LABEL && !can_delete_label_p (start))
1855         ;
1856       else
1857         next = flow_delete_insn (start);
1858
1859       if (start == finish)
1860         break;
1861       start = next;
1862     }
1863 }
1864
1865 /* Delete the insns in a (non-live) block.  We physically delete every
1866    non-deleted-note insn, and update the flow graph appropriately.
1867
1868    Return nonzero if we deleted an exception handler.  */
1869
1870 /* ??? Preserving all such notes strikes me as wrong.  It would be nice
1871    to post-process the stream to remove empty blocks, loops, ranges, etc.  */
1872
1873 int
1874 flow_delete_block (b)
1875      basic_block b;
1876 {
1877   int deleted_handler = 0;
1878   rtx insn, end, tmp;
1879
1880   /* If the head of this block is a CODE_LABEL, then it might be the
1881      label for an exception handler which can't be reached.
1882
1883      We need to remove the label from the exception_handler_label list
1884      and remove the associated NOTE_INSN_EH_REGION_BEG and
1885      NOTE_INSN_EH_REGION_END notes.  */
1886
1887   insn = b->head;
1888   
1889   never_reached_warning (insn);
1890
1891   if (GET_CODE (insn) == CODE_LABEL)
1892     {
1893       rtx x, *prev = &exception_handler_labels;
1894
1895       for (x = exception_handler_labels; x; x = XEXP (x, 1))
1896         {
1897           if (XEXP (x, 0) == insn)
1898             {
1899               /* Found a match, splice this label out of the EH label list.  */
1900               *prev = XEXP (x, 1);
1901               XEXP (x, 1) = NULL_RTX;
1902               XEXP (x, 0) = NULL_RTX;
1903
1904               /* Remove the handler from all regions */
1905               remove_handler (insn);
1906               deleted_handler = 1;
1907               break;
1908             }
1909           prev = &XEXP (x, 1);
1910         }
1911
1912       /* This label may be referenced by code solely for its value, or
1913          referenced by static data, or something.  We have determined
1914          that it is not reachable, but cannot delete the label itself.
1915          Save code space and continue to delete the balance of the block,
1916          along with properly updating the cfg.  */
1917       if (!can_delete_label_p (insn))
1918         {
1919           /* If we've only got one of these, skip the whole deleting
1920              insns thing.  */
1921           if (insn == b->end)
1922             goto no_delete_insns;
1923           insn = NEXT_INSN (insn);
1924         }
1925     }
1926
1927   /* Include any jump table following the basic block.  */
1928   end = b->end;
1929   if (GET_CODE (end) == JUMP_INSN
1930       && (tmp = JUMP_LABEL (end)) != NULL_RTX
1931       && (tmp = NEXT_INSN (tmp)) != NULL_RTX
1932       && GET_CODE (tmp) == JUMP_INSN
1933       && (GET_CODE (PATTERN (tmp)) == ADDR_VEC
1934           || GET_CODE (PATTERN (tmp)) == ADDR_DIFF_VEC))
1935     end = tmp;
1936
1937   /* Include any barrier that may follow the basic block.  */
1938   tmp = next_nonnote_insn (end);
1939   if (tmp && GET_CODE (tmp) == BARRIER)
1940     end = tmp;
1941
1942   /* Selectively delete the entire chain.  */
1943   flow_delete_insn_chain (insn, end);
1944
1945  no_delete_insns:
1946
1947   /* Remove the edges into and out of this block.  Note that there may 
1948      indeed be edges in, if we are removing an unreachable loop.  */
1949   {
1950     edge e, next, *q;
1951
1952     for (e = b->pred; e ; e = next)
1953       {
1954         for (q = &e->src->succ; *q != e; q = &(*q)->succ_next)
1955           continue;
1956         *q = e->succ_next;
1957         next = e->pred_next;
1958         n_edges--;
1959         free (e);
1960       }
1961     for (e = b->succ; e ; e = next)
1962       {
1963         for (q = &e->dest->pred; *q != e; q = &(*q)->pred_next)
1964           continue;
1965         *q = e->pred_next;
1966         next = e->succ_next;
1967         n_edges--;
1968         free (e);
1969       }
1970
1971     b->pred = NULL;
1972     b->succ = NULL;
1973   }
1974
1975   /* Remove the basic block from the array, and compact behind it.  */
1976   expunge_block (b);
1977
1978   return deleted_handler;
1979 }
1980
1981 /* Remove block B from the basic block array and compact behind it.  */
1982
1983 static void
1984 expunge_block (b)
1985      basic_block b;
1986 {
1987   int i, n = n_basic_blocks;
1988
1989   for (i = b->index; i + 1 < n; ++i)
1990     {
1991       basic_block x = BASIC_BLOCK (i + 1);
1992       BASIC_BLOCK (i) = x;
1993       x->index = i;
1994     }
1995
1996   basic_block_info->num_elements--;
1997   n_basic_blocks--;
1998 }
1999
2000 /* Delete INSN by patching it out.  Return the next insn.  */
2001
2002 rtx
2003 flow_delete_insn (insn)
2004      rtx insn;
2005 {
2006   rtx prev = PREV_INSN (insn);
2007   rtx next = NEXT_INSN (insn);
2008   rtx note;
2009
2010   PREV_INSN (insn) = NULL_RTX;
2011   NEXT_INSN (insn) = NULL_RTX;
2012
2013   if (prev)
2014     NEXT_INSN (prev) = next;
2015   if (next)
2016     PREV_INSN (next) = prev;
2017   else
2018     set_last_insn (prev);
2019
2020   if (GET_CODE (insn) == CODE_LABEL)
2021     remove_node_from_expr_list (insn, &nonlocal_goto_handler_labels);
2022
2023   /* If deleting a jump, decrement the use count of the label.  Deleting
2024      the label itself should happen in the normal course of block merging.  */
2025   if (GET_CODE (insn) == JUMP_INSN && JUMP_LABEL (insn))
2026     LABEL_NUSES (JUMP_LABEL (insn))--;
2027
2028   /* Also if deleting an insn that references a label.  */
2029   else if ((note = find_reg_note (insn, REG_LABEL, NULL_RTX)) != NULL_RTX)
2030     LABEL_NUSES (XEXP (note, 0))--;
2031
2032   return next;
2033 }
2034
2035 /* True if a given label can be deleted.  */
2036
2037 static int 
2038 can_delete_label_p (label)
2039      rtx label;
2040 {
2041   rtx x;
2042
2043   if (LABEL_PRESERVE_P (label))
2044     return 0;
2045
2046   for (x = forced_labels; x ; x = XEXP (x, 1))
2047     if (label == XEXP (x, 0))
2048       return 0;
2049   for (x = label_value_list; x ; x = XEXP (x, 1))
2050     if (label == XEXP (x, 0))
2051       return 0;
2052   for (x = exception_handler_labels; x ; x = XEXP (x, 1))
2053     if (label == XEXP (x, 0))
2054       return 0;
2055
2056   /* User declared labels must be preserved.  */
2057   if (LABEL_NAME (label) != 0)
2058     return 0;
2059   
2060   return 1;
2061 }
2062
2063 /* Blocks A and B are to be merged into a single block A.  The insns
2064    are already contiguous, hence `nomove'.  */
2065
2066 void
2067 merge_blocks_nomove (a, b)
2068      basic_block a, b;
2069 {
2070   edge e;
2071   rtx b_head, b_end, a_end;
2072   rtx del_first = NULL_RTX, del_last = NULL_RTX;
2073   int b_empty = 0;
2074
2075   /* If there was a CODE_LABEL beginning B, delete it.  */
2076   b_head = b->head;
2077   b_end = b->end;
2078   if (GET_CODE (b_head) == CODE_LABEL)
2079     {
2080       /* Detect basic blocks with nothing but a label.  This can happen
2081          in particular at the end of a function.  */
2082       if (b_head == b_end)
2083         b_empty = 1;
2084       del_first = del_last = b_head;
2085       b_head = NEXT_INSN (b_head);
2086     }
2087
2088   /* Delete the basic block note.  */
2089   if (GET_CODE (b_head) == NOTE 
2090       && NOTE_LINE_NUMBER (b_head) == NOTE_INSN_BASIC_BLOCK)
2091     {
2092       if (b_head == b_end)
2093         b_empty = 1;
2094       if (! del_last)
2095         del_first = b_head;
2096       del_last = b_head;
2097       b_head = NEXT_INSN (b_head);
2098     }
2099
2100   /* If there was a jump out of A, delete it.  */
2101   a_end = a->end;
2102   if (GET_CODE (a_end) == JUMP_INSN)
2103     {
2104       rtx prev;
2105
2106       prev = prev_nonnote_insn (a_end);
2107       if (!prev) 
2108         prev = a->head;
2109
2110       del_first = a_end;
2111
2112 #ifdef HAVE_cc0
2113       /* If this was a conditional jump, we need to also delete
2114          the insn that set cc0.  */
2115       if (prev && sets_cc0_p (prev))
2116         {
2117           rtx tmp = prev;
2118           prev = prev_nonnote_insn (prev);
2119           if (!prev)
2120             prev = a->head;
2121           del_first = tmp;
2122         }
2123 #endif
2124
2125       a_end = prev;
2126     }
2127
2128   /* Delete everything marked above as well as crap that might be
2129      hanging out between the two blocks.  */
2130   flow_delete_insn_chain (del_first, del_last);
2131
2132   /* Normally there should only be one successor of A and that is B, but
2133      partway though the merge of blocks for conditional_execution we'll
2134      be merging a TEST block with THEN and ELSE successors.  Free the
2135      whole lot of them and hope the caller knows what they're doing.  */
2136   while (a->succ)
2137     remove_edge (a->succ);
2138
2139   /* Adjust the edges out of B for the new owner.  */
2140   for (e = b->succ; e ; e = e->succ_next)
2141     e->src = a;
2142   a->succ = b->succ;
2143
2144   /* B hasn't quite yet ceased to exist.  Attempt to prevent mishap.  */
2145   b->pred = b->succ = NULL;
2146
2147   /* Reassociate the insns of B with A.  */
2148   if (!b_empty)
2149     {
2150       if (basic_block_for_insn)
2151         {
2152           BLOCK_FOR_INSN (b_head) = a;
2153           while (b_head != b_end)
2154             {
2155               b_head = NEXT_INSN (b_head);
2156               BLOCK_FOR_INSN (b_head) = a;
2157             }
2158         }
2159       a_end = b_end;
2160     }
2161   a->end = a_end;
2162
2163   expunge_block (b);
2164 }
2165
2166 /* Blocks A and B are to be merged into a single block.  A has no incoming
2167    fallthru edge, so it can be moved before B without adding or modifying
2168    any jumps (aside from the jump from A to B).  */
2169
2170 static int
2171 merge_blocks_move_predecessor_nojumps (a, b)
2172      basic_block a, b;
2173 {
2174   rtx start, end, barrier;
2175   int index;
2176
2177   start = a->head;
2178   end = a->end;
2179
2180   /* We want to delete the BARRIER after the end of the insns we are
2181      going to move.  If we don't find a BARRIER, then do nothing.  This
2182      can happen in some cases if we have labels we can not delete. 
2183
2184      Similarly, do nothing if we can not delete the label at the start
2185      of the target block.  */
2186   barrier = next_nonnote_insn (end);
2187   if (GET_CODE (barrier) != BARRIER
2188       || (GET_CODE (b->head) == CODE_LABEL
2189           && ! can_delete_label_p (b->head)))
2190     return 0;
2191   else
2192     flow_delete_insn (barrier);
2193
2194   /* Move block and loop notes out of the chain so that we do not
2195      disturb their order.
2196
2197      ??? A better solution would be to squeeze out all the non-nested notes
2198      and adjust the block trees appropriately.   Even better would be to have
2199      a tighter connection between block trees and rtl so that this is not
2200      necessary.  */
2201   start = squeeze_notes (start, end);
2202
2203   /* Scramble the insn chain.  */
2204   if (end != PREV_INSN (b->head))
2205     reorder_insns (start, end, PREV_INSN (b->head));
2206
2207   if (rtl_dump_file)
2208     {
2209       fprintf (rtl_dump_file, "Moved block %d before %d and merged.\n",
2210                a->index, b->index);
2211     }
2212
2213   /* Swap the records for the two blocks around.  Although we are deleting B,
2214      A is now where B was and we want to compact the BB array from where
2215      A used to be.  */
2216   BASIC_BLOCK(a->index) = b;
2217   BASIC_BLOCK(b->index) = a;
2218   index = a->index;
2219   a->index = b->index;
2220   b->index = index;
2221   
2222   /* Now blocks A and B are contiguous.  Merge them.  */
2223   merge_blocks_nomove (a, b);
2224
2225   return 1;
2226 }
2227
2228 /* Blocks A and B are to be merged into a single block.  B has no outgoing
2229    fallthru edge, so it can be moved after A without adding or modifying
2230    any jumps (aside from the jump from A to B).  */
2231
2232 static int
2233 merge_blocks_move_successor_nojumps (a, b)
2234      basic_block a, b;
2235 {
2236   rtx start, end, barrier;
2237
2238   start = b->head;
2239   end = b->end;
2240
2241   /* We want to delete the BARRIER after the end of the insns we are
2242      going to move.  If we don't find a BARRIER, then do nothing.  This
2243      can happen in some cases if we have labels we can not delete. 
2244
2245      Similarly, do nothing if we can not delete the label at the start
2246      of the target block.  */
2247   barrier = next_nonnote_insn (end);
2248   if (GET_CODE (barrier) != BARRIER
2249       || (GET_CODE (b->head) == CODE_LABEL
2250           && ! can_delete_label_p (b->head)))
2251     return 0;
2252   else
2253     flow_delete_insn (barrier);
2254
2255   /* Move block and loop notes out of the chain so that we do not
2256      disturb their order.
2257
2258      ??? A better solution would be to squeeze out all the non-nested notes
2259      and adjust the block trees appropriately.   Even better would be to have
2260      a tighter connection between block trees and rtl so that this is not
2261      necessary.  */
2262   start = squeeze_notes (start, end);
2263
2264   /* Scramble the insn chain.  */
2265   reorder_insns (start, end, a->end);
2266
2267   /* Now blocks A and B are contiguous.  Merge them.  */
2268   merge_blocks_nomove (a, b);
2269
2270   if (rtl_dump_file)
2271     {
2272       fprintf (rtl_dump_file, "Moved block %d after %d and merged.\n",
2273                b->index, a->index);
2274     }
2275
2276   return 1;
2277 }
2278
2279 /* Attempt to merge basic blocks that are potentially non-adjacent.  
2280    Return true iff the attempt succeeded.  */
2281
2282 static int
2283 merge_blocks (e, b, c)
2284      edge e;
2285      basic_block b, c;
2286 {
2287   /* If B has a fallthru edge to C, no need to move anything.  */
2288   if (e->flags & EDGE_FALLTHRU)
2289     {
2290       /* If a label still appears somewhere and we cannot delete the label,
2291          then we cannot merge the blocks.  The edge was tidied already.  */
2292
2293       rtx insn, stop = NEXT_INSN (c->head);
2294       for (insn = NEXT_INSN (b->end); insn != stop; insn = NEXT_INSN (insn))
2295         if (GET_CODE (insn) == CODE_LABEL && !can_delete_label_p (insn))
2296           return 0;
2297
2298       merge_blocks_nomove (b, c);
2299
2300       if (rtl_dump_file)
2301         {
2302           fprintf (rtl_dump_file, "Merged %d and %d without moving.\n",
2303                    b->index, c->index);
2304         }
2305
2306       return 1;
2307     }
2308   else
2309     {
2310       edge tmp_edge;
2311       basic_block d;
2312       int c_has_outgoing_fallthru;
2313       int b_has_incoming_fallthru;
2314
2315       /* We must make sure to not munge nesting of exception regions,
2316          lexical blocks, and loop notes.
2317   
2318          The first is taken care of by requiring that the active eh
2319          region at the end of one block always matches the active eh
2320          region at the beginning of the next block.
2321   
2322          The later two are taken care of by squeezing out all the notes.  */
2323   
2324       /* ???  A throw/catch edge (or any abnormal edge) should be rarely
2325          executed and we may want to treat blocks which have two out
2326          edges, one normal, one abnormal as only having one edge for
2327          block merging purposes.  */
2328
2329       for (tmp_edge = c->succ; tmp_edge ; tmp_edge = tmp_edge->succ_next)
2330         if (tmp_edge->flags & EDGE_FALLTHRU)
2331           break;
2332       c_has_outgoing_fallthru = (tmp_edge != NULL);
2333
2334       for (tmp_edge = b->pred; tmp_edge ; tmp_edge = tmp_edge->pred_next)
2335         if (tmp_edge->flags & EDGE_FALLTHRU)
2336           break;
2337       b_has_incoming_fallthru = (tmp_edge != NULL);
2338
2339       /* If B does not have an incoming fallthru, and the exception regions
2340          match, then it can be moved immediately before C without introducing
2341          or modifying jumps.
2342
2343          C can not be the first block, so we do not have to worry about
2344          accessing a non-existent block.  */
2345       d = BASIC_BLOCK (c->index - 1);
2346       if (! b_has_incoming_fallthru
2347           && d->eh_end == b->eh_beg
2348           && b->eh_end == c->eh_beg)
2349         return merge_blocks_move_predecessor_nojumps (b, c);
2350
2351       /* Otherwise, we're going to try to move C after B.  Make sure the
2352          exception regions match.
2353
2354          If B is the last basic block, then we must not try to access the
2355          block structure for block B + 1.  Luckily in that case we do not
2356          need to worry about matching exception regions.  */
2357       d = (b->index + 1 < n_basic_blocks ? BASIC_BLOCK (b->index + 1) : NULL);
2358       if (b->eh_end == c->eh_beg
2359           && (d == NULL || c->eh_end == d->eh_beg))
2360         {
2361           /* If C does not have an outgoing fallthru, then it can be moved
2362              immediately after B without introducing or modifying jumps.  */
2363           if (! c_has_outgoing_fallthru)
2364             return merge_blocks_move_successor_nojumps (b, c);
2365
2366           /* Otherwise, we'll need to insert an extra jump, and possibly
2367              a new block to contain it.  */
2368           /* ??? Not implemented yet.  */
2369         }
2370
2371       return 0;
2372     }
2373 }
2374
2375 /* Top level driver for merge_blocks.  */
2376
2377 static void
2378 try_merge_blocks ()
2379 {
2380   int i;
2381
2382   /* Attempt to merge blocks as made possible by edge removal.  If a block
2383      has only one successor, and the successor has only one predecessor, 
2384      they may be combined.  */
2385
2386   for (i = 0; i < n_basic_blocks; )
2387     {
2388       basic_block c, b = BASIC_BLOCK (i);
2389       edge s;
2390
2391       /* A loop because chains of blocks might be combineable.  */
2392       while ((s = b->succ) != NULL
2393              && s->succ_next == NULL
2394              && (s->flags & EDGE_EH) == 0
2395              && (c = s->dest) != EXIT_BLOCK_PTR
2396              && c->pred->pred_next == NULL
2397              /* If the jump insn has side effects, we can't kill the edge.  */
2398              && (GET_CODE (b->end) != JUMP_INSN
2399                  || onlyjump_p (b->end))
2400              && merge_blocks (s, b, c))
2401         continue;
2402
2403       /* Don't get confused by the index shift caused by deleting blocks.  */
2404       i = b->index + 1;
2405     }
2406 }
2407
2408 /* The given edge should potentially be a fallthru edge.  If that is in
2409    fact true, delete the jump and barriers that are in the way.  */
2410
2411 void
2412 tidy_fallthru_edge (e, b, c)
2413      edge e;
2414      basic_block b, c;
2415 {
2416   rtx q;
2417
2418   /* ??? In a late-running flow pass, other folks may have deleted basic
2419      blocks by nopping out blocks, leaving multiple BARRIERs between here
2420      and the target label. They ought to be chastized and fixed.
2421
2422      We can also wind up with a sequence of undeletable labels between
2423      one block and the next.
2424
2425      So search through a sequence of barriers, labels, and notes for
2426      the head of block C and assert that we really do fall through.  */
2427
2428   if (next_real_insn (b->end) != next_real_insn (PREV_INSN (c->head)))
2429     return;
2430
2431   /* Remove what will soon cease being the jump insn from the source block.
2432      If block B consisted only of this single jump, turn it into a deleted
2433      note.  */
2434   q = b->end;
2435   if (GET_CODE (q) == JUMP_INSN
2436       && (simplejump_p (q)
2437           || (b->succ == e && e->succ_next == NULL)))
2438     {
2439 #ifdef HAVE_cc0
2440       /* If this was a conditional jump, we need to also delete
2441          the insn that set cc0.  */
2442       if (! simplejump_p (q) && condjump_p (q) && sets_cc0_p (PREV_INSN (q)))
2443         q = PREV_INSN (q);
2444 #endif
2445
2446       if (b->head == q)
2447         {
2448           PUT_CODE (q, NOTE);
2449           NOTE_LINE_NUMBER (q) = NOTE_INSN_DELETED;
2450           NOTE_SOURCE_FILE (q) = 0;
2451         }
2452       else
2453         b->end = q = PREV_INSN (q);
2454     }
2455
2456   /* Selectively unlink the sequence.  */
2457   if (q != PREV_INSN (c->head))
2458     flow_delete_insn_chain (NEXT_INSN (q), PREV_INSN (c->head));
2459
2460   e->flags |= EDGE_FALLTHRU;
2461 }
2462
2463 /* Fix up edges that now fall through, or rather should now fall through
2464    but previously required a jump around now deleted blocks.  Simplify
2465    the search by only examining blocks numerically adjacent, since this
2466    is how find_basic_blocks created them.  */
2467
2468 static void
2469 tidy_fallthru_edges ()
2470 {
2471   int i;
2472
2473   for (i = 1; i < n_basic_blocks; ++i)
2474     {
2475       basic_block b = BASIC_BLOCK (i - 1);
2476       basic_block c = BASIC_BLOCK (i);
2477       edge s;
2478
2479       /* We care about simple conditional or unconditional jumps with
2480          a single successor.
2481
2482          If we had a conditional branch to the next instruction when
2483          find_basic_blocks was called, then there will only be one
2484          out edge for the block which ended with the conditional
2485          branch (since we do not create duplicate edges).
2486
2487          Furthermore, the edge will be marked as a fallthru because we
2488          merge the flags for the duplicate edges.  So we do not want to
2489          check that the edge is not a FALLTHRU edge.  */
2490       if ((s = b->succ) != NULL
2491           && s->succ_next == NULL
2492           && s->dest == c
2493           /* If the jump insn has side effects, we can't tidy the edge.  */
2494           && (GET_CODE (b->end) != JUMP_INSN
2495               || onlyjump_p (b->end)))
2496         tidy_fallthru_edge (s, b, c);
2497     }
2498 }
2499 \f
2500 /* Perform data flow analysis.
2501    F is the first insn of the function; FLAGS is a set of PROP_* flags
2502    to be used in accumulating flow info.  */
2503
2504 void
2505 life_analysis (f, file, flags)
2506      rtx f;
2507      FILE *file;
2508      int flags;
2509 {
2510 #ifdef ELIMINABLE_REGS
2511   register int i;
2512   static struct {int from, to; } eliminables[] = ELIMINABLE_REGS;
2513 #endif
2514
2515   /* Record which registers will be eliminated.  We use this in
2516      mark_used_regs.  */
2517
2518   CLEAR_HARD_REG_SET (elim_reg_set);
2519
2520 #ifdef ELIMINABLE_REGS
2521   for (i = 0; i < (int) (sizeof eliminables / sizeof eliminables[0]); i++)
2522     SET_HARD_REG_BIT (elim_reg_set, eliminables[i].from);
2523 #else
2524   SET_HARD_REG_BIT (elim_reg_set, FRAME_POINTER_REGNUM);
2525 #endif
2526
2527   if (! optimize)
2528     flags &= PROP_DEATH_NOTES | PROP_REG_INFO;
2529
2530   /* The post-reload life analysis have (on a global basis) the same
2531      registers live as was computed by reload itself.  elimination
2532      Otherwise offsets and such may be incorrect.
2533
2534      Reload will make some registers as live even though they do not
2535      appear in the rtl.  */
2536   if (reload_completed)
2537     flags &= ~PROP_REG_INFO;
2538
2539   /* We want alias analysis information for local dead store elimination.  */
2540   if (flags & PROP_SCAN_DEAD_CODE)
2541     init_alias_analysis ();
2542
2543   /* Always remove no-op moves.  Do this before other processing so
2544      that we don't have to keep re-scanning them.  */
2545   delete_noop_moves (f);
2546
2547   /* Some targets can emit simpler epilogues if they know that sp was
2548      not ever modified during the function.  After reload, of course,
2549      we've already emitted the epilogue so there's no sense searching.  */
2550   if (! reload_completed)
2551     notice_stack_pointer_modification (f);
2552     
2553   /* Allocate and zero out data structures that will record the
2554      data from lifetime analysis.  */
2555   allocate_reg_life_data ();
2556   allocate_bb_life_data ();
2557
2558   /* Find the set of registers live on function exit.  */
2559   mark_regs_live_at_end (EXIT_BLOCK_PTR->global_live_at_start);
2560
2561   /* "Update" life info from zero.  It'd be nice to begin the
2562      relaxation with just the exit and noreturn blocks, but that set
2563      is not immediately handy.  */
2564
2565   if (flags & PROP_REG_INFO)
2566     memset (regs_ever_live, 0, sizeof(regs_ever_live));
2567   update_life_info (NULL, UPDATE_LIFE_GLOBAL, flags);
2568
2569   /* Clean up.  */
2570   if (flags & PROP_SCAN_DEAD_CODE)
2571     end_alias_analysis ();
2572
2573   if (file)
2574     dump_flow_info (file);
2575
2576   free_basic_block_vars (1);
2577 }
2578
2579 /* A subroutine of verify_wide_reg, called through for_each_rtx.
2580    Search for REGNO.  If found, abort if it is not wider than word_mode.  */
2581
2582 static int
2583 verify_wide_reg_1 (px, pregno)
2584      rtx *px;
2585      void *pregno;
2586 {
2587   rtx x = *px;
2588   unsigned int regno = *(int *) pregno;
2589
2590   if (GET_CODE (x) == REG && REGNO (x) == regno)
2591     {
2592       if (GET_MODE_BITSIZE (GET_MODE (x)) <= BITS_PER_WORD)
2593         abort ();
2594       return 1;
2595     }
2596   return 0;
2597 }
2598
2599 /* A subroutine of verify_local_live_at_start.  Search through insns
2600    between HEAD and END looking for register REGNO.  */
2601
2602 static void
2603 verify_wide_reg (regno, head, end)
2604      int regno;
2605      rtx head, end;
2606 {
2607   while (1)
2608     {
2609       if (GET_RTX_CLASS (GET_CODE (head)) == 'i'
2610           && for_each_rtx (&PATTERN (head), verify_wide_reg_1, &regno))
2611         return;
2612       if (head == end)
2613         break;
2614       head = NEXT_INSN (head);
2615     }
2616
2617   /* We didn't find the register at all.  Something's way screwy.  */
2618   abort ();
2619 }
2620
2621 /* A subroutine of update_life_info.  Verify that there are no untoward
2622    changes in live_at_start during a local update.  */
2623
2624 static void
2625 verify_local_live_at_start (new_live_at_start, bb)
2626      regset new_live_at_start;
2627      basic_block bb;
2628 {
2629   if (reload_completed)
2630     {
2631       /* After reload, there are no pseudos, nor subregs of multi-word
2632          registers.  The regsets should exactly match.  */
2633       if (! REG_SET_EQUAL_P (new_live_at_start, bb->global_live_at_start))
2634         abort ();
2635     }
2636   else
2637     {
2638       int i;
2639
2640       /* Find the set of changed registers.  */
2641       XOR_REG_SET (new_live_at_start, bb->global_live_at_start);
2642
2643       EXECUTE_IF_SET_IN_REG_SET (new_live_at_start, 0, i,
2644         {
2645           /* No registers should die.  */
2646           if (REGNO_REG_SET_P (bb->global_live_at_start, i))
2647             abort ();
2648           /* Verify that the now-live register is wider than word_mode.  */
2649           verify_wide_reg (i, bb->head, bb->end);
2650         });
2651     }
2652 }
2653
2654 /* Updates life information starting with the basic blocks set in BLOCKS.
2655    If BLOCKS is null, consider it to be the universal set.
2656    
2657    If EXTENT is UPDATE_LIFE_LOCAL, such as after splitting or peepholeing,
2658    we are only expecting local modifications to basic blocks.  If we find
2659    extra registers live at the beginning of a block, then we either killed
2660    useful data, or we have a broken split that wants data not provided.
2661    If we find registers removed from live_at_start, that means we have
2662    a broken peephole that is killing a register it shouldn't.
2663
2664    ??? This is not true in one situation -- when a pre-reload splitter
2665    generates subregs of a multi-word pseudo, current life analysis will
2666    lose the kill.  So we _can_ have a pseudo go live.  How irritating.
2667
2668    Including PROP_REG_INFO does not properly refresh regs_ever_live
2669    unless the caller resets it to zero.  */
2670
2671 void
2672 update_life_info (blocks, extent, prop_flags)
2673      sbitmap blocks;
2674      enum update_life_extent extent;
2675      int prop_flags;
2676 {
2677   regset tmp;
2678   regset_head tmp_head;
2679   int i;
2680
2681   tmp = INITIALIZE_REG_SET (tmp_head);
2682
2683   /* For a global update, we go through the relaxation process again.  */
2684   if (extent != UPDATE_LIFE_LOCAL)
2685     {
2686       calculate_global_regs_live (blocks, blocks,
2687                                   prop_flags & PROP_SCAN_DEAD_CODE);
2688
2689       /* If asked, remove notes from the blocks we'll update.  */
2690       if (extent == UPDATE_LIFE_GLOBAL_RM_NOTES)
2691         count_or_remove_death_notes (blocks, 1);
2692     }
2693
2694   if (blocks)
2695     {
2696       EXECUTE_IF_SET_IN_SBITMAP (blocks, 0, i,
2697         {
2698           basic_block bb = BASIC_BLOCK (i);
2699
2700           COPY_REG_SET (tmp, bb->global_live_at_end);
2701           propagate_block (bb, tmp, (regset) NULL, prop_flags);
2702
2703           if (extent == UPDATE_LIFE_LOCAL)
2704             verify_local_live_at_start (tmp, bb);
2705         });
2706     }
2707   else
2708     {
2709       for (i = n_basic_blocks - 1; i >= 0; --i)
2710         {
2711           basic_block bb = BASIC_BLOCK (i);
2712
2713           COPY_REG_SET (tmp, bb->global_live_at_end);
2714           propagate_block (bb, tmp, (regset) NULL, prop_flags);
2715
2716           if (extent == UPDATE_LIFE_LOCAL)
2717             verify_local_live_at_start (tmp, bb);
2718         }
2719     }
2720
2721   FREE_REG_SET (tmp);
2722
2723   if (prop_flags & PROP_REG_INFO)
2724     {
2725       /* The only pseudos that are live at the beginning of the function
2726          are those that were not set anywhere in the function.  local-alloc
2727          doesn't know how to handle these correctly, so mark them as not
2728          local to any one basic block.  */
2729       EXECUTE_IF_SET_IN_REG_SET (ENTRY_BLOCK_PTR->global_live_at_end,
2730                                  FIRST_PSEUDO_REGISTER, i,
2731                                  { REG_BASIC_BLOCK (i) = REG_BLOCK_GLOBAL; });
2732
2733       /* We have a problem with any pseudoreg that lives across the setjmp. 
2734          ANSI says that if a user variable does not change in value between
2735          the setjmp and the longjmp, then the longjmp preserves it.  This
2736          includes longjmp from a place where the pseudo appears dead.
2737          (In principle, the value still exists if it is in scope.)
2738          If the pseudo goes in a hard reg, some other value may occupy
2739          that hard reg where this pseudo is dead, thus clobbering the pseudo.
2740          Conclusion: such a pseudo must not go in a hard reg.  */
2741       EXECUTE_IF_SET_IN_REG_SET (regs_live_at_setjmp,
2742                                  FIRST_PSEUDO_REGISTER, i,
2743                                  {
2744                                    if (regno_reg_rtx[i] != 0)
2745                                      {
2746                                        REG_LIVE_LENGTH (i) = -1;
2747                                        REG_BASIC_BLOCK (i) = REG_BLOCK_UNKNOWN;
2748                                      }
2749                                  });
2750     }
2751 }
2752
2753 /* Free the variables allocated by find_basic_blocks.
2754
2755    KEEP_HEAD_END_P is non-zero if basic_block_info is not to be freed.  */
2756
2757 void
2758 free_basic_block_vars (keep_head_end_p)
2759      int keep_head_end_p;
2760 {
2761   if (basic_block_for_insn)
2762     {
2763       VARRAY_FREE (basic_block_for_insn);
2764       basic_block_for_insn = NULL;
2765     }
2766
2767   if (! keep_head_end_p)
2768     {
2769       clear_edges ();
2770       VARRAY_FREE (basic_block_info);
2771       n_basic_blocks = 0;
2772
2773       ENTRY_BLOCK_PTR->aux = NULL;
2774       ENTRY_BLOCK_PTR->global_live_at_end = NULL;
2775       EXIT_BLOCK_PTR->aux = NULL;
2776       EXIT_BLOCK_PTR->global_live_at_start = NULL;
2777     }
2778 }
2779
2780 /* Return nonzero if the destination of SET equals the source.  */
2781 static int
2782 set_noop_p (set)
2783      rtx set;
2784 {
2785   rtx src = SET_SRC (set);
2786   rtx dst = SET_DEST (set);
2787
2788   if (GET_CODE (src) == SUBREG && GET_CODE (dst) == SUBREG)
2789     {
2790       if (SUBREG_WORD (src) != SUBREG_WORD (dst))
2791         return 0;
2792       src = SUBREG_REG (src);
2793       dst = SUBREG_REG (dst);
2794     }
2795
2796   return (GET_CODE (src) == REG && GET_CODE (dst) == REG
2797           && REGNO (src) == REGNO (dst));
2798 }
2799
2800 /* Return nonzero if an insn consists only of SETs, each of which only sets a
2801    value to itself.  */
2802 static int
2803 noop_move_p (insn)
2804      rtx insn;
2805 {
2806   rtx pat = PATTERN (insn);
2807
2808   /* Insns carrying these notes are useful later on.  */
2809   if (find_reg_note (insn, REG_EQUAL, NULL_RTX))
2810     return 0;
2811
2812   if (GET_CODE (pat) == SET && set_noop_p (pat))
2813     return 1;
2814
2815   if (GET_CODE (pat) == PARALLEL)
2816     {
2817       int i;
2818       /* If nothing but SETs of registers to themselves,
2819          this insn can also be deleted.  */
2820       for (i = 0; i < XVECLEN (pat, 0); i++)
2821         {
2822           rtx tem = XVECEXP (pat, 0, i);
2823
2824           if (GET_CODE (tem) == USE
2825               || GET_CODE (tem) == CLOBBER)
2826             continue;
2827
2828           if (GET_CODE (tem) != SET || ! set_noop_p (tem))
2829             return 0;
2830         }
2831
2832       return 1;
2833     }
2834   return 0;
2835 }
2836
2837 /* Delete any insns that copy a register to itself.  */
2838
2839 static void
2840 delete_noop_moves (f)
2841      rtx f;
2842 {
2843   rtx insn;
2844   for (insn = f; insn; insn = NEXT_INSN (insn))
2845     {
2846       if (GET_CODE (insn) == INSN && noop_move_p (insn))
2847         {
2848           PUT_CODE (insn, NOTE);
2849           NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
2850           NOTE_SOURCE_FILE (insn) = 0;
2851         }
2852     }
2853 }
2854
2855 /* Determine if the stack pointer is constant over the life of the function.
2856    Only useful before prologues have been emitted.  */
2857
2858 static void
2859 notice_stack_pointer_modification_1 (x, pat, data)
2860      rtx x;
2861      rtx pat ATTRIBUTE_UNUSED;
2862      void *data ATTRIBUTE_UNUSED;
2863 {
2864   if (x == stack_pointer_rtx
2865       /* The stack pointer is only modified indirectly as the result
2866          of a push until later in flow.  See the comments in rtl.texi
2867          regarding Embedded Side-Effects on Addresses.  */
2868       || (GET_CODE (x) == MEM
2869           && (GET_CODE (XEXP (x, 0)) == PRE_DEC
2870               || GET_CODE (XEXP (x, 0)) == PRE_INC
2871               || GET_CODE (XEXP (x, 0)) == POST_DEC
2872               || GET_CODE (XEXP (x, 0)) == POST_INC)
2873           && XEXP (XEXP (x, 0), 0) == stack_pointer_rtx))
2874     current_function_sp_is_unchanging = 0;
2875 }
2876
2877 static void
2878 notice_stack_pointer_modification (f)
2879      rtx f;
2880 {
2881   rtx insn;
2882
2883   /* Assume that the stack pointer is unchanging if alloca hasn't
2884      been used.  */
2885   current_function_sp_is_unchanging = !current_function_calls_alloca;
2886   if (! current_function_sp_is_unchanging)
2887     return;
2888
2889   for (insn = f; insn; insn = NEXT_INSN (insn))
2890     {
2891       if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
2892         {
2893           /* Check if insn modifies the stack pointer.  */
2894           note_stores (PATTERN (insn), notice_stack_pointer_modification_1,
2895                        NULL);
2896           if (! current_function_sp_is_unchanging)
2897             return;
2898         }
2899     }
2900 }
2901
2902 /* Mark a register in SET.  Hard registers in large modes get all
2903    of their component registers set as well.  */
2904 static void
2905 mark_reg (reg, xset)
2906      rtx reg;
2907      void *xset;
2908 {
2909   regset set = (regset) xset;
2910   int regno = REGNO (reg);
2911
2912   if (GET_MODE (reg) == BLKmode)
2913     abort ();
2914
2915   SET_REGNO_REG_SET (set, regno);
2916   if (regno < FIRST_PSEUDO_REGISTER)
2917     {
2918       int n = HARD_REGNO_NREGS (regno, GET_MODE (reg));
2919       while (--n > 0)
2920         SET_REGNO_REG_SET (set, regno + n);
2921     }
2922 }
2923
2924 /* Mark those regs which are needed at the end of the function as live
2925    at the end of the last basic block.  */
2926 static void
2927 mark_regs_live_at_end (set)
2928      regset set;
2929 {
2930   int i;
2931
2932   /* If exiting needs the right stack value, consider the stack pointer
2933      live at the end of the function.  */
2934   if ((HAVE_epilogue && reload_completed)
2935       || ! EXIT_IGNORE_STACK
2936       || (! FRAME_POINTER_REQUIRED
2937           && ! current_function_calls_alloca
2938           && flag_omit_frame_pointer)
2939       || current_function_sp_is_unchanging)
2940     {
2941       SET_REGNO_REG_SET (set, STACK_POINTER_REGNUM);
2942     }
2943
2944   /* Mark the frame pointer if needed at the end of the function.  If
2945      we end up eliminating it, it will be removed from the live list
2946      of each basic block by reload.  */
2947
2948   if (! reload_completed || frame_pointer_needed)
2949     {
2950       SET_REGNO_REG_SET (set, FRAME_POINTER_REGNUM);
2951 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
2952       /* If they are different, also mark the hard frame pointer as live */
2953       SET_REGNO_REG_SET (set, HARD_FRAME_POINTER_REGNUM);
2954 #endif      
2955     }
2956
2957 #ifdef PIC_OFFSET_TABLE_REGNUM
2958 #ifndef PIC_OFFSET_TABLE_REG_CALL_CLOBBERED
2959   /* Many architectures have a GP register even without flag_pic.
2960      Assume the pic register is not in use, or will be handled by
2961      other means, if it is not fixed.  */
2962   if (fixed_regs[PIC_OFFSET_TABLE_REGNUM])
2963     SET_REGNO_REG_SET (set, PIC_OFFSET_TABLE_REGNUM);
2964 #endif
2965 #endif
2966
2967   /* Mark all global registers, and all registers used by the epilogue
2968      as being live at the end of the function since they may be
2969      referenced by our caller.  */
2970   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
2971     if (global_regs[i]
2972 #ifdef EPILOGUE_USES
2973         || EPILOGUE_USES (i)
2974 #endif
2975         )
2976       SET_REGNO_REG_SET (set, i);
2977
2978   /* Mark all call-saved registers that we actaully used.  */
2979   if (HAVE_epilogue && reload_completed)
2980     {
2981       for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
2982         if (! call_used_regs[i] && regs_ever_live[i])
2983           SET_REGNO_REG_SET (set, i);
2984     }
2985
2986   /* Mark function return value.  */
2987   diddle_return_value (mark_reg, set);
2988 }
2989
2990 /* Callback function for for_each_successor_phi.  DATA is a regset.
2991    Sets the SRC_REGNO, the regno of the phi alternative for phi node
2992    INSN, in the regset.  */
2993
2994 static int
2995 set_phi_alternative_reg (insn, dest_regno, src_regno, data)
2996      rtx insn ATTRIBUTE_UNUSED;
2997      int dest_regno ATTRIBUTE_UNUSED;
2998      int src_regno;
2999      void *data;
3000 {
3001   regset live = (regset) data;
3002   SET_REGNO_REG_SET (live, src_regno);
3003   return 0;
3004 }
3005
3006 /* Propagate global life info around the graph of basic blocks.  Begin
3007    considering blocks with their corresponding bit set in BLOCKS_IN. 
3008    If BLOCKS_IN is null, consider it the universal set.
3009
3010    BLOCKS_OUT is set for every block that was changed.  */
3011
3012 static void
3013 calculate_global_regs_live (blocks_in, blocks_out, flags)
3014      sbitmap blocks_in, blocks_out;
3015      int flags;
3016 {
3017   basic_block *queue, *qhead, *qtail, *qend;
3018   regset tmp, new_live_at_end;
3019   regset_head tmp_head;
3020   regset_head new_live_at_end_head;
3021   int i;
3022
3023   tmp = INITIALIZE_REG_SET (tmp_head);
3024   new_live_at_end = INITIALIZE_REG_SET (new_live_at_end_head);
3025
3026   /* Create a worklist.  Allocate an extra slot for ENTRY_BLOCK, and one
3027      because the `head == tail' style test for an empty queue doesn't 
3028      work with a full queue.  */
3029   queue = (basic_block *) xmalloc ((n_basic_blocks + 2) * sizeof (*queue));
3030   qtail = queue;
3031   qhead = qend = queue + n_basic_blocks + 2;
3032
3033   /* Clear out the garbage that might be hanging out in bb->aux.  */
3034   for (i = n_basic_blocks - 1; i >= 0; --i)
3035     BASIC_BLOCK (i)->aux = NULL;
3036
3037   /* Queue the blocks set in the initial mask.  Do this in reverse block
3038      number order so that we are more likely for the first round to do 
3039      useful work.  We use AUX non-null to flag that the block is queued.  */
3040   if (blocks_in)
3041     {
3042       EXECUTE_IF_SET_IN_SBITMAP (blocks_in, 0, i,
3043         {
3044           basic_block bb = BASIC_BLOCK (i);
3045           *--qhead = bb;
3046           bb->aux = bb;
3047         });
3048     }
3049   else
3050     {
3051       for (i = 0; i < n_basic_blocks; ++i)
3052         {
3053           basic_block bb = BASIC_BLOCK (i);
3054           *--qhead = bb;
3055           bb->aux = bb;
3056         }
3057     }
3058
3059   if (blocks_out)
3060     sbitmap_zero (blocks_out);
3061
3062   while (qhead != qtail)
3063     {
3064       int rescan, changed;
3065       basic_block bb;
3066       edge e;
3067
3068       bb = *qhead++;
3069       if (qhead == qend)
3070         qhead = queue;
3071       bb->aux = NULL;
3072
3073       /* Begin by propogating live_at_start from the successor blocks.  */
3074       CLEAR_REG_SET (new_live_at_end);
3075       for (e = bb->succ; e ; e = e->succ_next)
3076         {
3077           basic_block sb = e->dest;
3078           IOR_REG_SET (new_live_at_end, sb->global_live_at_start);
3079         }
3080
3081       /* Force the stack pointer to be live -- which might not already be 
3082          the case for blocks within infinite loops.  */
3083       SET_REGNO_REG_SET (new_live_at_end, STACK_POINTER_REGNUM);
3084
3085       /* Regs used in phi nodes are not included in
3086          global_live_at_start, since they are live only along a
3087          particular edge.  Set those regs that are live because of a
3088          phi node alternative corresponding to this particular block.  */
3089       for_each_successor_phi (bb, &set_phi_alternative_reg, 
3090                               new_live_at_end);
3091
3092       if (bb == ENTRY_BLOCK_PTR)
3093         {
3094           COPY_REG_SET (bb->global_live_at_end, new_live_at_end);
3095           continue;
3096         }
3097
3098       /* On our first pass through this block, we'll go ahead and continue. 
3099          Recognize first pass by local_set NULL.  On subsequent passes, we
3100          get to skip out early if live_at_end wouldn't have changed.  */
3101
3102       if (bb->local_set == NULL)
3103         {
3104           bb->local_set = OBSTACK_ALLOC_REG_SET (function_obstack);
3105           rescan = 1;
3106         }
3107       else
3108         {
3109           /* If any bits were removed from live_at_end, we'll have to
3110              rescan the block.  This wouldn't be necessary if we had
3111              precalculated local_live, however with PROP_SCAN_DEAD_CODE
3112              local_live is really dependant on live_at_end.  */
3113           CLEAR_REG_SET (tmp);
3114           rescan = bitmap_operation (tmp, bb->global_live_at_end,
3115                                      new_live_at_end, BITMAP_AND_COMPL);
3116
3117           if (! rescan)
3118             {
3119               /* Find the set of changed bits.  Take this opportunity
3120                  to notice that this set is empty and early out.  */
3121               CLEAR_REG_SET (tmp);
3122               changed = bitmap_operation (tmp, bb->global_live_at_end,
3123                                           new_live_at_end, BITMAP_XOR);
3124               if (! changed)
3125                 continue;
3126
3127               /* If any of the changed bits overlap with local_set,
3128                  we'll have to rescan the block.  Detect overlap by
3129                  the AND with ~local_set turning off bits.  */
3130               rescan = bitmap_operation (tmp, tmp, bb->local_set,
3131                                          BITMAP_AND_COMPL);
3132             }
3133         }
3134
3135       /* Let our caller know that BB changed enough to require its
3136          death notes updated.  */
3137       if (blocks_out)
3138         SET_BIT (blocks_out, bb->index);
3139
3140       if (! rescan)
3141         {
3142           /* Add to live_at_start the set of all registers in
3143              new_live_at_end that aren't in the old live_at_end.  */
3144
3145           bitmap_operation (tmp, new_live_at_end, bb->global_live_at_end,
3146                             BITMAP_AND_COMPL);
3147           COPY_REG_SET (bb->global_live_at_end, new_live_at_end);
3148
3149           changed = bitmap_operation (bb->global_live_at_start,
3150                                       bb->global_live_at_start,
3151                                       tmp, BITMAP_IOR);
3152           if (! changed)
3153             continue;
3154         }
3155       else
3156         {
3157           COPY_REG_SET (bb->global_live_at_end, new_live_at_end);
3158
3159           /* Rescan the block insn by insn to turn (a copy of) live_at_end
3160              into live_at_start.  */
3161           propagate_block (bb, new_live_at_end, bb->local_set, flags);
3162
3163           /* If live_at start didn't change, no need to go farther.  */
3164           if (REG_SET_EQUAL_P (bb->global_live_at_start, new_live_at_end))
3165             continue;
3166
3167           COPY_REG_SET (bb->global_live_at_start, new_live_at_end);
3168         }
3169
3170       /* Queue all predecessors of BB so that we may re-examine
3171          their live_at_end.  */
3172       for (e = bb->pred; e ; e = e->pred_next)
3173         {
3174           basic_block pb = e->src;
3175           if (pb->aux == NULL)
3176             {
3177               *qtail++ = pb;
3178               if (qtail == qend)
3179                 qtail = queue;
3180               pb->aux = pb;
3181             }
3182         }
3183     }
3184
3185   FREE_REG_SET (tmp);
3186   FREE_REG_SET (new_live_at_end);
3187
3188   if (blocks_out)
3189     {
3190       EXECUTE_IF_SET_IN_SBITMAP (blocks_out, 0, i,
3191         {
3192           basic_block bb = BASIC_BLOCK (i);
3193           FREE_REG_SET (bb->local_set);
3194         });
3195     }
3196   else
3197     {
3198       for (i = n_basic_blocks - 1; i >= 0; --i)
3199         {
3200           basic_block bb = BASIC_BLOCK (i);
3201           FREE_REG_SET (bb->local_set);
3202         }
3203     }
3204
3205   free (queue);
3206 }
3207 \f
3208 /* Subroutines of life analysis.  */
3209
3210 /* Allocate the permanent data structures that represent the results
3211    of life analysis.  Not static since used also for stupid life analysis.  */
3212
3213 void
3214 allocate_bb_life_data ()
3215 {
3216   register int i;
3217
3218   for (i = 0; i < n_basic_blocks; i++)
3219     {
3220       basic_block bb = BASIC_BLOCK (i);
3221
3222       bb->global_live_at_start = OBSTACK_ALLOC_REG_SET (function_obstack);
3223       bb->global_live_at_end = OBSTACK_ALLOC_REG_SET (function_obstack);
3224     }
3225
3226   ENTRY_BLOCK_PTR->global_live_at_end
3227     = OBSTACK_ALLOC_REG_SET (function_obstack);
3228   EXIT_BLOCK_PTR->global_live_at_start
3229     = OBSTACK_ALLOC_REG_SET (function_obstack);
3230
3231   regs_live_at_setjmp = OBSTACK_ALLOC_REG_SET (function_obstack);
3232 }
3233
3234 void
3235 allocate_reg_life_data ()
3236 {
3237   int i;
3238
3239   max_regno = max_reg_num ();
3240
3241   /* Recalculate the register space, in case it has grown.  Old style
3242      vector oriented regsets would set regset_{size,bytes} here also.  */
3243   allocate_reg_info (max_regno, FALSE, FALSE);
3244
3245   /* Reset all the data we'll collect in propagate_block and its 
3246      subroutines.  */
3247   for (i = 0; i < max_regno; i++)
3248     {
3249       REG_N_SETS (i) = 0;
3250       REG_N_REFS (i) = 0;
3251       REG_N_DEATHS (i) = 0;
3252       REG_N_CALLS_CROSSED (i) = 0;
3253       REG_LIVE_LENGTH (i) = 0;
3254       REG_BASIC_BLOCK (i) = REG_BLOCK_UNKNOWN;
3255     }
3256 }
3257
3258 /* Delete dead instructions for propagate_block.  */
3259
3260 static void
3261 propagate_block_delete_insn (bb, insn)
3262      basic_block bb;
3263      rtx insn;
3264 {
3265   rtx inote = find_reg_note (insn, REG_LABEL, NULL_RTX);
3266
3267   /* If the insn referred to a label, and that label was attached to
3268      an ADDR_VEC, it's safe to delete the ADDR_VEC.  In fact, it's
3269      pretty much mandatory to delete it, because the ADDR_VEC may be
3270      referencing labels that no longer exist.  */
3271
3272   if (inote)
3273     {
3274       rtx label = XEXP (inote, 0);
3275       rtx next;
3276
3277       if (LABEL_NUSES (label) == 1
3278           && (next = next_nonnote_insn (label)) != NULL
3279           && GET_CODE (next) == JUMP_INSN
3280           && (GET_CODE (PATTERN (next)) == ADDR_VEC
3281               || GET_CODE (PATTERN (next)) == ADDR_DIFF_VEC))
3282         {
3283           rtx pat = PATTERN (next);
3284           int diff_vec_p = GET_CODE (pat) == ADDR_DIFF_VEC;
3285           int len = XVECLEN (pat, diff_vec_p);
3286           int i;
3287
3288           for (i = 0; i < len; i++)
3289             LABEL_NUSES (XEXP (XVECEXP (pat, diff_vec_p, i), 0))--;
3290
3291           flow_delete_insn (next);
3292         }
3293     }
3294
3295   if (bb->end == insn)
3296     bb->end = PREV_INSN (insn);
3297   flow_delete_insn (insn);
3298 }
3299
3300 /* Delete dead libcalls for propagate_block.  Return the insn
3301    before the libcall.  */
3302
3303 static rtx
3304 propagate_block_delete_libcall (bb, insn, note)
3305      basic_block bb;
3306      rtx insn, note;
3307 {
3308   rtx first = XEXP (note, 0);
3309   rtx before = PREV_INSN (first);
3310
3311   if (insn == bb->end)
3312     bb->end = before;
3313   
3314   flow_delete_insn_chain (first, insn);
3315   return before;
3316 }
3317
3318 /* Update the life-status of regs for one insn.  Return the previous insn.  */
3319
3320 rtx
3321 propagate_one_insn (pbi, insn)
3322      struct propagate_block_info *pbi;
3323      rtx insn;
3324 {
3325   rtx prev = PREV_INSN (insn);
3326   int flags = pbi->flags;
3327   int insn_is_dead = 0;
3328   int libcall_is_dead = 0;
3329   rtx note;
3330   int i;
3331
3332   if (! INSN_P (insn))
3333     return prev;
3334
3335   note = find_reg_note (insn, REG_RETVAL, NULL_RTX);
3336   if (flags & PROP_SCAN_DEAD_CODE)
3337     {
3338       insn_is_dead = insn_dead_p (pbi, PATTERN (insn), 0,
3339                                   REG_NOTES (insn));
3340       libcall_is_dead = (insn_is_dead && note != 0
3341                          && libcall_dead_p (pbi, PATTERN (insn),
3342                                             note, insn));
3343     }
3344
3345   /* We almost certainly don't want to delete prologue or epilogue
3346      instructions.  Warn about probable compiler losage.  */
3347   if (insn_is_dead
3348       && reload_completed
3349       && (((HAVE_epilogue || HAVE_prologue)
3350            && prologue_epilogue_contains (insn))
3351           || (HAVE_sibcall_epilogue
3352               && sibcall_epilogue_contains (insn))))
3353     {
3354       if (flags & PROP_KILL_DEAD_CODE)
3355         { 
3356           warning ("ICE: would have deleted prologue/epilogue insn");
3357           if (!inhibit_warnings)
3358             debug_rtx (insn);
3359         }
3360       libcall_is_dead = insn_is_dead = 0;
3361     }
3362
3363   /* If an instruction consists of just dead store(s) on final pass,
3364      delete it.  */
3365   if ((flags & PROP_KILL_DEAD_CODE) && insn_is_dead)
3366     {
3367       /* Record sets.  Do this even for dead instructions, since they
3368          would have killed the values if they hadn't been deleted.  */
3369       mark_set_regs (pbi, PATTERN (insn), insn);
3370
3371       /* CC0 is now known to be dead.  Either this insn used it,
3372          in which case it doesn't anymore, or clobbered it,
3373          so the next insn can't use it.  */
3374       pbi->cc0_live = 0;
3375
3376       if (libcall_is_dead)
3377         {
3378           prev = propagate_block_delete_libcall (pbi->bb, insn, note);
3379           insn = NEXT_INSN (prev);
3380         }
3381       else
3382         propagate_block_delete_insn (pbi->bb, insn);
3383
3384       return prev;
3385     }
3386
3387   /* See if this is an increment or decrement that can be merged into
3388      a following memory address.  */
3389 #ifdef AUTO_INC_DEC
3390   {
3391     register rtx x = single_set (insn);
3392
3393     /* Does this instruction increment or decrement a register?  */
3394     if (!reload_completed
3395         && (flags & PROP_AUTOINC)
3396         && x != 0
3397         && GET_CODE (SET_DEST (x)) == REG
3398         && (GET_CODE (SET_SRC (x)) == PLUS
3399             || GET_CODE (SET_SRC (x)) == MINUS)
3400         && XEXP (SET_SRC (x), 0) == SET_DEST (x)
3401         && GET_CODE (XEXP (SET_SRC (x), 1)) == CONST_INT
3402         /* Ok, look for a following memory ref we can combine with.
3403            If one is found, change the memory ref to a PRE_INC
3404            or PRE_DEC, cancel this insn, and return 1.
3405            Return 0 if nothing has been done.  */
3406         && try_pre_increment_1 (pbi, insn))
3407       return prev;
3408   }
3409 #endif /* AUTO_INC_DEC */
3410
3411   CLEAR_REG_SET (pbi->new_set);
3412
3413   /* If this is not the final pass, and this insn is copying the value of
3414      a library call and it's dead, don't scan the insns that perform the
3415      library call, so that the call's arguments are not marked live.  */
3416   if (libcall_is_dead)
3417     {
3418       /* Record the death of the dest reg.  */
3419       mark_set_regs (pbi, PATTERN (insn), insn);
3420
3421       insn = XEXP (note, 0);
3422       return PREV_INSN (insn);
3423     }
3424   else if (GET_CODE (PATTERN (insn)) == SET
3425            && SET_DEST (PATTERN (insn)) == stack_pointer_rtx
3426            && GET_CODE (SET_SRC (PATTERN (insn))) == PLUS
3427            && XEXP (SET_SRC (PATTERN (insn)), 0) == stack_pointer_rtx
3428            && GET_CODE (XEXP (SET_SRC (PATTERN (insn)), 1)) == CONST_INT)
3429     /* We have an insn to pop a constant amount off the stack.
3430        (Such insns use PLUS regardless of the direction of the stack,
3431        and any insn to adjust the stack by a constant is always a pop.)
3432        These insns, if not dead stores, have no effect on life.  */
3433     ;
3434   else
3435     {
3436       /* Any regs live at the time of a call instruction must not go
3437          in a register clobbered by calls.  Find all regs now live and
3438          record this for them.  */
3439
3440       if (GET_CODE (insn) == CALL_INSN && (flags & PROP_REG_INFO))
3441         EXECUTE_IF_SET_IN_REG_SET (pbi->reg_live, 0, i,
3442                                    { REG_N_CALLS_CROSSED (i)++; });
3443
3444       /* Record sets.  Do this even for dead instructions, since they
3445          would have killed the values if they hadn't been deleted.  */
3446       mark_set_regs (pbi, PATTERN (insn), insn);
3447
3448       if (GET_CODE (insn) == CALL_INSN)
3449         {
3450           register int i;
3451           rtx note, cond;
3452
3453           cond = NULL_RTX;
3454           if (GET_CODE (PATTERN (insn)) == COND_EXEC)
3455             cond = COND_EXEC_TEST (PATTERN (insn));
3456
3457           /* Non-constant calls clobber memory.  */
3458           if (! CONST_CALL_P (insn))
3459             free_EXPR_LIST_list (&pbi->mem_set_list);
3460
3461           /* There may be extra registers to be clobbered.  */
3462           for (note = CALL_INSN_FUNCTION_USAGE (insn);
3463                note;
3464                note = XEXP (note, 1))
3465             if (GET_CODE (XEXP (note, 0)) == CLOBBER)
3466               mark_set_1 (pbi, CLOBBER, XEXP (XEXP (note, 0), 0),
3467                           cond, insn, pbi->flags);
3468
3469           /* Calls change all call-used and global registers.  */
3470           for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3471             if (call_used_regs[i] && ! global_regs[i]
3472                 && ! fixed_regs[i])
3473               {
3474                 /* We do not want REG_UNUSED notes for these registers.  */
3475                 mark_set_1 (pbi, CLOBBER, gen_rtx_REG (reg_raw_mode[i], i),
3476                             cond, insn, pbi->flags & ~PROP_DEATH_NOTES);
3477               }
3478         }
3479
3480       /* If an insn doesn't use CC0, it becomes dead since we assume
3481          that every insn clobbers it.  So show it dead here;
3482          mark_used_regs will set it live if it is referenced.  */
3483       pbi->cc0_live = 0;
3484
3485       /* Record uses.  */
3486       if (! insn_is_dead)
3487         mark_used_regs (pbi, PATTERN (insn), NULL_RTX, insn);
3488
3489       /* Sometimes we may have inserted something before INSN (such as a move)
3490          when we make an auto-inc.  So ensure we will scan those insns.  */
3491 #ifdef AUTO_INC_DEC
3492       prev = PREV_INSN (insn);
3493 #endif
3494
3495       if (! insn_is_dead && GET_CODE (insn) == CALL_INSN)
3496         {
3497           register int i;
3498           rtx note, cond;
3499
3500           cond = NULL_RTX;
3501           if (GET_CODE (PATTERN (insn)) == COND_EXEC)
3502             cond = COND_EXEC_TEST (PATTERN (insn));
3503
3504           /* Calls use their arguments.  */
3505           for (note = CALL_INSN_FUNCTION_USAGE (insn);
3506                note;
3507                note = XEXP (note, 1))
3508             if (GET_CODE (XEXP (note, 0)) == USE)
3509               mark_used_regs (pbi, XEXP (XEXP (note, 0), 0),
3510                               cond, insn);
3511
3512           /* The stack ptr is used (honorarily) by a CALL insn.  */
3513           SET_REGNO_REG_SET (pbi->reg_live, STACK_POINTER_REGNUM);
3514
3515           /* Calls may also reference any of the global registers,
3516              so they are made live.  */
3517           for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3518             if (global_regs[i])
3519               mark_used_reg (pbi, gen_rtx_REG (reg_raw_mode[i], i),
3520                              cond, insn);
3521         }
3522     }
3523
3524   /* On final pass, update counts of how many insns in which each reg
3525      is live.  */
3526   if (flags & PROP_REG_INFO)
3527     EXECUTE_IF_SET_IN_REG_SET (pbi->reg_live, 0, i,
3528                                { REG_LIVE_LENGTH (i)++; });
3529
3530   return prev;
3531 }
3532
3533 /* Initialize a propagate_block_info struct for public consumption.
3534    Note that the structure itself is opaque to this file, but that
3535    the user can use the regsets provided here.  */
3536
3537 struct propagate_block_info *
3538 init_propagate_block_info (bb, live, local_set, flags)
3539      basic_block bb;
3540      regset live;
3541      regset local_set;
3542      int flags;
3543 {
3544   struct propagate_block_info *pbi = xmalloc (sizeof(*pbi));
3545
3546   pbi->bb = bb;
3547   pbi->reg_live = live;
3548   pbi->mem_set_list = NULL_RTX;
3549   pbi->local_set = local_set;
3550   pbi->cc0_live = 0;
3551   pbi->flags = flags;
3552
3553   if (flags & (PROP_LOG_LINKS | PROP_AUTOINC))
3554     pbi->reg_next_use = (rtx *) xcalloc (max_reg_num (), sizeof (rtx));
3555   else
3556     pbi->reg_next_use = NULL;
3557
3558   pbi->new_set = BITMAP_XMALLOC ();
3559
3560 #ifdef HAVE_conditional_execution
3561   pbi->reg_cond_dead = splay_tree_new (splay_tree_compare_ints, NULL,
3562                                        free_reg_cond_life_info);
3563   pbi->reg_cond_reg = BITMAP_XMALLOC ();
3564
3565   /* If this block ends in a conditional branch, for each register live
3566      from one side of the branch and not the other, record the register
3567      as conditionally dead.  */
3568   if (GET_CODE (bb->end) == JUMP_INSN
3569       && condjump_p (bb->end)
3570       && ! simplejump_p (bb->end))
3571     {
3572       regset_head diff_head;
3573       regset diff = INITIALIZE_REG_SET (diff_head);
3574       basic_block bb_true, bb_false;
3575       rtx cond_true, cond_false;
3576       int i;
3577
3578       /* Identify the successor blocks.  */
3579       bb_false = bb->succ->succ_next->dest;
3580       bb_true = bb->succ->dest;
3581       if (bb->succ->flags & EDGE_FALLTHRU)
3582         {
3583           basic_block t = bb_false;
3584           bb_false = bb_true;
3585           bb_true = t;
3586         }
3587       else if (! (bb->succ->succ_next->flags & EDGE_FALLTHRU))
3588         abort ();
3589      
3590       /* Extract the condition from the branch.  */
3591       cond_true = XEXP (SET_SRC (PATTERN (bb->end)), 0);
3592       cond_false = gen_rtx_fmt_ee (reverse_condition (GET_CODE (cond_true)),
3593                                    GET_MODE (cond_true), XEXP (cond_true, 0),
3594                                    XEXP (cond_true, 1));
3595       if (GET_CODE (XEXP (SET_SRC (PATTERN (bb->end)), 1)) == PC)
3596         {
3597           rtx t = cond_false;
3598           cond_false = cond_true;
3599           cond_true = t;
3600         }
3601
3602       /* Compute which register lead different lives in the successors.  */
3603       if (bitmap_operation (diff, bb_true->global_live_at_start,
3604                             bb_false->global_live_at_start, BITMAP_XOR))
3605         {
3606           if (GET_CODE (XEXP (cond_true, 0)) != REG)
3607             abort ();
3608           SET_REGNO_REG_SET (pbi.reg_cond_reg, REGNO (XEXP (cond_true, 0)));
3609
3610           /* For each such register, mark it conditionally dead.  */
3611           EXECUTE_IF_SET_IN_REG_SET
3612             (diff, 0, i,
3613              {
3614                struct reg_cond_life_info *rcli;
3615                rtx cond;
3616
3617                rcli = (struct reg_cond_life_info *) xmalloc (sizeof (*rcli));
3618
3619                if (REGNO_REG_SET_P (bb_true->global_live_at_start, i))
3620                  cond = cond_false;
3621                else
3622                  cond = cond_true;
3623                rcli->condition = alloc_EXPR_LIST (0, cond, NULL_RTX);
3624
3625                splay_tree_insert (pbi.reg_cond_dead, i,
3626                                   (splay_tree_value) rcli);
3627              });
3628         }
3629
3630       FREE_REG_SET (diff);
3631     }
3632 #endif
3633
3634   return pbi;
3635 }
3636
3637 /* Release a propagate_block_info struct.  */
3638
3639 void
3640 free_propagate_block_info (pbi)
3641      struct propagate_block_info *pbi;
3642 {
3643   free_EXPR_LIST_list (&pbi->mem_set_list);
3644
3645   BITMAP_XFREE (pbi->new_set);
3646
3647 #ifdef HAVE_conditional_execution
3648   splay_tree_delete (pbi->reg_cond_dead);
3649   BITMAP_XFREE (pbi->reg_cond_reg);
3650 #endif
3651
3652   if (pbi->reg_next_use)
3653     free (pbi->reg_next_use);
3654
3655   free (pbi);
3656 }
3657
3658 /* Compute the registers live at the beginning of a basic block BB from
3659    those live at the end.
3660
3661    When called, REG_LIVE contains those live at the end.  On return, it
3662    contains those live at the beginning.
3663
3664    LOCAL_SET, if non-null, will be set with all registers killed by 
3665    this basic block.  */
3666
3667 void
3668 propagate_block (bb, live, local_set, flags)
3669      basic_block bb;
3670      regset live;
3671      regset local_set;
3672      int flags;
3673 {
3674   struct propagate_block_info *pbi;
3675   rtx insn, prev;
3676   
3677   pbi = init_propagate_block_info (bb, live, local_set, flags);
3678
3679   if (flags & PROP_REG_INFO)
3680     {
3681       register int i;
3682
3683       /* Process the regs live at the end of the block.
3684          Mark them as not local to any one basic block. */
3685       EXECUTE_IF_SET_IN_REG_SET (live, 0, i,
3686                                  { REG_BASIC_BLOCK (i) = REG_BLOCK_GLOBAL; });
3687     }
3688
3689   /* Scan the block an insn at a time from end to beginning.  */
3690
3691   for (insn = bb->end; ; insn = prev)
3692     {
3693       /* If this is a call to `setjmp' et al, warn if any
3694          non-volatile datum is live.  */
3695       if ((flags & PROP_REG_INFO)
3696           && GET_CODE (insn) == NOTE
3697           && NOTE_LINE_NUMBER (insn) == NOTE_INSN_SETJMP)
3698         IOR_REG_SET (regs_live_at_setjmp, pbi->reg_live);
3699
3700       prev = propagate_one_insn (pbi, insn);
3701
3702       if (insn == bb->head)
3703         break;
3704     }
3705
3706   free_propagate_block_info (pbi);
3707 }
3708 \f
3709 /* Return 1 if X (the body of an insn, or part of it) is just dead stores
3710    (SET expressions whose destinations are registers dead after the insn).
3711    NEEDED is the regset that says which regs are alive after the insn.
3712
3713    Unless CALL_OK is non-zero, an insn is needed if it contains a CALL.
3714
3715    If X is the entire body of an insn, NOTES contains the reg notes
3716    pertaining to the insn.  */
3717
3718 static int
3719 insn_dead_p (pbi, x, call_ok, notes)
3720      struct propagate_block_info *pbi;
3721      rtx x;
3722      int call_ok;
3723      rtx notes ATTRIBUTE_UNUSED;
3724 {
3725   enum rtx_code code = GET_CODE (x);
3726
3727 #ifdef AUTO_INC_DEC
3728   /* If flow is invoked after reload, we must take existing AUTO_INC
3729      expresions into account.  */
3730   if (reload_completed)
3731     {
3732       for ( ; notes; notes = XEXP (notes, 1))
3733         {
3734           if (REG_NOTE_KIND (notes) == REG_INC)
3735             {
3736               int regno = REGNO (XEXP (notes, 0));
3737
3738               /* Don't delete insns to set global regs.  */
3739               if ((regno < FIRST_PSEUDO_REGISTER && global_regs[regno])
3740                   || REGNO_REG_SET_P (pbi->reg_live, regno))
3741                 return 0;
3742             }
3743         }
3744     }
3745 #endif
3746
3747   /* If setting something that's a reg or part of one,
3748      see if that register's altered value will be live.  */
3749
3750   if (code == SET)
3751     {
3752       rtx r = SET_DEST (x);
3753
3754 #ifdef HAVE_cc0
3755       if (GET_CODE (r) == CC0)
3756         return ! pbi->cc0_live;
3757 #endif
3758       
3759       /* A SET that is a subroutine call cannot be dead.  */
3760       if (GET_CODE (SET_SRC (x)) == CALL)
3761         {
3762           if (! call_ok)
3763             return 0;
3764         }
3765
3766       /* Don't eliminate loads from volatile memory or volatile asms.  */
3767       else if (volatile_refs_p (SET_SRC (x)))
3768         return 0;
3769
3770       if (GET_CODE (r) == MEM)
3771         {
3772           rtx temp;
3773
3774           if (MEM_VOLATILE_P (r))
3775             return 0;
3776
3777           /* Walk the set of memory locations we are currently tracking
3778              and see if one is an identical match to this memory location.
3779              If so, this memory write is dead (remember, we're walking
3780              backwards from the end of the block to the start.  */
3781           temp = pbi->mem_set_list;
3782           while (temp)
3783             {
3784               if (rtx_equal_p (XEXP (temp, 0), r))
3785                 return 1;
3786               temp = XEXP (temp, 1);
3787             }
3788         }
3789       else
3790         {
3791           while (GET_CODE (r) == SUBREG
3792                  || GET_CODE (r) == STRICT_LOW_PART
3793                  || GET_CODE (r) == ZERO_EXTRACT)
3794             r = XEXP (r, 0);
3795
3796           if (GET_CODE (r) == REG)
3797             {
3798               int regno = REGNO (r);
3799
3800               /* Obvious.  */
3801               if (REGNO_REG_SET_P (pbi->reg_live, regno))
3802                 return 0;
3803
3804               /* If this is a hard register, verify that subsequent
3805                  words are not needed.  */
3806               if (regno < FIRST_PSEUDO_REGISTER)
3807                 {
3808                   int n = HARD_REGNO_NREGS (regno, GET_MODE (r));
3809
3810                   while (--n > 0)
3811                     if (REGNO_REG_SET_P (pbi->reg_live, regno+n))
3812                       return 0;
3813                 }
3814
3815               /* Don't delete insns to set global regs.  */
3816               if (regno < FIRST_PSEUDO_REGISTER && global_regs[regno])
3817                 return 0;
3818
3819               /* Make sure insns to set the stack pointer aren't deleted.  */
3820               if (regno == STACK_POINTER_REGNUM)
3821                 return 0;
3822
3823               /* Make sure insns to set the frame pointer aren't deleted.  */
3824               if (regno == FRAME_POINTER_REGNUM
3825                   && (! reload_completed || frame_pointer_needed))
3826                 return 0;
3827 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
3828               if (regno == HARD_FRAME_POINTER_REGNUM
3829                   && (! reload_completed || frame_pointer_needed))
3830                 return 0;
3831 #endif
3832
3833 #if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
3834               /* Make sure insns to set arg pointer are never deleted
3835                  (if the arg pointer isn't fixed, there will be a USE
3836                  for it, so we can treat it normally).  */
3837               if (regno == ARG_POINTER_REGNUM && fixed_regs[regno])
3838                 return 0;
3839 #endif
3840
3841               /* Otherwise, the set is dead.  */
3842               return 1;
3843             }
3844         }
3845     }
3846
3847   /* If performing several activities, insn is dead if each activity
3848      is individually dead.  Also, CLOBBERs and USEs can be ignored; a
3849      CLOBBER or USE that's inside a PARALLEL doesn't make the insn
3850      worth keeping.  */
3851   else if (code == PARALLEL)
3852     {
3853       int i = XVECLEN (x, 0);
3854
3855       for (i--; i >= 0; i--)
3856         if (GET_CODE (XVECEXP (x, 0, i)) != CLOBBER
3857             && GET_CODE (XVECEXP (x, 0, i)) != USE
3858             && ! insn_dead_p (pbi, XVECEXP (x, 0, i), call_ok, NULL_RTX))
3859           return 0;
3860
3861       return 1;
3862     }
3863
3864   /* A CLOBBER of a pseudo-register that is dead serves no purpose.  That
3865      is not necessarily true for hard registers.  */
3866   else if (code == CLOBBER && GET_CODE (XEXP (x, 0)) == REG
3867            && REGNO (XEXP (x, 0)) >= FIRST_PSEUDO_REGISTER
3868            && ! REGNO_REG_SET_P (pbi->reg_live, REGNO (XEXP (x, 0))))
3869     return 1;
3870
3871   /* We do not check other CLOBBER or USE here.  An insn consisting of just
3872      a CLOBBER or just a USE should not be deleted.  */
3873   return 0;
3874 }
3875
3876 /* If X is the pattern of the last insn in a libcall, and assuming X is dead,
3877    return 1 if the entire library call is dead.
3878    This is true if X copies a register (hard or pseudo)
3879    and if the hard return  reg of the call insn is dead.
3880    (The caller should have tested the destination of X already for death.)
3881
3882    If this insn doesn't just copy a register, then we don't
3883    have an ordinary libcall.  In that case, cse could not have
3884    managed to substitute the source for the dest later on,
3885    so we can assume the libcall is dead.
3886
3887    NEEDED is the bit vector of pseudoregs live before this insn.
3888    NOTE is the REG_RETVAL note of the insn.  INSN is the insn itself.  */
3889
3890 static int
3891 libcall_dead_p (pbi, x, note, insn)
3892      struct propagate_block_info *pbi;
3893      rtx x;
3894      rtx note;
3895      rtx insn;
3896 {
3897   register RTX_CODE code = GET_CODE (x);
3898
3899   if (code == SET)
3900     {
3901       register rtx r = SET_SRC (x);
3902       if (GET_CODE (r) == REG)
3903         {
3904           rtx call = XEXP (note, 0);
3905           rtx call_pat;
3906           register int i;
3907
3908           /* Find the call insn.  */
3909           while (call != insn && GET_CODE (call) != CALL_INSN)
3910             call = NEXT_INSN (call);
3911
3912           /* If there is none, do nothing special,
3913              since ordinary death handling can understand these insns.  */
3914           if (call == insn)
3915             return 0;
3916
3917           /* See if the hard reg holding the value is dead.
3918              If this is a PARALLEL, find the call within it.  */
3919           call_pat = PATTERN (call);
3920           if (GET_CODE (call_pat) == PARALLEL)
3921             {
3922               for (i = XVECLEN (call_pat, 0) - 1; i >= 0; i--)
3923                 if (GET_CODE (XVECEXP (call_pat, 0, i)) == SET
3924                     && GET_CODE (SET_SRC (XVECEXP (call_pat, 0, i))) == CALL)
3925                   break;
3926
3927               /* This may be a library call that is returning a value
3928                  via invisible pointer.  Do nothing special, since
3929                  ordinary death handling can understand these insns.  */
3930               if (i < 0)
3931                 return 0;
3932
3933               call_pat = XVECEXP (call_pat, 0, i);
3934             }
3935
3936           return insn_dead_p (pbi, call_pat, 1, REG_NOTES (call));
3937         }
3938     }
3939   return 1;
3940 }
3941
3942 /* Return 1 if register REGNO was used before it was set, i.e. if it is
3943    live at function entry.  Don't count global register variables, variables
3944    in registers that can be used for function arg passing, or variables in
3945    fixed hard registers.  */
3946
3947 int
3948 regno_uninitialized (regno)
3949      int regno;
3950 {
3951   if (n_basic_blocks == 0
3952       || (regno < FIRST_PSEUDO_REGISTER
3953           && (global_regs[regno]
3954               || fixed_regs[regno]
3955               || FUNCTION_ARG_REGNO_P (regno))))
3956     return 0;
3957
3958   return REGNO_REG_SET_P (BASIC_BLOCK (0)->global_live_at_start, regno);
3959 }
3960
3961 /* 1 if register REGNO was alive at a place where `setjmp' was called
3962    and was set more than once or is an argument.
3963    Such regs may be clobbered by `longjmp'.  */
3964
3965 int
3966 regno_clobbered_at_setjmp (regno)
3967      int regno;
3968 {
3969   if (n_basic_blocks == 0)
3970     return 0;
3971
3972   return ((REG_N_SETS (regno) > 1
3973            || REGNO_REG_SET_P (BASIC_BLOCK (0)->global_live_at_start, regno))
3974           && REGNO_REG_SET_P (regs_live_at_setjmp, regno));
3975 }
3976 \f
3977 /* INSN references memory, possibly using autoincrement addressing modes.
3978    Find any entries on the mem_set_list that need to be invalidated due
3979    to an address change.  */
3980 static void
3981 invalidate_mems_from_autoinc (pbi, insn)
3982      struct propagate_block_info *pbi;
3983      rtx insn;
3984 {
3985   rtx note = REG_NOTES (insn);
3986   for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
3987     {
3988       if (REG_NOTE_KIND (note) == REG_INC)
3989         {
3990           rtx temp = pbi->mem_set_list;
3991           rtx prev = NULL_RTX;
3992           rtx next;
3993
3994           while (temp)
3995             {
3996               next = XEXP (temp, 1);
3997               if (reg_overlap_mentioned_p (XEXP (note, 0), XEXP (temp, 0)))
3998                 {
3999                   /* Splice temp out of list.  */
4000                   if (prev)
4001                     XEXP (prev, 1) = next;
4002                   else
4003                     pbi->mem_set_list = next;
4004                   free_EXPR_LIST_node (temp);
4005                 }
4006               else
4007                 prev = temp;
4008               temp = next;
4009             }
4010         }
4011     }
4012 }
4013
4014 /* Process the registers that are set within X.  Their bits are set to
4015    1 in the regset DEAD, because they are dead prior to this insn.
4016
4017    If INSN is nonzero, it is the insn being processed.
4018
4019    FLAGS is the set of operations to perform.  */
4020
4021 static void
4022 mark_set_regs (pbi, x, insn)
4023      struct propagate_block_info *pbi;
4024      rtx x, insn;
4025 {
4026   rtx cond = NULL_RTX;
4027   enum rtx_code code;
4028
4029  retry:
4030   switch (code = GET_CODE (x))
4031     {
4032     case SET:
4033     case CLOBBER:
4034       mark_set_1 (pbi, code, SET_DEST (x), cond, insn, pbi->flags);
4035       return;
4036
4037     case COND_EXEC:
4038       cond = COND_EXEC_TEST (x);
4039       x = COND_EXEC_CODE (x);
4040       goto retry;
4041
4042     case PARALLEL:
4043       {
4044         register int i;
4045         for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
4046           {
4047             rtx sub = XVECEXP (x, 0, i);
4048             switch (code = GET_CODE (sub))
4049               {
4050               case COND_EXEC:
4051                 if (cond != NULL_RTX)
4052                   abort ();
4053
4054                 cond = COND_EXEC_TEST (sub);
4055                 sub = COND_EXEC_CODE (sub);
4056                 if (GET_CODE (sub) != SET && GET_CODE (sub) != CLOBBER)
4057                   break;
4058                 /* FALLTHRU */
4059
4060               case SET:
4061               case CLOBBER:
4062                 mark_set_1 (pbi, code, SET_DEST (sub), cond, insn, pbi->flags);
4063                 break;
4064
4065               default:
4066                 break;
4067               }
4068           }
4069         break;
4070       }
4071
4072     default:
4073       break;
4074     }
4075 }
4076
4077 /* Process a single SET rtx, X.  */
4078
4079 static void
4080 mark_set_1 (pbi, code, reg, cond, insn, flags)
4081      struct propagate_block_info *pbi;
4082      enum rtx_code code;
4083      rtx reg, cond, insn;
4084      int flags;
4085 {
4086   int regno_first = -1, regno_last = -1;
4087   int not_dead = 0;
4088   int i;
4089
4090   /* Some targets place small structures in registers for
4091      return values of functions.  We have to detect this
4092      case specially here to get correct flow information.  */
4093   if (GET_CODE (reg) == PARALLEL
4094       && GET_MODE (reg) == BLKmode)
4095     {
4096       for (i = XVECLEN (reg, 0) - 1; i >= 0; i--)
4097         mark_set_1 (pbi, code, XVECEXP (reg, 0, i), cond, insn, flags);
4098       return;
4099     }
4100
4101   /* Modifying just one hardware register of a multi-reg value or just a
4102      byte field of a register does not mean the value from before this insn
4103      is now dead.  Of course, if it was dead after it's unused now.  */
4104
4105   switch (GET_CODE (reg))
4106     {
4107     case ZERO_EXTRACT:
4108     case SIGN_EXTRACT:
4109     case STRICT_LOW_PART:
4110       /* ??? Assumes STRICT_LOW_PART not used on multi-word registers.  */
4111       do
4112         reg = XEXP (reg, 0);
4113       while (GET_CODE (reg) == SUBREG
4114              || GET_CODE (reg) == ZERO_EXTRACT
4115              || GET_CODE (reg) == SIGN_EXTRACT
4116              || GET_CODE (reg) == STRICT_LOW_PART);
4117       if (GET_CODE (reg) == MEM)
4118         break;
4119       not_dead = REGNO_REG_SET_P (pbi->reg_live, REGNO (reg));
4120       /* FALLTHRU */
4121
4122     case REG:
4123       regno_last = regno_first = REGNO (reg);
4124       if (regno_first < FIRST_PSEUDO_REGISTER)
4125         regno_last += HARD_REGNO_NREGS (regno_first, GET_MODE (reg)) - 1;
4126       break;
4127
4128     case SUBREG:
4129       if (GET_CODE (SUBREG_REG (reg)) == REG)
4130         {
4131           enum machine_mode outer_mode = GET_MODE (reg);
4132           enum machine_mode inner_mode = GET_MODE (SUBREG_REG (reg));
4133
4134           /* Identify the range of registers affected.  This is moderately
4135              tricky for hard registers.  See alter_subreg.  */
4136
4137           regno_last = regno_first = REGNO (SUBREG_REG (reg));
4138           if (regno_first < FIRST_PSEUDO_REGISTER)
4139             {
4140 #ifdef ALTER_HARD_SUBREG
4141               regno_first = ALTER_HARD_SUBREG (outer_mode, SUBREG_WORD (reg),
4142                                                inner_mode, regno_first);
4143 #else
4144               regno_first += SUBREG_WORD (reg);
4145 #endif
4146               regno_last = (regno_first
4147                             + HARD_REGNO_NREGS (regno_first, outer_mode) - 1);
4148
4149               /* Since we've just adjusted the register number ranges, make
4150                  sure REG matches.  Otherwise some_was_live will be clear
4151                  when it shouldn't have been, and we'll create incorrect
4152                  REG_UNUSED notes.  */
4153               reg = gen_rtx_REG (outer_mode, regno_first);
4154             }
4155           else
4156             {
4157               /* If the number of words in the subreg is less than the number
4158                  of words in the full register, we have a well-defined partial
4159                  set.  Otherwise the high bits are undefined.
4160
4161                  This is only really applicable to pseudos, since we just took
4162                  care of multi-word hard registers.  */
4163               if (((GET_MODE_SIZE (outer_mode)
4164                     + UNITS_PER_WORD - 1) / UNITS_PER_WORD)
4165                   < ((GET_MODE_SIZE (inner_mode)
4166                       + UNITS_PER_WORD - 1) / UNITS_PER_WORD))
4167                 not_dead = REGNO_REG_SET_P (pbi->reg_live, regno_first);
4168
4169               reg = SUBREG_REG (reg);
4170             }
4171         }
4172       else
4173         reg = SUBREG_REG (reg);
4174       break;
4175
4176     default:
4177       break;
4178     }
4179
4180   /* If this set is a MEM, then it kills any aliased writes. 
4181      If this set is a REG, then it kills any MEMs which use the reg.  */
4182   if (flags & PROP_SCAN_DEAD_CODE)
4183     {
4184       if (GET_CODE (reg) == MEM || GET_CODE (reg) == REG)
4185         {
4186           rtx temp = pbi->mem_set_list;
4187           rtx prev = NULL_RTX;
4188           rtx next;
4189
4190           while (temp)
4191             {
4192               next = XEXP (temp, 1);
4193               if ((GET_CODE (reg) == MEM
4194                    && output_dependence (XEXP (temp, 0), reg))
4195                   || (GET_CODE (reg) == REG
4196                       && reg_overlap_mentioned_p (reg, XEXP (temp, 0))))
4197                 {
4198                   /* Splice this entry out of the list.  */
4199                   if (prev)
4200                     XEXP (prev, 1) = next;
4201                   else
4202                     pbi->mem_set_list = next;
4203                   free_EXPR_LIST_node (temp);
4204                 }
4205               else
4206                 prev = temp;
4207               temp = next;