![[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. ! 2: Copyright (C) 1987 Free Software Foundation, Inc. ! 3: ! 4: This file is part of GNU CC. ! 5: ! 6: GNU CC is distributed in the hope that it will be useful, ! 7: but WITHOUT ANY WARRANTY. No author or distributor ! 8: accepts responsibility to anyone for the consequences of using it ! 9: or for whether it serves any particular purpose or works at all, ! 10: unless he says so in writing. Refer to the GNU CC General Public ! 11: License for full details. ! 12: ! 13: Everyone is granted permission to copy, modify and redistribute ! 14: GNU CC, but only under the conditions described in the ! 15: GNU CC General Public License. A copy of this license is ! 16: supposed to have been given to you along with GNU CC so you ! 17: can know your rights and responsibilities. It should be in a ! 18: file named COPYING. Among other things, the copyright notice ! 19: and this notice must be preserved on all copies. */ ! 20: ! 21: ! 22: /* This 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" ! 43: ! 44: /* Vector mapping INSN_UIDs to luids. ! 45: The luids are like uids but increase monononically always. ! 46: We use them to see whether a jump comes from outside a given loop. */ ! 47: ! 48: static short *uid_luid; ! 49: ! 50: /* Get the luid of an insn. */ ! 51: ! 52: #define INSN_LUID(INSN) (uid_luid[INSN_UID (INSN)]) ! 53: ! 54: /* 1 + largest uid of any insn. */ ! 55: ! 56: static int max_uid; ! 57: ! 58: /* 1 + luid of last insn. */ ! 59: ! 60: static int max_luid; ! 61: ! 62: /* Nonzero if somewhere in the current loop ! 63: there is either a subroutine call, ! 64: or a store into a memory address that is not fixed, ! 65: or a store in a BLKmode memory operand, ! 66: or too many different fixed addresses stored in ! 67: to record them all in `loop_store_addrs'. ! 68: ! 69: In any of these cases, no memory location can be regarded ! 70: as invariant. */ ! 71: ! 72: static int unknown_address_altered; ! 73: ! 74: /* Nonzero if somewhere in the current loop there is a store ! 75: into a memory address that is not fixed but is known to be ! 76: part of an aggregate. ! 77: ! 78: In this case, no memory reference in an aggregate may be ! 79: considered invariant. */ ! 80: ! 81: static int unknown_aggregate_altered; ! 82: ! 83: /* Nonzero if somewhere in the current loop there is a store ! 84: into a memory address other than a fixed address not in an aggregate. ! 85: ! 86: In this case, no memory reference in an aggregate at a varying address ! 87: may be considered invariant. */ ! 88: ! 89: static int fixed_aggregate_altered; ! 90: ! 91: /* Nonzero if there is a subroutine call in the current loop. ! 92: (unknown_address_altered is also nonzero in this case.) */ ! 93: ! 94: static int loop_has_call; ! 95: ! 96: /* Array of fixed memory addresses that are stored in this loop. ! 97: If there are too many to fit here, ! 98: we just turn on unknown_address_altered. */ ! 99: ! 100: #define NUM_STORES 10 ! 101: static rtx loop_store_addrs[NUM_STORES]; ! 102: static int loop_store_widths[NUM_STORES]; ! 103: ! 104: /* Index of first available slot in above array. */ ! 105: static int loop_store_addrs_idx; ! 106: ! 107: /* During the analysis of a loop, a chain of `struct movable's ! 108: is made to record all the movable insns found. ! 109: Then the entire chain can be scanned to decide which to move. */ ! 110: ! 111: struct movable ! 112: { ! 113: rtx insn; /* A movable insn */ ! 114: int regno; /* The register it sets */ ! 115: short lifetime; /* lifetime of that register; ! 116: may be adjusted when matching movables ! 117: that load the same value are found. */ ! 118: unsigned int cond : 1; /* 1 if only conditionally movable */ ! 119: unsigned int force : 1; /* 1 means MUST move this insn */ ! 120: unsigned int global : 1; /* 1 means reg is live outside this loop */ ! 121: unsigned int dont : 1; /* 1 inhibits further processing of this */ ! 122: struct movable *match; /* First entry for same value */ ! 123: struct movable *forces; /* An insn that must be moved if this is */ ! 124: struct movable *next; ! 125: }; ! 126: ! 127: static rtx verify_loop (); ! 128: static int invariant_p (); ! 129: static int can_jump_into_range_p (); ! 130: static void count_loop_regs_set (); ! 131: static void note_addr_stored (); ! 132: static int loop_reg_used_before_p (); ! 133: static void constant_high_bytes (); ! 134: static void scan_loop (); ! 135: static rtx replace_regs (); ! 136: ! 137: /* Entry point of this file. Perform loop optimization ! 138: on the current function. F is the first insn of the function ! 139: and NREGS is the number of register numbers used. */ ! 140: ! 141: int ! 142: loop_optimize (f, nregs) ! 143: /* f is the first instruction of a chain of insns for one function */ ! 144: rtx f; ! 145: /* nregs is the total number of registers used in it */ ! 146: int nregs; ! 147: { ! 148: register rtx insn; ! 149: register int i; ! 150: rtx end; ! 151: rtx last_insn; ! 152: ! 153: init_recog (); ! 154: ! 155: /* First find the last real insn, and count the number of insns, ! 156: and assign insns their suids. */ ! 157: ! 158: for (insn = f, i = 0; insn; insn = NEXT_INSN (insn)) ! 159: if (INSN_UID (insn) > i) ! 160: i = INSN_UID (insn); ! 161: ! 162: max_uid = i + 1; ! 163: uid_luid = (short *) alloca ((i + 1) * sizeof (short)); ! 164: bzero (uid_luid, (i + 1) * sizeof (short)); ! 165: ! 166: /* Compute the mapping from uids to luids. ! 167: LUIDs are numbers assigned to insns, like uids, ! 168: except that luids increase monotonically through the code. */ ! 169: ! 170: for (insn = f, i = 0; insn; insn = NEXT_INSN (insn)) ! 171: { ! 172: last_insn = insn; ! 173: INSN_LUID (insn) = ++i; ! 174: } ! 175: ! 176: max_luid = i; ! 177: ! 178: /* Don't leave gaps in uid_luid for insns that have been ! 179: deleted. It is possible that the first or last insn ! 180: using some register has been deleted by cross-jumping. ! 181: Make sure that uid_luid for that former insn's uid ! 182: points to the general area where that insn used to be. */ ! 183: for (i = 0; i < max_uid; i++) ! 184: if (uid_luid[i] == 0) ! 185: uid_luid[i] = uid_luid[i - 1]; ! 186: ! 187: /* Find and process each loop. ! 188: We scan from the end, and process each loop when its start is seen, ! 189: so we process innermost loops first. */ ! 190: ! 191: for (insn = last_insn; insn; insn = PREV_INSN (insn)) ! 192: if (GET_CODE (insn) == NOTE ! 193: && NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG ! 194: /* Make sure it really is a loop -- no jumps in from outside. */ ! 195: && (end = verify_loop (f, insn))) ! 196: scan_loop (insn, end, nregs); ! 197: } ! 198: ! 199: /* Optimize one loop whose start is LOOP_START and end is END. ! 200: LOOP_START is the NOTE_INSN_LOOP_BEG and END is the matching ! 201: NOTE_INSN_LOOP_END. */ ! 202: ! 203: static void ! 204: scan_loop (loop_start, end, nregs) ! 205: rtx loop_start, end; ! 206: int nregs; ! 207: { ! 208: register int i; ! 209: register rtx p = NEXT_INSN (loop_start); ! 210: /* 1 if we are scanning insns that could be executed zero times. */ ! 211: int maybe_never = 0; ! 212: /* For a rotated loop that is entered near the bottom, ! 213: this is the label at the top. Otherwise it is zero. */ ! 214: rtx loop_top = 0; ! 215: /* Jump insn that enters the loop, or 0 if control drops in. */ ! 216: rtx loop_entry_jump = 0; ! 217: /* Place in the loop where control enters. */ ! 218: rtx scan_start; ! 219: /* Number of insns in the loop. */ ! 220: int insn_count; ! 221: int tem; ! 222: /* Indexed by register number, contains the number of times the reg ! 223: is set during the loop being scanned, or -1 if the insns that set it ! 224: have all been scanned as candidates for being moved out of the loop. ! 225: 0 indicates an invariant register; -1 a conditionally invariant one. */ ! 226: short *n_times_set; ! 227: /* Indexed by register number, contains the number of times the reg ! 228: was set during the loop being scanned, not counting changes due ! 229: to moving these insns out of the loop. */ ! 230: short *n_times_used; ! 231: /* Indexed by register number, contains 1 for a register whose ! 232: assignments may not be moved out of the loop. */ ! 233: char *may_not_move; ! 234: /* Chain describing insns movable in current loop. */ ! 235: struct movable *movables = 0; ! 236: /* Last element in `movables' -- so we can add elements at the end. */ ! 237: struct movable *last_movable = 0; ! 238: /* Ratio of extra register life span we can justify ! 239: for saving an instruction. More if loop doesn't call subroutines ! 240: since in that case saving an insn makes more difference ! 241: and more registers are available. */ ! 242: int threshold = loop_has_call ? 15 : 30; ! 243: ! 244: n_times_set = (short *) alloca (nregs * sizeof (short)); ! 245: n_times_used = (short *) alloca (nregs * sizeof (short)); ! 246: may_not_move = (char *) alloca (nregs); ! 247: ! 248: /* Determine whether this loop starts with a jump down ! 249: to a test at the end. */ ! 250: while (p != end ! 251: && GET_CODE (p) != CODE_LABEL && GET_CODE (p) != JUMP_INSN) ! 252: p = NEXT_INSN (p); ! 253: ! 254: /* "Loop" contains neither jumps nor labels; ! 255: it must have been a dummy. Think no more about it. */ ! 256: if (p == end) ! 257: return; ! 258: ! 259: /* If loop has a jump before the first label, ! 260: the true entry is the target of that jump. ! 261: Start scan from there. ! 262: But record in LOOP_TOP the place where the end-test jumps ! 263: back to so we can scan that after the end of the loop. */ ! 264: if (GET_CODE (p) == JUMP_INSN) ! 265: { ! 266: loop_entry_jump = p; ! 267: loop_top = NEXT_INSN (p); ! 268: /* Loop entry will never be a conditional jump. ! 269: If we see one, this must not be a real loop. */ ! 270: if (GET_CODE (loop_top) != BARRIER) ! 271: return; ! 272: while (GET_CODE (loop_top) != CODE_LABEL) ! 273: loop_top = NEXT_INSN (loop_top); ! 274: p = JUMP_LABEL (p); ! 275: /* Check to see whether the jump actually ! 276: jumps out of the loop (meaning it's no loop). ! 277: This case can happen for things like ! 278: do {..} while (0). */ ! 279: if (INSN_LUID (p) < INSN_LUID (loop_start) ! 280: || INSN_LUID (p) >= INSN_LUID (end)) ! 281: return; ! 282: } ! 283: ! 284: /* Count number of times each reg is set during this loop. ! 285: Set MAY_NOT_MOVE[I] if it is not safe to move out ! 286: the setting of register I. */ ! 287: ! 288: bzero (n_times_set, nregs * sizeof (short)); ! 289: bzero (may_not_move, nregs); ! 290: count_loop_regs_set (loop_start, end, n_times_set, may_not_move, ! 291: &insn_count, nregs); ! 292: for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) ! 293: may_not_move[i] = 1, n_times_set[i] = 1; ! 294: bcopy (n_times_set, n_times_used, nregs * sizeof (short)); ! 295: ! 296: /* Scan through the loop finding insns that are safe to move. ! 297: In each such insn, store QImode as the mode, to mark it. ! 298: Then set n_times_set to -1 for the reg being set, so that ! 299: this reg will be considered invariant for subsequent insns. ! 300: We consider whether subsequent insns use the reg ! 301: in deciding whether it is worth actually moving. ! 302: ! 303: MAYBE_NEVER is nonzero if we have passed a conditional jump insn ! 304: and therefore it is possible that the insns we are scanning ! 305: would never be executed. At such times, we must make sure ! 306: that it is safe to execute the insn once instead of zero times. ! 307: When MAYBE_NEVER is 0, all insns will be executed at least once ! 308: so that is not a problem. */ ! 309: ! 310: scan_start = p; ! 311: while (1) ! 312: { ! 313: p = NEXT_INSN (p); ! 314: /* At end of a straight-in loop, we are done. ! 315: At end of a loop entered at the bottom, scan the top. */ ! 316: if (p == scan_start) ! 317: break; ! 318: if (p == end) ! 319: { ! 320: if (loop_top != 0) ! 321: p = NEXT_INSN (loop_top); ! 322: else ! 323: break; ! 324: if (p == scan_start) ! 325: break; ! 326: } ! 327: if (GET_CODE (p) == INSN ! 328: && GET_CODE (PATTERN (p)) == SET ! 329: && GET_CODE (SET_DEST (PATTERN (p))) == REG ! 330: && ! may_not_move[REGNO (SET_DEST (PATTERN (p)))]) ! 331: { ! 332: /* If this register is used or set outside the loop, ! 333: then we can move it only if we know this insn is ! 334: executed exactly once per iteration, ! 335: and we can check all the insns executed before it ! 336: to make sure none of them used the value that ! 337: was lying around at entry to the loop. */ ! 338: if ((uid_luid[regno_last_uid[REGNO (SET_DEST (PATTERN (p)))]] > INSN_LUID (end) ! 339: || uid_luid[regno_first_uid[REGNO (SET_DEST (PATTERN (p)))]] < INSN_LUID (loop_start)) ! 340: && (maybe_never ! 341: || loop_reg_used_before_p (p, loop_start, scan_start, end))) ! 342: ; ! 343: else if ((tem = invariant_p (SET_SRC (PATTERN (p)), n_times_set)) ! 344: && (n_times_set[REGNO (SET_DEST (PATTERN (p)))] == 1 ! 345: || all_sets_invariant_p (SET_DEST (PATTERN (p)), ! 346: p, n_times_set))) ! 347: { ! 348: register struct movable *m; ! 349: register int regno = REGNO (SET_DEST (PATTERN (p))); ! 350: m = (struct movable *) alloca (sizeof (struct movable)); ! 351: m->next = 0; ! 352: m->insn = p; ! 353: m->force = 0; ! 354: m->dont = 0; ! 355: m->forces = 0; ! 356: m->regno = regno; ! 357: m->cond = (tem > 1); ! 358: m->global = (uid_luid[regno_last_uid[regno]] > INSN_LUID (end) ! 359: || uid_luid[regno_first_uid[regno]] < INSN_LUID (loop_start)); ! 360: m->match = 0; ! 361: m->lifetime = (uid_luid[regno_last_uid[regno]] ! 362: - uid_luid[regno_first_uid[regno]]); ! 363: n_times_set[regno] = -1; ! 364: /* Add M to the end of the chain MOVABLES. */ ! 365: if (movables == 0) ! 366: movables = m; ! 367: else ! 368: last_movable->next = m; ! 369: last_movable = m; ! 370: } ! 371: #ifdef SLOW_ZERO_EXTEND ! 372: /* If this register is set only once, and by zero-extending, ! 373: that means its high bytes are constant. ! 374: So clear them outside the loop and within the loop ! 375: just load the low bytes. ! 376: We must check that the machine has an instruction to do so. ! 377: Also, if the value loaded into the register ! 378: depends on the same register, this cannot be done. */ ! 379: ! 380: else if (GET_CODE (SET_SRC (PATTERN (p))) == ZERO_EXTEND ! 381: && !reg_mentioned_p (SET_DEST (PATTERN (p)), ! 382: SET_SRC (PATTERN (p)))) ! 383: { ! 384: register int regno = REGNO (SET_DEST (PATTERN (p))); ! 385: if ((threshold ! 386: * (uid_luid[regno_last_uid[regno]] ! 387: - uid_luid[regno_first_uid[regno]])) ! 388: >= insn_count) ! 389: constant_high_bytes (p, loop_start); ! 390: } ! 391: #endif /* SLOW_ZERO_EXTEND */ ! 392: } ! 393: /* Past a label or a jump, we get to insns for which we ! 394: can't count on whether or how many times they will be ! 395: executed during each iteration. Therefore, we can ! 396: only move out sets of trivial variables ! 397: (those not used after the loop). */ ! 398: else if (GET_CODE (p) == CODE_LABEL || GET_CODE (p) == JUMP_INSN) ! 399: maybe_never = 1; ! 400: } ! 401: ! 402: /* For each movable insn, see if the reg that it loads ! 403: leads when it dies right into another conditionally movable insn. */ ! 404: { ! 405: register struct movable *m, *m1; ! 406: for (m1 = movables; m1; m1 = m1->next) ! 407: { ! 408: int regno = m1->regno; ! 409: for (m = m1->next; m; m = m->next) ! 410: if (INSN_UID (m->insn) == regno_last_uid[regno]) ! 411: break; ! 412: if (m != 0 && SET_SRC (PATTERN (m->insn)) == SET_DEST (PATTERN (m1->insn))) ! 413: m = 0; ! 414: m1->forces = m; ! 415: } ! 416: } ! 417: ! 418: /* See if there are multiple movable insns that load the same value. ! 419: If there are, make all but the first point at the first one ! 420: through the `match' field, and add the priorities of them ! 421: all together as the priority of the first. */ ! 422: { ! 423: register struct movable *m; ! 424: rtx *reg_map = (rtx *) alloca (nregs * sizeof (rtx)); ! 425: char *matched_regs = (char *) alloca (nregs); ! 426: ! 427: bzero (reg_map, nregs * sizeof (rtx)); ! 428: ! 429: for (m = movables; m; m = m->next) ! 430: if (m->match == 0 && n_times_used[m->regno] == 1 && !m->global ! 431: && (! movables->cond ! 432: || 1 == invariant_p (SET_SRC (PATTERN (movables->insn)), n_times_set))) ! 433: { ! 434: register struct movable *m1; ! 435: int matched = 0; ! 436: int lifetime = m->lifetime; ! 437: int times_used = n_times_used[m->regno]; ! 438: ! 439: if (m->forces != 0) times_used++; ! 440: ! 441: bzero (matched_regs, nregs); ! 442: matched_regs[m->regno] = 1; ! 443: ! 444: for (m1 = m->next; m1; m1 = m1->next) ! 445: { ! 446: if (m1->match == 0 && n_times_used[m1->regno] == 1 ! 447: && !m1->global ! 448: /* Perform already-scheduled replacements ! 449: on M1's insn before comparing them! */ ! 450: && (replace_regs (PATTERN (m1->insn), reg_map), ! 451: ((GET_CODE (SET_SRC (PATTERN (m1->insn))) == REG ! 452: && matched_regs[REGNO (SET_SRC (PATTERN (m1->insn)))]) ! 453: || rtx_equal_p (SET_SRC (PATTERN (m->insn)), ! 454: SET_SRC (PATTERN (m1->insn)))))) ! 455: { ! 456: lifetime += m1->lifetime; ! 457: times_used += n_times_used[m1->regno]; ! 458: if (m1->forces != 0) times_used++; ! 459: m1->match = m; ! 460: matched_regs[m1->regno] = 1; ! 461: matched = 1; ! 462: } ! 463: } ! 464: ! 465: /* If the movable insn M has others that match it ! 466: and all together they merit being moved, ! 467: go through the others now and replace their registers ! 468: with M's register. Mark the others with the `dont' field ! 469: and do all processing on them now. */ ! 470: if (matched ! 471: && ((threshold * times_used * lifetime) >= insn_count ! 472: || m->force ! 473: || n_times_set[m->regno] == 0)) ! 474: { ! 475: m->force = 1; ! 476: m->lifetime = lifetime; ! 477: ! 478: for (m1 = m->next; m1; m1 = m1->next) ! 479: if (m1->match == m) ! 480: { ! 481: /* Schedule the reg loaded by M1 ! 482: for replacement so that shares the reg of M. */ ! 483: reg_map[m1->regno] = SET_DEST (PATTERN (m->insn)); ! 484: /* Get rid of the replaced reg ! 485: and prevent further processing of it. */ ! 486: m1->dont = 1; ! 487: delete_insn (m1->insn); ! 488: } ! 489: } ! 490: } ! 491: /* Go through all the instructions in the loop, making ! 492: all the register substitutions scheduled above. */ ! 493: for (p = loop_start; p != end; p = NEXT_INSN (p)) ! 494: if (GET_CODE (p) == INSN || GET_CODE (p) == JUMP_INSN ! 495: || GET_CODE (p) == CALL_INSN) ! 496: replace_regs (PATTERN (p), reg_map); ! 497: } ! 498: ! 499: /* Now consider each movable insn to decide whether it is worth moving. */ ! 500: ! 501: { ! 502: register struct movable *m; ! 503: for (m = movables; m; m = m->next) ! 504: if (!m->dont ! 505: && (! m->cond ! 506: || 1 == invariant_p (SET_SRC (PATTERN (m->insn)), n_times_set))) ! 507: /* We have an insn that is safe to move. */ ! 508: { ! 509: register int regno; ! 510: ! 511: p = m->insn; ! 512: regno = m->regno; ! 513: if (m->forces != 0) ! 514: n_times_used[regno]++; ! 515: ! 516: /* Don't move something out of the loop ! 517: if that would cause it to be live over a range ! 518: THRESHOLD times as long. That means the loop is so big ! 519: that moving won't speed things up much, ! 520: and it is liable to make register usage worse. */ ! 521: if (m->force ! 522: || (threshold * n_times_used[regno] * m->lifetime) >= insn_count ! 523: || n_times_set[regno] == 0) ! 524: { ! 525: rtx i1 = emit_insn_before (PATTERN (p), loop_start); ! 526: if (CONSTANT_ADDRESS_P (SET_SRC (PATTERN (p)))) ! 527: REG_NOTES (i1) ! 528: = gen_rtx (EXPR_LIST, REG_CONST, ! 529: SET_DEST (PATTERN (p)), REG_NOTES (i1)); ! 530: delete_insn (p); ! 531: n_times_set[regno] = 0; ! 532: /* Signal any other movables that match this one ! 533: that they should be moved too. */ ! 534: m->force = 1; ! 535: /* Signal any conditionally movable computation ! 536: that uses this one that it should be moved too. */ ! 537: if (m->forces != 0) ! 538: m->forces->force = 1; ! 539: } ! 540: } ! 541: } ! 542: ! 543: /* Now maybe duplicate the end-test before the loop. */ ! 544: if (loop_entry_jump != 0) ! 545: { ! 546: rtx endtestjump; ! 547: p = scan_start; ! 548: while (GET_CODE (p) != INSN && GET_CODE (p) != JUMP_INSN ! 549: && GET_CODE (p) != CALL_INSN) ! 550: p = NEXT_INSN (p); ! 551: endtestjump = next_real_insn (p); ! 552: /* Check that we (1) enter at a compare insn and (2) ! 553: the insn (presumably a jump) following that compare ! 554: is the last in the loop and jumps back to the loop beginning. */ ! 555: if (GET_CODE (PATTERN (p)) == SET ! 556: && SET_DEST (PATTERN (p)) == cc0_rtx ! 557: && endtestjump == prev_real_insn (end) ! 558: && prev_real_insn (JUMP_LABEL (endtestjump)) == loop_entry_jump) ! 559: { ! 560: rtx newlab; ! 561: ! 562: /* Ok, duplicate that test before loop entry. */ ! 563: emit_insn_before (copy_rtx (PATTERN (p)), loop_entry_jump); ! 564: /* Make a new entry-jump (before the original) ! 565: that uses the opposite condition and jumps in ! 566: after this conitional jump. */ ! 567: newlab = gen_label_rtx (); ! 568: emit_label_after (newlab, endtestjump); ! 569: emit_jump_insn_before (copy_rtx (PATTERN (endtestjump)), loop_entry_jump); ! 570: JUMP_LABEL (PREV_INSN (loop_entry_jump)) = JUMP_LABEL (endtestjump); ! 571: LABEL_NUSES (JUMP_LABEL (endtestjump))++; ! 572: invert_jump (PREV_INSN (loop_entry_jump), newlab); ! 573: /* Delete the original entry-jump. */ ! 574: delete_insn (loop_entry_jump); ! 575: } ! 576: } ! 577: } ! 578: ! 579: /* Throughout the rtx X, replace many registers according to REG_MAP. ! 580: Return the replacement for X (which may be X with altered contents). ! 581: REG_MAP[R] is the replacement for register R, or 0 for don't replace. */ ! 582: ! 583: static rtx ! 584: replace_regs (x, reg_map) ! 585: rtx x; ! 586: rtx *reg_map; ! 587: { ! 588: register RTX_CODE code = GET_CODE (x); ! 589: register int i; ! 590: register char *fmt; ! 591: ! 592: switch (code) ! 593: { ! 594: case PC: ! 595: case CC0: ! 596: case CONST_INT: ! 597: case CONST_DOUBLE: ! 598: case CONST: ! 599: case SYMBOL_REF: ! 600: case LABEL_REF: ! 601: return x; ! 602: ! 603: case REG: ! 604: if (reg_map[REGNO (x)] != 0) ! 605: return reg_map[REGNO (x)]; ! 606: return x; ! 607: } ! 608: ! 609: fmt = GET_RTX_FORMAT (code); ! 610: for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) ! 611: { ! 612: if (fmt[i] == 'e') ! 613: XEXP (x, i) = replace_regs (XEXP (x, i), reg_map); ! 614: if (fmt[i] == 'E') ! 615: { ! 616: register int j; ! 617: for (j = 0; j < XVECLEN (x, i); j++) ! 618: XVECEXP (x, i, j) = replace_regs (XVECEXP (x, i, j), reg_map); ! 619: } ! 620: } ! 621: return x; ! 622: } ! 623: ! 624: /* P is an instruction that sets a register to the result of a ZERO_EXTEND. ! 625: Replace it with an instruction to load just the low bytes ! 626: if the machine supports such an instruction, ! 627: and insert above LOOP_START an instruction to clear the register. */ ! 628: ! 629: static void ! 630: constant_high_bytes (p, loop_start) ! 631: rtx p, loop_start; ! 632: { ! 633: register rtx new; ! 634: register int insn_code_number; ! 635: ! 636: /* Try to change (SET (REG ...) (ZERO_EXTEND (..:B ...))) ! 637: to (SET (STRICT_LOW_PART (SUBREG:B (REG...))) ...). */ ! 638: ! 639: new = gen_rtx (SET, VOIDmode, ! 640: gen_rtx (STRICT_LOW_PART, VOIDmode, ! 641: gen_rtx (SUBREG, GET_MODE (XEXP (SET_SRC (PATTERN (p)), 0)), ! 642: SET_DEST (PATTERN (p)), ! 643: 0)), ! 644: XEXP (SET_SRC (PATTERN (p)), 0)); ! 645: insn_code_number = recog (new, p); ! 646: ! 647: if (insn_code_number) ! 648: { ! 649: register int i; ! 650: ! 651: /* Clear destination register before the loop. */ ! 652: emit_insn_before (gen_rtx (SET, VOIDmode, ! 653: SET_DEST (PATTERN (p)), ! 654: const0_rtx), ! 655: loop_start); ! 656: ! 657: /* Inside the loop, just load the low part. */ ! 658: PATTERN (p) = new; ! 659: } ! 660: } ! 661: ! 662: /* Verify that the ostensible loop starting at START ! 663: really is a loop: nothing jumps into it from outside. ! 664: Return the marker for the end of the loop, or zero if not a real loop. ! 665: ! 666: Also set the variables `unknown_*_altered' and `loop_has_call', ! 667: and fill in the array `loop_store_addrs'. */ ! 668: ! 669: static rtx ! 670: verify_loop (f, start) ! 671: rtx f, start; ! 672: { ! 673: register int level = 1; ! 674: register rtx insn, end; ! 675: ! 676: /* First find the LOOP_END that matches. ! 677: Also check each insn for storing in memory and record where. */ ! 678: ! 679: unknown_address_altered = 0; ! 680: unknown_aggregate_altered = 0; ! 681: fixed_aggregate_altered = 0; ! 682: loop_has_call = 0; ! 683: loop_store_addrs_idx = 0; ! 684: ! 685: for (insn = NEXT_INSN (start); level > 0; insn = NEXT_INSN (insn)) ! 686: { ! 687: if (insn == 0) ! 688: abort (); ! 689: if (GET_CODE (insn) == NOTE) ! 690: { ! 691: if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG) ! 692: ++level; ! 693: else if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END) ! 694: --level; ! 695: } ! 696: else if (GET_CODE (insn) == CALL_INSN) ! 697: { ! 698: unknown_address_altered = 1; ! 699: loop_has_call = 1; ! 700: } ! 701: else if (! unknown_address_altered) ! 702: { ! 703: if (GET_CODE (insn) == INSN || GET_CODE (insn) == JUMP_INSN) ! 704: note_stores (PATTERN (insn), note_addr_stored); ! 705: } ! 706: } ! 707: ! 708: end = insn; ! 709: ! 710: /* Now scan all jumps in the function and see if any of them can ! 711: reach a label within the range of the loop. */ ! 712: ! 713: for (insn = f; insn; insn = NEXT_INSN (insn)) ! 714: if (GET_CODE (insn) == JUMP_INSN ! 715: /* Don't get fooled by jumps inserted by loop-optimize. ! 716: They don't have valid LUIDs, and they never jump into loops. */ ! 717: && INSN_UID (insn) < max_uid ! 718: && (INSN_LUID (insn) < INSN_LUID (start) ! 719: || INSN_LUID (insn) > INSN_LUID (end)) ! 720: /* We have a jump that is outside the loop. ! 721: Does it jump into the loop? */ ! 722: && can_jump_into_range_p (PATTERN (insn), ! 723: INSN_LUID (start), INSN_LUID (end))) ! 724: return 0; ! 725: ! 726: #if 0 ! 727: /* Now scan all labels between them and check for any jumps from outside. ! 728: This uses the ref-chains set up by find_basic_blocks. ! 729: This code is not used because it's more convenient for other reasons ! 730: to do the loop optimization before find_basic_blocks. */ ! 731: ! 732: for (insn = start; insn != end; insn = NEXT_INSN (insn)) ! 733: if (GET_CODE (insn) == CODE_LABEL) ! 734: { ! 735: register rtx y; ! 736: for (y = LABEL_REFS (insn); y != insn; y = LABEL_NEXTREF (y)) ! 737: if (INSN_LUID (CONTAINING_INSN (y)) < INSN_LUID (start) ! 738: || INSN_LUID (CONTAINING_INSN (y)) > INSN_LUID (end)) ! 739: return 0; ! 740: } ! 741: #endif ! 742: ! 743: return end; ! 744: } ! 745: ! 746: /* Return 1 if somewhere in X is a LABEL_REF to a label ! 747: located between BEG and END. */ ! 748: ! 749: static int ! 750: can_jump_into_range_p (x, beg, end) ! 751: rtx x; ! 752: int beg, end; ! 753: { ! 754: register RTX_CODE code = GET_CODE (x); ! 755: register int i; ! 756: register char *fmt; ! 757: ! 758: if (code == LABEL_REF) ! 759: { ! 760: register int luid = INSN_LUID (XEXP (x, 0)); ! 761: return luid > beg && luid < end; ! 762: } ! 763: ! 764: fmt = GET_RTX_FORMAT (code); ! 765: for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) ! 766: { ! 767: if (fmt[i] == 'e') ! 768: { ! 769: if (can_jump_into_range_p (XEXP (x, i), beg, end)) ! 770: return 1; ! 771: } ! 772: else if (fmt[i] == 'E') ! 773: { ! 774: register int j; ! 775: for (j = 0; j < XVECLEN (x, i); j++) ! 776: if (can_jump_into_range_p (XVECEXP (x, i, j), beg, end)) ! 777: return 1; ! 778: } ! 779: } ! 780: ! 781: return 0; ! 782: } ! 783: ! 784: /* Record that a memory reference X is being set. */ ! 785: ! 786: static void ! 787: note_addr_stored (x) ! 788: rtx x; ! 789: { ! 790: rtx addr; ! 791: if (x == 0 || GET_CODE (x) != MEM) ! 792: return; ! 793: if (rtx_addr_varies_p (x)) ! 794: { ! 795: if (GET_CODE (XEXP (x, 0)) == PLUS) ! 796: unknown_aggregate_altered = 1; ! 797: else ! 798: unknown_address_altered = 1; ! 799: } ! 800: else if (GET_MODE (x) == BLKmode) ! 801: unknown_address_altered = 1; ! 802: else ! 803: { ! 804: register int i; ! 805: register rtx addr = XEXP (x, 0); ! 806: ! 807: if (x->in_struct) ! 808: fixed_aggregate_altered = 1; ! 809: for (i = 0; i < loop_store_addrs_idx; i++) ! 810: if (rtx_equal_p (loop_store_addrs[i], addr)) ! 811: { ! 812: if (loop_store_widths[i] < GET_MODE_SIZE (GET_MODE (x))) ! 813: loop_store_widths[i] = GET_MODE_SIZE (GET_MODE (x)); ! 814: break; ! 815: } ! 816: if (i == NUM_STORES) ! 817: unknown_address_altered = 1; ! 818: else if (i == loop_store_addrs_idx) ! 819: { ! 820: loop_store_widths[i] == GET_MODE_SIZE (GET_MODE (x)); ! 821: loop_store_addrs[loop_store_addrs_idx++] = addr; ! 822: } ! 823: } ! 824: } ! 825: ! 826: /* Return nonzero if the rtx X is invariant over the current loop. ! 827: N_TIMES_SET is a vector whose element I is nonzero if register I ! 828: is set during the loop. ! 829: ! 830: The value is 2 if we refer to something only conditionally invariant. ! 831: ! 832: If `unknown_address_altered' is nonzero, no memory ref is invariant. ! 833: Otherwise if `unknown_aggregate_altered' is nonzero, ! 834: a memory ref is invariant if it is not part of an aggregate ! 835: and its address is fixed and not in `loop_store_addrs'. ! 836: Otherwise if `fixed_aggregate_altered' is nonzero, ! 837: a memory ref is invariant ! 838: if its address is fixed and not in `loop_store_addrs'. ! 839: Otherwise, a memory ref is invariant if its address is fixed and not in ! 840: `loop_store_addrs' or if it is not an aggregate. */ ! 841: ! 842: static int ! 843: invariant_p (x, n_times_set) ! 844: register rtx x; ! 845: short *n_times_set; ! 846: { ! 847: register int i; ! 848: register RTX_CODE code = GET_CODE (x); ! 849: register char *fmt; ! 850: int conditional = 0; ! 851: ! 852: switch (code) ! 853: { ! 854: case CONST_INT: ! 855: case CONST_DOUBLE: ! 856: case SYMBOL_REF: ! 857: case LABEL_REF: ! 858: case CONST: ! 859: case UNCHANGING: ! 860: return 1; ! 861: ! 862: case PC: ! 863: case VOLATILE: ! 864: case CC0: ! 865: return 0; ! 866: ! 867: case REG: ! 868: if (n_times_set[REGNO (x)] == -1) ! 869: return 2; ! 870: return n_times_set[REGNO (x)] == 0; ! 871: ! 872: case MEM: ! 873: /* A store in a varying-address scalar (or a subroutine call) ! 874: could clobber anything in memory. */ ! 875: if (unknown_address_altered) ! 876: return 0; ! 877: /* A store in a varying-address aggregate component ! 878: could clobber anything except a scalar with a fixed address. */ ! 879: if (unknown_aggregate_altered ! 880: && ((x->in_struct || GET_CODE (XEXP (x, 0)) == PLUS) ! 881: || rtx_addr_varies_p (x))) ! 882: return 0; ! 883: /* A store in a fixed-address aggregate component ! 884: could clobber anything whose address is not fixed, ! 885: even an aggregate component. */ ! 886: if (fixed_aggregate_altered ! 887: && rtx_addr_varies_p (x)) ! 888: return 0; ! 889: /* Any store could clobber a varying-address scalar. */ ! 890: if (loop_store_addrs_idx ! 891: && !(x->in_struct || GET_CODE (XEXP (x, 0)) == PLUS) ! 892: && rtx_addr_varies_p (x)) ! 893: return 0; ! 894: /* A store in a fixed address clobbers overlapping references. */ ! 895: for (i = loop_store_addrs_idx - 1; i >= 0; i--) ! 896: if (addr_overlap_p (XEXP (x, 0), loop_store_addrs[i], ! 897: loop_store_widths[i])) ! 898: return 0; ! 899: /* It's not invalidated by a store in memory ! 900: but we must still verify the address is invariant. */ ! 901: } ! 902: ! 903: fmt = GET_RTX_FORMAT (code); ! 904: for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) ! 905: { ! 906: if (fmt[i] == 'E') ! 907: abort (); ! 908: if (fmt[i] == 'e') ! 909: { ! 910: int tem = invariant_p (XEXP (x, i), n_times_set); ! 911: if (tem == 0) ! 912: return 0; ! 913: if (tem == 2) ! 914: conditional = 1; ! 915: } ! 916: } ! 917: ! 918: return 1 + conditional; ! 919: } ! 920: ! 921: /* Return 1 if OTHER (a mem ref) overlaps the area of memory ! 922: which is SIZE bytes starting at BASE. */ ! 923: ! 924: int ! 925: addr_overlap_p (other, base, size) ! 926: rtx other; ! 927: rtx base; ! 928: int size; ! 929: { ! 930: int start = 0, end; ! 931: ! 932: if (GET_CODE (base) == CONST) ! 933: base = XEXP (base, 0); ! 934: if (GET_CODE (base) == PLUS ! 935: && GET_CODE (XEXP (base, 1)) == CONST_INT) ! 936: { ! 937: start = INTVAL (XEXP (base, 1)); ! 938: base = XEXP (base, 0); ! 939: } ! 940: ! 941: end = start + size; ! 942: return refers_to_mem_p (other, base, start, end); ! 943: } ! 944: ! 945: /* Return 1 if all insns in the basic block of INSN and following INSN ! 946: that set REG are invariant according to TABLE. */ ! 947: ! 948: static int ! 949: all_sets_invariant_p (reg, insn, table) ! 950: rtx reg, insn; ! 951: char *table; ! 952: { ! 953: register rtx p = insn; ! 954: register int regno = REGNO (reg); ! 955: ! 956: while (1) ! 957: { ! 958: register enum rtx_code code; ! 959: p = NEXT_INSN (p); ! 960: code = GET_CODE (p); ! 961: if (code == CODE_LABEL || code == JUMP_INSN) ! 962: return 1; ! 963: if (code == INSN && GET_CODE (PATTERN (p)) == SET ! 964: && GET_CODE (SET_DEST (PATTERN (p))) == REG ! 965: && REGNO (SET_DEST (PATTERN (p))) == regno) ! 966: { ! 967: if (!invariant_p (SET_SRC (PATTERN (p)), table)) ! 968: return 0; ! 969: } ! 970: } ! 971: } ! 972: ! 973: /* Increment N_TIMES_SET at the index of each register ! 974: that is modified by an insn between FROM and TO. ! 975: If the value of an element of N_TIMES_SET becomes 2 or more, ! 976: do not keep incrementing it; all values >= 2 would be ! 977: equivalent anyway, and this way we avoid danger of overflow. ! 978: ! 979: Store in *COUNT_PTR the number of actual instruction ! 980: in the loop. We use this to decide what is worth moving out. */ ! 981: ! 982: /* last_set[n] is nonzero iff reg n has been set in the current basic block. ! 983: In that case, it is the insn that last set reg n. */ ! 984: ! 985: static void ! 986: count_loop_regs_set (from, to, n_times_set, may_not_move, count_ptr, nregs) ! 987: register rtx from, to; ! 988: short *n_times_set; ! 989: char *may_not_move; ! 990: int *count_ptr; ! 991: int nregs; ! 992: { ! 993: register rtx *last_set = (rtx *) alloca (nregs * sizeof (rtx)); ! 994: register rtx insn; ! 995: register int count = 0; ! 996: register rtx dest; ! 997: ! 998: bzero (last_set, nregs * sizeof (rtx)); ! 999: for (insn = from; insn != to; insn = NEXT_INSN (insn)) ! 1000: { ! 1001: if (GET_CODE (insn) == INSN || GET_CODE (insn) == JUMP_INSN ! 1002: || GET_CODE (insn) == CALL_INSN) ! 1003: { ! 1004: ++count; ! 1005: if (GET_CODE (PATTERN (insn)) == SET) ! 1006: { ! 1007: dest = SET_DEST (PATTERN (insn)); ! 1008: while (GET_CODE (dest) == SUBREG ! 1009: || GET_CODE (dest) == ZERO_EXTRACT ! 1010: || GET_CODE (dest) == SIGN_EXTRACT ! 1011: || GET_CODE (dest) == STRICT_LOW_PART) ! 1012: dest = XEXP (dest, 0); ! 1013: if (GET_CODE (dest) == REG) ! 1014: { ! 1015: register int regno = REGNO (dest); ! 1016: /* If this is the first setting of this reg ! 1017: in current basic block, and it was set before, ! 1018: it must be set in two basic blocks, so it cannot ! 1019: be moved out of the loop. */ ! 1020: if (n_times_set[regno] > 0 && last_set[regno] == 0) ! 1021: may_not_move[regno] = 1; ! 1022: /* If this is not first setting in current basic block, ! 1023: see if reg was used in between previous one and this. ! 1024: If so, neither one can be moved. */ ! 1025: if (last_set[regno] != 0 ! 1026: && reg_used_between_p (dest, last_set[regno], insn)) ! 1027: may_not_move[regno] = 1; ! 1028: ++n_times_set[regno]; ! 1029: last_set[regno] = insn; ! 1030: } ! 1031: } ! 1032: else if (GET_CODE (PATTERN (insn)) == PARALLEL) ! 1033: { ! 1034: register int i; ! 1035: for (i = XVECLEN (PATTERN (insn), 0) - 1; i >= 0; i--) ! 1036: { ! 1037: register rtx x = XVECEXP (PATTERN (insn), 0, i); ! 1038: if (GET_CODE (x) == SET) ! 1039: { ! 1040: dest = SET_DEST (x); ! 1041: while (GET_CODE (dest) == SUBREG ! 1042: || GET_CODE (dest) == ZERO_EXTRACT ! 1043: || GET_CODE (dest) == SIGN_EXTRACT ! 1044: || GET_CODE (dest) == STRICT_LOW_PART) ! 1045: dest = XEXP (dest, 0); ! 1046: if (GET_CODE (dest) == REG) ! 1047: { ! 1048: register int regno = REGNO (dest); ! 1049: ++n_times_set[regno]; ! 1050: may_not_move[regno] = 1; ! 1051: last_set[regno] = insn; ! 1052: } ! 1053: } ! 1054: } ! 1055: } ! 1056: /* If a register is used as a subroutine address, ! 1057: don't allow this register's setting to be moved out of the loop. ! 1058: This condition is not at all logically correct ! 1059: but it averts a very common lossage pattern ! 1060: and creates lossage much less often. */ ! 1061: else if (GET_CODE (PATTERN (insn)) == CALL ! 1062: && GET_CODE (XEXP (PATTERN (insn), 0)) == MEM ! 1063: && GET_CODE (XEXP (XEXP (PATTERN (insn), 0), 0)) == REG) ! 1064: { ! 1065: register int regno ! 1066: = REGNO (XEXP (XEXP (PATTERN (insn), 0), 0)); ! 1067: may_not_move[regno] = 1; ! 1068: } ! 1069: } ! 1070: if (GET_CODE (insn) == CODE_LABEL || GET_CODE (insn) == JUMP_INSN) ! 1071: bzero (last_set, nregs * sizeof (rtx)); ! 1072: } ! 1073: *count_ptr = count; ! 1074: } ! 1075: ! 1076: /* Given a loop that is bounded by LOOP_START and LOOP_END ! 1077: and that is entered at SCAN_START, ! 1078: return 1 if the register set by insn INSN is used by ! 1079: any insn that precedes INSN in cyclic order starting ! 1080: from the loop entry point. */ ! 1081: ! 1082: static int ! 1083: loop_reg_used_before_p (insn, loop_start, scan_start, loop_end) ! 1084: rtx insn, loop_start, scan_start, loop_end; ! 1085: { ! 1086: rtx reg = SET_DEST (PATTERN (insn)); ! 1087: if (INSN_LUID (scan_start) > INSN_LUID (insn)) ! 1088: return (reg_used_between_p (reg, scan_start, loop_end) ! 1089: || reg_used_between_p (reg, loop_start, insn)); ! 1090: else ! 1091: return reg_used_between_p (reg, scan_start, insn); ! 1092: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.