![[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 2.x] / gcc|
Return to flow.c CVS log | Up to [GCC 2.x] / gcc |
1.1 root 1: /* Data flow analysis for GNU compiler. 1.1.1.7 ! root 2: Copyright (C) 1987, 1988, 1992, 1993, 1994 Free Software Foundation, Inc. 1.1 root 3: 4: This file is part of GNU CC. 5: 6: GNU CC is free software; you can redistribute it and/or modify 7: it under the terms of the GNU General Public License as published by 8: the Free Software Foundation; either version 2, or (at your option) 9: any later version. 10: 11: GNU CC is distributed in the hope that it will be useful, 12: but WITHOUT ANY WARRANTY; without even the implied warranty of 13: MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14: GNU General Public License for more details. 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. */ 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: Two types of elements can be added to an insn's REG_NOTES. 61: A REG_DEAD note is added to an insn's REG_NOTES for any register 62: that meets both of two conditions: The value in the register is not 63: needed in subsequent insns and the insn does not replace the value in 64: the register (in the case of multi-word hard registers, the value in 65: each register must be replaced by the insn to avoid a REG_DEAD note). 66: 67: In the vast majority of cases, an object in a REG_DEAD note will be 68: used somewhere in the insn. The (rare) exception to this is if an 69: insn uses a multi-word hard register and only some of the registers are 70: needed in subsequent insns. In that case, REG_DEAD notes will be 71: provided for those hard registers that are not subsequently needed. 72: Partial REG_DEAD notes of this type do not occur when an insn sets 73: only some of the hard registers used in such a multi-word operand; 74: omitting REG_DEAD notes for objects stored in an insn is optional and 75: the desire to do so does not justify the complexity of the partial 76: REG_DEAD notes. 77: 78: REG_UNUSED notes are added for each register that is set by the insn 79: but is unused subsequently (if every register set by the insn is unused 80: and the insn does not reference memory or have some other side-effect, 81: the insn is deleted instead). If only part of a multi-word hard 82: register is used in a subsequent insn, REG_UNUSED notes are made for 83: the parts that will not be used. 84: 85: To determine which registers are live after any insn, one can 86: start from the beginning of the basic block and scan insns, noting 87: which registers are set by each insn and which die there. 88: 89: ** Other actions of life_analysis ** 90: 91: life_analysis sets up the LOG_LINKS fields of insns because the 92: information needed to do so is readily available. 93: 94: life_analysis deletes insns whose only effect is to store a value 95: that is never used. 96: 97: life_analysis notices cases where a reference to a register as 98: a memory address can be combined with a preceding or following 99: incrementation or decrementation of the register. The separate 100: instruction to increment or decrement is deleted and the address 101: is changed to a POST_INC or similar rtx. 102: 103: Each time an incrementing or decrementing address is created, 104: a REG_INC element is added to the insn's REG_NOTES list. 105: 106: life_analysis fills in certain vectors containing information about 107: register usage: reg_n_refs, reg_n_deaths, reg_n_sets, reg_live_length, 108: reg_n_calls_crosses and reg_basic_block. */ 109: 110: #include <stdio.h> 111: #include "config.h" 112: #include "rtl.h" 113: #include "basic-block.h" 114: #include "insn-config.h" 115: #include "regs.h" 116: #include "hard-reg-set.h" 117: #include "flags.h" 118: #include "output.h" 119: 120: #include "obstack.h" 121: #define obstack_chunk_alloc xmalloc 122: #define obstack_chunk_free free 123: 124: /* List of labels that must never be deleted. */ 125: extern rtx forced_labels; 126: 127: /* Get the basic block number of an insn. 128: This info should not be expected to remain available 129: after the end of life_analysis. */ 130: 131: /* This is the limit of the allocated space in the following two arrays. */ 132: 133: static int max_uid_for_flow; 134: 135: #define BLOCK_NUM(INSN) uid_block_number[INSN_UID (INSN)] 136: 137: /* This is where the BLOCK_NUM values are really stored. 138: This is set up by find_basic_blocks and used there and in life_analysis, 139: and then freed. */ 140: 1.1.1.5 root 141: static int *uid_block_number; 1.1 root 142: 143: /* INSN_VOLATILE (insn) is 1 if the insn refers to anything volatile. */ 144: 145: #define INSN_VOLATILE(INSN) uid_volatile[INSN_UID (INSN)] 146: static char *uid_volatile; 147: 148: /* Number of basic blocks in the current function. */ 149: 150: int n_basic_blocks; 151: 152: /* Maximum register number used in this function, plus one. */ 153: 154: int max_regno; 155: 156: /* Maximum number of SCRATCH rtx's used in any basic block of this function. */ 157: 158: int max_scratch; 159: 160: /* Number of SCRATCH rtx's in the current block. */ 161: 162: static int num_scratch; 163: 164: /* Indexed by n, gives number of basic block that (REG n) is used in. 165: If the value is REG_BLOCK_GLOBAL (-2), 166: it means (REG n) is used in more than one basic block. 167: REG_BLOCK_UNKNOWN (-1) means it hasn't been seen yet so we don't know. 168: This information remains valid for the rest of the compilation 169: of the current function; it is used to control register allocation. */ 170: 1.1.1.5 root 171: int *reg_basic_block; 1.1 root 172: 173: /* Indexed by n, gives number of times (REG n) is used or set, each 174: weighted by its loop-depth. 175: This information remains valid for the rest of the compilation 176: of the current function; it is used to control register allocation. */ 177: 178: int *reg_n_refs; 179: 1.1.1.7 ! root 180: /* Indexed by N; says whether a psuedo register N was ever used ! 181: within a SUBREG that changes the size of the reg. Some machines prohibit ! 182: such objects to be in certain (usually floating-point) registers. */ ! 183: ! 184: char *reg_changes_size; ! 185: 1.1 root 186: /* Indexed by N, gives number of places register N dies. 187: This information remains valid for the rest of the compilation 188: of the current function; it is used to control register allocation. */ 189: 190: short *reg_n_deaths; 191: 192: /* Indexed by N, gives 1 if that reg is live across any CALL_INSNs. 193: This information remains valid for the rest of the compilation 194: of the current function; it is used to control register allocation. */ 195: 196: int *reg_n_calls_crossed; 197: 198: /* Total number of instructions at which (REG n) is live. 199: The larger this is, the less priority (REG n) gets for 200: allocation in a real register. 201: This information remains valid for the rest of the compilation 202: of the current function; it is used to control register allocation. 203: 204: local-alloc.c may alter this number to change the priority. 205: 206: Negative values are special. 207: -1 is used to mark a pseudo reg which has a constant or memory equivalent 208: and is used infrequently enough that it should not get a hard register. 209: -2 is used to mark a pseudo reg for a parameter, when a frame pointer 1.1.1.4 root 210: is not required. global.c makes an allocno for this but does 1.1 root 211: not try to assign a hard register to it. */ 212: 213: int *reg_live_length; 214: 215: /* Element N is the next insn that uses (hard or pseudo) register number N 216: within the current basic block; or zero, if there is no such insn. 217: This is valid only during the final backward scan in propagate_block. */ 218: 219: static rtx *reg_next_use; 220: 221: /* Size of a regset for the current function, 222: in (1) bytes and (2) elements. */ 223: 224: int regset_bytes; 225: int regset_size; 226: 227: /* Element N is first insn in basic block N. 228: This info lasts until we finish compiling the function. */ 229: 230: rtx *basic_block_head; 231: 232: /* Element N is last insn in basic block N. 233: This info lasts until we finish compiling the function. */ 234: 235: rtx *basic_block_end; 236: 237: /* Element N is a regset describing the registers live 238: at the start of basic block N. 239: This info lasts until we finish compiling the function. */ 240: 241: regset *basic_block_live_at_start; 242: 243: /* Regset of regs live when calls to `setjmp'-like functions happen. */ 244: 245: regset regs_live_at_setjmp; 246: 247: /* List made of EXPR_LIST rtx's which gives pairs of pseudo registers 248: that have to go in the same hard reg. 249: The first two regs in the list are a pair, and the next two 250: are another pair, etc. */ 251: rtx regs_may_share; 252: 253: /* Element N is nonzero if control can drop into basic block N 254: from the preceding basic block. Freed after life_analysis. */ 255: 256: static char *basic_block_drops_in; 257: 258: /* Element N is depth within loops of the last insn in basic block number N. 259: Freed after life_analysis. */ 260: 261: static short *basic_block_loop_depth; 262: 263: /* Element N nonzero if basic block N can actually be reached. 264: Vector exists only during find_basic_blocks. */ 265: 266: static char *block_live_static; 267: 268: /* Depth within loops of basic block being scanned for lifetime analysis, 269: plus one. This is the weight attached to references to registers. */ 270: 271: static int loop_depth; 272: 273: /* During propagate_block, this is non-zero if the value of CC0 is live. */ 274: 275: static int cc0_live; 276: 277: /* During propagate_block, this contains the last MEM stored into. It 278: is used to eliminate consecutive stores to the same location. */ 279: 280: static rtx last_mem_set; 281: 282: /* Set of registers that may be eliminable. These are handled specially 283: in updating regs_ever_live. */ 284: 285: static HARD_REG_SET elim_reg_set; 286: 287: /* Forward declarations */ 1.1.1.7 ! root 288: static void find_basic_blocks PROTO((rtx, rtx)); ! 289: static int uses_reg_or_mem PROTO((rtx)); ! 290: static void mark_label_ref PROTO((rtx, rtx, int)); ! 291: static void life_analysis PROTO((rtx, int)); ! 292: void allocate_for_life_analysis PROTO((void)); ! 293: static void init_regset_vector PROTO((regset *, regset, int, int)); ! 294: static void propagate_block PROTO((regset, rtx, rtx, int, ! 295: regset, int)); ! 296: static int insn_dead_p PROTO((rtx, regset, int)); ! 297: static int libcall_dead_p PROTO((rtx, regset, rtx, rtx)); ! 298: static void mark_set_regs PROTO((regset, regset, rtx, ! 299: rtx, regset)); ! 300: static void mark_set_1 PROTO((regset, regset, rtx, ! 301: rtx, regset)); ! 302: static void find_auto_inc PROTO((regset, rtx, rtx)); ! 303: static void mark_used_regs PROTO((regset, regset, rtx, int, rtx)); ! 304: static int try_pre_increment_1 PROTO((rtx)); ! 305: static int try_pre_increment PROTO((rtx, rtx, HOST_WIDE_INT)); ! 306: static rtx find_use_as_address PROTO((rtx, rtx, HOST_WIDE_INT)); ! 307: void dump_flow_info PROTO((FILE *)); 1.1 root 308: 309: /* Find basic blocks of the current function and perform data flow analysis. 310: F is the first insn of the function and NREGS the number of register numbers 311: in use. */ 312: 313: void 314: flow_analysis (f, nregs, file) 315: rtx f; 316: int nregs; 317: FILE *file; 318: { 319: register rtx insn; 320: register int i; 321: rtx nonlocal_label_list = nonlocal_label_rtx_list (); 322: 323: #ifdef ELIMINABLE_REGS 324: static struct {int from, to; } eliminables[] = ELIMINABLE_REGS; 325: #endif 326: 327: /* Record which registers will be eliminated. We use this in 328: mark_used_regs. */ 329: 330: CLEAR_HARD_REG_SET (elim_reg_set); 331: 332: #ifdef ELIMINABLE_REGS 333: for (i = 0; i < sizeof eliminables / sizeof eliminables[0]; i++) 334: SET_HARD_REG_BIT (elim_reg_set, eliminables[i].from); 335: #else 336: SET_HARD_REG_BIT (elim_reg_set, FRAME_POINTER_REGNUM); 337: #endif 338: 339: /* Count the basic blocks. Also find maximum insn uid value used. */ 340: 341: { 342: register RTX_CODE prev_code = JUMP_INSN; 343: register RTX_CODE code; 344: 345: max_uid_for_flow = 0; 346: 347: for (insn = f, i = 0; insn; insn = NEXT_INSN (insn)) 348: { 349: code = GET_CODE (insn); 350: if (INSN_UID (insn) > max_uid_for_flow) 351: max_uid_for_flow = INSN_UID (insn); 352: if (code == CODE_LABEL 353: || (GET_RTX_CLASS (code) == 'i' 354: && (prev_code == JUMP_INSN 355: || (prev_code == CALL_INSN 1.1.1.7 ! root 356: && nonlocal_label_list != 0) 1.1 root 357: || prev_code == BARRIER))) 358: i++; 1.1.1.7 ! root 359: if (code != NOTE) 1.1 root 360: prev_code = code; 361: } 362: } 363: 364: #ifdef AUTO_INC_DEC 365: /* Leave space for insns we make in some cases for auto-inc. These cases 366: are rare, so we don't need too much space. */ 367: max_uid_for_flow += max_uid_for_flow / 10; 368: #endif 369: 370: /* Allocate some tables that last till end of compiling this function 371: and some needed only in find_basic_blocks and life_analysis. */ 372: 373: n_basic_blocks = i; 374: basic_block_head = (rtx *) oballoc (n_basic_blocks * sizeof (rtx)); 375: basic_block_end = (rtx *) oballoc (n_basic_blocks * sizeof (rtx)); 376: basic_block_drops_in = (char *) alloca (n_basic_blocks); 377: basic_block_loop_depth = (short *) alloca (n_basic_blocks * sizeof (short)); 378: uid_block_number 1.1.1.5 root 379: = (int *) alloca ((max_uid_for_flow + 1) * sizeof (int)); 1.1 root 380: uid_volatile = (char *) alloca (max_uid_for_flow + 1); 381: bzero (uid_volatile, max_uid_for_flow + 1); 382: 383: find_basic_blocks (f, nonlocal_label_list); 384: life_analysis (f, nregs); 385: if (file) 386: dump_flow_info (file); 387: 388: basic_block_drops_in = 0; 389: uid_block_number = 0; 390: basic_block_loop_depth = 0; 391: } 392: 393: /* Find all basic blocks of the function whose first insn is F. 394: Store the correct data in the tables that describe the basic blocks, 395: set up the chains of references for each CODE_LABEL, and 396: delete any entire basic blocks that cannot be reached. 397: 398: NONLOCAL_LABEL_LIST is the same local variable from flow_analysis. */ 399: 400: static void 401: find_basic_blocks (f, nonlocal_label_list) 402: rtx f, nonlocal_label_list; 403: { 404: register rtx insn; 405: register int i; 406: register char *block_live = (char *) alloca (n_basic_blocks); 407: register char *block_marked = (char *) alloca (n_basic_blocks); 408: /* List of label_refs to all labels whose addresses are taken 409: and used as data. */ 410: rtx label_value_list = 0; 1.1.1.7 ! root 411: rtx x, note; ! 412: enum rtx_code prev_code, code; ! 413: int depth; 1.1 root 414: 415: block_live_static = block_live; 416: bzero (block_live, n_basic_blocks); 417: bzero (block_marked, n_basic_blocks); 418: 419: /* Initialize with just block 0 reachable and no blocks marked. */ 420: if (n_basic_blocks > 0) 421: block_live[0] = 1; 422: 1.1.1.7 ! root 423: /* Initialize the ref chain of each label to 0. Record where all the ! 424: blocks start and end and their depth in loops. For each insn, record ! 425: the block it is in. Also mark as reachable any blocks headed by labels ! 426: that must not be deleted. */ 1.1 root 427: 1.1.1.7 ! root 428: for (insn = f, i = -1, prev_code = JUMP_INSN, depth = 1; ! 429: insn; insn = NEXT_INSN (insn)) ! 430: { ! 431: code = GET_CODE (insn); ! 432: if (code == NOTE) ! 433: { ! 434: if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG) ! 435: depth++; ! 436: else if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END) ! 437: depth--; ! 438: } 1.1 root 439: 1.1.1.7 ! root 440: /* A basic block starts at label, or after something that can jump. */ ! 441: else if (code == CODE_LABEL ! 442: || (GET_RTX_CLASS (code) == 'i' ! 443: && (prev_code == JUMP_INSN ! 444: || (prev_code == CALL_INSN ! 445: && nonlocal_label_list != 0) ! 446: || prev_code == BARRIER))) ! 447: { ! 448: basic_block_head[++i] = insn; ! 449: basic_block_end[i] = insn; ! 450: basic_block_loop_depth[i] = depth; ! 451: ! 452: if (code == CODE_LABEL) ! 453: { 1.1 root 454: LABEL_REFS (insn) = insn; 455: /* Any label that cannot be deleted 456: is considered to start a reachable block. */ 457: if (LABEL_PRESERVE_P (insn)) 458: block_live[i] = 1; 459: } 1.1.1.7 ! root 460: } 1.1 root 461: 1.1.1.7 ! root 462: else if (GET_RTX_CLASS (code) == 'i') ! 463: { ! 464: basic_block_end[i] = insn; ! 465: basic_block_loop_depth[i] = depth; ! 466: } ! 467: ! 468: if (GET_RTX_CLASS (code) == 'i') ! 469: { ! 470: /* Make a list of all labels referred to other than by jumps. */ ! 471: for (note = REG_NOTES (insn); note; note = XEXP (note, 1)) ! 472: if (REG_NOTE_KIND (note) == REG_LABEL) 1.1 root 473: label_value_list = gen_rtx (EXPR_LIST, VOIDmode, XEXP (note, 0), 474: label_value_list); 1.1.1.7 ! root 475: } 1.1 root 476: 1.1.1.7 ! root 477: BLOCK_NUM (insn) = i; 1.1 root 478: 1.1.1.7 ! root 479: if (code != NOTE) ! 480: prev_code = code; ! 481: } ! 482: ! 483: if (i + 1 != n_basic_blocks) ! 484: abort (); 1.1 root 485: 1.1.1.4 root 486: /* Don't delete the labels (in this function) 487: that are referenced by non-jump instructions. */ 1.1.1.7 ! root 488: ! 489: for (x = label_value_list; x; x = XEXP (x, 1)) ! 490: if (! LABEL_REF_NONLOCAL_P (x)) ! 491: block_live[BLOCK_NUM (XEXP (x, 0))] = 1; ! 492: ! 493: for (x = forced_labels; x; x = XEXP (x, 1)) ! 494: if (! LABEL_REF_NONLOCAL_P (x)) ! 495: block_live[BLOCK_NUM (XEXP (x, 0))] = 1; 1.1 root 496: 497: /* Record which basic blocks control can drop in to. */ 498: 1.1.1.7 ! root 499: for (i = 0; i < n_basic_blocks; i++) ! 500: { ! 501: for (insn = PREV_INSN (basic_block_head[i]); ! 502: insn && GET_CODE (insn) == NOTE; insn = PREV_INSN (insn)) ! 503: ; ! 504: ! 505: basic_block_drops_in[i] = insn && GET_CODE (insn) != BARRIER; ! 506: } 1.1 root 507: 508: /* Now find which basic blocks can actually be reached 509: and put all jump insns' LABEL_REFS onto the ref-chains 510: of their target labels. */ 511: 512: if (n_basic_blocks > 0) 513: { 514: int something_marked = 1; 515: 1.1.1.7 ! root 516: /* Find all indirect jump insns and mark them as possibly jumping to all ! 517: the labels whose addresses are explicitly used. This is because, ! 518: when there are computed gotos, we can't tell which labels they jump ! 519: to, of all the possibilities. ! 520: ! 521: Tablejumps and casesi insns are OK and we can recognize them by ! 522: a (use (label_ref)). */ 1.1 root 523: 524: for (insn = f; insn; insn = NEXT_INSN (insn)) 1.1.1.7 ! root 525: if (GET_CODE (insn) == JUMP_INSN) 1.1 root 526: { 1.1.1.7 ! root 527: rtx pat = PATTERN (insn); ! 528: int computed_jump = 0; ! 529: ! 530: if (GET_CODE (pat) == PARALLEL) ! 531: { ! 532: int len = XVECLEN (pat, 0); ! 533: int has_use_labelref = 0; ! 534: ! 535: for (i = len - 1; i >= 0; i--) ! 536: if (GET_CODE (XVECEXP (pat, 0, i)) == USE ! 537: && (GET_CODE (XEXP (XVECEXP (pat, 0, i), 0)) ! 538: == LABEL_REF)) ! 539: has_use_labelref = 1; ! 540: ! 541: if (! has_use_labelref) ! 542: for (i = len - 1; i >= 0; i--) ! 543: if (GET_CODE (XVECEXP (pat, 0, i)) == SET ! 544: && SET_DEST (XVECEXP (pat, 0, i)) == pc_rtx ! 545: && uses_reg_or_mem (SET_SRC (XVECEXP (pat, 0, i)))) ! 546: computed_jump = 1; ! 547: } ! 548: else if (GET_CODE (pat) == SET ! 549: && SET_DEST (pat) == pc_rtx ! 550: && uses_reg_or_mem (SET_SRC (pat))) ! 551: computed_jump = 1; ! 552: ! 553: if (computed_jump) ! 554: { ! 555: for (x = label_value_list; x; x = XEXP (x, 1)) ! 556: mark_label_ref (gen_rtx (LABEL_REF, VOIDmode, XEXP (x, 0)), ! 557: insn, 0); ! 558: ! 559: for (x = forced_labels; x; x = XEXP (x, 1)) ! 560: mark_label_ref (gen_rtx (LABEL_REF, VOIDmode, XEXP (x, 0)), 1.1 root 561: insn, 0); 1.1.1.7 ! root 562: } 1.1 root 563: } 564: 565: /* Find all call insns and mark them as possibly jumping 566: to all the nonlocal goto handler labels. */ 567: 568: for (insn = f; insn; insn = NEXT_INSN (insn)) 569: if (GET_CODE (insn) == CALL_INSN) 570: { 571: for (x = nonlocal_label_list; x; x = XEXP (x, 1)) 1.1.1.5 root 572: /* Don't try marking labels that 573: were deleted as unreferenced. */ 574: if (GET_CODE (XEXP (x, 0)) == CODE_LABEL) 575: mark_label_ref (gen_rtx (LABEL_REF, VOIDmode, XEXP (x, 0)), 576: insn, 0); 1.1.1.7 ! root 577: 1.1 root 578: /* ??? This could be made smarter: 579: in some cases it's possible to tell that certain 580: calls will not do a nonlocal goto. 581: 582: For example, if the nested functions that do the 583: nonlocal gotos do not have their addresses taken, then 584: only calls to those functions or to other nested 585: functions that use them could possibly do nonlocal 586: gotos. */ 587: } 588: 589: /* Pass over all blocks, marking each block that is reachable 590: and has not yet been marked. 591: Keep doing this until, in one pass, no blocks have been marked. 592: Then blocks_live and blocks_marked are identical and correct. 593: In addition, all jumps actually reachable have been marked. */ 594: 595: while (something_marked) 596: { 597: something_marked = 0; 598: for (i = 0; i < n_basic_blocks; i++) 599: if (block_live[i] && !block_marked[i]) 600: { 601: block_marked[i] = 1; 602: something_marked = 1; 603: if (i + 1 < n_basic_blocks && basic_block_drops_in[i + 1]) 604: block_live[i + 1] = 1; 605: insn = basic_block_end[i]; 606: if (GET_CODE (insn) == JUMP_INSN) 607: mark_label_ref (PATTERN (insn), insn, 0); 608: } 609: } 610: 1.1.1.7 ! root 611: /* ??? See if we have a "live" basic block that is not reachable. ! 612: This can happen if it is headed by a label that is preserved or ! 613: in one of the label lists, but no call or computed jump is in ! 614: the loop. It's not clear if we can delete the block or not, ! 615: but don't for now. However, we will mess up register status if ! 616: it remains unreachable, so add a fake reachability from the ! 617: previous block. */ ! 618: ! 619: for (i = 1; i < n_basic_blocks; i++) ! 620: if (block_live[i] && ! basic_block_drops_in[i] ! 621: && GET_CODE (basic_block_head[i]) == CODE_LABEL ! 622: && LABEL_REFS (basic_block_head[i]) == basic_block_head[i]) ! 623: basic_block_drops_in[i] = 1; ! 624: 1.1 root 625: /* Now delete the code for any basic blocks that can't be reached. 626: They can occur because jump_optimize does not recognize 627: unreachable loops as unreachable. */ 628: 629: for (i = 0; i < n_basic_blocks; i++) 630: if (!block_live[i]) 631: { 632: insn = basic_block_head[i]; 633: while (1) 634: { 635: if (GET_CODE (insn) == BARRIER) 636: abort (); 637: if (GET_CODE (insn) != NOTE) 638: { 639: PUT_CODE (insn, NOTE); 640: NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED; 641: NOTE_SOURCE_FILE (insn) = 0; 642: } 643: if (insn == basic_block_end[i]) 644: { 645: /* BARRIERs are between basic blocks, not part of one. 646: Delete a BARRIER if the preceding jump is deleted. 647: We cannot alter a BARRIER into a NOTE 648: because it is too short; but we can really delete 649: it because it is not part of a basic block. */ 650: if (NEXT_INSN (insn) != 0 651: && GET_CODE (NEXT_INSN (insn)) == BARRIER) 652: delete_insn (NEXT_INSN (insn)); 653: break; 654: } 655: insn = NEXT_INSN (insn); 656: } 657: /* Each time we delete some basic blocks, 658: see if there is a jump around them that is 659: being turned into a no-op. If so, delete it. */ 660: 661: if (block_live[i - 1]) 662: { 663: register int j; 664: for (j = i; j < n_basic_blocks; j++) 665: if (block_live[j]) 666: { 667: rtx label; 668: insn = basic_block_end[i - 1]; 669: if (GET_CODE (insn) == JUMP_INSN 670: /* An unconditional jump is the only possibility 671: we must check for, since a conditional one 672: would make these blocks live. */ 673: && simplejump_p (insn) 674: && (label = XEXP (SET_SRC (PATTERN (insn)), 0), 1) 675: && INSN_UID (label) != 0 676: && BLOCK_NUM (label) == j) 677: { 678: PUT_CODE (insn, NOTE); 679: NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED; 680: NOTE_SOURCE_FILE (insn) = 0; 681: if (GET_CODE (NEXT_INSN (insn)) != BARRIER) 682: abort (); 683: delete_insn (NEXT_INSN (insn)); 684: } 685: break; 686: } 687: } 688: } 689: } 690: } 691: 1.1.1.7 ! root 692: /* Return 1 if X contain a REG or MEM that is not in the constant pool. */ ! 693: ! 694: static int ! 695: uses_reg_or_mem (x) ! 696: rtx x; ! 697: { ! 698: enum rtx_code code = GET_CODE (x); ! 699: int i, j; ! 700: char *fmt; ! 701: ! 702: if (code == REG ! 703: || (code == MEM ! 704: && ! (GET_CODE (XEXP (x, 0)) == SYMBOL_REF ! 705: && CONSTANT_POOL_ADDRESS_P (XEXP (x, 0))))) ! 706: return 1; ! 707: ! 708: fmt = GET_RTX_FORMAT (code); ! 709: for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) ! 710: { ! 711: if (fmt[i] == 'e' ! 712: && uses_reg_or_mem (XEXP (x, i))) ! 713: return 1; ! 714: ! 715: if (fmt[i] == 'E') ! 716: for (j = 0; j < XVECLEN (x, i); j++) ! 717: if (uses_reg_or_mem (XVECEXP (x, i, j))) ! 718: return 1; ! 719: } ! 720: ! 721: return 0; ! 722: } ! 723: 1.1 root 724: /* Check expression X for label references; 725: if one is found, add INSN to the label's chain of references. 726: 727: CHECKDUP means check for and avoid creating duplicate references 728: from the same insn. Such duplicates do no serious harm but 729: can slow life analysis. CHECKDUP is set only when duplicates 730: are likely. */ 731: 732: static void 733: mark_label_ref (x, insn, checkdup) 734: rtx x, insn; 735: int checkdup; 736: { 737: register RTX_CODE code; 738: register int i; 739: register char *fmt; 740: 741: /* We can be called with NULL when scanning label_value_list. */ 742: if (x == 0) 743: return; 744: 745: code = GET_CODE (x); 746: if (code == LABEL_REF) 747: { 748: register rtx label = XEXP (x, 0); 749: register rtx y; 750: if (GET_CODE (label) != CODE_LABEL) 751: abort (); 752: /* If the label was never emitted, this insn is junk, 753: but avoid a crash trying to refer to BLOCK_NUM (label). 754: This can happen as a result of a syntax error 755: and a diagnostic has already been printed. */ 756: if (INSN_UID (label) == 0) 757: return; 758: CONTAINING_INSN (x) = insn; 759: /* if CHECKDUP is set, check for duplicate ref from same insn 760: and don't insert. */ 761: if (checkdup) 762: for (y = LABEL_REFS (label); y != label; y = LABEL_NEXTREF (y)) 763: if (CONTAINING_INSN (y) == insn) 764: return; 765: LABEL_NEXTREF (x) = LABEL_REFS (label); 766: LABEL_REFS (label) = x; 767: block_live_static[BLOCK_NUM (label)] = 1; 768: return; 769: } 770: 771: fmt = GET_RTX_FORMAT (code); 772: for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) 773: { 774: if (fmt[i] == 'e') 775: mark_label_ref (XEXP (x, i), insn, 0); 776: if (fmt[i] == 'E') 777: { 778: register int j; 779: for (j = 0; j < XVECLEN (x, i); j++) 780: mark_label_ref (XVECEXP (x, i, j), insn, 1); 781: } 782: } 783: } 784: 785: /* Determine which registers are live at the start of each 786: basic block of the function whose first insn is F. 787: NREGS is the number of registers used in F. 788: We allocate the vector basic_block_live_at_start 789: and the regsets that it points to, and fill them with the data. 790: regset_size and regset_bytes are also set here. */ 791: 792: static void 793: life_analysis (f, nregs) 794: rtx f; 795: int nregs; 796: { 797: register regset tem; 798: int first_pass; 799: int changed; 800: /* For each basic block, a bitmask of regs 801: live on exit from the block. */ 802: regset *basic_block_live_at_end; 803: /* For each basic block, a bitmask of regs 804: live on entry to a successor-block of this block. 805: If this does not match basic_block_live_at_end, 806: that must be updated, and the block must be rescanned. */ 807: regset *basic_block_new_live_at_end; 808: /* For each basic block, a bitmask of regs 809: whose liveness at the end of the basic block 810: can make a difference in which regs are live on entry to the block. 811: These are the regs that are set within the basic block, 812: possibly excluding those that are used after they are set. */ 813: regset *basic_block_significant; 814: register int i; 815: rtx insn; 816: 817: struct obstack flow_obstack; 818: 819: gcc_obstack_init (&flow_obstack); 820: 821: max_regno = nregs; 822: 823: bzero (regs_ever_live, sizeof regs_ever_live); 824: 825: /* Allocate and zero out many data structures 826: that will record the data from lifetime analysis. */ 827: 828: allocate_for_life_analysis (); 829: 830: reg_next_use = (rtx *) alloca (nregs * sizeof (rtx)); 1.1.1.7 ! root 831: bzero ((char *) reg_next_use, nregs * sizeof (rtx)); 1.1 root 832: 833: /* Set up several regset-vectors used internally within this function. 834: Their meanings are documented above, with their declarations. */ 835: 1.1.1.7 ! root 836: basic_block_live_at_end ! 837: = (regset *) alloca (n_basic_blocks * sizeof (regset)); ! 838: 1.1 root 839: /* Don't use alloca since that leads to a crash rather than an error message 840: if there isn't enough space. 841: Don't use oballoc since we may need to allocate other things during 842: this function on the temporary obstack. */ 843: tem = (regset) obstack_alloc (&flow_obstack, n_basic_blocks * regset_bytes); 1.1.1.7 ! root 844: bzero ((char *) tem, n_basic_blocks * regset_bytes); ! 845: init_regset_vector (basic_block_live_at_end, tem, ! 846: n_basic_blocks, regset_bytes); 1.1 root 847: 1.1.1.7 ! root 848: basic_block_new_live_at_end ! 849: = (regset *) alloca (n_basic_blocks * sizeof (regset)); 1.1 root 850: tem = (regset) obstack_alloc (&flow_obstack, n_basic_blocks * regset_bytes); 1.1.1.7 ! root 851: bzero ((char *) tem, n_basic_blocks * regset_bytes); ! 852: init_regset_vector (basic_block_new_live_at_end, tem, ! 853: n_basic_blocks, regset_bytes); 1.1 root 854: 1.1.1.7 ! root 855: basic_block_significant ! 856: = (regset *) alloca (n_basic_blocks * sizeof (regset)); 1.1 root 857: tem = (regset) obstack_alloc (&flow_obstack, n_basic_blocks * regset_bytes); 1.1.1.7 ! root 858: bzero ((char *) tem, n_basic_blocks * regset_bytes); ! 859: init_regset_vector (basic_block_significant, tem, ! 860: n_basic_blocks, regset_bytes); 1.1 root 861: 862: /* Record which insns refer to any volatile memory 863: or for any reason can't be deleted just because they are dead stores. 864: Also, delete any insns that copy a register to itself. */ 865: 866: for (insn = f; insn; insn = NEXT_INSN (insn)) 867: { 868: enum rtx_code code1 = GET_CODE (insn); 869: if (code1 == CALL_INSN) 870: INSN_VOLATILE (insn) = 1; 871: else if (code1 == INSN || code1 == JUMP_INSN) 872: { 873: /* Delete (in effect) any obvious no-op moves. */ 874: if (GET_CODE (PATTERN (insn)) == SET 875: && GET_CODE (SET_DEST (PATTERN (insn))) == REG 876: && GET_CODE (SET_SRC (PATTERN (insn))) == REG 877: && REGNO (SET_DEST (PATTERN (insn))) == 878: REGNO (SET_SRC (PATTERN (insn))) 879: /* Insns carrying these notes are useful later on. */ 1.1.1.4 root 880: && ! find_reg_note (insn, REG_EQUAL, NULL_RTX)) 1.1 root 881: { 882: PUT_CODE (insn, NOTE); 883: NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED; 884: NOTE_SOURCE_FILE (insn) = 0; 885: } 886: else if (GET_CODE (PATTERN (insn)) == PARALLEL) 887: { 888: /* If nothing but SETs of registers to themselves, 889: this insn can also be deleted. */ 890: for (i = 0; i < XVECLEN (PATTERN (insn), 0); i++) 891: { 892: rtx tem = XVECEXP (PATTERN (insn), 0, i); 893: 894: if (GET_CODE (tem) == USE 895: || GET_CODE (tem) == CLOBBER) 896: continue; 897: 898: if (GET_CODE (tem) != SET 899: || GET_CODE (SET_DEST (tem)) != REG 900: || GET_CODE (SET_SRC (tem)) != REG 901: || REGNO (SET_DEST (tem)) != REGNO (SET_SRC (tem))) 902: break; 903: } 904: 905: if (i == XVECLEN (PATTERN (insn), 0) 906: /* Insns carrying these notes are useful later on. */ 1.1.1.4 root 907: && ! find_reg_note (insn, REG_EQUAL, NULL_RTX)) 1.1 root 908: { 909: PUT_CODE (insn, NOTE); 910: NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED; 911: NOTE_SOURCE_FILE (insn) = 0; 912: } 913: else 914: INSN_VOLATILE (insn) = volatile_refs_p (PATTERN (insn)); 915: } 916: else if (GET_CODE (PATTERN (insn)) != USE) 917: INSN_VOLATILE (insn) = volatile_refs_p (PATTERN (insn)); 918: /* A SET that makes space on the stack cannot be dead. 919: (Such SETs occur only for allocating variable-size data, 920: so they will always have a PLUS or MINUS according to the 921: direction of stack growth.) 922: Even if this function never uses this stack pointer value, 923: signal handlers do! */ 924: else if (code1 == INSN && GET_CODE (PATTERN (insn)) == SET 925: && SET_DEST (PATTERN (insn)) == stack_pointer_rtx 926: #ifdef STACK_GROWS_DOWNWARD 927: && GET_CODE (SET_SRC (PATTERN (insn))) == MINUS 928: #else 929: && GET_CODE (SET_SRC (PATTERN (insn))) == PLUS 930: #endif 931: && XEXP (SET_SRC (PATTERN (insn)), 0) == stack_pointer_rtx) 932: INSN_VOLATILE (insn) = 1; 933: } 934: } 935: 936: if (n_basic_blocks > 0) 937: #ifdef EXIT_IGNORE_STACK 938: if (! EXIT_IGNORE_STACK 939: || (! FRAME_POINTER_REQUIRED && flag_omit_frame_pointer)) 940: #endif 941: { 942: /* If exiting needs the right stack value, 943: consider the stack pointer live at the end of the function. */ 944: basic_block_live_at_end[n_basic_blocks - 1] 945: [STACK_POINTER_REGNUM / REGSET_ELT_BITS] 1.1.1.4 root 946: |= (REGSET_ELT_TYPE) 1 << (STACK_POINTER_REGNUM % REGSET_ELT_BITS); 1.1 root 947: basic_block_new_live_at_end[n_basic_blocks - 1] 948: [STACK_POINTER_REGNUM / REGSET_ELT_BITS] 1.1.1.4 root 949: |= (REGSET_ELT_TYPE) 1 << (STACK_POINTER_REGNUM % REGSET_ELT_BITS); 950: } 951: 952: /* Mark the frame pointer is needed at the end of the function. If 953: we end up eliminating it, it will be removed from the live list 954: of each basic block by reload. */ 955: 956: if (n_basic_blocks > 0) 957: { 958: basic_block_live_at_end[n_basic_blocks - 1] 959: [FRAME_POINTER_REGNUM / REGSET_ELT_BITS] 960: |= (REGSET_ELT_TYPE) 1 << (FRAME_POINTER_REGNUM % REGSET_ELT_BITS); 961: basic_block_new_live_at_end[n_basic_blocks - 1] 962: [FRAME_POINTER_REGNUM / REGSET_ELT_BITS] 963: |= (REGSET_ELT_TYPE) 1 << (FRAME_POINTER_REGNUM % REGSET_ELT_BITS); 1.1.1.6 root 964: #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM 965: /* If they are different, also mark the hard frame pointer as live */ 966: basic_block_live_at_end[n_basic_blocks - 1] 967: [HARD_FRAME_POINTER_REGNUM / REGSET_ELT_BITS] 968: |= (REGSET_ELT_TYPE) 1 << (HARD_FRAME_POINTER_REGNUM 969: % REGSET_ELT_BITS); 970: basic_block_new_live_at_end[n_basic_blocks - 1] 971: [HARD_FRAME_POINTER_REGNUM / REGSET_ELT_BITS] 972: |= (REGSET_ELT_TYPE) 1 << (HARD_FRAME_POINTER_REGNUM 973: % REGSET_ELT_BITS); 974: #endif 1.1 root 975: } 976: 977: /* Mark all global registers as being live at the end of the function 978: since they may be referenced by our caller. */ 979: 980: if (n_basic_blocks > 0) 981: for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) 982: if (global_regs[i]) 983: { 984: basic_block_live_at_end[n_basic_blocks - 1] 1.1.1.4 root 985: [i / REGSET_ELT_BITS] 986: |= (REGSET_ELT_TYPE) 1 << (i % REGSET_ELT_BITS); 1.1 root 987: basic_block_new_live_at_end[n_basic_blocks - 1] 1.1.1.4 root 988: [i / REGSET_ELT_BITS] 989: |= (REGSET_ELT_TYPE) 1 << (i % REGSET_ELT_BITS); 1.1 root 990: } 991: 992: /* Propagate life info through the basic blocks 993: around the graph of basic blocks. 994: 995: This is a relaxation process: each time a new register 996: is live at the end of the basic block, we must scan the block 997: to determine which registers are, as a consequence, live at the beginning 998: of that block. These registers must then be marked live at the ends 999: of all the blocks that can transfer control to that block. 1000: The process continues until it reaches a fixed point. */ 1001: 1002: first_pass = 1; 1003: changed = 1; 1004: while (changed) 1005: { 1006: changed = 0; 1007: for (i = n_basic_blocks - 1; i >= 0; i--) 1008: { 1009: int consider = first_pass; 1010: int must_rescan = first_pass; 1011: register int j; 1012: 1013: if (!first_pass) 1014: { 1015: /* Set CONSIDER if this block needs thinking about at all 1016: (that is, if the regs live now at the end of it 1017: are not the same as were live at the end of it when 1018: we last thought about it). 1019: Set must_rescan if it needs to be thought about 1020: instruction by instruction (that is, if any additional 1021: reg that is live at the end now but was not live there before 1022: is one of the significant regs of this basic block). */ 1023: 1024: for (j = 0; j < regset_size; j++) 1025: { 1.1.1.4 root 1026: register REGSET_ELT_TYPE x 1027: = (basic_block_new_live_at_end[i][j] 1028: & ~basic_block_live_at_end[i][j]); 1.1 root 1029: if (x) 1030: consider = 1; 1031: if (x & basic_block_significant[i][j]) 1032: { 1033: must_rescan = 1; 1034: consider = 1; 1035: break; 1036: } 1037: } 1038: 1039: if (! consider) 1040: continue; 1041: } 1042: 1043: /* The live_at_start of this block may be changing, 1044: so another pass will be required after this one. */ 1045: changed = 1; 1046: 1047: if (! must_rescan) 1048: { 1049: /* No complete rescan needed; 1050: just record those variables newly known live at end 1051: as live at start as well. */ 1052: for (j = 0; j < regset_size; j++) 1053: { 1.1.1.4 root 1054: register REGSET_ELT_TYPE x 1055: = (basic_block_new_live_at_end[i][j] 1056: & ~basic_block_live_at_end[i][j]); 1.1 root 1057: basic_block_live_at_start[i][j] |= x; 1058: basic_block_live_at_end[i][j] |= x; 1059: } 1060: } 1061: else 1062: { 1063: /* Update the basic_block_live_at_start 1064: by propagation backwards through the block. */ 1.1.1.7 ! root 1065: bcopy ((char *) basic_block_new_live_at_end[i], ! 1066: (char *) basic_block_live_at_end[i], regset_bytes); ! 1067: bcopy ((char *) basic_block_live_at_end[i], ! 1068: (char *) basic_block_live_at_start[i], regset_bytes); 1.1 root 1069: propagate_block (basic_block_live_at_start[i], 1070: basic_block_head[i], basic_block_end[i], 0, 1.1.1.4 root 1071: first_pass ? basic_block_significant[i] 1072: : (regset) 0, 1.1 root 1073: i); 1074: } 1075: 1076: { 1077: register rtx jump, head; 1.1.1.7 ! root 1078: 1.1 root 1079: /* Update the basic_block_new_live_at_end's of the block 1080: that falls through into this one (if any). */ 1081: head = basic_block_head[i]; 1082: if (basic_block_drops_in[i]) 1083: { 1084: register int j; 1085: for (j = 0; j < regset_size; j++) 1.1.1.7 ! root 1086: basic_block_new_live_at_end[i-1][j] 1.1 root 1087: |= basic_block_live_at_start[i][j]; 1088: } 1.1.1.7 ! root 1089: 1.1 root 1090: /* Update the basic_block_new_live_at_end's of 1091: all the blocks that jump to this one. */ 1092: if (GET_CODE (head) == CODE_LABEL) 1093: for (jump = LABEL_REFS (head); 1094: jump != head; 1095: jump = LABEL_NEXTREF (jump)) 1096: { 1097: register int from_block = BLOCK_NUM (CONTAINING_INSN (jump)); 1098: register int j; 1099: for (j = 0; j < regset_size; j++) 1100: basic_block_new_live_at_end[from_block][j] 1101: |= basic_block_live_at_start[i][j]; 1102: } 1103: } 1104: #ifdef USE_C_ALLOCA 1105: alloca (0); 1106: #endif 1107: } 1108: first_pass = 0; 1109: } 1110: 1111: /* The only pseudos that are live at the beginning of the function are 1112: those that were not set anywhere in the function. local-alloc doesn't 1113: know how to handle these correctly, so mark them as not local to any 1114: one basic block. */ 1115: 1116: if (n_basic_blocks > 0) 1117: for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++) 1118: if (basic_block_live_at_start[0][i / REGSET_ELT_BITS] 1.1.1.4 root 1119: & ((REGSET_ELT_TYPE) 1 << (i % REGSET_ELT_BITS))) 1.1 root 1120: reg_basic_block[i] = REG_BLOCK_GLOBAL; 1121: 1122: /* Now the life information is accurate. 1123: Make one more pass over each basic block 1124: to delete dead stores, create autoincrement addressing 1125: and record how many times each register is used, is set, or dies. 1126: 1127: To save time, we operate directly in basic_block_live_at_end[i], 1128: thus destroying it (in fact, converting it into a copy of 1129: basic_block_live_at_start[i]). This is ok now because 1130: basic_block_live_at_end[i] is no longer used past this point. */ 1131: 1132: max_scratch = 0; 1133: 1134: for (i = 0; i < n_basic_blocks; i++) 1135: { 1136: propagate_block (basic_block_live_at_end[i], 1.1.1.4 root 1137: basic_block_head[i], basic_block_end[i], 1, 1138: (regset) 0, i); 1.1 root 1139: #ifdef USE_C_ALLOCA 1140: alloca (0); 1141: #endif 1142: } 1143: 1144: #if 0 1145: /* Something live during a setjmp should not be put in a register 1146: on certain machines which restore regs from stack frames 1147: rather than from the jmpbuf. 1148: But we don't need to do this for the user's variables, since 1149: ANSI says only volatile variables need this. */ 1150: #ifdef LONGJMP_RESTORE_FROM_STACK 1151: for (i = FIRST_PSEUDO_REGISTER; i < nregs; i++) 1.1.1.4 root 1152: if (regs_live_at_setjmp[i / REGSET_ELT_BITS] 1153: & ((REGSET_ELT_TYPE) 1 << (i % REGSET_ELT_BITS)) 1.1 root 1154: && regno_reg_rtx[i] != 0 && ! REG_USERVAR_P (regno_reg_rtx[i])) 1155: { 1156: reg_live_length[i] = -1; 1157: reg_basic_block[i] = -1; 1158: } 1159: #endif 1160: #endif 1161: 1162: /* We have a problem with any pseudoreg that 1163: lives across the setjmp. ANSI says that if a 1164: user variable does not change in value 1165: between the setjmp and the longjmp, then the longjmp preserves it. 1166: This includes longjmp from a place where the pseudo appears dead. 1167: (In principle, the value still exists if it is in scope.) 1168: If the pseudo goes in a hard reg, some other value may occupy 1169: that hard reg where this pseudo is dead, thus clobbering the pseudo. 1170: Conclusion: such a pseudo must not go in a hard reg. */ 1171: for (i = FIRST_PSEUDO_REGISTER; i < nregs; i++) 1.1.1.4 root 1172: if ((regs_live_at_setjmp[i / REGSET_ELT_BITS] 1173: & ((REGSET_ELT_TYPE) 1 << (i % REGSET_ELT_BITS))) 1.1 root 1174: && regno_reg_rtx[i] != 0) 1175: { 1176: reg_live_length[i] = -1; 1177: reg_basic_block[i] = -1; 1178: } 1179: 1.1.1.4 root 1180: obstack_free (&flow_obstack, NULL_PTR); 1.1 root 1181: } 1182: 1183: /* Subroutines of life analysis. */ 1184: 1185: /* Allocate the permanent data structures that represent the results 1186: of life analysis. Not static since used also for stupid life analysis. */ 1187: 1188: void 1189: allocate_for_life_analysis () 1190: { 1191: register int i; 1192: register regset tem; 1193: 1194: regset_size = ((max_regno + REGSET_ELT_BITS - 1) / REGSET_ELT_BITS); 1195: regset_bytes = regset_size * sizeof (*(regset)0); 1196: 1197: reg_n_refs = (int *) oballoc (max_regno * sizeof (int)); 1.1.1.7 ! root 1198: bzero ((char *) reg_n_refs, max_regno * sizeof (int)); 1.1 root 1199: 1200: reg_n_sets = (short *) oballoc (max_regno * sizeof (short)); 1.1.1.7 ! root 1201: bzero ((char *) reg_n_sets, max_regno * sizeof (short)); 1.1 root 1202: 1203: reg_n_deaths = (short *) oballoc (max_regno * sizeof (short)); 1.1.1.7 ! root 1204: bzero ((char *) reg_n_deaths, max_regno * sizeof (short)); ! 1205: ! 1206: reg_changes_size = (char *) oballoc (max_regno * sizeof (char)); ! 1207: bzero (reg_changes_size, max_regno * sizeof (char));; 1.1 root 1208: 1209: reg_live_length = (int *) oballoc (max_regno * sizeof (int)); 1.1.1.7 ! root 1210: bzero ((char *) reg_live_length, max_regno * sizeof (int)); 1.1 root 1211: 1212: reg_n_calls_crossed = (int *) oballoc (max_regno * sizeof (int)); 1.1.1.7 ! root 1213: bzero ((char *) reg_n_calls_crossed, max_regno * sizeof (int)); 1.1 root 1214: 1.1.1.5 root 1215: reg_basic_block = (int *) oballoc (max_regno * sizeof (int)); 1.1 root 1216: for (i = 0; i < max_regno; i++) 1217: reg_basic_block[i] = REG_BLOCK_UNKNOWN; 1218: 1.1.1.7 ! root 1219: basic_block_live_at_start ! 1220: = (regset *) oballoc (n_basic_blocks * sizeof (regset)); 1.1 root 1221: tem = (regset) oballoc (n_basic_blocks * regset_bytes); 1.1.1.7 ! root 1222: bzero ((char *) tem, n_basic_blocks * regset_bytes); ! 1223: init_regset_vector (basic_block_live_at_start, tem, ! 1224: n_basic_blocks, regset_bytes); 1.1 root 1225: 1226: regs_live_at_setjmp = (regset) oballoc (regset_bytes); 1.1.1.7 ! root 1227: bzero ((char *) regs_live_at_setjmp, regset_bytes); 1.1 root 1228: } 1229: 1230: /* Make each element of VECTOR point at a regset, 1231: taking the space for all those regsets from SPACE. 1232: SPACE is of type regset, but it is really as long as NELTS regsets. 1233: BYTES_PER_ELT is the number of bytes in one regset. */ 1234: 1235: static void 1236: init_regset_vector (vector, space, nelts, bytes_per_elt) 1237: regset *vector; 1238: regset space; 1239: int nelts; 1240: int bytes_per_elt; 1241: { 1242: register int i; 1243: register regset p = space; 1244: 1245: for (i = 0; i < nelts; i++) 1246: { 1247: vector[i] = p; 1248: p += bytes_per_elt / sizeof (*p); 1249: } 1250: } 1.1.1.7 ! root 1251: 1.1 root 1252: /* Compute the registers live at the beginning of a basic block 1253: from those live at the end. 1254: 1255: When called, OLD contains those live at the end. 1256: On return, it contains those live at the beginning. 1257: FIRST and LAST are the first and last insns of the basic block. 1258: 1259: FINAL is nonzero if we are doing the final pass which is not 1260: for computing the life info (since that has already been done) 1261: but for acting on it. On this pass, we delete dead stores, 1262: set up the logical links and dead-variables lists of instructions, 1263: and merge instructions for autoincrement and autodecrement addresses. 1264: 1265: SIGNIFICANT is nonzero only the first time for each basic block. 1266: If it is nonzero, it points to a regset in which we store 1267: a 1 for each register that is set within the block. 1268: 1269: BNUM is the number of the basic block. */ 1270: 1271: static void 1272: propagate_block (old, first, last, final, significant, bnum) 1273: register regset old; 1274: rtx first; 1275: rtx last; 1276: int final; 1277: regset significant; 1278: int bnum; 1279: { 1280: register rtx insn; 1281: rtx prev; 1282: regset live; 1283: regset dead; 1284: 1285: /* The following variables are used only if FINAL is nonzero. */ 1286: /* This vector gets one element for each reg that has been live 1287: at any point in the basic block that has been scanned so far. 1288: SOMETIMES_MAX says how many elements are in use so far. 1289: In each element, OFFSET is the byte-number within a regset 1290: for the register described by the element, and BIT is a mask 1291: for that register's bit within the byte. */ 1.1.1.4 root 1292: register struct sometimes { short offset; short bit; } *regs_sometimes_live; 1.1 root 1293: int sometimes_max = 0; 1294: /* This regset has 1 for each reg that we have seen live so far. 1295: It and REGS_SOMETIMES_LIVE are updated together. */ 1296: regset maxlive; 1297: 1298: /* The loop depth may change in the middle of a basic block. Since we 1299: scan from end to beginning, we start with the depth at the end of the 1300: current basic block, and adjust as we pass ends and starts of loops. */ 1301: loop_depth = basic_block_loop_depth[bnum]; 1302: 1303: dead = (regset) alloca (regset_bytes); 1304: live = (regset) alloca (regset_bytes); 1305: 1306: cc0_live = 0; 1307: last_mem_set = 0; 1308: 1309: /* Include any notes at the end of the block in the scan. 1310: This is in case the block ends with a call to setjmp. */ 1311: 1312: while (NEXT_INSN (last) != 0 && GET_CODE (NEXT_INSN (last)) == NOTE) 1313: { 1314: /* Look for loop boundaries, we are going forward here. */ 1315: last = NEXT_INSN (last); 1316: if (NOTE_LINE_NUMBER (last) == NOTE_INSN_LOOP_BEG) 1317: loop_depth++; 1318: else if (NOTE_LINE_NUMBER (last) == NOTE_INSN_LOOP_END) 1319: loop_depth--; 1320: } 1321: 1322: if (final) 1323: { 1.1.1.4 root 1324: register int i, offset; 1325: REGSET_ELT_TYPE bit; 1.1 root 1326: 1327: num_scratch = 0; 1328: maxlive = (regset) alloca (regset_bytes); 1.1.1.7 ! root 1329: bcopy ((char *) old, (char *) maxlive, regset_bytes); 1.1 root 1330: regs_sometimes_live 1.1.1.4 root 1331: = (struct sometimes *) alloca (max_regno * sizeof (struct sometimes)); 1.1 root 1332: 1333: /* Process the regs live at the end of the block. 1334: Enter them in MAXLIVE and REGS_SOMETIMES_LIVE. 1335: Also mark them as not local to any one basic block. */ 1336: 1337: for (offset = 0, i = 0; offset < regset_size; offset++) 1338: for (bit = 1; bit; bit <<= 1, i++) 1339: { 1340: if (i == max_regno) 1341: break; 1342: if (old[offset] & bit) 1343: { 1344: reg_basic_block[i] = REG_BLOCK_GLOBAL; 1345: regs_sometimes_live[sometimes_max].offset = offset; 1346: regs_sometimes_live[sometimes_max].bit = i % REGSET_ELT_BITS; 1347: sometimes_max++; 1348: } 1349: } 1350: } 1351: 1352: /* Scan the block an insn at a time from end to beginning. */ 1353: 1354: for (insn = last; ; insn = prev) 1355: { 1356: prev = PREV_INSN (insn); 1357: 1358: /* Look for loop boundaries, remembering that we are going backwards. */ 1359: if (GET_CODE (insn) == NOTE 1360: && NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END) 1361: loop_depth++; 1362: else if (GET_CODE (insn) == NOTE 1363: && NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG) 1364: loop_depth--; 1365: 1366: /* If we have LOOP_DEPTH == 0, there has been a bookkeeping error. 1367: Abort now rather than setting register status incorrectly. */ 1368: if (loop_depth == 0) 1369: abort (); 1370: 1371: /* If this is a call to `setjmp' et al, 1372: warn if any non-volatile datum is live. */ 1373: 1374: if (final && GET_CODE (insn) == NOTE 1375: && NOTE_LINE_NUMBER (insn) == NOTE_INSN_SETJMP) 1376: { 1377: int i; 1378: for (i = 0; i < regset_size; i++) 1379: regs_live_at_setjmp[i] |= old[i]; 1380: } 1381: 1382: /* Update the life-status of regs for this insn. 1383: First DEAD gets which regs are set in this insn 1384: then LIVE gets which regs are used in this insn. 1385: Then the regs live before the insn 1386: are those live after, with DEAD regs turned off, 1387: and then LIVE regs turned on. */ 1388: 1389: if (GET_RTX_CLASS (GET_CODE (insn)) == 'i') 1390: { 1391: register int i; 1.1.1.4 root 1392: rtx note = find_reg_note (insn, REG_RETVAL, NULL_RTX); 1.1 root 1393: int insn_is_dead 1394: = (insn_dead_p (PATTERN (insn), old, 0) 1395: /* Don't delete something that refers to volatile storage! */ 1396: && ! INSN_VOLATILE (insn)); 1397: int libcall_is_dead 1398: = (insn_is_dead && note != 0 1399: && libcall_dead_p (PATTERN (insn), old, note, insn)); 1400: 1401: /* If an instruction consists of just dead store(s) on final pass, 1402: "delete" it by turning it into a NOTE of type NOTE_INSN_DELETED. 1403: We could really delete it with delete_insn, but that 1404: can cause trouble for first or last insn in a basic block. */ 1405: if (final && insn_is_dead) 1406: { 1407: PUT_CODE (insn, NOTE); 1408: NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED; 1409: NOTE_SOURCE_FILE (insn) = 0; 1410: 1.1.1.2 root 1411: /* CC0 is now known to be dead. Either this insn used it, 1412: in which case it doesn't anymore, or clobbered it, 1413: so the next insn can't use it. */ 1414: cc0_live = 0; 1415: 1.1 root 1416: /* If this insn is copying the return value from a library call, 1417: delete the entire library call. */ 1418: if (libcall_is_dead) 1419: { 1420: rtx first = XEXP (note, 0); 1421: rtx p = insn; 1422: while (INSN_DELETED_P (first)) 1423: first = NEXT_INSN (first); 1424: while (p != first) 1425: { 1426: p = PREV_INSN (p); 1427: PUT_CODE (p, NOTE); 1428: NOTE_LINE_NUMBER (p) = NOTE_INSN_DELETED; 1429: NOTE_SOURCE_FILE (p) = 0; 1430: } 1431: } 1432: goto flushed; 1433: } 1434: 1435: for (i = 0; i < regset_size; i++) 1436: { 1437: dead[i] = 0; /* Faster than bzero here */ 1438: live[i] = 0; /* since regset_size is usually small */ 1439: } 1440: 1441: /* See if this is an increment or decrement that can be 1442: merged into a following memory address. */ 1443: #ifdef AUTO_INC_DEC 1444: { 1445: register rtx x = PATTERN (insn); 1446: /* Does this instruction increment or decrement a register? */ 1447: if (final && GET_CODE (x) == SET 1448: && GET_CODE (SET_DEST (x)) == REG 1449: && (GET_CODE (SET_SRC (x)) == PLUS 1450: || GET_CODE (SET_SRC (x)) == MINUS) 1451: && XEXP (SET_SRC (x), 0) == SET_DEST (x) 1452: && GET_CODE (XEXP (SET_SRC (x), 1)) == CONST_INT 1453: /* Ok, look for a following memory ref we can combine with. 1454: If one is found, change the memory ref to a PRE_INC 1455: or PRE_DEC, cancel this insn, and return 1. 1456: Return 0 if nothing has been done. */ 1457: && try_pre_increment_1 (insn)) 1458: goto flushed; 1459: } 1460: #endif /* AUTO_INC_DEC */ 1461: 1462: /* If this is not the final pass, and this insn is copying the 1463: value of a library call and it's dead, don't scan the 1464: insns that perform the library call, so that the call's 1465: arguments are not marked live. */ 1466: if (libcall_is_dead) 1467: { 1468: /* Mark the dest reg as `significant'. */ 1.1.1.4 root 1469: mark_set_regs (old, dead, PATTERN (insn), NULL_RTX, significant); 1.1 root 1470: 1471: insn = XEXP (note, 0); 1472: prev = PREV_INSN (insn); 1473: } 1474: else if (GET_CODE (PATTERN (insn)) == SET 1475: && SET_DEST (PATTERN (insn)) == stack_pointer_rtx 1476: && GET_CODE (SET_SRC (PATTERN (insn))) == PLUS 1477: && XEXP (SET_SRC (PATTERN (insn)), 0) == stack_pointer_rtx 1478: && GET_CODE (XEXP (SET_SRC (PATTERN (insn)), 1)) == CONST_INT) 1479: /* We have an insn to pop a constant amount off the stack. 1480: (Such insns use PLUS regardless of the direction of the stack, 1481: and any insn to adjust the stack by a constant is always a pop.) 1482: These insns, if not dead stores, have no effect on life. */ 1483: ; 1484: else 1485: { 1486: /* LIVE gets the regs used in INSN; 1487: DEAD gets those set by it. Dead insns don't make anything 1488: live. */ 1489: 1.1.1.4 root 1490: mark_set_regs (old, dead, PATTERN (insn), 1491: final ? insn : NULL_RTX, significant); 1.1 root 1492: 1493: /* If an insn doesn't use CC0, it becomes dead since we 1494: assume that every insn clobbers it. So show it dead here; 1495: mark_used_regs will set it live if it is referenced. */ 1496: cc0_live = 0; 1497: 1498: if (! insn_is_dead) 1499: mark_used_regs (old, live, PATTERN (insn), final, insn); 1500: 1501: /* Sometimes we may have inserted something before INSN (such as 1502: a move) when we make an auto-inc. So ensure we will scan 1503: those insns. */ 1504: #ifdef AUTO_INC_DEC 1505: prev = PREV_INSN (insn); 1506: #endif 1507: 1508: if (! insn_is_dead && GET_CODE (insn) == CALL_INSN) 1509: { 1510: register int i; 1511: 1.1.1.7 ! root 1512: rtx note; ! 1513: ! 1514: for (note = CALL_INSN_FUNCTION_USAGE (insn); ! 1515: note; ! 1516: note = XEXP (note, 1)) ! 1517: if (GET_CODE (XEXP (note, 0)) == USE) ! 1518: mark_used_regs (old, live, SET_DEST (XEXP (note, 0)), ! 1519: final, insn); ! 1520: 1.1 root 1521: /* Each call clobbers all call-clobbered regs that are not 1522: global. Note that the function-value reg is a 1523: call-clobbered reg, and mark_set_regs has already had 1524: a chance to handle it. */ 1525: 1526: for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) 1527: if (call_used_regs[i] && ! global_regs[i]) 1528: dead[i / REGSET_ELT_BITS] 1.1.1.4 root 1529: |= ((REGSET_ELT_TYPE) 1 << (i % REGSET_ELT_BITS)); 1.1 root 1530: 1531: /* The stack ptr is used (honorarily) by a CALL insn. */ 1532: live[STACK_POINTER_REGNUM / REGSET_ELT_BITS] 1.1.1.4 root 1533: |= ((REGSET_ELT_TYPE) 1 1534: << (STACK_POINTER_REGNUM % REGSET_ELT_BITS)); 1.1 root 1535: 1536: /* Calls may also reference any of the global registers, 1537: so they are made live. */ 1538: for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) 1539: if (global_regs[i]) 1.1.1.7 ! root 1540: mark_used_regs (old, live, ! 1541: gen_rtx (REG, reg_raw_mode[i], i), ! 1542: final, insn); 1.1 root 1543: 1544: /* Calls also clobber memory. */ 1545: last_mem_set = 0; 1546: } 1547: 1548: /* Update OLD for the registers used or set. */ 1549: for (i = 0; i < regset_size; i++) 1550: { 1551: old[i] &= ~dead[i]; 1552: old[i] |= live[i]; 1553: } 1554: 1555: if (GET_CODE (insn) == CALL_INSN && final) 1556: { 1557: /* Any regs live at the time of a call instruction 1558: must not go in a register clobbered by calls. 1559: Find all regs now live and record this for them. */ 1560: 1.1.1.4 root 1561: register struct sometimes *p = regs_sometimes_live; 1.1 root 1562: 1563: for (i = 0; i < sometimes_max; i++, p++) 1.1.1.4 root 1564: if (old[p->offset] & ((REGSET_ELT_TYPE) 1 << p->bit)) 1.1 root 1565: reg_n_calls_crossed[p->offset * REGSET_ELT_BITS + p->bit]+= 1; 1566: } 1567: } 1568: 1569: /* On final pass, add any additional sometimes-live regs 1570: into MAXLIVE and REGS_SOMETIMES_LIVE. 1571: Also update counts of how many insns each reg is live at. */ 1572: 1573: if (final) 1574: { 1575: for (i = 0; i < regset_size; i++) 1576: { 1.1.1.4 root 1577: register REGSET_ELT_TYPE diff = live[i] & ~maxlive[i]; 1.1 root 1578: 1579: if (diff) 1580: { 1581: register int regno; 1582: maxlive[i] |= diff; 1583: for (regno = 0; diff && regno < REGSET_ELT_BITS; regno++) 1.1.1.4 root 1584: if (diff & ((REGSET_ELT_TYPE) 1 << regno)) 1.1 root 1585: { 1586: regs_sometimes_live[sometimes_max].offset = i; 1587: regs_sometimes_live[sometimes_max].bit = regno; 1.1.1.4 root 1588: diff &= ~ ((REGSET_ELT_TYPE) 1 << regno); 1.1 root 1589: sometimes_max++; 1590: } 1591: } 1592: } 1593: 1594: { 1.1.1.4 root 1595: register struct sometimes *p = regs_sometimes_live; 1.1 root 1596: for (i = 0; i < sometimes_max; i++, p++) 1597: { 1.1.1.4 root 1598: if (old[p->offset] & ((REGSET_ELT_TYPE) 1 << p->bit)) 1.1 root 1599: reg_live_length[p->offset * REGSET_ELT_BITS + p->bit]++; 1600: } 1601: } 1602: } 1603: } 1604: flushed: ; 1605: if (insn == first) 1606: break; 1607: } 1608: 1609: if (num_scratch > max_scratch) 1610: max_scratch = num_scratch; 1611: } 1612: 1613: /* Return 1 if X (the body of an insn, or part of it) is just dead stores 1614: (SET expressions whose destinations are registers dead after the insn). 1615: NEEDED is the regset that says which regs are alive after the insn. 1616: 1617: Unless CALL_OK is non-zero, an insn is needed if it contains a CALL. */ 1618: 1619: static int 1620: insn_dead_p (x, needed, call_ok) 1621: rtx x; 1622: regset needed; 1623: int call_ok; 1624: { 1625: register RTX_CODE code = GET_CODE (x); 1626: /* If setting something that's a reg or part of one, 1627: see if that register's altered value will be live. */ 1628: 1629: if (code == SET) 1630: { 1631: register rtx r = SET_DEST (x); 1632: /* A SET that is a subroutine call cannot be dead. */ 1633: if (! call_ok && GET_CODE (SET_SRC (x)) == CALL) 1634: return 0; 1635: 1636: #ifdef HAVE_cc0 1637: if (GET_CODE (r) == CC0) 1638: return ! cc0_live; 1639: #endif 1640: 1641: if (GET_CODE (r) == MEM && last_mem_set && ! MEM_VOLATILE_P (r) 1642: && rtx_equal_p (r, last_mem_set)) 1643: return 1; 1644: 1645: while (GET_CODE (r) == SUBREG 1646: || GET_CODE (r) == STRICT_LOW_PART 1647: || GET_CODE (r) == ZERO_EXTRACT 1648: || GET_CODE (r) == SIGN_EXTRACT) 1649: r = SUBREG_REG (r); 1650: 1651: if (GET_CODE (r) == REG) 1652: { 1653: register int regno = REGNO (r); 1654: register int offset = regno / REGSET_ELT_BITS; 1.1.1.4 root 1655: register REGSET_ELT_TYPE bit 1656: = (REGSET_ELT_TYPE) 1 << (regno % REGSET_ELT_BITS); 1.1 root 1657: 1.1.1.4 root 1658: /* Don't delete insns to set global regs. */ 1.1 root 1659: if ((regno < FIRST_PSEUDO_REGISTER && global_regs[regno]) 1660: /* Make sure insns to set frame pointer aren't deleted. */ 1661: || regno == FRAME_POINTER_REGNUM 1.1.1.6 root 1662: #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM 1663: || regno == HARD_FRAME_POINTER_REGNUM 1664: #endif 1.1 root 1665: #if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM 1666: /* Make sure insns to set arg pointer are never deleted 1667: (if the arg pointer isn't fixed, there will be a USE for 1668: it, so we can treat it normally). */ 1669: || (regno == ARG_POINTER_REGNUM && fixed_regs[regno]) 1670: #endif 1671: || (needed[offset] & bit) != 0) 1672: return 0; 1673: 1674: /* If this is a hard register, verify that subsequent words are 1675: not needed. */ 1676: if (regno < FIRST_PSEUDO_REGISTER) 1677: { 1678: int n = HARD_REGNO_NREGS (regno, GET_MODE (r)); 1679: 1680: while (--n > 0) 1681: if ((needed[(regno + n) / REGSET_ELT_BITS] 1.1.1.4 root 1682: & ((REGSET_ELT_TYPE) 1 1683: << ((regno + n) % REGSET_ELT_BITS))) != 0) 1.1 root 1684: return 0; 1685: } 1686: 1687: return 1; 1688: } 1689: } 1690: /* If performing several activities, 1691: insn is dead if each activity is individually dead. 1692: Also, CLOBBERs and USEs can be ignored; a CLOBBER or USE 1693: that's inside a PARALLEL doesn't make the insn worth keeping. */ 1694: else if (code == PARALLEL) 1695: { 1696: register int i = XVECLEN (x, 0); 1697: for (i--; i >= 0; i--) 1698: { 1699: rtx elt = XVECEXP (x, 0, i); 1700: if (!insn_dead_p (elt, needed, call_ok) 1701: && GET_CODE (elt) != CLOBBER 1702: && GET_CODE (elt) != USE) 1703: return 0; 1704: } 1705: return 1; 1706: } 1707: /* We do not check CLOBBER or USE here. 1708: An insn consisting of just a CLOBBER or just a USE 1709: should not be deleted. */ 1710: return 0; 1711: } 1712: 1713: /* If X is the pattern of the last insn in a libcall, and assuming X is dead, 1714: return 1 if the entire library call is dead. 1715: This is true if X copies a register (hard or pseudo) 1716: and if the hard return reg of the call insn is dead. 1717: (The caller should have tested the destination of X already for death.) 1718: 1719: If this insn doesn't just copy a register, then we don't 1720: have an ordinary libcall. In that case, cse could not have 1721: managed to substitute the source for the dest later on, 1722: so we can assume the libcall is dead. 1723: 1724: NEEDED is the bit vector of pseudoregs live before this insn. 1725: NOTE is the REG_RETVAL note of the insn. INSN is the insn itself. */ 1726: 1727: static int 1728: libcall_dead_p (x, needed, note, insn) 1729: rtx x; 1730: regset needed; 1731: rtx note; 1732: rtx insn; 1733: { 1734: register RTX_CODE code = GET_CODE (x); 1735: 1736: if (code == SET) 1737: { 1738: register rtx r = SET_SRC (x); 1739: if (GET_CODE (r) == REG) 1740: { 1741: rtx call = XEXP (note, 0); 1742: register int i; 1743: 1744: /* Find the call insn. */ 1745: while (call != insn && GET_CODE (call) != CALL_INSN) 1746: call = NEXT_INSN (call); 1747: 1748: /* If there is none, do nothing special, 1749: since ordinary death handling can understand these insns. */ 1750: if (call == insn) 1751: return 0; 1752: 1753: /* See if the hard reg holding the value is dead. 1754: If this is a PARALLEL, find the call within it. */ 1755: call = PATTERN (call); 1756: if (GET_CODE (call) == PARALLEL) 1757: { 1758: for (i = XVECLEN (call, 0) - 1; i >= 0; i--) 1759: if (GET_CODE (XVECEXP (call, 0, i)) == SET 1760: && GET_CODE (SET_SRC (XVECEXP (call, 0, i))) == CALL) 1761: break; 1762: 1.1.1.7 ! root 1763: /* This may be a library call that is returning a value ! 1764: via invisible pointer. Do nothing special, since ! 1765: ordinary death handling can understand these insns. */ 1.1 root 1766: if (i < 0) 1.1.1.7 ! root 1767: return 0; 1.1 root 1768: 1769: call = XVECEXP (call, 0, i); 1770: } 1771: 1772: return insn_dead_p (call, needed, 1); 1773: } 1774: } 1775: return 1; 1776: } 1777: 1778: /* Return 1 if register REGNO was used before it was set. 1.1.1.4 root 1779: In other words, if it is live at function entry. 1780: Don't count global regster variables, though. */ 1.1 root 1781: 1782: int 1783: regno_uninitialized (regno) 1784: int regno; 1785: { 1.1.1.5 root 1786: if (n_basic_blocks == 0 1787: || (regno < FIRST_PSEUDO_REGISTER && global_regs[regno])) 1.1 root 1788: return 0; 1789: 1790: return (basic_block_live_at_start[0][regno / REGSET_ELT_BITS] 1.1.1.4 root 1791: & ((REGSET_ELT_TYPE) 1 << (regno % REGSET_ELT_BITS))); 1.1 root 1792: } 1793: 1794: /* 1 if register REGNO was alive at a place where `setjmp' was called 1795: and was set more than once or is an argument. 1796: Such regs may be clobbered by `longjmp'. */ 1797: 1798: int 1799: regno_clobbered_at_setjmp (regno) 1800: int regno; 1801: { 1802: if (n_basic_blocks == 0) 1803: return 0; 1804: 1805: return ((reg_n_sets[regno] > 1 1806: || (basic_block_live_at_start[0][regno / REGSET_ELT_BITS] 1.1.1.4 root 1807: & ((REGSET_ELT_TYPE) 1 << (regno % REGSET_ELT_BITS)))) 1.1 root 1808: && (regs_live_at_setjmp[regno / REGSET_ELT_BITS] 1.1.1.4 root 1809: & ((REGSET_ELT_TYPE) 1 << (regno % REGSET_ELT_BITS)))); 1.1 root 1810: } 1811: 1812: /* Process the registers that are set within X. 1813: Their bits are set to 1 in the regset DEAD, 1814: because they are dead prior to this insn. 1815: 1816: If INSN is nonzero, it is the insn being processed 1817: and the fact that it is nonzero implies this is the FINAL pass 1818: in propagate_block. In this case, various info about register 1819: usage is stored, LOG_LINKS fields of insns are set up. */ 1820: 1821: static void 1822: mark_set_regs (needed, dead, x, insn, significant) 1823: regset needed; 1824: regset dead; 1825: rtx x; 1826: rtx insn; 1827: regset significant; 1828: { 1829: register RTX_CODE code = GET_CODE (x); 1830: 1831: if (code == SET || code == CLOBBER) 1832: mark_set_1 (needed, dead, x, insn, significant); 1833: else if (code == PARALLEL) 1834: { 1835: register int i; 1836: for (i = XVECLEN (x, 0) - 1; i >= 0; i--) 1837: { 1838: code = GET_CODE (XVECEXP (x, 0, i)); 1839: if (code == SET || code == CLOBBER) 1840: mark_set_1 (needed, dead, XVECEXP (x, 0, i), insn, significant); 1841: } 1842: } 1843: } 1844: 1845: /* Process a single SET rtx, X. */ 1846: 1847: static void 1848: mark_set_1 (needed, dead, x, insn, significant) 1849: regset needed; 1850: regset dead; 1851: rtx x; 1852: rtx insn; 1853: regset significant; 1854: { 1855: register int regno; 1856: register rtx reg = SET_DEST (x); 1857: 1858: /* Modifying just one hardware register of a multi-reg value 1859: or just a byte field of a register 1860: does not mean the value from before this insn is now dead. 1861: But it does mean liveness of that register at the end of the block 1862: is significant. 1863: 1864: Within mark_set_1, however, we treat it as if the register is 1865: indeed modified. mark_used_regs will, however, also treat this 1866: register as being used. Thus, we treat these insns as setting a 1867: new value for the register as a function of its old value. This 1868: cases LOG_LINKS to be made appropriately and this will help combine. */ 1869: 1870: while (GET_CODE (reg) == SUBREG || GET_CODE (reg) == ZERO_EXTRACT 1871: || GET_CODE (reg) == SIGN_EXTRACT 1872: || GET_CODE (reg) == STRICT_LOW_PART) 1873: reg = XEXP (reg, 0); 1874: 1875: /* If we are writing into memory or into a register mentioned in the 1876: address of the last thing stored into memory, show we don't know 1877: what the last store was. If we are writing memory, save the address 1878: unless it is volatile. */ 1879: if (GET_CODE (reg) == MEM 1880: || (GET_CODE (reg) == REG 1881: && last_mem_set != 0 && reg_overlap_mentioned_p (reg, last_mem_set))) 1882: last_mem_set = 0; 1883: 1884: if (GET_CODE (reg) == MEM && ! side_effects_p (reg) 1885: /* There are no REG_INC notes for SP, so we can't assume we'll see 1886: everything that invalidates it. To be safe, don't eliminate any 1887: stores though SP; none of them should be redundant anyway. */ 1888: && ! reg_mentioned_p (stack_pointer_rtx, reg)) 1889: last_mem_set = reg; 1890: 1891: if (GET_CODE (reg) == REG 1892: && (regno = REGNO (reg), regno != FRAME_POINTER_REGNUM) 1.1.1.6 root 1893: #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM 1894: && regno != HARD_FRAME_POINTER_REGNUM 1895: #endif 1.1 root 1896: #if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM 1897: && ! (regno == ARG_POINTER_REGNUM && fixed_regs[regno]) 1898: #endif 1899: && ! (regno < FIRST_PSEUDO_REGISTER && global_regs[regno])) 1900: /* && regno != STACK_POINTER_REGNUM) -- let's try without this. */ 1901: { 1902: register int offset = regno / REGSET_ELT_BITS; 1.1.1.4 root 1903: register REGSET_ELT_TYPE bit 1904: = (REGSET_ELT_TYPE) 1 << (regno % REGSET_ELT_BITS); 1905: REGSET_ELT_TYPE all_needed = (needed[offset] & bit); 1906: REGSET_ELT_TYPE some_needed = (needed[offset] & bit); 1.1 root 1907: 1908: /* Mark it as a significant register for this basic block. */ 1909: if (significant) 1910: significant[offset] |= bit; 1911: 1912: /* Mark it as as dead before this insn. */ 1913: dead[offset] |= bit; 1914: 1915: /* A hard reg in a wide mode may really be multiple registers. 1916: If so, mark all of them just like the first. */ 1917: if (regno < FIRST_PSEUDO_REGISTER) 1918: { 1919: int n; 1920: 1921: /* Nothing below is needed for the stack pointer; get out asap. 1922: Eg, log links aren't needed, since combine won't use them. */ 1923: if (regno == STACK_POINTER_REGNUM) 1924: return; 1925: 1926: n = HARD_REGNO_NREGS (regno, GET_MODE (reg)); 1927: while (--n > 0) 1928: { 1929: if (significant) 1930: significant[(regno + n) / REGSET_ELT_BITS] 1.1.1.4 root 1931: |= (REGSET_ELT_TYPE) 1 << ((regno + n) % REGSET_ELT_BITS); 1.1 root 1932: dead[(regno + n) / REGSET_ELT_BITS] 1.1.1.4 root 1933: |= (REGSET_ELT_TYPE) 1 << ((regno + n) % REGSET_ELT_BITS); 1934: some_needed 1935: |= (needed[(regno + n) / REGSET_ELT_BITS] 1936: & (REGSET_ELT_TYPE) 1 << ((regno + n) % REGSET_ELT_BITS)); 1937: all_needed 1938: &= (needed[(regno + n) / REGSET_ELT_BITS] 1939: & (REGSET_ELT_TYPE) 1 << ((regno + n) % REGSET_ELT_BITS)); 1.1 root 1940: } 1941: } 1942: /* Additional data to record if this is the final pass. */ 1943: if (insn) 1944: { 1945: register rtx y = reg_next_use[regno]; 1946: register int blocknum = BLOCK_NUM (insn); 1947: 1.1.1.5 root 1948: /* The next use is no longer "next", since a store intervenes. */ 1949: reg_next_use[regno] = 0; 1950: 1.1 root 1951: /* If this is a hard reg, record this function uses the reg. */ 1952: 1953: if (regno < FIRST_PSEUDO_REGISTER) 1954: { 1955: register int i; 1956: int endregno = regno + HARD_REGNO_NREGS (regno, GET_MODE (reg)); 1957: 1958: for (i = regno; i < endregno; i++) 1959: { 1960: regs_ever_live[i] = 1; 1961: reg_n_sets[i]++; 1962: } 1963: } 1964: else 1965: { 1966: /* Keep track of which basic blocks each reg appears in. */ 1967: 1968: if (reg_basic_block[regno] == REG_BLOCK_UNKNOWN) 1969: reg_basic_block[regno] = blocknum; 1970: else if (reg_basic_block[regno] != blocknum) 1971: reg_basic_block[regno] = REG_BLOCK_GLOBAL; 1972: 1973: /* Count (weighted) references, stores, etc. This counts a 1974: register twice if it is modified, but that is correct. */ 1975: reg_n_sets[regno]++; 1976: 1977: reg_n_refs[regno] += loop_depth; 1978: 1979: /* The insns where a reg is live are normally counted 1980: elsewhere, but we want the count to include the insn 1981: where the reg is set, and the normal counting mechanism 1982: would not count it. */ 1983: reg_live_length[regno]++; 1984: } 1985: 1986: if (all_needed) 1987: { 1988: /* Make a logical link from the next following insn 1989: that uses this register, back to this insn. 1990: The following insns have already been processed. 1991: 1992: We don't build a LOG_LINK for hard registers containing 1993: in ASM_OPERANDs. If these registers get replaced, 1994: we might wind up changing the semantics of the insn, 1995: even if reload can make what appear to be valid assignments 1996: later. */ 1997: if (y && (BLOCK_NUM (y) == blocknum) 1998: && (regno >= FIRST_PSEUDO_REGISTER 1999: || asm_noperands (PATTERN (y)) < 0)) 2000: LOG_LINKS (y) 2001: = gen_rtx (INSN_LIST, VOIDmode, insn, LOG_LINKS (y)); 2002: } 2003: else if (! some_needed) 2004: { 2005: /* Note that dead stores have already been deleted when possible 2006: If we get here, we have found a dead store that cannot 2007: be eliminated (because the same insn does something useful). 2008: Indicate this by marking the reg being set as dying here. */ 2009: REG_NOTES (insn) 2010: = gen_rtx (EXPR_LIST, REG_UNUSED, reg, REG_NOTES (insn)); 2011: reg_n_deaths[REGNO (reg)]++; 2012: } 2013: else 2014: { 2015: /* This is a case where we have a multi-word hard register 2016: and some, but not all, of the words of the register are 2017: needed in subsequent insns. Write REG_UNUSED notes 2018: for those parts that were not needed. This case should 2019: be rare. */ 2020: 2021: int i; 2022: 2023: for (i = HARD_REGNO_NREGS (regno, GET_MODE (reg)) - 1; 2024: i >= 0; i--) 2025: if ((needed[(regno + i) / REGSET_ELT_BITS] 1.1.1.4 root 2026: & ((REGSET_ELT_TYPE) 1 2027: << ((regno + i) % REGSET_ELT_BITS))) == 0) 1.1 root 2028: REG_NOTES (insn) 2029: = gen_rtx (EXPR_LIST, REG_UNUSED, 1.1.1.7 ! root 2030: gen_rtx (REG, reg_raw_mode[regno + i], ! 2031: regno + i), 1.1 root 2032: REG_NOTES (insn)); 2033: } 2034: } 2035: } 1.1.1.5 root 2036: else if (GET_CODE (reg) == REG) 2037: reg_next_use[regno] = 0; 1.1 root 2038: 2039: /* If this is the last pass and this is a SCRATCH, show it will be dying 2040: here and count it. */ 2041: else if (GET_CODE (reg) == SCRATCH && insn != 0) 2042: { 2043: REG_NOTES (insn) 2044: = gen_rtx (EXPR_LIST, REG_UNUSED, reg, REG_NOTES (insn)); 2045: num_scratch++; 2046: } 2047: } 2048: 2049: #ifdef AUTO_INC_DEC 2050: 2051: /* X is a MEM found in INSN. See if we can convert it into an auto-increment 2052: reference. */ 2053: 2054: static void 2055: find_auto_inc (needed, x, insn) 2056: regset needed; 2057: rtx x; 2058: rtx insn; 2059: { 2060: rtx addr = XEXP (x, 0); 1.1.1.7 ! root 2061: HOST_WIDE_INT offset = 0; ! 2062: rtx set; 1.1 root 2063: 2064: /* Here we detect use of an index register which might be good for 2065: postincrement, postdecrement, preincrement, or predecrement. */ 2066: 2067: if (GET_CODE (addr) == PLUS && GET_CODE (XEXP (addr, 1)) == CONST_INT) 2068: offset = INTVAL (XEXP (addr, 1)), addr = XEXP (addr, 0); 2069: 2070: if (GET_CODE (addr) == REG) 2071: { 2072: register rtx y; 2073: register int size = GET_MODE_SIZE (GET_MODE (x)); 2074: rtx use; 2075: rtx incr; 2076: int regno = REGNO (addr); 2077: 2078: /* Is the next use an increment that might make auto-increment? */ 1.1.1.7 ! root 2079: if ((incr = reg_next_use[regno]) != 0 ! 2080: && (set = single_set (incr)) != 0 ! 2081: && GET_CODE (set) == SET 1.1 root 2082: && BLOCK_NUM (incr) == BLOCK_NUM (insn) 2083: /* Can't add side effects to jumps; if reg is spilled and 2084: reloaded, there's no way to store back the altered value. */ 2085: && GET_CODE (insn) != JUMP_INSN 1.1.1.7 ! root 2086: && (y = SET_SRC (set), GET_CODE (y) == PLUS) 1.1 root 2087: && XEXP (y, 0) == addr 2088: && GET_CODE (XEXP (y, 1)) == CONST_INT 2089: && (0 2090: #ifdef HAVE_POST_INCREMENT 2091: || (INTVAL (XEXP (y, 1)) == size && offset == 0) 2092: #endif 2093: #ifdef HAVE_POST_DECREMENT 2094: || (INTVAL (XEXP (y, 1)) == - size && offset == 0) 2095: #endif 2096: #ifdef HAVE_PRE_INCREMENT 2097: || (INTVAL (XEXP (y, 1)) == size && offset == size) 2098: #endif 2099: #ifdef HAVE_PRE_DECREMENT 2100: || (INTVAL (XEXP (y, 1)) == - size && offset == - size) 2101: #endif 2102: ) 2103: /* Make sure this reg appears only once in this insn. */ 2104: && (use = find_use_as_address (PATTERN (insn), addr, offset), 2105: use != 0 && use != (rtx) 1)) 2106: { 1.1.1.7 ! root 2107: rtx q = SET_DEST (set); ! 2108: enum rtx_code inc_code = (INTVAL (XEXP (y, 1)) == size ! 2109: ? (offset ? PRE_INC : POST_INC) ! 2110: : (offset ? PRE_DEC : POST_DEC)); 1.1 root 2111: 2112: if (dead_or_set_p (incr, addr)) 1.1.1.7 ! root 2113: { ! 2114: /* This is the simple case. Try to make the auto-inc. If ! 2115: we can't, we are done. Otherwise, we will do any ! 2116: needed updates below. */ ! 2117: if (! validate_change (insn, &XEXP (x, 0), ! 2118: gen_rtx (inc_code, Pmode, addr), ! 2119: 0)) ! 2120: return; ! 2121: } 1.1.1.6 root 2122: else if (GET_CODE (q) == REG 2123: /* PREV_INSN used here to check the semi-open interval 2124: [insn,incr). */ 2125: && ! reg_used_between_p (q, PREV_INSN (insn), incr)) 1.1 root 2126: { 1.1.1.6 root 2127: /* We have *p followed sometime later by q = p+size. 1.1 root 2128: Both p and q must be live afterward, 1.1.1.6 root 2129: and q is not used between INSN and it's assignment. 1.1 root 2130: Change it to q = p, ...*q..., q = q+size. 2131: Then fall into the usual case. */ 2132: rtx insns, temp; 2133: 2134: start_sequence (); 2135: emit_move_insn (q, addr); 2136: insns = get_insns (); 2137: end_sequence (); 2138: 2139: /* If anything in INSNS have UID's that don't fit within the 2140: extra space we allocate earlier, we can't make this auto-inc. 2141: This should never happen. */ 2142: for (temp = insns; temp; temp = NEXT_INSN (temp)) 2143: { 2144: if (INSN_UID (temp) > max_uid_for_flow) 2145: return; 2146: BLOCK_NUM (temp) = BLOCK_NUM (insn); 2147: } 2148: 1.1.1.7 ! root 2149: /* If we can't make the auto-inc, or can't make the ! 2150: replacement into Y, exit. There's no point in making ! 2151: the change below if we can't do the auto-inc and doing ! 2152: so is not correct in the pre-inc case. */ ! 2153: ! 2154: validate_change (insn, &XEXP (x, 0), ! 2155: gen_rtx (inc_code, Pmode, q), ! 2156: 1); ! 2157: validate_change (incr, &XEXP (y, 0), q, 1); ! 2158: if (! apply_change_group ()) ! 2159: return; ! 2160: ! 2161: /* We now know we'll be doing this change, so emit the ! 2162: new insn(s) and do the updates. */ 1.1 root 2163: emit_insns_before (insns, insn); 2164: 2165: if (basic_block_head[BLOCK_NUM (insn)] == insn) 2166: basic_block_head[BLOCK_NUM (insn)] = insns; 2167: 2168: /* INCR will become a NOTE and INSN won't contain a 2169: use of ADDR. If a use of ADDR was just placed in 2170: the insn before INSN, make that the next use. 2171: Otherwise, invalidate it. */ 2172: if (GET_CODE (PREV_INSN (insn)) == INSN 2173: && GET_CODE (PATTERN (PREV_INSN (insn))) == SET 2174: && SET_SRC (PATTERN (PREV_INSN (insn))) == addr) 2175: reg_next_use[regno] = PREV_INSN (insn); 2176: else 2177: reg_next_use[regno] = 0; 2178: 2179: addr = q; 2180: regno = REGNO (q); 2181: 2182: /* REGNO is now used in INCR which is below INSN, but 2183: it previously wasn't live here. If we don't mark 2184: it as needed, we'll put a REG_DEAD note for it 2185: on this insn, which is incorrect. */ 2186: needed[regno / REGSET_ELT_BITS] 1.1.1.4 root 2187: |= (REGSET_ELT_TYPE) 1 << (regno % REGSET_ELT_BITS); 1.1 root 2188: 2189: /* If there are any calls between INSN and INCR, show 2190: that REGNO now crosses them. */ 2191: for (temp = insn; temp != incr; temp = NEXT_INSN (temp)) 2192: if (GET_CODE (temp) == CALL_INSN) 2193: reg_n_calls_crossed[regno]++; 2194: } 1.1.1.7 ! root 2195: else ! 2196: return; 1.1 root 2197: 1.1.1.7 ! root 2198: /* If we haven't returned, it means we were able to make the ! 2199: auto-inc, so update the status. First, record that this insn ! 2200: has an implicit side effect. */ 1.1 root 2201: 1.1.1.7 ! root 2202: REG_NOTES (insn) ! 2203: = gen_rtx (EXPR_LIST, REG_INC, addr, REG_NOTES (insn)); 1.1 root 2204: 1.1.1.7 ! root 2205: /* Modify the old increment-insn to simply copy ! 2206: the already-incremented value of our register. */ ! 2207: if (! validate_change (incr, &SET_SRC (set), addr, 0)) ! 2208: abort (); 1.1 root 2209: 1.1.1.7 ! root 2210: /* If that makes it a no-op (copying the register into itself) delete ! 2211: it so it won't appear to be a "use" and a "set" of this ! 2212: register. */ ! 2213: if (SET_DEST (set) == addr) ! 2214: { ! 2215: PUT_CODE (incr, NOTE); ! 2216: NOTE_LINE_NUMBER (incr) = NOTE_INSN_DELETED; ! 2217: NOTE_SOURCE_FILE (incr) = 0; ! 2218: } ! 2219: ! 2220: if (regno >= FIRST_PSEUDO_REGISTER) ! 2221: { ! 2222: /* Count an extra reference to the reg. When a reg is ! 2223: incremented, spilling it is worse, so we want to make ! 2224: that less likely. */ ! 2225: reg_n_refs[regno] += loop_depth; ! 2226: ! 2227: /* Count the increment as a setting of the register, ! 2228: even though it isn't a SET in rtl. */ ! 2229: reg_n_sets[regno]++; 1.1 root 2230: } 2231: } 2232: } 2233: } 2234: #endif /* AUTO_INC_DEC */ 2235: 2236: /* Scan expression X and store a 1-bit in LIVE for each reg it uses. 2237: This is done assuming the registers needed from X 2238: are those that have 1-bits in NEEDED. 2239: 2240: On the final pass, FINAL is 1. This means try for autoincrement 2241: and count the uses and deaths of each pseudo-reg. 2242: 2243: INSN is the containing instruction. If INSN is dead, this function is not 2244: called. */ 2245: 2246: static void 2247: mark_used_regs (needed, live, x, final, insn) 2248: regset needed; 2249: regset live; 2250: rtx x; 2251: int final; 1.1.1.7 ! root 2252: rtx insn; 1.1 root 2253: { 2254: register RTX_CODE code; 2255: register int regno; 2256: int i; 2257: 2258: retry: 2259: code = GET_CODE (x); 2260: switch (code) 2261: { 2262: case LABEL_REF: 2263: case SYMBOL_REF: 2264: case CONST_INT: 2265: case CONST: 2266: case CONST_DOUBLE: 2267: case PC: 2268: case ADDR_VEC: 2269: case ADDR_DIFF_VEC: 2270: case ASM_INPUT: 2271: return; 2272: 2273: #ifdef HAVE_cc0 2274: case CC0: 2275: cc0_live = 1; 2276: return; 2277: #endif 2278: 1.1.1.6 root 2279: case CLOBBER: 2280: /* If we are clobbering a MEM, mark any registers inside the address 2281: as being used. */ 2282: if (GET_CODE (XEXP (x, 0)) == MEM) 2283: mark_used_regs (needed, live, XEXP (XEXP (x, 0), 0), final, insn); 2284: return; 2285: 1.1 root 2286: case MEM: 2287: /* Invalidate the data for the last MEM stored. We could do this only 2288: if the addresses conflict, but this doesn't seem worthwhile. */ 2289: last_mem_set = 0; 2290: 2291: #ifdef AUTO_INC_DEC 2292: if (final) 2293: find_auto_inc (needed, x, insn); 2294: #endif 2295: break; 2296: 1.1.1.7 ! root 2297: case SUBREG: ! 2298: if (GET_CODE (SUBREG_REG (x)) == REG ! 2299: && REGNO (SUBREG_REG (x)) >= FIRST_PSEUDO_REGISTER ! 2300: && (GET_MODE_SIZE (GET_MODE (x)) ! 2301: != GET_MODE_SIZE (GET_MODE (SUBREG_REG (x)))) ! 2302: && (INTEGRAL_MODE_P (GET_MODE (x)) ! 2303: || INTEGRAL_MODE_P (GET_MODE (SUBREG_REG (x))))) ! 2304: reg_changes_size[REGNO (SUBREG_REG (x))] = 1; ! 2305: ! 2306: /* While we're here, optimize this case. */ ! 2307: x = SUBREG_REG (x); ! 2308: ! 2309: /* ... fall through ... */ ! 2310: 1.1 root 2311: case REG: 2312: /* See a register other than being set 2313: => mark it as needed. */ 2314: 2315: regno = REGNO (x); 2316: { 2317: register int offset = regno / REGSET_ELT_BITS; 1.1.1.4 root 2318: register REGSET_ELT_TYPE bit 2319: = (REGSET_ELT_TYPE) 1 << (regno % REGSET_ELT_BITS); 1.1.1.5 root 2320: REGSET_ELT_TYPE all_needed = needed[offset] & bit; 2321: REGSET_ELT_TYPE some_needed = needed[offset] & bit; 1.1 root 2322: 2323: live[offset] |= bit; 2324: /* A hard reg in a wide mode may really be multiple registers. 2325: If so, mark all of them just like the first. */ 2326: if (regno < FIRST_PSEUDO_REGISTER) 2327: { 2328: int n; 2329: 2330: /* For stack ptr or fixed arg pointer, 2331: nothing below can be necessary, so waste no more time. */ 2332: if (regno == STACK_POINTER_REGNUM 1.1.1.6 root 2333: #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM 2334: || regno == HARD_FRAME_POINTER_REGNUM 2335: #endif 1.1 root 2336: #if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM 2337: || (regno == ARG_POINTER_REGNUM && fixed_regs[regno]) 2338: #endif 2339: || regno == FRAME_POINTER_REGNUM) 2340: { 2341: /* If this is a register we are going to try to eliminate, 2342: don't mark it live here. If we are successful in 2343: eliminating it, it need not be live unless it is used for 2344: pseudos, in which case it will have been set live when 2345: it was allocated to the pseudos. If the register will not 2346: be eliminated, reload will set it live at that point. */ 2347: 2348: if (! TEST_HARD_REG_BIT (elim_reg_set, regno)) 2349: regs_ever_live[regno] = 1; 2350: return; 2351: } 2352: /* No death notes for global register variables; 2353: their values are live after this function exits. */ 2354: if (global_regs[regno]) 1.1.1.4 root 2355: { 2356: if (final) 2357: reg_next_use[regno] = insn; 2358: return; 2359: } 1.1 root 2360: 2361: n = HARD_REGNO_NREGS (regno, GET_MODE (x)); 2362: while (--n > 0) 2363: { 2364: live[(regno + n) / REGSET_ELT_BITS] 1.1.1.4 root 2365: |= (REGSET_ELT_TYPE) 1 << ((regno + n) % REGSET_ELT_BITS); 2366: some_needed 2367: |= (needed[(regno + n) / REGSET_ELT_BITS] 2368: & (REGSET_ELT_TYPE) 1 << ((regno + n) % REGSET_ELT_BITS)); 2369: all_needed 2370: &= (needed[(regno + n) / REGSET_ELT_BITS] 2371: & (REGSET_ELT_TYPE) 1 << ((regno + n) % REGSET_ELT_BITS)); 1.1 root 2372: } 2373: } 2374: if (final) 2375: { 2376: /* Record where each reg is used, so when the reg 2377: is set we know the next insn that uses it. */ 2378: 2379: reg_next_use[regno] = insn; 2380: 2381: if (regno < FIRST_PSEUDO_REGISTER) 2382: { 2383: /* If a hard reg is being used, 2384: record that this function does use it. */ 2385: 2386: i = HARD_REGNO_NREGS (regno, GET_MODE (x)); 2387: if (i == 0) 2388: i = 1; 2389: do 2390: regs_ever_live[regno + --i] = 1; 2391: while (i > 0); 2392: } 2393: else 2394: { 2395: /* Keep track of which basic block each reg appears in. */ 2396: 2397: register int blocknum = BLOCK_NUM (insn); 2398: 2399: if (reg_basic_block[regno] == REG_BLOCK_UNKNOWN) 2400: reg_basic_block[regno] = blocknum; 2401: else if (reg_basic_block[regno] != blocknum) 2402: reg_basic_block[regno] = REG_BLOCK_GLOBAL; 2403: 2404: /* Count (weighted) number of uses of each reg. */ 2405: 2406: reg_n_refs[regno] += loop_depth; 2407: } 2408: 2409: /* Record and count the insns in which a reg dies. 2410: If it is used in this insn and was dead below the insn 2411: then it dies in this insn. If it was set in this insn, 2412: we do not make a REG_DEAD note; likewise if we already 2413: made such a note. */ 2414: 2415: if (! all_needed 2416: && ! dead_or_set_p (insn, x) 2417: #if 0 2418: && (regno >= FIRST_PSEUDO_REGISTER || ! fixed_regs[regno]) 2419: #endif 2420: ) 2421: { 1.1.1.7 ! root 2422: /* Check for the case where the register dying partially ! 2423: overlaps the register set by this insn. */ ! 2424: if (regno < FIRST_PSEUDO_REGISTER ! 2425: && HARD_REGNO_NREGS (regno, GET_MODE (x)) > 1) ! 2426: { ! 2427: int n = HARD_REGNO_NREGS (regno, GET_MODE (x)); ! 2428: while (--n >= 0) ! 2429: some_needed |= dead_or_set_regno_p (insn, regno + n); ! 2430: } ! 2431: 1.1 root 2432: /* If none of the words in X is needed, make a REG_DEAD 2433: note. Otherwise, we must make partial REG_DEAD notes. */ 2434: if (! some_needed) 2435: { 2436: REG_NOTES (insn) 2437: = gen_rtx (EXPR_LIST, REG_DEAD, x, REG_NOTES (insn)); 2438: reg_n_deaths[regno]++; 2439: } 2440: else 2441: { 2442: int i; 2443: 2444: /* Don't make a REG_DEAD note for a part of a register 2445: that is set in the insn. */ 2446: 2447: for (i = HARD_REGNO_NREGS (regno, GET_MODE (x)) - 1; 2448: i >= 0; i--) 2449: if ((needed[(regno + i) / REGSET_ELT_BITS] 1.1.1.4 root 2450: & ((REGSET_ELT_TYPE) 1 2451: << ((regno + i) % REGSET_ELT_BITS))) == 0 1.1 root 2452: && ! dead_or_set_regno_p (insn, regno + i)) 2453: REG_NOTES (insn) 2454: = gen_rtx (EXPR_LIST, REG_DEAD, 1.1.1.7 ! root 2455: gen_rtx (REG, reg_raw_mode[regno + i], ! 2456: regno + i), 1.1 root 2457: REG_NOTES (insn)); 2458: } 2459: } 2460: } 2461: } 2462: return; 2463: 2464: case SET: 2465: { 2466: register rtx testreg = SET_DEST (x); 2467: int mark_dest = 0; 2468: 2469: /* If storing into MEM, don't show it as being used. But do 2470: show the address as being used. */ 2471: if (GET_CODE (testreg) == MEM) 2472: { 2473: #ifdef AUTO_INC_DEC 2474: if (final) 2475: find_auto_inc (needed, testreg, insn); 2476: #endif 2477: mark_used_regs (needed, live, XEXP (testreg, 0), final, insn); 2478: mark_used_regs (needed, live, SET_SRC (x), final, insn); 2479: return; 2480: } 2481: 2482: /* Storing in STRICT_LOW_PART is like storing in a reg 2483: in that this SET might be dead, so ignore it in TESTREG. 2484: but in some other ways it is like using the reg. 2485: 2486: Storing in a SUBREG or a bit field is like storing the entire 2487: register in that if the register's value is not used 2488: then this SET is not needed. */ 2489: while (GET_CODE (testreg) == STRICT_LOW_PART 2490: || GET_CODE (testreg) == ZERO_EXTRACT 2491: || GET_CODE (testreg) == SIGN_EXTRACT 2492: || GET_CODE (testreg) == SUBREG) 2493: { 2494: /* Modifying a single register in an alternate mode 2495: does not use any of the old value. But these other 2496: ways of storing in a register do use the old value. */ 2497: if (GET_CODE (testreg) == SUBREG 2498: && !(REG_SIZE (SUBREG_REG (testreg)) > REG_SIZE (testreg))) 2499: ; 2500: else 2501: mark_dest = 1; 2502: 2503: testreg = XEXP (testreg, 0); 2504: } 2505: 2506: /* If this is a store into a register, 2507: recursively scan the value being stored. */ 2508: 2509: if (GET_CODE (testreg) == REG 2510: && (regno = REGNO (testreg), regno != FRAME_POINTER_REGNUM) 1.1.1.6 root 2511: #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM 2512: && regno != HARD_FRAME_POINTER_REGNUM 2513: #endif 1.1 root 2514: #if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM 2515: && ! (regno == ARG_POINTER_REGNUM && fixed_regs[regno]) 2516: #endif 1.1.1.4 root 2517: ) 2518: /* We used to exclude global_regs here, but that seems wrong. 2519: Storing in them is like storing in mem. */ 1.1 root 2520: { 2521: mark_used_regs (needed, live, SET_SRC (x), final, insn); 2522: if (mark_dest) 2523: mark_used_regs (needed, live, SET_DEST (x), final, insn); 2524: return; 2525: } 2526: } 2527: break; 2528: 2529: case RETURN: 2530: /* If exiting needs the right stack value, consider this insn as 2531: using the stack pointer. In any event, consider it as using 2532: all global registers. */ 2533: 2534: #ifdef EXIT_IGNORE_STACK 2535: if (! EXIT_IGNORE_STACK 2536: || (! FRAME_POINTER_REQUIRED && flag_omit_frame_pointer)) 2537: #endif 2538: live[STACK_POINTER_REGNUM / REGSET_ELT_BITS] 1.1.1.4 root 2539: |= (REGSET_ELT_TYPE) 1 << (STACK_POINTER_REGNUM % REGSET_ELT_BITS); 1.1 root 2540: 2541: for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) 2542: if (global_regs[i]) 1.1.1.4 root 2543: live[i / REGSET_ELT_BITS] 2544: |= (REGSET_ELT_TYPE) 1 << (i % REGSET_ELT_BITS); 1.1 root 2545: break; 2546: } 2547: 2548: /* Recursively scan the operands of this expression. */ 2549: 2550: { 2551: register char *fmt = GET_RTX_FORMAT (code); 2552: register int i; 2553: 2554: for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) 2555: { 2556: if (fmt[i] == 'e') 2557: { 2558: /* Tail recursive case: save a function call level. */ 2559: if (i == 0) 2560: { 2561: x = XEXP (x, 0); 2562: goto retry; 2563: } 2564: mark_used_regs (needed, live, XEXP (x, i), final, insn); 2565: } 2566: else if (fmt[i] == 'E') 2567: { 2568: register int j; 2569: for (j = 0; j < XVECLEN (x, i); j++) 2570: mark_used_regs (needed, live, XVECEXP (x, i, j), final, insn); 2571: } 2572: } 2573: } 2574: } 2575: 2576: #ifdef AUTO_INC_DEC 2577: 2578: static int 2579: try_pre_increment_1 (insn) 2580: rtx insn; 2581: { 2582: /* Find the next use of this reg. If in same basic block, 2583: make it do pre-increment or pre-decrement if appropriate. */ 2584: rtx x = PATTERN (insn); 1.1.1.4 root 2585: HOST_WIDE_INT amount = ((GET_CODE (SET_SRC (x)) == PLUS ? 1 : -1) 1.1 root 2586: * INTVAL (XEXP (SET_SRC (x), 1))); 2587: int regno = REGNO (SET_DEST (x)); 2588: rtx y = reg_next_use[regno]; 2589: if (y != 0 2590: && BLOCK_NUM (y) == BLOCK_NUM (insn) 1.1.1.7 ! root 2591: /* Don't do this if the reg dies, or gets set in y; a standard addressing ! 2592: mode would be better. */ ! 2593: && ! dead_or_set_p (y, SET_DEST (x)) 1.1 root 2594: && try_pre_increment (y, SET_DEST (PATTERN (insn)), 2595: amount)) 2596: { 2597: /* We have found a suitable auto-increment 2598: and already changed insn Y to do it. 2599: So flush this increment-instruction. */ 2600: PUT_CODE (insn, NOTE); 2601: NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED; 2602: NOTE_SOURCE_FILE (insn) = 0; 2603: /* Count a reference to this reg for the increment 2604: insn we are deleting. When a reg is incremented. 2605: spilling it is worse, so we want to make that 2606: less likely. */ 2607: if (regno >= FIRST_PSEUDO_REGISTER) 2608: { 2609: reg_n_refs[regno] += loop_depth; 2610: reg_n_sets[regno]++; 2611: } 2612: return 1; 2613: } 2614: return 0; 2615: } 2616: 2617: /* Try to change INSN so that it does pre-increment or pre-decrement 2618: addressing on register REG in order to add AMOUNT to REG. 2619: AMOUNT is negative for pre-decrement. 2620: Returns 1 if the change could be made. 2621: This checks all about the validity of the result of modifying INSN. */ 2622: 2623: static int 2624: try_pre_increment (insn, reg, amount) 2625: rtx insn, reg; 1.1.1.4 root 2626: HOST_WIDE_INT amount; 1.1 root 2627: { 2628: register rtx use; 2629: 2630: /* Nonzero if we can try to make a pre-increment or pre-decrement. 2631: For example, addl $4,r1; movl (r1),... can become movl +(r1),... */ 2632: int pre_ok = 0; 2633: /* Nonzero if we can try to make a post-increment or post-decrement. 2634: For example, addl $4,r1; movl -4(r1),... can become movl (r1)+,... 2635: It is possible for both PRE_OK and POST_OK to be nonzero if the machine 2636: supports both pre-inc and post-inc, or both pre-dec and post-dec. */ 2637: int post_ok = 0; 2638: 2639: /* Nonzero if the opportunity actually requires post-inc or post-dec. */ 2640: int do_post = 0; 2641: 2642: /* From the sign of increment, see which possibilities are conceivable 2643: on this target machine. */ 2644: #ifdef HAVE_PRE_INCREMENT 2645: if (amount > 0) 2646: pre_ok = 1; 2647: #endif 2648: #ifdef HAVE_POST_INCREMENT 2649: if (amount > 0) 2650: post_ok = 1; 2651: #endif 2652: 2653: #ifdef HAVE_PRE_DECREMENT 2654: if (amount < 0) 2655: pre_ok = 1; 2656: #endif 2657: #ifdef HAVE_POST_DECREMENT 2658: if (amount < 0) 2659: post_ok = 1; 2660: #endif 2661: 2662: if (! (pre_ok || post_ok)) 2663: return 0; 2664: 2665: /* It is not safe to add a side effect to a jump insn 2666: because if the incremented register is spilled and must be reloaded 2667: there would be no way to store the incremented value back in memory. */ 2668: 2669: if (GET_CODE (insn) == JUMP_INSN) 2670: return 0; 2671: 2672: use = 0; 2673: if (pre_ok) 2674: use = find_use_as_address (PATTERN (insn), reg, 0); 2675: if (post_ok && (use == 0 || use == (rtx) 1)) 2676: { 2677: use = find_use_as_address (PATTERN (insn), reg, -amount); 2678: do_post = 1; 2679: } 2680: 2681: if (use == 0 || use == (rtx) 1) 2682: return 0; 2683: 2684: if (GET_MODE_SIZE (GET_MODE (use)) != (amount > 0 ? amount : - amount)) 2685: return 0; 2686: 1.1.1.7 ! root 2687: /* See if this combination of instruction and addressing mode exists. */ ! 2688: if (! validate_change (insn, &XEXP (use, 0), ! 2689: gen_rtx (amount > 0 ! 2690: ? (do_post ? POST_INC : PRE_INC) ! 2691: : (do_post ? POST_DEC : PRE_DEC), ! 2692: Pmode, reg), 0)) ! 2693: return 0; 1.1 root 2694: 2695: /* Record that this insn now has an implicit side effect on X. */ 2696: REG_NOTES (insn) = gen_rtx (EXPR_LIST, REG_INC, reg, REG_NOTES (insn)); 2697: return 1; 2698: } 2699: 2700: #endif /* AUTO_INC_DEC */ 2701: 2702: /* Find the place in the rtx X where REG is used as a memory address. 2703: Return the MEM rtx that so uses it. 2704: If PLUSCONST is nonzero, search instead for a memory address equivalent to 2705: (plus REG (const_int PLUSCONST)). 2706: 2707: If such an address does not appear, return 0. 2708: If REG appears more than once, or is used other than in such an address, 2709: return (rtx)1. */ 2710: 2711: static rtx 2712: find_use_as_address (x, reg, plusconst) 2713: register rtx x; 2714: rtx reg; 1.1.1.7 ! root 2715: HOST_WIDE_INT plusconst; 1.1 root 2716: { 2717: enum rtx_code code = GET_CODE (x); 2718: char *fmt = GET_RTX_FORMAT (code); 2719: register int i; 2720: register rtx value = 0; 2721: register rtx tem; 2722: 2723: if (code == MEM && XEXP (x, 0) == reg && plusconst == 0) 2724: return x; 2725: 2726: if (code == MEM && GET_CODE (XEXP (x, 0)) == PLUS 2727: && XEXP (XEXP (x, 0), 0) == reg 2728: && GET_CODE (XEXP (XEXP (x, 0), 1)) == CONST_INT 2729: && INTVAL (XEXP (XEXP (x, 0), 1)) == plusconst) 2730: return x; 2731: 2732: if (code == SIGN_EXTRACT || code == ZERO_EXTRACT) 2733: { 2734: /* If REG occurs inside a MEM used in a bit-field reference, 2735: that is unacceptable. */ 2736: if (find_use_as_address (XEXP (x, 0), reg, 0) != 0) 1.1.1.4 root 2737: return (rtx) (HOST_WIDE_INT) 1; 1.1 root 2738: } 2739: 2740: if (x == reg) 1.1.1.4 root 2741: return (rtx) (HOST_WIDE_INT) 1; 1.1 root 2742: 2743: for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) 2744: { 2745: if (fmt[i] == 'e') 2746: { 2747: tem = find_use_as_address (XEXP (x, i), reg, plusconst); 2748: if (value == 0) 2749: value = tem; 2750: else if (tem != 0) 1.1.1.4 root 2751: return (rtx) (HOST_WIDE_INT) 1; 1.1 root 2752: } 2753: if (fmt[i] == 'E') 2754: { 2755: register int j; 2756: for (j = XVECLEN (x, i) - 1; j >= 0; j--) 2757: { 2758: tem = find_use_as_address (XVECEXP (x, i, j), reg, plusconst); 2759: if (value == 0) 2760: value = tem; 2761: else if (tem != 0) 1.1.1.4 root 2762: return (rtx) (HOST_WIDE_INT) 1; 1.1 root 2763: } 2764: } 2765: } 2766: 2767: return value; 2768: } 2769: 2770: /* Write information about registers and basic blocks into FILE. 2771: This is part of making a debugging dump. */ 2772: 2773: void 2774: dump_flow_info (file) 2775: FILE *file; 2776: { 2777: register int i; 2778: static char *reg_class_names[] = REG_CLASS_NAMES; 2779: 2780: fprintf (file, "%d registers.\n", max_regno); 2781: 2782: for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++) 2783: if (reg_n_refs[i]) 2784: { 1.1.1.4 root 2785: enum reg_class class, altclass; 1.1 root 2786: fprintf (file, "\nRegister %d used %d times across %d insns", 2787: i, reg_n_refs[i], reg_live_length[i]); 2788: if (reg_basic_block[i] >= 0) 2789: fprintf (file, " in block %d", reg_basic_block[i]); 2790: if (reg_n_deaths[i] != 1) 2791: fprintf (file, "; dies in %d places", reg_n_deaths[i]); 2792: if (reg_n_calls_crossed[i] == 1) 2793: fprintf (file, "; crosses 1 call"); 2794: else if (reg_n_calls_crossed[i]) 2795: fprintf (file, "; crosses %d calls", reg_n_calls_crossed[i]); 2796: if (PSEUDO_REGNO_BYTES (i) != UNITS_PER_WORD) 2797: fprintf (file, "; %d bytes", PSEUDO_REGNO_BYTES (i)); 2798: class = reg_preferred_class (i); 1.1.1.4 root 2799: altclass = reg_alternate_class (i); 2800: if (class != GENERAL_REGS || altclass != ALL_REGS) 1.1 root 2801: { 1.1.1.4 root 2802: if (altclass == ALL_REGS || class == ALL_REGS) 2803: fprintf (file, "; pref %s", reg_class_names[(int) class]); 2804: else if (altclass == NO_REGS) 1.1 root 2805: fprintf (file, "; %s or none", reg_class_names[(int) class]); 2806: else 1.1.1.4 root 2807: fprintf (file, "; pref %s, else %s", 2808: reg_class_names[(int) class], 2809: reg_class_names[(int) altclass]); 1.1 root 2810: } 2811: if (REGNO_POINTER_FLAG (i)) 2812: fprintf (file, "; pointer"); 2813: fprintf (file, ".\n"); 2814: } 2815: fprintf (file, "\n%d basic blocks.\n", n_basic_blocks); 2816: for (i = 0; i < n_basic_blocks; i++) 2817: { 2818: register rtx head, jump; 2819: register int regno; 2820: fprintf (file, "\nBasic block %d: first insn %d, last %d.\n", 2821: i, 2822: INSN_UID (basic_block_head[i]), 2823: INSN_UID (basic_block_end[i])); 2824: /* The control flow graph's storage is freed 2825: now when flow_analysis returns. 2826: Don't try to print it if it is gone. */ 2827: if (basic_block_drops_in) 2828: { 2829: fprintf (file, "Reached from blocks: "); 2830: head = basic_block_head[i]; 2831: if (GET_CODE (head) == CODE_LABEL) 2832: for (jump = LABEL_REFS (head); 2833: jump != head; 2834: jump = LABEL_NEXTREF (jump)) 2835: { 2836: register int from_block = BLOCK_NUM (CONTAINING_INSN (jump)); 2837: fprintf (file, " %d", from_block); 2838: } 2839: if (basic_block_drops_in[i]) 2840: fprintf (file, " previous"); 2841: } 2842: fprintf (file, "\nRegisters live at start:"); 2843: for (regno = 0; regno < max_regno; regno++) 2844: { 2845: register int offset = regno / REGSET_ELT_BITS; 1.1.1.4 root 2846: register REGSET_ELT_TYPE bit 2847: = (REGSET_ELT_TYPE) 1 << (regno % REGSET_ELT_BITS); 1.1 root 2848: if (basic_block_live_at_start[i][offset] & bit) 2849: fprintf (file, " %d", regno); 2850: } 2851: fprintf (file, "\n"); 2852: } 2853: fprintf (file, "\n"); 2854: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.