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