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