OSDN Git Service

fc239b9694f998001c6baa7dc812b9a0763b7b03
[pf3gnuchains/gcc-fork.git] / gcc / flow.c
1 /* Data flow analysis for GNU compiler.
2    Copyright (C) 1987, 88, 92-96, 1997 Free Software Foundation, Inc.
3
4 This file is part of GNU CC.
5
6 GNU CC is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 2, or (at your option)
9 any later version.
10
11 GNU CC is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14 GNU General Public License for more details.
15
16 You should have received a copy of the GNU General Public License
17 along with GNU CC; see the file COPYING.  If not, write to
18 the Free Software Foundation, 59 Temple Place - Suite 330,
19 Boston, MA 02111-1307, USA.  */
20
21
22 /* This file contains the data flow analysis pass of the compiler.
23    It computes data flow information
24    which tells combine_instructions which insns to consider combining
25    and controls register allocation.
26
27    Additional data flow information that is too bulky to record
28    is generated during the analysis, and is used at that time to
29    create 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
38    into basic blocks.  It records the beginnings and ends of the
39    basic blocks in the vectors basic_block_head and basic_block_end,
40    and the number of blocks in n_basic_blocks.
41
42    find_basic_blocks also finds any unreachable loops
43    and deletes them.
44
45    ** life_analysis **
46
47    life_analysis is called immediately after find_basic_blocks.
48    It uses the basic block information to determine where each
49    hard or pseudo register is live.
50
51    ** live-register info **
52
53    The information about where each register is live is in two parts:
54    the REG_NOTES of insns, and the vector basic_block_live_at_start.
55
56    basic_block_live_at_start has an element for each basic block,
57    and the element is a bit-vector with a bit for each hard or pseudo
58    register.  The bit is 1 if the register is live at the beginning
59    of the basic block.
60
61    Two types of elements can be added to an insn's REG_NOTES.  
62    A REG_DEAD note is added to an insn's REG_NOTES for any register
63    that meets both of two conditions:  The value in the register is not
64    needed in subsequent insns and the insn does not replace the value in
65    the register (in the case of multi-word hard registers, the value in
66    each register must be replaced by the insn to avoid a REG_DEAD note).
67
68    In the vast majority of cases, an object in a REG_DEAD note will be
69    used somewhere in the insn.  The (rare) exception to this is if an
70    insn uses a multi-word hard register and only some of the registers are
71    needed in subsequent insns.  In that case, REG_DEAD notes will be
72    provided for those hard registers that are not subsequently needed.
73    Partial REG_DEAD notes of this type do not occur when an insn sets
74    only some of the hard registers used in such a multi-word operand;
75    omitting REG_DEAD notes for objects stored in an insn is optional and
76    the desire to do so does not justify the complexity of the partial
77    REG_DEAD notes.
78
79    REG_UNUSED notes are added for each register that is set by the insn
80    but is unused subsequently (if every register set by the insn is unused
81    and the insn does not reference memory or have some other side-effect,
82    the insn is deleted instead).  If only part of a multi-word hard
83    register is used in a subsequent insn, REG_UNUSED notes are made for
84    the parts that will not be used.
85
86    To determine which registers are live after any insn, one can
87    start from the beginning of the basic block and scan insns, noting
88    which registers are set by each insn and which die there.
89
90    ** Other actions of life_analysis **
91
92    life_analysis sets up the LOG_LINKS fields of insns because the
93    information needed to do so is readily available.
94
95    life_analysis deletes insns whose only effect is to store a value
96    that is never used.
97
98    life_analysis notices cases where a reference to a register as
99    a memory address can be combined with a preceding or following
100    incrementation or decrementation of the register.  The separate
101    instruction to increment or decrement is deleted and the address
102    is changed to a POST_INC or similar rtx.
103
104    Each time an incrementing or decrementing address is created,
105    a REG_INC element is added to the insn's REG_NOTES list.
106
107    life_analysis fills in certain vectors containing information about
108    register usage: reg_n_refs, reg_n_deaths, reg_n_sets, reg_live_length,
109    reg_n_calls_crosses and reg_basic_block.  */
110 \f
111 #include <stdio.h>
112 #include "config.h"
113 #include "rtl.h"
114 #include "basic-block.h"
115 #include "insn-config.h"
116 #include "regs.h"
117 #include "hard-reg-set.h"
118 #include "flags.h"
119 #include "output.h"
120 #include "except.h"
121
122 #include "obstack.h"
123 #define obstack_chunk_alloc xmalloc
124 #define obstack_chunk_free free
125
126 /* The contents of the current function definition are allocated
127    in this obstack, and all are freed at the end of the function.
128    For top-level functions, this is temporary_obstack.
129    Separate obstacks are made for nested functions.  */
130
131 extern struct obstack *function_obstack;
132
133 /* List of labels that must never be deleted.  */
134 extern rtx forced_labels;
135
136 /* Get the basic block number of an insn.
137    This info should not be expected to remain available
138    after the end of life_analysis.  */
139
140 /* This is the limit of the allocated space in the following two arrays.  */
141
142 static int max_uid_for_flow;
143
144 #define BLOCK_NUM(INSN)  uid_block_number[INSN_UID (INSN)]
145
146 /* This is where the BLOCK_NUM values are really stored.
147    This is set up by find_basic_blocks and used there and in life_analysis,
148    and then freed.  */
149
150 static int *uid_block_number;
151
152 /* INSN_VOLATILE (insn) is 1 if the insn refers to anything volatile.  */
153
154 #define INSN_VOLATILE(INSN) uid_volatile[INSN_UID (INSN)]
155 static char *uid_volatile;
156
157 /* Number of basic blocks in the current function.  */
158
159 int n_basic_blocks;
160
161 /* Maximum register number used in this function, plus one.  */
162
163 int max_regno;
164
165 /* Maximum number of SCRATCH rtx's used in any basic block of this
166    function.  */
167
168 int max_scratch;
169
170 /* Number of SCRATCH rtx's in the current block.  */
171
172 static int num_scratch;
173
174 /* Indexed by n, giving various register information */
175
176 reg_info *reg_n_info;
177
178 /* Element N is the next insn that uses (hard or pseudo) register number N
179    within the current basic block; or zero, if there is no such insn.
180    This is valid only during the final backward scan in propagate_block.  */
181
182 static rtx *reg_next_use;
183
184 /* Size of a regset for the current function,
185    in (1) bytes and (2) elements.  */
186
187 int regset_bytes;
188 int regset_size;
189
190 /* Element N is first insn in basic block N.
191    This info lasts until we finish compiling the function.  */
192
193 rtx *basic_block_head;
194
195 /* Element N is last insn in basic block N.
196    This info lasts until we finish compiling the function.  */
197
198 rtx *basic_block_end;
199
200 /* Element N is a regset describing the registers live
201    at the start of basic block N.
202    This info lasts until we finish compiling the function.  */
203
204 regset *basic_block_live_at_start;
205
206 /* Regset of regs live when calls to `setjmp'-like functions happen.  */
207
208 regset regs_live_at_setjmp;
209
210 /* List made of EXPR_LIST rtx's which gives pairs of pseudo registers
211    that have to go in the same hard reg.
212    The first two regs in the list are a pair, and the next two
213    are another pair, etc.  */
214 rtx regs_may_share;
215
216 /* Element N is nonzero if control can drop into basic block N
217    from the preceding basic block.  Freed after life_analysis.  */
218
219 static char *basic_block_drops_in;
220
221 /* Element N is depth within loops of the last insn in basic block number N.
222    Freed after life_analysis.  */
223
224 static short *basic_block_loop_depth;
225
226 /* Element N nonzero if basic block N can actually be reached.
227    Vector exists only during find_basic_blocks.  */
228
229 static char *block_live_static;
230
231 /* Depth within loops of basic block being scanned for lifetime analysis,
232    plus one.  This is the weight attached to references to registers.  */
233
234 static int loop_depth;
235
236 /* During propagate_block, this is non-zero if the value of CC0 is live.  */
237
238 static int cc0_live;
239
240 /* During propagate_block, this contains the last MEM stored into.  It
241    is used to eliminate consecutive stores to the same location.  */
242
243 static rtx last_mem_set;
244
245 /* Set of registers that may be eliminable.  These are handled specially
246    in updating regs_ever_live.  */
247
248 static HARD_REG_SET elim_reg_set;
249
250 /* Forward declarations */
251 static void find_basic_blocks           PROTO((rtx, rtx));
252 static int jmp_uses_reg_or_mem          PROTO((rtx));
253 static void mark_label_ref              PROTO((rtx, rtx, int));
254 static void life_analysis               PROTO((rtx, int));
255 void allocate_for_life_analysis         PROTO((void));
256 static void init_regset_vector          PROTO((regset *, int, int, struct obstack *));
257 static void propagate_block             PROTO((regset, rtx, rtx, int, 
258                                                regset, int));
259 static rtx flow_delete_insn             PROTO((rtx));
260 static int insn_dead_p                  PROTO((rtx, regset, int));
261 static int libcall_dead_p               PROTO((rtx, regset, rtx, rtx));
262 static void mark_set_regs               PROTO((regset, regset, rtx,
263                                                rtx, regset));
264 static void mark_set_1                  PROTO((regset, regset, rtx,
265                                                rtx, regset));
266 static void find_auto_inc               PROTO((regset, rtx, rtx));
267 static void mark_used_regs              PROTO((regset, regset, rtx, int, rtx));
268 static int try_pre_increment_1          PROTO((rtx));
269 static int try_pre_increment            PROTO((rtx, rtx, HOST_WIDE_INT));
270 static rtx find_use_as_address          PROTO((rtx, rtx, HOST_WIDE_INT));
271 void dump_flow_info                     PROTO((FILE *));
272 \f
273 /* Find basic blocks of the current function and perform data flow analysis.
274    F is the first insn of the function and NREGS the number of register numbers
275    in use.  */
276
277 void
278 flow_analysis (f, nregs, file)
279      rtx f;
280      int nregs;
281      FILE *file;
282 {
283   register rtx insn;
284   register int i;
285   rtx nonlocal_label_list = nonlocal_label_rtx_list ();
286
287 #ifdef ELIMINABLE_REGS
288   static struct {int from, to; } eliminables[] = ELIMINABLE_REGS;
289 #endif
290
291   /* Record which registers will be eliminated.  We use this in
292      mark_used_regs.  */
293
294   CLEAR_HARD_REG_SET (elim_reg_set);
295
296 #ifdef ELIMINABLE_REGS
297   for (i = 0; i < sizeof eliminables / sizeof eliminables[0]; i++)
298     SET_HARD_REG_BIT (elim_reg_set, eliminables[i].from);
299 #else
300   SET_HARD_REG_BIT (elim_reg_set, FRAME_POINTER_REGNUM);
301 #endif
302
303   /* Count the basic blocks.  Also find maximum insn uid value used.  */
304
305   {
306     register RTX_CODE prev_code = JUMP_INSN;
307     register RTX_CODE code;
308
309     max_uid_for_flow = 0;
310
311     for (insn = f, i = 0; insn; insn = NEXT_INSN (insn))
312       {
313         code = GET_CODE (insn);
314         if (INSN_UID (insn) > max_uid_for_flow)
315           max_uid_for_flow = INSN_UID (insn);
316         if (code == CODE_LABEL
317             || (GET_RTX_CLASS (code) == 'i'
318                 && (prev_code == JUMP_INSN
319                     || (prev_code == CALL_INSN
320                         && nonlocal_label_list != 0)
321                     || prev_code == BARRIER)))
322           i++;
323
324         if (code == CALL_INSN && find_reg_note (insn, REG_RETVAL, NULL_RTX))
325           code = INSN;
326
327         if (code != NOTE)
328           prev_code = code;
329       }
330   }
331
332 #ifdef AUTO_INC_DEC
333   /* Leave space for insns we make in some cases for auto-inc.  These cases
334      are rare, so we don't need too much space.  */
335   max_uid_for_flow += max_uid_for_flow / 10;
336 #endif
337
338   /* Allocate some tables that last till end of compiling this function
339      and some needed only in find_basic_blocks and life_analysis.  */
340
341   n_basic_blocks = i;
342   basic_block_head = (rtx *) oballoc (n_basic_blocks * sizeof (rtx));
343   basic_block_end = (rtx *) oballoc (n_basic_blocks * sizeof (rtx));
344   basic_block_drops_in = (char *) alloca (n_basic_blocks);
345   basic_block_loop_depth = (short *) alloca (n_basic_blocks * sizeof (short));
346   uid_block_number
347     = (int *) alloca ((max_uid_for_flow + 1) * sizeof (int));
348   uid_volatile = (char *) alloca (max_uid_for_flow + 1);
349   bzero (uid_volatile, max_uid_for_flow + 1);
350
351   find_basic_blocks (f, nonlocal_label_list);
352   life_analysis (f, nregs);
353   if (file)
354     dump_flow_info (file);
355
356   basic_block_drops_in = 0;
357   uid_block_number = 0;
358   basic_block_loop_depth = 0;
359 }
360 \f
361 /* Find all basic blocks of the function whose first insn is F.
362    Store the correct data in the tables that describe the basic blocks,
363    set up the chains of references for each CODE_LABEL, and
364    delete any entire basic blocks that cannot be reached.
365
366    NONLOCAL_LABEL_LIST is the same local variable from flow_analysis.  */
367
368 static void
369 find_basic_blocks (f, nonlocal_label_list)
370      rtx f, nonlocal_label_list;
371 {
372   register rtx insn;
373   register int i;
374   register char *block_live = (char *) alloca (n_basic_blocks);
375   register char *block_marked = (char *) alloca (n_basic_blocks);
376   /* List of label_refs to all labels whose addresses are taken
377      and used as data.  */
378   rtx label_value_list;
379   rtx x, note;
380   enum rtx_code prev_code, code;
381   int depth, pass;
382
383   pass = 1;
384  restart:
385
386   label_value_list = 0;
387   block_live_static = block_live;
388   bzero (block_live, n_basic_blocks);
389   bzero (block_marked, n_basic_blocks);
390
391   /* Initialize with just block 0 reachable and no blocks marked.  */
392   if (n_basic_blocks > 0)
393     block_live[0] = 1;
394
395   /* Initialize the ref chain of each label to 0.  Record where all the
396      blocks start and end and their depth in loops.  For each insn, record
397      the block it is in.   Also mark as reachable any blocks headed by labels
398      that must not be deleted.  */
399
400   for (insn = f, i = -1, prev_code = JUMP_INSN, depth = 1;
401        insn; insn = NEXT_INSN (insn))
402     {
403       code = GET_CODE (insn);
404       if (code == NOTE)
405         {
406           if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG)
407             depth++;
408           else if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END)
409             depth--;
410         }
411
412       /* A basic block starts at label, or after something that can jump.  */
413       else if (code == CODE_LABEL
414                || (GET_RTX_CLASS (code) == 'i'
415                    && (prev_code == JUMP_INSN
416                        || (prev_code == CALL_INSN
417                            && nonlocal_label_list != 0
418                            && ! find_reg_note (insn, REG_RETVAL, NULL_RTX))
419                        || prev_code == BARRIER)))
420         {
421           basic_block_head[++i] = insn;
422           basic_block_end[i] = insn;
423           basic_block_loop_depth[i] = depth;
424
425           if (code == CODE_LABEL)
426             {
427                 LABEL_REFS (insn) = insn;
428                 /* Any label that cannot be deleted
429                    is considered to start a reachable block.  */
430                 if (LABEL_PRESERVE_P (insn))
431                   block_live[i] = 1;
432               }
433         }
434
435       else if (GET_RTX_CLASS (code) == 'i')
436         {
437           basic_block_end[i] = insn;
438           basic_block_loop_depth[i] = depth;
439         }
440
441       if (GET_RTX_CLASS (code) == 'i')
442         {
443           /* Make a list of all labels referred to other than by jumps.  */
444           for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
445             if (REG_NOTE_KIND (note) == REG_LABEL)
446               label_value_list = gen_rtx (EXPR_LIST, VOIDmode, XEXP (note, 0),
447                                           label_value_list);
448         }
449
450       BLOCK_NUM (insn) = i;
451
452       if (code != NOTE)
453         prev_code = code;
454     }
455
456   /* During the second pass, `n_basic_blocks' is only an upper bound.
457      Only perform the sanity check for the first pass, and on the second
458      pass ensure `n_basic_blocks' is set to the correct value.  */
459   if (pass == 1 && i + 1 != n_basic_blocks)
460     abort ();
461   n_basic_blocks = i + 1;
462
463   /* Don't delete the labels (in this function)
464      that are referenced by non-jump instructions.  */
465
466   for (x = label_value_list; x; x = XEXP (x, 1))
467     if (! LABEL_REF_NONLOCAL_P (x))
468       block_live[BLOCK_NUM (XEXP (x, 0))] = 1;
469
470   for (x = forced_labels; x; x = XEXP (x, 1))
471     if (! LABEL_REF_NONLOCAL_P (x))
472       block_live[BLOCK_NUM (XEXP (x, 0))] = 1;
473
474   for (x = exception_handler_labels; x; x = XEXP (x, 1))
475     block_live[BLOCK_NUM (XEXP (x, 0))] = 1;
476
477   /* Record which basic blocks control can drop in to.  */
478
479   for (i = 0; i < n_basic_blocks; i++)
480     {
481       for (insn = PREV_INSN (basic_block_head[i]);
482            insn && GET_CODE (insn) == NOTE; insn = PREV_INSN (insn))
483         ;
484
485       basic_block_drops_in[i] = insn && GET_CODE (insn) != BARRIER;
486     }
487
488   /* Now find which basic blocks can actually be reached
489      and put all jump insns' LABEL_REFS onto the ref-chains
490      of their target labels.  */
491
492   if (n_basic_blocks > 0)
493     {
494       int something_marked = 1;
495       int deleted;
496
497       /* Find all indirect jump insns and mark them as possibly jumping to all
498          the labels whose addresses are explicitly used.  This is because,
499          when there are computed gotos, we can't tell which labels they jump
500          to, of all the possibilities.
501
502          Tablejumps and casesi insns are OK and we can recognize them by
503          a (use (label_ref)).  */
504
505       for (insn = f; insn; insn = NEXT_INSN (insn))
506         if (GET_CODE (insn) == JUMP_INSN)
507           {
508             rtx pat = PATTERN (insn);
509             int computed_jump = 0;
510
511             if (GET_CODE (pat) == PARALLEL)
512               {
513                 int len = XVECLEN (pat, 0);
514                 int has_use_labelref = 0;
515
516                 for (i = len - 1; i >= 0; i--)
517                   if (GET_CODE (XVECEXP (pat, 0, i)) == USE
518                       && (GET_CODE (XEXP (XVECEXP (pat, 0, i), 0))
519                           == LABEL_REF))
520                     has_use_labelref = 1;
521
522                 if (! has_use_labelref)
523                   for (i = len - 1; i >= 0; i--)
524                     if (GET_CODE (XVECEXP (pat, 0, i)) == SET
525                         && SET_DEST (XVECEXP (pat, 0, i)) == pc_rtx
526                         && jmp_uses_reg_or_mem (SET_SRC (XVECEXP (pat, 0, i))))
527                       computed_jump = 1;
528               }
529             else if (GET_CODE (pat) == SET
530                      && SET_DEST (pat) == pc_rtx
531                      && jmp_uses_reg_or_mem (SET_SRC (pat)))
532               computed_jump = 1;
533                     
534             if (computed_jump)
535               {
536                 for (x = label_value_list; x; x = XEXP (x, 1))
537                   mark_label_ref (gen_rtx (LABEL_REF, VOIDmode, XEXP (x, 0)),
538                                   insn, 0);
539
540                 for (x = forced_labels; x; x = XEXP (x, 1))
541                   mark_label_ref (gen_rtx (LABEL_REF, VOIDmode, XEXP (x, 0)),
542                               insn, 0);
543               }
544           }
545
546       /* Find all call insns and mark them as possibly jumping
547          to all the nonlocal goto handler labels.  */
548
549       for (insn = f; insn; insn = NEXT_INSN (insn))
550         if (GET_CODE (insn) == CALL_INSN
551             && ! find_reg_note (insn, REG_RETVAL, NULL_RTX))
552           {
553             for (x = nonlocal_label_list; x; x = XEXP (x, 1))
554               mark_label_ref (gen_rtx (LABEL_REF, VOIDmode, XEXP (x, 0)),
555                               insn, 0);
556
557             /* ??? This could be made smarter:
558                in some cases it's possible to tell that certain
559                calls will not do a nonlocal goto.
560
561                For example, if the nested functions that do the
562                nonlocal gotos do not have their addresses taken, then
563                only calls to those functions or to other nested
564                functions that use them could possibly do nonlocal
565                gotos.  */
566           }
567
568       /* Pass over all blocks, marking each block that is reachable
569          and has not yet been marked.
570          Keep doing this until, in one pass, no blocks have been marked.
571          Then blocks_live and blocks_marked are identical and correct.
572          In addition, all jumps actually reachable have been marked.  */
573
574       while (something_marked)
575         {
576           something_marked = 0;
577           for (i = 0; i < n_basic_blocks; i++)
578             if (block_live[i] && !block_marked[i])
579               {
580                 block_marked[i] = 1;
581                 something_marked = 1;
582                 if (i + 1 < n_basic_blocks && basic_block_drops_in[i + 1])
583                   block_live[i + 1] = 1;
584                 insn = basic_block_end[i];
585                 if (GET_CODE (insn) == JUMP_INSN)
586                   mark_label_ref (PATTERN (insn), insn, 0);
587               }
588         }
589
590       /* ??? See if we have a "live" basic block that is not reachable.
591          This can happen if it is headed by a label that is preserved or
592          in one of the label lists, but no call or computed jump is in
593          the loop.  It's not clear if we can delete the block or not,
594          but don't for now.  However, we will mess up register status if
595          it remains unreachable, so add a fake reachability from the
596          previous block.  */
597
598       for (i = 1; i < n_basic_blocks; i++)
599         if (block_live[i] && ! basic_block_drops_in[i]
600             && GET_CODE (basic_block_head[i]) == CODE_LABEL
601             && LABEL_REFS (basic_block_head[i]) == basic_block_head[i])
602           basic_block_drops_in[i] = 1;
603
604       /* Now delete the code for any basic blocks that can't be reached.
605          They can occur because jump_optimize does not recognize
606          unreachable loops as unreachable.  */
607
608       deleted = 0;
609       for (i = 0; i < n_basic_blocks; i++)
610         if (!block_live[i])
611           {
612             deleted++;
613
614             /* Delete the insns in a (non-live) block.  We physically delete
615                every non-note insn except the start and end (so
616                basic_block_head/end needn't be updated), we turn the latter
617                into NOTE_INSN_DELETED notes.
618                We use to "delete" the insns by turning them into notes, but
619                we may be deleting lots of insns that subsequent passes would
620                otherwise have to process.  Secondly, lots of deleted blocks in
621                a row can really slow down propagate_block since it will
622                otherwise process insn-turned-notes multiple times when it
623                looks for loop begin/end notes.  */
624             if (basic_block_head[i] != basic_block_end[i])
625               {
626                 /* It would be quicker to delete all of these with a single
627                    unchaining, rather than one at a time, but we need to keep
628                    the NOTE's.  */
629                 insn = NEXT_INSN (basic_block_head[i]);
630                 while (insn != basic_block_end[i])
631                   {
632                     if (GET_CODE (insn) == BARRIER)
633                       abort ();
634                     else if (GET_CODE (insn) != NOTE)
635                       insn = flow_delete_insn (insn);
636                     else
637                       insn = NEXT_INSN (insn);
638                   }
639               }
640             insn = basic_block_head[i];
641             if (GET_CODE (insn) != NOTE)
642               {
643                 /* Turn the head into a deleted insn note.  */
644                 if (GET_CODE (insn) == BARRIER)
645                   abort ();
646                 PUT_CODE (insn, NOTE);
647                 NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
648                 NOTE_SOURCE_FILE (insn) = 0;
649               }
650             insn = basic_block_end[i];
651             if (GET_CODE (insn) != NOTE)
652               {
653                 /* Turn the tail into a deleted insn note.  */
654                 if (GET_CODE (insn) == BARRIER)
655                   abort ();
656                 PUT_CODE (insn, NOTE);
657                 NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
658                 NOTE_SOURCE_FILE (insn) = 0;
659               }
660             /* BARRIERs are between basic blocks, not part of one.
661                Delete a BARRIER if the preceding jump is deleted.
662                We cannot alter a BARRIER into a NOTE
663                because it is too short; but we can really delete
664                it because it is not part of a basic block.  */
665             if (NEXT_INSN (insn) != 0
666                 && GET_CODE (NEXT_INSN (insn)) == BARRIER)
667               delete_insn (NEXT_INSN (insn));
668
669             /* Each time we delete some basic blocks,
670                see if there is a jump around them that is
671                being turned into a no-op.  If so, delete it.  */
672
673             if (block_live[i - 1])
674               {
675                 register int j;
676                 for (j = i + 1; j < n_basic_blocks; j++)
677                   if (block_live[j])
678                     {
679                       rtx label;
680                       insn = basic_block_end[i - 1];
681                       if (GET_CODE (insn) == JUMP_INSN
682                           /* An unconditional jump is the only possibility
683                              we must check for, since a conditional one
684                              would make these blocks live.  */
685                           && simplejump_p (insn)
686                           && (label = XEXP (SET_SRC (PATTERN (insn)), 0), 1)
687                           && INSN_UID (label) != 0
688                           && BLOCK_NUM (label) == j)
689                         {
690                           PUT_CODE (insn, NOTE);
691                           NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
692                           NOTE_SOURCE_FILE (insn) = 0;
693                           if (GET_CODE (NEXT_INSN (insn)) != BARRIER)
694                             abort ();
695                           delete_insn (NEXT_INSN (insn));
696                         }
697                       break;
698                     }
699               }
700           }
701
702       /* There are pathological cases where one function calling hundreds of
703          nested inline functions can generate lots and lots of unreachable
704          blocks that jump can't delete.  Since we don't use sparse matrices
705          a lot of memory will be needed to compile such functions.
706          Implementing sparse matrices is a fair bit of work and it is not
707          clear that they win more than they lose (we don't want to
708          unnecessarily slow down compilation of normal code).  By making
709          another pass for the pathological case, we can greatly speed up
710          their compilation without hurting normal code.  This works because
711          all the insns in the unreachable blocks have either been deleted or
712          turned into notes.
713          Note that we're talking about reducing memory usage by 10's of
714          megabytes and reducing compilation time by several minutes.  */
715       /* ??? The choice of when to make another pass is a bit arbitrary,
716          and was derived from empirical data.  */
717       if (pass == 1
718           && deleted > 200)
719         {
720           pass++;
721           n_basic_blocks -= deleted;
722           /* `n_basic_blocks' may not be correct at this point: two previously
723              separate blocks may now be merged.  That's ok though as we
724              recalculate it during the second pass.  It certainly can't be
725              any larger than the current value.  */
726           goto restart;
727         }
728     }
729 }
730 \f
731 /* Subroutines of find_basic_blocks.  */
732
733 /* Return 1 if X, the SRC_SRC of  SET of (pc) contain a REG or MEM that is
734    not in the constant pool and not in the condition of an IF_THEN_ELSE.  */
735
736 static int
737 jmp_uses_reg_or_mem (x)
738      rtx x;
739 {
740   enum rtx_code code = GET_CODE (x);
741   int i, j;
742   char *fmt;
743
744   switch (code)
745     {
746     case CONST:
747     case LABEL_REF:
748     case PC:
749       return 0;
750
751     case REG:
752       return 1;
753
754     case MEM:
755       return ! (GET_CODE (XEXP (x, 0)) == SYMBOL_REF
756                 && CONSTANT_POOL_ADDRESS_P (XEXP (x, 0)));
757
758     case IF_THEN_ELSE:
759       return (jmp_uses_reg_or_mem (XEXP (x, 1))
760               || jmp_uses_reg_or_mem (XEXP (x, 2)));
761
762     case PLUS:  case MINUS:  case MULT:
763       return (jmp_uses_reg_or_mem (XEXP (x, 0))
764               || jmp_uses_reg_or_mem (XEXP (x, 1)));
765     }
766
767   fmt = GET_RTX_FORMAT (code);
768   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
769     {
770       if (fmt[i] == 'e'
771           && jmp_uses_reg_or_mem (XEXP (x, i)))
772         return 1;
773
774       if (fmt[i] == 'E')
775         for (j = 0; j < XVECLEN (x, i); j++)
776           if (jmp_uses_reg_or_mem (XVECEXP (x, i, j)))
777             return 1;
778     }
779
780   return 0;
781 }
782
783 /* Check expression X for label references;
784    if one is found, add INSN to the label's chain of references.
785
786    CHECKDUP means check for and avoid creating duplicate references
787    from the same insn.  Such duplicates do no serious harm but
788    can slow life analysis.  CHECKDUP is set only when duplicates
789    are likely.  */
790
791 static void
792 mark_label_ref (x, insn, checkdup)
793      rtx x, insn;
794      int checkdup;
795 {
796   register RTX_CODE code;
797   register int i;
798   register char *fmt;
799
800   /* We can be called with NULL when scanning label_value_list.  */
801   if (x == 0)
802     return;
803
804   code = GET_CODE (x);
805   if (code == LABEL_REF)
806     {
807       register rtx label = XEXP (x, 0);
808       register rtx y;
809       if (GET_CODE (label) != CODE_LABEL)
810         abort ();
811       /* If the label was never emitted, this insn is junk,
812          but avoid a crash trying to refer to BLOCK_NUM (label).
813          This can happen as a result of a syntax error
814          and a diagnostic has already been printed.  */
815       if (INSN_UID (label) == 0)
816         return;
817       CONTAINING_INSN (x) = insn;
818       /* if CHECKDUP is set, check for duplicate ref from same insn
819          and don't insert.  */
820       if (checkdup)
821         for (y = LABEL_REFS (label); y != label; y = LABEL_NEXTREF (y))
822           if (CONTAINING_INSN (y) == insn)
823             return;
824       LABEL_NEXTREF (x) = LABEL_REFS (label);
825       LABEL_REFS (label) = x;
826       block_live_static[BLOCK_NUM (label)] = 1;
827       return;
828     }
829
830   fmt = GET_RTX_FORMAT (code);
831   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
832     {
833       if (fmt[i] == 'e')
834         mark_label_ref (XEXP (x, i), insn, 0);
835       if (fmt[i] == 'E')
836         {
837           register int j;
838           for (j = 0; j < XVECLEN (x, i); j++)
839             mark_label_ref (XVECEXP (x, i, j), insn, 1);
840         }
841     }
842 }
843
844 /* Delete INSN by patching it out.
845    Return the next insn.  */
846
847 static rtx
848 flow_delete_insn (insn)
849      rtx insn;
850 {
851   /* ??? For the moment we assume we don't have to watch for NULLs here
852      since the start/end of basic blocks aren't deleted like this.  */
853   NEXT_INSN (PREV_INSN (insn)) = NEXT_INSN (insn);
854   PREV_INSN (NEXT_INSN (insn)) = PREV_INSN (insn);
855   return NEXT_INSN (insn);
856 }
857 \f
858 /* Determine which registers are live at the start of each
859    basic block of the function whose first insn is F.
860    NREGS is the number of registers used in F.
861    We allocate the vector basic_block_live_at_start
862    and the regsets that it points to, and fill them with the data.
863    regset_size and regset_bytes are also set here.  */
864
865 static void
866 life_analysis (f, nregs)
867      rtx f;
868      int nregs;
869 {
870   int first_pass;
871   int changed;
872   /* For each basic block, a bitmask of regs
873      live on exit from the block.  */
874   regset *basic_block_live_at_end;
875   /* For each basic block, a bitmask of regs
876      live on entry to a successor-block of this block.
877      If this does not match basic_block_live_at_end,
878      that must be updated, and the block must be rescanned.  */
879   regset *basic_block_new_live_at_end;
880   /* For each basic block, a bitmask of regs
881      whose liveness at the end of the basic block
882      can make a difference in which regs are live on entry to the block.
883      These are the regs that are set within the basic block,
884      possibly excluding those that are used after they are set.  */
885   regset *basic_block_significant;
886   register int i;
887   rtx insn;
888
889   struct obstack flow_obstack;
890
891   gcc_obstack_init (&flow_obstack);
892
893   max_regno = nregs;
894
895   bzero (regs_ever_live, sizeof regs_ever_live);
896
897   /* Allocate and zero out many data structures
898      that will record the data from lifetime analysis.  */
899
900   allocate_for_life_analysis ();
901
902   reg_next_use = (rtx *) alloca (nregs * sizeof (rtx));
903   bzero ((char *) reg_next_use, nregs * sizeof (rtx));
904
905   /* Set up several regset-vectors used internally within this function.
906      Their meanings are documented above, with their declarations.  */
907
908   basic_block_live_at_end
909     = (regset *) alloca (n_basic_blocks * sizeof (regset));
910
911   /* Don't use alloca since that leads to a crash rather than an error message
912      if there isn't enough space.
913      Don't use oballoc since we may need to allocate other things during
914      this function on the temporary obstack.  */
915   init_regset_vector (basic_block_live_at_end, n_basic_blocks, regset_bytes,
916                       &flow_obstack);
917
918   basic_block_new_live_at_end
919     = (regset *) alloca (n_basic_blocks * sizeof (regset));
920   init_regset_vector (basic_block_new_live_at_end, n_basic_blocks, regset_bytes,
921                       &flow_obstack);
922
923   basic_block_significant
924     = (regset *) alloca (n_basic_blocks * sizeof (regset));
925   init_regset_vector (basic_block_significant, n_basic_blocks, regset_bytes,
926                       &flow_obstack);
927
928   /* Record which insns refer to any volatile memory
929      or for any reason can't be deleted just because they are dead stores.
930      Also, delete any insns that copy a register to itself.  */
931
932   for (insn = f; insn; insn = NEXT_INSN (insn))
933     {
934       enum rtx_code code1 = GET_CODE (insn);
935       if (code1 == CALL_INSN)
936         INSN_VOLATILE (insn) = 1;
937       else if (code1 == INSN || code1 == JUMP_INSN)
938         {
939           /* Delete (in effect) any obvious no-op moves.  */
940           if (GET_CODE (PATTERN (insn)) == SET
941               && GET_CODE (SET_DEST (PATTERN (insn))) == REG
942               && GET_CODE (SET_SRC (PATTERN (insn))) == REG
943               && (REGNO (SET_DEST (PATTERN (insn)))
944                   == REGNO (SET_SRC (PATTERN (insn))))
945               /* Insns carrying these notes are useful later on.  */
946               && ! find_reg_note (insn, REG_EQUAL, NULL_RTX))
947             {
948               PUT_CODE (insn, NOTE);
949               NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
950               NOTE_SOURCE_FILE (insn) = 0;
951             }
952           /* Delete (in effect) any obvious no-op moves.  */
953           else if (GET_CODE (PATTERN (insn)) == SET
954               && GET_CODE (SET_DEST (PATTERN (insn))) == SUBREG
955               && GET_CODE (SUBREG_REG (SET_DEST (PATTERN (insn)))) == REG
956               && GET_CODE (SET_SRC (PATTERN (insn))) == SUBREG
957               && GET_CODE (SUBREG_REG (SET_SRC (PATTERN (insn)))) == REG
958               && (REGNO (SUBREG_REG (SET_DEST (PATTERN (insn))))
959                   == REGNO (SUBREG_REG (SET_SRC (PATTERN (insn)))))
960               && SUBREG_WORD (SET_DEST (PATTERN (insn))) ==
961                               SUBREG_WORD (SET_SRC (PATTERN (insn)))
962               /* Insns carrying these notes are useful later on.  */
963               && ! find_reg_note (insn, REG_EQUAL, NULL_RTX))
964             {
965               PUT_CODE (insn, NOTE);
966               NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
967               NOTE_SOURCE_FILE (insn) = 0;
968             }
969           else if (GET_CODE (PATTERN (insn)) == PARALLEL)
970             {
971               /* If nothing but SETs of registers to themselves,
972                  this insn can also be deleted.  */
973               for (i = 0; i < XVECLEN (PATTERN (insn), 0); i++)
974                 {
975                   rtx tem = XVECEXP (PATTERN (insn), 0, i);
976
977                   if (GET_CODE (tem) == USE
978                       || GET_CODE (tem) == CLOBBER)
979                     continue;
980                     
981                   if (GET_CODE (tem) != SET
982                       || GET_CODE (SET_DEST (tem)) != REG
983                       || GET_CODE (SET_SRC (tem)) != REG
984                       || REGNO (SET_DEST (tem)) != REGNO (SET_SRC (tem)))
985                     break;
986                 }
987                 
988               if (i == XVECLEN (PATTERN (insn), 0)
989                   /* Insns carrying these notes are useful later on.  */
990                   && ! find_reg_note (insn, REG_EQUAL, NULL_RTX))
991                 {
992                   PUT_CODE (insn, NOTE);
993                   NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
994                   NOTE_SOURCE_FILE (insn) = 0;
995                 }
996               else
997                 INSN_VOLATILE (insn) = volatile_refs_p (PATTERN (insn));
998             }
999           else if (GET_CODE (PATTERN (insn)) != USE)
1000             INSN_VOLATILE (insn) = volatile_refs_p (PATTERN (insn));
1001           /* A SET that makes space on the stack cannot be dead.
1002              (Such SETs occur only for allocating variable-size data,
1003              so they will always have a PLUS or MINUS according to the
1004              direction of stack growth.)
1005              Even if this function never uses this stack pointer value,
1006              signal handlers do!  */
1007           else if (code1 == INSN && GET_CODE (PATTERN (insn)) == SET
1008                    && SET_DEST (PATTERN (insn)) == stack_pointer_rtx
1009 #ifdef STACK_GROWS_DOWNWARD
1010                    && GET_CODE (SET_SRC (PATTERN (insn))) == MINUS
1011 #else
1012                    && GET_CODE (SET_SRC (PATTERN (insn))) == PLUS
1013 #endif
1014                    && XEXP (SET_SRC (PATTERN (insn)), 0) == stack_pointer_rtx)
1015             INSN_VOLATILE (insn) = 1;
1016         }
1017     }
1018
1019   if (n_basic_blocks > 0)
1020 #ifdef EXIT_IGNORE_STACK
1021     if (! EXIT_IGNORE_STACK
1022         || (! FRAME_POINTER_REQUIRED && flag_omit_frame_pointer))
1023 #endif
1024       {
1025         /* If exiting needs the right stack value,
1026            consider the stack pointer live at the end of the function.  */
1027         SET_REGNO_REG_SET (basic_block_live_at_end[n_basic_blocks - 1],
1028                            STACK_POINTER_REGNUM);
1029         SET_REGNO_REG_SET (basic_block_new_live_at_end[n_basic_blocks - 1],
1030                            STACK_POINTER_REGNUM);
1031       }
1032
1033   /* Mark the frame pointer is needed at the end of the function.  If
1034      we end up eliminating it, it will be removed from the live list
1035      of each basic block by reload.  */
1036
1037   if (n_basic_blocks > 0)
1038     {
1039       SET_REGNO_REG_SET (basic_block_live_at_end[n_basic_blocks - 1],
1040                          FRAME_POINTER_REGNUM);
1041       SET_REGNO_REG_SET (basic_block_new_live_at_end[n_basic_blocks - 1],
1042                          FRAME_POINTER_REGNUM);
1043 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
1044       /* If they are different, also mark the hard frame pointer as live */
1045       SET_REGNO_REG_SET (basic_block_live_at_end[n_basic_blocks - 1],
1046                          HARD_FRAME_POINTER_REGNUM);
1047       SET_REGNO_REG_SET (basic_block_new_live_at_end[n_basic_blocks - 1],
1048                          HARD_FRAME_POINTER_REGNUM);
1049 #endif      
1050       }
1051
1052   /* Mark all global registers and all registers used by the epilogue
1053      as being live at the end of the function since they may be
1054      referenced by our caller.  */
1055
1056   if (n_basic_blocks > 0)
1057     for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1058       if (global_regs[i]
1059 #ifdef EPILOGUE_USES
1060           || EPILOGUE_USES (i)
1061 #endif
1062           )
1063         {
1064           SET_REGNO_REG_SET (basic_block_live_at_end[n_basic_blocks - 1], i);
1065           SET_REGNO_REG_SET (basic_block_new_live_at_end[n_basic_blocks - 1], i);
1066         }
1067
1068   /* Propagate life info through the basic blocks
1069      around the graph of basic blocks.
1070
1071      This is a relaxation process: each time a new register
1072      is live at the end of the basic block, we must scan the block
1073      to determine which registers are, as a consequence, live at the beginning
1074      of that block.  These registers must then be marked live at the ends
1075      of all the blocks that can transfer control to that block.
1076      The process continues until it reaches a fixed point.  */
1077
1078   first_pass = 1;
1079   changed = 1;
1080   while (changed)
1081     {
1082       changed = 0;
1083       for (i = n_basic_blocks - 1; i >= 0; i--)
1084         {
1085           int consider = first_pass;
1086           int must_rescan = first_pass;
1087           register int j;
1088
1089           if (!first_pass)
1090             {
1091               /* Set CONSIDER if this block needs thinking about at all
1092                  (that is, if the regs live now at the end of it
1093                  are not the same as were live at the end of it when
1094                  we last thought about it).
1095                  Set must_rescan if it needs to be thought about
1096                  instruction by instruction (that is, if any additional
1097                  reg that is live at the end now but was not live there before
1098                  is one of the significant regs of this basic block).  */
1099
1100               EXECUTE_IF_AND_COMPL_IN_REG_SET (basic_block_new_live_at_end[i],
1101                                                basic_block_live_at_end[i],
1102                                                0, j,
1103                                                {
1104                                                  consider = 1;
1105                                                  if (REGNO_REG_SET_P (basic_block_significant[i], j))
1106                                                    {
1107                                                      must_rescan = 1;
1108                                                      goto done;
1109                                                    }
1110                                                });
1111             done:
1112               if (! consider)
1113                 continue;
1114             }
1115
1116           /* The live_at_start of this block may be changing,
1117              so another pass will be required after this one.  */
1118           changed = 1;
1119
1120           if (! must_rescan)
1121             {
1122               /* No complete rescan needed;
1123                  just record those variables newly known live at end
1124                  as live at start as well.  */
1125               IOR_AND_COMPL_REG_SET (basic_block_live_at_start[i],
1126                                      basic_block_new_live_at_end[i],
1127                                      basic_block_live_at_end[i]);
1128
1129               IOR_AND_COMPL_REG_SET (basic_block_live_at_end[i],
1130                                      basic_block_new_live_at_end[i],
1131                                      basic_block_live_at_end[i]);
1132             }
1133           else
1134             {
1135               /* Update the basic_block_live_at_start
1136                  by propagation backwards through the block.  */
1137               COPY_REG_SET (basic_block_live_at_end[i],
1138                             basic_block_new_live_at_end[i]);
1139               COPY_REG_SET (basic_block_live_at_start[i],
1140                             basic_block_live_at_end[i]);
1141               propagate_block (basic_block_live_at_start[i],
1142                                basic_block_head[i], basic_block_end[i], 0,
1143                                first_pass ? basic_block_significant[i]
1144                                : (regset) 0,
1145                                i);
1146             }
1147
1148           {
1149             register rtx jump, head;
1150
1151             /* Update the basic_block_new_live_at_end's of the block
1152                that falls through into this one (if any).  */
1153             head = basic_block_head[i];
1154             if (basic_block_drops_in[i])
1155               IOR_REG_SET (basic_block_new_live_at_end[i-1],
1156                            basic_block_live_at_start[i]);
1157
1158             /* Update the basic_block_new_live_at_end's of
1159                all the blocks that jump to this one.  */
1160             if (GET_CODE (head) == CODE_LABEL)
1161               for (jump = LABEL_REFS (head);
1162                    jump != head;
1163                    jump = LABEL_NEXTREF (jump))
1164                 {
1165                   register int from_block = BLOCK_NUM (CONTAINING_INSN (jump));
1166                   IOR_REG_SET (basic_block_new_live_at_end[from_block],
1167                                basic_block_live_at_start[i]);
1168                 }
1169           }
1170 #ifdef USE_C_ALLOCA
1171           alloca (0);
1172 #endif
1173         }
1174       first_pass = 0;
1175     }
1176
1177   /* The only pseudos that are live at the beginning of the function are
1178      those that were not set anywhere in the function.  local-alloc doesn't
1179      know how to handle these correctly, so mark them as not local to any
1180      one basic block.  */
1181
1182   if (n_basic_blocks > 0)
1183     EXECUTE_IF_SET_IN_REG_SET (basic_block_live_at_start[0],
1184                                FIRST_PSEUDO_REGISTER, i,
1185                                {
1186                                  REG_BASIC_BLOCK (i) = REG_BLOCK_GLOBAL;
1187                                });
1188
1189   /* Now the life information is accurate.
1190      Make one more pass over each basic block
1191      to delete dead stores, create autoincrement addressing
1192      and record how many times each register is used, is set, or dies.
1193
1194      To save time, we operate directly in basic_block_live_at_end[i],
1195      thus destroying it (in fact, converting it into a copy of
1196      basic_block_live_at_start[i]).  This is ok now because
1197      basic_block_live_at_end[i] is no longer used past this point.  */
1198
1199   max_scratch = 0;
1200
1201   for (i = 0; i < n_basic_blocks; i++)
1202     {
1203       propagate_block (basic_block_live_at_end[i],
1204                        basic_block_head[i], basic_block_end[i], 1,
1205                        (regset) 0, i);
1206 #ifdef USE_C_ALLOCA
1207       alloca (0);
1208 #endif
1209     }
1210
1211 #if 0
1212   /* Something live during a setjmp should not be put in a register
1213      on certain machines which restore regs from stack frames
1214      rather than from the jmpbuf.
1215      But we don't need to do this for the user's variables, since
1216      ANSI says only volatile variables need this.  */
1217 #ifdef LONGJMP_RESTORE_FROM_STACK
1218   EXECUTE_IF_SET_IN_REG_SET (regs_live_at_setjmp,
1219                              FIRST_PSEUDO_REGISTER, i,
1220                              {
1221                                if (regno_reg_rtx[i] != 0
1222                                    && ! REG_USERVAR_P (regno_reg_rtx[i]))
1223                                  {
1224                                    REG_LIVE_LENGTH (i) = -1;
1225                                    REG_BASIC_BLOCK (i) = -1;
1226                                  }
1227                              });
1228 #endif
1229 #endif
1230
1231   /* We have a problem with any pseudoreg that
1232      lives across the setjmp.  ANSI says that if a
1233      user variable does not change in value
1234      between the setjmp and the longjmp, then the longjmp preserves it.
1235      This includes longjmp from a place where the pseudo appears dead.
1236      (In principle, the value still exists if it is in scope.)
1237      If the pseudo goes in a hard reg, some other value may occupy
1238      that hard reg where this pseudo is dead, thus clobbering the pseudo.
1239      Conclusion: such a pseudo must not go in a hard reg.  */
1240   EXECUTE_IF_SET_IN_REG_SET (regs_live_at_setjmp,
1241                              FIRST_PSEUDO_REGISTER, i,
1242                              {
1243                                if (regno_reg_rtx[i] != 0)
1244                                  {
1245                                    REG_LIVE_LENGTH (i) = -1;
1246                                    REG_BASIC_BLOCK (i) = -1;
1247                                  }
1248                              });
1249
1250   obstack_free (&flow_obstack, NULL_PTR);
1251 }
1252 \f
1253 /* Subroutines of life analysis.  */
1254
1255 /* Allocate the permanent data structures that represent the results
1256    of life analysis.  Not static since used also for stupid life analysis.  */
1257
1258 void
1259 allocate_for_life_analysis ()
1260 {
1261   register int i;
1262
1263   regset_size = ((max_regno + REGSET_ELT_BITS - 1) / REGSET_ELT_BITS);
1264   regset_bytes = regset_size * sizeof (*(regset) 0);
1265
1266   /* Because both reg_scan and flow_analysis want to set up the REG_N_SETS
1267      information, explicitly reset it here.  The allocation should have
1268      already happened on the previous reg_scan pass.  Make sure in case
1269      some more registers were allocated.  */
1270   allocate_reg_info (max_regno, FALSE, FALSE);
1271
1272   for (i = 0; i < max_regno; i++)
1273     REG_N_SETS (i) = 0;
1274
1275   basic_block_live_at_start
1276     = (regset *) oballoc (n_basic_blocks * sizeof (regset));
1277   init_regset_vector (basic_block_live_at_start, n_basic_blocks, regset_bytes,
1278                       function_obstack);
1279
1280   regs_live_at_setjmp = OBSTACK_ALLOC_REG_SET (function_obstack);
1281   CLEAR_REG_SET (regs_live_at_setjmp);
1282 }
1283
1284 /* Make each element of VECTOR point at a regset,
1285    taking the space for all those regsets from SPACE.
1286    SPACE is of type regset, but it is really as long as NELTS regsets.
1287    BYTES_PER_ELT is the number of bytes in one regset.  */
1288
1289 static void
1290 init_regset_vector (vector, nelts, bytes_per_elt, alloc_obstack)
1291      regset *vector;
1292      int nelts;
1293      int bytes_per_elt;
1294      struct obstack *alloc_obstack;
1295 {
1296   register int i;
1297
1298   for (i = 0; i < nelts; i++)
1299     {
1300       vector[i] = OBSTACK_ALLOC_REG_SET (alloc_obstack);
1301       CLEAR_REG_SET (vector[i]);
1302     }
1303 }
1304
1305 /* Compute the registers live at the beginning of a basic block
1306    from those live at the end.
1307
1308    When called, OLD contains those live at the end.
1309    On return, it contains those live at the beginning.
1310    FIRST and LAST are the first and last insns of the basic block.
1311
1312    FINAL is nonzero if we are doing the final pass which is not
1313    for computing the life info (since that has already been done)
1314    but for acting on it.  On this pass, we delete dead stores,
1315    set up the logical links and dead-variables lists of instructions,
1316    and merge instructions for autoincrement and autodecrement addresses.
1317
1318    SIGNIFICANT is nonzero only the first time for each basic block.
1319    If it is nonzero, it points to a regset in which we store
1320    a 1 for each register that is set within the block.
1321
1322    BNUM is the number of the basic block.  */
1323
1324 static void
1325 propagate_block (old, first, last, final, significant, bnum)
1326      register regset old;
1327      rtx first;
1328      rtx last;
1329      int final;
1330      regset significant;
1331      int bnum;
1332 {
1333   register rtx insn;
1334   rtx prev;
1335   regset live;
1336   regset dead;
1337
1338   /* The following variables are used only if FINAL is nonzero.  */
1339   /* This vector gets one element for each reg that has been live
1340      at any point in the basic block that has been scanned so far.
1341      SOMETIMES_MAX says how many elements are in use so far.  */
1342   register int *regs_sometimes_live;
1343   int sometimes_max = 0;
1344   /* This regset has 1 for each reg that we have seen live so far.
1345      It and REGS_SOMETIMES_LIVE are updated together.  */
1346   regset maxlive;
1347
1348   /* The loop depth may change in the middle of a basic block.  Since we
1349      scan from end to beginning, we start with the depth at the end of the
1350      current basic block, and adjust as we pass ends and starts of loops.  */
1351   loop_depth = basic_block_loop_depth[bnum];
1352
1353   dead = ALLOCA_REG_SET ();
1354   live = ALLOCA_REG_SET ();
1355
1356   cc0_live = 0;
1357   last_mem_set = 0;
1358
1359   /* Include any notes at the end of the block in the scan.
1360      This is in case the block ends with a call to setjmp.  */
1361
1362   while (NEXT_INSN (last) != 0 && GET_CODE (NEXT_INSN (last)) == NOTE)
1363     {
1364       /* Look for loop boundaries, we are going forward here.  */
1365       last = NEXT_INSN (last);
1366       if (NOTE_LINE_NUMBER (last) == NOTE_INSN_LOOP_BEG)
1367         loop_depth++;
1368       else if (NOTE_LINE_NUMBER (last) == NOTE_INSN_LOOP_END)
1369         loop_depth--;
1370     }
1371
1372   if (final)
1373     {
1374       register int i;
1375
1376       num_scratch = 0;
1377       maxlive = ALLOCA_REG_SET ();
1378       COPY_REG_SET (maxlive, old);
1379       regs_sometimes_live = (int *) alloca (max_regno * sizeof (int));
1380
1381       /* Process the regs live at the end of the block.
1382          Enter them in MAXLIVE and REGS_SOMETIMES_LIVE.
1383          Also mark them as not local to any one basic block. */
1384       EXECUTE_IF_SET_IN_REG_SET (old, 0, i,
1385                                  {
1386                                    REG_BASIC_BLOCK (i) = REG_BLOCK_GLOBAL;
1387                                    regs_sometimes_live[sometimes_max] = i;
1388                                    sometimes_max++;
1389                                  });
1390     }
1391
1392   /* Scan the block an insn at a time from end to beginning.  */
1393
1394   for (insn = last; ; insn = prev)
1395     {
1396       prev = PREV_INSN (insn);
1397
1398       if (GET_CODE (insn) == NOTE)
1399         {
1400           /* Look for loop boundaries, remembering that we are going
1401              backwards.  */
1402           if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END)
1403             loop_depth++;
1404           else if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG)
1405             loop_depth--;
1406
1407           /* If we have LOOP_DEPTH == 0, there has been a bookkeeping error. 
1408              Abort now rather than setting register status incorrectly.  */
1409           if (loop_depth == 0)
1410             abort ();
1411
1412           /* If this is a call to `setjmp' et al,
1413              warn if any non-volatile datum is live.  */
1414
1415           if (final && NOTE_LINE_NUMBER (insn) == NOTE_INSN_SETJMP)
1416             IOR_REG_SET (regs_live_at_setjmp, old);
1417         }
1418
1419       /* Update the life-status of regs for this insn.
1420          First DEAD gets which regs are set in this insn
1421          then LIVE gets which regs are used in this insn.
1422          Then the regs live before the insn
1423          are those live after, with DEAD regs turned off,
1424          and then LIVE regs turned on.  */
1425
1426       else if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
1427         {
1428           register int i;
1429           rtx note = find_reg_note (insn, REG_RETVAL, NULL_RTX);
1430           int insn_is_dead
1431             = (insn_dead_p (PATTERN (insn), old, 0)
1432                /* Don't delete something that refers to volatile storage!  */
1433                && ! INSN_VOLATILE (insn));
1434           int libcall_is_dead 
1435             = (insn_is_dead && note != 0
1436                && libcall_dead_p (PATTERN (insn), old, note, insn));
1437
1438           /* If an instruction consists of just dead store(s) on final pass,
1439              "delete" it by turning it into a NOTE of type NOTE_INSN_DELETED.
1440              We could really delete it with delete_insn, but that
1441              can cause trouble for first or last insn in a basic block.  */
1442           if (final && insn_is_dead)
1443             {
1444               PUT_CODE (insn, NOTE);
1445               NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
1446               NOTE_SOURCE_FILE (insn) = 0;
1447
1448               /* CC0 is now known to be dead.  Either this insn used it,
1449                  in which case it doesn't anymore, or clobbered it,
1450                  so the next insn can't use it.  */
1451               cc0_live = 0;
1452
1453               /* If this insn is copying the return value from a library call,
1454                  delete the entire library call.  */
1455               if (libcall_is_dead)
1456                 {
1457                   rtx first = XEXP (note, 0);
1458                   rtx p = insn;
1459                   while (INSN_DELETED_P (first))
1460                     first = NEXT_INSN (first);
1461                   while (p != first)
1462                     {
1463                       p = PREV_INSN (p);
1464                       PUT_CODE (p, NOTE);
1465                       NOTE_LINE_NUMBER (p) = NOTE_INSN_DELETED;
1466                       NOTE_SOURCE_FILE (p) = 0;
1467                     }
1468                 }
1469               goto flushed;
1470             }
1471
1472           CLEAR_REG_SET (dead);
1473           CLEAR_REG_SET (live);
1474
1475           /* See if this is an increment or decrement that can be
1476              merged into a following memory address.  */
1477 #ifdef AUTO_INC_DEC
1478           {
1479             register rtx x = PATTERN (insn);
1480             /* Does this instruction increment or decrement a register?  */
1481             if (final && GET_CODE (x) == SET
1482                 && GET_CODE (SET_DEST (x)) == REG
1483                 && (GET_CODE (SET_SRC (x)) == PLUS
1484                     || GET_CODE (SET_SRC (x)) == MINUS)
1485                 && XEXP (SET_SRC (x), 0) == SET_DEST (x)
1486                 && GET_CODE (XEXP (SET_SRC (x), 1)) == CONST_INT
1487                 /* Ok, look for a following memory ref we can combine with.
1488                    If one is found, change the memory ref to a PRE_INC
1489                    or PRE_DEC, cancel this insn, and return 1.
1490                    Return 0 if nothing has been done.  */
1491                 && try_pre_increment_1 (insn))
1492               goto flushed;
1493           }
1494 #endif /* AUTO_INC_DEC */
1495
1496           /* If this is not the final pass, and this insn is copying the
1497              value of a library call and it's dead, don't scan the
1498              insns that perform the library call, so that the call's
1499              arguments are not marked live.  */
1500           if (libcall_is_dead)
1501             {
1502               /* Mark the dest reg as `significant'.  */
1503               mark_set_regs (old, dead, PATTERN (insn), NULL_RTX, significant);
1504
1505               insn = XEXP (note, 0);
1506               prev = PREV_INSN (insn);
1507             }
1508           else if (GET_CODE (PATTERN (insn)) == SET
1509                    && SET_DEST (PATTERN (insn)) == stack_pointer_rtx
1510                    && GET_CODE (SET_SRC (PATTERN (insn))) == PLUS
1511                    && XEXP (SET_SRC (PATTERN (insn)), 0) == stack_pointer_rtx
1512                    && GET_CODE (XEXP (SET_SRC (PATTERN (insn)), 1)) == CONST_INT)
1513             /* We have an insn to pop a constant amount off the stack.
1514                (Such insns use PLUS regardless of the direction of the stack,
1515                and any insn to adjust the stack by a constant is always a pop.)
1516                These insns, if not dead stores, have no effect on life.  */
1517             ;
1518           else
1519             {
1520               /* LIVE gets the regs used in INSN;
1521                  DEAD gets those set by it.  Dead insns don't make anything
1522                  live.  */
1523
1524               mark_set_regs (old, dead, PATTERN (insn),
1525                              final ? insn : NULL_RTX, significant);
1526
1527               /* If an insn doesn't use CC0, it becomes dead since we 
1528                  assume that every insn clobbers it.  So show it dead here;
1529                  mark_used_regs will set it live if it is referenced.  */
1530               cc0_live = 0;
1531
1532               if (! insn_is_dead)
1533                 mark_used_regs (old, live, PATTERN (insn), final, insn);
1534
1535               /* Sometimes we may have inserted something before INSN (such as
1536                  a move) when we make an auto-inc.  So ensure we will scan
1537                  those insns.  */
1538 #ifdef AUTO_INC_DEC
1539               prev = PREV_INSN (insn);
1540 #endif
1541
1542               if (! insn_is_dead && GET_CODE (insn) == CALL_INSN)
1543                 {
1544                   register int i;
1545
1546                   rtx note;
1547
1548                   for (note = CALL_INSN_FUNCTION_USAGE (insn);
1549                        note;
1550                        note = XEXP (note, 1))
1551                     if (GET_CODE (XEXP (note, 0)) == USE)
1552                       mark_used_regs (old, live, SET_DEST (XEXP (note, 0)),
1553                                       final, insn);
1554
1555                   /* Each call clobbers all call-clobbered regs that are not
1556                      global or fixed.  Note that the function-value reg is a
1557                      call-clobbered reg, and mark_set_regs has already had
1558                      a chance to handle it.  */
1559
1560                   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1561                     if (call_used_regs[i] && ! global_regs[i]
1562                         && ! fixed_regs[i])
1563                       SET_REGNO_REG_SET (dead, i);
1564
1565                   /* The stack ptr is used (honorarily) by a CALL insn.  */
1566                   SET_REGNO_REG_SET (live, STACK_POINTER_REGNUM);
1567
1568                   /* Calls may also reference any of the global registers,
1569                      so they are made live.  */
1570                   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1571                     if (global_regs[i])
1572                       mark_used_regs (old, live,
1573                                       gen_rtx (REG, reg_raw_mode[i], i),
1574                                       final, insn);
1575
1576                   /* Calls also clobber memory.  */
1577                   last_mem_set = 0;
1578                 }
1579
1580               /* Update OLD for the registers used or set.  */
1581               AND_COMPL_REG_SET (old, dead);
1582               IOR_REG_SET (old, live);
1583
1584               if (GET_CODE (insn) == CALL_INSN && final)
1585                 {
1586                   /* Any regs live at the time of a call instruction
1587                      must not go in a register clobbered by calls.
1588                      Find all regs now live and record this for them.  */
1589
1590                   register int *p = regs_sometimes_live;
1591
1592                   for (i = 0; i < sometimes_max; i++, p++)
1593                     if (REGNO_REG_SET_P (old, *p))
1594                       REG_N_CALLS_CROSSED (*p)++;
1595                 }
1596             }
1597
1598           /* On final pass, add any additional sometimes-live regs
1599              into MAXLIVE and REGS_SOMETIMES_LIVE.
1600              Also update counts of how many insns each reg is live at.  */
1601
1602           if (final)
1603             {
1604               register int regno;
1605               register int *p;
1606
1607               EXECUTE_IF_AND_COMPL_IN_REG_SET (live, maxlive, 0, regno,
1608                                                {
1609                                                  regs_sometimes_live[sometimes_max++] = regno;
1610                                                  SET_REGNO_REG_SET (maxlive, regno);
1611                                                });
1612
1613               p = regs_sometimes_live;
1614               for (i = 0; i < sometimes_max; i++)
1615                 {
1616                   regno = *p++;
1617                   if (REGNO_REG_SET_P (old, regno))
1618                     REG_LIVE_LENGTH (regno)++;
1619                 }
1620             }
1621         }
1622     flushed: ;
1623       if (insn == first)
1624         break;
1625     }
1626
1627   if (num_scratch > max_scratch)
1628     max_scratch = num_scratch;
1629 }
1630 \f
1631 /* Return 1 if X (the body of an insn, or part of it) is just dead stores
1632    (SET expressions whose destinations are registers dead after the insn).
1633    NEEDED is the regset that says which regs are alive after the insn.
1634
1635    Unless CALL_OK is non-zero, an insn is needed if it contains a CALL.  */
1636
1637 static int
1638 insn_dead_p (x, needed, call_ok)
1639      rtx x;
1640      regset needed;
1641      int call_ok;
1642 {
1643   register RTX_CODE code = GET_CODE (x);
1644   /* If setting something that's a reg or part of one,
1645      see if that register's altered value will be live.  */
1646
1647   if (code == SET)
1648     {
1649       register rtx r = SET_DEST (x);
1650       /* A SET that is a subroutine call cannot be dead.  */
1651       if (! call_ok && GET_CODE (SET_SRC (x)) == CALL)
1652         return 0;
1653
1654 #ifdef HAVE_cc0
1655       if (GET_CODE (r) == CC0)
1656         return ! cc0_live;
1657 #endif
1658       
1659       if (GET_CODE (r) == MEM && last_mem_set && ! MEM_VOLATILE_P (r)
1660           && rtx_equal_p (r, last_mem_set))
1661         return 1;
1662
1663       while (GET_CODE (r) == SUBREG
1664              || GET_CODE (r) == STRICT_LOW_PART
1665              || GET_CODE (r) == ZERO_EXTRACT
1666              || GET_CODE (r) == SIGN_EXTRACT)
1667         r = SUBREG_REG (r);
1668
1669       if (GET_CODE (r) == REG)
1670         {
1671           register int regno = REGNO (r);
1672
1673           /* Don't delete insns to set global regs.  */
1674           if ((regno < FIRST_PSEUDO_REGISTER && global_regs[regno])
1675               /* Make sure insns to set frame pointer aren't deleted.  */
1676               || regno == FRAME_POINTER_REGNUM
1677 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
1678               || regno == HARD_FRAME_POINTER_REGNUM
1679 #endif
1680 #if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
1681               /* Make sure insns to set arg pointer are never deleted
1682                  (if the arg pointer isn't fixed, there will be a USE for
1683                  it, so we can treat it normally).  */
1684               || (regno == ARG_POINTER_REGNUM && fixed_regs[regno])
1685 #endif
1686               || REGNO_REG_SET_P (needed, regno))
1687             return 0;
1688
1689           /* If this is a hard register, verify that subsequent words are
1690              not needed.  */
1691           if (regno < FIRST_PSEUDO_REGISTER)
1692             {
1693               int n = HARD_REGNO_NREGS (regno, GET_MODE (r));
1694
1695               while (--n > 0)
1696                 if (REGNO_REG_SET_P (needed, regno+n))
1697                   return 0;
1698             }
1699
1700           return 1;
1701         }
1702     }
1703   /* If performing several activities,
1704      insn is dead if each activity is individually dead.
1705      Also, CLOBBERs and USEs can be ignored; a CLOBBER or USE
1706      that's inside a PARALLEL doesn't make the insn worth keeping.  */
1707   else if (code == PARALLEL)
1708     {
1709       register int i = XVECLEN (x, 0);
1710       for (i--; i >= 0; i--)
1711         {
1712           rtx elt = XVECEXP (x, 0, i);
1713           if (!insn_dead_p (elt, needed, call_ok)
1714               && GET_CODE (elt) != CLOBBER
1715               && GET_CODE (elt) != USE)
1716             return 0;
1717         }
1718       return 1;
1719     }
1720   /* We do not check CLOBBER or USE here.
1721      An insn consisting of just a CLOBBER or just a USE
1722      should not be deleted.  */
1723   return 0;
1724 }
1725
1726 /* If X is the pattern of the last insn in a libcall, and assuming X is dead,
1727    return 1 if the entire library call is dead.
1728    This is true if X copies a register (hard or pseudo)
1729    and if the hard return  reg of the call insn is dead.
1730    (The caller should have tested the destination of X already for death.)
1731
1732    If this insn doesn't just copy a register, then we don't
1733    have an ordinary libcall.  In that case, cse could not have
1734    managed to substitute the source for the dest later on,
1735    so we can assume the libcall is dead.
1736
1737    NEEDED is the bit vector of pseudoregs live before this insn.
1738    NOTE is the REG_RETVAL note of the insn.  INSN is the insn itself.  */
1739
1740 static int
1741 libcall_dead_p (x, needed, note, insn)
1742      rtx x;
1743      regset needed;
1744      rtx note;
1745      rtx insn;
1746 {
1747   register RTX_CODE code = GET_CODE (x);
1748
1749   if (code == SET)
1750     {
1751       register rtx r = SET_SRC (x);
1752       if (GET_CODE (r) == REG)
1753         {
1754           rtx call = XEXP (note, 0);
1755           register int i;
1756
1757           /* Find the call insn.  */
1758           while (call != insn && GET_CODE (call) != CALL_INSN)
1759             call = NEXT_INSN (call);
1760
1761           /* If there is none, do nothing special,
1762              since ordinary death handling can understand these insns.  */
1763           if (call == insn)
1764             return 0;
1765
1766           /* See if the hard reg holding the value is dead.
1767              If this is a PARALLEL, find the call within it.  */
1768           call = PATTERN (call);
1769           if (GET_CODE (call) == PARALLEL)
1770             {
1771               for (i = XVECLEN (call, 0) - 1; i >= 0; i--)
1772                 if (GET_CODE (XVECEXP (call, 0, i)) == SET
1773                     && GET_CODE (SET_SRC (XVECEXP (call, 0, i))) == CALL)
1774                   break;
1775
1776               /* This may be a library call that is returning a value
1777                  via invisible pointer.  Do nothing special, since
1778                  ordinary death handling can understand these insns.  */
1779               if (i < 0)
1780                 return 0;
1781
1782               call = XVECEXP (call, 0, i);
1783             }
1784
1785           return insn_dead_p (call, needed, 1);
1786         }
1787     }
1788   return 1;
1789 }
1790
1791 /* Return 1 if register REGNO was used before it was set.
1792    In other words, if it is live at function entry.
1793    Don't count global register variables or variables in registers
1794    that can be used for function arg passing, though.  */
1795
1796 int
1797 regno_uninitialized (regno)
1798      int regno;
1799 {
1800   if (n_basic_blocks == 0
1801       || (regno < FIRST_PSEUDO_REGISTER
1802           && (global_regs[regno] || FUNCTION_ARG_REGNO_P (regno))))
1803     return 0;
1804
1805   return REGNO_REG_SET_P (basic_block_live_at_start[0], regno);
1806 }
1807
1808 /* 1 if register REGNO was alive at a place where `setjmp' was called
1809    and was set more than once or is an argument.
1810    Such regs may be clobbered by `longjmp'.  */
1811
1812 int
1813 regno_clobbered_at_setjmp (regno)
1814      int regno;
1815 {
1816   if (n_basic_blocks == 0)
1817     return 0;
1818
1819   return ((REG_N_SETS (regno) > 1
1820            || REGNO_REG_SET_P (basic_block_live_at_start[0], regno))
1821           && REGNO_REG_SET_P (regs_live_at_setjmp, regno));
1822 }
1823 \f
1824 /* Process the registers that are set within X.
1825    Their bits are set to 1 in the regset DEAD,
1826    because they are dead prior to this insn.
1827
1828    If INSN is nonzero, it is the insn being processed
1829    and the fact that it is nonzero implies this is the FINAL pass
1830    in propagate_block.  In this case, various info about register
1831    usage is stored, LOG_LINKS fields of insns are set up.  */
1832
1833 static void
1834 mark_set_regs (needed, dead, x, insn, significant)
1835      regset needed;
1836      regset dead;
1837      rtx x;
1838      rtx insn;
1839      regset significant;
1840 {
1841   register RTX_CODE code = GET_CODE (x);
1842
1843   if (code == SET || code == CLOBBER)
1844     mark_set_1 (needed, dead, x, insn, significant);
1845   else if (code == PARALLEL)
1846     {
1847       register int i;
1848       for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
1849         {
1850           code = GET_CODE (XVECEXP (x, 0, i));
1851           if (code == SET || code == CLOBBER)
1852             mark_set_1 (needed, dead, XVECEXP (x, 0, i), insn, significant);
1853         }
1854     }
1855 }
1856
1857 /* Process a single SET rtx, X.  */
1858
1859 static void
1860 mark_set_1 (needed, dead, x, insn, significant)
1861      regset needed;
1862      regset dead;
1863      rtx x;
1864      rtx insn;
1865      regset significant;
1866 {
1867   register int regno;
1868   register rtx reg = SET_DEST (x);
1869
1870   /* Modifying just one hardware register of a multi-reg value
1871      or just a byte field of a register
1872      does not mean the value from before this insn is now dead.
1873      But it does mean liveness of that register at the end of the block
1874      is significant.
1875
1876      Within mark_set_1, however, we treat it as if the register is
1877      indeed modified.  mark_used_regs will, however, also treat this
1878      register as being used.  Thus, we treat these insns as setting a
1879      new value for the register as a function of its old value.  This
1880      cases LOG_LINKS to be made appropriately and this will help combine.  */
1881
1882   while (GET_CODE (reg) == SUBREG || GET_CODE (reg) == ZERO_EXTRACT
1883          || GET_CODE (reg) == SIGN_EXTRACT
1884          || GET_CODE (reg) == STRICT_LOW_PART)
1885     reg = XEXP (reg, 0);
1886
1887   /* If we are writing into memory or into a register mentioned in the
1888      address of the last thing stored into memory, show we don't know
1889      what the last store was.  If we are writing memory, save the address
1890      unless it is volatile.  */
1891   if (GET_CODE (reg) == MEM
1892       || (GET_CODE (reg) == REG
1893           && last_mem_set != 0 && reg_overlap_mentioned_p (reg, last_mem_set)))
1894     last_mem_set = 0;
1895     
1896   if (GET_CODE (reg) == MEM && ! side_effects_p (reg)
1897       /* There are no REG_INC notes for SP, so we can't assume we'll see 
1898          everything that invalidates it.  To be safe, don't eliminate any
1899          stores though SP; none of them should be redundant anyway.  */
1900       && ! reg_mentioned_p (stack_pointer_rtx, reg))
1901     last_mem_set = reg;
1902
1903   if (GET_CODE (reg) == REG
1904       && (regno = REGNO (reg), regno != FRAME_POINTER_REGNUM)
1905 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
1906       && regno != HARD_FRAME_POINTER_REGNUM
1907 #endif
1908 #if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
1909       && ! (regno == ARG_POINTER_REGNUM && fixed_regs[regno])
1910 #endif
1911       && ! (regno < FIRST_PSEUDO_REGISTER && global_regs[regno]))
1912     /* && regno != STACK_POINTER_REGNUM) -- let's try without this.  */
1913     {
1914       int some_needed = REGNO_REG_SET_P (needed, regno);
1915       int some_not_needed = ! some_needed;
1916
1917       /* Mark it as a significant register for this basic block.  */
1918       if (significant)
1919         SET_REGNO_REG_SET (significant, regno);
1920
1921       /* Mark it as as dead before this insn.  */
1922       SET_REGNO_REG_SET (dead, regno);
1923
1924       /* A hard reg in a wide mode may really be multiple registers.
1925          If so, mark all of them just like the first.  */
1926       if (regno < FIRST_PSEUDO_REGISTER)
1927         {
1928           int n;
1929
1930           /* Nothing below is needed for the stack pointer; get out asap.
1931              Eg, log links aren't needed, since combine won't use them.  */
1932           if (regno == STACK_POINTER_REGNUM)
1933             return;
1934
1935           n = HARD_REGNO_NREGS (regno, GET_MODE (reg));
1936           while (--n > 0)
1937             {
1938               int regno_n = regno + n;
1939               int needed_regno = REGNO_REG_SET_P (needed, regno_n);
1940               if (significant)
1941                 SET_REGNO_REG_SET (significant, regno_n);
1942
1943               SET_REGNO_REG_SET (dead, regno_n);
1944               some_needed |= needed_regno;
1945               some_not_needed |= ! needed_regno;
1946             }
1947         }
1948       /* Additional data to record if this is the final pass.  */
1949       if (insn)
1950         {
1951           register rtx y = reg_next_use[regno];
1952           register int blocknum = BLOCK_NUM (insn);
1953
1954           /* If this is a hard reg, record this function uses the reg.  */
1955
1956           if (regno < FIRST_PSEUDO_REGISTER)
1957             {
1958               register int i;
1959               int endregno = regno + HARD_REGNO_NREGS (regno, GET_MODE (reg));
1960
1961               for (i = regno; i < endregno; i++)
1962                 {
1963                   /* The next use is no longer "next", since a store
1964                      intervenes.  */
1965                   reg_next_use[i] = 0;
1966
1967                   regs_ever_live[i] = 1;
1968                   REG_N_SETS (i)++;
1969                 }
1970             }
1971           else
1972             {
1973               /* The next use is no longer "next", since a store
1974                  intervenes.  */
1975               reg_next_use[regno] = 0;
1976
1977               /* Keep track of which basic blocks each reg appears in.  */
1978
1979               if (REG_BASIC_BLOCK (regno) == REG_BLOCK_UNKNOWN)
1980                 REG_BASIC_BLOCK (regno) = blocknum;
1981               else if (REG_BASIC_BLOCK (regno) != blocknum)
1982                 REG_BASIC_BLOCK (regno) = REG_BLOCK_GLOBAL;
1983
1984               /* Count (weighted) references, stores, etc.  This counts a
1985                  register twice if it is modified, but that is correct.  */
1986               REG_N_SETS (regno)++;
1987
1988               REG_N_REFS (regno) += loop_depth;
1989                   
1990               /* The insns where a reg is live are normally counted
1991                  elsewhere, but we want the count to include the insn
1992                  where the reg is set, and the normal counting mechanism
1993                  would not count it.  */
1994               REG_LIVE_LENGTH (regno)++;
1995             }
1996
1997           if (! some_not_needed)
1998             {
1999               /* Make a logical link from the next following insn
2000                  that uses this register, back to this insn.
2001                  The following insns have already been processed.
2002
2003                  We don't build a LOG_LINK for hard registers containing
2004                  in ASM_OPERANDs.  If these registers get replaced,
2005                  we might wind up changing the semantics of the insn,
2006                  even if reload can make what appear to be valid assignments
2007                  later.  */
2008               if (y && (BLOCK_NUM (y) == blocknum)
2009                   && (regno >= FIRST_PSEUDO_REGISTER
2010                       || asm_noperands (PATTERN (y)) < 0))
2011                 LOG_LINKS (y)
2012                   = gen_rtx (INSN_LIST, VOIDmode, insn, LOG_LINKS (y));
2013             }
2014           else if (! some_needed)
2015             {
2016               /* Note that dead stores have already been deleted when possible
2017                  If we get here, we have found a dead store that cannot
2018                  be eliminated (because the same insn does something useful).
2019                  Indicate this by marking the reg being set as dying here.  */
2020               REG_NOTES (insn)
2021                 = gen_rtx (EXPR_LIST, REG_UNUSED, reg, REG_NOTES (insn));
2022               REG_N_DEATHS (REGNO (reg))++;
2023             }
2024           else
2025             {
2026               /* This is a case where we have a multi-word hard register
2027                  and some, but not all, of the words of the register are
2028                  needed in subsequent insns.  Write REG_UNUSED notes
2029                  for those parts that were not needed.  This case should
2030                  be rare.  */
2031
2032               int i;
2033
2034               for (i = HARD_REGNO_NREGS (regno, GET_MODE (reg)) - 1;
2035                    i >= 0; i--)
2036                 if (!REGNO_REG_SET_P (needed, regno + i))
2037                   REG_NOTES (insn)
2038                     = gen_rtx (EXPR_LIST, REG_UNUSED,
2039                                gen_rtx (REG, reg_raw_mode[regno + i],
2040                                         regno + i),
2041                                REG_NOTES (insn));
2042             }
2043         }
2044     }
2045   else if (GET_CODE (reg) == REG)
2046     reg_next_use[regno] = 0;
2047
2048   /* If this is the last pass and this is a SCRATCH, show it will be dying
2049      here and count it.  */
2050   else if (GET_CODE (reg) == SCRATCH && insn != 0)
2051     {
2052       REG_NOTES (insn)
2053         = gen_rtx (EXPR_LIST, REG_UNUSED, reg, REG_NOTES (insn));
2054       num_scratch++;
2055     }
2056 }
2057 \f
2058 #ifdef AUTO_INC_DEC
2059
2060 /* X is a MEM found in INSN.  See if we can convert it into an auto-increment
2061    reference.  */
2062
2063 static void
2064 find_auto_inc (needed, x, insn)
2065      regset needed;
2066      rtx x;
2067      rtx insn;
2068 {
2069   rtx addr = XEXP (x, 0);
2070   HOST_WIDE_INT offset = 0;
2071   rtx set;
2072
2073   /* Here we detect use of an index register which might be good for
2074      postincrement, postdecrement, preincrement, or predecrement.  */
2075
2076   if (GET_CODE (addr) == PLUS && GET_CODE (XEXP (addr, 1)) == CONST_INT)
2077     offset = INTVAL (XEXP (addr, 1)), addr = XEXP (addr, 0);
2078
2079   if (GET_CODE (addr) == REG)
2080     {
2081       register rtx y;
2082       register int size = GET_MODE_SIZE (GET_MODE (x));
2083       rtx use;
2084       rtx incr;
2085       int regno = REGNO (addr);
2086
2087       /* Is the next use an increment that might make auto-increment? */
2088       if ((incr = reg_next_use[regno]) != 0
2089           && (set = single_set (incr)) != 0
2090           && GET_CODE (set) == SET
2091           && BLOCK_NUM (incr) == BLOCK_NUM (insn)
2092           /* Can't add side effects to jumps; if reg is spilled and
2093              reloaded, there's no way to store back the altered value.  */
2094           && GET_CODE (insn) != JUMP_INSN
2095           && (y = SET_SRC (set), GET_CODE (y) == PLUS)
2096           && XEXP (y, 0) == addr
2097           && GET_CODE (XEXP (y, 1)) == CONST_INT
2098           && (0
2099 #ifdef HAVE_POST_INCREMENT
2100               || (INTVAL (XEXP (y, 1)) == size && offset == 0)
2101 #endif
2102 #ifdef HAVE_POST_DECREMENT
2103               || (INTVAL (XEXP (y, 1)) == - size && offset == 0)
2104 #endif
2105 #ifdef HAVE_PRE_INCREMENT
2106               || (INTVAL (XEXP (y, 1)) == size && offset == size)
2107 #endif
2108 #ifdef HAVE_PRE_DECREMENT
2109               || (INTVAL (XEXP (y, 1)) == - size && offset == - size)
2110 #endif
2111               )
2112           /* Make sure this reg appears only once in this insn.  */
2113           && (use = find_use_as_address (PATTERN (insn), addr, offset),
2114               use != 0 && use != (rtx) 1))
2115         {
2116           rtx q = SET_DEST (set);
2117           enum rtx_code inc_code = (INTVAL (XEXP (y, 1)) == size
2118                                     ? (offset ? PRE_INC : POST_INC)
2119                                     : (offset ? PRE_DEC : POST_DEC));
2120
2121           if (dead_or_set_p (incr, addr))
2122             {
2123               /* This is the simple case.  Try to make the auto-inc.  If
2124                  we can't, we are done.  Otherwise, we will do any
2125                  needed updates below.  */
2126               if (! validate_change (insn, &XEXP (x, 0),
2127                                      gen_rtx (inc_code, Pmode, addr),
2128                                      0))
2129                 return;
2130             }
2131           else if (GET_CODE (q) == REG
2132                    /* PREV_INSN used here to check the semi-open interval
2133                       [insn,incr).  */
2134                    && ! reg_used_between_p (q,  PREV_INSN (insn), incr)
2135                    /* We must also check for sets of q as q may be
2136                       a call clobbered hard register and there may
2137                       be a call between PREV_INSN (insn) and incr.  */
2138                    && ! reg_set_between_p (q,  PREV_INSN (insn), incr))
2139             {
2140               /* We have *p followed sometime later by q = p+size.
2141                  Both p and q must be live afterward,
2142                  and q is not used between INSN and it's assignment.
2143                  Change it to q = p, ...*q..., q = q+size.
2144                  Then fall into the usual case.  */
2145               rtx insns, temp;
2146
2147               start_sequence ();
2148               emit_move_insn (q, addr);
2149               insns = get_insns ();
2150               end_sequence ();
2151
2152               /* If anything in INSNS have UID's that don't fit within the
2153                  extra space we allocate earlier, we can't make this auto-inc.
2154                  This should never happen.  */
2155               for (temp = insns; temp; temp = NEXT_INSN (temp))
2156                 {
2157                   if (INSN_UID (temp) > max_uid_for_flow)
2158                     return;
2159                   BLOCK_NUM (temp) = BLOCK_NUM (insn);
2160                 }
2161
2162               /* If we can't make the auto-inc, or can't make the
2163                  replacement into Y, exit.  There's no point in making
2164                  the change below if we can't do the auto-inc and doing
2165                  so is not correct in the pre-inc case.  */
2166
2167               validate_change (insn, &XEXP (x, 0),
2168                                gen_rtx (inc_code, Pmode, q),
2169                                1);
2170               validate_change (incr, &XEXP (y, 0), q, 1);
2171               if (! apply_change_group ())
2172                 return;
2173
2174               /* We now know we'll be doing this change, so emit the
2175                  new insn(s) and do the updates.  */
2176               emit_insns_before (insns, insn);
2177
2178               if (basic_block_head[BLOCK_NUM (insn)] == insn)
2179                 basic_block_head[BLOCK_NUM (insn)] = insns;
2180
2181               /* INCR will become a NOTE and INSN won't contain a
2182                  use of ADDR.  If a use of ADDR was just placed in
2183                  the insn before INSN, make that the next use. 
2184                  Otherwise, invalidate it.  */
2185               if (GET_CODE (PREV_INSN (insn)) == INSN
2186                   && GET_CODE (PATTERN (PREV_INSN (insn))) == SET
2187                   && SET_SRC (PATTERN (PREV_INSN (insn))) == addr)
2188                 reg_next_use[regno] = PREV_INSN (insn);
2189               else
2190                 reg_next_use[regno] = 0;
2191
2192               addr = q;
2193               regno = REGNO (q);
2194
2195               /* REGNO is now used in INCR which is below INSN, but
2196                  it previously wasn't live here.  If we don't mark
2197                  it as needed, we'll put a REG_DEAD note for it
2198                  on this insn, which is incorrect.  */
2199               SET_REGNO_REG_SET (needed, regno);
2200
2201               /* If there are any calls between INSN and INCR, show
2202                  that REGNO now crosses them.  */
2203               for (temp = insn; temp != incr; temp = NEXT_INSN (temp))
2204                 if (GET_CODE (temp) == CALL_INSN)
2205                   REG_N_CALLS_CROSSED (regno)++;
2206             }
2207           else
2208             return;
2209
2210           /* If we haven't returned, it means we were able to make the
2211              auto-inc, so update the status.  First, record that this insn
2212              has an implicit side effect.  */
2213
2214           REG_NOTES (insn)
2215             = gen_rtx (EXPR_LIST, REG_INC, addr, REG_NOTES (insn));
2216
2217           /* Modify the old increment-insn to simply copy
2218              the already-incremented value of our register.  */
2219           if (! validate_change (incr, &SET_SRC (set), addr, 0))
2220             abort ();
2221
2222           /* If that makes it a no-op (copying the register into itself) delete
2223              it so it won't appear to be a "use" and a "set" of this
2224              register.  */
2225           if (SET_DEST (set) == addr)
2226             {
2227               PUT_CODE (incr, NOTE);
2228               NOTE_LINE_NUMBER (incr) = NOTE_INSN_DELETED;
2229               NOTE_SOURCE_FILE (incr) = 0;
2230             }
2231
2232           if (regno >= FIRST_PSEUDO_REGISTER)
2233             {
2234               /* Count an extra reference to the reg.  When a reg is
2235                  incremented, spilling it is worse, so we want to make
2236                  that less likely.  */
2237               REG_N_REFS (regno) += loop_depth;
2238
2239               /* Count the increment as a setting of the register,
2240                  even though it isn't a SET in rtl.  */
2241               REG_N_SETS (regno)++;
2242             }
2243         }
2244     }
2245 }
2246 #endif /* AUTO_INC_DEC */
2247 \f
2248 /* Scan expression X and store a 1-bit in LIVE for each reg it uses.
2249    This is done assuming the registers needed from X
2250    are those that have 1-bits in NEEDED.
2251
2252    On the final pass, FINAL is 1.  This means try for autoincrement
2253    and count the uses and deaths of each pseudo-reg.
2254
2255    INSN is the containing instruction.  If INSN is dead, this function is not
2256    called.  */
2257
2258 static void
2259 mark_used_regs (needed, live, x, final, insn)
2260      regset needed;
2261      regset live;
2262      rtx x;
2263      int final;
2264      rtx insn;
2265 {
2266   register RTX_CODE code;
2267   register int regno;
2268   int i;
2269
2270  retry:
2271   code = GET_CODE (x);
2272   switch (code)
2273     {
2274     case LABEL_REF:
2275     case SYMBOL_REF:
2276     case CONST_INT:
2277     case CONST:
2278     case CONST_DOUBLE:
2279     case PC:
2280     case ADDR_VEC:
2281     case ADDR_DIFF_VEC:
2282     case ASM_INPUT:
2283       return;
2284
2285 #ifdef HAVE_cc0
2286     case CC0:
2287       cc0_live = 1;
2288       return;
2289 #endif
2290
2291     case CLOBBER:
2292       /* If we are clobbering a MEM, mark any registers inside the address
2293          as being used.  */
2294       if (GET_CODE (XEXP (x, 0)) == MEM)
2295         mark_used_regs (needed, live, XEXP (XEXP (x, 0), 0), final, insn);
2296       return;
2297
2298     case MEM:
2299       /* CYGNUS LOCAL dje/8176 */
2300       /* Invalidate the data for the last MEM stored, but only if MEM is
2301          something that can be stored into.  */
2302       if (GET_CODE (XEXP (x, 0)) == SYMBOL_REF
2303           && CONSTANT_POOL_ADDRESS_P (XEXP (x, 0)))
2304         ; /* needn't clear last_mem_set */
2305       else
2306         last_mem_set = 0;
2307       /* END CYGNUS LOCAL */
2308
2309 #ifdef AUTO_INC_DEC
2310       if (final)
2311         find_auto_inc (needed, x, insn);
2312 #endif
2313       break;
2314
2315     case SUBREG:
2316       if (GET_CODE (SUBREG_REG (x)) == REG
2317           && REGNO (SUBREG_REG (x)) >= FIRST_PSEUDO_REGISTER
2318           && (GET_MODE_SIZE (GET_MODE (x))
2319               != GET_MODE_SIZE (GET_MODE (SUBREG_REG (x)))))
2320         REG_CHANGES_SIZE (REGNO (SUBREG_REG (x))) = 1;
2321
2322       /* While we're here, optimize this case.  */
2323       x = SUBREG_REG (x);
2324
2325       /* In case the SUBREG is not of a register, don't optimize */
2326       if (GET_CODE (x) != REG)
2327         {
2328           mark_used_regs (needed, live, x, final, insn);
2329           return;
2330         }
2331
2332       /* ... fall through ...  */
2333
2334     case REG:
2335       /* See a register other than being set
2336          => mark it as needed.  */
2337
2338       regno = REGNO (x);
2339       {
2340         REGSET_ELT_TYPE some_needed = REGNO_REG_SET_P (needed, regno);
2341         REGSET_ELT_TYPE some_not_needed = ! some_needed;
2342
2343         SET_REGNO_REG_SET (live, regno);
2344
2345         /* A hard reg in a wide mode may really be multiple registers.
2346            If so, mark all of them just like the first.  */
2347         if (regno < FIRST_PSEUDO_REGISTER)
2348           {
2349             int n;
2350
2351             /* For stack ptr or fixed arg pointer,
2352                nothing below can be necessary, so waste no more time.  */
2353             if (regno == STACK_POINTER_REGNUM
2354 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
2355                 || regno == HARD_FRAME_POINTER_REGNUM
2356 #endif
2357 #if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
2358                 || (regno == ARG_POINTER_REGNUM && fixed_regs[regno])
2359 #endif
2360                 || regno == FRAME_POINTER_REGNUM)
2361               {
2362                 /* If this is a register we are going to try to eliminate,
2363                    don't mark it live here.  If we are successful in
2364                    eliminating it, it need not be live unless it is used for
2365                    pseudos, in which case it will have been set live when
2366                    it was allocated to the pseudos.  If the register will not
2367                    be eliminated, reload will set it live at that point.  */
2368
2369                 if (! TEST_HARD_REG_BIT (elim_reg_set, regno))
2370                   regs_ever_live[regno] = 1;
2371                 return;
2372               }
2373             /* No death notes for global register variables;
2374                their values are live after this function exits.  */
2375             if (global_regs[regno])
2376               {
2377                 if (final)
2378                   reg_next_use[regno] = insn;
2379                 return;
2380               }
2381
2382             n = HARD_REGNO_NREGS (regno, GET_MODE (x));
2383             while (--n > 0)
2384               {
2385                 int regno_n = regno + n;
2386                 int needed_regno = REGNO_REG_SET_P (needed, regno_n);
2387
2388                 SET_REGNO_REG_SET (live, regno_n);
2389                 some_needed |= needed_regno;
2390                 some_not_needed != ! needed_regno;
2391               }
2392           }
2393         if (final)
2394           {
2395             /* Record where each reg is used, so when the reg
2396                is set we know the next insn that uses it.  */
2397
2398             reg_next_use[regno] = insn;
2399
2400             if (regno < FIRST_PSEUDO_REGISTER)
2401               {
2402                 /* If a hard reg is being used,
2403                    record that this function does use it.  */
2404
2405                 i = HARD_REGNO_NREGS (regno, GET_MODE (x));
2406                 if (i == 0)
2407                   i = 1;
2408                 do
2409                   regs_ever_live[regno + --i] = 1;
2410                 while (i > 0);
2411               }
2412             else
2413               {
2414                 /* Keep track of which basic block each reg appears in.  */
2415
2416                 register int blocknum = BLOCK_NUM (insn);
2417
2418                 if (REG_BASIC_BLOCK (regno) == REG_BLOCK_UNKNOWN)
2419                   REG_BASIC_BLOCK (regno) = blocknum;
2420                 else if (REG_BASIC_BLOCK (regno) != blocknum)
2421                   REG_BASIC_BLOCK (regno) = REG_BLOCK_GLOBAL;
2422
2423                 /* Count (weighted) number of uses of each reg.  */
2424
2425                 REG_N_REFS (regno) += loop_depth;
2426               }
2427
2428             /* Record and count the insns in which a reg dies.
2429                If it is used in this insn and was dead below the insn
2430                then it dies in this insn.  If it was set in this insn,
2431                we do not make a REG_DEAD note; likewise if we already
2432                made such a note.  */
2433
2434             if (some_not_needed
2435                 && ! dead_or_set_p (insn, x)
2436 #if 0
2437                 && (regno >= FIRST_PSEUDO_REGISTER || ! fixed_regs[regno])
2438 #endif
2439                 )
2440               {
2441                 /* Check for the case where the register dying partially
2442                    overlaps the register set by this insn.  */
2443                 if (regno < FIRST_PSEUDO_REGISTER
2444                     && HARD_REGNO_NREGS (regno, GET_MODE (x)) > 1)
2445                   {
2446                     int n = HARD_REGNO_NREGS (regno, GET_MODE (x));
2447                     while (--n >= 0)
2448                       some_needed |= dead_or_set_regno_p (insn, regno + n);
2449                   }
2450
2451                 /* If none of the words in X is needed, make a REG_DEAD
2452                    note.  Otherwise, we must make partial REG_DEAD notes.  */
2453                 if (! some_needed)
2454                   {
2455                     REG_NOTES (insn)
2456                       = gen_rtx (EXPR_LIST, REG_DEAD, x, REG_NOTES (insn));
2457                     REG_N_DEATHS (regno)++;
2458                   }
2459                 else
2460                   {
2461                     int i;
2462
2463                     /* Don't make a REG_DEAD note for a part of a register
2464                        that is set in the insn.  */
2465
2466                     for (i = HARD_REGNO_NREGS (regno, GET_MODE (x)) - 1;
2467                          i >= 0; i--)
2468                       if (!REGNO_REG_SET_P (needed, regno + i)
2469                           && ! dead_or_set_regno_p (insn, regno + i))
2470                         REG_NOTES (insn)
2471                           = gen_rtx (EXPR_LIST, REG_DEAD,
2472                                      gen_rtx (REG, reg_raw_mode[regno + i],
2473                                               regno + i),
2474                                      REG_NOTES (insn));
2475                   }
2476               }
2477           }
2478       }
2479       return;
2480
2481     case SET:
2482       {
2483         register rtx testreg = SET_DEST (x);
2484         int mark_dest = 0;
2485
2486         /* If storing into MEM, don't show it as being used.  But do
2487            show the address as being used.  */
2488         if (GET_CODE (testreg) == MEM)
2489           {
2490 #ifdef AUTO_INC_DEC
2491             if (final)
2492               find_auto_inc (needed, testreg, insn);
2493 #endif
2494             mark_used_regs (needed, live, XEXP (testreg, 0), final, insn);
2495             mark_used_regs (needed, live, SET_SRC (x), final, insn);
2496             return;
2497           }
2498             
2499         /* Storing in STRICT_LOW_PART is like storing in a reg
2500            in that this SET might be dead, so ignore it in TESTREG.
2501            but in some other ways it is like using the reg.
2502
2503            Storing in a SUBREG or a bit field is like storing the entire
2504            register in that if the register's value is not used
2505            then this SET is not needed.  */
2506         while (GET_CODE (testreg) == STRICT_LOW_PART
2507                || GET_CODE (testreg) == ZERO_EXTRACT
2508                || GET_CODE (testreg) == SIGN_EXTRACT
2509                || GET_CODE (testreg) == SUBREG)
2510           {
2511             if (GET_CODE (testreg) == SUBREG
2512                 && GET_CODE (SUBREG_REG (testreg)) == REG
2513                 && REGNO (SUBREG_REG (testreg)) >= FIRST_PSEUDO_REGISTER
2514                 && (GET_MODE_SIZE (GET_MODE (testreg))
2515                     != GET_MODE_SIZE (GET_MODE (SUBREG_REG (testreg)))))
2516               REG_CHANGES_SIZE (REGNO (SUBREG_REG (testreg))) = 1;
2517
2518             /* Modifying a single register in an alternate mode
2519                does not use any of the old value.  But these other
2520                ways of storing in a register do use the old value.  */
2521             if (GET_CODE (testreg) == SUBREG
2522                 && !(REG_SIZE (SUBREG_REG (testreg)) > REG_SIZE (testreg)))
2523               ;
2524             else
2525               mark_dest = 1;
2526
2527             testreg = XEXP (testreg, 0);
2528           }
2529
2530         /* If this is a store into a register,
2531            recursively scan the value being stored.  */
2532
2533         if (GET_CODE (testreg) == REG
2534             && (regno = REGNO (testreg), regno != FRAME_POINTER_REGNUM)
2535 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
2536             && regno != HARD_FRAME_POINTER_REGNUM
2537 #endif
2538 #if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
2539             && ! (regno == ARG_POINTER_REGNUM && fixed_regs[regno])
2540 #endif
2541             )
2542           /* We used to exclude global_regs here, but that seems wrong.
2543              Storing in them is like storing in mem.  */
2544           {
2545             mark_used_regs (needed, live, SET_SRC (x), final, insn);
2546             if (mark_dest)
2547               mark_used_regs (needed, live, SET_DEST (x), final, insn);
2548             return;
2549           }
2550       }
2551       break;
2552
2553     case RETURN:
2554       /* If exiting needs the right stack value, consider this insn as
2555          using the stack pointer.  In any event, consider it as using
2556          all global registers and all registers used by return.  */
2557
2558 #ifdef EXIT_IGNORE_STACK
2559       if (! EXIT_IGNORE_STACK
2560           || (! FRAME_POINTER_REQUIRED && flag_omit_frame_pointer))
2561 #endif
2562         SET_REGNO_REG_SET (live, STACK_POINTER_REGNUM);
2563
2564       for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
2565         if (global_regs[i]
2566 #ifdef EPILOGUE_USES
2567             || EPILOGUE_USES (i)
2568 #endif
2569             )
2570           SET_REGNO_REG_SET (live, i);
2571       break;
2572     }
2573
2574   /* Recursively scan the operands of this expression.  */
2575
2576   {
2577     register char *fmt = GET_RTX_FORMAT (code);
2578     register int i;
2579     
2580     for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2581       {
2582         if (fmt[i] == 'e')
2583           {
2584             /* Tail recursive case: save a function call level.  */
2585             if (i == 0)
2586               {
2587                 x = XEXP (x, 0);
2588                 goto retry;
2589               }
2590             mark_used_regs (needed, live, XEXP (x, i), final, insn);
2591           }
2592         else if (fmt[i] == 'E')
2593           {
2594             register int j;
2595             for (j = 0; j < XVECLEN (x, i); j++)
2596               mark_used_regs (needed, live, XVECEXP (x, i, j), final, insn);
2597           }
2598       }
2599   }
2600 }
2601 \f
2602 #ifdef AUTO_INC_DEC
2603
2604 static int
2605 try_pre_increment_1 (insn)
2606      rtx insn;
2607 {
2608   /* Find the next use of this reg.  If in same basic block,
2609      make it do pre-increment or pre-decrement if appropriate.  */
2610   rtx x = PATTERN (insn);
2611   HOST_WIDE_INT amount = ((GET_CODE (SET_SRC (x)) == PLUS ? 1 : -1)
2612                 * INTVAL (XEXP (SET_SRC (x), 1)));
2613   int regno = REGNO (SET_DEST (x));
2614   rtx y = reg_next_use[regno];
2615   if (y != 0
2616       && BLOCK_NUM (y) == BLOCK_NUM (insn)
2617       /* Don't do this if the reg dies, or gets set in y; a standard addressing
2618          mode would be better.  */
2619       && ! dead_or_set_p (y, SET_DEST (x))
2620       && try_pre_increment (y, SET_DEST (PATTERN (insn)),
2621                             amount))
2622     {
2623       /* We have found a suitable auto-increment
2624          and already changed insn Y to do it.
2625          So flush this increment-instruction.  */
2626       PUT_CODE (insn, NOTE);
2627       NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
2628       NOTE_SOURCE_FILE (insn) = 0;
2629       /* Count a reference to this reg for the increment
2630          insn we are deleting.  When a reg is incremented.
2631          spilling it is worse, so we want to make that
2632          less likely.  */
2633       if (regno >= FIRST_PSEUDO_REGISTER)
2634         {
2635           REG_N_REFS (regno) += loop_depth;
2636           REG_N_SETS (regno)++;
2637         }
2638       return 1;
2639     }
2640   return 0;
2641 }
2642
2643 /* Try to change INSN so that it does pre-increment or pre-decrement
2644    addressing on register REG in order to add AMOUNT to REG.
2645    AMOUNT is negative for pre-decrement.
2646    Returns 1 if the change could be made.
2647    This checks all about the validity of the result of modifying INSN.  */
2648
2649 static int
2650 try_pre_increment (insn, reg, amount)
2651      rtx insn, reg;
2652      HOST_WIDE_INT amount;
2653 {
2654   register rtx use;
2655
2656   /* Nonzero if we can try to make a pre-increment or pre-decrement.
2657      For example, addl $4,r1; movl (r1),... can become movl +(r1),...  */
2658   int pre_ok = 0;
2659   /* Nonzero if we can try to make a post-increment or post-decrement.
2660      For example, addl $4,r1; movl -4(r1),... can become movl (r1)+,...
2661      It is possible for both PRE_OK and POST_OK to be nonzero if the machine
2662      supports both pre-inc and post-inc, or both pre-dec and post-dec.  */
2663   int post_ok = 0;
2664
2665   /* Nonzero if the opportunity actually requires post-inc or post-dec.  */
2666   int do_post = 0;
2667
2668   /* From the sign of increment, see which possibilities are conceivable
2669      on this target machine.  */
2670 #ifdef HAVE_PRE_INCREMENT
2671   if (amount > 0)
2672     pre_ok = 1;
2673 #endif
2674 #ifdef HAVE_POST_INCREMENT
2675   if (amount > 0)
2676     post_ok = 1;
2677 #endif
2678
2679 #ifdef HAVE_PRE_DECREMENT
2680   if (amount < 0)
2681     pre_ok = 1;
2682 #endif
2683 #ifdef HAVE_POST_DECREMENT
2684   if (amount < 0)
2685     post_ok = 1;
2686 #endif
2687
2688   if (! (pre_ok || post_ok))
2689     return 0;
2690
2691   /* It is not safe to add a side effect to a jump insn
2692      because if the incremented register is spilled and must be reloaded
2693      there would be no way to store the incremented value back in memory.  */
2694
2695   if (GET_CODE (insn) == JUMP_INSN)
2696     return 0;
2697
2698   use = 0;
2699   if (pre_ok)
2700     use = find_use_as_address (PATTERN (insn), reg, 0);
2701   if (post_ok && (use == 0 || use == (rtx) 1))
2702     {
2703       use = find_use_as_address (PATTERN (insn), reg, -amount);
2704       do_post = 1;
2705     }
2706
2707   if (use == 0 || use == (rtx) 1)
2708     return 0;
2709
2710   if (GET_MODE_SIZE (GET_MODE (use)) != (amount > 0 ? amount : - amount))
2711     return 0;
2712
2713   /* See if this combination of instruction and addressing mode exists.  */
2714   if (! validate_change (insn, &XEXP (use, 0),
2715                          gen_rtx (amount > 0
2716                                   ? (do_post ? POST_INC : PRE_INC)
2717                                   : (do_post ? POST_DEC : PRE_DEC),
2718                                   Pmode, reg), 0))
2719     return 0;
2720
2721   /* Record that this insn now has an implicit side effect on X.  */
2722   REG_NOTES (insn) = gen_rtx (EXPR_LIST, REG_INC, reg, REG_NOTES (insn));
2723   return 1;
2724 }
2725
2726 #endif /* AUTO_INC_DEC */
2727 \f
2728 /* Find the place in the rtx X where REG is used as a memory address.
2729    Return the MEM rtx that so uses it.
2730    If PLUSCONST is nonzero, search instead for a memory address equivalent to
2731    (plus REG (const_int PLUSCONST)).
2732
2733    If such an address does not appear, return 0.
2734    If REG appears more than once, or is used other than in such an address,
2735    return (rtx)1.  */
2736
2737 static rtx
2738 find_use_as_address (x, reg, plusconst)
2739      register rtx x;
2740      rtx reg;
2741      HOST_WIDE_INT plusconst;
2742 {
2743   enum rtx_code code = GET_CODE (x);
2744   char *fmt = GET_RTX_FORMAT (code);
2745   register int i;
2746   register rtx value = 0;
2747   register rtx tem;
2748
2749   if (code == MEM && XEXP (x, 0) == reg && plusconst == 0)
2750     return x;
2751
2752   if (code == MEM && GET_CODE (XEXP (x, 0)) == PLUS
2753       && XEXP (XEXP (x, 0), 0) == reg
2754       && GET_CODE (XEXP (XEXP (x, 0), 1)) == CONST_INT
2755       && INTVAL (XEXP (XEXP (x, 0), 1)) == plusconst)
2756     return x;
2757
2758   if (code == SIGN_EXTRACT || code == ZERO_EXTRACT)
2759     {
2760       /* If REG occurs inside a MEM used in a bit-field reference,
2761          that is unacceptable.  */
2762       if (find_use_as_address (XEXP (x, 0), reg, 0) != 0)
2763         return (rtx) (HOST_WIDE_INT) 1;
2764     }
2765
2766   if (x == reg)
2767     return (rtx) (HOST_WIDE_INT) 1;
2768
2769   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2770     {
2771       if (fmt[i] == 'e')
2772         {
2773           tem = find_use_as_address (XEXP (x, i), reg, plusconst);
2774           if (value == 0)
2775             value = tem;
2776           else if (tem != 0)
2777             return (rtx) (HOST_WIDE_INT) 1;
2778         }
2779       if (fmt[i] == 'E')
2780         {
2781           register int j;
2782           for (j = XVECLEN (x, i) - 1; j >= 0; j--)
2783             {
2784               tem = find_use_as_address (XVECEXP (x, i, j), reg, plusconst);
2785               if (value == 0)
2786                 value = tem;
2787               else if (tem != 0)
2788                 return (rtx) (HOST_WIDE_INT) 1;
2789             }
2790         }
2791     }
2792
2793   return value;
2794 }
2795 \f
2796 /* Write information about registers and basic blocks into FILE.
2797    This is part of making a debugging dump.  */
2798
2799 void
2800 dump_flow_info (file)
2801      FILE *file;
2802 {
2803   register int i;
2804   static char *reg_class_names[] = REG_CLASS_NAMES;
2805
2806   fprintf (file, "%d registers.\n", max_regno);
2807
2808   for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
2809     if (REG_N_REFS (i))
2810       {
2811         enum reg_class class, altclass;
2812         fprintf (file, "\nRegister %d used %d times across %d insns",
2813                  i, REG_N_REFS (i), REG_LIVE_LENGTH (i));
2814         if (REG_BASIC_BLOCK (i) >= 0)
2815           fprintf (file, " in block %d", REG_BASIC_BLOCK (i));
2816         if (REG_N_DEATHS (i) != 1)
2817           fprintf (file, "; dies in %d places", REG_N_DEATHS (i));
2818         if (REG_N_CALLS_CROSSED (i) == 1)
2819           fprintf (file, "; crosses 1 call");
2820         else if (REG_N_CALLS_CROSSED (i))
2821           fprintf (file, "; crosses %d calls", REG_N_CALLS_CROSSED (i));
2822         if (PSEUDO_REGNO_BYTES (i) != UNITS_PER_WORD)
2823           fprintf (file, "; %d bytes", PSEUDO_REGNO_BYTES (i));
2824         class = reg_preferred_class (i);
2825         altclass = reg_alternate_class (i);
2826         if (class != GENERAL_REGS || altclass != ALL_REGS)
2827           {
2828             if (altclass == ALL_REGS || class == ALL_REGS)
2829               fprintf (file, "; pref %s", reg_class_names[(int) class]);
2830             else if (altclass == NO_REGS)
2831               fprintf (file, "; %s or none", reg_class_names[(int) class]);
2832             else
2833               fprintf (file, "; pref %s, else %s",
2834                        reg_class_names[(int) class],
2835                        reg_class_names[(int) altclass]);
2836           }
2837         if (REGNO_POINTER_FLAG (i))
2838           fprintf (file, "; pointer");
2839         fprintf (file, ".\n");
2840       }
2841   fprintf (file, "\n%d basic blocks.\n", n_basic_blocks);
2842   for (i = 0; i < n_basic_blocks; i++)
2843     {
2844       register rtx head, jump;
2845       register int regno;
2846       fprintf (file, "\nBasic block %d: first insn %d, last %d.\n",
2847                i,
2848                INSN_UID (basic_block_head[i]),
2849                INSN_UID (basic_block_end[i]));
2850       /* The control flow graph's storage is freed
2851          now when flow_analysis returns.
2852          Don't try to print it if it is gone.  */
2853       if (basic_block_drops_in)
2854         {
2855           fprintf (file, "Reached from blocks: ");
2856           head = basic_block_head[i];
2857           if (GET_CODE (head) == CODE_LABEL)
2858             for (jump = LABEL_REFS (head);
2859                  jump != head;
2860                  jump = LABEL_NEXTREF (jump))
2861               {
2862                 register int from_block = BLOCK_NUM (CONTAINING_INSN (jump));
2863                 fprintf (file, " %d", from_block);
2864               }
2865           if (basic_block_drops_in[i])
2866             fprintf (file, " previous");
2867         }
2868       fprintf (file, "\nRegisters live at start:");
2869       for (regno = 0; regno < max_regno; regno++)
2870         if (REGNO_REG_SET_P (basic_block_live_at_start[i], regno))
2871           fprintf (file, " %d", regno);
2872       fprintf (file, "\n");
2873     }
2874   fprintf (file, "\n");
2875 }