OSDN Git Service

2006-09-06 James E Wilson <wilson@specifix.com>
[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   else
651     {
652       /* FIXME: This can go when the dataflow branch has been merged in.  */
653       /* For a local update, if we are creating new REG_DEAD notes, then we
654          must delete the old ones first to avoid conflicts if they are
655          different.  */
656       if (prop_flags & PROP_DEATH_NOTES)
657         count_or_remove_death_notes (blocks,
658                                      prop_flags & PROP_POST_REGSTACK ? -1 : 1);
659     }
660                                      
661
662   /* Clear log links in case we are asked to (re)compute them.  */
663   if (prop_flags & PROP_LOG_LINKS)
664     clear_log_links (blocks);
665
666   if (blocks)
667     {
668       sbitmap_iterator sbi;
669
670       EXECUTE_IF_SET_IN_SBITMAP (blocks, 0, i, sbi)
671         {
672           bb = BASIC_BLOCK (i);
673           if (bb)
674             {
675               /* The bitmap may be flawed in that one of the basic
676                  blocks may have been deleted before you get here.  */
677               COPY_REG_SET (tmp, bb->il.rtl->global_live_at_end);
678               propagate_block (bb, tmp, NULL, NULL, stabilized_prop_flags);
679               
680               if (extent == UPDATE_LIFE_LOCAL)
681                 verify_local_live_at_start (tmp, bb);
682             }
683         };
684     }
685   else
686     {
687       FOR_EACH_BB_REVERSE (bb)
688         {
689           COPY_REG_SET (tmp, bb->il.rtl->global_live_at_end);
690
691           propagate_block (bb, tmp, NULL, NULL, stabilized_prop_flags);
692
693           if (extent == UPDATE_LIFE_LOCAL)
694             verify_local_live_at_start (tmp, bb);
695         }
696     }
697
698   FREE_REG_SET (tmp);
699
700   if (prop_flags & PROP_REG_INFO)
701     {
702       reg_set_iterator rsi;
703
704       /* The only pseudos that are live at the beginning of the function
705          are those that were not set anywhere in the function.  local-alloc
706          doesn't know how to handle these correctly, so mark them as not
707          local to any one basic block.  */
708       EXECUTE_IF_SET_IN_REG_SET (ENTRY_BLOCK_PTR->il.rtl->global_live_at_end,
709                                  FIRST_PSEUDO_REGISTER, i, rsi)
710         REG_BASIC_BLOCK (i) = REG_BLOCK_GLOBAL;
711
712       /* We have a problem with any pseudoreg that lives across the setjmp.
713          ANSI says that if a user variable does not change in value between
714          the setjmp and the longjmp, then the longjmp preserves it.  This
715          includes longjmp from a place where the pseudo appears dead.
716          (In principle, the value still exists if it is in scope.)
717          If the pseudo goes in a hard reg, some other value may occupy
718          that hard reg where this pseudo is dead, thus clobbering the pseudo.
719          Conclusion: such a pseudo must not go in a hard reg.  */
720       EXECUTE_IF_SET_IN_REG_SET (regs_live_at_setjmp,
721                                  FIRST_PSEUDO_REGISTER, i, rsi)
722         {
723           if (regno_reg_rtx[i] != 0)
724             {
725               REG_LIVE_LENGTH (i) = -1;
726               REG_BASIC_BLOCK (i) = REG_BLOCK_UNKNOWN;
727             }
728         }
729     }
730   if (reg_deaths)
731     {
732       free (reg_deaths);
733       reg_deaths = NULL;
734     }
735   timevar_pop ((extent == UPDATE_LIFE_LOCAL || blocks)
736                ? TV_LIFE_UPDATE : TV_LIFE);
737   if (ndead && dump_file)
738     fprintf (dump_file, "deleted %i dead insns\n", ndead);
739   return ndead;
740 }
741
742 /* Update life information in all blocks where BB_DIRTY is set.  */
743
744 int
745 update_life_info_in_dirty_blocks (enum update_life_extent extent, int prop_flags)
746 {
747   sbitmap update_life_blocks = sbitmap_alloc (last_basic_block);
748   int n = 0;
749   basic_block bb;
750   int retval = 0;
751
752   sbitmap_zero (update_life_blocks);
753   FOR_EACH_BB (bb)
754     {
755       if (bb->flags & BB_DIRTY)
756         {
757           SET_BIT (update_life_blocks, bb->index);
758           n++;
759         }
760     }
761
762   if (n)
763     retval = update_life_info (update_life_blocks, extent, prop_flags);
764
765   sbitmap_free (update_life_blocks);
766   return retval;
767 }
768
769 /* Free the variables allocated by find_basic_blocks.  */
770
771 void
772 free_basic_block_vars (void)
773 {
774   if (basic_block_info)
775     {
776       clear_edges ();
777       basic_block_info = NULL;
778     }
779   n_basic_blocks = 0;
780   last_basic_block = 0;
781   n_edges = 0;
782
783   label_to_block_map = NULL;
784
785   ENTRY_BLOCK_PTR->aux = NULL;
786   ENTRY_BLOCK_PTR->il.rtl->global_live_at_end = NULL;
787   EXIT_BLOCK_PTR->aux = NULL;
788   EXIT_BLOCK_PTR->il.rtl->global_live_at_start = NULL;
789 }
790
791 /* Delete any insns that copy a register to itself.  */
792
793 int
794 delete_noop_moves (void)
795 {
796   rtx insn, next;
797   basic_block bb;
798   int nnoops = 0;
799
800   FOR_EACH_BB (bb)
801     {
802       for (insn = BB_HEAD (bb); insn != NEXT_INSN (BB_END (bb)); insn = next)
803         {
804           next = NEXT_INSN (insn);
805           if (INSN_P (insn) && noop_move_p (insn))
806             {
807               rtx note;
808
809               /* If we're about to remove the first insn of a libcall
810                  then move the libcall note to the next real insn and
811                  update the retval note.  */
812               if ((note = find_reg_note (insn, REG_LIBCALL, NULL_RTX))
813                        && XEXP (note, 0) != insn)
814                 {
815                   rtx new_libcall_insn = next_real_insn (insn);
816                   rtx retval_note = find_reg_note (XEXP (note, 0),
817                                                    REG_RETVAL, NULL_RTX);
818                   REG_NOTES (new_libcall_insn)
819                     = gen_rtx_INSN_LIST (REG_LIBCALL, XEXP (note, 0),
820                                          REG_NOTES (new_libcall_insn));
821                   XEXP (retval_note, 0) = new_libcall_insn;
822                 }
823
824               delete_insn_and_edges (insn);
825               nnoops++;
826             }
827         }
828     }
829
830   if (nnoops && dump_file)
831     fprintf (dump_file, "deleted %i noop moves\n", nnoops);
832
833   return nnoops;
834 }
835
836 /* Delete any jump tables never referenced.  We can't delete them at the
837    time of removing tablejump insn as they are referenced by the preceding
838    insns computing the destination, so we delay deleting and garbagecollect
839    them once life information is computed.  */
840 void
841 delete_dead_jumptables (void)
842 {
843   basic_block bb;
844
845   /* A dead jump table does not belong to any basic block.  Scan insns
846      between two adjacent basic blocks.  */
847   FOR_EACH_BB (bb)
848     {
849       rtx insn, next;
850
851       for (insn = NEXT_INSN (BB_END (bb));
852            insn && !NOTE_INSN_BASIC_BLOCK_P (insn);
853            insn = next)
854         {
855           next = NEXT_INSN (insn);
856           if (LABEL_P (insn)
857               && LABEL_NUSES (insn) == LABEL_PRESERVE_P (insn)
858               && JUMP_P (next)
859               && (GET_CODE (PATTERN (next)) == ADDR_VEC
860                   || GET_CODE (PATTERN (next)) == ADDR_DIFF_VEC))
861             {
862               rtx label = insn, jump = next;
863
864               if (dump_file)
865                 fprintf (dump_file, "Dead jumptable %i removed\n",
866                          INSN_UID (insn));
867
868               next = NEXT_INSN (next);
869               delete_insn (jump);
870               delete_insn (label);
871             }
872         }
873     }
874 }
875
876 /* Determine if the stack pointer is constant over the life of the function.
877    Only useful before prologues have been emitted.  */
878
879 static void
880 notice_stack_pointer_modification_1 (rtx x, rtx pat ATTRIBUTE_UNUSED,
881                                      void *data ATTRIBUTE_UNUSED)
882 {
883   if (x == stack_pointer_rtx
884       /* The stack pointer is only modified indirectly as the result
885          of a push until later in flow.  See the comments in rtl.texi
886          regarding Embedded Side-Effects on Addresses.  */
887       || (MEM_P (x)
888           && GET_RTX_CLASS (GET_CODE (XEXP (x, 0))) == RTX_AUTOINC
889           && XEXP (XEXP (x, 0), 0) == stack_pointer_rtx))
890     current_function_sp_is_unchanging = 0;
891 }
892
893 static void
894 notice_stack_pointer_modification (void)
895 {
896   basic_block bb;
897   rtx insn;
898
899   /* Assume that the stack pointer is unchanging if alloca hasn't
900      been used.  */
901   current_function_sp_is_unchanging = !current_function_calls_alloca;
902   if (! current_function_sp_is_unchanging)
903     return;
904
905   FOR_EACH_BB (bb)
906     FOR_BB_INSNS (bb, insn)
907       {
908         if (INSN_P (insn))
909           {
910             /* Check if insn modifies the stack pointer.  */
911             note_stores (PATTERN (insn),
912                          notice_stack_pointer_modification_1,
913                          NULL);
914             if (! current_function_sp_is_unchanging)
915               return;
916           }
917       }
918 }
919
920 /* Mark a register in SET.  Hard registers in large modes get all
921    of their component registers set as well.  */
922
923 static void
924 mark_reg (rtx reg, void *xset)
925 {
926   regset set = (regset) xset;
927   int regno = REGNO (reg);
928
929   gcc_assert (GET_MODE (reg) != BLKmode);
930
931   SET_REGNO_REG_SET (set, regno);
932   if (regno < FIRST_PSEUDO_REGISTER)
933     {
934       int n = hard_regno_nregs[regno][GET_MODE (reg)];
935       while (--n > 0)
936         SET_REGNO_REG_SET (set, regno + n);
937     }
938 }
939
940 /* Mark those regs which are needed at the end of the function as live
941    at the end of the last basic block.  */
942
943 static void
944 mark_regs_live_at_end (regset set)
945 {
946   unsigned int i;
947
948   /* If exiting needs the right stack value, consider the stack pointer
949      live at the end of the function.  */
950   if ((HAVE_epilogue && epilogue_completed)
951       || ! EXIT_IGNORE_STACK
952       || (! FRAME_POINTER_REQUIRED
953           && ! current_function_calls_alloca
954           && flag_omit_frame_pointer)
955       || current_function_sp_is_unchanging)
956     {
957       SET_REGNO_REG_SET (set, STACK_POINTER_REGNUM);
958     }
959
960   /* Mark the frame pointer if needed at the end of the function.  If
961      we end up eliminating it, it will be removed from the live list
962      of each basic block by reload.  */
963
964   if (! reload_completed || frame_pointer_needed)
965     {
966       SET_REGNO_REG_SET (set, FRAME_POINTER_REGNUM);
967 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
968       /* If they are different, also mark the hard frame pointer as live.  */
969       if (! LOCAL_REGNO (HARD_FRAME_POINTER_REGNUM))
970         SET_REGNO_REG_SET (set, HARD_FRAME_POINTER_REGNUM);
971 #endif
972     }
973
974 #ifndef PIC_OFFSET_TABLE_REG_CALL_CLOBBERED
975   /* Many architectures have a GP register even without flag_pic.
976      Assume the pic register is not in use, or will be handled by
977      other means, if it is not fixed.  */
978   if ((unsigned) PIC_OFFSET_TABLE_REGNUM != INVALID_REGNUM
979       && fixed_regs[PIC_OFFSET_TABLE_REGNUM])
980     SET_REGNO_REG_SET (set, PIC_OFFSET_TABLE_REGNUM);
981 #endif
982
983   /* Mark all global registers, and all registers used by the epilogue
984      as being live at the end of the function since they may be
985      referenced by our caller.  */
986   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
987     if (global_regs[i] || EPILOGUE_USES (i))
988       SET_REGNO_REG_SET (set, i);
989
990   if (HAVE_epilogue && epilogue_completed)
991     {
992       /* Mark all call-saved registers that we actually used.  */
993       for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
994         if (regs_ever_live[i] && ! LOCAL_REGNO (i)
995             && ! TEST_HARD_REG_BIT (regs_invalidated_by_call, i))
996           SET_REGNO_REG_SET (set, i);
997     }
998
999 #ifdef EH_RETURN_DATA_REGNO
1000   /* Mark the registers that will contain data for the handler.  */
1001   if (reload_completed && current_function_calls_eh_return)
1002     for (i = 0; ; ++i)
1003       {
1004         unsigned regno = EH_RETURN_DATA_REGNO(i);
1005         if (regno == INVALID_REGNUM)
1006           break;
1007         SET_REGNO_REG_SET (set, regno);
1008       }
1009 #endif
1010 #ifdef EH_RETURN_STACKADJ_RTX
1011   if ((! HAVE_epilogue || ! epilogue_completed)
1012       && current_function_calls_eh_return)
1013     {
1014       rtx tmp = EH_RETURN_STACKADJ_RTX;
1015       if (tmp && REG_P (tmp))
1016         mark_reg (tmp, set);
1017     }
1018 #endif
1019 #ifdef EH_RETURN_HANDLER_RTX
1020   if ((! HAVE_epilogue || ! epilogue_completed)
1021       && current_function_calls_eh_return)
1022     {
1023       rtx tmp = EH_RETURN_HANDLER_RTX;
1024       if (tmp && REG_P (tmp))
1025         mark_reg (tmp, set);
1026     }
1027 #endif
1028
1029   /* Mark function return value.  */
1030   diddle_return_value (mark_reg, set);
1031 }
1032
1033 /* Propagate global life info around the graph of basic blocks.  Begin
1034    considering blocks with their corresponding bit set in BLOCKS_IN.
1035    If BLOCKS_IN is null, consider it the universal set.
1036
1037    BLOCKS_OUT is set for every block that was changed.  */
1038
1039 static void
1040 calculate_global_regs_live (sbitmap blocks_in, sbitmap blocks_out, int flags)
1041 {
1042   basic_block *queue, *qhead, *qtail, *qend, bb;
1043   regset tmp, new_live_at_end, invalidated_by_call;
1044   regset registers_made_dead;
1045   bool failure_strategy_required = false;
1046   int *block_accesses;
1047
1048   /* The registers that are modified within this in block.  */
1049   regset *local_sets;
1050
1051   /* The registers that are conditionally modified within this block.
1052      In other words, regs that are set only as part of a COND_EXEC.  */
1053   regset *cond_local_sets;
1054
1055   unsigned int i;
1056
1057   /* Some passes used to forget clear aux field of basic block causing
1058      sick behavior here.  */
1059 #ifdef ENABLE_CHECKING
1060   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
1061     gcc_assert (!bb->aux);
1062 #endif
1063
1064   tmp = ALLOC_REG_SET (&reg_obstack);
1065   new_live_at_end = ALLOC_REG_SET (&reg_obstack);
1066   invalidated_by_call = ALLOC_REG_SET (&reg_obstack);
1067   registers_made_dead = ALLOC_REG_SET (&reg_obstack);
1068
1069   /* Inconveniently, this is only readily available in hard reg set form.  */
1070   for (i = 0; i < FIRST_PSEUDO_REGISTER; ++i)
1071     if (TEST_HARD_REG_BIT (regs_invalidated_by_call, i))
1072       SET_REGNO_REG_SET (invalidated_by_call, i);
1073
1074   /* Allocate space for the sets of local properties.  */
1075   local_sets = XCNEWVEC (bitmap, last_basic_block);
1076   cond_local_sets = XCNEWVEC (bitmap, last_basic_block);
1077
1078   /* Create a worklist.  Allocate an extra slot for the `head == tail'
1079      style test for an empty queue doesn't work with a full queue.  */
1080   queue = XNEWVEC (basic_block, n_basic_blocks + 1);
1081   qtail = queue;
1082   qhead = qend = queue + n_basic_blocks;
1083
1084   /* Queue the blocks set in the initial mask.  Do this in reverse block
1085      number order so that we are more likely for the first round to do
1086      useful work.  We use AUX non-null to flag that the block is queued.  */
1087   if (blocks_in)
1088     {
1089       FOR_EACH_BB (bb)
1090         if (TEST_BIT (blocks_in, bb->index))
1091           {
1092             *--qhead = bb;
1093             bb->aux = bb;
1094           }
1095     }
1096   else
1097     {
1098       FOR_EACH_BB (bb)
1099         {
1100           *--qhead = bb;
1101           bb->aux = bb;
1102         }
1103     }
1104
1105   block_accesses = XCNEWVEC (int, last_basic_block);
1106   
1107   /* We clean aux when we remove the initially-enqueued bbs, but we
1108      don't enqueue ENTRY and EXIT initially, so clean them upfront and
1109      unconditionally.  */
1110   ENTRY_BLOCK_PTR->aux = EXIT_BLOCK_PTR->aux = NULL;
1111
1112   if (blocks_out)
1113     sbitmap_zero (blocks_out);
1114
1115   /* We work through the queue until there are no more blocks.  What
1116      is live at the end of this block is precisely the union of what
1117      is live at the beginning of all its successors.  So, we set its
1118      GLOBAL_LIVE_AT_END field based on the GLOBAL_LIVE_AT_START field
1119      for its successors.  Then, we compute GLOBAL_LIVE_AT_START for
1120      this block by walking through the instructions in this block in
1121      reverse order and updating as we go.  If that changed
1122      GLOBAL_LIVE_AT_START, we add the predecessors of the block to the
1123      queue; they will now need to recalculate GLOBAL_LIVE_AT_END.
1124
1125      We are guaranteed to terminate, because GLOBAL_LIVE_AT_START
1126      never shrinks.  If a register appears in GLOBAL_LIVE_AT_START, it
1127      must either be live at the end of the block, or used within the
1128      block.  In the latter case, it will certainly never disappear
1129      from GLOBAL_LIVE_AT_START.  In the former case, the register
1130      could go away only if it disappeared from GLOBAL_LIVE_AT_START
1131      for one of the successor blocks.  By induction, that cannot
1132      occur.
1133
1134      ??? This reasoning doesn't work if we start from non-empty initial
1135      GLOBAL_LIVE_AT_START sets.  And there are actually two problems:
1136        1) Updating may not terminate (endless oscillation).
1137        2) Even if it does (and it usually does), the resulting information
1138           may be inaccurate.  Consider for example the following case:
1139
1140           a = ...;
1141           while (...) {...}  -- 'a' not mentioned at all
1142           ... = a;
1143
1144           If the use of 'a' is deleted between two calculations of liveness
1145           information and the initial sets are not cleared, the information
1146           about a's liveness will get stuck inside the loop and the set will
1147           appear not to be dead.
1148
1149      We do not attempt to solve 2) -- the information is conservatively
1150      correct (i.e. we never claim that something live is dead) and the
1151      amount of optimization opportunities missed due to this problem is
1152      not significant.
1153
1154      1) is more serious.  In order to fix it, we monitor the number of times
1155      each block is processed.  Once one of the blocks has been processed more
1156      times than the maximum number of rounds, we use the following strategy:
1157      When a register disappears from one of the sets, we add it to a MAKE_DEAD
1158      set, remove all registers in this set from all GLOBAL_LIVE_AT_* sets and
1159      add the blocks with changed sets into the queue.  Thus we are guaranteed
1160      to terminate (the worst case corresponds to all registers in MADE_DEAD,
1161      in which case the original reasoning above is valid), but in general we
1162      only fix up a few offending registers.
1163
1164      The maximum number of rounds for computing liveness is the largest of
1165      MAX_LIVENESS_ROUNDS and the latest loop depth count for this function.  */
1166
1167   while (qhead != qtail)
1168     {
1169       int rescan, changed;
1170       basic_block bb;
1171       edge e;
1172       edge_iterator ei;
1173
1174       bb = *qhead++;
1175       if (qhead == qend)
1176         qhead = queue;
1177       bb->aux = NULL;
1178
1179       /* Should we start using the failure strategy?  */
1180       if (bb != ENTRY_BLOCK_PTR)
1181         {
1182           int max_liveness_rounds =
1183             MAX (MAX_LIVENESS_ROUNDS, cfun->max_loop_depth);
1184
1185           block_accesses[bb->index]++;
1186           if (block_accesses[bb->index] > max_liveness_rounds)
1187             failure_strategy_required = true;
1188         }
1189
1190       /* Begin by propagating live_at_start from the successor blocks.  */
1191       CLEAR_REG_SET (new_live_at_end);
1192
1193       if (EDGE_COUNT (bb->succs) > 0)
1194         FOR_EACH_EDGE (e, ei, bb->succs)
1195           {
1196             basic_block sb = e->dest;
1197
1198             /* Call-clobbered registers die across exception and
1199                call edges.  */
1200             /* ??? Abnormal call edges ignored for the moment, as this gets
1201                confused by sibling call edges, which crashes reg-stack.  */
1202             if (e->flags & EDGE_EH)
1203               bitmap_ior_and_compl_into (new_live_at_end,
1204                                          sb->il.rtl->global_live_at_start,
1205                                          invalidated_by_call);
1206             else
1207               IOR_REG_SET (new_live_at_end, sb->il.rtl->global_live_at_start);
1208
1209             /* If a target saves one register in another (instead of on
1210                the stack) the save register will need to be live for EH.  */
1211             if (e->flags & EDGE_EH)
1212               for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1213                 if (EH_USES (i))
1214                   SET_REGNO_REG_SET (new_live_at_end, i);
1215           }
1216       else
1217         {
1218           /* This might be a noreturn function that throws.  And
1219              even if it isn't, getting the unwind info right helps
1220              debugging.  */
1221           for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1222             if (EH_USES (i))
1223               SET_REGNO_REG_SET (new_live_at_end, i);
1224         }
1225
1226       /* The all-important stack pointer must always be live.  */
1227       SET_REGNO_REG_SET (new_live_at_end, STACK_POINTER_REGNUM);
1228
1229       /* Before reload, there are a few registers that must be forced
1230          live everywhere -- which might not already be the case for
1231          blocks within infinite loops.  */
1232       if (! reload_completed)
1233         {
1234           /* Any reference to any pseudo before reload is a potential
1235              reference of the frame pointer.  */
1236           SET_REGNO_REG_SET (new_live_at_end, FRAME_POINTER_REGNUM);
1237
1238 #if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
1239           /* Pseudos with argument area equivalences may require
1240              reloading via the argument pointer.  */
1241           if (fixed_regs[ARG_POINTER_REGNUM])
1242             SET_REGNO_REG_SET (new_live_at_end, ARG_POINTER_REGNUM);
1243 #endif
1244
1245           /* Any constant, or pseudo with constant equivalences, may
1246              require reloading from memory using the pic register.  */
1247           if ((unsigned) PIC_OFFSET_TABLE_REGNUM != INVALID_REGNUM
1248               && fixed_regs[PIC_OFFSET_TABLE_REGNUM])
1249             SET_REGNO_REG_SET (new_live_at_end, PIC_OFFSET_TABLE_REGNUM);
1250         }
1251
1252       if (bb == ENTRY_BLOCK_PTR)
1253         {
1254           COPY_REG_SET (bb->il.rtl->global_live_at_end, new_live_at_end);
1255           continue;
1256         }
1257
1258       /* On our first pass through this block, we'll go ahead and continue.
1259          Recognize first pass by checking if local_set is NULL for this
1260          basic block.  On subsequent passes, we get to skip out early if
1261          live_at_end wouldn't have changed.  */
1262
1263       if (local_sets[bb->index] == NULL)
1264         {
1265           local_sets[bb->index] = ALLOC_REG_SET (&reg_obstack);
1266           cond_local_sets[bb->index] = ALLOC_REG_SET (&reg_obstack);
1267           rescan = 1;
1268         }
1269       else
1270         {
1271           /* If any bits were removed from live_at_end, we'll have to
1272              rescan the block.  This wouldn't be necessary if we had
1273              precalculated local_live, however with PROP_SCAN_DEAD_CODE
1274              local_live is really dependent on live_at_end.  */
1275           rescan = bitmap_intersect_compl_p (bb->il.rtl->global_live_at_end,
1276                                              new_live_at_end);
1277
1278           if (!rescan)
1279             {
1280               regset cond_local_set;
1281
1282                /* If any of the registers in the new live_at_end set are
1283                   conditionally set in this basic block, we must rescan.
1284                   This is because conditional lifetimes at the end of the
1285                   block do not just take the live_at_end set into
1286                   account, but also the liveness at the start of each
1287                   successor block.  We can miss changes in those sets if
1288                   we only compare the new live_at_end against the
1289                   previous one.  */
1290               cond_local_set = cond_local_sets[bb->index];
1291               rescan = bitmap_intersect_p (new_live_at_end, cond_local_set);
1292             }
1293
1294           if (!rescan)
1295             {
1296               regset local_set;
1297
1298               /* Find the set of changed bits.  Take this opportunity
1299                  to notice that this set is empty and early out.  */
1300               bitmap_xor (tmp, bb->il.rtl->global_live_at_end, new_live_at_end);
1301               if (bitmap_empty_p (tmp))
1302                 continue;
1303   
1304               /* If any of the changed bits overlap with local_sets[bb],
1305                  we'll have to rescan the block.  */
1306               local_set = local_sets[bb->index];
1307               rescan = bitmap_intersect_p (tmp, local_set);
1308             }
1309         }
1310
1311       /* Let our caller know that BB changed enough to require its
1312          death notes updated.  */
1313       if (blocks_out)
1314         SET_BIT (blocks_out, bb->index);
1315
1316       if (! rescan)
1317         {
1318           /* Add to live_at_start the set of all registers in
1319              new_live_at_end that aren't in the old live_at_end.  */
1320           
1321           changed = bitmap_ior_and_compl_into (bb->il.rtl->global_live_at_start,
1322                                                new_live_at_end,
1323                                                bb->il.rtl->global_live_at_end);
1324           COPY_REG_SET (bb->il.rtl->global_live_at_end, new_live_at_end);
1325           if (! changed)
1326             continue;
1327         }
1328       else
1329         {
1330           COPY_REG_SET (bb->il.rtl->global_live_at_end, new_live_at_end);
1331
1332           /* Rescan the block insn by insn to turn (a copy of) live_at_end
1333              into live_at_start.  */
1334           propagate_block (bb, new_live_at_end,
1335                            local_sets[bb->index],
1336                            cond_local_sets[bb->index],
1337                            flags);
1338
1339           /* If live_at start didn't change, no need to go farther.  */
1340           if (REG_SET_EQUAL_P (bb->il.rtl->global_live_at_start,
1341                                new_live_at_end))
1342             continue;
1343
1344           if (failure_strategy_required)
1345             {
1346               /* Get the list of registers that were removed from the
1347                  bb->global_live_at_start set.  */
1348               bitmap_and_compl (tmp, bb->il.rtl->global_live_at_start,
1349                                 new_live_at_end);
1350               if (!bitmap_empty_p (tmp))
1351                 {
1352                   bool pbb_changed;
1353                   basic_block pbb;
1354                 
1355                   /* It should not happen that one of registers we have
1356                      removed last time is disappears again before any other
1357                      register does.  */
1358                   pbb_changed = bitmap_ior_into (registers_made_dead, tmp);
1359                   gcc_assert (pbb_changed);
1360
1361                   /* Now remove the registers from all sets.  */
1362                   FOR_EACH_BB (pbb)
1363                     {
1364                       pbb_changed = false;
1365
1366                       pbb_changed
1367                         |= bitmap_and_compl_into
1368                             (pbb->il.rtl->global_live_at_start,
1369                              registers_made_dead);
1370                       pbb_changed
1371                         |= bitmap_and_compl_into
1372                             (pbb->il.rtl->global_live_at_end,
1373                              registers_made_dead);
1374                       if (!pbb_changed)
1375                         continue;
1376
1377                       /* Note the (possible) change.  */
1378                       if (blocks_out)
1379                         SET_BIT (blocks_out, pbb->index);
1380
1381                       /* Makes sure to really rescan the block.  */
1382                       if (local_sets[pbb->index])
1383                         {
1384                           FREE_REG_SET (local_sets[pbb->index]);
1385                           FREE_REG_SET (cond_local_sets[pbb->index]);
1386                           local_sets[pbb->index] = 0;
1387                         }
1388
1389                       /* Add it to the queue.  */
1390                       if (pbb->aux == NULL)
1391                         {
1392                           *qtail++ = pbb;
1393                           if (qtail == qend)
1394                             qtail = queue;
1395                           pbb->aux = pbb;
1396                         }
1397                     }
1398                   continue;
1399                 }
1400             } /* end of failure_strategy_required */
1401
1402           COPY_REG_SET (bb->il.rtl->global_live_at_start, new_live_at_end);
1403         }
1404
1405       /* Queue all predecessors of BB so that we may re-examine
1406          their live_at_end.  */
1407       FOR_EACH_EDGE (e, ei, bb->preds)
1408         {
1409           basic_block pb = e->src;
1410
1411           gcc_assert ((e->flags & EDGE_FAKE) == 0);
1412
1413           if (pb->aux == NULL)
1414             {
1415               *qtail++ = pb;
1416               if (qtail == qend)
1417                 qtail = queue;
1418               pb->aux = pb;
1419             }
1420         }
1421     }
1422
1423   FREE_REG_SET (tmp);
1424   FREE_REG_SET (new_live_at_end);
1425   FREE_REG_SET (invalidated_by_call);
1426   FREE_REG_SET (registers_made_dead);
1427
1428   if (blocks_out)
1429     {
1430       sbitmap_iterator sbi;
1431
1432       EXECUTE_IF_SET_IN_SBITMAP (blocks_out, 0, i, sbi)
1433         {
1434           basic_block bb = BASIC_BLOCK (i);
1435           FREE_REG_SET (local_sets[bb->index]);
1436           FREE_REG_SET (cond_local_sets[bb->index]);
1437         };
1438     }
1439   else
1440     {
1441       FOR_EACH_BB (bb)
1442         {
1443           FREE_REG_SET (local_sets[bb->index]);
1444           FREE_REG_SET (cond_local_sets[bb->index]);
1445         }
1446     }
1447
1448   free (block_accesses);
1449   free (queue);
1450   free (cond_local_sets);
1451   free (local_sets);
1452 }
1453
1454 \f
1455 /* This structure is used to pass parameters to and from the
1456    the function find_regno_partial(). It is used to pass in the
1457    register number we are looking, as well as to return any rtx
1458    we find.  */
1459
1460 typedef struct {
1461   unsigned regno_to_find;
1462   rtx retval;
1463 } find_regno_partial_param;
1464
1465
1466 /* Find the rtx for the reg numbers specified in 'data' if it is
1467    part of an expression which only uses part of the register.  Return
1468    it in the structure passed in.  */
1469 static int
1470 find_regno_partial (rtx *ptr, void *data)
1471 {
1472   find_regno_partial_param *param = (find_regno_partial_param *)data;
1473   unsigned reg = param->regno_to_find;
1474   param->retval = NULL_RTX;
1475
1476   if (*ptr == NULL_RTX)
1477     return 0;
1478
1479   switch (GET_CODE (*ptr))
1480     {
1481     case ZERO_EXTRACT:
1482     case SIGN_EXTRACT:
1483     case STRICT_LOW_PART:
1484       if (REG_P (XEXP (*ptr, 0)) && REGNO (XEXP (*ptr, 0)) == reg)
1485         {
1486           param->retval = XEXP (*ptr, 0);
1487           return 1;
1488         }
1489       break;
1490
1491     case SUBREG:
1492       if (REG_P (SUBREG_REG (*ptr))
1493           && REGNO (SUBREG_REG (*ptr)) == reg)
1494         {
1495           param->retval = SUBREG_REG (*ptr);
1496           return 1;
1497         }
1498       break;
1499
1500     default:
1501       break;
1502     }
1503
1504   return 0;
1505 }
1506
1507 /* Process all immediate successors of the entry block looking for pseudo
1508    registers which are live on entry. Find all of those whose first
1509    instance is a partial register reference of some kind, and initialize
1510    them to 0 after the entry block.  This will prevent bit sets within
1511    registers whose value is unknown, and may contain some kind of sticky
1512    bits we don't want.  */
1513
1514 static int
1515 initialize_uninitialized_subregs (void)
1516 {
1517   rtx insn;
1518   edge e;
1519   unsigned reg, did_something = 0;
1520   find_regno_partial_param param;
1521   edge_iterator ei;
1522
1523   FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
1524     {
1525       basic_block bb = e->dest;
1526       regset map = bb->il.rtl->global_live_at_start;
1527       reg_set_iterator rsi;
1528
1529       EXECUTE_IF_SET_IN_REG_SET (map, FIRST_PSEUDO_REGISTER, reg, rsi)
1530         {
1531           int uid = REGNO_FIRST_UID (reg);
1532           rtx i;
1533
1534           /* Find an insn which mentions the register we are looking for.
1535              Its preferable to have an instance of the register's rtl since
1536              there may be various flags set which we need to duplicate.
1537              If we can't find it, its probably an automatic whose initial
1538              value doesn't matter, or hopefully something we don't care about.  */
1539           for (i = get_insns (); i && INSN_UID (i) != uid; i = NEXT_INSN (i))
1540             ;
1541           if (i != NULL_RTX)
1542             {
1543               /* Found the insn, now get the REG rtx, if we can.  */
1544               param.regno_to_find = reg;
1545               for_each_rtx (&i, find_regno_partial, &param);
1546               if (param.retval != NULL_RTX)
1547                 {
1548                   start_sequence ();
1549                   emit_move_insn (param.retval,
1550                                   CONST0_RTX (GET_MODE (param.retval)));
1551                   insn = get_insns ();
1552                   end_sequence ();
1553                   insert_insn_on_edge (insn, e);
1554                   did_something = 1;
1555                 }
1556             }
1557         }
1558     }
1559
1560   if (did_something)
1561     commit_edge_insertions ();
1562   return did_something;
1563 }
1564
1565 \f
1566 /* Subroutines of life analysis.  */
1567
1568 /* Allocate the permanent data structures that represent the results
1569    of life analysis.  */
1570
1571 static void
1572 allocate_bb_life_data (void)
1573 {
1574   basic_block bb;
1575
1576   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
1577     {
1578       if (bb->il.rtl->global_live_at_start)
1579         {
1580           CLEAR_REG_SET (bb->il.rtl->global_live_at_start);
1581           CLEAR_REG_SET (bb->il.rtl->global_live_at_end);
1582         }
1583       else
1584         {
1585           bb->il.rtl->global_live_at_start = ALLOC_REG_SET (&reg_obstack);
1586           bb->il.rtl->global_live_at_end = ALLOC_REG_SET (&reg_obstack);
1587         }
1588     }
1589
1590   regs_live_at_setjmp = ALLOC_REG_SET (&reg_obstack);
1591 }
1592
1593 void
1594 allocate_reg_life_data (void)
1595 {
1596   int i;
1597
1598   max_regno = max_reg_num ();
1599   gcc_assert (!reg_deaths);
1600   reg_deaths = XCNEWVEC (int, max_regno);
1601
1602   /* Recalculate the register space, in case it has grown.  Old style
1603      vector oriented regsets would set regset_{size,bytes} here also.  */
1604   allocate_reg_info (max_regno, FALSE, FALSE);
1605
1606   /* Reset all the data we'll collect in propagate_block and its
1607      subroutines.  */
1608   for (i = 0; i < max_regno; i++)
1609     {
1610       REG_N_SETS (i) = 0;
1611       REG_N_REFS (i) = 0;
1612       REG_N_DEATHS (i) = 0;
1613       REG_N_CALLS_CROSSED (i) = 0;
1614       REG_N_THROWING_CALLS_CROSSED (i) = 0;
1615       REG_LIVE_LENGTH (i) = 0;
1616       REG_FREQ (i) = 0;
1617       REG_BASIC_BLOCK (i) = REG_BLOCK_UNKNOWN;
1618     }
1619 }
1620
1621 /* Delete dead instructions for propagate_block.  */
1622
1623 static void
1624 propagate_block_delete_insn (rtx insn)
1625 {
1626   rtx inote = find_reg_note (insn, REG_LABEL, NULL_RTX);
1627
1628   /* If the insn referred to a label, and that label was attached to
1629      an ADDR_VEC, it's safe to delete the ADDR_VEC.  In fact, it's
1630      pretty much mandatory to delete it, because the ADDR_VEC may be
1631      referencing labels that no longer exist.
1632
1633      INSN may reference a deleted label, particularly when a jump
1634      table has been optimized into a direct jump.  There's no
1635      real good way to fix up the reference to the deleted label
1636      when the label is deleted, so we just allow it here.  */
1637
1638   if (inote && LABEL_P (inote))
1639     {
1640       rtx label = XEXP (inote, 0);
1641       rtx next;
1642
1643       /* The label may be forced if it has been put in the constant
1644          pool.  If that is the only use we must discard the table
1645          jump following it, but not the label itself.  */
1646       if (LABEL_NUSES (label) == 1 + LABEL_PRESERVE_P (label)
1647           && (next = next_nonnote_insn (label)) != NULL
1648           && JUMP_P (next)
1649           && (GET_CODE (PATTERN (next)) == ADDR_VEC
1650               || GET_CODE (PATTERN (next)) == ADDR_DIFF_VEC))
1651         {
1652           rtx pat = PATTERN (next);
1653           int diff_vec_p = GET_CODE (pat) == ADDR_DIFF_VEC;
1654           int len = XVECLEN (pat, diff_vec_p);
1655           int i;
1656
1657           for (i = 0; i < len; i++)
1658             LABEL_NUSES (XEXP (XVECEXP (pat, diff_vec_p, i), 0))--;
1659
1660           delete_insn_and_edges (next);
1661           ndead++;
1662         }
1663     }
1664
1665   delete_insn_and_edges (insn);
1666   ndead++;
1667 }
1668
1669 /* Delete dead libcalls for propagate_block.  Return the insn
1670    before the libcall.  */
1671
1672 static rtx
1673 propagate_block_delete_libcall (rtx insn, rtx note)
1674 {
1675   rtx first = XEXP (note, 0);
1676   rtx before = PREV_INSN (first);
1677
1678   delete_insn_chain_and_edges (first, insn);
1679   ndead++;
1680   return before;
1681 }
1682
1683 /* Update the life-status of regs for one insn.  Return the previous insn.  */
1684
1685 rtx
1686 propagate_one_insn (struct propagate_block_info *pbi, rtx insn)
1687 {
1688   rtx prev = PREV_INSN (insn);
1689   int flags = pbi->flags;
1690   int insn_is_dead = 0;
1691   int libcall_is_dead = 0;
1692   rtx note;
1693   unsigned i;
1694
1695   if (! INSN_P (insn))
1696     return prev;
1697
1698   note = find_reg_note (insn, REG_RETVAL, NULL_RTX);
1699   if (flags & PROP_SCAN_DEAD_CODE)
1700     {
1701       insn_is_dead = insn_dead_p (pbi, PATTERN (insn), 0, REG_NOTES (insn));
1702       libcall_is_dead = (insn_is_dead && note != 0
1703                          && libcall_dead_p (pbi, note, insn));
1704     }
1705
1706   /* If an instruction consists of just dead store(s) on final pass,
1707      delete it.  */
1708   if ((flags & PROP_KILL_DEAD_CODE) && insn_is_dead)
1709     {
1710       /* If we're trying to delete a prologue or epilogue instruction
1711          that isn't flagged as possibly being dead, something is wrong.
1712          But if we are keeping the stack pointer depressed, we might well
1713          be deleting insns that are used to compute the amount to update
1714          it by, so they are fine.  */
1715       if (reload_completed
1716           && !(TREE_CODE (TREE_TYPE (current_function_decl)) == FUNCTION_TYPE
1717                 && (TYPE_RETURNS_STACK_DEPRESSED
1718                     (TREE_TYPE (current_function_decl))))
1719           && (((HAVE_epilogue || HAVE_prologue)
1720                && prologue_epilogue_contains (insn))
1721               || (HAVE_sibcall_epilogue
1722                   && sibcall_epilogue_contains (insn)))
1723           && find_reg_note (insn, REG_MAYBE_DEAD, NULL_RTX) == 0)
1724         fatal_insn ("Attempt to delete prologue/epilogue insn:", insn);
1725
1726       /* Record sets.  Do this even for dead instructions, since they
1727          would have killed the values if they hadn't been deleted.  To
1728          be consistent, we also have to emit a clobber when we delete
1729          an insn that clobbers a live register.  */
1730       pbi->flags |= PROP_DEAD_INSN;
1731       mark_set_regs (pbi, PATTERN (insn), insn);
1732       pbi->flags &= ~PROP_DEAD_INSN;
1733
1734       /* CC0 is now known to be dead.  Either this insn used it,
1735          in which case it doesn't anymore, or clobbered it,
1736          so the next insn can't use it.  */
1737       pbi->cc0_live = 0;
1738
1739       if (libcall_is_dead)
1740         prev = propagate_block_delete_libcall (insn, note);
1741       else
1742         {
1743
1744         /* If INSN contains a RETVAL note and is dead, but the libcall
1745            as a whole is not dead, then we want to remove INSN, but
1746            not the whole libcall sequence.
1747
1748            However, we need to also remove the dangling REG_LIBCALL
1749            note so that we do not have mis-matched LIBCALL/RETVAL
1750            notes.  In theory we could find a new location for the
1751            REG_RETVAL note, but it hardly seems worth the effort.
1752
1753            NOTE at this point will be the RETVAL note if it exists.  */
1754           if (note)
1755             {
1756               rtx libcall_note;
1757
1758               libcall_note
1759                 = find_reg_note (XEXP (note, 0), REG_LIBCALL, NULL_RTX);
1760               remove_note (XEXP (note, 0), libcall_note);
1761             }
1762
1763           /* Similarly if INSN contains a LIBCALL note, remove the
1764              dangling REG_RETVAL note.  */
1765           note = find_reg_note (insn, REG_LIBCALL, NULL_RTX);
1766           if (note)
1767             {
1768               rtx retval_note;
1769
1770               retval_note
1771                 = find_reg_note (XEXP (note, 0), REG_RETVAL, NULL_RTX);
1772               remove_note (XEXP (note, 0), retval_note);
1773             }
1774
1775           /* Now delete INSN.  */
1776           propagate_block_delete_insn (insn);
1777         }
1778
1779       return prev;
1780     }
1781
1782   /* See if this is an increment or decrement that can be merged into
1783      a following memory address.  */
1784 #ifdef AUTO_INC_DEC
1785   {
1786     rtx x = single_set (insn);
1787
1788     /* Does this instruction increment or decrement a register?  */
1789     if ((flags & PROP_AUTOINC)
1790         && x != 0
1791         && REG_P (SET_DEST (x))
1792         && (GET_CODE (SET_SRC (x)) == PLUS
1793             || GET_CODE (SET_SRC (x)) == MINUS)
1794         && XEXP (SET_SRC (x), 0) == SET_DEST (x)
1795         && GET_CODE (XEXP (SET_SRC (x), 1)) == CONST_INT
1796         /* Ok, look for a following memory ref we can combine with.
1797            If one is found, change the memory ref to a PRE_INC
1798            or PRE_DEC, cancel this insn, and return 1.
1799            Return 0 if nothing has been done.  */
1800         && try_pre_increment_1 (pbi, insn))
1801       return prev;
1802   }
1803 #endif /* AUTO_INC_DEC */
1804
1805   CLEAR_REG_SET (pbi->new_set);
1806
1807   /* If this is not the final pass, and this insn is copying the value of
1808      a library call and it's dead, don't scan the insns that perform the
1809      library call, so that the call's arguments are not marked live.  */
1810   if (libcall_is_dead)
1811     {
1812       /* Record the death of the dest reg.  */
1813       mark_set_regs (pbi, PATTERN (insn), insn);
1814
1815       insn = XEXP (note, 0);
1816       return PREV_INSN (insn);
1817     }
1818   else if (GET_CODE (PATTERN (insn)) == SET
1819            && SET_DEST (PATTERN (insn)) == stack_pointer_rtx
1820            && GET_CODE (SET_SRC (PATTERN (insn))) == PLUS
1821            && XEXP (SET_SRC (PATTERN (insn)), 0) == stack_pointer_rtx
1822            && GET_CODE (XEXP (SET_SRC (PATTERN (insn)), 1)) == CONST_INT)
1823     {
1824       /* We have an insn to pop a constant amount off the stack.
1825          (Such insns use PLUS regardless of the direction of the stack,
1826          and any insn to adjust the stack by a constant is always a pop
1827          or part of a push.)
1828          These insns, if not dead stores, have no effect on life, though
1829          they do have an effect on the memory stores we are tracking.  */
1830       invalidate_mems_from_set (pbi, stack_pointer_rtx);
1831       /* Still, we need to update local_set, lest ifcvt.c:dead_or_predicable
1832          concludes that the stack pointer is not modified.  */
1833       mark_set_regs (pbi, PATTERN (insn), insn);
1834     }
1835   else
1836     {
1837       /* Any regs live at the time of a call instruction must not go
1838          in a register clobbered by calls.  Find all regs now live and
1839          record this for them.  */
1840
1841       if (CALL_P (insn) && (flags & PROP_REG_INFO))
1842         {
1843           reg_set_iterator rsi;
1844           EXECUTE_IF_SET_IN_REG_SET (pbi->reg_live, 0, i, rsi)
1845             REG_N_CALLS_CROSSED (i)++;
1846           if (can_throw_internal (insn))
1847             EXECUTE_IF_SET_IN_REG_SET (pbi->reg_live, 0, i, rsi)
1848               REG_N_THROWING_CALLS_CROSSED (i)++;
1849         }
1850
1851       /* Record sets.  Do this even for dead instructions, since they
1852          would have killed the values if they hadn't been deleted.  */
1853       mark_set_regs (pbi, PATTERN (insn), insn);
1854
1855       if (CALL_P (insn))
1856         {
1857           regset live_at_end;
1858           bool sibcall_p;
1859           rtx note, cond;
1860           int i;
1861
1862           cond = NULL_RTX;
1863           if (GET_CODE (PATTERN (insn)) == COND_EXEC)
1864             cond = COND_EXEC_TEST (PATTERN (insn));
1865
1866           /* Non-constant calls clobber memory, constant calls do not
1867              clobber memory, though they may clobber outgoing arguments
1868              on the stack.  */
1869           if (! CONST_OR_PURE_CALL_P (insn))
1870             {
1871               free_EXPR_LIST_list (&pbi->mem_set_list);
1872               pbi->mem_set_list_len = 0;
1873             }
1874           else
1875             invalidate_mems_from_set (pbi, stack_pointer_rtx);
1876
1877           /* There may be extra registers to be clobbered.  */
1878           for (note = CALL_INSN_FUNCTION_USAGE (insn);
1879                note;
1880                note = XEXP (note, 1))
1881             if (GET_CODE (XEXP (note, 0)) == CLOBBER)
1882               mark_set_1 (pbi, CLOBBER, XEXP (XEXP (note, 0), 0),
1883                           cond, insn, pbi->flags);
1884
1885           /* Calls change all call-used and global registers; sibcalls do not
1886              clobber anything that must be preserved at end-of-function,
1887              except for return values.  */
1888
1889           sibcall_p = SIBLING_CALL_P (insn);
1890           live_at_end = EXIT_BLOCK_PTR->il.rtl->global_live_at_start;
1891           for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1892             if (TEST_HARD_REG_BIT (regs_invalidated_by_call, i)
1893                 && ! (sibcall_p
1894                       && REGNO_REG_SET_P (live_at_end, i)
1895                       && ! refers_to_regno_p (i, i+1,
1896                                               current_function_return_rtx,
1897                                               (rtx *) 0)))
1898               {
1899                 enum rtx_code code = global_regs[i] ? SET : CLOBBER;
1900                 /* We do not want REG_UNUSED notes for these registers.  */
1901                 mark_set_1 (pbi, code, regno_reg_rtx[i], cond, insn,
1902                             pbi->flags & ~(PROP_DEATH_NOTES | PROP_REG_INFO));
1903               }
1904         }
1905
1906       /* If an insn doesn't use CC0, it becomes dead since we assume
1907          that every insn clobbers it.  So show it dead here;
1908          mark_used_regs will set it live if it is referenced.  */
1909       pbi->cc0_live = 0;
1910
1911       /* Record uses.  */
1912       if (! insn_is_dead)
1913         mark_used_regs (pbi, PATTERN (insn), NULL_RTX, insn);
1914
1915       /* Sometimes we may have inserted something before INSN (such as a move)
1916          when we make an auto-inc.  So ensure we will scan those insns.  */
1917 #ifdef AUTO_INC_DEC
1918       prev = PREV_INSN (insn);
1919 #endif
1920
1921       if (! insn_is_dead && CALL_P (insn))
1922         {
1923           int i;
1924           rtx note, cond;
1925
1926           cond = NULL_RTX;
1927           if (GET_CODE (PATTERN (insn)) == COND_EXEC)
1928             cond = COND_EXEC_TEST (PATTERN (insn));
1929
1930           /* Calls use their arguments, and may clobber memory which
1931              address involves some register.  */
1932           for (note = CALL_INSN_FUNCTION_USAGE (insn);
1933                note;
1934                note = XEXP (note, 1))
1935             /* We find USE or CLOBBER entities in a FUNCTION_USAGE list: both
1936                of which mark_used_regs knows how to handle.  */
1937             mark_used_regs (pbi, XEXP (XEXP (note, 0), 0), cond, insn);
1938
1939           /* The stack ptr is used (honorarily) by a CALL insn.  */
1940           if ((flags & PROP_REG_INFO)
1941               && !REGNO_REG_SET_P (pbi->reg_live, STACK_POINTER_REGNUM))
1942             reg_deaths[STACK_POINTER_REGNUM] = pbi->insn_num;
1943           SET_REGNO_REG_SET (pbi->reg_live, STACK_POINTER_REGNUM);
1944
1945           /* Calls may also reference any of the global registers,
1946              so they are made live.  */
1947           for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1948             if (global_regs[i])
1949               mark_used_reg (pbi, regno_reg_rtx[i], cond, insn);
1950         }
1951     }
1952
1953   pbi->insn_num++;
1954
1955   return prev;
1956 }
1957
1958 /* Initialize a propagate_block_info struct for public consumption.
1959    Note that the structure itself is opaque to this file, but that
1960    the user can use the regsets provided here.  */
1961
1962 struct propagate_block_info *
1963 init_propagate_block_info (basic_block bb, regset live, regset local_set,
1964                            regset cond_local_set, int flags)
1965 {
1966   struct propagate_block_info *pbi = XNEW (struct propagate_block_info);
1967
1968   pbi->bb = bb;
1969   pbi->reg_live = live;
1970   pbi->mem_set_list = NULL_RTX;
1971   pbi->mem_set_list_len = 0;
1972   pbi->local_set = local_set;
1973   pbi->cond_local_set = cond_local_set;
1974   pbi->cc0_live = 0;
1975   pbi->flags = flags;
1976   pbi->insn_num = 0;
1977
1978   if (flags & (PROP_LOG_LINKS | PROP_AUTOINC))
1979     pbi->reg_next_use = XCNEWVEC (rtx, max_reg_num ());
1980   else
1981     pbi->reg_next_use = NULL;
1982
1983   pbi->new_set = BITMAP_ALLOC (NULL);
1984
1985 #ifdef HAVE_conditional_execution
1986   pbi->reg_cond_dead = splay_tree_new (splay_tree_compare_ints, NULL,
1987                                        free_reg_cond_life_info);
1988   pbi->reg_cond_reg = BITMAP_ALLOC (NULL);
1989
1990   /* If this block ends in a conditional branch, for each register
1991      live from one side of the branch and not the other, record the
1992      register as conditionally dead.  */
1993   if (JUMP_P (BB_END (bb))
1994       && any_condjump_p (BB_END (bb)))
1995     {
1996       regset diff = ALLOC_REG_SET (&reg_obstack);
1997       basic_block bb_true, bb_false;
1998       unsigned i;
1999
2000       /* Identify the successor blocks.  */
2001       bb_true = EDGE_SUCC (bb, 0)->dest;
2002       if (!single_succ_p (bb))
2003         {
2004           bb_false = EDGE_SUCC (bb, 1)->dest;
2005
2006           if (EDGE_SUCC (bb, 0)->flags & EDGE_FALLTHRU)
2007             {
2008               basic_block t = bb_false;
2009               bb_false = bb_true;
2010               bb_true = t;
2011             }
2012           else
2013             gcc_assert (EDGE_SUCC (bb, 1)->flags & EDGE_FALLTHRU);
2014         }
2015       else
2016         {
2017           /* This can happen with a conditional jump to the next insn.  */
2018           gcc_assert (JUMP_LABEL (BB_END (bb)) == BB_HEAD (bb_true));
2019
2020           /* Simplest way to do nothing.  */
2021           bb_false = bb_true;
2022         }
2023
2024       /* Compute which register lead different lives in the successors.  */
2025       bitmap_xor (diff, bb_true->il.rtl->global_live_at_start,
2026                   bb_false->il.rtl->global_live_at_start);
2027       
2028       if (!bitmap_empty_p (diff))
2029           {
2030           /* Extract the condition from the branch.  */
2031           rtx set_src = SET_SRC (pc_set (BB_END (bb)));
2032           rtx cond_true = XEXP (set_src, 0);
2033           rtx reg = XEXP (cond_true, 0);
2034           enum rtx_code inv_cond;
2035
2036           if (GET_CODE (reg) == SUBREG)
2037             reg = SUBREG_REG (reg);
2038
2039           /* We can only track conditional lifetimes if the condition is
2040              in the form of a reversible comparison of a register against
2041              zero.  If the condition is more complex than that, then it is
2042              safe not to record any information.  */
2043           inv_cond = reversed_comparison_code (cond_true, BB_END (bb));
2044           if (inv_cond != UNKNOWN
2045               && REG_P (reg)
2046               && XEXP (cond_true, 1) == const0_rtx)
2047             {
2048               rtx cond_false
2049                 = gen_rtx_fmt_ee (inv_cond,
2050                                   GET_MODE (cond_true), XEXP (cond_true, 0),
2051                                   XEXP (cond_true, 1));
2052               reg_set_iterator rsi;
2053
2054               if (GET_CODE (XEXP (set_src, 1)) == PC)
2055                 {
2056                   rtx t = cond_false;
2057                   cond_false = cond_true;
2058                   cond_true = t;
2059                 }
2060
2061               SET_REGNO_REG_SET (pbi->reg_cond_reg, REGNO (reg));
2062
2063               /* For each such register, mark it conditionally dead.  */
2064               EXECUTE_IF_SET_IN_REG_SET (diff, 0, i, rsi)
2065                 {
2066                   struct reg_cond_life_info *rcli;
2067                   rtx cond;
2068
2069                   rcli = XNEW (struct reg_cond_life_info);
2070
2071                   if (REGNO_REG_SET_P (bb_true->il.rtl->global_live_at_start,
2072                                        i))
2073                     cond = cond_false;
2074                   else
2075                     cond = cond_true;
2076                   rcli->condition = cond;
2077                   rcli->stores = const0_rtx;
2078                   rcli->orig_condition = cond;
2079
2080                   splay_tree_insert (pbi->reg_cond_dead, i,
2081                                      (splay_tree_value) rcli);
2082                 }
2083             }
2084         }
2085
2086       FREE_REG_SET (diff);
2087     }
2088 #endif
2089
2090   /* If this block has no successors, any stores to the frame that aren't
2091      used later in the block are dead.  So make a pass over the block
2092      recording any such that are made and show them dead at the end.  We do
2093      a very conservative and simple job here.  */
2094   if (optimize
2095       && ! (TREE_CODE (TREE_TYPE (current_function_decl)) == FUNCTION_TYPE
2096             && (TYPE_RETURNS_STACK_DEPRESSED
2097                 (TREE_TYPE (current_function_decl))))
2098       && (flags & PROP_SCAN_DEAD_STORES)
2099       && (EDGE_COUNT (bb->succs) == 0
2100           || (single_succ_p (bb)
2101               && single_succ (bb) == EXIT_BLOCK_PTR
2102               && ! current_function_calls_eh_return)))
2103     {
2104       rtx insn, set;
2105       for (insn = BB_END (bb); insn != BB_HEAD (bb); insn = PREV_INSN (insn))
2106         if (NONJUMP_INSN_P (insn)
2107             && (set = single_set (insn))
2108             && MEM_P (SET_DEST (set)))
2109           {
2110             rtx mem = SET_DEST (set);
2111             rtx canon_mem = canon_rtx (mem);
2112
2113             if (XEXP (canon_mem, 0) == frame_pointer_rtx
2114                 || (GET_CODE (XEXP (canon_mem, 0)) == PLUS
2115                     && XEXP (XEXP (canon_mem, 0), 0) == frame_pointer_rtx
2116                     && GET_CODE (XEXP (XEXP (canon_mem, 0), 1)) == CONST_INT))
2117               add_to_mem_set_list (pbi, canon_mem);
2118           }
2119     }
2120
2121   return pbi;
2122 }
2123
2124 /* Release a propagate_block_info struct.  */
2125
2126 void
2127 free_propagate_block_info (struct propagate_block_info *pbi)
2128 {
2129   free_EXPR_LIST_list (&pbi->mem_set_list);
2130
2131   BITMAP_FREE (pbi->new_set);
2132
2133 #ifdef HAVE_conditional_execution
2134   splay_tree_delete (pbi->reg_cond_dead);
2135   BITMAP_FREE (pbi->reg_cond_reg);
2136 #endif
2137
2138   if (pbi->flags & PROP_REG_INFO)
2139     {
2140       int num = pbi->insn_num;
2141       unsigned i;
2142       reg_set_iterator rsi;
2143
2144       EXECUTE_IF_SET_IN_REG_SET (pbi->reg_live, 0, i, rsi)
2145         {
2146           REG_LIVE_LENGTH (i) += num - reg_deaths[i];
2147           reg_deaths[i] = 0;
2148         }
2149     }
2150   if (pbi->reg_next_use)
2151     free (pbi->reg_next_use);
2152
2153   free (pbi);
2154 }
2155
2156 /* Compute the registers live at the beginning of a basic block BB from
2157    those live at the end.
2158
2159    When called, REG_LIVE contains those live at the end.  On return, it
2160    contains those live at the beginning.
2161
2162    LOCAL_SET, if non-null, will be set with all registers killed
2163    unconditionally by this basic block.
2164    Likewise, COND_LOCAL_SET, if non-null, will be set with all registers
2165    killed conditionally by this basic block.  If there is any unconditional
2166    set of a register, then the corresponding bit will be set in LOCAL_SET
2167    and cleared in COND_LOCAL_SET.
2168    It is valid for LOCAL_SET and COND_LOCAL_SET to be the same set.  In this
2169    case, the resulting set will be equal to the union of the two sets that
2170    would otherwise be computed.
2171
2172    Return nonzero if an INSN is deleted (i.e. by dead code removal).  */
2173
2174 int
2175 propagate_block (basic_block bb, regset live, regset local_set,
2176                  regset cond_local_set, int flags)
2177 {
2178   struct propagate_block_info *pbi;
2179   rtx insn, prev;
2180   int changed;
2181
2182   pbi = init_propagate_block_info (bb, live, local_set, cond_local_set, flags);
2183
2184   if (flags & PROP_REG_INFO)
2185     {
2186       unsigned i;
2187       reg_set_iterator rsi;
2188
2189       /* Process the regs live at the end of the block.
2190          Mark them as not local to any one basic block.  */
2191       EXECUTE_IF_SET_IN_REG_SET (live, 0, i, rsi)
2192         REG_BASIC_BLOCK (i) = REG_BLOCK_GLOBAL;
2193     }
2194
2195   /* Scan the block an insn at a time from end to beginning.  */
2196
2197   changed = 0;
2198   for (insn = BB_END (bb); ; insn = prev)
2199     {
2200       /* If this is a call to `setjmp' et al, warn if any
2201          non-volatile datum is live.  */
2202       if ((flags & PROP_REG_INFO)
2203           && CALL_P (insn)
2204           && find_reg_note (insn, REG_SETJMP, NULL))
2205         IOR_REG_SET (regs_live_at_setjmp, pbi->reg_live);
2206
2207       prev = propagate_one_insn (pbi, insn);
2208       if (!prev)
2209         changed |= insn != get_insns ();
2210       else
2211         changed |= NEXT_INSN (prev) != insn;
2212
2213       if (insn == BB_HEAD (bb))
2214         break;
2215     }
2216
2217   free_propagate_block_info (pbi);
2218
2219   return changed;
2220 }
2221 \f
2222 /* Return 1 if X (the body of an insn, or part of it) is just dead stores
2223    (SET expressions whose destinations are registers dead after the insn).
2224    NEEDED is the regset that says which regs are alive after the insn.
2225
2226    Unless CALL_OK is nonzero, an insn is needed if it contains a CALL.
2227
2228    If X is the entire body of an insn, NOTES contains the reg notes
2229    pertaining to the insn.  */
2230
2231 static int
2232 insn_dead_p (struct propagate_block_info *pbi, rtx x, int call_ok,
2233              rtx notes ATTRIBUTE_UNUSED)
2234 {
2235   enum rtx_code code = GET_CODE (x);
2236
2237   /* Don't eliminate insns that may trap.  */
2238   if (flag_non_call_exceptions && may_trap_p (x))
2239     return 0;
2240
2241 #ifdef AUTO_INC_DEC
2242   /* As flow is invoked after combine, we must take existing AUTO_INC
2243      expressions into account.  */
2244   for (; notes; notes = XEXP (notes, 1))
2245     {
2246       if (REG_NOTE_KIND (notes) == REG_INC)
2247         {
2248           int regno = REGNO (XEXP (notes, 0));
2249
2250           /* Don't delete insns to set global regs.  */
2251           if ((regno < FIRST_PSEUDO_REGISTER && global_regs[regno])
2252               || REGNO_REG_SET_P (pbi->reg_live, regno))
2253             return 0;
2254         }
2255     }
2256 #endif
2257
2258   /* If setting something that's a reg or part of one,
2259      see if that register's altered value will be live.  */
2260
2261   if (code == SET)
2262     {
2263       rtx r = SET_DEST (x);
2264
2265 #ifdef HAVE_cc0
2266       if (GET_CODE (r) == CC0)
2267         return ! pbi->cc0_live;
2268 #endif
2269
2270       /* A SET that is a subroutine call cannot be dead.  */
2271       if (GET_CODE (SET_SRC (x)) == CALL)
2272         {
2273           if (! call_ok)
2274             return 0;
2275         }
2276
2277       /* Don't eliminate loads from volatile memory or volatile asms.  */
2278       else if (volatile_refs_p (SET_SRC (x)))
2279         return 0;
2280
2281       if (MEM_P (r))
2282         {
2283           rtx temp, canon_r;
2284
2285           if (MEM_VOLATILE_P (r) || GET_MODE (r) == BLKmode)
2286             return 0;
2287
2288           canon_r = canon_rtx (r);
2289
2290           /* Walk the set of memory locations we are currently tracking
2291              and see if one is an identical match to this memory location.
2292              If so, this memory write is dead (remember, we're walking
2293              backwards from the end of the block to the start).  Since
2294              rtx_equal_p does not check the alias set or flags, we also
2295              must have the potential for them to conflict (anti_dependence).  */
2296           for (temp = pbi->mem_set_list; temp != 0; temp = XEXP (temp, 1))
2297             if (anti_dependence (r, XEXP (temp, 0)))
2298               {
2299                 rtx mem = XEXP (temp, 0);
2300
2301                 if (rtx_equal_p (XEXP (canon_r, 0), XEXP (mem, 0))
2302                     && (GET_MODE_SIZE (GET_MODE (canon_r))
2303                         <= GET_MODE_SIZE (GET_MODE (mem))))
2304                   return 1;
2305
2306 #ifdef AUTO_INC_DEC
2307                 /* Check if memory reference matches an auto increment. Only
2308                    post increment/decrement or modify are valid.  */
2309                 if (GET_MODE (mem) == GET_MODE (r)
2310                     && (GET_CODE (XEXP (mem, 0)) == POST_DEC
2311                         || GET_CODE (XEXP (mem, 0)) == POST_INC
2312                         || GET_CODE (XEXP (mem, 0)) == POST_MODIFY)
2313                     && GET_MODE (XEXP (mem, 0)) == GET_MODE (r)
2314                     && rtx_equal_p (XEXP (XEXP (mem, 0), 0), XEXP (r, 0)))
2315                   return 1;
2316 #endif
2317               }
2318         }
2319       else
2320         {
2321           while (GET_CODE (r) == SUBREG
2322                  || GET_CODE (r) == STRICT_LOW_PART
2323                  || GET_CODE (r) == ZERO_EXTRACT)
2324             r = XEXP (r, 0);
2325
2326           if (REG_P (r))
2327             {
2328               int regno = REGNO (r);
2329
2330               /* Obvious.  */
2331               if (REGNO_REG_SET_P (pbi->reg_live, regno))
2332                 return 0;
2333
2334               /* If this is a hard register, verify that subsequent
2335                  words are not needed.  */
2336               if (regno < FIRST_PSEUDO_REGISTER)
2337                 {
2338                   int n = hard_regno_nregs[regno][GET_MODE (r)];
2339
2340                   while (--n > 0)
2341                     if (REGNO_REG_SET_P (pbi->reg_live, regno+n))
2342                       return 0;
2343                 }
2344
2345               /* Don't delete insns to set global regs.  */
2346               if (regno < FIRST_PSEUDO_REGISTER && global_regs[regno])
2347                 return 0;
2348
2349               /* Make sure insns to set the stack pointer aren't deleted.  */
2350               if (regno == STACK_POINTER_REGNUM)
2351                 return 0;
2352
2353               /* ??? These bits might be redundant with the force live bits
2354                  in calculate_global_regs_live.  We would delete from
2355                  sequential sets; whether this actually affects real code
2356                  for anything but the stack pointer I don't know.  */
2357               /* Make sure insns to set the frame pointer aren't deleted.  */
2358               if (regno == FRAME_POINTER_REGNUM
2359                   && (! reload_completed || frame_pointer_needed))
2360                 return 0;
2361 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
2362               if (regno == HARD_FRAME_POINTER_REGNUM
2363                   && (! reload_completed || frame_pointer_needed))
2364                 return 0;
2365 #endif
2366
2367 #if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
2368               /* Make sure insns to set arg pointer are never deleted
2369                  (if the arg pointer isn't fixed, there will be a USE
2370                  for it, so we can treat it normally).  */
2371               if (regno == ARG_POINTER_REGNUM && fixed_regs[regno])
2372                 return 0;
2373 #endif
2374
2375               /* Otherwise, the set is dead.  */
2376               return 1;
2377             }
2378         }
2379     }
2380
2381   /* If performing several activities, insn is dead if each activity
2382      is individually dead.  Also, CLOBBERs and USEs can be ignored; a
2383      CLOBBER or USE that's inside a PARALLEL doesn't make the insn
2384      worth keeping.  */
2385   else if (code == PARALLEL)
2386     {
2387       int i = XVECLEN (x, 0);
2388
2389       for (i--; i >= 0; i--)
2390         if (GET_CODE (XVECEXP (x, 0, i)) != CLOBBER
2391             && GET_CODE (XVECEXP (x, 0, i)) != USE
2392             && ! insn_dead_p (pbi, XVECEXP (x, 0, i), call_ok, NULL_RTX))
2393           return 0;
2394
2395       return 1;
2396     }
2397
2398   /* A CLOBBER of a pseudo-register that is dead serves no purpose.  That
2399      is not necessarily true for hard registers until after reload.  */
2400   else if (code == CLOBBER)
2401     {
2402       if (REG_P (XEXP (x, 0))
2403           && (REGNO (XEXP (x, 0)) >= FIRST_PSEUDO_REGISTER
2404               || reload_completed)
2405           && ! REGNO_REG_SET_P (pbi->reg_live, REGNO (XEXP (x, 0))))
2406         return 1;
2407     }
2408
2409   /* ??? A base USE is a historical relic.  It ought not be needed anymore.
2410      Instances where it is still used are either (1) temporary and the USE
2411      escaped the pass, (2) cruft and the USE need not be emitted anymore,
2412      or (3) hiding bugs elsewhere that are not properly representing data
2413      flow.  */
2414
2415   return 0;
2416 }
2417
2418 /* If INSN is the last insn in a libcall, and assuming INSN is dead,
2419    return 1 if the entire library call is dead.
2420    This is true if INSN copies a register (hard or pseudo)
2421    and if the hard return reg of the call insn is dead.
2422    (The caller should have tested the destination of the SET inside
2423    INSN already for death.)
2424
2425    If this insn doesn't just copy a register, then we don't
2426    have an ordinary libcall.  In that case, cse could not have
2427    managed to substitute the source for the dest later on,
2428    so we can assume the libcall is dead.
2429
2430    PBI is the block info giving pseudoregs live before this insn.
2431    NOTE is the REG_RETVAL note of the insn.  */
2432
2433 static int
2434 libcall_dead_p (struct propagate_block_info *pbi, rtx note, rtx insn)
2435 {
2436   rtx x = single_set (insn);
2437
2438   if (x)
2439     {
2440       rtx r = SET_SRC (x);
2441
2442       if (REG_P (r) || GET_CODE (r) == SUBREG)
2443         {
2444           rtx call = XEXP (note, 0);
2445           rtx call_pat;
2446           int i;
2447
2448           /* Find the call insn.  */
2449           while (call != insn && !CALL_P (call))
2450             call = NEXT_INSN (call);
2451
2452           /* If there is none, do nothing special,
2453              since ordinary death handling can understand these insns.  */
2454           if (call == insn)
2455             return 0;
2456
2457           /* See if the hard reg holding the value is dead.
2458              If this is a PARALLEL, find the call within it.  */
2459           call_pat = PATTERN (call);
2460           if (GET_CODE (call_pat) == PARALLEL)
2461             {
2462               for (i = XVECLEN (call_pat, 0) - 1; i >= 0; i--)
2463                 if (GET_CODE (XVECEXP (call_pat, 0, i)) == SET
2464                     && GET_CODE (SET_SRC (XVECEXP (call_pat, 0, i))) == CALL)
2465                   break;
2466
2467               /* This may be a library call that is returning a value
2468                  via invisible pointer.  Do nothing special, since
2469                  ordinary death handling can understand these insns.  */
2470               if (i < 0)
2471                 return 0;
2472
2473               call_pat = XVECEXP (call_pat, 0, i);
2474             }
2475
2476           if (! insn_dead_p (pbi, call_pat, 1, REG_NOTES (call)))
2477             return 0;
2478
2479           while ((insn = PREV_INSN (insn)) != call)
2480             {
2481               if (! INSN_P (insn))
2482                 continue;
2483               if (! insn_dead_p (pbi, PATTERN (insn), 0, REG_NOTES (insn)))
2484                 return 0;
2485             }
2486           return 1;
2487         }
2488     }
2489   return 0;
2490 }
2491
2492 /* 1 if register REGNO was alive at a place where `setjmp' was called
2493    and was set more than once or is an argument.
2494    Such regs may be clobbered by `longjmp'.  */
2495
2496 int
2497 regno_clobbered_at_setjmp (int regno)
2498 {
2499   if (n_basic_blocks == NUM_FIXED_BLOCKS)
2500     return 0;
2501
2502   return ((REG_N_SETS (regno) > 1
2503            || REGNO_REG_SET_P (ENTRY_BLOCK_PTR->il.rtl->global_live_at_end,
2504                                regno))
2505           && REGNO_REG_SET_P (regs_live_at_setjmp, regno));
2506 }
2507 \f
2508 /* Add MEM to PBI->MEM_SET_LIST.  MEM should be canonical.  Respect the
2509    maximal list size; look for overlaps in mode and select the largest.  */
2510 static void
2511 add_to_mem_set_list (struct propagate_block_info *pbi, rtx mem)
2512 {
2513   rtx i;
2514
2515   /* We don't know how large a BLKmode store is, so we must not
2516      take them into consideration.  */
2517   if (GET_MODE (mem) == BLKmode)
2518     return;
2519
2520   for (i = pbi->mem_set_list; i ; i = XEXP (i, 1))
2521     {
2522       rtx e = XEXP (i, 0);
2523       if (rtx_equal_p (XEXP (mem, 0), XEXP (e, 0)))
2524         {
2525           if (GET_MODE_SIZE (GET_MODE (mem)) > GET_MODE_SIZE (GET_MODE (e)))
2526             {
2527 #ifdef AUTO_INC_DEC
2528               /* If we must store a copy of the mem, we can just modify
2529                  the mode of the stored copy.  */
2530               if (pbi->flags & PROP_AUTOINC)
2531                 PUT_MODE (e, GET_MODE (mem));
2532               else
2533 #endif
2534                 XEXP (i, 0) = mem;
2535             }
2536           return;
2537         }
2538     }
2539
2540   if (pbi->mem_set_list_len < PARAM_VALUE (PARAM_MAX_FLOW_MEMORY_LOCATIONS))
2541     {
2542 #ifdef AUTO_INC_DEC
2543       /* Store a copy of mem, otherwise the address may be
2544          scrogged by find_auto_inc.  */
2545       if (pbi->flags & PROP_AUTOINC)
2546         mem = shallow_copy_rtx (mem);
2547 #endif
2548       pbi->mem_set_list = alloc_EXPR_LIST (0, mem, pbi->mem_set_list);
2549       pbi->mem_set_list_len++;
2550     }
2551 }
2552
2553 /* INSN references memory, possibly using autoincrement addressing modes.
2554    Find any entries on the mem_set_list that need to be invalidated due
2555    to an address change.  */
2556
2557 static int
2558 invalidate_mems_from_autoinc (rtx *px, void *data)
2559 {
2560   rtx x = *px;
2561   struct propagate_block_info *pbi = data;
2562
2563   if (GET_RTX_CLASS (GET_CODE (x)) == RTX_AUTOINC)
2564     {
2565       invalidate_mems_from_set (pbi, XEXP (x, 0));
2566       return -1;
2567     }
2568
2569   return 0;
2570 }
2571
2572 /* EXP is a REG or MEM.  Remove any dependent entries from
2573    pbi->mem_set_list.  */
2574
2575 static void
2576 invalidate_mems_from_set (struct propagate_block_info *pbi, rtx exp)
2577 {
2578   rtx temp = pbi->mem_set_list;
2579   rtx prev = NULL_RTX;
2580   rtx next;
2581
2582   while (temp)
2583     {
2584       next = XEXP (temp, 1);
2585       if ((REG_P (exp) && reg_overlap_mentioned_p (exp, XEXP (temp, 0)))
2586           /* When we get an EXP that is a mem here, we want to check if EXP
2587              overlaps the *address* of any of the mems in the list (i.e. not
2588              whether the mems actually overlap; that's done elsewhere).  */
2589           || (MEM_P (exp)
2590               && reg_overlap_mentioned_p (exp, XEXP (XEXP (temp, 0), 0))))
2591         {
2592           /* Splice this entry out of the list.  */
2593           if (prev)
2594             XEXP (prev, 1) = next;
2595           else
2596             pbi->mem_set_list = next;
2597           free_EXPR_LIST_node (temp);
2598           pbi->mem_set_list_len--;
2599         }
2600       else
2601         prev = temp;
2602       temp = next;
2603     }
2604 }
2605
2606 /* Process the registers that are set within X.  Their bits are set to
2607    1 in the regset DEAD, because they are dead prior to this insn.
2608
2609    If INSN is nonzero, it is the insn being processed.
2610
2611    FLAGS is the set of operations to perform.  */
2612
2613 static void
2614 mark_set_regs (struct propagate_block_info *pbi, rtx x, rtx insn)
2615 {
2616   rtx cond = NULL_RTX;
2617   rtx link;
2618   enum rtx_code code;
2619   int flags = pbi->flags;
2620
2621   if (insn)
2622     for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
2623       {
2624         if (REG_NOTE_KIND (link) == REG_INC)
2625           mark_set_1 (pbi, SET, XEXP (link, 0),
2626                       (GET_CODE (x) == COND_EXEC
2627                        ? COND_EXEC_TEST (x) : NULL_RTX),
2628                       insn, flags);
2629       }
2630  retry:
2631   switch (code = GET_CODE (x))
2632     {
2633     case SET:
2634       if (GET_CODE (XEXP (x, 1)) == ASM_OPERANDS)
2635         flags |= PROP_ASM_SCAN;
2636       /* Fall through */
2637     case CLOBBER:
2638       mark_set_1 (pbi, code, SET_DEST (x), cond, insn, flags);
2639       return;
2640
2641     case COND_EXEC:
2642       cond = COND_EXEC_TEST (x);
2643       x = COND_EXEC_CODE (x);
2644       goto retry;
2645
2646     case PARALLEL:
2647       {
2648         int i;
2649
2650         /* We must scan forwards.  If we have an asm, we need to set
2651            the PROP_ASM_SCAN flag before scanning the clobbers.  */
2652         for (i = 0; i < XVECLEN (x, 0); i++)
2653           {
2654             rtx sub = XVECEXP (x, 0, i);
2655             switch (code = GET_CODE (sub))
2656               {
2657               case COND_EXEC:
2658                 gcc_assert (!cond);
2659
2660                 cond = COND_EXEC_TEST (sub);
2661                 sub = COND_EXEC_CODE (sub);
2662                 if (GET_CODE (sub) == SET)
2663                   goto mark_set;
2664                 if (GET_CODE (sub) == CLOBBER)
2665                   goto mark_clob;
2666                 break;
2667
2668               case SET:
2669               mark_set:
2670                 if (GET_CODE (XEXP (sub, 1)) == ASM_OPERANDS)
2671                   flags |= PROP_ASM_SCAN;
2672                 /* Fall through */
2673               case CLOBBER:
2674               mark_clob:
2675                 mark_set_1 (pbi, code, SET_DEST (sub), cond, insn, flags);
2676                 break;
2677
2678               case ASM_OPERANDS:
2679                 flags |= PROP_ASM_SCAN;
2680                 break;
2681
2682               default:
2683                 break;
2684               }
2685           }
2686         break;
2687       }
2688
2689     default:
2690       break;
2691     }
2692 }
2693
2694 /* Process a single set, which appears in INSN.  REG (which may not
2695    actually be a REG, it may also be a SUBREG, PARALLEL, etc.) is
2696    being set using the CODE (which may be SET, CLOBBER, or COND_EXEC).
2697    If the set is conditional (because it appear in a COND_EXEC), COND
2698    will be the condition.  */
2699
2700 static void
2701 mark_set_1 (struct propagate_block_info *pbi, enum rtx_code code, rtx reg, rtx cond, rtx insn, int flags)
2702 {
2703   int regno_first = -1, regno_last = -1;
2704   unsigned long not_dead = 0;
2705   int i;
2706
2707   /* Modifying just one hardware register of a multi-reg value or just a
2708      byte field of a register does not mean the value from before this insn
2709      is now dead.  Of course, if it was dead after it's unused now.  */
2710
2711   switch (GET_CODE (reg))
2712     {
2713     case PARALLEL:
2714       /* Some targets place small structures in registers for return values of
2715          functions.  We have to detect this case specially here to get correct
2716          flow information.  */
2717       for (i = XVECLEN (reg, 0) - 1; i >= 0; i--)
2718         if (XEXP (XVECEXP (reg, 0, i), 0) != 0)
2719           mark_set_1 (pbi, code, XEXP (XVECEXP (reg, 0, i), 0), cond, insn,
2720                       flags);
2721       return;
2722
2723     case SIGN_EXTRACT:
2724       /* SIGN_EXTRACT cannot be an lvalue.  */
2725       gcc_unreachable ();
2726
2727     case ZERO_EXTRACT:
2728     case STRICT_LOW_PART:
2729       /* ??? Assumes STRICT_LOW_PART not used on multi-word registers.  */
2730       do
2731         reg = XEXP (reg, 0);
2732       while (GET_CODE (reg) == SUBREG
2733              || GET_CODE (reg) == ZERO_EXTRACT
2734              || GET_CODE (reg) == STRICT_LOW_PART);
2735       if (MEM_P (reg))
2736         break;
2737       not_dead = (unsigned long) REGNO_REG_SET_P (pbi->reg_live, REGNO (reg));
2738       /* Fall through.  */
2739
2740     case REG:
2741       regno_last = regno_first = REGNO (reg);
2742       if (regno_first < FIRST_PSEUDO_REGISTER)
2743         regno_last += hard_regno_nregs[regno_first][GET_MODE (reg)] - 1;
2744       break;
2745
2746     case SUBREG:
2747       if (REG_P (SUBREG_REG (reg)))
2748         {
2749           enum machine_mode outer_mode = GET_MODE (reg);
2750           enum machine_mode inner_mode = GET_MODE (SUBREG_REG (reg));
2751
2752           /* Identify the range of registers affected.  This is moderately
2753              tricky for hard registers.  See alter_subreg.  */
2754
2755           regno_last = regno_first = REGNO (SUBREG_REG (reg));
2756           if (regno_first < FIRST_PSEUDO_REGISTER)
2757             {
2758               regno_first += subreg_regno_offset (regno_first, inner_mode,
2759                                                   SUBREG_BYTE (reg),
2760                                                   outer_mode);
2761               regno_last = (regno_first
2762                             + hard_regno_nregs[regno_first][outer_mode] - 1);
2763
2764               /* Since we've just adjusted the register number ranges, make
2765                  sure REG matches.  Otherwise some_was_live will be clear
2766                  when it shouldn't have been, and we'll create incorrect
2767                  REG_UNUSED notes.  */
2768               reg = gen_rtx_REG (outer_mode, regno_first);
2769             }
2770           else
2771             {
2772               /* If the number of words in the subreg is less than the number
2773                  of words in the full register, we have a well-defined partial
2774                  set.  Otherwise the high bits are undefined.
2775
2776                  This is only really applicable to pseudos, since we just took
2777                  care of multi-word hard registers.  */
2778               if (((GET_MODE_SIZE (outer_mode)
2779                     + UNITS_PER_WORD - 1) / UNITS_PER_WORD)
2780                   < ((GET_MODE_SIZE (inner_mode)
2781                       + UNITS_PER_WORD - 1) / UNITS_PER_WORD))
2782                 not_dead = (unsigned long) REGNO_REG_SET_P (pbi->reg_live,
2783                                                             regno_first);
2784
2785               reg = SUBREG_REG (reg);
2786             }
2787         }
2788       else
2789         reg = SUBREG_REG (reg);
2790       break;
2791
2792     default:
2793       break;
2794     }
2795
2796   /* If this set is a MEM, then it kills any aliased writes and any
2797      other MEMs which use it.
2798      If this set is a REG, then it kills any MEMs which use the reg.  */
2799   if (optimize && (flags & PROP_SCAN_DEAD_STORES))
2800     {
2801       if (REG_P (reg) || MEM_P (reg))
2802         invalidate_mems_from_set (pbi, reg);
2803
2804       /* If the memory reference had embedded side effects (autoincrement
2805          address modes) then we may need to kill some entries on the
2806          memory set list.  */
2807       if (insn && MEM_P (reg))
2808         for_each_rtx (&PATTERN (insn), invalidate_mems_from_autoinc, pbi);
2809
2810       if (MEM_P (reg) && ! side_effects_p (reg)
2811           /* ??? With more effort we could track conditional memory life.  */
2812           && ! cond)
2813         add_to_mem_set_list (pbi, canon_rtx (reg));
2814     }
2815
2816   if (REG_P (reg)
2817       && ! (regno_first == FRAME_POINTER_REGNUM
2818             && (! reload_completed || frame_pointer_needed))
2819 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
2820       && ! (regno_first == HARD_FRAME_POINTER_REGNUM
2821             && (! reload_completed || frame_pointer_needed))
2822 #endif
2823 #if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
2824       && ! (regno_first == ARG_POINTER_REGNUM && fixed_regs[regno_first])
2825 #endif
2826       )
2827     {
2828       int some_was_live = 0, some_was_dead = 0;
2829
2830       for (i = regno_first; i <= regno_last; ++i)
2831         {
2832           int needed_regno = REGNO_REG_SET_P (pbi->reg_live, i);
2833           if (pbi->local_set)
2834             {
2835               /* Order of the set operation matters here since both
2836                  sets may be the same.  */
2837               CLEAR_REGNO_REG_SET (pbi->cond_local_set, i);
2838               if (cond != NULL_RTX
2839                   && ! REGNO_REG_SET_P (pbi->local_set, i))
2840                 SET_REGNO_REG_SET (pbi->cond_local_set, i);
2841               else
2842                 SET_REGNO_REG_SET (pbi->local_set, i);
2843             }
2844           if (code != CLOBBER || needed_regno)
2845             SET_REGNO_REG_SET (pbi->new_set, i);
2846
2847           some_was_live |= needed_regno;
2848           some_was_dead |= ! needed_regno;
2849         }
2850
2851 #ifdef HAVE_conditional_execution
2852       /* Consider conditional death in deciding that the register needs
2853          a death note.  */
2854       if (some_was_live && ! not_dead
2855           /* The stack pointer is never dead.  Well, not strictly true,
2856              but it's very difficult to tell from here.  Hopefully
2857              combine_stack_adjustments will fix up the most egregious
2858              errors.  */
2859           && regno_first != STACK_POINTER_REGNUM)
2860         {
2861           for (i = regno_first; i <= regno_last; ++i)
2862             if (! mark_regno_cond_dead (pbi, i, cond))
2863               not_dead |= ((unsigned long) 1) << (i - regno_first);
2864         }
2865 #endif
2866
2867       /* Additional data to record if this is the final pass.  */
2868       if (flags & (PROP_LOG_LINKS | PROP_REG_INFO
2869                    | PROP_DEATH_NOTES | PROP_AUTOINC))
2870         {
2871           rtx y;
2872           int blocknum = pbi->bb->index;
2873
2874           y = NULL_RTX;
2875           if (flags & (PROP_LOG_LINKS | PROP_AUTOINC))
2876             {
2877               y = pbi->reg_next_use[regno_first];
2878
2879               /* The next use is no longer next, since a store intervenes.  */
2880               for (i = regno_first; i <= regno_last; ++i)
2881                 pbi->reg_next_use[i] = 0;
2882             }
2883
2884           if (flags & PROP_REG_INFO)
2885             {
2886               for (i = regno_first; i <= regno_last; ++i)
2887                 {
2888                   /* Count (weighted) references, stores, etc.  This counts a
2889                      register twice if it is modified, but that is correct.  */
2890                   REG_N_SETS (i) += 1;
2891                   REG_N_REFS (i) += 1;
2892                   REG_FREQ (i) += REG_FREQ_FROM_BB (pbi->bb);
2893
2894                   /* The insns where a reg is live are normally counted
2895                      elsewhere, but we want the count to include the insn
2896                      where the reg is set, and the normal counting mechanism
2897                      would not count it.  */
2898                   REG_LIVE_LENGTH (i) += 1;
2899                 }
2900
2901               /* If this is a hard reg, record this function uses the reg.  */
2902               if (regno_first < FIRST_PSEUDO_REGISTER)
2903                 {
2904                   for (i = regno_first; i <= regno_last; i++)
2905                     regs_ever_live[i] = 1;
2906                   if (flags & PROP_ASM_SCAN)
2907                     for (i = regno_first; i <= regno_last; i++)
2908                       regs_asm_clobbered[i] = 1;
2909                 }
2910               else
2911                 {
2912                   /* Keep track of which basic blocks each reg appears in.  */
2913                   if (REG_BASIC_BLOCK (regno_first) == REG_BLOCK_UNKNOWN)
2914                     REG_BASIC_BLOCK (regno_first) = blocknum;
2915                   else if (REG_BASIC_BLOCK (regno_first) != blocknum)
2916                     REG_BASIC_BLOCK (regno_first) = REG_BLOCK_GLOBAL;
2917                 }
2918             }
2919
2920           if (! some_was_dead)
2921             {
2922               if (flags & PROP_LOG_LINKS)
2923                 {
2924                   /* Make a logical link from the next following insn
2925                      that uses this register, back to this insn.
2926                      The following insns have already been processed.
2927
2928                      We don't build a LOG_LINK for hard registers containing
2929                      in ASM_OPERANDs.  If these registers get replaced,
2930                      we might wind up changing the semantics of the insn,
2931                      even if reload can make what appear to be valid
2932                      assignments later.
2933
2934                      We don't build a LOG_LINK for global registers to
2935                      or from a function call.  We don't want to let
2936                      combine think that it knows what is going on with
2937                      global registers.  */
2938                   if (y && (BLOCK_NUM (y) == blocknum)
2939                       && (regno_first >= FIRST_PSEUDO_REGISTER
2940                           || (asm_noperands (PATTERN (y)) < 0
2941                               && ! ((CALL_P (insn)
2942                                      || CALL_P (y))
2943                                     && global_regs[regno_first]))))
2944                     LOG_LINKS (y) = alloc_INSN_LIST (insn, LOG_LINKS (y));
2945                 }
2946             }
2947           else if (not_dead)
2948             ;
2949           else if (! some_was_live)
2950             {
2951               if (flags & PROP_REG_INFO)
2952                 REG_N_DEATHS (regno_first) += 1;
2953
2954               if (flags & PROP_DEATH_NOTES
2955 #ifdef STACK_REGS
2956                   && (!(flags & PROP_POST_REGSTACK)
2957                       || !IN_RANGE (REGNO (reg), FIRST_STACK_REG,
2958                                     LAST_STACK_REG))
2959 #endif
2960                   )
2961                 {
2962                   /* Note that dead stores have already been deleted
2963                      when possible.  If we get here, we have found a
2964                      dead store that cannot be eliminated (because the
2965                      same insn does something useful).  Indicate this
2966                      by marking the reg being set as dying here.  */
2967                   REG_NOTES (insn)
2968                     = alloc_EXPR_LIST (REG_UNUSED, reg, REG_NOTES (insn));
2969                 }
2970             }
2971           else
2972             {
2973               if (flags & PROP_DEATH_NOTES
2974 #ifdef STACK_REGS
2975                   && (!(flags & PROP_POST_REGSTACK)
2976                       || !IN_RANGE (REGNO (reg), FIRST_STACK_REG,
2977                                     LAST_STACK_REG))
2978 #endif
2979                   )
2980                 {
2981                   /* This is a case where we have a multi-word hard register
2982                      and some, but not all, of the words of the register are
2983                      needed in subsequent insns.  Write REG_UNUSED notes
2984                      for those parts that were not needed.  This case should
2985                      be rare.  */
2986
2987                   for (i = regno_first; i <= regno_last; ++i)
2988                     if (! REGNO_REG_SET_P (pbi->reg_live, i))
2989                       REG_NOTES (insn)
2990                         = alloc_EXPR_LIST (REG_UNUSED,
2991                                            regno_reg_rtx[i],
2992                                            REG_NOTES (insn));
2993                 }
2994             }
2995         }
2996
2997       /* Mark the register as being dead.  */
2998       if (some_was_live
2999           /* The stack pointer is never dead.  Well, not strictly true,
3000              but it's very difficult to tell from here.  Hopefully
3001              combine_stack_adjustments will fix up the most egregious
3002              errors.  */
3003           && regno_first != STACK_POINTER_REGNUM)
3004         {
3005           for (i = regno_first; i <= regno_last; ++i)
3006             if (!(not_dead & (((unsigned long) 1) << (i - regno_first))))
3007               {
3008                 if ((pbi->flags & PROP_REG_INFO)
3009                     && REGNO_REG_SET_P (pbi->reg_live, i))
3010                   {
3011                     REG_LIVE_LENGTH (i) += pbi->insn_num - reg_deaths[i];
3012                     reg_deaths[i] = 0;
3013                   }
3014                 CLEAR_REGNO_REG_SET (pbi->reg_live, i);
3015               }
3016           if (flags & PROP_DEAD_INSN)
3017             emit_insn_after (gen_rtx_CLOBBER (VOIDmode, reg), insn);
3018         }
3019     }
3020   else if (REG_P (reg))
3021     {
3022       if (flags & (PROP_LOG_LINKS | PROP_AUTOINC))
3023         pbi->reg_next_use[regno_first] = 0;
3024
3025       if ((flags & PROP_REG_INFO) != 0
3026           && (flags & PROP_ASM_SCAN) != 0
3027           &&  regno_first < FIRST_PSEUDO_REGISTER)
3028         {
3029           for (i = regno_first; i <= regno_last; i++)
3030             regs_asm_clobbered[i] = 1;
3031         }
3032     }
3033
3034   /* If this is the last pass and this is a SCRATCH, show it will be dying
3035      here and count it.  */
3036   else if (GET_CODE (reg) == SCRATCH)
3037     {
3038       if (flags & PROP_DEATH_NOTES
3039 #ifdef STACK_REGS
3040           && (!(flags & PROP_POST_REGSTACK)
3041               || !IN_RANGE (REGNO (reg), FIRST_STACK_REG, LAST_STACK_REG))
3042 #endif
3043           )
3044         REG_NOTES (insn)
3045           = alloc_EXPR_LIST (REG_UNUSED, reg, REG_NOTES (insn));
3046     }
3047 }
3048 \f
3049 #ifdef HAVE_conditional_execution
3050 /* Mark REGNO conditionally dead.
3051    Return true if the register is now unconditionally dead.  */
3052
3053 static int
3054 mark_regno_cond_dead (struct propagate_block_info *pbi, int regno, rtx cond)
3055 {
3056   /* If this is a store to a predicate register, the value of the
3057      predicate is changing, we don't know that the predicate as seen
3058      before is the same as that seen after.  Flush all dependent
3059      conditions from reg_cond_dead.  This will make all such
3060      conditionally live registers unconditionally live.  */
3061   if (REGNO_REG_SET_P (pbi->reg_cond_reg, regno))
3062     flush_reg_cond_reg (pbi, regno);
3063
3064   /* If this is an unconditional store, remove any conditional
3065      life that may have existed.  */
3066   if (cond == NULL_RTX)
3067     splay_tree_remove (pbi->reg_cond_dead, regno);
3068   else
3069     {
3070       splay_tree_node node;
3071       struct reg_cond_life_info *rcli;
3072       rtx ncond;
3073
3074       /* Otherwise this is a conditional set.  Record that fact.
3075          It may have been conditionally used, or there may be a
3076          subsequent set with a complementary condition.  */
3077
3078       node = splay_tree_lookup (pbi->reg_cond_dead, regno);
3079       if (node == NULL)
3080         {
3081           /* The register was unconditionally live previously.
3082              Record the current condition as the condition under
3083              which it is dead.  */
3084           rcli = XNEW (struct reg_cond_life_info);
3085           rcli->condition = cond;
3086           rcli->stores = cond;
3087           rcli->orig_condition = const0_rtx;
3088           splay_tree_insert (pbi->reg_cond_dead, regno,
3089                              (splay_tree_value) rcli);
3090
3091           SET_REGNO_REG_SET (pbi->reg_cond_reg, REGNO (XEXP (cond, 0)));
3092
3093           /* Not unconditionally dead.  */
3094           return 0;
3095         }
3096       else
3097         {
3098           /* The register was conditionally live previously.
3099              Add the new condition to the old.  */
3100           rcli = (struct reg_cond_life_info *) node->value;
3101           ncond = rcli->condition;
3102           ncond = ior_reg_cond (ncond, cond, 1);
3103           if (rcli->stores == const0_rtx)
3104             rcli->stores = cond;
3105           else if (rcli->stores != const1_rtx)
3106             rcli->stores = ior_reg_cond (rcli->stores, cond, 1);
3107
3108           /* If the register is now unconditionally dead, remove the entry
3109              in the splay_tree.  A register is unconditionally dead if the
3110              dead condition ncond is true.  A register is also unconditionally
3111              dead if the sum of all conditional stores is an unconditional
3112              store (stores is true), and the dead condition is identically the
3113              same as the original dead condition initialized at the end of
3114              the block.  This is a pointer compare, not an rtx_equal_p
3115              compare.  */
3116           if (ncond == const1_rtx
3117               || (ncond == rcli->orig_condition && rcli->stores == const1_rtx))
3118             splay_tree_remove (pbi->reg_cond_dead, regno);
3119           else
3120             {
3121               rcli->condition = ncond;
3122
3123               SET_REGNO_REG_SET (pbi->reg_cond_reg, REGNO (XEXP (cond, 0)));
3124
3125               /* Not unconditionally dead.  */
3126               return 0;
3127             }
3128         }
3129     }
3130
3131   return 1;
3132 }
3133
3134 /* Called from splay_tree_delete for pbi->reg_cond_life.  */
3135
3136 static void
3137 free_reg_cond_life_info (splay_tree_value value)
3138 {
3139   struct reg_cond_life_info *rcli = (struct reg_cond_life_info *) value;
3140   free (rcli);
3141 }
3142
3143 /* Helper function for flush_reg_cond_reg.  */
3144
3145 static int
3146 flush_reg_cond_reg_1 (splay_tree_node node, void *data)
3147 {
3148   struct reg_cond_life_info *rcli;
3149   int *xdata = (int *) data;
3150   unsigned int regno = xdata[0];
3151
3152   /* Don't need to search if last flushed value was farther on in
3153      the in-order traversal.  */
3154   if (xdata[1] >= (int) node->key)
3155     return 0;
3156
3157   /* Splice out portions of the expression that refer to regno.  */
3158   rcli = (struct reg_cond_life_info *) node->value;
3159   rcli->condition = elim_reg_cond (rcli->condition, regno);
3160   if (rcli->stores != const0_rtx && rcli->stores != const1_rtx)
3161     rcli->stores = elim_reg_cond (rcli->stores, regno);
3162
3163   /* If the entire condition is now false, signal the node to be removed.  */
3164   if (rcli->condition == const0_rtx)
3165     {
3166       xdata[1] = node->key;
3167       return -1;
3168     }
3169   else
3170     gcc_assert (rcli->condition != const1_rtx);
3171
3172   return 0;
3173 }
3174
3175 /* Flush all (sub) expressions referring to REGNO from REG_COND_LIVE.  */
3176
3177 static void
3178 flush_reg_cond_reg (struct propagate_block_info *pbi, int regno)
3179 {
3180   int pair[2];
3181
3182   pair[0] = regno;
3183   pair[1] = -1;
3184   while (splay_tree_foreach (pbi->reg_cond_dead,
3185                              flush_reg_cond_reg_1, pair) == -1)
3186     splay_tree_remove (pbi->reg_cond_dead, pair[1]);
3187
3188   CLEAR_REGNO_REG_SET (pbi->reg_cond_reg, regno);
3189 }
3190
3191 /* Logical arithmetic on predicate conditions.  IOR, NOT and AND.
3192    For ior/and, the ADD flag determines whether we want to add the new
3193    condition X to the old one unconditionally.  If it is zero, we will
3194    only return a new expression if X allows us to simplify part of
3195    OLD, otherwise we return NULL to the caller.
3196    If ADD is nonzero, we will return a new condition in all cases.  The
3197    toplevel caller of one of these functions should always pass 1 for
3198    ADD.  */
3199
3200 static rtx
3201 ior_reg_cond (rtx old, rtx x, int add)
3202 {
3203   rtx op0, op1;
3204
3205   if (COMPARISON_P (old))
3206     {
3207       if (COMPARISON_P (x)
3208           && REVERSE_CONDEXEC_PREDICATES_P (x, old)
3209           && REGNO (XEXP (x, 0)) == REGNO (XEXP (old, 0)))
3210         return const1_rtx;
3211       if (GET_CODE (x) == GET_CODE (old)
3212           && REGNO (XEXP (x, 0)) == REGNO (XEXP (old, 0)))
3213         return old;
3214       if (! add)
3215         return NULL;
3216       return gen_rtx_IOR (0, old, x);
3217     }
3218
3219   switch (GET_CODE (old))
3220     {
3221     case IOR:
3222       op0 = ior_reg_cond (XEXP (old, 0), x, 0);
3223       op1 = ior_reg_cond (XEXP (old, 1), x, 0);
3224       if (op0 != NULL || op1 != NULL)
3225         {
3226           if (op0 == const0_rtx)
3227             return op1 ? op1 : gen_rtx_IOR (0, XEXP (old, 1), x);
3228           if (op1 == const0_rtx)
3229             return op0 ? op0 : gen_rtx_IOR (0, XEXP (old, 0), x);
3230           if (op0 == const1_rtx || op1 == const1_rtx)
3231             return const1_rtx;
3232           if (op0 == NULL)
3233             op0 = gen_rtx_IOR (0, XEXP (old, 0), x);
3234           else if (rtx_equal_p (x, op0))
3235             /* (x | A) | x ~ (x | A).  */
3236             return old;
3237           if (op1 == NULL)
3238             op1 = gen_rtx_IOR (0, XEXP (old, 1), x);
3239           else if (rtx_equal_p (x, op1))
3240             /* (A | x) | x ~ (A | x).  */
3241             return old;
3242           return gen_rtx_IOR (0, op0, op1);
3243         }
3244       if (! add)
3245         return NULL;
3246       return gen_rtx_IOR (0, old, x);
3247
3248     case AND:
3249       op0 = ior_reg_cond (XEXP (old, 0), x, 0);
3250       op1 = ior_reg_cond (XEXP (old, 1), x, 0);
3251       if (op0 != NULL || op1 != NULL)
3252         {
3253           if (op0 == const1_rtx)
3254             return op1 ? op1 : gen_rtx_IOR (0, XEXP (old, 1), x);
3255           if (op1 == const1_rtx)
3256             return op0 ? op0 : gen_rtx_IOR (0, XEXP (old, 0), x);
3257           if (op0 == const0_rtx || op1 == const0_rtx)
3258             return const0_rtx;
3259           if (op0 == NULL)
3260             op0 = gen_rtx_IOR (0, XEXP (old, 0), x);
3261           else if (rtx_equal_p (x, op0))
3262             /* (x & A) | x ~ x.  */
3263             return op0;
3264           if (op1 == NULL)
3265             op1 = gen_rtx_IOR (0, XEXP (old, 1), x);
3266           else if (rtx_equal_p (x, op1))
3267             /* (A & x) | x ~ x.  */
3268             return op1;
3269           return gen_rtx_AND (0, op0, op1);
3270         }
3271       if (! add)
3272         return NULL;
3273       return gen_rtx_IOR (0, old, x);
3274
3275     case NOT:
3276       op0 = and_reg_cond (XEXP (old, 0), not_reg_cond (x), 0);
3277       if (op0 != NULL)
3278         return not_reg_cond (op0);
3279       if (! add)
3280         return NULL;
3281       return gen_rtx_IOR (0, old, x);
3282
3283     default:
3284       gcc_unreachable ();
3285     }
3286 }
3287
3288 static rtx
3289 not_reg_cond (rtx x)
3290 {
3291   if (x == const0_rtx)
3292     return const1_rtx;
3293   else if (x == const1_rtx)
3294     return const0_rtx;
3295   if (GET_CODE (x) == NOT)
3296     return XEXP (x, 0);
3297   if (COMPARISON_P (x)
3298       && REG_P (XEXP (x, 0)))
3299     {
3300       gcc_assert (XEXP (x, 1) == const0_rtx);
3301
3302       return gen_rtx_fmt_ee (reversed_comparison_code (x, NULL),
3303                              VOIDmode, XEXP (x, 0), const0_rtx);
3304     }
3305   return gen_rtx_NOT (0, x);
3306 }
3307
3308 static rtx
3309 and_reg_cond (rtx old, rtx x, int add)
3310 {
3311   rtx op0, op1;
3312
3313   if (COMPARISON_P (old))
3314     {
3315       if (COMPARISON_P (x)
3316           && GET_CODE (x) == reversed_comparison_code (old, NULL)
3317           && REGNO (XEXP (x, 0)) == REGNO (XEXP (old, 0)))
3318         return const0_rtx;
3319       if (GET_CODE (x) == GET_CODE (old)
3320           && REGNO (XEXP (x, 0)) == REGNO (XEXP (old, 0)))
3321         return old;
3322       if (! add)
3323         return NULL;
3324       return gen_rtx_AND (0, old, x);
3325     }
3326
3327   switch (GET_CODE (old))
3328     {
3329     case IOR:
3330       op0 = and_reg_cond (XEXP (old, 0), x, 0);
3331       op1 = and_reg_cond (XEXP (old, 1), x, 0);
3332       if (op0 != NULL || op1 != NULL)
3333         {
3334           if (op0 == const0_rtx)
3335             return op1 ? op1 : gen_rtx_AND (0, XEXP (old, 1), x);
3336           if (op1 == const0_rtx)
3337             return op0 ? op0 : gen_rtx_AND (0, XEXP (old, 0), x);
3338           if (op0 == const1_rtx || op1 == const1_rtx)
3339             return const1_rtx;
3340           if (op0 == NULL)
3341             op0 = gen_rtx_AND (0, XEXP (old, 0), x);
3342           else if (rtx_equal_p (x, op0))
3343             /* (x | A) & x ~ x.  */
3344             return op0;
3345           if (op1 == NULL)
3346             op1 = gen_rtx_AND (0, XEXP (old, 1), x);
3347           else if (rtx_equal_p (x, op1))
3348             /* (A | x) & x ~ x.  */
3349             return op1;
3350           return gen_rtx_IOR (0, op0, op1);
3351         }
3352       if (! add)
3353         return NULL;
3354       return gen_rtx_AND (0, old, x);
3355
3356     case AND:
3357       op0 = and_reg_cond (XEXP (old, 0), x, 0);
3358       op1 = and_reg_cond (XEXP (old, 1), x, 0);
3359       if (op0 != NULL || op1 != NULL)
3360         {
3361           if (op0 == const1_rtx)
3362             return op1 ? op1 : gen_rtx_AND (0, XEXP (old, 1), x);
3363           if (op1 == const1_rtx)
3364             return op0 ? op0 : gen_rtx_AND (0, XEXP (old, 0), x);
3365           if (op0 == const0_rtx || op1 == const0_rtx)
3366             return const0_rtx;
3367           if (op0 == NULL)
3368             op0 = gen_rtx_AND (0, XEXP (old, 0), x);
3369           else if (rtx_equal_p (x, op0))
3370             /* (x & A) & x ~ (x & A).  */
3371             return old;
3372           if (op1 == NULL)
3373             op1 = gen_rtx_AND (0, XEXP (old, 1), x);
3374           else if (rtx_equal_p (x, op1))
3375             /* (A & x) & x ~ (A & x).  */
3376             return old;
3377           return gen_rtx_AND (0, op0, op1);
3378         }
3379       if (! add)
3380         return NULL;
3381       return gen_rtx_AND (0, old, x);
3382
3383     case NOT:
3384       op0 = ior_reg_cond (XEXP (old, 0), not_reg_cond (x), 0);
3385       if (op0 != NULL)
3386         return not_reg_cond (op0);
3387       if (! add)
3388         return NULL;
3389       return gen_rtx_AND (0, old, x);
3390
3391     default:
3392       gcc_unreachable ();
3393     }
3394 }
3395
3396 /* Given a condition X, remove references to reg REGNO and return the
3397    new condition.  The removal will be done so that all conditions
3398    involving REGNO are considered to evaluate to false.  This function
3399    is used when the value of REGNO changes.  */
3400
3401 static rtx
3402 elim_reg_cond (rtx x, unsigned int regno)
3403 {
3404   rtx op0, op1;
3405
3406   if (COMPARISON_P (x))
3407     {
3408       if (REGNO (XEXP (x, 0)) == regno)
3409         return const0_rtx;
3410       return x;
3411     }
3412
3413   switch (GET_CODE (x))
3414     {
3415     case AND:
3416       op0 = elim_reg_cond (XEXP (x, 0), regno);
3417       op1 = elim_reg_cond (XEXP (x, 1), regno);
3418       if (op0 == const0_rtx || op1 == const0_rtx)
3419         return const0_rtx;
3420       if (op0 == const1_rtx)
3421         return op1;
3422       if (op1 == const1_rtx)
3423         return op0;
3424       if (op0 == XEXP (x, 0) && op1 == XEXP (x, 1))
3425         return x;
3426       return gen_rtx_AND (0, op0, op1);
3427
3428     case IOR:
3429       op0 = elim_reg_cond (XEXP (x, 0), regno);
3430       op1 = elim_reg_cond (XEXP (x, 1), regno);
3431       if (op0 == const1_rtx || op1 == const1_rtx)
3432         return const1_rtx;
3433       if (op0 == const0_rtx)
3434         return op1;
3435       if (op1 == const0_rtx)
3436         return op0;
3437       if (op0 == XEXP (x, 0) && op1 == XEXP (x, 1))
3438         return x;
3439       return gen_rtx_IOR (0, op0, op1);
3440
3441     case NOT:
3442       op0 = elim_reg_cond (XEXP (x, 0), regno);
3443       if (op0 == const0_rtx)
3444         return const1_rtx;
3445       if (op0 == const1_rtx)
3446         return const0_rtx;
3447       if (op0 != XEXP (x, 0))
3448         return not_reg_cond (op0);
3449       return x;
3450
3451     default:
3452       gcc_unreachable ();
3453     }
3454 }
3455 #endif /* HAVE_conditional_execution */
3456 \f
3457 #ifdef AUTO_INC_DEC
3458
3459 /* Try to substitute the auto-inc expression INC as the address inside
3460    MEM which occurs in INSN.  Currently, the address of MEM is an expression
3461    involving INCR_REG, and INCR is the next use of INCR_REG; it is an insn
3462    that has a single set whose source is a PLUS of INCR_REG and something
3463    else.  */
3464
3465 static void
3466 attempt_auto_inc (struct propagate_block_info *pbi, rtx inc, rtx insn,
3467                   rtx mem, rtx incr, rtx incr_reg)
3468 {
3469   int regno = REGNO (incr_reg);
3470   rtx set = single_set (incr);
3471   rtx q = SET_DEST (set);
3472   rtx y = SET_SRC (set);
3473   int opnum = XEXP (y, 0) == incr_reg ? 0 : 1;
3474   int changed;
3475
3476   /* Make sure this reg appears only once in this insn.  */
3477   if (count_occurrences (PATTERN (insn), incr_reg, 1) != 1)
3478     return;
3479
3480   if (dead_or_set_p (incr, incr_reg)
3481       /* Mustn't autoinc an eliminable register.  */
3482       && (regno >= FIRST_PSEUDO_REGISTER
3483           || ! TEST_HARD_REG_BIT (elim_reg_set, regno)))
3484     {
3485       /* This is the simple case.  Try to make the auto-inc.