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