1 /* Data flow analysis for GNU compiler.
2 Copyright (C) 1987, 88, 92-96, 1997 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, 59 Temple Place - Suite 330,
19 Boston, MA 02111-1307, USA. */
22 /* This file contains the data flow analysis pass of the compiler.
23 It computes data flow information
24 which tells combine_instructions which insns to consider combining
25 and controls register allocation.
27 Additional data flow information that is too bulky to record
28 is generated during the analysis, and is used at that time to
29 create autoincrement and autodecrement addressing.
31 The first step is dividing the function into basic blocks.
32 find_basic_blocks does this. Then life_analysis determines
33 where each register is live and where it is dead.
35 ** find_basic_blocks **
37 find_basic_blocks divides the current function's rtl
38 into basic blocks. It records the beginnings and ends of the
39 basic blocks in the vectors basic_block_head and basic_block_end,
40 and the number of blocks in n_basic_blocks.
42 find_basic_blocks also finds any unreachable loops
47 life_analysis is called immediately after find_basic_blocks.
48 It uses the basic block information to determine where each
49 hard or pseudo register is live.
51 ** live-register info **
53 The information about where each register is live is in two parts:
54 the REG_NOTES of insns, and the vector basic_block_live_at_start.
56 basic_block_live_at_start has an element for each basic block,
57 and the element is a bit-vector with a bit for each hard or pseudo
58 register. The bit is 1 if the register is live at the beginning
61 Two types of elements can be added to an insn's REG_NOTES.
62 A REG_DEAD note is added to an insn's REG_NOTES for any register
63 that meets both of two conditions: The value in the register is not
64 needed in subsequent insns and the insn does not replace the value in
65 the register (in the case of multi-word hard registers, the value in
66 each register must be replaced by the insn to avoid a REG_DEAD note).
68 In the vast majority of cases, an object in a REG_DEAD note will be
69 used somewhere in the insn. The (rare) exception to this is if an
70 insn uses a multi-word hard register and only some of the registers are
71 needed in subsequent insns. In that case, REG_DEAD notes will be
72 provided for those hard registers that are not subsequently needed.
73 Partial REG_DEAD notes of this type do not occur when an insn sets
74 only some of the hard registers used in such a multi-word operand;
75 omitting REG_DEAD notes for objects stored in an insn is optional and
76 the desire to do so does not justify the complexity of the partial
79 REG_UNUSED notes are added for each register that is set by the insn
80 but is unused subsequently (if every register set by the insn is unused
81 and the insn does not reference memory or have some other side-effect,
82 the insn is deleted instead). If only part of a multi-word hard
83 register is used in a subsequent insn, REG_UNUSED notes are made for
84 the parts that will not be used.
86 To determine which registers are live after any insn, one can
87 start from the beginning of the basic block and scan insns, noting
88 which registers are set by each insn and which die there.
90 ** Other actions of life_analysis **
92 life_analysis sets up the LOG_LINKS fields of insns because the
93 information needed to do so is readily available.
95 life_analysis deletes insns whose only effect is to store a value
98 life_analysis notices cases where a reference to a register as
99 a memory address can be combined with a preceding or following
100 incrementation or decrementation of the register. The separate
101 instruction to increment or decrement is deleted and the address
102 is changed to a POST_INC or similar rtx.
104 Each time an incrementing or decrementing address is created,
105 a REG_INC element is added to the insn's REG_NOTES list.
107 life_analysis fills in certain vectors containing information about
108 register usage: reg_n_refs, reg_n_deaths, reg_n_sets, reg_live_length,
109 reg_n_calls_crosses and reg_basic_block. */
114 #include "basic-block.h"
115 #include "insn-config.h"
117 #include "hard-reg-set.h"
123 #define obstack_chunk_alloc xmalloc
124 #define obstack_chunk_free free
126 /* The contents of the current function definition are allocated
127 in this obstack, and all are freed at the end of the function.
128 For top-level functions, this is temporary_obstack.
129 Separate obstacks are made for nested functions. */
131 extern struct obstack *function_obstack;
133 /* List of labels that must never be deleted. */
134 extern rtx forced_labels;
136 /* Get the basic block number of an insn.
137 This info should not be expected to remain available
138 after the end of life_analysis. */
140 /* This is the limit of the allocated space in the following two arrays. */
142 static int max_uid_for_flow;
144 #define BLOCK_NUM(INSN) uid_block_number[INSN_UID (INSN)]
146 /* This is where the BLOCK_NUM values are really stored.
147 This is set up by find_basic_blocks and used there and in life_analysis,
150 int *uid_block_number;
152 /* INSN_VOLATILE (insn) is 1 if the insn refers to anything volatile. */
154 #define INSN_VOLATILE(INSN) uid_volatile[INSN_UID (INSN)]
155 static char *uid_volatile;
157 /* Number of basic blocks in the current function. */
161 /* Maximum register number used in this function, plus one. */
165 /* Maximum number of SCRATCH rtx's used in any basic block of this
170 /* Number of SCRATCH rtx's in the current block. */
172 static int num_scratch;
174 /* Indexed by n, giving various register information */
176 reg_info *reg_n_info;
178 /* Element N is the next insn that uses (hard or pseudo) register number N
179 within the current basic block; or zero, if there is no such insn.
180 This is valid only during the final backward scan in propagate_block. */
182 static rtx *reg_next_use;
184 /* Size of a regset for the current function,
185 in (1) bytes and (2) elements. */
190 /* Element N is first insn in basic block N.
191 This info lasts until we finish compiling the function. */
193 rtx *basic_block_head;
195 /* Element N is last insn in basic block N.
196 This info lasts until we finish compiling the function. */
198 rtx *basic_block_end;
200 /* Element N is a regset describing the registers live
201 at the start of basic block N.
202 This info lasts until we finish compiling the function. */
204 regset *basic_block_live_at_start;
206 /* Regset of regs live when calls to `setjmp'-like functions happen. */
208 regset regs_live_at_setjmp;
210 /* List made of EXPR_LIST rtx's which gives pairs of pseudo registers
211 that have to go in the same hard reg.
212 The first two regs in the list are a pair, and the next two
213 are another pair, etc. */
216 /* Element N is nonzero if control can drop into basic block N
217 from the preceding basic block. Freed after life_analysis. */
219 static char *basic_block_drops_in;
221 /* Element N is depth within loops of the last insn in basic block number N.
222 Freed after life_analysis. */
224 static short *basic_block_loop_depth;
226 /* Element N nonzero if basic block N can actually be reached.
227 Vector exists only during find_basic_blocks. */
229 static char *block_live_static;
231 /* Depth within loops of basic block being scanned for lifetime analysis,
232 plus one. This is the weight attached to references to registers. */
234 static int loop_depth;
236 /* During propagate_block, this is non-zero if the value of CC0 is live. */
240 /* During propagate_block, this contains the last MEM stored into. It
241 is used to eliminate consecutive stores to the same location. */
243 static rtx last_mem_set;
245 /* Set of registers that may be eliminable. These are handled specially
246 in updating regs_ever_live. */
248 static HARD_REG_SET elim_reg_set;
250 /* Forward declarations */
251 static void find_basic_blocks_1 PROTO((rtx, rtx, int));
252 static void mark_label_ref PROTO((rtx, rtx, int));
253 static void life_analysis_1 PROTO((rtx, int));
254 void allocate_for_life_analysis PROTO((void));
255 void init_regset_vector PROTO((regset *, int, struct obstack *));
256 void free_regset_vector PROTO((regset *, int));
257 static void propagate_block PROTO((regset, rtx, rtx, int,
259 static rtx flow_delete_insn PROTO((rtx));
260 static int insn_dead_p PROTO((rtx, regset, int));
261 static int libcall_dead_p PROTO((rtx, regset, rtx, rtx));
262 static void mark_set_regs PROTO((regset, regset, rtx,
264 static void mark_set_1 PROTO((regset, regset, rtx,
267 static void find_auto_inc PROTO((regset, rtx, rtx));
268 static int try_pre_increment_1 PROTO((rtx));
269 static int try_pre_increment PROTO((rtx, rtx, HOST_WIDE_INT));
271 static void mark_used_regs PROTO((regset, regset, rtx, int, rtx));
272 void dump_flow_info PROTO((FILE *));
273 static void add_pred_succ PROTO ((int, int, int_list_ptr *,
274 int_list_ptr *, int *, int *));
275 static int_list_ptr alloc_int_list_node PROTO ((int_list_block **));
276 static int_list_ptr add_int_list_node PROTO ((int_list_block **,
279 /* Find basic blocks of the current function.
280 F is the first insn of the function and NREGS the number of register numbers
282 LIVE_REACHABLE_P is non-zero if the caller needs all live blocks to
283 be reachable. This turns on a kludge that causes the control flow
284 information to be inaccurate and not suitable for passes like GCSE. */
287 find_basic_blocks (f, nregs, file, live_reachable_p)
291 int live_reachable_p;
295 rtx nonlocal_label_list = nonlocal_label_rtx_list ();
296 int in_libcall_block = 0;
298 /* Count the basic blocks. Also find maximum insn uid value used. */
301 register RTX_CODE prev_code = JUMP_INSN;
302 register RTX_CODE code;
305 max_uid_for_flow = 0;
307 for (insn = f, i = 0; insn; insn = NEXT_INSN (insn))
310 /* Track when we are inside in LIBCALL block. */
311 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
312 && find_reg_note (insn, REG_LIBCALL, NULL_RTX))
313 in_libcall_block = 1;
315 code = GET_CODE (insn);
316 if (INSN_UID (insn) > max_uid_for_flow)
317 max_uid_for_flow = INSN_UID (insn);
318 if (code == CODE_LABEL
319 || (GET_RTX_CLASS (code) == 'i'
320 && (prev_code == JUMP_INSN
321 || (prev_code == CALL_INSN
322 && (nonlocal_label_list != 0 || eh_region)
323 && ! in_libcall_block)
324 || prev_code == BARRIER)))
327 if (code == CALL_INSN && find_reg_note (insn, REG_RETVAL, NULL_RTX))
332 else if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_BEG)
334 else if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_END)
337 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
338 && find_reg_note (insn, REG_RETVAL, NULL_RTX))
339 in_libcall_block = 0;
346 /* Leave space for insns life_analysis makes in some cases for auto-inc.
347 These cases are rare, so we don't need too much space. */
348 max_uid_for_flow += max_uid_for_flow / 10;
351 /* Allocate some tables that last till end of compiling this function
352 and some needed only in find_basic_blocks and life_analysis. */
354 basic_block_head = (rtx *) xmalloc (n_basic_blocks * sizeof (rtx));
355 basic_block_end = (rtx *) xmalloc (n_basic_blocks * sizeof (rtx));
356 basic_block_drops_in = (char *) xmalloc (n_basic_blocks);
357 basic_block_loop_depth = (short *) xmalloc (n_basic_blocks * sizeof (short));
359 = (int *) xmalloc ((max_uid_for_flow + 1) * sizeof (int));
360 uid_volatile = (char *) xmalloc (max_uid_for_flow + 1);
361 bzero (uid_volatile, max_uid_for_flow + 1);
363 find_basic_blocks_1 (f, nonlocal_label_list, live_reachable_p);
366 /* Find all basic blocks of the function whose first insn is F.
367 Store the correct data in the tables that describe the basic blocks,
368 set up the chains of references for each CODE_LABEL, and
369 delete any entire basic blocks that cannot be reached.
371 NONLOCAL_LABEL_LIST is a list of non-local labels in the function.
372 Blocks that are otherwise unreachable may be reachable with a non-local
374 LIVE_REACHABLE_P is non-zero if the caller needs all live blocks to
375 be reachable. This turns on a kludge that causes the control flow
376 information to be inaccurate and not suitable for passes like GCSE. */
379 find_basic_blocks_1 (f, nonlocal_label_list, live_reachable_p)
380 rtx f, nonlocal_label_list;
381 int live_reachable_p;
385 register char *block_live = (char *) alloca (n_basic_blocks);
386 register char *block_marked = (char *) alloca (n_basic_blocks);
387 /* An array of CODE_LABELs, indexed by UID for the start of the active
388 EH handler for each insn in F. */
389 rtx *active_eh_handler;
390 /* List of label_refs to all labels whose addresses are taken
392 rtx label_value_list;
393 rtx x, note, eh_note;
394 enum rtx_code prev_code, code;
396 int in_libcall_block = 0;
399 active_eh_handler = (rtx *) alloca ((max_uid_for_flow + 1) * sizeof (rtx));
402 label_value_list = 0;
403 block_live_static = block_live;
404 bzero (block_live, n_basic_blocks);
405 bzero (block_marked, n_basic_blocks);
406 bzero (active_eh_handler, (max_uid_for_flow + 1) * sizeof (rtx));
408 /* Initialize with just block 0 reachable and no blocks marked. */
409 if (n_basic_blocks > 0)
412 /* Initialize the ref chain of each label to 0. Record where all the
413 blocks start and end and their depth in loops. For each insn, record
414 the block it is in. Also mark as reachable any blocks headed by labels
415 that must not be deleted. */
417 for (eh_note = NULL_RTX, insn = f, i = -1, prev_code = JUMP_INSN, depth = 1;
418 insn; insn = NEXT_INSN (insn))
421 /* Track when we are inside in LIBCALL block. */
422 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
423 && find_reg_note (insn, REG_LIBCALL, NULL_RTX))
424 in_libcall_block = 1;
426 code = GET_CODE (insn);
429 if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG)
431 else if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END)
435 /* A basic block starts at label, or after something that can jump. */
436 else if (code == CODE_LABEL
437 || (GET_RTX_CLASS (code) == 'i'
438 && (prev_code == JUMP_INSN
439 || (prev_code == CALL_INSN
440 && (nonlocal_label_list != 0 || eh_note)
441 && ! in_libcall_block)
442 || prev_code == BARRIER)))
444 basic_block_head[++i] = insn;
445 basic_block_end[i] = insn;
446 basic_block_loop_depth[i] = depth;
448 if (code == CODE_LABEL)
450 LABEL_REFS (insn) = insn;
451 /* Any label that cannot be deleted
452 is considered to start a reachable block. */
453 if (LABEL_PRESERVE_P (insn))
458 else if (GET_RTX_CLASS (code) == 'i')
460 basic_block_end[i] = insn;
461 basic_block_loop_depth[i] = depth;
464 if (GET_RTX_CLASS (code) == 'i')
466 /* Make a list of all labels referred to other than by jumps. */
467 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
468 if (REG_NOTE_KIND (note) == REG_LABEL)
469 label_value_list = gen_rtx_EXPR_LIST (VOIDmode, XEXP (note, 0),
473 /* Keep a lifo list of the currently active exception handlers. */
474 if (GET_CODE (insn) == NOTE)
476 if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_BEG)
478 for (x = exception_handler_labels; x; x = XEXP (x, 1))
479 if (CODE_LABEL_NUMBER (XEXP (x, 0)) == NOTE_BLOCK_NUMBER (insn))
481 eh_note = gen_rtx_EXPR_LIST (VOIDmode,
482 XEXP (x, 0), eh_note);
488 else if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_END)
489 eh_note = XEXP (eh_note, 1);
491 /* If we encounter a CALL_INSN, note which exception handler it
492 might pass control to.
494 If doing asynchronous exceptions, record the active EH handler
495 for every insn, since most insns can throw. */
497 && (asynchronous_exceptions
498 || (GET_CODE (insn) == CALL_INSN
499 && ! in_libcall_block)))
500 active_eh_handler[INSN_UID (insn)] = XEXP (eh_note, 0);
502 BLOCK_NUM (insn) = i;
507 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
508 && find_reg_note (insn, REG_RETVAL, NULL_RTX))
509 in_libcall_block = 0;
512 /* During the second pass, `n_basic_blocks' is only an upper bound.
513 Only perform the sanity check for the first pass, and on the second
514 pass ensure `n_basic_blocks' is set to the correct value. */
515 if (pass == 1 && i + 1 != n_basic_blocks)
517 n_basic_blocks = i + 1;
519 /* Record which basic blocks control can drop in to. */
521 for (i = 0; i < n_basic_blocks; i++)
523 for (insn = PREV_INSN (basic_block_head[i]);
524 insn && GET_CODE (insn) == NOTE; insn = PREV_INSN (insn))
527 basic_block_drops_in[i] = insn && GET_CODE (insn) != BARRIER;
530 /* Now find which basic blocks can actually be reached
531 and put all jump insns' LABEL_REFS onto the ref-chains
532 of their target labels. */
534 if (n_basic_blocks > 0)
536 int something_marked = 1;
539 /* Pass over all blocks, marking each block that is reachable
540 and has not yet been marked.
541 Keep doing this until, in one pass, no blocks have been marked.
542 Then blocks_live and blocks_marked are identical and correct.
543 In addition, all jumps actually reachable have been marked. */
545 while (something_marked)
547 something_marked = 0;
548 for (i = 0; i < n_basic_blocks; i++)
549 if (block_live[i] && !block_marked[i])
552 something_marked = 1;
553 if (i + 1 < n_basic_blocks && basic_block_drops_in[i + 1])
554 block_live[i + 1] = 1;
555 insn = basic_block_end[i];
556 if (GET_CODE (insn) == JUMP_INSN)
557 mark_label_ref (PATTERN (insn), insn, 0);
559 /* If we have any forced labels, mark them as potentially
560 reachable from this block. */
561 for (x = forced_labels; x; x = XEXP (x, 1))
562 if (! LABEL_REF_NONLOCAL_P (x))
563 mark_label_ref (gen_rtx_LABEL_REF (VOIDmode, XEXP (x, 0)),
566 /* Now scan the insns for this block, we may need to make
567 edges for some of them to various non-obvious locations
568 (exception handlers, nonlocal labels, etc). */
569 for (insn = basic_block_head[i];
570 insn != NEXT_INSN (basic_block_end[i]);
571 insn = NEXT_INSN (insn))
573 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
576 /* References to labels in non-jumping insns have
577 REG_LABEL notes attached to them.
579 This can happen for computed gotos; we don't care
580 about them here since the values are also on the
581 label_value_list and will be marked live if we find
582 a live computed goto.
584 This can also happen when we take the address of
585 a label to pass as an argument to __throw. Note
586 throw only uses the value to determine what handler
587 should be called -- ie the label is not used as
588 a jump target, it just marks regions in the code.
590 In theory we should be able to ignore the REG_LABEL
591 notes, but we have to make sure that the label and
592 associated insns aren't marked dead, so we make
593 the block in question live and create an edge from
594 this insn to the label. This is not strictly
595 correct, but it is close enough for now. */
596 for (note = REG_NOTES (insn);
598 note = XEXP (note, 1))
600 if (REG_NOTE_KIND (note) == REG_LABEL)
603 block_live[BLOCK_NUM (x)] = 1;
604 mark_label_ref (gen_rtx_LABEL_REF (VOIDmode, x),
609 /* If this is a computed jump, then mark it as
610 reaching everything on the label_value_list
611 and forced_labels list. */
612 if (computed_jump_p (insn))
614 for (x = label_value_list; x; x = XEXP (x, 1))
615 mark_label_ref (gen_rtx_LABEL_REF (VOIDmode,
619 for (x = forced_labels; x; x = XEXP (x, 1))
620 mark_label_ref (gen_rtx_LABEL_REF (VOIDmode,
625 /* If this is a CALL_INSN, then mark it as reaching
626 the active EH handler for this CALL_INSN. If
627 we're handling asynchronous exceptions mark every
628 insn as reaching the active EH handler.
630 Also mark the CALL_INSN as reaching any nonlocal
632 else if (asynchronous_exceptions
633 || (GET_CODE (insn) == CALL_INSN
634 && ! find_reg_note (insn, REG_RETVAL,
637 if (active_eh_handler[INSN_UID (insn)])
638 mark_label_ref (gen_rtx_LABEL_REF (VOIDmode,
639 active_eh_handler[INSN_UID (insn)]),
642 if (!asynchronous_exceptions)
644 for (x = nonlocal_label_list;
647 mark_label_ref (gen_rtx_LABEL_REF (VOIDmode,
651 /* ??? This could be made smarter:
652 in some cases it's possible to tell that
653 certain calls will not do a nonlocal goto.
655 For example, if the nested functions that
656 do the nonlocal gotos do not have their
657 addresses taken, then only calls to those
658 functions or to other nested functions that
659 use them could possibly do nonlocal gotos. */
666 /* This should never happen. If it does that means we've computed an
667 incorrect flow graph, which can lead to aborts/crashes later in the
668 compiler or incorrect code generation.
670 We used to try and continue here, but that's just asking for trouble
671 later during the compile or at runtime. It's easier to debug the
672 problem here than later! */
673 for (i = 1; i < n_basic_blocks; i++)
674 if (block_live[i] && ! basic_block_drops_in[i]
675 && GET_CODE (basic_block_head[i]) == CODE_LABEL
676 && LABEL_REFS (basic_block_head[i]) == basic_block_head[i])
679 /* Now delete the code for any basic blocks that can't be reached.
680 They can occur because jump_optimize does not recognize
683 /* Now delete the code for any basic blocks that can't be reached.
684 They can occur because jump_optimize does not recognize
685 unreachable loops as unreachable. */
688 for (i = 0; i < n_basic_blocks; i++)
693 /* Delete the insns in a (non-live) block. We physically delete
694 every non-note insn except the start and end (so
695 basic_block_head/end needn't be updated), we turn the latter
696 into NOTE_INSN_DELETED notes.
697 We use to "delete" the insns by turning them into notes, but
698 we may be deleting lots of insns that subsequent passes would
699 otherwise have to process. Secondly, lots of deleted blocks in
700 a row can really slow down propagate_block since it will
701 otherwise process insn-turned-notes multiple times when it
702 looks for loop begin/end notes. */
703 if (basic_block_head[i] != basic_block_end[i])
705 /* It would be quicker to delete all of these with a single
706 unchaining, rather than one at a time, but we need to keep
708 insn = NEXT_INSN (basic_block_head[i]);
709 while (insn != basic_block_end[i])
711 if (GET_CODE (insn) == BARRIER)
713 else if (GET_CODE (insn) != NOTE)
714 insn = flow_delete_insn (insn);
716 insn = NEXT_INSN (insn);
719 insn = basic_block_head[i];
720 if (GET_CODE (insn) != NOTE)
722 /* Turn the head into a deleted insn note. */
723 if (GET_CODE (insn) == BARRIER)
726 /* If the head of this block is a CODE_LABEL, then it might
727 be the label for an exception handler which can't be
730 We need to remove the label from the exception_handler_label
731 list and remove the associated NOTE_EH_REGION_BEG and
732 NOTE_EH_REGION_END notes. */
733 if (GET_CODE (insn) == CODE_LABEL)
735 rtx x, *prev = &exception_handler_labels;
737 for (x = exception_handler_labels; x; x = XEXP (x, 1))
739 if (XEXP (x, 0) == insn)
741 /* Found a match, splice this label out of the
744 XEXP (x, 1) = NULL_RTX;
745 XEXP (x, 0) = NULL_RTX;
747 /* Now we have to find the EH_BEG and EH_END notes
748 associated with this label and remove them. */
750 for (x = get_insns (); x; x = NEXT_INSN (x))
752 if (GET_CODE (x) == NOTE
753 && ((NOTE_LINE_NUMBER (x)
754 == NOTE_INSN_EH_REGION_BEG)
755 || (NOTE_LINE_NUMBER (x)
756 == NOTE_INSN_EH_REGION_END))
757 && (NOTE_BLOCK_NUMBER (x)
758 == CODE_LABEL_NUMBER (insn)))
760 NOTE_LINE_NUMBER (x) = NOTE_INSN_DELETED;
761 NOTE_SOURCE_FILE (x) = 0;
770 PUT_CODE (insn, NOTE);
771 NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
772 NOTE_SOURCE_FILE (insn) = 0;
774 insn = basic_block_end[i];
775 if (GET_CODE (insn) != NOTE)
777 /* Turn the tail into a deleted insn note. */
778 if (GET_CODE (insn) == BARRIER)
780 PUT_CODE (insn, NOTE);
781 NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
782 NOTE_SOURCE_FILE (insn) = 0;
784 /* BARRIERs are between basic blocks, not part of one.
785 Delete a BARRIER if the preceding jump is deleted.
786 We cannot alter a BARRIER into a NOTE
787 because it is too short; but we can really delete
788 it because it is not part of a basic block. */
789 if (NEXT_INSN (insn) != 0
790 && GET_CODE (NEXT_INSN (insn)) == BARRIER)
791 delete_insn (NEXT_INSN (insn));
793 /* Each time we delete some basic blocks,
794 see if there is a jump around them that is
795 being turned into a no-op. If so, delete it. */
797 if (block_live[i - 1])
800 for (j = i + 1; j < n_basic_blocks; j++)
804 insn = basic_block_end[i - 1];
805 if (GET_CODE (insn) == JUMP_INSN
806 /* An unconditional jump is the only possibility
807 we must check for, since a conditional one
808 would make these blocks live. */
809 && simplejump_p (insn)
810 && (label = XEXP (SET_SRC (PATTERN (insn)), 0), 1)
811 && INSN_UID (label) != 0
812 && BLOCK_NUM (label) == j)
814 PUT_CODE (insn, NOTE);
815 NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
816 NOTE_SOURCE_FILE (insn) = 0;
817 if (GET_CODE (NEXT_INSN (insn)) != BARRIER)
819 delete_insn (NEXT_INSN (insn));
826 /* There are pathological cases where one function calling hundreds of
827 nested inline functions can generate lots and lots of unreachable
828 blocks that jump can't delete. Since we don't use sparse matrices
829 a lot of memory will be needed to compile such functions.
830 Implementing sparse matrices is a fair bit of work and it is not
831 clear that they win more than they lose (we don't want to
832 unnecessarily slow down compilation of normal code). By making
833 another pass for the pathological case, we can greatly speed up
834 their compilation without hurting normal code. This works because
835 all the insns in the unreachable blocks have either been deleted or
837 Note that we're talking about reducing memory usage by 10's of
838 megabytes and reducing compilation time by several minutes. */
839 /* ??? The choice of when to make another pass is a bit arbitrary,
840 and was derived from empirical data. */
845 n_basic_blocks -= deleted;
846 /* `n_basic_blocks' may not be correct at this point: two previously
847 separate blocks may now be merged. That's ok though as we
848 recalculate it during the second pass. It certainly can't be
849 any larger than the current value. */
855 /* Record INSN's block number as BB. */
858 set_block_num (insn, bb)
862 if (INSN_UID (insn) >= max_uid_for_flow)
864 /* Add one-eighth the size so we don't keep calling xrealloc. */
865 max_uid_for_flow = INSN_UID (insn) + (INSN_UID (insn) + 7) / 8;
866 uid_block_number = (int *)
867 xrealloc (uid_block_number, (max_uid_for_flow + 1) * sizeof (int));
869 BLOCK_NUM (insn) = bb;
873 /* Subroutines of find_basic_blocks. */
875 /* Check expression X for label references;
876 if one is found, add INSN to the label's chain of references.
878 CHECKDUP means check for and avoid creating duplicate references
879 from the same insn. Such duplicates do no serious harm but
880 can slow life analysis. CHECKDUP is set only when duplicates
884 mark_label_ref (x, insn, checkdup)
888 register RTX_CODE code;
892 /* We can be called with NULL when scanning label_value_list. */
897 if (code == LABEL_REF)
899 register rtx label = XEXP (x, 0);
901 if (GET_CODE (label) != CODE_LABEL)
903 /* If the label was never emitted, this insn is junk,
904 but avoid a crash trying to refer to BLOCK_NUM (label).
905 This can happen as a result of a syntax error
906 and a diagnostic has already been printed. */
907 if (INSN_UID (label) == 0)
909 CONTAINING_INSN (x) = insn;
910 /* if CHECKDUP is set, check for duplicate ref from same insn
913 for (y = LABEL_REFS (label); y != label; y = LABEL_NEXTREF (y))
914 if (CONTAINING_INSN (y) == insn)
916 LABEL_NEXTREF (x) = LABEL_REFS (label);
917 LABEL_REFS (label) = x;
918 block_live_static[BLOCK_NUM (label)] = 1;
922 fmt = GET_RTX_FORMAT (code);
923 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
926 mark_label_ref (XEXP (x, i), insn, 0);
930 for (j = 0; j < XVECLEN (x, i); j++)
931 mark_label_ref (XVECEXP (x, i, j), insn, 1);
936 /* Delete INSN by patching it out.
937 Return the next insn. */
940 flow_delete_insn (insn)
943 /* ??? For the moment we assume we don't have to watch for NULLs here
944 since the start/end of basic blocks aren't deleted like this. */
945 NEXT_INSN (PREV_INSN (insn)) = NEXT_INSN (insn);
946 PREV_INSN (NEXT_INSN (insn)) = PREV_INSN (insn);
947 return NEXT_INSN (insn);
950 /* Perform data flow analysis.
951 F is the first insn of the function and NREGS the number of register numbers
955 life_analysis (f, nregs, file)
963 #ifdef ELIMINABLE_REGS
964 static struct {int from, to; } eliminables[] = ELIMINABLE_REGS;
967 /* Record which registers will be eliminated. We use this in
970 CLEAR_HARD_REG_SET (elim_reg_set);
972 #ifdef ELIMINABLE_REGS
973 for (i = 0; i < sizeof eliminables / sizeof eliminables[0]; i++)
974 SET_HARD_REG_BIT (elim_reg_set, eliminables[i].from);
976 SET_HARD_REG_BIT (elim_reg_set, FRAME_POINTER_REGNUM);
979 life_analysis_1 (f, nregs);
981 dump_flow_info (file);
983 free_basic_block_vars (1);
986 /* Free the variables allocated by find_basic_blocks.
988 KEEP_HEAD_END_P is non-zero if basic_block_head and basic_block_end
989 are not to be freed. */
992 free_basic_block_vars (keep_head_end_p)
995 if (basic_block_drops_in)
997 free (basic_block_drops_in);
998 /* Tell dump_flow_info this isn't available anymore. */
999 basic_block_drops_in = 0;
1001 if (basic_block_loop_depth)
1003 free (basic_block_loop_depth);
1004 basic_block_loop_depth = 0;
1006 if (uid_block_number)
1008 free (uid_block_number);
1009 uid_block_number = 0;
1013 free (uid_volatile);
1017 if (! keep_head_end_p && basic_block_head)
1019 free (basic_block_head);
1020 basic_block_head = 0;
1021 free (basic_block_end);
1022 basic_block_end = 0;
1026 /* Determine which registers are live at the start of each
1027 basic block of the function whose first insn is F.
1028 NREGS is the number of registers used in F.
1029 We allocate the vector basic_block_live_at_start
1030 and the regsets that it points to, and fill them with the data.
1031 regset_size and regset_bytes are also set here. */
1034 life_analysis_1 (f, nregs)
1040 /* For each basic block, a bitmask of regs
1041 live on exit from the block. */
1042 regset *basic_block_live_at_end;
1043 /* For each basic block, a bitmask of regs
1044 live on entry to a successor-block of this block.
1045 If this does not match basic_block_live_at_end,
1046 that must be updated, and the block must be rescanned. */
1047 regset *basic_block_new_live_at_end;
1048 /* For each basic block, a bitmask of regs
1049 whose liveness at the end of the basic block
1050 can make a difference in which regs are live on entry to the block.
1051 These are the regs that are set within the basic block,
1052 possibly excluding those that are used after they are set. */
1053 regset *basic_block_significant;
1057 struct obstack flow_obstack;
1059 gcc_obstack_init (&flow_obstack);
1063 bzero (regs_ever_live, sizeof regs_ever_live);
1065 /* Allocate and zero out many data structures
1066 that will record the data from lifetime analysis. */
1068 allocate_for_life_analysis ();
1070 reg_next_use = (rtx *) alloca (nregs * sizeof (rtx));
1071 bzero ((char *) reg_next_use, nregs * sizeof (rtx));
1073 /* Set up several regset-vectors used internally within this function.
1074 Their meanings are documented above, with their declarations. */
1076 basic_block_live_at_end
1077 = (regset *) alloca (n_basic_blocks * sizeof (regset));
1079 /* Don't use alloca since that leads to a crash rather than an error message
1080 if there isn't enough space.
1081 Don't use oballoc since we may need to allocate other things during
1082 this function on the temporary obstack. */
1083 init_regset_vector (basic_block_live_at_end, n_basic_blocks, &flow_obstack);
1085 basic_block_new_live_at_end
1086 = (regset *) alloca (n_basic_blocks * sizeof (regset));
1087 init_regset_vector (basic_block_new_live_at_end, n_basic_blocks,
1090 basic_block_significant
1091 = (regset *) alloca (n_basic_blocks * sizeof (regset));
1092 init_regset_vector (basic_block_significant, n_basic_blocks, &flow_obstack);
1094 /* Record which insns refer to any volatile memory
1095 or for any reason can't be deleted just because they are dead stores.
1096 Also, delete any insns that copy a register to itself. */
1098 for (insn = f; insn; insn = NEXT_INSN (insn))
1100 enum rtx_code code1 = GET_CODE (insn);
1101 if (code1 == CALL_INSN)
1102 INSN_VOLATILE (insn) = 1;
1103 else if (code1 == INSN || code1 == JUMP_INSN)
1105 /* Delete (in effect) any obvious no-op moves. */
1106 if (GET_CODE (PATTERN (insn)) == SET
1107 && GET_CODE (SET_DEST (PATTERN (insn))) == REG
1108 && GET_CODE (SET_SRC (PATTERN (insn))) == REG
1109 && (REGNO (SET_DEST (PATTERN (insn)))
1110 == REGNO (SET_SRC (PATTERN (insn))))
1111 /* Insns carrying these notes are useful later on. */
1112 && ! find_reg_note (insn, REG_EQUAL, NULL_RTX))
1114 PUT_CODE (insn, NOTE);
1115 NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
1116 NOTE_SOURCE_FILE (insn) = 0;
1118 /* Delete (in effect) any obvious no-op moves. */
1119 else if (GET_CODE (PATTERN (insn)) == SET
1120 && GET_CODE (SET_DEST (PATTERN (insn))) == SUBREG
1121 && GET_CODE (SUBREG_REG (SET_DEST (PATTERN (insn)))) == REG
1122 && GET_CODE (SET_SRC (PATTERN (insn))) == SUBREG
1123 && GET_CODE (SUBREG_REG (SET_SRC (PATTERN (insn)))) == REG
1124 && (REGNO (SUBREG_REG (SET_DEST (PATTERN (insn))))
1125 == REGNO (SUBREG_REG (SET_SRC (PATTERN (insn)))))
1126 && SUBREG_WORD (SET_DEST (PATTERN (insn))) ==
1127 SUBREG_WORD (SET_SRC (PATTERN (insn)))
1128 /* Insns carrying these notes are useful later on. */
1129 && ! find_reg_note (insn, REG_EQUAL, NULL_RTX))
1131 PUT_CODE (insn, NOTE);
1132 NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
1133 NOTE_SOURCE_FILE (insn) = 0;
1135 else if (GET_CODE (PATTERN (insn)) == PARALLEL)
1137 /* If nothing but SETs of registers to themselves,
1138 this insn can also be deleted. */
1139 for (i = 0; i < XVECLEN (PATTERN (insn), 0); i++)
1141 rtx tem = XVECEXP (PATTERN (insn), 0, i);
1143 if (GET_CODE (tem) == USE
1144 || GET_CODE (tem) == CLOBBER)
1147 if (GET_CODE (tem) != SET
1148 || GET_CODE (SET_DEST (tem)) != REG
1149 || GET_CODE (SET_SRC (tem)) != REG
1150 || REGNO (SET_DEST (tem)) != REGNO (SET_SRC (tem)))
1154 if (i == XVECLEN (PATTERN (insn), 0)
1155 /* Insns carrying these notes are useful later on. */
1156 && ! find_reg_note (insn, REG_EQUAL, NULL_RTX))
1158 PUT_CODE (insn, NOTE);
1159 NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
1160 NOTE_SOURCE_FILE (insn) = 0;
1163 INSN_VOLATILE (insn) = volatile_refs_p (PATTERN (insn));
1165 else if (GET_CODE (PATTERN (insn)) != USE)
1166 INSN_VOLATILE (insn) = volatile_refs_p (PATTERN (insn));
1167 /* A SET that makes space on the stack cannot be dead.
1168 (Such SETs occur only for allocating variable-size data,
1169 so they will always have a PLUS or MINUS according to the
1170 direction of stack growth.)
1171 Even if this function never uses this stack pointer value,
1172 signal handlers do! */
1173 else if (code1 == INSN && GET_CODE (PATTERN (insn)) == SET
1174 && SET_DEST (PATTERN (insn)) == stack_pointer_rtx
1175 #ifdef STACK_GROWS_DOWNWARD
1176 && GET_CODE (SET_SRC (PATTERN (insn))) == MINUS
1178 && GET_CODE (SET_SRC (PATTERN (insn))) == PLUS
1180 && XEXP (SET_SRC (PATTERN (insn)), 0) == stack_pointer_rtx)
1181 INSN_VOLATILE (insn) = 1;
1185 if (n_basic_blocks > 0)
1186 #ifdef EXIT_IGNORE_STACK
1187 if (! EXIT_IGNORE_STACK
1188 || (! FRAME_POINTER_REQUIRED
1189 && ! current_function_calls_alloca
1190 && flag_omit_frame_pointer))
1193 /* If exiting needs the right stack value,
1194 consider the stack pointer live at the end of the function. */
1195 SET_REGNO_REG_SET (basic_block_live_at_end[n_basic_blocks - 1],
1196 STACK_POINTER_REGNUM);
1197 SET_REGNO_REG_SET (basic_block_new_live_at_end[n_basic_blocks - 1],
1198 STACK_POINTER_REGNUM);
1201 /* Mark the frame pointer is needed at the end of the function. If
1202 we end up eliminating it, it will be removed from the live list
1203 of each basic block by reload. */
1205 if (n_basic_blocks > 0)
1207 SET_REGNO_REG_SET (basic_block_live_at_end[n_basic_blocks - 1],
1208 FRAME_POINTER_REGNUM);
1209 SET_REGNO_REG_SET (basic_block_new_live_at_end[n_basic_blocks - 1],
1210 FRAME_POINTER_REGNUM);
1211 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
1212 /* If they are different, also mark the hard frame pointer as live */
1213 SET_REGNO_REG_SET (basic_block_live_at_end[n_basic_blocks - 1],
1214 HARD_FRAME_POINTER_REGNUM);
1215 SET_REGNO_REG_SET (basic_block_new_live_at_end[n_basic_blocks - 1],
1216 HARD_FRAME_POINTER_REGNUM);
1220 /* Mark all global registers and all registers used by the epilogue
1221 as being live at the end of the function since they may be
1222 referenced by our caller. */
1224 if (n_basic_blocks > 0)
1225 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1227 #ifdef EPILOGUE_USES
1228 || EPILOGUE_USES (i)
1232 SET_REGNO_REG_SET (basic_block_live_at_end[n_basic_blocks - 1], i);
1233 SET_REGNO_REG_SET (basic_block_new_live_at_end[n_basic_blocks - 1], i);
1236 /* Propagate life info through the basic blocks
1237 around the graph of basic blocks.
1239 This is a relaxation process: each time a new register
1240 is live at the end of the basic block, we must scan the block
1241 to determine which registers are, as a consequence, live at the beginning
1242 of that block. These registers must then be marked live at the ends
1243 of all the blocks that can transfer control to that block.
1244 The process continues until it reaches a fixed point. */
1251 for (i = n_basic_blocks - 1; i >= 0; i--)
1253 int consider = first_pass;
1254 int must_rescan = first_pass;
1259 /* Set CONSIDER if this block needs thinking about at all
1260 (that is, if the regs live now at the end of it
1261 are not the same as were live at the end of it when
1262 we last thought about it).
1263 Set must_rescan if it needs to be thought about
1264 instruction by instruction (that is, if any additional
1265 reg that is live at the end now but was not live there before
1266 is one of the significant regs of this basic block). */
1268 EXECUTE_IF_AND_COMPL_IN_REG_SET
1269 (basic_block_new_live_at_end[i],
1270 basic_block_live_at_end[i], 0, j,
1273 if (REGNO_REG_SET_P (basic_block_significant[i], j))
1284 /* The live_at_start of this block may be changing,
1285 so another pass will be required after this one. */
1290 /* No complete rescan needed;
1291 just record those variables newly known live at end
1292 as live at start as well. */
1293 IOR_AND_COMPL_REG_SET (basic_block_live_at_start[i],
1294 basic_block_new_live_at_end[i],
1295 basic_block_live_at_end[i]);
1297 IOR_AND_COMPL_REG_SET (basic_block_live_at_end[i],
1298 basic_block_new_live_at_end[i],
1299 basic_block_live_at_end[i]);
1303 /* Update the basic_block_live_at_start
1304 by propagation backwards through the block. */
1305 COPY_REG_SET (basic_block_live_at_end[i],
1306 basic_block_new_live_at_end[i]);
1307 COPY_REG_SET (basic_block_live_at_start[i],
1308 basic_block_live_at_end[i]);
1309 propagate_block (basic_block_live_at_start[i],
1310 basic_block_head[i], basic_block_end[i], 0,
1311 first_pass ? basic_block_significant[i]
1317 register rtx jump, head;
1319 /* Update the basic_block_new_live_at_end's of the block
1320 that falls through into this one (if any). */
1321 head = basic_block_head[i];
1322 if (basic_block_drops_in[i])
1323 IOR_REG_SET (basic_block_new_live_at_end[i-1],
1324 basic_block_live_at_start[i]);
1326 /* Update the basic_block_new_live_at_end's of
1327 all the blocks that jump to this one. */
1328 if (GET_CODE (head) == CODE_LABEL)
1329 for (jump = LABEL_REFS (head);
1331 jump = LABEL_NEXTREF (jump))
1333 register int from_block = BLOCK_NUM (CONTAINING_INSN (jump));
1334 IOR_REG_SET (basic_block_new_live_at_end[from_block],
1335 basic_block_live_at_start[i]);
1345 /* The only pseudos that are live at the beginning of the function are
1346 those that were not set anywhere in the function. local-alloc doesn't
1347 know how to handle these correctly, so mark them as not local to any
1350 if (n_basic_blocks > 0)
1351 EXECUTE_IF_SET_IN_REG_SET (basic_block_live_at_start[0],
1352 FIRST_PSEUDO_REGISTER, i,
1354 REG_BASIC_BLOCK (i) = REG_BLOCK_GLOBAL;
1357 /* Now the life information is accurate.
1358 Make one more pass over each basic block
1359 to delete dead stores, create autoincrement addressing
1360 and record how many times each register is used, is set, or dies.
1362 To save time, we operate directly in basic_block_live_at_end[i],
1363 thus destroying it (in fact, converting it into a copy of
1364 basic_block_live_at_start[i]). This is ok now because
1365 basic_block_live_at_end[i] is no longer used past this point. */
1369 for (i = 0; i < n_basic_blocks; i++)
1371 propagate_block (basic_block_live_at_end[i],
1372 basic_block_head[i], basic_block_end[i], 1,
1380 /* Something live during a setjmp should not be put in a register
1381 on certain machines which restore regs from stack frames
1382 rather than from the jmpbuf.
1383 But we don't need to do this for the user's variables, since
1384 ANSI says only volatile variables need this. */
1385 #ifdef LONGJMP_RESTORE_FROM_STACK
1386 EXECUTE_IF_SET_IN_REG_SET (regs_live_at_setjmp,
1387 FIRST_PSEUDO_REGISTER, i,
1389 if (regno_reg_rtx[i] != 0
1390 && ! REG_USERVAR_P (regno_reg_rtx[i]))
1392 REG_LIVE_LENGTH (i) = -1;
1393 REG_BASIC_BLOCK (i) = -1;
1399 /* We have a problem with any pseudoreg that
1400 lives across the setjmp. ANSI says that if a
1401 user variable does not change in value
1402 between the setjmp and the longjmp, then the longjmp preserves it.
1403 This includes longjmp from a place where the pseudo appears dead.
1404 (In principle, the value still exists if it is in scope.)
1405 If the pseudo goes in a hard reg, some other value may occupy
1406 that hard reg where this pseudo is dead, thus clobbering the pseudo.
1407 Conclusion: such a pseudo must not go in a hard reg. */
1408 EXECUTE_IF_SET_IN_REG_SET (regs_live_at_setjmp,
1409 FIRST_PSEUDO_REGISTER, i,
1411 if (regno_reg_rtx[i] != 0)
1413 REG_LIVE_LENGTH (i) = -1;
1414 REG_BASIC_BLOCK (i) = -1;
1419 free_regset_vector (basic_block_live_at_end, n_basic_blocks);
1420 free_regset_vector (basic_block_new_live_at_end, n_basic_blocks);
1421 free_regset_vector (basic_block_significant, n_basic_blocks);
1422 basic_block_live_at_end = (regset *)0;
1423 basic_block_new_live_at_end = (regset *)0;
1424 basic_block_significant = (regset *)0;
1426 obstack_free (&flow_obstack, NULL_PTR);
1429 /* Subroutines of life analysis. */
1431 /* Allocate the permanent data structures that represent the results
1432 of life analysis. Not static since used also for stupid life analysis. */
1435 allocate_for_life_analysis ()
1439 /* Recalculate the register space, in case it has grown. Old style
1440 vector oriented regsets would set regset_{size,bytes} here also. */
1441 allocate_reg_info (max_regno, FALSE, FALSE);
1443 /* Because both reg_scan and flow_analysis want to set up the REG_N_SETS
1444 information, explicitly reset it here. The allocation should have
1445 already happened on the previous reg_scan pass. Make sure in case
1446 some more registers were allocated. */
1447 for (i = 0; i < max_regno; i++)
1450 basic_block_live_at_start
1451 = (regset *) oballoc (n_basic_blocks * sizeof (regset));
1452 init_regset_vector (basic_block_live_at_start, n_basic_blocks,
1455 regs_live_at_setjmp = OBSTACK_ALLOC_REG_SET (function_obstack);
1456 CLEAR_REG_SET (regs_live_at_setjmp);
1459 /* Make each element of VECTOR point at a regset. The vector has
1460 NELTS elements, and space is allocated from the ALLOC_OBSTACK
1464 init_regset_vector (vector, nelts, alloc_obstack)
1467 struct obstack *alloc_obstack;
1471 for (i = 0; i < nelts; i++)
1473 vector[i] = OBSTACK_ALLOC_REG_SET (alloc_obstack);
1474 CLEAR_REG_SET (vector[i]);
1478 /* Release any additional space allocated for each element of VECTOR point
1479 other than the regset header itself. The vector has NELTS elements. */
1482 free_regset_vector (vector, nelts)
1488 for (i = 0; i < nelts; i++)
1489 FREE_REG_SET (vector[i]);
1492 /* Compute the registers live at the beginning of a basic block
1493 from those live at the end.
1495 When called, OLD contains those live at the end.
1496 On return, it contains those live at the beginning.
1497 FIRST and LAST are the first and last insns of the basic block.
1499 FINAL is nonzero if we are doing the final pass which is not
1500 for computing the life info (since that has already been done)
1501 but for acting on it. On this pass, we delete dead stores,
1502 set up the logical links and dead-variables lists of instructions,
1503 and merge instructions for autoincrement and autodecrement addresses.
1505 SIGNIFICANT is nonzero only the first time for each basic block.
1506 If it is nonzero, it points to a regset in which we store
1507 a 1 for each register that is set within the block.
1509 BNUM is the number of the basic block. */
1512 propagate_block (old, first, last, final, significant, bnum)
1513 register regset old;
1525 /* The following variables are used only if FINAL is nonzero. */
1526 /* This vector gets one element for each reg that has been live
1527 at any point in the basic block that has been scanned so far.
1528 SOMETIMES_MAX says how many elements are in use so far. */
1529 register int *regs_sometimes_live;
1530 int sometimes_max = 0;
1531 /* This regset has 1 for each reg that we have seen live so far.
1532 It and REGS_SOMETIMES_LIVE are updated together. */
1535 /* The loop depth may change in the middle of a basic block. Since we
1536 scan from end to beginning, we start with the depth at the end of the
1537 current basic block, and adjust as we pass ends and starts of loops. */
1538 loop_depth = basic_block_loop_depth[bnum];
1540 dead = ALLOCA_REG_SET ();
1541 live = ALLOCA_REG_SET ();
1546 /* Include any notes at the end of the block in the scan.
1547 This is in case the block ends with a call to setjmp. */
1549 while (NEXT_INSN (last) != 0 && GET_CODE (NEXT_INSN (last)) == NOTE)
1551 /* Look for loop boundaries, we are going forward here. */
1552 last = NEXT_INSN (last);
1553 if (NOTE_LINE_NUMBER (last) == NOTE_INSN_LOOP_BEG)
1555 else if (NOTE_LINE_NUMBER (last) == NOTE_INSN_LOOP_END)
1564 maxlive = ALLOCA_REG_SET ();
1565 COPY_REG_SET (maxlive, old);
1566 regs_sometimes_live = (int *) alloca (max_regno * sizeof (int));
1568 /* Process the regs live at the end of the block.
1569 Enter them in MAXLIVE and REGS_SOMETIMES_LIVE.
1570 Also mark them as not local to any one basic block. */
1571 EXECUTE_IF_SET_IN_REG_SET (old, 0, i,
1573 REG_BASIC_BLOCK (i) = REG_BLOCK_GLOBAL;
1574 regs_sometimes_live[sometimes_max] = i;
1579 /* Scan the block an insn at a time from end to beginning. */
1581 for (insn = last; ; insn = prev)
1583 prev = PREV_INSN (insn);
1585 if (GET_CODE (insn) == NOTE)
1587 /* Look for loop boundaries, remembering that we are going
1589 if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END)
1591 else if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG)
1594 /* If we have LOOP_DEPTH == 0, there has been a bookkeeping error.
1595 Abort now rather than setting register status incorrectly. */
1596 if (loop_depth == 0)
1599 /* If this is a call to `setjmp' et al,
1600 warn if any non-volatile datum is live. */
1602 if (final && NOTE_LINE_NUMBER (insn) == NOTE_INSN_SETJMP)
1603 IOR_REG_SET (regs_live_at_setjmp, old);
1606 /* Update the life-status of regs for this insn.
1607 First DEAD gets which regs are set in this insn
1608 then LIVE gets which regs are used in this insn.
1609 Then the regs live before the insn
1610 are those live after, with DEAD regs turned off,
1611 and then LIVE regs turned on. */
1613 else if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
1616 rtx note = find_reg_note (insn, REG_RETVAL, NULL_RTX);
1618 = (insn_dead_p (PATTERN (insn), old, 0)
1619 /* Don't delete something that refers to volatile storage! */
1620 && ! INSN_VOLATILE (insn));
1622 = (insn_is_dead && note != 0
1623 && libcall_dead_p (PATTERN (insn), old, note, insn));
1625 /* If an instruction consists of just dead store(s) on final pass,
1626 "delete" it by turning it into a NOTE of type NOTE_INSN_DELETED.
1627 We could really delete it with delete_insn, but that
1628 can cause trouble for first or last insn in a basic block. */
1629 if (final && insn_is_dead)
1631 PUT_CODE (insn, NOTE);
1632 NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
1633 NOTE_SOURCE_FILE (insn) = 0;
1635 /* CC0 is now known to be dead. Either this insn used it,
1636 in which case it doesn't anymore, or clobbered it,
1637 so the next insn can't use it. */
1640 /* If this insn is copying the return value from a library call,
1641 delete the entire library call. */
1642 if (libcall_is_dead)
1644 rtx first = XEXP (note, 0);
1646 while (INSN_DELETED_P (first))
1647 first = NEXT_INSN (first);
1652 NOTE_LINE_NUMBER (p) = NOTE_INSN_DELETED;
1653 NOTE_SOURCE_FILE (p) = 0;
1659 CLEAR_REG_SET (dead);
1660 CLEAR_REG_SET (live);
1662 /* See if this is an increment or decrement that can be
1663 merged into a following memory address. */
1666 register rtx x = single_set (insn);
1668 /* Does this instruction increment or decrement a register? */
1670 && GET_CODE (SET_DEST (x)) == REG
1671 && (GET_CODE (SET_SRC (x)) == PLUS
1672 || GET_CODE (SET_SRC (x)) == MINUS)
1673 && XEXP (SET_SRC (x), 0) == SET_DEST (x)
1674 && GET_CODE (XEXP (SET_SRC (x), 1)) == CONST_INT
1675 /* Ok, look for a following memory ref we can combine with.
1676 If one is found, change the memory ref to a PRE_INC
1677 or PRE_DEC, cancel this insn, and return 1.
1678 Return 0 if nothing has been done. */
1679 && try_pre_increment_1 (insn))
1682 #endif /* AUTO_INC_DEC */
1684 /* If this is not the final pass, and this insn is copying the
1685 value of a library call and it's dead, don't scan the
1686 insns that perform the library call, so that the call's
1687 arguments are not marked live. */
1688 if (libcall_is_dead)
1690 /* Mark the dest reg as `significant'. */
1691 mark_set_regs (old, dead, PATTERN (insn), NULL_RTX, significant);
1693 insn = XEXP (note, 0);
1694 prev = PREV_INSN (insn);
1696 else if (GET_CODE (PATTERN (insn)) == SET
1697 && SET_DEST (PATTERN (insn)) == stack_pointer_rtx
1698 && GET_CODE (SET_SRC (PATTERN (insn))) == PLUS
1699 && XEXP (SET_SRC (PATTERN (insn)), 0) == stack_pointer_rtx
1700 && GET_CODE (XEXP (SET_SRC (PATTERN (insn)), 1)) == CONST_INT)
1701 /* We have an insn to pop a constant amount off the stack.
1702 (Such insns use PLUS regardless of the direction of the stack,
1703 and any insn to adjust the stack by a constant is always a pop.)
1704 These insns, if not dead stores, have no effect on life. */
1708 /* LIVE gets the regs used in INSN;
1709 DEAD gets those set by it. Dead insns don't make anything
1712 mark_set_regs (old, dead, PATTERN (insn),
1713 final ? insn : NULL_RTX, significant);
1715 /* If an insn doesn't use CC0, it becomes dead since we
1716 assume that every insn clobbers it. So show it dead here;
1717 mark_used_regs will set it live if it is referenced. */
1721 mark_used_regs (old, live, PATTERN (insn), final, insn);
1723 /* Sometimes we may have inserted something before INSN (such as
1724 a move) when we make an auto-inc. So ensure we will scan
1727 prev = PREV_INSN (insn);
1730 if (! insn_is_dead && GET_CODE (insn) == CALL_INSN)
1736 for (note = CALL_INSN_FUNCTION_USAGE (insn);
1738 note = XEXP (note, 1))
1739 if (GET_CODE (XEXP (note, 0)) == USE)
1740 mark_used_regs (old, live, SET_DEST (XEXP (note, 0)),
1743 /* Each call clobbers all call-clobbered regs that are not
1744 global or fixed. Note that the function-value reg is a
1745 call-clobbered reg, and mark_set_regs has already had
1746 a chance to handle it. */
1748 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1749 if (call_used_regs[i] && ! global_regs[i]
1751 SET_REGNO_REG_SET (dead, i);
1753 /* The stack ptr is used (honorarily) by a CALL insn. */
1754 SET_REGNO_REG_SET (live, STACK_POINTER_REGNUM);
1756 /* Calls may also reference any of the global registers,
1757 so they are made live. */
1758 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1760 mark_used_regs (old, live,
1761 gen_rtx_REG (reg_raw_mode[i], i),
1764 /* Calls also clobber memory. */
1768 /* Update OLD for the registers used or set. */
1769 AND_COMPL_REG_SET (old, dead);
1770 IOR_REG_SET (old, live);
1772 if (GET_CODE (insn) == CALL_INSN && final)
1774 /* Any regs live at the time of a call instruction
1775 must not go in a register clobbered by calls.
1776 Find all regs now live and record this for them. */
1778 register int *p = regs_sometimes_live;
1780 for (i = 0; i < sometimes_max; i++, p++)
1781 if (REGNO_REG_SET_P (old, *p))
1782 REG_N_CALLS_CROSSED (*p)++;
1786 /* On final pass, add any additional sometimes-live regs
1787 into MAXLIVE and REGS_SOMETIMES_LIVE.
1788 Also update counts of how many insns each reg is live at. */
1795 EXECUTE_IF_AND_COMPL_IN_REG_SET
1796 (live, maxlive, 0, regno,
1798 regs_sometimes_live[sometimes_max++] = regno;
1799 SET_REGNO_REG_SET (maxlive, regno);
1802 p = regs_sometimes_live;
1803 for (i = 0; i < sometimes_max; i++)
1806 if (REGNO_REG_SET_P (old, regno))
1807 REG_LIVE_LENGTH (regno)++;
1816 FREE_REG_SET (dead);
1817 FREE_REG_SET (live);
1819 FREE_REG_SET (maxlive);
1821 if (num_scratch > max_scratch)
1822 max_scratch = num_scratch;
1825 /* Return 1 if X (the body of an insn, or part of it) is just dead stores
1826 (SET expressions whose destinations are registers dead after the insn).
1827 NEEDED is the regset that says which regs are alive after the insn.
1829 Unless CALL_OK is non-zero, an insn is needed if it contains a CALL. */
1832 insn_dead_p (x, needed, call_ok)
1837 register RTX_CODE code = GET_CODE (x);
1838 /* If setting something that's a reg or part of one,
1839 see if that register's altered value will be live. */
1843 register rtx r = SET_DEST (x);
1844 /* A SET that is a subroutine call cannot be dead. */
1845 if (! call_ok && GET_CODE (SET_SRC (x)) == CALL)
1849 if (GET_CODE (r) == CC0)
1853 if (GET_CODE (r) == MEM && last_mem_set && ! MEM_VOLATILE_P (r)
1854 && rtx_equal_p (r, last_mem_set))
1857 while (GET_CODE (r) == SUBREG
1858 || GET_CODE (r) == STRICT_LOW_PART
1859 || GET_CODE (r) == ZERO_EXTRACT
1860 || GET_CODE (r) == SIGN_EXTRACT)
1863 if (GET_CODE (r) == REG)
1865 register int regno = REGNO (r);
1867 /* Don't delete insns to set global regs. */
1868 if ((regno < FIRST_PSEUDO_REGISTER && global_regs[regno])
1869 /* Make sure insns to set frame pointer aren't deleted. */
1870 || regno == FRAME_POINTER_REGNUM
1871 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
1872 || regno == HARD_FRAME_POINTER_REGNUM
1874 #if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
1875 /* Make sure insns to set arg pointer are never deleted
1876 (if the arg pointer isn't fixed, there will be a USE for
1877 it, so we can treat it normally). */
1878 || (regno == ARG_POINTER_REGNUM && fixed_regs[regno])
1880 || REGNO_REG_SET_P (needed, regno))
1883 /* If this is a hard register, verify that subsequent words are
1885 if (regno < FIRST_PSEUDO_REGISTER)
1887 int n = HARD_REGNO_NREGS (regno, GET_MODE (r));
1890 if (REGNO_REG_SET_P (needed, regno+n))
1897 /* If performing several activities,
1898 insn is dead if each activity is individually dead.
1899 Also, CLOBBERs and USEs can be ignored; a CLOBBER or USE
1900 that's inside a PARALLEL doesn't make the insn worth keeping. */
1901 else if (code == PARALLEL)
1903 register int i = XVECLEN (x, 0);
1904 for (i--; i >= 0; i--)
1906 rtx elt = XVECEXP (x, 0, i);
1907 if (!insn_dead_p (elt, needed, call_ok)
1908 && GET_CODE (elt) != CLOBBER
1909 && GET_CODE (elt) != USE)
1914 /* We do not check CLOBBER or USE here.
1915 An insn consisting of just a CLOBBER or just a USE
1916 should not be deleted. */
1920 /* If X is the pattern of the last insn in a libcall, and assuming X is dead,
1921 return 1 if the entire library call is dead.
1922 This is true if X copies a register (hard or pseudo)
1923 and if the hard return reg of the call insn is dead.
1924 (The caller should have tested the destination of X already for death.)
1926 If this insn doesn't just copy a register, then we don't
1927 have an ordinary libcall. In that case, cse could not have
1928 managed to substitute the source for the dest later on,
1929 so we can assume the libcall is dead.
1931 NEEDED is the bit vector of pseudoregs live before this insn.
1932 NOTE is the REG_RETVAL note of the insn. INSN is the insn itself. */
1935 libcall_dead_p (x, needed, note, insn)
1941 register RTX_CODE code = GET_CODE (x);
1945 register rtx r = SET_SRC (x);
1946 if (GET_CODE (r) == REG)
1948 rtx call = XEXP (note, 0);
1951 /* Find the call insn. */
1952 while (call != insn && GET_CODE (call) != CALL_INSN)
1953 call = NEXT_INSN (call);
1955 /* If there is none, do nothing special,
1956 since ordinary death handling can understand these insns. */
1960 /* See if the hard reg holding the value is dead.
1961 If this is a PARALLEL, find the call within it. */
1962 call = PATTERN (call);
1963 if (GET_CODE (call) == PARALLEL)
1965 for (i = XVECLEN (call, 0) - 1; i >= 0; i--)
1966 if (GET_CODE (XVECEXP (call, 0, i)) == SET
1967 && GET_CODE (SET_SRC (XVECEXP (call, 0, i))) == CALL)
1970 /* This may be a library call that is returning a value
1971 via invisible pointer. Do nothing special, since
1972 ordinary death handling can understand these insns. */
1976 call = XVECEXP (call, 0, i);
1979 return insn_dead_p (call, needed, 1);
1985 /* Return 1 if register REGNO was used before it was set.
1986 In other words, if it is live at function entry.
1987 Don't count global register variables or variables in registers
1988 that can be used for function arg passing, though. */
1991 regno_uninitialized (regno)
1994 if (n_basic_blocks == 0
1995 || (regno < FIRST_PSEUDO_REGISTER
1996 && (global_regs[regno] || FUNCTION_ARG_REGNO_P (regno))))
1999 return REGNO_REG_SET_P (basic_block_live_at_start[0], regno);
2002 /* 1 if register REGNO was alive at a place where `setjmp' was called
2003 and was set more than once or is an argument.
2004 Such regs may be clobbered by `longjmp'. */
2007 regno_clobbered_at_setjmp (regno)
2010 if (n_basic_blocks == 0)
2013 return ((REG_N_SETS (regno) > 1
2014 || REGNO_REG_SET_P (basic_block_live_at_start[0], regno))
2015 && REGNO_REG_SET_P (regs_live_at_setjmp, regno));
2018 /* Process the registers that are set within X.
2019 Their bits are set to 1 in the regset DEAD,
2020 because they are dead prior to this insn.
2022 If INSN is nonzero, it is the insn being processed
2023 and the fact that it is nonzero implies this is the FINAL pass
2024 in propagate_block. In this case, various info about register
2025 usage is stored, LOG_LINKS fields of insns are set up. */
2028 mark_set_regs (needed, dead, x, insn, significant)
2035 register RTX_CODE code = GET_CODE (x);
2037 if (code == SET || code == CLOBBER)
2038 mark_set_1 (needed, dead, x, insn, significant);
2039 else if (code == PARALLEL)
2042 for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
2044 code = GET_CODE (XVECEXP (x, 0, i));
2045 if (code == SET || code == CLOBBER)
2046 mark_set_1 (needed, dead, XVECEXP (x, 0, i), insn, significant);
2051 /* Process a single SET rtx, X. */
2054 mark_set_1 (needed, dead, x, insn, significant)
2062 register rtx reg = SET_DEST (x);
2064 /* Modifying just one hardware register of a multi-reg value
2065 or just a byte field of a register
2066 does not mean the value from before this insn is now dead.
2067 But it does mean liveness of that register at the end of the block
2070 Within mark_set_1, however, we treat it as if the register is
2071 indeed modified. mark_used_regs will, however, also treat this
2072 register as being used. Thus, we treat these insns as setting a
2073 new value for the register as a function of its old value. This
2074 cases LOG_LINKS to be made appropriately and this will help combine. */
2076 while (GET_CODE (reg) == SUBREG || GET_CODE (reg) == ZERO_EXTRACT
2077 || GET_CODE (reg) == SIGN_EXTRACT
2078 || GET_CODE (reg) == STRICT_LOW_PART)
2079 reg = XEXP (reg, 0);
2081 /* If we are writing into memory or into a register mentioned in the
2082 address of the last thing stored into memory, show we don't know
2083 what the last store was. If we are writing memory, save the address
2084 unless it is volatile. */
2085 if (GET_CODE (reg) == MEM
2086 || (GET_CODE (reg) == REG
2087 && last_mem_set != 0 && reg_overlap_mentioned_p (reg, last_mem_set)))
2090 if (GET_CODE (reg) == MEM && ! side_effects_p (reg)
2091 /* There are no REG_INC notes for SP, so we can't assume we'll see
2092 everything that invalidates it. To be safe, don't eliminate any
2093 stores though SP; none of them should be redundant anyway. */
2094 && ! reg_mentioned_p (stack_pointer_rtx, reg))
2097 if (GET_CODE (reg) == REG
2098 && (regno = REGNO (reg), regno != FRAME_POINTER_REGNUM)
2099 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
2100 && regno != HARD_FRAME_POINTER_REGNUM
2102 #if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
2103 && ! (regno == ARG_POINTER_REGNUM && fixed_regs[regno])
2105 && ! (regno < FIRST_PSEUDO_REGISTER && global_regs[regno]))
2106 /* && regno != STACK_POINTER_REGNUM) -- let's try without this. */
2108 int some_needed = REGNO_REG_SET_P (needed, regno);
2109 int some_not_needed = ! some_needed;
2111 /* Mark it as a significant register for this basic block. */
2113 SET_REGNO_REG_SET (significant, regno);
2115 /* Mark it as as dead before this insn. */
2116 SET_REGNO_REG_SET (dead, regno);
2118 /* A hard reg in a wide mode may really be multiple registers.
2119 If so, mark all of them just like the first. */
2120 if (regno < FIRST_PSEUDO_REGISTER)
2124 /* Nothing below is needed for the stack pointer; get out asap.
2125 Eg, log links aren't needed, since combine won't use them. */
2126 if (regno == STACK_POINTER_REGNUM)
2129 n = HARD_REGNO_NREGS (regno, GET_MODE (reg));
2132 int regno_n = regno + n;
2133 int needed_regno = REGNO_REG_SET_P (needed, regno_n);
2135 SET_REGNO_REG_SET (significant, regno_n);
2137 SET_REGNO_REG_SET (dead, regno_n);
2138 some_needed |= needed_regno;
2139 some_not_needed |= ! needed_regno;
2142 /* Additional data to record if this is the final pass. */
2145 register rtx y = reg_next_use[regno];
2146 register int blocknum = BLOCK_NUM (insn);
2148 /* If this is a hard reg, record this function uses the reg. */
2150 if (regno < FIRST_PSEUDO_REGISTER)
2153 int endregno = regno + HARD_REGNO_NREGS (regno, GET_MODE (reg));
2155 for (i = regno; i < endregno; i++)
2157 /* The next use is no longer "next", since a store
2159 reg_next_use[i] = 0;
2161 regs_ever_live[i] = 1;
2167 /* The next use is no longer "next", since a store
2169 reg_next_use[regno] = 0;
2171 /* Keep track of which basic blocks each reg appears in. */
2173 if (REG_BASIC_BLOCK (regno) == REG_BLOCK_UNKNOWN)
2174 REG_BASIC_BLOCK (regno) = blocknum;
2175 else if (REG_BASIC_BLOCK (regno) != blocknum)
2176 REG_BASIC_BLOCK (regno) = REG_BLOCK_GLOBAL;
2178 /* Count (weighted) references, stores, etc. This counts a
2179 register twice if it is modified, but that is correct. */
2180 REG_N_SETS (regno)++;
2182 REG_N_REFS (regno) += loop_depth;
2184 /* The insns where a reg is live are normally counted
2185 elsewhere, but we want the count to include the insn
2186 where the reg is set, and the normal counting mechanism
2187 would not count it. */
2188 REG_LIVE_LENGTH (regno)++;
2191 if (! some_not_needed)
2193 /* Make a logical link from the next following insn
2194 that uses this register, back to this insn.
2195 The following insns have already been processed.
2197 We don't build a LOG_LINK for hard registers containing
2198 in ASM_OPERANDs. If these registers get replaced,
2199 we might wind up changing the semantics of the insn,
2200 even if reload can make what appear to be valid assignments
2202 if (y && (BLOCK_NUM (y) == blocknum)
2203 && (regno >= FIRST_PSEUDO_REGISTER
2204 || asm_noperands (PATTERN (y)) < 0))
2206 = gen_rtx_INSN_LIST (VOIDmode, insn, LOG_LINKS (y));
2208 else if (! some_needed)
2210 /* Note that dead stores have already been deleted when possible
2211 If we get here, we have found a dead store that cannot
2212 be eliminated (because the same insn does something useful).
2213 Indicate this by marking the reg being set as dying here. */
2215 = gen_rtx_EXPR_LIST (REG_UNUSED, reg, REG_NOTES (insn));
2216 REG_N_DEATHS (REGNO (reg))++;
2220 /* This is a case where we have a multi-word hard register
2221 and some, but not all, of the words of the register are
2222 needed in subsequent insns. Write REG_UNUSED notes
2223 for those parts that were not needed. This case should
2228 for (i = HARD_REGNO_NREGS (regno, GET_MODE (reg)) - 1;
2230 if (!REGNO_REG_SET_P (needed, regno + i))
2232 = gen_rtx_EXPR_LIST (REG_UNUSED,
2233 gen_rtx_REG (reg_raw_mode[regno + i],
2239 else if (GET_CODE (reg) == REG)
2240 reg_next_use[regno] = 0;
2242 /* If this is the last pass and this is a SCRATCH, show it will be dying
2243 here and count it. */
2244 else if (GET_CODE (reg) == SCRATCH && insn != 0)
2247 = gen_rtx_EXPR_LIST (REG_UNUSED, reg, REG_NOTES (insn));
2254 /* X is a MEM found in INSN. See if we can convert it into an auto-increment
2258 find_auto_inc (needed, x, insn)
2263 rtx addr = XEXP (x, 0);
2264 HOST_WIDE_INT offset = 0;
2267 /* Here we detect use of an index register which might be good for
2268 postincrement, postdecrement, preincrement, or predecrement. */
2270 if (GET_CODE (addr) == PLUS && GET_CODE (XEXP (addr, 1)) == CONST_INT)
2271 offset = INTVAL (XEXP (addr, 1)), addr = XEXP (addr, 0);
2273 if (GET_CODE (addr) == REG)
2276 register int size = GET_MODE_SIZE (GET_MODE (x));
2279 int regno = REGNO (addr);
2281 /* Is the next use an increment that might make auto-increment? */
2282 if ((incr = reg_next_use[regno]) != 0
2283 && (set = single_set (incr)) != 0
2284 && GET_CODE (set) == SET
2285 && BLOCK_NUM (incr) == BLOCK_NUM (insn)
2286 /* Can't add side effects to jumps; if reg is spilled and
2287 reloaded, there's no way to store back the altered value. */
2288 && GET_CODE (insn) != JUMP_INSN
2289 && (y = SET_SRC (set), GET_CODE (y) == PLUS)
2290 && XEXP (y, 0) == addr
2291 && GET_CODE (XEXP (y, 1)) == CONST_INT
2293 #ifdef HAVE_POST_INCREMENT
2294 || (INTVAL (XEXP (y, 1)) == size && offset == 0)
2296 #ifdef HAVE_POST_DECREMENT
2297 || (INTVAL (XEXP (y, 1)) == - size && offset == 0)
2299 #ifdef HAVE_PRE_INCREMENT
2300 || (INTVAL (XEXP (y, 1)) == size && offset == size)
2302 #ifdef HAVE_PRE_DECREMENT
2303 || (INTVAL (XEXP (y, 1)) == - size && offset == - size)
2306 /* Make sure this reg appears only once in this insn. */
2307 && (use = find_use_as_address (PATTERN (insn), addr, offset),
2308 use != 0 && use != (rtx) 1))
2310 rtx q = SET_DEST (set);
2311 enum rtx_code inc_code = (INTVAL (XEXP (y, 1)) == size
2312 ? (offset ? PRE_INC : POST_INC)
2313 : (offset ? PRE_DEC : POST_DEC));
2315 if (dead_or_set_p (incr, addr))
2317 /* This is the simple case. Try to make the auto-inc. If
2318 we can't, we are done. Otherwise, we will do any
2319 needed updates below. */
2320 if (! validate_change (insn, &XEXP (x, 0),
2321 gen_rtx_fmt_e (inc_code, Pmode, addr),
2325 else if (GET_CODE (q) == REG
2326 /* PREV_INSN used here to check the semi-open interval
2328 && ! reg_used_between_p (q, PREV_INSN (insn), incr)
2329 /* We must also check for sets of q as q may be
2330 a call clobbered hard register and there may
2331 be a call between PREV_INSN (insn) and incr. */
2332 && ! reg_set_between_p (q, PREV_INSN (insn), incr))
2334 /* We have *p followed sometime later by q = p+size.
2335 Both p and q must be live afterward,
2336 and q is not used between INSN and it's assignment.
2337 Change it to q = p, ...*q..., q = q+size.
2338 Then fall into the usual case. */
2342 emit_move_insn (q, addr);
2343 insns = get_insns ();
2346 /* If anything in INSNS have UID's that don't fit within the
2347 extra space we allocate earlier, we can't make this auto-inc.
2348 This should never happen. */
2349 for (temp = insns; temp; temp = NEXT_INSN (temp))
2351 if (INSN_UID (temp) > max_uid_for_flow)
2353 BLOCK_NUM (temp) = BLOCK_NUM (insn);
2356 /* If we can't make the auto-inc, or can't make the
2357 replacement into Y, exit. There's no point in making
2358 the change below if we can't do the auto-inc and doing
2359 so is not correct in the pre-inc case. */
2361 validate_change (insn, &XEXP (x, 0),
2362 gen_rtx_fmt_e (inc_code, Pmode, q),
2364 validate_change (incr, &XEXP (y, 0), q, 1);
2365 if (! apply_change_group ())
2368 /* We now know we'll be doing this change, so emit the
2369 new insn(s) and do the updates. */
2370 emit_insns_before (insns, insn);
2372 if (basic_block_head[BLOCK_NUM (insn)] == insn)
2373 basic_block_head[BLOCK_NUM (insn)] = insns;
2375 /* INCR will become a NOTE and INSN won't contain a
2376 use of ADDR. If a use of ADDR was just placed in
2377 the insn before INSN, make that the next use.
2378 Otherwise, invalidate it. */
2379 if (GET_CODE (PREV_INSN (insn)) == INSN
2380 && GET_CODE (PATTERN (PREV_INSN (insn))) == SET
2381 && SET_SRC (PATTERN (PREV_INSN (insn))) == addr)
2382 reg_next_use[regno] = PREV_INSN (insn);
2384 reg_next_use[regno] = 0;
2389 /* REGNO is now used in INCR which is below INSN, but
2390 it previously wasn't live here. If we don't mark
2391 it as needed, we'll put a REG_DEAD note for it
2392 on this insn, which is incorrect. */
2393 SET_REGNO_REG_SET (needed, regno);
2395 /* If there are any calls between INSN and INCR, show
2396 that REGNO now crosses them. */
2397 for (temp = insn; temp != incr; temp = NEXT_INSN (temp))
2398 if (GET_CODE (temp) == CALL_INSN)
2399 REG_N_CALLS_CROSSED (regno)++;
2404 /* If we haven't returned, it means we were able to make the
2405 auto-inc, so update the status. First, record that this insn
2406 has an implicit side effect. */
2409 = gen_rtx_EXPR_LIST (REG_INC, addr, REG_NOTES (insn));
2411 /* Modify the old increment-insn to simply copy
2412 the already-incremented value of our register. */
2413 if (! validate_change (incr, &SET_SRC (set), addr, 0))
2416 /* If that makes it a no-op (copying the register into itself) delete
2417 it so it won't appear to be a "use" and a "set" of this
2419 if (SET_DEST (set) == addr)
2421 PUT_CODE (incr, NOTE);
2422 NOTE_LINE_NUMBER (incr) = NOTE_INSN_DELETED;
2423 NOTE_SOURCE_FILE (incr) = 0;
2426 if (regno >= FIRST_PSEUDO_REGISTER)
2428 /* Count an extra reference to the reg. When a reg is
2429 incremented, spilling it is worse, so we want to make
2430 that less likely. */
2431 REG_N_REFS (regno) += loop_depth;
2433 /* Count the increment as a setting of the register,
2434 even though it isn't a SET in rtl. */
2435 REG_N_SETS (regno)++;
2440 #endif /* AUTO_INC_DEC */
2442 /* Scan expression X and store a 1-bit in LIVE for each reg it uses.
2443 This is done assuming the registers needed from X
2444 are those that have 1-bits in NEEDED.
2446 On the final pass, FINAL is 1. This means try for autoincrement
2447 and count the uses and deaths of each pseudo-reg.
2449 INSN is the containing instruction. If INSN is dead, this function is not
2453 mark_used_regs (needed, live, x, final, insn)
2460 register RTX_CODE code;
2465 code = GET_CODE (x);
2486 /* If we are clobbering a MEM, mark any registers inside the address
2488 if (GET_CODE (XEXP (x, 0)) == MEM)
2489 mark_used_regs (needed, live, XEXP (XEXP (x, 0), 0), final, insn);
2493 /* Invalidate the data for the last MEM stored, but only if MEM is
2494 something that can be stored into. */
2495 if (GET_CODE (XEXP (x, 0)) == SYMBOL_REF
2496 && CONSTANT_POOL_ADDRESS_P (XEXP (x, 0)))
2497 ; /* needn't clear last_mem_set */
2503 find_auto_inc (needed, x, insn);
2508 if (GET_CODE (SUBREG_REG (x)) == REG
2509 && REGNO (SUBREG_REG (x)) >= FIRST_PSEUDO_REGISTER
2510 && (GET_MODE_SIZE (GET_MODE (x))
2511 != GET_MODE_SIZE (GET_MODE (SUBREG_REG (x)))))
2512 REG_CHANGES_SIZE (REGNO (SUBREG_REG (x))) = 1;
2514 /* While we're here, optimize this case. */
2517 /* In case the SUBREG is not of a register, don't optimize */
2518 if (GET_CODE (x) != REG)
2520 mark_used_regs (needed, live, x, final, insn);
2524 /* ... fall through ... */
2527 /* See a register other than being set
2528 => mark it as needed. */
2532 int some_needed = REGNO_REG_SET_P (needed, regno);
2533 int some_not_needed = ! some_needed;
2535 SET_REGNO_REG_SET (live, regno);
2537 /* A hard reg in a wide mode may really be multiple registers.
2538 If so, mark all of them just like the first. */
2539 if (regno < FIRST_PSEUDO_REGISTER)
2543 /* For stack ptr or fixed arg pointer,
2544 nothing below can be necessary, so waste no more time. */
2545 if (regno == STACK_POINTER_REGNUM
2546 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
2547 || regno == HARD_FRAME_POINTER_REGNUM
2549 #if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
2550 || (regno == ARG_POINTER_REGNUM && fixed_regs[regno])
2552 || regno == FRAME_POINTER_REGNUM)
2554 /* If this is a register we are going to try to eliminate,
2555 don't mark it live here. If we are successful in
2556 eliminating it, it need not be live unless it is used for
2557 pseudos, in which case it will have been set live when
2558 it was allocated to the pseudos. If the register will not
2559 be eliminated, reload will set it live at that point. */
2561 if (! TEST_HARD_REG_BIT (elim_reg_set, regno))
2562 regs_ever_live[regno] = 1;
2565 /* No death notes for global register variables;
2566 their values are live after this function exits. */
2567 if (global_regs[regno])
2570 reg_next_use[regno] = insn;
2574 n = HARD_REGNO_NREGS (regno, GET_MODE (x));
2577 int regno_n = regno + n;
2578 int needed_regno = REGNO_REG_SET_P (needed, regno_n);
2580 SET_REGNO_REG_SET (live, regno_n);
2581 some_needed |= needed_regno;
2582 some_not_needed |= ! needed_regno;
2587 /* Record where each reg is used, so when the reg
2588 is set we know the next insn that uses it. */
2590 reg_next_use[regno] = insn;
2592 if (regno < FIRST_PSEUDO_REGISTER)
2594 /* If a hard reg is being used,
2595 record that this function does use it. */
2597 i = HARD_REGNO_NREGS (regno, GET_MODE (x));
2601 regs_ever_live[regno + --i] = 1;
2606 /* Keep track of which basic block each reg appears in. */
2608 register int blocknum = BLOCK_NUM (insn);
2610 if (REG_BASIC_BLOCK (regno) == REG_BLOCK_UNKNOWN)
2611 REG_BASIC_BLOCK (regno) = blocknum;
2612 else if (REG_BASIC_BLOCK (regno) != blocknum)
2613 REG_BASIC_BLOCK (regno) = REG_BLOCK_GLOBAL;
2615 /* Count (weighted) number of uses of each reg. */
2617 REG_N_REFS (regno) += loop_depth;
2620 /* Record and count the insns in which a reg dies.
2621 If it is used in this insn and was dead below the insn
2622 then it dies in this insn. If it was set in this insn,
2623 we do not make a REG_DEAD note; likewise if we already
2624 made such a note. */
2627 && ! dead_or_set_p (insn, x)
2629 && (regno >= FIRST_PSEUDO_REGISTER || ! fixed_regs[regno])
2633 /* Check for the case where the register dying partially
2634 overlaps the register set by this insn. */
2635 if (regno < FIRST_PSEUDO_REGISTER
2636 && HARD_REGNO_NREGS (regno, GET_MODE (x)) > 1)
2638 int n = HARD_REGNO_NREGS (regno, GET_MODE (x));
2640 some_needed |= dead_or_set_regno_p (insn, regno + n);
2643 /* If none of the words in X is needed, make a REG_DEAD
2644 note. Otherwise, we must make partial REG_DEAD notes. */
2648 = gen_rtx_EXPR_LIST (REG_DEAD, x, REG_NOTES (insn));
2649 REG_N_DEATHS (regno)++;
2655 /* Don't make a REG_DEAD note for a part of a register
2656 that is set in the insn. */
2658 for (i = HARD_REGNO_NREGS (regno, GET_MODE (x)) - 1;
2660 if (!REGNO_REG_SET_P (needed, regno + i)
2661 && ! dead_or_set_regno_p (insn, regno + i))
2663 = gen_rtx_EXPR_LIST (REG_DEAD,
2664 gen_rtx_REG (reg_raw_mode[regno + i],
2675 register rtx testreg = SET_DEST (x);
2678 /* If storing into MEM, don't show it as being used. But do
2679 show the address as being used. */
2680 if (GET_CODE (testreg) == MEM)
2684 find_auto_inc (needed, testreg, insn);
2686 mark_used_regs (needed, live, XEXP (testreg, 0), final, insn);
2687 mark_used_regs (needed, live, SET_SRC (x), final, insn);
2691 /* Storing in STRICT_LOW_PART is like storing in a reg
2692 in that this SET might be dead, so ignore it in TESTREG.
2693 but in some other ways it is like using the reg.
2695 Storing in a SUBREG or a bit field is like storing the entire
2696 register in that if the register's value is not used
2697 then this SET is not needed. */
2698 while (GET_CODE (testreg) == STRICT_LOW_PART
2699 || GET_CODE (testreg) == ZERO_EXTRACT
2700 || GET_CODE (testreg) == SIGN_EXTRACT
2701 || GET_CODE (testreg) == SUBREG)
2703 if (GET_CODE (testreg) == SUBREG
2704 && GET_CODE (SUBREG_REG (testreg)) == REG
2705 && REGNO (SUBREG_REG (testreg)) >= FIRST_PSEUDO_REGISTER
2706 && (GET_MODE_SIZE (GET_MODE (testreg))
2707 != GET_MODE_SIZE (GET_MODE (SUBREG_REG (testreg)))))
2708 REG_CHANGES_SIZE (REGNO (SUBREG_REG (testreg))) = 1;
2710 /* Modifying a single register in an alternate mode
2711 does not use any of the old value. But these other
2712 ways of storing in a register do use the old value. */
2713 if (GET_CODE (testreg) == SUBREG
2714 && !(REG_SIZE (SUBREG_REG (testreg)) > REG_SIZE (testreg)))
2719 testreg = XEXP (testreg, 0);
2722 /* If this is a store into a register,
2723 recursively scan the value being stored. */
2725 if (GET_CODE (testreg) == REG
2726 && (regno = REGNO (testreg), regno != FRAME_POINTER_REGNUM)
2727 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
2728 && regno != HARD_FRAME_POINTER_REGNUM
2730 #if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
2731 && ! (regno == ARG_POINTER_REGNUM && fixed_regs[regno])
2734 /* We used to exclude global_regs here, but that seems wrong.
2735 Storing in them is like storing in mem. */
2737 mark_used_regs (needed, live, SET_SRC (x), final, insn);
2739 mark_used_regs (needed, live, SET_DEST (x), final, insn);
2746 /* If exiting needs the right stack value, consider this insn as
2747 using the stack pointer. In any event, consider it as using
2748 all global registers and all registers used by return. */
2750 #ifdef EXIT_IGNORE_STACK
2751 if (! EXIT_IGNORE_STACK
2752 || (! FRAME_POINTER_REQUIRED
2753 && ! current_function_calls_alloca
2754 && flag_omit_frame_pointer))
2756 SET_REGNO_REG_SET (live, STACK_POINTER_REGNUM);
2758 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
2760 #ifdef EPILOGUE_USES
2761 || EPILOGUE_USES (i)
2764 SET_REGNO_REG_SET (live, i);
2771 /* Recursively scan the operands of this expression. */
2774 register char *fmt = GET_RTX_FORMAT (code);
2777 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2781 /* Tail recursive case: save a function call level. */
2787 mark_used_regs (needed, live, XEXP (x, i), final, insn);
2789 else if (fmt[i] == 'E')
2792 for (j = 0; j < XVECLEN (x, i); j++)
2793 mark_used_regs (needed, live, XVECEXP (x, i, j), final, insn);
2802 try_pre_increment_1 (insn)
2805 /* Find the next use of this reg. If in same basic block,
2806 make it do pre-increment or pre-decrement if appropriate. */
2807 rtx x = single_set (insn);
2808 HOST_WIDE_INT amount = ((GET_CODE (SET_SRC (x)) == PLUS ? 1 : -1)
2809 * INTVAL (XEXP (SET_SRC (x), 1)));
2810 int regno = REGNO (SET_DEST (x));
2811 rtx y = reg_next_use[regno];
2813 && BLOCK_NUM (y) == BLOCK_NUM (insn)
2814 /* Don't do this if the reg dies, or gets set in y; a standard addressing
2815 mode would be better. */
2816 && ! dead_or_set_p (y, SET_DEST (x))
2817 && try_pre_increment (y, SET_DEST (x), amount))
2819 /* We have found a suitable auto-increment
2820 and already changed insn Y to do it.
2821 So flush this increment-instruction. */
2822 PUT_CODE (insn, NOTE);
2823 NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
2824 NOTE_SOURCE_FILE (insn) = 0;
2825 /* Count a reference to this reg for the increment
2826 insn we are deleting. When a reg is incremented.
2827 spilling it is worse, so we want to make that
2829 if (regno >= FIRST_PSEUDO_REGISTER)
2831 REG_N_REFS (regno) += loop_depth;
2832 REG_N_SETS (regno)++;
2839 /* Try to change INSN so that it does pre-increment or pre-decrement
2840 addressing on register REG in order to add AMOUNT to REG.
2841 AMOUNT is negative for pre-decrement.
2842 Returns 1 if the change could be made.
2843 This checks all about the validity of the result of modifying INSN. */
2846 try_pre_increment (insn, reg, amount)
2848 HOST_WIDE_INT amount;
2852 /* Nonzero if we can try to make a pre-increment or pre-decrement.
2853 For example, addl $4,r1; movl (r1),... can become movl +(r1),... */
2855 /* Nonzero if we can try to make a post-increment or post-decrement.
2856 For example, addl $4,r1; movl -4(r1),... can become movl (r1)+,...
2857 It is possible for both PRE_OK and POST_OK to be nonzero if the machine
2858 supports both pre-inc and post-inc, or both pre-dec and post-dec. */
2861 /* Nonzero if the opportunity actually requires post-inc or post-dec. */
2864 /* From the sign of increment, see which possibilities are conceivable
2865 on this target machine. */
2866 #ifdef HAVE_PRE_INCREMENT
2870 #ifdef HAVE_POST_INCREMENT
2875 #ifdef HAVE_PRE_DECREMENT
2879 #ifdef HAVE_POST_DECREMENT
2884 if (! (pre_ok || post_ok))
2887 /* It is not safe to add a side effect to a jump insn
2888 because if the incremented register is spilled and must be reloaded
2889 there would be no way to store the incremented value back in memory. */
2891 if (GET_CODE (insn) == JUMP_INSN)
2896 use = find_use_as_address (PATTERN (insn), reg, 0);
2897 if (post_ok && (use == 0 || use == (rtx) 1))
2899 use = find_use_as_address (PATTERN (insn), reg, -amount);
2903 if (use == 0 || use == (rtx) 1)
2906 if (GET_MODE_SIZE (GET_MODE (use)) != (amount > 0 ? amount : - amount))
2909 /* See if this combination of instruction and addressing mode exists. */
2910 if (! validate_change (insn, &XEXP (use, 0),
2911 gen_rtx_fmt_e (amount > 0
2912 ? (do_post ? POST_INC : PRE_INC)
2913 : (do_post ? POST_DEC : PRE_DEC),
2917 /* Record that this insn now has an implicit side effect on X. */
2918 REG_NOTES (insn) = gen_rtx_EXPR_LIST (REG_INC, reg, REG_NOTES (insn));
2922 #endif /* AUTO_INC_DEC */
2924 /* Find the place in the rtx X where REG is used as a memory address.
2925 Return the MEM rtx that so uses it.
2926 If PLUSCONST is nonzero, search instead for a memory address equivalent to
2927 (plus REG (const_int PLUSCONST)).
2929 If such an address does not appear, return 0.
2930 If REG appears more than once, or is used other than in such an address,
2934 find_use_as_address (x, reg, plusconst)
2937 HOST_WIDE_INT plusconst;
2939 enum rtx_code code = GET_CODE (x);
2940 char *fmt = GET_RTX_FORMAT (code);
2942 register rtx value = 0;
2945 if (code == MEM && XEXP (x, 0) == reg && plusconst == 0)
2948 if (code == MEM && GET_CODE (XEXP (x, 0)) == PLUS
2949 && XEXP (XEXP (x, 0), 0) == reg
2950 && GET_CODE (XEXP (XEXP (x, 0), 1)) == CONST_INT
2951 && INTVAL (XEXP (XEXP (x, 0), 1)) == plusconst)
2954 if (code == SIGN_EXTRACT || code == ZERO_EXTRACT)
2956 /* If REG occurs inside a MEM used in a bit-field reference,
2957 that is unacceptable. */
2958 if (find_use_as_address (XEXP (x, 0), reg, 0) != 0)
2959 return (rtx) (HOST_WIDE_INT) 1;
2963 return (rtx) (HOST_WIDE_INT) 1;
2965 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2969 tem = find_use_as_address (XEXP (x, i), reg, plusconst);
2973 return (rtx) (HOST_WIDE_INT) 1;
2978 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
2980 tem = find_use_as_address (XVECEXP (x, i, j), reg, plusconst);
2984 return (rtx) (HOST_WIDE_INT) 1;
2992 /* Write information about registers and basic blocks into FILE.
2993 This is part of making a debugging dump. */
2996 dump_flow_info (file)
3000 static char *reg_class_names[] = REG_CLASS_NAMES;
3002 fprintf (file, "%d registers.\n", max_regno);
3004 for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
3007 enum reg_class class, altclass;
3008 fprintf (file, "\nRegister %d used %d times across %d insns",
3009 i, REG_N_REFS (i), REG_LIVE_LENGTH (i));
3010 if (REG_BASIC_BLOCK (i) >= 0)
3011 fprintf (file, " in block %d", REG_BASIC_BLOCK (i));
3012 if (REG_N_DEATHS (i) != 1)
3013 fprintf (file, "; dies in %d places", REG_N_DEATHS (i));
3014 if (REG_N_CALLS_CROSSED (i) == 1)
3015 fprintf (file, "; crosses 1 call");
3016 else if (REG_N_CALLS_CROSSED (i))
3017 fprintf (file, "; crosses %d calls", REG_N_CALLS_CROSSED (i));
3018 if (PSEUDO_REGNO_BYTES (i) != UNITS_PER_WORD)
3019 fprintf (file, "; %d bytes", PSEUDO_REGNO_BYTES (i));
3020 class = reg_preferred_class (i);
3021 altclass = reg_alternate_class (i);
3022 if (class != GENERAL_REGS || altclass != ALL_REGS)
3024 if (altclass == ALL_REGS || class == ALL_REGS)
3025 fprintf (file, "; pref %s", reg_class_names[(int) class]);
3026 else if (altclass == NO_REGS)
3027 fprintf (file, "; %s or none", reg_class_names[(int) class]);
3029 fprintf (file, "; pref %s, else %s",
3030 reg_class_names[(int) class],
3031 reg_class_names[(int) altclass]);
3033 if (REGNO_POINTER_FLAG (i))
3034 fprintf (file, "; pointer");
3035 fprintf (file, ".\n");
3037 fprintf (file, "\n%d basic blocks.\n", n_basic_blocks);
3038 for (i = 0; i < n_basic_blocks; i++)
3040 register rtx head, jump;
3042 fprintf (file, "\nBasic block %d: first insn %d, last %d.\n",
3044 INSN_UID (basic_block_head[i]),
3045 INSN_UID (basic_block_end[i]));
3046 /* The control flow graph's storage is freed
3047 now when flow_analysis returns.
3048 Don't try to print it if it is gone. */
3049 if (basic_block_drops_in)
3051 fprintf (file, "Reached from blocks: ");
3052 head = basic_block_head[i];
3053 if (GET_CODE (head) == CODE_LABEL)
3054 for (jump = LABEL_REFS (head);
3056 jump = LABEL_NEXTREF (jump))
3058 register int from_block = BLOCK_NUM (CONTAINING_INSN (jump));
3059 fprintf (file, " %d", from_block);
3061 if (basic_block_drops_in[i])
3062 fprintf (file, " previous");
3064 fprintf (file, "\nRegisters live at start:");
3065 for (regno = 0; regno < max_regno; regno++)
3066 if (REGNO_REG_SET_P (basic_block_live_at_start[i], regno))
3067 fprintf (file, " %d", regno);
3068 fprintf (file, "\n");
3070 fprintf (file, "\n");
3074 /* Like print_rtl, but also print out live information for the start of each
3078 print_rtl_with_bb (outf, rtx_first)
3082 register rtx tmp_rtx;
3085 fprintf (outf, "(nil)\n");
3090 enum bb_state { NOT_IN_BB, IN_ONE_BB, IN_MULTIPLE_BB };
3091 int max_uid = get_max_uid ();
3092 int *start = (int *) alloca (max_uid * sizeof (int));
3093 int *end = (int *) alloca (max_uid * sizeof (int));
3094 char *in_bb_p = (char *) alloca (max_uid * sizeof (enum bb_state));
3096 for (i = 0; i < max_uid; i++)
3098 start[i] = end[i] = -1;
3099 in_bb_p[i] = NOT_IN_BB;
3102 for (i = n_basic_blocks-1; i >= 0; i--)
3105 start[INSN_UID (basic_block_head[i])] = i;
3106 end[INSN_UID (basic_block_end[i])] = i;
3107 for (x = basic_block_head[i]; x != NULL_RTX; x = NEXT_INSN (x))
3109 in_bb_p[ INSN_UID(x)]
3110 = (in_bb_p[ INSN_UID(x)] == NOT_IN_BB)
3111 ? IN_ONE_BB : IN_MULTIPLE_BB;
3112 if (x == basic_block_end[i])
3117 for (tmp_rtx = rtx_first; NULL != tmp_rtx; tmp_rtx = NEXT_INSN (tmp_rtx))
3119 if ((bb = start[INSN_UID (tmp_rtx)]) >= 0)
3121 fprintf (outf, ";; Start of basic block %d, registers live:",
3124 EXECUTE_IF_SET_IN_REG_SET (basic_block_live_at_start[bb], 0, i,
3126 fprintf (outf, " %d", i);
3127 if (i < FIRST_PSEUDO_REGISTER)
3128 fprintf (outf, " [%s]",
3134 if (in_bb_p[ INSN_UID(tmp_rtx)] == NOT_IN_BB
3135 && GET_CODE (tmp_rtx) != NOTE
3136 && GET_CODE (tmp_rtx) != BARRIER)
3137 fprintf (outf, ";; Insn is not within a basic block\n");
3138 else if (in_bb_p[ INSN_UID(tmp_rtx)] == IN_MULTIPLE_BB)
3139 fprintf (outf, ";; Insn is in multiple basic blocks\n");
3141 print_rtl_single (outf, tmp_rtx);
3143 if ((bb = end[INSN_UID (tmp_rtx)]) >= 0)
3144 fprintf (outf, ";; End of basic block %d\n", bb);
3152 /* Integer list support. */
3154 /* Allocate a node from list *HEAD_PTR. */
3157 alloc_int_list_node (head_ptr)
3158 int_list_block **head_ptr;
3160 struct int_list_block *first_blk = *head_ptr;
3162 if (first_blk == NULL || first_blk->nodes_left <= 0)
3164 first_blk = (struct int_list_block *) xmalloc (sizeof (struct int_list_block));
3165 first_blk->nodes_left = INT_LIST_NODES_IN_BLK;
3166 first_blk->next = *head_ptr;
3167 *head_ptr = first_blk;
3170 first_blk->nodes_left--;
3171 return &first_blk->nodes[first_blk->nodes_left];
3174 /* Pointer to head of predecessor/successor block list. */
3175 static int_list_block *pred_int_list_blocks;
3177 /* Add a new node to integer list LIST with value VAL.
3178 LIST is a pointer to a list object to allow for different implementations.
3179 If *LIST is initially NULL, the list is empty.
3180 The caller must not care whether the element is added to the front or
3181 to the end of the list (to allow for different implementations). */
3184 add_int_list_node (blk_list, list, val)
3185 int_list_block **blk_list;
3189 int_list_ptr p = alloc_int_list_node (blk_list);
3197 /* Free the blocks of lists at BLK_LIST. */
3200 free_int_list (blk_list)
3201 int_list_block **blk_list;
3203 int_list_block *p, *next;
3205 for (p = *blk_list; p != NULL; p = next)
3211 /* Mark list as empty for the next function we compile. */
3215 /* Predecessor/successor computation. */
3217 /* Mark PRED_BB a precessor of SUCC_BB,
3218 and conversely SUCC_BB a successor of PRED_BB. */
3221 add_pred_succ (pred_bb, succ_bb, s_preds, s_succs, num_preds, num_succs)
3224 int_list_ptr *s_preds;
3225 int_list_ptr *s_succs;
3229 if (succ_bb != EXIT_BLOCK)
3231 add_int_list_node (&pred_int_list_blocks, &s_preds[succ_bb], pred_bb);
3232 num_preds[succ_bb]++;
3234 if (pred_bb != ENTRY_BLOCK)
3236 add_int_list_node (&pred_int_list_blocks, &s_succs[pred_bb], succ_bb);
3237 num_succs[pred_bb]++;
3241 /* Compute the predecessors and successors for each block. */
3243 compute_preds_succs (s_preds, s_succs, num_preds, num_succs)
3244 int_list_ptr *s_preds;
3245 int_list_ptr *s_succs;
3249 int bb, clear_local_bb_vars = 0;
3251 bzero ((char *) s_preds, n_basic_blocks * sizeof (int_list_ptr));
3252 bzero ((char *) s_succs, n_basic_blocks * sizeof (int_list_ptr));
3253 bzero ((char *) num_preds, n_basic_blocks * sizeof (int));
3254 bzero ((char *) num_succs, n_basic_blocks * sizeof (int));
3256 /* This routine can be called after life analysis; in that case
3257 basic_block_drops_in and uid_block_number will not be available
3258 and we must recompute their values. */
3259 if (basic_block_drops_in == NULL || uid_block_number == NULL)
3261 clear_local_bb_vars = 1;
3262 basic_block_drops_in = (char *) alloca (n_basic_blocks);
3263 uid_block_number = (int *) alloca ((get_max_uid () + 1) * sizeof (int));
3265 bzero ((char *) basic_block_drops_in, n_basic_blocks * sizeof (char));
3266 bzero ((char *) uid_block_number, n_basic_blocks * sizeof (int));
3268 /* Scan each basic block setting basic_block_drops_in and
3269 uid_block_number as needed. */
3270 for (bb = 0; bb < n_basic_blocks; bb++)
3272 rtx insn, stop_insn;
3275 stop_insn = NULL_RTX;
3277 stop_insn = basic_block_end[bb-1];
3279 /* Look backwards from the start of this block. Stop if we
3280 hit the start of the function or the end of a previous
3281 block. Don't walk backwards through blocks that are just
3283 for (insn = PREV_INSN (basic_block_head[bb]);
3284 insn && insn != stop_insn && GET_CODE (insn) == NOTE;
3285 insn = PREV_INSN (insn))
3288 /* Never set basic_block_drops_in for the first block. It is
3291 If we stopped on anything other than a BARRIER, then this
3294 basic_block_drops_in[bb] = (insn ? GET_CODE (insn) != BARRIER : 1);
3296 insn = basic_block_head[bb];
3299 BLOCK_NUM (insn) = bb;
3300 if (insn == basic_block_end[bb])
3302 insn = NEXT_INSN (insn);
3307 for (bb = 0; bb < n_basic_blocks; bb++)
3312 head = BLOCK_HEAD (bb);
3314 if (GET_CODE (head) == CODE_LABEL)
3315 for (jump = LABEL_REFS (head);
3317 jump = LABEL_NEXTREF (jump))
3319 if (! INSN_DELETED_P (CONTAINING_INSN (jump))
3320 && (GET_CODE (CONTAINING_INSN (jump)) != NOTE
3321 || (NOTE_LINE_NUMBER (CONTAINING_INSN (jump))
3322 != NOTE_INSN_DELETED)))
3323 add_pred_succ (BLOCK_NUM (CONTAINING_INSN (jump)), bb,
3324 s_preds, s_succs, num_preds, num_succs);
3327 jump = BLOCK_END (bb);
3328 /* If this is a RETURN insn or a conditional jump in the last
3329 basic block, or a non-jump insn in the last basic block, then
3330 this block reaches the exit block. */
3331 if ((GET_CODE (jump) == JUMP_INSN && GET_CODE (PATTERN (jump)) == RETURN)
3332 || (((GET_CODE (jump) == JUMP_INSN
3333 && condjump_p (jump) && !simplejump_p (jump))
3334 || GET_CODE (jump) != JUMP_INSN)
3335 && (bb == n_basic_blocks - 1)))
3336 add_pred_succ (bb, EXIT_BLOCK, s_preds, s_succs, num_preds, num_succs);
3338 if (basic_block_drops_in[bb])
3339 add_pred_succ (bb - 1, bb, s_preds, s_succs, num_preds, num_succs);
3342 add_pred_succ (ENTRY_BLOCK, 0, s_preds, s_succs, num_preds, num_succs);
3345 /* If we allocated any variables in temporary storage, clear out the
3346 pointer to the local storage to avoid dangling pointers. */
3347 if (clear_local_bb_vars)
3349 basic_block_drops_in = NULL;
3350 uid_block_number = NULL;
3356 dump_bb_data (file, preds, succs)
3358 int_list_ptr *preds;
3359 int_list_ptr *succs;
3364 fprintf (file, "BB data\n\n");
3365 for (bb = 0; bb < n_basic_blocks; bb++)
3367 fprintf (file, "BB %d, start %d, end %d\n", bb,
3368 INSN_UID (BLOCK_HEAD (bb)), INSN_UID (BLOCK_END (bb)));
3369 fprintf (file, " preds:");
3370 for (p = preds[bb]; p != NULL; p = p->next)
3372 int pred_bb = INT_LIST_VAL (p);
3373 if (pred_bb == ENTRY_BLOCK)
3374 fprintf (file, " entry");
3376 fprintf (file, " %d", pred_bb);
3378 fprintf (file, "\n");
3379 fprintf (file, " succs:");
3380 for (p = succs[bb]; p != NULL; p = p->next)
3382 int succ_bb = INT_LIST_VAL (p);
3383 if (succ_bb == EXIT_BLOCK)
3384 fprintf (file, " exit");
3386 fprintf (file, " %d", succ_bb);
3388 fprintf (file, "\n");
3390 fprintf (file, "\n");
3393 /* Free basic block data storage. */
3398 free_int_list (&pred_int_list_blocks);
3401 /* Bitmap manipulation routines. */
3403 /* Allocate a simple bitmap of N_ELMS bits. */
3406 sbitmap_alloc (n_elms)
3409 int bytes, size, amt;
3412 size = SBITMAP_SET_SIZE (n_elms);
3413 bytes = size * sizeof (SBITMAP_ELT_TYPE);
3414 amt = (sizeof (struct simple_bitmap_def)
3415 + bytes - sizeof (SBITMAP_ELT_TYPE));
3416 bmap = (sbitmap) xmalloc (amt);
3417 bmap->n_bits = n_elms;
3419 bmap->bytes = bytes;
3423 /* Allocate a vector of N_VECS bitmaps of N_ELMS bits. */
3426 sbitmap_vector_alloc (n_vecs, n_elms)
3429 int i, bytes, offset, elm_bytes, size, amt;
3430 sbitmap *bitmap_vector;
3432 size = SBITMAP_SET_SIZE (n_elms);
3433 bytes = size * sizeof (SBITMAP_ELT_TYPE);
3434 elm_bytes = (sizeof (struct simple_bitmap_def)
3435 + bytes - sizeof (SBITMAP_ELT_TYPE));
3436 amt = (n_vecs * sizeof (sbitmap *)) + (n_vecs * elm_bytes);
3437 bitmap_vector = (sbitmap *) xmalloc (amt);
3439 /* ??? There may be alignment problems, `offset' should be rounded up
3440 each time to account for alignment. Later [if ever]. */
3442 for (i = 0, offset = n_vecs * sizeof (sbitmap *);
3444 i++, offset += elm_bytes)
3446 sbitmap b = (sbitmap) ((char *) bitmap_vector + offset);
3447 bitmap_vector[i] = b;
3453 return bitmap_vector;
3456 /* Copy sbitmap SRC to DST. */
3459 sbitmap_copy (dst, src)
3467 for (i = 0; i < dst->size; i++)
3471 /* Zero all elements in a bitmap. */
3477 bzero ((char *) bmap->elms, bmap->bytes);
3480 /* Set to ones all elements in a bitmap. */
3486 memset (bmap->elms, -1, bmap->bytes);
3489 /* Zero a vector of N_VECS bitmaps. */
3492 sbitmap_vector_zero (bmap, n_vecs)
3498 for (i = 0; i < n_vecs; i++)
3499 sbitmap_zero (bmap[i]);
3502 /* Set to ones a vector of N_VECS bitmaps. */
3505 sbitmap_vector_ones (bmap, n_vecs)
3511 for (i = 0; i < n_vecs; i++)
3512 sbitmap_ones (bmap[i]);
3515 /* Set DST to be A union (B - C).
3517 Return non-zero if any change is made. */
3520 sbitmap_union_of_diff (dst, a, b, c)
3521 sbitmap dst, a, b, c;
3524 sbitmap_ptr dstp, ap, bp, cp;
3531 for (i = 0; i < dst->size; i++)
3533 SBITMAP_ELT_TYPE tmp = *ap | (*bp & ~*cp);
3537 dstp++; ap++; bp++; cp++;
3542 /* Set bitmap DST to the bitwise negation of the bitmap SRC. */
3545 sbitmap_not (dst, src)
3549 sbitmap_ptr dstp, ap;
3553 for (i = 0; i < dst->size; i++)
3555 SBITMAP_ELT_TYPE tmp = ~(*ap);
3561 /* Set the bits in DST to be the difference between the bits
3562 in A and the bits in B. i.e. dst = a - b.
3563 The - operator is implemented as a & (~b). */
3566 sbitmap_difference (dst, a, b)
3570 sbitmap_ptr dstp, ap, bp;
3575 for (i = 0; i < dst->size; i++)
3576 *dstp++ = *ap++ & (~*bp++);
3579 /* Set DST to be (A and B)).
3580 Return non-zero if any change is made. */
3583 sbitmap_a_and_b (dst, a, b)
3587 sbitmap_ptr dstp, ap, bp;
3593 for (i = 0; i < dst->size; i++)
3595 SBITMAP_ELT_TYPE tmp = *ap & *bp;
3603 /* Set DST to be (A or B)).
3604 Return non-zero if any change is made. */
3607 sbitmap_a_or_b (dst, a, b)
3611 sbitmap_ptr dstp, ap, bp;
3617 for (i = 0; i < dst->size; i++)
3619 SBITMAP_ELT_TYPE tmp = *ap | *bp;
3628 /* Set DST to be (A or (B and C)).
3629 Return non-zero if any change is made. */
3632 sbitmap_a_or_b_and_c (dst, a, b, c)
3633 sbitmap dst, a, b, c;
3636 sbitmap_ptr dstp, ap, bp, cp;
3643 for (i = 0; i < dst->size; i++)
3645 SBITMAP_ELT_TYPE tmp = *ap | (*bp & *cp);
3649 dstp++; ap++; bp++; cp++;
3654 /* Set DST to be (A ann (B or C)).
3655 Return non-zero if any change is made. */
3658 sbitmap_a_and_b_or_c (dst, a, b, c)
3659 sbitmap dst, a, b, c;
3662 sbitmap_ptr dstp, ap, bp, cp;
3669 for (i = 0; i < dst->size; i++)
3671 SBITMAP_ELT_TYPE tmp = *ap & (*bp | *cp);
3675 dstp++; ap++; bp++; cp++;
3680 /* Set the bitmap DST to the intersection of SRC of all predecessors or
3681 successors of block number BB (PRED_SUCC says which). */
3684 sbitmap_intersect_of_predsucc (dst, src, bb, pred_succ)
3688 int_list_ptr *pred_succ;
3692 int set_size = dst->size;
3696 /* It is possible that there are no predecessors(/successors).
3697 This can happen for example in unreachable code. */
3701 /* In APL-speak this is the `and' reduction of the empty set and thus
3702 the result is the identity for `and'. */
3707 /* Set result to first predecessor/successor. */
3709 for ( ; ps != NULL; ps = ps->next)
3711 ps_bb = INT_LIST_VAL (ps);
3712 if (ps_bb == ENTRY_BLOCK || ps_bb == EXIT_BLOCK)
3714 sbitmap_copy (dst, src[ps_bb]);
3715 /* Break out since we're only doing first predecessor. */
3721 /* Now do the remaining predecessors/successors. */
3723 for (ps = ps->next; ps != NULL; ps = ps->next)
3728 ps_bb = INT_LIST_VAL (ps);
3729 if (ps_bb == ENTRY_BLOCK || ps_bb == EXIT_BLOCK)
3732 p = src[ps_bb]->elms;
3735 for (i = 0; i < set_size; i++)
3740 /* Set the bitmap DST to the intersection of SRC of all predecessors
3741 of block number BB. */
3744 sbitmap_intersect_of_predecessors (dst, src, bb, s_preds)
3748 int_list_ptr *s_preds;
3750 sbitmap_intersect_of_predsucc (dst, src, bb, s_preds);
3753 /* Set the bitmap DST to the intersection of SRC of all successors
3754 of block number BB. */
3757 sbitmap_intersect_of_successors (dst, src, bb, s_succs)
3761 int_list_ptr *s_succs;
3763 sbitmap_intersect_of_predsucc (dst, src, bb, s_succs);
3766 /* Set the bitmap DST to the union of SRC of all predecessors/successors of
3770 sbitmap_union_of_predsucc (dst, src, bb, pred_succ)
3774 int_list_ptr *pred_succ;
3778 int set_size = dst->size;
3782 /* It is possible that there are no predecessors(/successors).
3783 This can happen for example in unreachable code. */
3787 /* In APL-speak this is the `or' reduction of the empty set and thus
3788 the result is the identity for `or'. */
3793 /* Set result to first predecessor/successor. */
3795 for ( ; ps != NULL; ps = ps->next)
3797 ps_bb = INT_LIST_VAL (ps);
3798 if (ps_bb == ENTRY_BLOCK || ps_bb == EXIT_BLOCK)
3800 sbitmap_copy (dst, src[ps_bb]);
3801 /* Break out since we're only doing first predecessor. */
3807 /* Now do the remaining predecessors/successors. */
3809 for (ps = ps->next; ps != NULL; ps = ps->next)
3814 ps_bb = INT_LIST_VAL (ps);
3815 if (ps_bb == ENTRY_BLOCK || ps_bb == EXIT_BLOCK)
3818 p = src[ps_bb]->elms;
3821 for (i = 0; i < set_size; i++)
3826 /* Set the bitmap DST to the union of SRC of all predecessors of
3830 sbitmap_union_of_predecessors (dst, src, bb, s_preds)
3834 int_list_ptr *s_preds;
3836 sbitmap_union_of_predsucc (dst, src, bb, s_preds);
3839 /* Compute dominator relationships. */
3841 compute_dominators (dominators, post_dominators, s_preds, s_succs)
3842 sbitmap *dominators;
3843 sbitmap *post_dominators;
3844 int_list_ptr *s_preds;
3845 int_list_ptr *s_succs;
3847 int bb, changed, passes;
3848 sbitmap *temp_bitmap;
3850 temp_bitmap = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks);
3851 sbitmap_vector_ones (dominators, n_basic_blocks);
3852 sbitmap_vector_ones (post_dominators, n_basic_blocks);
3853 sbitmap_vector_zero (temp_bitmap, n_basic_blocks);
3855 sbitmap_zero (dominators[0]);
3856 SET_BIT (dominators[0], 0);
3858 sbitmap_zero (post_dominators[n_basic_blocks-1]);
3859 SET_BIT (post_dominators[n_basic_blocks-1], 0);
3866 for (bb = 1; bb < n_basic_blocks; bb++)
3868 sbitmap_intersect_of_predecessors (temp_bitmap[bb], dominators,
3870 SET_BIT (temp_bitmap[bb], bb);
3871 changed |= sbitmap_a_and_b (dominators[bb],
3874 sbitmap_intersect_of_successors (temp_bitmap[bb], post_dominators,
3876 SET_BIT (temp_bitmap[bb], bb);
3877 changed |= sbitmap_a_and_b (post_dominators[bb],
3878 post_dominators[bb],