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