![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to unroll.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 unroll.c CVS log | Up to [GCC 2.x] / gcc |
1.1 root 1: /* Try to unroll loops, and split induction variables. 1.1.1.7 ! root 2: Copyright (C) 1992, 1993, 1994 Free Software Foundation, Inc. 1.1 root 3: Contributed by James E. Wilson, Cygnus Support/UC Berkeley. 4: 5: This file is part of GNU CC. 6: 7: GNU CC is free software; you can redistribute it and/or modify 8: it under the terms of the GNU General Public License as published by 9: the Free Software Foundation; either version 2, or (at your option) 10: any later version. 11: 12: GNU CC is distributed in the hope that it will be useful, 13: but WITHOUT ANY WARRANTY; without even the implied warranty of 14: MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15: GNU General Public License for more details. 16: 17: You should have received a copy of the GNU General Public License 18: along with GNU CC; see the file COPYING. If not, write to 19: the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA. */ 20: 21: /* Try to unroll a loop, and split induction variables. 22: 23: Loops for which the number of iterations can be calculated exactly are 24: handled specially. If the number of iterations times the insn_count is 25: less than MAX_UNROLLED_INSNS, then the loop is unrolled completely. 26: Otherwise, we try to unroll the loop a number of times modulo the number 27: of iterations, so that only one exit test will be needed. It is unrolled 28: a number of times approximately equal to MAX_UNROLLED_INSNS divided by 29: the insn count. 30: 31: Otherwise, if the number of iterations can be calculated exactly at 32: run time, and the loop is always entered at the top, then we try to 33: precondition the loop. That is, at run time, calculate how many times 34: the loop will execute, and then execute the loop body a few times so 35: that the remaining iterations will be some multiple of 4 (or 2 if the 36: loop is large). Then fall through to a loop unrolled 4 (or 2) times, 37: with only one exit test needed at the end of the loop. 38: 39: Otherwise, if the number of iterations can not be calculated exactly, 40: not even at run time, then we still unroll the loop a number of times 41: approximately equal to MAX_UNROLLED_INSNS divided by the insn count, 42: but there must be an exit test after each copy of the loop body. 43: 44: For each induction variable, which is dead outside the loop (replaceable) 45: or for which we can easily calculate the final value, if we can easily 46: calculate its value at each place where it is set as a function of the 47: current loop unroll count and the variable's value at loop entry, then 48: the induction variable is split into `N' different variables, one for 49: each copy of the loop body. One variable is live across the backward 50: branch, and the others are all calculated as a function of this variable. 51: This helps eliminate data dependencies, and leads to further opportunities 52: for cse. */ 53: 54: /* Possible improvements follow: */ 55: 56: /* ??? Add an extra pass somewhere to determine whether unrolling will 57: give any benefit. E.g. after generating all unrolled insns, compute the 58: cost of all insns and compare against cost of insns in rolled loop. 59: 60: - On traditional architectures, unrolling a non-constant bound loop 61: is a win if there is a giv whose only use is in memory addresses, the 1.1.1.3 root 62: memory addresses can be split, and hence giv increments can be 1.1 root 63: eliminated. 64: - It is also a win if the loop is executed many times, and preconditioning 65: can be performed for the loop. 66: Add code to check for these and similar cases. */ 67: 68: /* ??? Improve control of which loops get unrolled. Could use profiling 69: info to only unroll the most commonly executed loops. Perhaps have 70: a user specifyable option to control the amount of code expansion, 71: or the percent of loops to consider for unrolling. Etc. */ 72: 73: /* ??? Look at the register copies inside the loop to see if they form a 74: simple permutation. If so, iterate the permutation until it gets back to 75: the start state. This is how many times we should unroll the loop, for 76: best results, because then all register copies can be eliminated. 77: For example, the lisp nreverse function should be unrolled 3 times 78: while (this) 79: { 80: next = this->cdr; 81: this->cdr = prev; 82: prev = this; 83: this = next; 84: } 85: 86: ??? The number of times to unroll the loop may also be based on data 87: references in the loop. For example, if we have a loop that references 88: x[i-1], x[i], and x[i+1], we should unroll it a multiple of 3 times. */ 89: 90: /* ??? Add some simple linear equation solving capability so that we can 91: determine the number of loop iterations for more complex loops. 92: For example, consider this loop from gdb 93: #define SWAP_TARGET_AND_HOST(buffer,len) 94: { 95: char tmp; 96: char *p = (char *) buffer; 97: char *q = ((char *) buffer) + len - 1; 98: int iterations = (len + 1) >> 1; 99: int i; 100: for (p; p < q; p++, q--;) 101: { 102: tmp = *q; 103: *q = *p; 104: *p = tmp; 105: } 106: } 107: Note that: 108: start value = p = &buffer + current_iteration 109: end value = q = &buffer + len - 1 - current_iteration 110: Given the loop exit test of "p < q", then there must be "q - p" iterations, 111: set equal to zero and solve for number of iterations: 112: q - p = len - 1 - 2*current_iteration = 0 113: current_iteration = (len - 1) / 2 114: Hence, there are (len - 1) / 2 (rounded up to the nearest integer) 115: iterations of this loop. */ 116: 117: /* ??? Currently, no labels are marked as loop invariant when doing loop 118: unrolling. This is because an insn inside the loop, that loads the address 119: of a label inside the loop into a register, could be moved outside the loop 120: by the invariant code motion pass if labels were invariant. If the loop 121: is subsequently unrolled, the code will be wrong because each unrolled 122: body of the loop will use the same address, whereas each actually needs a 123: different address. A case where this happens is when a loop containing 124: a switch statement is unrolled. 125: 126: It would be better to let labels be considered invariant. When we 127: unroll loops here, check to see if any insns using a label local to the 128: loop were moved before the loop. If so, then correct the problem, by 129: moving the insn back into the loop, or perhaps replicate the insn before 130: the loop, one copy for each time the loop is unrolled. */ 131: 132: /* The prime factors looked for when trying to unroll a loop by some 133: number which is modulo the total number of iterations. Just checking 134: for these 4 prime factors will find at least one factor for 75% of 135: all numbers theoretically. Practically speaking, this will succeed 136: almost all of the time since loops are generally a multiple of 2 137: and/or 5. */ 138: 139: #define NUM_FACTORS 4 140: 141: struct _factor { int factor, count; } factors[NUM_FACTORS] 142: = { {2, 0}, {3, 0}, {5, 0}, {7, 0}}; 143: 144: /* Describes the different types of loop unrolling performed. */ 145: 146: enum unroll_types { UNROLL_COMPLETELY, UNROLL_MODULO, UNROLL_NAIVE }; 147: 148: #include "config.h" 149: #include "rtl.h" 150: #include "insn-config.h" 151: #include "integrate.h" 152: #include "regs.h" 153: #include "flags.h" 154: #include "expr.h" 155: #include <stdio.h> 156: #include "loop.h" 157: 158: /* This controls which loops are unrolled, and by how much we unroll 159: them. */ 160: 161: #ifndef MAX_UNROLLED_INSNS 162: #define MAX_UNROLLED_INSNS 100 163: #endif 164: 165: /* Indexed by register number, if non-zero, then it contains a pointer 166: to a struct induction for a DEST_REG giv which has been combined with 167: one of more address givs. This is needed because whenever such a DEST_REG 168: giv is modified, we must modify the value of all split address givs 169: that were combined with this DEST_REG giv. */ 170: 171: static struct induction **addr_combined_regs; 172: 173: /* Indexed by register number, if this is a splittable induction variable, 174: then this will hold the current value of the register, which depends on the 175: iteration number. */ 176: 177: static rtx *splittable_regs; 178: 179: /* Indexed by register number, if this is a splittable induction variable, 180: then this will hold the number of instructions in the loop that modify 181: the induction variable. Used to ensure that only the last insn modifying 182: a split iv will update the original iv of the dest. */ 183: 184: static int *splittable_regs_updates; 185: 186: /* Values describing the current loop's iteration variable. These are set up 187: by loop_iterations, and used by precondition_loop_p. */ 188: 189: static rtx loop_iteration_var; 190: static rtx loop_initial_value; 191: static rtx loop_increment; 192: static rtx loop_final_value; 193: 194: /* Forward declarations. */ 195: 196: static void init_reg_map (); 197: static int precondition_loop_p (); 198: static void copy_loop_body (); 199: static void iteration_info (); 200: static rtx approx_final_value (); 201: static int find_splittable_regs (); 202: static int find_splittable_givs (); 203: static rtx fold_rtx_mult_add (); 1.1.1.7 ! root 204: static rtx remap_split_bivs (); 1.1 root 205: 206: /* Try to unroll one loop and split induction variables in the loop. 207: 208: The loop is described by the arguments LOOP_END, INSN_COUNT, and 1.1.1.3 root 209: LOOP_START. END_INSERT_BEFORE indicates where insns should be added 1.1 root 210: which need to be executed when the loop falls through. STRENGTH_REDUCTION_P 211: indicates whether information generated in the strength reduction pass 212: is available. 213: 214: This function is intended to be called from within `strength_reduce' 215: in loop.c. */ 216: 217: void 218: unroll_loop (loop_end, insn_count, loop_start, end_insert_before, 219: strength_reduce_p) 220: rtx loop_end; 221: int insn_count; 222: rtx loop_start; 223: rtx end_insert_before; 224: int strength_reduce_p; 225: { 226: int i, j, temp; 227: int unroll_number = 1; 228: rtx copy_start, copy_end; 229: rtx insn, copy, sequence, pattern, tem; 230: int max_labelno, max_insnno; 231: rtx insert_before; 232: struct inline_remap *map; 233: char *local_label; 234: int maxregnum; 235: int new_maxregnum; 236: rtx exit_label = 0; 237: rtx start_label; 238: struct iv_class *bl; 239: int splitting_not_safe = 0; 240: enum unroll_types unroll_type; 241: int loop_preconditioned = 0; 242: rtx safety_label; 243: /* This points to the last real insn in the loop, which should be either 244: a JUMP_INSN (for conditional jumps) or a BARRIER (for unconditional 245: jumps). */ 246: rtx last_loop_insn; 247: 248: /* Don't bother unrolling huge loops. Since the minimum factor is 249: two, loops greater than one half of MAX_UNROLLED_INSNS will never 250: be unrolled. */ 251: if (insn_count > MAX_UNROLLED_INSNS / 2) 252: { 253: if (loop_dump_stream) 254: fprintf (loop_dump_stream, "Unrolling failure: Loop too big.\n"); 255: return; 256: } 257: 258: /* When emitting debugger info, we can't unroll loops with unequal numbers 259: of block_beg and block_end notes, because that would unbalance the block 260: structure of the function. This can happen as a result of the 261: "if (foo) bar; else break;" optimization in jump.c. */ 262: 263: if (write_symbols != NO_DEBUG) 264: { 265: int block_begins = 0; 266: int block_ends = 0; 267: 268: for (insn = loop_start; insn != loop_end; insn = NEXT_INSN (insn)) 269: { 270: if (GET_CODE (insn) == NOTE) 271: { 272: if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_BLOCK_BEG) 273: block_begins++; 274: else if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_BLOCK_END) 275: block_ends++; 276: } 277: } 278: 279: if (block_begins != block_ends) 280: { 281: if (loop_dump_stream) 282: fprintf (loop_dump_stream, 283: "Unrolling failure: Unbalanced block notes.\n"); 284: return; 285: } 286: } 287: 288: /* Determine type of unroll to perform. Depends on the number of iterations 289: and the size of the loop. */ 290: 291: /* If there is no strength reduce info, then set loop_n_iterations to zero. 292: This can happen if strength_reduce can't find any bivs in the loop. 293: A value of zero indicates that the number of iterations could not be 294: calculated. */ 295: 296: if (! strength_reduce_p) 297: loop_n_iterations = 0; 298: 299: if (loop_dump_stream && loop_n_iterations > 0) 300: fprintf (loop_dump_stream, 301: "Loop unrolling: %d iterations.\n", loop_n_iterations); 302: 303: /* Find and save a pointer to the last nonnote insn in the loop. */ 304: 305: last_loop_insn = prev_nonnote_insn (loop_end); 306: 307: /* Calculate how many times to unroll the loop. Indicate whether or 308: not the loop is being completely unrolled. */ 309: 310: if (loop_n_iterations == 1) 311: { 312: /* If number of iterations is exactly 1, then eliminate the compare and 313: branch at the end of the loop since they will never be taken. 314: Then return, since no other action is needed here. */ 315: 316: /* If the last instruction is not a BARRIER or a JUMP_INSN, then 317: don't do anything. */ 318: 319: if (GET_CODE (last_loop_insn) == BARRIER) 320: { 321: /* Delete the jump insn. This will delete the barrier also. */ 322: delete_insn (PREV_INSN (last_loop_insn)); 323: } 324: else if (GET_CODE (last_loop_insn) == JUMP_INSN) 325: { 326: #ifdef HAVE_cc0 1.1.1.2 root 327: /* The immediately preceding insn is a compare which must be 1.1 root 328: deleted. */ 329: delete_insn (last_loop_insn); 330: delete_insn (PREV_INSN (last_loop_insn)); 331: #else 1.1.1.2 root 332: /* The immediately preceding insn may not be the compare, so don't 1.1 root 333: delete it. */ 334: delete_insn (last_loop_insn); 335: #endif 336: } 337: return; 338: } 339: else if (loop_n_iterations > 0 340: && loop_n_iterations * insn_count < MAX_UNROLLED_INSNS) 341: { 342: unroll_number = loop_n_iterations; 343: unroll_type = UNROLL_COMPLETELY; 344: } 345: else if (loop_n_iterations > 0) 346: { 347: /* Try to factor the number of iterations. Don't bother with the 348: general case, only using 2, 3, 5, and 7 will get 75% of all 349: numbers theoretically, and almost all in practice. */ 350: 351: for (i = 0; i < NUM_FACTORS; i++) 352: factors[i].count = 0; 353: 354: temp = loop_n_iterations; 355: for (i = NUM_FACTORS - 1; i >= 0; i--) 356: while (temp % factors[i].factor == 0) 357: { 358: factors[i].count++; 359: temp = temp / factors[i].factor; 360: } 361: 362: /* Start with the larger factors first so that we generally 363: get lots of unrolling. */ 364: 365: unroll_number = 1; 366: temp = insn_count; 367: for (i = 3; i >= 0; i--) 368: while (factors[i].count--) 369: { 370: if (temp * factors[i].factor < MAX_UNROLLED_INSNS) 371: { 372: unroll_number *= factors[i].factor; 373: temp *= factors[i].factor; 374: } 375: else 376: break; 377: } 378: 379: /* If we couldn't find any factors, then unroll as in the normal 380: case. */ 381: if (unroll_number == 1) 382: { 383: if (loop_dump_stream) 384: fprintf (loop_dump_stream, 385: "Loop unrolling: No factors found.\n"); 386: } 387: else 388: unroll_type = UNROLL_MODULO; 389: } 390: 391: 392: /* Default case, calculate number of times to unroll loop based on its 393: size. */ 394: if (unroll_number == 1) 395: { 396: if (8 * insn_count < MAX_UNROLLED_INSNS) 397: unroll_number = 8; 398: else if (4 * insn_count < MAX_UNROLLED_INSNS) 399: unroll_number = 4; 400: else 401: unroll_number = 2; 402: 403: unroll_type = UNROLL_NAIVE; 404: } 405: 406: /* Now we know how many times to unroll the loop. */ 407: 408: if (loop_dump_stream) 409: fprintf (loop_dump_stream, 410: "Unrolling loop %d times.\n", unroll_number); 411: 412: 413: if (unroll_type == UNROLL_COMPLETELY || unroll_type == UNROLL_MODULO) 414: { 415: /* Loops of these types should never start with a jump down to 416: the exit condition test. For now, check for this case just to 417: be sure. UNROLL_NAIVE loops can be of this form, this case is 418: handled below. */ 419: insn = loop_start; 420: while (GET_CODE (insn) != CODE_LABEL && GET_CODE (insn) != JUMP_INSN) 421: insn = NEXT_INSN (insn); 422: if (GET_CODE (insn) == JUMP_INSN) 423: abort (); 424: } 425: 426: if (unroll_type == UNROLL_COMPLETELY) 427: { 428: /* Completely unrolling the loop: Delete the compare and branch at 429: the end (the last two instructions). This delete must done at the 430: very end of loop unrolling, to avoid problems with calls to 431: back_branch_in_range_p, which is called by find_splittable_regs. 432: All increments of splittable bivs/givs are changed to load constant 433: instructions. */ 434: 435: copy_start = loop_start; 436: 437: /* Set insert_before to the instruction immediately after the JUMP_INSN 438: (or BARRIER), so that any NOTEs between the JUMP_INSN and the end of 439: the loop will be correctly handled by copy_loop_body. */ 440: insert_before = NEXT_INSN (last_loop_insn); 441: 442: /* Set copy_end to the insn before the jump at the end of the loop. */ 443: if (GET_CODE (last_loop_insn) == BARRIER) 444: copy_end = PREV_INSN (PREV_INSN (last_loop_insn)); 445: else if (GET_CODE (last_loop_insn) == JUMP_INSN) 446: { 447: #ifdef HAVE_cc0 448: /* The instruction immediately before the JUMP_INSN is a compare 449: instruction which we do not want to copy. */ 450: copy_end = PREV_INSN (PREV_INSN (last_loop_insn)); 451: #else 452: /* The instruction immediately before the JUMP_INSN may not be the 453: compare, so we must copy it. */ 454: copy_end = PREV_INSN (last_loop_insn); 455: #endif 456: } 457: else 458: { 459: /* We currently can't unroll a loop if it doesn't end with a 460: JUMP_INSN. There would need to be a mechanism that recognizes 461: this case, and then inserts a jump after each loop body, which 462: jumps to after the last loop body. */ 463: if (loop_dump_stream) 464: fprintf (loop_dump_stream, 465: "Unrolling failure: loop does not end with a JUMP_INSN.\n"); 466: return; 467: } 468: } 469: else if (unroll_type == UNROLL_MODULO) 470: { 471: /* Partially unrolling the loop: The compare and branch at the end 472: (the last two instructions) must remain. Don't copy the compare 473: and branch instructions at the end of the loop. Insert the unrolled 474: code immediately before the compare/branch at the end so that the 475: code will fall through to them as before. */ 476: 477: copy_start = loop_start; 478: 479: /* Set insert_before to the jump insn at the end of the loop. 480: Set copy_end to before the jump insn at the end of the loop. */ 481: if (GET_CODE (last_loop_insn) == BARRIER) 482: { 483: insert_before = PREV_INSN (last_loop_insn); 484: copy_end = PREV_INSN (insert_before); 485: } 486: else if (GET_CODE (last_loop_insn) == JUMP_INSN) 487: { 488: #ifdef HAVE_cc0 489: /* The instruction immediately before the JUMP_INSN is a compare 490: instruction which we do not want to copy or delete. */ 491: insert_before = PREV_INSN (last_loop_insn); 492: copy_end = PREV_INSN (insert_before); 493: #else 494: /* The instruction immediately before the JUMP_INSN may not be the 495: compare, so we must copy it. */ 496: insert_before = last_loop_insn; 497: copy_end = PREV_INSN (last_loop_insn); 498: #endif 499: } 500: else 501: { 502: /* We currently can't unroll a loop if it doesn't end with a 503: JUMP_INSN. There would need to be a mechanism that recognizes 504: this case, and then inserts a jump after each loop body, which 505: jumps to after the last loop body. */ 506: if (loop_dump_stream) 507: fprintf (loop_dump_stream, 508: "Unrolling failure: loop does not end with a JUMP_INSN.\n"); 509: return; 510: } 511: } 512: else 513: { 514: /* Normal case: Must copy the compare and branch instructions at the 515: end of the loop. */ 516: 517: if (GET_CODE (last_loop_insn) == BARRIER) 518: { 519: /* Loop ends with an unconditional jump and a barrier. 520: Handle this like above, don't copy jump and barrier. 521: This is not strictly necessary, but doing so prevents generating 522: unconditional jumps to an immediately following label. 523: 524: This will be corrected below if the target of this jump is 525: not the start_label. */ 526: 527: insert_before = PREV_INSN (last_loop_insn); 528: copy_end = PREV_INSN (insert_before); 529: } 530: else if (GET_CODE (last_loop_insn) == JUMP_INSN) 531: { 532: /* Set insert_before to immediately after the JUMP_INSN, so that 533: NOTEs at the end of the loop will be correctly handled by 534: copy_loop_body. */ 535: insert_before = NEXT_INSN (last_loop_insn); 536: copy_end = last_loop_insn; 537: } 538: else 539: { 540: /* We currently can't unroll a loop if it doesn't end with a 541: JUMP_INSN. There would need to be a mechanism that recognizes 542: this case, and then inserts a jump after each loop body, which 543: jumps to after the last loop body. */ 544: if (loop_dump_stream) 545: fprintf (loop_dump_stream, 546: "Unrolling failure: loop does not end with a JUMP_INSN.\n"); 547: return; 548: } 549: 550: /* If copying exit test branches because they can not be eliminated, 551: then must convert the fall through case of the branch to a jump past 552: the end of the loop. Create a label to emit after the loop and save 553: it for later use. Do not use the label after the loop, if any, since 554: it might be used by insns outside the loop, or there might be insns 555: added before it later by final_[bg]iv_value which must be after 556: the real exit label. */ 557: exit_label = gen_label_rtx (); 558: 559: insn = loop_start; 560: while (GET_CODE (insn) != CODE_LABEL && GET_CODE (insn) != JUMP_INSN) 561: insn = NEXT_INSN (insn); 562: 563: if (GET_CODE (insn) == JUMP_INSN) 564: { 565: /* The loop starts with a jump down to the exit condition test. 566: Start copying the loop after the barrier following this 567: jump insn. */ 568: copy_start = NEXT_INSN (insn); 569: 570: /* Splitting induction variables doesn't work when the loop is 571: entered via a jump to the bottom, because then we end up doing 572: a comparison against a new register for a split variable, but 573: we did not execute the set insn for the new register because 574: it was skipped over. */ 575: splitting_not_safe = 1; 576: if (loop_dump_stream) 577: fprintf (loop_dump_stream, 578: "Splitting not safe, because loop not entered at top.\n"); 579: } 580: else 581: copy_start = loop_start; 582: } 583: 584: /* This should always be the first label in the loop. */ 585: start_label = NEXT_INSN (copy_start); 586: /* There may be a line number note and/or a loop continue note here. */ 587: while (GET_CODE (start_label) == NOTE) 588: start_label = NEXT_INSN (start_label); 589: if (GET_CODE (start_label) != CODE_LABEL) 590: { 591: /* This can happen as a result of jump threading. If the first insns in 592: the loop test the same condition as the loop's backward jump, or the 593: opposite condition, then the backward jump will be modified to point 594: to elsewhere, and the loop's start label is deleted. 595: 596: This case currently can not be handled by the loop unrolling code. */ 597: 598: if (loop_dump_stream) 599: fprintf (loop_dump_stream, 600: "Unrolling failure: unknown insns between BEG note and loop label.\n"); 601: return; 602: } 1.1.1.6 root 603: if (LABEL_NAME (start_label)) 604: { 605: /* The jump optimization pass must have combined the original start label 606: with a named label for a goto. We can't unroll this case because 607: jumps which go to the named label must be handled differently than 608: jumps to the loop start, and it is impossible to differentiate them 609: in this case. */ 610: if (loop_dump_stream) 611: fprintf (loop_dump_stream, 612: "Unrolling failure: loop start label is gone\n"); 613: return; 614: } 1.1 root 615: 616: if (unroll_type == UNROLL_NAIVE 617: && GET_CODE (last_loop_insn) == BARRIER 618: && start_label != JUMP_LABEL (PREV_INSN (last_loop_insn))) 619: { 620: /* In this case, we must copy the jump and barrier, because they will 621: not be converted to jumps to an immediately following label. */ 622: 623: insert_before = NEXT_INSN (last_loop_insn); 624: copy_end = last_loop_insn; 625: } 626: 627: /* Allocate a translation table for the labels and insn numbers. 628: They will be filled in as we copy the insns in the loop. */ 629: 630: max_labelno = max_label_num (); 631: max_insnno = get_max_uid (); 632: 633: map = (struct inline_remap *) alloca (sizeof (struct inline_remap)); 634: 1.1.1.5 root 635: map->integrating = 0; 636: 1.1 root 637: /* Allocate the label map. */ 638: 639: if (max_labelno > 0) 640: { 641: map->label_map = (rtx *) alloca (max_labelno * sizeof (rtx)); 642: 643: local_label = (char *) alloca (max_labelno); 644: bzero (local_label, max_labelno); 645: } 646: else 647: map->label_map = 0; 648: 649: /* Search the loop and mark all local labels, i.e. the ones which have to 650: be distinct labels when copied. For all labels which might be 651: non-local, set their label_map entries to point to themselves. 652: If they happen to be local their label_map entries will be overwritten 653: before the loop body is copied. The label_map entries for local labels 654: will be set to a different value each time the loop body is copied. */ 655: 656: for (insn = copy_start; insn != loop_end; insn = NEXT_INSN (insn)) 657: { 658: if (GET_CODE (insn) == CODE_LABEL) 659: local_label[CODE_LABEL_NUMBER (insn)] = 1; 660: else if (GET_CODE (insn) == JUMP_INSN) 661: { 662: if (JUMP_LABEL (insn)) 663: map->label_map[CODE_LABEL_NUMBER (JUMP_LABEL (insn))] 664: = JUMP_LABEL (insn); 665: else if (GET_CODE (PATTERN (insn)) == ADDR_VEC 666: || GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC) 667: { 668: rtx pat = PATTERN (insn); 669: int diff_vec_p = GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC; 670: int len = XVECLEN (pat, diff_vec_p); 671: rtx label; 672: 673: for (i = 0; i < len; i++) 674: { 675: label = XEXP (XVECEXP (pat, diff_vec_p, i), 0); 676: map->label_map[CODE_LABEL_NUMBER (label)] = label; 677: } 678: } 679: } 680: } 681: 682: /* Allocate space for the insn map. */ 683: 684: map->insn_map = (rtx *) alloca (max_insnno * sizeof (rtx)); 685: 686: /* Set this to zero, to indicate that we are doing loop unrolling, 687: not function inlining. */ 688: map->inline_target = 0; 689: 690: /* The register and constant maps depend on the number of registers 691: present, so the final maps can't be created until after 692: find_splittable_regs is called. However, they are needed for 693: preconditioning, so we create temporary maps when preconditioning 694: is performed. */ 695: 696: /* The preconditioning code may allocate two new pseudo registers. */ 697: maxregnum = max_reg_num (); 698: 699: /* Allocate and zero out the splittable_regs and addr_combined_regs 700: arrays. These must be zeroed here because they will be used if 701: loop preconditioning is performed, and must be zero for that case. 702: 703: It is safe to do this here, since the extra registers created by the 704: preconditioning code and find_splittable_regs will never be used 1.1.1.3 root 705: to access the splittable_regs[] and addr_combined_regs[] arrays. */ 1.1 root 706: 707: splittable_regs = (rtx *) alloca (maxregnum * sizeof (rtx)); 1.1.1.7 ! root 708: bzero ((char *) splittable_regs, maxregnum * sizeof (rtx)); 1.1 root 709: splittable_regs_updates = (int *) alloca (maxregnum * sizeof (int)); 1.1.1.7 ! root 710: bzero ((char *) splittable_regs_updates, maxregnum * sizeof (int)); 1.1 root 711: addr_combined_regs 712: = (struct induction **) alloca (maxregnum * sizeof (struct induction *)); 1.1.1.7 ! root 713: bzero ((char *) addr_combined_regs, maxregnum * sizeof (struct induction *)); 1.1 root 714: 715: /* If this loop requires exit tests when unrolled, check to see if we 716: can precondition the loop so as to make the exit tests unnecessary. 717: Just like variable splitting, this is not safe if the loop is entered 718: via a jump to the bottom. Also, can not do this if no strength 719: reduce info, because precondition_loop_p uses this info. */ 720: 721: /* Must copy the loop body for preconditioning before the following 722: find_splittable_regs call since that will emit insns which need to 723: be after the preconditioned loop copies, but immediately before the 724: unrolled loop copies. */ 725: 726: /* Also, it is not safe to split induction variables for the preconditioned 727: copies of the loop body. If we split induction variables, then the code 728: assumes that each induction variable can be represented as a function 729: of its initial value and the loop iteration number. This is not true 730: in this case, because the last preconditioned copy of the loop body 731: could be any iteration from the first up to the `unroll_number-1'th, 732: depending on the initial value of the iteration variable. Therefore 733: we can not split induction variables here, because we can not calculate 734: their value. Hence, this code must occur before find_splittable_regs 735: is called. */ 736: 737: if (unroll_type == UNROLL_NAIVE && ! splitting_not_safe && strength_reduce_p) 738: { 739: rtx initial_value, final_value, increment; 740: 741: if (precondition_loop_p (&initial_value, &final_value, &increment, 742: loop_start, loop_end)) 743: { 744: register rtx diff, temp; 745: enum machine_mode mode; 746: rtx *labels; 747: int abs_inc, neg_inc; 748: 749: map->reg_map = (rtx *) alloca (maxregnum * sizeof (rtx)); 750: 751: map->const_equiv_map = (rtx *) alloca (maxregnum * sizeof (rtx)); 752: map->const_age_map = (unsigned *) alloca (maxregnum 753: * sizeof (unsigned)); 754: map->const_equiv_map_size = maxregnum; 755: global_const_equiv_map = map->const_equiv_map; 1.1.1.6 root 756: global_const_equiv_map_size = maxregnum; 1.1 root 757: 758: init_reg_map (map, maxregnum); 759: 760: /* Limit loop unrolling to 4, since this will make 7 copies of 761: the loop body. */ 762: if (unroll_number > 4) 763: unroll_number = 4; 764: 765: /* Save the absolute value of the increment, and also whether or 766: not it is negative. */ 767: neg_inc = 0; 768: abs_inc = INTVAL (increment); 769: if (abs_inc < 0) 770: { 771: abs_inc = - abs_inc; 772: neg_inc = 1; 773: } 774: 775: start_sequence (); 776: 777: /* Decide what mode to do these calculations in. Choose the larger 778: of final_value's mode and initial_value's mode, or a full-word if 779: both are constants. */ 780: mode = GET_MODE (final_value); 781: if (mode == VOIDmode) 782: { 783: mode = GET_MODE (initial_value); 784: if (mode == VOIDmode) 785: mode = word_mode; 786: } 787: else if (mode != GET_MODE (initial_value) 788: && (GET_MODE_SIZE (mode) 789: < GET_MODE_SIZE (GET_MODE (initial_value)))) 790: mode = GET_MODE (initial_value); 791: 792: /* Calculate the difference between the final and initial values. 793: Final value may be a (plus (reg x) (const_int 1)) rtx. 794: Let the following cse pass simplify this if initial value is 795: a constant. 796: 797: We must copy the final and initial values here to avoid 798: improperly shared rtl. */ 799: 800: diff = expand_binop (mode, sub_optab, copy_rtx (final_value), 1.1.1.4 root 801: copy_rtx (initial_value), NULL_RTX, 0, 1.1 root 802: OPTAB_LIB_WIDEN); 803: 804: /* Now calculate (diff % (unroll * abs (increment))) by using an 805: and instruction. */ 806: diff = expand_binop (GET_MODE (diff), and_optab, diff, 1.1.1.4 root 807: GEN_INT (unroll_number * abs_inc - 1), 808: NULL_RTX, 0, OPTAB_LIB_WIDEN); 1.1 root 809: 810: /* Now emit a sequence of branches to jump to the proper precond 811: loop entry point. */ 812: 813: labels = (rtx *) alloca (sizeof (rtx) * unroll_number); 814: for (i = 0; i < unroll_number; i++) 815: labels[i] = gen_label_rtx (); 816: 817: /* Assuming the unroll_number is 4, and the increment is 2, then 818: for a negative increment: for a positive increment: 819: diff = 0,1 precond 0 diff = 0,7 precond 0 820: diff = 2,3 precond 3 diff = 1,2 precond 1 821: diff = 4,5 precond 2 diff = 3,4 precond 2 822: diff = 6,7 precond 1 diff = 5,6 precond 3 */ 823: 824: /* We only need to emit (unroll_number - 1) branches here, the 825: last case just falls through to the following code. */ 826: 827: /* ??? This would give better code if we emitted a tree of branches 828: instead of the current linear list of branches. */ 829: 830: for (i = 0; i < unroll_number - 1; i++) 831: { 832: int cmp_const; 833: 834: /* For negative increments, must invert the constant compared 835: against, except when comparing against zero. */ 836: if (i == 0) 837: cmp_const = 0; 838: else if (neg_inc) 839: cmp_const = unroll_number - i; 840: else 841: cmp_const = i; 842: 1.1.1.4 root 843: emit_cmp_insn (diff, GEN_INT (abs_inc * cmp_const), 844: EQ, NULL_RTX, mode, 0, 0); 1.1 root 845: 846: if (i == 0) 847: emit_jump_insn (gen_beq (labels[i])); 848: else if (neg_inc) 849: emit_jump_insn (gen_bge (labels[i])); 850: else 851: emit_jump_insn (gen_ble (labels[i])); 852: JUMP_LABEL (get_last_insn ()) = labels[i]; 853: LABEL_NUSES (labels[i])++; 854: } 855: 856: /* If the increment is greater than one, then we need another branch, 857: to handle other cases equivalent to 0. */ 858: 859: /* ??? This should be merged into the code above somehow to help 860: simplify the code here, and reduce the number of branches emitted. 861: For the negative increment case, the branch here could easily 862: be merged with the `0' case branch above. For the positive 863: increment case, it is not clear how this can be simplified. */ 864: 865: if (abs_inc != 1) 866: { 867: int cmp_const; 868: 869: if (neg_inc) 870: cmp_const = abs_inc - 1; 871: else 872: cmp_const = abs_inc * (unroll_number - 1) + 1; 873: 1.1.1.4 root 874: emit_cmp_insn (diff, GEN_INT (cmp_const), EQ, NULL_RTX, 875: mode, 0, 0); 1.1 root 876: 877: if (neg_inc) 878: emit_jump_insn (gen_ble (labels[0])); 879: else 880: emit_jump_insn (gen_bge (labels[0])); 881: JUMP_LABEL (get_last_insn ()) = labels[0]; 882: LABEL_NUSES (labels[0])++; 883: } 884: 885: sequence = gen_sequence (); 886: end_sequence (); 887: emit_insn_before (sequence, loop_start); 888: 889: /* Only the last copy of the loop body here needs the exit 890: test, so set copy_end to exclude the compare/branch here, 891: and then reset it inside the loop when get to the last 892: copy. */ 893: 894: if (GET_CODE (last_loop_insn) == BARRIER) 895: copy_end = PREV_INSN (PREV_INSN (last_loop_insn)); 896: else if (GET_CODE (last_loop_insn) == JUMP_INSN) 897: { 898: #ifdef HAVE_cc0 1.1.1.2 root 899: /* The immediately preceding insn is a compare which we do not 1.1 root 900: want to copy. */ 901: copy_end = PREV_INSN (PREV_INSN (last_loop_insn)); 902: #else 1.1.1.2 root 903: /* The immediately preceding insn may not be a compare, so we 1.1 root 904: must copy it. */ 905: copy_end = PREV_INSN (last_loop_insn); 906: #endif 907: } 908: else 909: abort (); 910: 911: for (i = 1; i < unroll_number; i++) 912: { 913: emit_label_after (labels[unroll_number - i], 914: PREV_INSN (loop_start)); 915: 1.1.1.7 ! root 916: bzero ((char *) map->insn_map, max_insnno * sizeof (rtx)); ! 917: bzero ((char *) map->const_equiv_map, maxregnum * sizeof (rtx)); ! 918: bzero ((char *) map->const_age_map, ! 919: maxregnum * sizeof (unsigned)); 1.1 root 920: map->const_age = 0; 921: 922: for (j = 0; j < max_labelno; j++) 923: if (local_label[j]) 924: map->label_map[j] = gen_label_rtx (); 925: 926: /* The last copy needs the compare/branch insns at the end, 927: so reset copy_end here if the loop ends with a conditional 928: branch. */ 929: 930: if (i == unroll_number - 1) 931: { 932: if (GET_CODE (last_loop_insn) == BARRIER) 933: copy_end = PREV_INSN (PREV_INSN (last_loop_insn)); 934: else 935: copy_end = last_loop_insn; 936: } 937: 938: /* None of the copies are the `last_iteration', so just 939: pass zero for that parameter. */ 940: copy_loop_body (copy_start, copy_end, map, exit_label, 0, 941: unroll_type, start_label, loop_end, 942: loop_start, copy_end); 943: } 944: emit_label_after (labels[0], PREV_INSN (loop_start)); 945: 946: if (GET_CODE (last_loop_insn) == BARRIER) 947: { 948: insert_before = PREV_INSN (last_loop_insn); 949: copy_end = PREV_INSN (insert_before); 950: } 951: else 952: { 953: #ifdef HAVE_cc0 1.1.1.2 root 954: /* The immediately preceding insn is a compare which we do not 1.1 root 955: want to copy. */ 956: insert_before = PREV_INSN (last_loop_insn); 957: copy_end = PREV_INSN (insert_before); 958: #else 1.1.1.2 root 959: /* The immediately preceding insn may not be a compare, so we 1.1 root 960: must copy it. */ 961: insert_before = last_loop_insn; 962: copy_end = PREV_INSN (last_loop_insn); 963: #endif 964: } 965: 966: /* Set unroll type to MODULO now. */ 967: unroll_type = UNROLL_MODULO; 968: loop_preconditioned = 1; 969: } 970: } 971: 972: /* If reach here, and the loop type is UNROLL_NAIVE, then don't unroll 973: the loop unless all loops are being unrolled. */ 974: if (unroll_type == UNROLL_NAIVE && ! flag_unroll_all_loops) 975: { 976: if (loop_dump_stream) 977: fprintf (loop_dump_stream, "Unrolling failure: Naive unrolling not being done.\n"); 978: return; 979: } 980: 981: /* At this point, we are guaranteed to unroll the loop. */ 982: 983: /* For each biv and giv, determine whether it can be safely split into 984: a different variable for each unrolled copy of the loop body. 985: We precalculate and save this info here, since computing it is 986: expensive. 987: 988: Do this before deleting any instructions from the loop, so that 989: back_branch_in_range_p will work correctly. */ 990: 991: if (splitting_not_safe) 992: temp = 0; 993: else 994: temp = find_splittable_regs (unroll_type, loop_start, loop_end, 995: end_insert_before, unroll_number); 996: 997: /* find_splittable_regs may have created some new registers, so must 998: reallocate the reg_map with the new larger size, and must realloc 999: the constant maps also. */ 1000: 1001: maxregnum = max_reg_num (); 1002: map->reg_map = (rtx *) alloca (maxregnum * sizeof (rtx)); 1003: 1004: init_reg_map (map, maxregnum); 1005: 1006: /* Space is needed in some of the map for new registers, so new_maxregnum 1007: is an (over)estimate of how many registers will exist at the end. */ 1008: new_maxregnum = maxregnum + (temp * unroll_number * 2); 1009: 1010: /* Must realloc space for the constant maps, because the number of registers 1011: may have changed. */ 1012: 1013: map->const_equiv_map = (rtx *) alloca (new_maxregnum * sizeof (rtx)); 1014: map->const_age_map = (unsigned *) alloca (new_maxregnum * sizeof (unsigned)); 1015: 1.1.1.6 root 1016: map->const_equiv_map_size = new_maxregnum; 1.1 root 1017: global_const_equiv_map = map->const_equiv_map; 1.1.1.6 root 1018: global_const_equiv_map_size = new_maxregnum; 1.1 root 1019: 1020: /* Search the list of bivs and givs to find ones which need to be remapped 1021: when split, and set their reg_map entry appropriately. */ 1022: 1023: for (bl = loop_iv_list; bl; bl = bl->next) 1024: { 1025: if (REGNO (bl->biv->src_reg) != bl->regno) 1026: map->reg_map[bl->regno] = bl->biv->src_reg; 1027: #if 0 1028: /* Currently, non-reduced/final-value givs are never split. */ 1029: for (v = bl->giv; v; v = v->next_iv) 1030: if (REGNO (v->src_reg) != bl->regno) 1031: map->reg_map[REGNO (v->dest_reg)] = v->src_reg; 1032: #endif 1033: } 1034: 1035: /* If the loop is being partially unrolled, and the iteration variables 1036: are being split, and are being renamed for the split, then must fix up 1.1.1.7 ! root 1037: the compare/jump instruction at the end of the loop to refer to the new 1.1 root 1038: registers. This compare isn't copied, so the registers used in it 1039: will never be replaced if it isn't done here. */ 1040: 1041: if (unroll_type == UNROLL_MODULO) 1042: { 1043: insn = NEXT_INSN (copy_end); 1.1.1.7 ! root 1044: if (GET_CODE (insn) == INSN || GET_CODE (insn) == JUMP_INSN) ! 1045: PATTERN (insn) = remap_split_bivs (PATTERN (insn)); 1.1 root 1046: } 1047: 1048: /* For unroll_number - 1 times, make a copy of each instruction 1049: between copy_start and copy_end, and insert these new instructions 1050: before the end of the loop. */ 1051: 1052: for (i = 0; i < unroll_number; i++) 1053: { 1.1.1.7 ! root 1054: bzero ((char *) map->insn_map, max_insnno * sizeof (rtx)); ! 1055: bzero ((char *) map->const_equiv_map, new_maxregnum * sizeof (rtx)); ! 1056: bzero ((char *) map->const_age_map, new_maxregnum * sizeof (unsigned)); 1.1 root 1057: map->const_age = 0; 1058: 1059: for (j = 0; j < max_labelno; j++) 1060: if (local_label[j]) 1061: map->label_map[j] = gen_label_rtx (); 1062: 1063: /* If loop starts with a branch to the test, then fix it so that 1064: it points to the test of the first unrolled copy of the loop. */ 1065: if (i == 0 && loop_start != copy_start) 1066: { 1067: insn = PREV_INSN (copy_start); 1068: pattern = PATTERN (insn); 1069: 1070: tem = map->label_map[CODE_LABEL_NUMBER 1071: (XEXP (SET_SRC (pattern), 0))]; 1072: SET_SRC (pattern) = gen_rtx (LABEL_REF, VOIDmode, tem); 1073: 1074: /* Set the jump label so that it can be used by later loop unrolling 1075: passes. */ 1076: JUMP_LABEL (insn) = tem; 1077: LABEL_NUSES (tem)++; 1078: } 1079: 1080: copy_loop_body (copy_start, copy_end, map, exit_label, 1081: i == unroll_number - 1, unroll_type, start_label, 1082: loop_end, insert_before, insert_before); 1083: } 1084: 1085: /* Before deleting any insns, emit a CODE_LABEL immediately after the last 1086: insn to be deleted. This prevents any runaway delete_insn call from 1087: more insns that it should, as it always stops at a CODE_LABEL. */ 1088: 1089: /* Delete the compare and branch at the end of the loop if completely 1090: unrolling the loop. Deleting the backward branch at the end also 1091: deletes the code label at the start of the loop. This is done at 1092: the very end to avoid problems with back_branch_in_range_p. */ 1093: 1094: if (unroll_type == UNROLL_COMPLETELY) 1095: safety_label = emit_label_after (gen_label_rtx (), last_loop_insn); 1096: else 1097: safety_label = emit_label_after (gen_label_rtx (), copy_end); 1098: 1099: /* Delete all of the original loop instructions. Don't delete the 1100: LOOP_BEG note, or the first code label in the loop. */ 1101: 1102: insn = NEXT_INSN (copy_start); 1103: while (insn != safety_label) 1104: { 1105: if (insn != start_label) 1106: insn = delete_insn (insn); 1107: else 1108: insn = NEXT_INSN (insn); 1109: } 1110: 1111: /* Can now delete the 'safety' label emitted to protect us from runaway 1112: delete_insn calls. */ 1113: if (INSN_DELETED_P (safety_label)) 1114: abort (); 1115: delete_insn (safety_label); 1116: 1117: /* If exit_label exists, emit it after the loop. Doing the emit here 1118: forces it to have a higher INSN_UID than any insn in the unrolled loop. 1119: This is needed so that mostly_true_jump in reorg.c will treat jumps 1120: to this loop end label correctly, i.e. predict that they are usually 1121: not taken. */ 1122: if (exit_label) 1123: emit_label_after (exit_label, loop_end); 1124: } 1125: 1126: /* Return true if the loop can be safely, and profitably, preconditioned 1127: so that the unrolled copies of the loop body don't need exit tests. 1128: 1129: This only works if final_value, initial_value and increment can be 1130: determined, and if increment is a constant power of 2. 1131: If increment is not a power of 2, then the preconditioning modulo 1132: operation would require a real modulo instead of a boolean AND, and this 1133: is not considered `profitable'. */ 1134: 1135: /* ??? If the loop is known to be executed very many times, or the machine 1136: has a very cheap divide instruction, then preconditioning is a win even 1137: when the increment is not a power of 2. Use RTX_COST to compute 1138: whether divide is cheap. */ 1139: 1140: static int 1141: precondition_loop_p (initial_value, final_value, increment, loop_start, 1142: loop_end) 1143: rtx *initial_value, *final_value, *increment; 1144: rtx loop_start, loop_end; 1145: { 1146: 1147: if (loop_n_iterations > 0) 1148: { 1149: *initial_value = const0_rtx; 1150: *increment = const1_rtx; 1.1.1.4 root 1151: *final_value = GEN_INT (loop_n_iterations); 1.1 root 1152: 1153: if (loop_dump_stream) 1154: fprintf (loop_dump_stream, 1155: "Preconditioning: Success, number of iterations known, %d.\n", 1156: loop_n_iterations); 1157: return 1; 1158: } 1159: 1160: if (loop_initial_value == 0) 1161: { 1162: if (loop_dump_stream) 1163: fprintf (loop_dump_stream, 1164: "Preconditioning: Could not find initial value.\n"); 1165: return 0; 1166: } 1167: else if (loop_increment == 0) 1168: { 1169: if (loop_dump_stream) 1170: fprintf (loop_dump_stream, 1171: "Preconditioning: Could not find increment value.\n"); 1172: return 0; 1173: } 1174: else if (GET_CODE (loop_increment) != CONST_INT) 1175: { 1176: if (loop_dump_stream) 1177: fprintf (loop_dump_stream, 1178: "Preconditioning: Increment not a constant.\n"); 1179: return 0; 1180: } 1181: else if ((exact_log2 (INTVAL (loop_increment)) < 0) 1182: && (exact_log2 (- INTVAL (loop_increment)) < 0)) 1183: { 1184: if (loop_dump_stream) 1185: fprintf (loop_dump_stream, 1186: "Preconditioning: Increment not a constant power of 2.\n"); 1187: return 0; 1188: } 1189: 1190: /* Unsigned_compare and compare_dir can be ignored here, since they do 1191: not matter for preconditioning. */ 1192: 1193: if (loop_final_value == 0) 1194: { 1195: if (loop_dump_stream) 1196: fprintf (loop_dump_stream, 1197: "Preconditioning: EQ comparison loop.\n"); 1198: return 0; 1199: } 1200: 1201: /* Must ensure that final_value is invariant, so call invariant_p to 1202: check. Before doing so, must check regno against max_reg_before_loop 1.1.1.3 root 1203: to make sure that the register is in the range covered by invariant_p. 1.1 root 1204: If it isn't, then it is most likely a biv/giv which by definition are 1205: not invariant. */ 1206: if ((GET_CODE (loop_final_value) == REG 1207: && REGNO (loop_final_value) >= max_reg_before_loop) 1208: || (GET_CODE (loop_final_value) == PLUS 1209: && REGNO (XEXP (loop_final_value, 0)) >= max_reg_before_loop) 1210: || ! invariant_p (loop_final_value)) 1211: { 1212: if (loop_dump_stream) 1213: fprintf (loop_dump_stream, 1214: "Preconditioning: Final value not invariant.\n"); 1215: return 0; 1216: } 1217: 1218: /* Fail for floating point values, since the caller of this function 1219: does not have code to deal with them. */ 1220: if (GET_MODE_CLASS (GET_MODE (loop_final_value)) == MODE_FLOAT 1.1.1.2 root 1221: || GET_MODE_CLASS (GET_MODE (loop_initial_value)) == MODE_FLOAT) 1.1 root 1222: { 1223: if (loop_dump_stream) 1224: fprintf (loop_dump_stream, 1225: "Preconditioning: Floating point final or initial value.\n"); 1226: return 0; 1227: } 1228: 1229: /* Now set initial_value to be the iteration_var, since that may be a 1230: simpler expression, and is guaranteed to be correct if all of the 1231: above tests succeed. 1232: 1233: We can not use the initial_value as calculated, because it will be 1234: one too small for loops of the form "while (i-- > 0)". We can not 1235: emit code before the loop_skip_over insns to fix this problem as this 1236: will then give a number one too large for loops of the form 1237: "while (--i > 0)". 1238: 1239: Note that all loops that reach here are entered at the top, because 1240: this function is not called if the loop starts with a jump. */ 1241: 1242: /* Fail if loop_iteration_var is not live before loop_start, since we need 1243: to test its value in the preconditioning code. */ 1244: 1245: if (uid_luid[regno_first_uid[REGNO (loop_iteration_var)]] 1246: > INSN_LUID (loop_start)) 1247: { 1248: if (loop_dump_stream) 1249: fprintf (loop_dump_stream, 1250: "Preconditioning: Iteration var not live before loop start.\n"); 1251: return 0; 1252: } 1253: 1254: *initial_value = loop_iteration_var; 1255: *increment = loop_increment; 1256: *final_value = loop_final_value; 1257: 1258: /* Success! */ 1259: if (loop_dump_stream) 1260: fprintf (loop_dump_stream, "Preconditioning: Successful.\n"); 1261: return 1; 1262: } 1263: 1264: 1265: /* All pseudo-registers must be mapped to themselves. Two hard registers 1266: must be mapped, VIRTUAL_STACK_VARS_REGNUM and VIRTUAL_INCOMING_ARGS_ 1267: REGNUM, to avoid function-inlining specific conversions of these 1268: registers. All other hard regs can not be mapped because they may be 1269: used with different 1270: modes. */ 1271: 1272: static void 1273: init_reg_map (map, maxregnum) 1274: struct inline_remap *map; 1275: int maxregnum; 1276: { 1277: int i; 1278: 1279: for (i = maxregnum - 1; i > LAST_VIRTUAL_REGISTER; i--) 1280: map->reg_map[i] = regno_reg_rtx[i]; 1281: /* Just clear the rest of the entries. */ 1282: for (i = LAST_VIRTUAL_REGISTER; i >= 0; i--) 1283: map->reg_map[i] = 0; 1284: 1285: map->reg_map[VIRTUAL_STACK_VARS_REGNUM] 1286: = regno_reg_rtx[VIRTUAL_STACK_VARS_REGNUM]; 1287: map->reg_map[VIRTUAL_INCOMING_ARGS_REGNUM] 1288: = regno_reg_rtx[VIRTUAL_INCOMING_ARGS_REGNUM]; 1289: } 1290: 1291: /* Strength-reduction will often emit code for optimized biv/givs which 1292: calculates their value in a temporary register, and then copies the result 1293: to the iv. This procedure reconstructs the pattern computing the iv; 1294: verifying that all operands are of the proper form. 1295: 1296: The return value is the amount that the giv is incremented by. */ 1297: 1298: static rtx 1299: calculate_giv_inc (pattern, src_insn, regno) 1300: rtx pattern, src_insn; 1301: int regno; 1302: { 1303: rtx increment; 1.1.1.5 root 1304: rtx increment_total = 0; 1305: int tries = 0; 1.1 root 1306: 1.1.1.5 root 1307: retry: 1.1 root 1308: /* Verify that we have an increment insn here. First check for a plus 1309: as the set source. */ 1310: if (GET_CODE (SET_SRC (pattern)) != PLUS) 1311: { 1312: /* SR sometimes computes the new giv value in a temp, then copies it 1313: to the new_reg. */ 1314: src_insn = PREV_INSN (src_insn); 1315: pattern = PATTERN (src_insn); 1316: if (GET_CODE (SET_SRC (pattern)) != PLUS) 1317: abort (); 1318: 1319: /* The last insn emitted is not needed, so delete it to avoid confusing 1320: the second cse pass. This insn sets the giv unnecessarily. */ 1321: delete_insn (get_last_insn ()); 1322: } 1323: 1324: /* Verify that we have a constant as the second operand of the plus. */ 1325: increment = XEXP (SET_SRC (pattern), 1); 1326: if (GET_CODE (increment) != CONST_INT) 1327: { 1328: /* SR sometimes puts the constant in a register, especially if it is 1329: too big to be an add immed operand. */ 1.1.1.5 root 1330: src_insn = PREV_INSN (src_insn); 1331: increment = SET_SRC (PATTERN (src_insn)); 1.1 root 1332: 1333: /* SR may have used LO_SUM to compute the constant if it is too large 1334: for a load immed operand. In this case, the constant is in operand 1335: one of the LO_SUM rtx. */ 1336: if (GET_CODE (increment) == LO_SUM) 1337: increment = XEXP (increment, 1); 1.1.1.7 ! root 1338: else if (GET_CODE (increment) == IOR) ! 1339: { ! 1340: /* The rs6000 port loads some constants with IOR. */ ! 1341: rtx second_part = XEXP (increment, 1); ! 1342: ! 1343: src_insn = PREV_INSN (src_insn); ! 1344: increment = SET_SRC (PATTERN (src_insn)); ! 1345: /* Don't need the last insn anymore. */ ! 1346: delete_insn (get_last_insn ()); ! 1347: ! 1348: if (GET_CODE (second_part) != CONST_INT ! 1349: || GET_CODE (increment) != CONST_INT) ! 1350: abort (); ! 1351: ! 1352: increment = GEN_INT (INTVAL (increment) | INTVAL (second_part)); ! 1353: } 1.1 root 1354: 1355: if (GET_CODE (increment) != CONST_INT) 1356: abort (); 1357: 1.1.1.7 ! root 1358: /* The insn loading the constant into a register is no longer needed, 1.1 root 1359: so delete it. */ 1360: delete_insn (get_last_insn ()); 1361: } 1362: 1.1.1.5 root 1363: if (increment_total) 1364: increment_total = GEN_INT (INTVAL (increment_total) + INTVAL (increment)); 1365: else 1366: increment_total = increment; 1367: 1368: /* Check that the source register is the same as the register we expected 1369: to see as the source. If not, something is seriously wrong. */ 1.1 root 1370: if (GET_CODE (XEXP (SET_SRC (pattern), 0)) != REG 1371: || REGNO (XEXP (SET_SRC (pattern), 0)) != regno) 1.1.1.5 root 1372: { 1373: /* Some machines (e.g. the romp), may emit two add instructions for 1374: certain constants, so lets try looking for another add immediately 1375: before this one if we have only seen one add insn so far. */ 1376: 1377: if (tries == 0) 1378: { 1379: tries++; 1380: 1381: src_insn = PREV_INSN (src_insn); 1382: pattern = PATTERN (src_insn); 1383: 1384: delete_insn (get_last_insn ()); 1385: 1386: goto retry; 1387: } 1388: 1389: abort (); 1390: } 1391: 1392: return increment_total; 1393: } 1394: 1395: /* Copy REG_NOTES, except for insn references, because not all insn_map 1396: entries are valid yet. We do need to copy registers now though, because 1397: the reg_map entries can change during copying. */ 1398: 1399: static rtx 1400: initial_reg_note_copy (notes, map) 1401: rtx notes; 1402: struct inline_remap *map; 1403: { 1404: rtx copy; 1405: 1406: if (notes == 0) 1407: return 0; 1408: 1409: copy = rtx_alloc (GET_CODE (notes)); 1410: PUT_MODE (copy, GET_MODE (notes)); 1411: 1412: if (GET_CODE (notes) == EXPR_LIST) 1413: XEXP (copy, 0) = copy_rtx_and_substitute (XEXP (notes, 0), map); 1414: else if (GET_CODE (notes) == INSN_LIST) 1415: /* Don't substitute for these yet. */ 1416: XEXP (copy, 0) = XEXP (notes, 0); 1417: else 1.1 root 1418: abort (); 1419: 1.1.1.5 root 1420: XEXP (copy, 1) = initial_reg_note_copy (XEXP (notes, 1), map); 1421: 1422: return copy; 1.1 root 1423: } 1424: 1.1.1.5 root 1425: /* Fixup insn references in copied REG_NOTES. */ 1426: 1427: static void 1428: final_reg_note_copy (notes, map) 1429: rtx notes; 1430: struct inline_remap *map; 1431: { 1432: rtx note; 1433: 1434: for (note = notes; note; note = XEXP (note, 1)) 1435: if (GET_CODE (note) == INSN_LIST) 1436: XEXP (note, 0) = map->insn_map[INSN_UID (XEXP (note, 0))]; 1437: } 1.1 root 1438: 1439: /* Copy each instruction in the loop, substituting from map as appropriate. 1440: This is very similar to a loop in expand_inline_function. */ 1441: 1442: static void 1443: copy_loop_body (copy_start, copy_end, map, exit_label, last_iteration, 1444: unroll_type, start_label, loop_end, insert_before, 1445: copy_notes_from) 1446: rtx copy_start, copy_end; 1447: struct inline_remap *map; 1.1.1.4 root 1448: rtx exit_label; 1.1 root 1449: int last_iteration; 1450: enum unroll_types unroll_type; 1451: rtx start_label, loop_end, insert_before, copy_notes_from; 1452: { 1453: rtx insn, pattern; 1454: rtx tem, copy; 1455: int dest_reg_was_split, i; 1456: rtx cc0_insn = 0; 1457: rtx final_label = 0; 1458: rtx giv_inc, giv_dest_reg, giv_src_reg; 1459: 1460: /* If this isn't the last iteration, then map any references to the 1461: start_label to final_label. Final label will then be emitted immediately 1462: after the end of this loop body if it was ever used. 1463: 1464: If this is the last iteration, then map references to the start_label 1465: to itself. */ 1466: if (! last_iteration) 1467: { 1468: final_label = gen_label_rtx (); 1469: map->label_map[CODE_LABEL_NUMBER (start_label)] = final_label; 1470: } 1471: else 1472: map->label_map[CODE_LABEL_NUMBER (start_label)] = start_label; 1473: 1474: start_sequence (); 1475: 1476: insn = copy_start; 1477: do 1478: { 1479: insn = NEXT_INSN (insn); 1480: 1481: map->orig_asm_operands_vector = 0; 1482: 1483: switch (GET_CODE (insn)) 1484: { 1485: case INSN: 1486: pattern = PATTERN (insn); 1487: copy = 0; 1488: giv_inc = 0; 1489: 1490: /* Check to see if this is a giv that has been combined with 1491: some split address givs. (Combined in the sense that 1492: `combine_givs' in loop.c has put two givs in the same register.) 1493: In this case, we must search all givs based on the same biv to 1494: find the address givs. Then split the address givs. 1495: Do this before splitting the giv, since that may map the 1496: SET_DEST to a new register. */ 1497: 1498: if (GET_CODE (pattern) == SET 1499: && GET_CODE (SET_DEST (pattern)) == REG 1500: && addr_combined_regs[REGNO (SET_DEST (pattern))]) 1501: { 1502: struct iv_class *bl; 1503: struct induction *v, *tv; 1504: int regno = REGNO (SET_DEST (pattern)); 1505: 1506: v = addr_combined_regs[REGNO (SET_DEST (pattern))]; 1507: bl = reg_biv_class[REGNO (v->src_reg)]; 1508: 1509: /* Although the giv_inc amount is not needed here, we must call 1510: calculate_giv_inc here since it might try to delete the 1511: last insn emitted. If we wait until later to call it, 1512: we might accidentally delete insns generated immediately 1513: below by emit_unrolled_add. */ 1514: 1515: giv_inc = calculate_giv_inc (pattern, insn, regno); 1516: 1517: /* Now find all address giv's that were combined with this 1518: giv 'v'. */ 1519: for (tv = bl->giv; tv; tv = tv->next_iv) 1520: if (tv->giv_type == DEST_ADDR && tv->same == v) 1521: { 1.1.1.3 root 1522: int this_giv_inc = INTVAL (giv_inc); 1523: 1524: /* Scale this_giv_inc if the multiplicative factors of 1525: the two givs are different. */ 1526: if (tv->mult_val != v->mult_val) 1527: this_giv_inc = (this_giv_inc / INTVAL (v->mult_val) 1528: * INTVAL (tv->mult_val)); 1529: 1530: tv->dest_reg = plus_constant (tv->dest_reg, this_giv_inc); 1.1 root 1531: *tv->location = tv->dest_reg; 1532: 1533: if (last_iteration && unroll_type != UNROLL_COMPLETELY) 1534: { 1535: /* Must emit an insn to increment the split address 1536: giv. Add in the const_adjust field in case there 1537: was a constant eliminated from the address. */ 1538: rtx value, dest_reg; 1539: 1540: /* tv->dest_reg will be either a bare register, 1541: or else a register plus a constant. */ 1542: if (GET_CODE (tv->dest_reg) == REG) 1543: dest_reg = tv->dest_reg; 1544: else 1545: dest_reg = XEXP (tv->dest_reg, 0); 1546: 1.1.1.7 ! root 1547: /* Check for shared address givs, and avoid ! 1548: incrementing the shared psuedo reg more than ! 1549: once. */ ! 1550: if (! (tv != v && tv->insn == v->insn ! 1551: && tv->new_reg == v->new_reg)) ! 1552: { ! 1553: /* tv->dest_reg may actually be a (PLUS (REG) ! 1554: (CONST)) here, so we must call plus_constant ! 1555: to add the const_adjust amount before calling ! 1556: emit_unrolled_add below. */ ! 1557: value = plus_constant (tv->dest_reg, ! 1558: tv->const_adjust); ! 1559: ! 1560: /* The constant could be too large for an add ! 1561: immediate, so can't directly emit an insn ! 1562: here. */ ! 1563: emit_unrolled_add (dest_reg, XEXP (value, 0), ! 1564: XEXP (value, 1)); ! 1565: } 1.1 root 1566: 1567: /* Reset the giv to be just the register again, in case 1.1.1.2 root 1568: it is used after the set we have just emitted. 1569: We must subtract the const_adjust factor added in 1570: above. */ 1571: tv->dest_reg = plus_constant (dest_reg, 1572: - tv->const_adjust); 1.1 root 1573: *tv->location = tv->dest_reg; 1574: } 1575: } 1576: } 1577: 1578: /* If this is a setting of a splittable variable, then determine 1579: how to split the variable, create a new set based on this split, 1580: and set up the reg_map so that later uses of the variable will 1581: use the new split variable. */ 1582: 1583: dest_reg_was_split = 0; 1584: 1585: if (GET_CODE (pattern) == SET 1586: && GET_CODE (SET_DEST (pattern)) == REG 1587: && splittable_regs[REGNO (SET_DEST (pattern))]) 1588: { 1589: int regno = REGNO (SET_DEST (pattern)); 1590: 1591: dest_reg_was_split = 1; 1592: 1593: /* Compute the increment value for the giv, if it wasn't 1594: already computed above. */ 1595: 1596: if (giv_inc == 0) 1597: giv_inc = calculate_giv_inc (pattern, insn, regno); 1598: giv_dest_reg = SET_DEST (pattern); 1599: giv_src_reg = SET_DEST (pattern); 1600: 1601: if (unroll_type == UNROLL_COMPLETELY) 1602: { 1603: /* Completely unrolling the loop. Set the induction 1604: variable to a known constant value. */ 1605: 1606: /* The value in splittable_regs may be an invariant 1607: value, so we must use plus_constant here. */ 1608: splittable_regs[regno] 1609: = plus_constant (splittable_regs[regno], INTVAL (giv_inc)); 1610: 1611: if (GET_CODE (splittable_regs[regno]) == PLUS) 1612: { 1613: giv_src_reg = XEXP (splittable_regs[regno], 0); 1614: giv_inc = XEXP (splittable_regs[regno], 1); 1615: } 1616: else 1617: { 1618: /* The splittable_regs value must be a REG or a 1619: CONST_INT, so put the entire value in the giv_src_reg 1620: variable. */ 1621: giv_src_reg = splittable_regs[regno]; 1622: giv_inc = const0_rtx; 1623: } 1624: } 1625: else 1626: { 1627: /* Partially unrolling loop. Create a new pseudo 1628: register for the iteration variable, and set it to 1629: be a constant plus the original register. Except 1630: on the last iteration, when the result has to 1631: go back into the original iteration var register. */ 1632: 1633: /* Handle bivs which must be mapped to a new register 1634: when split. This happens for bivs which need their 1635: final value set before loop entry. The new register 1636: for the biv was stored in the biv's first struct 1637: induction entry by find_splittable_regs. */ 1638: 1639: if (regno < max_reg_before_loop 1640: && reg_iv_type[regno] == BASIC_INDUCT) 1641: { 1642: giv_src_reg = reg_biv_class[regno]->biv->src_reg; 1643: giv_dest_reg = giv_src_reg; 1644: } 1645: 1646: #if 0 1647: /* If non-reduced/final-value givs were split, then 1648: this would have to remap those givs also. See 1649: find_splittable_regs. */ 1650: #endif 1651: 1652: splittable_regs[regno] 1.1.1.4 root 1653: = GEN_INT (INTVAL (giv_inc) 1.1 root 1654: + INTVAL (splittable_regs[regno])); 1655: giv_inc = splittable_regs[regno]; 1656: 1657: /* Now split the induction variable by changing the dest 1658: of this insn to a new register, and setting its 1659: reg_map entry to point to this new register. 1660: 1661: If this is the last iteration, and this is the last insn 1662: that will update the iv, then reuse the original dest, 1663: to ensure that the iv will have the proper value when 1664: the loop exits or repeats. 1665: 1666: Using splittable_regs_updates here like this is safe, 1667: because it can only be greater than one if all 1668: instructions modifying the iv are always executed in 1669: order. */ 1670: 1671: if (! last_iteration 1672: || (splittable_regs_updates[regno]-- != 1)) 1673: { 1674: tem = gen_reg_rtx (GET_MODE (giv_src_reg)); 1675: giv_dest_reg = tem; 1676: map->reg_map[regno] = tem; 1677: } 1678: else 1679: map->reg_map[regno] = giv_src_reg; 1680: } 1681: 1682: /* The constant being added could be too large for an add 1683: immediate, so can't directly emit an insn here. */ 1684: emit_unrolled_add (giv_dest_reg, giv_src_reg, giv_inc); 1685: copy = get_last_insn (); 1686: pattern = PATTERN (copy); 1687: } 1688: else 1689: { 1690: pattern = copy_rtx_and_substitute (pattern, map); 1691: copy = emit_insn (pattern); 1692: } 1.1.1.5 root 1693: REG_NOTES (copy) = initial_reg_note_copy (REG_NOTES (insn), map); 1.1 root 1694: 1695: #ifdef HAVE_cc0 1696: /* If this insn is setting CC0, it may need to look at 1697: the insn that uses CC0 to see what type of insn it is. 1698: In that case, the call to recog via validate_change will 1699: fail. So don't substitute constants here. Instead, 1700: do it when we emit the following insn. 1701: 1702: For example, see the pyr.md file. That machine has signed and 1703: unsigned compares. The compare patterns must check the 1704: following branch insn to see which what kind of compare to 1705: emit. 1706: 1707: If the previous insn set CC0, substitute constants on it as 1708: well. */ 1709: if (sets_cc0_p (copy) != 0) 1710: cc0_insn = copy; 1711: else 1712: { 1713: if (cc0_insn) 1714: try_constants (cc0_insn, map); 1715: cc0_insn = 0; 1716: try_constants (copy, map); 1717: } 1718: #else 1719: try_constants (copy, map); 1720: #endif 1721: 1722: /* Make split induction variable constants `permanent' since we 1723: know there are no backward branches across iteration variable 1724: settings which would invalidate this. */ 1725: if (dest_reg_was_split) 1726: { 1727: int regno = REGNO (SET_DEST (pattern)); 1728: 1.1.1.6 root 1729: if (regno < map->const_equiv_map_size 1730: && map->const_age_map[regno] == map->const_age) 1.1 root 1731: map->const_age_map[regno] = -1; 1732: } 1733: break; 1734: 1735: case JUMP_INSN: 1.1.1.5 root 1736: pattern = copy_rtx_and_substitute (PATTERN (insn), map); 1737: copy = emit_jump_insn (pattern); 1738: REG_NOTES (copy) = initial_reg_note_copy (REG_NOTES (insn), map); 1739: 1.1 root 1740: if (JUMP_LABEL (insn) == start_label && insn == copy_end 1741: && ! last_iteration) 1742: { 1743: /* This is a branch to the beginning of the loop; this is the 1744: last insn being copied; and this is not the last iteration. 1745: In this case, we want to change the original fall through 1746: case to be a branch past the end of the loop, and the 1747: original jump label case to fall_through. */ 1748: 1.1.1.7 ! root 1749: if (invert_exp (pattern, copy)) ! 1750: { ! 1751: if (! redirect_exp (&pattern, ! 1752: map->label_map[CODE_LABEL_NUMBER ! 1753: (JUMP_LABEL (insn))], ! 1754: exit_label, copy)) ! 1755: abort (); ! 1756: } ! 1757: else ! 1758: { ! 1759: rtx jmp; ! 1760: rtx lab = gen_label_rtx (); ! 1761: /* Can't do it by reversing the jump (probably becasue we ! 1762: couln't reverse the conditions), so emit a new ! 1763: jump_insn after COPY, and redirect the jump around ! 1764: that. */ ! 1765: jmp = emit_jump_insn_after (gen_jump (exit_label), copy); ! 1766: jmp = emit_barrier_after (jmp); ! 1767: emit_label_after (lab, jmp); ! 1768: LABEL_NUSES (lab) = 0; ! 1769: if (! redirect_exp (&pattern, ! 1770: map->label_map[CODE_LABEL_NUMBER ! 1771: (JUMP_LABEL (insn))], ! 1772: lab, copy)) ! 1773: abort (); ! 1774: } 1.1 root 1775: } 1776: 1777: #ifdef HAVE_cc0 1778: if (cc0_insn) 1779: try_constants (cc0_insn, map); 1780: cc0_insn = 0; 1781: #endif 1782: try_constants (copy, map); 1783: 1784: /* Set the jump label of COPY correctly to avoid problems with 1785: later passes of unroll_loop, if INSN had jump label set. */ 1786: if (JUMP_LABEL (insn)) 1787: { 1.1.1.4 root 1788: rtx label = 0; 1789: 1.1 root 1790: /* Can't use the label_map for every insn, since this may be 1791: the backward branch, and hence the label was not mapped. */ 1792: if (GET_CODE (pattern) == SET) 1793: { 1794: tem = SET_SRC (pattern); 1795: if (GET_CODE (tem) == LABEL_REF) 1.1.1.4 root 1796: label = XEXP (tem, 0); 1.1 root 1797: else if (GET_CODE (tem) == IF_THEN_ELSE) 1798: { 1799: if (XEXP (tem, 1) != pc_rtx) 1.1.1.4 root 1800: label = XEXP (XEXP (tem, 1), 0); 1.1 root 1801: else 1.1.1.4 root 1802: label = XEXP (XEXP (tem, 2), 0); 1.1 root 1803: } 1804: } 1.1.1.4 root 1805: 1806: if (label && GET_CODE (label) == CODE_LABEL) 1807: JUMP_LABEL (copy) = label; 1.1 root 1808: else 1809: { 1810: /* An unrecognizable jump insn, probably the entry jump 1811: for a switch statement. This label must have been mapped, 1812: so just use the label_map to get the new jump label. */ 1813: JUMP_LABEL (copy) = map->label_map[CODE_LABEL_NUMBER 1814: (JUMP_LABEL (insn))]; 1815: } 1816: 1817: /* If this is a non-local jump, then must increase the label 1818: use count so that the label will not be deleted when the 1819: original jump is deleted. */ 1820: LABEL_NUSES (JUMP_LABEL (copy))++; 1821: } 1822: else if (GET_CODE (PATTERN (copy)) == ADDR_VEC 1823: || GET_CODE (PATTERN (copy)) == ADDR_DIFF_VEC) 1824: { 1825: rtx pat = PATTERN (copy); 1826: int diff_vec_p = GET_CODE (pat) == ADDR_DIFF_VEC; 1827: int len = XVECLEN (pat, diff_vec_p); 1828: int i; 1829: 1830: for (i = 0; i < len; i++) 1831: LABEL_NUSES (XEXP (XVECEXP (pat, diff_vec_p, i), 0))++; 1832: } 1833: 1834: /* If this used to be a conditional jump insn but whose branch 1835: direction is now known, we must do something special. */ 1836: if (condjump_p (insn) && !simplejump_p (insn) && map->last_pc_value) 1837: { 1838: #ifdef HAVE_cc0 1839: /* The previous insn set cc0 for us. So delete it. */ 1840: delete_insn (PREV_INSN (copy)); 1841: #endif 1842: 1843: /* If this is now a no-op, delete it. */ 1844: if (map->last_pc_value == pc_rtx) 1845: { 1.1.1.7 ! root 1846: /* Don't let delete_insn delete the label referenced here, ! 1847: because we might possibly need it later for some other ! 1848: instruction in the loop. */ ! 1849: if (JUMP_LABEL (copy)) ! 1850: LABEL_NUSES (JUMP_LABEL (copy))++; 1.1 root 1851: delete_insn (copy); 1.1.1.7 ! root 1852: if (JUMP_LABEL (copy)) ! 1853: LABEL_NUSES (JUMP_LABEL (copy))--; 1.1 root 1854: copy = 0; 1855: } 1856: else 1857: /* Otherwise, this is unconditional jump so we must put a 1858: BARRIER after it. We could do some dead code elimination 1859: here, but jump.c will do it just as well. */ 1860: emit_barrier (); 1861: } 1862: break; 1863: 1864: case CALL_INSN: 1865: pattern = copy_rtx_and_substitute (PATTERN (insn), map); 1866: copy = emit_call_insn (pattern); 1.1.1.5 root 1867: REG_NOTES (copy) = initial_reg_note_copy (REG_NOTES (insn), map); 1.1 root 1868: 1.1.1.7 ! root 1869: /* Because the USAGE information potentially contains objects other ! 1870: than hard registers, we need to copy it. */ ! 1871: CALL_INSN_FUNCTION_USAGE (copy) = ! 1872: copy_rtx_and_substitute (CALL_INSN_FUNCTION_USAGE (insn), map); ! 1873: 1.1 root 1874: #ifdef HAVE_cc0 1875: if (cc0_insn) 1876: try_constants (cc0_insn, map); 1877: cc0_insn = 0; 1878: #endif 1879: try_constants (copy, map); 1880: 1881: /* Be lazy and assume CALL_INSNs clobber all hard registers. */ 1882: for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) 1883: map->const_equiv_map[i] = 0; 1884: break; 1885: 1886: case CODE_LABEL: 1887: /* If this is the loop start label, then we don't need to emit a 1888: copy of this label since no one will use it. */ 1889: 1890: if (insn != start_label) 1891: { 1892: copy = emit_label (map->label_map[CODE_LABEL_NUMBER (insn)]); 1893: map->const_age++; 1894: } 1895: break; 1896: 1897: case BARRIER: 1898: copy = emit_barrier (); 1899: break; 1900: 1901: case NOTE: 1.1.1.4 root 1902: /* VTOP notes are valid only before the loop exit test. If placed 1903: anywhere else, loop may generate bad code. */ 1904: 1905: if (NOTE_LINE_NUMBER (insn) != NOTE_INSN_DELETED 1906: && (NOTE_LINE_NUMBER (insn) != NOTE_INSN_LOOP_VTOP 1907: || (last_iteration && unroll_type != UNROLL_COMPLETELY))) 1.1 root 1908: copy = emit_note (NOTE_SOURCE_FILE (insn), 1909: NOTE_LINE_NUMBER (insn)); 1910: else 1911: copy = 0; 1912: break; 1913: 1914: default: 1915: abort (); 1916: break; 1917: } 1918: 1919: map->insn_map[INSN_UID (insn)] = copy; 1920: } 1921: while (insn != copy_end); 1922: 1.1.1.5 root 1923: /* Now finish coping the REG_NOTES. */ 1.1 root 1924: insn = copy_start; 1925: do 1926: { 1927: insn = NEXT_INSN (insn); 1928: if ((GET_CODE (insn) == INSN || GET_CODE (insn) == JUMP_INSN 1929: || GET_CODE (insn) == CALL_INSN) 1930: && map->insn_map[INSN_UID (insn)]) 1.1.1.5 root 1931: final_reg_note_copy (REG_NOTES (map->insn_map[INSN_UID (insn)]), map); 1.1 root 1932: } 1933: while (insn != copy_end); 1934: 1935: /* There may be notes between copy_notes_from and loop_end. Emit a copy of 1936: each of these notes here, since there may be some important ones, such as 1937: NOTE_INSN_BLOCK_END notes, in this group. We don't do this on the last 1938: iteration, because the original notes won't be deleted. 1939: 1940: We can't use insert_before here, because when from preconditioning, 1941: insert_before points before the loop. We can't use copy_end, because 1942: there may be insns already inserted after it (which we don't want to 1943: copy) when not from preconditioning code. */ 1944: 1945: if (! last_iteration) 1946: { 1947: for (insn = copy_notes_from; insn != loop_end; insn = NEXT_INSN (insn)) 1948: { 1949: if (GET_CODE (insn) == NOTE 1950: && NOTE_LINE_NUMBER (insn) != NOTE_INSN_DELETED) 1951: emit_note (NOTE_SOURCE_FILE (insn), NOTE_LINE_NUMBER (insn)); 1952: } 1953: } 1954: 1955: if (final_label && LABEL_NUSES (final_label) > 0) 1956: emit_label (final_label); 1957: 1958: tem = gen_sequence (); 1959: end_sequence (); 1960: emit_insn_before (tem, insert_before); 1961: } 1962: 1963: /* Emit an insn, using the expand_binop to ensure that a valid insn is 1964: emitted. This will correctly handle the case where the increment value 1965: won't fit in the immediate field of a PLUS insns. */ 1966: 1967: void 1968: emit_unrolled_add (dest_reg, src_reg, increment) 1969: rtx dest_reg, src_reg, increment; 1970: { 1971: rtx result; 1972: 1973: result = expand_binop (GET_MODE (dest_reg), add_optab, src_reg, increment, 1974: dest_reg, 0, OPTAB_LIB_WIDEN); 1975: 1976: if (dest_reg != result) 1977: emit_move_insn (dest_reg, result); 1978: } 1979: 1980: /* Searches the insns between INSN and LOOP_END. Returns 1 if there 1981: is a backward branch in that range that branches to somewhere between 1982: LOOP_START and INSN. Returns 0 otherwise. */ 1983: 1.1.1.3 root 1984: /* ??? This is quadratic algorithm. Could be rewritten to be linear. 1.1 root 1985: In practice, this is not a problem, because this function is seldom called, 1986: and uses a negligible amount of CPU time on average. */ 1987: 1988: static int 1989: back_branch_in_range_p (insn, loop_start, loop_end) 1990: rtx insn; 1991: rtx loop_start, loop_end; 1992: { 1993: rtx p, q, target_insn; 1994: 1995: /* Stop before we get to the backward branch at the end of the loop. */ 1996: loop_end = prev_nonnote_insn (loop_end); 1997: if (GET_CODE (loop_end) == BARRIER) 1998: loop_end = PREV_INSN (loop_end); 1999: 2000: /* Check in case insn has been deleted, search forward for first non 2001: deleted insn following it. */ 2002: while (INSN_DELETED_P (insn)) 2003: insn = NEXT_INSN (insn); 2004: 2005: /* Check for the case where insn is the last insn in the loop. */ 2006: if (insn == loop_end) 2007: return 0; 2008: 2009: for (p = NEXT_INSN (insn); p != loop_end; p = NEXT_INSN (p)) 2010: { 2011: if (GET_CODE (p) == JUMP_INSN) 2012: { 2013: target_insn = JUMP_LABEL (p); 2014: 2015: /* Search from loop_start to insn, to see if one of them is 2016: the target_insn. We can't use INSN_LUID comparisons here, 2017: since insn may not have an LUID entry. */ 2018: for (q = loop_start; q != insn; q = NEXT_INSN (q)) 2019: if (q == target_insn) 2020: return 1; 2021: } 2022: } 2023: 2024: return 0; 2025: } 2026: 2027: /* Try to generate the simplest rtx for the expression 2028: (PLUS (MULT mult1 mult2) add1). This is used to calculate the initial 2029: value of giv's. */ 2030: 2031: static rtx 2032: fold_rtx_mult_add (mult1, mult2, add1, mode) 2033: rtx mult1, mult2, add1; 2034: enum machine_mode mode; 2035: { 2036: rtx temp, mult_res; 2037: rtx result; 2038: 2039: /* The modes must all be the same. This should always be true. For now, 2040: check to make sure. */ 2041: if ((GET_MODE (mult1) != mode && GET_MODE (mult1) != VOIDmode) 2042: || (GET_MODE (mult2) != mode && GET_MODE (mult2) != VOIDmode) 2043: || (GET_MODE (add1) != mode && GET_MODE (add1) != VOIDmode)) 2044: abort (); 2045: 2046: /* Ensure that if at least one of mult1/mult2 are constant, then mult2 2047: will be a constant. */ 2048: if (GET_CODE (mult1) == CONST_INT) 2049: { 2050: temp = mult2; 2051: mult2 = mult1; 2052: mult1 = temp; 2053: } 2054: 2055: mult_res = simplify_binary_operation (MULT, mode, mult1, mult2); 2056: if (! mult_res) 2057: mult_res = gen_rtx (MULT, mode, mult1, mult2); 2058: 2059: /* Again, put the constant second. */ 2060: if (GET_CODE (add1) == CONST_INT) 2061: { 2062: temp = add1; 2063: add1 = mult_res; 2064: mult_res = temp; 2065: } 2066: 2067: result = simplify_binary_operation (PLUS, mode, add1, mult_res); 2068: if (! result) 2069: result = gen_rtx (PLUS, mode, add1, mult_res); 2070: 2071: return result; 2072: } 2073: 2074: /* Searches the list of induction struct's for the biv BL, to try to calculate 2075: the total increment value for one iteration of the loop as a constant. 2076: 2077: Returns the increment value as an rtx, simplified as much as possible, 2078: if it can be calculated. Otherwise, returns 0. */ 2079: 2080: rtx 2081: biv_total_increment (bl, loop_start, loop_end) 2082: struct iv_class *bl; 2083: rtx loop_start, loop_end; 2084: { 2085: struct induction *v; 2086: rtx result; 2087: 2088: /* For increment, must check every instruction that sets it. Each 2089: instruction must be executed only once each time through the loop. 2090: To verify this, we check that the the insn is always executed, and that 2091: there are no backward branches after the insn that branch to before it. 2092: Also, the insn must have a mult_val of one (to make sure it really is 2093: an increment). */ 2094: 2095: result = const0_rtx; 2096: for (v = bl->biv; v; v = v->next_iv) 2097: { 2098: if (v->always_computable && v->mult_val == const1_rtx 2099: && ! back_branch_in_range_p (v->insn, loop_start, loop_end)) 2100: result = fold_rtx_mult_add (result, const1_rtx, v->add_val, v->mode); 2101: else 2102: return 0; 2103: } 2104: 2105: return result; 2106: } 2107: 2108: /* Determine the initial value of the iteration variable, and the amount 2109: that it is incremented each loop. Use the tables constructed by 2110: the strength reduction pass to calculate these values. 2111: 2112: Initial_value and/or increment are set to zero if their values could not 2113: be calculated. */ 2114: 2115: static void 2116: iteration_info (iteration_var, initial_value, increment, loop_start, loop_end) 2117: rtx iteration_var, *initial_value, *increment; 2118: rtx loop_start, loop_end; 2119: { 2120: struct iv_class *bl; 2121: struct induction *v, *b; 2122: 2123: /* Clear the result values, in case no answer can be found. */ 2124: *initial_value = 0; 2125: *increment = 0; 2126: 2127: /* The iteration variable can be either a giv or a biv. Check to see 2128: which it is, and compute the variable's initial value, and increment 2129: value if possible. */ 2130: 2131: /* If this is a new register, can't handle it since we don't have any 2132: reg_iv_type entry for it. */ 2133: if (REGNO (iteration_var) >= max_reg_before_loop) 2134: { 2135: if (loop_dump_stream) 2136: fprintf (loop_dump_stream, 2137: "Loop unrolling: No reg_iv_type entry for iteration var.\n"); 2138: return; 2139: } 2140: /* Reject iteration variables larger than the host long size, since they 2141: could result in a number of iterations greater than the range of our 2142: `unsigned long' variable loop_n_iterations. */ 2143: else if (GET_MODE_BITSIZE (GET_MODE (iteration_var)) > HOST_BITS_PER_LONG) 2144: { 2145: if (loop_dump_stream) 2146: fprintf (loop_dump_stream, 2147: "Loop unrolling: Iteration var rejected because mode larger than host long.\n"); 2148: return; 2149: } 2150: else if (GET_MODE_CLASS (GET_MODE (iteration_var)) != MODE_INT) 2151: { 2152: if (loop_dump_stream) 2153: fprintf (loop_dump_stream, 1.1.1.2 root 2154: "Loop unrolling: Iteration var not an integer.\n"); 1.1 root 2155: return; 2156: } 2157: else if (reg_iv_type[REGNO (iteration_var)] == BASIC_INDUCT) 2158: { 2159: /* Grab initial value, only useful if it is a constant. */ 2160: bl = reg_biv_class[REGNO (iteration_var)]; 2161: *initial_value = bl->initial_value; 2162: 2163: *increment = biv_total_increment (bl, loop_start, loop_end); 2164: } 2165: else if (reg_iv_type[REGNO (iteration_var)] == GENERAL_INDUCT) 2166: { 2167: #if 1 2168: /* ??? The code below does not work because the incorrect number of 2169: iterations is calculated when the biv is incremented after the giv 2170: is set (which is the usual case). This can probably be accounted 2171: for by biasing the initial_value by subtracting the amount of the 2172: increment that occurs between the giv set and the giv test. However, 2173: a giv as an iterator is very rare, so it does not seem worthwhile 2174: to handle this. */ 2175: /* ??? An example failure is: i = 6; do {;} while (i++ < 9). */ 2176: if (loop_dump_stream) 2177: fprintf (loop_dump_stream, 2178: "Loop unrolling: Giv iterators are not handled.\n"); 2179: return; 2180: #else 2181: /* Initial value is mult_val times the biv's initial value plus 2182: add_val. Only useful if it is a constant. */ 2183: v = reg_iv_info[REGNO (iteration_var)]; 2184: bl = reg_biv_class[REGNO (v->src_reg)]; 2185: *initial_value = fold_rtx_mult_add (v->mult_val, bl->initial_value, 2186: v->add_val, v->mode); 2187: 2188: /* Increment value is mult_val times the increment value of the biv. */ 2189: 2190: *increment = biv_total_increment (bl, loop_start, loop_end); 2191: if (*increment) 2192: *increment = fold_rtx_mult_add (v->mult_val, *increment, const0_rtx, 2193: v->mode); 2194: #endif 2195: } 2196: else 2197: { 2198: if (loop_dump_stream) 2199: fprintf (loop_dump_stream, 2200: "Loop unrolling: Not basic or general induction var.\n"); 2201: return; 2202: } 2203: } 2204: 2205: /* Calculate the approximate final value of the iteration variable 2206: which has an loop exit test with code COMPARISON_CODE and comparison value 2207: of COMPARISON_VALUE. Also returns an indication of whether the comparison 2208: was signed or unsigned, and the direction of the comparison. This info is 2209: needed to calculate the number of loop iterations. */ 2210: 2211: static rtx 2212: approx_final_value (comparison_code, comparison_value, unsigned_p, compare_dir) 2213: enum rtx_code comparison_code; 2214: rtx comparison_value; 2215: int *unsigned_p; 2216: int *compare_dir; 2217: { 2218: /* Calculate the final value of the induction variable. 2219: The exact final value depends on the branch operator, and increment sign. 2220: This is only an approximate value. It will be wrong if the iteration 2221: variable is not incremented by one each time through the loop, and 2222: approx final value - start value % increment != 0. */ 2223: 2224: *unsigned_p = 0; 2225: switch (comparison_code) 2226: { 2227: case LEU: 2228: *unsigned_p = 1; 2229: case LE: 2230: *compare_dir = 1; 2231: return plus_constant (comparison_value, 1); 2232: case GEU: 2233: *unsigned_p = 1; 2234: case GE: 2235: *compare_dir = -1; 2236: return plus_constant (comparison_value, -1); 2237: case EQ: 2238: /* Can not calculate a final value for this case. */ 2239: *compare_dir = 0; 2240: return 0; 2241: case LTU: 2242: *unsigned_p = 1; 2243: case LT: 2244: *compare_dir = 1; 2245: return comparison_value; 2246: break; 2247: case GTU: 2248: *unsigned_p = 1; 2249: case GT: 2250: *compare_dir = -1; 2251: return comparison_value; 2252: case NE: 2253: *compare_dir = 0; 2254: return comparison_value; 2255: default: 2256: abort (); 2257: } 2258: } 2259: 2260: /* For each biv and giv, determine whether it can be safely split into 2261: a different variable for each unrolled copy of the loop body. If it 2262: is safe to split, then indicate that by saving some useful info 2263: in the splittable_regs array. 2264: 2265: If the loop is being completely unrolled, then splittable_regs will hold 2266: the current value of the induction variable while the loop is unrolled. 2267: It must be set to the initial value of the induction variable here. 2268: Otherwise, splittable_regs will hold the difference between the current 2269: value of the induction variable and the value the induction variable had 1.1.1.6 root 2270: at the top of the loop. It must be set to the value 0 here. 2271: 2272: Returns the total number of instructions that set registers that are 2273: splittable. */ 1.1 root 2274: 2275: /* ?? If the loop is only unrolled twice, then most of the restrictions to 2276: constant values are unnecessary, since we can easily calculate increment 2277: values in this case even if nothing is constant. The increment value 2278: should not involve a multiply however. */ 2279: 2280: /* ?? Even if the biv/giv increment values aren't constant, it may still 2281: be beneficial to split the variable if the loop is only unrolled a few 2282: times, since multiplies by small integers (1,2,3,4) are very cheap. */ 2283: 2284: static int 2285: find_splittable_regs (unroll_type, loop_start, loop_end, end_insert_before, 2286: unroll_number) 2287: enum unroll_types unroll_type; 2288: rtx loop_start, loop_end; 2289: rtx end_insert_before; 2290: int unroll_number; 2291: { 2292: struct iv_class *bl; 1.1.1.4 root 2293: struct induction *v; 1.1 root 2294: rtx increment, tem; 2295: rtx biv_final_value; 2296: int biv_splittable; 2297: int result = 0; 2298: 2299: for (bl = loop_iv_list; bl; bl = bl->next) 2300: { 2301: /* Biv_total_increment must return a constant value, 2302: otherwise we can not calculate the split values. */ 2303: 2304: increment = biv_total_increment (bl, loop_start, loop_end); 2305: if (! increment || GET_CODE (increment) != CONST_INT) 2306: continue; 2307: 2308: /* The loop must be unrolled completely, or else have a known number 2309: of iterations and only one exit, or else the biv must be dead 2310: outside the loop, or else the final value must be known. Otherwise, 2311: it is unsafe to split the biv since it may not have the proper 2312: value on loop exit. */ 2313: 2314: /* loop_number_exit_labels is non-zero if the loop has an exit other than 2315: a fall through at the end. */ 2316: 2317: biv_splittable = 1; 2318: biv_final_value = 0; 2319: if (unroll_type != UNROLL_COMPLETELY 2320: && (loop_number_exit_labels[uid_loop_num[INSN_UID (loop_start)]] 2321: || unroll_type == UNROLL_NAIVE) 2322: && (uid_luid[regno_last_uid[bl->regno]] >= INSN_LUID (loop_end) 2323: || ! bl->init_insn 2324: || INSN_UID (bl->init_insn) >= max_uid_for_loop 2325: || (uid_luid[regno_first_uid[bl->regno]] 2326: < INSN_LUID (bl->init_insn)) 2327: || reg_mentioned_p (bl->biv->dest_reg, SET_SRC (bl->init_set))) 2328: && ! (biv_final_value = final_biv_value (bl, loop_start, loop_end))) 2329: biv_splittable = 0; 2330: 1.1.1.4 root 2331: /* If any of the insns setting the BIV don't do so with a simple 2332: PLUS, we don't know how to split it. */ 2333: for (v = bl->biv; biv_splittable && v; v = v->next_iv) 2334: if ((tem = single_set (v->insn)) == 0 2335: || GET_CODE (SET_DEST (tem)) != REG 2336: || REGNO (SET_DEST (tem)) != bl->regno 2337: || GET_CODE (SET_SRC (tem)) != PLUS) 2338: biv_splittable = 0; 2339: 1.1 root 2340: /* If final value is non-zero, then must emit an instruction which sets 2341: the value of the biv to the proper value. This is done after 2342: handling all of the givs, since some of them may need to use the 2343: biv's value in their initialization code. */ 2344: 2345: /* This biv is splittable. If completely unrolling the loop, save 2346: the biv's initial value. Otherwise, save the constant zero. */ 2347: 2348: if (biv_splittable == 1) 2349: { 2350: if (unroll_type == UNROLL_COMPLETELY) 2351: { 2352: /* If the initial value of the biv is itself (i.e. it is too 2353: complicated for strength_reduce to compute), or is a hard 1.1.1.2 root 2354: register, then we must create a new pseudo reg to hold the 1.1 root 2355: initial value of the biv. */ 2356: 2357: if (GET_CODE (bl->initial_value) == REG 2358: && (REGNO (bl->initial_value) == bl->regno 2359: || REGNO (bl->initial_value) < FIRST_PSEUDO_REGISTER)) 2360: { 2361: rtx tem = gen_reg_rtx (bl->biv->mode); 2362: 2363: emit_insn_before (gen_move_insn (tem, bl->biv->src_reg), 2364: loop_start); 2365: 2366: if (loop_dump_stream) 2367: fprintf (loop_dump_stream, "Biv %d initial value remapped to %d.\n", 2368: bl->regno, REGNO (tem)); 2369: 2370: splittable_regs[bl->regno] = tem; 2371: } 2372: else 2373: splittable_regs[bl->regno] = bl->initial_value; 2374: } 2375: else 2376: splittable_regs[bl->regno] = const0_rtx; 2377: 2378: /* Save the number of instructions that modify the biv, so that 2379: we can treat the last one specially. */ 2380: 2381: splittable_regs_updates[bl->regno] = bl->biv_count; 1.1.1.6 root 2382: result += bl->biv_count; 1.1 root 2383: 2384: if (loop_dump_stream) 2385: fprintf (loop_dump_stream, 2386: "Biv %d safe to split.\n", bl->regno); 2387: } 2388: 2389: /* Check every giv that depends on this biv to see whether it is 2390: splittable also. Even if the biv isn't splittable, givs which 2391: depend on it may be splittable if the biv is live outside the 2392: loop, and the givs aren't. */ 2393: 1.1.1.6 root 2394: result += find_splittable_givs (bl, unroll_type, loop_start, loop_end, 2395: increment, unroll_number); 1.1 root 2396: 2397: /* If final value is non-zero, then must emit an instruction which sets 2398: the value of the biv to the proper value. This is done after 2399: handling all of the givs, since some of them may need to use the 2400: biv's value in their initialization code. */ 2401: if (biv_final_value) 2402: { 2403: /* If the loop has multiple exits, emit the insns before the 2404: loop to ensure that it will always be executed no matter 2405: how the loop exits. Otherwise emit the insn after the loop, 2406: since this is slightly more efficient. */ 2407: if (! loop_number_exit_labels[uid_loop_num[INSN_UID (loop_start)]]) 2408: emit_insn_before (gen_move_insn (bl->biv->src_reg, 2409: biv_final_value), 2410: end_insert_before); 2411: else 2412: { 2413: /* Create a new register to hold the value of the biv, and then 2414: set the biv to its final value before the loop start. The biv 2415: is set to its final value before loop start to ensure that 2416: this insn will always be executed, no matter how the loop 2417: exits. */ 2418: rtx tem = gen_reg_rtx (bl->biv->mode); 2419: emit_insn_before (gen_move_insn (tem, bl->biv->src_reg), 2420: loop_start); 2421: emit_insn_before (gen_move_insn (bl->biv->src_reg, 2422: biv_final_value), 2423: loop_start); 2424: 2425: if (loop_dump_stream) 2426: fprintf (loop_dump_stream, "Biv %d mapped to %d for split.\n", 2427: REGNO (bl->biv->src_reg), REGNO (tem)); 2428: 2429: /* Set up the mapping from the original biv register to the new 2430: register. */ 2431: bl->biv->src_reg = tem; 2432: } 2433: } 2434: } 2435: return result; 2436: } 2437: 2438: /* For every giv based on the biv BL, check to determine whether it is 1.1.1.6 root 2439: splittable. This is a subroutine to find_splittable_regs (). 2440: 2441: Return the number of instructions that set splittable registers. */ 1.1 root 2442: 2443: static int 2444: find_splittable_givs (bl, unroll_type, loop_start, loop_end, increment, 1.1.1.6 root 2445: unroll_number) 1.1 root 2446: struct iv_class *bl; 2447: enum unroll_types unroll_type; 2448: rtx loop_start, loop_end; 2449: rtx increment; 1.1.1.6 root 2450: int unroll_number; 1.1 root 2451: { 2452: struct induction *v; 2453: rtx final_value; 2454: rtx tem; 1.1.1.6 root 2455: int result = 0; 1.1 root 2456: 2457: for (v = bl->giv; v; v = v->next_iv) 2458: { 2459: rtx giv_inc, value; 2460: 2461: /* Only split the giv if it has already been reduced, or if the loop is 2462: being completely unrolled. */ 2463: if (unroll_type != UNROLL_COMPLETELY && v->ignore) 2464: continue; 2465: 2466: /* The giv can be split if the insn that sets the giv is executed once 2467: and only once on every iteration of the loop. */ 2468: /* An address giv can always be split. v->insn is just a use not a set, 2469: and hence it does not matter whether it is always executed. All that 2470: matters is that all the biv increments are always executed, and we 2471: won't reach here if they aren't. */ 2472: if (v->giv_type != DEST_ADDR 2473: && (! v->always_computable 2474: || back_branch_in_range_p (v->insn, loop_start, loop_end))) 2475: continue; 2476: 2477: /* The giv increment value must be a constant. */ 2478: giv_inc = fold_rtx_mult_add (v->mult_val, increment, const0_rtx, 2479: v->mode); 2480: if (! giv_inc || GET_CODE (giv_inc) != CONST_INT) 2481: continue; 2482: 2483: /* The loop must be unrolled completely, or else have a known number of 2484: iterations and only one exit, or else the giv must be dead outside 2485: the loop, or else the final value of the giv must be known. 2486: Otherwise, it is not safe to split the giv since it may not have the 2487: proper value on loop exit. */ 2488: 2489: /* The used outside loop test will fail for DEST_ADDR givs. They are 2490: never used outside the loop anyways, so it is always safe to split a 2491: DEST_ADDR giv. */ 2492: 2493: final_value = 0; 2494: if (unroll_type != UNROLL_COMPLETELY 2495: && (loop_number_exit_labels[uid_loop_num[INSN_UID (loop_start)]] 2496: || unroll_type == UNROLL_NAIVE) 2497: && v->giv_type != DEST_ADDR 2498: && ((regno_first_uid[REGNO (v->dest_reg)] != INSN_UID (v->insn) 2499: /* Check for the case where the pseudo is set by a shift/add 2500: sequence, in which case the first insn setting the pseudo 2501: is the first insn of the shift/add sequence. */ 1.1.1.4 root 2502: && (! (tem = find_reg_note (v->insn, REG_RETVAL, NULL_RTX)) 1.1 root 2503: || (regno_first_uid[REGNO (v->dest_reg)] 2504: != INSN_UID (XEXP (tem, 0))))) 2505: /* Line above always fails if INSN was moved by loop opt. */ 2506: || (uid_luid[regno_last_uid[REGNO (v->dest_reg)]] 2507: >= INSN_LUID (loop_end))) 2508: && ! (final_value = v->final_value)) 2509: continue; 2510: 2511: #if 0 2512: /* Currently, non-reduced/final-value givs are never split. */ 2513: /* Should emit insns after the loop if possible, as the biv final value 2514: code below does. */ 2515: 2516: /* If the final value is non-zero, and the giv has not been reduced, 2517: then must emit an instruction to set the final value. */ 2518: if (final_value && !v->new_reg) 2519: { 2520: /* Create a new register to hold the value of the giv, and then set 2521: the giv to its final value before the loop start. The giv is set 2522: to its final value before loop start to ensure that this insn 2523: will always be executed, no matter how we exit. */ 2524: tem = gen_reg_rtx (v->mode); 2525: emit_insn_before (gen_move_insn (tem, v->dest_reg), loop_start); 2526: emit_insn_before (gen_move_insn (v->dest_reg, final_value), 2527: loop_start); 2528: 2529: if (loop_dump_stream) 2530: fprintf (loop_dump_stream, "Giv %d mapped to %d for split.\n", 2531: REGNO (v->dest_reg), REGNO (tem)); 2532: 2533: v->src_reg = tem; 2534: } 2535: #endif 2536: 2537: /* This giv is splittable. If completely unrolling the loop, save the 2538: giv's initial value. Otherwise, save the constant zero for it. */ 2539: 2540: if (unroll_type == UNROLL_COMPLETELY) 1.1.1.4 root 2541: { 2542: /* It is not safe to use bl->initial_value here, because it may not 2543: be invariant. It is safe to use the initial value stored in 2544: the splittable_regs array if it is set. In rare cases, it won't 2545: be set, so then we do exactly the same thing as 2546: find_splittable_regs does to get a safe value. */ 2547: rtx biv_initial_value; 2548: 2549: if (splittable_regs[bl->regno]) 2550: biv_initial_value = splittable_regs[bl->regno]; 2551: else if (GET_CODE (bl->initial_value) != REG 2552: || (REGNO (bl->initial_value) != bl->regno 2553: && REGNO (bl->initial_value) >= FIRST_PSEUDO_REGISTER)) 2554: biv_initial_value = bl->initial_value; 2555: else 2556: { 2557: rtx tem = gen_reg_rtx (bl->biv->mode); 2558: 2559: emit_insn_before (gen_move_insn (tem, bl->biv->src_reg), 2560: loop_start); 2561: biv_initial_value = tem; 2562: } 2563: value = fold_rtx_mult_add (v->mult_val, biv_initial_value, 2564: v->add_val, v->mode); 2565: } 1.1 root 2566: else 2567: value = const0_rtx; 2568: 2569: if (v->new_reg) 2570: { 1.1.1.3 root 2571: /* If a giv was combined with another giv, then we can only split 2572: this giv if the giv it was combined with was reduced. This 2573: is because the value of v->new_reg is meaningless in this 2574: case. */ 2575: if (v->same && ! v->same->new_reg) 1.1 root 2576: { 2577: if (loop_dump_stream) 2578: fprintf (loop_dump_stream, 1.1.1.3 root 2579: "giv combined with unreduced giv not split.\n"); 2580: continue; 2581: } 2582: /* If the giv is an address destination, it could be something other 2583: than a simple register, these have to be treated differently. */ 2584: else if (v->giv_type == DEST_REG) 2585: { 2586: /* If value is not a constant, register, or register plus 2587: constant, then compute its value into a register before 2588: loop start. This prevents illegal rtx sharing, and should 2589: generate better code. We can use bl->initial_value here 2590: instead of splittable_regs[bl->regno] because this code 2591: is going before the loop start. */ 2592: if (unroll_type == UNROLL_COMPLETELY 2593: && GET_CODE (value) != CONST_INT 2594: && GET_CODE (value) != REG 2595: && (GET_CODE (value) != PLUS 2596: || GET_CODE (XEXP (value, 0)) != REG 2597: || GET_CODE (XEXP (value, 1)) != CONST_INT)) 2598: { 2599: rtx tem = gen_reg_rtx (v->mode); 2600: emit_iv_add_mult (bl->initial_value, v->mult_val, 2601: v->add_val, tem, loop_start); 2602: value = tem; 2603: } 2604: 2605: splittable_regs[REGNO (v->new_reg)] = value; 1.1 root 2606: } 2607: else 2608: { 2609: /* Splitting address givs is useful since it will often allow us 2610: to eliminate some increment insns for the base giv as 2611: unnecessary. */ 2612: 2613: /* If the addr giv is combined with a dest_reg giv, then all 2614: references to that dest reg will be remapped, which is NOT 2615: what we want for split addr regs. We always create a new 2616: register for the split addr giv, just to be safe. */ 2617: 2618: /* ??? If there are multiple address givs which have been 2619: combined with the same dest_reg giv, then we may only need 2620: one new register for them. Pulling out constants below will 2621: catch some of the common cases of this. Currently, I leave 2622: the work of simplifying multiple address givs to the 2623: following cse pass. */ 2624: 1.1.1.7 ! root 2625: /* As a special case, if we have multiple identical address givs ! 2626: within a single instruction, then we do use a single psuedo ! 2627: reg for both. This is necessary in case one is a match_dup ! 2628: of the other. */ ! 2629: 1.1 root 2630: v->const_adjust = 0; 1.1.1.7 ! root 2631: ! 2632: if (v->same && v->same->insn == v->insn ! 2633: && v->new_reg == v->same->new_reg) ! 2634: { ! 2635: v->dest_reg = v->same->dest_reg; ! 2636: if (loop_dump_stream) ! 2637: fprintf (loop_dump_stream, ! 2638: "Sharing address givs with reg %d\n", ! 2639: REGNO (v->dest_reg)); ! 2640: } ! 2641: else if (unroll_type != UNROLL_COMPLETELY) 1.1 root 2642: { 2643: /* If not completely unrolling the loop, then create a new 2644: register to hold the split value of the DEST_ADDR giv. 2645: Emit insn to initialize its value before loop start. */ 2646: tem = gen_reg_rtx (v->mode); 2647: 2648: /* If the address giv has a constant in its new_reg value, 2649: then this constant can be pulled out and put in value, 2650: instead of being part of the initialization code. */ 2651: 2652: if (GET_CODE (v->new_reg) == PLUS 2653: && GET_CODE (XEXP (v->new_reg, 1)) == CONST_INT) 2654: { 2655: v->dest_reg 2656: = plus_constant (tem, INTVAL (XEXP (v->new_reg,1))); 2657: 2658: /* Only succeed if this will give valid addresses. 2659: Try to validate both the first and the last 2660: address resulting from loop unrolling, if 2661: one fails, then can't do const elim here. */ 1.1.1.4 root 2662: if (memory_address_p (v->mem_mode, v->dest_reg) 2663: && memory_address_p (v->mem_mode, 1.1 root 2664: plus_constant (v->dest_reg, 2665: INTVAL (giv_inc) 2666: * (unroll_number - 1)))) 2667: { 2668: /* Save the negative of the eliminated const, so 2669: that we can calculate the dest_reg's increment 2670: value later. */ 2671: v->const_adjust = - INTVAL (XEXP (v->new_reg, 1)); 2672: 2673: v->new_reg = XEXP (v->new_reg, 0); 2674: if (loop_dump_stream) 2675: fprintf (loop_dump_stream, 2676: "Eliminating constant from giv %d\n", 2677: REGNO (tem)); 2678: } 2679: else 2680: v->dest_reg = tem; 2681: } 2682: else 2683: v->dest_reg = tem; 2684: 2685: /* If the address hasn't been checked for validity yet, do so 2686: now, and fail completely if either the first or the last 2687: unrolled copy of the address is not a valid address. */ 2688: if (v->dest_reg == tem 1.1.1.4 root 2689: && (! memory_address_p (v->mem_mode, v->dest_reg) 2690: || ! memory_address_p (v->mem_mode, 1.1 root 2691: plus_constant (v->dest_reg, 2692: INTVAL (giv_inc) 2693: * (unroll_number -1))))) 2694: { 2695: if (loop_dump_stream) 2696: fprintf (loop_dump_stream, 2697: "Illegal address for giv at insn %d\n", 2698: INSN_UID (v->insn)); 2699: continue; 2700: } 2701: 2702: /* To initialize the new register, just move the value of 2703: new_reg into it. This is not guaranteed to give a valid 2704: instruction on machines with complex addressing modes. 2705: If we can't recognize it, then delete it and emit insns 2706: to calculate the value from scratch. */ 2707: emit_insn_before (gen_rtx (SET, VOIDmode, tem, 2708: copy_rtx (v->new_reg)), 2709: loop_start); 1.1.1.4 root 2710: if (recog_memoized (PREV_INSN (loop_start)) < 0) 1.1 root 2711: { 1.1.1.7 ! root 2712: rtx sequence, ret; ! 2713: ! 2714: /* We can't use bl->initial_value to compute the initial ! 2715: value, because the loop may have been preconditioned. ! 2716: We must calculate it from NEW_REG. Try using ! 2717: force_operand instead of emit_iv_add_mult. */ 1.1 root 2718: delete_insn (PREV_INSN (loop_start)); 1.1.1.7 ! root 2719: ! 2720: start_sequence (); ! 2721: ret = force_operand (v->new_reg, tem); ! 2722: if (ret != tem) ! 2723: emit_move_insn (tem, ret); ! 2724: sequence = gen_sequence (); ! 2725: end_sequence (); ! 2726: emit_insn_before (sequence, loop_start); ! 2727: 1.1 root 2728: if (loop_dump_stream) 2729: fprintf (loop_dump_stream, 2730: "Illegal init insn, rewritten.\n"); 2731: } 2732: } 2733: else 2734: { 2735: v->dest_reg = value; 2736: 2737: /* Check the resulting address for validity, and fail 2738: if the resulting address would be illegal. */ 1.1.1.4 root 2739: if (! memory_address_p (v->mem_mode, v->dest_reg) 2740: || ! memory_address_p (v->mem_mode, 1.1 root 2741: plus_constant (v->dest_reg, 2742: INTVAL (giv_inc) * 2743: (unroll_number -1)))) 2744: { 2745: if (loop_dump_stream) 2746: fprintf (loop_dump_stream, 2747: "Illegal address for giv at insn %d\n", 2748: INSN_UID (v->insn)); 2749: continue; 2750: } 2751: } 2752: 2753: /* Store the value of dest_reg into the insn. This sharing 2754: will not be a problem as this insn will always be copied 2755: later. */ 2756: 2757: *v->location = v->dest_reg; 2758: 2759: /* If this address giv is combined with a dest reg giv, then 2760: save the base giv's induction pointer so that we will be 2761: able to handle this address giv properly. The base giv 2762: itself does not have to be splittable. */ 2763: 2764: if (v->same && v->same->giv_type == DEST_REG) 2765: addr_combined_regs[REGNO (v->same->new_reg)] = v->same; 2766: 2767: if (GET_CODE (v->new_reg) == REG) 2768: { 2769: /* This giv maybe hasn't been combined with any others. 2770: Make sure that it's giv is marked as splittable here. */ 2771: 2772: splittable_regs[REGNO (v->new_reg)] = value; 2773: 2774: /* Make it appear to depend upon itself, so that the 2775: giv will be properly split in the main loop above. */ 2776: if (! v->same) 2777: { 2778: v->same = v; 2779: addr_combined_regs[REGNO (v->new_reg)] = v; 2780: } 2781: } 1.1.1.2 root 2782: 1.1 root 2783: if (loop_dump_stream) 2784: fprintf (loop_dump_stream, "DEST_ADDR giv being split.\n"); 2785: } 2786: } 2787: else 2788: { 2789: #if 0 2790: /* Currently, unreduced giv's can't be split. This is not too much 2791: of a problem since unreduced giv's are not live across loop 2792: iterations anyways. When unrolling a loop completely though, 2793: it makes sense to reduce&split givs when possible, as this will 2794: result in simpler instructions, and will not require that a reg 2795: be live across loop iterations. */ 2796: 2797: splittable_regs[REGNO (v->dest_reg)] = value; 2798: fprintf (stderr, "Giv %d at insn %d not reduced\n", 2799: REGNO (v->dest_reg), INSN_UID (v->insn)); 2800: #else 2801: continue; 2802: #endif 2803: } 2804: 2805: /* Givs are only updated once by definition. Mark it so if this is 2806: a splittable register. Don't need to do anything for address givs 2807: where this may not be a register. */ 2808: 2809: if (GET_CODE (v->new_reg) == REG) 2810: splittable_regs_updates[REGNO (v->new_reg)] = 1; 2811: 2812: result++; 2813: 2814: if (loop_dump_stream) 2815: { 2816: int regnum; 2817: 2818: if (GET_CODE (v->dest_reg) == CONST_INT) 2819: regnum = -1; 2820: else if (GET_CODE (v->dest_reg) != REG) 2821: regnum = REGNO (XEXP (v->dest_reg, 0)); 2822: else 2823: regnum = REGNO (v->dest_reg); 2824: fprintf (loop_dump_stream, "Giv %d at insn %d safe to split.\n", 2825: regnum, INSN_UID (v->insn)); 2826: } 2827: } 2828: 2829: return result; 2830: } 2831: 2832: /* Try to prove that the register is dead after the loop exits. Trace every 2833: loop exit looking for an insn that will always be executed, which sets 2834: the register to some value, and appears before the first use of the register 2835: is found. If successful, then return 1, otherwise return 0. */ 2836: 2837: /* ?? Could be made more intelligent in the handling of jumps, so that 2838: it can search past if statements and other similar structures. */ 2839: 2840: static int 2841: reg_dead_after_loop (reg, loop_start, loop_end) 2842: rtx reg, loop_start, loop_end; 2843: { 2844: rtx insn, label; 2845: enum rtx_code code; 1.1.1.2 root 2846: int jump_count = 0; 1.1 root 2847: 2848: /* HACK: Must also search the loop fall through exit, create a label_ref 2849: here which points to the loop_end, and append the loop_number_exit_labels 2850: list to it. */ 2851: label = gen_rtx (LABEL_REF, VOIDmode, loop_end); 2852: LABEL_NEXTREF (label) 2853: = loop_number_exit_labels[uid_loop_num[INSN_UID (loop_start)]]; 2854: 2855: for ( ; label; label = LABEL_NEXTREF (label)) 2856: { 2857: /* Succeed if find an insn which sets the biv or if reach end of 2858: function. Fail if find an insn that uses the biv, or if come to 2859: a conditional jump. */ 2860: 2861: insn = NEXT_INSN (XEXP (label, 0)); 1.1.1.2 root 2862: while (insn) 1.1 root 2863: { 1.1.1.2 root 2864: code = GET_CODE (insn); 2865: if (GET_RTX_CLASS (code) == 'i') 1.1 root 2866: { 1.1.1.2 root 2867: rtx set; 2868: 2869: if (reg_referenced_p (reg, PATTERN (insn))) 1.1 root 2870: return 0; 1.1.1.2 root 2871: 2872: set = single_set (insn); 2873: if (set && rtx_equal_p (SET_DEST (set), reg)) 2874: break; 1.1 root 2875: } 1.1.1.2 root 2876: 1.1 root 2877: if (code == JUMP_INSN) 2878: { 2879: if (GET_CODE (PATTERN (insn)) == RETURN) 2880: break; 1.1.1.2 root 2881: else if (! simplejump_p (insn) 2882: /* Prevent infinite loop following infinite loops. */ 2883: || jump_count++ > 20) 1.1 root 2884: return 0; 2885: else 1.1.1.2 root 2886: insn = JUMP_LABEL (insn); 1.1 root 2887: } 1.1.1.2 root 2888: 1.1 root 2889: insn = NEXT_INSN (insn); 2890: } 2891: } 2892: 2893: /* Success, the register is dead on all loop exits. */ 2894: return 1; 2895: } 2896: 2897: /* Try to calculate the final value of the biv, the value it will have at 2898: the end of the loop. If we can do it, return that value. */ 2899: 2900: rtx 2901: final_biv_value (bl, loop_start, loop_end) 2902: struct iv_class *bl; 2903: rtx loop_start, loop_end; 2904: { 2905: rtx increment, tem; 2906: 1.1.1.2 root 2907: /* ??? This only works for MODE_INT biv's. Reject all others for now. */ 2908: 2909: if (GET_MODE_CLASS (bl->biv->mode) != MODE_INT) 2910: return 0; 2911: 1.1 root 2912: /* The final value for reversed bivs must be calculated differently than 2913: for ordinary bivs. In this case, there is already an insn after the 2914: loop which sets this biv's final value (if necessary), and there are 2915: no other loop exits, so we can return any value. */ 2916: if (bl->reversed) 2917: { 2918: if (loop_dump_stream) 2919: fprintf (loop_dump_stream, 2920: "Final biv value for %d, reversed biv.\n", bl->regno); 2921: 2922: return const0_rtx; 2923: } 2924: 2925: /* Try to calculate the final value as initial value + (number of iterations 2926: * increment). For this to work, increment must be invariant, the only 2927: exit from the loop must be the fall through at the bottom (otherwise 2928: it may not have its final value when the loop exits), and the initial 2929: value of the biv must be invariant. */ 2930: 2931: if (loop_n_iterations != 0 2932: && ! loop_number_exit_labels[uid_loop_num[INSN_UID (loop_start)]] 2933: && invariant_p (bl->initial_value)) 2934: { 2935: increment = biv_total_increment (bl, loop_start, loop_end); 2936: 2937: if (increment && invariant_p (increment)) 2938: { 2939: /* Can calculate the loop exit value, emit insns after loop 2940: end to calculate this value into a temporary register in 2941: case it is needed later. */ 2942: 2943: tem = gen_reg_rtx (bl->biv->mode); 1.1.1.4 root 2944: /* Make sure loop_end is not the last insn. */ 2945: if (NEXT_INSN (loop_end) == 0) 2946: emit_note_after (NOTE_INSN_DELETED, loop_end); 2947: emit_iv_add_mult (increment, GEN_INT (loop_n_iterations), 1.1 root 2948: bl->initial_value, tem, NEXT_INSN (loop_end)); 2949: 2950: if (loop_dump_stream) 2951: fprintf (loop_dump_stream, 2952: "Final biv value for %d, calculated.\n", bl->regno); 2953: 2954: return tem; 2955: } 2956: } 2957: 2958: /* Check to see if the biv is dead at all loop exits. */ 2959: if (reg_dead_after_loop (bl->biv->src_reg, loop_start, loop_end)) 2960: { 2961: if (loop_dump_stream) 2962: fprintf (loop_dump_stream, 2963: "Final biv value for %d, biv dead after loop exit.\n", 2964: bl->regno); 2965: 2966: return const0_rtx; 2967: } 2968: 2969: return 0; 2970: } 2971: 2972: /* Try to calculate the final value of the giv, the value it will have at 2973: the end of the loop. If we can do it, return that value. */ 2974: 2975: rtx 2976: final_giv_value (v, loop_start, loop_end) 2977: struct induction *v; 2978: rtx loop_start, loop_end; 2979: { 2980: struct iv_class *bl; 1.1.1.4 root 2981: rtx insn; 1.1 root 2982: rtx increment, tem; 1.1.1.3 root 2983: rtx insert_before, seq; 1.1 root 2984: 2985: bl = reg_biv_class[REGNO (v->src_reg)]; 2986: 2987: /* The final value for givs which depend on reversed bivs must be calculated 2988: differently than for ordinary givs. In this case, there is already an 2989: insn after the loop which sets this giv's final value (if necessary), 2990: and there are no other loop exits, so we can return any value. */ 2991: if (bl->reversed) 2992: { 2993: if (loop_dump_stream) 2994: fprintf (loop_dump_stream, 2995: "Final giv value for %d, depends on reversed biv\n", 2996: REGNO (v->dest_reg)); 2997: return const0_rtx; 2998: } 2999: 3000: /* Try to calculate the final value as a function of the biv it depends 3001: upon. The only exit from the loop must be the fall through at the bottom 3002: (otherwise it may not have its final value when the loop exits). */ 3003: 3004: /* ??? Can calculate the final giv value by subtracting off the 3005: extra biv increments times the giv's mult_val. The loop must have 3006: only one exit for this to work, but the loop iterations does not need 3007: to be known. */ 3008: 3009: if (loop_n_iterations != 0 3010: && ! loop_number_exit_labels[uid_loop_num[INSN_UID (loop_start)]]) 3011: { 3012: /* ?? It is tempting to use the biv's value here since these insns will 3013: be put after the loop, and hence the biv will have its final value 3014: then. However, this fails if the biv is subsequently eliminated. 3015: Perhaps determine whether biv's are eliminable before trying to 3016: determine whether giv's are replaceable so that we can use the 3017: biv value here if it is not eliminable. */ 3018: 3019: increment = biv_total_increment (bl, loop_start, loop_end); 3020: 3021: if (increment && invariant_p (increment)) 3022: { 3023: /* Can calculate the loop exit value of its biv as 3024: (loop_n_iterations * increment) + initial_value */ 3025: 3026: /* The loop exit value of the giv is then 3027: (final_biv_value - extra increments) * mult_val + add_val. 3028: The extra increments are any increments to the biv which 3029: occur in the loop after the giv's value is calculated. 3030: We must search from the insn that sets the giv to the end 3031: of the loop to calculate this value. */ 3032: 3033: insert_before = NEXT_INSN (loop_end); 3034: 3035: /* Put the final biv value in tem. */ 3036: tem = gen_reg_rtx (bl->biv->mode); 1.1.1.4 root 3037: emit_iv_add_mult (increment, GEN_INT (loop_n_iterations), 1.1 root 3038: bl->initial_value, tem, insert_before); 3039: 3040: /* Subtract off extra increments as we find them. */ 3041: for (insn = NEXT_INSN (v->insn); insn != loop_end; 3042: insn = NEXT_INSN (insn)) 3043: { 1.1.1.4 root 3044: struct induction *biv; 3045: 3046: for (biv = bl->biv; biv; biv = biv->next_iv) 3047: if (biv->insn == insn) 3048: { 3049: start_sequence (); 3050: tem = expand_binop (GET_MODE (tem), sub_optab, tem, 3051: biv->add_val, NULL_RTX, 0, 3052: OPTAB_LIB_WIDEN); 3053: seq = gen_sequence (); 3054: end_sequence (); 3055: emit_insn_before (seq, insert_before); 3056: } 1.1 root 3057: } 3058: 3059: /* Now calculate the giv's final value. */ 3060: emit_iv_add_mult (tem, v->mult_val, v->add_val, tem, 3061: insert_before); 3062: 3063: if (loop_dump_stream) 3064: fprintf (loop_dump_stream, 3065: "Final giv value for %d, calc from biv's value.\n", 3066: REGNO (v->dest_reg)); 3067: 3068: return tem; 3069: } 3070: } 3071: 3072: /* Replaceable giv's should never reach here. */ 3073: if (v->replaceable) 3074: abort (); 3075: 3076: /* Check to see if the biv is dead at all loop exits. */ 3077: if (reg_dead_after_loop (v->dest_reg, loop_start, loop_end)) 3078: { 3079: if (loop_dump_stream) 3080: fprintf (loop_dump_stream, 3081: "Final giv value for %d, giv dead after loop exit.\n", 3082: REGNO (v->dest_reg)); 3083: 3084: return const0_rtx; 3085: } 3086: 3087: return 0; 3088: } 3089: 3090: 3091: /* Calculate the number of loop iterations. Returns the exact number of loop 1.1.1.3 root 3092: iterations if it can be calculated, otherwise returns zero. */ 1.1 root 3093: 1.1.1.4 root 3094: unsigned HOST_WIDE_INT 1.1 root 3095: loop_iterations (loop_start, loop_end) 3096: rtx loop_start, loop_end; 3097: { 3098: rtx comparison, comparison_value; 3099: rtx iteration_var, initial_value, increment, final_value; 3100: enum rtx_code comparison_code; 1.1.1.4 root 3101: HOST_WIDE_INT i; 3102: int increment_dir; 1.1 root 3103: int unsigned_compare, compare_dir, final_larger; 3104: unsigned long tempu; 3105: rtx last_loop_insn; 3106: 3107: /* First find the iteration variable. If the last insn is a conditional 3108: branch, and the insn before tests a register value, make that the 3109: iteration variable. */ 3110: 3111: loop_initial_value = 0; 3112: loop_increment = 0; 3113: loop_final_value = 0; 3114: loop_iteration_var = 0; 3115: 1.1.1.7 ! root 3116: /* We used to use pren_nonnote_insn here, but that fails because it might ! 3117: accidentally get the branch for a contained loop if the branch for this ! 3118: loop was deleted. We can only trust branches immediately before the ! 3119: loop_end. */ ! 3120: last_loop_insn = PREV_INSN (loop_end); 1.1 root 3121: 3122: comparison = get_condition_for_loop (last_loop_insn); 3123: if (comparison == 0) 3124: { 3125: if (loop_dump_stream) 3126: fprintf (loop_dump_stream, 3127: "Loop unrolling: No final conditional branch found.\n"); 3128: return 0; 3129: } 3130: 3131: /* ??? Get_condition may switch position of induction variable and 3132: invariant register when it canonicalizes the comparison. */ 3133: 3134: comparison_code = GET_CODE (comparison); 3135: iteration_var = XEXP (comparison, 0); 3136: comparison_value = XEXP (comparison, 1); 3137: 3138: if (GET_CODE (iteration_var) != REG) 3139: { 3140: if (loop_dump_stream) 3141: fprintf (loop_dump_stream, 3142: "Loop unrolling: Comparison not against register.\n"); 3143: return 0; 3144: } 3145: 3146: /* Loop iterations is always called before any new registers are created 3147: now, so this should never occur. */ 3148: 3149: if (REGNO (iteration_var) >= max_reg_before_loop) 3150: abort (); 3151: 3152: iteration_info (iteration_var, &initial_value, &increment, 3153: loop_start, loop_end); 3154: if (initial_value == 0) 3155: /* iteration_info already printed a message. */ 3156: return 0; 3157: 3158: /* If the comparison value is an invariant register, then try to find 3159: its value from the insns before the start of the loop. */ 3160: 3161: if (GET_CODE (comparison_value) == REG && invariant_p (comparison_value)) 3162: { 3163: rtx insn, set; 3164: 3165: for (insn = PREV_INSN (loop_start); insn ; insn = PREV_INSN (insn)) 3166: { 3167: if (GET_CODE (insn) == CODE_LABEL) 3168: break; 3169: 3170: else if (GET_RTX_CLASS (GET_CODE (insn)) == 'i' 1.1.1.5 root 3171: && reg_set_p (comparison_value, insn)) 1.1 root 3172: { 1.1.1.5 root 3173: /* We found the last insn before the loop that sets the register. 3174: If it sets the entire register, and has a REG_EQUAL note, 3175: then use the value of the REG_EQUAL note. */ 3176: if ((set = single_set (insn)) 3177: && (SET_DEST (set) == comparison_value)) 3178: { 3179: rtx note = find_reg_note (insn, REG_EQUAL, NULL_RTX); 1.1 root 3180: 1.1.1.7 ! root 3181: /* Only use the REG_EQUAL note if it is a constant. ! 3182: Other things, divide in particular, will cause ! 3183: problems later if we use them. */ ! 3184: if (note && GET_CODE (XEXP (note, 0)) != EXPR_LIST ! 3185: && CONSTANT_P (XEXP (note, 0))) 1.1.1.5 root 3186: comparison_value = XEXP (note, 0); 3187: } 1.1 root 3188: break; 3189: } 3190: } 3191: } 3192: 3193: final_value = approx_final_value (comparison_code, comparison_value, 3194: &unsigned_compare, &compare_dir); 3195: 3196: /* Save the calculated values describing this loop's bounds, in case 3197: precondition_loop_p will need them later. These values can not be 3198: recalculated inside precondition_loop_p because strength reduction 3199: optimizations may obscure the loop's structure. */ 3200: 3201: loop_iteration_var = iteration_var; 3202: loop_initial_value = initial_value; 3203: loop_increment = increment; 3204: loop_final_value = final_value; 3205: 1.1.1.7 ! root 3206: if (increment == 0) ! 3207: { ! 3208: if (loop_dump_stream) ! 3209: fprintf (loop_dump_stream, ! 3210: "Loop unrolling: Increment value can't be calculated.\n"); ! 3211: return 0; ! 3212: } ! 3213: else if (GET_CODE (increment) != CONST_INT) ! 3214: { ! 3215: if (loop_dump_stream) ! 3216: fprintf (loop_dump_stream, ! 3217: "Loop unrolling: Increment value not constant.\n"); ! 3218: return 0; ! 3219: } ! 3220: else if (GET_CODE (initial_value) != CONST_INT) ! 3221: { ! 3222: if (loop_dump_stream) ! 3223: fprintf (loop_dump_stream, ! 3224: "Loop unrolling: Initial value not constant.\n"); ! 3225: return 0; ! 3226: } ! 3227: else if (final_value == 0) 1.1 root 3228: { 3229: if (loop_dump_stream) 3230: fprintf (loop_dump_stream, 3231: "Loop unrolling: EQ comparison loop.\n"); 3232: return 0; 3233: } 3234: else if (GET_CODE (final_value) != CONST_INT) 3235: { 3236: if (loop_dump_stream) 3237: fprintf (loop_dump_stream, 3238: "Loop unrolling: Final value not constant.\n"); 3239: return 0; 3240: } 3241: 3242: /* ?? Final value and initial value do not have to be constants. 3243: Only their difference has to be constant. When the iteration variable 3244: is an array address, the final value and initial value might both 3245: be addresses with the same base but different constant offsets. 3246: Final value must be invariant for this to work. 3247: 1.1.1.3 root 3248: To do this, need some way to find the values of registers which are 1.1 root 3249: invariant. */ 3250: 3251: /* Final_larger is 1 if final larger, 0 if they are equal, otherwise -1. */ 3252: if (unsigned_compare) 3253: final_larger 1.1.1.4 root 3254: = ((unsigned HOST_WIDE_INT) INTVAL (final_value) 3255: > (unsigned HOST_WIDE_INT) INTVAL (initial_value)) 3256: - ((unsigned HOST_WIDE_INT) INTVAL (final_value) 3257: < (unsigned HOST_WIDE_INT) INTVAL (initial_value)); 1.1 root 3258: else 1.1.1.4 root 3259: final_larger = (INTVAL (final_value) > INTVAL (initial_value)) 3260: - (INTVAL (final_value) < INTVAL (initial_value)); 1.1 root 3261: 3262: if (INTVAL (increment) > 0) 3263: increment_dir = 1; 3264: else if (INTVAL (increment) == 0) 3265: increment_dir = 0; 3266: else 3267: increment_dir = -1; 3268: 3269: /* There are 27 different cases: compare_dir = -1, 0, 1; 3270: final_larger = -1, 0, 1; increment_dir = -1, 0, 1. 3271: There are 4 normal cases, 4 reverse cases (where the iteration variable 3272: will overflow before the loop exits), 4 infinite loop cases, and 15 3273: immediate exit (0 or 1 iteration depending on loop type) cases. 3274: Only try to optimize the normal cases. */ 3275: 3276: /* (compare_dir/final_larger/increment_dir) 3277: Normal cases: (0/-1/-1), (0/1/1), (-1/-1/-1), (1/1/1) 3278: Reverse cases: (0/-1/1), (0/1/-1), (-1/-1/1), (1/1/-1) 3279: Infinite loops: (0/-1/0), (0/1/0), (-1/-1/0), (1/1/0) 3280: Immediate exit: (0/0/X), (-1/0/X), (-1/1/X), (1/0/X), (1/-1/X) */ 3281: 3282: /* ?? If the meaning of reverse loops (where the iteration variable 3283: will overflow before the loop exits) is undefined, then could 3284: eliminate all of these special checks, and just always assume 3285: the loops are normal/immediate/infinite. Note that this means 3286: the sign of increment_dir does not have to be known. Also, 3287: since it does not really hurt if immediate exit loops or infinite loops 3288: are optimized, then that case could be ignored also, and hence all 3289: loops can be optimized. 3290: 3291: According to ANSI Spec, the reverse loop case result is undefined, 3292: because the action on overflow is undefined. 3293: 3294: See also the special test for NE loops below. */ 3295: 3296: if (final_larger == increment_dir && final_larger != 0 3297: && (final_larger == compare_dir || compare_dir == 0)) 3298: /* Normal case. */ 3299: ; 3300: else 3301: { 3302: if (loop_dump_stream) 3303: fprintf (loop_dump_stream, 3304: "Loop unrolling: Not normal loop.\n"); 3305: return 0; 3306: } 3307: 3308: /* Calculate the number of iterations, final_value is only an approximation, 3309: so correct for that. Note that tempu and loop_n_iterations are 3310: unsigned, because they can be as large as 2^n - 1. */ 3311: 3312: i = INTVAL (increment); 3313: if (i > 0) 3314: tempu = INTVAL (final_value) - INTVAL (initial_value); 3315: else if (i < 0) 3316: { 3317: tempu = INTVAL (initial_value) - INTVAL (final_value); 3318: i = -i; 3319: } 3320: else 3321: abort (); 3322: 3323: /* For NE tests, make sure that the iteration variable won't miss the 3324: final value. If tempu mod i is not zero, then the iteration variable 3325: will overflow before the loop exits, and we can not calculate the 3326: number of iterations. */ 3327: if (compare_dir == 0 && (tempu % i) != 0) 3328: return 0; 3329: 3330: return tempu / i + ((tempu % i) != 0); 3331: } 1.1.1.7 ! root 3332: ! 3333: /* Replace uses of split bivs with their split psuedo register. This is ! 3334: for original instructions which remain after loop unrolling without ! 3335: copying. */ ! 3336: ! 3337: static rtx ! 3338: remap_split_bivs (x) ! 3339: rtx x; ! 3340: { ! 3341: register enum rtx_code code; ! 3342: register int i; ! 3343: register char *fmt; ! 3344: ! 3345: if (x == 0) ! 3346: return x; ! 3347: ! 3348: code = GET_CODE (x); ! 3349: switch (code) ! 3350: { ! 3351: case SCRATCH: ! 3352: case PC: ! 3353: case CC0: ! 3354: case CONST_INT: ! 3355: case CONST_DOUBLE: ! 3356: case CONST: ! 3357: case SYMBOL_REF: ! 3358: case LABEL_REF: ! 3359: return x; ! 3360: ! 3361: case REG: ! 3362: #if 0 ! 3363: /* If non-reduced/final-value givs were split, then this would also ! 3364: have to remap those givs also. */ ! 3365: #endif ! 3366: if (REGNO (x) < max_reg_before_loop ! 3367: && reg_iv_type[REGNO (x)] == BASIC_INDUCT) ! 3368: return reg_biv_class[REGNO (x)]->biv->src_reg; ! 3369: } ! 3370: ! 3371: fmt = GET_RTX_FORMAT (code); ! 3372: for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) ! 3373: { ! 3374: if (fmt[i] == 'e') ! 3375: XEXP (x, i) = remap_split_bivs (XEXP (x, i)); ! 3376: if (fmt[i] == 'E') ! 3377: { ! 3378: register int j; ! 3379: for (j = 0; j < XVECLEN (x, i); j++) ! 3380: XVECEXP (x, i, j) = remap_split_bivs (XVECEXP (x, i, j)); ! 3381: } ! 3382: } ! 3383: return x; ! 3384: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.