OSDN Git Service

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