OSDN Git Service

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