Daily bump.
[official-gcc.git] / gcc / flow.c
blobc58fd499e3e2e08e5b700ca37bd91975ffe1f130
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 Free Software Foundation, Inc.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 2, or (at your option) any later
10 version.
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15 for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING. If not, write to the Free
19 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
20 02111-1307, USA. */
22 /* This file contains the data flow analysis pass of the compiler. It
23 computes data flow information which tells combine_instructions
24 which insns to consider combining and controls register allocation.
26 Additional data flow information that is too bulky to record is
27 generated during the analysis, and is used at that time to create
28 autoincrement and autodecrement addressing.
30 The first step is dividing the function into basic blocks.
31 find_basic_blocks does this. Then life_analysis determines
32 where each register is live and where it is dead.
34 ** find_basic_blocks **
36 find_basic_blocks divides the current function's rtl into basic
37 blocks and constructs the CFG. The blocks are recorded in the
38 basic_block_info array; the CFG exists in the edge structures
39 referenced by the blocks.
41 find_basic_blocks also finds any unreachable loops and deletes them.
43 ** life_analysis **
45 life_analysis is called immediately after find_basic_blocks.
46 It uses the basic block information to determine where each
47 hard or pseudo register is live.
49 ** live-register info **
51 The information about where each register is live is in two parts:
52 the REG_NOTES of insns, and the vector basic_block->global_live_at_start.
54 basic_block->global_live_at_start has an element for each basic
55 block, and the element is a bit-vector with a bit for each hard or
56 pseudo register. The bit is 1 if the register is live at the
57 beginning of the basic block.
59 Two types of elements can be added to an insn's REG_NOTES.
60 A REG_DEAD note is added to an insn's REG_NOTES for any register
61 that meets both of two conditions: The value in the register is not
62 needed in subsequent insns and the insn does not replace the value in
63 the register (in the case of multi-word hard registers, the value in
64 each register must be replaced by the insn to avoid a REG_DEAD note).
66 In the vast majority of cases, an object in a REG_DEAD note will be
67 used somewhere in the insn. The (rare) exception to this is if an
68 insn uses a multi-word hard register and only some of the registers are
69 needed in subsequent insns. In that case, REG_DEAD notes will be
70 provided for those hard registers that are not subsequently needed.
71 Partial REG_DEAD notes of this type do not occur when an insn sets
72 only some of the hard registers used in such a multi-word operand;
73 omitting REG_DEAD notes for objects stored in an insn is optional and
74 the desire to do so does not justify the complexity of the partial
75 REG_DEAD notes.
77 REG_UNUSED notes are added for each register that is set by the insn
78 but is unused subsequently (if every register set by the insn is unused
79 and the insn does not reference memory or have some other side-effect,
80 the insn is deleted instead). If only part of a multi-word hard
81 register is used in a subsequent insn, REG_UNUSED notes are made for
82 the parts that will not be used.
84 To determine which registers are live after any insn, one can
85 start from the beginning of the basic block and scan insns, noting
86 which registers are set by each insn and which die there.
88 ** Other actions of life_analysis **
90 life_analysis sets up the LOG_LINKS fields of insns because the
91 information needed to do so is readily available.
93 life_analysis deletes insns whose only effect is to store a value
94 that is never used.
96 life_analysis notices cases where a reference to a register as
97 a memory address can be combined with a preceding or following
98 incrementation or decrementation of the register. The separate
99 instruction to increment or decrement is deleted and the address
100 is changed to a POST_INC or similar rtx.
102 Each time an incrementing or decrementing address is created,
103 a REG_INC element is added to the insn's REG_NOTES list.
105 life_analysis fills in certain vectors containing information about
106 register usage: REG_N_REFS, REG_N_DEATHS, REG_N_SETS, REG_LIVE_LENGTH,
107 REG_N_CALLS_CROSSED and REG_BASIC_BLOCK.
109 life_analysis sets current_function_sp_is_unchanging if the function
110 doesn't modify the stack pointer. */
112 /* TODO:
114 Split out from life_analysis:
115 - local property discovery
116 - global property computation
117 - log links creation
118 - pre/post modify transformation
121 #include "config.h"
122 #include "system.h"
123 #include "coretypes.h"
124 #include "tm.h"
125 #include "tree.h"
126 #include "rtl.h"
127 #include "tm_p.h"
128 #include "hard-reg-set.h"
129 #include "basic-block.h"
130 #include "insn-config.h"
131 #include "regs.h"
132 #include "flags.h"
133 #include "output.h"
134 #include "function.h"
135 #include "except.h"
136 #include "toplev.h"
137 #include "recog.h"
138 #include "expr.h"
139 #include "timevar.h"
141 #include "obstack.h"
142 #include "splay-tree.h"
144 #ifndef HAVE_epilogue
145 #define HAVE_epilogue 0
146 #endif
147 #ifndef HAVE_prologue
148 #define HAVE_prologue 0
149 #endif
150 #ifndef HAVE_sibcall_epilogue
151 #define HAVE_sibcall_epilogue 0
152 #endif
154 #ifndef EPILOGUE_USES
155 #define EPILOGUE_USES(REGNO) 0
156 #endif
157 #ifndef EH_USES
158 #define EH_USES(REGNO) 0
159 #endif
161 #ifdef HAVE_conditional_execution
162 #ifndef REVERSE_CONDEXEC_PREDICATES_P
163 #define REVERSE_CONDEXEC_PREDICATES_P(x, y) \
164 (GET_CODE ((x)) == reversed_comparison_code ((y), NULL))
165 #endif
166 #endif
168 /* This is the maximum number of times we process any given block if the
169 latest loop depth count is smaller than this number. Only used for the
170 failure strategy to avoid infinite loops in calculate_global_regs_live. */
171 #define MAX_LIVENESS_ROUNDS 20
173 /* Nonzero if the second flow pass has completed. */
174 int flow2_completed;
176 /* Maximum register number used in this function, plus one. */
178 int max_regno;
180 /* Indexed by n, giving various register information */
182 varray_type reg_n_info;
184 /* Regset of regs live when calls to `setjmp'-like functions happen. */
185 /* ??? Does this exist only for the setjmp-clobbered warning message? */
187 static regset regs_live_at_setjmp;
189 /* List made of EXPR_LIST rtx's which gives pairs of pseudo registers
190 that have to go in the same hard reg.
191 The first two regs in the list are a pair, and the next two
192 are another pair, etc. */
193 rtx regs_may_share;
195 /* Set of registers that may be eliminable. These are handled specially
196 in updating regs_ever_live. */
198 static HARD_REG_SET elim_reg_set;
200 /* Holds information for tracking conditional register life information. */
201 struct reg_cond_life_info
203 /* A boolean expression of conditions under which a register is dead. */
204 rtx condition;
205 /* Conditions under which a register is dead at the basic block end. */
206 rtx orig_condition;
208 /* A boolean expression of conditions under which a register has been
209 stored into. */
210 rtx stores;
212 /* ??? Could store mask of bytes that are dead, so that we could finally
213 track lifetimes of multi-word registers accessed via subregs. */
216 /* For use in communicating between propagate_block and its subroutines.
217 Holds all information needed to compute life and def-use information. */
219 struct propagate_block_info
221 /* The basic block we're considering. */
222 basic_block bb;
224 /* Bit N is set if register N is conditionally or unconditionally live. */
225 regset reg_live;
227 /* Bit N is set if register N is set this insn. */
228 regset new_set;
230 /* Element N is the next insn that uses (hard or pseudo) register N
231 within the current basic block; or zero, if there is no such insn. */
232 rtx *reg_next_use;
234 /* Contains a list of all the MEMs we are tracking for dead store
235 elimination. */
236 rtx mem_set_list;
238 /* If non-null, record the set of registers set unconditionally in the
239 basic block. */
240 regset local_set;
242 /* If non-null, record the set of registers set conditionally in the
243 basic block. */
244 regset cond_local_set;
246 #ifdef HAVE_conditional_execution
247 /* Indexed by register number, holds a reg_cond_life_info for each
248 register that is not unconditionally live or dead. */
249 splay_tree reg_cond_dead;
251 /* Bit N is set if register N is in an expression in reg_cond_dead. */
252 regset reg_cond_reg;
253 #endif
255 /* The length of mem_set_list. */
256 int mem_set_list_len;
258 /* Nonzero if the value of CC0 is live. */
259 int cc0_live;
261 /* Flags controlling the set of information propagate_block collects. */
262 int flags;
263 /* Index of instruction being processed. */
264 int insn_num;
267 /* Number of dead insns removed. */
268 static int ndead;
270 /* When PROP_REG_INFO set, array contains pbi->insn_num of instruction
271 where given register died. When the register is marked alive, we use the
272 information to compute amount of instructions life range cross.
273 (remember, we are walking backward). This can be computed as current
274 pbi->insn_num - reg_deaths[regno].
275 At the end of processing each basic block, the remaining live registers
276 are inspected and liferanges are increased same way so liverange of global
277 registers are computed correctly.
279 The array is maintained clear for dead registers, so it can be safely reused
280 for next basic block without expensive memset of the whole array after
281 reseting pbi->insn_num to 0. */
283 static int *reg_deaths;
285 /* Maximum length of pbi->mem_set_list before we start dropping
286 new elements on the floor. */
287 #define MAX_MEM_SET_LIST_LEN 100
289 /* Forward declarations */
290 static int verify_wide_reg_1 (rtx *, void *);
291 static void verify_wide_reg (int, basic_block);
292 static void verify_local_live_at_start (regset, basic_block);
293 static void notice_stack_pointer_modification_1 (rtx, rtx, void *);
294 static void notice_stack_pointer_modification (void);
295 static void mark_reg (rtx, void *);
296 static void mark_regs_live_at_end (regset);
297 static void calculate_global_regs_live (sbitmap, sbitmap, int);
298 static void propagate_block_delete_insn (rtx);
299 static rtx propagate_block_delete_libcall (rtx, rtx);
300 static int insn_dead_p (struct propagate_block_info *, rtx, int, rtx);
301 static int libcall_dead_p (struct propagate_block_info *, rtx, rtx);
302 static void mark_set_regs (struct propagate_block_info *, rtx, rtx);
303 static void mark_set_1 (struct propagate_block_info *, enum rtx_code, rtx,
304 rtx, rtx, int);
305 static int find_regno_partial (rtx *, void *);
307 #ifdef HAVE_conditional_execution
308 static int mark_regno_cond_dead (struct propagate_block_info *, int, rtx);
309 static void free_reg_cond_life_info (splay_tree_value);
310 static int flush_reg_cond_reg_1 (splay_tree_node, void *);
311 static void flush_reg_cond_reg (struct propagate_block_info *, int);
312 static rtx elim_reg_cond (rtx, unsigned int);
313 static rtx ior_reg_cond (rtx, rtx, int);
314 static rtx not_reg_cond (rtx);
315 static rtx and_reg_cond (rtx, rtx, int);
316 #endif
317 #ifdef AUTO_INC_DEC
318 static void attempt_auto_inc (struct propagate_block_info *, rtx, rtx, rtx,
319 rtx, rtx);
320 static void find_auto_inc (struct propagate_block_info *, rtx, rtx);
321 static int try_pre_increment_1 (struct propagate_block_info *, rtx);
322 static int try_pre_increment (rtx, rtx, HOST_WIDE_INT);
323 #endif
324 static void mark_used_reg (struct propagate_block_info *, rtx, rtx, rtx);
325 static void mark_used_regs (struct propagate_block_info *, rtx, rtx, rtx);
326 void debug_flow_info (void);
327 static void add_to_mem_set_list (struct propagate_block_info *, rtx);
328 static int invalidate_mems_from_autoinc (rtx *, void *);
329 static void invalidate_mems_from_set (struct propagate_block_info *, rtx);
330 static void clear_log_links (sbitmap);
331 static int count_or_remove_death_notes_bb (basic_block, int);
332 static void allocate_bb_life_data (void);
334 /* Return the INSN immediately following the NOTE_INSN_BASIC_BLOCK
335 note associated with the BLOCK. */
338 first_insn_after_basic_block_note (basic_block block)
340 rtx insn;
342 /* Get the first instruction in the block. */
343 insn = BB_HEAD (block);
345 if (insn == NULL_RTX)
346 return NULL_RTX;
347 if (LABEL_P (insn))
348 insn = NEXT_INSN (insn);
349 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (insn));
351 return NEXT_INSN (insn);
354 /* Perform data flow analysis for the whole control flow graph.
355 FLAGS is a set of PROP_* flags to be used in accumulating flow info. */
357 void
358 life_analysis (FILE *file, int flags)
360 #ifdef ELIMINABLE_REGS
361 int i;
362 static const struct {const int from, to; } eliminables[] = ELIMINABLE_REGS;
363 #endif
365 /* Record which registers will be eliminated. We use this in
366 mark_used_regs. */
368 CLEAR_HARD_REG_SET (elim_reg_set);
370 #ifdef ELIMINABLE_REGS
371 for (i = 0; i < (int) ARRAY_SIZE (eliminables); i++)
372 SET_HARD_REG_BIT (elim_reg_set, eliminables[i].from);
373 #else
374 SET_HARD_REG_BIT (elim_reg_set, FRAME_POINTER_REGNUM);
375 #endif
378 #ifdef CANNOT_CHANGE_MODE_CLASS
379 if (flags & PROP_REG_INFO)
380 init_subregs_of_mode ();
381 #endif
383 if (! optimize)
384 flags &= ~(PROP_LOG_LINKS | PROP_AUTOINC | PROP_ALLOW_CFG_CHANGES);
386 /* The post-reload life analysis have (on a global basis) the same
387 registers live as was computed by reload itself. elimination
388 Otherwise offsets and such may be incorrect.
390 Reload will make some registers as live even though they do not
391 appear in the rtl.
393 We don't want to create new auto-incs after reload, since they
394 are unlikely to be useful and can cause problems with shared
395 stack slots. */
396 if (reload_completed)
397 flags &= ~(PROP_REG_INFO | PROP_AUTOINC);
399 /* We want alias analysis information for local dead store elimination. */
400 if (optimize && (flags & PROP_SCAN_DEAD_STORES))
401 init_alias_analysis ();
403 /* Always remove no-op moves. Do this before other processing so
404 that we don't have to keep re-scanning them. */
405 delete_noop_moves ();
407 /* Some targets can emit simpler epilogues if they know that sp was
408 not ever modified during the function. After reload, of course,
409 we've already emitted the epilogue so there's no sense searching. */
410 if (! reload_completed)
411 notice_stack_pointer_modification ();
413 /* Allocate and zero out data structures that will record the
414 data from lifetime analysis. */
415 allocate_reg_life_data ();
416 allocate_bb_life_data ();
418 /* Find the set of registers live on function exit. */
419 mark_regs_live_at_end (EXIT_BLOCK_PTR->global_live_at_start);
421 /* "Update" life info from zero. It'd be nice to begin the
422 relaxation with just the exit and noreturn blocks, but that set
423 is not immediately handy. */
425 if (flags & PROP_REG_INFO)
427 memset (regs_ever_live, 0, sizeof (regs_ever_live));
428 memset (regs_asm_clobbered, 0, sizeof (regs_asm_clobbered));
430 update_life_info (NULL, UPDATE_LIFE_GLOBAL, flags);
431 if (reg_deaths)
433 free (reg_deaths);
434 reg_deaths = NULL;
437 /* Clean up. */
438 if (optimize && (flags & PROP_SCAN_DEAD_STORES))
439 end_alias_analysis ();
441 if (file)
442 dump_flow_info (file);
444 /* Removing dead insns should have made jumptables really dead. */
445 delete_dead_jumptables ();
448 /* A subroutine of verify_wide_reg, called through for_each_rtx.
449 Search for REGNO. If found, return 2 if it is not wider than
450 word_mode. */
452 static int
453 verify_wide_reg_1 (rtx *px, void *pregno)
455 rtx x = *px;
456 unsigned int regno = *(int *) pregno;
458 if (REG_P (x) && REGNO (x) == regno)
460 if (GET_MODE_BITSIZE (GET_MODE (x)) <= BITS_PER_WORD)
461 return 2;
462 return 1;
464 return 0;
467 /* A subroutine of verify_local_live_at_start. Search through insns
468 of BB looking for register REGNO. */
470 static void
471 verify_wide_reg (int regno, basic_block bb)
473 rtx head = BB_HEAD (bb), end = BB_END (bb);
475 while (1)
477 if (INSN_P (head))
479 int r = for_each_rtx (&PATTERN (head), verify_wide_reg_1, &regno);
480 if (r == 1)
481 return;
482 if (r == 2)
483 break;
485 if (head == end)
486 break;
487 head = NEXT_INSN (head);
489 if (dump_file)
491 fprintf (dump_file, "Register %d died unexpectedly.\n", regno);
492 dump_bb (bb, dump_file, 0);
494 fatal_error ("internal consistency failure");
497 /* A subroutine of update_life_info. Verify that there are no untoward
498 changes in live_at_start during a local update. */
500 static void
501 verify_local_live_at_start (regset new_live_at_start, basic_block bb)
503 if (reload_completed)
505 /* After reload, there are no pseudos, nor subregs of multi-word
506 registers. The regsets should exactly match. */
507 if (! REG_SET_EQUAL_P (new_live_at_start, bb->global_live_at_start))
509 if (dump_file)
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);
518 fatal_error ("internal consistency failure");
521 else
523 unsigned i;
524 reg_set_iterator rsi;
526 /* Find the set of changed registers. */
527 XOR_REG_SET (new_live_at_start, bb->global_live_at_start);
529 EXECUTE_IF_SET_IN_REG_SET (new_live_at_start, 0, i, rsi)
531 /* No registers should die. */
532 if (REGNO_REG_SET_P (bb->global_live_at_start, i))
534 if (dump_file)
536 fprintf (dump_file,
537 "Register %d died unexpectedly.\n", i);
538 dump_bb (bb, dump_file, 0);
540 fatal_error ("internal consistency failure");
542 /* Verify that the now-live register is wider than word_mode. */
543 verify_wide_reg (i, bb);
548 /* Updates life information starting with the basic blocks set in BLOCKS.
549 If BLOCKS is null, consider it to be the universal set.
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.
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.
562 It is also not true when a peephole decides that it doesn't need one
563 or more of the inputs.
565 Including PROP_REG_INFO does not properly refresh regs_ever_live
566 unless the caller resets it to zero. */
569 update_life_info (sbitmap blocks, enum update_life_extent extent,
570 int prop_flags)
572 regset tmp;
573 unsigned i;
574 int stabilized_prop_flags = prop_flags;
575 basic_block bb;
577 tmp = ALLOC_REG_SET (&reg_obstack);
578 ndead = 0;
580 if ((prop_flags & PROP_REG_INFO) && !reg_deaths)
581 reg_deaths = xcalloc (sizeof (*reg_deaths), max_regno);
583 timevar_push ((extent == UPDATE_LIFE_LOCAL || blocks)
584 ? TV_LIFE_UPDATE : TV_LIFE);
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));
591 /* For a global update, we go through the relaxation process again. */
592 if (extent != UPDATE_LIFE_LOCAL)
594 for ( ; ; )
596 int changed = 0;
598 calculate_global_regs_live (blocks, blocks,
599 prop_flags & (PROP_SCAN_DEAD_CODE
600 | PROP_SCAN_DEAD_STORES
601 | PROP_ALLOW_CFG_CHANGES));
603 if ((prop_flags & (PROP_KILL_DEAD_CODE | PROP_ALLOW_CFG_CHANGES))
604 != (PROP_KILL_DEAD_CODE | PROP_ALLOW_CFG_CHANGES))
605 break;
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)
611 COPY_REG_SET (tmp, bb->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));
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);
626 if (! changed)
627 break;
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 MAX_MEM_SET_LIST_LEN usage).
632 Further improvement may be possible. */
633 cleanup_cfg (CLEANUP_EXPENSIVE);
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)
640 CLEAR_REG_SET (bb->global_live_at_start);
641 CLEAR_REG_SET (bb->global_live_at_end);
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, 1);
650 /* Clear log links in case we are asked to (re)compute them. */
651 if (prop_flags & PROP_LOG_LINKS)
652 clear_log_links (blocks);
654 if (blocks)
656 EXECUTE_IF_SET_IN_SBITMAP (blocks, 0, i,
658 bb = BASIC_BLOCK (i);
660 COPY_REG_SET (tmp, bb->global_live_at_end);
661 propagate_block (bb, tmp, NULL, NULL, stabilized_prop_flags);
663 if (extent == UPDATE_LIFE_LOCAL)
664 verify_local_live_at_start (tmp, bb);
667 else
669 FOR_EACH_BB_REVERSE (bb)
671 COPY_REG_SET (tmp, bb->global_live_at_end);
673 propagate_block (bb, tmp, NULL, NULL, stabilized_prop_flags);
675 if (extent == UPDATE_LIFE_LOCAL)
676 verify_local_live_at_start (tmp, bb);
680 FREE_REG_SET (tmp);
682 if (prop_flags & PROP_REG_INFO)
684 reg_set_iterator rsi;
686 /* The only pseudos that are live at the beginning of the function
687 are those that were not set anywhere in the function. local-alloc
688 doesn't know how to handle these correctly, so mark them as not
689 local to any one basic block. */
690 EXECUTE_IF_SET_IN_REG_SET (ENTRY_BLOCK_PTR->global_live_at_end,
691 FIRST_PSEUDO_REGISTER, i, rsi)
692 REG_BASIC_BLOCK (i) = REG_BLOCK_GLOBAL;
694 /* We have a problem with any pseudoreg that lives across the setjmp.
695 ANSI says that if a user variable does not change in value between
696 the setjmp and the longjmp, then the longjmp preserves it. This
697 includes longjmp from a place where the pseudo appears dead.
698 (In principle, the value still exists if it is in scope.)
699 If the pseudo goes in a hard reg, some other value may occupy
700 that hard reg where this pseudo is dead, thus clobbering the pseudo.
701 Conclusion: such a pseudo must not go in a hard reg. */
702 EXECUTE_IF_SET_IN_REG_SET (regs_live_at_setjmp,
703 FIRST_PSEUDO_REGISTER, i, rsi)
705 if (regno_reg_rtx[i] != 0)
707 REG_LIVE_LENGTH (i) = -1;
708 REG_BASIC_BLOCK (i) = REG_BLOCK_UNKNOWN;
712 if (reg_deaths)
714 free (reg_deaths);
715 reg_deaths = NULL;
717 timevar_pop ((extent == UPDATE_LIFE_LOCAL || blocks)
718 ? TV_LIFE_UPDATE : TV_LIFE);
719 if (ndead && dump_file)
720 fprintf (dump_file, "deleted %i dead insns\n", ndead);
721 return ndead;
724 /* Update life information in all blocks where BB_DIRTY is set. */
727 update_life_info_in_dirty_blocks (enum update_life_extent extent, int prop_flags)
729 sbitmap update_life_blocks = sbitmap_alloc (last_basic_block);
730 int n = 0;
731 basic_block bb;
732 int retval = 0;
734 sbitmap_zero (update_life_blocks);
735 FOR_EACH_BB (bb)
737 if (bb->flags & BB_DIRTY)
739 SET_BIT (update_life_blocks, bb->index);
740 n++;
744 if (n)
745 retval = update_life_info (update_life_blocks, extent, prop_flags);
747 sbitmap_free (update_life_blocks);
748 return retval;
751 /* Free the variables allocated by find_basic_blocks. */
753 void
754 free_basic_block_vars (void)
756 if (basic_block_info)
758 clear_edges ();
759 basic_block_info = NULL;
761 n_basic_blocks = 0;
762 last_basic_block = 0;
764 ENTRY_BLOCK_PTR->aux = NULL;
765 ENTRY_BLOCK_PTR->global_live_at_end = NULL;
766 EXIT_BLOCK_PTR->aux = NULL;
767 EXIT_BLOCK_PTR->global_live_at_start = NULL;
770 /* Delete any insns that copy a register to itself. */
773 delete_noop_moves (void)
775 rtx insn, next;
776 basic_block bb;
777 int nnoops = 0;
779 FOR_EACH_BB (bb)
781 for (insn = BB_HEAD (bb); insn != NEXT_INSN (BB_END (bb)); insn = next)
783 next = NEXT_INSN (insn);
784 if (INSN_P (insn) && noop_move_p (insn))
786 rtx note;
788 /* If we're about to remove the first insn of a libcall
789 then move the libcall note to the next real insn and
790 update the retval note. */
791 if ((note = find_reg_note (insn, REG_LIBCALL, NULL_RTX))
792 && XEXP (note, 0) != insn)
794 rtx new_libcall_insn = next_real_insn (insn);
795 rtx retval_note = find_reg_note (XEXP (note, 0),
796 REG_RETVAL, NULL_RTX);
797 REG_NOTES (new_libcall_insn)
798 = gen_rtx_INSN_LIST (REG_LIBCALL, XEXP (note, 0),
799 REG_NOTES (new_libcall_insn));
800 XEXP (retval_note, 0) = new_libcall_insn;
803 delete_insn_and_edges (insn);
804 nnoops++;
808 if (nnoops && dump_file)
809 fprintf (dump_file, "deleted %i noop moves", nnoops);
810 return nnoops;
813 /* Delete any jump tables never referenced. We can't delete them at the
814 time of removing tablejump insn as they are referenced by the preceding
815 insns computing the destination, so we delay deleting and garbagecollect
816 them once life information is computed. */
817 void
818 delete_dead_jumptables (void)
820 basic_block bb;
822 /* A dead jump table does not belong to any basic block. Scan insns
823 between two adjacent basic blocks. */
824 FOR_EACH_BB (bb)
826 rtx insn, next;
828 for (insn = NEXT_INSN (BB_END (bb));
829 insn && !NOTE_INSN_BASIC_BLOCK_P (insn);
830 insn = next)
832 next = NEXT_INSN (insn);
833 if (LABEL_P (insn)
834 && LABEL_NUSES (insn) == LABEL_PRESERVE_P (insn)
835 && JUMP_P (next)
836 && (GET_CODE (PATTERN (next)) == ADDR_VEC
837 || GET_CODE (PATTERN (next)) == ADDR_DIFF_VEC))
839 rtx label = insn, jump = next;
841 if (dump_file)
842 fprintf (dump_file, "Dead jumptable %i removed\n",
843 INSN_UID (insn));
845 next = NEXT_INSN (next);
846 delete_insn (jump);
847 delete_insn (label);
853 /* Determine if the stack pointer is constant over the life of the function.
854 Only useful before prologues have been emitted. */
856 static void
857 notice_stack_pointer_modification_1 (rtx x, rtx pat ATTRIBUTE_UNUSED,
858 void *data ATTRIBUTE_UNUSED)
860 if (x == stack_pointer_rtx
861 /* The stack pointer is only modified indirectly as the result
862 of a push until later in flow. See the comments in rtl.texi
863 regarding Embedded Side-Effects on Addresses. */
864 || (MEM_P (x)
865 && GET_RTX_CLASS (GET_CODE (XEXP (x, 0))) == RTX_AUTOINC
866 && XEXP (XEXP (x, 0), 0) == stack_pointer_rtx))
867 current_function_sp_is_unchanging = 0;
870 static void
871 notice_stack_pointer_modification (void)
873 basic_block bb;
874 rtx insn;
876 /* Assume that the stack pointer is unchanging if alloca hasn't
877 been used. */
878 current_function_sp_is_unchanging = !current_function_calls_alloca;
879 if (! current_function_sp_is_unchanging)
880 return;
882 FOR_EACH_BB (bb)
883 FOR_BB_INSNS (bb, insn)
885 if (INSN_P (insn))
887 /* Check if insn modifies the stack pointer. */
888 note_stores (PATTERN (insn),
889 notice_stack_pointer_modification_1,
890 NULL);
891 if (! current_function_sp_is_unchanging)
892 return;
897 /* Mark a register in SET. Hard registers in large modes get all
898 of their component registers set as well. */
900 static void
901 mark_reg (rtx reg, void *xset)
903 regset set = (regset) xset;
904 int regno = REGNO (reg);
906 gcc_assert (GET_MODE (reg) != BLKmode);
908 SET_REGNO_REG_SET (set, regno);
909 if (regno < FIRST_PSEUDO_REGISTER)
911 int n = hard_regno_nregs[regno][GET_MODE (reg)];
912 while (--n > 0)
913 SET_REGNO_REG_SET (set, regno + n);
917 /* Mark those regs which are needed at the end of the function as live
918 at the end of the last basic block. */
920 static void
921 mark_regs_live_at_end (regset set)
923 unsigned int i;
925 /* If exiting needs the right stack value, consider the stack pointer
926 live at the end of the function. */
927 if ((HAVE_epilogue && epilogue_completed)
928 || ! EXIT_IGNORE_STACK
929 || (! FRAME_POINTER_REQUIRED
930 && ! current_function_calls_alloca
931 && flag_omit_frame_pointer)
932 || current_function_sp_is_unchanging)
934 SET_REGNO_REG_SET (set, STACK_POINTER_REGNUM);
937 /* Mark the frame pointer if needed at the end of the function. If
938 we end up eliminating it, it will be removed from the live list
939 of each basic block by reload. */
941 if (! reload_completed || frame_pointer_needed)
943 SET_REGNO_REG_SET (set, FRAME_POINTER_REGNUM);
944 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
945 /* If they are different, also mark the hard frame pointer as live. */
946 if (! LOCAL_REGNO (HARD_FRAME_POINTER_REGNUM))
947 SET_REGNO_REG_SET (set, HARD_FRAME_POINTER_REGNUM);
948 #endif
951 #ifndef PIC_OFFSET_TABLE_REG_CALL_CLOBBERED
952 /* Many architectures have a GP register even without flag_pic.
953 Assume the pic register is not in use, or will be handled by
954 other means, if it is not fixed. */
955 if ((unsigned) PIC_OFFSET_TABLE_REGNUM != INVALID_REGNUM
956 && fixed_regs[PIC_OFFSET_TABLE_REGNUM])
957 SET_REGNO_REG_SET (set, PIC_OFFSET_TABLE_REGNUM);
958 #endif
960 /* Mark all global registers, and all registers used by the epilogue
961 as being live at the end of the function since they may be
962 referenced by our caller. */
963 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
964 if (global_regs[i] || EPILOGUE_USES (i))
965 SET_REGNO_REG_SET (set, i);
967 if (HAVE_epilogue && epilogue_completed)
969 /* Mark all call-saved registers that we actually used. */
970 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
971 if (regs_ever_live[i] && ! LOCAL_REGNO (i)
972 && ! TEST_HARD_REG_BIT (regs_invalidated_by_call, i))
973 SET_REGNO_REG_SET (set, i);
976 #ifdef EH_RETURN_DATA_REGNO
977 /* Mark the registers that will contain data for the handler. */
978 if (reload_completed && current_function_calls_eh_return)
979 for (i = 0; ; ++i)
981 unsigned regno = EH_RETURN_DATA_REGNO(i);
982 if (regno == INVALID_REGNUM)
983 break;
984 SET_REGNO_REG_SET (set, regno);
986 #endif
987 #ifdef EH_RETURN_STACKADJ_RTX
988 if ((! HAVE_epilogue || ! epilogue_completed)
989 && current_function_calls_eh_return)
991 rtx tmp = EH_RETURN_STACKADJ_RTX;
992 if (tmp && REG_P (tmp))
993 mark_reg (tmp, set);
995 #endif
996 #ifdef EH_RETURN_HANDLER_RTX
997 if ((! HAVE_epilogue || ! epilogue_completed)
998 && current_function_calls_eh_return)
1000 rtx tmp = EH_RETURN_HANDLER_RTX;
1001 if (tmp && REG_P (tmp))
1002 mark_reg (tmp, set);
1004 #endif
1006 /* Mark function return value. */
1007 diddle_return_value (mark_reg, set);
1010 /* Propagate global life info around the graph of basic blocks. Begin
1011 considering blocks with their corresponding bit set in BLOCKS_IN.
1012 If BLOCKS_IN is null, consider it the universal set.
1014 BLOCKS_OUT is set for every block that was changed. */
1016 static void
1017 calculate_global_regs_live (sbitmap blocks_in, sbitmap blocks_out, int flags)
1019 basic_block *queue, *qhead, *qtail, *qend, bb;
1020 regset tmp, new_live_at_end, invalidated_by_call;
1021 regset registers_made_dead;
1022 bool failure_strategy_required = false;
1023 int *block_accesses;
1025 /* The registers that are modified within this in block. */
1026 regset *local_sets;
1028 /* The registers that are conditionally modified within this block.
1029 In other words, regs that are set only as part of a COND_EXEC. */
1030 regset *cond_local_sets;
1032 int i;
1034 /* Some passes used to forget clear aux field of basic block causing
1035 sick behavior here. */
1036 #ifdef ENABLE_CHECKING
1037 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
1038 gcc_assert (!bb->aux);
1039 #endif
1041 tmp = ALLOC_REG_SET (&reg_obstack);
1042 new_live_at_end = ALLOC_REG_SET (&reg_obstack);
1043 invalidated_by_call = ALLOC_REG_SET (&reg_obstack);
1044 registers_made_dead = ALLOC_REG_SET (&reg_obstack);
1046 /* Inconveniently, this is only readily available in hard reg set form. */
1047 for (i = 0; i < FIRST_PSEUDO_REGISTER; ++i)
1048 if (TEST_HARD_REG_BIT (regs_invalidated_by_call, i))
1049 SET_REGNO_REG_SET (invalidated_by_call, i);
1051 /* Allocate space for the sets of local properties. */
1052 local_sets = xcalloc (last_basic_block - (INVALID_BLOCK + 1),
1053 sizeof (regset));
1054 cond_local_sets = xcalloc (last_basic_block - (INVALID_BLOCK + 1),
1055 sizeof (regset));
1057 /* Create a worklist. Allocate an extra slot for ENTRY_BLOCK, and one
1058 because the `head == tail' style test for an empty queue doesn't
1059 work with a full queue. */
1060 queue = xmalloc ((n_basic_blocks - (INVALID_BLOCK + 1)) * sizeof (*queue));
1061 qtail = queue;
1062 qhead = qend = queue + n_basic_blocks - (INVALID_BLOCK + 1);
1064 /* Queue the blocks set in the initial mask. Do this in reverse block
1065 number order so that we are more likely for the first round to do
1066 useful work. We use AUX non-null to flag that the block is queued. */
1067 if (blocks_in)
1069 FOR_EACH_BB (bb)
1070 if (TEST_BIT (blocks_in, bb->index))
1072 *--qhead = bb;
1073 bb->aux = bb;
1076 else
1078 FOR_EACH_BB (bb)
1080 *--qhead = bb;
1081 bb->aux = bb;
1085 block_accesses = xcalloc (last_basic_block, sizeof (int));
1087 /* We clean aux when we remove the initially-enqueued bbs, but we
1088 don't enqueue ENTRY and EXIT initially, so clean them upfront and
1089 unconditionally. */
1090 ENTRY_BLOCK_PTR->aux = EXIT_BLOCK_PTR->aux = NULL;
1092 if (blocks_out)
1093 sbitmap_zero (blocks_out);
1095 /* We work through the queue until there are no more blocks. What
1096 is live at the end of this block is precisely the union of what
1097 is live at the beginning of all its successors. So, we set its
1098 GLOBAL_LIVE_AT_END field based on the GLOBAL_LIVE_AT_START field
1099 for its successors. Then, we compute GLOBAL_LIVE_AT_START for
1100 this block by walking through the instructions in this block in
1101 reverse order and updating as we go. If that changed
1102 GLOBAL_LIVE_AT_START, we add the predecessors of the block to the
1103 queue; they will now need to recalculate GLOBAL_LIVE_AT_END.
1105 We are guaranteed to terminate, because GLOBAL_LIVE_AT_START
1106 never shrinks. If a register appears in GLOBAL_LIVE_AT_START, it
1107 must either be live at the end of the block, or used within the
1108 block. In the latter case, it will certainly never disappear
1109 from GLOBAL_LIVE_AT_START. In the former case, the register
1110 could go away only if it disappeared from GLOBAL_LIVE_AT_START
1111 for one of the successor blocks. By induction, that cannot
1112 occur.
1114 ??? This reasoning doesn't work if we start from non-empty initial
1115 GLOBAL_LIVE_AT_START sets. And there are actually two problems:
1116 1) Updating may not terminate (endless oscillation).
1117 2) Even if it does (and it usually does), the resulting information
1118 may be inaccurate. Consider for example the following case:
1120 a = ...;
1121 while (...) {...} -- 'a' not mentioned at all
1122 ... = a;
1124 If the use of 'a' is deleted between two calculations of liveness
1125 information and the initial sets are not cleared, the information
1126 about a's liveness will get stuck inside the loop and the set will
1127 appear not to be dead.
1129 We do not attempt to solve 2) -- the information is conservatively
1130 correct (i.e. we never claim that something live is dead) and the
1131 amount of optimization opportunities missed due to this problem is
1132 not significant.
1134 1) is more serious. In order to fix it, we monitor the number of times
1135 each block is processed. Once one of the blocks has been processed more
1136 times than the maximum number of rounds, we use the following strategy:
1137 When a register disappears from one of the sets, we add it to a MAKE_DEAD
1138 set, remove all registers in this set from all GLOBAL_LIVE_AT_* sets and
1139 add the blocks with changed sets into the queue. Thus we are guaranteed
1140 to terminate (the worst case corresponds to all registers in MADE_DEAD,
1141 in which case the original reasoning above is valid), but in general we
1142 only fix up a few offending registers.
1144 The maximum number of rounds for computing liveness is the largest of
1145 MAX_LIVENESS_ROUNDS and the latest loop depth count for this function. */
1147 while (qhead != qtail)
1149 int rescan, changed;
1150 basic_block bb;
1151 edge e;
1152 edge_iterator ei;
1154 bb = *qhead++;
1155 if (qhead == qend)
1156 qhead = queue;
1157 bb->aux = NULL;
1159 /* Should we start using the failure strategy? */
1160 if (bb != ENTRY_BLOCK_PTR)
1162 int max_liveness_rounds =
1163 MAX (MAX_LIVENESS_ROUNDS, cfun->max_loop_depth);
1165 block_accesses[bb->index]++;
1166 if (block_accesses[bb->index] > max_liveness_rounds)
1167 failure_strategy_required = true;
1170 /* Begin by propagating live_at_start from the successor blocks. */
1171 CLEAR_REG_SET (new_live_at_end);
1173 if (EDGE_COUNT (bb->succs) > 0)
1174 FOR_EACH_EDGE (e, ei, bb->succs)
1176 basic_block sb = e->dest;
1178 /* Call-clobbered registers die across exception and
1179 call edges. */
1180 /* ??? Abnormal call edges ignored for the moment, as this gets
1181 confused by sibling call edges, which crashes reg-stack. */
1182 if (e->flags & EDGE_EH)
1183 bitmap_ior_and_compl_into (new_live_at_end,
1184 sb->global_live_at_start,
1185 invalidated_by_call);
1186 else
1187 IOR_REG_SET (new_live_at_end, sb->global_live_at_start);
1189 /* If a target saves one register in another (instead of on
1190 the stack) the save register will need to be live for EH. */
1191 if (e->flags & EDGE_EH)
1192 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1193 if (EH_USES (i))
1194 SET_REGNO_REG_SET (new_live_at_end, i);
1196 else
1198 /* This might be a noreturn function that throws. And
1199 even if it isn't, getting the unwind info right helps
1200 debugging. */
1201 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1202 if (EH_USES (i))
1203 SET_REGNO_REG_SET (new_live_at_end, i);
1206 /* The all-important stack pointer must always be live. */
1207 SET_REGNO_REG_SET (new_live_at_end, STACK_POINTER_REGNUM);
1209 /* Before reload, there are a few registers that must be forced
1210 live everywhere -- which might not already be the case for
1211 blocks within infinite loops. */
1212 if (! reload_completed)
1214 /* Any reference to any pseudo before reload is a potential
1215 reference of the frame pointer. */
1216 SET_REGNO_REG_SET (new_live_at_end, FRAME_POINTER_REGNUM);
1218 #if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
1219 /* Pseudos with argument area equivalences may require
1220 reloading via the argument pointer. */
1221 if (fixed_regs[ARG_POINTER_REGNUM])
1222 SET_REGNO_REG_SET (new_live_at_end, ARG_POINTER_REGNUM);
1223 #endif
1225 /* Any constant, or pseudo with constant equivalences, may
1226 require reloading from memory using the pic register. */
1227 if ((unsigned) PIC_OFFSET_TABLE_REGNUM != INVALID_REGNUM
1228 && fixed_regs[PIC_OFFSET_TABLE_REGNUM])
1229 SET_REGNO_REG_SET (new_live_at_end, PIC_OFFSET_TABLE_REGNUM);
1232 if (bb == ENTRY_BLOCK_PTR)
1234 COPY_REG_SET (bb->global_live_at_end, new_live_at_end);
1235 continue;
1238 /* On our first pass through this block, we'll go ahead and continue.
1239 Recognize first pass by checking if local_set is NULL for this
1240 basic block. On subsequent passes, we get to skip out early if
1241 live_at_end wouldn't have changed. */
1243 if (local_sets[bb->index - (INVALID_BLOCK + 1)] == NULL)
1245 local_sets[bb->index - (INVALID_BLOCK + 1)]
1246 = ALLOC_REG_SET (&reg_obstack);
1247 cond_local_sets[bb->index - (INVALID_BLOCK + 1)]
1248 = ALLOC_REG_SET (&reg_obstack);
1249 rescan = 1;
1251 else
1253 /* If any bits were removed from live_at_end, we'll have to
1254 rescan the block. This wouldn't be necessary if we had
1255 precalculated local_live, however with PROP_SCAN_DEAD_CODE
1256 local_live is really dependent on live_at_end. */
1257 rescan = bitmap_intersect_compl_p (bb->global_live_at_end,
1258 new_live_at_end);
1260 if (!rescan)
1262 regset cond_local_set;
1264 /* If any of the registers in the new live_at_end set are
1265 conditionally set in this basic block, we must rescan.
1266 This is because conditional lifetimes at the end of the
1267 block do not just take the live_at_end set into
1268 account, but also the liveness at the start of each
1269 successor block. We can miss changes in those sets if
1270 we only compare the new live_at_end against the
1271 previous one. */
1272 cond_local_set = cond_local_sets[bb->index - (INVALID_BLOCK + 1)];
1273 rescan = bitmap_intersect_p (new_live_at_end, cond_local_set);
1276 if (!rescan)
1278 regset local_set;
1280 /* Find the set of changed bits. Take this opportunity
1281 to notice that this set is empty and early out. */
1282 bitmap_xor (tmp, bb->global_live_at_end, new_live_at_end);
1283 if (bitmap_empty_p (tmp))
1284 continue;
1286 /* If any of the changed bits overlap with local_sets[bb],
1287 we'll have to rescan the block. */
1288 local_set = local_sets[bb->index - (INVALID_BLOCK + 1)];
1289 rescan = bitmap_intersect_p (tmp, local_set);
1293 /* Let our caller know that BB changed enough to require its
1294 death notes updated. */
1295 if (blocks_out)
1296 SET_BIT (blocks_out, bb->index);
1298 if (! rescan)
1300 /* Add to live_at_start the set of all registers in
1301 new_live_at_end that aren't in the old live_at_end. */
1303 changed = bitmap_ior_and_compl_into (bb->global_live_at_start,
1304 new_live_at_end,
1305 bb->global_live_at_end);
1306 COPY_REG_SET (bb->global_live_at_end, new_live_at_end);
1307 if (! changed)
1308 continue;
1310 else
1312 COPY_REG_SET (bb->global_live_at_end, new_live_at_end);
1314 /* Rescan the block insn by insn to turn (a copy of) live_at_end
1315 into live_at_start. */
1316 propagate_block (bb, new_live_at_end,
1317 local_sets[bb->index - (INVALID_BLOCK + 1)],
1318 cond_local_sets[bb->index - (INVALID_BLOCK + 1)],
1319 flags);
1321 /* If live_at start didn't change, no need to go farther. */
1322 if (REG_SET_EQUAL_P (bb->global_live_at_start, new_live_at_end))
1323 continue;
1325 if (failure_strategy_required)
1327 /* Get the list of registers that were removed from the
1328 bb->global_live_at_start set. */
1329 bitmap_and_compl (tmp, bb->global_live_at_start,
1330 new_live_at_end);
1331 if (!bitmap_empty_p (tmp))
1333 bool pbb_changed;
1334 basic_block pbb;
1336 /* It should not happen that one of registers we have
1337 removed last time is disappears again before any other
1338 register does. */
1339 pbb_changed = bitmap_ior_into (registers_made_dead, tmp);
1340 gcc_assert (pbb_changed);
1342 /* Now remove the registers from all sets. */
1343 FOR_EACH_BB (pbb)
1345 pbb_changed = false;
1347 pbb_changed
1348 |= bitmap_and_compl_into (pbb->global_live_at_start,
1349 registers_made_dead);
1350 pbb_changed
1351 |= bitmap_and_compl_into (pbb->global_live_at_end,
1352 registers_made_dead);
1353 if (!pbb_changed)
1354 continue;
1356 /* Note the (possible) change. */
1357 if (blocks_out)
1358 SET_BIT (blocks_out, pbb->index);
1360 /* Makes sure to really rescan the block. */
1361 if (local_sets[pbb->index - (INVALID_BLOCK + 1)])
1363 FREE_REG_SET (local_sets[pbb->index - (INVALID_BLOCK + 1)]);
1364 FREE_REG_SET (cond_local_sets[pbb->index - (INVALID_BLOCK + 1)]);
1365 local_sets[pbb->index - (INVALID_BLOCK + 1)] = 0;
1368 /* Add it to the queue. */
1369 if (pbb->aux == NULL)
1371 *qtail++ = pbb;
1372 if (qtail == qend)
1373 qtail = queue;
1374 pbb->aux = pbb;
1377 continue;
1379 } /* end of failure_strategy_required */
1381 COPY_REG_SET (bb->global_live_at_start, new_live_at_end);
1384 /* Queue all predecessors of BB so that we may re-examine
1385 their live_at_end. */
1386 FOR_EACH_EDGE (e, ei, bb->preds)
1388 basic_block pb = e->src;
1389 if (pb->aux == NULL)
1391 *qtail++ = pb;
1392 if (qtail == qend)
1393 qtail = queue;
1394 pb->aux = pb;
1399 FREE_REG_SET (tmp);
1400 FREE_REG_SET (new_live_at_end);
1401 FREE_REG_SET (invalidated_by_call);
1402 FREE_REG_SET (registers_made_dead);
1404 if (blocks_out)
1406 EXECUTE_IF_SET_IN_SBITMAP (blocks_out, 0, i,
1408 basic_block bb = BASIC_BLOCK (i);
1409 FREE_REG_SET (local_sets[bb->index - (INVALID_BLOCK + 1)]);
1410 FREE_REG_SET (cond_local_sets[bb->index - (INVALID_BLOCK + 1)]);
1413 else
1415 FOR_EACH_BB (bb)
1417 FREE_REG_SET (local_sets[bb->index - (INVALID_BLOCK + 1)]);
1418 FREE_REG_SET (cond_local_sets[bb->index - (INVALID_BLOCK + 1)]);
1422 free (block_accesses);
1423 free (queue);
1424 free (cond_local_sets);
1425 free (local_sets);
1429 /* This structure is used to pass parameters to and from the
1430 the function find_regno_partial(). It is used to pass in the
1431 register number we are looking, as well as to return any rtx
1432 we find. */
1434 typedef struct {
1435 unsigned regno_to_find;
1436 rtx retval;
1437 } find_regno_partial_param;
1440 /* Find the rtx for the reg numbers specified in 'data' if it is
1441 part of an expression which only uses part of the register. Return
1442 it in the structure passed in. */
1443 static int
1444 find_regno_partial (rtx *ptr, void *data)
1446 find_regno_partial_param *param = (find_regno_partial_param *)data;
1447 unsigned reg = param->regno_to_find;
1448 param->retval = NULL_RTX;
1450 if (*ptr == NULL_RTX)
1451 return 0;
1453 switch (GET_CODE (*ptr))
1455 case ZERO_EXTRACT:
1456 case SIGN_EXTRACT:
1457 case STRICT_LOW_PART:
1458 if (REG_P (XEXP (*ptr, 0)) && REGNO (XEXP (*ptr, 0)) == reg)
1460 param->retval = XEXP (*ptr, 0);
1461 return 1;
1463 break;
1465 case SUBREG:
1466 if (REG_P (SUBREG_REG (*ptr))
1467 && REGNO (SUBREG_REG (*ptr)) == reg)
1469 param->retval = SUBREG_REG (*ptr);
1470 return 1;
1472 break;
1474 default:
1475 break;
1478 return 0;
1481 /* Process all immediate successors of the entry block looking for pseudo
1482 registers which are live on entry. Find all of those whose first
1483 instance is a partial register reference of some kind, and initialize
1484 them to 0 after the entry block. This will prevent bit sets within
1485 registers whose value is unknown, and may contain some kind of sticky
1486 bits we don't want. */
1489 initialize_uninitialized_subregs (void)
1491 rtx insn;
1492 edge e;
1493 unsigned reg, did_something = 0;
1494 find_regno_partial_param param;
1495 edge_iterator ei;
1497 FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
1499 basic_block bb = e->dest;
1500 regset map = bb->global_live_at_start;
1501 reg_set_iterator rsi;
1503 EXECUTE_IF_SET_IN_REG_SET (map, FIRST_PSEUDO_REGISTER, reg, rsi)
1505 int uid = REGNO_FIRST_UID (reg);
1506 rtx i;
1508 /* Find an insn which mentions the register we are looking for.
1509 Its preferable to have an instance of the register's rtl since
1510 there may be various flags set which we need to duplicate.
1511 If we can't find it, its probably an automatic whose initial
1512 value doesn't matter, or hopefully something we don't care about. */
1513 for (i = get_insns (); i && INSN_UID (i) != uid; i = NEXT_INSN (i))
1515 if (i != NULL_RTX)
1517 /* Found the insn, now get the REG rtx, if we can. */
1518 param.regno_to_find = reg;
1519 for_each_rtx (&i, find_regno_partial, &param);
1520 if (param.retval != NULL_RTX)
1522 start_sequence ();
1523 emit_move_insn (param.retval,
1524 CONST0_RTX (GET_MODE (param.retval)));
1525 insn = get_insns ();
1526 end_sequence ();
1527 insert_insn_on_edge (insn, e);
1528 did_something = 1;
1534 if (did_something)
1535 commit_edge_insertions ();
1536 return did_something;
1540 /* Subroutines of life analysis. */
1542 /* Allocate the permanent data structures that represent the results
1543 of life analysis. */
1545 static void
1546 allocate_bb_life_data (void)
1548 basic_block bb;
1550 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
1552 bb->global_live_at_start = ALLOC_REG_SET (&reg_obstack);
1553 bb->global_live_at_end = ALLOC_REG_SET (&reg_obstack);
1556 regs_live_at_setjmp = ALLOC_REG_SET (&reg_obstack);
1559 void
1560 allocate_reg_life_data (void)
1562 int i;
1564 max_regno = max_reg_num ();
1565 gcc_assert (!reg_deaths);
1566 reg_deaths = xcalloc (sizeof (*reg_deaths), max_regno);
1568 /* Recalculate the register space, in case it has grown. Old style
1569 vector oriented regsets would set regset_{size,bytes} here also. */
1570 allocate_reg_info (max_regno, FALSE, FALSE);
1572 /* Reset all the data we'll collect in propagate_block and its
1573 subroutines. */
1574 for (i = 0; i < max_regno; i++)
1576 REG_N_SETS (i) = 0;
1577 REG_N_REFS (i) = 0;
1578 REG_N_DEATHS (i) = 0;
1579 REG_N_CALLS_CROSSED (i) = 0;
1580 REG_LIVE_LENGTH (i) = 0;
1581 REG_FREQ (i) = 0;
1582 REG_BASIC_BLOCK (i) = REG_BLOCK_UNKNOWN;
1586 /* Delete dead instructions for propagate_block. */
1588 static void
1589 propagate_block_delete_insn (rtx insn)
1591 rtx inote = find_reg_note (insn, REG_LABEL, NULL_RTX);
1593 /* If the insn referred to a label, and that label was attached to
1594 an ADDR_VEC, it's safe to delete the ADDR_VEC. In fact, it's
1595 pretty much mandatory to delete it, because the ADDR_VEC may be
1596 referencing labels that no longer exist.
1598 INSN may reference a deleted label, particularly when a jump
1599 table has been optimized into a direct jump. There's no
1600 real good way to fix up the reference to the deleted label
1601 when the label is deleted, so we just allow it here. */
1603 if (inote && LABEL_P (inote))
1605 rtx label = XEXP (inote, 0);
1606 rtx next;
1608 /* The label may be forced if it has been put in the constant
1609 pool. If that is the only use we must discard the table
1610 jump following it, but not the label itself. */
1611 if (LABEL_NUSES (label) == 1 + LABEL_PRESERVE_P (label)
1612 && (next = next_nonnote_insn (label)) != NULL
1613 && JUMP_P (next)
1614 && (GET_CODE (PATTERN (next)) == ADDR_VEC
1615 || GET_CODE (PATTERN (next)) == ADDR_DIFF_VEC))
1617 rtx pat = PATTERN (next);
1618 int diff_vec_p = GET_CODE (pat) == ADDR_DIFF_VEC;
1619 int len = XVECLEN (pat, diff_vec_p);
1620 int i;
1622 for (i = 0; i < len; i++)
1623 LABEL_NUSES (XEXP (XVECEXP (pat, diff_vec_p, i), 0))--;
1625 delete_insn_and_edges (next);
1626 ndead++;
1630 delete_insn_and_edges (insn);
1631 ndead++;
1634 /* Delete dead libcalls for propagate_block. Return the insn
1635 before the libcall. */
1637 static rtx
1638 propagate_block_delete_libcall (rtx insn, rtx note)
1640 rtx first = XEXP (note, 0);
1641 rtx before = PREV_INSN (first);
1643 delete_insn_chain_and_edges (first, insn);
1644 ndead++;
1645 return before;
1648 /* Update the life-status of regs for one insn. Return the previous insn. */
1651 propagate_one_insn (struct propagate_block_info *pbi, rtx insn)
1653 rtx prev = PREV_INSN (insn);
1654 int flags = pbi->flags;
1655 int insn_is_dead = 0;
1656 int libcall_is_dead = 0;
1657 rtx note;
1658 unsigned i;
1660 if (! INSN_P (insn))
1661 return prev;
1663 note = find_reg_note (insn, REG_RETVAL, NULL_RTX);
1664 if (flags & PROP_SCAN_DEAD_CODE)
1666 insn_is_dead = insn_dead_p (pbi, PATTERN (insn), 0, REG_NOTES (insn));
1667 libcall_is_dead = (insn_is_dead && note != 0
1668 && libcall_dead_p (pbi, note, insn));
1671 /* If an instruction consists of just dead store(s) on final pass,
1672 delete it. */
1673 if ((flags & PROP_KILL_DEAD_CODE) && insn_is_dead)
1675 /* If we're trying to delete a prologue or epilogue instruction
1676 that isn't flagged as possibly being dead, something is wrong.
1677 But if we are keeping the stack pointer depressed, we might well
1678 be deleting insns that are used to compute the amount to update
1679 it by, so they are fine. */
1680 if (reload_completed
1681 && !(TREE_CODE (TREE_TYPE (current_function_decl)) == FUNCTION_TYPE
1682 && (TYPE_RETURNS_STACK_DEPRESSED
1683 (TREE_TYPE (current_function_decl))))
1684 && (((HAVE_epilogue || HAVE_prologue)
1685 && prologue_epilogue_contains (insn))
1686 || (HAVE_sibcall_epilogue
1687 && sibcall_epilogue_contains (insn)))
1688 && find_reg_note (insn, REG_MAYBE_DEAD, NULL_RTX) == 0)
1689 fatal_insn ("Attempt to delete prologue/epilogue insn:", insn);
1691 /* Record sets. Do this even for dead instructions, since they
1692 would have killed the values if they hadn't been deleted. */
1693 mark_set_regs (pbi, PATTERN (insn), insn);
1695 /* CC0 is now known to be dead. Either this insn used it,
1696 in which case it doesn't anymore, or clobbered it,
1697 so the next insn can't use it. */
1698 pbi->cc0_live = 0;
1700 if (libcall_is_dead)
1701 prev = propagate_block_delete_libcall (insn, note);
1702 else
1705 /* If INSN contains a RETVAL note and is dead, but the libcall
1706 as a whole is not dead, then we want to remove INSN, but
1707 not the whole libcall sequence.
1709 However, we need to also remove the dangling REG_LIBCALL
1710 note so that we do not have mis-matched LIBCALL/RETVAL
1711 notes. In theory we could find a new location for the
1712 REG_RETVAL note, but it hardly seems worth the effort.
1714 NOTE at this point will be the RETVAL note if it exists. */
1715 if (note)
1717 rtx libcall_note;
1719 libcall_note
1720 = find_reg_note (XEXP (note, 0), REG_LIBCALL, NULL_RTX);
1721 remove_note (XEXP (note, 0), libcall_note);
1724 /* Similarly if INSN contains a LIBCALL note, remove the
1725 dangling REG_RETVAL note. */
1726 note = find_reg_note (insn, REG_LIBCALL, NULL_RTX);
1727 if (note)
1729 rtx retval_note;
1731 retval_note
1732 = find_reg_note (XEXP (note, 0), REG_RETVAL, NULL_RTX);
1733 remove_note (XEXP (note, 0), retval_note);
1736 /* Now delete INSN. */
1737 propagate_block_delete_insn (insn);
1740 return prev;
1743 /* See if this is an increment or decrement that can be merged into
1744 a following memory address. */
1745 #ifdef AUTO_INC_DEC
1747 rtx x = single_set (insn);
1749 /* Does this instruction increment or decrement a register? */
1750 if ((flags & PROP_AUTOINC)
1751 && x != 0
1752 && REG_P (SET_DEST (x))
1753 && (GET_CODE (SET_SRC (x)) == PLUS
1754 || GET_CODE (SET_SRC (x)) == MINUS)
1755 && XEXP (SET_SRC (x), 0) == SET_DEST (x)
1756 && GET_CODE (XEXP (SET_SRC (x), 1)) == CONST_INT
1757 /* Ok, look for a following memory ref we can combine with.
1758 If one is found, change the memory ref to a PRE_INC
1759 or PRE_DEC, cancel this insn, and return 1.
1760 Return 0 if nothing has been done. */
1761 && try_pre_increment_1 (pbi, insn))
1762 return prev;
1764 #endif /* AUTO_INC_DEC */
1766 CLEAR_REG_SET (pbi->new_set);
1768 /* If this is not the final pass, and this insn is copying the value of
1769 a library call and it's dead, don't scan the insns that perform the
1770 library call, so that the call's arguments are not marked live. */
1771 if (libcall_is_dead)
1773 /* Record the death of the dest reg. */
1774 mark_set_regs (pbi, PATTERN (insn), insn);
1776 insn = XEXP (note, 0);
1777 return PREV_INSN (insn);
1779 else if (GET_CODE (PATTERN (insn)) == SET
1780 && SET_DEST (PATTERN (insn)) == stack_pointer_rtx
1781 && GET_CODE (SET_SRC (PATTERN (insn))) == PLUS
1782 && XEXP (SET_SRC (PATTERN (insn)), 0) == stack_pointer_rtx
1783 && GET_CODE (XEXP (SET_SRC (PATTERN (insn)), 1)) == CONST_INT)
1785 /* We have an insn to pop a constant amount off the stack.
1786 (Such insns use PLUS regardless of the direction of the stack,
1787 and any insn to adjust the stack by a constant is always a pop
1788 or part of a push.)
1789 These insns, if not dead stores, have no effect on life, though
1790 they do have an effect on the memory stores we are tracking. */
1791 invalidate_mems_from_set (pbi, stack_pointer_rtx);
1792 /* Still, we need to update local_set, lest ifcvt.c:dead_or_predicable
1793 concludes that the stack pointer is not modified. */
1794 mark_set_regs (pbi, PATTERN (insn), insn);
1796 else
1798 rtx note;
1799 /* Any regs live at the time of a call instruction must not go
1800 in a register clobbered by calls. Find all regs now live and
1801 record this for them. */
1803 if (CALL_P (insn) && (flags & PROP_REG_INFO))
1805 reg_set_iterator rsi;
1806 EXECUTE_IF_SET_IN_REG_SET (pbi->reg_live, 0, i, rsi)
1807 REG_N_CALLS_CROSSED (i)++;
1810 /* Record sets. Do this even for dead instructions, since they
1811 would have killed the values if they hadn't been deleted. */
1812 mark_set_regs (pbi, PATTERN (insn), insn);
1814 if (CALL_P (insn))
1816 regset live_at_end;
1817 bool sibcall_p;
1818 rtx note, cond;
1819 int i;
1821 cond = NULL_RTX;
1822 if (GET_CODE (PATTERN (insn)) == COND_EXEC)
1823 cond = COND_EXEC_TEST (PATTERN (insn));
1825 /* Non-constant calls clobber memory, constant calls do not
1826 clobber memory, though they may clobber outgoing arguments
1827 on the stack. */
1828 if (! CONST_OR_PURE_CALL_P (insn))
1830 free_EXPR_LIST_list (&pbi->mem_set_list);
1831 pbi->mem_set_list_len = 0;
1833 else
1834 invalidate_mems_from_set (pbi, stack_pointer_rtx);
1836 /* There may be extra registers to be clobbered. */
1837 for (note = CALL_INSN_FUNCTION_USAGE (insn);
1838 note;
1839 note = XEXP (note, 1))
1840 if (GET_CODE (XEXP (note, 0)) == CLOBBER)
1841 mark_set_1 (pbi, CLOBBER, XEXP (XEXP (note, 0), 0),
1842 cond, insn, pbi->flags);
1844 /* Calls change all call-used and global registers; sibcalls do not
1845 clobber anything that must be preserved at end-of-function,
1846 except for return values. */
1848 sibcall_p = SIBLING_CALL_P (insn);
1849 live_at_end = EXIT_BLOCK_PTR->global_live_at_start;
1850 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1851 if (TEST_HARD_REG_BIT (regs_invalidated_by_call, i)
1852 && ! (sibcall_p
1853 && REGNO_REG_SET_P (live_at_end, i)
1854 && ! refers_to_regno_p (i, i+1,
1855 current_function_return_rtx,
1856 (rtx *) 0)))
1858 enum rtx_code code = global_regs[i] ? SET : CLOBBER;
1859 /* We do not want REG_UNUSED notes for these registers. */
1860 mark_set_1 (pbi, code, regno_reg_rtx[i], cond, insn,
1861 pbi->flags & ~(PROP_DEATH_NOTES | PROP_REG_INFO));
1865 /* If an insn doesn't use CC0, it becomes dead since we assume
1866 that every insn clobbers it. So show it dead here;
1867 mark_used_regs will set it live if it is referenced. */
1868 pbi->cc0_live = 0;
1870 /* Record uses. */
1871 if (! insn_is_dead)
1872 mark_used_regs (pbi, PATTERN (insn), NULL_RTX, insn);
1873 if ((flags & PROP_EQUAL_NOTES)
1874 && ((note = find_reg_note (insn, REG_EQUAL, NULL_RTX))
1875 || (note = find_reg_note (insn, REG_EQUIV, NULL_RTX))))
1876 mark_used_regs (pbi, XEXP (note, 0), NULL_RTX, insn);
1878 /* Sometimes we may have inserted something before INSN (such as a move)
1879 when we make an auto-inc. So ensure we will scan those insns. */
1880 #ifdef AUTO_INC_DEC
1881 prev = PREV_INSN (insn);
1882 #endif
1884 if (! insn_is_dead && CALL_P (insn))
1886 int i;
1887 rtx note, cond;
1889 cond = NULL_RTX;
1890 if (GET_CODE (PATTERN (insn)) == COND_EXEC)
1891 cond = COND_EXEC_TEST (PATTERN (insn));
1893 /* Calls use their arguments, and may clobber memory which
1894 address involves some register. */
1895 for (note = CALL_INSN_FUNCTION_USAGE (insn);
1896 note;
1897 note = XEXP (note, 1))
1898 /* We find USE or CLOBBER entities in a FUNCTION_USAGE list: both
1899 of which mark_used_regs knows how to handle. */
1900 mark_used_regs (pbi, XEXP (XEXP (note, 0), 0), cond, insn);
1902 /* The stack ptr is used (honorarily) by a CALL insn. */
1903 if ((flags & PROP_REG_INFO)
1904 && !REGNO_REG_SET_P (pbi->reg_live, STACK_POINTER_REGNUM))
1905 reg_deaths[STACK_POINTER_REGNUM] = pbi->insn_num;
1906 SET_REGNO_REG_SET (pbi->reg_live, STACK_POINTER_REGNUM);
1908 /* Calls may also reference any of the global registers,
1909 so they are made live. */
1910 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1911 if (global_regs[i])
1912 mark_used_reg (pbi, regno_reg_rtx[i], cond, insn);
1916 pbi->insn_num++;
1918 return prev;
1921 /* Initialize a propagate_block_info struct for public consumption.
1922 Note that the structure itself is opaque to this file, but that
1923 the user can use the regsets provided here. */
1925 struct propagate_block_info *
1926 init_propagate_block_info (basic_block bb, regset live, regset local_set,
1927 regset cond_local_set, int flags)
1929 struct propagate_block_info *pbi = xmalloc (sizeof (*pbi));
1931 pbi->bb = bb;
1932 pbi->reg_live = live;
1933 pbi->mem_set_list = NULL_RTX;
1934 pbi->mem_set_list_len = 0;
1935 pbi->local_set = local_set;
1936 pbi->cond_local_set = cond_local_set;
1937 pbi->cc0_live = 0;
1938 pbi->flags = flags;
1939 pbi->insn_num = 0;
1941 if (flags & (PROP_LOG_LINKS | PROP_AUTOINC))
1942 pbi->reg_next_use = xcalloc (max_reg_num (), sizeof (rtx));
1943 else
1944 pbi->reg_next_use = NULL;
1946 pbi->new_set = BITMAP_ALLOC (NULL);
1948 #ifdef HAVE_conditional_execution
1949 pbi->reg_cond_dead = splay_tree_new (splay_tree_compare_ints, NULL,
1950 free_reg_cond_life_info);
1951 pbi->reg_cond_reg = BITMAP_ALLOC (NULL);
1953 /* If this block ends in a conditional branch, for each register
1954 live from one side of the branch and not the other, record the
1955 register as conditionally dead. */
1956 if (JUMP_P (BB_END (bb))
1957 && any_condjump_p (BB_END (bb)))
1959 regset diff = ALLOC_REG_SET (&reg_obstack);
1960 basic_block bb_true, bb_false;
1961 unsigned i;
1963 /* Identify the successor blocks. */
1964 bb_true = EDGE_SUCC (bb, 0)->dest;
1965 if (!single_succ_p (bb))
1967 bb_false = EDGE_SUCC (bb, 1)->dest;
1969 if (EDGE_SUCC (bb, 0)->flags & EDGE_FALLTHRU)
1971 basic_block t = bb_false;
1972 bb_false = bb_true;
1973 bb_true = t;
1975 else
1976 gcc_assert (EDGE_SUCC (bb, 1)->flags & EDGE_FALLTHRU);
1978 else
1980 /* This can happen with a conditional jump to the next insn. */
1981 gcc_assert (JUMP_LABEL (BB_END (bb)) == BB_HEAD (bb_true));
1983 /* Simplest way to do nothing. */
1984 bb_false = bb_true;
1987 /* Compute which register lead different lives in the successors. */
1988 bitmap_xor (diff, bb_true->global_live_at_start,
1989 bb_false->global_live_at_start);
1991 if (!bitmap_empty_p (diff))
1993 /* Extract the condition from the branch. */
1994 rtx set_src = SET_SRC (pc_set (BB_END (bb)));
1995 rtx cond_true = XEXP (set_src, 0);
1996 rtx reg = XEXP (cond_true, 0);
1997 enum rtx_code inv_cond;
1999 if (GET_CODE (reg) == SUBREG)
2000 reg = SUBREG_REG (reg);
2002 /* We can only track conditional lifetimes if the condition is
2003 in the form of a reversible comparison of a register against
2004 zero. If the condition is more complex than that, then it is
2005 safe not to record any information. */
2006 inv_cond = reversed_comparison_code (cond_true, BB_END (bb));
2007 if (inv_cond != UNKNOWN
2008 && REG_P (reg)
2009 && XEXP (cond_true, 1) == const0_rtx)
2011 rtx cond_false
2012 = gen_rtx_fmt_ee (inv_cond,
2013 GET_MODE (cond_true), XEXP (cond_true, 0),
2014 XEXP (cond_true, 1));
2015 reg_set_iterator rsi;
2017 if (GET_CODE (XEXP (set_src, 1)) == PC)
2019 rtx t = cond_false;
2020 cond_false = cond_true;
2021 cond_true = t;
2024 SET_REGNO_REG_SET (pbi->reg_cond_reg, REGNO (reg));
2026 /* For each such register, mark it conditionally dead. */
2027 EXECUTE_IF_SET_IN_REG_SET (diff, 0, i, rsi)
2029 struct reg_cond_life_info *rcli;
2030 rtx cond;
2032 rcli = xmalloc (sizeof (*rcli));
2034 if (REGNO_REG_SET_P (bb_true->global_live_at_start, i))
2035 cond = cond_false;
2036 else
2037 cond = cond_true;
2038 rcli->condition = cond;
2039 rcli->stores = const0_rtx;
2040 rcli->orig_condition = cond;
2042 splay_tree_insert (pbi->reg_cond_dead, i,
2043 (splay_tree_value) rcli);
2048 FREE_REG_SET (diff);
2050 #endif
2052 /* If this block has no successors, any stores to the frame that aren't
2053 used later in the block are dead. So make a pass over the block
2054 recording any such that are made and show them dead at the end. We do
2055 a very conservative and simple job here. */
2056 if (optimize
2057 && ! (TREE_CODE (TREE_TYPE (current_function_decl)) == FUNCTION_TYPE
2058 && (TYPE_RETURNS_STACK_DEPRESSED
2059 (TREE_TYPE (current_function_decl))))
2060 && (flags & PROP_SCAN_DEAD_STORES)
2061 && (EDGE_COUNT (bb->succs) == 0
2062 || (single_succ_p (bb)
2063 && single_succ (bb) == EXIT_BLOCK_PTR
2064 && ! current_function_calls_eh_return)))
2066 rtx insn, set;
2067 for (insn = BB_END (bb); insn != BB_HEAD (bb); insn = PREV_INSN (insn))
2068 if (NONJUMP_INSN_P (insn)
2069 && (set = single_set (insn))
2070 && MEM_P (SET_DEST (set)))
2072 rtx mem = SET_DEST (set);
2073 rtx canon_mem = canon_rtx (mem);
2075 if (XEXP (canon_mem, 0) == frame_pointer_rtx
2076 || (GET_CODE (XEXP (canon_mem, 0)) == PLUS
2077 && XEXP (XEXP (canon_mem, 0), 0) == frame_pointer_rtx
2078 && GET_CODE (XEXP (XEXP (canon_mem, 0), 1)) == CONST_INT))
2079 add_to_mem_set_list (pbi, canon_mem);
2083 return pbi;
2086 /* Release a propagate_block_info struct. */
2088 void
2089 free_propagate_block_info (struct propagate_block_info *pbi)
2091 free_EXPR_LIST_list (&pbi->mem_set_list);
2093 BITMAP_FREE (pbi->new_set);
2095 #ifdef HAVE_conditional_execution
2096 splay_tree_delete (pbi->reg_cond_dead);
2097 BITMAP_FREE (pbi->reg_cond_reg);
2098 #endif
2100 if (pbi->flags & PROP_REG_INFO)
2102 int num = pbi->insn_num;
2103 unsigned i;
2104 reg_set_iterator rsi;
2106 EXECUTE_IF_SET_IN_REG_SET (pbi->reg_live, 0, i, rsi)
2108 REG_LIVE_LENGTH (i) += num - reg_deaths[i];
2109 reg_deaths[i] = 0;
2112 if (pbi->reg_next_use)
2113 free (pbi->reg_next_use);
2115 free (pbi);
2118 /* Compute the registers live at the beginning of a basic block BB from
2119 those live at the end.
2121 When called, REG_LIVE contains those live at the end. On return, it
2122 contains those live at the beginning.
2124 LOCAL_SET, if non-null, will be set with all registers killed
2125 unconditionally by this basic block.
2126 Likewise, COND_LOCAL_SET, if non-null, will be set with all registers
2127 killed conditionally by this basic block. If there is any unconditional
2128 set of a register, then the corresponding bit will be set in LOCAL_SET
2129 and cleared in COND_LOCAL_SET.
2130 It is valid for LOCAL_SET and COND_LOCAL_SET to be the same set. In this
2131 case, the resulting set will be equal to the union of the two sets that
2132 would otherwise be computed.
2134 Return nonzero if an INSN is deleted (i.e. by dead code removal). */
2137 propagate_block (basic_block bb, regset live, regset local_set,
2138 regset cond_local_set, int flags)
2140 struct propagate_block_info *pbi;
2141 rtx insn, prev;
2142 int changed;
2144 pbi = init_propagate_block_info (bb, live, local_set, cond_local_set, flags);
2146 if (flags & PROP_REG_INFO)
2148 unsigned i;
2149 reg_set_iterator rsi;
2151 /* Process the regs live at the end of the block.
2152 Mark them as not local to any one basic block. */
2153 EXECUTE_IF_SET_IN_REG_SET (live, 0, i, rsi)
2154 REG_BASIC_BLOCK (i) = REG_BLOCK_GLOBAL;
2157 /* Scan the block an insn at a time from end to beginning. */
2159 changed = 0;
2160 for (insn = BB_END (bb); ; insn = prev)
2162 /* If this is a call to `setjmp' et al, warn if any
2163 non-volatile datum is live. */
2164 if ((flags & PROP_REG_INFO)
2165 && CALL_P (insn)
2166 && find_reg_note (insn, REG_SETJMP, NULL))
2167 IOR_REG_SET (regs_live_at_setjmp, pbi->reg_live);
2169 prev = propagate_one_insn (pbi, insn);
2170 if (!prev)
2171 changed |= insn != get_insns ();
2172 else
2173 changed |= NEXT_INSN (prev) != insn;
2175 if (insn == BB_HEAD (bb))
2176 break;
2179 free_propagate_block_info (pbi);
2181 return changed;
2184 /* Return 1 if X (the body of an insn, or part of it) is just dead stores
2185 (SET expressions whose destinations are registers dead after the insn).
2186 NEEDED is the regset that says which regs are alive after the insn.
2188 Unless CALL_OK is nonzero, an insn is needed if it contains a CALL.
2190 If X is the entire body of an insn, NOTES contains the reg notes
2191 pertaining to the insn. */
2193 static int
2194 insn_dead_p (struct propagate_block_info *pbi, rtx x, int call_ok,
2195 rtx notes ATTRIBUTE_UNUSED)
2197 enum rtx_code code = GET_CODE (x);
2199 /* Don't eliminate insns that may trap. */
2200 if (flag_non_call_exceptions && may_trap_p (x))
2201 return 0;
2203 #ifdef AUTO_INC_DEC
2204 /* As flow is invoked after combine, we must take existing AUTO_INC
2205 expressions into account. */
2206 for (; notes; notes = XEXP (notes, 1))
2208 if (REG_NOTE_KIND (notes) == REG_INC)
2210 int regno = REGNO (XEXP (notes, 0));
2212 /* Don't delete insns to set global regs. */
2213 if ((regno < FIRST_PSEUDO_REGISTER && global_regs[regno])
2214 || REGNO_REG_SET_P (pbi->reg_live, regno))
2215 return 0;
2218 #endif
2220 /* If setting something that's a reg or part of one,
2221 see if that register's altered value will be live. */
2223 if (code == SET)
2225 rtx r = SET_DEST (x);
2227 #ifdef HAVE_cc0
2228 if (GET_CODE (r) == CC0)
2229 return ! pbi->cc0_live;
2230 #endif
2232 /* A SET that is a subroutine call cannot be dead. */
2233 if (GET_CODE (SET_SRC (x)) == CALL)
2235 if (! call_ok)
2236 return 0;
2239 /* Don't eliminate loads from volatile memory or volatile asms. */
2240 else if (volatile_refs_p (SET_SRC (x)))
2241 return 0;
2243 if (MEM_P (r))
2245 rtx temp, canon_r;
2247 if (MEM_VOLATILE_P (r) || GET_MODE (r) == BLKmode)
2248 return 0;
2250 canon_r = canon_rtx (r);
2252 /* Walk the set of memory locations we are currently tracking
2253 and see if one is an identical match to this memory location.
2254 If so, this memory write is dead (remember, we're walking
2255 backwards from the end of the block to the start). Since
2256 rtx_equal_p does not check the alias set or flags, we also
2257 must have the potential for them to conflict (anti_dependence). */
2258 for (temp = pbi->mem_set_list; temp != 0; temp = XEXP (temp, 1))
2259 if (anti_dependence (r, XEXP (temp, 0)))
2261 rtx mem = XEXP (temp, 0);
2263 if (rtx_equal_p (XEXP (canon_r, 0), XEXP (mem, 0))
2264 && (GET_MODE_SIZE (GET_MODE (canon_r))
2265 <= GET_MODE_SIZE (GET_MODE (mem))))
2266 return 1;
2268 #ifdef AUTO_INC_DEC
2269 /* Check if memory reference matches an auto increment. Only
2270 post increment/decrement or modify are valid. */
2271 if (GET_MODE (mem) == GET_MODE (r)
2272 && (GET_CODE (XEXP (mem, 0)) == POST_DEC
2273 || GET_CODE (XEXP (mem, 0)) == POST_INC
2274 || GET_CODE (XEXP (mem, 0)) == POST_MODIFY)
2275 && GET_MODE (XEXP (mem, 0)) == GET_MODE (r)
2276 && rtx_equal_p (XEXP (XEXP (mem, 0), 0), XEXP (r, 0)))
2277 return 1;
2278 #endif
2281 else
2283 while (GET_CODE (r) == SUBREG
2284 || GET_CODE (r) == STRICT_LOW_PART
2285 || GET_CODE (r) == ZERO_EXTRACT)
2286 r = XEXP (r, 0);
2288 if (REG_P (r))
2290 int regno = REGNO (r);
2292 /* Obvious. */
2293 if (REGNO_REG_SET_P (pbi->reg_live, regno))
2294 return 0;
2296 /* If this is a hard register, verify that subsequent
2297 words are not needed. */
2298 if (regno < FIRST_PSEUDO_REGISTER)
2300 int n = hard_regno_nregs[regno][GET_MODE (r)];
2302 while (--n > 0)
2303 if (REGNO_REG_SET_P (pbi->reg_live, regno+n))
2304 return 0;
2307 /* Don't delete insns to set global regs. */
2308 if (regno < FIRST_PSEUDO_REGISTER && global_regs[regno])
2309 return 0;
2311 /* Make sure insns to set the stack pointer aren't deleted. */
2312 if (regno == STACK_POINTER_REGNUM)
2313 return 0;
2315 /* ??? These bits might be redundant with the force live bits
2316 in calculate_global_regs_live. We would delete from
2317 sequential sets; whether this actually affects real code
2318 for anything but the stack pointer I don't know. */
2319 /* Make sure insns to set the frame pointer aren't deleted. */
2320 if (regno == FRAME_POINTER_REGNUM
2321 && (! reload_completed || frame_pointer_needed))
2322 return 0;
2323 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
2324 if (regno == HARD_FRAME_POINTER_REGNUM
2325 && (! reload_completed || frame_pointer_needed))
2326 return 0;
2327 #endif
2329 #if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
2330 /* Make sure insns to set arg pointer are never deleted
2331 (if the arg pointer isn't fixed, there will be a USE
2332 for it, so we can treat it normally). */
2333 if (regno == ARG_POINTER_REGNUM && fixed_regs[regno])
2334 return 0;
2335 #endif
2337 /* Otherwise, the set is dead. */
2338 return 1;
2343 /* If performing several activities, insn is dead if each activity
2344 is individually dead. Also, CLOBBERs and USEs can be ignored; a
2345 CLOBBER or USE that's inside a PARALLEL doesn't make the insn
2346 worth keeping. */
2347 else if (code == PARALLEL)
2349 int i = XVECLEN (x, 0);
2351 for (i--; i >= 0; i--)
2352 if (GET_CODE (XVECEXP (x, 0, i)) != CLOBBER
2353 && GET_CODE (XVECEXP (x, 0, i)) != USE
2354 && ! insn_dead_p (pbi, XVECEXP (x, 0, i), call_ok, NULL_RTX))
2355 return 0;
2357 return 1;
2360 /* A CLOBBER of a pseudo-register that is dead serves no purpose. That
2361 is not necessarily true for hard registers until after reload. */
2362 else if (code == CLOBBER)
2364 if (REG_P (XEXP (x, 0))
2365 && (REGNO (XEXP (x, 0)) >= FIRST_PSEUDO_REGISTER
2366 || reload_completed)
2367 && ! REGNO_REG_SET_P (pbi->reg_live, REGNO (XEXP (x, 0))))
2368 return 1;
2371 /* ??? A base USE is a historical relic. It ought not be needed anymore.
2372 Instances where it is still used are either (1) temporary and the USE
2373 escaped the pass, (2) cruft and the USE need not be emitted anymore,
2374 or (3) hiding bugs elsewhere that are not properly representing data
2375 flow. */
2377 return 0;
2380 /* If INSN is the last insn in a libcall, and assuming INSN is dead,
2381 return 1 if the entire library call is dead.
2382 This is true if INSN copies a register (hard or pseudo)
2383 and if the hard return reg of the call insn is dead.
2384 (The caller should have tested the destination of the SET inside
2385 INSN already for death.)
2387 If this insn doesn't just copy a register, then we don't
2388 have an ordinary libcall. In that case, cse could not have
2389 managed to substitute the source for the dest later on,
2390 so we can assume the libcall is dead.
2392 PBI is the block info giving pseudoregs live before this insn.
2393 NOTE is the REG_RETVAL note of the insn. */
2395 static int
2396 libcall_dead_p (struct propagate_block_info *pbi, rtx note, rtx insn)
2398 rtx x = single_set (insn);
2400 if (x)
2402 rtx r = SET_SRC (x);
2404 if (REG_P (r) || GET_CODE (r) == SUBREG)
2406 rtx call = XEXP (note, 0);
2407 rtx call_pat;
2408 int i;
2410 /* Find the call insn. */
2411 while (call != insn && !CALL_P (call))
2412 call = NEXT_INSN (call);
2414 /* If there is none, do nothing special,
2415 since ordinary death handling can understand these insns. */
2416 if (call == insn)
2417 return 0;
2419 /* See if the hard reg holding the value is dead.
2420 If this is a PARALLEL, find the call within it. */
2421 call_pat = PATTERN (call);
2422 if (GET_CODE (call_pat) == PARALLEL)
2424 for (i = XVECLEN (call_pat, 0) - 1; i >= 0; i--)
2425 if (GET_CODE (XVECEXP (call_pat, 0, i)) == SET
2426 && GET_CODE (SET_SRC (XVECEXP (call_pat, 0, i))) == CALL)
2427 break;
2429 /* This may be a library call that is returning a value
2430 via invisible pointer. Do nothing special, since
2431 ordinary death handling can understand these insns. */
2432 if (i < 0)
2433 return 0;
2435 call_pat = XVECEXP (call_pat, 0, i);
2438 if (! insn_dead_p (pbi, call_pat, 1, REG_NOTES (call)))
2439 return 0;
2441 while ((insn = PREV_INSN (insn)) != call)
2443 if (! INSN_P (insn))
2444 continue;
2445 if (! insn_dead_p (pbi, PATTERN (insn), 0, REG_NOTES (insn)))
2446 return 0;
2448 return 1;
2451 return 0;
2454 /* 1 if register REGNO was alive at a place where `setjmp' was called
2455 and was set more than once or is an argument.
2456 Such regs may be clobbered by `longjmp'. */
2459 regno_clobbered_at_setjmp (int regno)
2461 if (n_basic_blocks == 0)
2462 return 0;
2464 return ((REG_N_SETS (regno) > 1
2465 || REGNO_REG_SET_P (ENTRY_BLOCK_PTR->global_live_at_end, regno))
2466 && REGNO_REG_SET_P (regs_live_at_setjmp, regno));
2469 /* Add MEM to PBI->MEM_SET_LIST. MEM should be canonical. Respect the
2470 maximal list size; look for overlaps in mode and select the largest. */
2471 static void
2472 add_to_mem_set_list (struct propagate_block_info *pbi, rtx mem)
2474 rtx i;
2476 /* We don't know how large a BLKmode store is, so we must not
2477 take them into consideration. */
2478 if (GET_MODE (mem) == BLKmode)
2479 return;
2481 for (i = pbi->mem_set_list; i ; i = XEXP (i, 1))
2483 rtx e = XEXP (i, 0);
2484 if (rtx_equal_p (XEXP (mem, 0), XEXP (e, 0)))
2486 if (GET_MODE_SIZE (GET_MODE (mem)) > GET_MODE_SIZE (GET_MODE (e)))
2488 #ifdef AUTO_INC_DEC
2489 /* If we must store a copy of the mem, we can just modify
2490 the mode of the stored copy. */
2491 if (pbi->flags & PROP_AUTOINC)
2492 PUT_MODE (e, GET_MODE (mem));
2493 else
2494 #endif
2495 XEXP (i, 0) = mem;
2497 return;
2501 if (pbi->mem_set_list_len < MAX_MEM_SET_LIST_LEN)
2503 #ifdef AUTO_INC_DEC
2504 /* Store a copy of mem, otherwise the address may be
2505 scrogged by find_auto_inc. */
2506 if (pbi->flags & PROP_AUTOINC)
2507 mem = shallow_copy_rtx (mem);
2508 #endif
2509 pbi->mem_set_list = alloc_EXPR_LIST (0, mem, pbi->mem_set_list);
2510 pbi->mem_set_list_len++;
2514 /* INSN references memory, possibly using autoincrement addressing modes.
2515 Find any entries on the mem_set_list that need to be invalidated due
2516 to an address change. */
2518 static int
2519 invalidate_mems_from_autoinc (rtx *px, void *data)
2521 rtx x = *px;
2522 struct propagate_block_info *pbi = data;
2524 if (GET_RTX_CLASS (GET_CODE (x)) == RTX_AUTOINC)
2526 invalidate_mems_from_set (pbi, XEXP (x, 0));
2527 return -1;
2530 return 0;
2533 /* EXP is a REG. Remove any dependent entries from pbi->mem_set_list. */
2535 static void
2536 invalidate_mems_from_set (struct propagate_block_info *pbi, rtx exp)
2538 rtx temp = pbi->mem_set_list;
2539 rtx prev = NULL_RTX;
2540 rtx next;
2542 while (temp)
2544 next = XEXP (temp, 1);
2545 if (reg_overlap_mentioned_p (exp, XEXP (temp, 0)))
2547 /* Splice this entry out of the list. */
2548 if (prev)
2549 XEXP (prev, 1) = next;
2550 else
2551 pbi->mem_set_list = next;
2552 free_EXPR_LIST_node (temp);
2553 pbi->mem_set_list_len--;
2555 else
2556 prev = temp;
2557 temp = next;
2561 /* Process the registers that are set within X. Their bits are set to
2562 1 in the regset DEAD, because they are dead prior to this insn.
2564 If INSN is nonzero, it is the insn being processed.
2566 FLAGS is the set of operations to perform. */
2568 static void
2569 mark_set_regs (struct propagate_block_info *pbi, rtx x, rtx insn)
2571 rtx cond = NULL_RTX;
2572 rtx link;
2573 enum rtx_code code;
2574 int flags = pbi->flags;
2576 if (insn)
2577 for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
2579 if (REG_NOTE_KIND (link) == REG_INC)
2580 mark_set_1 (pbi, SET, XEXP (link, 0),
2581 (GET_CODE (x) == COND_EXEC
2582 ? COND_EXEC_TEST (x) : NULL_RTX),
2583 insn, flags);
2585 retry:
2586 switch (code = GET_CODE (x))
2588 case SET:
2589 if (GET_CODE (XEXP (x, 1)) == ASM_OPERANDS)
2590 flags |= PROP_ASM_SCAN;
2591 /* Fall through */
2592 case CLOBBER:
2593 mark_set_1 (pbi, code, SET_DEST (x), cond, insn, flags);
2594 return;
2596 case COND_EXEC:
2597 cond = COND_EXEC_TEST (x);
2598 x = COND_EXEC_CODE (x);
2599 goto retry;
2601 case PARALLEL:
2603 int i;
2605 /* We must scan forwards. If we have an asm, we need to set
2606 the PROP_ASM_SCAN flag before scanning the clobbers. */
2607 for (i = 0; i < XVECLEN (x, 0); i++)
2609 rtx sub = XVECEXP (x, 0, i);
2610 switch (code = GET_CODE (sub))
2612 case COND_EXEC:
2613 gcc_assert (!cond);
2615 cond = COND_EXEC_TEST (sub);
2616 sub = COND_EXEC_CODE (sub);
2617 if (GET_CODE (sub) == SET)
2618 goto mark_set;
2619 if (GET_CODE (sub) == CLOBBER)
2620 goto mark_clob;
2621 break;
2623 case SET:
2624 mark_set:
2625 if (GET_CODE (XEXP (sub, 1)) == ASM_OPERANDS)
2626 flags |= PROP_ASM_SCAN;
2627 /* Fall through */
2628 case CLOBBER:
2629 mark_clob:
2630 mark_set_1 (pbi, code, SET_DEST (sub), cond, insn, flags);
2631 break;
2633 case ASM_OPERANDS:
2634 flags |= PROP_ASM_SCAN;
2635 break;
2637 default:
2638 break;
2641 break;
2644 default:
2645 break;
2649 /* Process a single set, which appears in INSN. REG (which may not
2650 actually be a REG, it may also be a SUBREG, PARALLEL, etc.) is
2651 being set using the CODE (which may be SET, CLOBBER, or COND_EXEC).
2652 If the set is conditional (because it appear in a COND_EXEC), COND
2653 will be the condition. */
2655 static void
2656 mark_set_1 (struct propagate_block_info *pbi, enum rtx_code code, rtx reg, rtx cond, rtx insn, int flags)
2658 int regno_first = -1, regno_last = -1;
2659 unsigned long not_dead = 0;
2660 int i;
2662 /* Modifying just one hardware register of a multi-reg value or just a
2663 byte field of a register does not mean the value from before this insn
2664 is now dead. Of course, if it was dead after it's unused now. */
2666 switch (GET_CODE (reg))
2668 case PARALLEL:
2669 /* Some targets place small structures in registers for return values of
2670 functions. We have to detect this case specially here to get correct
2671 flow information. */
2672 for (i = XVECLEN (reg, 0) - 1; i >= 0; i--)
2673 if (XEXP (XVECEXP (reg, 0, i), 0) != 0)
2674 mark_set_1 (pbi, code, XEXP (XVECEXP (reg, 0, i), 0), cond, insn,
2675 flags);
2676 return;
2678 case SIGN_EXTRACT:
2679 /* SIGN_EXTRACT cannot be an lvalue. */
2680 gcc_unreachable ();
2682 case ZERO_EXTRACT:
2683 case STRICT_LOW_PART:
2684 /* ??? Assumes STRICT_LOW_PART not used on multi-word registers. */
2686 reg = XEXP (reg, 0);
2687 while (GET_CODE (reg) == SUBREG
2688 || GET_CODE (reg) == ZERO_EXTRACT
2689 || GET_CODE (reg) == STRICT_LOW_PART);
2690 if (MEM_P (reg))
2691 break;
2692 not_dead = (unsigned long) REGNO_REG_SET_P (pbi->reg_live, REGNO (reg));
2693 /* Fall through. */
2695 case REG:
2696 regno_last = regno_first = REGNO (reg);
2697 if (regno_first < FIRST_PSEUDO_REGISTER)
2698 regno_last += hard_regno_nregs[regno_first][GET_MODE (reg)] - 1;
2699 break;
2701 case SUBREG:
2702 if (REG_P (SUBREG_REG (reg)))
2704 enum machine_mode outer_mode = GET_MODE (reg);
2705 enum machine_mode inner_mode = GET_MODE (SUBREG_REG (reg));
2707 /* Identify the range of registers affected. This is moderately
2708 tricky for hard registers. See alter_subreg. */
2710 regno_last = regno_first = REGNO (SUBREG_REG (reg));
2711 if (regno_first < FIRST_PSEUDO_REGISTER)
2713 regno_first += subreg_regno_offset (regno_first, inner_mode,
2714 SUBREG_BYTE (reg),
2715 outer_mode);
2716 regno_last = (regno_first
2717 + hard_regno_nregs[regno_first][outer_mode] - 1);
2719 /* Since we've just adjusted the register number ranges, make
2720 sure REG matches. Otherwise some_was_live will be clear
2721 when it shouldn't have been, and we'll create incorrect
2722 REG_UNUSED notes. */
2723 reg = gen_rtx_REG (outer_mode, regno_first);
2725 else
2727 /* If the number of words in the subreg is less than the number
2728 of words in the full register, we have a well-defined partial
2729 set. Otherwise the high bits are undefined.
2731 This is only really applicable to pseudos, since we just took
2732 care of multi-word hard registers. */
2733 if (((GET_MODE_SIZE (outer_mode)
2734 + UNITS_PER_WORD - 1) / UNITS_PER_WORD)
2735 < ((GET_MODE_SIZE (inner_mode)
2736 + UNITS_PER_WORD - 1) / UNITS_PER_WORD))
2737 not_dead = (unsigned long) REGNO_REG_SET_P (pbi->reg_live,
2738 regno_first);
2740 reg = SUBREG_REG (reg);
2743 else
2744 reg = SUBREG_REG (reg);
2745 break;
2747 default:
2748 break;
2751 /* If this set is a MEM, then it kills any aliased writes.
2752 If this set is a REG, then it kills any MEMs which use the reg. */
2753 if (optimize && (flags & PROP_SCAN_DEAD_STORES))
2755 if (REG_P (reg))
2756 invalidate_mems_from_set (pbi, reg);
2758 /* If the memory reference had embedded side effects (autoincrement
2759 address modes) then we may need to kill some entries on the
2760 memory set list. */
2761 if (insn && MEM_P (reg))
2762 for_each_rtx (&PATTERN (insn), invalidate_mems_from_autoinc, pbi);
2764 if (MEM_P (reg) && ! side_effects_p (reg)
2765 /* ??? With more effort we could track conditional memory life. */
2766 && ! cond)
2767 add_to_mem_set_list (pbi, canon_rtx (reg));
2770 if (REG_P (reg)
2771 && ! (regno_first == FRAME_POINTER_REGNUM
2772 && (! reload_completed || frame_pointer_needed))
2773 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
2774 && ! (regno_first == HARD_FRAME_POINTER_REGNUM
2775 && (! reload_completed || frame_pointer_needed))
2776 #endif
2777 #if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
2778 && ! (regno_first == ARG_POINTER_REGNUM && fixed_regs[regno_first])
2779 #endif
2782 int some_was_live = 0, some_was_dead = 0;
2784 for (i = regno_first; i <= regno_last; ++i)
2786 int needed_regno = REGNO_REG_SET_P (pbi->reg_live, i);
2787 if (pbi->local_set)
2789 /* Order of the set operation matters here since both
2790 sets may be the same. */
2791 CLEAR_REGNO_REG_SET (pbi->cond_local_set, i);
2792 if (cond != NULL_RTX
2793 && ! REGNO_REG_SET_P (pbi->local_set, i))
2794 SET_REGNO_REG_SET (pbi->cond_local_set, i);
2795 else
2796 SET_REGNO_REG_SET (pbi->local_set, i);
2798 if (code != CLOBBER)
2799 SET_REGNO_REG_SET (pbi->new_set, i);
2801 some_was_live |= needed_regno;
2802 some_was_dead |= ! needed_regno;
2805 #ifdef HAVE_conditional_execution
2806 /* Consider conditional death in deciding that the register needs
2807 a death note. */
2808 if (some_was_live && ! not_dead
2809 /* The stack pointer is never dead. Well, not strictly true,
2810 but it's very difficult to tell from here. Hopefully
2811 combine_stack_adjustments will fix up the most egregious
2812 errors. */
2813 && regno_first != STACK_POINTER_REGNUM)
2815 for (i = regno_first; i <= regno_last; ++i)
2816 if (! mark_regno_cond_dead (pbi, i, cond))
2817 not_dead |= ((unsigned long) 1) << (i - regno_first);
2819 #endif
2821 /* Additional data to record if this is the final pass. */
2822 if (flags & (PROP_LOG_LINKS | PROP_REG_INFO
2823 | PROP_DEATH_NOTES | PROP_AUTOINC))
2825 rtx y;
2826 int blocknum = pbi->bb->index;
2828 y = NULL_RTX;
2829 if (flags & (PROP_LOG_LINKS | PROP_AUTOINC))
2831 y = pbi->reg_next_use[regno_first];
2833 /* The next use is no longer next, since a store intervenes. */
2834 for (i = regno_first; i <= regno_last; ++i)
2835 pbi->reg_next_use[i] = 0;
2838 if (flags & PROP_REG_INFO)
2840 for (i = regno_first; i <= regno_last; ++i)
2842 /* Count (weighted) references, stores, etc. This counts a
2843 register twice if it is modified, but that is correct. */
2844 REG_N_SETS (i) += 1;
2845 REG_N_REFS (i) += 1;
2846 REG_FREQ (i) += REG_FREQ_FROM_BB (pbi->bb);
2848 /* The insns where a reg is live are normally counted
2849 elsewhere, but we want the count to include the insn
2850 where the reg is set, and the normal counting mechanism
2851 would not count it. */
2852 REG_LIVE_LENGTH (i) += 1;
2855 /* If this is a hard reg, record this function uses the reg. */
2856 if (regno_first < FIRST_PSEUDO_REGISTER)
2858 for (i = regno_first; i <= regno_last; i++)
2859 regs_ever_live[i] = 1;
2860 if (flags & PROP_ASM_SCAN)
2861 for (i = regno_first; i <= regno_last; i++)
2862 regs_asm_clobbered[i] = 1;
2864 else
2866 /* Keep track of which basic blocks each reg appears in. */
2867 if (REG_BASIC_BLOCK (regno_first) == REG_BLOCK_UNKNOWN)
2868 REG_BASIC_BLOCK (regno_first) = blocknum;
2869 else if (REG_BASIC_BLOCK (regno_first) != blocknum)
2870 REG_BASIC_BLOCK (regno_first) = REG_BLOCK_GLOBAL;
2874 if (! some_was_dead)
2876 if (flags & PROP_LOG_LINKS)
2878 /* Make a logical link from the next following insn
2879 that uses this register, back to this insn.
2880 The following insns have already been processed.
2882 We don't build a LOG_LINK for hard registers containing
2883 in ASM_OPERANDs. If these registers get replaced,
2884 we might wind up changing the semantics of the insn,
2885 even if reload can make what appear to be valid
2886 assignments later.
2888 We don't build a LOG_LINK for global registers to
2889 or from a function call. We don't want to let
2890 combine think that it knows what is going on with
2891 global registers. */
2892 if (y && (BLOCK_NUM (y) == blocknum)
2893 && (regno_first >= FIRST_PSEUDO_REGISTER
2894 || (asm_noperands (PATTERN (y)) < 0
2895 && ! ((CALL_P (insn)
2896 || CALL_P (y))
2897 && global_regs[regno_first]))))
2898 LOG_LINKS (y) = alloc_INSN_LIST (insn, LOG_LINKS (y));
2901 else if (not_dead)
2903 else if (! some_was_live)
2905 if (flags & PROP_REG_INFO)
2906 REG_N_DEATHS (regno_first) += 1;
2908 if (flags & PROP_DEATH_NOTES)
2910 /* Note that dead stores have already been deleted
2911 when possible. If we get here, we have found a
2912 dead store that cannot be eliminated (because the
2913 same insn does something useful). Indicate this
2914 by marking the reg being set as dying here. */
2915 REG_NOTES (insn)
2916 = alloc_EXPR_LIST (REG_UNUSED, reg, REG_NOTES (insn));
2919 else
2921 if (flags & PROP_DEATH_NOTES)
2923 /* This is a case where we have a multi-word hard register
2924 and some, but not all, of the words of the register are
2925 needed in subsequent insns. Write REG_UNUSED notes
2926 for those parts that were not needed. This case should
2927 be rare. */
2929 for (i = regno_first; i <= regno_last; ++i)
2930 if (! REGNO_REG_SET_P (pbi->reg_live, i))
2931 REG_NOTES (insn)
2932 = alloc_EXPR_LIST (REG_UNUSED,
2933 regno_reg_rtx[i],
2934 REG_NOTES (insn));
2939 /* Mark the register as being dead. */
2940 if (some_was_live
2941 /* The stack pointer is never dead. Well, not strictly true,
2942 but it's very difficult to tell from here. Hopefully
2943 combine_stack_adjustments will fix up the most egregious
2944 errors. */
2945 && regno_first != STACK_POINTER_REGNUM)
2947 for (i = regno_first; i <= regno_last; ++i)
2948 if (!(not_dead & (((unsigned long) 1) << (i - regno_first))))
2950 if ((pbi->flags & PROP_REG_INFO)
2951 && REGNO_REG_SET_P (pbi->reg_live, i))
2953 REG_LIVE_LENGTH (i) += pbi->insn_num - reg_deaths[i];
2954 reg_deaths[i] = 0;
2956 CLEAR_REGNO_REG_SET (pbi->reg_live, i);
2960 else if (REG_P (reg))
2962 if (flags & (PROP_LOG_LINKS | PROP_AUTOINC))
2963 pbi->reg_next_use[regno_first] = 0;
2965 if ((flags & PROP_REG_INFO) != 0
2966 && (flags & PROP_ASM_SCAN) != 0
2967 && regno_first < FIRST_PSEUDO_REGISTER)
2969 for (i = regno_first; i <= regno_last; i++)
2970 regs_asm_clobbered[i] = 1;
2974 /* If this is the last pass and this is a SCRATCH, show it will be dying
2975 here and count it. */
2976 else if (GET_CODE (reg) == SCRATCH)
2978 if (flags & PROP_DEATH_NOTES)
2979 REG_NOTES (insn)
2980 = alloc_EXPR_LIST (REG_UNUSED, reg, REG_NOTES (insn));
2984 #ifdef HAVE_conditional_execution
2985 /* Mark REGNO conditionally dead.
2986 Return true if the register is now unconditionally dead. */
2988 static int
2989 mark_regno_cond_dead (struct propagate_block_info *pbi, int regno, rtx cond)
2991 /* If this is a store to a predicate register, the value of the
2992 predicate is changing, we don't know that the predicate as seen
2993 before is the same as that seen after. Flush all dependent
2994 conditions from reg_cond_dead. This will make all such
2995 conditionally live registers unconditionally live. */
2996 if (REGNO_REG_SET_P (pbi->reg_cond_reg, regno))
2997 flush_reg_cond_reg (pbi, regno);
2999 /* If this is an unconditional store, remove any conditional
3000 life that may have existed. */
3001 if (cond == NULL_RTX)
3002 splay_tree_remove (pbi->reg_cond_dead, regno);
3003 else
3005 splay_tree_node node;
3006 struct reg_cond_life_info *rcli;
3007 rtx ncond;
3009 /* Otherwise this is a conditional set. Record that fact.
3010 It may have been conditionally used, or there may be a
3011 subsequent set with a complementary condition. */
3013 node = splay_tree_lookup (pbi->reg_cond_dead, regno);
3014 if (node == NULL)
3016 /* The register was unconditionally live previously.
3017 Record the current condition as the condition under
3018 which it is dead. */
3019 rcli = xmalloc (sizeof (*rcli));
3020 rcli->condition = cond;
3021 rcli->stores = cond;
3022 rcli->orig_condition = const0_rtx;
3023 splay_tree_insert (pbi->reg_cond_dead, regno,
3024 (splay_tree_value) rcli);
3026 SET_REGNO_REG_SET (pbi->reg_cond_reg, REGNO (XEXP (cond, 0)));
3028 /* Not unconditionally dead. */
3029 return 0;
3031 else
3033 /* The register was conditionally live previously.
3034 Add the new condition to the old. */
3035 rcli = (struct reg_cond_life_info *) node->value;
3036 ncond = rcli->condition;
3037 ncond = ior_reg_cond (ncond, cond, 1);
3038 if (rcli->stores == const0_rtx)
3039 rcli->stores = cond;
3040 else if (rcli->stores != const1_rtx)
3041 rcli->stores = ior_reg_cond (rcli->stores, cond, 1);
3043 /* If the register is now unconditionally dead, remove the entry
3044 in the splay_tree. A register is unconditionally dead if the
3045 dead condition ncond is true. A register is also unconditionally
3046 dead if the sum of all conditional stores is an unconditional
3047 store (stores is true), and the dead condition is identically the
3048 same as the original dead condition initialized at the end of
3049 the block. This is a pointer compare, not an rtx_equal_p
3050 compare. */
3051 if (ncond == const1_rtx
3052 || (ncond == rcli->orig_condition && rcli->stores == const1_rtx))
3053 splay_tree_remove (pbi->reg_cond_dead, regno);
3054 else
3056 rcli->condition = ncond;
3058 SET_REGNO_REG_SET (pbi->reg_cond_reg, REGNO (XEXP (cond, 0)));
3060 /* Not unconditionally dead. */
3061 return 0;
3066 return 1;
3069 /* Called from splay_tree_delete for pbi->reg_cond_life. */
3071 static void
3072 free_reg_cond_life_info (splay_tree_value value)
3074 struct reg_cond_life_info *rcli = (struct reg_cond_life_info *) value;
3075 free (rcli);
3078 /* Helper function for flush_reg_cond_reg. */
3080 static int
3081 flush_reg_cond_reg_1 (splay_tree_node node, void *data)
3083 struct reg_cond_life_info *rcli;
3084 int *xdata = (int *) data;
3085 unsigned int regno = xdata[0];
3087 /* Don't need to search if last flushed value was farther on in
3088 the in-order traversal. */
3089 if (xdata[1] >= (int) node->key)
3090 return 0;
3092 /* Splice out portions of the expression that refer to regno. */
3093 rcli = (struct reg_cond_life_info *) node->value;
3094 rcli->condition = elim_reg_cond (rcli->condition, regno);
3095 if (rcli->stores != const0_rtx && rcli->stores != const1_rtx)
3096 rcli->stores = elim_reg_cond (rcli->stores, regno);
3098 /* If the entire condition is now false, signal the node to be removed. */
3099 if (rcli->condition == const0_rtx)
3101 xdata[1] = node->key;
3102 return -1;
3104 else
3105 gcc_assert (rcli->condition != const1_rtx);
3107 return 0;
3110 /* Flush all (sub) expressions referring to REGNO from REG_COND_LIVE. */
3112 static void
3113 flush_reg_cond_reg (struct propagate_block_info *pbi, int regno)
3115 int pair[2];
3117 pair[0] = regno;
3118 pair[1] = -1;
3119 while (splay_tree_foreach (pbi->reg_cond_dead,
3120 flush_reg_cond_reg_1, pair) == -1)
3121 splay_tree_remove (pbi->reg_cond_dead, pair[1]);
3123 CLEAR_REGNO_REG_SET (pbi->reg_cond_reg, regno);
3126 /* Logical arithmetic on predicate conditions. IOR, NOT and AND.
3127 For ior/and, the ADD flag determines whether we want to add the new
3128 condition X to the old one unconditionally. If it is zero, we will
3129 only return a new expression if X allows us to simplify part of
3130 OLD, otherwise we return NULL to the caller.
3131 If ADD is nonzero, we will return a new condition in all cases. The
3132 toplevel caller of one of these functions should always pass 1 for
3133 ADD. */
3135 static rtx
3136 ior_reg_cond (rtx old, rtx x, int add)
3138 rtx op0, op1;
3140 if (COMPARISON_P (old))
3142 if (COMPARISON_P (x)
3143 && REVERSE_CONDEXEC_PREDICATES_P (x, old)
3144 && REGNO (XEXP (x, 0)) == REGNO (XEXP (old, 0)))
3145 return const1_rtx;
3146 if (GET_CODE (x) == GET_CODE (old)
3147 && REGNO (XEXP (x, 0)) == REGNO (XEXP (old, 0)))
3148 return old;
3149 if (! add)
3150 return NULL;
3151 return gen_rtx_IOR (0, old, x);
3154 switch (GET_CODE (old))
3156 case IOR:
3157 op0 = ior_reg_cond (XEXP (old, 0), x, 0);
3158 op1 = ior_reg_cond (XEXP (old, 1), x, 0);
3159 if (op0 != NULL || op1 != NULL)
3161 if (op0 == const0_rtx)
3162 return op1 ? op1 : gen_rtx_IOR (0, XEXP (old, 1), x);
3163 if (op1 == const0_rtx)
3164 return op0 ? op0 : gen_rtx_IOR (0, XEXP (old, 0), x);
3165 if (op0 == const1_rtx || op1 == const1_rtx)
3166 return const1_rtx;
3167 if (op0 == NULL)
3168 op0 = gen_rtx_IOR (0, XEXP (old, 0), x);
3169 else if (rtx_equal_p (x, op0))
3170 /* (x | A) | x ~ (x | A). */
3171 return old;
3172 if (op1 == NULL)
3173 op1 = gen_rtx_IOR (0, XEXP (old, 1), x);
3174 else if (rtx_equal_p (x, op1))
3175 /* (A | x) | x ~ (A | x). */
3176 return old;
3177 return gen_rtx_IOR (0, op0, op1);
3179 if (! add)
3180 return NULL;
3181 return gen_rtx_IOR (0, old, x);
3183 case AND:
3184 op0 = ior_reg_cond (XEXP (old, 0), x, 0);
3185 op1 = ior_reg_cond (XEXP (old, 1), x, 0);
3186 if (op0 != NULL || op1 != NULL)
3188 if (op0 == const1_rtx)
3189 return op1 ? op1 : gen_rtx_IOR (0, XEXP (old, 1), x);
3190 if (op1 == const1_rtx)
3191 return op0 ? op0 : gen_rtx_IOR (0, XEXP (old, 0), x);
3192 if (op0 == const0_rtx || op1 == const0_rtx)
3193 return const0_rtx;
3194 if (op0 == NULL)
3195 op0 = gen_rtx_IOR (0, XEXP (old, 0), x);
3196 else if (rtx_equal_p (x, op0))
3197 /* (x & A) | x ~ x. */
3198 return op0;
3199 if (op1 == NULL)
3200 op1 = gen_rtx_IOR (0, XEXP (old, 1), x);
3201 else if (rtx_equal_p (x, op1))
3202 /* (A & x) | x ~ x. */
3203 return op1;
3204 return gen_rtx_AND (0, op0, op1);
3206 if (! add)
3207 return NULL;
3208 return gen_rtx_IOR (0, old, x);
3210 case NOT:
3211 op0 = and_reg_cond (XEXP (old, 0), not_reg_cond (x), 0);
3212 if (op0 != NULL)
3213 return not_reg_cond (op0);
3214 if (! add)
3215 return NULL;
3216 return gen_rtx_IOR (0, old, x);
3218 default:
3219 gcc_unreachable ();
3223 static rtx
3224 not_reg_cond (rtx x)
3226 if (x == const0_rtx)
3227 return const1_rtx;
3228 else if (x == const1_rtx)
3229 return const0_rtx;
3230 if (GET_CODE (x) == NOT)
3231 return XEXP (x, 0);
3232 if (COMPARISON_P (x)
3233 && REG_P (XEXP (x, 0)))
3235 gcc_assert (XEXP (x, 1) == const0_rtx);
3237 return gen_rtx_fmt_ee (reversed_comparison_code (x, NULL),
3238 VOIDmode, XEXP (x, 0), const0_rtx);
3240 return gen_rtx_NOT (0, x);
3243 static rtx
3244 and_reg_cond (rtx old, rtx x, int add)
3246 rtx op0, op1;
3248 if (COMPARISON_P (old))
3250 if (COMPARISON_P (x)
3251 && GET_CODE (x) == reversed_comparison_code (old, NULL)
3252 && REGNO (XEXP (x, 0)) == REGNO (XEXP (old, 0)))
3253 return const0_rtx;
3254 if (GET_CODE (x) == GET_CODE (old)
3255 && REGNO (XEXP (x, 0)) == REGNO (XEXP (old, 0)))
3256 return old;
3257 if (! add)
3258 return NULL;
3259 return gen_rtx_AND (0, old, x);
3262 switch (GET_CODE (old))
3264 case IOR:
3265 op0 = and_reg_cond (XEXP (old, 0), x, 0);
3266 op1 = and_reg_cond (XEXP (old, 1), x, 0);
3267 if (op0 != NULL || op1 != NULL)
3269 if (op0 == const0_rtx)
3270 return op1 ? op1 : gen_rtx_AND (0, XEXP (old, 1), x);
3271 if (op1 == const0_rtx)
3272 return op0 ? op0 : gen_rtx_AND (0, XEXP (old, 0), x);
3273 if (op0 == const1_rtx || op1 == const1_rtx)
3274 return const1_rtx;
3275 if (op0 == NULL)
3276 op0 = gen_rtx_AND (0, XEXP (old, 0), x);
3277 else if (rtx_equal_p (x, op0))
3278 /* (x | A) & x ~ x. */
3279 return op0;
3280 if (op1 == NULL)
3281 op1 = gen_rtx_AND (0, XEXP (old, 1), x);
3282 else if (rtx_equal_p (x, op1))
3283 /* (A | x) & x ~ x. */
3284 return op1;
3285 return gen_rtx_IOR (0, op0, op1);
3287 if (! add)
3288 return NULL;
3289 return gen_rtx_AND (0, old, x);
3291 case AND:
3292 op0 = and_reg_cond (XEXP (old, 0), x, 0);
3293 op1 = and_reg_cond (XEXP (old, 1), x, 0);
3294 if (op0 != NULL || op1 != NULL)
3296 if (op0 == const1_rtx)
3297 return op1 ? op1 : gen_rtx_AND (0, XEXP (old, 1), x);
3298 if (op1 == const1_rtx)
3299 return op0 ? op0 : gen_rtx_AND (0, XEXP (old, 0), x);
3300 if (op0 == const0_rtx || op1 == const0_rtx)
3301 return const0_rtx;
3302 if (op0 == NULL)
3303 op0 = gen_rtx_AND (0, XEXP (old, 0), x);
3304 else if (rtx_equal_p (x, op0))
3305 /* (x & A) & x ~ (x & A). */
3306 return old;
3307 if (op1 == NULL)
3308 op1 = gen_rtx_AND (0, XEXP (old, 1), x);
3309 else if (rtx_equal_p (x, op1))
3310 /* (A & x) & x ~ (A & x). */
3311 return old;
3312 return gen_rtx_AND (0, op0, op1);
3314 if (! add)
3315 return NULL;
3316 return gen_rtx_AND (0, old, x);
3318 case NOT:
3319 op0 = ior_reg_cond (XEXP (old, 0), not_reg_cond (x), 0);
3320 if (op0 != NULL)
3321 return not_reg_cond (op0);
3322 if (! add)
3323 return NULL;
3324 return gen_rtx_AND (0, old, x);
3326 default:
3327 gcc_unreachable ();
3331 /* Given a condition X, remove references to reg REGNO and return the
3332 new condition. The removal will be done so that all conditions
3333 involving REGNO are considered to evaluate to false. This function
3334 is used when the value of REGNO changes. */
3336 static rtx
3337 elim_reg_cond (rtx x, unsigned int regno)
3339 rtx op0, op1;
3341 if (COMPARISON_P (x))
3343 if (REGNO (XEXP (x, 0)) == regno)
3344 return const0_rtx;
3345 return x;
3348 switch (GET_CODE (x))
3350 case AND:
3351 op0 = elim_reg_cond (XEXP (x, 0), regno);
3352 op1 = elim_reg_cond (XEXP (x, 1), regno);
3353 if (op0 == const0_rtx || op1 == const0_rtx)
3354 return const0_rtx;
3355 if (op0 == const1_rtx)
3356 return op1;
3357 if (op1 == const1_rtx)
3358 return op0;
3359 if (op0 == XEXP (x, 0) && op1 == XEXP (x, 1))
3360 return x;
3361 return gen_rtx_AND (0, op0, op1);
3363 case IOR:
3364 op0 = elim_reg_cond (XEXP (x, 0), regno);
3365 op1 = elim_reg_cond (XEXP (x, 1), regno);
3366 if (op0 == const1_rtx || op1 == const1_rtx)
3367 return const1_rtx;
3368 if (op0 == const0_rtx)
3369 return op1;
3370 if (op1 == const0_rtx)
3371 return op0;
3372 if (op0 == XEXP (x, 0) && op1 == XEXP (x, 1))
3373 return x;
3374 return gen_rtx_IOR (0, op0, op1);
3376 case NOT:
3377 op0 = elim_reg_cond (XEXP (x, 0), regno);
3378 if (op0 == const0_rtx)
3379 return const1_rtx;
3380 if (op0 == const1_rtx)
3381 return const0_rtx;
3382 if (op0 != XEXP (x, 0))
3383 return not_reg_cond (op0);
3384 return x;
3386 default:
3387 gcc_unreachable ();
3390 #endif /* HAVE_conditional_execution */
3392 #ifdef AUTO_INC_DEC
3394 /* Try to substitute the auto-inc expression INC as the address inside
3395 MEM which occurs in INSN. Currently, the address of MEM is an expression
3396 involving INCR_REG, and INCR is the next use of INCR_REG; it is an insn
3397 that has a single set whose source is a PLUS of INCR_REG and something
3398 else. */
3400 static void
3401 attempt_auto_inc (struct propagate_block_info *pbi, rtx inc, rtx insn,
3402 rtx mem, rtx incr, rtx incr_reg)
3404 int regno = REGNO (incr_reg);
3405 rtx set = single_set (incr);
3406 rtx q = SET_DEST (set);
3407 rtx y = SET_SRC (set);
3408 int opnum = XEXP (y, 0) == incr_reg ? 0 : 1;
3409 int changed;
3411 /* Make sure this reg appears only once in this insn. */
3412 if (count_occurrences (PATTERN (insn), incr_reg, 1) != 1)
3413 return;
3415 if (dead_or_set_p (incr, incr_reg)
3416 /* Mustn't autoinc an eliminable register. */
3417 && (regno >= FIRST_PSEUDO_REGISTER
3418 || ! TEST_HARD_REG_BIT (elim_reg_set, regno)))
3420 /* This is the simple case. Try to make the auto-inc. If
3421 we can't, we are done. Otherwise, we will do any
3422 needed updates below. */
3423 if (! validate_change (insn, &XEXP (mem, 0), inc, 0))
3424 return;
3426 else if (REG_P (q)
3427 /* PREV_INSN used here to check the semi-open interval
3428 [insn,incr). */
3429 && ! reg_used_between_p (q, PREV_INSN (insn), incr)
3430 /* We must also check for sets of q as q may be
3431 a call clobbered hard register and there may
3432 be a call between PREV_INSN (insn) and incr. */
3433 && ! reg_set_between_p (q, PREV_INSN (insn), incr))
3435 /* We have *p followed sometime later by q = p+size.
3436 Both p and q must be live afterward,
3437 and q is not used between INSN and its assignment.
3438 Change it to q = p, ...*q..., q = q+size.
3439 Then fall into the usual case. */
3440 rtx insns, temp;
3442 start_sequence ();
3443 emit_move_insn (q, incr_reg);
3444 insns = get_insns ();
3445 end_sequence ();
3447 /* If we can't make the auto-inc, or can't make the
3448 replacement into Y, exit. There's no point in making
3449 the change below if we can't do the auto-inc and doing
3450 so is not correct in the pre-inc case. */
3452 XEXP (inc, 0) = q;
3453 validate_change (insn, &XEXP (mem, 0), inc, 1);
3454 validate_change (incr, &XEXP (y, opnum), q, 1);
3455 if (! apply_change_group ())
3456 return;
3458 /* We now know we'll be doing this change, so emit the
3459 new insn(s) and do the updates. */
3460 emit_insn_before (insns, insn);
3462 if (BB_HEAD (pbi->bb) == insn)
3463 BB_HEAD (pbi->bb) = insns;
3465 /* INCR will become a NOTE and INSN won't contain a
3466 use of INCR_REG. If a use of INCR_REG was just placed in
3467 the insn before INSN, make that the next use.
3468 Otherwise, invalidate it. */
3469 if (NONJUMP_INSN_P (PREV_INSN (insn))
3470 && GET_CODE (PATTERN (PREV_INSN (insn))) == SET
3471 && SET_SRC (PATTERN (PREV_INSN (insn))) == incr_reg)
3472 pbi->reg_next_use[regno] = PREV_INSN (insn);
3473 else
3474 pbi->reg_next_use[regno] = 0;
3476 incr_reg = q;
3477 regno = REGNO (q);
3479 if ((pbi->flags & PROP_REG_INFO)
3480 && !REGNO_REG_SET_P (pbi->reg_live, regno))
3481 reg_deaths[regno] = pbi->insn_num;
3483 /* REGNO is now used in INCR which is below INSN, but
3484 it previously wasn't live here. If we don't mark
3485 it as live, we'll put a REG_DEAD note for it
3486 on this insn, which is incorrect. */
3487 SET_REGNO_REG_SET (pbi->reg_live, regno);
3489 /* If there are any calls between INSN and INCR, show
3490 that REGNO now crosses them. */
3491 for (temp = insn; temp != incr; temp = NEXT_INSN (temp))
3492 if (CALL_P (temp))
3493 REG_N_CALLS_CROSSED (regno)++;
3495 /* Invalidate alias info for Q since we just changed its value. */
3496 clear_reg_alias_info (q);
3498 else
3499 return;
3501 /* If we haven't returned, it means we were able to make the
3502 auto-inc, so update the status. First, record that this insn
3503 has an implicit side effect. */
3505 REG_NOTES (insn) = alloc_EXPR_LIST (REG_INC, incr_reg, REG_NOTES (insn));
3507 /* Modify the old increment-insn to simply copy
3508 the already-incremented value of our register. */
3509 changed = validate_change (incr, &SET_SRC (set), incr_reg, 0);
3510 gcc_assert (changed);
3512 /* If that makes it a no-op (copying the register into itself) delete
3513 it so it won't appear to be a "use" and a "set" of this
3514 register. */
3515 if (REGNO (SET_DEST (set)) == REGNO (incr_reg))
3517 /* If the original source was dead, it's dead now. */
3518 rtx note;
3520 while ((note = find_reg_note (incr, REG_DEAD, NULL_RTX)) != NULL_RTX)
3522 remove_note (incr, note);
3523 if (XEXP (note, 0) != incr_reg)
3525 unsigned int regno = REGNO (XEXP (note, 0));
3527 if ((pbi->flags & PROP_REG_INFO)
3528 && REGNO_REG_SET_P (pbi->reg_live, regno))
3530 REG_LIVE_LENGTH (regno) += pbi->insn_num - reg_deaths[regno];
3531 reg_deaths[regno] = 0;
3533 CLEAR_REGNO_REG_SET (pbi->reg_live, REGNO (XEXP (note, 0)));
3537 SET_INSN_DELETED (incr);
3540 if (regno >= FIRST_PSEUDO_REGISTER)
3542 /* Count an extra reference to the reg. When a reg is
3543 incremented, spilling it is worse, so we want to make
3544 that less likely. */
3545 REG_FREQ (regno) += REG_FREQ_FROM_BB (pbi->bb);
3547 /* Count the increment as a setting of the register,
3548 even though it isn't a SET in rtl. */
3549 REG_N_SETS (regno)++;
3553 /* X is a MEM found in INSN. See if we can convert it into an auto-increment
3554 reference. */
3556 static void
3557 find_auto_inc (struct propagate_block_info *pbi, rtx x, rtx insn)
3559 rtx addr = XEXP (x, 0);
3560 HOST_WIDE_INT offset = 0;
3561 rtx set, y, incr, inc_val;
3562 int regno;
3563 int size = GET_MODE_SIZE (GET_MODE (x));
3565 if (JUMP_P (insn))
3566 return;
3568 /* Here we detect use of an index register which might be good for
3569 postincrement, postdecrement, preincrement, or predecrement. */
3571 if (GET_CODE (addr) == PLUS && GET_CODE (XEXP (addr, 1)) == CONST_INT)
3572 offset = INTVAL (XEXP (addr, 1)), addr = XEXP (addr, 0);
3574 if (!REG_P (addr))
3575 return;
3577 regno = REGNO (addr);
3579 /* Is the next use an increment that might make auto-increment? */
3580 incr = pbi->reg_next_use[regno];
3581 if (incr == 0 || BLOCK_NUM (incr) != BLOCK_NUM (insn))
3582 return;
3583 set = single_set (incr);
3584 if (set == 0 || GET_CODE (set) != SET)
3585 return;
3586 y = SET_SRC (set);
3588 if (GET_CODE (y) != PLUS)
3589 return;
3591 if (REG_P (XEXP (y, 0)) && REGNO (XEXP (y, 0)) == REGNO (addr))
3592 inc_val = XEXP (y, 1);
3593 else if (REG_P (XEXP (y, 1)) && REGNO (XEXP (y, 1)) == REGNO (addr))
3594 inc_val = XEXP (y, 0);
3595 else
3596 return;
3598 if (GET_CODE (inc_val) == CONST_INT)
3600 if (HAVE_POST_INCREMENT
3601 && (INTVAL (inc_val) == size && offset == 0))
3602 attempt_auto_inc (pbi, gen_rtx_POST_INC (Pmode, addr), insn, x,
3603 incr, addr);
3604 else if (HAVE_POST_DECREMENT
3605 && (INTVAL (inc_val) == -size && offset == 0))
3606 attempt_auto_inc (pbi, gen_rtx_POST_DEC (Pmode, addr), insn, x,
3607 incr, addr);
3608 else if (HAVE_PRE_INCREMENT
3609 && (INTVAL (inc_val) == size && offset == size))
3610 attempt_auto_inc (pbi, gen_rtx_PRE_INC (Pmode, addr), insn, x,
3611 incr, addr);
3612 else if (HAVE_PRE_DECREMENT
3613 && (INTVAL (inc_val) == -size && offset == -size))
3614 attempt_auto_inc (pbi, gen_rtx_PRE_DEC (Pmode, addr), insn, x,
3615 incr, addr);
3616 else if (HAVE_POST_MODIFY_DISP && offset == 0)
3617 attempt_auto_inc (pbi, gen_rtx_POST_MODIFY (Pmode, addr,
3618 gen_rtx_PLUS (Pmode,
3619 addr,
3620 inc_val)),
3621 insn, x, incr, addr);
3622 else if (HAVE_PRE_MODIFY_DISP && offset == INTVAL (inc_val))
3623 attempt_auto_inc (pbi, gen_rtx_PRE_MODIFY (Pmode, addr,
3624 gen_rtx_PLUS (Pmode,
3625 addr,
3626 inc_val)),
3627 insn, x, incr, addr);
3629 else if (REG_P (inc_val)
3630 && ! reg_set_between_p (inc_val, PREV_INSN (insn),
3631 NEXT_INSN (incr)))
3634 if (HAVE_POST_MODIFY_REG && offset == 0)
3635 attempt_auto_inc (pbi, gen_rtx_POST_MODIFY (Pmode, addr,
3636 gen_rtx_PLUS (Pmode,
3637 addr,
3638 inc_val)),
3639 insn, x, incr, addr);
3643 #endif /* AUTO_INC_DEC */
3645 static void
3646 mark_used_reg (struct propagate_block_info *pbi, rtx reg,
3647 rtx cond ATTRIBUTE_UNUSED, rtx insn)
3649 unsigned int regno_first, regno_last, i;
3650 int some_was_live, some_was_dead, some_not_set;
3652 regno_last = regno_first = REGNO (reg);
3653 if (regno_first < FIRST_PSEUDO_REGISTER)
3654 regno_last += hard_regno_nregs[regno_first][GET_MODE (reg)] - 1;
3656 /* Find out if any of this register is live after this instruction. */
3657 some_was_live = some_was_dead = 0;
3658 for (i = regno_first; i <= regno_last; ++i)
3660 int needed_regno = REGNO_REG_SET_P (pbi->reg_live, i);
3661 some_was_live |= needed_regno;
3662 some_was_dead |= ! needed_regno;
3665 /* Find out if any of the register was set this insn. */
3666 some_not_set = 0;
3667 for (i = regno_first; i <= regno_last; ++i)
3668 some_not_set |= ! REGNO_REG_SET_P (pbi->new_set, i);
3670 if (pbi->flags & (PROP_LOG_LINKS | PROP_AUTOINC))
3672 /* Record where each reg is used, so when the reg is set we know
3673 the next insn that uses it. */
3674 pbi->reg_next_use[regno_first] = insn;
3677 if (pbi->flags & PROP_REG_INFO)
3679 if (regno_first < FIRST_PSEUDO_REGISTER)
3681 /* If this is a register we are going to try to eliminate,
3682 don't mark it live here. If we are successful in
3683 eliminating it, it need not be live unless it is used for
3684 pseudos, in which case it will have been set live when it
3685 was allocated to the pseudos. If the register will not
3686 be eliminated, reload will set it live at that point.
3688 Otherwise, record that this function uses this register. */
3689 /* ??? The PPC backend tries to "eliminate" on the pic
3690 register to itself. This should be fixed. In the mean
3691 time, hack around it. */
3693 if (! (TEST_HARD_REG_BIT (elim_reg_set, regno_first)
3694 && (regno_first == FRAME_POINTER_REGNUM
3695 || regno_first == ARG_POINTER_REGNUM)))
3696 for (i = regno_first; i <= regno_last; ++i)
3697 regs_ever_live[i] = 1;
3699 else
3701 /* Keep track of which basic block each reg appears in. */
3703 int blocknum = pbi->bb->index;
3704 if (REG_BASIC_BLOCK (regno_first) == REG_BLOCK_UNKNOWN)
3705 REG_BASIC_BLOCK (regno_first) = blocknum;
3706 else if (REG_BASIC_BLOCK (regno_first) != blocknum)
3707 REG_BASIC_BLOCK (regno_first) = REG_BLOCK_GLOBAL;
3709 /* Count (weighted) number of uses of each reg. */
3710 REG_FREQ (regno_first) += REG_FREQ_FROM_BB (pbi->bb);
3711 REG_N_REFS (regno_first)++;
3713 for (i = regno_first; i <= regno_last; ++i)
3714 if (! REGNO_REG_SET_P (pbi->reg_live, i))
3716 gcc_assert (!reg_deaths[i]);
3717 reg_deaths[i] = pbi->insn_num;
3721 /* Record and count the insns in which a reg dies. If it is used in
3722 this insn and was dead below the insn then it dies in this insn.
3723 If it was set in this insn, we do not make a REG_DEAD note;
3724 likewise if we already made such a note. */
3725 if ((pbi->flags & (PROP_DEATH_NOTES | PROP_REG_INFO))
3726 && some_was_dead
3727 && some_not_set)
3729 /* Check for the case where the register dying partially
3730 overlaps the register set by this insn. */
3731 if (regno_first != regno_last)
3732 for (i = regno_first; i <= regno_last; ++i)
3733 some_was_live |= REGNO_REG_SET_P (pbi->new_set, i);
3735 /* If none of the words in X is needed, make a REG_DEAD note.
3736 Otherwise, we must make partial REG_DEAD notes. */
3737 if (! some_was_live)
3739 if ((pbi->flags & PROP_DEATH_NOTES)
3740 && ! find_regno_note (insn, REG_DEAD, regno_first))
3741 REG_NOTES (insn)
3742 = alloc_EXPR_LIST (REG_DEAD, reg, REG_NOTES (insn));
3744 if (pbi->flags & PROP_REG_INFO)
3745 REG_N_DEATHS (regno_first)++;
3747 else
3749 /* Don't make a REG_DEAD note for a part of a register
3750 that is set in the insn. */
3751 for (i = regno_first; i <= regno_last; ++i)
3752 if (! REGNO_REG_SET_P (pbi->reg_live, i)
3753 && ! dead_or_set_regno_p (insn, i))
3754 REG_NOTES (insn)
3755 = alloc_EXPR_LIST (REG_DEAD,
3756 regno_reg_rtx[i],
3757 REG_NOTES (insn));
3761 /* Mark the register as being live. */
3762 for (i = regno_first; i <= regno_last; ++i)
3764 #ifdef HAVE_conditional_execution
3765 int this_was_live = REGNO_REG_SET_P (pbi->reg_live, i);
3766 #endif
3768 SET_REGNO_REG_SET (pbi->reg_live, i);
3770 #ifdef HAVE_conditional_execution
3771 /* If this is a conditional use, record that fact. If it is later
3772 conditionally set, we'll know to kill the register. */
3773 if (cond != NULL_RTX)
3775 splay_tree_node node;
3776 struct reg_cond_life_info *rcli;
3777 rtx ncond;
3779 if (this_was_live)
3781 node = splay_tree_lookup (pbi->reg_cond_dead, i);
3782 if (node == NULL)
3784 /* The register was unconditionally live previously.
3785 No need to do anything. */
3787 else
3789 /* The register was conditionally live previously.
3790 Subtract the new life cond from the old death cond. */
3791 rcli = (struct reg_cond_life_info *) node->value;
3792 ncond = rcli->condition;
3793 ncond = and_reg_cond (ncond, not_reg_cond (cond), 1);
3795 /* If the register is now unconditionally live,
3796 remove the entry in the splay_tree. */
3797 if (ncond == const0_rtx)
3798 splay_tree_remove (pbi->reg_cond_dead, i);
3799 else
3801 rcli->condition = ncond;
3802 SET_REGNO_REG_SET (pbi->reg_cond_reg,
3803 REGNO (XEXP (cond, 0)));
3807 else
3809 /* The register was not previously live at all. Record
3810 the condition under which it is still dead. */
3811 rcli = xmalloc (sizeof (*rcli));
3812 rcli->condition = not_reg_cond (cond);
3813 rcli->stores = const0_rtx;
3814 rcli->orig_condition = const0_rtx;
3815 splay_tree_insert (pbi->reg_cond_dead, i,
3816 (splay_tree_value) rcli);
3818 SET_REGNO_REG_SET (pbi->reg_cond_reg, REGNO (XEXP (cond, 0)));
3821 else if (this_was_live)
3823 /* The register may have been conditionally live previously, but
3824 is now unconditionally live. Remove it from the conditionally
3825 dead list, so that a conditional set won't cause us to think
3826 it dead. */
3827 splay_tree_remove (pbi->reg_cond_dead, i);
3829 #endif
3833 /* Scan expression X and store a 1-bit in NEW_LIVE for each reg it uses.
3834 This is done assuming the registers needed from X are those that
3835 have 1-bits in PBI->REG_LIVE.
3837 INSN is the containing instruction. If INSN is dead, this function
3838 is not called. */
3840 static void
3841 mark_used_regs (struct propagate_block_info *pbi, rtx x, rtx cond, rtx insn)
3843 RTX_CODE code;
3844 int regno;
3845 int flags = pbi->flags;
3847 retry:
3848 if (!x)
3849 return;
3850 code = GET_CODE (x);
3851 switch (code)
3853 case LABEL_REF:
3854 case SYMBOL_REF:
3855 case CONST_INT:
3856 case CONST:
3857 case CONST_DOUBLE:
3858 case CONST_VECTOR:
3859 case PC:
3860 case ADDR_VEC:
3861 case ADDR_DIFF_VEC:
3862 return;
3864 #ifdef HAVE_cc0
3865 case CC0:
3866 pbi->cc0_live = 1;
3867 return;
3868 #endif
3870 case CLOBBER:
3871 /* If we are clobbering a MEM, mark any registers inside the address
3872 as being used. */
3873 if (MEM_P (XEXP (x, 0)))
3874 mark_used_regs (pbi, XEXP (XEXP (x, 0), 0), cond, insn);
3875 return;
3877 case MEM:
3878 /* Don't bother watching stores to mems if this is not the
3879 final pass. We'll not be deleting dead stores this round. */
3880 if (optimize && (flags & PROP_SCAN_DEAD_STORES))
3882 /* Invalidate the data for the last MEM stored, but only if MEM is
3883 something that can be stored into. */
3884 if (GET_CODE (XEXP (x, 0)) == SYMBOL_REF
3885 && CONSTANT_POOL_ADDRESS_P (XEXP (x, 0)))
3886 /* Needn't clear the memory set list. */
3888 else
3890 rtx temp = pbi->mem_set_list;
3891 rtx prev = NULL_RTX;
3892 rtx next;
3894 while (temp)
3896 next = XEXP (temp, 1);
3897 if (anti_dependence (XEXP (temp, 0), x))
3899 /* Splice temp out of the list. */
3900 if (prev)
3901 XEXP (prev, 1) = next;
3902 else
3903 pbi->mem_set_list = next;
3904 free_EXPR_LIST_node (temp);
3905 pbi->mem_set_list_len--;
3907 else
3908 prev = temp;
3909 temp = next;
3913 /* If the memory reference had embedded side effects (autoincrement
3914 address modes. Then we may need to kill some entries on the
3915 memory set list. */
3916 if (insn)
3917 for_each_rtx (&PATTERN (insn), invalidate_mems_from_autoinc, pbi);
3920 #ifdef AUTO_INC_DEC
3921 if (flags & PROP_AUTOINC)
3922 find_auto_inc (pbi, x, insn);
3923 #endif
3924 break;
3926 case SUBREG:
3927 #ifdef CANNOT_CHANGE_MODE_CLASS
3928 if (flags & PROP_REG_INFO)
3929 record_subregs_of_mode (x);
3930 #endif
3932 /* While we're here, optimize this case. */
3933 x = SUBREG_REG (x);
3934 if (!REG_P (x))
3935 goto retry;
3936 /* Fall through. */
3938 case REG:
3939 /* See a register other than being set => mark it as needed. */
3940 mark_used_reg (pbi, x, cond, insn);
3941 return;
3943 case SET:
3945 rtx testreg = SET_DEST (x);
3946 int mark_dest = 0;
3948 /* If storing into MEM, don't show it as being used. But do
3949 show the address as being used. */
3950 if (MEM_P (testreg))
3952 #ifdef AUTO_INC_DEC
3953 if (flags & PROP_AUTOINC)
3954 find_auto_inc (pbi, testreg, insn);
3955 #endif
3956 mark_used_regs (pbi, XEXP (testreg, 0), cond, insn);
3957 mark_used_regs (pbi, SET_SRC (x), cond, insn);
3958 return;
3961 /* Storing in STRICT_LOW_PART is like storing in a reg
3962 in that this SET might be dead, so ignore it in TESTREG.
3963 but in some other ways it is like using the reg.
3965 Storing in a SUBREG or a bit field is like storing the entire
3966 register in that if the register's value is not used
3967 then this SET is not needed. */
3968 while (GET_CODE (testreg) == STRICT_LOW_PART
3969 || GET_CODE (testreg) == ZERO_EXTRACT
3970 || GET_CODE (testreg) == SUBREG)
3972 #ifdef CANNOT_CHANGE_MODE_CLASS
3973 if ((flags & PROP_REG_INFO) && GET_CODE (testreg) == SUBREG)
3974 record_subregs_of_mode (testreg);
3975 #endif
3977 /* Modifying a single register in an alternate mode
3978 does not use any of the old value. But these other
3979 ways of storing in a register do use the old value. */
3980 if (GET_CODE (testreg) == SUBREG
3981 && !((REG_BYTES (SUBREG_REG (testreg))
3982 + UNITS_PER_WORD - 1) / UNITS_PER_WORD
3983 > (REG_BYTES (testreg)
3984 + UNITS_PER_WORD - 1) / UNITS_PER_WORD))
3986 else
3987 mark_dest = 1;
3989 testreg = XEXP (testreg, 0);
3992 /* If this is a store into a register or group of registers,
3993 recursively scan the value being stored. */
3995 if ((GET_CODE (testreg) == PARALLEL
3996 && GET_MODE (testreg) == BLKmode)
3997 || (REG_P (testreg)
3998 && (regno = REGNO (testreg),
3999 ! (regno == FRAME_POINTER_REGNUM
4000 && (! reload_completed || frame_pointer_needed)))
4001 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
4002 && ! (regno == HARD_FRAME_POINTER_REGNUM
4003 && (! reload_completed || frame_pointer_needed))
4004 #endif
4005 #if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
4006 && ! (regno == ARG_POINTER_REGNUM && fixed_regs[regno])
4007 #endif
4010 if (mark_dest)
4011 mark_used_regs (pbi, SET_DEST (x), cond, insn);
4012 mark_used_regs (pbi, SET_SRC (x), cond, insn);
4013 return;
4016 break;
4018 case ASM_OPERANDS:
4019 case UNSPEC_VOLATILE:
4020 case TRAP_IF:
4021 case ASM_INPUT:
4023 /* Traditional and volatile asm instructions must be considered to use
4024 and clobber all hard registers, all pseudo-registers and all of
4025 memory. So must TRAP_IF and UNSPEC_VOLATILE operations.
4027 Consider for instance a volatile asm that changes the fpu rounding
4028 mode. An insn should not be moved across this even if it only uses
4029 pseudo-regs because it might give an incorrectly rounded result.
4031 ?!? Unfortunately, marking all hard registers as live causes massive
4032 problems for the register allocator and marking all pseudos as live
4033 creates mountains of uninitialized variable warnings.
4035 So for now, just clear the memory set list and mark any regs
4036 we can find in ASM_OPERANDS as used. */
4037 if (code != ASM_OPERANDS || MEM_VOLATILE_P (x))
4039 free_EXPR_LIST_list (&pbi->mem_set_list);
4040 pbi->mem_set_list_len = 0;
4043 /* For all ASM_OPERANDS, we must traverse the vector of input operands.
4044 We can not just fall through here since then we would be confused
4045 by the ASM_INPUT rtx inside ASM_OPERANDS, which do not indicate
4046 traditional asms unlike their normal usage. */
4047 if (code == ASM_OPERANDS)
4049 int j;
4051 for (j = 0; j < ASM_OPERANDS_INPUT_LENGTH (x); j++)
4052 mark_used_regs (pbi, ASM_OPERANDS_INPUT (x, j), cond, insn);
4054 break;
4057 case COND_EXEC:
4058 gcc_assert (!cond);
4060 mark_used_regs (pbi, COND_EXEC_TEST (x), NULL_RTX, insn);
4062 cond = COND_EXEC_TEST (x);
4063 x = COND_EXEC_CODE (x);
4064 goto retry;
4066 default:
4067 break;
4070 /* Recursively scan the operands of this expression. */
4073 const char * const fmt = GET_RTX_FORMAT (code);
4074 int i;
4076 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
4078 if (fmt[i] == 'e')
4080 /* Tail recursive case: save a function call level. */
4081 if (i == 0)
4083 x = XEXP (x, 0);
4084 goto retry;
4086 mark_used_regs (pbi, XEXP (x, i), cond, insn);
4088 else if (fmt[i] == 'E')
4090 int j;
4091 for (j = 0; j < XVECLEN (x, i); j++)
4092 mark_used_regs (pbi, XVECEXP (x, i, j), cond, insn);
4098 #ifdef AUTO_INC_DEC
4100 static int
4101 try_pre_increment_1 (struct propagate_block_info *pbi, rtx insn)
4103 /* Find the next use of this reg. If in same basic block,
4104 make it do pre-increment or pre-decrement if appropriate. */
4105 rtx x = single_set (insn);
4106 HOST_WIDE_INT amount = ((GET_CODE (SET_SRC (x)) == PLUS ? 1 : -1)
4107 * INTVAL (XEXP (SET_SRC (x), 1)));
4108 int regno = REGNO (SET_DEST (x));
4109 rtx y = pbi->reg_next_use[regno];
4110 if (y != 0
4111 && SET_DEST (x) != stack_pointer_rtx
4112 && BLOCK_NUM (y) == BLOCK_NUM (insn)
4113 /* Don't do this if the reg dies, or gets set in y; a standard addressing
4114 mode would be better. */
4115 && ! dead_or_set_p (y, SET_DEST (x))
4116 && try_pre_increment (y, SET_DEST (x), amount))
4118 /* We have found a suitable auto-increment and already changed
4119 insn Y to do it. So flush this increment instruction. */
4120 propagate_block_delete_insn (insn);
4122 /* Count a reference to this reg for the increment insn we are
4123 deleting. When a reg is incremented, spilling it is worse,
4124 so we want to make that less likely. */
4125 if (regno >= FIRST_PSEUDO_REGISTER)
4127 REG_FREQ (regno) += REG_FREQ_FROM_BB (pbi->bb);
4128 REG_N_SETS (regno)++;
4131 /* Flush any remembered memories depending on the value of
4132 the incremented register. */
4133 invalidate_mems_from_set (pbi, SET_DEST (x));
4135 return 1;
4137 return 0;
4140 /* Try to change INSN so that it does pre-increment or pre-decrement
4141 addressing on register REG in order to add AMOUNT to REG.
4142 AMOUNT is negative for pre-decrement.
4143 Returns 1 if the change could be made.
4144 This checks all about the validity of the result of modifying INSN. */
4146 static int
4147 try_pre_increment (rtx insn, rtx reg, HOST_WIDE_INT amount)
4149 rtx use;
4151 /* Nonzero if we can try to make a pre-increment or pre-decrement.
4152 For example, addl $4,r1; movl (r1),... can become movl +(r1),... */
4153 int pre_ok = 0;
4154 /* Nonzero if we can try to make a post-increment or post-decrement.
4155 For example, addl $4,r1; movl -4(r1),... can become movl (r1)+,...
4156 It is possible for both PRE_OK and POST_OK to be nonzero if the machine
4157 supports both pre-inc and post-inc, or both pre-dec and post-dec. */
4158 int post_ok = 0;
4160 /* Nonzero if the opportunity actually requires post-inc or post-dec. */
4161 int do_post = 0;
4163 /* From the sign of increment, see which possibilities are conceivable
4164 on this target machine. */
4165 if (HAVE_PRE_INCREMENT && amount > 0)
4166 pre_ok = 1;
4167 if (HAVE_POST_INCREMENT && amount > 0)
4168 post_ok = 1;
4170 if (HAVE_PRE_DECREMENT && amount < 0)
4171 pre_ok = 1;
4172 if (HAVE_POST_DECREMENT && amount < 0)
4173 post_ok = 1;
4175 if (! (pre_ok || post_ok))
4176 return 0;
4178 /* It is not safe to add a side effect to a jump insn
4179 because if the incremented register is spilled and must be reloaded
4180 there would be no way to store the incremented value back in memory. */
4182 if (JUMP_P (insn))
4183 return 0;
4185 use = 0;
4186 if (pre_ok)
4187 use = find_use_as_address (PATTERN (insn), reg, 0);
4188 if (post_ok && (use == 0 || use == (rtx) (size_t) 1))
4190 use = find_use_as_address (PATTERN (insn), reg, -amount);
4191 do_post = 1;
4194 if (use == 0 || use == (rtx) (size_t) 1)
4195 return 0;
4197 if (GET_MODE_SIZE (GET_MODE (use)) != (amount > 0 ? amount : - amount))
4198 return 0;
4200 /* See if this combination of instruction and addressing mode exists. */
4201 if (! validate_change (insn, &XEXP (use, 0),
4202 gen_rtx_fmt_e (amount > 0
4203 ? (do_post ? POST_INC : PRE_INC)
4204 : (do_post ? POST_DEC : PRE_DEC),
4205 Pmode, reg), 0))
4206 return 0;
4208 /* Record that this insn now has an implicit side effect on X. */
4209 REG_NOTES (insn) = alloc_EXPR_LIST (REG_INC, reg, REG_NOTES (insn));
4210 return 1;
4213 #endif /* AUTO_INC_DEC */
4215 /* Find the place in the rtx X where REG is used as a memory address.
4216 Return the MEM rtx that so uses it.
4217 If PLUSCONST is nonzero, search instead for a memory address equivalent to
4218 (plus REG (const_int PLUSCONST)).
4220 If such an address does not appear, return 0.
4221 If REG appears more than once, or is used other than in such an address,
4222 return (rtx) 1. */
4225 find_use_as_address (rtx x, rtx reg, HOST_WIDE_INT plusconst)
4227 enum rtx_code code = GET_CODE (x);
4228 const char * const fmt = GET_RTX_FORMAT (code);
4229 int i;
4230 rtx value = 0;
4231 rtx tem;
4233 if (code == MEM && XEXP (x, 0) == reg && plusconst == 0)
4234 return x;
4236 if (code == MEM && GET_CODE (XEXP (x, 0)) == PLUS
4237 && XEXP (XEXP (x, 0), 0) == reg
4238 && GET_CODE (XEXP (XEXP (x, 0), 1)) == CONST_INT
4239 && INTVAL (XEXP (XEXP (x, 0), 1)) == plusconst)
4240 return x;
4242 if (code == SIGN_EXTRACT || code == ZERO_EXTRACT)
4244 /* If REG occurs inside a MEM used in a bit-field reference,
4245 that is unacceptable. */
4246 if (find_use_as_address (XEXP (x, 0), reg, 0) != 0)
4247 return (rtx) (size_t) 1;
4250 if (x == reg)
4251 return (rtx) (size_t) 1;
4253 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
4255 if (fmt[i] == 'e')
4257 tem = find_use_as_address (XEXP (x, i), reg, plusconst);
4258 if (value == 0)
4259 value = tem;
4260 else if (tem != 0)
4261 return (rtx) (size_t) 1;
4263 else if (fmt[i] == 'E')
4265 int j;
4266 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
4268 tem = find_use_as_address (XVECEXP (x, i, j), reg, plusconst);
4269 if (value == 0)
4270 value = tem;
4271 else if (tem != 0)
4272 return (rtx) (size_t) 1;
4277 return value;
4280 /* Write information about registers and basic blocks into FILE.
4281 This is part of making a debugging dump. */
4283 void
4284 dump_regset (regset r, FILE *outf)
4286 unsigned i;
4287 reg_set_iterator rsi;
4289 if (r == NULL)
4291 fputs (" (nil)", outf);
4292 return;
4295 EXECUTE_IF_SET_IN_REG_SET (r, 0, i, rsi)
4297 fprintf (outf, " %d", i);
4298 if (i < FIRST_PSEUDO_REGISTER)
4299 fprintf (outf, " [%s]",
4300 reg_names[i]);
4304 /* Print a human-readable representation of R on the standard error
4305 stream. This function is designed to be used from within the
4306 debugger. */
4308 void
4309 debug_regset (regset r)
4311 dump_regset (r, stderr);
4312 putc ('\n', stderr);
4315 /* Recompute register set/reference counts immediately prior to register
4316 allocation.
4318 This avoids problems with set/reference counts changing to/from values
4319 which have special meanings to the register allocators.
4321 Additionally, the reference counts are the primary component used by the
4322 register allocators to prioritize pseudos for allocation to hard regs.
4323 More accurate reference counts generally lead to better register allocation.
4325 It might be worthwhile to update REG_LIVE_LENGTH, REG_BASIC_BLOCK and
4326 possibly other information which is used by the register allocators. */
4328 void
4329 recompute_reg_usage (void)
4331 allocate_reg_life_data ();
4332 /* distribute_notes in combiner fails to convert some of the REG_UNUSED notes
4333 to REG_DEAD notes. This causes CHECK_DEAD_NOTES in sched1 to abort. To
4334 solve this update the DEATH_NOTES here. */
4335 update_life_info (NULL, UPDATE_LIFE_LOCAL, PROP_REG_INFO | PROP_DEATH_NOTES);
4338 /* Optionally removes all the REG_DEAD and REG_UNUSED notes from a set of
4339 blocks. If BLOCKS is NULL, assume the universal set. Returns a count
4340 of the number of registers that died. */
4343 count_or_remove_death_notes (sbitmap blocks, int kill)
4345 int count = 0;
4346 int i;
4347 basic_block bb;
4349 /* This used to be a loop over all the blocks with a membership test
4350 inside the loop. That can be amazingly expensive on a large CFG
4351 when only a small number of bits are set in BLOCKs (for example,
4352 the calls from the scheduler typically have very few bits set).
4354 For extra credit, someone should convert BLOCKS to a bitmap rather
4355 than an sbitmap. */
4356 if (blocks)
4358 EXECUTE_IF_SET_IN_SBITMAP (blocks, 0, i,
4360 count += count_or_remove_death_notes_bb (BASIC_BLOCK (i), kill);
4363 else
4365 FOR_EACH_BB (bb)
4367 count += count_or_remove_death_notes_bb (bb, kill);
4371 return count;
4374 /* Optionally removes all the REG_DEAD and REG_UNUSED notes from basic
4375 block BB. Returns a count of the number of registers that died. */
4377 static int
4378 count_or_remove_death_notes_bb (basic_block bb, int kill)
4380 int count = 0;
4381 rtx insn;
4383 for (insn = BB_HEAD (bb); ; insn = NEXT_INSN (insn))
4385 if (INSN_P (insn))
4387 rtx *pprev = &REG_NOTES (insn);
4388 rtx link = *pprev;
4390 while (link)
4392 switch (REG_NOTE_KIND (link))
4394 case REG_DEAD:
4395 if (REG_P (XEXP (link, 0)))
4397 rtx reg = XEXP (link, 0);
4398 int n;
4400 if (REGNO (reg) >= FIRST_PSEUDO_REGISTER)
4401 n = 1;
4402 else
4403 n = hard_regno_nregs[REGNO (reg)][GET_MODE (reg)];
4404 count += n;
4407 /* Fall through. */
4409 case REG_UNUSED:
4410 if (kill)
4412 rtx next = XEXP (link, 1);
4413 free_EXPR_LIST_node (link);
4414 *pprev = link = next;
4415 break;
4417 /* Fall through. */
4419 default:
4420 pprev = &XEXP (link, 1);
4421 link = *pprev;
4422 break;
4427 if (insn == BB_END (bb))
4428 break;
4431 return count;
4434 /* Clear LOG_LINKS fields of insns in a selected blocks or whole chain
4435 if blocks is NULL. */
4437 static void
4438 clear_log_links (sbitmap blocks)
4440 rtx insn;
4441 int i;
4443 if (!blocks)
4445 for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
4446 if (INSN_P (insn))
4447 free_INSN_LIST_list (&LOG_LINKS (insn));
4449 else
4450 EXECUTE_IF_SET_IN_SBITMAP (blocks, 0, i,
4452 basic_block bb = BASIC_BLOCK (i);
4454 for (insn = BB_HEAD (bb); insn != NEXT_INSN (BB_END (bb));
4455 insn = NEXT_INSN (insn))
4456 if (INSN_P (insn))
4457 free_INSN_LIST_list (&LOG_LINKS (insn));
4461 /* Given a register bitmap, turn on the bits in a HARD_REG_SET that
4462 correspond to the hard registers, if any, set in that map. This
4463 could be done far more efficiently by having all sorts of special-cases
4464 with moving single words, but probably isn't worth the trouble. */
4466 void
4467 reg_set_to_hard_reg_set (HARD_REG_SET *to, bitmap from)
4469 unsigned i;
4470 bitmap_iterator bi;
4472 EXECUTE_IF_SET_IN_BITMAP (from, 0, i, bi)
4474 if (i >= FIRST_PSEUDO_REGISTER)
4475 return;
4476 SET_HARD_REG_BIT (*to, i);