![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to flow.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [GCC 1.x] / gcc|
Return to flow.c CVS log | Up to [GCC 1.x] / gcc |
1.1 root 1: /* Data flow analysis for GNU compiler.
1.1.1.2 root 2: Copyright (C) 1987, 1988 Free Software Foundation, Inc.
1.1 root 3:
4: This file is part of GNU CC.
5:
1.1.1.12 root 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 1, or (at your option)
9: any later version.
10:
1.1 root 11: GNU CC is distributed in the hope that it will be useful,
1.1.1.12 root 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.
15:
16: You should have received a copy of the GNU General Public License
17: along with GNU CC; see the file COPYING. If not, write to
18: the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA. */
1.1 root 19:
20:
21: /* This file contains the data flow analysis pass of the compiler.
22: It computes data flow information
23: which tells combine_instructions which insns to consider combining
24: and controls register allocation.
25:
26: Additional data flow information that is too bulky to record
27: is generated during the analysis, and is used at that time to
28: create autoincrement and autodecrement addressing.
29:
30: The first step is dividing the function into basic blocks.
31: find_basic_blocks does this. Then life_analysis determines
32: where each register is live and where it is dead.
33:
34: ** find_basic_blocks **
35:
36: find_basic_blocks divides the current function's rtl
37: into basic blocks. It records the beginnings and ends of the
38: basic blocks in the vectors basic_block_head and basic_block_end,
39: and the number of blocks in n_basic_blocks.
40:
41: find_basic_blocks also finds any unreachable loops
42: and deletes them.
43:
44: ** life_analysis **
45:
46: life_analysis is called immediately after find_basic_blocks.
47: It uses the basic block information to determine where each
48: hard or pseudo register is live.
49:
50: ** live-register info **
51:
52: The information about where each register is live is in two parts:
53: the REG_NOTES of insns, and the vector basic_block_live_at_start.
54:
55: basic_block_live_at_start has an element for each basic block,
56: and the element is a bit-vector with a bit for each hard or pseudo
57: register. The bit is 1 if the register is live at the beginning
58: of the basic block.
59:
60: To each insn's REG_NOTES is added an element for each register
61: that is live before the insn or set by the insn, but is dead
62: after the insn.
63:
64: To determine which registers are live after any insn, one can
65: start from the beginning of the basic block and scan insns, noting
66: which registers are set by each insn and which die there.
67:
68: ** Other actions of life_analysis **
69:
70: life_analysis sets up the LOG_LINKS fields of insns because the
71: information needed to do so is readily available.
72:
73: life_analysis deletes insns whose only effect is to store a value
74: that is never used.
75:
76: life_analysis notices cases where a reference to a register as
77: a memory address can be combined with a preceding or following
78: incrementation or decrementation of the register. The separate
79: instruction to increment or decrement is deleted and the address
80: is changed to a POST_INC or similar rtx.
81:
82: Each time an incrementing or decrementing address is created,
83: a REG_INC element is added to the insn's REG_NOTES list.
84:
85: life_analysis fills in certain vectors containing information about
86: register usage: reg_n_refs, reg_n_deaths, reg_n_sets,
1.1.1.14 root 87: reg_live_length, reg_n_calls_crosses and reg_basic_block. */
1.1 root 88:
89: #include <stdio.h>
90: #include "config.h"
91: #include "rtl.h"
92: #include "basic-block.h"
93: #include "regs.h"
1.1.1.2 root 94: #include "hard-reg-set.h"
95: #include "flags.h"
1.1 root 96:
1.1.1.14 root 97: #include "obstack.h"
98: #define obstack_chunk_alloc xmalloc
99: #define obstack_chunk_free free
100:
101: extern int xmalloc ();
102: extern void free ();
103:
1.1 root 104: /* Get the basic block number of an insn.
105: This info should not be expected to remain available
106: after the end of life_analysis. */
107:
108: #define BLOCK_NUM(INSN) uid_block_number[INSN_UID (INSN)]
109:
110: /* This is where the BLOCK_NUM values are really stored.
111: This is set up by find_basic_blocks and used there and in life_analysis,
112: and then freed. */
113:
114: static short *uid_block_number;
115:
1.1.1.2 root 116: /* INSN_VOLATILE (insn) is 1 if the insn refers to anything volatile. */
117:
118: #define INSN_VOLATILE(INSN) uid_volatile[INSN_UID (INSN)]
119: static char *uid_volatile;
120:
1.1 root 121: /* Number of basic blocks in the current function. */
122:
123: int n_basic_blocks;
124:
125: /* Maximum register number used in this function, plus one. */
126:
127: int max_regno;
128:
129: /* Indexed by n, gives number of basic block that (REG n) is used in.
1.1.1.10 root 130: If the value is REG_BLOCK_GLOBAL (-2),
131: it means (REG n) is used in more than one basic block.
132: REG_BLOCK_UNKNOWN (-1) means it hasn't been seen yet so we don't know.
1.1 root 133: This information remains valid for the rest of the compilation
134: of the current function; it is used to control register allocation. */
135:
136: short *reg_basic_block;
137:
138: /* Indexed by n, gives number of times (REG n) is used or set, each
139: weighted by its loop-depth.
140: This information remains valid for the rest of the compilation
141: of the current function; it is used to control register allocation. */
142:
143: short *reg_n_refs;
144:
145: /* Indexed by n, gives number of times (REG n) is set.
146: This information remains valid for the rest of the compilation
147: of the current function; it is used to control register allocation. */
148:
149: short *reg_n_sets;
150:
151: /* Indexed by N, gives number of places register N dies.
152: This information remains valid for the rest of the compilation
153: of the current function; it is used to control register allocation. */
154:
155: short *reg_n_deaths;
156:
157: /* Indexed by N, gives 1 if that reg is live across any CALL_INSNs.
158: This information remains valid for the rest of the compilation
159: of the current function; it is used to control register allocation. */
160:
1.1.1.12 root 161: int *reg_n_calls_crossed;
1.1 root 162:
1.1.1.15! root 163: /* Indexed by N, gives the uid of the first insn that mentions reg N,
! 164: provided that reg is local to one basic block.
! 165: The value here is undefined otherwise. */
! 166:
! 167: rtx *reg_first_use;
! 168:
1.1 root 169: /* Total number of instructions at which (REG n) is live.
170: The larger this is, the less priority (REG n) gets for
171: allocation in a real register.
172: This information remains valid for the rest of the compilation
1.1.1.2 root 173: of the current function; it is used to control register allocation.
174:
175: local-alloc.c may alter this number to change the priority.
176:
177: Negative values are special.
178: -1 is used to mark a pseudo reg which has a constant or memory equivalent
179: and is used infrequently enough that it should not get a hard register.
180: -2 is used to mark a pseudo reg for a parameter, when a frame pointer
181: is not required. global-alloc.c makes an allocno for this but does
182: not try to assign a hard register to it. */
1.1 root 183:
184: int *reg_live_length;
185:
186: /* Element N is the next insn that uses (hard or pseudo) register number N
187: within the current basic block; or zero, if there is no such insn.
188: This is valid only during the final backward scan in propagate_block. */
189:
190: static rtx *reg_next_use;
191:
192: /* Size of a regset for the current function,
193: in (1) bytes and (2) elements. */
194:
195: int regset_bytes;
196: int regset_size;
197:
198: /* Element N is first insn in basic block N.
199: This info lasts until we finish compiling the function. */
200:
201: rtx *basic_block_head;
202:
203: /* Element N is last insn in basic block N.
204: This info lasts until we finish compiling the function. */
205:
206: rtx *basic_block_end;
207:
208: /* Element N is a regset describing the registers live
209: at the start of basic block N.
210: This info lasts until we finish compiling the function. */
211:
212: regset *basic_block_live_at_start;
213:
1.1.1.2 root 214: /* Regset of regs live when calls to `setjmp'-like functions happen. */
215:
216: regset regs_live_at_setjmp;
217:
1.1 root 218: /* Element N is nonzero if control can drop into basic block N
219: from the preceding basic block. Freed after life_analysis. */
220:
1.1.1.2 root 221: static char *basic_block_drops_in;
1.1 root 222:
223: /* Element N is depth within loops of basic block number N.
224: Freed after life_analysis. */
225:
1.1.1.2 root 226: static short *basic_block_loop_depth;
1.1 root 227:
228: /* Element N nonzero if basic block N can actually be reached.
229: Vector exists only during find_basic_blocks. */
230:
1.1.1.2 root 231: static char *block_live_static;
1.1 root 232:
233: /* Depth within loops of basic block being scanned for lifetime analysis,
234: plus one. This is the weight attached to references to registers. */
235:
1.1.1.2 root 236: static int loop_depth;
237:
238: /* Define AUTO_INC_DEC if machine has any kind of incrementing
239: or decrementing addressing. */
240:
241: #ifdef HAVE_PRE_DECREMENT
242: #define AUTO_INC_DEC
243: #endif
244:
245: #ifdef HAVE_PRE_INCREMENT
246: #define AUTO_INC_DEC
247: #endif
248:
249: #ifdef HAVE_POST_DECREMENT
250: #define AUTO_INC_DEC
251: #endif
252:
253: #ifdef HAVE_POST_INCREMENT
254: #define AUTO_INC_DEC
255: #endif
1.1 root 256:
257: /* Forward declarations */
258: static void find_basic_blocks ();
259: static void life_analysis ();
260: static void mark_label_ref ();
261: void allocate_for_life_analysis (); /* Used also in stupid_life_analysis */
262: static void init_regset_vector ();
263: static void propagate_block ();
264: static void mark_set_regs ();
265: static void mark_used_regs ();
266: static int insn_dead_p ();
1.1.1.10 root 267: static int libcall_dead_p ();
1.1 root 268: static int try_pre_increment ();
269: static int try_pre_increment_1 ();
270: static rtx find_use_as_address ();
1.1.1.2 root 271: void dump_flow_info ();
1.1 root 272:
273: /* Find basic blocks of the current function and perform data flow analysis.
274: F is the first insn of the function and NREGS the number of register numbers
275: in use. */
276:
277: void
278: flow_analysis (f, nregs, file)
279: rtx f;
280: int nregs;
281: FILE *file;
282: {
283: register rtx insn;
284: register int i;
285: register int max_uid = 0;
286:
287: /* Count the basic blocks. Also find maximum insn uid value used. */
288:
289: {
290: register RTX_CODE prev_code = JUMP_INSN;
291: register RTX_CODE code;
292:
293: for (insn = f, i = 0; insn; insn = NEXT_INSN (insn))
294: {
295: code = GET_CODE (insn);
296: if (INSN_UID (insn) > max_uid)
297: max_uid = INSN_UID (insn);
298: if (code == CODE_LABEL
299: || (prev_code != INSN && prev_code != CALL_INSN
300: && prev_code != CODE_LABEL
301: && (code == INSN || code == CALL_INSN || code == JUMP_INSN)))
302: i++;
303: if (code != NOTE)
304: prev_code = code;
305: }
306: }
307:
308: /* Allocate some tables that last till end of compiling this function
309: and some needed only in find_basic_blocks and life_analysis. */
310:
311: n_basic_blocks = i;
312: basic_block_head = (rtx *) oballoc (n_basic_blocks * sizeof (rtx));
313: basic_block_end = (rtx *) oballoc (n_basic_blocks * sizeof (rtx));
314: basic_block_drops_in = (char *) alloca (n_basic_blocks);
315: basic_block_loop_depth = (short *) alloca (n_basic_blocks * sizeof (short));
316: uid_block_number = (short *) alloca ((max_uid + 1) * sizeof (short));
1.1.1.2 root 317: uid_volatile = (char *) alloca (max_uid + 1);
318: bzero (uid_volatile, max_uid + 1);
1.1 root 319:
320: find_basic_blocks (f);
321: life_analysis (f, nregs);
322: if (file)
323: dump_flow_info (file);
324:
325: basic_block_drops_in = 0;
326: uid_block_number = 0;
327: basic_block_loop_depth = 0;
328: }
329:
330: /* Find all basic blocks of the function whose first insn is F.
331: Store the correct data in the tables that describe the basic blocks,
332: set up the chains of references for each CODE_LABEL, and
333: delete any entire basic blocks that cannot be reached. */
334:
335: static void
336: find_basic_blocks (f)
337: rtx f;
338: {
339: register rtx insn;
340: register int i;
341:
342: /* Initialize the ref chain of each label to 0. */
343: /* Record where all the blocks start and end and their depth in loops. */
344: /* For each insn, record the block it is in. */
345:
346: {
347: register RTX_CODE prev_code = JUMP_INSN;
348: register RTX_CODE code;
349: int depth = 1;
350:
351: for (insn = f, i = -1; insn; insn = NEXT_INSN (insn))
352: {
353: code = GET_CODE (insn);
354: if (code == NOTE)
355: {
356: if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG)
357: depth++;
358: else if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END)
359: depth--;
360: }
361: else if (code == CODE_LABEL
362: || (prev_code != INSN && prev_code != CALL_INSN
363: && prev_code != CODE_LABEL
364: && (code == INSN || code == CALL_INSN || code == JUMP_INSN)))
365: {
366: basic_block_head[++i] = insn;
367: basic_block_end[i] = insn;
368: basic_block_loop_depth[i] = depth;
369: if (code == CODE_LABEL)
370: LABEL_REFS (insn) = insn;
371: }
372: else if (code == INSN || code == CALL_INSN || code == JUMP_INSN)
373: basic_block_end[i] = insn;
374: BLOCK_NUM (insn) = i;
375: if (code != NOTE)
376: prev_code = code;
377: }
1.1.1.4 root 378: if (i + 1 != n_basic_blocks)
379: abort ();
1.1 root 380: }
381:
382: /* Record which basic blocks control can drop in to. */
383:
384: {
385: register int i;
386: for (i = 0; i < n_basic_blocks; i++)
387: {
388: register rtx insn = PREV_INSN (basic_block_head[i]);
1.1.1.2 root 389: /* TEMP1 is used to avoid a bug in Sequent's compiler. */
390: register int temp1;
1.1 root 391: while (insn && GET_CODE (insn) == NOTE)
392: insn = PREV_INSN (insn);
1.1.1.2 root 393: temp1 = insn && GET_CODE (insn) != BARRIER;
394: basic_block_drops_in[i] = temp1;
1.1 root 395: }
396: }
397:
398: /* Now find which basic blocks can actually be reached
399: and put all jump insns' LABEL_REFS onto the ref-chains
400: of their target labels. */
401:
402: if (n_basic_blocks > 0)
403: {
404: register char *block_live = (char *) alloca (n_basic_blocks);
405: register char *block_marked = (char *) alloca (n_basic_blocks);
406: int something_marked = 1;
407:
408: /* Initialize with just block 0 reachable and no blocks marked. */
409:
410: bzero (block_live, n_basic_blocks);
411: bzero (block_marked, n_basic_blocks);
412: block_live[0] = 1;
413: block_live_static = block_live;
414:
415: /* Pass over all blocks, marking each block that is reachable
416: and has not yet been marked.
417: Keep doing this until, in one pass, no blocks have been marked.
418: Then blocks_live and blocks_marked are identical and correct.
419: In addition, all jumps actually reachable have been marked. */
420:
421: while (something_marked)
422: {
423: something_marked = 0;
424: for (i = 0; i < n_basic_blocks; i++)
425: if (block_live[i] && !block_marked[i])
426: {
427: block_marked[i] = 1;
428: something_marked = 1;
429: if (i + 1 < n_basic_blocks && basic_block_drops_in[i + 1])
430: block_live[i + 1] = 1;
431: insn = basic_block_end[i];
432: if (GET_CODE (insn) == JUMP_INSN)
433: mark_label_ref (PATTERN (insn), insn, 0);
434: }
435: }
436:
437: /* Now delete the code for any basic blocks that can't be reached.
438: They can occur because jump_optimize does not recognize
439: unreachable loops as unreachable. */
440:
441: for (i = 0; i < n_basic_blocks; i++)
442: if (!block_live[i])
443: {
444: insn = basic_block_head[i];
445: while (1)
446: {
1.1.1.2 root 447: if (GET_CODE (insn) == BARRIER)
448: abort ();
1.1 root 449: if (GET_CODE (insn) != NOTE)
450: {
451: PUT_CODE (insn, NOTE);
452: NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
453: NOTE_SOURCE_FILE (insn) = 0;
454: }
455: if (insn == basic_block_end[i])
1.1.1.2 root 456: {
457: /* BARRIERs are between basic blocks, not part of one.
458: Delete a BARRIER if the preceding jump is deleted.
459: We cannot alter a BARRIER into a NOTE
460: because it is too short; but we can really delete
461: it because it is not part of a basic block. */
462: if (NEXT_INSN (insn) != 0
463: && GET_CODE (NEXT_INSN (insn)) == BARRIER)
464: delete_insn (NEXT_INSN (insn));
465: break;
466: }
1.1 root 467: insn = NEXT_INSN (insn);
468: }
469: /* Each time we delete some basic blocks,
470: see if there is a jump around them that is
471: being turned into a no-op. If so, delete it. */
472:
473: if (block_live[i - 1])
474: {
475: register int j;
476: for (j = i; j < n_basic_blocks; j++)
477: if (block_live[j])
478: {
1.1.1.6 root 479: rtx label;
1.1 root 480: insn = basic_block_end[i - 1];
481: if (GET_CODE (insn) == JUMP_INSN
1.1.1.6 root 482: /* An unconditional jump is the only possibility
483: we must check for, since a conditional one
484: would make these blocks live. */
485: && simplejump_p (insn)
486: && (label = XEXP (SET_SRC (PATTERN (insn)), 0), 1)
487: && INSN_UID (label) != 0
488: && BLOCK_NUM (label) == j)
1.1 root 489: {
490: PUT_CODE (insn, NOTE);
491: NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
492: NOTE_SOURCE_FILE (insn) = 0;
1.1.1.2 root 493: if (GET_CODE (NEXT_INSN (insn)) != BARRIER)
494: abort ();
495: delete_insn (NEXT_INSN (insn));
1.1 root 496: }
497: break;
498: }
499: }
500: }
501: }
502: }
503:
504: /* Check expression X for label references;
505: if one is found, add INSN to the label's chain of references.
506:
507: CHECKDUP means check for and avoid creating duplicate references
508: from the same insn. Such duplicates do no serious harm but
509: can slow life analysis. CHECKDUP is set only when duplicates
510: are likely. */
511:
512: static void
513: mark_label_ref (x, insn, checkdup)
514: rtx x, insn;
515: int checkdup;
516: {
517: register RTX_CODE code = GET_CODE (x);
518: register int i;
519: register char *fmt;
520:
521: if (code == LABEL_REF)
522: {
523: register rtx label = XEXP (x, 0);
524: register rtx y;
525: if (GET_CODE (label) != CODE_LABEL)
1.1.1.4 root 526: abort ();
1.1.1.2 root 527: /* If the label was never emitted, this insn is junk,
528: but avoid a crash trying to refer to BLOCK_NUM (label).
529: This can happen as a result of a syntax error
530: and a diagnostic has already been printed. */
531: if (INSN_UID (label) == 0)
532: return;
1.1 root 533: CONTAINING_INSN (x) = insn;
534: /* if CHECKDUP is set, check for duplicate ref from same insn
535: and don't insert. */
536: if (checkdup)
537: for (y = LABEL_REFS (label); y != label; y = LABEL_NEXTREF (y))
538: if (CONTAINING_INSN (y) == insn)
539: return;
540: LABEL_NEXTREF (x) = LABEL_REFS (label);
541: LABEL_REFS (label) = x;
542: block_live_static[BLOCK_NUM (label)] = 1;
543: return;
544: }
545:
546: fmt = GET_RTX_FORMAT (code);
547: for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
548: {
549: if (fmt[i] == 'e')
550: mark_label_ref (XEXP (x, i), insn, 0);
551: if (fmt[i] == 'E')
552: {
553: register int j;
554: for (j = 0; j < XVECLEN (x, i); j++)
555: mark_label_ref (XVECEXP (x, i, j), insn, 1);
556: }
557: }
558: }
559:
560: /* Determine the which registers are live at the start of each
561: basic block of the function whose first insn is F.
562: NREGS is the number of registers used in F.
563: We allocate the vector basic_block_live_at_start
564: and the regsets that it points to, and fill them with the data.
565: regset_size and regset_bytes are also set here. */
566:
567: static void
568: life_analysis (f, nregs)
569: rtx f;
570: int nregs;
571: {
572: register regset tem;
573: int first_pass;
574: int changed;
575: /* For each basic block, a bitmask of regs
576: live on exit from the block. */
577: regset *basic_block_live_at_end;
578: /* For each basic block, a bitmask of regs
579: live on entry to a successor-block of this block.
580: If this does not match basic_block_live_at_end,
581: that must be updated, and the block must be rescanned. */
582: regset *basic_block_new_live_at_end;
583: /* For each basic block, a bitmask of regs
584: whose liveness at the end of the basic block
585: can make a difference in which regs are live on entry to the block.
586: These are the regs that are set within the basic block,
587: possibly excluding those that are used after they are set. */
588: regset *basic_block_significant;
589: register int i;
1.1.1.2 root 590: rtx insn;
1.1 root 591:
1.1.1.14 root 592: struct obstack flow_obstack;
593:
594: obstack_init (&flow_obstack);
595:
1.1 root 596: max_regno = nregs;
597:
598: bzero (regs_ever_live, sizeof regs_ever_live);
599:
600: /* Allocate and zero out many data structures
601: that will record the data from lifetime analysis. */
602:
603: allocate_for_life_analysis ();
604:
605: reg_next_use = (rtx *) alloca (nregs * sizeof (rtx));
606: bzero (reg_next_use, nregs * sizeof (rtx));
607:
608: /* Set up several regset-vectors used internally within this function.
609: Their meanings are documented above, with their declarations. */
610:
611: basic_block_live_at_end = (regset *) alloca (n_basic_blocks * sizeof (regset));
1.1.1.14 root 612: /* Don't use alloca since that leads to a crash rather than an error message
613: if there isn't enough space.
614: Don't use oballoc since we may need to allocate other things during
615: this function on the temporary obstack. */
616: tem = (regset) obstack_alloc (&flow_obstack, n_basic_blocks * regset_bytes);
1.1 root 617: bzero (tem, n_basic_blocks * regset_bytes);
618: init_regset_vector (basic_block_live_at_end, tem, n_basic_blocks, regset_bytes);
619:
620: basic_block_new_live_at_end = (regset *) alloca (n_basic_blocks * sizeof (regset));
1.1.1.14 root 621: tem = (regset) obstack_alloc (&flow_obstack, n_basic_blocks * regset_bytes);
1.1 root 622: bzero (tem, n_basic_blocks * regset_bytes);
623: init_regset_vector (basic_block_new_live_at_end, tem, n_basic_blocks, regset_bytes);
624:
625: basic_block_significant = (regset *) alloca (n_basic_blocks * sizeof (regset));
1.1.1.14 root 626: tem = (regset) obstack_alloc (&flow_obstack, n_basic_blocks * regset_bytes);
1.1 root 627: bzero (tem, n_basic_blocks * regset_bytes);
628: init_regset_vector (basic_block_significant, tem, n_basic_blocks, regset_bytes);
629:
1.1.1.4 root 630: /* Record which insns refer to any volatile memory
1.1.1.9 root 631: or for any reason can't be deleted just because they are dead stores.
632: Also, delete any insns that copy a register to itself. */
1.1.1.2 root 633:
634: for (insn = f; insn; insn = NEXT_INSN (insn))
1.1.1.4 root 635: {
636: enum rtx_code code1 = GET_CODE (insn);
637: if (code1 == CALL_INSN)
638: INSN_VOLATILE (insn) = 1;
639: else if (code1 == INSN || code1 == JUMP_INSN)
640: {
1.1.1.9 root 641: if (GET_CODE (PATTERN (insn)) == SET
642: && GET_CODE (SET_DEST (PATTERN (insn))) == REG
643: && GET_CODE (SET_SRC (PATTERN (insn))) == REG
644: && REGNO (SET_DEST (PATTERN (insn))) ==
645: REGNO (SET_SRC (PATTERN (insn))))
646: {
647: PUT_CODE (insn, NOTE);
648: NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
649: NOTE_SOURCE_FILE (insn) = 0;
650: }
651: else if (GET_CODE (PATTERN (insn)) != USE)
1.1.1.4 root 652: INSN_VOLATILE (insn) = volatile_refs_p (PATTERN (insn));
1.1.1.15! root 653: /* A SET that makes space on the stack cannot be dead.
! 654: (Such SETs occur only for allocating variable-size data,
! 655: so they will always have a PLUS or MINUS according to the
! 656: direction of stack growth.)
! 657: Even if this function never uses this stack pointer value,
! 658: signal handlers do! */
! 659: else if (code1 == INSN && GET_CODE (PATTERN (insn)) == SET
! 660: && SET_DEST (PATTERN (insn)) == stack_pointer_rtx
1.1.1.6 root 661: #ifdef STACK_GROWS_DOWNWARD
1.1.1.15! root 662: && GET_CODE (SET_SRC (PATTERN (insn))) == MINUS
1.1.1.6 root 663: #else
1.1.1.15! root 664: && GET_CODE (SET_SRC (PATTERN (insn))) == PLUS
1.1.1.6 root 665: #endif
1.1.1.15! root 666: && XEXP (SET_SRC (PATTERN (insn)), 0) == stack_pointer_rtx)
! 667: INSN_VOLATILE (insn) = 1;
! 668: }
1.1.1.4 root 669: }
1.1.1.2 root 670:
671: if (n_basic_blocks > 0)
672: #ifdef EXIT_IGNORE_STACK
673: if (! (EXIT_IGNORE_STACK) || ! frame_pointer_needed)
674: #endif
675: {
676: /* If exiting needs the right stack value,
677: consider the stack pointer live at the end of the function. */
678: basic_block_live_at_end[n_basic_blocks - 1]
679: [STACK_POINTER_REGNUM / REGSET_ELT_BITS]
680: |= 1 << (STACK_POINTER_REGNUM % REGSET_ELT_BITS);
681: basic_block_new_live_at_end[n_basic_blocks - 1]
682: [STACK_POINTER_REGNUM / REGSET_ELT_BITS]
683: |= 1 << (STACK_POINTER_REGNUM % REGSET_ELT_BITS);
684: }
685:
1.1 root 686: /* Propagate life info through the basic blocks
687: around the graph of basic blocks.
688:
689: This is a relaxation process: each time a new register
690: is live at the end of the basic block, we must scan the block
691: to determine which registers are, as a consequence, live at the beginning
692: of that block. These registers must then be marked live at the ends
693: of all the blocks that can transfer control to that block.
694: The process continues until it reaches a fixed point. */
695:
696: first_pass = 1;
697: changed = 1;
698: while (changed)
699: {
700: changed = 0;
701: for (i = n_basic_blocks - 1; i >= 0; i--)
702: {
703: int consider = first_pass;
704: int must_rescan = first_pass;
705: register int j;
706:
707: /* Set CONSIDER if this block needs thinking about at all
708: (that is, if the regs live now at the end of it
709: are not the same as were live at the end of it when
710: we last thought about it).
711: Set must_rescan if it needs to be thought about
712: instruction by instruction (that is, if any additional
713: reg that is live at the end now but was not live there before
714: is one of the significant regs of this basic block). */
715:
716: for (j = 0; j < regset_size; j++)
717: {
718: register int x = basic_block_new_live_at_end[i][j]
719: & ~basic_block_live_at_end[i][j];
720: if (x)
721: consider = 1;
722: if (x & basic_block_significant[i][j])
723: {
724: must_rescan = 1;
725: consider = 1;
726: break;
727: }
728: }
729:
730: if (! consider)
731: continue;
732:
733: /* The live_at_start of this block may be changing,
734: so another pass will be required after this one. */
735: changed = 1;
736:
737: if (! must_rescan)
738: {
739: /* No complete rescan needed;
740: just record those variables newly known live at end
741: as live at start as well. */
742: for (j = 0; j < regset_size; j++)
743: {
744: register int x = basic_block_new_live_at_end[i][j]
745: & ~basic_block_live_at_end[i][j];
746: basic_block_live_at_start[i][j] |= x;
747: basic_block_live_at_end[i][j] |= x;
748: }
749: }
750: else
751: {
752: /* Update the basic_block_live_at_start
753: by propagation backwards through the block. */
754: bcopy (basic_block_new_live_at_end[i],
755: basic_block_live_at_end[i], regset_bytes);
756: bcopy (basic_block_live_at_end[i],
757: basic_block_live_at_start[i], regset_bytes);
758: propagate_block (basic_block_live_at_start[i],
759: basic_block_head[i], basic_block_end[i], 0,
760: first_pass ? basic_block_significant[i] : 0,
761: i);
762: }
763:
764: {
765: register rtx jump, head;
766: /* Update the basic_block_new_live_at_end's of the block
767: that falls through into this one (if any). */
768: head = basic_block_head[i];
769: jump = PREV_INSN (head);
770: if (basic_block_drops_in[i])
771: {
1.1.1.14 root 772: register int from_block = BLOCK_NUM (jump);
1.1 root 773: register int j;
774: for (j = 0; j < regset_size; j++)
775: basic_block_new_live_at_end[from_block][j]
776: |= basic_block_live_at_start[i][j];
777: }
778: /* Update the basic_block_new_live_at_end's of
779: all the blocks that jump to this one. */
780: if (GET_CODE (head) == CODE_LABEL)
781: for (jump = LABEL_REFS (head);
782: jump != head;
783: jump = LABEL_NEXTREF (jump))
784: {
1.1.1.14 root 785: register int from_block = BLOCK_NUM (CONTAINING_INSN (jump));
1.1 root 786: register int j;
787: for (j = 0; j < regset_size; j++)
788: basic_block_new_live_at_end[from_block][j]
789: |= basic_block_live_at_start[i][j];
790: }
791: }
1.1.1.13 root 792: #ifdef USE_C_ALLOCA
793: alloca (0);
794: #endif
1.1 root 795: }
796: first_pass = 0;
797: }
798:
1.1.1.5 root 799: #if 0 /* This seems unnecessary; life at start of function shouldn't
800: mean that the reg is live in more than one basic block. */
801:
1.1.1.2 root 802: /* Process the regs live at the beginning of the function.
803: Mark them as not local to any one basic block. */
804:
805: if (n_basic_blocks > 0)
806: for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
807: if (basic_block_live_at_start[0][i / REGSET_ELT_BITS]
808: & (1 << (i % REGSET_ELT_BITS)))
1.1.1.4 root 809: reg_basic_block[i] = REG_BLOCK_GLOBAL;
1.1.1.5 root 810: #endif
1.1.1.2 root 811:
1.1 root 812: /* Now the life information is accurate.
813: Make one more pass over each basic block
814: to delete dead stores, create autoincrement addressing
815: and record how many times each register is used, is set, or dies.
816:
817: To save time, we operate directly in basic_block_live_at_end[i],
818: thus destroying it (in fact, converting it into a copy of
819: basic_block_live_at_start[i]). This is ok now because
820: basic_block_live_at_end[i] is no longer used past this point. */
821:
822: for (i = 0; i < n_basic_blocks; i++)
823: {
824: propagate_block (basic_block_live_at_end[i],
825: basic_block_head[i], basic_block_end[i], 1, 0, i);
1.1.1.13 root 826: #ifdef USE_C_ALLOCA
827: alloca (0);
828: #endif
1.1 root 829: }
1.1.1.14 root 830:
1.1.1.15! root 831: #if 0
1.1.1.14 root 832: /* Something live during a setjmp should not be put in a register
833: on certain machines which restore regs from stack frames
834: rather than from the jmpbuf.
835: But we don't need to do this for the user's variables, since
836: ANSI says only volatile variables need this. */
837: #ifdef LONGJMP_RESTORE_FROM_STACK
838: for (i = FIRST_PSEUDO_REGISTER; i < nregs; i++)
839: if (regs_live_at_setjmp[i / REGSET_ELT_BITS] & (1 << (i % REGSET_ELT_BITS))
840: && regno_reg_rtx[i] != 0 && ! REG_USERVAR_P (regno_reg_rtx[i]))
841: {
842: reg_live_length[i] = -1;
843: reg_basic_block[i] = -1;
844: }
845: #endif
1.1.1.15! root 846: #endif
! 847:
! 848: /* We have a problem with any pseudoreg that
! 849: lives across the setjmp. ANSI says that if a
! 850: user variable does not change in value
! 851: between the setjmp and the longjmp, then the longjmp preserves it.
! 852: This includes longjmp from a place where the pseudo appears dead.
! 853: (In principle, the value still exists if it is in scope.)
! 854: If the pseudo goes in a hard reg, some other value may occupy
! 855: that hard reg where this pseudo is dead, thus clobbering the pseudo.
! 856: Conclusion: such a pseudo must not go in a hard reg. */
! 857: for (i = FIRST_PSEUDO_REGISTER; i < nregs; i++)
! 858: if (regs_live_at_setjmp[i / REGSET_ELT_BITS] & (1 << (i % REGSET_ELT_BITS))
! 859: && regno_reg_rtx[i] != 0)
! 860: {
! 861: reg_live_length[i] = -1;
! 862: reg_basic_block[i] = -1;
! 863: }
1.1.1.14 root 864:
865: obstack_free (&flow_obstack, 0);
1.1 root 866: }
867:
868: /* Subroutines of life analysis. */
869:
870: /* Allocate the permanent data structures that represent the results
871: of life analysis. Not static since used also for stupid life analysis. */
872:
873: void
874: allocate_for_life_analysis ()
875: {
876: register int i;
877: register regset tem;
878:
879: regset_size = ((max_regno + REGSET_ELT_BITS - 1) / REGSET_ELT_BITS);
880: regset_bytes = regset_size * sizeof (*(regset)0);
881:
882: reg_n_refs = (short *) oballoc (max_regno * sizeof (short));
883: bzero (reg_n_refs, max_regno * sizeof (short));
884:
885: reg_n_sets = (short *) oballoc (max_regno * sizeof (short));
886: bzero (reg_n_sets, max_regno * sizeof (short));
887:
888: reg_n_deaths = (short *) oballoc (max_regno * sizeof (short));
889: bzero (reg_n_deaths, max_regno * sizeof (short));
890:
1.1.1.15! root 891: reg_first_use = (rtx *) oballoc (max_regno * sizeof (rtx));
! 892: bzero (reg_first_use, max_regno * sizeof (rtx));
! 893:
1.1 root 894: reg_live_length = (int *) oballoc (max_regno * sizeof (int));
895: bzero (reg_live_length, max_regno * sizeof (int));
896:
1.1.1.12 root 897: reg_n_calls_crossed = (int *) oballoc (max_regno * sizeof (int));
898: bzero (reg_n_calls_crossed, max_regno * sizeof (int));
1.1 root 899:
900: reg_basic_block = (short *) oballoc (max_regno * sizeof (short));
901: for (i = 0; i < max_regno; i++)
1.1.1.4 root 902: reg_basic_block[i] = REG_BLOCK_UNKNOWN;
1.1 root 903:
904: basic_block_live_at_start = (regset *) oballoc (n_basic_blocks * sizeof (regset));
905: tem = (regset) oballoc (n_basic_blocks * regset_bytes);
906: bzero (tem, n_basic_blocks * regset_bytes);
907: init_regset_vector (basic_block_live_at_start, tem, n_basic_blocks, regset_bytes);
1.1.1.2 root 908:
909: regs_live_at_setjmp = (regset) oballoc (regset_bytes);
910: bzero (regs_live_at_setjmp, regset_bytes);
1.1 root 911: }
912:
913: /* Make each element of VECTOR point at a regset,
914: taking the space for all those regsets from SPACE.
915: SPACE is of type regset, but it is really as long as NELTS regsets.
916: BYTES_PER_ELT is the number of bytes in one regset. */
917:
918: static void
919: init_regset_vector (vector, space, nelts, bytes_per_elt)
920: regset *vector;
921: regset space;
922: int nelts;
923: int bytes_per_elt;
924: {
925: register int i;
926: register regset p = space;
927:
928: for (i = 0; i < nelts; i++)
929: {
930: vector[i] = p;
931: p += bytes_per_elt / sizeof (*p);
932: }
933: }
934:
935: /* Compute the registers live at the beginning of a basic block
936: from those live at the end.
937:
938: When called, OLD contains those live at the end.
939: On return, it contains those live at the beginning.
940: FIRST and LAST are the first and last insns of the basic block.
941:
942: FINAL is nonzero if we are doing the final pass which is not
943: for computing the life info (since that has already been done)
944: but for acting on it. On this pass, we delete dead stores,
945: set up the logical links and dead-variables lists of instructions,
946: and merge instructions for autoincrement and autodecrement addresses.
947:
948: SIGNIFICANT is nonzero only the first time for each basic block.
949: If it is nonzero, it points to a regset in which we store
950: a 1 for each register that is set within the block.
951:
952: BNUM is the number of the basic block. */
953:
954: static void
955: propagate_block (old, first, last, final, significant, bnum)
956: register regset old;
957: rtx first;
958: rtx last;
959: int final;
960: regset significant;
961: int bnum;
962: {
963: register rtx insn;
964: rtx prev;
965: regset live;
966: regset dead;
967:
968: /* The following variables are used only if FINAL is nonzero. */
969: /* This vector gets one element for each reg that has been live
970: at any point in the basic block that has been scanned so far.
971: SOMETIMES_MAX says how many elements are in use so far.
972: In each element, OFFSET is the byte-number within a regset
973: for the register described by the element, and BIT is a mask
974: for that register's bit within the byte. */
975: register struct foo { short offset; short bit; } *regs_sometimes_live;
976: int sometimes_max = 0;
977: /* This regset has 1 for each reg that we have seen live so far.
978: It and REGS_SOMETIMES_LIVE are updated together. */
979: regset maxlive;
980:
981: loop_depth = basic_block_loop_depth[bnum];
982:
983: dead = (regset) alloca (regset_bytes);
984: live = (regset) alloca (regset_bytes);
985:
986: if (final)
987: {
988: register int i, offset, bit;
989:
990: maxlive = (regset) alloca (regset_bytes);
991: bcopy (old, maxlive, regset_bytes);
992: regs_sometimes_live
993: = (struct foo *) alloca (max_regno * sizeof (struct foo));
994:
995: /* Process the regs live at the end of the block.
996: Enter them in MAXLIVE and REGS_SOMETIMES_LIVE.
997: Also mark them as not local to any one basic block. */
998:
999: for (offset = 0, i = 0; offset < regset_size; offset++)
1000: for (bit = 1; bit; bit <<= 1, i++)
1001: {
1002: if (i == max_regno)
1003: break;
1004: if (old[offset] & bit)
1005: {
1.1.1.4 root 1006: reg_basic_block[i] = REG_BLOCK_GLOBAL;
1.1 root 1007: regs_sometimes_live[sometimes_max].offset = offset;
1008: regs_sometimes_live[sometimes_max].bit = i % REGSET_ELT_BITS;
1009: sometimes_max++;
1010: }
1011: }
1012: }
1013:
1.1.1.15! root 1014: /* Include any notes at the end of the block in the scan.
! 1015: This is in case the block ends with a call to setjmp. */
! 1016:
! 1017: while (NEXT_INSN (last) != 0 && GET_CODE (NEXT_INSN (last)) == NOTE)
! 1018: last = NEXT_INSN (last);
! 1019:
1.1 root 1020: /* Scan the block an insn at a time from end to beginning. */
1021:
1022: for (insn = last; ; insn = prev)
1023: {
1024: prev = PREV_INSN (insn);
1025:
1.1.1.2 root 1026: /* If this is a call to `setjmp' et al,
1027: warn if any non-volatile datum is live. */
1028:
1029: if (final && GET_CODE (insn) == NOTE
1030: && NOTE_LINE_NUMBER (insn) == NOTE_INSN_SETJMP)
1031: {
1032: int i;
1033: for (i = 0; i < regset_size; i++)
1034: regs_live_at_setjmp[i] |= old[i];
1.1 root 1035: }
1036:
1037: /* Update the life-status of regs for this insn.
1038: First DEAD gets which regs are set in this insn
1039: then LIVE gets which regs are used in this insn.
1040: Then the regs live before the insn
1041: are those live after, with DEAD regs turned off,
1042: and then LIVE regs turned on. */
1043:
1044: if (GET_CODE (insn) == INSN
1045: || GET_CODE (insn) == JUMP_INSN
1046: || GET_CODE (insn) == CALL_INSN)
1047: {
1048: register int i;
1.1.1.2 root 1049: rtx note = find_reg_note (insn, REG_RETVAL, 0);
1050:
1.1 root 1051: /* If an instruction consists of just dead store(s) on final pass,
1052: "delete" it by turning it into a NOTE of type NOTE_INSN_DELETED.
1053: We could really delete it with delete_insn, but that
1054: can cause trouble for first or last insn in a basic block. */
1.1.1.2 root 1055: if (final && insn_dead_p (PATTERN (insn), old, 1)
1056: /* Don't delete something that refers to volatile storage! */
1057: && ! INSN_VOLATILE (insn))
1.1 root 1058: {
1.1.1.10 root 1059: rtx oldpat = PATTERN (insn);
1.1 root 1060: PUT_CODE (insn, NOTE);
1061: NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
1062: NOTE_SOURCE_FILE (insn) = 0;
1.1.1.2 root 1063: /* If this insn is copying the return value from a library call,
1064: delete the entire library call. */
1.1.1.10 root 1065: if (note && libcall_dead_p (oldpat, old))
1.1.1.2 root 1066: {
1067: rtx first = XEXP (note, 0);
1068: rtx prev = insn;
1.1.1.9 root 1069: while (INSN_DELETED_P (first))
1.1.1.2 root 1070: first = NEXT_INSN (first);
1071: while (prev != first)
1072: {
1073: prev = PREV_INSN (prev);
1074: PUT_CODE (prev, NOTE);
1075: NOTE_LINE_NUMBER (prev) = NOTE_INSN_DELETED;
1076: NOTE_SOURCE_FILE (prev) = 0;
1077: }
1078: }
1.1 root 1079: goto flushed;
1080: }
1.1.1.2 root 1081:
1082: for (i = 0; i < regset_size; i++)
1.1 root 1083: {
1.1.1.2 root 1084: dead[i] = 0; /* Faster than bzero here */
1085: live[i] = 0; /* since regset_size is usually small */
1086: }
1.1 root 1087:
1.1.1.2 root 1088: /* See if this is an increment or decrement that can be
1089: merged into a following memory address. */
1090: #ifdef AUTO_INC_DEC
1091: {
1092: register rtx x = PATTERN (insn);
1093: /* Does this instruction increment or decrement a register? */
1094: if (final && GET_CODE (x) == SET
1095: && GET_CODE (SET_DEST (x)) == REG
1096: && (GET_CODE (SET_SRC (x)) == PLUS
1097: || GET_CODE (SET_SRC (x)) == MINUS)
1098: && XEXP (SET_SRC (x), 0) == SET_DEST (x)
1099: && GET_CODE (XEXP (SET_SRC (x), 1)) == CONST_INT
1100: /* Ok, look for a following memory ref we can combine with.
1101: If one is found, change the memory ref to a PRE_INC
1102: or PRE_DEC, cancel this insn, and return 1.
1103: Return 0 if nothing has been done. */
1104: && try_pre_increment_1 (insn))
1105: goto flushed;
1106: }
1107: #endif /* AUTO_INC_DEC */
1.1 root 1108:
1.1.1.2 root 1109: /* If this is not the final pass, and this insn is copying the
1110: value of a library call and it's dead, don't scan the
1111: insns that perform the library call, so that the call's
1112: arguments are not marked live. */
1.1.1.10 root 1113: if (note && insn_dead_p (PATTERN (insn), old, 1)
1114: && libcall_dead_p (PATTERN (insn), old))
1.1.1.3 root 1115: {
1.1.1.4 root 1116: /* Mark the dest reg as `significant'. */
1117: mark_set_regs (old, dead, PATTERN (insn), 0, significant);
1118:
1.1.1.3 root 1119: insn = XEXP (note, 0);
1120: prev = PREV_INSN (insn);
1121: }
1.1.1.9 root 1122: else if (GET_CODE (PATTERN (insn)) == SET
1123: && SET_DEST (PATTERN (insn)) == stack_pointer_rtx
1.1.1.4 root 1124: && GET_CODE (SET_SRC (PATTERN (insn))) == PLUS
1125: && XEXP (SET_SRC (PATTERN (insn)), 0) == stack_pointer_rtx
1126: && GET_CODE (XEXP (SET_SRC (PATTERN (insn)), 1)) == CONST_INT)
1.1.1.10 root 1127: /* We have an insn to pop a constant amount off the stack.
1128: (Such insns use PLUS regardless of the direction of the stack,
1129: and any insn to adjust the stack by a constant is always a pop.)
1130: These insns, if not dead stores, have no effect on life. */
1.1.1.4 root 1131: ;
1.1.1.2 root 1132: else
1133: {
1134: /* LIVE gets the regs used in INSN; DEAD gets those set by it. */
1.1 root 1135: mark_set_regs (old, dead, PATTERN (insn), final ? insn : 0,
1136: significant);
1.1.1.2 root 1137: mark_used_regs (old, live, PATTERN (insn), final, insn);
1.1 root 1138:
1139: /* Update OLD for the registers used or set. */
1140: for (i = 0; i < regset_size; i++)
1141: {
1142: old[i] &= ~dead[i];
1143: old[i] |= live[i];
1144: }
1145:
1.1.1.2 root 1146: if (GET_CODE (insn) == CALL_INSN)
1147: {
1148: register int i;
1149:
1150: /* Each call clobbers all call-clobbered regs.
1151: Note that the function-value reg is one of these, and
1152: mark_set_regs has already had a chance to handle it. */
1153: for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1154: if (call_used_regs[i])
1.1.1.9 root 1155: dead[i / REGSET_ELT_BITS] |=
1156: (1 << (i % REGSET_ELT_BITS));
1.1.1.2 root 1157:
1158: /* The stack ptr is used (honorarily) by a CALL insn. */
1.1.1.9 root 1159: live[STACK_POINTER_REGNUM / REGSET_ELT_BITS]
1.1.1.2 root 1160: |= (1 << (STACK_POINTER_REGNUM % REGSET_ELT_BITS));
1.1.1.9 root 1161: }
1.1.1.2 root 1162:
1.1.1.9 root 1163: /* Update OLD for the registers used or set. */
1164: for (i = 0; i < regset_size; i++)
1165: {
1166: old[i] &= ~dead[i];
1167: old[i] |= live[i];
1168: }
1169:
1170: if (GET_CODE (insn) == CALL_INSN && final)
1171: {
1172: /* Any regs live at the time of a call instruction
1173: must not go in a register clobbered by calls.
1174: Find all regs now live and record this for them. */
1175:
1176: register struct foo *p = regs_sometimes_live;
1177:
1178: for (i = 0; i < sometimes_max; i++, p++)
1179: if (old[p->offset] & (1 << p->bit))
1.1.1.12 root 1180: reg_n_calls_crossed[p->offset * REGSET_ELT_BITS + p->bit]+= 1;
1.1.1.2 root 1181: }
1182: }
1183:
1184: /* On final pass, add any additional sometimes-live regs
1185: into MAXLIVE and REGS_SOMETIMES_LIVE.
1186: Also update counts of how many insns each reg is live at. */
1.1 root 1187:
1.1.1.2 root 1188: if (final)
1189: {
1190: for (i = 0; i < regset_size; i++)
1.1 root 1191: {
1.1.1.2 root 1192: register int diff = live[i] & ~maxlive[i];
1.1 root 1193:
1.1.1.2 root 1194: if (diff)
1195: {
1196: register int regno;
1197: maxlive[i] |= diff;
1198: for (regno = 0; diff && regno < REGSET_ELT_BITS; regno++)
1199: if (diff & (1 << regno))
1200: {
1201: regs_sometimes_live[sometimes_max].offset = i;
1202: regs_sometimes_live[sometimes_max].bit = regno;
1203: diff &= ~ (1 << regno);
1204: sometimes_max++;
1205: }
1206: }
1207: }
1.1 root 1208:
1.1.1.2 root 1209: {
1210: register struct foo *p = regs_sometimes_live;
1211: for (i = 0; i < sometimes_max; i++, p++)
1.1 root 1212: {
1.1.1.2 root 1213: if (old[p->offset] & (1 << p->bit))
1214: reg_live_length[p->offset * REGSET_ELT_BITS + p->bit]++;
1.1 root 1215: }
1.1.1.2 root 1216: }
1.1 root 1217: }
1218: }
1.1.1.2 root 1219: flushed: ;
1.1 root 1220: if (insn == first)
1221: break;
1222: }
1223: }
1224:
1225: /* Return 1 if X (the body of an insn, or part of it) is just dead stores
1226: (SET expressions whose destinations are registers dead after the insn).
1227: NEEDED is the regset that says which regs are alive after the insn. */
1228:
1229: static int
1.1.1.2 root 1230: insn_dead_p (x, needed, strict_low_ok)
1.1 root 1231: rtx x;
1232: regset needed;
1.1.1.2 root 1233: int strict_low_ok;
1.1 root 1234: {
1235: register RTX_CODE code = GET_CODE (x);
1.1.1.2 root 1236: #if 0
1.1 root 1237: /* Make sure insns to set the stack pointer are never deleted. */
1238: needed[STACK_POINTER_REGNUM / REGSET_ELT_BITS]
1239: |= 1 << (STACK_POINTER_REGNUM % REGSET_ELT_BITS);
1.1.1.2 root 1240: #endif
1241:
1242: /* If setting something that's a reg or part of one,
1243: see if that register's altered value will be live. */
1244:
1245: if (code == SET)
1.1 root 1246: {
1.1.1.2 root 1247: register rtx r = SET_DEST (x);
1248: /* A SET that is a subroutine call cannot be dead. */
1249: if (GET_CODE (SET_SRC (x)) == CALL)
1250: return 0;
1251: while (GET_CODE (r) == SUBREG
1252: || (strict_low_ok && GET_CODE (r) == STRICT_LOW_PART)
1253: || GET_CODE (r) == ZERO_EXTRACT
1254: || GET_CODE (r) == SIGN_EXTRACT)
1255: r = SUBREG_REG (r);
1256: if (GET_CODE (r) == REG)
1257: {
1258: register int regno = REGNO (r);
1259: register int offset = regno / REGSET_ELT_BITS;
1260: register int bit = 1 << (regno % REGSET_ELT_BITS);
1.1.1.11 root 1261: return (! (regno < FIRST_PSEUDO_REGISTER && global_regs[regno])
1262: && (needed[offset] & bit) == 0);
1.1.1.2 root 1263: }
1.1 root 1264: }
1.1.1.2 root 1265: /* If performing several activities,
1266: insn is dead if each activity is individually dead.
1267: Also, CLOBBERs and USEs can be ignored; a CLOBBER or USE
1268: that's inside a PARALLEL doesn't make the insn worth keeping. */
1269: else if (code == PARALLEL)
1.1 root 1270: {
1271: register int i = XVECLEN (x, 0);
1272: for (i--; i >= 0; i--)
1.1.1.2 root 1273: {
1274: rtx elt = XVECEXP (x, 0, i);
1275: if (!insn_dead_p (elt, needed, strict_low_ok)
1276: && GET_CODE (elt) != CLOBBER
1277: && GET_CODE (elt) != USE)
1278: return 0;
1279: }
1.1 root 1280: return 1;
1281: }
1.1.1.2 root 1282: /* We do not check CLOBBER or USE here.
1283: An insn consisting of just a CLOBBER or just a USE
1284: should not be deleted. */
1.1 root 1285: return 0;
1286: }
1287:
1.1.1.10 root 1288: /* If X is the last insn in a libcall, and assuming X is dead,
1289: return 1 if the entire library call is dead.
1290: This is true if the source of X is a dead register
1291: (as well as the destination, which we tested already).
1292: If this insn doesn't just copy a register, then we don't
1293: have an ordinary libcall. In that case, cse could not have
1294: managed to substitute the source for the dest later on,
1295: so we can assume the libcall is dead. */
1296:
1297: static int
1298: libcall_dead_p (x, needed)
1299: rtx x;
1300: regset needed;
1301: {
1302: register RTX_CODE code = GET_CODE (x);
1303:
1304: if (code == SET)
1305: {
1306: register rtx r = SET_SRC (x);
1307: if (GET_CODE (r) == REG)
1308: {
1309: register int regno = REGNO (r);
1310: register int offset = regno / REGSET_ELT_BITS;
1311: register int bit = 1 << (regno % REGSET_ELT_BITS);
1312: return (needed[offset] & bit) == 0;
1313: }
1314: }
1315: return 1;
1316: }
1317:
1.1.1.2 root 1318: /* Return 1 if register REGNO was used before it was set.
1319: In other words, if it is live at function entry. */
1.1 root 1320:
1.1.1.2 root 1321: int
1322: regno_uninitialized (regno)
1.1 root 1323: int regno;
1324: {
1.1.1.11 root 1325: if (n_basic_blocks == 0)
1326: return 0;
1327:
1.1.1.2 root 1328: return (basic_block_live_at_start[0][regno / REGSET_ELT_BITS]
1329: & (1 << (regno % REGSET_ELT_BITS)));
1330: }
1331:
1332: /* 1 if register REGNO was alive at a place where `setjmp' was called
1333: and was set more than once. Such regs may be clobbered by `longjmp'. */
1334:
1335: int
1336: regno_clobbered_at_setjmp (regno)
1337: int regno;
1338: {
1339: return (reg_n_sets[regno] > 1
1340: && (regs_live_at_setjmp[regno / REGSET_ELT_BITS]
1341: & (1 << (regno % REGSET_ELT_BITS))));
1.1 root 1342: }
1343:
1344: /* Process the registers that are set within X.
1345: Their bits are set to 1 in the regset DEAD,
1346: because they are dead prior to this insn.
1347:
1348: If INSN is nonzero, it is the insn being processed
1349: and the fact that it is nonzero implies this is the FINAL pass
1350: in propagate_block. In this case, various info about register
1351: usage is stored, LOG_LINKS fields of insns are set up. */
1352:
1353: static void mark_set_1 ();
1354:
1355: static void
1356: mark_set_regs (needed, dead, x, insn, significant)
1357: regset needed;
1358: regset dead;
1359: rtx x;
1360: rtx insn;
1361: regset significant;
1362: {
1363: register RTX_CODE code = GET_CODE (x);
1364:
1365: if (code == SET || code == CLOBBER)
1366: mark_set_1 (needed, dead, x, insn, significant);
1367: else if (code == PARALLEL)
1368: {
1369: register int i;
1370: for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
1371: {
1372: code = GET_CODE (XVECEXP (x, 0, i));
1373: if (code == SET || code == CLOBBER)
1374: mark_set_1 (needed, dead, XVECEXP (x, 0, i), insn, significant);
1375: }
1376: }
1377: }
1378:
1379: /* Process a single SET rtx, X. */
1380:
1381: static void
1382: mark_set_1 (needed, dead, x, insn, significant)
1383: regset needed;
1384: regset dead;
1385: rtx x;
1386: rtx insn;
1387: regset significant;
1388: {
1389: register int regno;
1390: register rtx reg = SET_DEST (x);
1.1.1.13 root 1391: int subreg_p = 0;
1.1 root 1392:
1.1.1.2 root 1393: if (reg == 0)
1394: return;
1.1.1.15! root 1395: /* Modifying just one hardware register of a multi-reg value
! 1396: or just a byte field of a register
! 1397: does not mean the value from before this insn is now dead.
! 1398: But it does mean liveness of that register at the end of the block
! 1399: is significant. */
! 1400: while (GET_CODE (reg) == SUBREG || GET_CODE (reg) == ZERO_EXTRACT
! 1401: || GET_CODE (reg) == SIGN_EXTRACT
! 1402: || GET_CODE (reg) == STRICT_LOW_PART)
! 1403: {
! 1404: if (GET_CODE (reg) == ZERO_EXTRACT
! 1405: || GET_CODE (reg) == SIGN_EXTRACT
! 1406: || (GET_CODE (reg) == SUBREG
! 1407: && REG_SIZE (SUBREG_REG (reg)) > REG_SIZE (reg)))
1.1.1.13 root 1408: subreg_p = 1;
1.1 root 1409:
1.1.1.15! root 1410: reg = XEXP (reg, 0);
1.1 root 1411: }
1412:
1413: if (GET_CODE (reg) == REG
1414: && (regno = REGNO (reg), regno != FRAME_POINTER_REGNUM)
1.1.1.11 root 1415: && regno != ARG_POINTER_REGNUM
1416: && ! (regno < FIRST_PSEUDO_REGISTER && global_regs[regno]))
1.1.1.2 root 1417: /* && regno != STACK_POINTER_REGNUM) -- let's try without this. */
1.1 root 1418: {
1419: register int offset = regno / REGSET_ELT_BITS;
1420: register int bit = 1 << (regno % REGSET_ELT_BITS);
1.1.1.2 root 1421: int is_needed = 0;
1422:
1.1 root 1423: /* Mark it as a significant register for this basic block. */
1424: if (significant)
1425: significant[offset] |= bit;
1.1.1.13 root 1426: /* That's all we do, if we are setting only part of the register. */
1427: if (subreg_p)
1428: return;
1429:
1430: /* If entire register being set, mark it as as dead before this insn. */
1431: dead[offset] |= bit;
1.1.1.2 root 1432: /* A hard reg in a wide mode may really be multiple registers.
1433: If so, mark all of them just like the first. */
1434: if (regno < FIRST_PSEUDO_REGISTER)
1435: {
1.1.1.4 root 1436: int n;
1437:
1438: /* Nothing below is needed for the stack pointer; get out asap.
1439: Eg, log links aren't needed, since combine won't use them. */
1440: if (regno == STACK_POINTER_REGNUM)
1441: return;
1442:
1443: n = HARD_REGNO_NREGS (regno, GET_MODE (reg));
1.1.1.2 root 1444: while (--n > 0)
1445: {
1446: dead[(regno + n) / REGSET_ELT_BITS]
1447: |= 1 << ((regno + n) % REGSET_ELT_BITS);
1448: if (significant)
1449: significant[(regno + n) / REGSET_ELT_BITS]
1450: |= 1 << ((regno + n) % REGSET_ELT_BITS);
1451: is_needed |= (needed[(regno + n) / REGSET_ELT_BITS]
1452: & 1 << ((regno + n) % REGSET_ELT_BITS));
1453: }
1454: }
1.1 root 1455: /* Additional data to record if this is the final pass. */
1456: if (insn)
1457: {
1458: register rtx y = reg_next_use[regno];
1459: register int blocknum = BLOCK_NUM (insn);
1460:
1.1.1.9 root 1461: /* If this is a hard reg, record this function uses the reg.
1462: `combine.c' will get confused if LOG_LINKs are made
1463: for hard regs. */
1.1 root 1464:
1465: if (regno < FIRST_PSEUDO_REGISTER)
1466: {
1467: register int i;
1468: i = HARD_REGNO_NREGS (regno, GET_MODE (reg));
1.1.1.8 root 1469: if (i == 0)
1470: i = 1;
1.1 root 1471: do
1472: regs_ever_live[regno + --i] = 1;
1473: while (i > 0);
1.1.1.4 root 1474:
1475: if (! ((needed[offset] & bit) || is_needed))
1476: {
1477: /* Note that dead stores have already been deleted if poss.
1478: If we get here, we have found a dead store that cannot
1479: be eliminated (because the insn does something useful).
1480: Indicate this by marking the reg set as dying here. */
1481: REG_NOTES (insn)
1482: = gen_rtx (EXPR_LIST, REG_DEAD,
1483: reg, REG_NOTES (insn));
1484: reg_n_deaths[REGNO (reg)]++;
1485: }
1486: return;
1.1 root 1487: }
1488:
1489: /* Keep track of which basic blocks each reg appears in. */
1490:
1.1.1.4 root 1491: if (reg_basic_block[regno] == REG_BLOCK_UNKNOWN)
1.1 root 1492: reg_basic_block[regno] = blocknum;
1493: else if (reg_basic_block[regno] != blocknum)
1.1.1.4 root 1494: reg_basic_block[regno] = REG_BLOCK_GLOBAL;
1.1 root 1495:
1.1.1.15! root 1496: /* Record first insn to use this reg. */
! 1497: reg_first_use[regno] = insn;
! 1498:
1.1 root 1499: /* Count (weighted) references, stores, etc. */
1500: reg_n_refs[regno] += loop_depth;
1501: reg_n_sets[regno]++;
1.1.1.2 root 1502: /* The next use is no longer "next", since a store intervenes. */
1503: reg_next_use[regno] = 0;
1.1 root 1504: /* The insns where a reg is live are normally counted elsewhere,
1505: but we want the count to include the insn where the reg is set,
1506: and the normal counting mechanism would not count it. */
1507: reg_live_length[regno]++;
1.1.1.2 root 1508: if ((needed[offset] & bit) || is_needed)
1.1 root 1509: {
1510: /* Make a logical link from the next following insn
1511: that uses this register, back to this insn.
1512: The following insns have already been processed. */
1513: if (y && (BLOCK_NUM (y) == blocknum))
1514: LOG_LINKS (y)
1515: = gen_rtx (INSN_LIST, VOIDmode, insn, LOG_LINKS (y));
1516: }
1517: else
1518: {
1519: /* Note that dead stores have already been deleted when possible
1520: If we get here, we have found a dead store that cannot
1521: be eliminated (because the same insn does something useful).
1522: Indicate this by marking the reg being set as dying here. */
1523: REG_NOTES (insn)
1524: = gen_rtx (EXPR_LIST, REG_DEAD,
1525: reg, REG_NOTES (insn));
1.1.1.3 root 1526: reg_n_deaths[REGNO (reg)]++;
1.1 root 1527: }
1528: }
1529: }
1530: }
1531:
1532: /* Scan expression X and store a 1-bit in LIVE for each reg it uses.
1533: This is done assuming the registers needed from X
1534: are those that have 1-bits in NEEDED.
1535:
1.1.1.2 root 1536: On the final pass, FINAL is 1. This means try for autoincrement
1537: and count the uses and deaths of each pseudo-reg.
1538:
1539: INSN is the containing instruction. */
1.1 root 1540:
1541: static void
1.1.1.2 root 1542: mark_used_regs (needed, live, x, final, insn)
1.1 root 1543: regset needed;
1544: regset live;
1545: rtx x;
1546: rtx insn;
1.1.1.2 root 1547: int final;
1.1 root 1548: {
1549: register RTX_CODE code;
1550: register int regno;
1551:
1552: retry:
1553: code = GET_CODE (x);
1554: switch (code)
1555: {
1556: case LABEL_REF:
1557: case SYMBOL_REF:
1558: case CONST_INT:
1559: case CONST:
1.1.1.4 root 1560: case CONST_DOUBLE:
1.1 root 1561: case CC0:
1562: case PC:
1563: case CLOBBER:
1.1.1.4 root 1564: case ADDR_VEC:
1565: case ADDR_DIFF_VEC:
1566: case ASM_INPUT:
1.1 root 1567: return;
1568:
1569: #if defined (HAVE_POST_INCREMENT) || defined (HAVE_POST_DECREMENT)
1570: case MEM:
1571: /* Here we detect use of an index register which might
1572: be good for postincrement or postdecrement. */
1.1.1.2 root 1573: if (final)
1.1 root 1574: {
1575: rtx addr = XEXP (x, 0);
1576: register int size = GET_MODE_SIZE (GET_MODE (x));
1577:
1578: if (GET_CODE (addr) == REG)
1579: {
1580: register rtx y;
1581: regno = REGNO (addr);
1582: /* Is the next use an increment that might make auto-increment? */
1583: y = reg_next_use[regno];
1584: if (y && GET_CODE (PATTERN (y)) == SET
1585: && BLOCK_NUM (y) == BLOCK_NUM (insn)
1586: /* Can't add side effects to jumps; if reg is spilled and
1587: reloaded, there's no way to store back the altered value. */
1588: && GET_CODE (insn) != JUMP_INSN
1589: && (y = SET_SRC (PATTERN (y)),
1590: (0
1591: #ifdef HAVE_POST_INCREMENT
1592: || GET_CODE (y) == PLUS
1593: #endif
1594: #ifdef HAVE_POST_DECREMENT
1595: || GET_CODE (y) == MINUS
1596: #endif
1597: )
1598: && XEXP (y, 0) == addr
1599: && GET_CODE (XEXP (y, 1)) == CONST_INT
1.1.1.2 root 1600: && INTVAL (XEXP (y, 1)) == size)
1601: && dead_or_set_p (reg_next_use[regno], addr))
1.1 root 1602: {
1.1.1.2 root 1603: rtx use = find_use_as_address (PATTERN (insn), addr, 0);
1.1 root 1604:
1605: /* Make sure this register appears only once in this insn. */
1606: if (use != 0 && use != (rtx) 1)
1607: {
1608: /* We have found a suitable auto-increment:
1609: do POST_INC around the register here,
1610: and patch out the increment instruction that follows. */
1611: XEXP (x, 0)
1612: = gen_rtx (GET_CODE (y) == PLUS ? POST_INC : POST_DEC,
1613: Pmode, addr);
1614: /* Record that this insn has an implicit side effect. */
1615: REG_NOTES (insn)
1616: = gen_rtx (EXPR_LIST, REG_INC, addr, REG_NOTES (insn));
1617:
1.1.1.2 root 1618: /* Modify the old increment-insn to simply copy
1619: the already-incremented value of our register. */
1.1 root 1620: y = reg_next_use[regno];
1.1.1.2 root 1621: SET_SRC (PATTERN (y)) = addr;
1622:
1623: /* If that makes it a no-op (copying the register
1624: into itself) then change it to a simpler no-op
1625: so it won't appear to be a "use" and a "set"
1626: of this register. */
1627: if (SET_DEST (PATTERN (y)) == addr)
1628: PATTERN (y) = gen_rtx (USE, VOIDmode, const0_rtx);
1629:
1630: /* Count an extra reference to the reg for the increment.
1631: When a reg is incremented.
1.1 root 1632: spilling it is worse, so we want to make that
1633: less likely. */
1634: reg_n_refs[regno] += loop_depth;
1.1.1.2 root 1635: /* Count the increment as a setting of the register,
1636: even though it isn't a SET in rtl. */
1637: reg_n_sets[regno]++;
1.1 root 1638: }
1639: }
1640: }
1641: }
1642: break;
1643: #endif /* HAVE_POST_INCREMENT or HAVE_POST_DECREMENT */
1644:
1645: case REG:
1646: /* See a register other than being set
1647: => mark it as needed. */
1648:
1649: regno = REGNO (x);
1.1.1.14 root 1650: if (regno != FRAME_POINTER_REGNUM)
1651: /* && regno != ARG_POINTER_REGNUM) -- and without this. */
1.1.1.2 root 1652: /* && regno != STACK_POINTER_REGNUM) -- let's try without this. */
1.1 root 1653: {
1654: register int offset = regno / REGSET_ELT_BITS;
1655: register int bit = 1 << (regno % REGSET_ELT_BITS);
1.1.1.2 root 1656: int is_needed = 0;
1657:
1.1 root 1658: live[offset] |= bit;
1.1.1.2 root 1659: /* A hard reg in a wide mode may really be multiple registers.
1660: If so, mark all of them just like the first. */
1661: if (regno < FIRST_PSEUDO_REGISTER)
1662: {
1.1.1.4 root 1663: int n;
1664:
1.1.1.14 root 1665: /* For stack ptr or arg pointer,
1666: nothing below can be necessary, so waste no more time. */
1667: if (regno == STACK_POINTER_REGNUM
1668: || regno == ARG_POINTER_REGNUM)
1.1.1.4 root 1669: return;
1.1.1.12 root 1670: /* No death notes for global register variables;
1671: their values are live after this function exits. */
1672: if (global_regs[regno])
1673: return;
1.1.1.4 root 1674:
1675: n = HARD_REGNO_NREGS (regno, GET_MODE (x));
1.1.1.2 root 1676: while (--n > 0)
1677: {
1678: live[(regno + n) / REGSET_ELT_BITS]
1679: |= 1 << ((regno + n) % REGSET_ELT_BITS);
1680: is_needed |= (needed[(regno + n) / REGSET_ELT_BITS]
1681: & 1 << ((regno + n) % REGSET_ELT_BITS));
1682: }
1683: }
1684: if (final)
1.1 root 1685: {
1686: if (regno < FIRST_PSEUDO_REGISTER)
1687: {
1.1.1.4 root 1688: /* If a hard reg is being used,
1689: record that this function does use it. */
1690:
1.1 root 1691: register int i;
1692: i = HARD_REGNO_NREGS (regno, GET_MODE (x));
1.1.1.8 root 1693: if (i == 0)
1694: i = 1;
1.1 root 1695: do
1696: regs_ever_live[regno + --i] = 1;
1697: while (i > 0);
1698: }
1.1.1.4 root 1699: else
1700: {
1701: /* Keep track of which basic block each reg appears in. */
1.1 root 1702:
1.1.1.4 root 1703: register int blocknum = BLOCK_NUM (insn);
1.1 root 1704:
1.1.1.4 root 1705: if (reg_basic_block[regno] == REG_BLOCK_UNKNOWN)
1706: reg_basic_block[regno] = blocknum;
1707: else if (reg_basic_block[regno] != blocknum)
1708: reg_basic_block[regno] = REG_BLOCK_GLOBAL;
1.1 root 1709:
1.1.1.15! root 1710: /* Record the earliest insn that uses this reg,
! 1711: provided the reg is used only in one basic block.
! 1712: Do this by recording each insn, and the one that
! 1713: sticks is the last one scanned (the earliest insn). */
! 1714:
! 1715: reg_first_use[regno] = insn;
! 1716:
1.1.1.4 root 1717: /* Record where each reg is used, so when the reg
1718: is set we know the next insn that uses it. */
1.1 root 1719:
1.1.1.4 root 1720: reg_next_use[regno] = insn;
1.1 root 1721:
1.1.1.4 root 1722: /* Count (weighted) number of uses of each reg. */
1.1 root 1723:
1.1.1.4 root 1724: reg_n_refs[regno] += loop_depth;
1725: }
1.1.1.12 root 1726:
1.1 root 1727: /* Record and count the insns in which a reg dies.
1728: If it is used in this insn and was dead below the insn
1729: then it dies in this insn. */
1730:
1.1.1.2 root 1731: if (!(needed[offset] & bit) && !is_needed
1732: && ! find_regno_note (insn, REG_DEAD, regno))
1.1 root 1733: {
1734: REG_NOTES (insn)
1735: = gen_rtx (EXPR_LIST, REG_DEAD, x, REG_NOTES (insn));
1736: reg_n_deaths[regno]++;
1737: }
1738: }
1739: }
1740: return;
1741:
1742: case SET:
1743: {
1.1.1.2 root 1744: register rtx testreg = SET_DEST (x);
1745: int mark_dest = 0;
1.1 root 1746:
1.1.1.2 root 1747: /* Storing in STRICT_LOW_PART is like storing in a reg
1748: in that this SET might be dead, so ignore it in TESTREG.
1749: but in some other ways it is like using the reg. */
1750: /* Storing in a SUBREG or a bit field is like storing the entire
1751: register in that if the register's value is not used
1752: then this SET is not needed. */
1753: while (GET_CODE (testreg) == STRICT_LOW_PART
1754: || GET_CODE (testreg) == ZERO_EXTRACT
1755: || GET_CODE (testreg) == SIGN_EXTRACT
1756: || GET_CODE (testreg) == SUBREG)
1757: {
1758: /* Modifying a single register in an alternate mode
1759: does not use any of the old value. But these other
1760: ways of storing in a register do use the old value. */
1761: if (GET_CODE (testreg) == SUBREG
1762: && !(REG_SIZE (SUBREG_REG (testreg)) > REG_SIZE (testreg)))
1763: ;
1764: else
1765: mark_dest = 1;
1766:
1767: testreg = XEXP (testreg, 0);
1768: }
1.1 root 1769:
1770: /* If this is a store into a register,
1771: recursively scan the only value being stored,
1772: and only if the register's value is live after this insn.
1773: If the value being computed here would never be used
1774: then the values it uses don't need to be computed either. */
1775:
1.1.1.2 root 1776: if (GET_CODE (testreg) == REG
1777: && (regno = REGNO (testreg), regno != FRAME_POINTER_REGNUM)
1.1.1.11 root 1778: && regno != ARG_POINTER_REGNUM
1779: && ! (regno < FIRST_PSEUDO_REGISTER && global_regs[regno]))
1.1.1.7 root 1780: #if 0 /* This was added in 1.25, but screws up death notes for hard regs.
1781: It probably isn't really needed anyway. */
1.1.1.6 root 1782: && (regno >= FIRST_PSEUDO_REGISTER
1783: || INSN_VOLATILE (insn)))
1.1.1.7 root 1784: #endif
1.1 root 1785: {
1786: register int offset = regno / REGSET_ELT_BITS;
1787: register int bit = 1 << (regno % REGSET_ELT_BITS);
1.1.1.2 root 1788: if ((needed[offset] & bit)
1789: /* If insn refers to volatile, we mustn't delete it,
1790: so its inputs are all needed. */
1791: || INSN_VOLATILE (insn))
1792: {
1793: mark_used_regs (needed, live, SET_SRC (x), final, insn);
1794: if (mark_dest)
1795: mark_used_regs (needed, live, SET_DEST (x), final, insn);
1796: }
1.1 root 1797: return;
1798: }
1799: }
1800: break;
1801: }
1802:
1803: /* Recursively scan the operands of this expression. */
1804:
1805: {
1806: register char *fmt = GET_RTX_FORMAT (code);
1807: register int i;
1808:
1809: for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1810: {
1811: if (fmt[i] == 'e')
1812: {
1813: /* Tail recursive case: save a function call level. */
1814: if (i == 0)
1815: {
1816: x = XEXP (x, 0);
1817: goto retry;
1818: }
1.1.1.2 root 1819: mark_used_regs (needed, live, XEXP (x, i), final, insn);
1.1 root 1820: }
1.1.1.4 root 1821: else if (fmt[i] == 'E')
1.1 root 1822: {
1823: register int j;
1824: for (j = 0; j < XVECLEN (x, i); j++)
1.1.1.2 root 1825: mark_used_regs (needed, live, XVECEXP (x, i, j), final, insn);
1.1 root 1826: }
1827: }
1828: }
1829: }
1830:
1.1.1.2 root 1831: #ifdef AUTO_INC_DEC
1.1 root 1832:
1833: static int
1834: try_pre_increment_1 (insn)
1835: rtx insn;
1836: {
1837: /* Find the next use of this reg. If in same basic block,
1838: make it do pre-increment or pre-decrement if appropriate. */
1839: rtx x = PATTERN (insn);
1840: int amount = ((GET_CODE (SET_SRC (x)) == PLUS ? 1 : -1)
1841: * INTVAL (XEXP (SET_SRC (x), 1)));
1842: int regno = REGNO (SET_DEST (x));
1843: rtx y = reg_next_use[regno];
1844: if (y != 0
1845: && BLOCK_NUM (y) == BLOCK_NUM (insn)
1846: && try_pre_increment (y, SET_DEST (PATTERN (insn)),
1847: amount))
1848: {
1849: /* We have found a suitable auto-increment
1850: and already changed insn Y to do it.
1851: So flush this increment-instruction. */
1852: PUT_CODE (insn, NOTE);
1853: NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
1854: NOTE_SOURCE_FILE (insn) = 0;
1855: /* Count a reference to this reg for the increment
1856: insn we are deleting. When a reg is incremented.
1857: spilling it is worse, so we want to make that
1858: less likely. */
1859: reg_n_refs[regno] += loop_depth;
1.1.1.2 root 1860: reg_n_sets[regno]++;
1.1 root 1861: return 1;
1862: }
1863: return 0;
1864: }
1865:
1866: /* Try to change INSN so that it does pre-increment or pre-decrement
1867: addressing on register REG in order to add AMOUNT to REG.
1868: AMOUNT is negative for pre-decrement.
1869: Returns 1 if the change could be made.
1870: This checks all about the validity of the result of modifying INSN. */
1871:
1872: static int
1873: try_pre_increment (insn, reg, amount)
1874: rtx insn, reg;
1875: int amount;
1876: {
1877: register rtx use;
1878:
1.1.1.2 root 1879: /* Nonzero if we can try to make a pre-increment or pre-decrement.
1880: For example, addl $4,r1; movl (r1),... can become movl +(r1),... */
1881: int pre_ok = 0;
1882: /* Nonzero if we can try to make a post-increment or post-decrement.
1883: For example, addl $4,r1; movl -4(r1),... can become movl (r1)+,...
1884: It is possible for both PRE_OK and POST_OK to be nonzero if the machine
1885: supports both pre-inc and post-inc, or both pre-dec and post-dec. */
1886: int post_ok = 0;
1887:
1888: /* Nonzero if the opportunity actually requires post-inc or post-dec. */
1889: int do_post = 0;
1890:
1891: /* From the sign of increment, see which possibilities are conceivable
1892: on this target machine. */
1893: #ifdef HAVE_PRE_INCREMENT
1.1 root 1894: if (amount > 0)
1.1.1.2 root 1895: pre_ok = 1;
1.1 root 1896: #endif
1.1.1.2 root 1897: #ifdef HAVE_POST_INCREMENT
1898: if (amount > 0)
1899: post_ok = 1;
1.1 root 1900: #endif
1901:
1.1.1.2 root 1902: #ifdef HAVE_PRE_DECREMENT
1.1 root 1903: if (amount < 0)
1.1.1.2 root 1904: pre_ok = 1;
1905: #endif
1906: #ifdef HAVE_POST_DECREMENT
1907: if (amount < 0)
1908: post_ok = 1;
1.1 root 1909: #endif
1910:
1.1.1.2 root 1911: if (! (pre_ok || post_ok))
1912: return 0;
1913:
1.1 root 1914: /* It is not safe to add a side effect to a jump insn
1915: because if the incremented register is spilled and must be reloaded
1916: there would be no way to store the incremented value back in memory. */
1917:
1918: if (GET_CODE (insn) == JUMP_INSN)
1919: return 0;
1920:
1.1.1.2 root 1921: use = 0;
1922: if (pre_ok)
1923: use = find_use_as_address (PATTERN (insn), reg, 0);
1924: if (post_ok && (use == 0 || use == (rtx) 1))
1925: {
1926: use = find_use_as_address (PATTERN (insn), reg, -amount);
1927: do_post = 1;
1928: }
1.1 root 1929:
1930: if (use == 0 || use == (rtx) 1)
1931: return 0;
1932:
1933: if (GET_MODE_SIZE (GET_MODE (use)) != (amount > 0 ? amount : - amount))
1934: return 0;
1935:
1.1.1.2 root 1936: XEXP (use, 0) = gen_rtx (amount > 0
1937: ? (do_post ? POST_INC : PRE_INC)
1938: : (do_post ? POST_DEC : PRE_DEC),
1.1 root 1939: Pmode, reg);
1940:
1941: /* Record that this insn now has an implicit side effect on X. */
1942: REG_NOTES (insn) = gen_rtx (EXPR_LIST, REG_INC, reg, REG_NOTES (insn));
1943: return 1;
1944: }
1945:
1.1.1.2 root 1946: #endif /* AUTO_INC_DEC */
1947:
1.1 root 1948: /* Find the place in the rtx X where REG is used as a memory address.
1949: Return the MEM rtx that so uses it.
1.1.1.2 root 1950: If PLUSCONST is nonzero, search instead for a memory address equivalent to
1951: (plus REG (const_int PLUSCONST)).
1952:
1953: If such an address does not appear, return 0.
1954: If REG appears more than once, or is used other than in such an address,
1.1 root 1955: return (rtx)1. */
1956:
1957: static rtx
1.1.1.2 root 1958: find_use_as_address (x, reg, plusconst)
1.1 root 1959: register rtx x;
1960: rtx reg;
1.1.1.2 root 1961: int plusconst;
1.1 root 1962: {
1963: enum rtx_code code = GET_CODE (x);
1964: char *fmt = GET_RTX_FORMAT (code);
1965: register int i;
1966: register rtx value = 0;
1967: register rtx tem;
1968:
1.1.1.2 root 1969: if (code == MEM && XEXP (x, 0) == reg && plusconst == 0)
1.1 root 1970: return x;
1971:
1.1.1.2 root 1972: if (code == MEM && GET_CODE (XEXP (x, 0)) == PLUS
1973: && XEXP (XEXP (x, 0), 0) == reg
1974: && GET_CODE (XEXP (XEXP (x, 0), 1)) == CONST_INT
1975: && INTVAL (XEXP (XEXP (x, 0), 1)) == plusconst)
1976: return x;
1977:
1978: if (code == SIGN_EXTRACT || code == ZERO_EXTRACT)
1979: {
1980: /* If REG occurs inside a MEM used in a bit-field reference,
1981: that is unacceptable. */
1982: if (find_use_as_address (XEXP (x, 0), reg, 0) != 0)
1983: return (rtx) 1;
1984: }
1985:
1.1 root 1986: if (x == reg)
1987: return (rtx) 1;
1988:
1989: for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1990: {
1991: if (fmt[i] == 'e')
1992: {
1.1.1.2 root 1993: tem = find_use_as_address (XEXP (x, i), reg, plusconst);
1.1 root 1994: if (value == 0)
1995: value = tem;
1996: else if (tem != 0)
1997: return (rtx) 1;
1998: }
1999: if (fmt[i] == 'E')
2000: {
2001: register int j;
2002: for (j = XVECLEN (x, i) - 1; j >= 0; j--)
2003: {
1.1.1.2 root 2004: tem = find_use_as_address (XVECEXP (x, i, j), reg, plusconst);
1.1 root 2005: if (value == 0)
2006: value = tem;
2007: else if (tem != 0)
2008: return (rtx) 1;
2009: }
2010: }
2011: }
2012:
2013: return value;
2014: }
2015:
2016: /* Write information about registers and basic blocks into FILE.
2017: This is part of making a debugging dump. */
2018:
1.1.1.2 root 2019: void
1.1 root 2020: dump_flow_info (file)
2021: FILE *file;
2022: {
2023: register int i;
2024: static char *reg_class_names[] = REG_CLASS_NAMES;
2025:
2026: fprintf (file, "%d registers.\n", max_regno);
2027:
2028: for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
2029: if (reg_n_refs[i])
2030: {
2031: enum reg_class class;
2032: fprintf (file, "\nRegister %d used %d times across %d insns",
2033: i, reg_n_refs[i], reg_live_length[i]);
2034: if (reg_basic_block[i] >= 0)
2035: fprintf (file, " in block %d", reg_basic_block[i]);
2036: if (reg_n_deaths[i] != 1)
2037: fprintf (file, "; dies in %d places", reg_n_deaths[i]);
1.1.1.12 root 2038: if (reg_n_calls_crossed[i] == 1)
2039: fprintf (file, "; crosses 1 call", reg_n_calls_crossed[i]);
2040: else if (reg_n_calls_crossed[i])
2041: fprintf (file, "; crosses %d calls", reg_n_calls_crossed[i]);
1.1 root 2042: if (PSEUDO_REGNO_BYTES (i) != UNITS_PER_WORD)
2043: fprintf (file, "; %d bytes", PSEUDO_REGNO_BYTES (i));
2044: class = reg_preferred_class (i);
2045: if (class != GENERAL_REGS)
1.1.1.2 root 2046: {
2047: if (reg_preferred_or_nothing (i))
2048: fprintf (file, "; %s or none", reg_class_names[(int) class]);
2049: else
2050: fprintf (file, "; pref %s", reg_class_names[(int) class]);
2051: }
1.1 root 2052: if (REGNO_POINTER_FLAG (i))
2053: fprintf (file, "; pointer");
2054: fprintf (file, ".\n");
2055: }
2056: fprintf (file, "\n%d basic blocks.\n", n_basic_blocks);
2057: for (i = 0; i < n_basic_blocks; i++)
2058: {
2059: register rtx head, jump;
2060: register int regno;
2061: fprintf (file, "\nBasic block %d: first insn %d, last %d.\n",
2062: i,
2063: INSN_UID (basic_block_head[i]),
2064: INSN_UID (basic_block_end[i]));
2065: /* The control flow graph's storage is freed
2066: now when flow_analysis returns.
2067: Don't try to print it if it is gone. */
2068: if (basic_block_drops_in)
2069: {
2070: fprintf (file, "Reached from blocks: ");
2071: head = basic_block_head[i];
2072: if (GET_CODE (head) == CODE_LABEL)
2073: for (jump = LABEL_REFS (head);
2074: jump != head;
2075: jump = LABEL_NEXTREF (jump))
2076: {
1.1.1.14 root 2077: register int from_block = BLOCK_NUM (CONTAINING_INSN (jump));
1.1 root 2078: fprintf (file, " %d", from_block);
2079: }
2080: if (basic_block_drops_in[i])
2081: fprintf (file, " previous");
2082: }
2083: fprintf (file, "\nRegisters live at start:");
2084: for (regno = 0; regno < max_regno; regno++)
2085: {
2086: register int offset = regno / REGSET_ELT_BITS;
2087: register int bit = 1 << (regno % REGSET_ELT_BITS);
2088: if (basic_block_live_at_start[i][offset] & bit)
2089: fprintf (file, " %d", regno);
2090: }
2091: fprintf (file, "\n");
2092: }
2093: fprintf (file, "\n");
2094: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.