OSDN Git Service

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