OSDN Git Service

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