OSDN Git Service

* flow.c (life_analysis): Only turn off PROP_LOG_LINKS and
[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 "hard-reg-set.h"
128 #include "basic-block.h"
129 #include "insn-config.h"
130 #include "regs.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 #include "ssa.h"
140
141 #include "obstack.h"
142 #include "splay-tree.h"
143
144 #define obstack_chunk_alloc xmalloc
145 #define obstack_chunk_free free
146
147
148 /* EXIT_IGNORE_STACK should be nonzero if, when returning from a function,
149    the stack pointer does not matter.  The value is tested only in
150    functions that have frame pointers.
151    No definition is equivalent to always zero.  */
152 #ifndef EXIT_IGNORE_STACK
153 #define EXIT_IGNORE_STACK 0
154 #endif
155
156 #ifndef HAVE_epilogue
157 #define HAVE_epilogue 0
158 #endif
159 #ifndef HAVE_prologue
160 #define HAVE_prologue 0
161 #endif
162 #ifndef HAVE_sibcall_epilogue
163 #define HAVE_sibcall_epilogue 0
164 #endif
165
166 #ifndef LOCAL_REGNO
167 #define LOCAL_REGNO(REGNO)  0
168 #endif
169 #ifndef EPILOGUE_USES
170 #define EPILOGUE_USES(REGNO)  0
171 #endif
172
173 /* The contents of the current function definition are allocated
174    in this obstack, and all are freed at the end of the function.
175    For top-level functions, this is temporary_obstack.
176    Separate obstacks are made for nested functions.  */
177
178 extern struct obstack *function_obstack;
179
180 /* Number of basic blocks in the current function.  */
181
182 int n_basic_blocks;
183
184 /* Number of edges in the current function.  */
185
186 int n_edges;
187
188 /* The basic block array.  */
189
190 varray_type basic_block_info;
191
192 /* The special entry and exit blocks.  */
193
194 struct basic_block_def entry_exit_blocks[2]
195 = {{NULL,                       /* head */
196     NULL,                       /* end */
197     NULL,                       /* pred */
198     NULL,                       /* succ */
199     NULL,                       /* local_set */
200     NULL,                       /* global_live_at_start */
201     NULL,                       /* global_live_at_end */
202     NULL,                       /* aux */
203     ENTRY_BLOCK,                /* index */
204     0,                          /* loop_depth */
205     -1, -1,                     /* eh_beg, eh_end */
206     0                           /* count */
207   },
208   {
209     NULL,                       /* head */
210     NULL,                       /* end */
211     NULL,                       /* pred */
212     NULL,                       /* succ */
213     NULL,                       /* local_set */
214     NULL,                       /* global_live_at_start */
215     NULL,                       /* global_live_at_end */
216     NULL,                       /* aux */
217     EXIT_BLOCK,                 /* index */
218     0,                          /* loop_depth */
219     -1, -1,                     /* eh_beg, eh_end */
220     0                           /* count */
221   }
222 };
223
224 /* Nonzero if the second flow pass has completed.  */
225 int flow2_completed;
226
227 /* Maximum register number used in this function, plus one.  */
228
229 int max_regno;
230
231 /* Indexed by n, giving various register information */
232
233 varray_type reg_n_info;
234
235 /* Size of a regset for the current function,
236    in (1) bytes and (2) elements.  */
237
238 int regset_bytes;
239 int regset_size;
240
241 /* Regset of regs live when calls to `setjmp'-like functions happen.  */
242 /* ??? Does this exist only for the setjmp-clobbered warning message?  */
243
244 regset regs_live_at_setjmp;
245
246 /* List made of EXPR_LIST rtx's which gives pairs of pseudo registers
247    that have to go in the same hard reg.
248    The first two regs in the list are a pair, and the next two
249    are another pair, etc.  */
250 rtx regs_may_share;
251
252 /* Set of registers that may be eliminable.  These are handled specially
253    in updating regs_ever_live.  */
254
255 static HARD_REG_SET elim_reg_set;
256
257 /* The basic block structure for every insn, indexed by uid.  */
258
259 varray_type basic_block_for_insn;
260
261 /* The labels mentioned in non-jump rtl.  Valid during find_basic_blocks.  */
262 /* ??? Should probably be using LABEL_NUSES instead.  It would take a 
263    bit of surgery to be able to use or co-opt the routines in jump.  */
264
265 static rtx label_value_list;
266 static rtx tail_recursion_label_list;
267
268 /* Holds information for tracking conditional register life information.  */
269 struct reg_cond_life_info
270 {
271   /* An EXPR_LIST of conditions under which a register is dead.  */
272   rtx condition;
273
274   /* ??? Could store mask of bytes that are dead, so that we could finally
275      track lifetimes of multi-word registers accessed via subregs.  */
276 };
277
278 /* For use in communicating between propagate_block and its subroutines.
279    Holds all information needed to compute life and def-use information.  */
280
281 struct propagate_block_info
282 {
283   /* The basic block we're considering.  */
284   basic_block bb;
285
286   /* Bit N is set if register N is conditionally or unconditionally live.  */
287   regset reg_live;
288
289   /* Bit N is set if register N is set this insn.  */
290   regset new_set;
291
292   /* Element N is the next insn that uses (hard or pseudo) register N
293      within the current basic block; or zero, if there is no such insn.  */
294   rtx *reg_next_use;
295
296   /* Contains a list of all the MEMs we are tracking for dead store
297      elimination.  */
298   rtx mem_set_list;
299
300   /* If non-null, record the set of registers set in the basic block.  */
301   regset local_set;
302
303 #ifdef HAVE_conditional_execution
304   /* Indexed by register number, holds a reg_cond_life_info for each
305      register that is not unconditionally live or dead.  */
306   splay_tree reg_cond_dead;
307
308   /* Bit N is set if register N is in an expression in reg_cond_dead.  */
309   regset reg_cond_reg;
310 #endif
311
312   /* Non-zero if the value of CC0 is live.  */
313   int cc0_live;
314
315   /* Flags controling the set of information propagate_block collects.  */
316   int flags;
317 };
318
319 /* Store the data structures necessary for depth-first search. */
320 struct depth_first_search_dsS {
321   /* stack for backtracking during the algorithm */
322   basic_block *stack;
323
324   /* number of edges in the stack.  That is, positions 0, ..., sp-1
325      have edges. */
326   unsigned int sp;
327
328   /* record of basic blocks already seen by depth-first search */
329   sbitmap visited_blocks;
330 };
331 typedef struct depth_first_search_dsS *depth_first_search_ds;
332
333 /* Forward declarations */
334 static int count_basic_blocks           PARAMS ((rtx));
335 static void find_basic_blocks_1         PARAMS ((rtx));
336 static rtx find_label_refs              PARAMS ((rtx, rtx));
337 static void clear_edges                 PARAMS ((void));
338 static void make_edges                  PARAMS ((rtx));
339 static void make_label_edge             PARAMS ((sbitmap *, basic_block,
340                                                  rtx, int));
341 static void make_eh_edge                PARAMS ((sbitmap *, eh_nesting_info *,
342                                                  basic_block, rtx, int));
343 static void mark_critical_edges         PARAMS ((void));
344 static void move_stray_eh_region_notes  PARAMS ((void));
345 static void record_active_eh_regions    PARAMS ((rtx));
346
347 static void commit_one_edge_insertion   PARAMS ((edge));
348
349 static void delete_unreachable_blocks   PARAMS ((void));
350 static void delete_eh_regions           PARAMS ((void));
351 static int can_delete_note_p            PARAMS ((rtx));
352 static void expunge_block               PARAMS ((basic_block));
353 static int can_delete_label_p           PARAMS ((rtx));
354 static int tail_recursion_label_p       PARAMS ((rtx));
355 static int merge_blocks_move_predecessor_nojumps PARAMS ((basic_block,
356                                                           basic_block));
357 static int merge_blocks_move_successor_nojumps PARAMS ((basic_block,
358                                                         basic_block));
359 static int merge_blocks                 PARAMS ((edge,basic_block,basic_block));
360 static void try_merge_blocks            PARAMS ((void));
361 static void tidy_fallthru_edges         PARAMS ((void));
362 static int verify_wide_reg_1            PARAMS ((rtx *, void *));
363 static void verify_wide_reg             PARAMS ((int, rtx, rtx));
364 static void verify_local_live_at_start  PARAMS ((regset, basic_block));
365 static int set_noop_p                   PARAMS ((rtx));
366 static int noop_move_p                  PARAMS ((rtx));
367 static void delete_noop_moves           PARAMS ((rtx));
368 static void notice_stack_pointer_modification_1 PARAMS ((rtx, rtx, void *));
369 static void notice_stack_pointer_modification PARAMS ((rtx));
370 static void mark_reg                    PARAMS ((rtx, void *));
371 static void mark_regs_live_at_end       PARAMS ((regset));
372 static int set_phi_alternative_reg      PARAMS ((rtx, int, int, void *));
373 static void calculate_global_regs_live  PARAMS ((sbitmap, sbitmap, int));
374 static void propagate_block_delete_insn PARAMS ((basic_block, rtx));
375 static rtx propagate_block_delete_libcall PARAMS ((basic_block, rtx, rtx));
376 static int insn_dead_p                  PARAMS ((struct propagate_block_info *,
377                                                  rtx, int, rtx));
378 static int libcall_dead_p               PARAMS ((struct propagate_block_info *,
379                                                  rtx, rtx));
380 static void mark_set_regs               PARAMS ((struct propagate_block_info *,
381                                                  rtx, rtx));
382 static void mark_set_1                  PARAMS ((struct propagate_block_info *,
383                                                  enum rtx_code, rtx, rtx,
384                                                  rtx, int));
385 #ifdef HAVE_conditional_execution
386 static int mark_regno_cond_dead         PARAMS ((struct propagate_block_info *,
387                                                  int, rtx));
388 static void free_reg_cond_life_info     PARAMS ((splay_tree_value));
389 static int flush_reg_cond_reg_1         PARAMS ((splay_tree_node, void *));
390 static void flush_reg_cond_reg          PARAMS ((struct propagate_block_info *,
391                                                  int));
392 static rtx ior_reg_cond                 PARAMS ((rtx, rtx));
393 static rtx not_reg_cond                 PARAMS ((rtx));
394 static rtx nand_reg_cond                PARAMS ((rtx, rtx));
395 #endif
396 #ifdef AUTO_INC_DEC
397 static void attempt_auto_inc            PARAMS ((struct propagate_block_info *,
398                                                  rtx, rtx, rtx, rtx, rtx));
399 static void find_auto_inc               PARAMS ((struct propagate_block_info *,
400                                                  rtx, rtx));
401 static int try_pre_increment_1          PARAMS ((struct propagate_block_info *,
402                                                  rtx));
403 static int try_pre_increment            PARAMS ((rtx, rtx, HOST_WIDE_INT));
404 #endif
405 static void mark_used_reg               PARAMS ((struct propagate_block_info *,
406                                                  rtx, rtx, rtx));
407 static void mark_used_regs              PARAMS ((struct propagate_block_info *,
408                                                  rtx, rtx, rtx));
409 void dump_flow_info                     PARAMS ((FILE *));
410 void debug_flow_info                    PARAMS ((void));
411 static void dump_edge_info              PARAMS ((FILE *, edge, int));
412
413 static void invalidate_mems_from_autoinc PARAMS ((struct propagate_block_info *,
414                                                   rtx));
415 static void remove_fake_successors      PARAMS ((basic_block));
416 static void flow_nodes_print    PARAMS ((const char *, const sbitmap, FILE *));
417 static void flow_exits_print PARAMS ((const char *, const edge *, int, FILE *));
418 static void flow_loops_cfg_dump         PARAMS ((const struct loops *, FILE *));
419 static int flow_loop_nested_p           PARAMS ((struct loop *, struct loop *));
420 static int flow_loop_exits_find         PARAMS ((const sbitmap, edge **));
421 static int flow_loop_nodes_find PARAMS ((basic_block, basic_block, sbitmap));
422 static int flow_depth_first_order_compute PARAMS ((int *, int *));
423 static void flow_dfs_compute_reverse_init
424   PARAMS ((depth_first_search_ds));
425 static void flow_dfs_compute_reverse_add_bb
426   PARAMS ((depth_first_search_ds, basic_block));
427 static basic_block flow_dfs_compute_reverse_execute
428   PARAMS ((depth_first_search_ds));
429 static void flow_dfs_compute_reverse_finish
430   PARAMS ((depth_first_search_ds));
431 static basic_block flow_loop_pre_header_find PARAMS ((basic_block, const sbitmap *));
432 static void flow_loop_tree_node_add     PARAMS ((struct loop *, struct loop *));
433 static void flow_loops_tree_build       PARAMS ((struct loops *));
434 static int flow_loop_level_compute      PARAMS ((struct loop *, int));
435 static int flow_loops_level_compute     PARAMS ((struct loops *));
436 \f
437 /* Find basic blocks of the current function.
438    F is the first insn of the function and NREGS the number of register
439    numbers in use.  */
440
441 void
442 find_basic_blocks (f, nregs, file)
443      rtx f;
444      int nregs ATTRIBUTE_UNUSED;
445      FILE *file ATTRIBUTE_UNUSED;
446 {
447   int max_uid;
448
449   /* Flush out existing data.  */
450   if (basic_block_info != NULL)
451     {
452       int i;
453
454       clear_edges ();
455
456       /* Clear bb->aux on all extant basic blocks.  We'll use this as a 
457          tag for reuse during create_basic_block, just in case some pass
458          copies around basic block notes improperly.  */
459       for (i = 0; i < n_basic_blocks; ++i)
460         BASIC_BLOCK (i)->aux = NULL;
461
462       VARRAY_FREE (basic_block_info);
463     }
464
465   n_basic_blocks = count_basic_blocks (f);
466
467   /* Size the basic block table.  The actual structures will be allocated
468      by find_basic_blocks_1, since we want to keep the structure pointers
469      stable across calls to find_basic_blocks.  */
470   /* ??? This whole issue would be much simpler if we called find_basic_blocks
471      exactly once, and thereafter we don't have a single long chain of 
472      instructions at all until close to the end of compilation when we
473      actually lay them out.  */
474
475   VARRAY_BB_INIT (basic_block_info, n_basic_blocks, "basic_block_info");
476
477   find_basic_blocks_1 (f);
478   
479   /* Record the block to which an insn belongs.  */
480   /* ??? This should be done another way, by which (perhaps) a label is
481      tagged directly with the basic block that it starts.  It is used for
482      more than that currently, but IMO that is the only valid use.  */
483
484   max_uid = get_max_uid ();
485 #ifdef AUTO_INC_DEC
486   /* Leave space for insns life_analysis makes in some cases for auto-inc.
487      These cases are rare, so we don't need too much space.  */
488   max_uid += max_uid / 10;
489 #endif
490
491   compute_bb_for_insn (max_uid);
492
493   /* Discover the edges of our cfg.  */
494   record_active_eh_regions (f);
495   make_edges (label_value_list);
496
497   /* Do very simple cleanup now, for the benefit of code that runs between
498      here and cleanup_cfg, e.g. thread_prologue_and_epilogue_insns.  */
499   tidy_fallthru_edges ();
500
501   mark_critical_edges ();
502
503 #ifdef ENABLE_CHECKING
504   verify_flow_info ();
505 #endif
506 }
507
508 /* Count the basic blocks of the function.  */
509
510 static int 
511 count_basic_blocks (f)
512      rtx f;
513 {
514   register rtx insn;
515   register RTX_CODE prev_code;
516   register int count = 0;
517   int eh_region = 0;
518   int call_had_abnormal_edge = 0;
519
520   prev_code = JUMP_INSN;
521   for (insn = f; insn; insn = NEXT_INSN (insn))
522     {
523       register RTX_CODE code = GET_CODE (insn);
524
525       if (code == CODE_LABEL
526           || (GET_RTX_CLASS (code) == 'i'
527               && (prev_code == JUMP_INSN
528                   || prev_code == BARRIER
529                   || (prev_code == CALL_INSN && call_had_abnormal_edge))))
530         count++;
531
532       /* Record whether this call created an edge.  */
533       if (code == CALL_INSN)
534         {
535           rtx note = find_reg_note (insn, REG_EH_REGION, NULL_RTX);
536           int region = (note ? INTVAL (XEXP (note, 0)) : 1);
537
538           call_had_abnormal_edge = 0;
539
540           /* If there is an EH region or rethrow, we have an edge.  */
541           if ((eh_region && region > 0)
542               || find_reg_note (insn, REG_EH_RETHROW, NULL_RTX))
543             call_had_abnormal_edge = 1;
544           else if (nonlocal_goto_handler_labels && region >= 0)
545             /* If there is a nonlocal goto label and the specified
546                region number isn't -1, we have an edge. (0 means
547                no throw, but might have a nonlocal goto).  */
548             call_had_abnormal_edge = 1;
549         }
550
551       if (code != NOTE)
552         prev_code = code;
553       else if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_BEG)
554         ++eh_region;
555       else if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_END)
556         --eh_region;
557     }
558
559   /* The rest of the compiler works a bit smoother when we don't have to
560      check for the edge case of do-nothing functions with no basic blocks.  */
561   if (count == 0)
562     {
563       emit_insn (gen_rtx_USE (VOIDmode, const0_rtx));
564       count = 1;
565     }
566
567   return count;
568 }
569
570 /* Scan a list of insns for labels referred to other than by jumps.
571    This is used to scan the alternatives of a call placeholder.  */
572 static rtx
573 find_label_refs (f, lvl)
574      rtx f;
575      rtx lvl;
576 {
577   rtx insn;
578
579   for (insn = f; insn; insn = NEXT_INSN (insn))
580     if (INSN_P (insn))
581       {
582         rtx note;
583
584         /* Make a list of all labels referred to other than by jumps
585            (which just don't have the REG_LABEL notes). 
586
587            Make a special exception for labels followed by an ADDR*VEC,
588            as this would be a part of the tablejump setup code. 
589
590            Make a special exception for the eh_return_stub_label, which
591            we know isn't part of any otherwise visible control flow.  */
592              
593         for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
594           if (REG_NOTE_KIND (note) == REG_LABEL)
595             {
596               rtx lab = XEXP (note, 0), next;
597
598               if (lab == eh_return_stub_label)
599                 ;
600               else if ((next = next_nonnote_insn (lab)) != NULL
601                        && GET_CODE (next) == JUMP_INSN
602                        && (GET_CODE (PATTERN (next)) == ADDR_VEC
603                            || GET_CODE (PATTERN (next)) == ADDR_DIFF_VEC))
604                 ;
605               else if (GET_CODE (lab) == NOTE)
606                 ;
607               else
608                 lvl = alloc_EXPR_LIST (0, XEXP (note, 0), lvl);
609             }
610       }
611
612   return lvl;
613 }
614
615 /* Find all basic blocks of the function whose first insn is F.
616
617    Collect and return a list of labels whose addresses are taken.  This
618    will be used in make_edges for use with computed gotos.  */
619
620 static void
621 find_basic_blocks_1 (f)
622      rtx f;
623 {
624   register rtx insn, next;
625   int i = 0;
626   rtx bb_note = NULL_RTX;
627   rtx eh_list = NULL_RTX;
628   rtx lvl = NULL_RTX;
629   rtx trll = NULL_RTX;
630   rtx head = NULL_RTX;
631   rtx end = NULL_RTX;
632   
633   /* We process the instructions in a slightly different way than we did
634      previously.  This is so that we see a NOTE_BASIC_BLOCK after we have
635      closed out the previous block, so that it gets attached at the proper
636      place.  Since this form should be equivalent to the previous,
637      count_basic_blocks continues to use the old form as a check.  */
638
639   for (insn = f; insn; insn = next)
640     {
641       enum rtx_code code = GET_CODE (insn);
642
643       next = NEXT_INSN (insn);
644
645       switch (code)
646         {
647         case NOTE:
648           {
649             int kind = NOTE_LINE_NUMBER (insn);
650
651             /* Keep a LIFO list of the currently active exception notes.  */
652             if (kind == NOTE_INSN_EH_REGION_BEG)
653               eh_list = alloc_INSN_LIST (insn, eh_list);
654             else if (kind == NOTE_INSN_EH_REGION_END)
655               {
656                 rtx t = eh_list;
657
658                 eh_list = XEXP (eh_list, 1);
659                 free_INSN_LIST_node (t);
660               }
661
662             /* Look for basic block notes with which to keep the 
663                basic_block_info pointers stable.  Unthread the note now;
664                we'll put it back at the right place in create_basic_block.
665                Or not at all if we've already found a note in this block.  */
666             else if (kind == NOTE_INSN_BASIC_BLOCK)
667               {
668                 if (bb_note == NULL_RTX)
669                   bb_note = insn;
670                 else
671                   next = flow_delete_insn (insn);
672               }
673             break;
674           }
675
676         case CODE_LABEL:
677           /* A basic block starts at a label.  If we've closed one off due 
678              to a barrier or some such, no need to do it again.  */
679           if (head != NULL_RTX)
680             {
681               /* While we now have edge lists with which other portions of
682                  the compiler might determine a call ending a basic block
683                  does not imply an abnormal edge, it will be a bit before
684                  everything can be updated.  So continue to emit a noop at
685                  the end of such a block.  */
686               if (GET_CODE (end) == CALL_INSN && ! SIBLING_CALL_P (end))
687                 {
688                   rtx nop = gen_rtx_USE (VOIDmode, const0_rtx);
689                   end = emit_insn_after (nop, end);
690                 }
691
692               create_basic_block (i++, head, end, bb_note);
693               bb_note = NULL_RTX;
694             }
695
696           head = end = insn;
697           break;
698
699         case JUMP_INSN:
700           /* A basic block ends at a jump.  */
701           if (head == NULL_RTX)
702             head = insn;
703           else
704             {
705               /* ??? Make a special check for table jumps.  The way this 
706                  happens is truly and amazingly gross.  We are about to
707                  create a basic block that contains just a code label and
708                  an addr*vec jump insn.  Worse, an addr_diff_vec creates
709                  its own natural loop.
710
711                  Prevent this bit of brain damage, pasting things together
712                  correctly in make_edges.  
713
714                  The correct solution involves emitting the table directly
715                  on the tablejump instruction as a note, or JUMP_LABEL.  */
716
717               if (GET_CODE (PATTERN (insn)) == ADDR_VEC
718                   || GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC)
719                 {
720                   head = end = NULL;
721                   n_basic_blocks--;
722                   break;
723                 }
724             }
725           end = insn;
726           goto new_bb_inclusive;
727
728         case BARRIER:
729           /* A basic block ends at a barrier.  It may be that an unconditional
730              jump already closed the basic block -- no need to do it again.  */
731           if (head == NULL_RTX)
732             break;
733
734           /* While we now have edge lists with which other portions of the
735              compiler might determine a call ending a basic block does not
736              imply an abnormal edge, it will be a bit before everything can
737              be updated.  So continue to emit a noop at the end of such a
738              block.  */
739           if (GET_CODE (end) == CALL_INSN && ! SIBLING_CALL_P (end))
740             {
741               rtx nop = gen_rtx_USE (VOIDmode, const0_rtx);
742               end = emit_insn_after (nop, end);
743             }
744           goto new_bb_exclusive;
745
746         case CALL_INSN:
747           {
748             /* Record whether this call created an edge.  */
749             rtx note = find_reg_note (insn, REG_EH_REGION, NULL_RTX);
750             int region = (note ? INTVAL (XEXP (note, 0)) : 1);
751             int call_has_abnormal_edge = 0;
752
753             if (GET_CODE (PATTERN (insn)) == CALL_PLACEHOLDER)
754               {
755                 /* Scan each of the alternatives for label refs.  */
756                 lvl = find_label_refs (XEXP (PATTERN (insn), 0), lvl);
757                 lvl = find_label_refs (XEXP (PATTERN (insn), 1), lvl);
758                 lvl = find_label_refs (XEXP (PATTERN (insn), 2), lvl);
759                 /* Record its tail recursion label, if any.  */
760                 if (XEXP (PATTERN (insn), 3) != NULL_RTX)
761                   trll = alloc_EXPR_LIST (0, XEXP (PATTERN (insn), 3), trll);
762               }
763
764             /* If there is an EH region or rethrow, we have an edge.  */
765             if ((eh_list && region > 0)
766                 || find_reg_note (insn, REG_EH_RETHROW, NULL_RTX))
767               call_has_abnormal_edge = 1;
768             else if (nonlocal_goto_handler_labels && region >= 0)
769               /* If there is a nonlocal goto label and the specified
770                  region number isn't -1, we have an edge. (0 means
771                  no throw, but might have a nonlocal goto).  */
772               call_has_abnormal_edge = 1;
773
774             /* A basic block ends at a call that can either throw or
775                do a non-local goto.  */
776             if (call_has_abnormal_edge)
777               {
778               new_bb_inclusive:
779                 if (head == NULL_RTX)
780                   head = insn;
781                 end = insn;
782
783               new_bb_exclusive:
784                 create_basic_block (i++, head, end, bb_note);
785                 head = end = NULL_RTX;
786                 bb_note = NULL_RTX;
787                 break;
788               }
789             }
790           /* FALLTHRU */
791
792         default:
793           if (GET_RTX_CLASS (code) == 'i')
794             {
795               if (head == NULL_RTX)
796                 head = insn;
797               end = insn;
798             }
799           break;
800         }
801
802       if (GET_RTX_CLASS (code) == 'i')
803         {
804           rtx note;
805
806           /* Make a list of all labels referred to other than by jumps
807              (which just don't have the REG_LABEL notes). 
808
809              Make a special exception for labels followed by an ADDR*VEC,
810              as this would be a part of the tablejump setup code. 
811
812              Make a special exception for the eh_return_stub_label, which
813              we know isn't part of any otherwise visible control flow.  */
814              
815           for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
816             if (REG_NOTE_KIND (note) == REG_LABEL)
817               {
818                 rtx lab = XEXP (note, 0), next;
819
820                 if (lab == eh_return_stub_label)
821                   ;
822                 else if ((next = next_nonnote_insn (lab)) != NULL
823                          && GET_CODE (next) == JUMP_INSN
824                          && (GET_CODE (PATTERN (next)) == ADDR_VEC
825                              || GET_CODE (PATTERN (next)) == ADDR_DIFF_VEC))
826                   ;
827                 else if (GET_CODE (lab) == NOTE)
828                   ;
829                 else
830                   lvl = alloc_EXPR_LIST (0, XEXP (note, 0), lvl);
831               }
832         }
833     }
834
835   if (head != NULL_RTX)
836     create_basic_block (i++, head, end, bb_note);
837   else if (bb_note)
838     flow_delete_insn (bb_note);
839
840   if (i != n_basic_blocks)
841     abort ();
842
843   label_value_list = lvl;
844   tail_recursion_label_list = trll;
845 }
846
847 /* Tidy the CFG by deleting unreachable code and whatnot.  */
848
849 void
850 cleanup_cfg (f)
851      rtx f;
852 {
853   delete_unreachable_blocks ();
854   move_stray_eh_region_notes ();
855   record_active_eh_regions (f);
856   try_merge_blocks ();
857   mark_critical_edges ();
858
859   /* Kill the data we won't maintain.  */
860   free_EXPR_LIST_list (&label_value_list);
861   free_EXPR_LIST_list (&tail_recursion_label_list);
862 }
863
864 /* Create a new basic block consisting of the instructions between
865    HEAD and END inclusive.  Reuses the note and basic block struct
866    in BB_NOTE, if any.  */
867
868 void
869 create_basic_block (index, head, end, bb_note)
870      int index;
871      rtx head, end, bb_note;
872 {
873   basic_block bb;
874
875   if (bb_note
876       && ! RTX_INTEGRATED_P (bb_note)
877       && (bb = NOTE_BASIC_BLOCK (bb_note)) != NULL
878       && bb->aux == NULL)
879     {
880       /* If we found an existing note, thread it back onto the chain.  */
881
882       rtx after;
883
884       if (GET_CODE (head) == CODE_LABEL)
885         after = head;
886       else
887         {
888           after = PREV_INSN (head);
889           head = bb_note;
890         }
891
892       if (after != bb_note && NEXT_INSN (after) != bb_note)
893         reorder_insns (bb_note, bb_note, after);
894     }
895   else
896     {
897       /* Otherwise we must create a note and a basic block structure.
898          Since we allow basic block structs in rtl, give the struct
899          the same lifetime by allocating it off the function obstack
900          rather than using malloc.  */
901
902       bb = (basic_block) obstack_alloc (function_obstack, sizeof (*bb));
903       memset (bb, 0, sizeof (*bb));
904
905       if (GET_CODE (head) == CODE_LABEL)
906         bb_note = emit_note_after (NOTE_INSN_BASIC_BLOCK, head);
907       else
908         {
909           bb_note = emit_note_before (NOTE_INSN_BASIC_BLOCK, head);
910           head = bb_note;
911         }
912       NOTE_BASIC_BLOCK (bb_note) = bb;
913     }
914
915   /* Always include the bb note in the block.  */
916   if (NEXT_INSN (end) == bb_note)
917     end = bb_note;
918
919   bb->head = head;
920   bb->end = end;
921   bb->index = index;
922   BASIC_BLOCK (index) = bb;
923
924   /* Tag the block so that we know it has been used when considering
925      other basic block notes.  */
926   bb->aux = bb;
927 }
928 \f
929 /* Records the basic block struct in BB_FOR_INSN, for every instruction
930    indexed by INSN_UID.  MAX is the size of the array.  */
931
932 void
933 compute_bb_for_insn (max)
934      int max;
935 {
936   int i;
937
938   if (basic_block_for_insn)
939     VARRAY_FREE (basic_block_for_insn);
940   VARRAY_BB_INIT (basic_block_for_insn, max, "basic_block_for_insn");
941
942   for (i = 0; i < n_basic_blocks; ++i)
943     {
944       basic_block bb = BASIC_BLOCK (i);
945       rtx insn, end;
946
947       end = bb->end;
948       insn = bb->head;
949       while (1)
950         {
951           int uid = INSN_UID (insn);
952           if (uid < max)
953             VARRAY_BB (basic_block_for_insn, uid) = bb;
954           if (insn == end)
955             break;
956           insn = NEXT_INSN (insn);
957         }
958     }
959 }
960
961 /* Free the memory associated with the edge structures.  */
962
963 static void
964 clear_edges ()
965 {
966   int i;
967   edge n, e;
968
969   for (i = 0; i < n_basic_blocks; ++i)
970     {
971       basic_block bb = BASIC_BLOCK (i);
972
973       for (e = bb->succ; e ; e = n)
974         {
975           n = e->succ_next;
976           free (e);
977         }
978
979       bb->succ = 0;
980       bb->pred = 0;
981     }
982
983   for (e = ENTRY_BLOCK_PTR->succ; e ; e = n)
984     {
985       n = e->succ_next;
986       free (e);
987     }
988
989   ENTRY_BLOCK_PTR->succ = 0;
990   EXIT_BLOCK_PTR->pred = 0;
991
992   n_edges = 0;
993 }
994
995 /* Identify the edges between basic blocks.
996
997    NONLOCAL_LABEL_LIST is a list of non-local labels in the function.  Blocks
998    that are otherwise unreachable may be reachable with a non-local goto.
999
1000    BB_EH_END is an array indexed by basic block number in which we record 
1001    the list of exception regions active at the end of the basic block.  */
1002
1003 static void
1004 make_edges (label_value_list)
1005      rtx label_value_list;
1006 {
1007   int i;
1008   eh_nesting_info *eh_nest_info = init_eh_nesting_info ();
1009   sbitmap *edge_cache = NULL;
1010
1011   /* Assume no computed jump; revise as we create edges.  */
1012   current_function_has_computed_jump = 0;
1013
1014   /* Heavy use of computed goto in machine-generated code can lead to
1015      nearly fully-connected CFGs.  In that case we spend a significant
1016      amount of time searching the edge lists for duplicates.  */
1017   if (forced_labels || label_value_list)
1018     {
1019       edge_cache = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks);
1020       sbitmap_vector_zero (edge_cache, n_basic_blocks);
1021     }
1022
1023   /* By nature of the way these get numbered, block 0 is always the entry.  */
1024   make_edge (edge_cache, ENTRY_BLOCK_PTR, BASIC_BLOCK (0), EDGE_FALLTHRU);
1025
1026   for (i = 0; i < n_basic_blocks; ++i)
1027     {
1028       basic_block bb = BASIC_BLOCK (i);
1029       rtx insn, x;
1030       enum rtx_code code;
1031       int force_fallthru = 0;
1032
1033       /* Examine the last instruction of the block, and discover the
1034          ways we can leave the block.  */
1035
1036       insn = bb->end;
1037       code = GET_CODE (insn);
1038
1039       /* A branch.  */
1040       if (code == JUMP_INSN)
1041         {
1042           rtx tmp;
1043
1044           /* ??? Recognize a tablejump and do the right thing.  */
1045           if ((tmp = JUMP_LABEL (insn)) != NULL_RTX
1046               && (tmp = NEXT_INSN (tmp)) != NULL_RTX
1047               && GET_CODE (tmp) == JUMP_INSN
1048               && (GET_CODE (PATTERN (tmp)) == ADDR_VEC
1049                   || GET_CODE (PATTERN (tmp)) == ADDR_DIFF_VEC))
1050             {
1051               rtvec vec;
1052               int j;
1053
1054               if (GET_CODE (PATTERN (tmp)) == ADDR_VEC)
1055                 vec = XVEC (PATTERN (tmp), 0);
1056               else
1057                 vec = XVEC (PATTERN (tmp), 1);
1058
1059               for (j = GET_NUM_ELEM (vec) - 1; j >= 0; --j)
1060                 make_label_edge (edge_cache, bb,
1061                                  XEXP (RTVEC_ELT (vec, j), 0), 0);
1062
1063               /* Some targets (eg, ARM) emit a conditional jump that also
1064                  contains the out-of-range target.  Scan for these and
1065                  add an edge if necessary.  */
1066               if ((tmp = single_set (insn)) != NULL
1067                   && SET_DEST (tmp) == pc_rtx
1068                   && GET_CODE (SET_SRC (tmp)) == IF_THEN_ELSE
1069                   && GET_CODE (XEXP (SET_SRC (tmp), 2)) == LABEL_REF)
1070                 make_label_edge (edge_cache, bb,
1071                                  XEXP (XEXP (SET_SRC (tmp), 2), 0), 0);
1072
1073 #ifdef CASE_DROPS_THROUGH
1074               /* Silly VAXen.  The ADDR_VEC is going to be in the way of
1075                  us naturally detecting fallthru into the next block.  */
1076               force_fallthru = 1;
1077 #endif
1078             }
1079
1080           /* If this is a computed jump, then mark it as reaching
1081              everything on the label_value_list and forced_labels list.  */
1082           else if (computed_jump_p (insn))
1083             {
1084               current_function_has_computed_jump = 1;
1085
1086               for (x = label_value_list; x; x = XEXP (x, 1))
1087                 make_label_edge (edge_cache, bb, XEXP (x, 0), EDGE_ABNORMAL);
1088               
1089               for (x = forced_labels; x; x = XEXP (x, 1))
1090                 make_label_edge (edge_cache, bb, XEXP (x, 0), EDGE_ABNORMAL);
1091             }
1092
1093           /* Returns create an exit out.  */
1094           else if (returnjump_p (insn))
1095             make_edge (edge_cache, bb, EXIT_BLOCK_PTR, 0);
1096
1097           /* Otherwise, we have a plain conditional or unconditional jump.  */
1098           else
1099             {
1100               if (! JUMP_LABEL (insn))
1101                 abort ();
1102               make_label_edge (edge_cache, bb, JUMP_LABEL (insn), 0);
1103             }
1104         }
1105
1106       /* If this is a sibling call insn, then this is in effect a 
1107          combined call and return, and so we need an edge to the
1108          exit block.  No need to worry about EH edges, since we
1109          wouldn't have created the sibling call in the first place.  */
1110
1111       if (code == CALL_INSN && SIBLING_CALL_P (insn))
1112         make_edge (edge_cache, bb, EXIT_BLOCK_PTR,
1113                    EDGE_ABNORMAL | EDGE_ABNORMAL_CALL);
1114       else
1115
1116       /* If this is a CALL_INSN, then mark it as reaching the active EH
1117          handler for this CALL_INSN.  If we're handling asynchronous
1118          exceptions then any insn can reach any of the active handlers.
1119
1120          Also mark the CALL_INSN as reaching any nonlocal goto handler.  */
1121
1122       if (code == CALL_INSN || asynchronous_exceptions)
1123         {
1124           /* Add any appropriate EH edges.  We do this unconditionally
1125              since there may be a REG_EH_REGION or REG_EH_RETHROW note
1126              on the call, and this needn't be within an EH region.  */
1127           make_eh_edge (edge_cache, eh_nest_info, bb, insn, bb->eh_end);
1128
1129           /* If we have asynchronous exceptions, do the same for *all*
1130              exception regions active in the block.  */
1131           if (asynchronous_exceptions
1132               && bb->eh_beg != bb->eh_end)
1133             {
1134               if (bb->eh_beg >= 0)
1135                 make_eh_edge (edge_cache, eh_nest_info, bb,
1136                               NULL_RTX, bb->eh_beg);
1137
1138               for (x = bb->head; x != bb->end; x = NEXT_INSN (x))
1139                 if (GET_CODE (x) == NOTE
1140                     && (NOTE_LINE_NUMBER (x) == NOTE_INSN_EH_REGION_BEG
1141                         || NOTE_LINE_NUMBER (x) == NOTE_INSN_EH_REGION_END))
1142                   {
1143                     int region = NOTE_EH_HANDLER (x);
1144                     make_eh_edge (edge_cache, eh_nest_info, bb,
1145                                   NULL_RTX, region);
1146                   }
1147             }
1148
1149           if (code == CALL_INSN && nonlocal_goto_handler_labels)
1150             {
1151               /* ??? This could be made smarter: in some cases it's possible
1152                  to tell that certain calls will not do a nonlocal goto.
1153
1154                  For example, if the nested functions that do the nonlocal
1155                  gotos do not have their addresses taken, then only calls to
1156                  those functions or to other nested functions that use them
1157                  could possibly do nonlocal gotos.  */
1158               /* We do know that a REG_EH_REGION note with a value less
1159                  than 0 is guaranteed not to perform a non-local goto.  */
1160               rtx note = find_reg_note (insn, REG_EH_REGION, NULL_RTX);
1161               if (!note || INTVAL (XEXP (note, 0)) >=  0)
1162                 for (x = nonlocal_goto_handler_labels; x ; x = XEXP (x, 1))
1163                   make_label_edge (edge_cache, bb, XEXP (x, 0),
1164                                    EDGE_ABNORMAL | EDGE_ABNORMAL_CALL);
1165             }
1166         }
1167
1168       /* We know something about the structure of the function __throw in
1169          libgcc2.c.  It is the only function that ever contains eh_stub
1170          labels.  It modifies its return address so that the last block
1171          returns to one of the eh_stub labels within it.  So we have to
1172          make additional edges in the flow graph.  */
1173       if (i + 1 == n_basic_blocks && eh_return_stub_label != 0)
1174         make_label_edge (edge_cache, bb, eh_return_stub_label, EDGE_EH);
1175
1176       /* Find out if we can drop through to the next block.  */
1177       insn = next_nonnote_insn (insn);
1178       if (!insn || (i + 1 == n_basic_blocks && force_fallthru))
1179         make_edge (edge_cache, bb, EXIT_BLOCK_PTR, EDGE_FALLTHRU);
1180       else if (i + 1 < n_basic_blocks)
1181         {
1182           rtx tmp = BLOCK_HEAD (i + 1);
1183           if (GET_CODE (tmp) == NOTE)
1184             tmp = next_nonnote_insn (tmp);
1185           if (force_fallthru || insn == tmp)
1186             make_edge (edge_cache, bb, BASIC_BLOCK (i + 1), EDGE_FALLTHRU);
1187         }
1188     }
1189
1190   free_eh_nesting_info (eh_nest_info);
1191   if (edge_cache)
1192     sbitmap_vector_free (edge_cache);
1193 }
1194
1195 /* Create an edge between two basic blocks.  FLAGS are auxiliary information
1196    about the edge that is accumulated between calls.  */
1197
1198 void
1199 make_edge (edge_cache, src, dst, flags)
1200      sbitmap *edge_cache;
1201      basic_block src, dst;
1202      int flags;
1203 {
1204   int use_edge_cache;
1205   edge e;
1206
1207   /* Don't bother with edge cache for ENTRY or EXIT; there aren't that
1208      many edges to them, and we didn't allocate memory for it.  */
1209   use_edge_cache = (edge_cache
1210                     && src != ENTRY_BLOCK_PTR
1211                     && dst != EXIT_BLOCK_PTR);
1212
1213   /* Make sure we don't add duplicate edges.  */
1214   if (! use_edge_cache || TEST_BIT (edge_cache[src->index], dst->index))
1215     for (e = src->succ; e ; e = e->succ_next)
1216       if (e->dest == dst)
1217         {
1218           e->flags |= flags;
1219           return;
1220         }
1221
1222   e = (edge) xcalloc (1, sizeof (*e));
1223   n_edges++;
1224
1225   e->succ_next = src->succ;
1226   e->pred_next = dst->pred;
1227   e->src = src;
1228   e->dest = dst;
1229   e->flags = flags;
1230
1231   src->succ = e;
1232   dst->pred = e;
1233
1234   if (use_edge_cache)
1235     SET_BIT (edge_cache[src->index], dst->index);
1236 }
1237
1238 /* Create an edge from a basic block to a label.  */
1239
1240 static void
1241 make_label_edge (edge_cache, src, label, flags)
1242      sbitmap *edge_cache;
1243      basic_block src;
1244      rtx label;
1245      int flags;
1246 {
1247   if (GET_CODE (label) != CODE_LABEL)
1248     abort ();
1249
1250   /* If the label was never emitted, this insn is junk, but avoid a
1251      crash trying to refer to BLOCK_FOR_INSN (label).  This can happen
1252      as a result of a syntax error and a diagnostic has already been
1253      printed.  */
1254
1255   if (INSN_UID (label) == 0)
1256     return;
1257
1258   make_edge (edge_cache, src, BLOCK_FOR_INSN (label), flags);
1259 }
1260
1261 /* Create the edges generated by INSN in REGION.  */
1262
1263 static void
1264 make_eh_edge (edge_cache, eh_nest_info, src, insn, region)
1265      sbitmap *edge_cache;
1266      eh_nesting_info *eh_nest_info;
1267      basic_block src;
1268      rtx insn;
1269      int region;
1270 {
1271   handler_info **handler_list;
1272   int num, is_call;
1273
1274   is_call = (insn && GET_CODE (insn) == CALL_INSN ? EDGE_ABNORMAL_CALL : 0);
1275   num = reachable_handlers (region, eh_nest_info, insn, &handler_list);
1276   while (--num >= 0)
1277     {
1278       make_label_edge (edge_cache, src, handler_list[num]->handler_label,
1279                        EDGE_ABNORMAL | EDGE_EH | is_call);
1280     }
1281 }
1282
1283 /* EH_REGION notes appearing between basic blocks is ambiguous, and even
1284    dangerous if we intend to move basic blocks around.  Move such notes
1285    into the following block.  */
1286
1287 static void
1288 move_stray_eh_region_notes ()
1289 {
1290   int i;
1291   basic_block b1, b2;
1292
1293   if (n_basic_blocks < 2)
1294     return;
1295
1296   b2 = BASIC_BLOCK (n_basic_blocks - 1);
1297   for (i = n_basic_blocks - 2; i >= 0; --i, b2 = b1)
1298     {
1299       rtx insn, next, list = NULL_RTX;
1300
1301       b1 = BASIC_BLOCK (i);
1302       for (insn = NEXT_INSN (b1->end); insn != b2->head; insn = next)
1303         {
1304           next = NEXT_INSN (insn);
1305           if (GET_CODE (insn) == NOTE
1306               && (NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_BEG
1307                   || NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_END))
1308             {
1309               /* Unlink from the insn chain.  */
1310               NEXT_INSN (PREV_INSN (insn)) = next;
1311               PREV_INSN (next) = PREV_INSN (insn);
1312
1313               /* Queue it.  */
1314               NEXT_INSN (insn) = list;
1315               list = insn;
1316             }
1317         }
1318
1319       if (list == NULL_RTX)
1320         continue;
1321
1322       /* Find where to insert these things.  */
1323       insn = b2->head;
1324       if (GET_CODE (insn) == CODE_LABEL)
1325         insn = NEXT_INSN (insn);
1326
1327       while (list)
1328         {
1329           next = NEXT_INSN (list);
1330           add_insn_after (list, insn);
1331           list = next;
1332         }
1333     }
1334 }
1335
1336 /* Recompute eh_beg/eh_end for each basic block.  */
1337
1338 static void
1339 record_active_eh_regions (f)
1340      rtx f;
1341 {
1342   rtx insn, eh_list = NULL_RTX;
1343   int i = 0;
1344   basic_block bb = BASIC_BLOCK (0);
1345
1346   for (insn = f; insn ; insn = NEXT_INSN (insn))
1347     {
1348       if (bb->head == insn)
1349         bb->eh_beg = (eh_list ? NOTE_EH_HANDLER (XEXP (eh_list, 0)) : -1);
1350
1351       if (GET_CODE (insn) == NOTE)
1352         {
1353           int kind = NOTE_LINE_NUMBER (insn);
1354           if (kind == NOTE_INSN_EH_REGION_BEG)
1355             eh_list = alloc_INSN_LIST (insn, eh_list);
1356           else if (kind == NOTE_INSN_EH_REGION_END)
1357             {
1358               rtx t = XEXP (eh_list, 1);
1359               free_INSN_LIST_node (eh_list);
1360               eh_list = t;
1361             }
1362         }
1363
1364       if (bb->end == insn)
1365         {
1366           bb->eh_end = (eh_list ? NOTE_EH_HANDLER (XEXP (eh_list, 0)) : -1);
1367           i += 1;
1368           if (i == n_basic_blocks)
1369             break;
1370           bb = BASIC_BLOCK (i);
1371         }
1372     }
1373 }
1374
1375 /* Identify critical edges and set the bits appropriately.  */
1376
1377 static void
1378 mark_critical_edges ()
1379 {
1380   int i, n = n_basic_blocks;
1381   basic_block bb;
1382
1383   /* We begin with the entry block.  This is not terribly important now,
1384      but could be if a front end (Fortran) implemented alternate entry
1385      points.  */
1386   bb = ENTRY_BLOCK_PTR;
1387   i = -1;
1388
1389   while (1)
1390     {
1391       edge e;
1392
1393       /* (1) Critical edges must have a source with multiple successors.  */
1394       if (bb->succ && bb->succ->succ_next)
1395         {
1396           for (e = bb->succ; e ; e = e->succ_next)
1397             {
1398               /* (2) Critical edges must have a destination with multiple
1399                  predecessors.  Note that we know there is at least one
1400                  predecessor -- the edge we followed to get here.  */
1401               if (e->dest->pred->pred_next)
1402                 e->flags |= EDGE_CRITICAL;
1403               else
1404                 e->flags &= ~EDGE_CRITICAL;
1405             }
1406         }
1407       else
1408         {
1409           for (e = bb->succ; e ; e = e->succ_next)
1410             e->flags &= ~EDGE_CRITICAL;
1411         }
1412
1413       if (++i >= n)
1414         break;
1415       bb = BASIC_BLOCK (i);
1416     }
1417 }
1418 \f
1419 /* Split a (typically critical) edge.  Return the new block.
1420    Abort on abnormal edges. 
1421
1422    ??? The code generally expects to be called on critical edges.
1423    The case of a block ending in an unconditional jump to a 
1424    block with multiple predecessors is not handled optimally.  */
1425
1426 basic_block
1427 split_edge (edge_in)
1428      edge edge_in;
1429 {
1430   basic_block old_pred, bb, old_succ;
1431   edge edge_out;
1432   rtx bb_note;
1433   int i, j;
1434  
1435   /* Abnormal edges cannot be split.  */
1436   if ((edge_in->flags & EDGE_ABNORMAL) != 0)
1437     abort ();
1438
1439   old_pred = edge_in->src;
1440   old_succ = edge_in->dest;
1441
1442   /* Remove the existing edge from the destination's pred list.  */
1443   {
1444     edge *pp;
1445     for (pp = &old_succ->pred; *pp != edge_in; pp = &(*pp)->pred_next)
1446       continue;
1447     *pp = edge_in->pred_next;
1448     edge_in->pred_next = NULL;
1449   }
1450
1451   /* Create the new structures.  */
1452   bb = (basic_block) obstack_alloc (function_obstack, sizeof (*bb));
1453   edge_out = (edge) xcalloc (1, sizeof (*edge_out));
1454   n_edges++;
1455
1456   memset (bb, 0, sizeof (*bb));
1457
1458   /* ??? This info is likely going to be out of date very soon.  */
1459   if (old_succ->global_live_at_start)
1460     {
1461       bb->global_live_at_start = OBSTACK_ALLOC_REG_SET (function_obstack);
1462       bb->global_live_at_end = OBSTACK_ALLOC_REG_SET (function_obstack);
1463       COPY_REG_SET (bb->global_live_at_start, old_succ->global_live_at_start);
1464       COPY_REG_SET (bb->global_live_at_end, old_succ->global_live_at_start);
1465     }
1466
1467   /* Wire them up.  */
1468   bb->pred = edge_in;
1469   bb->succ = edge_out;
1470   bb->count = edge_in->count;
1471
1472   edge_in->dest = bb;
1473   edge_in->flags &= ~EDGE_CRITICAL;
1474
1475   edge_out->pred_next = old_succ->pred;
1476   edge_out->succ_next = NULL;
1477   edge_out->src = bb;
1478   edge_out->dest = old_succ;
1479   edge_out->flags = EDGE_FALLTHRU;
1480   edge_out->probability = REG_BR_PROB_BASE;
1481   edge_out->count = edge_in->count;
1482
1483   old_succ->pred = edge_out;
1484
1485   /* Tricky case -- if there existed a fallthru into the successor
1486      (and we're not it) we must add a new unconditional jump around
1487      the new block we're actually interested in. 
1488
1489      Further, if that edge is critical, this means a second new basic
1490      block must be created to hold it.  In order to simplify correct
1491      insn placement, do this before we touch the existing basic block
1492      ordering for the block we were really wanting.  */
1493   if ((edge_in->flags & EDGE_FALLTHRU) == 0)
1494     {
1495       edge e;
1496       for (e = edge_out->pred_next; e ; e = e->pred_next)
1497         if (e->flags & EDGE_FALLTHRU)
1498           break;
1499
1500       if (e)
1501         {
1502           basic_block jump_block;
1503           rtx pos;
1504
1505           if ((e->flags & EDGE_CRITICAL) == 0
1506               && e->src != ENTRY_BLOCK_PTR)
1507             {
1508               /* Non critical -- we can simply add a jump to the end
1509                  of the existing predecessor.  */
1510               jump_block = e->src;
1511             }
1512           else
1513             {
1514               /* We need a new block to hold the jump.  The simplest
1515                  way to do the bulk of the work here is to recursively
1516                  call ourselves.  */
1517               jump_block = split_edge (e);
1518               e = jump_block->succ;
1519             }
1520
1521           /* Now add the jump insn ...  */
1522           pos = emit_jump_insn_after (gen_jump (old_succ->head),
1523                                       jump_block->end);
1524           jump_block->end = pos;
1525           if (basic_block_for_insn)
1526             set_block_for_insn (pos, jump_block);
1527           emit_barrier_after (pos);
1528
1529           /* ... let jump know that label is in use, ...  */
1530           JUMP_LABEL (pos) = old_succ->head;
1531           ++LABEL_NUSES (old_succ->head);
1532           
1533           /* ... and clear fallthru on the outgoing edge.  */
1534           e->flags &= ~EDGE_FALLTHRU;
1535
1536           /* Continue splitting the interesting edge.  */
1537         }
1538     }
1539
1540   /* Place the new block just in front of the successor.  */
1541   VARRAY_GROW (basic_block_info, ++n_basic_blocks);
1542   if (old_succ == EXIT_BLOCK_PTR)
1543     j = n_basic_blocks - 1;
1544   else
1545     j = old_succ->index;
1546   for (i = n_basic_blocks - 1; i > j; --i)
1547     {
1548       basic_block tmp = BASIC_BLOCK (i - 1);
1549       BASIC_BLOCK (i) = tmp;
1550       tmp->index = i;
1551     }
1552   BASIC_BLOCK (i) = bb;
1553   bb->index = i;
1554
1555   /* Create the basic block note. 
1556
1557      Where we place the note can have a noticable impact on the generated
1558      code.  Consider this cfg: 
1559         
1560
1561                         E
1562                         |
1563                         0
1564                        / \
1565                    +->1-->2--->E
1566                    |  |
1567                    +--+
1568
1569       If we need to insert an insn on the edge from block 0 to block 1,
1570       we want to ensure the instructions we insert are outside of any
1571       loop notes that physically sit between block 0 and block 1.  Otherwise
1572       we confuse the loop optimizer into thinking the loop is a phony.  */
1573   if (old_succ != EXIT_BLOCK_PTR
1574       && PREV_INSN (old_succ->head)
1575       && GET_CODE (PREV_INSN (old_succ->head)) == NOTE
1576       && NOTE_LINE_NUMBER (PREV_INSN (old_succ->head)) == NOTE_INSN_LOOP_BEG)
1577     bb_note = emit_note_before (NOTE_INSN_BASIC_BLOCK,
1578                                 PREV_INSN (old_succ->head));
1579   else if (old_succ != EXIT_BLOCK_PTR)
1580     bb_note = emit_note_before (NOTE_INSN_BASIC_BLOCK, old_succ->head);
1581   else
1582     bb_note = emit_note_after (NOTE_INSN_BASIC_BLOCK, get_last_insn ());
1583   NOTE_BASIC_BLOCK (bb_note) = bb;
1584   bb->head = bb->end = bb_note;
1585
1586   /* Not quite simple -- for non-fallthru edges, we must adjust the
1587      predecessor's jump instruction to target our new block.  */
1588   if ((edge_in->flags & EDGE_FALLTHRU) == 0)
1589     {
1590       rtx tmp, insn = old_pred->end;
1591       rtx old_label = old_succ->head;
1592       rtx new_label = gen_label_rtx ();
1593
1594       if (GET_CODE (insn) != JUMP_INSN)
1595         abort ();
1596
1597       /* ??? Recognize a tablejump and adjust all matching cases.  */
1598       if ((tmp = JUMP_LABEL (insn)) != NULL_RTX
1599           && (tmp = NEXT_INSN (tmp)) != NULL_RTX
1600           && GET_CODE (tmp) == JUMP_INSN
1601           && (GET_CODE (PATTERN (tmp)) == ADDR_VEC
1602               || GET_CODE (PATTERN (tmp)) == ADDR_DIFF_VEC))
1603         {
1604           rtvec vec;
1605           int j;
1606
1607           if (GET_CODE (PATTERN (tmp)) == ADDR_VEC)
1608             vec = XVEC (PATTERN (tmp), 0);
1609           else
1610             vec = XVEC (PATTERN (tmp), 1);
1611
1612           for (j = GET_NUM_ELEM (vec) - 1; j >= 0; --j)
1613             if (XEXP (RTVEC_ELT (vec, j), 0) == old_label)
1614               {
1615                 RTVEC_ELT (vec, j) = gen_rtx_LABEL_REF (VOIDmode, new_label);
1616                 --LABEL_NUSES (old_label);
1617                 ++LABEL_NUSES (new_label);
1618               }
1619
1620           /* Handle casesi dispatch insns */
1621           if ((tmp = single_set (insn)) != NULL
1622               && SET_DEST (tmp) == pc_rtx
1623               && GET_CODE (SET_SRC (tmp)) == IF_THEN_ELSE
1624               && GET_CODE (XEXP (SET_SRC (tmp), 2)) == LABEL_REF
1625               && XEXP (XEXP (SET_SRC (tmp), 2), 0) == old_label)
1626             {
1627               XEXP (SET_SRC (tmp), 2) = gen_rtx_LABEL_REF (VOIDmode, 
1628                                                            new_label);
1629               --LABEL_NUSES (old_label);
1630               ++LABEL_NUSES (new_label);
1631             }
1632         }
1633       else
1634         {
1635           /* This would have indicated an abnormal edge.  */
1636           if (computed_jump_p (insn))
1637             abort ();
1638
1639           /* A return instruction can't be redirected.  */
1640           if (returnjump_p (insn))
1641             abort ();
1642
1643           /* If the insn doesn't go where we think, we're confused.  */
1644           if (JUMP_LABEL (insn) != old_label)
1645             abort ();
1646
1647           redirect_jump (insn, new_label, 0);
1648         }
1649
1650       emit_label_before (new_label, bb_note);
1651       bb->head = new_label;
1652     }
1653
1654   return bb;
1655 }
1656
1657 /* Queue instructions for insertion on an edge between two basic blocks.
1658    The new instructions and basic blocks (if any) will not appear in the
1659    CFG until commit_edge_insertions is called.  */
1660
1661 void
1662 insert_insn_on_edge (pattern, e)
1663      rtx pattern;
1664      edge e;
1665 {
1666   /* We cannot insert instructions on an abnormal critical edge.
1667      It will be easier to find the culprit if we die now.  */
1668   if ((e->flags & (EDGE_ABNORMAL|EDGE_CRITICAL))
1669       == (EDGE_ABNORMAL|EDGE_CRITICAL))
1670     abort ();
1671
1672   if (e->insns == NULL_RTX)
1673     start_sequence ();
1674   else
1675     push_to_sequence (e->insns);
1676
1677   emit_insn (pattern);
1678
1679   e->insns = get_insns ();
1680   end_sequence();
1681 }
1682
1683 /* Update the CFG for the instructions queued on edge E.  */
1684
1685 static void
1686 commit_one_edge_insertion (e)
1687      edge e;
1688 {
1689   rtx before = NULL_RTX, after = NULL_RTX, insns, tmp, last;
1690   basic_block bb;
1691
1692   /* Pull the insns off the edge now since the edge might go away.  */
1693   insns = e->insns;
1694   e->insns = NULL_RTX;
1695
1696   /* Figure out where to put these things.  If the destination has
1697      one predecessor, insert there.  Except for the exit block.  */
1698   if (e->dest->pred->pred_next == NULL
1699       && e->dest != EXIT_BLOCK_PTR)
1700     {
1701       bb = e->dest;
1702
1703       /* Get the location correct wrt a code label, and "nice" wrt
1704          a basic block note, and before everything else.  */
1705       tmp = bb->head;
1706       if (GET_CODE (tmp) == CODE_LABEL)
1707         tmp = NEXT_INSN (tmp);
1708       if (NOTE_INSN_BASIC_BLOCK_P (tmp))
1709         tmp = NEXT_INSN (tmp);
1710       if (tmp == bb->head)
1711         before = tmp;
1712       else
1713         after = PREV_INSN (tmp);
1714     }
1715   
1716   /* If the source has one successor and the edge is not abnormal,
1717      insert there.  Except for the entry block.  */
1718   else if ((e->flags & EDGE_ABNORMAL) == 0
1719            && e->src->succ->succ_next == NULL
1720            && e->src != ENTRY_BLOCK_PTR)
1721     {
1722       bb = e->src;
1723       /* It is possible to have a non-simple jump here.  Consider a target
1724          where some forms of unconditional jumps clobber a register.  This
1725          happens on the fr30 for example. 
1726
1727          We know this block has a single successor, so we can just emit
1728          the queued insns before the jump.  */
1729       if (GET_CODE (bb->end) == JUMP_INSN)
1730         {
1731           before = bb->end;
1732         }
1733       else
1734         {
1735           /* We'd better be fallthru, or we've lost track of what's what.  */
1736           if ((e->flags & EDGE_FALLTHRU) == 0)
1737             abort ();
1738
1739           after = bb->end;
1740         }
1741     }
1742
1743   /* Otherwise we must split the edge.  */
1744   else
1745     {
1746       bb = split_edge (e);
1747       after = bb->end;
1748     }
1749
1750   /* Now that we've found the spot, do the insertion.  */
1751
1752   /* Set the new block number for these insns, if structure is allocated.  */
1753   if (basic_block_for_insn)
1754     {
1755       rtx i;
1756       for (i = insns; i != NULL_RTX; i = NEXT_INSN (i))
1757         set_block_for_insn (i, bb);
1758     }
1759
1760   if (before)
1761     {
1762       emit_insns_before (insns, before);
1763       if (before == bb->head)
1764         bb->head = insns;
1765
1766       last = prev_nonnote_insn (before);
1767     }
1768   else
1769     {
1770       last = emit_insns_after (insns, after);
1771       if (after == bb->end)
1772         bb->end = last;
1773     }
1774
1775   if (returnjump_p (last))
1776     {
1777       /* ??? Remove all outgoing edges from BB and add one for EXIT. 
1778          This is not currently a problem because this only happens
1779          for the (single) epilogue, which already has a fallthru edge
1780          to EXIT.  */
1781
1782       e = bb->succ;
1783       if (e->dest != EXIT_BLOCK_PTR
1784           || e->succ_next != NULL
1785           || (e->flags & EDGE_FALLTHRU) == 0)
1786         abort ();
1787       e->flags &= ~EDGE_FALLTHRU;
1788
1789       emit_barrier_after (last);
1790       bb->end = last;
1791
1792       if (before)
1793         flow_delete_insn (before);
1794     }
1795   else if (GET_CODE (last) == JUMP_INSN)
1796     abort ();
1797 }
1798
1799 /* Update the CFG for all queued instructions.  */
1800
1801 void
1802 commit_edge_insertions ()
1803 {
1804   int i;
1805   basic_block bb;
1806
1807 #ifdef ENABLE_CHECKING
1808   verify_flow_info ();
1809 #endif
1810  
1811   i = -1;
1812   bb = ENTRY_BLOCK_PTR;
1813   while (1)
1814     {
1815       edge e, next;
1816
1817       for (e = bb->succ; e ; e = next)
1818         {
1819           next = e->succ_next;
1820           if (e->insns)
1821             commit_one_edge_insertion (e);
1822         }
1823
1824       if (++i >= n_basic_blocks)
1825         break;
1826       bb = BASIC_BLOCK (i);
1827     }
1828 }
1829 \f
1830 /* Delete all unreachable basic blocks.   */
1831
1832 static void
1833 delete_unreachable_blocks ()
1834 {
1835   basic_block *worklist, *tos;
1836   int deleted_handler;
1837   edge e;
1838   int i, n;
1839
1840   n = n_basic_blocks;
1841   tos = worklist = (basic_block *) xmalloc (sizeof (basic_block) * n);
1842
1843   /* Use basic_block->aux as a marker.  Clear them all.  */
1844
1845   for (i = 0; i < n; ++i)
1846     BASIC_BLOCK (i)->aux = NULL;
1847
1848   /* Add our starting points to the worklist.  Almost always there will
1849      be only one.  It isn't inconcievable that we might one day directly
1850      support Fortran alternate entry points.  */
1851
1852   for (e = ENTRY_BLOCK_PTR->succ; e ; e = e->succ_next)
1853     {
1854       *tos++ = e->dest;
1855
1856       /* Mark the block with a handy non-null value.  */
1857       e->dest->aux = e;
1858     }
1859       
1860   /* Iterate: find everything reachable from what we've already seen.  */
1861
1862   while (tos != worklist)
1863     {
1864       basic_block b = *--tos;
1865
1866       for (e = b->succ; e ; e = e->succ_next)
1867         if (!e->dest->aux)
1868           {
1869             *tos++ = e->dest;
1870             e->dest->aux = e;
1871           }
1872     }
1873
1874   /* Delete all unreachable basic blocks.  Count down so that we don't
1875      interfere with the block renumbering that happens in flow_delete_block. */
1876
1877   deleted_handler = 0;
1878
1879   for (i = n - 1; i >= 0; --i)
1880     {
1881       basic_block b = BASIC_BLOCK (i);
1882
1883       if (b->aux != NULL)
1884         /* This block was found.  Tidy up the mark.  */
1885         b->aux = NULL;
1886       else
1887         deleted_handler |= flow_delete_block (b);
1888     }
1889
1890   tidy_fallthru_edges ();
1891
1892   /* If we deleted an exception handler, we may have EH region begin/end
1893      blocks to remove as well. */
1894   if (deleted_handler)
1895     delete_eh_regions ();
1896
1897   free (worklist);
1898 }
1899
1900 /* Find EH regions for which there is no longer a handler, and delete them.  */
1901
1902 static void
1903 delete_eh_regions ()
1904 {
1905   rtx insn;
1906
1907   update_rethrow_references ();
1908
1909   for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
1910     if (GET_CODE (insn) == NOTE)
1911       {
1912         if ((NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_BEG) ||
1913             (NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_END)) 
1914           {
1915             int num = NOTE_EH_HANDLER (insn);
1916             /* A NULL handler indicates a region is no longer needed,
1917                as long as its rethrow label isn't used.  */
1918             if (get_first_handler (num) == NULL && ! rethrow_used (num))
1919               {
1920                 NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
1921                 NOTE_SOURCE_FILE (insn) = 0;
1922               }
1923           }
1924       }
1925 }
1926
1927 /* Return true if NOTE is not one of the ones that must be kept paired,
1928    so that we may simply delete them.  */
1929
1930 static int
1931 can_delete_note_p (note)
1932      rtx note;
1933 {
1934   return (NOTE_LINE_NUMBER (note) == NOTE_INSN_DELETED
1935           || NOTE_LINE_NUMBER (note) == NOTE_INSN_BASIC_BLOCK);
1936 }
1937
1938 /* Unlink a chain of insns between START and FINISH, leaving notes
1939    that must be paired.  */
1940
1941 void
1942 flow_delete_insn_chain (start, finish)
1943      rtx start, finish;
1944 {
1945   /* Unchain the insns one by one.  It would be quicker to delete all
1946      of these with a single unchaining, rather than one at a time, but
1947      we need to keep the NOTE's.  */
1948
1949   rtx next;
1950
1951   while (1)
1952     {
1953       next = NEXT_INSN (start);
1954       if (GET_CODE (start) == NOTE && !can_delete_note_p (start))
1955         ;
1956       else if (GET_CODE (start) == CODE_LABEL
1957                && ! can_delete_label_p (start))
1958         {
1959           const char *name = LABEL_NAME (start);
1960           PUT_CODE (start, NOTE);
1961           NOTE_LINE_NUMBER (start) = NOTE_INSN_DELETED_LABEL;
1962           NOTE_SOURCE_FILE (start) = name;
1963         }
1964       else
1965         next = flow_delete_insn (start);
1966
1967       if (start == finish)
1968         break;
1969       start = next;
1970     }
1971 }
1972
1973 /* Delete the insns in a (non-live) block.  We physically delete every
1974    non-deleted-note insn, and update the flow graph appropriately.
1975
1976    Return nonzero if we deleted an exception handler.  */
1977
1978 /* ??? Preserving all such notes strikes me as wrong.  It would be nice
1979    to post-process the stream to remove empty blocks, loops, ranges, etc.  */
1980
1981 int
1982 flow_delete_block (b)
1983      basic_block b;
1984 {
1985   int deleted_handler = 0;
1986   rtx insn, end, tmp;
1987
1988   /* If the head of this block is a CODE_LABEL, then it might be the
1989      label for an exception handler which can't be reached.
1990
1991      We need to remove the label from the exception_handler_label list
1992      and remove the associated NOTE_INSN_EH_REGION_BEG and
1993      NOTE_INSN_EH_REGION_END notes.  */
1994
1995   insn = b->head;
1996   
1997   never_reached_warning (insn);
1998
1999   if (GET_CODE (insn) == CODE_LABEL)
2000     {
2001       rtx x, *prev = &exception_handler_labels;
2002
2003       for (x = exception_handler_labels; x; x = XEXP (x, 1))
2004         {
2005           if (XEXP (x, 0) == insn)
2006             {
2007               /* Found a match, splice this label out of the EH label list.  */
2008               *prev = XEXP (x, 1);
2009               XEXP (x, 1) = NULL_RTX;
2010               XEXP (x, 0) = NULL_RTX;
2011
2012               /* Remove the handler from all regions */
2013               remove_handler (insn);
2014               deleted_handler = 1;
2015               break;
2016             }
2017           prev = &XEXP (x, 1);
2018         }
2019     }
2020
2021   /* Include any jump table following the basic block.  */
2022   end = b->end;
2023   if (GET_CODE (end) == JUMP_INSN
2024       && (tmp = JUMP_LABEL (end)) != NULL_RTX
2025       && (tmp = NEXT_INSN (tmp)) != NULL_RTX
2026       && GET_CODE (tmp) == JUMP_INSN
2027       && (GET_CODE (PATTERN (tmp)) == ADDR_VEC
2028           || GET_CODE (PATTERN (tmp)) == ADDR_DIFF_VEC))
2029     end = tmp;
2030
2031   /* Include any barrier that may follow the basic block.  */
2032   tmp = next_nonnote_insn (end);
2033   if (tmp && GET_CODE (tmp) == BARRIER)
2034     end = tmp;
2035
2036   /* Selectively delete the entire chain.  */
2037   flow_delete_insn_chain (insn, end);
2038
2039   /* Remove the edges into and out of this block.  Note that there may 
2040      indeed be edges in, if we are removing an unreachable loop.  */
2041   {
2042     edge e, next, *q;
2043
2044     for (e = b->pred; e ; e = next)
2045       {
2046         for (q = &e->src->succ; *q != e; q = &(*q)->succ_next)
2047           continue;
2048         *q = e->succ_next;
2049         next = e->pred_next;
2050         n_edges--;
2051         free (e);
2052       }
2053     for (e = b->succ; e ; e = next)
2054       {
2055         for (q = &e->dest->pred; *q != e; q = &(*q)->pred_next)
2056           continue;
2057         *q = e->pred_next;
2058         next = e->succ_next;
2059         n_edges--;
2060         free (e);
2061       }
2062
2063     b->pred = NULL;
2064     b->succ = NULL;
2065   }
2066
2067   /* Remove the basic block from the array, and compact behind it.  */
2068   expunge_block (b);
2069
2070   return deleted_handler;
2071 }
2072
2073 /* Remove block B from the basic block array and compact behind it.  */
2074
2075 static void
2076 expunge_block (b)
2077      basic_block b;
2078 {
2079   int i, n = n_basic_blocks;
2080
2081   for (i = b->index; i + 1 < n; ++i)
2082     {
2083       basic_block x = BASIC_BLOCK (i + 1);
2084       BASIC_BLOCK (i) = x;
2085       x->index = i;
2086     }
2087
2088   basic_block_info->num_elements--;
2089   n_basic_blocks--;
2090 }
2091
2092 /* Delete INSN by patching it out.  Return the next insn.  */
2093
2094 rtx
2095 flow_delete_insn (insn)
2096      rtx insn;
2097 {
2098   rtx prev = PREV_INSN (insn);
2099   rtx next = NEXT_INSN (insn);
2100   rtx note;
2101
2102   PREV_INSN (insn) = NULL_RTX;
2103   NEXT_INSN (insn) = NULL_RTX;
2104   INSN_DELETED_P (insn) = 1;
2105   
2106   if (prev)
2107     NEXT_INSN (prev) = next;
2108   if (next)
2109     PREV_INSN (next) = prev;
2110   else
2111     set_last_insn (prev);
2112
2113   if (GET_CODE (insn) == CODE_LABEL)
2114     remove_node_from_expr_list (insn, &nonlocal_goto_handler_labels);
2115
2116   /* If deleting a jump, decrement the use count of the label.  Deleting
2117      the label itself should happen in the normal course of block merging.  */
2118   if (GET_CODE (insn) == JUMP_INSN
2119       && JUMP_LABEL (insn)
2120       && GET_CODE (JUMP_LABEL (insn)) == CODE_LABEL)
2121     LABEL_NUSES (JUMP_LABEL (insn))--;
2122
2123   /* Also if deleting an insn that references a label.  */
2124   else if ((note = find_reg_note (insn, REG_LABEL, NULL_RTX)) != NULL_RTX
2125            && GET_CODE (XEXP (note, 0)) == CODE_LABEL)
2126     LABEL_NUSES (XEXP (note, 0))--;
2127
2128   return next;
2129 }
2130
2131 /* True if a given label can be deleted.  */
2132
2133 static int 
2134 can_delete_label_p (label)
2135      rtx label;
2136 {
2137   rtx x;
2138
2139   if (LABEL_PRESERVE_P (label))
2140     return 0;
2141
2142   for (x = forced_labels; x ; x = XEXP (x, 1))
2143     if (label == XEXP (x, 0))
2144       return 0;
2145   for (x = label_value_list; x ; x = XEXP (x, 1))
2146     if (label == XEXP (x, 0))
2147       return 0;
2148   for (x = exception_handler_labels; x ; x = XEXP (x, 1))
2149     if (label == XEXP (x, 0))
2150       return 0;
2151
2152   /* User declared labels must be preserved.  */
2153   if (LABEL_NAME (label) != 0)
2154     return 0;
2155   
2156   return 1;
2157 }
2158
2159 static int
2160 tail_recursion_label_p (label)
2161      rtx label;
2162 {
2163   rtx x;
2164
2165   for (x = tail_recursion_label_list; x ; x = XEXP (x, 1))
2166     if (label == XEXP (x, 0))
2167       return 1;
2168
2169   return 0;
2170 }
2171
2172 /* Blocks A and B are to be merged into a single block A.  The insns
2173    are already contiguous, hence `nomove'.  */
2174
2175 void
2176 merge_blocks_nomove (a, b)
2177      basic_block a, b;
2178 {
2179   edge e;
2180   rtx b_head, b_end, a_end;
2181   rtx del_first = NULL_RTX, del_last = NULL_RTX;
2182   int b_empty = 0;
2183
2184   /* If there was a CODE_LABEL beginning B, delete it.  */
2185   b_head = b->head;
2186   b_end = b->end;
2187   if (GET_CODE (b_head) == CODE_LABEL)
2188     {
2189       /* Detect basic blocks with nothing but a label.  This can happen
2190          in particular at the end of a function.  */
2191       if (b_head == b_end)
2192         b_empty = 1;
2193       del_first = del_last = b_head;
2194       b_head = NEXT_INSN (b_head);
2195     }
2196
2197   /* Delete the basic block note.  */
2198   if (NOTE_INSN_BASIC_BLOCK_P (b_head))
2199     {
2200       if (b_head == b_end)
2201         b_empty = 1;
2202       if (! del_last)
2203         del_first = b_head;
2204       del_last = b_head;
2205       b_head = NEXT_INSN (b_head);
2206     }
2207
2208   /* If there was a jump out of A, delete it.  */
2209   a_end = a->end;
2210   if (GET_CODE (a_end) == JUMP_INSN)
2211     {
2212       rtx prev;
2213
2214       prev = prev_nonnote_insn (a_end);
2215       if (!prev) 
2216         prev = a->head;
2217
2218       del_first = a_end;
2219
2220 #ifdef HAVE_cc0
2221       /* If this was a conditional jump, we need to also delete
2222          the insn that set cc0.  */
2223       if (prev && sets_cc0_p (prev))
2224         {
2225           rtx tmp = prev;
2226           prev = prev_nonnote_insn (prev);
2227           if (!prev)
2228             prev = a->head;
2229           del_first = tmp;
2230         }
2231 #endif
2232
2233       a_end = prev;
2234     }
2235   else if (GET_CODE (NEXT_INSN (a_end)) == BARRIER)
2236     del_first = NEXT_INSN (a_end);
2237
2238   /* Delete everything marked above as well as crap that might be
2239      hanging out between the two blocks.  */
2240   flow_delete_insn_chain (del_first, del_last);
2241
2242   /* Normally there should only be one successor of A and that is B, but
2243      partway though the merge of blocks for conditional_execution we'll
2244      be merging a TEST block with THEN and ELSE successors.  Free the
2245      whole lot of them and hope the caller knows what they're doing.  */
2246   while (a->succ)
2247     remove_edge (a->succ);
2248
2249   /* Adjust the edges out of B for the new owner.  */
2250   for (e = b->succ; e ; e = e->succ_next)
2251     e->src = a;
2252   a->succ = b->succ;
2253
2254   /* B hasn't quite yet ceased to exist.  Attempt to prevent mishap.  */
2255   b->pred = b->succ = NULL;
2256
2257   /* Reassociate the insns of B with A.  */
2258   if (!b_empty)
2259     {
2260       if (basic_block_for_insn)
2261         {
2262           BLOCK_FOR_INSN (b_head) = a;
2263           while (b_head != b_end)
2264             {
2265               b_head = NEXT_INSN (b_head);
2266               BLOCK_FOR_INSN (b_head) = a;
2267             }
2268         }
2269       a_end = b_end;
2270     }
2271   a->end = a_end;
2272
2273   expunge_block (b);
2274 }
2275
2276 /* Blocks A and B are to be merged into a single block.  A has no incoming
2277    fallthru edge, so it can be moved before B without adding or modifying
2278    any jumps (aside from the jump from A to B).  */
2279
2280 static int
2281 merge_blocks_move_predecessor_nojumps (a, b)
2282      basic_block a, b;
2283 {
2284   rtx start, end, barrier;
2285   int index;
2286
2287   start = a->head;
2288   end = a->end;
2289
2290   barrier = next_nonnote_insn (end);
2291   if (GET_CODE (barrier) != BARRIER)
2292     abort ();
2293   flow_delete_insn (barrier);
2294
2295   /* Move block and loop notes out of the chain so that we do not
2296      disturb their order.
2297
2298      ??? A better solution would be to squeeze out all the non-nested notes
2299      and adjust the block trees appropriately.   Even better would be to have
2300      a tighter connection between block trees and rtl so that this is not
2301      necessary.  */
2302   start = squeeze_notes (start, end);
2303
2304   /* Scramble the insn chain.  */
2305   if (end != PREV_INSN (b->head))
2306     reorder_insns (start, end, PREV_INSN (b->head));
2307
2308   if (rtl_dump_file)
2309     {
2310       fprintf (rtl_dump_file, "Moved block %d before %d and merged.\n",
2311                a->index, b->index);
2312     }
2313
2314   /* Swap the records for the two blocks around.  Although we are deleting B,
2315      A is now where B was and we want to compact the BB array from where
2316      A used to be.  */
2317   BASIC_BLOCK(a->index) = b;
2318   BASIC_BLOCK(b->index) = a;
2319   index = a->index;
2320   a->index = b->index;
2321   b->index = index;
2322   
2323   /* Now blocks A and B are contiguous.  Merge them.  */
2324   merge_blocks_nomove (a, b);
2325
2326   return 1;
2327 }
2328
2329 /* Blocks A and B are to be merged into a single block.  B has no outgoing
2330    fallthru edge, so it can be moved after A without adding or modifying
2331    any jumps (aside from the jump from A to B).  */
2332
2333 static int
2334 merge_blocks_move_successor_nojumps (a, b)
2335      basic_block a, b;
2336 {
2337   rtx start, end, barrier;
2338
2339   start = b->head;
2340   end = b->end;
2341   barrier = NEXT_INSN (end);
2342
2343   /* Recognize a jump table following block B.  */
2344   if (GET_CODE (barrier) == CODE_LABEL
2345       && NEXT_INSN (barrier)
2346       && GET_CODE (NEXT_INSN (barrier)) == JUMP_INSN
2347       && (GET_CODE (PATTERN (NEXT_INSN (barrier))) == ADDR_VEC
2348           || GET_CODE (PATTERN (NEXT_INSN (barrier))) == ADDR_DIFF_VEC))
2349     {
2350       end = NEXT_INSN (barrier);
2351       barrier = NEXT_INSN (end);
2352     }
2353
2354   /* There had better have been a barrier there.  Delete it.  */
2355   if (GET_CODE (barrier) != BARRIER)
2356     abort ();
2357   flow_delete_insn (barrier);
2358
2359   /* Move block and loop notes out of the chain so that we do not
2360      disturb their order.
2361
2362      ??? A better solution would be to squeeze out all the non-nested notes
2363      and adjust the block trees appropriately.   Even better would be to have
2364      a tighter connection between block trees and rtl so that this is not
2365      necessary.  */
2366   start = squeeze_notes (start, end);
2367
2368   /* Scramble the insn chain.  */
2369   reorder_insns (start, end, a->end);
2370
2371   /* Now blocks A and B are contiguous.  Merge them.  */
2372   merge_blocks_nomove (a, b);
2373
2374   if (rtl_dump_file)
2375     {
2376       fprintf (rtl_dump_file, "Moved block %d after %d and merged.\n",
2377                b->index, a->index);
2378     }
2379
2380   return 1;
2381 }
2382
2383 /* Attempt to merge basic blocks that are potentially non-adjacent.  
2384    Return true iff the attempt succeeded.  */
2385
2386 static int
2387 merge_blocks (e, b, c)
2388      edge e;
2389      basic_block b, c;
2390 {
2391   /* If C has a tail recursion label, do not merge.  There is no
2392      edge recorded from the call_placeholder back to this label, as
2393      that would make optimize_sibling_and_tail_recursive_calls more
2394      complex for no gain.  */
2395   if (GET_CODE (c->head) == CODE_LABEL
2396       && tail_recursion_label_p (c->head))
2397     return 0;
2398
2399   /* If B has a fallthru edge to C, no need to move anything.  */
2400   if (e->flags & EDGE_FALLTHRU)
2401     {
2402       merge_blocks_nomove (b, c);
2403
2404       if (rtl_dump_file)
2405         {
2406           fprintf (rtl_dump_file, "Merged %d and %d without moving.\n",
2407                    b->index, c->index);
2408         }
2409
2410       return 1;
2411     }
2412   else
2413     {
2414       edge tmp_edge;
2415       basic_block d;
2416       int c_has_outgoing_fallthru;
2417       int b_has_incoming_fallthru;
2418
2419       /* We must make sure to not munge nesting of exception regions,
2420          lexical blocks, and loop notes.
2421   
2422          The first is taken care of by requiring that the active eh
2423          region at the end of one block always matches the active eh
2424          region at the beginning of the next block.
2425   
2426          The later two are taken care of by squeezing out all the notes.  */
2427   
2428       /* ???  A throw/catch edge (or any abnormal edge) should be rarely
2429          executed and we may want to treat blocks which have two out
2430          edges, one normal, one abnormal as only having one edge for
2431          block merging purposes.  */
2432
2433       for (tmp_edge = c->succ; tmp_edge ; tmp_edge = tmp_edge->succ_next)
2434         if (tmp_edge->flags & EDGE_FALLTHRU)
2435           break;
2436       c_has_outgoing_fallthru = (tmp_edge != NULL);
2437
2438       for (tmp_edge = b->pred; tmp_edge ; tmp_edge = tmp_edge->pred_next)
2439         if (tmp_edge->flags & EDGE_FALLTHRU)
2440           break;
2441       b_has_incoming_fallthru = (tmp_edge != NULL);
2442
2443       /* If B does not have an incoming fallthru, and the exception regions
2444          match, then it can be moved immediately before C without introducing
2445          or modifying jumps.
2446
2447          C can not be the first block, so we do not have to worry about
2448          accessing a non-existent block.  */
2449       d = BASIC_BLOCK (c->index - 1);
2450       if (! b_has_incoming_fallthru
2451           && d->eh_end == b->eh_beg
2452           && b->eh_end == c->eh_beg)
2453         return merge_blocks_move_predecessor_nojumps (b, c);
2454
2455       /* Otherwise, we're going to try to move C after B.  Make sure the
2456          exception regions match.
2457
2458          If B is the last basic block, then we must not try to access the
2459          block structure for block B + 1.  Luckily in that case we do not
2460          need to worry about matching exception regions.  */
2461       d = (b->index + 1 < n_basic_blocks ? BASIC_BLOCK (b->index + 1) : NULL);
2462       if (b->eh_end == c->eh_beg
2463           && (d == NULL || c->eh_end == d->eh_beg))
2464         {
2465           /* If C does not have an outgoing fallthru, then it can be moved
2466              immediately after B without introducing or modifying jumps.  */
2467           if (! c_has_outgoing_fallthru)
2468             return merge_blocks_move_successor_nojumps (b, c);
2469
2470           /* Otherwise, we'll need to insert an extra jump, and possibly
2471              a new block to contain it.  */
2472           /* ??? Not implemented yet.  */
2473         }
2474
2475       return 0;
2476     }
2477 }
2478
2479 /* Top level driver for merge_blocks.  */
2480
2481 static void
2482 try_merge_blocks ()
2483 {
2484   int i;
2485
2486   /* Attempt to merge blocks as made possible by edge removal.  If a block
2487      has only one successor, and the successor has only one predecessor, 
2488      they may be combined.  */
2489
2490   for (i = 0; i < n_basic_blocks; )
2491     {
2492       basic_block c, b = BASIC_BLOCK (i);
2493       edge s;
2494
2495       /* A loop because chains of blocks might be combineable.  */
2496       while ((s = b->succ) != NULL
2497              && s->succ_next == NULL
2498              && (s->flags & EDGE_EH) == 0
2499              && (c = s->dest) != EXIT_BLOCK_PTR
2500              && c->pred->pred_next == NULL
2501              /* If the jump insn has side effects, we can't kill the edge.  */
2502              && (GET_CODE (b->end) != JUMP_INSN
2503                  || onlyjump_p (b->end))
2504              && merge_blocks (s, b, c))
2505         continue;
2506
2507       /* Don't get confused by the index shift caused by deleting blocks.  */
2508       i = b->index + 1;
2509     }
2510 }
2511
2512 /* The given edge should potentially be a fallthru edge.  If that is in
2513    fact true, delete the jump and barriers that are in the way.  */
2514
2515 void
2516 tidy_fallthru_edge (e, b, c)
2517      edge e;
2518      basic_block b, c;
2519 {
2520   rtx q;
2521
2522   /* ??? In a late-running flow pass, other folks may have deleted basic
2523      blocks by nopping out blocks, leaving multiple BARRIERs between here
2524      and the target label. They ought to be chastized and fixed.
2525
2526      We can also wind up with a sequence of undeletable labels between
2527      one block and the next.
2528
2529      So search through a sequence of barriers, labels, and notes for
2530      the head of block C and assert that we really do fall through.  */
2531
2532   if (next_real_insn (b->end) != next_real_insn (PREV_INSN (c->head)))
2533     return;
2534
2535   /* Remove what will soon cease being the jump insn from the source block.
2536      If block B consisted only of this single jump, turn it into a deleted
2537      note.  */
2538   q = b->end;
2539   if (GET_CODE (q) == JUMP_INSN
2540       && onlyjump_p (q)
2541       && (any_uncondjump_p (q)
2542           || (b->succ == e && e->succ_next == NULL)))
2543     {
2544 #ifdef HAVE_cc0
2545       /* If this was a conditional jump, we need to also delete
2546          the insn that set cc0.  */
2547       if (any_condjump_p (q) && sets_cc0_p (PREV_INSN (q)))
2548         q = PREV_INSN (q);
2549 #endif
2550
2551       if (b->head == q)
2552         {
2553           PUT_CODE (q, NOTE);
2554           NOTE_LINE_NUMBER (q) = NOTE_INSN_DELETED;
2555           NOTE_SOURCE_FILE (q) = 0;
2556         }
2557       else
2558         b->end = q = PREV_INSN (q);
2559     }
2560
2561   /* Selectively unlink the sequence.  */
2562   if (q != PREV_INSN (c->head))
2563     flow_delete_insn_chain (NEXT_INSN (q), PREV_INSN (c->head));
2564
2565   e->flags |= EDGE_FALLTHRU;
2566 }
2567
2568 /* Fix up edges that now fall through, or rather should now fall through
2569    but previously required a jump around now deleted blocks.  Simplify
2570    the search by only examining blocks numerically adjacent, since this
2571    is how find_basic_blocks created them.  */
2572
2573 static void
2574 tidy_fallthru_edges ()
2575 {
2576   int i;
2577
2578   for (i = 1; i < n_basic_blocks; ++i)
2579     {
2580       basic_block b = BASIC_BLOCK (i - 1);
2581       basic_block c = BASIC_BLOCK (i);
2582       edge s;
2583
2584       /* We care about simple conditional or unconditional jumps with
2585          a single successor.
2586
2587          If we had a conditional branch to the next instruction when
2588          find_basic_blocks was called, then there will only be one
2589          out edge for the block which ended with the conditional
2590          branch (since we do not create duplicate edges).
2591
2592          Furthermore, the edge will be marked as a fallthru because we
2593          merge the flags for the duplicate edges.  So we do not want to
2594          check that the edge is not a FALLTHRU edge.  */
2595       if ((s = b->succ) != NULL
2596           && s->succ_next == NULL
2597           && s->dest == c
2598           /* If the jump insn has side effects, we can't tidy the edge.  */
2599           && (GET_CODE (b->end) != JUMP_INSN
2600               || onlyjump_p (b->end)))
2601         tidy_fallthru_edge (s, b, c);
2602     }
2603 }
2604 \f
2605 /* Perform data flow analysis.
2606    F is the first insn of the function; FLAGS is a set of PROP_* flags
2607    to be used in accumulating flow info.  */
2608
2609 void
2610 life_analysis (f, file, flags)
2611      rtx f;
2612      FILE *file;
2613      int flags;
2614 {
2615 #ifdef ELIMINABLE_REGS
2616   register int i;
2617   static struct {int from, to; } eliminables[] = ELIMINABLE_REGS;
2618 #endif
2619
2620   /* Record which registers will be eliminated.  We use this in
2621      mark_used_regs.  */
2622
2623   CLEAR_HARD_REG_SET (elim_reg_set);
2624
2625 #ifdef ELIMINABLE_REGS
2626   for (i = 0; i < (int) (sizeof eliminables / sizeof eliminables[0]); i++)
2627     SET_HARD_REG_BIT (elim_reg_set, eliminables[i].from);
2628 #else
2629   SET_HARD_REG_BIT (elim_reg_set, FRAME_POINTER_REGNUM);
2630 #endif
2631
2632   if (! optimize)
2633     flags &= ~(PROP_LOG_LINKS | PROP_AUTOINC);
2634
2635   /* The post-reload life analysis have (on a global basis) the same
2636      registers live as was computed by reload itself.  elimination
2637      Otherwise offsets and such may be incorrect.
2638
2639      Reload will make some registers as live even though they do not
2640      appear in the rtl.  
2641
2642      We don't want to create new auto-incs after reload, since they
2643      are unlikely to be useful and can cause problems with shared
2644      stack slots.  */
2645   if (reload_completed)
2646     flags &= ~(PROP_REG_INFO | PROP_AUTOINC);
2647
2648   /* We want alias analysis information for local dead store elimination.  */
2649   if (optimize && (flags & PROP_SCAN_DEAD_CODE))
2650     init_alias_analysis ();
2651
2652   /* Always remove no-op moves.  Do this before other processing so
2653      that we don't have to keep re-scanning them.  */
2654   delete_noop_moves (f);
2655
2656   /* Some targets can emit simpler epilogues if they know that sp was
2657      not ever modified during the function.  After reload, of course,
2658      we've already emitted the epilogue so there's no sense searching.  */
2659   if (! reload_completed)
2660     notice_stack_pointer_modification (f);
2661     
2662   /* Allocate and zero out data structures that will record the
2663      data from lifetime analysis.  */
2664   allocate_reg_life_data ();
2665   allocate_bb_life_data ();
2666
2667   /* Find the set of registers live on function exit.  */
2668   mark_regs_live_at_end (EXIT_BLOCK_PTR->global_live_at_start);
2669
2670   /* "Update" life info from zero.  It'd be nice to begin the
2671      relaxation with just the exit and noreturn blocks, but that set
2672      is not immediately handy.  */
2673
2674   if (flags & PROP_REG_INFO)
2675     memset (regs_ever_live, 0, sizeof(regs_ever_live));
2676   update_life_info (NULL, UPDATE_LIFE_GLOBAL, flags);
2677
2678   /* Clean up.  */
2679   if (optimize && (flags & PROP_SCAN_DEAD_CODE))
2680     end_alias_analysis ();
2681
2682   if (file)
2683     dump_flow_info (file);
2684
2685   free_basic_block_vars (1);
2686 }
2687
2688 /* A subroutine of verify_wide_reg, called through for_each_rtx.
2689    Search for REGNO.  If found, abort if it is not wider than word_mode.  */
2690
2691 static int
2692 verify_wide_reg_1 (px, pregno)
2693      rtx *px;
2694      void *pregno;
2695 {
2696   rtx x = *px;
2697   unsigned int regno = *(int *) pregno;
2698
2699   if (GET_CODE (x) == REG && REGNO (x) == regno)
2700     {
2701       if (GET_MODE_BITSIZE (GET_MODE (x)) <= BITS_PER_WORD)
2702         abort ();
2703       return 1;
2704     }
2705   return 0;
2706 }
2707
2708 /* A subroutine of verify_local_live_at_start.  Search through insns
2709    between HEAD and END looking for register REGNO.  */
2710
2711 static void
2712 verify_wide_reg (regno, head, end)
2713      int regno;
2714      rtx head, end;
2715 {
2716   while (1)
2717     {
2718       if (INSN_P (head)
2719           && for_each_rtx (&PATTERN (head), verify_wide_reg_1, &regno))
2720         return;
2721       if (head == end)
2722         break;
2723       head = NEXT_INSN (head);
2724     }
2725
2726   /* We didn't find the register at all.  Something's way screwy.  */
2727   abort ();
2728 }
2729
2730 /* A subroutine of update_life_info.  Verify that there are no untoward
2731    changes in live_at_start during a local update.  */
2732
2733 static void
2734 verify_local_live_at_start (new_live_at_start, bb)
2735      regset new_live_at_start;
2736      basic_block bb;
2737 {
2738   if (reload_completed)
2739     {
2740       /* After reload, there are no pseudos, nor subregs of multi-word
2741          registers.  The regsets should exactly match.  */
2742       if (! REG_SET_EQUAL_P (new_live_at_start, bb->global_live_at_start))
2743         abort ();
2744     }
2745   else
2746     {
2747       int i;
2748
2749       /* Find the set of changed registers.  */
2750       XOR_REG_SET (new_live_at_start, bb->global_live_at_start);
2751
2752       EXECUTE_IF_SET_IN_REG_SET (new_live_at_start, 0, i,
2753         {
2754           /* No registers should die.  */
2755           if (REGNO_REG_SET_P (bb->global_live_at_start, i))
2756             abort ();
2757           /* Verify that the now-live register is wider than word_mode.  */
2758           verify_wide_reg (i, bb->head, bb->end);
2759         });
2760     }
2761 }
2762
2763 /* Updates life information starting with the basic blocks set in BLOCKS.
2764    If BLOCKS is null, consider it to be the universal set.
2765    
2766    If EXTENT is UPDATE_LIFE_LOCAL, such as after splitting or peepholeing,
2767    we are only expecting local modifications to basic blocks.  If we find
2768    extra registers live at the beginning of a block, then we either killed
2769    useful data, or we have a broken split that wants data not provided.
2770    If we find registers removed from live_at_start, that means we have
2771    a broken peephole that is killing a register it shouldn't.
2772
2773    ??? This is not true in one situation -- when a pre-reload splitter
2774    generates subregs of a multi-word pseudo, current life analysis will
2775    lose the kill.  So we _can_ have a pseudo go live.  How irritating.
2776
2777    Including PROP_REG_INFO does not properly refresh regs_ever_live
2778    unless the caller resets it to zero.  */
2779
2780 void
2781 update_life_info (blocks, extent, prop_flags)
2782      sbitmap blocks;
2783      enum update_life_extent extent;
2784      int prop_flags;
2785 {
2786   regset tmp;
2787   regset_head tmp_head;
2788   int i;
2789
2790   tmp = INITIALIZE_REG_SET (tmp_head);
2791
2792   /* For a global update, we go through the relaxation process again.  */
2793   if (extent != UPDATE_LIFE_LOCAL)
2794     {
2795       calculate_global_regs_live (blocks, blocks,
2796                                   prop_flags & PROP_SCAN_DEAD_CODE);
2797
2798       /* If asked, remove notes from the blocks we'll update.  */
2799       if (extent == UPDATE_LIFE_GLOBAL_RM_NOTES)
2800         count_or_remove_death_notes (blocks, 1);
2801     }
2802
2803   if (blocks)
2804     {
2805       EXECUTE_IF_SET_IN_SBITMAP (blocks, 0, i,
2806         {
2807           basic_block bb = BASIC_BLOCK (i);
2808
2809           COPY_REG_SET (tmp, bb->global_live_at_end);
2810           propagate_block (bb, tmp, (regset) NULL, prop_flags);
2811
2812           if (extent == UPDATE_LIFE_LOCAL)
2813             verify_local_live_at_start (tmp, bb);
2814         });
2815     }
2816   else
2817     {
2818       for (i = n_basic_blocks - 1; i >= 0; --i)
2819         {
2820           basic_block bb = BASIC_BLOCK (i);
2821
2822           COPY_REG_SET (tmp, bb->global_live_at_end);
2823           propagate_block (bb, tmp, (regset) NULL, prop_flags);
2824
2825           if (extent == UPDATE_LIFE_LOCAL)
2826             verify_local_live_at_start (tmp, bb);
2827         }
2828     }
2829
2830   FREE_REG_SET (tmp);
2831
2832   if (prop_flags & PROP_REG_INFO)
2833     {
2834       /* The only pseudos that are live at the beginning of the function
2835          are those that were not set anywhere in the function.  local-alloc
2836          doesn't know how to handle these correctly, so mark them as not
2837          local to any one basic block.  */
2838       EXECUTE_IF_SET_IN_REG_SET (ENTRY_BLOCK_PTR->global_live_at_end,
2839                                  FIRST_PSEUDO_REGISTER, i,
2840                                  { REG_BASIC_BLOCK (i) = REG_BLOCK_GLOBAL; });
2841
2842       /* We have a problem with any pseudoreg that lives across the setjmp. 
2843          ANSI says that if a user variable does not change in value between
2844          the setjmp and the longjmp, then the longjmp preserves it.  This
2845          includes longjmp from a place where the pseudo appears dead.
2846          (In principle, the value still exists if it is in scope.)
2847          If the pseudo goes in a hard reg, some other value may occupy
2848          that hard reg where this pseudo is dead, thus clobbering the pseudo.
2849          Conclusion: such a pseudo must not go in a hard reg.  */
2850       EXECUTE_IF_SET_IN_REG_SET (regs_live_at_setjmp,
2851                                  FIRST_PSEUDO_REGISTER, i,
2852                                  {
2853                                    if (regno_reg_rtx[i] != 0)
2854                                      {
2855                                        REG_LIVE_LENGTH (i) = -1;
2856                                        REG_BASIC_BLOCK (i) = REG_BLOCK_UNKNOWN;
2857                                      }
2858                                  });
2859     }
2860 }
2861
2862 /* Free the variables allocated by find_basic_blocks.
2863
2864    KEEP_HEAD_END_P is non-zero if basic_block_info is not to be freed.  */
2865
2866 void
2867 free_basic_block_vars (keep_head_end_p)
2868      int keep_head_end_p;
2869 {
2870   if (basic_block_for_insn)
2871     {
2872       VARRAY_FREE (basic_block_for_insn);
2873       basic_block_for_insn = NULL;
2874     }
2875
2876   if (! keep_head_end_p)
2877     {
2878       clear_edges ();
2879       VARRAY_FREE (basic_block_info);
2880       n_basic_blocks = 0;
2881
2882       ENTRY_BLOCK_PTR->aux = NULL;
2883       ENTRY_BLOCK_PTR->global_live_at_end = NULL;
2884       EXIT_BLOCK_PTR->aux = NULL;
2885       EXIT_BLOCK_PTR->global_live_at_start = NULL;
2886     }
2887 }
2888
2889 /* Return nonzero if the destination of SET equals the source.  */
2890 static int
2891 set_noop_p (set)
2892      rtx set;
2893 {
2894   rtx src = SET_SRC (set);
2895   rtx dst = SET_DEST (set);
2896
2897   if (GET_CODE (src) == SUBREG && GET_CODE (dst) == SUBREG)
2898     {
2899       if (SUBREG_WORD (src) != SUBREG_WORD (dst))
2900         return 0;
2901       src = SUBREG_REG (src);
2902       dst = SUBREG_REG (dst);
2903     }
2904
2905   return (GET_CODE (src) == REG && GET_CODE (dst) == REG
2906           && REGNO (src) == REGNO (dst));
2907 }
2908
2909 /* Return nonzero if an insn consists only of SETs, each of which only sets a
2910    value to itself.  */
2911 static int
2912 noop_move_p (insn)
2913      rtx insn;
2914 {
2915   rtx pat = PATTERN (insn);
2916
2917   /* Insns carrying these notes are useful later on.  */
2918   if (find_reg_note (insn, REG_EQUAL, NULL_RTX))
2919     return 0;
2920
2921   if (GET_CODE (pat) == SET && set_noop_p (pat))
2922     return 1;
2923
2924   if (GET_CODE (pat) == PARALLEL)
2925     {
2926       int i;
2927       /* If nothing but SETs of registers to themselves,
2928          this insn can also be deleted.  */
2929       for (i = 0; i < XVECLEN (pat, 0); i++)
2930         {
2931           rtx tem = XVECEXP (pat, 0, i);
2932
2933           if (GET_CODE (tem) == USE
2934               || GET_CODE (tem) == CLOBBER)
2935             continue;
2936
2937           if (GET_CODE (tem) != SET || ! set_noop_p (tem))
2938             return 0;
2939         }
2940
2941       return 1;
2942     }
2943   return 0;
2944 }
2945
2946 /* Delete any insns that copy a register to itself.  */
2947
2948 static void
2949 delete_noop_moves (f)
2950      rtx f;
2951 {
2952   rtx insn;
2953   for (insn = f; insn; insn = NEXT_INSN (insn))
2954     {
2955       if (GET_CODE (insn) == INSN && noop_move_p (insn))
2956         {
2957           PUT_CODE (insn, NOTE);
2958           NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
2959           NOTE_SOURCE_FILE (insn) = 0;
2960         }
2961     }
2962 }
2963
2964 /* Determine if the stack pointer is constant over the life of the function.
2965    Only useful before prologues have been emitted.  */
2966
2967 static void
2968 notice_stack_pointer_modification_1 (x, pat, data)
2969      rtx x;
2970      rtx pat ATTRIBUTE_UNUSED;
2971      void *data ATTRIBUTE_UNUSED;
2972 {
2973   if (x == stack_pointer_rtx
2974       /* The stack pointer is only modified indirectly as the result
2975          of a push until later in flow.  See the comments in rtl.texi
2976          regarding Embedded Side-Effects on Addresses.  */
2977       || (GET_CODE (x) == MEM
2978           && (GET_CODE (XEXP (x, 0)) == PRE_DEC
2979               || GET_CODE (XEXP (x, 0)) == PRE_INC
2980               || GET_CODE (XEXP (x, 0)) == POST_DEC
2981               || GET_CODE (XEXP (x, 0)) == POST_INC)
2982           && XEXP (XEXP (x, 0), 0) == stack_pointer_rtx))
2983     current_function_sp_is_unchanging = 0;
2984 }
2985
2986 static void
2987 notice_stack_pointer_modification (f)
2988      rtx f;
2989 {
2990   rtx insn;
2991
2992   /* Assume that the stack pointer is unchanging if alloca hasn't
2993      been used.  */
2994   current_function_sp_is_unchanging = !current_function_calls_alloca;
2995   if (! current_function_sp_is_unchanging)
2996     return;
2997
2998   for (insn = f; insn; insn = NEXT_INSN (insn))
2999     {
3000       if (INSN_P (insn))
3001         {
3002           /* Check if insn modifies the stack pointer.  */
3003           note_stores (PATTERN (insn), notice_stack_pointer_modification_1,
3004                        NULL);
3005           if (! current_function_sp_is_unchanging)
3006             return;
3007         }
3008     }
3009 }
3010
3011 /* Mark a register in SET.  Hard registers in large modes get all
3012    of their component registers set as well.  */
3013 static void
3014 mark_reg (reg, xset)
3015      rtx reg;
3016      void *xset;
3017 {
3018   regset set = (regset) xset;
3019   int regno = REGNO (reg);
3020
3021   if (GET_MODE (reg) == BLKmode)
3022     abort ();
3023
3024   SET_REGNO_REG_SET (set, regno);
3025   if (regno < FIRST_PSEUDO_REGISTER)
3026     {
3027       int n = HARD_REGNO_NREGS (regno, GET_MODE (reg));
3028       while (--n > 0)
3029         SET_REGNO_REG_SET (set, regno + n);
3030     }
3031 }
3032
3033 /* Mark those regs which are needed at the end of the function as live
3034    at the end of the last basic block.  */
3035 static void
3036 mark_regs_live_at_end (set)
3037      regset set;
3038 {
3039   int i;
3040
3041   /* If exiting needs the right stack value, consider the stack pointer
3042      live at the end of the function.  */
3043   if ((HAVE_epilogue && reload_completed)
3044       || ! EXIT_IGNORE_STACK
3045       || (! FRAME_POINTER_REQUIRED
3046           && ! current_function_calls_alloca
3047           && flag_omit_frame_pointer)
3048       || current_function_sp_is_unchanging)
3049     {
3050       SET_REGNO_REG_SET (set, STACK_POINTER_REGNUM);
3051     }
3052
3053   /* Mark the frame pointer if needed at the end of the function.  If
3054      we end up eliminating it, it will be removed from the live list
3055      of each basic block by reload.  */
3056
3057   if (! reload_completed || frame_pointer_needed)
3058     {
3059       SET_REGNO_REG_SET (set, FRAME_POINTER_REGNUM);
3060 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
3061       /* If they are different, also mark the hard frame pointer as live.  */
3062       if (! LOCAL_REGNO (HARD_FRAME_POINTER_REGNUM))
3063         SET_REGNO_REG_SET (set, HARD_FRAME_POINTER_REGNUM);
3064 #endif      
3065     }
3066
3067 #ifdef PIC_OFFSET_TABLE_REGNUM
3068 #ifndef PIC_OFFSET_TABLE_REG_CALL_CLOBBERED
3069   /* Many architectures have a GP register even without flag_pic.
3070      Assume the pic register is not in use, or will be handled by
3071      other means, if it is not fixed.  */
3072   if (fixed_regs[PIC_OFFSET_TABLE_REGNUM])
3073     SET_REGNO_REG_SET (set, PIC_OFFSET_TABLE_REGNUM);
3074 #endif
3075 #endif
3076
3077   /* Mark all global registers, and all registers used by the epilogue
3078      as being live at the end of the function since they may be
3079      referenced by our caller.  */
3080   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3081     if (global_regs[i] || EPILOGUE_USES (i))
3082       SET_REGNO_REG_SET (set, i);
3083
3084   /* Mark all call-saved registers that we actaully used.  */
3085   if (HAVE_epilogue && reload_completed)
3086     {
3087       for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3088         if (regs_ever_live[i] && ! call_used_regs[i] && ! LOCAL_REGNO (i))
3089           SET_REGNO_REG_SET (set, i);
3090     }
3091
3092   /* Mark function return value.  */
3093   diddle_return_value (mark_reg, set);
3094 }
3095
3096 /* Callback function for for_each_successor_phi.  DATA is a regset.
3097    Sets the SRC_REGNO, the regno of the phi alternative for phi node
3098    INSN, in the regset.  */
3099
3100 static int
3101 set_phi_alternative_reg (insn, dest_regno, src_regno, data)
3102      rtx insn ATTRIBUTE_UNUSED;
3103      int dest_regno ATTRIBUTE_UNUSED;
3104      int src_regno;
3105      void *data;
3106 {
3107   regset live = (regset) data;
3108   SET_REGNO_REG_SET (live, src_regno);
3109   return 0;
3110 }
3111
3112 /* Propagate global life info around the graph of basic blocks.  Begin
3113    considering blocks with their corresponding bit set in BLOCKS_IN. 
3114    If BLOCKS_IN is null, consider it the universal set.
3115
3116    BLOCKS_OUT is set for every block that was changed.  */
3117
3118 static void
3119 calculate_global_regs_live (blocks_in, blocks_out, flags)
3120      sbitmap blocks_in, blocks_out;
3121      int flags;
3122 {
3123   basic_block *queue, *qhead, *qtail, *qend;
3124   regset tmp, new_live_at_end;
3125   regset_head tmp_head;
3126   regset_head new_live_at_end_head;
3127   int i;
3128
3129   tmp = INITIALIZE_REG_SET (tmp_head);
3130   new_live_at_end = INITIALIZE_REG_SET (new_live_at_end_head);
3131
3132   /* Create a worklist.  Allocate an extra slot for ENTRY_BLOCK, and one
3133      because the `head == tail' style test for an empty queue doesn't 
3134      work with a full queue.  */
3135   queue = (basic_block *) xmalloc ((n_basic_blocks + 2) * sizeof (*queue));
3136   qtail = queue;
3137   qhead = qend = queue + n_basic_blocks + 2;
3138
3139   /* Clear out the garbage that might be hanging out in bb->aux.  */
3140   for (i = n_basic_blocks - 1; i >= 0; --i)
3141     BASIC_BLOCK (i)->aux = NULL;
3142
3143   /* Queue the blocks set in the initial mask.  Do this in reverse block
3144      number order so that we are more likely for the first round to do 
3145      useful work.  We use AUX non-null to flag that the block is queued.  */
3146   if (blocks_in)
3147     {
3148       EXECUTE_IF_SET_IN_SBITMAP (blocks_in, 0, i,
3149         {
3150           basic_block bb = BASIC_BLOCK (i);
3151           *--qhead = bb;
3152           bb->aux = bb;
3153         });
3154     }
3155   else
3156     {
3157       for (i = 0; i < n_basic_blocks; ++i)
3158         {
3159           basic_block bb = BASIC_BLOCK (i);
3160           *--qhead = bb;
3161           bb->aux = bb;
3162         }
3163     }
3164
3165   if (blocks_out)
3166     sbitmap_zero (blocks_out);
3167
3168   while (qhead != qtail)
3169     {
3170       int rescan, changed;
3171       basic_block bb;
3172       edge e;
3173
3174       bb = *qhead++;
3175       if (qhead == qend)
3176         qhead = queue;
3177       bb->aux = NULL;
3178
3179       /* Begin by propogating live_at_start from the successor blocks.  */
3180       CLEAR_REG_SET (new_live_at_end);
3181       for (e = bb->succ; e ; e = e->succ_next)
3182         {
3183           basic_block sb = e->dest;
3184           IOR_REG_SET (new_live_at_end, sb->global_live_at_start);
3185         }
3186
3187       /* Force the stack pointer to be live -- which might not already be 
3188          the case for blocks within infinite loops.  */
3189       SET_REGNO_REG_SET (new_live_at_end, STACK_POINTER_REGNUM);
3190
3191       /* Regs used in phi nodes are not included in
3192          global_live_at_start, since they are live only along a
3193          particular edge.  Set those regs that are live because of a
3194          phi node alternative corresponding to this particular block.  */
3195       if (in_ssa_form)
3196         for_each_successor_phi (bb, &set_phi_alternative_reg, 
3197                                 new_live_at_end);
3198
3199       if (bb == ENTRY_BLOCK_PTR)
3200         {
3201           COPY_REG_SET (bb->global_live_at_end, new_live_at_end);
3202           continue;
3203         }
3204
3205       /* On our first pass through this block, we'll go ahead and continue. 
3206          Recognize first pass by local_set NULL.  On subsequent passes, we
3207          get to skip out early if live_at_end wouldn't have changed.  */
3208
3209       if (bb->local_set == NULL)
3210         {
3211           bb->local_set = OBSTACK_ALLOC_REG_SET (function_obstack);
3212           rescan = 1;
3213         }
3214       else
3215         {
3216           /* If any bits were removed from live_at_end, we'll have to
3217              rescan the block.  This wouldn't be necessary if we had
3218              precalculated local_live, however with PROP_SCAN_DEAD_CODE
3219              local_live is really dependent on live_at_end.  */
3220           CLEAR_REG_SET (tmp);
3221           rescan = bitmap_operation (tmp, bb->global_live_at_end,
3222                                      new_live_at_end, BITMAP_AND_COMPL);
3223
3224           if (! rescan)
3225             {
3226               /* Find the set of changed bits.  Take this opportunity
3227                  to notice that this set is empty and early out.  */
3228               CLEAR_REG_SET (tmp);
3229               changed = bitmap_operation (tmp, bb->global_live_at_end,
3230                                           new_live_at_end, BITMAP_XOR);
3231               if (! changed)
3232                 continue;
3233
3234               /* If any of the changed bits overlap with local_set,
3235                  we'll have to rescan the block.  Detect overlap by
3236                  the AND with ~local_set turning off bits.  */
3237               rescan = bitmap_operation (tmp, tmp, bb->local_set,
3238                                          BITMAP_AND_COMPL);
3239             }
3240         }
3241
3242       /* Let our caller know that BB changed enough to require its
3243          death notes updated.  */
3244       if (blocks_out)
3245         SET_BIT (blocks_out, bb->index);
3246
3247       if (! rescan)
3248         {
3249           /* Add to live_at_start the set of all registers in
3250              new_live_at_end that aren't in the old live_at_end.  */
3251
3252           bitmap_operation (tmp, new_live_at_end, bb->global_live_at_end,
3253                             BITMAP_AND_COMPL);
3254           COPY_REG_SET (bb->global_live_at_end, new_live_at_end);
3255
3256           changed = bitmap_operation (bb->global_live_at_start,
3257                                       bb->global_live_at_start,
3258                                       tmp, BITMAP_IOR);
3259           if (! changed)
3260             continue;
3261         }
3262       else
3263         {
3264           COPY_REG_SET (bb->global_live_at_end, new_live_at_end);
3265
3266           /* Rescan the block insn by insn to turn (a copy of) live_at_end
3267              into live_at_start.  */
3268           propagate_block (bb, new_live_at_end, bb->local_set, flags);
3269
3270           /* If live_at start didn't change, no need to go farther.  */
3271           if (REG_SET_EQUAL_P (bb->global_live_at_start, new_live_at_end))
3272             continue;
3273
3274           COPY_REG_SET (bb->global_live_at_start, new_live_at_end);
3275         }
3276
3277       /* Queue all predecessors of BB so that we may re-examine
3278          their live_at_end.  */
3279       for (e = bb->pred; e ; e = e->pred_next)
3280         {
3281           basic_block pb = e->src;
3282           if (pb->aux == NULL)
3283             {
3284               *qtail++ = pb;
3285               if (qtail == qend)
3286                 qtail = queue;
3287               pb->aux = pb;
3288             }
3289         }
3290     }
3291
3292   FREE_REG_SET (tmp);
3293   FREE_REG_SET (new_live_at_end);
3294
3295   if (blocks_out)
3296     {
3297       EXECUTE_IF_SET_IN_SBITMAP (blocks_out, 0, i,
3298         {
3299           basic_block bb = BASIC_BLOCK (i);
3300           FREE_REG_SET (bb->local_set);
3301         });
3302     }
3303   else
3304     {
3305       for (i = n_basic_blocks - 1; i >= 0; --i)
3306         {
3307           basic_block bb = BASIC_BLOCK (i);
3308           FREE_REG_SET (bb->local_set);
3309         }
3310     }
3311
3312   free (queue);
3313 }
3314 \f
3315 /* Subroutines of life analysis.  */
3316
3317 /* Allocate the permanent data structures that represent the results
3318    of life analysis.  Not static since used also for stupid life analysis.  */
3319
3320 void
3321 allocate_bb_life_data ()
3322 {
3323   register int i;
3324
3325   for (i = 0; i < n_basic_blocks; i++)
3326     {
3327       basic_block bb = BASIC_BLOCK (i);
3328
3329       bb->global_live_at_start = OBSTACK_ALLOC_REG_SET (function_obstack);
3330       bb->global_live_at_end = OBSTACK_ALLOC_REG_SET (function_obstack);
3331     }
3332
3333   ENTRY_BLOCK_PTR->global_live_at_end
3334     = OBSTACK_ALLOC_REG_SET (function_obstack);
3335   EXIT_BLOCK_PTR->global_live_at_start
3336     = OBSTACK_ALLOC_REG_SET (function_obstack);
3337
3338   regs_live_at_setjmp = OBSTACK_ALLOC_REG_SET (function_obstack);
3339 }
3340
3341 void
3342 allocate_reg_life_data ()
3343 {
3344   int i;
3345
3346   max_regno = max_reg_num ();
3347
3348   /* Recalculate the register space, in case it has grown.  Old style
3349      vector oriented regsets would set regset_{size,bytes} here also.  */
3350   allocate_reg_info (max_regno, FALSE, FALSE);
3351
3352   /* Reset all the data we'll collect in propagate_block and its 
3353      subroutines.  */
3354   for (i = 0; i < max_regno; i++)
3355     {
3356       REG_N_SETS (i) = 0;
3357       REG_N_REFS (i) = 0;
3358       REG_N_DEATHS (i) = 0;
3359       REG_N_CALLS_CROSSED (i) = 0;
3360       REG_LIVE_LENGTH (i) = 0;
3361       REG_BASIC_BLOCK (i) = REG_BLOCK_UNKNOWN;
3362     }
3363 }
3364
3365 /* Delete dead instructions for propagate_block.  */
3366
3367 static void
3368 propagate_block_delete_insn (bb, insn)
3369      basic_block bb;
3370      rtx insn;
3371 {
3372   rtx inote = find_reg_note (insn, REG_LABEL, NULL_RTX);
3373
3374   /* If the insn referred to a label, and that label was attached to
3375      an ADDR_VEC, it's safe to delete the ADDR_VEC.  In fact, it's
3376      pretty much mandatory to delete it, because the ADDR_VEC may be
3377      referencing labels that no longer exist.  */
3378
3379   if (inote)
3380     {
3381       rtx label = XEXP (inote, 0);
3382       rtx next;
3383
3384       if (LABEL_NUSES (label) == 1
3385           && (next = next_nonnote_insn (label)) != NULL
3386           && GET_CODE (next) == JUMP_INSN
3387           && (GET_CODE (PATTERN (next)) == ADDR_VEC
3388               || GET_CODE (PATTERN (next)) == ADDR_DIFF_VEC))
3389         {
3390           rtx pat = PATTERN (next);
3391           int diff_vec_p = GET_CODE (pat) == ADDR_DIFF_VEC;
3392           int len = XVECLEN (pat, diff_vec_p);
3393           int i;
3394
3395           for (i = 0; i < len; i++)
3396             LABEL_NUSES (XEXP (XVECEXP (pat, diff_vec_p, i), 0))--;
3397
3398           flow_delete_insn (next);
3399         }
3400     }
3401
3402   if (bb->end == insn)
3403     bb->end = PREV_INSN (insn);
3404   flow_delete_insn (insn);
3405 }
3406
3407 /* Delete dead libcalls for propagate_block.  Return the insn
3408    before the libcall.  */
3409
3410 static rtx
3411 propagate_block_delete_libcall (bb, insn, note)
3412      basic_block bb;
3413      rtx insn, note;
3414 {
3415   rtx first = XEXP (note, 0);
3416   rtx before = PREV_INSN (first);
3417
3418   if (insn == bb->end)
3419     bb->end = before;
3420   
3421   flow_delete_insn_chain (first, insn);
3422   return before;
3423 }
3424
3425 /* Update the life-status of regs for one insn.  Return the previous insn.  */
3426
3427 rtx
3428 propagate_one_insn (pbi, insn)
3429      struct propagate_block_info *pbi;
3430      rtx insn;
3431 {
3432   rtx prev = PREV_INSN (insn);
3433   int flags = pbi->flags;
3434   int insn_is_dead = 0;
3435   int libcall_is_dead = 0;
3436   rtx note;
3437   int i;
3438
3439   if (! INSN_P (insn))
3440     return prev;
3441
3442   note = find_reg_note (insn, REG_RETVAL, NULL_RTX);
3443   if (flags & PROP_SCAN_DEAD_CODE)
3444     {
3445       insn_is_dead = insn_dead_p (pbi, PATTERN (insn), 0,
3446                                   REG_NOTES (insn));
3447       libcall_is_dead = (insn_is_dead && note != 0
3448                          && libcall_dead_p (pbi, note, insn));
3449     }
3450
3451   /* We almost certainly don't want to delete prologue or epilogue
3452      instructions.  Warn about probable compiler losage.  */
3453   if (insn_is_dead
3454       && reload_completed
3455       && (((HAVE_epilogue || HAVE_prologue)
3456            && prologue_epilogue_contains (insn))
3457           || (HAVE_sibcall_epilogue
3458               && sibcall_epilogue_contains (insn)))
3459       && find_reg_note (insn, REG_MAYBE_DEAD, NULL_RTX) == 0)
3460     {
3461       if (flags & PROP_KILL_DEAD_CODE)
3462         { 
3463           warning ("ICE: would have deleted prologue/epilogue insn");
3464           if (!inhibit_warnings)
3465             debug_rtx (insn);
3466         }
3467       libcall_is_dead = insn_is_dead = 0;
3468     }
3469
3470   /* If an instruction consists of just dead store(s) on final pass,
3471      delete it.  */
3472   if ((flags & PROP_KILL_DEAD_CODE) && insn_is_dead)
3473     {
3474       /* Record sets.  Do this even for dead instructions, since they
3475          would have killed the values if they hadn't been deleted.  */
3476       mark_set_regs (pbi, PATTERN (insn), insn);
3477
3478       /* CC0 is now known to be dead.  Either this insn used it,
3479          in which case it doesn't anymore, or clobbered it,
3480          so the next insn can't use it.  */
3481       pbi->cc0_live = 0;
3482
3483       if (libcall_is_dead)
3484         {
3485           prev = propagate_block_delete_libcall (pbi->bb, insn, note);
3486           insn = NEXT_INSN (prev);
3487         }
3488       else
3489         propagate_block_delete_insn (pbi->bb, insn);
3490
3491       return prev;
3492     }
3493
3494   /* See if this is an increment or decrement that can be merged into
3495      a following memory address.  */
3496 #ifdef AUTO_INC_DEC
3497   {
3498     register rtx x = single_set (insn);
3499
3500     /* Does this instruction increment or decrement a register?  */
3501     if ((flags & PROP_AUTOINC)
3502         && x != 0
3503         && GET_CODE (SET_DEST (x)) == REG
3504         && (GET_CODE (SET_SRC (x)) == PLUS
3505             || GET_CODE (SET_SRC (x)) == MINUS)
3506         && XEXP (SET_SRC (x), 0) == SET_DEST (x)
3507         && GET_CODE (XEXP (SET_SRC (x), 1)) == CONST_INT
3508         /* Ok, look for a following memory ref we can combine with.
3509            If one is found, change the memory ref to a PRE_INC
3510            or PRE_DEC, cancel this insn, and return 1.
3511            Return 0 if nothing has been done.  */
3512         && try_pre_increment_1 (pbi, insn))
3513       return prev;
3514   }
3515 #endif /* AUTO_INC_DEC */
3516
3517   CLEAR_REG_SET (pbi->new_set);
3518
3519   /* If this is not the final pass, and this insn is copying the value of
3520      a library call and it's dead, don't scan the insns that perform the
3521      library call, so that the call's arguments are not marked live.  */
3522   if (libcall_is_dead)
3523     {
3524       /* Record the death of the dest reg.  */
3525       mark_set_regs (pbi, PATTERN (insn), insn);
3526
3527       insn = XEXP (note, 0);
3528       return PREV_INSN (insn);
3529     }
3530   else if (GET_CODE (PATTERN (insn)) == SET
3531            && SET_DEST (PATTERN (insn)) == stack_pointer_rtx
3532            && GET_CODE (SET_SRC (PATTERN (insn))) == PLUS
3533            && XEXP (SET_SRC (PATTERN (insn)), 0) == stack_pointer_rtx
3534            && GET_CODE (XEXP (SET_SRC (PATTERN (insn)), 1)) == CONST_INT)
3535     /* We have an insn to pop a constant amount off the stack.
3536        (Such insns use PLUS regardless of the direction of the stack,
3537        and any insn to adjust the stack by a constant is always a pop.)
3538        These insns, if not dead stores, have no effect on life.  */
3539     ;
3540   else
3541     {
3542       /* Any regs live at the time of a call instruction must not go
3543          in a register clobbered by calls.  Find all regs now live and
3544          record this for them.  */
3545
3546       if (GET_CODE (insn) == CALL_INSN && (flags & PROP_REG_INFO))
3547         EXECUTE_IF_SET_IN_REG_SET (pbi->reg_live, 0, i,
3548                                    { REG_N_CALLS_CROSSED (i)++; });
3549
3550       /* Record sets.  Do this even for dead instructions, since they
3551          would have killed the values if they hadn't been deleted.  */
3552       mark_set_regs (pbi, PATTERN (insn), insn);
3553
3554       if (GET_CODE (insn) == CALL_INSN)
3555         {
3556           register int i;
3557           rtx note, cond;
3558
3559           cond = NULL_RTX;
3560           if (GET_CODE (PATTERN (insn)) == COND_EXEC)
3561             cond = COND_EXEC_TEST (PATTERN (insn));
3562
3563           /* Non-constant calls clobber memory.  */
3564           if (! CONST_CALL_P (insn))
3565             free_EXPR_LIST_list (&pbi->mem_set_list);
3566
3567           /* There may be extra registers to be clobbered.  */
3568           for (note = CALL_INSN_FUNCTION_USAGE (insn);
3569                note;
3570                note = XEXP (note, 1))
3571             if (GET_CODE (XEXP (note, 0)) == CLOBBER)
3572               mark_set_1 (pbi, CLOBBER, XEXP (XEXP (note, 0), 0),
3573                           cond, insn, pbi->flags);
3574
3575           /* Calls change all call-used and global registers.  */
3576           for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3577             if (call_used_regs[i] && ! global_regs[i]
3578                 && ! fixed_regs[i])
3579               {
3580                 /* We do not want REG_UNUSED notes for these registers.  */
3581                 mark_set_1 (pbi, CLOBBER, gen_rtx_REG (reg_raw_mode[i], i),
3582                             cond, insn,
3583                             pbi->flags & ~(PROP_DEATH_NOTES | PROP_REG_INFO));
3584               }
3585         }
3586
3587       /* If an insn doesn't use CC0, it becomes dead since we assume
3588          that every insn clobbers it.  So show it dead here;
3589          mark_used_regs will set it live if it is referenced.  */
3590       pbi->cc0_live = 0;
3591
3592       /* Record uses.  */
3593       if (! insn_is_dead)
3594         mark_used_regs (pbi, PATTERN (insn), NULL_RTX, insn);
3595
3596       /* Sometimes we may have inserted something before INSN (such as a move)
3597          when we make an auto-inc.  So ensure we will scan those insns.  */
3598 #ifdef AUTO_INC_DEC
3599       prev = PREV_INSN (insn);
3600 #endif
3601
3602       if (! insn_is_dead && GET_CODE (insn) == CALL_INSN)
3603         {
3604           register int i;
3605           rtx note, cond;
3606
3607           cond = NULL_RTX;
3608           if (GET_CODE (PATTERN (insn)) == COND_EXEC)
3609             cond = COND_EXEC_TEST (PATTERN (insn));
3610
3611           /* Calls use their arguments.  */
3612           for (note = CALL_INSN_FUNCTION_USAGE (insn);
3613                note;
3614                note = XEXP (note, 1))
3615             if (GET_CODE (XEXP (note, 0)) == USE)
3616               mark_used_regs (pbi, XEXP (XEXP (note, 0), 0),
3617                               cond, insn);
3618
3619           /* The stack ptr is used (honorarily) by a CALL insn.  */
3620           SET_REGNO_REG_SET (pbi->reg_live, STACK_POINTER_REGNUM);
3621
3622           /* Calls may also reference any of the global registers,
3623              so they are made live.  */
3624           for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3625             if (global_regs[i])
3626               mark_used_reg (pbi, gen_rtx_REG (reg_raw_mode[i], i),
3627                              cond, insn);
3628         }
3629     }
3630
3631   /* On final pass, update counts of how many insns in which each reg
3632      is live.  */
3633   if (flags & PROP_REG_INFO)
3634     EXECUTE_IF_SET_IN_REG_SET (pbi->reg_live, 0, i,
3635                                { REG_LIVE_LENGTH (i)++; });
3636
3637   return prev;
3638 }
3639
3640 /* Initialize a propagate_block_info struct for public consumption.
3641    Note that the structure itself is opaque to this file, but that
3642    the user can use the regsets provided here.  */
3643
3644 struct propagate_block_info *
3645 init_propagate_block_info (bb, live, local_set, flags)
3646      basic_block bb;
3647      regset live;
3648      regset local_set;
3649      int flags;
3650 {
3651   struct propagate_block_info *pbi = xmalloc (sizeof(*pbi));
3652
3653   pbi->bb = bb;
3654   pbi->reg_live = live;
3655   pbi->mem_set_list = NULL_RTX;
3656   pbi->local_set = local_set;
3657   pbi->cc0_live = 0;
3658   pbi->flags = flags;
3659
3660   if (flags & (PROP_LOG_LINKS | PROP_AUTOINC))
3661     pbi->reg_next_use = (rtx *) xcalloc (max_reg_num (), sizeof (rtx));
3662   else
3663     pbi->reg_next_use = NULL;
3664
3665   pbi->new_set = BITMAP_XMALLOC ();
3666
3667 #ifdef HAVE_conditional_execution
3668   pbi->reg_cond_dead = splay_tree_new (splay_tree_compare_ints, NULL,
3669                                        free_reg_cond_life_info);
3670   pbi->reg_cond_reg = BITMAP_XMALLOC ();
3671
3672   /* If this block ends in a conditional branch, for each register live
3673      from one side of the branch and not the other, record the register
3674      as conditionally dead.  */
3675   if ((flags & (PROP_DEATH_NOTES | PROP_SCAN_DEAD_CODE))
3676       && GET_CODE (bb->end) == JUMP_INSN
3677       && any_condjump_p (bb->end))
3678     {
3679       regset_head diff_head;
3680       regset diff = INITIALIZE_REG_SET (diff_head);
3681       basic_block bb_true, bb_false;
3682       rtx cond_true, cond_false, set_src;
3683       int i;
3684
3685       /* Identify the successor blocks.  */
3686       bb_true = bb->succ->dest;
3687       if (bb->succ->succ_next != NULL)
3688         {
3689           bb_false = bb->succ->succ_next->dest;
3690
3691           if (bb->succ->flags & EDGE_FALLTHRU)
3692             {
3693               basic_block t = bb_false;
3694               bb_false = bb_true;
3695               bb_true = t;
3696             }
3697           else if (! (bb->succ->succ_next->flags & EDGE_FALLTHRU))
3698             abort ();
3699         }
3700       else
3701         {
3702           /* This can happen with a conditional jump to the next insn.  */
3703           if (JUMP_LABEL (bb->end) != bb_true->head)
3704             abort ();
3705
3706           /* Simplest way to do nothing.  */
3707           bb_false = bb_true;
3708         }
3709      
3710       /* Extract the condition from the branch.  */
3711       set_src = SET_SRC (pc_set (bb->end));
3712       cond_true = XEXP (set_src, 0);
3713       cond_false = gen_rtx_fmt_ee (reverse_condition (GET_CODE (cond_true)),
3714                                    GET_MODE (cond_true), XEXP (cond_true, 0),
3715                                    XEXP (cond_true, 1));
3716       if (GET_CODE (XEXP (set_src, 1)) == PC)
3717         {
3718           rtx t = cond_false;
3719           cond_false = cond_true;
3720           cond_true = t;
3721         }
3722
3723       /* Compute which register lead different lives in the successors.  */
3724       if (bitmap_operation (diff, bb_true->global_live_at_start,
3725                             bb_false->global_live_at_start, BITMAP_XOR))
3726         {
3727           if (GET_CODE (XEXP (cond_true, 0)) != REG)
3728             abort ();
3729           SET_REGNO_REG_SET (pbi->reg_cond_reg, REGNO (XEXP (cond_true, 0)));
3730
3731           /* For each such register, mark it conditionally dead.  */
3732           EXECUTE_IF_SET_IN_REG_SET
3733             (diff, 0, i,
3734              {
3735                struct reg_cond_life_info *rcli;
3736                rtx cond;
3737
3738                rcli = (struct reg_cond_life_info *) xmalloc (sizeof (*rcli));
3739
3740                if (REGNO_REG_SET_P (bb_true->global_live_at_start, i))
3741                  cond = cond_false;
3742                else
3743                  cond = cond_true;
3744                rcli->condition = alloc_EXPR_LIST (0, cond, NULL_RTX);
3745
3746                splay_tree_insert (pbi->reg_cond_dead, i,
3747                                   (splay_tree_value) rcli);
3748              });
3749         }
3750
3751       FREE_REG_SET (diff);
3752     }
3753 #endif
3754
3755   /* If this block has no successors, any stores to the frame that aren't
3756      used later in the block are dead.  So make a pass over the block
3757      recording any such that are made and show them dead at the end.  We do
3758      a very conservative and simple job here.  */
3759   if (optimize
3760       && (flags & PROP_SCAN_DEAD_CODE)
3761       && (bb->succ == NULL
3762           || (bb->succ->succ_next == NULL
3763               && bb->succ->dest == EXIT_BLOCK_PTR)))
3764     {
3765       rtx insn;
3766       for (insn = bb->end; insn != bb->head; insn = PREV_INSN (insn))
3767         if (GET_CODE (insn) == INSN
3768             && GET_CODE (PATTERN (insn)) == SET
3769             && GET_CODE (SET_DEST (PATTERN (insn))) == MEM)
3770           {
3771             rtx mem = SET_DEST (PATTERN (insn));
3772             
3773             if (XEXP (mem, 0) == frame_pointer_rtx
3774                 || (GET_CODE (XEXP (mem, 0)) == PLUS
3775                     && XEXP (XEXP (mem, 0), 0) == frame_pointer_rtx
3776                     && GET_CODE (XEXP (XEXP (mem, 0), 1)) == CONST_INT))
3777               pbi->mem_set_list = alloc_EXPR_LIST (0, mem, pbi->mem_set_list);
3778           }
3779     }
3780
3781   return pbi;
3782 }
3783
3784 /* Release a propagate_block_info struct.  */
3785
3786 void
3787 free_propagate_block_info (pbi)
3788      struct propagate_block_info *pbi;
3789 {
3790   free_EXPR_LIST_list (&pbi->mem_set_list);
3791
3792   BITMAP_XFREE (pbi->new_set);
3793
3794 #ifdef HAVE_conditional_execution
3795   splay_tree_delete (pbi->reg_cond_dead);
3796   BITMAP_XFREE (pbi->reg_cond_reg);
3797 #endif
3798
3799   if (pbi->reg_next_use)
3800     free (pbi->reg_next_use);
3801
3802   free (pbi);
3803 }
3804
3805 /* Compute the registers live at the beginning of a basic block BB from
3806    those live at the end.
3807
3808    When called, REG_LIVE contains those live at the end.  On return, it
3809    contains those live at the beginning.
3810
3811    LOCAL_SET, if non-null, will be set with all registers killed by 
3812    this basic block.  */
3813
3814 void
3815 propagate_block (bb, live, local_set, flags)
3816      basic_block bb;
3817      regset live;
3818      regset local_set;
3819      int flags;
3820 {
3821   struct propagate_block_info *pbi;
3822   rtx insn, prev;
3823   
3824   pbi = init_propagate_block_info (bb, live, local_set, flags);
3825
3826   if (flags & PROP_REG_INFO)
3827     {
3828       register int i;
3829
3830       /* Process the regs live at the end of the block.
3831          Mark them as not local to any one basic block. */
3832       EXECUTE_IF_SET_IN_REG_SET (live, 0, i,
3833                                  { REG_BASIC_BLOCK (i) = REG_BLOCK_GLOBAL; });
3834     }
3835
3836   /* Scan the block an insn at a time from end to beginning.  */
3837
3838   for (insn = bb->end; ; insn = prev)
3839     {
3840       /* If this is a call to `setjmp' et al, warn if any
3841          non-volatile datum is live.  */
3842       if ((flags & PROP_REG_INFO)
3843           && GET_CODE (insn) == NOTE
3844           && NOTE_LINE_NUMBER (insn) == NOTE_INSN_SETJMP)
3845         IOR_REG_SET (regs_live_at_setjmp, pbi->reg_live);
3846
3847       prev = propagate_one_insn (pbi, insn);
3848
3849       if (insn == bb->head)
3850         break;
3851     }
3852
3853   free_propagate_block_info (pbi);
3854 }
3855 \f
3856 /* Return 1 if X (the body of an insn, or part of it) is just dead stores
3857    (SET expressions whose destinations are registers dead after the insn).
3858    NEEDED is the regset that says which regs are alive after the insn.
3859
3860    Unless CALL_OK is non-zero, an insn is needed if it contains a CALL.
3861
3862    If X is the entire body of an insn, NOTES contains the reg notes
3863    pertaining to the insn.  */
3864
3865 static int
3866 insn_dead_p (pbi, x, call_ok, notes)
3867      struct propagate_block_info *pbi;
3868      rtx x;
3869      int call_ok;
3870      rtx notes ATTRIBUTE_UNUSED;
3871 {
3872   enum rtx_code code = GET_CODE (x);
3873
3874 #ifdef AUTO_INC_DEC
3875   /* If flow is invoked after reload, we must take existing AUTO_INC
3876      expresions into account.  */
3877   if (reload_completed)
3878     {
3879       for ( ; notes; notes = XEXP (notes, 1))
3880         {
3881           if (REG_NOTE_KIND (notes) == REG_INC)
3882             {
3883               int regno = REGNO (XEXP (notes, 0));
3884
3885               /* Don't delete insns to set global regs.  */
3886               if ((regno < FIRST_PSEUDO_REGISTER && global_regs[regno])
3887                   || REGNO_REG_SET_P (pbi->reg_live, regno))
3888                 return 0;
3889             }
3890         }
3891     }
3892 #endif
3893
3894   /* If setting something that's a reg or part of one,
3895      see if that register's altered value will be live.  */
3896
3897   if (code == SET)
3898     {
3899       rtx r = SET_DEST (x);
3900
3901 #ifdef HAVE_cc0
3902       if (GET_CODE (r) == CC0)
3903         return ! pbi->cc0_live;
3904 #endif
3905       
3906       /* A SET that is a subroutine call cannot be dead.  */
3907       if (GET_CODE (SET_SRC (x)) == CALL)
3908         {
3909           if (! call_ok)
3910             return 0;
3911         }
3912
3913       /* Don't eliminate loads from volatile memory or volatile asms.  */
3914       else if (volatile_refs_p (SET_SRC (x)))
3915         return 0;
3916
3917       if (GET_CODE (r) == MEM)
3918         {
3919           rtx temp;
3920
3921           if (MEM_VOLATILE_P (r))
3922             return 0;
3923
3924           /* Walk the set of memory locations we are currently tracking
3925              and see if one is an identical match to this memory location.
3926              If so, this memory write is dead (remember, we're walking
3927              backwards from the end of the block to the start).  */
3928           temp = pbi->mem_set_list;
3929           while (temp)
3930             {
3931               if (rtx_equal_p (XEXP (temp, 0), r))
3932                 return 1;
3933               temp = XEXP (temp, 1);
3934             }
3935         }
3936       else
3937         {
3938           while (GET_CODE (r) == SUBREG
3939                  || GET_CODE (r) == STRICT_LOW_PART
3940                  || GET_CODE (r) == ZERO_EXTRACT)
3941             r = XEXP (r, 0);
3942
3943           if (GET_CODE (r) == REG)
3944             {
3945               int regno = REGNO (r);
3946
3947               /* Obvious.  */
3948               if (REGNO_REG_SET_P (pbi->reg_live, regno))
3949                 return 0;
3950
3951               /* If this is a hard register, verify that subsequent
3952                  words are not needed.  */
3953               if (regno < FIRST_PSEUDO_REGISTER)
3954                 {
3955                   int n = HARD_REGNO_NREGS (regno, GET_MODE (r));
3956
3957                   while (--n > 0)
3958                     if (REGNO_REG_SET_P (pbi->reg_live, regno+n))
3959                       return 0;
3960                 }
3961
3962               /* Don't delete insns to set global regs.  */
3963               if (regno < FIRST_PSEUDO_REGISTER && global_regs[regno])
3964                 return 0;
3965
3966               /* Make sure insns to set the stack pointer aren't deleted.  */
3967               if (regno == STACK_POINTER_REGNUM)
3968                 return 0;
3969
3970               /* Make sure insns to set the frame pointer aren't deleted.  */
3971               if (regno == FRAME_POINTER_REGNUM
3972                   && (! reload_completed || frame_pointer_needed))
3973                 return 0;
3974 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
3975               if (regno == HARD_FRAME_POINTER_REGNUM
3976                   && (! reload_completed || frame_pointer_needed))
3977                 return 0;
3978 #endif
3979
3980 #if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
3981               /* Make sure insns to set arg pointer are never deleted
3982                  (if the arg pointer isn't fixed, there will be a USE
3983                  for it, so we can treat it normally).  */
3984               if (regno == ARG_POINTER_REGNUM && fixed_regs[regno])
3985                 return 0;
3986 #endif
3987
3988 #ifdef PIC_OFFSET_TABLE_REGNUM
3989               /* Before reload, do not allow sets of the pic register
3990                  to be deleted.  Reload can insert references to
3991                  constant pool memory anywhere in the function, making
3992                  the PIC register live where it wasn't before.  */
3993               if (regno == PIC_OFFSET_TABLE_REGNUM && fixed_regs[regno]
3994                   && ! reload_completed)
3995                 return 0;
3996 #endif
3997
3998               /* Otherwise, the set is dead.  */
3999               return 1;
4000             }
4001         }
4002     }
4003
4004   /* If performing several activities, insn is dead if each activity
4005      is individually dead.  Also, CLOBBERs and USEs can be ignored; a
4006      CLOBBER or USE that's inside a PARALLEL doesn't make the insn
4007      worth keeping.  */
4008   else if (code == PARALLEL)
4009     {
4010       int i = XVECLEN (x, 0);
4011
4012       for (i--; i >= 0; i--)
4013         if (GET_CODE (XVECEXP (x, 0, i)) != CLOBBER
4014             && GET_CODE (XVECEXP (x, 0, i)) != USE
4015             && ! insn_dead_p (pbi, XVECEXP (x, 0, i), call_ok, NULL_RTX))
4016           return 0;
4017
4018       return 1;
4019     }
4020
4021   /* A CLOBBER of a pseudo-register that is dead serves no purpose.  That
4022      is not necessarily true for hard registers.  */
4023   else if (code == CLOBBER && GET_CODE (XEXP (x, 0)) == REG
4024            && REGNO (XEXP (x, 0)) >= FIRST_PSEUDO_REGISTER
4025            && ! REGNO_REG_SET_P (pbi->reg_live, REGNO (XEXP (x, 0))))
4026     return 1;
4027
4028   /* We do not check other CLOBBER or USE here.  An insn consisting of just
4029      a CLOBBER or just a USE should not be deleted.  */
4030   return 0;
4031 }
4032
4033 /* If INSN is the last insn in a libcall, and assuming INSN is dead,
4034    return 1 if the entire library call is dead.
4035    This is true if INSN copies a register (hard or pseudo)
4036    and if the hard return reg of the call insn is dead.
4037    (The caller should have tested the destination of the SET inside
4038    INSN already for death.)
4039
4040    If this insn doesn't just copy a register, then we don't
4041    have an ordinary libcall.  In that case, cse could not have
4042    managed to substitute the source for the dest later on,
4043    so we can assume the libcall is dead.
4044
4045    PBI is the block info giving pseudoregs live before this insn.
4046    NOTE is the REG_RETVAL note of the insn.  */
4047
4048 static int
4049 libcall_dead_p (pbi, note, insn)
4050      struct propagate_block_info *pbi;
4051      rtx note;
4052      rtx insn;
4053 {
4054   rtx x = single_set (insn);
4055
4056   if (x)
4057     {
4058       register rtx r = SET_SRC (x);
4059       if (GET_CODE (r) == REG)
4060         {
4061           rtx call = XEXP (note, 0);
4062           rtx call_pat;
4063           register int i;
4064
4065           /* Find the call insn.  */
4066           while (call != insn && GET_CODE (call) != CALL_INSN)
4067             call = NEXT_INSN (call);
4068
4069           /* If there is none, do nothing special,
4070              since ordinary death handling can understand these insns.  */
4071           if (call == insn)
4072             return 0;
4073
4074           /* See if the hard reg holding the value is dead.
4075              If this is a PARALLEL, find the call within it.  */
4076           call_pat = PATTERN (call);
4077           if (GET_CODE (call_pat) == PARALLEL)
4078             {
4079               for (i = XVECLEN (call_pat, 0) - 1; i >= 0; i--)
4080                 if (GET_CODE (XVECEXP (call_pat, 0, i)) == SET
4081                     && GET_CODE (SET_SRC (XVECEXP (call_pat, 0, i))) == CALL)
4082                   break;
4083
4084               /* This may be a library call that is returning a value
4085                  via invisible pointer.  Do nothing special, since
4086                  ordinary death handling can understand these insns.  */
4087               if (i < 0)
4088                 return 0;
4089
4090               call_pat = XVECEXP (call_pat, 0, i);
4091             }
4092
4093           return insn_dead_p (pbi, call_pat, 1, REG_NOTES (call));
4094         }
4095     }
4096   return 1;
4097 }
4098
4099 /* Return 1 if register REGNO was used before it was set, i.e. if it is
4100    live at function entry.  Don't count global register variables, variables
4101    in registers that can be used for function arg passing, or variables in
4102    fixed hard registers.  */
4103
4104 int
4105 regno_uninitialized (regno)
4106      int regno;
4107 {
4108   if (n_basic_blocks == 0
4109       || (regno < FIRST_PSEUDO_REGISTER
4110           && (global_regs[regno]
4111               || fixed_regs[regno]
4112               || FUNCTION_ARG_REGNO_P (regno))))
4113     return 0;
4114
4115   return REGNO_REG_SET_P (BASIC_BLOCK (0)->global_live_at_start, regno);
4116 }
4117
4118 /* 1 if register REGNO was alive at a place where `setjmp' was called
4119    and was set more than once or is an argument.
4120    Such regs may be clobbered by `longjmp'.  */
4121
4122 int
4123 regno_clobbered_at_setjmp (regno)
4124      int regno;
4125 {
4126   if (n_basic_blocks == 0)
4127     return 0;
4128
4129   return ((REG_N_SETS (regno) > 1
4130            || REGNO_REG_SET_P (BASIC_BLOCK (0)->global_live_at_start, regno))
4131           && REGNO_REG_SET_P (regs_live_at_setjmp, regno));
4132 }
4133 \f
4134 /* INSN references memory, possibly using autoincrement addressing modes.
4135    Find any entries on the mem_set_list that need to be invalidated due
4136    to an address change.  */
4137
4138 static void
4139 invalidate_mems_from_autoinc (pbi, insn)
4140      struct propagate_block_info *pbi;
4141      rtx insn;
4142 {
4143   rtx note = REG_NOTES (insn);
4144   for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
4145     {
4146       if (REG_NOTE_KIND (note) == REG_INC)
4147         {
4148           rtx temp = pbi->mem_set_list;
4149           rtx prev = NULL_RTX;
4150           rtx next;
4151
4152           while (temp)
4153             {
4154               next = XEXP (temp, 1);
4155               if (reg_overlap_mentioned_p (XEXP (note, 0), XEXP (temp, 0)))
4156                 {
4157                   /* Splice temp out of list.  */
4158                   if (prev)
4159                     XEXP (prev, 1) = next;
4160                   else
4161                     pbi->mem_set_list = next;
4162                   free_EXPR_LIST_node (temp);
4163                 }
4164               else
4165                 prev = temp;
4166               temp = next;
4167             }
4168         }
4169     }
4170 }
4171
4172 /* Process the registers that are set within X.  Their bits are set to
4173    1 in the regset DEAD, because they are dead prior to this insn.
4174
4175    If INSN is nonzero, it is the insn being processed.
4176
4177    FLAGS is the set of operations to perform.  */
4178
4179 static void
4180 mark_set_regs (pbi, x, insn)
4181      struct propagate_block_info *pbi;
4182      rtx x, insn;
4183 {
4184   rtx cond = NULL_RTX;
4185   rtx link;
4186   enum rtx_code code;
4187
4188   if (insn)
4189     for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
4190       {
4191         if (REG_NOTE_KIND (link) == REG_INC)
4192           mark_set_1 (pbi, SET, XEXP (link, 0),
4193                       (GET_CODE (x) == COND_EXEC
4194                        ? COND_EXEC_TEST (x) : NULL_RTX),
4195                       insn, pbi->flags);
4196       }
4197  retry:
4198   switch (code = GET_CODE (x))
4199     {
4200     case SET:
4201     case CLOBBER:
4202       mark_set_1 (pbi, code, SET_DEST (x), cond, insn, pbi->flags);
4203       return;
4204
4205     case COND_EXEC:
4206       cond = COND_EXEC_TEST (x);
4207       x = COND_EXEC_CODE (x);
4208       goto retry;
4209
4210     case PARALLEL:
4211       {
4212         register int i;
4213         for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
4214           {
4215             rtx sub = XVECEXP (x, 0, i);
4216             switch (code = GET_CODE (sub))
4217               {
4218               case COND_EXEC:
4219                 if (cond != NULL_RTX)
4220                   abort ();
4221
4222                 cond = COND_EXEC_TEST (sub);
4223                 sub = COND_EXEC_CODE (sub);
4224                 if (GET_CODE (sub) != SET && GET_CODE (sub) != CLOBBER)
4225                   break;
4226                 /* FALLTHRU */
4227
4228               case SET:
4229               case CLOBBER:
4230                 mark_set_1 (pbi, code, SET_DEST (sub), cond, insn, pbi->flags);
4231                 break;
4232
4233               default:
4234                 break;
4235               }
4236           }
4237         break;
4238       }
4239
4240     default:
4241       break;
4242     }
4243 }
4244
4245 /* Process a single SET rtx, X.  */
4246
4247 static void
4248 mark_set_1 (pbi, code, reg, cond, insn, flags)
4249      struct propagate_block_info *pbi;
4250      enum rtx_code code;
4251      rtx reg, cond, insn;
4252      int flags;
4253 {
4254   int regno_first = -1, regno_last = -1;
4255   int not_dead = 0;
4256   int i;
4257
4258   /* Some targets place small structures in registers for
4259      return values of functions.  We have to detect this
4260      case specially here to get correct flow information.  */
4261   if (GET_CODE (reg) == PARALLEL
4262       && GET_MODE (reg) == BLKmode)
4263     {
4264       for (i = XVECLEN (reg, 0) - 1; i >= 0; i--)
4265         mark_set_1 (pbi, code, XVECEXP (reg, 0, i), cond, insn, flags);
4266       return;
4267     }
4268
4269   /* Modifying just one hardware register of a multi-reg value or just a
4270      byte field of a register does not mean the value from before this insn
4271      is now dead.  Of course, if it was dead after it's unused now.  */
4272
4273   switch (GET_CODE (reg))
4274     {
4275     case ZERO_EXTRACT:
4276     case SIGN_EXTRACT:
4277     case STRICT_LOW_PART:
4278       /* ??? Assumes STRICT_LOW_PART not used on multi-word registers.  */
4279       do
4280         reg = XEXP (reg, 0);
4281       while (GET_CODE (reg) == SUBREG
4282              || GET_CODE (reg) == ZERO_EXTRACT
4283              || GET_CODE (reg) == SIGN_EXTRACT
4284              || GET_CODE (reg) == STRICT_LOW_PART);
4285       if (GET_CODE (reg) == MEM)
4286         break;
4287       not_dead = REGNO_REG_SET_P (pbi->reg_live, REGNO (reg));
4288       /* FALLTHRU */
4289
4290     case REG:
4291       regno_last = regno_first = REGNO (reg);
4292       if (regno_first < FIRST_PSEUDO_REGISTER)
4293         regno_last += HARD_REGNO_NREGS (regno_first, GET_MODE (reg)) - 1;
4294       break;
4295
4296     case SUBREG:
4297       if (GET_CODE (SUBREG_REG (reg)) == REG)
4298         {
4299           enum machine_mode outer_mode = GET_MODE (reg);
4300           enum machine_mode inner_mode = GET_MODE (SUBREG_REG (reg));
4301
4302           /* Identify the range of registers affected.  This is moderately
4303              tricky for hard registers.  See alter_subreg.  */
4304
4305           regno_last = regno_first = REGNO (SUBREG_REG (reg));
4306           if (regno_first < FIRST_PSEUDO_REGISTER)
4307             {
4308 #ifdef ALTER_HARD_SUBREG
4309               regno_first = ALTER_HARD_SUBREG (outer_mode, SUBREG_WORD (reg),
4310                                                inner_mode, regno_first);
4311 #else
4312               regno_first += SUBREG_WORD (reg);
4313 #endif
4314               regno_last = (regno_first
4315                             + HARD_REGNO_NREGS (regno_first, outer_mode) - 1);
4316
4317               /* Since we've just adjusted the register number ranges, make
4318                  sure REG matches.  Otherwise some_was_live will be clear
4319                  when it shouldn't have been, and we'll create incorrect
4320                  REG_UNUSED notes.  */
4321               reg = gen_rtx_REG (outer_mode, regno_first);
4322             }
4323           else
4324             {
4325               /* If the number of words in the subreg is less than the number
4326                  of words in the full register, we have a well-defined partial
4327                  set.  Otherwise the high bits are undefined.
4328
4329                  This is only really applicable to pseudos, since we just took
4330                  care of multi-word hard registers.  */
4331               if (((GET_MODE_SIZE (outer_mode)
4332                     + UNITS_PER_WORD - 1) / UNITS_PER_WORD)
4333                   < ((GET_MODE_SIZE (inner_mode)
4334                       + UNITS_PER_WORD - 1) / UNITS_PER_WORD))
4335                 not_dead = REGNO_REG_SET_P (pbi->reg_live, regno_first);
4336
4337               reg = SUBREG_REG (reg);
4338             }
4339         }
4340       else
4341         reg = SUBREG_REG (reg);
4342       break;
4343
4344     default:
4345       break;
4346     }
4347
4348   /* If this set is a MEM, then it kills any aliased writes. 
4349      If this set is a REG, then it kills any MEMs which use the reg.  */
4350   if (optimize && (flags & PROP_SCAN_DEAD_CODE))
4351     {
4352       if (GET_CODE (reg) == MEM || GET_CODE (reg) == REG)
4353         {
4354           rtx temp = pbi->mem_set_list;
4355           rtx prev = NULL_RTX;
4356           rtx next;
4357
4358           while (temp)
4359             {
4360               next = XEXP (temp, 1);
4361               if ((GET_CODE (reg) == MEM
4362                    && output_dependence (XEXP (temp, 0), reg))
4363                   || (GET_CODE (reg) == REG
4364                       && reg_overlap_mentioned_p (reg, XEXP (temp, 0))))
4365                 {
4366                   /* Splice this entry out of the list.  */
4367                   if (prev)
4368                     XEXP (prev, 1) = next;
4369                   else
4370                     pbi->mem_set_list = next;
4371                   free_EXPR_LIST_node (temp);
4372                 }
4373               else
4374                 prev = temp;
4375               temp = next;
4376             }
4377         }
4378
4379       /* If the memory reference had embedded side effects (autoincrement
4380          address modes.  Then we may need to kill some entries on the
4381          memory set list.  */
4382       if (insn && GET_CODE (reg) == MEM)
4383         invalidate_mems_from_autoinc (pbi, insn);
4384
4385       if (GET_CODE (reg) == MEM && ! side_effects_p (reg)
4386           /* ??? With more effort we could track conditional memory life.  */
4387           && ! cond
4388           /* We do not know the size of a BLKmode store, so we do not track
4389              them for redundant store elimination.  */
4390           && GET_MODE (reg) != BLKmode
4391           /* There are no REG_INC notes for SP, so we can't assume we'll see 
4392              everything that invalidates it.  To be safe, don't eliminate any
4393              stores though SP; none of them should be redundant anyway.  */
4394           && ! reg_mentioned_p (stack_pointer_rtx, reg))
4395         pbi->mem_set_list = alloc_EXPR_LIST (0, reg, pbi->mem_set_list);
4396     }
4397
4398   if (GET_CODE (reg) == REG
4399       && ! (regno_first == FRAME_POINTER_REGNUM
4400             && (! reload_completed || frame_pointer_needed))
4401 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
4402       && ! (regno_first == HARD_FRAME_POINTER_REGNUM
4403             && (! reload_completed || frame_pointer_needed))
4404 #endif
4405 #if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
4406       && ! (regno_first == ARG_POINTER_REGNUM && fixed_regs[regno_first])
4407 #endif
4408       )
4409     {
4410       int some_was_live = 0, some_was_dead = 0;
4411
4412       for (i = regno_first; i <= regno_last; ++i)
4413         {
4414           int needed_regno = REGNO_REG_SET_P (pbi->reg_live, i);
4415           if (pbi->local_set)
4416             SET_REGNO_REG_SET (pbi->local_set, i);
4417           if (code != CLOBBER)
4418             SET_REGNO_REG_SET (pbi->new_set, i);
4419
4420           some_was_live |= needed_regno;
4421           some_was_dead |= ! needed_regno;
4422         }
4423
4424 #ifdef HAVE_conditional_execution
4425       /* Consider conditional death in deciding that the register needs
4426          a death note.  */
4427       if (some_was_live && ! not_dead
4428           /* The stack pointer is never dead.  Well, not strictly true,
4429              but it's very difficult to tell from here.  Hopefully
4430              combine_stack_adjustments will fix up the most egregious
4431              errors.  */
4432           && regno_first != STACK_POINTER_REGNUM)
4433         {
4434           for (i = regno_first; i <= regno_last; ++i)
4435             if (! mark_regno_cond_dead (pbi, i, cond))
4436               not_dead = 1;
4437         }
4438 #endif
4439
4440       /* Additional data to record if this is the final pass.  */
4441       if (flags & (PROP_LOG_LINKS | PROP_REG_INFO
4442                    | PROP_DEATH_NOTES | PROP_AUTOINC))
4443         {
4444           register rtx y;
4445           register int blocknum = pbi->bb->index;
4446
4447           y = NULL_RTX;
4448           if (flags & (PROP_LOG_LINKS | PROP_AUTOINC))
4449             {
4450               y = pbi->reg_next_use[regno_first];
4451
4452               /* The next use is no longer next, since a store intervenes.  */
4453               for (i = regno_first; i <= regno_last; ++i)
4454                 pbi->reg_next_use[i] = 0;
4455             }
4456
4457           if (flags & PROP_REG_INFO)
4458             {
4459               for (i = regno_first; i <= regno_last; ++i)
4460                 {
4461                   /* Count (weighted) references, stores, etc.  This counts a
4462                      register twice if it is modified, but that is correct.  */
4463                   REG_N_SETS (i) += 1;
4464                   REG_N_REFS (i) += (optimize_size ? 1
4465                                      : pbi->bb->loop_depth + 1);
4466
4467                   /* The insns where a reg is live are normally counted
4468                      elsewhere, but we want the count to include the insn
4469                      where the reg is set, and the normal counting mechanism
4470                      would not count it.  */
4471                   REG_LIVE_LENGTH (i) += 1;
4472                 }
4473
4474               /* If this is a hard reg, record this function uses the reg.  */
4475               if (regno_first < FIRST_PSEUDO_REGISTER)
4476                 {
4477                   for (i = regno_first; i <= regno_last; i++)
4478                     regs_ever_live[i] = 1;
4479                 }
4480               else
4481                 {
4482                   /* Keep track of which basic blocks each reg appears in.  */
4483                   if (REG_BASIC_BLOCK (regno_first) == REG_BLOCK_UNKNOWN)
4484                     REG_BASIC_BLOCK (regno_first) = blocknum;
4485                   else if (REG_BASIC_BLOCK (regno_first) != blocknum)
4486                     REG_BASIC_BLOCK (regno_first) = REG_BLOCK_GLOBAL;
4487                 }
4488             }
4489
4490           if (! some_was_dead)
4491             {
4492               if (flags & PROP_LOG_LINKS)
4493                 {
4494                   /* Make a logical link from the next following insn
4495                      that uses this register, back to this insn.
4496                      The following insns have already been processed.
4497
4498                      We don't build a LOG_LINK for hard registers containing
4499                      in ASM_OPERANDs.  If these registers get replaced,
4500                      we might wind up changing the semantics of the insn,
4501                      even if reload can make what appear to be valid
4502                      assignments later.  */
4503                   if (y && (BLOCK_NUM (y) == blocknum)
4504                       && (regno_first >= FIRST_PSEUDO_REGISTER
4505                           || asm_noperands (PATTERN (y)) < 0))
4506                     LOG_LINKS (y) = alloc_INSN_LIST (insn, LOG_LINKS (y));
4507                 }
4508             }
4509           else if (not_dead)
4510             ;
4511           else if (! some_was_live)
4512             {
4513               if (flags & PROP_REG_INFO)
4514                 REG_N_DEATHS (regno_first) += 1;
4515
4516               if (flags & PROP_DEATH_NOTES)
4517                 {
4518                   /* Note that dead stores have already been deleted
4519                      when possible.  If we get here, we have found a
4520                      dead store that cannot be eliminated (because the
4521                      same insn does something useful).  Indicate this
4522                      by marking the reg being set as dying here.  */
4523                   REG_NOTES (insn)
4524                     = alloc_EXPR_LIST (REG_UNUSED, reg, REG_NOTES (insn));
4525                 }
4526             }
4527           else
4528             {
4529               if (flags & PROP_DEATH_NOTES)
4530                 {
4531                   /* This is a case where we have a multi-word hard register
4532                      and some, but not all, of the words of the register are
4533                      needed in subsequent insns.  Write REG_UNUSED notes
4534                      for those parts that were not needed.  This case should
4535                      be rare.  */
4536
4537                   for (i = regno_first; i <= regno_last; ++i)
4538                     if (! REGNO_REG_SET_P (pbi->reg_live, i))
4539                       REG_NOTES (insn)
4540                         = alloc_EXPR_LIST (REG_UNUSED,
4541                                            gen_rtx_REG (reg_raw_mode[i], i),
4542                                            REG_NOTES (insn));
4543                 }
4544             }
4545         }
4546
4547       /* Mark the register as being dead.  */
4548       if (some_was_live
4549           && ! not_dead
4550           /* The stack pointer is never dead.  Well, not strictly true,
4551              but it's very difficult to tell from here.  Hopefully
4552              combine_stack_adjustments will fix up the most egregious
4553              errors.  */
4554           && regno_first != STACK_POINTER_REGNUM)
4555         {
4556           for (i = regno_first; i <= regno_last; ++i)
4557             CLEAR_REGNO_REG_SET (pbi->reg_live, i);
4558         }
4559     }
4560   else if (GET_CODE (reg) == REG)
4561     {
4562       if (flags & (PROP_LOG_LINKS | PROP_AUTOINC))
4563         pbi->reg_next_use[regno_first] = 0;
4564     }
4565
4566   /* If this is the last pass and this is a SCRATCH, show it will be dying
4567      here and count it.  */
4568   else if (GET_CODE (reg) == SCRATCH)
4569     {
4570       if (flags & PROP_DEATH_NOTES)
4571         REG_NOTES (insn)
4572           = alloc_EXPR_LIST (REG_UNUSED, reg, REG_NOTES (insn));
4573     }
4574 }
4575 \f
4576 #ifdef HAVE_conditional_execution
4577 /* Mark REGNO conditionally dead.  Return true if the register is
4578    now unconditionally dead.  */
4579
4580 static int
4581 mark_regno_cond_dead (pbi, regno, cond)
4582      struct propagate_block_info *pbi;
4583      int regno;
4584      rtx cond;
4585 {
4586   /* If this is a store to a predicate register, the value of the
4587      predicate is changing, we don't know that the predicate as seen
4588      before is the same as that seen after.  Flush all dependent
4589      conditions from reg_cond_dead.  This will make all such
4590      conditionally live registers unconditionally live.  */
4591   if (REGNO_REG_SET_P (pbi->reg_cond_reg, regno))
4592     flush_reg_cond_reg (pbi, regno);
4593
4594   /* If this is an unconditional store, remove any conditional
4595      life that may have existed.  */
4596   if (cond == NULL_RTX)
4597     splay_tree_remove (pbi->reg_cond_dead, regno);
4598   else
4599     {
4600       splay_tree_node node;
4601       struct reg_cond_life_info *rcli;
4602       rtx ncond;
4603
4604       /* Otherwise this is a conditional set.  Record that fact.
4605          It may have been conditionally used, or there may be a
4606          subsequent set with a complimentary condition.  */
4607
4608       node = splay_tree_lookup (pbi->reg_cond_dead, regno);
4609       if (node == NULL)
4610         {
4611           /* The register was unconditionally live previously.
4612              Record the current condition as the condition under
4613              which it is dead.  */
4614           rcli = (struct reg_cond_life_info *)
4615             xmalloc (sizeof (*rcli));
4616           rcli->condition = alloc_EXPR_LIST (0, cond, NULL_RTX);
4617           splay_tree_insert (pbi->reg_cond_dead, regno,
4618                              (splay_tree_value) rcli);
4619
4620           SET_REGNO_REG_SET (pbi->reg_cond_reg,
4621                              REGNO (XEXP (cond, 0)));
4622
4623           /* Not unconditionaly dead.  */
4624           return 0;
4625         }
4626       else
4627         {
4628           /* The register was conditionally live previously. 
4629              Add the new condition to the old.  */
4630           rcli = (struct reg_cond_life_info *) node->value;
4631           ncond = rcli->condition;
4632           ncond = ior_reg_cond (ncond, cond);
4633
4634           /* If the register is now unconditionally dead,
4635              remove the entry in the splay_tree.  */
4636           if (ncond == const1_rtx)
4637             splay_tree_remove (pbi->reg_cond_dead, regno);
4638           else
4639             {
4640               rcli->condition = ncond;
4641
4642               SET_REGNO_REG_SET (pbi->reg_cond_reg,
4643                                  REGNO (XEXP (cond, 0)));
4644
4645               /* Not unconditionaly dead.  */
4646               return 0;
4647             }
4648         }
4649     }
4650
4651   return 1;
4652 }
4653
4654 /* Called from splay_tree_delete for pbi->reg_cond_life.  */
4655
4656 static void
4657 free_reg_cond_life_info (value)
4658      splay_tree_value value;
4659 {
4660   struct reg_cond_life_info *rcli = (struct reg_cond_life_info *) value;
4661   free_EXPR_LIST_list (&rcli->condition);
4662   free (rcli);
4663 }
4664
4665 /* Helper function for flush_reg_cond_reg.  */
4666
4667 static int
4668 flush_reg_cond_reg_1 (node, data)
4669      splay_tree_node node;
4670      void *data;
4671 {
4672   struct reg_cond_life_info *rcli;
4673   int *xdata = (int *) data;
4674   unsigned int regno = xdata[0];
4675   rtx c, *prev;
4676
4677   /* Don't need to search if last flushed value was farther on in
4678      the in-order traversal.  */
4679   if (xdata[1] >= (int) node->key)
4680     return 0;
4681
4682   /* Splice out portions of the expression that refer to regno.  */
4683   rcli = (struct reg_cond_life_info *) node->value;
4684   c = *(prev = &rcli->condition);
4685   while (c)
4686     {
4687       if (regno == REGNO (XEXP (XEXP (c, 0), 0)))
4688         {
4689           rtx next = XEXP (c, 1);
4690           free_EXPR_LIST_node (c);
4691           c = *prev = next;
4692         }
4693       else
4694         c = *(prev = &XEXP (c, 1));
4695     }
4696
4697   /* If the entire condition is now NULL, signal the node to be removed.  */
4698   if (! rcli->condition)
4699     {
4700       xdata[1] = node->key;
4701       return -1;
4702     }
4703   else
4704     return 0;
4705 }
4706
4707 /* Flush all (sub) expressions referring to REGNO from REG_COND_LIVE.  */
4708
4709 static void
4710 flush_reg_cond_reg (pbi, regno)
4711      struct propagate_block_info *pbi;
4712      int regno;
4713 {
4714   int pair[2];
4715
4716   pair[0] = regno;
4717   pair[1] = -1;
4718   while (splay_tree_foreach (pbi->reg_cond_dead,
4719                              flush_reg_cond_reg_1, pair) == -1)
4720     splay_tree_remove (pbi->reg_cond_dead, pair[1]);
4721
4722   CLEAR_REGNO_REG_SET (pbi->reg_cond_reg, regno);
4723 }
4724
4725 /* Logical arithmetic on predicate conditions.  IOR, NOT and NAND.
4726    We actually use EXPR_LIST to chain the sub-expressions together
4727    instead of IOR because it's easier to manipulate and we have 
4728    the lists.c functions to reuse nodes.
4729    
4730    Return a new rtl expression as appropriate.  */
4731
4732 static rtx
4733 ior_reg_cond (old, x)
4734      rtx old, x;
4735 {
4736   enum rtx_code x_code;
4737   rtx x_reg;
4738   rtx c;
4739
4740   /* We expect these conditions to be of the form (eq reg 0).  */
4741   x_code = GET_CODE (x);
4742   if (GET_RTX_CLASS (x_code) != '<'
4743       || GET_CODE (x_reg = XEXP (x, 0)) != REG
4744       || XEXP (x, 1) != const0_rtx)
4745     abort ();
4746
4747   /* Search the expression for an existing sub-expression of X_REG.  */
4748   for (c = old; c ; c = XEXP (c, 1))
4749     {
4750       rtx y = XEXP (c, 0);
4751       if (REGNO (XEXP (y, 0)) == REGNO (x_reg))
4752         {
4753           /* If we find X already present in OLD, we need do nothing.  */
4754           if (GET_CODE (y) == x_code)
4755             return old;
4756
4757           /* If we find X being a compliment of a condition in OLD, 
4758              then the entire condition is true.  */
4759           if (GET_CODE (y) == reverse_condition (x_code))
4760             return const1_rtx;
4761         }
4762     }
4763
4764   /* Otherwise just add to the chain.  */
4765   return alloc_EXPR_LIST (0, x, old);
4766 }
4767
4768 static rtx
4769 not_reg_cond (x)
4770      rtx x;
4771 {
4772   enum rtx_code x_code;
4773   rtx x_reg;
4774
4775   /* We expect these conditions to be of the form (eq reg 0).  */
4776   x_code = GET_CODE (x);
4777   if (GET_RTX_CLASS (x_code) != '<'
4778       || GET_CODE (x_reg = XEXP (x, 0)) != REG
4779       || XEXP (x, 1) != const0_rtx)
4780     abort ();
4781
4782   return alloc_EXPR_LIST (0, gen_rtx_fmt_ee (reverse_condition (x_code),
4783                                              VOIDmode, x_reg, const0_rtx),
4784                           NULL_RTX);
4785 }
4786
4787 static rtx
4788 nand_reg_cond (old, x)
4789      rtx old, x;
4790 {
4791   enum rtx_code x_code;
4792   rtx x_reg;
4793   rtx c, *prev;
4794
4795   /* We expect these conditions to be of the form (eq reg 0).  */
4796   x_code = GET_CODE (x);
4797   if (GET_RTX_CLASS (x_code) != '<'
4798       || GET_CODE (x_reg = XEXP (x, 0)) != REG
4799       || XEXP (x, 1) != const0_rtx)
4800     abort ();
4801
4802   /* Search the expression for an existing sub-expression of X_REG.  */
4803
4804   for (c = *(prev = &old); c ; c = *(prev = &XEXP (c, 1)))
4805     {
4806       rtx y = XEXP (c, 0);
4807       if (REGNO (XEXP (y, 0)) == REGNO (x_reg))
4808         {
4809           /* If we find X already present in OLD, then we need to 
4810              splice it out.  */
4811           if (GET_CODE (y) == x_code)
4812             {
4813               *prev = XEXP (c, 1);
4814               free_EXPR_LIST_node (c);
4815               return old ? old : const0_rtx;
4816             }
4817
4818           /* If we find X being a compliment of a condition in OLD, 
4819              then we need do nothing.  */
4820           if (GET_CODE (y) == reverse_condition (x_code))
4821             return old;
4822         }
4823     }
4824
4825   /* Otherwise, by implication, the register in question is now live for
4826      the inverse of the condition X.  */
4827   return alloc_EXPR_LIST (0, gen_rtx_fmt_ee (reverse_condition (x_code),
4828                                              VOIDmode, x_reg, const0_rtx),
4829                           old);
4830 }
4831 #endif /* HAVE_conditional_execution */
4832 \f
4833 #ifdef AUTO_INC_DEC
4834
4835 /* Try to substitute the auto-inc expression INC as the address inside
4836    MEM which occurs in INSN.  Currently, the address of MEM is an expression
4837    involving INCR_REG, and INCR is the next use of INCR_REG; it is an insn
4838    that has a single set whose source is a PLUS of INCR_REG and something
4839    else.  */
4840
4841 static void
4842 attempt_auto_inc (pbi, inc, insn, mem, incr, incr_reg)
4843      struct propagate_block_info *pbi;
4844      rtx inc, insn, mem, incr, incr_reg;
4845 {
4846   int regno = REGNO (incr_reg);
4847   rtx set = single_set (incr);
4848   rtx q = SET_DEST (set);
4849   rtx y = SET_SRC (set);
4850   int opnum = XEXP (y, 0) == incr_reg ? 0 : 1;
4851
4852   /* Make sure this reg appears only once in this insn.  */
4853   if (count_occurrences (PATTERN (insn), incr_reg, 1) != 1)
4854     return;
4855
4856   if (dead_or_set_p (incr, incr_reg)
4857       /* Mustn't autoinc an eliminable register.  */
4858       && (regno >= FIRST_PSEUDO_REGISTER
4859           || ! TEST_HARD_REG_BIT (elim_reg_set, regno)))
4860     {
4861       /* This is the simple case.  Try to make the auto-inc.  If
4862          we can't, we are done.  Otherwise, we will do any
4863          needed updates below.  */
4864       if (! validate_change (insn, &XEXP (mem, 0), inc, 0))
4865         return;
4866     }
4867   else if (GET_CODE (q) == REG
4868            /* PREV_INSN used here to check the semi-open interval
4869               [insn,incr).  */
4870            && ! reg_used_between_p (q,  PREV_INSN (insn), incr)
4871            /* We must also check for sets of q as q may be
4872               a call clobbered hard register and there may
4873               be a call between PREV_INSN (insn) and incr.  */
4874            && ! reg_set_between_p (q,  PREV_INSN (insn), incr))
4875     {
4876       /* We have *p followed sometime later by q = p+size.
4877          Both p and q must be live afterward,
4878          and q is not used between INSN and its assignment.
4879          Change it to q = p, ...*q..., q = q+size.
4880          Then fall into the usual case.  */
4881       rtx insns, temp;
4882       basic_block bb;
4883
4884       start_sequence ();
4885       emit_move_insn (q, incr_reg);
4886       insns = get_insns ();
4887       end_sequence ();
4888
4889       if (basic_block_for_insn)
4890         for (temp = insns; temp; temp = NEXT_INSN (temp))
4891           set_block_for_insn (temp, pbi->bb);
4892
4893       /* If we can't make the auto-inc, or can't make the
4894          replacement into Y, exit.  There's no point in making
4895          the change below if we can't do the auto-inc and doing
4896          so is not correct in the pre-inc case.  */
4897
4898       XEXP (inc, 0) = q;
4899       validate_change (insn, &XEXP (mem, 0), inc, 1);
4900       validate_change (incr, &XEXP (y, opnum), q, 1);
4901       if (! apply_change_group ())
4902         return;
4903
4904       /* We now know we'll be doing this change, so emit the
4905          new insn(s) and do the updates.  */
4906       emit_insns_before (insns, insn);
4907
4908       if (pbi->bb->head == insn)
4909         pbi->bb->head = insns;
4910
4911       /* INCR will become a NOTE and INSN won't contain a
4912          use of INCR_REG.  If a use of INCR_REG was just placed in
4913          the insn before INSN, make that the next use. 
4914          Otherwise, invalidate it.  */
4915       if (GET_CODE (PREV_INSN (insn)) == INSN
4916           && GET_CODE (PATTERN (PREV_INSN (insn))) == SET
4917           && SET_SRC (PATTERN (PREV_INSN (insn))) == incr_reg)
4918         pbi->reg_next_use[regno] = PREV_INSN (insn);
4919       else
4920         pbi->reg_next_use[regno] = 0;
4921
4922       incr_reg = q;
4923       regno = REGNO (q);
4924
4925       /* REGNO is now used in INCR which is below INSN, but
4926          it previously wasn't live here.  If we don't mark
4927          it as live, we'll put a REG_DEAD note for it
4928          on this insn, which is incorrect.  */
4929       SET_REGNO_REG_SET (pbi->reg_live, regno);
4930
4931       /* If there are any calls between INSN and INCR, show
4932          that REGNO now crosses them.  */
4933       for (temp = insn; temp != incr; temp = NEXT_INSN (temp))
4934         if (GET_CODE (temp) == CALL_INSN)
4935           REG_N_CALLS_CROSSED (regno)++;
4936     }
4937   else
4938     return;
4939
4940   /* If we haven't returned, it means we were able to make the
4941      auto-inc, so update the status.  First, record that this insn
4942      has an implicit side effect.  */
4943
4944   REG_NOTES (insn)
4945     = alloc_EXPR_LIST (REG_INC, incr_reg, REG_NOTES (insn));
4946
4947   /* Modify the old increment-insn to simply copy
4948      the already-incremented value of our register.  */
4949   if (! validate_change (incr, &SET_SRC (set), incr_reg, 0))
4950     abort ();
4951
4952   /* If that makes it a no-op (copying the register into itself) delete
4953      it so it won't appear to be a "use" and a "set" of this
4954      register.  */
4955   if (REGNO (SET_DEST (set)) == REGNO (incr_reg))
4956     {
4957       /* If the original source was dead, it's dead now.  */
4958       rtx note;
4959       
4960       while (note = find_reg_note (incr, REG_DEAD, NULL_RTX))
4961         {
4962           remove_note (incr, note);
4963           if (XEXP (note, 0) != incr_reg)
4964             CLEAR_REGNO_REG_SET (pbi->reg_live, REGNO (XEXP (note, 0)));
4965         }
4966
4967       PUT_CODE (incr, NOTE);
4968       NOTE_LINE_NUMBER (incr) = NOTE_INSN_DELETED;
4969       NOTE_SOURCE_FILE (incr) = 0;
4970     }
4971
4972   if (regno >= FIRST_PSEUDO_REGISTER)
4973     {
4974       /* Count an extra reference to the reg.  When a reg is
4975          incremented, spilling it is worse, so we want to make
4976          that less likely.  */
4977       REG_N_REFS (regno) += (optimize_size ? 1 : pbi->bb->loop_depth + 1);
4978
4979       /* Count the increment as a setting of the register,
4980          even though it isn't a SET in rtl.  */
4981       REG_N_SETS (regno)++;
4982     }
4983 }
4984
4985 /* X is a MEM found in INSN.  See if we can convert it into an auto-increment
4986    reference.  */
4987
4988 static void
4989 find_auto_inc (pbi, x, insn)
4990      struct propagate_block_info *pbi;
4991      rtx x;
4992      rtx insn;
4993 {
4994   rtx addr = XEXP (x, 0);
4995   HOST_WIDE_INT offset = 0;
4996   rtx set, y, incr, inc_val;
4997   int regno;
4998   int size = GET_MODE_SIZE (GET_MODE (x));
4999
5000   if (GET_CODE (insn) == JUMP_INSN)
5001     return;
5002
5003   /* Here we detect use of an index register which might be good for
5004      postincrement, postdecrement, preincrement, or predecrement.  */
5005
5006   if (GET_CODE (addr) == PLUS && GET_CODE (XEXP (addr, 1)) == CONST_INT)
5007     offset = INTVAL (XEXP (addr, 1)), addr = XEXP (addr, 0);
5008
5009   if (GET_CODE (addr) != REG)
5010     return;
5011
5012   regno = REGNO (addr);
5013
5014   /* Is the next use an increment that might make auto-increment? */
5015   incr = pbi->reg_next_use[regno];
5016   if (incr == 0 || BLOCK_NUM (incr) != BLOCK_NUM (insn))
5017     return;
5018   set = single_set (incr);
5019   if (set == 0 || GET_CODE (set) != SET)
5020     return;
5021   y = SET_SRC (set);
5022
5023   if (GET_CODE (y) != PLUS)
5024     return;
5025
5026   if (REG_P (XEXP (y, 0)) && REGNO (XEXP (y, 0)) == REGNO (addr))
5027     inc_val = XEXP (y, 1);
5028   else if (REG_P (XEXP (y, 1)) && REGNO (XEXP (y, 1)) == REGNO (addr))
5029     inc_val = XEXP (y, 0);
5030   else
5031     return;
5032
5033   if (GET_CODE (inc_val) == CONST_INT)
5034     {
5035       if (HAVE_POST_INCREMENT
5036           && (INTVAL (inc_val) == size && offset == 0))
5037         attempt_auto_inc (pbi, gen_rtx_POST_INC (Pmode, addr), insn, x,
5038                           incr, addr);
5039       else if (HAVE_POST_DECREMENT
5040                && (INTVAL (inc_val) == - size && offset == 0))
5041         attempt_auto_inc (pbi, gen_rtx_POST_DEC (Pmode, addr), insn, x,
5042                           incr, addr);
5043       else if (HAVE_PRE_INCREMENT
5044                && (INTVAL (inc_val) == size && offset == size))
5045         attempt_auto_inc (pbi, gen_rtx_PRE_INC (Pmode, addr), insn, x,
5046                           incr, addr);
5047       else if (HAVE_PRE_DECREMENT
5048                && (INTVAL (inc_val) == - size && offset == - size))
5049         attempt_auto_inc (pbi, gen_rtx_PRE_DEC (Pmode, addr), insn, x,
5050                           incr, addr);
5051       else if (HAVE_POST_MODIFY_DISP && offset == 0)
5052         attempt_auto_inc (pbi, gen_rtx_POST_MODIFY (Pmode, addr,
5053                                                     gen_rtx_PLUS (Pmode,
5054                                                                   addr,
5055                                                                   inc_val)),
5056                           insn, x, incr, addr);
5057     }
5058   else if (GET_CODE (inc_val) == REG
5059            && ! reg_set_between_p (inc_val, PREV_INSN (insn),
5060                                    NEXT_INSN (incr)))
5061
5062     {
5063       if (HAVE_POST_MODIFY_REG && offset == 0)
5064         attempt_auto_inc (pbi, gen_rtx_POST_MODIFY (Pmode, addr,
5065                                                     gen_rtx_PLUS (Pmode,
5066                                                                   addr,
5067                                                                   inc_val)),
5068                           insn, x, incr, addr);
5069     }
5070 }
5071
5072 #endif /* AUTO_INC_DEC */
5073 \f
5074 static void
5075 mark_used_reg (pbi, reg, cond, insn)
5076      struct propagate_block_info *pbi;
5077      rtx reg;
5078      rtx cond ATTRIBUTE_UNUSED;
5079      rtx insn;
5080 {
5081   int regno = REGNO (reg);
5082   int some_was_live = REGNO_REG_SET_P (pbi->reg_live, regno);
5083   int some_was_dead = ! some_was_live;
5084   int some_not_set;
5085   int n;
5086
5087   /* A hard reg in a wide mode may really be multiple registers.
5088      If so, mark all of them just like the first.  */
5089   if (regno < FIRST_PSEUDO_REGISTER)
5090     {
5091       n = HARD_REGNO_NREGS (regno, GET_MODE (reg));
5092       while (--n > 0)
5093         {
5094           int needed_regno = REGNO_REG_SET_P (pbi->reg_live, regno + n);
5095           some_was_live |= needed_regno;
5096           some_was_dead |= ! needed_regno;
5097         }
5098     }
5099
5100   if (pbi->flags & (PROP_LOG_LINKS | PROP_AUTOINC))
5101     {
5102       /* Record where each reg is used, so when the reg is set we know
5103          the next insn that uses it.  */
5104       pbi->reg_next_use[regno] = insn;
5105     }
5106
5107   if (pbi->flags & PROP_REG_INFO)
5108     {
5109       if (regno < FIRST_PSEUDO_REGISTER)
5110         {
5111           /* If this is a register we are going to try to eliminate,
5112              don't mark it live here.  If we are successful in
5113              eliminating it, it need not be live unless it is used for
5114              pseudos, in which case it will have been set live when it
5115              was allocated to the pseudos.  If the register will not
5116              be eliminated, reload will set it live at that point.
5117
5118              Otherwise, record that this function uses this register.  */
5119           /* ??? The PPC backend tries to "eliminate" on the pic
5120              register to itself.  This should be fixed.  In the mean
5121              time, hack around it.  */
5122
5123           if (! (TEST_HARD_REG_BIT (elim_reg_set, regno)
5124                  && (regno == FRAME_POINTER_REGNUM
5125                      || regno == ARG_POINTER_REGNUM)))
5126             {
5127               int n = HARD_REGNO_NREGS (regno, GET_MODE (reg));
5128               do
5129                 regs_ever_live[regno + --n] = 1;
5130               while (n > 0);
5131             }
5132         }
5133       else
5134         {
5135           /* Keep track of which basic block each reg appears in.  */
5136
5137           register int blocknum = pbi->bb->index;
5138           if (REG_BASIC_BLOCK (regno) == REG_BLOCK_UNKNOWN)
5139             REG_BASIC_BLOCK (regno) = blocknum;
5140           else if (REG_BASIC_BLOCK (regno) != blocknum)
5141             REG_BASIC_BLOCK (regno) = REG_BLOCK_GLOBAL;
5142
5143           /* Count (weighted) number of uses of each reg.  */
5144           REG_N_REFS (regno) += (optimize_size ? 1
5145                                  : pbi->bb->loop_depth + 1);
5146         }
5147     }
5148
5149   /* Find out if any of the register was set this insn.  */
5150   some_not_set = ! REGNO_REG_SET_P (pbi->new_set, regno);
5151   if (regno < FIRST_PSEUDO_REGISTER)
5152     {
5153       n = HARD_REGNO_NREGS (regno, GET_MODE (reg));
5154       while (--n > 0)
5155         some_not_set |= ! REGNO_REG_SET_P (pbi->new_set, regno + n);
5156     }
5157
5158   /* Record and count the insns in which a reg dies.  If it is used in
5159      this insn and was dead below the insn then it dies in this insn.
5160      If it was set in this insn, we do not make a REG_DEAD note;
5161      likewise if we already made such a note.  */
5162   if ((pbi->flags & (PROP_DEATH_NOTES | PROP_REG_INFO))
5163       && some_was_dead
5164       && some_not_set)
5165     {
5166       /* Check for the case where the register dying partially
5167          overlaps the register set by this insn.  */
5168       if (regno < FIRST_PSEUDO_REGISTER
5169           && HARD_REGNO_NREGS (regno, GET_MODE (reg)) > 1)
5170         {
5171           n = HARD_REGNO_NREGS (regno, GET_MODE (reg));
5172           while (--n >= 0)
5173             some_was_live |= REGNO_REG_SET_P (pbi->new_set, regno + n);
5174         }
5175
5176       /* If none of the words in X is needed, make a REG_DEAD note.
5177          Otherwise, we must make partial REG_DEAD notes.  */
5178       if (! some_was_live)
5179         {
5180           if ((pbi->flags & PROP_DEATH_NOTES)
5181               && ! find_regno_note (insn, REG_DEAD, regno))
5182             REG_NOTES (insn)
5183               = alloc_EXPR_LIST (REG_DEAD, reg, REG_NOTES (insn));
5184
5185           if (pbi->flags & PROP_REG_INFO)
5186             REG_N_DEATHS (regno)++;
5187         }
5188       else
5189         {
5190           /* Don't make a REG_DEAD note for a part of a register
5191              that is set in the insn.  */
5192
5193           n = regno + HARD_REGNO_NREGS (regno, GET_MODE (reg)) - 1;
5194           for (; n >= regno; n--)
5195             if (! REGNO_REG_SET_P (pbi->reg_live, n)
5196                 && ! dead_or_set_regno_p (insn, n))
5197               REG_NOTES (insn)
5198                 = alloc_EXPR_LIST (REG_DEAD,
5199                                    gen_rtx_REG (reg_raw_mode[n], n),
5200                                    REG_NOTES (insn));
5201         }
5202     }
5203
5204   SET_REGNO_REG_SET (pbi->reg_live, regno);
5205   if (regno < FIRST_PSEUDO_REGISTER)
5206     {
5207       n = HARD_REGNO_NREGS (regno, GET_MODE (reg));
5208       while (--n > 0)
5209         SET_REGNO_REG_SET (pbi->reg_live, regno + n);
5210     }
5211
5212 #ifdef HAVE_conditional_execution
5213   /* If this is a conditional use, record that fact.  If it is later
5214      conditionally set, we'll know to kill the register.  */
5215   if (cond != NULL_RTX)
5216     {
5217       splay_tree_node node;
5218       struct reg_cond_life_info *rcli;
5219       rtx ncond;
5220
5221       if (some_was_live)
5222         {
5223           node = splay_tree_lookup (pbi->reg_cond_dead, regno);
5224           if (node == NULL)
5225             {
5226               /* The register was unconditionally live previously.
5227                  No need to do anything.  */
5228             }
5229           else
5230             {
5231               /* The register was conditionally live previously. 
5232                  Subtract the new life cond from the old death cond.  */
5233               rcli = (struct reg_cond_life_info *) node->value;
5234               ncond = rcli->condition;
5235               ncond = nand_reg_cond (ncond, cond);
5236
5237               /* If the register is now unconditionally live, remove the
5238                  entry in the splay_tree.  */
5239               if (ncond == const0_rtx)
5240                 {
5241                   rcli->condition = NULL_RTX;
5242                   splay_tree_remove (pbi->reg_cond_dead, regno);
5243                 }
5244               else
5245                 rcli->condition = ncond;
5246             }
5247         }
5248       else
5249         {
5250           /* The register was not previously live at all.  Record
5251              the condition under which it is still dead.  */
5252           rcli = (struct reg_cond_life_info *) xmalloc (sizeof (*rcli));
5253           rcli->condition = not_reg_cond (cond);
5254           splay_tree_insert (pbi->reg_cond_dead, regno,
5255                              (splay_tree_value) rcli);
5256         }
5257     }
5258   else if (some_was_live)
5259     {
5260       splay_tree_node node;
5261       struct reg_cond_life_info *rcli;
5262
5263       node = splay_tree_lookup (pbi->reg_cond_dead, regno);
5264       if (node != NULL)
5265         {
5266           /* The register was conditionally live previously, but is now
5267              unconditionally so.  Remove it from the conditionally dead
5268              list, so that a conditional set won't cause us to think
5269              it dead.  */
5270           rcli = (struct reg_cond_life_info *) node->value;
5271           rcli->condition = NULL_RTX;
5272           splay_tree_remove (pbi->reg_cond_dead, regno);
5273         }
5274     }
5275
5276 #endif
5277 }
5278
5279 /* Scan expression X and store a 1-bit in NEW_LIVE for each reg it uses.
5280    This is done assuming the registers needed from X are those that
5281    have 1-bits in PBI->REG_LIVE.
5282
5283    INSN is the containing instruction.  If INSN is dead, this function
5284    is not called.  */
5285
5286 static void
5287 mark_used_regs (pbi, x, cond, insn)
5288      struct propagate_block_info *pbi;
5289      rtx x, cond, insn;
5290 {
5291   register RTX_CODE code;
5292   register int regno;
5293   int flags = pbi->flags;
5294
5295  retry:
5296   code = GET_CODE (x);
5297   switch (code)
5298     {
5299     case LABEL_REF:
5300     case SYMBOL_REF:
5301     case CONST_INT:
5302     case CONST:
5303     case CONST_DOUBLE:
5304     case PC:
5305     case ADDR_VEC:
5306     case ADDR_DIFF_VEC:
5307       return;
5308
5309 #ifdef HAVE_cc0
5310     case CC0:
5311       pbi->cc0_live = 1;
5312       return;
5313 #endif
5314
5315     case CLOBBER:
5316       /* If we are clobbering a MEM, mark any registers inside the address
5317          as being used.  */
5318       if (GET_CODE (XEXP (x, 0)) == MEM)
5319         mark_used_regs (pbi, XEXP (XEXP (x, 0), 0), cond, insn);
5320       return;
5321
5322     case MEM:
5323       /* Don't bother watching stores to mems if this is not the 
5324          final pass.  We'll not be deleting dead stores this round.  */
5325       if (optimize && (flags & PROP_SCAN_DEAD_CODE))
5326         {
5327           /* Invalidate the data for the last MEM stored, but only if MEM is
5328              something that can be stored into.  */
5329           if (GET_CODE (XEXP (x, 0)) == SYMBOL_REF
5330               && CONSTANT_POOL_ADDRESS_P (XEXP (x, 0)))
5331             ; /* needn't clear the memory set list */
5332           else
5333             {
5334               rtx temp = pbi->mem_set_list;
5335               rtx prev = NULL_RTX;
5336               rtx next;
5337
5338               while (temp)
5339                 {
5340                   next = XEXP (temp, 1);
5341                   if (anti_dependence (XEXP (temp, 0), x))
5342                     {
5343                       /* Splice temp out of the list.  */
5344                       if (prev)
5345                         XEXP (prev, 1) = next;
5346                       else
5347                         pbi->mem_set_list = next;
5348                       free_EXPR_LIST_node (temp);
5349                     }
5350                   else
5351                     prev = temp;
5352                   temp = next;
5353                 }
5354             }
5355
5356           /* If the memory reference had embedded side effects (autoincrement
5357              address modes.  Then we may need to kill some entries on the
5358              memory set list.  */
5359           if (insn)
5360             invalidate_mems_from_autoinc (pbi, insn);
5361         }
5362
5363 #ifdef AUTO_INC_DEC
5364       if (flags & PROP_AUTOINC)
5365         find_auto_inc (pbi, x, insn);
5366 #endif
5367       break;
5368
5369     case SUBREG:
5370 #ifdef CLASS_CANNOT_CHANGE_MODE
5371       if (GET_CODE (SUBREG_REG (x)) == REG
5372           && REGNO (SUBREG_REG (x)) >= FIRST_PSEUDO_REGISTER
5373           && CLASS_CANNOT_CHANGE_MODE_P (GET_MODE (x),
5374                                          GET_MODE (SUBREG_REG (x))))
5375         REG_CHANGES_MODE (REGNO (SUBREG_REG (x))) = 1;
5376 #endif
5377
5378       /* While we're here, optimize this case.  */
5379       x = SUBREG_REG (x);
5380       if (GET_CODE (x) != REG)
5381         goto retry;
5382       /* FALLTHRU */
5383
5384     case REG:
5385       /* See a register other than being set => mark it as needed.  */
5386       mark_used_reg (pbi, x, cond, insn);
5387       return;
5388
5389     case SET:
5390       {
5391         register rtx testreg = SET_DEST (x);
5392         int mark_dest = 0;
5393
5394         /* If storing into MEM, don't show it as being used.  But do
5395            show the address as being used.  */
5396         if (GET_CODE (testreg) == MEM)
5397           {
5398 #ifdef AUTO_INC_DEC
5399             if (flags & PROP_AUTOINC)
5400               find_auto_inc (pbi, testreg, insn);
5401 #endif
5402             mark_used_regs (pbi, XEXP (testreg, 0), cond, insn);
5403             mark_used_regs (pbi, SET_SRC (x), cond, insn);
5404             return;
5405           }
5406             
5407         /* Storing in STRICT_LOW_PART is like storing in a reg
5408            in that this SET might be dead, so ignore it in TESTREG.
5409            but in some other ways it is like using the reg.
5410
5411            Storing in a SUBREG or a bit field is like storing the entire
5412            register in that if the register's value is not used
5413            then this SET is not needed.  */
5414         while (GET_CODE (testreg) == STRICT_LOW_PART
5415                || GET_CODE (testreg) == ZERO_EXTRACT
5416                || GET_CODE (testreg) == SIGN_EXTRACT
5417                || GET_CODE (testreg) == SUBREG)
5418           {
5419 #ifdef CLASS_CANNOT_CHANGE_MODE
5420             if (GET_CODE (testreg) == SUBREG
5421                 && GET_CODE (SUBREG_REG (testreg)) == REG
5422                 && REGNO (SUBREG_REG (testreg)) >= FIRST_PSEUDO_REGISTER
5423                 && CLASS_CANNOT_CHANGE_MODE_P (GET_MODE (SUBREG_REG (testreg)),
5424                                                GET_MODE (testreg)))
5425               REG_CHANGES_MODE (REGNO (SUBREG_REG (testreg))) = 1;
5426 #endif
5427
5428             /* Modifying a single register in an alternate mode
5429                does not use any of the old value.  But these other
5430                ways of storing in a register do use the old value.  */
5431             if (GET_CODE (testreg) == SUBREG
5432                 && !(REG_SIZE (SUBREG_REG (testreg)) > REG_SIZE (testreg)))
5433               ;
5434             else
5435               mark_dest = 1;
5436
5437             testreg = XEXP (testreg, 0);
5438           }
5439
5440         /* If this is a store into a register, recursively scan the
5441            value being stored.  */
5442
5443         if ((GET_CODE (testreg) == PARALLEL
5444              && GET_MODE (testreg) == BLKmode)
5445             || (GET_CODE (testreg) == REG
5446                 && (regno = REGNO (testreg),
5447                     ! (regno == FRAME_POINTER_REGNUM
5448                        && (! reload_completed || frame_pointer_needed)))
5449 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
5450                 && ! (regno == HARD_FRAME_POINTER_REGNUM
5451                       && (! reload_completed || frame_pointer_needed))
5452 #endif
5453 #if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
5454                 && ! (regno == ARG_POINTER_REGNUM && fixed_regs[regno])
5455 #endif
5456                 ))
5457           {
5458             if (mark_dest)
5459               mark_used_regs (pbi, SET_DEST (x), cond, insn);
5460             mark_used_regs (pbi, SET_SRC (x), cond, insn);
5461             return;
5462           }
5463       }
5464       break;
5465
5466     case ASM_OPERANDS:
5467     case UNSPEC_VOLATILE:
5468     case TRAP_IF:
5469     case ASM_INPUT:
5470       {
5471         /* Traditional and volatile asm instructions must be considered to use
5472            and clobber all hard registers, all pseudo-registers and all of
5473            memory.  So must TRAP_IF and UNSPEC_VOLATILE operations.
5474
5475            Consider for instance a volatile asm that changes the fpu rounding
5476            mode.  An insn should not be moved across this even if it only uses
5477            pseudo-regs because it might give an incorrectly rounded result. 
5478
5479            ?!? Unfortunately, marking all hard registers as live causes massive
5480            problems for the register allocator and marking all pseudos as live
5481            creates mountains of uninitialized variable warnings.
5482
5483            So for now, just clear the memory set list and mark any regs
5484            we can find in ASM_OPERANDS as used.  */
5485         if (code != ASM_OPERANDS || MEM_VOLATILE_P (x))
5486           free_EXPR_LIST_list (&pbi->mem_set_list);
5487
5488         /* For all ASM_OPERANDS, we must traverse the vector of input operands.
5489            We can not just fall through here since then we would be confused
5490            by the ASM_INPUT rtx inside ASM_OPERANDS, which do not indicate
5491            traditional asms unlike their normal usage.  */
5492         if (code == ASM_OPERANDS)
5493           {
5494             int j;
5495
5496             for (j = 0; j < ASM_OPERANDS_INPUT_LENGTH (x); j++)
5497               mark_used_regs (pbi, ASM_OPERANDS_INPUT (x, j), cond, insn);
5498           }
5499         break;
5500       }
5501
5502     case COND_EXEC:
5503       if (cond != NULL_RTX)
5504         abort ();
5505
5506       mark_used_regs (pbi, COND_EXEC_TEST (x), NULL_RTX, insn);
5507
5508       cond = COND_EXEC_TEST (x);
5509       x = COND_EXEC_CODE (x);
5510       goto retry;
5511
5512     case PHI:
5513       /* We _do_not_ want to scan operands of phi nodes.  Operands of
5514          a phi function are evaluated only when control reaches this
5515          block along a particular edge.  Therefore, regs that appear
5516          as arguments to phi should not be added to the global live at
5517          start.  */
5518       return;
5519
5520     default:
5521       break;
5522     }
5523
5524   /* Recursively scan the operands of this expression.  */
5525
5526   {
5527     register const char *fmt = GET_RTX_FORMAT (code);
5528     register int i;
5529     
5530     for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
5531       {
5532         if (fmt[i] == 'e')
5533           {
5534             /* Tail recursive case: save a function call level.  */
5535             if (i == 0)
5536               {
5537                 x = XEXP (x, 0);
5538                 goto retry;
5539               }
5540             mark_used_regs (pbi, XEXP (x, i), cond, insn);
5541           }
5542         else if (fmt[i] == 'E')
5543           {
5544             register int j;
5545             for (j = 0; j < XVECLEN (x, i); j++)
5546               mark_used_regs (pbi, XVECEXP (x, i, j), cond, insn);
5547           }
5548       }
5549   }
5550 }
5551 \f
5552 #ifdef AUTO_INC_DEC
5553
5554 static int
5555 try_pre_increment_1 (pbi, insn)
5556      struct propagate_block_info *pbi;
5557      rtx insn;
5558 {
5559   /* Find the next use of this reg.  If in same basic block,
5560      make it do pre-increment or pre-decrement if appropriate.  */
5561   rtx x = single_set (insn);
5562   HOST_WIDE_INT amount = ((GET_CODE (SET_SRC (x)) == PLUS ? 1 : -1)
5563                 * INTVAL (XEXP (SET_SRC (x), 1)));
5564   int regno = REGNO (SET_DEST (x));
5565   rtx y = pbi->reg_next_use[regno];
5566   if (y != 0
5567       && BLOCK_NUM (y) == BLOCK_NUM (insn)
5568       /* Don't do this if the reg dies, or gets set in y; a standard addressing
5569          mode would be better.  */
5570       && ! dead_or_set_p (y, SET_DEST (x))
5571       && try_pre_increment (y, SET_DEST (x), amount))
5572     {
5573       /* We have found a suitable auto-increment
5574          and already changed insn Y to do it.
5575          So flush this increment-instruction.  */
5576       PUT_CODE (insn, NOTE);
5577       NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
5578       NOTE_SOURCE_FILE (insn) = 0;
5579       /* Count a reference to this reg for the increment
5580          insn we are deleting.  When a reg is incremented.
5581          spilling it is worse, so we want to make that
5582          less likely.  */
5583       if (regno >= FIRST_PSEUDO_REGISTER)
5584         {
5585           REG_N_REFS (regno) += (optimize_size ? 1
5586                                  : pbi->bb->loop_depth + 1);
5587           REG_N_SETS (regno)++;
5588         }
5589       return 1;
5590     }
5591   return 0;
5592 }
5593
5594 /* Try to change INSN so that it does pre-increment or pre-decrement
5595    addressing on register REG in order to add AMOUNT to REG.
5596    AMOUNT is negative for pre-decrement.
5597    Returns 1 if the change could be made.
5598    This checks all about the validity of the result of modifying INSN.  */
5599
5600 static int
5601 try_pre_increment (insn, reg, amount)
5602      rtx insn, reg;
5603      HOST_WIDE_INT amount;
5604 {
5605   register rtx use;
5606
5607   /* Nonzero if we can try to make a pre-increment or pre-decrement.
5608      For example, addl $4,r1; movl (r1),... can become movl +(r1),...  */
5609   int pre_ok = 0;
5610   /* Nonzero if we can try to make a post-increment or post-decrement.
5611      For example, addl $4,r1; movl -4(r1),... can become movl (r1)+,...
5612      It is possible for both PRE_OK and POST_OK to be nonzero if the machine
5613      supports both pre-inc and post-inc, or both pre-dec and post-dec.  */
5614   int post_ok = 0;
5615
5616   /* Nonzero if the opportunity actually requires post-inc or post-dec.  */
5617   int do_post = 0;
5618
5619   /* From the sign of increment, see which possibilities are conceivable
5620      on this target machine.  */
5621   if (HAVE_PRE_INCREMENT && amount > 0)
5622     pre_ok = 1;
5623   if (HAVE_POST_INCREMENT && amount > 0)
5624     post_ok = 1;
5625
5626   if (HAVE_PRE_DECREMENT && amount < 0)
5627     pre_ok = 1;
5628   if (HAVE_POST_DECREMENT && amount < 0)
5629     post_ok = 1;
5630
5631   if (! (pre_ok || post_ok))
5632     return 0;
5633
5634   /* It is not safe to add a side effect to a jump insn
5635      because if the incremented register is spilled and must be reloaded
5636      there would be no way to store the incremented value back in memory.  */
5637
5638   if (GET_CODE (insn) == JUMP_INSN)
5639     return 0;
5640
5641   use = 0;
5642   if (pre_ok)
5643     use = find_use_as_address (PATTERN (insn), reg, 0);
5644   if (post_ok && (use == 0 || use == (rtx) 1))
5645     {
5646       use = find_use_as_address (PATTERN (insn), reg, -amount);
5647       do_post = 1;
5648     }
5649
5650   if (use == 0 || use == (rtx) 1)
5651     return 0;
5652
5653   if (GET_MODE_SIZE (GET_MODE (use)) != (amount > 0 ? amount : - amount))
5654     return 0;
5655
5656   /* See if this combination of instruction and addressing mode exists.  */
5657   if (! validate_change (insn, &XEXP (use, 0),
5658                          gen_rtx_fmt_e (amount > 0
5659                                         ? (do_post ? POST_INC : PRE_INC)
5660                                         : (do_post ? POST_DEC : PRE_DEC),
5661                                         Pmode, reg), 0))
5662     return 0;
5663
5664   /* Record that this insn now has an implicit side effect on X.  */
5665   REG_NOTES (insn) = alloc_EXPR_LIST (REG_INC, reg, REG_NOTES (insn));
5666   return 1;
5667 }
5668
5669 #endif /* AUTO_INC_DEC */
5670 \f
5671 /* Find the place in the rtx X where REG is used as a memory address.
5672    Return the MEM rtx that so uses it.
5673    If PLUSCONST is nonzero, search instead for a memory address equivalent to
5674    (plus REG (const_int PLUSCONST)).
5675
5676    If such an address does not appear, return 0.
5677    If REG appears more than once, or is used other than in such an address,
5678    return (rtx)1.  */
5679
5680 rtx
5681 find_use_as_address (x, reg, plusconst)
5682      register rtx x;
5683      rtx reg;
5684      HOST_WIDE_INT plusconst;
5685 {
5686   enum rtx_code code = GET_CODE (x);
5687   const char *fmt = GET_RTX_FORMAT (code);
5688   register int i;
5689   register rtx value = 0;
5690   register rtx tem;
5691
5692   if (code == MEM && XEXP (x, 0) == reg && plusconst == 0)
5693     return x;
5694
5695   if (code == MEM && GET_CODE (XEXP (x, 0)) == PLUS
5696       && XEXP (XEXP (x, 0), 0) == reg
5697       && GET_CODE (XEXP (XEXP (x, 0), 1)) == CONST_INT
5698       && INTVAL (XEXP (XEXP (x, 0), 1)) == plusconst)
5699     return x;
5700
5701   if (code == SIGN_EXTRACT || code == ZERO_EXTRACT)
5702     {
5703       /* If REG occurs inside a MEM used in a bit-field reference,
5704          that is unacceptable.  */
5705       if (find_use_as_address (XEXP (x, 0), reg, 0) != 0)
5706         return (rtx) (HOST_WIDE_INT) 1;
5707     }
5708
5709   if (x == reg)
5710     return (rtx) (HOST_WIDE_INT) 1;
5711
5712   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
5713     {
5714       if (fmt[i] == 'e')
5715         {
5716           tem = find_use_as_address (XEXP (x, i), reg, plusconst);
5717           if (value == 0)
5718             value = tem;
5719           else if (tem != 0)
5720             return (rtx) (HOST_WIDE_INT) 1;
5721         }
5722       else if (fmt[i] == 'E')
5723         {
5724           register int j;
5725           for (j = XVECLEN (x, i) - 1; j >= 0; j--)
5726             {
5727               tem = find_use_as_address (XVECEXP (x, i, j), reg, plusconst);
5728               if (value == 0)
5729                 value = tem;
5730               else if (tem != 0)
5731                 return (rtx) (HOST_WIDE_INT) 1;
5732             }
5733         }
5734     }
5735
5736   return value;
5737 }
5738 \f
5739 /* Write information about registers and basic blocks into FILE.
5740    This is part of making a debugging dump.  */
5741
5742 void
5743 dump_regset (r, outf)
5744      regset r;
5745      FILE *outf;
5746 {
5747   int i;
5748   if (r == NULL)
5749     {
5750       fputs (" (nil)", outf);
5751       return;
5752     }
5753
5754   EXECUTE_IF_SET_IN_REG_SET (r, 0, i,
5755     {
5756       fprintf (outf, " %d", i);
5757       if (i < FIRST_PSEUDO_REGISTER)
5758         fprintf (outf, " [%s]",
5759                  reg_names[i]);
5760     });
5761 }
5762
5763 void
5764 debug_regset (r)
5765      regset r;
5766 {
5767   dump_regset (r, stderr);
5768   putc ('\n', stderr);
5769 }
5770
5771 void
5772 dump_flow_info (file)
5773      FILE *file;
5774 {
5775   register int i;
5776   static const char * const reg_class_names[] = REG_CLASS_NAMES;
5777
5778   fprintf (file, "%d registers.\n", max_regno);
5779   for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
5780     if (REG_N_REFS (i))
5781       {
5782         enum reg_class class, altclass;
5783         fprintf (file, "\nRegister %d used %d times across %d insns",
5784                  i, REG_N_REFS (i), REG_LIVE_LENGTH (i));
5785         if (REG_BASIC_BLOCK (i) >= 0)
5786           fprintf (file, " in block %d", REG_BASIC_BLOCK (i));
5787         if (REG_N_SETS (i))
5788           fprintf (file, "; set %d time%s", REG_N_SETS (i),
5789                    (REG_N_SETS (i) == 1) ? "" : "s");
5790         if (REG_USERVAR_P (regno_reg_rtx[i]))
5791           fprintf (file, "; user var");
5792         if (REG_N_DEATHS (i) != 1)
5793           fprintf (file, "; dies in %d places", REG_N_DEATHS (i));
5794         if (REG_N_CALLS_CROSSED (i) == 1)
5795           fprintf (file, "; crosses 1 call");
5796         else if (REG_N_CALLS_CROSSED (i))
5797           fprintf (file, "; crosses %d calls", REG_N_CALLS_CROSSED (i));
5798         if (PSEUDO_REGNO_BYTES (i) != UNITS_PER_WORD)
5799           fprintf (file, "; %d bytes", PSEUDO_REGNO_BYTES (i));
5800         class = reg_preferred_class (i);
5801         altclass = reg_alternate_class (i);
5802         if (class != GENERAL_REGS || altclass != ALL_REGS)
5803           {
5804             if (altclass == ALL_REGS || class == ALL_REGS)
5805               fprintf (file, "; pref %s", reg_class_names[(int) class]);
5806             else if (altclass == NO_REGS)
5807               fprintf (file, "; %s or none", reg_class_names[(int) class]);
5808             else
5809               fprintf (file, "; pref %s, else %s",
5810                        reg_class_names[(int) class],
5811                        reg_class_names[(int) altclass]);
5812           }
5813         if (REGNO_POINTER_FLAG (i))
5814           fprintf (file, "; pointer");
5815         fprintf (file, ".\n");
5816       }
5817
5818   fprintf (file, "\n%d basic blocks, %d edges.\n", n_basic_blocks, n_edges);
5819   for (i = 0; i < n_basic_blocks; i++)
5820     {
5821       register basic_block bb = BASIC_BLOCK (i);
5822       register edge e;
5823
5824       fprintf (file, "\nBasic block %d: first insn %d, last %d, loop_depth %d, count %d.\n",
5825                i, INSN_UID (bb->head), INSN_UID (bb->end), bb->loop_depth, bb->count);
5826
5827       fprintf (file, "Predecessors: ");
5828       for (e = bb->pred; e ; e = e->pred_next)
5829         dump_edge_info (file, e, 0);
5830
5831       fprintf (file, "\nSuccessors: ");
5832       for (e = bb->succ; e ; e = e->succ_next)
5833         dump_edge_info (file, e, 1);
5834
5835       fprintf (file, "\nRegisters live at start:");
5836       dump_regset (bb->global_live_at_start, file);
5837
5838       fprintf (file, "\nRegisters live at end:");
5839       dump_regset (bb->global_live_at_end, file);
5840
5841       putc('\n', file);
5842     }
5843
5844   putc('\n', file);
5845 }
5846
5847 void
5848 debug_flow_info ()
5849 {
5850   dump_flow_info (stderr);
5851 }
5852
5853 static void
5854 dump_edge_info (file, e, do_succ)
5855      FILE *file;
5856      edge e;
5857      int do_succ;
5858 {
5859   basic_block side = (do_succ ? e->dest : e->src);
5860
5861   if (side == ENTRY_BLOCK_PTR)
5862     fputs (" ENTRY", file);
5863   else if (side == EXIT_BLOCK_PTR)
5864     fputs (" EXIT", file);
5865   else
5866     fprintf (file, " %d", side->index);
5867
5868   if (e->count)
5869     fprintf (file, " count:%d", e->count);
5870
5871   if (e->flags)
5872     {
5873       static const char * const bitnames[] = {
5874         "fallthru", "crit", "ab", "abcall", "eh", "fake"
5875       };
5876       int comma = 0;
5877       int i, flags = e->flags;
5878
5879       fputc (' ', file);
5880       fputc ('(', file);
5881       for (i = 0; flags; i++)
5882         if (flags & (1 << i))
5883           {
5884             flags &= ~(1 << i);
5885
5886             if (comma)
5887               fputc (',', file);
5888             if (i < (int)(sizeof (bitnames) / sizeof (*bitnames)))
5889               fputs (bitnames[i], file);
5890             else
5891               fprintf (file, "%d", i);
5892             comma = 1;
5893           }
5894       fputc (')', file);
5895     }
5896 }
5897
5898 \f
5899 /* Print out one basic block with live information at start and end.  */
5900 void
5901 dump_bb (bb, outf)
5902      basic_block bb;
5903      FILE *outf;
5904 {
5905   rtx insn;
5906   rtx last;
5907   edge e;
5908
5909   fprintf (outf, ";; Basic block %d, loop depth %d, count %d",
5910            bb->index, bb->loop_depth, bb->count);
5911   if (bb->eh_beg != -1 || bb->eh_end != -1)
5912     fprintf (outf, ", eh regions %d/%d", bb->eh_beg, bb->eh_end);
5913   putc ('\n', outf);
5914
5915   fputs (";; Predecessors: ", outf);
5916   for (e = bb->pred; e ; e = e->pred_next)
5917     dump_edge_info (outf, e, 0);
5918   putc ('\n', outf);
5919
5920   fputs (";; Registers live at start:", outf);
5921   dump_regset (bb->global_live_at_start, outf);
5922   putc ('\n', outf);
5923
5924   for (insn = bb->head, last = NEXT_INSN (bb->end);
5925        insn != last;
5926        insn = NEXT_INSN (insn))
5927     print_rtl_single (outf, insn);
5928
5929   fputs (";; Registers live at end:", outf);
5930   dump_regset (bb->global_live_at_end, outf);
5931   putc ('\n', outf);
5932
5933   fputs (";; Successors: ", outf);
5934   for (e = bb->succ; e; e = e->succ_next)
5935     dump_edge_info (outf, e, 1);
5936   putc ('\n', outf);
5937 }
5938
5939 void
5940 debug_bb (bb)
5941      basic_block bb;
5942 {
5943   dump_bb (bb, stderr);
5944 }
5945
5946 void
5947 debug_bb_n (n)
5948      int n;
5949 {
5950   dump_bb (BASIC_BLOCK(n), stderr);
5951 }
5952
5953 /* Like print_rtl, but also print out live information for the start of each
5954    basic block.  */
5955
5956 void
5957 print_rtl_with_bb (outf, rtx_first)
5958      FILE *outf;
5959      rtx rtx_first;
5960 {
5961   register rtx tmp_rtx;
5962
5963   if (rtx_first == 0)
5964     fprintf (outf, "(nil)\n");
5965   else
5966     {
5967       int i;
5968       enum bb_state { NOT_IN_BB, IN_ONE_BB, IN_MULTIPLE_BB };
5969       int max_uid = get_max_uid ();
5970       basic_block *start = (basic_block *)
5971         xcalloc (max_uid, sizeof (basic_block));
5972       basic_block *end = (basic_block *)
5973         xcalloc (max_uid, sizeof (basic_block));
5974       enum bb_state *in_bb_p = (enum bb_state *)
5975         xcalloc (max_uid, sizeof (enum bb_state));
5976
5977       for (i = n_basic_blocks - 1; i >= 0; i--)
5978         {
5979           basic_block bb = BASIC_BLOCK (i);
5980           rtx x;
5981
5982           start[INSN_UID (bb->head)] = bb;
5983           end[INSN_UID (bb->end)] = bb;
5984           for (x = bb->head; x != NULL_RTX; x = NEXT_INSN (x))
5985             {
5986               enum bb_state state = IN_MULTIPLE_BB;
5987               if (in_bb_p[INSN_UID(x)] == NOT_IN_BB)
5988                 state = IN_ONE_BB;
5989               in_bb_p[INSN_UID(x)] = state;
5990
5991               if (x == bb->end)
5992                 break;
5993             }
5994         }
5995
5996       for (tmp_rtx = rtx_first; NULL != tmp_rtx; tmp_rtx = NEXT_INSN (tmp_rtx))
5997         {
5998           int did_output;
5999           basic_block bb;
6000
6001           if ((bb = start[INSN_UID (tmp_rtx)]) != NULL)
6002             {
6003               fprintf (outf, ";; Start of basic block %d, registers live:",
6004                        bb->index);
6005               dump_regset (bb->global_live_at_start, outf);
6006               putc ('\n', outf);
6007             }
6008
6009           if (in_bb_p[INSN_UID(tmp_rtx)] == NOT_IN_BB
6010               && GET_CODE (tmp_rtx) != NOTE
6011               && GET_CODE (tmp_rtx) != BARRIER)
6012             fprintf (outf, ";; Insn is not within a basic block\n");
6013           else if (in_bb_p[INSN_UID(tmp_rtx)] == IN_MULTIPLE_BB)
6014             fprintf (outf, ";; Insn is in multiple basic blocks\n");
6015
6016           did_output = print_rtl_single (outf, tmp_rtx);
6017
6018           if ((bb = end[INSN_UID (tmp_rtx)]) != NULL)
6019             {
6020               fprintf (outf, ";; End of basic block %d, registers live:\n",
6021                        bb->index);
6022               dump_regset (bb->global_live_at_end, outf);
6023               putc ('\n', outf);
6024             }
6025
6026           if (did_output)
6027             putc ('\n', outf);
6028         }
6029
6030       free (start);
6031       free (end);
6032       free (in_bb_p);
6033     }
6034
6035   if (current_function_epilogue_delay_list != 0)
6036     {
6037       fprintf (outf, "\n;; Insns in epilogue delay list:\n\n");
6038       for (tmp_rtx = current_function_epilogue_delay_list; tmp_rtx != 0;
6039            tmp_rtx = XEXP (tmp_rtx, 1))
6040         print_rtl_single (outf, XEXP (tmp_rtx, 0));
6041     }
6042 }
6043
6044 /* Compute dominator relationships using new flow graph structures.  */
6045 void
6046 compute_flow_dominators (dominators, post_dominators)
6047      sbitmap *dominators;
6048      sbitmap *post_dominators;
6049 {
6050   int bb;
6051   sbitmap *temp_bitmap;
6052   edge e;
6053   basic_block *worklist, *workend, *qin, *qout;
6054   int qlen;
6055
6056   /* Allocate a worklist array/queue.  Entries are only added to the
6057      list if they were not already on the list.  So the size is
6058      bounded by the number of basic blocks.  */
6059   worklist = (basic_block *) xmalloc (sizeof (basic_block) * n_basic_blocks);
6060   workend = &worklist[n_basic_blocks];
6061
6062   temp_bitmap = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks);
6063   sbitmap_vector_zero (temp_bitmap, n_basic_blocks);
6064
6065   if (dominators)
6066     {
6067       /* The optimistic setting of dominators requires us to put every
6068          block on the work list initially.  */
6069       qin = qout = worklist;
6070       for (bb = 0; bb < n_basic_blocks; bb++)
6071         {
6072           *qin++ = BASIC_BLOCK (bb);
6073           BASIC_BLOCK (bb)->aux = BASIC_BLOCK (bb);
6074         }
6075       qlen = n_basic_blocks;
6076       qin = worklist;
6077
6078       /* We want a maximal solution, so initially assume everything dominates
6079          everything else.  */
6080       sbitmap_vector_ones (dominators, n_basic_blocks);
6081
6082       /* Mark successors of the entry block so we can identify them below.  */
6083       for (e = ENTRY_BLOCK_PTR->succ; e; e = e->succ_next)
6084         e->dest->aux = ENTRY_BLOCK_PTR;
6085
6086       /* Iterate until the worklist is empty.  */
6087       while (qlen)
6088         {
6089           /* Take the first entry off the worklist.  */
6090           basic_block b = *qout++;
6091           if (qout >= workend)
6092             qout = worklist;
6093           qlen--;
6094
6095           bb = b->index;
6096
6097           /* Compute the intersection of the dominators of all the
6098              predecessor blocks.
6099
6100              If one of the predecessor blocks is the ENTRY block, then the
6101              intersection of the dominators of the predecessor blocks is
6102              defined as the null set.  We can identify such blocks by the
6103              special value in the AUX field in the block structure.  */
6104           if (b->aux == ENTRY_BLOCK_PTR)
6105             {
6106               /* Do not clear the aux field for blocks which are
6107                  successors of the ENTRY block.  That way we never add
6108                  them to the worklist again.
6109
6110                  The intersect of dominators of the preds of this block is
6111                  defined as the null set.  */
6112               sbitmap_zero (temp_bitmap[bb]);
6113             }
6114           else
6115             {
6116               /* Clear the aux field of this block so it can be added to
6117                  the worklist again if necessary.  */
6118               b->aux = NULL;
6119               sbitmap_intersection_of_preds (temp_bitmap[bb], dominators, bb);
6120             }
6121
6122           /* Make sure each block always dominates itself.  */
6123           SET_BIT (temp_bitmap[bb], bb);
6124
6125           /* If the out state of this block changed, then we need to
6126              add the successors of this block to the worklist if they
6127              are not already on the worklist.  */
6128           if (sbitmap_a_and_b (dominators[bb], dominators[bb], temp_bitmap[bb]))
6129             {
6130               for (e = b->succ; e; e = e->succ_next)
6131                 {
6132                   if (!e->dest->aux && e->dest != EXIT_BLOCK_PTR)
6133                     {
6134                       *qin++ = e->dest;
6135                       if (qin >= workend)
6136                         qin = worklist;
6137                       qlen++;
6138
6139                       e->dest->aux = e;
6140                     }
6141                 }
6142             }
6143         }
6144     }
6145
6146   if (post_dominators)
6147     {
6148       /* The optimistic setting of dominators requires us to put every
6149          block on the work list initially.  */
6150       qin = qout = worklist;
6151       for (bb = 0; bb < n_basic_blocks; bb++)
6152         {
6153           *qin++ = BASIC_BLOCK (bb);
6154           BASIC_BLOCK (bb)->aux = BASIC_BLOCK (bb);
6155         }
6156       qlen = n_basic_blocks;
6157       qin = worklist;
6158
6159       /* We want a maximal solution, so initially assume everything post
6160          dominates everything else.  */
6161       sbitmap_vector_ones (post_dominators, n_basic_blocks);
6162
6163       /* Mark predecessors of the exit block so we can identify them below.  */
6164       for (e = EXIT_BLOCK_PTR->pred; e; e = e->pred_next)
6165         e->src->aux = EXIT_BLOCK_PTR;
6166
6167       /* Iterate until the worklist is empty.  */
6168       while (qlen)
6169         {
6170           /* Take the first entry off the worklist.  */
6171           basic_block b = *qout++;
6172           if (qout >= workend)
6173             qout = worklist;
6174           qlen--;
6175
6176           bb = b->index;
6177
6178           /* Compute the intersection of the post dominators of all the
6179              successor blocks.
6180
6181              If one of the successor blocks is the EXIT block, then the
6182              intersection of the dominators of the successor blocks is
6183              defined as the null set.  We can identify such blocks by the
6184              special value in the AUX field in the block structure.  */
6185           if (b->aux == EXIT_BLOCK_PTR)
6186             {
6187               /* Do not clear the aux field for blocks which are
6188                  predecessors of the EXIT block.  That way we we never
6189                  add them to the worklist again.
6190
6191                  The intersect of dominators of the succs of this block is
6192                  defined as the null set.  */
6193               sbitmap_zero (temp_bitmap[bb]);
6194             }
6195           else
6196             {
6197               /* Clear the aux field of this block so it can be added to
6198                  the worklist again if necessary.  */
6199               b->aux = NULL;
6200               sbitmap_intersection_of_succs (temp_bitmap[bb],
6201                                              post_dominators, bb);
6202             }
6203
6204           /* Make sure each block always post dominates itself.  */
6205           SET_BIT (temp_bitmap[bb], bb);
6206
6207           /* If the out state of this block changed, then we need to
6208              add the successors of this block to the worklist if they
6209              are not already on the worklist.  */
6210           if (sbitmap_a_and_b (post_dominators[bb],
6211                                post_dominators[bb],
6212                                temp_bitmap[bb]))
6213             {
6214               for (e = b->pred; e; e = e->pred_next)
6215                 {
6216                   if (!e->src->aux && e->src != ENTRY_BLOCK_PTR)
6217                     {
6218                       *qin++ = e->src;
6219                       if (qin >= workend)
6220                         qin = worklist;
6221                       qlen++;
6222
6223                       e->src->aux = e;
6224                     }
6225                 }
6226             }
6227         }
6228     }
6229
6230   free (worklist);
6231   free (temp_bitmap);
6232 }
6233
6234 /* Given DOMINATORS, compute the immediate dominators into IDOM.  If a
6235    block dominates only itself, its entry remains as INVALID_BLOCK.  */
6236
6237 void
6238 compute_immediate_dominators (idom, dominators)
6239      int *idom;
6240      sbitmap *dominators;
6241 {
6242   sbitmap *tmp;
6243   int b;
6244
6245   tmp = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks);
6246
6247   /* Begin with tmp(n) = dom(n) - { n }.  */
6248   for (b = n_basic_blocks; --b >= 0; )
6249     {
6250       sbitmap_copy (tmp[b], dominators[b]);
6251       RESET_BIT (tmp[b], b);
6252     }
6253
6254   /* Subtract out all of our dominator's dominators.  */
6255   for (b = n_basic_blocks; --b >= 0; )
6256     {
6257       sbitmap tmp_b = tmp[b];
6258       int s;
6259
6260       for (s = n_basic_blocks; --s >= 0; )
6261         if (TEST_BIT (tmp_b, s))
6262           sbitmap_difference (tmp_b, tmp_b, tmp[s]);
6263     }
6264
6265   /* Find the one bit set in the bitmap and put it in the output array.  */
6266   for (b = n_basic_blocks; --b >= 0; )
6267     {
6268       int t;
6269       EXECUTE_IF_SET_IN_SBITMAP (tmp[b], 0, t, { idom[b] = t; });
6270     }
6271
6272   sbitmap_vector_free (tmp);
6273 }
6274
6275 /* Given POSTDOMINATORS, compute the immediate postdominators into
6276    IDOM.  If a block is only dominated by itself, its entry remains as
6277    INVALID_BLOCK.  */
6278
6279 void
6280 compute_immediate_postdominators (idom, postdominators)
6281      int *idom;
6282      sbitmap *postdominators;
6283 {
6284   compute_immediate_dominators (idom, postdominators);
6285 }
6286
6287 /* Recompute register set/reference counts immediately prior to register
6288    allocation.
6289
6290    This avoids problems with set/reference counts changing to/from values
6291    which have special meanings to the register allocators.
6292
6293    Additionally, the reference counts are the primary component used by the
6294    register allocators to prioritize pseudos for allocation to hard regs.
6295    More accurate reference counts generally lead to better register allocation.
6296
6297    F is the first insn to be scanned.
6298
6299    LOOP_STEP denotes how much loop_depth should be incremented per
6300    loop nesting level in order to increase the ref count more for
6301    references in a loop.
6302
6303    It might be worthwhile to update REG_LIVE_LENGTH, REG_BASIC_BLOCK and
6304    possibly other information which is used by the register allocators.  */
6305
6306 void
6307 recompute_reg_usage (f, loop_step)
6308      rtx f ATTRIBUTE_UNUSED;
6309      int loop_step ATTRIBUTE_UNUSED;
6310 {
6311   allocate_reg_life_data ();
6312   update_life_info (NULL, UPDATE_LIFE_LOCAL, PROP_REG_INFO);
6313 }
6314
6315 /* Optionally removes all the REG_DEAD and REG_UNUSED notes from a set of
6316    blocks.  If BLOCKS is NULL, assume the universal set.  Returns a count
6317    of the number of registers that died.  */
6318
6319 int
6320 count_or_remove_death_notes (blocks, kill)
6321     sbitmap blocks;
6322     int kill;
6323 {
6324   int i, count = 0;
6325
6326   for (i = n_basic_blocks - 1; i >= 0; --i)
6327     {
6328       basic_block bb;
6329       rtx insn;
6330
6331       if (blocks && ! TEST_BIT (blocks, i))
6332         continue;
6333
6334       bb = BASIC_BLOCK (i);
6335
6336       for (insn = bb->head; ; insn = NEXT_INSN (insn))
6337         {
6338           if (INSN_P (insn))
6339             {
6340               rtx *pprev = &REG_NOTES (insn);
6341               rtx link = *pprev;
6342
6343               while (link)
6344                 {
6345                   switch (REG_NOTE_KIND (link))
6346                     {
6347                     case REG_DEAD:
6348                       if (GET_CODE (XEXP (link, 0)) == REG)
6349                         {
6350                           rtx reg = XEXP (link, 0);
6351                           int n;
6352
6353                           if (REGNO (reg) >= FIRST_PSEUDO_REGISTER)
6354                             n = 1;
6355                           else
6356                             n = HARD_REGNO_NREGS (REGNO (reg), GET_MODE (reg));
6357                           count += n;
6358                         }
6359                       /* FALLTHRU */
6360
6361                     case REG_UNUSED:
6362                       if (kill)
6363                         {
6364                           rtx next = XEXP (link, 1);
6365                           free_EXPR_LIST_node (link);
6366                           *pprev = link = next;
6367                           break;
6368                         }
6369                       /* FALLTHRU */
6370
6371                     default:
6372                       pprev = &XEXP (link, 1);
6373                       link = *pprev;
6374                       break;
6375                     }
6376                 }
6377             }
6378
6379           if (insn == bb->end)
6380             break;
6381         }
6382     }
6383
6384   return count;
6385 }
6386
6387 /* Record INSN's block as BB.  */
6388
6389 void
6390 set_block_for_insn (insn, bb)
6391      rtx insn;
6392      basic_block bb;
6393 {
6394   size_t uid = INSN_UID (insn);
6395   if (uid >= basic_block_for_insn->num_elements)
6396     {
6397       int new_size;
6398       
6399       /* Add one-eighth the size so we don't keep calling xrealloc.  */
6400       new_size = uid + (uid + 7) / 8;
6401
6402       VARRAY_GROW (basic_block_for_insn, new_size);
6403     }
6404   VARRAY_BB (basic_block_for_insn, uid) = bb;
6405 }
6406
6407 /* Record INSN's block number as BB.  */
6408 /* ??? This has got to go.  */
6409
6410 void
6411 set_block_num (insn, bb)
6412      rtx insn;
6413      int bb;
6414 {
6415   set_block_for_insn (insn, BASIC_BLOCK (bb));
6416 }
6417 \f
6418 /* Verify the CFG consistency.  This function check some CFG invariants and
6419    aborts when something is wrong.  Hope that this function will help to
6420    convert many optimization passes to preserve CFG consistent.
6421
6422    Currently it does following checks: 
6423
6424    - test head/end pointers
6425    - overlapping of basic blocks
6426    - edge list corectness
6427    - headers of basic blocks (the NOTE_INSN_BASIC_BLOCK note)
6428    - tails of basic blocks (ensure that boundary is necesary)
6429    - scans body of the basic block for JUMP_INSN, CODE_LABEL
6430      and NOTE_INSN_BASIC_BLOCK
6431    - check that all insns are in the basic blocks 
6432    (except the switch handling code, barriers and notes)
6433    - check that all returns are followed by barriers
6434
6435    In future it can be extended check a lot of other stuff as well
6436    (reachability of basic blocks, life information, etc. etc.).  */
6437
6438 void
6439 verify_flow_info ()
6440 {
6441   const int max_uid = get_max_uid ();
6442   const rtx rtx_first = get_insns ();
6443   rtx last_head = get_last_insn ();
6444   basic_block *bb_info;
6445   rtx x;
6446   int i, last_bb_num_seen, num_bb_notes, err = 0;
6447
6448   bb_info = (basic_block *) xcalloc (max_uid, sizeof (basic_block));
6449
6450   for (i = n_basic_blocks - 1; i >= 0; i--)
6451     {
6452       basic_block bb = BASIC_BLOCK (i);
6453       rtx head = bb->head;
6454       rtx end = bb->end;
6455
6456       /* Verify the end of the basic block is in the INSN chain.  */
6457       for (x = last_head; x != NULL_RTX; x = PREV_INSN (x))
6458         if (x == end)
6459           break;
6460       if (!x)
6461         {
6462           error ("End insn %d for block %d not found in the insn stream.",
6463                  INSN_UID (end), bb->index);
6464           err = 1;
6465         }
6466
6467       /* Work backwards from the end to the head of the basic block
6468          to verify the head is in the RTL chain.  */
6469       for ( ; x != NULL_RTX; x = PREV_INSN (x))
6470         {
6471           /* While walking over the insn chain, verify insns appear
6472              in only one basic block and initialize the BB_INFO array
6473              used by other passes.  */
6474           if (bb_info[INSN_UID (x)] != NULL)
6475             {
6476               error ("Insn %d is in multiple basic blocks (%d and %d)",
6477                      INSN_UID (x), bb->index, bb_info[INSN_UID (x)]->index);
6478               err = 1;
6479             }
6480           bb_info[INSN_UID (x)] = bb;
6481
6482           if (x == head)
6483             break;
6484         }
6485       if (!x)
6486         {
6487           error ("Head insn %d for block %d not found in the insn stream.",
6488                  INSN_UID (head), bb->index);
6489           err = 1;
6490         }
6491
6492       last_head = x;
6493     }
6494
6495   /* Now check the basic blocks (boundaries etc.) */
6496   for (i = n_basic_blocks - 1; i >= 0; i--)
6497     {
6498       basic_block bb = BASIC_BLOCK (i);
6499       /* Check corectness of edge lists */
6500       edge e;
6501
6502       e = bb->succ;
6503       while (e)
6504         {
6505           if (e->src != bb)
6506             {
6507               fprintf (stderr, "verify_flow_info: Basic block %d succ edge is corrupted\n",
6508                        bb->index);
6509               fprintf (stderr, "Predecessor: ");
6510               dump_edge_info (stderr, e, 0);
6511               fprintf (stderr, "\nSuccessor: ");
6512               dump_edge_info (stderr, e, 1);
6513               fflush (stderr);
6514               err = 1;
6515             }
6516           if (e->dest != EXIT_BLOCK_PTR)
6517             {
6518               edge e2 = e->dest->pred;
6519               while (e2 && e2 != e)
6520                 e2 = e2->pred_next;
6521               if (!e2)
6522                 {
6523                   error ("Basic block %i edge lists are corrupted", bb->index);
6524                   err = 1;
6525                 }
6526             }
6527           e = e->succ_next;
6528         }
6529
6530       e = bb->pred;
6531       while (e)
6532         {
6533           if (e->dest != bb)
6534             {
6535               error ("Basic block %d pred edge is corrupted", bb->index);
6536               fputs ("Predecessor: ", stderr);
6537               dump_edge_info (stderr, e, 0);
6538               fputs ("\nSuccessor: ", stderr);
6539               dump_edge_info (stderr, e, 1);
6540               fputc ('\n', stderr);
6541               err = 1;
6542             }
6543           if (e->src != ENTRY_BLOCK_PTR)
6544             {
6545               edge e2 = e->src->succ;
6546               while (e2 && e2 != e)
6547                 e2 = e2->succ_next;
6548               if (!e2)
6549                 {
6550                   error ("Basic block %i edge lists are corrupted", bb->index);
6551                   err = 1;
6552                 }
6553             }
6554           e = e->pred_next;
6555         }
6556
6557       /* OK pointers are correct.  Now check the header of basic
6558          block.  It ought to contain optional CODE_LABEL followed
6559          by NOTE_BASIC_BLOCK.  */
6560       x = bb->head;
6561       if (GET_CODE (x) == CODE_LABEL)
6562         {
6563           if (bb->end == x)
6564             {
6565               error ("NOTE_INSN_BASIC_BLOCK is missing for block %d",
6566                      bb->index);
6567               err = 1;
6568             }
6569           x = NEXT_INSN (x);
6570         }
6571       if (!NOTE_INSN_BASIC_BLOCK_P (x) || NOTE_BASIC_BLOCK (x) != bb)
6572         {
6573           error ("NOTE_INSN_BASIC_BLOCK is missing for block %d\n",
6574                  bb->index);
6575           err = 1;
6576         }
6577
6578       if (bb->end == x)
6579         {
6580           /* Do checks for empty blocks here */
6581         }
6582       else
6583         {
6584           x = NEXT_INSN (x);
6585           while (x)
6586             {
6587               if (NOTE_INSN_BASIC_BLOCK_P (x))
6588                 {
6589                   error ("NOTE_INSN_BASIC_BLOCK %d in the middle of basic block %d",
6590                          INSN_UID (x), bb->index);
6591                   err = 1;
6592                 }
6593
6594               if (x == bb->end)
6595                 break;
6596
6597               if (GET_CODE (x) == JUMP_INSN
6598                   || GET_CODE (x) == CODE_LABEL
6599                   || GET_CODE (x) == BARRIER)
6600                 {
6601                   error ("In basic block %d:", bb->index);
6602                   fatal_insn ("Flow control insn inside a basic block", x);
6603                 }
6604
6605               x = NEXT_INSN (x);
6606             }
6607         }
6608     }
6609
6610   last_bb_num_seen = -1;
6611   num_bb_notes = 0;
6612   x = rtx_first;
6613   while (x)
6614     {
6615       if (NOTE_INSN_BASIC_BLOCK_P (x))
6616         {
6617           basic_block bb = NOTE_BASIC_BLOCK (x);
6618           num_bb_notes++;
6619           if (bb->index != last_bb_num_seen + 1)
6620             fatal ("Basic blocks not numbered consecutively");
6621           last_bb_num_seen = bb->index;
6622         }
6623
6624       if (!bb_info[INSN_UID (x)])
6625         {
6626           switch (GET_CODE (x))
6627             {
6628             case BARRIER:
6629             case NOTE:
6630               break;
6631
6632             case CODE_LABEL:
6633               /* An addr_vec is placed outside any block block.  */
6634               if (NEXT_INSN (x)
6635                   && GET_CODE (NEXT_INSN (x)) == JUMP_INSN
6636                   && (GET_CODE (PATTERN (NEXT_INSN (x))) == ADDR_DIFF_VEC
6637                       || GET_CODE (PATTERN (NEXT_INSN (x))) == ADDR_VEC))
6638                 {
6639                   x = NEXT_INSN (x);
6640                 }
6641
6642               /* But in any case, non-deletable labels can appear anywhere.  */
6643               break;
6644
6645             default:
6646               fatal_insn ("Insn outside basic block", x);
6647             }
6648         }
6649
6650       if (INSN_P (x)
6651           && GET_CODE (x) == JUMP_INSN
6652           && returnjump_p (x) && ! condjump_p (x)
6653           && ! (NEXT_INSN (x) && GET_CODE (NEXT_INSN (x)) == BARRIER))
6654             fatal_insn ("Return not followed by barrier", x);
6655
6656       x = NEXT_INSN (x);
6657     }
6658
6659   if (num_bb_notes != n_basic_blocks)
6660     fatal ("number of bb notes in insn chain (%d) != n_basic_blocks (%d)",
6661            num_bb_notes, n_basic_blocks);
6662
6663   if (err)
6664     abort ();
6665
6666   /* Clean up.  */
6667   free (bb_info);
6668 }
6669 \f
6670 /* Functions to access an edge list with a vector representation.
6671    Enough data is kept such that given an index number, the 
6672    pred and succ that edge represents can be determined, or
6673    given a pred and a succ, its index number can be returned.
6674    This allows algorithms which consume a lot of memory to 
6675    represent the normally full matrix of edge (pred,succ) with a
6676    single indexed vector,  edge (EDGE_INDEX (pred, succ)), with no
6677    wasted space in the client code due to sparse flow graphs.  */
6678
6679 /* This functions initializes the edge list. Basically the entire 
6680    flowgraph is processed, and all edges are assigned a number,
6681    and the data structure is filled in.  */
6682 struct edge_list *
6683 create_edge_list ()
6684 {
6685   struct edge_list *elist;
6686   edge e;
6687   int num_edges;
6688   int x;
6689   int block_count;
6690
6691   block_count = n_basic_blocks + 2;   /* Include the entry and exit blocks.  */
6692
6693   num_edges = 0;
6694
6695   /* Determine the number of edges in the flow graph by counting successor
6696      edges on each basic block.  */
6697   for (x = 0; x < n_basic_blocks; x++)
6698     {
6699       basic_block bb = BASIC_BLOCK (x);
6700
6701       for (e = bb->succ; e; e = e->succ_next)
6702         num_edges++;
6703     }
6704   /* Don't forget successors of the entry block.  */
6705   for (e = ENTRY_BLOCK_PTR->succ; e; e = e->succ_next)
6706     num_edges++;
6707
6708   elist = (struct edge_list *) xmalloc (sizeof (struct edge_list));
6709   elist->num_blocks = block_count;
6710   elist->num_edges = num_edges;
6711   elist->index_to_edge = (edge *) xmalloc (sizeof (edge) * num_edges);
6712
6713   num_edges = 0;
6714
6715   /* Follow successors of the entry block, and register these edges.  */
6716   for (e = ENTRY_BLOCK_PTR->succ; e; e = e->succ_next)
6717     {
6718       elist->index_to_edge[num_edges] = e;
6719       num_edges++;
6720     }
6721   
6722   for (x = 0; x < n_basic_blocks; x++)
6723     {
6724       basic_block bb = BASIC_BLOCK (x);
6725
6726       /* Follow all successors of blocks, and register these edges.  */
6727       for (e = bb->succ; e; e = e->succ_next)
6728         {
6729           elist->index_to_edge[num_edges] = e;
6730           num_edges++;
6731         }
6732     }
6733   return elist;
6734 }
6735
6736 /* This function free's memory associated with an edge list.  */
6737 void
6738 free_edge_list (elist)
6739      struct edge_list *elist;
6740 {
6741   if (elist)
6742     {
6743       free (elist->index_to_edge);
6744       free (elist);
6745     }
6746 }
6747
6748 /* This function provides debug output showing an edge list.  */
6749 void 
6750 print_edge_list (f, elist)
6751      FILE *f;
6752      struct edge_list *elist;
6753 {
6754   int x;
6755   fprintf(f, "Compressed edge list, %d BBs + entry & exit, and %d edges\n",
6756           elist->num_blocks - 2, elist->num_edges);
6757
6758   for (x = 0; x < elist->num_edges; x++)
6759     {
6760       fprintf (f, " %-4d - edge(", x);
6761       if (INDEX_EDGE_PRED_BB (elist, x) == ENTRY_BLOCK_PTR)
6762         fprintf (f,"entry,");
6763       else
6764         fprintf (f,"%d,", INDEX_EDGE_PRED_BB (elist, x)->index);
6765
6766       if (INDEX_EDGE_SUCC_BB (elist, x) == EXIT_BLOCK_PTR)
6767         fprintf (f,"exit)\n");
6768       else
6769         fprintf (f,"%d)\n", INDEX_EDGE_SUCC_BB (elist, x)->index);
6770     }
6771 }
6772
6773 /* This function provides an internal consistency check of an edge list,
6774    verifying that all edges are present, and that there are no 
6775    extra edges.  */
6776 void
6777 verify_edge_list (f, elist)
6778      FILE *f;
6779      struct edge_list *elist;
6780 {
6781   int x, pred, succ, index;
6782   edge e;
6783
6784   for (x = 0; x < n_basic_blocks; x++)
6785     {
6786       basic_block bb = BASIC_BLOCK (x);
6787
6788       for (e = bb->succ; e; e = e->succ_next)
6789         {
6790           pred = e->src->index;
6791           succ = e->dest->index;
6792           index = EDGE_INDEX (elist, e->src, e->dest);
6793           if (index == EDGE_INDEX_NO_EDGE)
6794             {
6795               fprintf (f, "*p* No index for edge from %d to %d\n",pred, succ);
6796               continue;
6797             }
6798           if (INDEX_EDGE_PRED_BB (elist, index)->index != pred)
6799             fprintf (f, "*p* Pred for index %d should be %d not %d\n",
6800                      index, pred, INDEX_EDGE_PRED_BB (elist, index)->index);
6801           if (INDEX_EDGE_SUCC_BB (elist, index)->index != succ)
6802             fprintf (f, "*p* Succ for index %d should be %d not %d\n",
6803                      index, succ, INDEX_EDGE_SUCC_BB (elist, index)->index);
6804         }
6805     }
6806   for (e = ENTRY_BLOCK_PTR->succ; e; e = e->succ_next)
6807     {
6808       pred = e->src->index;
6809       succ = e->dest->index;
6810       index = EDGE_INDEX (elist, e->src, e->dest);
6811       if (index == EDGE_INDEX_NO_EDGE)
6812         {
6813           fprintf (f, "*p* No index for edge from %d to %d\n",pred, succ);
6814           continue;
6815         }
6816       if (INDEX_EDGE_PRED_BB (elist, index)->index != pred)
6817         fprintf (f, "*p* Pred for index %d should be %d not %d\n",
6818                  index, pred, INDEX_EDGE_PRED_BB (elist, index)->index);
6819       if (INDEX_EDGE_SUCC_BB (elist, index)->index != succ)
6820         fprintf (f, "*p* Succ for index %d should be %d not %d\n",
6821                  index, succ, INDEX_EDGE_SUCC_BB (elist, index)->index);
6822     }
6823   /* We've verified that all the edges are in the list, no lets make sure
6824      there are no spurious edges in the list.  */
6825   
6826   for (pred = 0 ; pred < n_basic_blocks; pred++)
6827     for (succ = 0 ; succ < n_basic_blocks; succ++)
6828       {
6829         basic_block p = BASIC_BLOCK (pred);
6830         basic_block s = BASIC_BLOCK (succ);
6831
6832         int found_edge = 0;
6833
6834         for (e = p->succ; e; e = e->succ_next)
6835           if (e->dest == s)
6836             {
6837               found_edge = 1;
6838               break;
6839             }
6840         for (e = s->pred; e; e = e->pred_next)
6841           if (e->src == p)
6842             {
6843               found_edge = 1;
6844               break;
6845             }
6846         if (EDGE_INDEX (elist, BASIC_BLOCK (pred), BASIC_BLOCK (succ)) 
6847             == EDGE_INDEX_NO_EDGE && found_edge != 0)
6848           fprintf (f, "*** Edge (%d, %d) appears to not have an index\n",
6849                    pred, succ);
6850         if (EDGE_INDEX (elist, BASIC_BLOCK (pred), BASIC_BLOCK (succ)) 
6851             != EDGE_INDEX_NO_EDGE && found_edge == 0)
6852           fprintf (f, "*** Edge (%d, %d) has index %d, but there is no edge\n",
6853                    pred, succ, EDGE_INDEX (elist, BASIC_BLOCK (pred), 
6854                                            BASIC_BLOCK (succ)));
6855       }
6856     for (succ = 0 ; succ < n_basic_blocks; succ++)
6857       {
6858         basic_block p = ENTRY_BLOCK_PTR;
6859         basic_block s = BASIC_BLOCK (succ);
6860
6861         int found_edge = 0;
6862
6863         for (e = p->succ; e; e = e->succ_next)
6864           if (e->dest == s)
6865             {
6866               found_edge = 1;
6867               break;
6868             }
6869         for (e = s->pred; e; e = e->pred_next)
6870           if (e->src == p)
6871             {
6872               found_edge = 1;
6873               break;
6874             }
6875         if (EDGE_INDEX (elist, ENTRY_BLOCK_PTR, BASIC_BLOCK (succ)) 
6876             == EDGE_INDEX_NO_EDGE && found_edge != 0)
6877           fprintf (f, "*** Edge (entry, %d) appears to not have an index\n",
6878                    succ);
6879         if (EDGE_INDEX (elist, ENTRY_BLOCK_PTR, BASIC_BLOCK (succ)) 
6880             != EDGE_INDEX_NO_EDGE && found_edge == 0)
6881           fprintf (f, "*** Edge (entry, %d) has index %d, but no edge exists\n",
6882                    succ, EDGE_INDEX (elist, ENTRY_BLOCK_PTR, 
6883                                      BASIC_BLOCK (succ)));
6884       }
6885     for (pred = 0 ; pred < n_basic_blocks; pred++)
6886       {
6887         basic_block p = BASIC_BLOCK (pred);
6888         basic_block s = EXIT_BLOCK_PTR;
6889
6890         int found_edge = 0;
6891
6892         for (e = p->succ; e; e = e->succ_next)
6893           if (e->dest == s)
6894             {
6895               found_edge = 1;
6896               break;
6897             }
6898         for (e = s->pred; e; e = e->pred_next)
6899           if (e->src == p)
6900             {
6901               found_edge = 1;
6902               break;
6903             }
6904         if (EDGE_INDEX (elist, BASIC_BLOCK (pred), EXIT_BLOCK_PTR) 
6905             == EDGE_INDEX_NO_EDGE && found_edge != 0)
6906           fprintf (f, "*** Edge (%d, exit) appears to not have an index\n",
6907                    pred);
6908         if (EDGE_INDEX (elist, BASIC_BLOCK (pred), EXIT_BLOCK_PTR) 
6909             != EDGE_INDEX_NO_EDGE && found_edge == 0)
6910           fprintf (f, "*** Edge (%d, exit) has index %d, but no edge exists\n",
6911                    pred, EDGE_INDEX (elist, BASIC_BLOCK (pred), 
6912                                      EXIT_BLOCK_PTR));
6913       }
6914 }
6915
6916 /* This routine will determine what, if any, edge there is between
6917    a specified predecessor and successor.  */
6918 int
6919 find_edge_index (edge_list, pred, succ)
6920      struct edge_list *edge_list;
6921      basic_block pred, succ;
6922 {
6923   int x;
6924   for (x = 0; x < NUM_EDGES (edge_list); x++)
6925     {
6926       if (INDEX_EDGE_PRED_BB (edge_list, x) == pred
6927           && INDEX_EDGE_SUCC_BB (edge_list, x) == succ)
6928         return x;
6929     }
6930   return (EDGE_INDEX_NO_EDGE);
6931 }
6932
6933 /* This function will remove an edge from the flow graph.  */
6934 void
6935 remove_edge (e)
6936      edge e;
6937 {
6938   edge last_pred = NULL;
6939   edge last_succ = NULL;
6940   edge tmp;
6941   basic_block src, dest;
6942   src = e->src;
6943   dest = e->dest;
6944   for (tmp = src->succ; tmp && tmp != e; tmp = tmp->succ_next)
6945     last_succ = tmp;
6946
6947   if (!tmp)
6948     abort ();
6949   if (last_succ)
6950     last_succ->succ_next = e->succ_next;
6951   else
6952     src->succ = e->succ_next;
6953
6954   for (tmp = dest->pred; tmp && tmp != e; tmp = tmp->pred_next)
6955     last_pred = tmp;
6956
6957   if (!tmp)
6958     abort ();
6959   if (last_pred)
6960     last_pred->pred_next = e->pred_next;
6961   else
6962     dest->pred = e->pred_next;
6963
6964   n_edges--;
6965   free (e);
6966 }
6967
6968 /* This routine will remove any fake successor edges for a basic block.
6969    When the edge is removed, it is also removed from whatever predecessor
6970    list it is in.  */
6971 static void
6972 remove_fake_successors (bb)
6973      basic_block bb;
6974 {
6975   edge e;
6976   for (e = bb->succ; e ; )
6977     {
6978       edge tmp = e;
6979       e = e->succ_next;
6980       if ((tmp->flags & EDGE_FAKE) == EDGE_FAKE)
6981         remove_edge (tmp);
6982     }
6983 }
6984
6985 /* This routine will remove all fake edges from the flow graph.  If
6986    we remove all fake successors, it will automatically remove all
6987    fake predecessors.  */
6988 void
6989 remove_fake_edges ()
6990 {
6991   int x;
6992
6993   for (x = 0; x < n_basic_blocks; x++)
6994     remove_fake_successors (BASIC_BLOCK (x));
6995
6996   /* We've handled all successors except the entry block's.  */
6997   remove_fake_successors (ENTRY_BLOCK_PTR);
6998 }
6999
7000 /* This function will add a fake edge between any block which has no
7001    successors, and the exit block. Some data flow equations require these
7002    edges to exist.  */
7003 void
7004 add_noreturn_fake_exit_edges ()
7005 {
7006   int x;
7007
7008   for (x = 0; x < n_basic_blocks; x++)
7009     if (BASIC_BLOCK (x)->succ == NULL)
7010       make_edge (NULL, BASIC_BLOCK (x), EXIT_BLOCK_PTR, EDGE_FAKE);
7011 }
7012
7013 /* This function adds a fake edge between any infinite loops to the
7014    exit block.  Some optimizations require a path from each node to
7015    the exit node.
7016
7017    See also Morgan, Figure 3.10, pp. 82-83.
7018
7019    The current implementation is ugly, not attempting to minimize the
7020    number of inserted fake edges.  To reduce the number of fake edges
7021    to insert, add fake edges from _innermost_ loops containing only
7022    nodes not reachable from the exit block. */
7023 void
7024 connect_infinite_loops_to_exit ()
7025 {
7026   basic_block unvisited_block;
7027
7028   /* Perform depth-first search in the reverse graph to find nodes
7029      reachable from the exit block. */
7030   struct depth_first_search_dsS dfs_ds;
7031
7032   flow_dfs_compute_reverse_init (&dfs_ds);
7033   flow_dfs_compute_reverse_add_bb (&dfs_ds, EXIT_BLOCK_PTR);
7034   
7035   /* Repeatedly add fake edges, updating the unreachable nodes. */
7036   while (1)
7037     {
7038       unvisited_block = flow_dfs_compute_reverse_execute (&dfs_ds);
7039       if (!unvisited_block)
7040         break;
7041       make_edge (NULL, unvisited_block, EXIT_BLOCK_PTR, EDGE_FAKE);
7042       flow_dfs_compute_reverse_add_bb (&dfs_ds, unvisited_block);
7043     }
7044
7045   flow_dfs_compute_reverse_finish (&dfs_ds);
7046
7047   return;
7048 }
7049
7050 /* Redirect an edge's successor from one block to another.  */
7051 void
7052 redirect_edge_succ (e, new_succ)
7053      edge e;
7054      basic_block new_succ;
7055 {
7056   edge *pe;
7057
7058   /* Disconnect the edge from the old successor block.  */
7059   for (pe = &e->dest->pred; *pe != e ; pe = &(*pe)->pred_next)
7060     continue;
7061   *pe = (*pe)->pred_next;
7062
7063   /* Reconnect the edge to the new successor block.  */
7064   e->pred_next = new_succ->pred;
7065   new_succ->pred = e;
7066   e->dest = new_succ;
7067 }
7068
7069 /* Redirect an edge's predecessor from one block to another.  */
7070 void
7071 redirect_edge_pred (e, new_pred)
7072      edge e;
7073      basic_block new_pred;
7074 {
7075   edge *pe;
7076
7077   /* Disconnect the edge from the old predecessor block.  */
7078   for (pe = &e->src->succ; *pe != e ; pe = &(*pe)->succ_next)
7079     continue;
7080   *pe = (*pe)->succ_next;
7081
7082   /* Reconnect the edge to the new predecessor block.  */
7083   e->succ_next = new_pred->succ;
7084   new_pred->succ = e;
7085   e->src = new_pred;
7086 }
7087 \f
7088 /* Dump the list of basic blocks in the bitmap NODES.  */
7089 static void 
7090 flow_nodes_print (str, nodes, file)
7091      const char *str;
7092      const sbitmap nodes;
7093      FILE *file;
7094 {
7095   int node;
7096
7097   fprintf (file, "%s { ", str);
7098   EXECUTE_IF_SET_IN_SBITMAP (nodes, 0, node, {fprintf (file, "%d ", node);});
7099   fputs ("}\n", file);
7100 }
7101
7102
7103 /* Dump the list of exiting edges in the array EDGES.  */
7104 static void 
7105 flow_exits_print (str, edges, num_edges, file)
7106      const char *str;
7107      const edge *edges;
7108      int num_edges;
7109      FILE *file;
7110 {
7111   int i;
7112
7113   fprintf (file, "%s { ", str);
7114   for (i = 0; i < num_edges; i++)
7115     fprintf (file, "%d->%d ", edges[i]->src->index, edges[i]->dest->index);
7116   fputs ("}\n", file);
7117 }
7118
7119
7120 /* Dump loop related CFG information.  */
7121 static void
7122 flow_loops_cfg_dump (loops, file)
7123      const struct loops *loops;
7124      FILE *file;
7125 {
7126   int i;
7127
7128   if (! loops->num || ! file || ! loops->cfg.dom)
7129     return;
7130
7131   for (i = 0; i < n_basic_blocks; i++)
7132     {
7133       edge succ;
7134
7135       fprintf (file, ";; %d succs { ", i);
7136       for (succ = BASIC_BLOCK (i)->succ; succ; succ = succ->succ_next)
7137         fprintf (file, "%d ", succ->dest->index);
7138       flow_nodes_print ("} dom", loops->cfg.dom[i], file);      
7139     }
7140
7141
7142   /* Dump the DFS node order.  */
7143   if (loops->cfg.dfs_order)
7144     {
7145       fputs (";; DFS order: ", file);
7146       for (i = 0; i < n_basic_blocks; i++)
7147         fprintf (file, "%d ", loops->cfg.dfs_order[i]);
7148       fputs ("\n", file);
7149     }
7150   /* Dump the reverse completion node order.  */
7151   if (loops->cfg.rc_order)
7152     {
7153       fputs (";; RC order: ", file);
7154       for (i = 0; i < n_basic_blocks; i++)
7155         fprintf (file, "%d ", loops->cfg.rc_order[i]);
7156       fputs ("\n", file);
7157     }
7158 }
7159
7160
7161 /* Return non-zero if the nodes of LOOP are a subset of OUTER.  */
7162 static int
7163 flow_loop_nested_p (outer, loop)
7164      struct loop *outer;
7165      struct loop *loop;
7166 {
7167   return sbitmap_a_subset_b_p (loop->nodes, outer->nodes);
7168 }
7169
7170
7171 /* Dump the loop information specified by LOOPS to the stream FILE.  */
7172 void 
7173 flow_loops_dump (loops, file, verbose)
7174      const struct loops *loops;
7175      FILE *file;
7176      int verbose;
7177 {
7178   int i;
7179   int num_loops;
7180
7181   num_loops = loops->num;
7182   if (! num_loops || ! file)
7183     return;
7184
7185   fprintf (file, ";; %d loops found, %d levels\n", 
7186            num_loops, loops->levels);
7187
7188   for (i = 0; i < num_loops; i++)
7189     {
7190       struct loop *loop = &loops->array[i];
7191
7192       fprintf (file, ";; loop %d (%d to %d):\n;;   header %d, latch %d, pre-header %d, depth %d, level %d, outer %ld\n",
7193                i, INSN_UID (loop->header->head), INSN_UID (loop->latch->end),
7194                loop->header->index, loop->latch->index,
7195                loop->pre_header ? loop->pre_header->index : -1, 
7196                loop->depth, loop->level,
7197                (long) (loop->outer ? (loop->outer - loops->array) : -1));
7198       fprintf (file, ";;   %d", loop->num_nodes);
7199       flow_nodes_print (" nodes", loop->nodes, file);
7200       fprintf (file, ";;   %d", loop->num_exits);
7201       flow_exits_print (" exits", loop->exits, loop->num_exits, file);
7202
7203       if (loop->shared)
7204         {
7205           int j;
7206
7207           for (j = 0; j < i; j++)
7208             {
7209               struct loop *oloop = &loops->array[j];
7210
7211               if (loop->header == oloop->header)
7212                 {
7213                   int disjoint;
7214                   int smaller;
7215
7216                   smaller = loop->num_nodes < oloop->num_nodes;
7217
7218                   /* If the union of LOOP and OLOOP is different than
7219                      the larger of LOOP and OLOOP then LOOP and OLOOP
7220                      must be disjoint.  */
7221                   disjoint = ! flow_loop_nested_p (smaller ? loop : oloop,
7222                                                    smaller ? oloop : loop);
7223                   fprintf (file, 
7224                            ";; loop header %d shared by loops %d, %d %s\n",
7225                            loop->header->index, i, j,
7226                            disjoint ? "disjoint" : "nested");
7227                 }
7228             }
7229         }
7230
7231       if (verbose)
7232         {
7233           /* Print diagnostics to compare our concept of a loop with
7234              what the loop notes say.  */
7235           if (GET_CODE (PREV_INSN (loop->first->head)) != NOTE
7236               || NOTE_LINE_NUMBER (PREV_INSN (loop->first->head))
7237               != NOTE_INSN_LOOP_BEG)
7238             fprintf (file, ";; No NOTE_INSN_LOOP_BEG at %d\n", 
7239                      INSN_UID (PREV_INSN (loop->first->head)));
7240           if (GET_CODE (NEXT_INSN (loop->last->end)) != NOTE
7241               || NOTE_LINE_NUMBER (NEXT_INSN (loop->last->end))
7242               != NOTE_INSN_LOOP_END)
7243             fprintf (file, ";; No NOTE_INSN_LOOP_END at %d\n",
7244                      INSN_UID (NEXT_INSN (loop->last->end)));
7245         }
7246     }
7247
7248   if (verbose)
7249     flow_loops_cfg_dump (loops, file);
7250 }
7251
7252
7253 /* Free all the memory allocated for LOOPS.  */
7254 void 
7255 flow_loops_free (loops)
7256        struct loops *loops;
7257 {
7258   if (loops->array)
7259     {
7260       int i;
7261
7262       if (! loops->num)
7263         abort ();
7264
7265       /* Free the loop descriptors.  */
7266       for (i = 0; i < loops->num; i++)
7267         {
7268           struct loop *loop = &loops->array[i];
7269           
7270           if (loop->nodes)
7271             sbitmap_free (loop->nodes);
7272           if (loop->exits)
7273             free (loop->exits);
7274         }
7275       free (loops->array);
7276       loops->array = NULL;
7277       
7278       if (loops->cfg.dom)
7279         sbitmap_vector_free (loops->cfg.dom);
7280       if (loops->cfg.dfs_order)
7281         free (loops->cfg.dfs_order);
7282
7283       sbitmap_free (loops->shared_headers);
7284     }
7285 }
7286
7287
7288 /* Find the exits from the loop using the bitmap of loop nodes NODES
7289    and store in EXITS array.  Return the number of exits from the
7290    loop.  */
7291 static int
7292 flow_loop_exits_find (nodes, exits)
7293      const sbitmap nodes;
7294      edge **exits;
7295 {
7296   edge e;
7297   int node;
7298   int num_exits;
7299
7300   *exits = NULL;
7301
7302   /* Check all nodes within the loop to see if there are any
7303      successors not in the loop.  Note that a node may have multiple
7304      exiting edges.  */
7305   num_exits = 0;
7306   EXECUTE_IF_SET_IN_SBITMAP (nodes, 0, node, {
7307     for (e = BASIC_BLOCK (node)->succ; e; e = e->succ_next)
7308       {
7309         basic_block dest = e->dest;       
7310
7311         if (dest == EXIT_BLOCK_PTR || ! TEST_BIT (nodes, dest->index))
7312             num_exits++;
7313       }
7314   });
7315
7316   if (! num_exits)
7317     return 0;
7318
7319   *exits = (edge *) xmalloc (num_exits * sizeof (edge *));
7320
7321   /* Store all exiting edges into an array.  */
7322   num_exits = 0;
7323   EXECUTE_IF_SET_IN_SBITMAP (nodes, 0, node, {
7324     for (e = BASIC_BLOCK (node)->succ; e; e = e->succ_next)
7325       {
7326         basic_block dest = e->dest;       
7327
7328         if (dest == EXIT_BLOCK_PTR || ! TEST_BIT (nodes, dest->index))
7329           (*exits)[num_exits++] = e;
7330       }
7331   });
7332
7333   return num_exits;
7334 }
7335
7336
7337 /* Find the nodes contained within the loop with header HEADER and
7338    latch LATCH and store in NODES.  Return the number of nodes within
7339    the loop.  */
7340 static int 
7341 flow_loop_nodes_find (header, latch, nodes)
7342      basic_block header;
7343      basic_block latch;
7344      sbitmap nodes;
7345 {
7346   basic_block *stack;
7347   int sp;
7348   int num_nodes = 0;
7349
7350   stack = (basic_block *) xmalloc (n_basic_blocks * sizeof (basic_block));
7351   sp = 0;
7352
7353   /* Start with only the loop header in the set of loop nodes.  */
7354   sbitmap_zero (nodes);
7355   SET_BIT (nodes, header->index);
7356   num_nodes++;
7357   header->loop_depth++;
7358
7359   /* Push the loop latch on to the stack.  */
7360   if (! TEST_BIT (nodes, latch->index))
7361     {
7362       SET_BIT (nodes, latch->index);
7363       latch->loop_depth++;
7364       num_nodes++;
7365       stack[sp++] = latch;
7366     }
7367
7368   while (sp)
7369     {
7370       basic_block node;
7371       edge e;
7372
7373       node = stack[--sp];
7374       for (e = node->pred; e; e = e->pred_next)
7375         {
7376           basic_block ancestor = e->src;
7377           
7378           /* If each ancestor not marked as part of loop, add to set of
7379              loop nodes and push on to stack.  */
7380           if (ancestor != ENTRY_BLOCK_PTR
7381               && ! TEST_BIT (nodes, ancestor->index))
7382             {
7383               SET_BIT (nodes, ancestor->index);
7384               ancestor->loop_depth++;
7385               num_nodes++;
7386               stack[sp++] = ancestor;
7387             }
7388         }
7389     }
7390   free (stack);
7391   return num_nodes;
7392 }
7393
7394
7395 /* Compute the depth first search order and store in the array
7396   DFS_ORDER if non-zero, marking the nodes visited in VISITED.  If
7397   RC_ORDER is non-zero, return the reverse completion number for each
7398   node.  Returns the number of nodes visited.  A depth first search
7399   tries to get as far away from the starting point as quickly as
7400   possible.  */
7401 static int
7402 flow_depth_first_order_compute (dfs_order, rc_order)
7403      int *dfs_order;
7404      int *rc_order;
7405 {
7406   edge *stack;
7407   int sp;
7408   int dfsnum = 0;
7409   int rcnum = n_basic_blocks - 1;
7410   sbitmap visited;
7411
7412   /* Allocate stack for back-tracking up CFG.  */
7413   stack = (edge *) xmalloc ((n_basic_blocks + 1) * sizeof (edge));
7414   sp = 0;
7415
7416   /* Allocate bitmap to track nodes that have been visited.  */
7417   visited = sbitmap_alloc (n_basic_blocks);
7418
7419   /* None of the nodes in the CFG have been visited yet.  */
7420   sbitmap_zero (visited);
7421   
7422   /* Push the first edge on to the stack.  */
7423   stack[sp++] = ENTRY_BLOCK_PTR->succ;
7424
7425   while (sp)
7426     {
7427       edge e;
7428       basic_block src;
7429       basic_block dest;
7430
7431       /* Look at the edge on the top of the stack.  */
7432       e = stack[sp - 1];
7433       src = e->src;
7434       dest = e->dest;
7435       
7436       /* Check if the edge destination has been visited yet.  */
7437       if (dest != EXIT_BLOCK_PTR && ! TEST_BIT (visited, dest->index))
7438         {
7439           /* Mark that we have visited the destination.  */
7440           SET_BIT (visited, dest->index);
7441           
7442           if (dfs_order)
7443             dfs_order[dfsnum++] = dest->index;
7444
7445           if (dest->succ)
7446             {
7447               /* Since the DEST node has been visited for the first
7448                  time, check its successors.  */
7449               stack[sp++] = dest->succ;
7450             }
7451           else
7452             {
7453               /* There are no successors for the DEST node so assign
7454                  its reverse completion number.  */
7455               if (rc_order)
7456                 rc_order[rcnum--] = dest->index;
7457             }
7458         }
7459       else
7460         {
7461           if (! e->succ_next && src != ENTRY_BLOCK_PTR)
7462             {
7463               /* There are no more successors for the SRC node
7464                  so assign its reverse completion number.  */
7465               if (rc_order)
7466                 rc_order[rcnum--] = src->index;
7467             }
7468           
7469           if (e->succ_next)
7470             stack[sp - 1] = e->succ_next;
7471           else
7472             sp--;
7473         }
7474     }
7475
7476   free (stack);
7477   sbitmap_free (visited);
7478
7479   /* The number of nodes visited should not be greater than
7480      n_basic_blocks.  */
7481   if (dfsnum > n_basic_blocks)
7482     abort ();
7483
7484   /* There are some nodes left in the CFG that are unreachable.  */
7485   if (dfsnum < n_basic_blocks)
7486     abort ();
7487   return dfsnum;
7488 }
7489
7490
7491 /* Compute the depth first search order on the _reverse_ graph and
7492    store in the array DFS_ORDER, marking the nodes visited in VISITED.
7493    Returns the number of nodes visited.
7494
7495    The computation is split into three pieces:
7496
7497    flow_dfs_compute_reverse_init () creates the necessary data
7498    structures.
7499
7500    flow_dfs_compute_reverse_add_bb () adds a basic block to the data
7501    structures.  The block will start the search.
7502
7503    flow_dfs_compute_reverse_execute () continues (or starts) the
7504    search using the block on the top of the stack, stopping when the
7505    stack is empty.
7506
7507    flow_dfs_compute_reverse_finish () destroys the necessary data
7508    structures.
7509
7510    Thus, the user will probably call ..._init(), call ..._add_bb() to
7511    add a beginning basic block to the stack, call ..._execute(),
7512    possibly add another bb to the stack and again call ..._execute(),
7513    ..., and finally call _finish(). */
7514
7515 /* Initialize the data structures used for depth-first search on the
7516    reverse graph.  If INITIALIZE_STACK is nonzero, the exit block is
7517    added to the basic block stack.  DATA is the current depth-first
7518    search context.  If INITIALIZE_STACK is non-zero, there is an
7519    element on the stack.  */
7520
7521 static void
7522 flow_dfs_compute_reverse_init (data)
7523      depth_first_search_ds data;
7524 {
7525   /* Allocate stack for back-tracking up CFG.  */
7526   data->stack =
7527     (basic_block *) xmalloc ((n_basic_blocks - (INVALID_BLOCK+1)) 
7528                              * sizeof (basic_block));
7529   data->sp = 0;
7530
7531   /* Allocate bitmap to track nodes that have been visited.  */
7532   data->visited_blocks 
7533     = sbitmap_alloc (n_basic_blocks - (INVALID_BLOCK + 1));
7534
7535   /* None of the nodes in the CFG have been visited yet.  */
7536   sbitmap_zero (data->visited_blocks);
7537
7538   return;
7539 }
7540
7541 /* Add the specified basic block to the top of the dfs data
7542    structures.  When the search continues, it will start at the
7543    block. */
7544
7545 static void
7546 flow_dfs_compute_reverse_add_bb (data, bb)
7547      depth_first_search_ds data;
7548      basic_block bb;
7549 {
7550   data->stack[data->sp++] = bb;
7551   return;
7552 }
7553
7554 /* Continue the depth-first search through the reverse graph starting
7555    with the block at the stack's top and ending when the stack is
7556    empty.  Visited nodes are marked.  Returns an unvisited basic
7557    block, or NULL if there is none available.  */
7558 static basic_block
7559 flow_dfs_compute_reverse_execute (data)
7560      depth_first_search_ds data;
7561 {
7562   basic_block bb;
7563   edge e;
7564   int i;
7565
7566   while (data->sp > 0)
7567     {
7568       bb = data->stack[--data->sp];
7569
7570       /* Mark that we have visited this node. */
7571       if (!TEST_BIT (data->visited_blocks, bb->index - (INVALID_BLOCK+1)))
7572         {
7573           SET_BIT (data->visited_blocks, bb->index - (INVALID_BLOCK+1));
7574
7575           /* Perform depth-first search on adjacent vertices. */
7576           for (e = bb->pred; e; e = e->pred_next)
7577             flow_dfs_compute_reverse_add_bb (data, e->src);
7578         }
7579     }
7580
7581   /* Determine if there are unvisited basic blocks. */
7582   for (i = n_basic_blocks - (INVALID_BLOCK+1); --i >= 0; )
7583     if (!TEST_BIT (data->visited_blocks, i))
7584       return BASIC_BLOCK (i + (INVALID_BLOCK+1));
7585   return NULL;
7586 }
7587
7588 /* Destroy the data structures needed for depth-first search on the
7589    reverse graph. */
7590
7591 static void
7592 flow_dfs_compute_reverse_finish (data)
7593      depth_first_search_ds data;
7594 {
7595   free (data->stack);
7596   sbitmap_free (data->visited_blocks);
7597   return;
7598 }
7599
7600 /* Return the block for the pre-header of the loop with header
7601    HEADER where DOM specifies the dominator information.  Return NULL if
7602    there is no pre-header.  */
7603 static basic_block
7604 flow_loop_pre_header_find (header, dom)
7605      basic_block header;
7606      const sbitmap *dom;     
7607 {
7608   basic_block pre_header;
7609   edge e;
7610
7611   /* If block p is a predecessor of the header and is the only block
7612      that the header does not dominate, then it is the pre-header.  */
7613   pre_header = NULL;
7614   for (e = header->pred; e; e = e->pred_next)
7615     {
7616       basic_block node = e->src;
7617       
7618       if (node != ENTRY_BLOCK_PTR
7619           && ! TEST_BIT (dom[node->index], header->index))
7620         {
7621           if (pre_header == NULL)
7622             pre_header = node;
7623           else
7624             {
7625               /* There are multiple edges into the header from outside 
7626                  the loop so there is no pre-header block.  */
7627               pre_header = NULL;
7628               break;
7629             }
7630         }
7631     }
7632   return pre_header;
7633 }
7634
7635
7636 /* Add LOOP to the loop hierarchy tree where PREVLOOP was the loop
7637    previously added.  The insertion algorithm assumes that the loops
7638    are added in the order found by a depth first search of the CFG.  */
7639 static void
7640 flow_loop_tree_node_add (prevloop, loop)
7641      struct loop *prevloop;
7642      struct loop *loop;
7643 {
7644
7645   if (flow_loop_nested_p (prevloop, loop))
7646     {
7647       prevloop->inner = loop;
7648       loop->outer = prevloop;
7649       return;
7650     }
7651
7652   while (prevloop->outer)
7653     {
7654       if (flow_loop_nested_p (prevloop->outer, loop))
7655         {
7656           prevloop->next = loop;
7657           loop->outer = prevloop->outer;
7658           return;
7659         }
7660       prevloop = prevloop->outer;
7661     }
7662   
7663   prevloop->next = loop;
7664   loop->outer = NULL;
7665 }
7666
7667
7668 /* Build the loop hierarchy tree for LOOPS.  */
7669 static void
7670 flow_loops_tree_build (loops)
7671        struct loops *loops;
7672 {
7673   int i;
7674   int num_loops;
7675
7676   num_loops = loops->num;
7677   if (! num_loops)
7678     return;
7679
7680   /* Root the loop hierarchy tree with the first loop found.
7681      Since we used a depth first search this should be the 
7682      outermost loop.  */
7683   loops->tree = &loops->array[0];
7684   loops->tree->outer = loops->tree->inner = loops->tree->next = NULL;
7685
7686   /* Add the remaining loops to the tree.  */
7687   for (i = 1; i < num_loops; i++)
7688     flow_loop_tree_node_add (&loops->array[i - 1], &loops->array[i]);
7689 }
7690
7691
7692 /* Helper function to compute loop nesting depth and enclosed loop level
7693    for the natural loop specified by LOOP at the loop depth DEPTH.   
7694    Returns the loop level.  */
7695 static int
7696 flow_loop_level_compute (loop, depth)
7697      struct loop *loop;
7698      int depth;
7699 {
7700   struct loop *inner;
7701   int level = 1;
7702
7703   if (! loop)
7704     return 0;
7705
7706   /* Traverse loop tree assigning depth and computing level as the
7707      maximum level of all the inner loops of this loop.  The loop
7708      level is equivalent to the height of the loop in the loop tree
7709      and corresponds to the number of enclosed loop levels (including
7710      itself).  */
7711   for (inner = loop->inner; inner; inner = inner->next)
7712     {
7713       int ilevel;
7714
7715       ilevel = flow_loop_level_compute (inner, depth + 1) + 1;
7716
7717       if (ilevel > level)
7718         level = ilevel;
7719     }
7720   loop->level = level;
7721   loop->depth = depth;
7722   return level;
7723 }
7724
7725
7726 /* Compute the loop nesting depth and enclosed loop level for the loop
7727    hierarchy tree specfied by LOOPS.  Return the maximum enclosed loop
7728    level.  */
7729
7730 static int
7731 flow_loops_level_compute (loops)
7732      struct loops *loops;
7733 {
7734   struct loop *loop;
7735   int level;
7736   int levels = 0;
7737
7738   /* Traverse all the outer level loops.  */
7739   for (loop = loops->tree; loop; loop = loop->next)
7740     {
7741       level = flow_loop_level_compute (loop, 1);
7742       if (level > levels)
7743         levels = level;
7744     }
7745   return levels;
7746 }
7747
7748
7749 /* Find all the natural loops in the function and save in LOOPS structure
7750    and recalculate loop_depth information in basic block structures.
7751    Return the number of natural loops found.  */
7752
7753 int 
7754 flow_loops_find (loops)
7755        struct loops *loops;
7756 {
7757   int i;
7758   int b;
7759   int num_loops;
7760   edge e;
7761   sbitmap headers;
7762   sbitmap *dom;
7763   int *dfs_order;
7764   int *rc_order;
7765   
7766   loops->num = 0;
7767   loops->array = NULL;
7768   loops->tree = NULL;
7769   dfs_order = NULL;
7770   rc_order = NULL;
7771
7772   /* Taking care of this degenerate case makes the rest of
7773      this code simpler.  */
7774   if (n_basic_blocks == 0)
7775     return 0;
7776
7777   /* Compute the dominators.  */
7778   dom = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks);
7779   compute_flow_dominators (dom, NULL);
7780
7781   /* Count the number of loop edges (back edges).  This should be the
7782      same as the number of natural loops.  Also clear the loop_depth
7783      and as we work from inner->outer in a loop nest we call
7784      find_loop_nodes_find which will increment loop_depth for nodes
7785      within the current loop, which happens to enclose inner loops.  */
7786
7787   num_loops = 0;
7788   for (b = 0; b < n_basic_blocks; b++)
7789     {
7790       BASIC_BLOCK (b)->loop_depth = 0;
7791       for (e = BASIC_BLOCK (b)->pred; e; e = e->pred_next)
7792         {
7793           basic_block latch = e->src;
7794           
7795           /* Look for back edges where a predecessor is dominated
7796              by this block.  A natural loop has a single entry
7797              node (header) that dominates all the nodes in the
7798              loop.  It also has single back edge to the header
7799              from a latch node.  Note that multiple natural loops
7800              may share the same header.  */
7801           if (latch != ENTRY_BLOCK_PTR && TEST_BIT (dom[latch->index], b))
7802             num_loops++;
7803         }
7804     }
7805   
7806   if (num_loops)
7807     {
7808       /* Compute depth first search order of the CFG so that outer
7809          natural loops will be found before inner natural loops.  */
7810       dfs_order = (int *) xmalloc (n_basic_blocks * sizeof (int));
7811       rc_order = (int *) xmalloc (n_basic_blocks * sizeof (int));
7812       flow_depth_first_order_compute (dfs_order, rc_order);
7813
7814       /* Allocate loop structures.  */
7815       loops->array
7816         = (struct loop *) xcalloc (num_loops, sizeof (struct loop));
7817       
7818       headers = sbitmap_alloc (n_basic_blocks);
7819       sbitmap_zero (headers);
7820
7821       loops->shared_headers = sbitmap_alloc (n_basic_blocks);
7822       sbitmap_zero (loops->shared_headers);
7823
7824       /* Find and record information about all the natural loops
7825          in the CFG.  */
7826       num_loops = 0;
7827       for (b = 0; b < n_basic_blocks; b++)
7828         {
7829           basic_block header;
7830
7831           /* Search the nodes of the CFG in DFS order that we can find
7832              outer loops first.  */
7833           header = BASIC_BLOCK (rc_order[b]);
7834           
7835           /* Look for all the possible latch blocks for this header.  */
7836           for (e = header->pred; e; e = e->pred_next)
7837             {
7838               basic_block latch = e->src;
7839               
7840               /* Look for back edges where a predecessor is dominated
7841                  by this block.  A natural loop has a single entry
7842                  node (header) that dominates all the nodes in the
7843                  loop.  It also has single back edge to the header
7844                  from a latch node.  Note that multiple natural loops
7845                  may share the same header.  */
7846               if (latch != ENTRY_BLOCK_PTR
7847                   && TEST_BIT (dom[latch->index], header->index))
7848                 {
7849                   struct loop *loop;
7850                   
7851                   loop = loops->array + num_loops;
7852                   
7853                   loop->header = header;
7854                   loop->latch = latch;
7855                   loop->num = num_loops;
7856                   
7857                   /* Keep track of blocks that are loop headers so
7858                      that we can tell which loops should be merged.  */
7859                   if (TEST_BIT (headers, header->index))
7860                     SET_BIT (loops->shared_headers, header->index);
7861                   SET_BIT (headers, header->index);
7862                   
7863                   /* Find nodes contained within the loop.  */
7864                   loop->nodes = sbitmap_alloc (n_basic_blocks);
7865                   loop->num_nodes
7866                     = flow_loop_nodes_find (header, latch, loop->nodes);
7867
7868                   /* Compute first and last blocks within the loop.
7869                      These are often the same as the loop header and
7870                      loop latch respectively, but this is not always
7871                      the case.  */
7872                   loop->first
7873                     = BASIC_BLOCK (sbitmap_first_set_bit (loop->nodes));
7874                   loop->last
7875                     = BASIC_BLOCK (sbitmap_last_set_bit (loop->nodes)); 
7876           
7877                   /* Find edges which exit the loop.  Note that a node
7878                      may have several exit edges.  */
7879                   loop->num_exits
7880                     = flow_loop_exits_find (loop->nodes, &loop->exits);
7881
7882                   /* Look to see if the loop has a pre-header node.  */
7883                   loop->pre_header 
7884                     = flow_loop_pre_header_find (header, dom);
7885
7886                   num_loops++;
7887                 }
7888             }
7889         }
7890       
7891       /* Natural loops with shared headers may either be disjoint or
7892          nested.  Disjoint loops with shared headers cannot be inner
7893          loops and should be merged.  For now just mark loops that share
7894          headers.  */
7895       for (i = 0; i < num_loops; i++)
7896         if (TEST_BIT (loops->shared_headers, loops->array[i].header->index))
7897           loops->array[i].shared = 1;
7898
7899       sbitmap_free (headers);
7900     }
7901
7902   loops->num = num_loops;
7903
7904   /* Save CFG derived information to avoid recomputing it.  */
7905   loops->cfg.dom = dom;
7906   loops->cfg.dfs_order = dfs_order;
7907   loops->cfg.rc_order = rc_order;
7908
7909   /* Build the loop hierarchy tree.  */
7910   flow_loops_tree_build (loops);
7911
7912   /* Assign the loop nesting depth and enclosed loop level for each
7913      loop.  */
7914   loops->levels = flow_loops_level_compute (loops);
7915
7916   return num_loops;
7917 }
7918
7919
7920 /* Return non-zero if edge E enters header of LOOP from outside of LOOP.  */
7921
7922 int
7923 flow_loop_outside_edge_p (loop, e)
7924      const struct loop *loop;
7925      edge e;
7926 {
7927   if (e->dest != loop->header)
7928     abort ();
7929   return (e->src == ENTRY_BLOCK_PTR)
7930     || ! TEST_BIT (loop->nodes, e->src->index);
7931 }
7932
7933
7934 /* Clear LOG_LINKS fields of insns in a chain.  
7935    Also clear the global_live_at_{start,end} fields of the basic block
7936    structures.  */
7937
7938 void
7939 clear_log_links (insns)
7940      rtx insns;
7941 {
7942   rtx i;
7943   int b;
7944
7945   for (i = insns; i; i = NEXT_INSN (i))
7946     if (INSN_P (i))
7947       LOG_LINKS (i) = 0;
7948
7949   for (b = 0; b < n_basic_blocks; b++)
7950     {
7951       basic_block bb = BASIC_BLOCK (b);
7952
7953       bb->global_live_at_start = NULL;
7954       bb->global_live_at_end = NULL;
7955     }
7956
7957   ENTRY_BLOCK_PTR->global_live_at_end = NULL;
7958   EXIT_BLOCK_PTR->global_live_at_start = NULL;
7959 }
7960
7961 /* Given a register bitmap, turn on the bits in a HARD_REG_SET that
7962    correspond to the hard registers, if any, set in that map.  This
7963    could be done far more efficiently by having all sorts of special-cases
7964    with moving single words, but probably isn't worth the trouble.  */
7965
7966 void
7967 reg_set_to_hard_reg_set (to, from)
7968      HARD_REG_SET *to;
7969      bitmap from;
7970 {
7971   int i;
7972
7973   EXECUTE_IF_SET_IN_BITMAP
7974     (from, 0, i,
7975      {
7976        if (i >= FIRST_PSEUDO_REGISTER)
7977          return;
7978        SET_HARD_REG_BIT (*to, i);
7979      });
7980 }
7981