OSDN Git Service

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