1 /* Data flow analysis for GNU compiler.
2 Copyright (C) 1987, 1988, 1992 Free Software Foundation, Inc.
4 This file is part of GNU CC.
6 GNU CC is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 2, or (at your option)
11 GNU CC is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
16 You should have received a copy of the GNU General Public License
17 along with GNU CC; see the file COPYING. If not, write to
18 the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA. */
21 /* This file contains the data flow analysis pass of the compiler.
22 It computes data flow information
23 which tells combine_instructions which insns to consider combining
24 and controls register allocation.
26 Additional data flow information that is too bulky to record
27 is generated during the analysis, and is used at that time to
28 create 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
37 into basic blocks. It records the beginnings and ends of the
38 basic blocks in the vectors basic_block_head and basic_block_end,
39 and the number of blocks in n_basic_blocks.
41 find_basic_blocks also finds any unreachable loops
46 life_analysis is called immediately after find_basic_blocks.
47 It uses the basic block information to determine where each
48 hard or pseudo register is live.
50 ** live-register info **
52 The information about where each register is live is in two parts:
53 the REG_NOTES of insns, and the vector basic_block_live_at_start.
55 basic_block_live_at_start has an element for each basic block,
56 and the element is a bit-vector with a bit for each hard or pseudo
57 register. The bit is 1 if the register is live at the beginning
60 Two types of elements can be added to an insn's REG_NOTES.
61 A REG_DEAD note is added to an insn's REG_NOTES for any register
62 that meets both of two conditions: The value in the register is not
63 needed in subsequent insns and the insn does not replace the value in
64 the register (in the case of multi-word hard registers, the value in
65 each register must be replaced by the insn to avoid a REG_DEAD note).
67 In the vast majority of cases, an object in a REG_DEAD note will be
68 used somewhere in the insn. The (rare) exception to this is if an
69 insn uses a multi-word hard register and only some of the registers are
70 needed in subsequent insns. In that case, REG_DEAD notes will be
71 provided for those hard registers that are not subsequently needed.
72 Partial REG_DEAD notes of this type do not occur when an insn sets
73 only some of the hard registers used in such a multi-word operand;
74 omitting REG_DEAD notes for objects stored in an insn is optional and
75 the desire to do so does not justify the complexity of the partial
78 REG_UNUSED notes are added for each register that is set by the insn
79 but is unused subsequently (if every register set by the insn is unused
80 and the insn does not reference memory or have some other side-effect,
81 the insn is deleted instead). If only part of a multi-word hard
82 register is used in a subsequent insn, REG_UNUSED notes are made for
83 the parts that will not be used.
85 To determine which registers are live after any insn, one can
86 start from the beginning of the basic block and scan insns, noting
87 which registers are set by each insn and which die there.
89 ** Other actions of life_analysis **
91 life_analysis sets up the LOG_LINKS fields of insns because the
92 information needed to do so is readily available.
94 life_analysis deletes insns whose only effect is to store a value
97 life_analysis notices cases where a reference to a register as
98 a memory address can be combined with a preceding or following
99 incrementation or decrementation of the register. The separate
100 instruction to increment or decrement is deleted and the address
101 is changed to a POST_INC or similar rtx.
103 Each time an incrementing or decrementing address is created,
104 a REG_INC element is added to the insn's REG_NOTES list.
106 life_analysis fills in certain vectors containing information about
107 register usage: reg_n_refs, reg_n_deaths, reg_n_sets, reg_live_length,
108 reg_n_calls_crosses and reg_basic_block. */
113 #include "basic-block.h"
114 #include "insn-config.h"
116 #include "hard-reg-set.h"
121 #define obstack_chunk_alloc xmalloc
122 #define obstack_chunk_free free
124 /* List of labels that must never be deleted. */
125 extern rtx forced_labels;
127 /* Get the basic block number of an insn.
128 This info should not be expected to remain available
129 after the end of life_analysis. */
131 /* This is the limit of the allocated space in the following two arrays. */
133 static int max_uid_for_flow;
135 #define BLOCK_NUM(INSN) uid_block_number[INSN_UID (INSN)]
137 /* This is where the BLOCK_NUM values are really stored.
138 This is set up by find_basic_blocks and used there and in life_analysis,
141 static int *uid_block_number;
143 /* INSN_VOLATILE (insn) is 1 if the insn refers to anything volatile. */
145 #define INSN_VOLATILE(INSN) uid_volatile[INSN_UID (INSN)]
146 static char *uid_volatile;
148 /* Number of basic blocks in the current function. */
152 /* Maximum register number used in this function, plus one. */
156 /* Maximum number of SCRATCH rtx's used in any basic block of this function. */
160 /* Number of SCRATCH rtx's in the current block. */
162 static int num_scratch;
164 /* Indexed by n, gives number of basic block that (REG n) is used in.
165 If the value is REG_BLOCK_GLOBAL (-2),
166 it means (REG n) is used in more than one basic block.
167 REG_BLOCK_UNKNOWN (-1) means it hasn't been seen yet so we don't know.
168 This information remains valid for the rest of the compilation
169 of the current function; it is used to control register allocation. */
171 int *reg_basic_block;
173 /* Indexed by n, gives number of times (REG n) is used or set, each
174 weighted by its loop-depth.
175 This information remains valid for the rest of the compilation
176 of the current function; it is used to control register allocation. */
180 /* Indexed by N, gives number of places register N dies.
181 This information remains valid for the rest of the compilation
182 of the current function; it is used to control register allocation. */
186 /* Indexed by N, gives 1 if that reg is live across any CALL_INSNs.
187 This information remains valid for the rest of the compilation
188 of the current function; it is used to control register allocation. */
190 int *reg_n_calls_crossed;
192 /* Total number of instructions at which (REG n) is live.
193 The larger this is, the less priority (REG n) gets for
194 allocation in a real register.
195 This information remains valid for the rest of the compilation
196 of the current function; it is used to control register allocation.
198 local-alloc.c may alter this number to change the priority.
200 Negative values are special.
201 -1 is used to mark a pseudo reg which has a constant or memory equivalent
202 and is used infrequently enough that it should not get a hard register.
203 -2 is used to mark a pseudo reg for a parameter, when a frame pointer
204 is not required. global.c makes an allocno for this but does
205 not try to assign a hard register to it. */
207 int *reg_live_length;
209 /* Element N is the next insn that uses (hard or pseudo) register number N
210 within the current basic block; or zero, if there is no such insn.
211 This is valid only during the final backward scan in propagate_block. */
213 static rtx *reg_next_use;
215 /* Size of a regset for the current function,
216 in (1) bytes and (2) elements. */
221 /* Element N is first insn in basic block N.
222 This info lasts until we finish compiling the function. */
224 rtx *basic_block_head;
226 /* Element N is last insn in basic block N.
227 This info lasts until we finish compiling the function. */
229 rtx *basic_block_end;
231 /* Element N is a regset describing the registers live
232 at the start of basic block N.
233 This info lasts until we finish compiling the function. */
235 regset *basic_block_live_at_start;
237 /* Regset of regs live when calls to `setjmp'-like functions happen. */
239 regset regs_live_at_setjmp;
241 /* List made of EXPR_LIST rtx's which gives pairs of pseudo registers
242 that have to go in the same hard reg.
243 The first two regs in the list are a pair, and the next two
244 are another pair, etc. */
247 /* Element N is nonzero if control can drop into basic block N
248 from the preceding basic block. Freed after life_analysis. */
250 static char *basic_block_drops_in;
252 /* Element N is depth within loops of the last insn in basic block number N.
253 Freed after life_analysis. */
255 static short *basic_block_loop_depth;
257 /* Element N nonzero if basic block N can actually be reached.
258 Vector exists only during find_basic_blocks. */
260 static char *block_live_static;
262 /* Depth within loops of basic block being scanned for lifetime analysis,
263 plus one. This is the weight attached to references to registers. */
265 static int loop_depth;
267 /* During propagate_block, this is non-zero if the value of CC0 is live. */
271 /* During propagate_block, this contains the last MEM stored into. It
272 is used to eliminate consecutive stores to the same location. */
274 static rtx last_mem_set;
276 /* Set of registers that may be eliminable. These are handled specially
277 in updating regs_ever_live. */
279 static HARD_REG_SET elim_reg_set;
281 /* Forward declarations */
282 static void find_basic_blocks ();
283 static void life_analysis ();
284 static void mark_label_ref ();
285 void allocate_for_life_analysis (); /* Used also in stupid_life_analysis */
286 static void init_regset_vector ();
287 static void propagate_block ();
288 static void mark_set_regs ();
289 static void mark_used_regs ();
290 static int insn_dead_p ();
291 static int libcall_dead_p ();
292 static int try_pre_increment ();
293 static int try_pre_increment_1 ();
294 static rtx find_use_as_address ();
295 void dump_flow_info ();
297 /* Find basic blocks of the current function and perform data flow analysis.
298 F is the first insn of the function and NREGS the number of register numbers
302 flow_analysis (f, nregs, file)
309 rtx nonlocal_label_list = nonlocal_label_rtx_list ();
311 #ifdef ELIMINABLE_REGS
312 static struct {int from, to; } eliminables[] = ELIMINABLE_REGS;
315 /* Record which registers will be eliminated. We use this in
318 CLEAR_HARD_REG_SET (elim_reg_set);
320 #ifdef ELIMINABLE_REGS
321 for (i = 0; i < sizeof eliminables / sizeof eliminables[0]; i++)
322 SET_HARD_REG_BIT (elim_reg_set, eliminables[i].from);
324 SET_HARD_REG_BIT (elim_reg_set, FRAME_POINTER_REGNUM);
327 /* Count the basic blocks. Also find maximum insn uid value used. */
330 register RTX_CODE prev_code = JUMP_INSN;
331 register RTX_CODE code;
333 max_uid_for_flow = 0;
335 for (insn = f, i = 0; insn; insn = NEXT_INSN (insn))
337 code = GET_CODE (insn);
338 if (INSN_UID (insn) > max_uid_for_flow)
339 max_uid_for_flow = INSN_UID (insn);
340 if (code == CODE_LABEL
341 || (GET_RTX_CLASS (code) == 'i'
342 && (prev_code == JUMP_INSN
343 || (prev_code == CALL_INSN
344 && nonlocal_label_list != 0
345 /* Ignore a CLOBBER after a CALL_INSN here. */
347 && GET_CODE (PATTERN (insn)) == CLOBBER))
348 || prev_code == BARRIER)))
351 /* Skip a CLOBBER after a CALL_INSN. See similar code in
352 find_basic_blocks. */
353 && ! (prev_code == CALL_INSN
354 && code == INSN && GET_CODE (PATTERN (insn)) == CLOBBER))
360 /* Leave space for insns we make in some cases for auto-inc. These cases
361 are rare, so we don't need too much space. */
362 max_uid_for_flow += max_uid_for_flow / 10;
365 /* Allocate some tables that last till end of compiling this function
366 and some needed only in find_basic_blocks and life_analysis. */
369 basic_block_head = (rtx *) oballoc (n_basic_blocks * sizeof (rtx));
370 basic_block_end = (rtx *) oballoc (n_basic_blocks * sizeof (rtx));
371 basic_block_drops_in = (char *) alloca (n_basic_blocks);
372 basic_block_loop_depth = (short *) alloca (n_basic_blocks * sizeof (short));
374 = (int *) alloca ((max_uid_for_flow + 1) * sizeof (int));
375 uid_volatile = (char *) alloca (max_uid_for_flow + 1);
376 bzero (uid_volatile, max_uid_for_flow + 1);
378 find_basic_blocks (f, nonlocal_label_list);
379 life_analysis (f, nregs);
381 dump_flow_info (file);
383 basic_block_drops_in = 0;
384 uid_block_number = 0;
385 basic_block_loop_depth = 0;
388 /* Find all basic blocks of the function whose first insn is F.
389 Store the correct data in the tables that describe the basic blocks,
390 set up the chains of references for each CODE_LABEL, and
391 delete any entire basic blocks that cannot be reached.
393 NONLOCAL_LABEL_LIST is the same local variable from flow_analysis. */
396 find_basic_blocks (f, nonlocal_label_list)
397 rtx f, nonlocal_label_list;
401 register char *block_live = (char *) alloca (n_basic_blocks);
402 register char *block_marked = (char *) alloca (n_basic_blocks);
403 /* List of label_refs to all labels whose addresses are taken
405 rtx label_value_list = 0;
407 block_live_static = block_live;
408 bzero (block_live, n_basic_blocks);
409 bzero (block_marked, n_basic_blocks);
411 /* Initialize with just block 0 reachable and no blocks marked. */
412 if (n_basic_blocks > 0)
415 /* Initialize the ref chain of each label to 0. */
416 /* Record where all the blocks start and end and their depth in loops. */
417 /* For each insn, record the block it is in. */
418 /* Also mark as reachable any blocks headed by labels that
419 must not be deleted. */
422 register RTX_CODE prev_code = JUMP_INSN;
423 register RTX_CODE code;
426 for (insn = f, i = -1; insn; insn = NEXT_INSN (insn))
428 code = GET_CODE (insn);
431 if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG)
433 else if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END)
436 /* A basic block starts at label, or after something that can jump. */
437 else if (code == CODE_LABEL
438 || (GET_RTX_CLASS (code) == 'i'
439 && (prev_code == JUMP_INSN
440 || (prev_code == CALL_INSN
441 && nonlocal_label_list != 0
442 /* Ignore if CLOBBER since we consider this
443 part of the CALL. See below. */
445 && GET_CODE (PATTERN (insn)) == CLOBBER))
446 || prev_code == BARRIER)))
448 basic_block_head[++i] = insn;
449 basic_block_end[i] = insn;
450 basic_block_loop_depth[i] = depth;
451 if (code == CODE_LABEL)
453 LABEL_REFS (insn) = insn;
454 /* Any label that cannot be deleted
455 is considered to start a reachable block. */
456 if (LABEL_PRESERVE_P (insn))
460 else if (GET_RTX_CLASS (code) == 'i')
462 basic_block_end[i] = insn;
463 basic_block_loop_depth[i] = depth;
466 /* Make a list of all labels referred to other than by jumps. */
467 if (code == INSN || code == CALL_INSN)
469 rtx note = find_reg_note (insn, REG_LABEL, NULL_RTX);
471 label_value_list = gen_rtx (EXPR_LIST, VOIDmode, XEXP (note, 0),
475 BLOCK_NUM (insn) = i;
477 /* Don't separate a CALL_INSN from following CLOBBER insns. This is
478 a kludge that will go away when each CALL_INSN records its
482 && ! (prev_code == CALL_INSN && code == INSN
483 && GET_CODE (PATTERN (insn)) == CLOBBER))
486 if (i + 1 != n_basic_blocks)
490 /* Don't delete the labels (in this function)
491 that are referenced by non-jump instructions. */
494 for (x = label_value_list; x; x = XEXP (x, 1))
495 if (! LABEL_REF_NONLOCAL_P (x))
496 block_live[BLOCK_NUM (XEXP (x, 0))] = 1;
499 /* Record which basic blocks control can drop in to. */
503 for (i = 0; i < n_basic_blocks; i++)
505 register rtx insn = PREV_INSN (basic_block_head[i]);
506 /* TEMP1 is used to avoid a bug in Sequent's compiler. */
508 while (insn && GET_CODE (insn) == NOTE)
509 insn = PREV_INSN (insn);
510 temp1 = insn && GET_CODE (insn) != BARRIER;
511 basic_block_drops_in[i] = temp1;
515 /* Now find which basic blocks can actually be reached
516 and put all jump insns' LABEL_REFS onto the ref-chains
517 of their target labels. */
519 if (n_basic_blocks > 0)
521 int something_marked = 1;
523 /* Find all indirect jump insns and mark them as possibly jumping
524 to all the labels whose addresses are explicitly used.
525 This is because, when there are computed gotos,
526 we can't tell which labels they jump to, of all the possibilities. */
528 for (insn = f; insn; insn = NEXT_INSN (insn))
529 if (GET_CODE (insn) == JUMP_INSN
530 && GET_CODE (PATTERN (insn)) == SET
531 && SET_DEST (PATTERN (insn)) == pc_rtx
532 && (GET_CODE (SET_SRC (PATTERN (insn))) == REG
533 || GET_CODE (SET_SRC (PATTERN (insn))) == MEM))
536 for (x = label_value_list; x; x = XEXP (x, 1))
537 mark_label_ref (gen_rtx (LABEL_REF, VOIDmode, XEXP (x, 0)),
539 for (x = forced_labels; x; x = XEXP (x, 1))
540 mark_label_ref (gen_rtx (LABEL_REF, VOIDmode, XEXP (x, 0)),
544 /* Find all call insns and mark them as possibly jumping
545 to all the nonlocal goto handler labels. */
547 for (insn = f; insn; insn = NEXT_INSN (insn))
548 if (GET_CODE (insn) == CALL_INSN)
551 for (x = nonlocal_label_list; x; x = XEXP (x, 1))
552 /* Don't try marking labels that
553 were deleted as unreferenced. */
554 if (GET_CODE (XEXP (x, 0)) == CODE_LABEL)
555 mark_label_ref (gen_rtx (LABEL_REF, VOIDmode, XEXP (x, 0)),
557 /* ??? This could be made smarter:
558 in some cases it's possible to tell that certain
559 calls will not do a nonlocal goto.
561 For example, if the nested functions that do the
562 nonlocal gotos do not have their addresses taken, then
563 only calls to those functions or to other nested
564 functions that use them could possibly do nonlocal
568 /* Pass over all blocks, marking each block that is reachable
569 and has not yet been marked.
570 Keep doing this until, in one pass, no blocks have been marked.
571 Then blocks_live and blocks_marked are identical and correct.
572 In addition, all jumps actually reachable have been marked. */
574 while (something_marked)
576 something_marked = 0;
577 for (i = 0; i < n_basic_blocks; i++)
578 if (block_live[i] && !block_marked[i])
581 something_marked = 1;
582 if (i + 1 < n_basic_blocks && basic_block_drops_in[i + 1])
583 block_live[i + 1] = 1;
584 insn = basic_block_end[i];
585 if (GET_CODE (insn) == JUMP_INSN)
586 mark_label_ref (PATTERN (insn), insn, 0);
590 /* Now delete the code for any basic blocks that can't be reached.
591 They can occur because jump_optimize does not recognize
592 unreachable loops as unreachable. */
594 for (i = 0; i < n_basic_blocks; i++)
597 insn = basic_block_head[i];
600 if (GET_CODE (insn) == BARRIER)
602 if (GET_CODE (insn) != NOTE)
604 PUT_CODE (insn, NOTE);
605 NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
606 NOTE_SOURCE_FILE (insn) = 0;
608 if (insn == basic_block_end[i])
610 /* BARRIERs are between basic blocks, not part of one.
611 Delete a BARRIER if the preceding jump is deleted.
612 We cannot alter a BARRIER into a NOTE
613 because it is too short; but we can really delete
614 it because it is not part of a basic block. */
615 if (NEXT_INSN (insn) != 0
616 && GET_CODE (NEXT_INSN (insn)) == BARRIER)
617 delete_insn (NEXT_INSN (insn));
620 insn = NEXT_INSN (insn);
622 /* Each time we delete some basic blocks,
623 see if there is a jump around them that is
624 being turned into a no-op. If so, delete it. */
626 if (block_live[i - 1])
629 for (j = i; j < n_basic_blocks; j++)
633 insn = basic_block_end[i - 1];
634 if (GET_CODE (insn) == JUMP_INSN
635 /* An unconditional jump is the only possibility
636 we must check for, since a conditional one
637 would make these blocks live. */
638 && simplejump_p (insn)
639 && (label = XEXP (SET_SRC (PATTERN (insn)), 0), 1)
640 && INSN_UID (label) != 0
641 && BLOCK_NUM (label) == j)
643 PUT_CODE (insn, NOTE);
644 NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
645 NOTE_SOURCE_FILE (insn) = 0;
646 if (GET_CODE (NEXT_INSN (insn)) != BARRIER)
648 delete_insn (NEXT_INSN (insn));
657 /* Check expression X for label references;
658 if one is found, add INSN to the label's chain of references.
660 CHECKDUP means check for and avoid creating duplicate references
661 from the same insn. Such duplicates do no serious harm but
662 can slow life analysis. CHECKDUP is set only when duplicates
666 mark_label_ref (x, insn, checkdup)
670 register RTX_CODE code;
674 /* We can be called with NULL when scanning label_value_list. */
679 if (code == LABEL_REF)
681 register rtx label = XEXP (x, 0);
683 if (GET_CODE (label) != CODE_LABEL)
685 /* If the label was never emitted, this insn is junk,
686 but avoid a crash trying to refer to BLOCK_NUM (label).
687 This can happen as a result of a syntax error
688 and a diagnostic has already been printed. */
689 if (INSN_UID (label) == 0)
691 CONTAINING_INSN (x) = insn;
692 /* if CHECKDUP is set, check for duplicate ref from same insn
695 for (y = LABEL_REFS (label); y != label; y = LABEL_NEXTREF (y))
696 if (CONTAINING_INSN (y) == insn)
698 LABEL_NEXTREF (x) = LABEL_REFS (label);
699 LABEL_REFS (label) = x;
700 block_live_static[BLOCK_NUM (label)] = 1;
704 fmt = GET_RTX_FORMAT (code);
705 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
708 mark_label_ref (XEXP (x, i), insn, 0);
712 for (j = 0; j < XVECLEN (x, i); j++)
713 mark_label_ref (XVECEXP (x, i, j), insn, 1);
718 /* Determine which registers are live at the start of each
719 basic block of the function whose first insn is F.
720 NREGS is the number of registers used in F.
721 We allocate the vector basic_block_live_at_start
722 and the regsets that it points to, and fill them with the data.
723 regset_size and regset_bytes are also set here. */
726 life_analysis (f, nregs)
733 /* For each basic block, a bitmask of regs
734 live on exit from the block. */
735 regset *basic_block_live_at_end;
736 /* For each basic block, a bitmask of regs
737 live on entry to a successor-block of this block.
738 If this does not match basic_block_live_at_end,
739 that must be updated, and the block must be rescanned. */
740 regset *basic_block_new_live_at_end;
741 /* For each basic block, a bitmask of regs
742 whose liveness at the end of the basic block
743 can make a difference in which regs are live on entry to the block.
744 These are the regs that are set within the basic block,
745 possibly excluding those that are used after they are set. */
746 regset *basic_block_significant;
750 struct obstack flow_obstack;
752 gcc_obstack_init (&flow_obstack);
756 bzero (regs_ever_live, sizeof regs_ever_live);
758 /* Allocate and zero out many data structures
759 that will record the data from lifetime analysis. */
761 allocate_for_life_analysis ();
763 reg_next_use = (rtx *) alloca (nregs * sizeof (rtx));
764 bzero (reg_next_use, nregs * sizeof (rtx));
766 /* Set up several regset-vectors used internally within this function.
767 Their meanings are documented above, with their declarations. */
769 basic_block_live_at_end = (regset *) alloca (n_basic_blocks * sizeof (regset));
770 /* Don't use alloca since that leads to a crash rather than an error message
771 if there isn't enough space.
772 Don't use oballoc since we may need to allocate other things during
773 this function on the temporary obstack. */
774 tem = (regset) obstack_alloc (&flow_obstack, n_basic_blocks * regset_bytes);
775 bzero (tem, n_basic_blocks * regset_bytes);
776 init_regset_vector (basic_block_live_at_end, tem, n_basic_blocks, regset_bytes);
778 basic_block_new_live_at_end = (regset *) alloca (n_basic_blocks * sizeof (regset));
779 tem = (regset) obstack_alloc (&flow_obstack, n_basic_blocks * regset_bytes);
780 bzero (tem, n_basic_blocks * regset_bytes);
781 init_regset_vector (basic_block_new_live_at_end, tem, n_basic_blocks, regset_bytes);
783 basic_block_significant = (regset *) alloca (n_basic_blocks * sizeof (regset));
784 tem = (regset) obstack_alloc (&flow_obstack, n_basic_blocks * regset_bytes);
785 bzero (tem, n_basic_blocks * regset_bytes);
786 init_regset_vector (basic_block_significant, tem, n_basic_blocks, regset_bytes);
788 /* Record which insns refer to any volatile memory
789 or for any reason can't be deleted just because they are dead stores.
790 Also, delete any insns that copy a register to itself. */
792 for (insn = f; insn; insn = NEXT_INSN (insn))
794 enum rtx_code code1 = GET_CODE (insn);
795 if (code1 == CALL_INSN)
796 INSN_VOLATILE (insn) = 1;
797 else if (code1 == INSN || code1 == JUMP_INSN)
799 /* Delete (in effect) any obvious no-op moves. */
800 if (GET_CODE (PATTERN (insn)) == SET
801 && GET_CODE (SET_DEST (PATTERN (insn))) == REG
802 && GET_CODE (SET_SRC (PATTERN (insn))) == REG
803 && REGNO (SET_DEST (PATTERN (insn))) ==
804 REGNO (SET_SRC (PATTERN (insn)))
805 /* Insns carrying these notes are useful later on. */
806 && ! find_reg_note (insn, REG_EQUAL, NULL_RTX))
808 PUT_CODE (insn, NOTE);
809 NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
810 NOTE_SOURCE_FILE (insn) = 0;
812 else if (GET_CODE (PATTERN (insn)) == PARALLEL)
814 /* If nothing but SETs of registers to themselves,
815 this insn can also be deleted. */
816 for (i = 0; i < XVECLEN (PATTERN (insn), 0); i++)
818 rtx tem = XVECEXP (PATTERN (insn), 0, i);
820 if (GET_CODE (tem) == USE
821 || GET_CODE (tem) == CLOBBER)
824 if (GET_CODE (tem) != SET
825 || GET_CODE (SET_DEST (tem)) != REG
826 || GET_CODE (SET_SRC (tem)) != REG
827 || REGNO (SET_DEST (tem)) != REGNO (SET_SRC (tem)))
831 if (i == XVECLEN (PATTERN (insn), 0)
832 /* Insns carrying these notes are useful later on. */
833 && ! find_reg_note (insn, REG_EQUAL, NULL_RTX))
835 PUT_CODE (insn, NOTE);
836 NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
837 NOTE_SOURCE_FILE (insn) = 0;
840 INSN_VOLATILE (insn) = volatile_refs_p (PATTERN (insn));
842 else if (GET_CODE (PATTERN (insn)) != USE)
843 INSN_VOLATILE (insn) = volatile_refs_p (PATTERN (insn));
844 /* A SET that makes space on the stack cannot be dead.
845 (Such SETs occur only for allocating variable-size data,
846 so they will always have a PLUS or MINUS according to the
847 direction of stack growth.)
848 Even if this function never uses this stack pointer value,
849 signal handlers do! */
850 else if (code1 == INSN && GET_CODE (PATTERN (insn)) == SET
851 && SET_DEST (PATTERN (insn)) == stack_pointer_rtx
852 #ifdef STACK_GROWS_DOWNWARD
853 && GET_CODE (SET_SRC (PATTERN (insn))) == MINUS
855 && GET_CODE (SET_SRC (PATTERN (insn))) == PLUS
857 && XEXP (SET_SRC (PATTERN (insn)), 0) == stack_pointer_rtx)
858 INSN_VOLATILE (insn) = 1;
862 if (n_basic_blocks > 0)
863 #ifdef EXIT_IGNORE_STACK
864 if (! EXIT_IGNORE_STACK
865 || (! FRAME_POINTER_REQUIRED && flag_omit_frame_pointer))
868 /* If exiting needs the right stack value,
869 consider the stack pointer live at the end of the function. */
870 basic_block_live_at_end[n_basic_blocks - 1]
871 [STACK_POINTER_REGNUM / REGSET_ELT_BITS]
872 |= (REGSET_ELT_TYPE) 1 << (STACK_POINTER_REGNUM % REGSET_ELT_BITS);
873 basic_block_new_live_at_end[n_basic_blocks - 1]
874 [STACK_POINTER_REGNUM / REGSET_ELT_BITS]
875 |= (REGSET_ELT_TYPE) 1 << (STACK_POINTER_REGNUM % REGSET_ELT_BITS);
878 /* Mark the frame pointer is needed at the end of the function. If
879 we end up eliminating it, it will be removed from the live list
880 of each basic block by reload. */
882 if (n_basic_blocks > 0)
884 basic_block_live_at_end[n_basic_blocks - 1]
885 [FRAME_POINTER_REGNUM / REGSET_ELT_BITS]
886 |= (REGSET_ELT_TYPE) 1 << (FRAME_POINTER_REGNUM % REGSET_ELT_BITS);
887 basic_block_new_live_at_end[n_basic_blocks - 1]
888 [FRAME_POINTER_REGNUM / REGSET_ELT_BITS]
889 |= (REGSET_ELT_TYPE) 1 << (FRAME_POINTER_REGNUM % REGSET_ELT_BITS);
890 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
891 /* If they are different, also mark the hard frame pointer as live */
892 basic_block_live_at_end[n_basic_blocks - 1]
893 [HARD_FRAME_POINTER_REGNUM / REGSET_ELT_BITS]
894 |= (REGSET_ELT_TYPE) 1 << (HARD_FRAME_POINTER_REGNUM
896 basic_block_new_live_at_end[n_basic_blocks - 1]
897 [HARD_FRAME_POINTER_REGNUM / REGSET_ELT_BITS]
898 |= (REGSET_ELT_TYPE) 1 << (HARD_FRAME_POINTER_REGNUM
903 /* Mark all global registers as being live at the end of the function
904 since they may be referenced by our caller. */
906 if (n_basic_blocks > 0)
907 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
910 basic_block_live_at_end[n_basic_blocks - 1]
911 [i / REGSET_ELT_BITS]
912 |= (REGSET_ELT_TYPE) 1 << (i % REGSET_ELT_BITS);
913 basic_block_new_live_at_end[n_basic_blocks - 1]
914 [i / REGSET_ELT_BITS]
915 |= (REGSET_ELT_TYPE) 1 << (i % REGSET_ELT_BITS);
918 /* Propagate life info through the basic blocks
919 around the graph of basic blocks.
921 This is a relaxation process: each time a new register
922 is live at the end of the basic block, we must scan the block
923 to determine which registers are, as a consequence, live at the beginning
924 of that block. These registers must then be marked live at the ends
925 of all the blocks that can transfer control to that block.
926 The process continues until it reaches a fixed point. */
933 for (i = n_basic_blocks - 1; i >= 0; i--)
935 int consider = first_pass;
936 int must_rescan = first_pass;
941 /* Set CONSIDER if this block needs thinking about at all
942 (that is, if the regs live now at the end of it
943 are not the same as were live at the end of it when
944 we last thought about it).
945 Set must_rescan if it needs to be thought about
946 instruction by instruction (that is, if any additional
947 reg that is live at the end now but was not live there before
948 is one of the significant regs of this basic block). */
950 for (j = 0; j < regset_size; j++)
952 register REGSET_ELT_TYPE x
953 = (basic_block_new_live_at_end[i][j]
954 & ~basic_block_live_at_end[i][j]);
957 if (x & basic_block_significant[i][j])
969 /* The live_at_start of this block may be changing,
970 so another pass will be required after this one. */
975 /* No complete rescan needed;
976 just record those variables newly known live at end
977 as live at start as well. */
978 for (j = 0; j < regset_size; j++)
980 register REGSET_ELT_TYPE x
981 = (basic_block_new_live_at_end[i][j]
982 & ~basic_block_live_at_end[i][j]);
983 basic_block_live_at_start[i][j] |= x;
984 basic_block_live_at_end[i][j] |= x;
989 /* Update the basic_block_live_at_start
990 by propagation backwards through the block. */
991 bcopy (basic_block_new_live_at_end[i],
992 basic_block_live_at_end[i], regset_bytes);
993 bcopy (basic_block_live_at_end[i],
994 basic_block_live_at_start[i], regset_bytes);
995 propagate_block (basic_block_live_at_start[i],
996 basic_block_head[i], basic_block_end[i], 0,
997 first_pass ? basic_block_significant[i]
1003 register rtx jump, head;
1004 /* Update the basic_block_new_live_at_end's of the block
1005 that falls through into this one (if any). */
1006 head = basic_block_head[i];
1007 jump = PREV_INSN (head);
1008 if (basic_block_drops_in[i])
1010 register int from_block = BLOCK_NUM (jump);
1012 for (j = 0; j < regset_size; j++)
1013 basic_block_new_live_at_end[from_block][j]
1014 |= basic_block_live_at_start[i][j];
1016 /* Update the basic_block_new_live_at_end's of
1017 all the blocks that jump to this one. */
1018 if (GET_CODE (head) == CODE_LABEL)
1019 for (jump = LABEL_REFS (head);
1021 jump = LABEL_NEXTREF (jump))
1023 register int from_block = BLOCK_NUM (CONTAINING_INSN (jump));
1025 for (j = 0; j < regset_size; j++)
1026 basic_block_new_live_at_end[from_block][j]
1027 |= basic_block_live_at_start[i][j];
1037 /* The only pseudos that are live at the beginning of the function are
1038 those that were not set anywhere in the function. local-alloc doesn't
1039 know how to handle these correctly, so mark them as not local to any
1042 if (n_basic_blocks > 0)
1043 for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
1044 if (basic_block_live_at_start[0][i / REGSET_ELT_BITS]
1045 & ((REGSET_ELT_TYPE) 1 << (i % REGSET_ELT_BITS)))
1046 reg_basic_block[i] = REG_BLOCK_GLOBAL;
1048 /* Now the life information is accurate.
1049 Make one more pass over each basic block
1050 to delete dead stores, create autoincrement addressing
1051 and record how many times each register is used, is set, or dies.
1053 To save time, we operate directly in basic_block_live_at_end[i],
1054 thus destroying it (in fact, converting it into a copy of
1055 basic_block_live_at_start[i]). This is ok now because
1056 basic_block_live_at_end[i] is no longer used past this point. */
1060 for (i = 0; i < n_basic_blocks; i++)
1062 propagate_block (basic_block_live_at_end[i],
1063 basic_block_head[i], basic_block_end[i], 1,
1071 /* Something live during a setjmp should not be put in a register
1072 on certain machines which restore regs from stack frames
1073 rather than from the jmpbuf.
1074 But we don't need to do this for the user's variables, since
1075 ANSI says only volatile variables need this. */
1076 #ifdef LONGJMP_RESTORE_FROM_STACK
1077 for (i = FIRST_PSEUDO_REGISTER; i < nregs; i++)
1078 if (regs_live_at_setjmp[i / REGSET_ELT_BITS]
1079 & ((REGSET_ELT_TYPE) 1 << (i % REGSET_ELT_BITS))
1080 && regno_reg_rtx[i] != 0 && ! REG_USERVAR_P (regno_reg_rtx[i]))
1082 reg_live_length[i] = -1;
1083 reg_basic_block[i] = -1;
1088 /* We have a problem with any pseudoreg that
1089 lives across the setjmp. ANSI says that if a
1090 user variable does not change in value
1091 between the setjmp and the longjmp, then the longjmp preserves it.
1092 This includes longjmp from a place where the pseudo appears dead.
1093 (In principle, the value still exists if it is in scope.)
1094 If the pseudo goes in a hard reg, some other value may occupy
1095 that hard reg where this pseudo is dead, thus clobbering the pseudo.
1096 Conclusion: such a pseudo must not go in a hard reg. */
1097 for (i = FIRST_PSEUDO_REGISTER; i < nregs; i++)
1098 if ((regs_live_at_setjmp[i / REGSET_ELT_BITS]
1099 & ((REGSET_ELT_TYPE) 1 << (i % REGSET_ELT_BITS)))
1100 && regno_reg_rtx[i] != 0)
1102 reg_live_length[i] = -1;
1103 reg_basic_block[i] = -1;
1106 obstack_free (&flow_obstack, NULL_PTR);
1109 /* Subroutines of life analysis. */
1111 /* Allocate the permanent data structures that represent the results
1112 of life analysis. Not static since used also for stupid life analysis. */
1115 allocate_for_life_analysis ()
1118 register regset tem;
1120 regset_size = ((max_regno + REGSET_ELT_BITS - 1) / REGSET_ELT_BITS);
1121 regset_bytes = regset_size * sizeof (*(regset)0);
1123 reg_n_refs = (int *) oballoc (max_regno * sizeof (int));
1124 bzero (reg_n_refs, max_regno * sizeof (int));
1126 reg_n_sets = (short *) oballoc (max_regno * sizeof (short));
1127 bzero (reg_n_sets, max_regno * sizeof (short));
1129 reg_n_deaths = (short *) oballoc (max_regno * sizeof (short));
1130 bzero (reg_n_deaths, max_regno * sizeof (short));
1132 reg_live_length = (int *) oballoc (max_regno * sizeof (int));
1133 bzero (reg_live_length, max_regno * sizeof (int));
1135 reg_n_calls_crossed = (int *) oballoc (max_regno * sizeof (int));
1136 bzero (reg_n_calls_crossed, max_regno * sizeof (int));
1138 reg_basic_block = (int *) oballoc (max_regno * sizeof (int));
1139 for (i = 0; i < max_regno; i++)
1140 reg_basic_block[i] = REG_BLOCK_UNKNOWN;
1142 basic_block_live_at_start = (regset *) oballoc (n_basic_blocks * sizeof (regset));
1143 tem = (regset) oballoc (n_basic_blocks * regset_bytes);
1144 bzero (tem, n_basic_blocks * regset_bytes);
1145 init_regset_vector (basic_block_live_at_start, tem, n_basic_blocks, regset_bytes);
1147 regs_live_at_setjmp = (regset) oballoc (regset_bytes);
1148 bzero (regs_live_at_setjmp, regset_bytes);
1151 /* Make each element of VECTOR point at a regset,
1152 taking the space for all those regsets from SPACE.
1153 SPACE is of type regset, but it is really as long as NELTS regsets.
1154 BYTES_PER_ELT is the number of bytes in one regset. */
1157 init_regset_vector (vector, space, nelts, bytes_per_elt)
1164 register regset p = space;
1166 for (i = 0; i < nelts; i++)
1169 p += bytes_per_elt / sizeof (*p);
1173 /* Compute the registers live at the beginning of a basic block
1174 from those live at the end.
1176 When called, OLD contains those live at the end.
1177 On return, it contains those live at the beginning.
1178 FIRST and LAST are the first and last insns of the basic block.
1180 FINAL is nonzero if we are doing the final pass which is not
1181 for computing the life info (since that has already been done)
1182 but for acting on it. On this pass, we delete dead stores,
1183 set up the logical links and dead-variables lists of instructions,
1184 and merge instructions for autoincrement and autodecrement addresses.
1186 SIGNIFICANT is nonzero only the first time for each basic block.
1187 If it is nonzero, it points to a regset in which we store
1188 a 1 for each register that is set within the block.
1190 BNUM is the number of the basic block. */
1193 propagate_block (old, first, last, final, significant, bnum)
1194 register regset old;
1206 /* The following variables are used only if FINAL is nonzero. */
1207 /* This vector gets one element for each reg that has been live
1208 at any point in the basic block that has been scanned so far.
1209 SOMETIMES_MAX says how many elements are in use so far.
1210 In each element, OFFSET is the byte-number within a regset
1211 for the register described by the element, and BIT is a mask
1212 for that register's bit within the byte. */
1213 register struct sometimes { short offset; short bit; } *regs_sometimes_live;
1214 int sometimes_max = 0;
1215 /* This regset has 1 for each reg that we have seen live so far.
1216 It and REGS_SOMETIMES_LIVE are updated together. */
1219 /* The loop depth may change in the middle of a basic block. Since we
1220 scan from end to beginning, we start with the depth at the end of the
1221 current basic block, and adjust as we pass ends and starts of loops. */
1222 loop_depth = basic_block_loop_depth[bnum];
1224 dead = (regset) alloca (regset_bytes);
1225 live = (regset) alloca (regset_bytes);
1230 /* Include any notes at the end of the block in the scan.
1231 This is in case the block ends with a call to setjmp. */
1233 while (NEXT_INSN (last) != 0 && GET_CODE (NEXT_INSN (last)) == NOTE)
1235 /* Look for loop boundaries, we are going forward here. */
1236 last = NEXT_INSN (last);
1237 if (NOTE_LINE_NUMBER (last) == NOTE_INSN_LOOP_BEG)
1239 else if (NOTE_LINE_NUMBER (last) == NOTE_INSN_LOOP_END)
1245 register int i, offset;
1246 REGSET_ELT_TYPE bit;
1249 maxlive = (regset) alloca (regset_bytes);
1250 bcopy (old, maxlive, regset_bytes);
1252 = (struct sometimes *) alloca (max_regno * sizeof (struct sometimes));
1254 /* Process the regs live at the end of the block.
1255 Enter them in MAXLIVE and REGS_SOMETIMES_LIVE.
1256 Also mark them as not local to any one basic block. */
1258 for (offset = 0, i = 0; offset < regset_size; offset++)
1259 for (bit = 1; bit; bit <<= 1, i++)
1263 if (old[offset] & bit)
1265 reg_basic_block[i] = REG_BLOCK_GLOBAL;
1266 regs_sometimes_live[sometimes_max].offset = offset;
1267 regs_sometimes_live[sometimes_max].bit = i % REGSET_ELT_BITS;
1273 /* Scan the block an insn at a time from end to beginning. */
1275 for (insn = last; ; insn = prev)
1277 prev = PREV_INSN (insn);
1279 /* Look for loop boundaries, remembering that we are going backwards. */
1280 if (GET_CODE (insn) == NOTE
1281 && NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END)
1283 else if (GET_CODE (insn) == NOTE
1284 && NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG)
1287 /* If we have LOOP_DEPTH == 0, there has been a bookkeeping error.
1288 Abort now rather than setting register status incorrectly. */
1289 if (loop_depth == 0)
1292 /* If this is a call to `setjmp' et al,
1293 warn if any non-volatile datum is live. */
1295 if (final && GET_CODE (insn) == NOTE
1296 && NOTE_LINE_NUMBER (insn) == NOTE_INSN_SETJMP)
1299 for (i = 0; i < regset_size; i++)
1300 regs_live_at_setjmp[i] |= old[i];
1303 /* Update the life-status of regs for this insn.
1304 First DEAD gets which regs are set in this insn
1305 then LIVE gets which regs are used in this insn.
1306 Then the regs live before the insn
1307 are those live after, with DEAD regs turned off,
1308 and then LIVE regs turned on. */
1310 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
1313 rtx note = find_reg_note (insn, REG_RETVAL, NULL_RTX);
1315 = (insn_dead_p (PATTERN (insn), old, 0)
1316 /* Don't delete something that refers to volatile storage! */
1317 && ! INSN_VOLATILE (insn));
1319 = (insn_is_dead && note != 0
1320 && libcall_dead_p (PATTERN (insn), old, note, insn));
1322 /* If an instruction consists of just dead store(s) on final pass,
1323 "delete" it by turning it into a NOTE of type NOTE_INSN_DELETED.
1324 We could really delete it with delete_insn, but that
1325 can cause trouble for first or last insn in a basic block. */
1326 if (final && insn_is_dead)
1328 PUT_CODE (insn, NOTE);
1329 NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
1330 NOTE_SOURCE_FILE (insn) = 0;
1332 /* CC0 is now known to be dead. Either this insn used it,
1333 in which case it doesn't anymore, or clobbered it,
1334 so the next insn can't use it. */
1337 /* If this insn is copying the return value from a library call,
1338 delete the entire library call. */
1339 if (libcall_is_dead)
1341 rtx first = XEXP (note, 0);
1343 while (INSN_DELETED_P (first))
1344 first = NEXT_INSN (first);
1349 NOTE_LINE_NUMBER (p) = NOTE_INSN_DELETED;
1350 NOTE_SOURCE_FILE (p) = 0;
1356 for (i = 0; i < regset_size; i++)
1358 dead[i] = 0; /* Faster than bzero here */
1359 live[i] = 0; /* since regset_size is usually small */
1362 /* See if this is an increment or decrement that can be
1363 merged into a following memory address. */
1366 register rtx x = PATTERN (insn);
1367 /* Does this instruction increment or decrement a register? */
1368 if (final && GET_CODE (x) == SET
1369 && GET_CODE (SET_DEST (x)) == REG
1370 && (GET_CODE (SET_SRC (x)) == PLUS
1371 || GET_CODE (SET_SRC (x)) == MINUS)
1372 && XEXP (SET_SRC (x), 0) == SET_DEST (x)
1373 && GET_CODE (XEXP (SET_SRC (x), 1)) == CONST_INT
1374 /* Ok, look for a following memory ref we can combine with.
1375 If one is found, change the memory ref to a PRE_INC
1376 or PRE_DEC, cancel this insn, and return 1.
1377 Return 0 if nothing has been done. */
1378 && try_pre_increment_1 (insn))
1381 #endif /* AUTO_INC_DEC */
1383 /* If this is not the final pass, and this insn is copying the
1384 value of a library call and it's dead, don't scan the
1385 insns that perform the library call, so that the call's
1386 arguments are not marked live. */
1387 if (libcall_is_dead)
1389 /* Mark the dest reg as `significant'. */
1390 mark_set_regs (old, dead, PATTERN (insn), NULL_RTX, significant);
1392 insn = XEXP (note, 0);
1393 prev = PREV_INSN (insn);
1395 else if (GET_CODE (PATTERN (insn)) == SET
1396 && SET_DEST (PATTERN (insn)) == stack_pointer_rtx
1397 && GET_CODE (SET_SRC (PATTERN (insn))) == PLUS
1398 && XEXP (SET_SRC (PATTERN (insn)), 0) == stack_pointer_rtx
1399 && GET_CODE (XEXP (SET_SRC (PATTERN (insn)), 1)) == CONST_INT)
1400 /* We have an insn to pop a constant amount off the stack.
1401 (Such insns use PLUS regardless of the direction of the stack,
1402 and any insn to adjust the stack by a constant is always a pop.)
1403 These insns, if not dead stores, have no effect on life. */
1407 /* LIVE gets the regs used in INSN;
1408 DEAD gets those set by it. Dead insns don't make anything
1411 mark_set_regs (old, dead, PATTERN (insn),
1412 final ? insn : NULL_RTX, significant);
1414 /* If an insn doesn't use CC0, it becomes dead since we
1415 assume that every insn clobbers it. So show it dead here;
1416 mark_used_regs will set it live if it is referenced. */
1420 mark_used_regs (old, live, PATTERN (insn), final, insn);
1422 /* Sometimes we may have inserted something before INSN (such as
1423 a move) when we make an auto-inc. So ensure we will scan
1426 prev = PREV_INSN (insn);
1429 if (! insn_is_dead && GET_CODE (insn) == CALL_INSN)
1433 /* Each call clobbers all call-clobbered regs that are not
1434 global. Note that the function-value reg is a
1435 call-clobbered reg, and mark_set_regs has already had
1436 a chance to handle it. */
1438 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1439 if (call_used_regs[i] && ! global_regs[i])
1440 dead[i / REGSET_ELT_BITS]
1441 |= ((REGSET_ELT_TYPE) 1 << (i % REGSET_ELT_BITS));
1443 /* The stack ptr is used (honorarily) by a CALL insn. */
1444 live[STACK_POINTER_REGNUM / REGSET_ELT_BITS]
1445 |= ((REGSET_ELT_TYPE) 1
1446 << (STACK_POINTER_REGNUM % REGSET_ELT_BITS));
1448 /* Calls may also reference any of the global registers,
1449 so they are made live. */
1451 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1453 live[i / REGSET_ELT_BITS]
1454 |= ((REGSET_ELT_TYPE) 1 << (i % REGSET_ELT_BITS));
1456 /* Calls also clobber memory. */
1460 /* Update OLD for the registers used or set. */
1461 for (i = 0; i < regset_size; i++)
1467 if (GET_CODE (insn) == CALL_INSN && final)
1469 /* Any regs live at the time of a call instruction
1470 must not go in a register clobbered by calls.
1471 Find all regs now live and record this for them. */
1473 register struct sometimes *p = regs_sometimes_live;
1475 for (i = 0; i < sometimes_max; i++, p++)
1476 if (old[p->offset] & ((REGSET_ELT_TYPE) 1 << p->bit))
1477 reg_n_calls_crossed[p->offset * REGSET_ELT_BITS + p->bit]+= 1;
1481 /* On final pass, add any additional sometimes-live regs
1482 into MAXLIVE and REGS_SOMETIMES_LIVE.
1483 Also update counts of how many insns each reg is live at. */
1487 for (i = 0; i < regset_size; i++)
1489 register REGSET_ELT_TYPE diff = live[i] & ~maxlive[i];
1495 for (regno = 0; diff && regno < REGSET_ELT_BITS; regno++)
1496 if (diff & ((REGSET_ELT_TYPE) 1 << regno))
1498 regs_sometimes_live[sometimes_max].offset = i;
1499 regs_sometimes_live[sometimes_max].bit = regno;
1500 diff &= ~ ((REGSET_ELT_TYPE) 1 << regno);
1507 register struct sometimes *p = regs_sometimes_live;
1508 for (i = 0; i < sometimes_max; i++, p++)
1510 if (old[p->offset] & ((REGSET_ELT_TYPE) 1 << p->bit))
1511 reg_live_length[p->offset * REGSET_ELT_BITS + p->bit]++;
1521 if (num_scratch > max_scratch)
1522 max_scratch = num_scratch;
1525 /* Return 1 if X (the body of an insn, or part of it) is just dead stores
1526 (SET expressions whose destinations are registers dead after the insn).
1527 NEEDED is the regset that says which regs are alive after the insn.
1529 Unless CALL_OK is non-zero, an insn is needed if it contains a CALL. */
1532 insn_dead_p (x, needed, call_ok)
1537 register RTX_CODE code = GET_CODE (x);
1538 /* If setting something that's a reg or part of one,
1539 see if that register's altered value will be live. */
1543 register rtx r = SET_DEST (x);
1544 /* A SET that is a subroutine call cannot be dead. */
1545 if (! call_ok && GET_CODE (SET_SRC (x)) == CALL)
1549 if (GET_CODE (r) == CC0)
1553 if (GET_CODE (r) == MEM && last_mem_set && ! MEM_VOLATILE_P (r)
1554 && rtx_equal_p (r, last_mem_set))
1557 while (GET_CODE (r) == SUBREG
1558 || GET_CODE (r) == STRICT_LOW_PART
1559 || GET_CODE (r) == ZERO_EXTRACT
1560 || GET_CODE (r) == SIGN_EXTRACT)
1563 if (GET_CODE (r) == REG)
1565 register int regno = REGNO (r);
1566 register int offset = regno / REGSET_ELT_BITS;
1567 register REGSET_ELT_TYPE bit
1568 = (REGSET_ELT_TYPE) 1 << (regno % REGSET_ELT_BITS);
1570 /* Don't delete insns to set global regs. */
1571 if ((regno < FIRST_PSEUDO_REGISTER && global_regs[regno])
1572 /* Make sure insns to set frame pointer aren't deleted. */
1573 || regno == FRAME_POINTER_REGNUM
1574 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
1575 || regno == HARD_FRAME_POINTER_REGNUM
1577 #if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
1578 /* Make sure insns to set arg pointer are never deleted
1579 (if the arg pointer isn't fixed, there will be a USE for
1580 it, so we can treat it normally). */
1581 || (regno == ARG_POINTER_REGNUM && fixed_regs[regno])
1583 || (needed[offset] & bit) != 0)
1586 /* If this is a hard register, verify that subsequent words are
1588 if (regno < FIRST_PSEUDO_REGISTER)
1590 int n = HARD_REGNO_NREGS (regno, GET_MODE (r));
1593 if ((needed[(regno + n) / REGSET_ELT_BITS]
1594 & ((REGSET_ELT_TYPE) 1
1595 << ((regno + n) % REGSET_ELT_BITS))) != 0)
1602 /* If performing several activities,
1603 insn is dead if each activity is individually dead.
1604 Also, CLOBBERs and USEs can be ignored; a CLOBBER or USE
1605 that's inside a PARALLEL doesn't make the insn worth keeping. */
1606 else if (code == PARALLEL)
1608 register int i = XVECLEN (x, 0);
1609 for (i--; i >= 0; i--)
1611 rtx elt = XVECEXP (x, 0, i);
1612 if (!insn_dead_p (elt, needed, call_ok)
1613 && GET_CODE (elt) != CLOBBER
1614 && GET_CODE (elt) != USE)
1619 /* We do not check CLOBBER or USE here.
1620 An insn consisting of just a CLOBBER or just a USE
1621 should not be deleted. */
1625 /* If X is the pattern of the last insn in a libcall, and assuming X is dead,
1626 return 1 if the entire library call is dead.
1627 This is true if X copies a register (hard or pseudo)
1628 and if the hard return reg of the call insn is dead.
1629 (The caller should have tested the destination of X already for death.)
1631 If this insn doesn't just copy a register, then we don't
1632 have an ordinary libcall. In that case, cse could not have
1633 managed to substitute the source for the dest later on,
1634 so we can assume the libcall is dead.
1636 NEEDED is the bit vector of pseudoregs live before this insn.
1637 NOTE is the REG_RETVAL note of the insn. INSN is the insn itself. */
1640 libcall_dead_p (x, needed, note, insn)
1646 register RTX_CODE code = GET_CODE (x);
1650 register rtx r = SET_SRC (x);
1651 if (GET_CODE (r) == REG)
1653 rtx call = XEXP (note, 0);
1656 /* Find the call insn. */
1657 while (call != insn && GET_CODE (call) != CALL_INSN)
1658 call = NEXT_INSN (call);
1660 /* If there is none, do nothing special,
1661 since ordinary death handling can understand these insns. */
1665 /* See if the hard reg holding the value is dead.
1666 If this is a PARALLEL, find the call within it. */
1667 call = PATTERN (call);
1668 if (GET_CODE (call) == PARALLEL)
1670 for (i = XVECLEN (call, 0) - 1; i >= 0; i--)
1671 if (GET_CODE (XVECEXP (call, 0, i)) == SET
1672 && GET_CODE (SET_SRC (XVECEXP (call, 0, i))) == CALL)
1678 call = XVECEXP (call, 0, i);
1681 return insn_dead_p (call, needed, 1);
1687 /* Return 1 if register REGNO was used before it was set.
1688 In other words, if it is live at function entry.
1689 Don't count global regster variables, though. */
1692 regno_uninitialized (regno)
1695 if (n_basic_blocks == 0
1696 || (regno < FIRST_PSEUDO_REGISTER && global_regs[regno]))
1699 return (basic_block_live_at_start[0][regno / REGSET_ELT_BITS]
1700 & ((REGSET_ELT_TYPE) 1 << (regno % REGSET_ELT_BITS)));
1703 /* 1 if register REGNO was alive at a place where `setjmp' was called
1704 and was set more than once or is an argument.
1705 Such regs may be clobbered by `longjmp'. */
1708 regno_clobbered_at_setjmp (regno)
1711 if (n_basic_blocks == 0)
1714 return ((reg_n_sets[regno] > 1
1715 || (basic_block_live_at_start[0][regno / REGSET_ELT_BITS]
1716 & ((REGSET_ELT_TYPE) 1 << (regno % REGSET_ELT_BITS))))
1717 && (regs_live_at_setjmp[regno / REGSET_ELT_BITS]
1718 & ((REGSET_ELT_TYPE) 1 << (regno % REGSET_ELT_BITS))));
1721 /* Process the registers that are set within X.
1722 Their bits are set to 1 in the regset DEAD,
1723 because they are dead prior to this insn.
1725 If INSN is nonzero, it is the insn being processed
1726 and the fact that it is nonzero implies this is the FINAL pass
1727 in propagate_block. In this case, various info about register
1728 usage is stored, LOG_LINKS fields of insns are set up. */
1730 static void mark_set_1 ();
1733 mark_set_regs (needed, dead, x, insn, significant)
1740 register RTX_CODE code = GET_CODE (x);
1742 if (code == SET || code == CLOBBER)
1743 mark_set_1 (needed, dead, x, insn, significant);
1744 else if (code == PARALLEL)
1747 for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
1749 code = GET_CODE (XVECEXP (x, 0, i));
1750 if (code == SET || code == CLOBBER)
1751 mark_set_1 (needed, dead, XVECEXP (x, 0, i), insn, significant);
1756 /* Process a single SET rtx, X. */
1759 mark_set_1 (needed, dead, x, insn, significant)
1767 register rtx reg = SET_DEST (x);
1769 /* Modifying just one hardware register of a multi-reg value
1770 or just a byte field of a register
1771 does not mean the value from before this insn is now dead.
1772 But it does mean liveness of that register at the end of the block
1775 Within mark_set_1, however, we treat it as if the register is
1776 indeed modified. mark_used_regs will, however, also treat this
1777 register as being used. Thus, we treat these insns as setting a
1778 new value for the register as a function of its old value. This
1779 cases LOG_LINKS to be made appropriately and this will help combine. */
1781 while (GET_CODE (reg) == SUBREG || GET_CODE (reg) == ZERO_EXTRACT
1782 || GET_CODE (reg) == SIGN_EXTRACT
1783 || GET_CODE (reg) == STRICT_LOW_PART)
1784 reg = XEXP (reg, 0);
1786 /* If we are writing into memory or into a register mentioned in the
1787 address of the last thing stored into memory, show we don't know
1788 what the last store was. If we are writing memory, save the address
1789 unless it is volatile. */
1790 if (GET_CODE (reg) == MEM
1791 || (GET_CODE (reg) == REG
1792 && last_mem_set != 0 && reg_overlap_mentioned_p (reg, last_mem_set)))
1795 if (GET_CODE (reg) == MEM && ! side_effects_p (reg)
1796 /* There are no REG_INC notes for SP, so we can't assume we'll see
1797 everything that invalidates it. To be safe, don't eliminate any
1798 stores though SP; none of them should be redundant anyway. */
1799 && ! reg_mentioned_p (stack_pointer_rtx, reg))
1802 if (GET_CODE (reg) == REG
1803 && (regno = REGNO (reg), regno != FRAME_POINTER_REGNUM)
1804 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
1805 && regno != HARD_FRAME_POINTER_REGNUM
1807 #if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
1808 && ! (regno == ARG_POINTER_REGNUM && fixed_regs[regno])
1810 && ! (regno < FIRST_PSEUDO_REGISTER && global_regs[regno]))
1811 /* && regno != STACK_POINTER_REGNUM) -- let's try without this. */
1813 register int offset = regno / REGSET_ELT_BITS;
1814 register REGSET_ELT_TYPE bit
1815 = (REGSET_ELT_TYPE) 1 << (regno % REGSET_ELT_BITS);
1816 REGSET_ELT_TYPE all_needed = (needed[offset] & bit);
1817 REGSET_ELT_TYPE some_needed = (needed[offset] & bit);
1819 /* Mark it as a significant register for this basic block. */
1821 significant[offset] |= bit;
1823 /* Mark it as as dead before this insn. */
1824 dead[offset] |= bit;
1826 /* A hard reg in a wide mode may really be multiple registers.
1827 If so, mark all of them just like the first. */
1828 if (regno < FIRST_PSEUDO_REGISTER)
1832 /* Nothing below is needed for the stack pointer; get out asap.
1833 Eg, log links aren't needed, since combine won't use them. */
1834 if (regno == STACK_POINTER_REGNUM)
1837 n = HARD_REGNO_NREGS (regno, GET_MODE (reg));
1841 significant[(regno + n) / REGSET_ELT_BITS]
1842 |= (REGSET_ELT_TYPE) 1 << ((regno + n) % REGSET_ELT_BITS);
1843 dead[(regno + n) / REGSET_ELT_BITS]
1844 |= (REGSET_ELT_TYPE) 1 << ((regno + n) % REGSET_ELT_BITS);
1846 |= (needed[(regno + n) / REGSET_ELT_BITS]
1847 & (REGSET_ELT_TYPE) 1 << ((regno + n) % REGSET_ELT_BITS));
1849 &= (needed[(regno + n) / REGSET_ELT_BITS]
1850 & (REGSET_ELT_TYPE) 1 << ((regno + n) % REGSET_ELT_BITS));
1853 /* Additional data to record if this is the final pass. */
1856 register rtx y = reg_next_use[regno];
1857 register int blocknum = BLOCK_NUM (insn);
1859 /* The next use is no longer "next", since a store intervenes. */
1860 reg_next_use[regno] = 0;
1862 /* If this is a hard reg, record this function uses the reg. */
1864 if (regno < FIRST_PSEUDO_REGISTER)
1867 int endregno = regno + HARD_REGNO_NREGS (regno, GET_MODE (reg));
1869 for (i = regno; i < endregno; i++)
1871 regs_ever_live[i] = 1;
1877 /* Keep track of which basic blocks each reg appears in. */
1879 if (reg_basic_block[regno] == REG_BLOCK_UNKNOWN)
1880 reg_basic_block[regno] = blocknum;
1881 else if (reg_basic_block[regno] != blocknum)
1882 reg_basic_block[regno] = REG_BLOCK_GLOBAL;
1884 /* Count (weighted) references, stores, etc. This counts a
1885 register twice if it is modified, but that is correct. */
1886 reg_n_sets[regno]++;
1888 reg_n_refs[regno] += loop_depth;
1890 /* The insns where a reg is live are normally counted
1891 elsewhere, but we want the count to include the insn
1892 where the reg is set, and the normal counting mechanism
1893 would not count it. */
1894 reg_live_length[regno]++;
1899 /* Make a logical link from the next following insn
1900 that uses this register, back to this insn.
1901 The following insns have already been processed.
1903 We don't build a LOG_LINK for hard registers containing
1904 in ASM_OPERANDs. If these registers get replaced,
1905 we might wind up changing the semantics of the insn,
1906 even if reload can make what appear to be valid assignments
1908 if (y && (BLOCK_NUM (y) == blocknum)
1909 && (regno >= FIRST_PSEUDO_REGISTER
1910 || asm_noperands (PATTERN (y)) < 0))
1912 = gen_rtx (INSN_LIST, VOIDmode, insn, LOG_LINKS (y));
1914 else if (! some_needed)
1916 /* Note that dead stores have already been deleted when possible
1917 If we get here, we have found a dead store that cannot
1918 be eliminated (because the same insn does something useful).
1919 Indicate this by marking the reg being set as dying here. */
1921 = gen_rtx (EXPR_LIST, REG_UNUSED, reg, REG_NOTES (insn));
1922 reg_n_deaths[REGNO (reg)]++;
1926 /* This is a case where we have a multi-word hard register
1927 and some, but not all, of the words of the register are
1928 needed in subsequent insns. Write REG_UNUSED notes
1929 for those parts that were not needed. This case should
1934 for (i = HARD_REGNO_NREGS (regno, GET_MODE (reg)) - 1;
1936 if ((needed[(regno + i) / REGSET_ELT_BITS]
1937 & ((REGSET_ELT_TYPE) 1
1938 << ((regno + i) % REGSET_ELT_BITS))) == 0)
1940 = gen_rtx (EXPR_LIST, REG_UNUSED,
1941 gen_rtx (REG, word_mode, regno + i),
1946 else if (GET_CODE (reg) == REG)
1947 reg_next_use[regno] = 0;
1949 /* If this is the last pass and this is a SCRATCH, show it will be dying
1950 here and count it. */
1951 else if (GET_CODE (reg) == SCRATCH && insn != 0)
1954 = gen_rtx (EXPR_LIST, REG_UNUSED, reg, REG_NOTES (insn));
1961 /* X is a MEM found in INSN. See if we can convert it into an auto-increment
1965 find_auto_inc (needed, x, insn)
1970 rtx addr = XEXP (x, 0);
1973 /* Here we detect use of an index register which might be good for
1974 postincrement, postdecrement, preincrement, or predecrement. */
1976 if (GET_CODE (addr) == PLUS && GET_CODE (XEXP (addr, 1)) == CONST_INT)
1977 offset = INTVAL (XEXP (addr, 1)), addr = XEXP (addr, 0);
1979 if (GET_CODE (addr) == REG)
1982 register int size = GET_MODE_SIZE (GET_MODE (x));
1985 int regno = REGNO (addr);
1987 /* Is the next use an increment that might make auto-increment? */
1988 incr = reg_next_use[regno];
1989 if (incr && GET_CODE (PATTERN (incr)) == SET
1990 && BLOCK_NUM (incr) == BLOCK_NUM (insn)
1991 /* Can't add side effects to jumps; if reg is spilled and
1992 reloaded, there's no way to store back the altered value. */
1993 && GET_CODE (insn) != JUMP_INSN
1994 && (y = SET_SRC (PATTERN (incr)), GET_CODE (y) == PLUS)
1995 && XEXP (y, 0) == addr
1996 && GET_CODE (XEXP (y, 1)) == CONST_INT
1998 #ifdef HAVE_POST_INCREMENT
1999 || (INTVAL (XEXP (y, 1)) == size && offset == 0)
2001 #ifdef HAVE_POST_DECREMENT
2002 || (INTVAL (XEXP (y, 1)) == - size && offset == 0)
2004 #ifdef HAVE_PRE_INCREMENT
2005 || (INTVAL (XEXP (y, 1)) == size && offset == size)
2007 #ifdef HAVE_PRE_DECREMENT
2008 || (INTVAL (XEXP (y, 1)) == - size && offset == - size)
2011 /* Make sure this reg appears only once in this insn. */
2012 && (use = find_use_as_address (PATTERN (insn), addr, offset),
2013 use != 0 && use != (rtx) 1))
2016 rtx q = SET_DEST (PATTERN (incr));
2018 if (dead_or_set_p (incr, addr))
2020 else if (GET_CODE (q) == REG
2021 /* PREV_INSN used here to check the semi-open interval
2023 && ! reg_used_between_p (q, PREV_INSN (insn), incr))
2025 /* We have *p followed sometime later by q = p+size.
2026 Both p and q must be live afterward,
2027 and q is not used between INSN and it's assignment.
2028 Change it to q = p, ...*q..., q = q+size.
2029 Then fall into the usual case. */
2033 emit_move_insn (q, addr);
2034 insns = get_insns ();
2037 /* If anything in INSNS have UID's that don't fit within the
2038 extra space we allocate earlier, we can't make this auto-inc.
2039 This should never happen. */
2040 for (temp = insns; temp; temp = NEXT_INSN (temp))
2042 if (INSN_UID (temp) > max_uid_for_flow)
2044 BLOCK_NUM (temp) = BLOCK_NUM (insn);
2047 emit_insns_before (insns, insn);
2049 if (basic_block_head[BLOCK_NUM (insn)] == insn)
2050 basic_block_head[BLOCK_NUM (insn)] = insns;
2055 /* INCR will become a NOTE and INSN won't contain a
2056 use of ADDR. If a use of ADDR was just placed in
2057 the insn before INSN, make that the next use.
2058 Otherwise, invalidate it. */
2059 if (GET_CODE (PREV_INSN (insn)) == INSN
2060 && GET_CODE (PATTERN (PREV_INSN (insn))) == SET
2061 && SET_SRC (PATTERN (PREV_INSN (insn))) == addr)
2062 reg_next_use[regno] = PREV_INSN (insn);
2064 reg_next_use[regno] = 0;
2070 /* REGNO is now used in INCR which is below INSN, but
2071 it previously wasn't live here. If we don't mark
2072 it as needed, we'll put a REG_DEAD note for it
2073 on this insn, which is incorrect. */
2074 needed[regno / REGSET_ELT_BITS]
2075 |= (REGSET_ELT_TYPE) 1 << (regno % REGSET_ELT_BITS);
2077 /* If there are any calls between INSN and INCR, show
2078 that REGNO now crosses them. */
2079 for (temp = insn; temp != incr; temp = NEXT_INSN (temp))
2080 if (GET_CODE (temp) == CALL_INSN)
2081 reg_n_calls_crossed[regno]++;
2086 /* We have found a suitable auto-increment: do POST_INC around
2087 the register here, and patch out the increment instruction
2089 XEXP (x, 0) = gen_rtx ((INTVAL (XEXP (y, 1)) == size
2090 ? (offset ? PRE_INC : POST_INC)
2091 : (offset ? PRE_DEC : POST_DEC)),
2094 /* Record that this insn has an implicit side effect. */
2096 = gen_rtx (EXPR_LIST, REG_INC, addr, REG_NOTES (insn));
2098 /* Modify the old increment-insn to simply copy
2099 the already-incremented value of our register. */
2100 SET_SRC (PATTERN (incr)) = addr;
2101 /* Indicate insn must be re-recognized. */
2102 INSN_CODE (incr) = -1;
2104 /* If that makes it a no-op (copying the register into itself)
2105 then delete it so it won't appear to be a "use" and a "set"
2106 of this register. */
2107 if (SET_DEST (PATTERN (incr)) == addr)
2109 PUT_CODE (incr, NOTE);
2110 NOTE_LINE_NUMBER (incr) = NOTE_INSN_DELETED;
2111 NOTE_SOURCE_FILE (incr) = 0;
2114 if (regno >= FIRST_PSEUDO_REGISTER)
2116 /* Count an extra reference to the reg. When a reg is
2117 incremented, spilling it is worse, so we want to make
2118 that less likely. */
2119 reg_n_refs[regno] += loop_depth;
2120 /* Count the increment as a setting of the register,
2121 even though it isn't a SET in rtl. */
2122 reg_n_sets[regno]++;
2128 #endif /* AUTO_INC_DEC */
2130 /* Scan expression X and store a 1-bit in LIVE for each reg it uses.
2131 This is done assuming the registers needed from X
2132 are those that have 1-bits in NEEDED.
2134 On the final pass, FINAL is 1. This means try for autoincrement
2135 and count the uses and deaths of each pseudo-reg.
2137 INSN is the containing instruction. If INSN is dead, this function is not
2141 mark_used_regs (needed, live, x, final, insn)
2148 register RTX_CODE code;
2153 code = GET_CODE (x);
2174 /* Invalidate the data for the last MEM stored. We could do this only
2175 if the addresses conflict, but this doesn't seem worthwhile. */
2180 find_auto_inc (needed, x, insn);
2185 /* See a register other than being set
2186 => mark it as needed. */
2190 register int offset = regno / REGSET_ELT_BITS;
2191 register REGSET_ELT_TYPE bit
2192 = (REGSET_ELT_TYPE) 1 << (regno % REGSET_ELT_BITS);
2193 REGSET_ELT_TYPE all_needed = needed[offset] & bit;
2194 REGSET_ELT_TYPE some_needed = needed[offset] & bit;
2196 live[offset] |= bit;
2197 /* A hard reg in a wide mode may really be multiple registers.
2198 If so, mark all of them just like the first. */
2199 if (regno < FIRST_PSEUDO_REGISTER)
2203 /* For stack ptr or fixed arg pointer,
2204 nothing below can be necessary, so waste no more time. */
2205 if (regno == STACK_POINTER_REGNUM
2206 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
2207 || regno == HARD_FRAME_POINTER_REGNUM
2209 #if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
2210 || (regno == ARG_POINTER_REGNUM && fixed_regs[regno])
2212 || regno == FRAME_POINTER_REGNUM)
2214 /* If this is a register we are going to try to eliminate,
2215 don't mark it live here. If we are successful in
2216 eliminating it, it need not be live unless it is used for
2217 pseudos, in which case it will have been set live when
2218 it was allocated to the pseudos. If the register will not
2219 be eliminated, reload will set it live at that point. */
2221 if (! TEST_HARD_REG_BIT (elim_reg_set, regno))
2222 regs_ever_live[regno] = 1;
2225 /* No death notes for global register variables;
2226 their values are live after this function exits. */
2227 if (global_regs[regno])
2230 reg_next_use[regno] = insn;
2234 n = HARD_REGNO_NREGS (regno, GET_MODE (x));
2237 live[(regno + n) / REGSET_ELT_BITS]
2238 |= (REGSET_ELT_TYPE) 1 << ((regno + n) % REGSET_ELT_BITS);
2240 |= (needed[(regno + n) / REGSET_ELT_BITS]
2241 & (REGSET_ELT_TYPE) 1 << ((regno + n) % REGSET_ELT_BITS));
2243 &= (needed[(regno + n) / REGSET_ELT_BITS]
2244 & (REGSET_ELT_TYPE) 1 << ((regno + n) % REGSET_ELT_BITS));
2249 /* Record where each reg is used, so when the reg
2250 is set we know the next insn that uses it. */
2252 reg_next_use[regno] = insn;
2254 if (regno < FIRST_PSEUDO_REGISTER)
2256 /* If a hard reg is being used,
2257 record that this function does use it. */
2259 i = HARD_REGNO_NREGS (regno, GET_MODE (x));
2263 regs_ever_live[regno + --i] = 1;
2268 /* Keep track of which basic block each reg appears in. */
2270 register int blocknum = BLOCK_NUM (insn);
2272 if (reg_basic_block[regno] == REG_BLOCK_UNKNOWN)
2273 reg_basic_block[regno] = blocknum;
2274 else if (reg_basic_block[regno] != blocknum)
2275 reg_basic_block[regno] = REG_BLOCK_GLOBAL;
2277 /* Count (weighted) number of uses of each reg. */
2279 reg_n_refs[regno] += loop_depth;
2282 /* Record and count the insns in which a reg dies.
2283 If it is used in this insn and was dead below the insn
2284 then it dies in this insn. If it was set in this insn,
2285 we do not make a REG_DEAD note; likewise if we already
2286 made such a note. */
2289 && ! dead_or_set_p (insn, x)
2291 && (regno >= FIRST_PSEUDO_REGISTER || ! fixed_regs[regno])
2295 /* If none of the words in X is needed, make a REG_DEAD
2296 note. Otherwise, we must make partial REG_DEAD notes. */
2300 = gen_rtx (EXPR_LIST, REG_DEAD, x, REG_NOTES (insn));
2301 reg_n_deaths[regno]++;
2307 /* Don't make a REG_DEAD note for a part of a register
2308 that is set in the insn. */
2310 for (i = HARD_REGNO_NREGS (regno, GET_MODE (x)) - 1;
2312 if ((needed[(regno + i) / REGSET_ELT_BITS]
2313 & ((REGSET_ELT_TYPE) 1
2314 << ((regno + i) % REGSET_ELT_BITS))) == 0
2315 && ! dead_or_set_regno_p (insn, regno + i))
2317 = gen_rtx (EXPR_LIST, REG_DEAD,
2318 gen_rtx (REG, word_mode, regno + i),
2328 register rtx testreg = SET_DEST (x);
2331 /* If storing into MEM, don't show it as being used. But do
2332 show the address as being used. */
2333 if (GET_CODE (testreg) == MEM)
2337 find_auto_inc (needed, testreg, insn);
2339 mark_used_regs (needed, live, XEXP (testreg, 0), final, insn);
2340 mark_used_regs (needed, live, SET_SRC (x), final, insn);
2344 /* Storing in STRICT_LOW_PART is like storing in a reg
2345 in that this SET might be dead, so ignore it in TESTREG.
2346 but in some other ways it is like using the reg.
2348 Storing in a SUBREG or a bit field is like storing the entire
2349 register in that if the register's value is not used
2350 then this SET is not needed. */
2351 while (GET_CODE (testreg) == STRICT_LOW_PART
2352 || GET_CODE (testreg) == ZERO_EXTRACT
2353 || GET_CODE (testreg) == SIGN_EXTRACT
2354 || GET_CODE (testreg) == SUBREG)
2356 /* Modifying a single register in an alternate mode
2357 does not use any of the old value. But these other
2358 ways of storing in a register do use the old value. */
2359 if (GET_CODE (testreg) == SUBREG
2360 && !(REG_SIZE (SUBREG_REG (testreg)) > REG_SIZE (testreg)))
2365 testreg = XEXP (testreg, 0);
2368 /* If this is a store into a register,
2369 recursively scan the value being stored. */
2371 if (GET_CODE (testreg) == REG
2372 && (regno = REGNO (testreg), regno != FRAME_POINTER_REGNUM)
2373 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
2374 && regno != HARD_FRAME_POINTER_REGNUM
2376 #if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
2377 && ! (regno == ARG_POINTER_REGNUM && fixed_regs[regno])
2380 /* We used to exclude global_regs here, but that seems wrong.
2381 Storing in them is like storing in mem. */
2383 mark_used_regs (needed, live, SET_SRC (x), final, insn);
2385 mark_used_regs (needed, live, SET_DEST (x), final, insn);
2392 /* If exiting needs the right stack value, consider this insn as
2393 using the stack pointer. In any event, consider it as using
2394 all global registers. */
2396 #ifdef EXIT_IGNORE_STACK
2397 if (! EXIT_IGNORE_STACK
2398 || (! FRAME_POINTER_REQUIRED && flag_omit_frame_pointer))
2400 live[STACK_POINTER_REGNUM / REGSET_ELT_BITS]
2401 |= (REGSET_ELT_TYPE) 1 << (STACK_POINTER_REGNUM % REGSET_ELT_BITS);
2403 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
2405 live[i / REGSET_ELT_BITS]
2406 |= (REGSET_ELT_TYPE) 1 << (i % REGSET_ELT_BITS);
2410 /* Recursively scan the operands of this expression. */
2413 register char *fmt = GET_RTX_FORMAT (code);
2416 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2420 /* Tail recursive case: save a function call level. */
2426 mark_used_regs (needed, live, XEXP (x, i), final, insn);
2428 else if (fmt[i] == 'E')
2431 for (j = 0; j < XVECLEN (x, i); j++)
2432 mark_used_regs (needed, live, XVECEXP (x, i, j), final, insn);
2441 try_pre_increment_1 (insn)
2444 /* Find the next use of this reg. If in same basic block,
2445 make it do pre-increment or pre-decrement if appropriate. */
2446 rtx x = PATTERN (insn);
2447 HOST_WIDE_INT amount = ((GET_CODE (SET_SRC (x)) == PLUS ? 1 : -1)
2448 * INTVAL (XEXP (SET_SRC (x), 1)));
2449 int regno = REGNO (SET_DEST (x));
2450 rtx y = reg_next_use[regno];
2452 && BLOCK_NUM (y) == BLOCK_NUM (insn)
2453 && try_pre_increment (y, SET_DEST (PATTERN (insn)),
2456 /* We have found a suitable auto-increment
2457 and already changed insn Y to do it.
2458 So flush this increment-instruction. */
2459 PUT_CODE (insn, NOTE);
2460 NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
2461 NOTE_SOURCE_FILE (insn) = 0;
2462 /* Count a reference to this reg for the increment
2463 insn we are deleting. When a reg is incremented.
2464 spilling it is worse, so we want to make that
2466 if (regno >= FIRST_PSEUDO_REGISTER)
2468 reg_n_refs[regno] += loop_depth;
2469 reg_n_sets[regno]++;
2476 /* Try to change INSN so that it does pre-increment or pre-decrement
2477 addressing on register REG in order to add AMOUNT to REG.
2478 AMOUNT is negative for pre-decrement.
2479 Returns 1 if the change could be made.
2480 This checks all about the validity of the result of modifying INSN. */
2483 try_pre_increment (insn, reg, amount)
2485 HOST_WIDE_INT amount;
2489 /* Nonzero if we can try to make a pre-increment or pre-decrement.
2490 For example, addl $4,r1; movl (r1),... can become movl +(r1),... */
2492 /* Nonzero if we can try to make a post-increment or post-decrement.
2493 For example, addl $4,r1; movl -4(r1),... can become movl (r1)+,...
2494 It is possible for both PRE_OK and POST_OK to be nonzero if the machine
2495 supports both pre-inc and post-inc, or both pre-dec and post-dec. */
2498 /* Nonzero if the opportunity actually requires post-inc or post-dec. */
2501 /* From the sign of increment, see which possibilities are conceivable
2502 on this target machine. */
2503 #ifdef HAVE_PRE_INCREMENT
2507 #ifdef HAVE_POST_INCREMENT
2512 #ifdef HAVE_PRE_DECREMENT
2516 #ifdef HAVE_POST_DECREMENT
2521 if (! (pre_ok || post_ok))
2524 /* It is not safe to add a side effect to a jump insn
2525 because if the incremented register is spilled and must be reloaded
2526 there would be no way to store the incremented value back in memory. */
2528 if (GET_CODE (insn) == JUMP_INSN)
2533 use = find_use_as_address (PATTERN (insn), reg, 0);
2534 if (post_ok && (use == 0 || use == (rtx) 1))
2536 use = find_use_as_address (PATTERN (insn), reg, -amount);
2540 if (use == 0 || use == (rtx) 1)
2543 if (GET_MODE_SIZE (GET_MODE (use)) != (amount > 0 ? amount : - amount))
2546 XEXP (use, 0) = gen_rtx (amount > 0
2547 ? (do_post ? POST_INC : PRE_INC)
2548 : (do_post ? POST_DEC : PRE_DEC),
2551 /* Record that this insn now has an implicit side effect on X. */
2552 REG_NOTES (insn) = gen_rtx (EXPR_LIST, REG_INC, reg, REG_NOTES (insn));
2556 #endif /* AUTO_INC_DEC */
2558 /* Find the place in the rtx X where REG is used as a memory address.
2559 Return the MEM rtx that so uses it.
2560 If PLUSCONST is nonzero, search instead for a memory address equivalent to
2561 (plus REG (const_int PLUSCONST)).
2563 If such an address does not appear, return 0.
2564 If REG appears more than once, or is used other than in such an address,
2568 find_use_as_address (x, reg, plusconst)
2573 enum rtx_code code = GET_CODE (x);
2574 char *fmt = GET_RTX_FORMAT (code);
2576 register rtx value = 0;
2579 if (code == MEM && XEXP (x, 0) == reg && plusconst == 0)
2582 if (code == MEM && GET_CODE (XEXP (x, 0)) == PLUS
2583 && XEXP (XEXP (x, 0), 0) == reg
2584 && GET_CODE (XEXP (XEXP (x, 0), 1)) == CONST_INT
2585 && INTVAL (XEXP (XEXP (x, 0), 1)) == plusconst)
2588 if (code == SIGN_EXTRACT || code == ZERO_EXTRACT)
2590 /* If REG occurs inside a MEM used in a bit-field reference,
2591 that is unacceptable. */
2592 if (find_use_as_address (XEXP (x, 0), reg, 0) != 0)
2593 return (rtx) (HOST_WIDE_INT) 1;
2597 return (rtx) (HOST_WIDE_INT) 1;
2599 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2603 tem = find_use_as_address (XEXP (x, i), reg, plusconst);
2607 return (rtx) (HOST_WIDE_INT) 1;
2612 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
2614 tem = find_use_as_address (XVECEXP (x, i, j), reg, plusconst);
2618 return (rtx) (HOST_WIDE_INT) 1;
2626 /* Write information about registers and basic blocks into FILE.
2627 This is part of making a debugging dump. */
2630 dump_flow_info (file)
2634 static char *reg_class_names[] = REG_CLASS_NAMES;
2636 fprintf (file, "%d registers.\n", max_regno);
2638 for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
2641 enum reg_class class, altclass;
2642 fprintf (file, "\nRegister %d used %d times across %d insns",
2643 i, reg_n_refs[i], reg_live_length[i]);
2644 if (reg_basic_block[i] >= 0)
2645 fprintf (file, " in block %d", reg_basic_block[i]);
2646 if (reg_n_deaths[i] != 1)
2647 fprintf (file, "; dies in %d places", reg_n_deaths[i]);
2648 if (reg_n_calls_crossed[i] == 1)
2649 fprintf (file, "; crosses 1 call");
2650 else if (reg_n_calls_crossed[i])
2651 fprintf (file, "; crosses %d calls", reg_n_calls_crossed[i]);
2652 if (PSEUDO_REGNO_BYTES (i) != UNITS_PER_WORD)
2653 fprintf (file, "; %d bytes", PSEUDO_REGNO_BYTES (i));
2654 class = reg_preferred_class (i);
2655 altclass = reg_alternate_class (i);
2656 if (class != GENERAL_REGS || altclass != ALL_REGS)
2658 if (altclass == ALL_REGS || class == ALL_REGS)
2659 fprintf (file, "; pref %s", reg_class_names[(int) class]);
2660 else if (altclass == NO_REGS)
2661 fprintf (file, "; %s or none", reg_class_names[(int) class]);
2663 fprintf (file, "; pref %s, else %s",
2664 reg_class_names[(int) class],
2665 reg_class_names[(int) altclass]);
2667 if (REGNO_POINTER_FLAG (i))
2668 fprintf (file, "; pointer");
2669 fprintf (file, ".\n");
2671 fprintf (file, "\n%d basic blocks.\n", n_basic_blocks);
2672 for (i = 0; i < n_basic_blocks; i++)
2674 register rtx head, jump;
2676 fprintf (file, "\nBasic block %d: first insn %d, last %d.\n",
2678 INSN_UID (basic_block_head[i]),
2679 INSN_UID (basic_block_end[i]));
2680 /* The control flow graph's storage is freed
2681 now when flow_analysis returns.
2682 Don't try to print it if it is gone. */
2683 if (basic_block_drops_in)
2685 fprintf (file, "Reached from blocks: ");
2686 head = basic_block_head[i];
2687 if (GET_CODE (head) == CODE_LABEL)
2688 for (jump = LABEL_REFS (head);
2690 jump = LABEL_NEXTREF (jump))
2692 register int from_block = BLOCK_NUM (CONTAINING_INSN (jump));
2693 fprintf (file, " %d", from_block);
2695 if (basic_block_drops_in[i])
2696 fprintf (file, " previous");
2698 fprintf (file, "\nRegisters live at start:");
2699 for (regno = 0; regno < max_regno; regno++)
2701 register int offset = regno / REGSET_ELT_BITS;
2702 register REGSET_ELT_TYPE bit
2703 = (REGSET_ELT_TYPE) 1 << (regno % REGSET_ELT_BITS);
2704 if (basic_block_live_at_start[i][offset] & bit)
2705 fprintf (file, " %d", regno);
2707 fprintf (file, "\n");
2709 fprintf (file, "\n");