![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to loop.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [GCC 1.x] / gcc|
Return to loop.c CVS log | Up to [GCC 1.x] / gcc |
1.1 root 1: /* Move constant computations out of loops. 1.1.1.2 ! root 2: Copyright (C) 1987, 1988 Free Software Foundation, Inc. 1.1 root 3: 4: This file is part of GNU CC. 5: 6: GNU CC is distributed in the hope that it will be useful, 7: but WITHOUT ANY WARRANTY. No author or distributor 8: accepts responsibility to anyone for the consequences of using it 9: or for whether it serves any particular purpose or works at all, 10: unless he says so in writing. Refer to the GNU CC General Public 11: License for full details. 12: 13: Everyone is granted permission to copy, modify and redistribute 14: GNU CC, but only under the conditions described in the 15: GNU CC General Public License. A copy of this license is 16: supposed to have been given to you along with GNU CC so you 17: can know your rights and responsibilities. It should be in a 18: file named COPYING. Among other things, the copyright notice 19: and this notice must be preserved on all copies. */ 20: 21: 22: /* This is the loop optimization pass of the compiler. 23: It finds invariant computations within loops and moves them 24: to the beginning of the loop. 25: 26: It also finds cases where 27: a register is set within the loop by zero-extending a narrower value 28: and changes these to zero the entire register once before the loop 29: and merely copy the low part within the loop. 30: 31: Most of the complexity is in heuristics to decide when it is worth 32: while to do these things. */ 33: 34: /* ??? verify_loop would run faster if we made one table 35: of the minimum and maximum luids from which each label is reached. 36: Also, it would be faster if loop_store_addrs were a hash table. */ 37: 38: #include "config.h" 39: #include "rtl.h" 40: #include "insn-config.h" 41: #include "regs.h" 42: #include "recog.h" 1.1.1.2 ! root 43: #include <stdio.h> 1.1 root 44: 45: /* Vector mapping INSN_UIDs to luids. 46: The luids are like uids but increase monononically always. 47: We use them to see whether a jump comes from outside a given loop. */ 48: 49: static short *uid_luid; 50: 51: /* Get the luid of an insn. */ 52: 53: #define INSN_LUID(INSN) (uid_luid[INSN_UID (INSN)]) 54: 55: /* 1 + largest uid of any insn. */ 56: 57: static int max_uid; 58: 59: /* 1 + luid of last insn. */ 60: 61: static int max_luid; 62: 63: /* Nonzero if somewhere in the current loop 64: there is either a subroutine call, 65: or a store into a memory address that is not fixed, 66: or a store in a BLKmode memory operand, 67: or too many different fixed addresses stored in 68: to record them all in `loop_store_addrs'. 69: 70: In any of these cases, no memory location can be regarded 71: as invariant. */ 72: 73: static int unknown_address_altered; 74: 75: /* Nonzero if somewhere in the current loop there is a store 76: into a memory address that is not fixed but is known to be 77: part of an aggregate. 78: 79: In this case, no memory reference in an aggregate may be 80: considered invariant. */ 81: 82: static int unknown_aggregate_altered; 83: 84: /* Nonzero if somewhere in the current loop there is a store 85: into a memory address other than a fixed address not in an aggregate. 86: 87: In this case, no memory reference in an aggregate at a varying address 88: may be considered invariant. */ 89: 90: static int fixed_aggregate_altered; 91: 92: /* Nonzero if there is a subroutine call in the current loop. 93: (unknown_address_altered is also nonzero in this case.) */ 94: 95: static int loop_has_call; 96: 97: /* Array of fixed memory addresses that are stored in this loop. 98: If there are too many to fit here, 99: we just turn on unknown_address_altered. */ 100: 101: #define NUM_STORES 10 102: static rtx loop_store_addrs[NUM_STORES]; 103: static int loop_store_widths[NUM_STORES]; 104: 105: /* Index of first available slot in above array. */ 106: static int loop_store_addrs_idx; 107: 108: /* During the analysis of a loop, a chain of `struct movable's 109: is made to record all the movable insns found. 110: Then the entire chain can be scanned to decide which to move. */ 111: 112: struct movable 113: { 114: rtx insn; /* A movable insn */ 1.1.1.2 ! root 115: int consec; /* Number of consecutive following insns ! 116: that must be moved with this one. */ 1.1 root 117: int regno; /* The register it sets */ 118: short lifetime; /* lifetime of that register; 119: may be adjusted when matching movables 120: that load the same value are found. */ 1.1.1.2 ! root 121: short times_used; /* Number of times the register is used, ! 122: plus uses of related insns that could ! 123: be moved if this one is. */ 1.1 root 124: unsigned int cond : 1; /* 1 if only conditionally movable */ 125: unsigned int force : 1; /* 1 means MUST move this insn */ 126: unsigned int global : 1; /* 1 means reg is live outside this loop */ 1.1.1.2 ! root 127: unsigned int done : 1; /* 1 inhibits further processing of this */ ! 128: unsigned int partial : 1; /* Moving this doesn't make it invariant. */ 1.1 root 129: struct movable *match; /* First entry for same value */ 130: struct movable *forces; /* An insn that must be moved if this is */ 131: struct movable *next; 132: }; 133: 1.1.1.2 ! root 134: static FILE *loop_dump_stream; ! 135: 1.1 root 136: static rtx verify_loop (); 137: static int invariant_p (); 138: static int can_jump_into_range_p (); 139: static void count_loop_regs_set (); 140: static void note_addr_stored (); 141: static int loop_reg_used_before_p (); 142: static void constant_high_bytes (); 143: static void scan_loop (); 144: static rtx replace_regs (); 1.1.1.2 ! root 145: static void move_movables (); ! 146: static int may_trap_p (); 1.1 root 147: 148: /* Entry point of this file. Perform loop optimization 149: on the current function. F is the first insn of the function 150: and NREGS is the number of register numbers used. */ 151: 1.1.1.2 ! root 152: void ! 153: loop_optimize (f, nregs, dumpfile) 1.1 root 154: /* f is the first instruction of a chain of insns for one function */ 155: rtx f; 156: /* nregs is the total number of registers used in it */ 157: int nregs; 1.1.1.2 ! root 158: FILE *dumpfile; 1.1 root 159: { 160: register rtx insn; 161: register int i; 162: rtx end; 163: rtx last_insn; 164: 1.1.1.2 ! root 165: loop_dump_stream = dumpfile; ! 166: 1.1 root 167: init_recog (); 168: 169: /* First find the last real insn, and count the number of insns, 170: and assign insns their suids. */ 171: 172: for (insn = f, i = 0; insn; insn = NEXT_INSN (insn)) 173: if (INSN_UID (insn) > i) 174: i = INSN_UID (insn); 175: 176: max_uid = i + 1; 177: uid_luid = (short *) alloca ((i + 1) * sizeof (short)); 178: bzero (uid_luid, (i + 1) * sizeof (short)); 179: 180: /* Compute the mapping from uids to luids. 181: LUIDs are numbers assigned to insns, like uids, 182: except that luids increase monotonically through the code. */ 183: 184: for (insn = f, i = 0; insn; insn = NEXT_INSN (insn)) 185: { 186: last_insn = insn; 187: INSN_LUID (insn) = ++i; 188: } 189: 190: max_luid = i; 191: 192: /* Don't leave gaps in uid_luid for insns that have been 193: deleted. It is possible that the first or last insn 194: using some register has been deleted by cross-jumping. 195: Make sure that uid_luid for that former insn's uid 196: points to the general area where that insn used to be. */ 197: for (i = 0; i < max_uid; i++) 1.1.1.2 ! root 198: { ! 199: uid_luid[0] = uid_luid[i]; ! 200: if (uid_luid[0] != 0) ! 201: break; ! 202: } ! 203: for (i = 0; i < max_uid; i++) 1.1 root 204: if (uid_luid[i] == 0) 205: uid_luid[i] = uid_luid[i - 1]; 206: 207: /* Find and process each loop. 208: We scan from the end, and process each loop when its start is seen, 209: so we process innermost loops first. */ 210: 211: for (insn = last_insn; insn; insn = PREV_INSN (insn)) 212: if (GET_CODE (insn) == NOTE 213: && NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG 214: /* Make sure it really is a loop -- no jumps in from outside. */ 215: && (end = verify_loop (f, insn))) 216: scan_loop (insn, end, nregs); 217: } 218: 219: /* Optimize one loop whose start is LOOP_START and end is END. 220: LOOP_START is the NOTE_INSN_LOOP_BEG and END is the matching 221: NOTE_INSN_LOOP_END. */ 222: 223: static void 224: scan_loop (loop_start, end, nregs) 225: rtx loop_start, end; 226: int nregs; 227: { 228: register int i; 229: register rtx p = NEXT_INSN (loop_start); 230: /* 1 if we are scanning insns that could be executed zero times. */ 231: int maybe_never = 0; 232: /* For a rotated loop that is entered near the bottom, 233: this is the label at the top. Otherwise it is zero. */ 234: rtx loop_top = 0; 1.1.1.2 ! root 235: /* This is the insn (whatever kind) before the NOTE that starts the loop. ! 236: Any insns moved out of the loop will follow it. */ ! 237: rtx before_start = PREV_INSN (loop_start); 1.1 root 238: /* Jump insn that enters the loop, or 0 if control drops in. */ 239: rtx loop_entry_jump = 0; 240: /* Place in the loop where control enters. */ 241: rtx scan_start; 242: /* Number of insns in the loop. */ 243: int insn_count; 244: int tem; 245: /* Indexed by register number, contains the number of times the reg 246: is set during the loop being scanned, or -1 if the insns that set it 247: have all been scanned as candidates for being moved out of the loop. 248: 0 indicates an invariant register; -1 a conditionally invariant one. */ 249: short *n_times_set; 250: /* Indexed by register number, contains the number of times the reg 251: was set during the loop being scanned, not counting changes due 252: to moving these insns out of the loop. */ 253: short *n_times_used; 254: /* Indexed by register number, contains 1 for a register whose 255: assignments may not be moved out of the loop. */ 256: char *may_not_move; 257: /* Chain describing insns movable in current loop. */ 258: struct movable *movables = 0; 259: /* Last element in `movables' -- so we can add elements at the end. */ 260: struct movable *last_movable = 0; 261: /* Ratio of extra register life span we can justify 262: for saving an instruction. More if loop doesn't call subroutines 263: since in that case saving an insn makes more difference 264: and more registers are available. */ 1.1.1.2 ! root 265: int threshold = loop_has_call ? 17 : 34; 1.1 root 266: 267: n_times_set = (short *) alloca (nregs * sizeof (short)); 268: n_times_used = (short *) alloca (nregs * sizeof (short)); 269: may_not_move = (char *) alloca (nregs); 270: 271: /* Determine whether this loop starts with a jump down 272: to a test at the end. */ 273: while (p != end 274: && GET_CODE (p) != CODE_LABEL && GET_CODE (p) != JUMP_INSN) 275: p = NEXT_INSN (p); 276: 277: /* "Loop" contains neither jumps nor labels; 278: it must have been a dummy. Think no more about it. */ 279: if (p == end) 280: return; 281: 1.1.1.2 ! root 282: scan_start = p; ! 283: 1.1 root 284: /* If loop has a jump before the first label, 285: the true entry is the target of that jump. 286: Start scan from there. 287: But record in LOOP_TOP the place where the end-test jumps 288: back to so we can scan that after the end of the loop. */ 289: if (GET_CODE (p) == JUMP_INSN) 290: { 291: loop_entry_jump = p; 292: loop_top = NEXT_INSN (p); 293: /* Loop entry will never be a conditional jump. 294: If we see one, this must not be a real loop. */ 295: if (GET_CODE (loop_top) != BARRIER) 296: return; 297: p = JUMP_LABEL (p); 298: /* Check to see whether the jump actually 299: jumps out of the loop (meaning it's no loop). 300: This case can happen for things like 301: do {..} while (0). */ 1.1.1.2 ! root 302: if (p == 0 ! 303: || INSN_LUID (p) < INSN_LUID (loop_start) 1.1 root 304: || INSN_LUID (p) >= INSN_LUID (end)) 1.1.1.2 ! root 305: { ! 306: if (loop_dump_stream) ! 307: fprintf (loop_dump_stream, "\nLoop from %d to %d is phony.\n\n", ! 308: INSN_UID (loop_start), INSN_UID (end)); ! 309: return; ! 310: } ! 311: ! 312: /* Find the first label after the entry-jump. */ ! 313: while (GET_CODE (loop_top) != CODE_LABEL) ! 314: { ! 315: loop_top = NEXT_INSN (loop_top); ! 316: if (loop_top == 0) ! 317: abort (); ! 318: } ! 319: ! 320: /* Maybe rearrange the loop to drop straight in ! 321: with a new test to jump around it entirely. ! 322: (The latter is considered outside the loop.) ! 323: If this is done, we no longer enter with a jump. */ ! 324: if (loop_skip_over (loop_start, end, loop_entry_jump)) ! 325: loop_top = 0; ! 326: else ! 327: /* We really do enter with a jump; ! 328: scan the loop from the place where the jump jumps to. */ ! 329: scan_start = p; 1.1 root 330: } 331: 332: /* Count number of times each reg is set during this loop. 333: Set MAY_NOT_MOVE[I] if it is not safe to move out 334: the setting of register I. */ 335: 336: bzero (n_times_set, nregs * sizeof (short)); 337: bzero (may_not_move, nregs); 1.1.1.2 ! root 338: count_loop_regs_set (loop_top ? loop_top : loop_start, end, ! 339: n_times_set, may_not_move, 1.1 root 340: &insn_count, nregs); 341: for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) 342: may_not_move[i] = 1, n_times_set[i] = 1; 343: bcopy (n_times_set, n_times_used, nregs * sizeof (short)); 344: 1.1.1.2 ! root 345: if (loop_dump_stream) ! 346: fprintf (loop_dump_stream, "\nLoop from %d to %d: %d real insns\n\n", ! 347: INSN_UID (loop_start), INSN_UID (end), insn_count); ! 348: 1.1 root 349: /* Scan through the loop finding insns that are safe to move. 350: In each such insn, store QImode as the mode, to mark it. 351: Then set n_times_set to -1 for the reg being set, so that 352: this reg will be considered invariant for subsequent insns. 353: We consider whether subsequent insns use the reg 354: in deciding whether it is worth actually moving. 355: 356: MAYBE_NEVER is nonzero if we have passed a conditional jump insn 357: and therefore it is possible that the insns we are scanning 358: would never be executed. At such times, we must make sure 359: that it is safe to execute the insn once instead of zero times. 360: When MAYBE_NEVER is 0, all insns will be executed at least once 361: so that is not a problem. */ 362: 1.1.1.2 ! root 363: p = scan_start; 1.1 root 364: while (1) 365: { 366: p = NEXT_INSN (p); 367: /* At end of a straight-in loop, we are done. 368: At end of a loop entered at the bottom, scan the top. */ 369: if (p == scan_start) 370: break; 371: if (p == end) 372: { 373: if (loop_top != 0) 374: p = NEXT_INSN (loop_top); 375: else 376: break; 377: if (p == scan_start) 378: break; 379: } 380: if (GET_CODE (p) == INSN 381: && GET_CODE (PATTERN (p)) == SET 382: && GET_CODE (SET_DEST (PATTERN (p))) == REG 383: && ! may_not_move[REGNO (SET_DEST (PATTERN (p)))]) 384: { 385: /* If this register is used or set outside the loop, 386: then we can move it only if we know this insn is 387: executed exactly once per iteration, 388: and we can check all the insns executed before it 389: to make sure none of them used the value that 390: was lying around at entry to the loop. */ 391: if ((uid_luid[regno_last_uid[REGNO (SET_DEST (PATTERN (p)))]] > INSN_LUID (end) 392: || uid_luid[regno_first_uid[REGNO (SET_DEST (PATTERN (p)))]] < INSN_LUID (loop_start)) 393: && (maybe_never 394: || loop_reg_used_before_p (p, loop_start, scan_start, end))) 395: ; 1.1.1.2 ! root 396: /* If this can cause a trap (such as divide by zero), can't move it ! 397: unless it's guaranteed to be executed once loop is entered. */ ! 398: else if (maybe_never && may_trap_p (SET_SRC (PATTERN (p)))) ! 399: ; 1.1 root 400: else if ((tem = invariant_p (SET_SRC (PATTERN (p)), n_times_set)) 401: && (n_times_set[REGNO (SET_DEST (PATTERN (p)))] == 1 1.1.1.2 ! root 402: || consec_sets_invariant_p (SET_DEST (PATTERN (p)), ! 403: p, n_times_set))) 1.1 root 404: { 405: register struct movable *m; 406: register int regno = REGNO (SET_DEST (PATTERN (p))); 1.1.1.2 ! root 407: int count; 1.1 root 408: m = (struct movable *) alloca (sizeof (struct movable)); 409: m->next = 0; 410: m->insn = p; 411: m->force = 0; 1.1.1.2 ! root 412: m->consec = n_times_set[REGNO (SET_DEST (PATTERN (p)))] - 1; ! 413: m->done = 0; 1.1 root 414: m->forces = 0; 1.1.1.2 ! root 415: m->partial = 0; 1.1 root 416: m->regno = regno; 417: m->cond = (tem > 1); 418: m->global = (uid_luid[regno_last_uid[regno]] > INSN_LUID (end) 419: || uid_luid[regno_first_uid[regno]] < INSN_LUID (loop_start)); 420: m->match = 0; 421: m->lifetime = (uid_luid[regno_last_uid[regno]] 422: - uid_luid[regno_first_uid[regno]]); 1.1.1.2 ! root 423: m->times_used = n_times_used[regno]; 1.1 root 424: n_times_set[regno] = -1; 425: /* Add M to the end of the chain MOVABLES. */ 426: if (movables == 0) 427: movables = m; 428: else 429: last_movable->next = m; 430: last_movable = m; 1.1.1.2 ! root 431: /* Skip the consecutive insns, if there are any. */ ! 432: for (count = m->consec - 1; count >= 0; count--) ! 433: { ! 434: do p = NEXT_INSN (p); ! 435: while (GET_CODE (p) == NOTE); ! 436: } 1.1 root 437: } 1.1.1.2 ! root 438: /* If this register is always set within a STRICT_LOW_PART ! 439: or set to zero, then its high bytes are constant. 1.1 root 440: So clear them outside the loop and within the loop 441: just load the low bytes. 442: We must check that the machine has an instruction to do so. 443: Also, if the value loaded into the register 444: depends on the same register, this cannot be done. */ 1.1.1.2 ! root 445: else if (SET_SRC (PATTERN (p)) == const0_rtx ! 446: && GET_CODE (NEXT_INSN (p)) == INSN ! 447: && GET_CODE (PATTERN (NEXT_INSN (p))) == SET ! 448: && (GET_CODE (SET_DEST (PATTERN (NEXT_INSN (p)))) ! 449: == STRICT_LOW_PART) ! 450: && (GET_CODE (XEXP (SET_DEST (PATTERN (NEXT_INSN (p))), 0)) ! 451: == SUBREG) ! 452: && (SUBREG_REG (XEXP (SET_DEST (PATTERN (NEXT_INSN (p))), 0)) ! 453: == SET_DEST (PATTERN (p))) 1.1 root 454: && !reg_mentioned_p (SET_DEST (PATTERN (p)), 1.1.1.2 ! root 455: SET_SRC (PATTERN (NEXT_INSN (p))))) 1.1 root 456: { 457: register int regno = REGNO (SET_DEST (PATTERN (p))); 1.1.1.2 ! root 458: if (n_times_set[regno] == 2) ! 459: { ! 460: register struct movable *m; ! 461: int count; ! 462: m = (struct movable *) alloca (sizeof (struct movable)); ! 463: m->next = 0; ! 464: m->insn = p; ! 465: m->force = 0; ! 466: m->consec = 0; ! 467: m->done = 0; ! 468: m->forces = 0; ! 469: m->partial = 1; ! 470: m->regno = regno; ! 471: m->cond = 0; ! 472: /* Say "global" so this register is not combined ! 473: with any other. In fact, it is sometimes possible ! 474: to combine two of these registers, but the criteria ! 475: are special and have not been programmed in. */ ! 476: m->global = 1; ! 477: m->match = 0; ! 478: m->lifetime = (uid_luid[regno_last_uid[regno]] ! 479: - uid_luid[regno_first_uid[regno]]); ! 480: m->times_used = n_times_used[regno]; ! 481: n_times_set[regno] = -1; ! 482: /* Add M to the end of the chain MOVABLES. */ ! 483: if (movables == 0) ! 484: movables = m; ! 485: else ! 486: last_movable->next = m; ! 487: last_movable = m; ! 488: /* Skip the consecutive insns, if there are any. */ ! 489: for (count = m->consec - 1; count >= 0; count--) ! 490: { ! 491: do p = NEXT_INSN (p); ! 492: while (GET_CODE (p) == NOTE); ! 493: } ! 494: } 1.1 root 495: } 496: } 497: /* Past a label or a jump, we get to insns for which we 498: can't count on whether or how many times they will be 499: executed during each iteration. Therefore, we can 500: only move out sets of trivial variables 501: (those not used after the loop). */ 502: else if (GET_CODE (p) == CODE_LABEL || GET_CODE (p) == JUMP_INSN) 503: maybe_never = 1; 504: } 505: 506: /* For each movable insn, see if the reg that it loads 1.1.1.2 ! root 507: leads when it dies right into another conditionally movable insn. ! 508: If so, record that the second insn "forces" the first one, ! 509: since the second can be moved only if the first is. */ ! 510: 1.1 root 511: { 512: register struct movable *m, *m1; 513: for (m1 = movables; m1; m1 = m1->next) 514: { 515: int regno = m1->regno; 516: for (m = m1->next; m; m = m->next) 517: if (INSN_UID (m->insn) == regno_last_uid[regno]) 518: break; 519: if (m != 0 && SET_SRC (PATTERN (m->insn)) == SET_DEST (PATTERN (m1->insn))) 520: m = 0; 1.1.1.2 ! root 521: ! 522: /* Increase the priority of the moving the first insn ! 523: since it permits the second to be moved as well. */ ! 524: if (m != 0) ! 525: { ! 526: m->forces = m1; ! 527: m1->lifetime += m->lifetime; ! 528: m1->times_used += m1->times_used; ! 529: } 1.1 root 530: } 531: } 532: 533: /* See if there are multiple movable insns that load the same value. 534: If there are, make all but the first point at the first one 535: through the `match' field, and add the priorities of them 536: all together as the priority of the first. */ 1.1.1.2 ! root 537: 1.1 root 538: { 539: register struct movable *m; 540: char *matched_regs = (char *) alloca (nregs); 541: 1.1.1.2 ! root 542: /* Regs that are used more than once are not allowed to match ! 543: or be matched. I'm no longer sure why not. */ 1.1 root 544: 545: for (m = movables; m; m = m->next) 1.1.1.2 ! root 546: if (m->match == 0 && n_times_used[m->regno] == 1) 1.1 root 547: { 548: register struct movable *m1; 1.1.1.2 ! root 549: int regno = m->regno; 1.1 root 550: 551: bzero (matched_regs, nregs); 1.1.1.2 ! root 552: matched_regs[regno] = 1; 1.1 root 553: 554: for (m1 = m->next; m1; m1 = m1->next) 1.1.1.2 ! root 555: if (m1->match == 0 && n_times_used[m1->regno] == 1 ! 556: /* A reg used outside the loop mustn't be eliminated. */ ! 557: && !m1->global ! 558: && (matched_regs[m1->regno] ! 559: || ! 560: ( ! 561: /* Can't combine regs with different modes ! 562: even if loaded from the same constant. */ ! 563: (GET_MODE (SET_DEST (PATTERN (m->insn))) ! 564: == GET_MODE (SET_DEST (PATTERN (m1->insn)))) ! 565: /* See if the source of M1 says it matches M. */ ! 566: && ((GET_CODE (SET_SRC (PATTERN (m1->insn))) == REG ! 567: && matched_regs[REGNO (SET_SRC (PATTERN (m1->insn)))]) ! 568: || rtx_equal_p (SET_SRC (PATTERN (m->insn)), ! 569: SET_SRC (PATTERN (m1->insn))) ! 570: || (REG_NOTES (m->insn) && REG_NOTES (m1->insn) ! 571: && REG_NOTE_KIND (REG_NOTES (m->insn)) == REG_EQUIV ! 572: && REG_NOTE_KIND (REG_NOTES (m1->insn)) == REG_EQUIV ! 573: && rtx_equal_p (XEXP (REG_NOTES (m->insn), 0), ! 574: XEXP (REG_NOTES (m1->insn), 0))))))) ! 575: { ! 576: m->lifetime += m1->lifetime; ! 577: m->times_used += m1->times_used; ! 578: m1->match = m; ! 579: matched_regs[m1->regno] = 1; ! 580: } ! 581: } ! 582: } ! 583: ! 584: /* Now consider each movable insn to decide whether it is worth moving. */ ! 585: ! 586: move_movables (movables, n_times_set, n_times_used, threshold, ! 587: insn_count, loop_start, end, nregs); ! 588: } ! 589: ! 590: /* Scan MOVABLES, and move the insns that deserve to be moved. ! 591: If two matching movables are combined, replace one reg with the ! 592: other throughout. */ ! 593: ! 594: static void ! 595: move_movables (movables, n_times_set, n_times_used, threshold, ! 596: insn_count, loop_start, end, nregs) ! 597: struct movable *movables; ! 598: short *n_times_set; ! 599: short *n_times_used; ! 600: int threshold; ! 601: int insn_count; ! 602: rtx loop_start; ! 603: rtx end; ! 604: int nregs; ! 605: { ! 606: rtx new_start = 0; ! 607: register struct movable *m; ! 608: register rtx p; ! 609: /* Map of pseudo-register replacements to handle combining ! 610: when we move several insns that load the same value ! 611: into different pseudo-registers. */ ! 612: rtx *reg_map = (rtx *) alloca (nregs * sizeof (rtx)); ! 613: char *already_moved = (char *) alloca (nregs); ! 614: ! 615: bzero (already_moved, nregs); ! 616: bzero (reg_map, nregs * sizeof (rtx)); ! 617: ! 618: for (m = movables; m; m = m->next) ! 619: { ! 620: /* Describe this movable insn. */ ! 621: ! 622: if (loop_dump_stream) ! 623: { ! 624: fprintf (loop_dump_stream, "Insn %d: regno %d (life %d), ", ! 625: INSN_UID (m->insn), m->regno, m->lifetime); ! 626: if (m->consec > 0) ! 627: fprintf (loop_dump_stream, "consec %d, ", m->consec); ! 628: if (m->cond) ! 629: fprintf (loop_dump_stream, "cond "); ! 630: if (m->force) ! 631: fprintf (loop_dump_stream, "force "); ! 632: if (m->global) ! 633: fprintf (loop_dump_stream, "global "); ! 634: if (m->done) ! 635: fprintf (loop_dump_stream, "done "); ! 636: if (m->match) ! 637: fprintf (loop_dump_stream, "matches %d ", ! 638: INSN_UID (m->match->insn)); ! 639: if (m->forces) ! 640: fprintf (loop_dump_stream, "forces %d ", ! 641: INSN_UID (m->forces->insn)); ! 642: } ! 643: ! 644: /* Ignore the insn if it's already done (it matched something else). ! 645: Otherwise, see if it is now safe to move. */ ! 646: ! 647: if (!m->done ! 648: && (! m->cond ! 649: || 1 == invariant_p (SET_SRC (PATTERN (m->insn)), n_times_set)) ! 650: && (! m->forces || m->forces->done)) ! 651: { ! 652: register int regno; ! 653: register rtx p; ! 654: int times_used = m->times_used + m->consec; ! 655: ! 656: /* We have an insn that is safe to move. ! 657: Compute its desirability. */ ! 658: ! 659: p = m->insn; ! 660: regno = m->regno; ! 661: ! 662: if (loop_dump_stream) ! 663: fprintf (loop_dump_stream, "reg uses %d ", times_used); ! 664: ! 665: /* An insn MUST be moved if we already moved something else ! 666: which is safe only if this one is moved too: that is, ! 667: if already_moved[REGNO] is nonzero. */ ! 668: ! 669: /* An insn is desirable to move if the new lifetime of the ! 670: register is no more than THRESHOLD times the old lifetime. ! 671: If it's not desirable, it means the loop is so big ! 672: that moving won't speed things up much, ! 673: and it is liable to make register usage worse. */ ! 674: ! 675: /* It is also desirable to move if it can be moved at no ! 676: extra cost because something else was already moved. */ ! 677: ! 678: if (already_moved[regno] ! 679: || (threshold * times_used * m->lifetime) >= insn_count ! 680: || (m->forces && m->forces->done ! 681: && n_times_used[m->forces->regno] == 1)) 1.1 root 682: { 1.1.1.2 ! root 683: int count; ! 684: register struct movable *m1; ! 685: ! 686: for (count = m->consec; count >= 0; count--) 1.1 root 687: { 1.1.1.2 ! root 688: rtx i1 = emit_insn_before (PATTERN (p), loop_start); ! 689: if (new_start == 0) ! 690: new_start = i1; ! 691: ! 692: if (loop_dump_stream) ! 693: fprintf (loop_dump_stream, "moved to %d", INSN_UID (i1)); ! 694: ! 695: /* Mark the moved, invariant reg as being equivalent to ! 696: its constant value. */ ! 697: REG_NOTES (i1) = REG_NOTES (p); ! 698: if (REG_NOTES (i1) == 0 ! 699: && ! m->partial /* But not if its a zero-extend clr. */ ! 700: && ! m->global /* and not if used outside the loop ! 701: (since it might get set outside). */ ! 702: && CONSTANT_P (SET_SRC (PATTERN (p)))) ! 703: REG_NOTES (i1) ! 704: = gen_rtx (EXPR_LIST, REG_EQUIV, ! 705: SET_SRC (PATTERN (p)), REG_NOTES (i1)); ! 706: delete_insn (p); ! 707: do p = NEXT_INSN (p); ! 708: while (GET_CODE (p) == NOTE); ! 709: ! 710: /* The more insns we move, the less we like moving them. */ ! 711: threshold -= 2; 1.1 root 712: } 1.1.1.2 ! root 713: ! 714: /* Any other movable that loads the same register ! 715: MUST be moved. */ ! 716: already_moved[regno] = 1; ! 717: ! 718: /* The reg set here is now invariant. */ ! 719: if (! m->partial) ! 720: n_times_set[regno] = 0; ! 721: ! 722: m->done = 1; ! 723: ! 724: /* Combine with this moved insn any other matching movables. */ 1.1 root 725: 726: for (m1 = m->next; m1; m1 = m1->next) 727: if (m1->match == m) 728: { 729: /* Schedule the reg loaded by M1 730: for replacement so that shares the reg of M. */ 731: reg_map[m1->regno] = SET_DEST (PATTERN (m->insn)); 1.1.1.2 ! root 732: /* Get rid of the matching insn 1.1 root 733: and prevent further processing of it. */ 1.1.1.2 ! root 734: m1->done = 1; 1.1 root 735: delete_insn (m1->insn); 1.1.1.2 ! root 736: ! 737: /* Any other movable that loads the same register ! 738: MUST be moved. */ ! 739: already_moved[m1->regno] = 1; ! 740: ! 741: /* The reg merged here is now invariant. */ ! 742: if (m->partial) ! 743: n_times_set[m1->regno] = 0; 1.1 root 744: } 745: } 1.1.1.2 ! root 746: else if (loop_dump_stream) ! 747: fprintf (loop_dump_stream, "not desirable"); 1.1 root 748: } 1.1.1.2 ! root 749: else if (loop_dump_stream && !m->match) ! 750: fprintf (loop_dump_stream, "not safe"); 1.1 root 751: 1.1.1.2 ! root 752: if (loop_dump_stream) ! 753: fprintf (loop_dump_stream, "\n"); ! 754: } 1.1 root 755: 1.1.1.2 ! root 756: if (new_start == 0) ! 757: new_start = loop_start; 1.1 root 758: 1.1.1.2 ! root 759: /* Go through all the instructions in the loop, making ! 760: all the register substitutions scheduled in REG_MAP. */ ! 761: for (p = new_start; p != end; p = NEXT_INSN (p)) ! 762: if (GET_CODE (p) == INSN || GET_CODE (p) == JUMP_INSN ! 763: || GET_CODE (p) == CALL_INSN) ! 764: replace_regs (PATTERN (p), reg_map); ! 765: } ! 766: ! 767: /* Optionally change a loop which enters just before the endtest ! 768: to one which falls straight in ! 769: after skipping around the entire loop if the endtest would drop out. ! 770: Returns 1 if the change was made, 0 if the loop was not really suitable. */ ! 771: ! 772: int ! 773: loop_skip_over (start, end, loop_entry_jump) ! 774: rtx start; ! 775: rtx end; ! 776: rtx loop_entry_jump; ! 777: { ! 778: rtx endtestjump; ! 779: register rtx p = JUMP_LABEL (loop_entry_jump); 1.1 root 780: 1.1.1.2 ! root 781: while (GET_CODE (p) != INSN && GET_CODE (p) != JUMP_INSN ! 782: && GET_CODE (p) != CALL_INSN) ! 783: p = NEXT_INSN (p); ! 784: endtestjump = next_real_insn (p); ! 785: ! 786: /* Check that we (1) enter at a compare insn and (2) ! 787: the insn (presumably a jump) following that compare ! 788: is the last in the loop and jumps back to the loop beginning. */ ! 789: ! 790: if (GET_CODE (PATTERN (p)) == SET ! 791: && SET_DEST (PATTERN (p)) == cc0_rtx ! 792: && endtestjump == prev_real_insn (end) ! 793: && prev_real_insn (JUMP_LABEL (endtestjump)) == loop_entry_jump) 1.1 root 794: { 1.1.1.2 ! root 795: rtx newlab; ! 796: /* This is the jump that we insert. */ ! 797: rtx new_jump; ! 798: ! 799: /* Ok, duplicate that test before start of loop. */ ! 800: emit_insn_before (copy_rtx (PATTERN (p)), start); ! 801: /* Make a new entry-jump (before the original one) ! 802: whose condition is opposite to the loop-around endtest ! 803: and which jumps around the loop (to just after the endtest). */ ! 804: newlab = gen_label_rtx (); ! 805: emit_label_after (newlab, endtestjump); ! 806: emit_jump_insn_before (copy_rtx (PATTERN (endtestjump)), start); ! 807: new_jump = PREV_INSN (start); ! 808: JUMP_LABEL (new_jump) = JUMP_LABEL (endtestjump); ! 809: LABEL_NUSES (JUMP_LABEL (endtestjump))++; ! 810: invert_jump (new_jump, newlab); ! 811: /* Delete the original entry-jump. */ ! 812: delete_insn (loop_entry_jump); 1.1 root 813: 1.1.1.2 ! root 814: return 1; 1.1 root 815: } 1.1.1.2 ! root 816: ! 817: return 0; 1.1 root 818: } 819: 820: /* Throughout the rtx X, replace many registers according to REG_MAP. 821: Return the replacement for X (which may be X with altered contents). 822: REG_MAP[R] is the replacement for register R, or 0 for don't replace. */ 823: 824: static rtx 825: replace_regs (x, reg_map) 826: rtx x; 827: rtx *reg_map; 828: { 829: register RTX_CODE code = GET_CODE (x); 830: register int i; 831: register char *fmt; 832: 833: switch (code) 834: { 835: case PC: 836: case CC0: 837: case CONST_INT: 838: case CONST_DOUBLE: 839: case CONST: 840: case SYMBOL_REF: 841: case LABEL_REF: 842: return x; 843: 844: case REG: 845: if (reg_map[REGNO (x)] != 0) 846: return reg_map[REGNO (x)]; 847: return x; 848: } 849: 850: fmt = GET_RTX_FORMAT (code); 851: for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) 852: { 853: if (fmt[i] == 'e') 854: XEXP (x, i) = replace_regs (XEXP (x, i), reg_map); 855: if (fmt[i] == 'E') 856: { 857: register int j; 858: for (j = 0; j < XVECLEN (x, i); j++) 859: XVECEXP (x, i, j) = replace_regs (XVECEXP (x, i, j), reg_map); 860: } 861: } 862: return x; 863: } 864: 865: /* P is an instruction that sets a register to the result of a ZERO_EXTEND. 866: Replace it with an instruction to load just the low bytes 867: if the machine supports such an instruction, 868: and insert above LOOP_START an instruction to clear the register. */ 869: 870: static void 871: constant_high_bytes (p, loop_start) 872: rtx p, loop_start; 873: { 874: register rtx new; 875: register int insn_code_number; 876: 877: /* Try to change (SET (REG ...) (ZERO_EXTEND (..:B ...))) 878: to (SET (STRICT_LOW_PART (SUBREG:B (REG...))) ...). */ 879: 880: new = gen_rtx (SET, VOIDmode, 881: gen_rtx (STRICT_LOW_PART, VOIDmode, 882: gen_rtx (SUBREG, GET_MODE (XEXP (SET_SRC (PATTERN (p)), 0)), 883: SET_DEST (PATTERN (p)), 884: 0)), 885: XEXP (SET_SRC (PATTERN (p)), 0)); 886: insn_code_number = recog (new, p); 887: 888: if (insn_code_number) 889: { 890: register int i; 891: 892: /* Clear destination register before the loop. */ 893: emit_insn_before (gen_rtx (SET, VOIDmode, 894: SET_DEST (PATTERN (p)), 895: const0_rtx), 896: loop_start); 897: 898: /* Inside the loop, just load the low part. */ 899: PATTERN (p) = new; 900: } 901: } 902: 903: /* Verify that the ostensible loop starting at START 904: really is a loop: nothing jumps into it from outside. 905: Return the marker for the end of the loop, or zero if not a real loop. 906: 907: Also set the variables `unknown_*_altered' and `loop_has_call', 908: and fill in the array `loop_store_addrs'. */ 909: 910: static rtx 911: verify_loop (f, start) 912: rtx f, start; 913: { 914: register int level = 1; 915: register rtx insn, end; 916: 917: /* First find the LOOP_END that matches. 918: Also check each insn for storing in memory and record where. */ 919: 920: unknown_address_altered = 0; 921: unknown_aggregate_altered = 0; 922: fixed_aggregate_altered = 0; 923: loop_has_call = 0; 924: loop_store_addrs_idx = 0; 925: 926: for (insn = NEXT_INSN (start); level > 0; insn = NEXT_INSN (insn)) 927: { 928: if (insn == 0) 1.1.1.2 ! root 929: /* Parse errors can cause a loop-beg with no loop-end. */ ! 930: return 0; 1.1 root 931: if (GET_CODE (insn) == NOTE) 932: { 933: if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG) 934: ++level; 935: else if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END) 1.1.1.2 ! root 936: { ! 937: --level; ! 938: if (level == 0) ! 939: { ! 940: end = insn; ! 941: break; ! 942: } ! 943: } 1.1 root 944: } 945: else if (GET_CODE (insn) == CALL_INSN) 946: { 947: unknown_address_altered = 1; 948: loop_has_call = 1; 949: } 950: else if (! unknown_address_altered) 951: { 952: if (GET_CODE (insn) == INSN || GET_CODE (insn) == JUMP_INSN) 953: note_stores (PATTERN (insn), note_addr_stored); 954: } 955: } 956: 957: /* Now scan all jumps in the function and see if any of them can 958: reach a label within the range of the loop. */ 959: 960: for (insn = f; insn; insn = NEXT_INSN (insn)) 961: if (GET_CODE (insn) == JUMP_INSN 962: /* Don't get fooled by jumps inserted by loop-optimize. 963: They don't have valid LUIDs, and they never jump into loops. */ 964: && INSN_UID (insn) < max_uid 965: && (INSN_LUID (insn) < INSN_LUID (start) 966: || INSN_LUID (insn) > INSN_LUID (end)) 967: /* We have a jump that is outside the loop. 968: Does it jump into the loop? */ 969: && can_jump_into_range_p (PATTERN (insn), 970: INSN_LUID (start), INSN_LUID (end))) 971: return 0; 972: 973: #if 0 974: /* Now scan all labels between them and check for any jumps from outside. 975: This uses the ref-chains set up by find_basic_blocks. 976: This code is not used because it's more convenient for other reasons 977: to do the loop optimization before find_basic_blocks. */ 978: 979: for (insn = start; insn != end; insn = NEXT_INSN (insn)) 980: if (GET_CODE (insn) == CODE_LABEL) 981: { 982: register rtx y; 983: for (y = LABEL_REFS (insn); y != insn; y = LABEL_NEXTREF (y)) 984: if (INSN_LUID (CONTAINING_INSN (y)) < INSN_LUID (start) 985: || INSN_LUID (CONTAINING_INSN (y)) > INSN_LUID (end)) 986: return 0; 987: } 988: #endif 989: 990: return end; 991: } 992: 993: /* Return 1 if somewhere in X is a LABEL_REF to a label 994: located between BEG and END. */ 995: 996: static int 997: can_jump_into_range_p (x, beg, end) 998: rtx x; 999: int beg, end; 1000: { 1001: register RTX_CODE code = GET_CODE (x); 1002: register int i; 1003: register char *fmt; 1004: 1005: if (code == LABEL_REF) 1006: { 1007: register int luid = INSN_LUID (XEXP (x, 0)); 1008: return luid > beg && luid < end; 1009: } 1010: 1011: fmt = GET_RTX_FORMAT (code); 1012: for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) 1013: { 1014: if (fmt[i] == 'e') 1015: { 1016: if (can_jump_into_range_p (XEXP (x, i), beg, end)) 1017: return 1; 1018: } 1019: else if (fmt[i] == 'E') 1020: { 1021: register int j; 1022: for (j = 0; j < XVECLEN (x, i); j++) 1023: if (can_jump_into_range_p (XVECEXP (x, i, j), beg, end)) 1024: return 1; 1025: } 1026: } 1027: 1028: return 0; 1029: } 1030: 1031: /* Record that a memory reference X is being set. */ 1032: 1033: static void 1034: note_addr_stored (x) 1035: rtx x; 1036: { 1037: rtx addr; 1038: if (x == 0 || GET_CODE (x) != MEM) 1039: return; 1.1.1.2 ! root 1040: if (GET_MODE (x) == BLKmode) ! 1041: unknown_address_altered = 1; ! 1042: else if (rtx_addr_varies_p (x)) 1.1 root 1043: { 1044: if (GET_CODE (XEXP (x, 0)) == PLUS) 1045: unknown_aggregate_altered = 1; 1046: else 1047: unknown_address_altered = 1; 1048: } 1049: else 1050: { 1051: register int i; 1052: register rtx addr = XEXP (x, 0); 1053: 1054: if (x->in_struct) 1055: fixed_aggregate_altered = 1; 1056: for (i = 0; i < loop_store_addrs_idx; i++) 1057: if (rtx_equal_p (loop_store_addrs[i], addr)) 1058: { 1059: if (loop_store_widths[i] < GET_MODE_SIZE (GET_MODE (x))) 1060: loop_store_widths[i] = GET_MODE_SIZE (GET_MODE (x)); 1061: break; 1062: } 1063: if (i == NUM_STORES) 1064: unknown_address_altered = 1; 1065: else if (i == loop_store_addrs_idx) 1066: { 1.1.1.2 ! root 1067: loop_store_widths[i] = GET_MODE_SIZE (GET_MODE (x)); 1.1 root 1068: loop_store_addrs[loop_store_addrs_idx++] = addr; 1069: } 1070: } 1071: } 1072: 1073: /* Return nonzero if the rtx X is invariant over the current loop. 1074: N_TIMES_SET is a vector whose element I is nonzero if register I 1075: is set during the loop. 1076: 1077: The value is 2 if we refer to something only conditionally invariant. 1078: 1079: If `unknown_address_altered' is nonzero, no memory ref is invariant. 1080: Otherwise if `unknown_aggregate_altered' is nonzero, 1081: a memory ref is invariant if it is not part of an aggregate 1082: and its address is fixed and not in `loop_store_addrs'. 1083: Otherwise if `fixed_aggregate_altered' is nonzero, 1084: a memory ref is invariant 1085: if its address is fixed and not in `loop_store_addrs'. 1086: Otherwise, a memory ref is invariant if its address is fixed and not in 1087: `loop_store_addrs' or if it is not an aggregate. */ 1088: 1089: static int 1090: invariant_p (x, n_times_set) 1091: register rtx x; 1092: short *n_times_set; 1093: { 1094: register int i; 1095: register RTX_CODE code = GET_CODE (x); 1096: register char *fmt; 1097: int conditional = 0; 1098: 1099: switch (code) 1100: { 1101: case CONST_INT: 1102: case CONST_DOUBLE: 1103: case SYMBOL_REF: 1104: case LABEL_REF: 1105: case CONST: 1106: return 1; 1107: 1108: case PC: 1109: case CC0: 1110: return 0; 1111: 1112: case REG: 1.1.1.2 ! root 1113: if (x == frame_pointer_rtx || x == arg_pointer_rtx ! 1114: || x->unchanging) ! 1115: return 1; 1.1 root 1116: if (n_times_set[REGNO (x)] == -1) 1117: return 2; 1118: return n_times_set[REGNO (x)] == 0; 1119: 1120: case MEM: 1121: /* A store in a varying-address scalar (or a subroutine call) 1122: could clobber anything in memory. */ 1123: if (unknown_address_altered) 1124: return 0; 1.1.1.2 ! root 1125: /* Don't mess with volatile memory references. */ ! 1126: if (x->volatil) ! 1127: return 0; ! 1128: /* If it's declared read-only, it is invariant ! 1129: if its address is invariant. */ ! 1130: if (x->unchanging) ! 1131: return invariant_p (XEXP (x, 0), n_times_set); 1.1 root 1132: /* A store in a varying-address aggregate component 1133: could clobber anything except a scalar with a fixed address. */ 1134: if (unknown_aggregate_altered 1135: && ((x->in_struct || GET_CODE (XEXP (x, 0)) == PLUS) 1136: || rtx_addr_varies_p (x))) 1137: return 0; 1138: /* A store in a fixed-address aggregate component 1139: could clobber anything whose address is not fixed, 1140: even an aggregate component. */ 1141: if (fixed_aggregate_altered 1142: && rtx_addr_varies_p (x)) 1143: return 0; 1144: /* Any store could clobber a varying-address scalar. */ 1145: if (loop_store_addrs_idx 1146: && !(x->in_struct || GET_CODE (XEXP (x, 0)) == PLUS) 1147: && rtx_addr_varies_p (x)) 1148: return 0; 1149: /* A store in a fixed address clobbers overlapping references. */ 1150: for (i = loop_store_addrs_idx - 1; i >= 0; i--) 1.1.1.2 ! root 1151: if (addr_overlap_p (x, loop_store_addrs[i], loop_store_widths[i])) 1.1 root 1152: return 0; 1153: /* It's not invalidated by a store in memory 1154: but we must still verify the address is invariant. */ 1.1.1.2 ! root 1155: break; ! 1156: ! 1157: case ASM_OPERANDS: ! 1158: /* Don't mess with insns declared volatile. */ ! 1159: if (x->volatil) ! 1160: return 0; 1.1 root 1161: } 1162: 1163: fmt = GET_RTX_FORMAT (code); 1164: for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) 1165: { 1166: if (fmt[i] == 'e') 1167: { 1168: int tem = invariant_p (XEXP (x, i), n_times_set); 1169: if (tem == 0) 1170: return 0; 1171: if (tem == 2) 1172: conditional = 1; 1173: } 1.1.1.2 ! root 1174: else if (fmt[i] == 'E') ! 1175: { ! 1176: register int j; ! 1177: for (j = 0; j < XVECLEN (x, i); j++) ! 1178: { ! 1179: int tem = invariant_p (XVECEXP (x, i, j), n_times_set); ! 1180: if (tem == 0) ! 1181: return 0; ! 1182: if (tem == 2) ! 1183: conditional = 1; ! 1184: } ! 1185: ! 1186: } 1.1 root 1187: } 1188: 1189: return 1 + conditional; 1190: } 1191: 1192: /* Return 1 if OTHER (a mem ref) overlaps the area of memory 1193: which is SIZE bytes starting at BASE. */ 1194: 1195: int 1196: addr_overlap_p (other, base, size) 1197: rtx other; 1198: rtx base; 1199: int size; 1200: { 1201: int start = 0, end; 1202: 1203: if (GET_CODE (base) == CONST) 1204: base = XEXP (base, 0); 1205: if (GET_CODE (base) == PLUS 1206: && GET_CODE (XEXP (base, 1)) == CONST_INT) 1207: { 1208: start = INTVAL (XEXP (base, 1)); 1209: base = XEXP (base, 0); 1210: } 1211: 1212: end = start + size; 1213: return refers_to_mem_p (other, base, start, end); 1214: } 1.1.1.2 ! root 1215: ! 1216: /* Return 1 if all the insns in the loop that set REG ! 1217: are INSN and the immediately following insns, ! 1218: and if each of those insns sets REG in an invariant way ! 1219: according to TABLE (not counting uses of REG in them). ! 1220: ! 1221: We assume that INSN itself is the first set of REG ! 1222: and that its source is invariant. */ ! 1223: ! 1224: static int ! 1225: consec_sets_invariant_p (reg, insn, table) ! 1226: rtx reg, insn; ! 1227: short *table; ! 1228: { ! 1229: register rtx p = insn; ! 1230: register int regno = REGNO (reg); ! 1231: /* Number of sets we have to insist on finding after INSN. */ ! 1232: int count = table[regno] - 1; ! 1233: int old = table[regno]; ! 1234: ! 1235: table[regno] = 0; ! 1236: ! 1237: while (count > 0) ! 1238: { ! 1239: register enum rtx_code code; ! 1240: p = NEXT_INSN (p); ! 1241: code = GET_CODE (p); ! 1242: if (code == INSN && GET_CODE (PATTERN (p)) == SET ! 1243: && GET_CODE (SET_DEST (PATTERN (p))) == REG ! 1244: && REGNO (SET_DEST (PATTERN (p))) == regno ! 1245: && invariant_p (SET_SRC (PATTERN (p)), table)) ! 1246: count--; ! 1247: else if (code != NOTE) ! 1248: { ! 1249: table[regno] = old; ! 1250: return 0; ! 1251: } ! 1252: } ! 1253: ! 1254: table[regno] = old; ! 1255: return 1; ! 1256: } ! 1257: ! 1258: #if 0 ! 1259: /* I don't think this condition is sufficient to allow INSN ! 1260: to be moved, so we no longer test it. */ 1.1 root 1261: 1262: /* Return 1 if all insns in the basic block of INSN and following INSN 1263: that set REG are invariant according to TABLE. */ 1264: 1265: static int 1266: all_sets_invariant_p (reg, insn, table) 1267: rtx reg, insn; 1.1.1.2 ! root 1268: short *table; 1.1 root 1269: { 1270: register rtx p = insn; 1271: register int regno = REGNO (reg); 1272: 1273: while (1) 1274: { 1275: register enum rtx_code code; 1276: p = NEXT_INSN (p); 1277: code = GET_CODE (p); 1278: if (code == CODE_LABEL || code == JUMP_INSN) 1279: return 1; 1280: if (code == INSN && GET_CODE (PATTERN (p)) == SET 1281: && GET_CODE (SET_DEST (PATTERN (p))) == REG 1282: && REGNO (SET_DEST (PATTERN (p))) == regno) 1283: { 1284: if (!invariant_p (SET_SRC (PATTERN (p)), table)) 1285: return 0; 1286: } 1287: } 1288: } 1.1.1.2 ! root 1289: #endif /* 0 */ 1.1 root 1290: 1291: /* Increment N_TIMES_SET at the index of each register 1292: that is modified by an insn between FROM and TO. 1293: If the value of an element of N_TIMES_SET becomes 2 or more, 1294: do not keep incrementing it; all values >= 2 would be 1295: equivalent anyway, and this way we avoid danger of overflow. 1296: 1297: Store in *COUNT_PTR the number of actual instruction 1298: in the loop. We use this to decide what is worth moving out. */ 1299: 1300: /* last_set[n] is nonzero iff reg n has been set in the current basic block. 1301: In that case, it is the insn that last set reg n. */ 1302: 1303: static void 1304: count_loop_regs_set (from, to, n_times_set, may_not_move, count_ptr, nregs) 1305: register rtx from, to; 1306: short *n_times_set; 1307: char *may_not_move; 1308: int *count_ptr; 1309: int nregs; 1310: { 1311: register rtx *last_set = (rtx *) alloca (nregs * sizeof (rtx)); 1312: register rtx insn; 1313: register int count = 0; 1314: register rtx dest; 1315: 1316: bzero (last_set, nregs * sizeof (rtx)); 1317: for (insn = from; insn != to; insn = NEXT_INSN (insn)) 1318: { 1.1.1.2 ! root 1319: if (GET_CODE (insn) == CALL_INSN) ! 1320: { ! 1321: /* If a register is used as a subroutine address, ! 1322: don't allow this register's setting to be moved out of the loop. ! 1323: This condition is not at all logically correct ! 1324: but it averts a very common lossage pattern ! 1325: and creates lossage much less often. */ ! 1326: if (GET_CODE (PATTERN (insn)) == CALL ! 1327: && GET_CODE (XEXP (PATTERN (insn), 0)) == MEM ! 1328: && GET_CODE (XEXP (XEXP (PATTERN (insn), 0), 0)) == REG) ! 1329: { ! 1330: register int regno ! 1331: = REGNO (XEXP (XEXP (PATTERN (insn), 0), 0)); ! 1332: may_not_move[regno] = 1; ! 1333: } ! 1334: else if (GET_CODE (PATTERN (insn)) == SET ! 1335: && GET_CODE (SET_SRC (PATTERN (insn))) == CALL ! 1336: && GET_CODE (XEXP (SET_SRC (PATTERN (insn)), 0)) == MEM ! 1337: && GET_CODE (XEXP (XEXP (SET_SRC (PATTERN (insn)), 0), 0)) == REG) ! 1338: { ! 1339: register int regno ! 1340: = REGNO (XEXP (XEXP (SET_SRC (PATTERN (insn)), 0), 0)); ! 1341: may_not_move[regno] = 1; ! 1342: /* The call insn itself sets a reg, which cannot be moved. */ ! 1343: may_not_move[REGNO (SET_DEST (PATTERN (insn)))] = 1; ! 1344: n_times_set[REGNO (SET_DEST (PATTERN (insn)))]++; ! 1345: } ! 1346: } ! 1347: if (GET_CODE (insn) == INSN || GET_CODE (insn) == JUMP_INSN) 1.1 root 1348: { 1349: ++count; 1.1.1.2 ! root 1350: if (GET_CODE (PATTERN (insn)) == CLOBBER ! 1351: && GET_CODE (XEXP (PATTERN (insn), 0)) == REG) ! 1352: /* Don't move a reg that has an explicit clobber. ! 1353: We might do so sometimes, but it's not worth the pain. */ ! 1354: may_not_move[REGNO (XEXP (PATTERN (insn), 0))] = 1; ! 1355: else if (GET_CODE (PATTERN (insn)) == SET) 1.1 root 1356: { 1357: dest = SET_DEST (PATTERN (insn)); 1358: while (GET_CODE (dest) == SUBREG 1359: || GET_CODE (dest) == ZERO_EXTRACT 1360: || GET_CODE (dest) == SIGN_EXTRACT 1361: || GET_CODE (dest) == STRICT_LOW_PART) 1362: dest = XEXP (dest, 0); 1363: if (GET_CODE (dest) == REG) 1364: { 1365: register int regno = REGNO (dest); 1366: /* If this is the first setting of this reg 1367: in current basic block, and it was set before, 1368: it must be set in two basic blocks, so it cannot 1369: be moved out of the loop. */ 1370: if (n_times_set[regno] > 0 && last_set[regno] == 0) 1371: may_not_move[regno] = 1; 1372: /* If this is not first setting in current basic block, 1373: see if reg was used in between previous one and this. 1374: If so, neither one can be moved. */ 1375: if (last_set[regno] != 0 1376: && reg_used_between_p (dest, last_set[regno], insn)) 1377: may_not_move[regno] = 1; 1378: ++n_times_set[regno]; 1379: last_set[regno] = insn; 1380: } 1381: } 1382: else if (GET_CODE (PATTERN (insn)) == PARALLEL) 1383: { 1384: register int i; 1385: for (i = XVECLEN (PATTERN (insn), 0) - 1; i >= 0; i--) 1386: { 1387: register rtx x = XVECEXP (PATTERN (insn), 0, i); 1.1.1.2 ! root 1388: if (GET_CODE (x) == CLOBBER && GET_CODE (XEXP (x, 0)) == REG) ! 1389: /* Don't move a reg that has an explicit clobber. ! 1390: It's not worth the pain to try to do it correctly. */ ! 1391: may_not_move[REGNO (XEXP (x, 0))] = 1; 1.1 root 1392: if (GET_CODE (x) == SET) 1393: { 1394: dest = SET_DEST (x); 1395: while (GET_CODE (dest) == SUBREG 1396: || GET_CODE (dest) == ZERO_EXTRACT 1397: || GET_CODE (dest) == SIGN_EXTRACT 1398: || GET_CODE (dest) == STRICT_LOW_PART) 1399: dest = XEXP (dest, 0); 1400: if (GET_CODE (dest) == REG) 1401: { 1402: register int regno = REGNO (dest); 1403: ++n_times_set[regno]; 1404: may_not_move[regno] = 1; 1405: last_set[regno] = insn; 1406: } 1407: } 1408: } 1409: } 1410: } 1411: if (GET_CODE (insn) == CODE_LABEL || GET_CODE (insn) == JUMP_INSN) 1412: bzero (last_set, nregs * sizeof (rtx)); 1413: } 1414: *count_ptr = count; 1415: } 1416: 1417: /* Given a loop that is bounded by LOOP_START and LOOP_END 1418: and that is entered at SCAN_START, 1419: return 1 if the register set by insn INSN is used by 1420: any insn that precedes INSN in cyclic order starting 1421: from the loop entry point. */ 1422: 1423: static int 1424: loop_reg_used_before_p (insn, loop_start, scan_start, loop_end) 1425: rtx insn, loop_start, scan_start, loop_end; 1426: { 1427: rtx reg = SET_DEST (PATTERN (insn)); 1428: if (INSN_LUID (scan_start) > INSN_LUID (insn)) 1429: return (reg_used_between_p (reg, scan_start, loop_end) 1430: || reg_used_between_p (reg, loop_start, insn)); 1431: else 1432: return reg_used_between_p (reg, scan_start, insn); 1433: } 1.1.1.2 ! root 1434: ! 1435: /* Return nonzero if X is a division that might trap. */ ! 1436: ! 1437: static int ! 1438: may_trap_p (x) ! 1439: rtx x; ! 1440: { ! 1441: switch (GET_CODE (x)) ! 1442: { ! 1443: case DIV: ! 1444: case MOD: ! 1445: case UDIV: ! 1446: case UMOD: ! 1447: if (! CONSTANT_P (XEXP (x, 1)) ! 1448: && GET_CODE (XEXP (x, 1)) != CONST_DOUBLE) ! 1449: return 1; ! 1450: } ! 1451: return 0; ! 1452: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.