![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to loop.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [GCC 2.x] / gcc|
Return to loop.c CVS log | Up to [GCC 2.x] / gcc |
1.1 root 1: /* Move constant computations out of loops. 1.1.1.4 ! root 2: Copyright (C) 1987, 1988, 1989, 1991, 1992 Free Software Foundation, Inc. 1.1 root 3: 4: This file is part of GNU CC. 5: 6: GNU CC is free software; you can redistribute it and/or modify 7: it under the terms of the GNU General Public License as published by 8: the Free Software Foundation; either version 2, or (at your option) 9: any later version. 10: 11: GNU CC is distributed in the hope that it will be useful, 12: but WITHOUT ANY WARRANTY; without even the implied warranty of 13: MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14: GNU General Public License for more details. 15: 16: You should have received a copy of the GNU General Public License 17: along with GNU CC; see the file COPYING. If not, write to 18: the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA. */ 19: 20: 21: /* This is the loop optimization pass of the compiler. 22: It finds invariant computations within loops and moves them 23: to the beginning of the loop. Then it identifies basic and 24: general induction variables. Strength reduction is applied to the general 25: induction variables, and induction variable elimination is applied to 26: the basic induction variables. 27: 28: It also finds cases where 29: a register is set within the loop by zero-extending a narrower value 30: and changes these to zero the entire register once before the loop 31: and merely copy the low part within the loop. 32: 33: Most of the complexity is in heuristics to decide when it is worth 34: while to do these things. */ 35: 1.1.1.4 ! root 36: #include <stdio.h> 1.1 root 37: #include "config.h" 38: #include "rtl.h" 39: #include "obstack.h" 40: #include "expr.h" 41: #include "insn-config.h" 42: #include "insn-flags.h" 43: #include "regs.h" 44: #include "hard-reg-set.h" 45: #include "recog.h" 46: #include "flags.h" 47: #include "real.h" 48: #include "loop.h" 49: 50: /* Vector mapping INSN_UIDs to luids. 1.1.1.2 root 51: The luids are like uids but increase monotonically always. 1.1 root 52: We use them to see whether a jump comes from outside a given loop. */ 53: 54: int *uid_luid; 55: 56: /* Indexed by INSN_UID, contains the ordinal giving the (innermost) loop 57: number the insn is contained in. */ 58: 59: int *uid_loop_num; 60: 61: /* 1 + largest uid of any insn. */ 62: 63: int max_uid_for_loop; 64: 65: /* 1 + luid of last insn. */ 66: 67: static int max_luid; 68: 69: /* Number of loops detected in current function. Used as index to the 70: next few tables. */ 71: 72: static int max_loop_num; 73: 74: /* Indexed by loop number, contains the first and last insn of each loop. */ 75: 76: static rtx *loop_number_loop_starts, *loop_number_loop_ends; 77: 78: /* For each loop, gives the containing loop number, -1 if none. */ 79: 80: int *loop_outer_loop; 81: 82: /* Indexed by loop number, contains a nonzero value if the "loop" isn't 83: really a loop (an insn outside the loop branches into it). */ 84: 85: static char *loop_invalid; 86: 87: /* Indexed by loop number, links together all LABEL_REFs which refer to 88: code labels outside the loop. Used by routines that need to know all 89: loop exits, such as final_biv_value and final_giv_value. 90: 91: This does not include loop exits due to return instructions. This is 92: because all bivs and givs are pseudos, and hence must be dead after a 93: return, so the presense of a return does not affect any of the 94: optimizations that use this info. It is simpler to just not include return 95: instructions on this list. */ 96: 97: rtx *loop_number_exit_labels; 98: 99: /* Holds the number of loop iterations. It is zero if the number could not be 1.1.1.4 ! root 100: calculated. Must be unsigned since the number of iterations can ! 101: be as high as 2^wordsize-1. For loops with a wider iterator, this number ! 102: will will be zero if the number of loop iterations is too large for an ! 103: unsigned integer to hold. */ 1.1 root 104: 1.1.1.4 ! root 105: unsigned HOST_WIDE_INT loop_n_iterations; 1.1 root 106: 107: /* Nonzero if there is a subroutine call in the current loop. 108: (unknown_address_altered is also nonzero in this case.) */ 109: 110: static int loop_has_call; 111: 1.1.1.3 root 112: /* Nonzero if there is a volatile memory reference in the current 113: loop. */ 114: 115: static int loop_has_volatile; 116: 1.1 root 117: /* Added loop_continue which is the NOTE_INSN_LOOP_CONT of the 118: current loop. A continue statement will generate a branch to 119: NEXT_INSN (loop_continue). */ 120: 121: static rtx loop_continue; 122: 123: /* Indexed by register number, contains the number of times the reg 124: is set during the loop being scanned. 125: During code motion, a negative value indicates a reg that has been 126: made a candidate; in particular -2 means that it is an candidate that 1.1.1.3 root 127: we know is equal to a constant and -1 means that it is an candidate 1.1 root 128: not known equal to a constant. 129: After code motion, regs moved have 0 (which is accurate now) 130: while the failed candidates have the original number of times set. 131: 132: Therefore, at all times, == 0 indicates an invariant register; 133: < 0 a conditionally invariant one. */ 134: 135: static short *n_times_set; 136: 137: /* Original value of n_times_set; same except that this value 138: is not set negative for a reg whose sets have been made candidates 139: and not set to 0 for a reg that is moved. */ 140: 141: static short *n_times_used; 142: 143: /* Index by register number, 1 indicates that the register 144: cannot be moved or strength reduced. */ 145: 146: static char *may_not_optimize; 147: 148: /* Nonzero means reg N has already been moved out of one loop. 149: This reduces the desire to move it out of another. */ 150: 151: static char *moved_once; 152: 153: /* Array of MEMs that are stored in this loop. If there are too many to fit 154: here, we just turn on unknown_address_altered. */ 155: 156: #define NUM_STORES 20 157: static rtx loop_store_mems[NUM_STORES]; 158: 159: /* Index of first available slot in above array. */ 160: static int loop_store_mems_idx; 161: 162: /* Nonzero if we don't know what MEMs were changed in the current loop. 1.1.1.3 root 163: This happens if the loop contains a call (in which case `loop_has_call' 1.1 root 164: will also be set) or if we store into more than NUM_STORES MEMs. */ 165: 166: static int unknown_address_altered; 167: 168: /* Count of movable (i.e. invariant) instructions discovered in the loop. */ 169: static int num_movables; 170: 171: /* Count of memory write instructions discovered in the loop. */ 172: static int num_mem_sets; 173: 174: /* Number of loops contained within the current one, including itself. */ 175: static int loops_enclosed; 176: 177: /* Bound on pseudo register number before loop optimization. 178: A pseudo has valid regscan info if its number is < max_reg_before_loop. */ 179: int max_reg_before_loop; 180: 181: /* This obstack is used in product_cheap_p to allocate its rtl. It 182: may call gen_reg_rtx which, in turn, may reallocate regno_reg_rtx. 183: If we used the same obstack that it did, we would be deallocating 184: that array. */ 185: 186: static struct obstack temp_obstack; 187: 188: /* This is where the pointer to the obstack being used for RTL is stored. */ 189: 190: extern struct obstack *rtl_obstack; 191: 192: #define obstack_chunk_alloc xmalloc 193: #define obstack_chunk_free free 194: 195: extern char *oballoc (); 196: 197: /* During the analysis of a loop, a chain of `struct movable's 198: is made to record all the movable insns found. 199: Then the entire chain can be scanned to decide which to move. */ 200: 201: struct movable 202: { 203: rtx insn; /* A movable insn */ 204: rtx set_src; /* The expression this reg is set from. */ 205: rtx set_dest; /* The destination of this SET. */ 206: rtx dependencies; /* When INSN is libcall, this is an EXPR_LIST 207: of any registers used within the LIBCALL. */ 208: int consec; /* Number of consecutive following insns 209: that must be moved with this one. */ 210: int regno; /* The register it sets */ 211: short lifetime; /* lifetime of that register; 212: may be adjusted when matching movables 213: that load the same value are found. */ 214: short savings; /* Number of insns we can move for this reg, 215: including other movables that force this 216: or match this one. */ 217: unsigned int cond : 1; /* 1 if only conditionally movable */ 218: unsigned int force : 1; /* 1 means MUST move this insn */ 219: unsigned int global : 1; /* 1 means reg is live outside this loop */ 220: /* If PARTIAL is 1, GLOBAL means something different: 221: that the reg is live outside the range from where it is set 222: to the following label. */ 223: unsigned int done : 1; /* 1 inhibits further processing of this */ 224: 225: unsigned int partial : 1; /* 1 means this reg is used for zero-extending. 226: In particular, moving it does not make it 227: invariant. */ 228: unsigned int move_insn : 1; /* 1 means that we call emit_move_insn to 229: load SRC, rather than copying INSN. */ 230: unsigned int is_equiv : 1; /* 1 means a REG_EQUIV is present on INSN. */ 231: enum machine_mode savemode; /* Nonzero means it is a mode for a low part 232: that we should avoid changing when clearing 233: the rest of the reg. */ 234: struct movable *match; /* First entry for same value */ 235: struct movable *forces; /* An insn that must be moved if this is */ 236: struct movable *next; 237: }; 238: 239: FILE *loop_dump_stream; 240: 241: /* Forward declarations. */ 242: 243: static void find_and_verify_loops (); 244: static void mark_loop_jump (); 245: static void prescan_loop (); 246: static int reg_in_basic_block_p (); 247: static int consec_sets_invariant_p (); 248: static rtx libcall_other_reg (); 249: static int labels_in_range_p (); 250: static void count_loop_regs_set (); 251: static void note_addr_stored (); 252: static int loop_reg_used_before_p (); 253: static void scan_loop (); 254: static void replace_call_address (); 255: static rtx skip_consec_insns (); 256: static int libcall_benefit (); 257: static void ignore_some_movables (); 258: static void force_movables (); 259: static void combine_movables (); 260: static int rtx_equal_for_loop_p (); 261: static void move_movables (); 262: static void strength_reduce (); 263: static int valid_initial_value_p (); 264: static void find_mem_givs (); 265: static void record_biv (); 266: static void check_final_value (); 267: static void record_giv (); 268: static void update_giv_derive (); 269: static void delete_insn_forces (); 270: static int basic_induction_var (); 271: static rtx simplify_giv_expr (); 272: static int general_induction_var (); 273: static int consec_sets_giv (); 274: static int check_dbra_loop (); 275: static rtx express_from (); 276: static int combine_givs_p (); 277: static void combine_givs (); 278: static int product_cheap_p (); 279: static int maybe_eliminate_biv (); 280: static int maybe_eliminate_biv_1 (); 281: static int last_use_this_basic_block (); 282: static void record_initial (); 283: static void update_reg_last_use (); 284: 285: /* Relative gain of eliminating various kinds of operations. */ 286: int add_cost; 287: #if 0 288: int shift_cost; 289: int mult_cost; 290: #endif 291: 292: /* Benefit penalty, if a giv is not replaceable, i.e. must emit an insn to 293: copy the value of the strength reduced giv to its original register. */ 294: int copy_cost; 295: 296: void 297: init_loop () 298: { 299: char *free_point = (char *) oballoc (1); 1.1.1.4 ! root 300: rtx reg = gen_rtx (REG, word_mode, 0); ! 301: rtx pow2 = GEN_INT (32); 1.1 root 302: rtx lea; 303: int i; 304: 1.1.1.4 ! root 305: add_cost = rtx_cost (gen_rtx (PLUS, word_mode, reg, reg), SET); 1.1 root 306: 307: /* We multiply by 2 to reconcile the difference in scale between 308: these two ways of computing costs. Otherwise the cost of a copy 309: will be far less than the cost of an add. */ 1.1.1.4 ! root 310: 1.1 root 311: copy_cost = 2 * 2; 312: 313: /* Free the objects we just allocated. */ 314: obfree (free_point); 315: 316: /* Initialize the obstack used for rtl in product_cheap_p. */ 317: gcc_obstack_init (&temp_obstack); 318: } 319: 320: /* Entry point of this file. Perform loop optimization 321: on the current function. F is the first insn of the function 322: and DUMPFILE is a stream for output of a trace of actions taken 323: (or 0 if none should be output). */ 324: 325: void 326: loop_optimize (f, dumpfile) 327: /* f is the first instruction of a chain of insns for one function */ 328: rtx f; 329: FILE *dumpfile; 330: { 331: register rtx insn; 332: register int i; 333: rtx end; 334: rtx last_insn; 335: 336: loop_dump_stream = dumpfile; 337: 338: init_recog_no_volatile (); 339: init_alias_analysis (); 340: 341: max_reg_before_loop = max_reg_num (); 342: 343: moved_once = (char *) alloca (max_reg_before_loop); 344: bzero (moved_once, max_reg_before_loop); 345: 346: regs_may_share = 0; 347: 348: /* Count the number of loops. */ 349: 350: max_loop_num = 0; 351: for (insn = f; insn; insn = NEXT_INSN (insn)) 352: { 353: if (GET_CODE (insn) == NOTE 354: && NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG) 355: max_loop_num++; 356: } 357: 358: /* Don't waste time if no loops. */ 359: if (max_loop_num == 0) 360: return; 361: 362: /* Get size to use for tables indexed by uids. 363: Leave some space for labels allocated by find_and_verify_loops. */ 1.1.1.4 ! root 364: max_uid_for_loop = get_max_uid () + 1 + max_loop_num * 32; 1.1 root 365: 366: uid_luid = (int *) alloca (max_uid_for_loop * sizeof (int)); 367: uid_loop_num = (int *) alloca (max_uid_for_loop * sizeof (int)); 368: 369: bzero (uid_luid, max_uid_for_loop * sizeof (int)); 370: bzero (uid_loop_num, max_uid_for_loop * sizeof (int)); 371: 372: /* Allocate tables for recording each loop. We set each entry, so they need 373: not be zeroed. */ 374: loop_number_loop_starts = (rtx *) alloca (max_loop_num * sizeof (rtx)); 375: loop_number_loop_ends = (rtx *) alloca (max_loop_num * sizeof (rtx)); 376: loop_outer_loop = (int *) alloca (max_loop_num * sizeof (int)); 377: loop_invalid = (char *) alloca (max_loop_num * sizeof (char)); 378: loop_number_exit_labels = (rtx *) alloca (max_loop_num * sizeof (rtx)); 379: 380: /* Find and process each loop. 381: First, find them, and record them in order of their beginnings. */ 382: find_and_verify_loops (f); 383: 384: /* Now find all register lifetimes. This must be done after 385: find_and_verify_loops, because it might reorder the insns in the 386: function. */ 387: reg_scan (f, max_reg_num (), 1); 388: 1.1.1.4 ! root 389: /* See if we went too far. */ ! 390: if (get_max_uid () > max_uid_for_loop) ! 391: abort (); ! 392: 1.1 root 393: /* Compute the mapping from uids to luids. 394: LUIDs are numbers assigned to insns, like uids, 395: except that luids increase monotonically through the code. 396: Don't assign luids to line-number NOTEs, so that the distance in luids 397: between two insns is not affected by -g. */ 398: 399: for (insn = f, i = 0; insn; insn = NEXT_INSN (insn)) 400: { 401: last_insn = insn; 402: if (GET_CODE (insn) != NOTE 403: || NOTE_LINE_NUMBER (insn) <= 0) 404: uid_luid[INSN_UID (insn)] = ++i; 405: else 406: /* Give a line number note the same luid as preceding insn. */ 407: uid_luid[INSN_UID (insn)] = i; 408: } 409: 410: max_luid = i + 1; 411: 412: /* Don't leave gaps in uid_luid for insns that have been 413: deleted. It is possible that the first or last insn 414: using some register has been deleted by cross-jumping. 415: Make sure that uid_luid for that former insn's uid 416: points to the general area where that insn used to be. */ 417: for (i = 0; i < max_uid_for_loop; i++) 418: { 419: uid_luid[0] = uid_luid[i]; 420: if (uid_luid[0] != 0) 421: break; 422: } 423: for (i = 0; i < max_uid_for_loop; i++) 424: if (uid_luid[i] == 0) 425: uid_luid[i] = uid_luid[i - 1]; 426: 427: /* Create a mapping from loops to BLOCK tree nodes. */ 428: if (flag_unroll_loops && write_symbols != NO_DEBUG) 1.1.1.4 ! root 429: find_loop_tree_blocks (); 1.1 root 430: 431: /* Now scan the loops, last ones first, since this means inner ones are done 432: before outer ones. */ 433: for (i = max_loop_num-1; i >= 0; i--) 434: if (! loop_invalid[i] && loop_number_loop_ends[i]) 435: scan_loop (loop_number_loop_starts[i], loop_number_loop_ends[i], 436: max_reg_num ()); 1.1.1.4 ! root 437: ! 438: /* If debugging and unrolling loops, we must replicate the tree nodes ! 439: corresponding to the blocks inside the loop, so that the original one ! 440: to one mapping will remain. */ ! 441: if (flag_unroll_loops && write_symbols != NO_DEBUG) ! 442: unroll_block_trees (); 1.1 root 443: } 444: 445: /* Optimize one loop whose start is LOOP_START and end is END. 446: LOOP_START is the NOTE_INSN_LOOP_BEG and END is the matching 447: NOTE_INSN_LOOP_END. */ 448: 449: /* ??? Could also move memory writes out of loops if the destination address 450: is invariant, the source is invariant, the memory write is not volatile, 451: and if we can prove that no read inside the loop can read this address 452: before the write occurs. If there is a read of this address after the 453: write, then we can also mark the memory read as invariant. */ 454: 455: static void 456: scan_loop (loop_start, end, nregs) 457: rtx loop_start, end; 458: int nregs; 459: { 460: register int i; 461: register rtx p; 462: /* 1 if we are scanning insns that could be executed zero times. */ 463: int maybe_never = 0; 464: /* 1 if we are scanning insns that might never be executed 465: due to a subroutine call which might exit before they are reached. */ 466: int call_passed = 0; 467: /* For a rotated loop that is entered near the bottom, 468: this is the label at the top. Otherwise it is zero. */ 469: rtx loop_top = 0; 470: /* Jump insn that enters the loop, or 0 if control drops in. */ 471: rtx loop_entry_jump = 0; 472: /* Place in the loop where control enters. */ 473: rtx scan_start; 474: /* Number of insns in the loop. */ 475: int insn_count; 476: int in_libcall = 0; 477: int tem; 478: rtx temp; 479: /* The SET from an insn, if it is the only SET in the insn. */ 480: rtx set, set1; 481: /* Chain describing insns movable in current loop. */ 482: struct movable *movables = 0; 483: /* Last element in `movables' -- so we can add elements at the end. */ 484: struct movable *last_movable = 0; 485: /* Ratio of extra register life span we can justify 486: for saving an instruction. More if loop doesn't call subroutines 487: since in that case saving an insn makes more difference 488: and more registers are available. */ 489: int threshold; 490: /* If we have calls, contains the insn in which a register was used 491: if it was used exactly once; contains const0_rtx if it was used more 492: than once. */ 493: rtx *reg_single_usage = 0; 494: 495: n_times_set = (short *) alloca (nregs * sizeof (short)); 496: n_times_used = (short *) alloca (nregs * sizeof (short)); 497: may_not_optimize = (char *) alloca (nregs); 498: 499: /* Determine whether this loop starts with a jump down to a test at 500: the end. This will occur for a small number of loops with a test 501: that is too complex to duplicate in front of the loop. 502: 503: We search for the first insn or label in the loop, skipping NOTEs. 504: However, we must be careful not to skip past a NOTE_INSN_LOOP_BEG 505: (because we might have a loop executed only once that contains a 506: loop which starts with a jump to its exit test) or a NOTE_INSN_LOOP_END 507: (in case we have a degenerate loop). 508: 509: Note that if we mistakenly think that a loop is entered at the top 510: when, in fact, it is entered at the exit test, the only effect will be 511: slightly poorer optimization. Making the opposite error can generate 512: incorrect code. Since very few loops now start with a jump to the 513: exit test, the code here to detect that case is very conservative. */ 514: 515: for (p = NEXT_INSN (loop_start); 516: p != end 517: && GET_CODE (p) != CODE_LABEL && GET_RTX_CLASS (GET_CODE (p)) != 'i' 518: && (GET_CODE (p) != NOTE 519: || (NOTE_LINE_NUMBER (p) != NOTE_INSN_LOOP_BEG 520: && NOTE_LINE_NUMBER (p) != NOTE_INSN_LOOP_END)); 521: p = NEXT_INSN (p)) 522: ; 523: 524: scan_start = p; 525: 526: /* Set up variables describing this loop. */ 527: prescan_loop (loop_start, end); 528: threshold = (loop_has_call ? 1 : 2) * (1 + n_non_fixed_regs); 529: 530: /* If loop has a jump before the first label, 531: the true entry is the target of that jump. 532: Start scan from there. 533: But record in LOOP_TOP the place where the end-test jumps 534: back to so we can scan that after the end of the loop. */ 535: if (GET_CODE (p) == JUMP_INSN) 536: { 537: loop_entry_jump = p; 538: 539: /* Loop entry must be unconditional jump (and not a RETURN) */ 540: if (simplejump_p (p) 541: && JUMP_LABEL (p) != 0 542: /* Check to see whether the jump actually 543: jumps out of the loop (meaning it's no loop). 544: This case can happen for things like 545: do {..} while (0). If this label was generated previously 546: by loop, we can't tell anything about it and have to reject 547: the loop. */ 548: && INSN_UID (JUMP_LABEL (p)) < max_uid_for_loop 549: && INSN_LUID (JUMP_LABEL (p)) >= INSN_LUID (loop_start) 550: && INSN_LUID (JUMP_LABEL (p)) < INSN_LUID (end)) 551: { 552: loop_top = next_label (scan_start); 553: scan_start = JUMP_LABEL (p); 554: } 555: } 556: 557: /* If SCAN_START was an insn created by loop, we don't know its luid 558: as required by loop_reg_used_before_p. So skip such loops. (This 559: test may never be true, but it's best to play it safe.) 560: 561: Also, skip loops where we do not start scanning at a label. This 562: test also rejects loops starting with a JUMP_INSN that failed the 563: test above. */ 564: 565: if (INSN_UID (scan_start) >= max_uid_for_loop 566: || GET_CODE (scan_start) != CODE_LABEL) 567: { 568: if (loop_dump_stream) 569: fprintf (loop_dump_stream, "\nLoop from %d to %d is phony.\n\n", 570: INSN_UID (loop_start), INSN_UID (end)); 571: return; 572: } 573: 574: /* Count number of times each reg is set during this loop. 575: Set may_not_optimize[I] if it is not safe to move out 576: the setting of register I. If this loop has calls, set 577: reg_single_usage[I]. */ 578: 579: bzero (n_times_set, nregs * sizeof (short)); 580: bzero (may_not_optimize, nregs); 581: 582: if (loop_has_call) 583: { 584: reg_single_usage = (rtx *) alloca (nregs * sizeof (rtx)); 585: bzero (reg_single_usage, nregs * sizeof (rtx)); 586: } 587: 588: count_loop_regs_set (loop_top ? loop_top : loop_start, end, 589: may_not_optimize, reg_single_usage, &insn_count, nregs); 590: 591: for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) 592: may_not_optimize[i] = 1, n_times_set[i] = 1; 593: bcopy (n_times_set, n_times_used, nregs * sizeof (short)); 594: 595: if (loop_dump_stream) 596: { 597: fprintf (loop_dump_stream, "\nLoop from %d to %d: %d real insns.\n", 598: INSN_UID (loop_start), INSN_UID (end), insn_count); 599: if (loop_continue) 600: fprintf (loop_dump_stream, "Continue at insn %d.\n", 601: INSN_UID (loop_continue)); 602: } 603: 604: /* Scan through the loop finding insns that are safe to move. 605: Set n_times_set negative for the reg being set, so that 606: this reg will be considered invariant for subsequent insns. 607: We consider whether subsequent insns use the reg 608: in deciding whether it is worth actually moving. 609: 610: MAYBE_NEVER is nonzero if we have passed a conditional jump insn 611: and therefore it is possible that the insns we are scanning 612: would never be executed. At such times, we must make sure 613: that it is safe to execute the insn once instead of zero times. 614: When MAYBE_NEVER is 0, all insns will be executed at least once 615: so that is not a problem. */ 616: 617: p = scan_start; 618: while (1) 619: { 620: p = NEXT_INSN (p); 621: /* At end of a straight-in loop, we are done. 622: At end of a loop entered at the bottom, scan the top. */ 623: if (p == scan_start) 624: break; 625: if (p == end) 626: { 627: if (loop_top != 0) 628: p = NEXT_INSN (loop_top); 629: else 630: break; 631: if (p == scan_start) 632: break; 633: } 634: 635: if (GET_RTX_CLASS (GET_CODE (p)) == 'i' 1.1.1.4 ! root 636: && find_reg_note (p, REG_LIBCALL, NULL_RTX)) 1.1 root 637: in_libcall = 1; 638: else if (GET_RTX_CLASS (GET_CODE (p)) == 'i' 1.1.1.4 ! root 639: && find_reg_note (p, REG_RETVAL, NULL_RTX)) 1.1 root 640: in_libcall = 0; 641: 642: if (GET_CODE (p) == INSN 643: && (set = single_set (p)) 644: && GET_CODE (SET_DEST (set)) == REG 645: && ! may_not_optimize[REGNO (SET_DEST (set))]) 646: { 647: int tem1 = 0; 648: int tem2 = 0; 649: int move_insn = 0; 650: rtx src = SET_SRC (set); 651: rtx dependencies = 0; 652: 653: /* Figure out what to use as a source of this insn. If a REG_EQUIV 654: note is given or if a REG_EQUAL note with a constant operand is 655: specified, use it as the source and mark that we should move 656: this insn by calling emit_move_insn rather that duplicating the 657: insn. 658: 659: Otherwise, only use the REG_EQUAL contents if a REG_RETVAL note 660: is present. */ 1.1.1.4 ! root 661: temp = find_reg_note (p, REG_EQUIV, NULL_RTX); 1.1 root 662: if (temp) 663: src = XEXP (temp, 0), move_insn = 1; 664: else 665: { 1.1.1.4 ! root 666: temp = find_reg_note (p, REG_EQUAL, NULL_RTX); 1.1 root 667: if (temp && CONSTANT_P (XEXP (temp, 0))) 668: src = XEXP (temp, 0), move_insn = 1; 1.1.1.4 ! root 669: if (temp && find_reg_note (p, REG_RETVAL, NULL_RTX)) 1.1 root 670: { 671: src = XEXP (temp, 0); 672: /* A libcall block can use regs that don't appear in 673: the equivalent expression. To move the libcall, 674: we must move those regs too. */ 675: dependencies = libcall_other_reg (p, src); 676: } 677: } 678: 679: /* Don't try to optimize a register that was made 680: by loop-optimization for an inner loop. 681: We don't know its life-span, so we can't compute the benefit. */ 682: if (REGNO (SET_DEST (set)) >= max_reg_before_loop) 683: ; 684: /* In order to move a register, we need to have one of three cases: 685: (1) it is used only in the same basic block as the set 686: (2) it is not a user variable. 687: (3) the set is guaranteed to be executed once the loop starts, 688: and the reg is not used until after that. */ 689: else if (! ((! maybe_never 690: && ! loop_reg_used_before_p (set, p, loop_start, 691: scan_start, end)) 692: || ! REG_USERVAR_P (SET_DEST (PATTERN (p))) 693: || reg_in_basic_block_p (p, SET_DEST (PATTERN (p))))) 694: ; 695: else if ((tem = invariant_p (src)) 696: && (dependencies == 0 697: || (tem2 = invariant_p (dependencies)) != 0) 698: && (n_times_set[REGNO (SET_DEST (set))] == 1 699: || (tem1 700: = consec_sets_invariant_p (SET_DEST (set), 701: n_times_set[REGNO (SET_DEST (set))], 702: p))) 703: /* If the insn can cause a trap (such as divide by zero), 704: can't move it unless it's guaranteed to be executed 705: once loop is entered. Even a function call might 706: prevent the trap insn from being reached 707: (since it might exit!) */ 708: && ! ((maybe_never || call_passed) 709: && may_trap_p (src))) 710: { 711: register struct movable *m; 712: register int regno = REGNO (SET_DEST (set)); 713: 714: /* A potential lossage is where we have a case where two insns 715: can be combined as long as they are both in the loop, but 716: we move one of them outside the loop. For large loops, 717: this can lose. The most common case of this is the address 718: of a function being called. 719: 720: Therefore, if this register is marked as being used exactly 721: once if we are in a loop with calls (a "large loop"), see if 722: we can replace the usage of this register with the source 723: of this SET. If we can, delete this insn. 724: 725: Don't do this if P has a REG_RETVAL note or if we have 726: SMALL_REGISTER_CLASSES and SET_SRC is a hard register. */ 727: 728: if (reg_single_usage && reg_single_usage[regno] != 0 729: && reg_single_usage[regno] != const0_rtx 730: && regno_first_uid[regno] == INSN_UID (p) 731: && (regno_last_uid[regno] 732: == INSN_UID (reg_single_usage[regno])) 733: && n_times_set[REGNO (SET_DEST (set))] == 1 734: && ! side_effects_p (SET_SRC (set)) 1.1.1.4 ! root 735: && ! find_reg_note (p, REG_RETVAL, NULL_RTX) 1.1 root 736: #ifdef SMALL_REGISTER_CLASSES 737: && ! (GET_CODE (SET_SRC (set)) == REG 738: && REGNO (SET_SRC (set)) < FIRST_PSEUDO_REGISTER) 739: #endif 740: /* This test is not redundant; SET_SRC (set) might be 741: a call-clobbered register and the life of REGNO 742: might span a call. */ 743: && ! modified_between_p (SET_SRC (set), p, 744: reg_single_usage[regno]) 745: && validate_replace_rtx (SET_DEST (set), SET_SRC (set), 746: reg_single_usage[regno])) 747: { 748: /* Replace any usage in a REG_EQUAL note. */ 749: REG_NOTES (reg_single_usage[regno]) 750: = replace_rtx (REG_NOTES (reg_single_usage[regno]), 751: SET_DEST (set), SET_SRC (set)); 752: 753: PUT_CODE (p, NOTE); 754: NOTE_LINE_NUMBER (p) = NOTE_INSN_DELETED; 755: NOTE_SOURCE_FILE (p) = 0; 756: n_times_set[regno] = 0; 757: continue; 758: } 759: 760: m = (struct movable *) alloca (sizeof (struct movable)); 761: m->next = 0; 762: m->insn = p; 763: m->set_src = src; 764: m->dependencies = dependencies; 765: m->set_dest = SET_DEST (set); 766: m->force = 0; 767: m->consec = n_times_set[REGNO (SET_DEST (set))] - 1; 768: m->done = 0; 769: m->forces = 0; 770: m->partial = 0; 771: m->move_insn = move_insn; 1.1.1.4 ! root 772: m->is_equiv = (find_reg_note (p, REG_EQUIV, NULL_RTX) != 0); 1.1 root 773: m->savemode = VOIDmode; 774: m->regno = regno; 775: /* Set M->cond if either invariant_p or consec_sets_invariant_p 776: returned 2 (only conditionally invariant). */ 777: m->cond = ((tem | tem1 | tem2) > 1); 778: m->global = (uid_luid[regno_last_uid[regno]] > INSN_LUID (end) 779: || uid_luid[regno_first_uid[regno]] < INSN_LUID (loop_start)); 780: m->match = 0; 781: m->lifetime = (uid_luid[regno_last_uid[regno]] 782: - uid_luid[regno_first_uid[regno]]); 783: m->savings = n_times_used[regno]; 1.1.1.4 ! root 784: if (find_reg_note (p, REG_RETVAL, NULL_RTX)) 1.1 root 785: m->savings += libcall_benefit (p); 786: n_times_set[regno] = move_insn ? -2 : -1; 787: /* Add M to the end of the chain MOVABLES. */ 788: if (movables == 0) 789: movables = m; 790: else 791: last_movable->next = m; 792: last_movable = m; 793: 794: if (m->consec > 0) 795: { 796: /* Skip this insn, not checking REG_LIBCALL notes. */ 797: p = NEXT_INSN (p); 798: /* Skip the consecutive insns, if there are any. */ 799: p = skip_consec_insns (p, m->consec); 800: /* Back up to the last insn of the consecutive group. */ 801: p = prev_nonnote_insn (p); 802: 803: /* We must now reset m->move_insn, m->is_equiv, and possibly 804: m->set_src to correspond to the effects of all the 805: insns. */ 1.1.1.4 ! root 806: temp = find_reg_note (p, REG_EQUIV, NULL_RTX); 1.1 root 807: if (temp) 808: m->set_src = XEXP (temp, 0), m->move_insn = 1; 809: else 810: { 1.1.1.4 ! root 811: temp = find_reg_note (p, REG_EQUAL, NULL_RTX); 1.1 root 812: if (temp && CONSTANT_P (XEXP (temp, 0))) 813: m->set_src = XEXP (temp, 0), m->move_insn = 1; 814: else 815: m->move_insn = 0; 816: 817: } 1.1.1.4 ! root 818: m->is_equiv = (find_reg_note (p, REG_EQUIV, NULL_RTX) != 0); 1.1 root 819: } 820: } 821: /* If this register is always set within a STRICT_LOW_PART 822: or set to zero, then its high bytes are constant. 823: So clear them outside the loop and within the loop 824: just load the low bytes. 825: We must check that the machine has an instruction to do so. 826: Also, if the value loaded into the register 827: depends on the same register, this cannot be done. */ 828: else if (SET_SRC (set) == const0_rtx 829: && GET_CODE (NEXT_INSN (p)) == INSN 830: && (set1 = single_set (NEXT_INSN (p))) 831: && GET_CODE (set1) == SET 832: && (GET_CODE (SET_DEST (set1)) == STRICT_LOW_PART) 833: && (GET_CODE (XEXP (SET_DEST (set1), 0)) == SUBREG) 834: && (SUBREG_REG (XEXP (SET_DEST (set1), 0)) 835: == SET_DEST (set)) 836: && !reg_mentioned_p (SET_DEST (set), SET_SRC (set1))) 837: { 838: register int regno = REGNO (SET_DEST (set)); 839: if (n_times_set[regno] == 2) 840: { 841: register struct movable *m; 842: m = (struct movable *) alloca (sizeof (struct movable)); 843: m->next = 0; 844: m->insn = p; 845: m->set_dest = SET_DEST (set); 846: m->dependencies = 0; 847: m->force = 0; 848: m->consec = 0; 849: m->done = 0; 850: m->forces = 0; 851: m->move_insn = 0; 852: m->partial = 1; 853: /* If the insn may not be executed on some cycles, 854: we can't clear the whole reg; clear just high part. 855: Not even if the reg is used only within this loop. 856: Consider this: 857: while (1) 858: while (s != t) { 859: if (foo ()) x = *s; 860: use (x); 861: } 862: Clearing x before the inner loop could clobber a value 863: being saved from the last time around the outer loop. 864: However, if the reg is not used outside this loop 865: and all uses of the register are in the same 866: basic block as the store, there is no problem. 867: 868: If this insn was made by loop, we don't know its 869: INSN_LUID and hence must make a conservative 870: assumption. */ 871: m->global = (INSN_UID (p) >= max_uid_for_loop 872: || (uid_luid[regno_last_uid[regno]] 873: > INSN_LUID (end)) 874: || (uid_luid[regno_first_uid[regno]] 875: < INSN_LUID (p)) 876: || (labels_in_range_p 877: (p, uid_luid[regno_first_uid[regno]]))); 878: if (maybe_never && m->global) 879: m->savemode = GET_MODE (SET_SRC (set1)); 880: else 881: m->savemode = VOIDmode; 882: m->regno = regno; 883: m->cond = 0; 884: m->match = 0; 885: m->lifetime = (uid_luid[regno_last_uid[regno]] 886: - uid_luid[regno_first_uid[regno]]); 887: m->savings = 1; 888: n_times_set[regno] = -1; 889: /* Add M to the end of the chain MOVABLES. */ 890: if (movables == 0) 891: movables = m; 892: else 893: last_movable->next = m; 894: last_movable = m; 895: } 896: } 897: } 898: /* Past a call insn, we get to insns which might not be executed 899: because the call might exit. This matters for insns that trap. 900: Call insns inside a REG_LIBCALL/REG_RETVAL block always return, 901: so they don't count. */ 902: else if (GET_CODE (p) == CALL_INSN && ! in_libcall) 903: call_passed = 1; 904: /* Past a label or a jump, we get to insns for which we 905: can't count on whether or how many times they will be 906: executed during each iteration. Therefore, we can 907: only move out sets of trivial variables 908: (those not used after the loop). */ 909: /* This code appears in three places, once in scan_loop, and twice 910: in strength_reduce. */ 911: else if ((GET_CODE (p) == CODE_LABEL || GET_CODE (p) == JUMP_INSN) 912: /* If we enter the loop in the middle, and scan around to the 913: beginning, don't set maybe_never for that. This must be an 914: unconditional jump, otherwise the code at the top of the 915: loop might never be executed. Unconditional jumps are 916: followed a by barrier then loop end. */ 917: && ! (GET_CODE (p) == JUMP_INSN && JUMP_LABEL (p) == loop_top 918: && NEXT_INSN (NEXT_INSN (p)) == end 919: && simplejump_p (p))) 920: maybe_never = 1; 921: /* At the virtual top of a converted loop, insns are again known to 922: be executed: logically, the loop begins here even though the exit 923: code has been duplicated. */ 924: else if (GET_CODE (p) == NOTE 925: && NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_VTOP) 926: maybe_never = call_passed = 0; 927: } 928: 929: /* If one movable subsumes another, ignore that other. */ 930: 931: ignore_some_movables (movables); 932: 933: /* For each movable insn, see if the reg that it loads 934: leads when it dies right into another conditionally movable insn. 935: If so, record that the second insn "forces" the first one, 936: since the second can be moved only if the first is. */ 937: 938: force_movables (movables); 939: 940: /* See if there are multiple movable insns that load the same value. 941: If there are, make all but the first point at the first one 942: through the `match' field, and add the priorities of them 943: all together as the priority of the first. */ 944: 945: combine_movables (movables, nregs); 946: 947: /* Now consider each movable insn to decide whether it is worth moving. 948: Store 0 in n_times_set for each reg that is moved. */ 949: 950: move_movables (movables, threshold, 951: insn_count, loop_start, end, nregs); 952: 953: /* Now candidates that still are negative are those not moved. 954: Change n_times_set to indicate that those are not actually invariant. */ 955: for (i = 0; i < nregs; i++) 956: if (n_times_set[i] < 0) 957: n_times_set[i] = n_times_used[i]; 958: 959: if (flag_strength_reduce) 960: strength_reduce (scan_start, end, loop_top, 961: insn_count, loop_start, end); 962: } 963: 964: /* Add elements to *OUTPUT to record all the pseudo-regs 965: mentioned in IN_THIS but not mentioned in NOT_IN_THIS. */ 966: 967: void 968: record_excess_regs (in_this, not_in_this, output) 969: rtx in_this, not_in_this; 970: rtx *output; 971: { 972: enum rtx_code code; 973: char *fmt; 974: int i; 975: 976: code = GET_CODE (in_this); 977: 978: switch (code) 979: { 980: case PC: 981: case CC0: 982: case CONST_INT: 983: case CONST_DOUBLE: 984: case CONST: 985: case SYMBOL_REF: 986: case LABEL_REF: 987: return; 988: 989: case REG: 990: if (REGNO (in_this) >= FIRST_PSEUDO_REGISTER 991: && ! reg_mentioned_p (in_this, not_in_this)) 992: *output = gen_rtx (EXPR_LIST, VOIDmode, in_this, *output); 993: return; 994: } 995: 996: fmt = GET_RTX_FORMAT (code); 997: for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) 998: { 999: int j; 1000: 1001: switch (fmt[i]) 1002: { 1003: case 'E': 1004: for (j = 0; j < XVECLEN (in_this, i); j++) 1005: record_excess_regs (XVECEXP (in_this, i, j), not_in_this, output); 1006: break; 1007: 1008: case 'e': 1009: record_excess_regs (XEXP (in_this, i), not_in_this, output); 1010: break; 1011: } 1012: } 1013: } 1014: 1015: /* Check what regs are referred to in the libcall block ending with INSN, 1016: aside from those mentioned in the equivalent value. 1017: If there are none, return 0. 1018: If there are one or more, return an EXPR_LIST containing all of them. */ 1019: 1020: static rtx 1021: libcall_other_reg (insn, equiv) 1022: rtx insn, equiv; 1023: { 1.1.1.4 ! root 1024: rtx note = find_reg_note (insn, REG_RETVAL, NULL_RTX); 1.1 root 1025: rtx p = XEXP (note, 0); 1026: rtx output = 0; 1027: 1028: /* First, find all the regs used in the libcall block 1029: that are not mentioned as inputs to the result. */ 1030: 1031: while (p != insn) 1032: { 1033: if (GET_CODE (p) == INSN || GET_CODE (p) == JUMP_INSN 1034: || GET_CODE (p) == CALL_INSN) 1035: record_excess_regs (PATTERN (p), equiv, &output); 1036: p = NEXT_INSN (p); 1037: } 1038: 1039: return output; 1040: } 1041: 1042: /* Return 1 if all uses of REG 1043: are between INSN and the end of the basic block. */ 1044: 1045: static int 1046: reg_in_basic_block_p (insn, reg) 1047: rtx insn, reg; 1048: { 1049: int regno = REGNO (reg); 1050: rtx p; 1051: 1052: if (regno_first_uid[regno] != INSN_UID (insn)) 1053: return 0; 1054: 1055: /* Search this basic block for the already recorded last use of the reg. */ 1056: for (p = insn; p; p = NEXT_INSN (p)) 1057: { 1058: switch (GET_CODE (p)) 1059: { 1060: case NOTE: 1061: break; 1062: 1063: case INSN: 1064: case CALL_INSN: 1065: /* Ordinary insn: if this is the last use, we win. */ 1066: if (regno_last_uid[regno] == INSN_UID (p)) 1067: return 1; 1068: break; 1069: 1070: case JUMP_INSN: 1071: /* Jump insn: if this is the last use, we win. */ 1072: if (regno_last_uid[regno] == INSN_UID (p)) 1073: return 1; 1074: /* Otherwise, it's the end of the basic block, so we lose. */ 1075: return 0; 1076: 1077: case CODE_LABEL: 1078: case BARRIER: 1079: /* It's the end of the basic block, so we lose. */ 1080: return 0; 1081: } 1082: } 1083: 1084: /* The "last use" doesn't follow the "first use"?? */ 1085: abort (); 1086: } 1087: 1088: /* Compute the benefit of eliminating the insns in the block whose 1089: last insn is LAST. This may be a group of insns used to compute a 1090: value directly or can contain a library call. */ 1091: 1092: static int 1093: libcall_benefit (last) 1094: rtx last; 1095: { 1096: rtx insn; 1097: int benefit = 0; 1098: 1.1.1.4 ! root 1099: for (insn = XEXP (find_reg_note (last, REG_RETVAL, NULL_RTX), 0); 1.1 root 1100: insn != last; insn = NEXT_INSN (insn)) 1101: { 1102: if (GET_CODE (insn) == CALL_INSN) 1103: benefit += 10; /* Assume at least this many insns in a library 1104: routine. */ 1105: else if (GET_CODE (insn) == INSN 1106: && GET_CODE (PATTERN (insn)) != USE 1107: && GET_CODE (PATTERN (insn)) != CLOBBER) 1108: benefit++; 1109: } 1110: 1111: return benefit; 1112: } 1113: 1114: /* Skip COUNT insns from INSN, counting library calls as 1 insn. */ 1115: 1116: static rtx 1117: skip_consec_insns (insn, count) 1118: rtx insn; 1119: int count; 1120: { 1121: for (; count > 0; count--) 1122: { 1123: rtx temp; 1124: 1125: /* If first insn of libcall sequence, skip to end. */ 1126: /* Do this at start of loop, since INSN is guaranteed to 1127: be an insn here. */ 1128: if (GET_CODE (insn) != NOTE 1.1.1.4 ! root 1129: && (temp = find_reg_note (insn, REG_LIBCALL, NULL_RTX))) 1.1 root 1130: insn = XEXP (temp, 0); 1131: 1132: do insn = NEXT_INSN (insn); 1133: while (GET_CODE (insn) == NOTE); 1134: } 1135: 1136: return insn; 1137: } 1138: 1139: /* Ignore any movable whose insn falls within a libcall 1140: which is part of another movable. 1141: We make use of the fact that the movable for the libcall value 1142: was made later and so appears later on the chain. */ 1143: 1144: static void 1145: ignore_some_movables (movables) 1146: struct movable *movables; 1147: { 1148: register struct movable *m, *m1; 1149: 1150: for (m = movables; m; m = m->next) 1151: { 1152: /* Is this a movable for the value of a libcall? */ 1.1.1.4 ! root 1153: rtx note = find_reg_note (m->insn, REG_RETVAL, NULL_RTX); 1.1 root 1154: if (note) 1155: { 1156: rtx insn; 1157: /* Check for earlier movables inside that range, 1158: and mark them invalid. We cannot use LUIDs here because 1159: insns created by loop.c for prior loops don't have LUIDs. 1160: Rather than reject all such insns from movables, we just 1161: explicitly check each insn in the libcall (since invariant 1162: libcalls aren't that common). */ 1163: for (insn = XEXP (note, 0); insn != m->insn; insn = NEXT_INSN (insn)) 1164: for (m1 = movables; m1 != m; m1 = m1->next) 1165: if (m1->insn == insn) 1166: m1->done = 1; 1167: } 1168: } 1169: } 1170: 1171: /* For each movable insn, see if the reg that it loads 1172: leads when it dies right into another conditionally movable insn. 1173: If so, record that the second insn "forces" the first one, 1174: since the second can be moved only if the first is. */ 1175: 1176: static void 1177: force_movables (movables) 1178: struct movable *movables; 1179: { 1180: register struct movable *m, *m1; 1181: for (m1 = movables; m1; m1 = m1->next) 1182: /* Omit this if moving just the (SET (REG) 0) of a zero-extend. */ 1183: if (!m1->partial && !m1->done) 1184: { 1185: int regno = m1->regno; 1186: for (m = m1->next; m; m = m->next) 1187: /* ??? Could this be a bug? What if CSE caused the 1188: register of M1 to be used after this insn? 1189: Since CSE does not update regno_last_uid, 1190: this insn M->insn might not be where it dies. 1191: But very likely this doesn't matter; what matters is 1192: that M's reg is computed from M1's reg. */ 1193: if (INSN_UID (m->insn) == regno_last_uid[regno] 1194: && !m->done) 1195: break; 1196: if (m != 0 && m->set_src == m1->set_dest 1197: /* If m->consec, m->set_src isn't valid. */ 1198: && m->consec == 0) 1199: m = 0; 1200: 1201: /* Increase the priority of the moving the first insn 1202: since it permits the second to be moved as well. */ 1203: if (m != 0) 1204: { 1205: m->forces = m1; 1206: m1->lifetime += m->lifetime; 1207: m1->savings += m1->savings; 1208: } 1209: } 1210: } 1211: 1212: /* Find invariant expressions that are equal and can be combined into 1213: one register. */ 1214: 1215: static void 1216: combine_movables (movables, nregs) 1217: struct movable *movables; 1218: int nregs; 1219: { 1220: register struct movable *m; 1221: char *matched_regs = (char *) alloca (nregs); 1222: enum machine_mode mode; 1223: 1224: /* Regs that are set more than once are not allowed to match 1225: or be matched. I'm no longer sure why not. */ 1226: /* Perhaps testing m->consec_sets would be more appropriate here? */ 1227: 1228: for (m = movables; m; m = m->next) 1229: if (m->match == 0 && n_times_used[m->regno] == 1 && !m->partial) 1230: { 1231: register struct movable *m1; 1232: int regno = m->regno; 1233: rtx reg_note, reg_note1; 1234: 1235: bzero (matched_regs, nregs); 1236: matched_regs[regno] = 1; 1237: 1238: for (m1 = movables; m1; m1 = m1->next) 1239: if (m != m1 && m1->match == 0 && n_times_used[m1->regno] == 1 1240: /* A reg used outside the loop mustn't be eliminated. */ 1241: && !m1->global 1242: /* A reg used for zero-extending mustn't be eliminated. */ 1243: && !m1->partial 1244: && (matched_regs[m1->regno] 1245: || 1246: ( 1247: /* Can combine regs with different modes loaded from the 1248: same constant only if the modes are the same or 1249: if both are integer modes with M wider or the same 1250: width as M1. The check for integer is redundant, but 1251: safe, since the only case of differing destination 1252: modes with equal sources is when both sources are 1253: VOIDmode, i.e., CONST_INT. */ 1254: (GET_MODE (m->set_dest) == GET_MODE (m1->set_dest) 1255: || (GET_MODE_CLASS (GET_MODE (m->set_dest)) == MODE_INT 1256: && GET_MODE_CLASS (GET_MODE (m1->set_dest)) == MODE_INT 1257: && (GET_MODE_BITSIZE (GET_MODE (m->set_dest)) 1258: >= GET_MODE_BITSIZE (GET_MODE (m1->set_dest))))) 1259: /* See if the source of M1 says it matches M. */ 1260: && ((GET_CODE (m1->set_src) == REG 1261: && matched_regs[REGNO (m1->set_src)]) 1262: || rtx_equal_for_loop_p (m->set_src, m1->set_src, 1263: movables)))) 1264: && ((m->dependencies == m1->dependencies) 1265: || rtx_equal_p (m->dependencies, m1->dependencies))) 1266: { 1267: m->lifetime += m1->lifetime; 1268: m->savings += m1->savings; 1269: m1->done = 1; 1270: m1->match = m; 1271: matched_regs[m1->regno] = 1; 1272: } 1273: } 1274: 1275: /* Now combine the regs used for zero-extension. 1276: This can be done for those not marked `global' 1277: provided their lives don't overlap. */ 1278: 1279: for (mode = GET_CLASS_NARROWEST_MODE (MODE_INT); mode != VOIDmode; 1280: mode = GET_MODE_WIDER_MODE (mode)) 1281: { 1282: register struct movable *m0 = 0; 1283: 1284: /* Combine all the registers for extension from mode MODE. 1285: Don't combine any that are used outside this loop. */ 1286: for (m = movables; m; m = m->next) 1287: if (m->partial && ! m->global 1288: && mode == GET_MODE (SET_SRC (PATTERN (NEXT_INSN (m->insn))))) 1289: { 1290: register struct movable *m1; 1291: int first = uid_luid[regno_first_uid[m->regno]]; 1292: int last = uid_luid[regno_last_uid[m->regno]]; 1293: 1294: if (m0 == 0) 1295: { 1296: /* First one: don't check for overlap, just record it. */ 1297: m0 = m; 1298: continue; 1299: } 1300: 1301: /* Make sure they extend to the same mode. 1302: (Almost always true.) */ 1303: if (GET_MODE (m->set_dest) != GET_MODE (m0->set_dest)) 1304: continue; 1305: 1306: /* We already have one: check for overlap with those 1307: already combined together. */ 1308: for (m1 = movables; m1 != m; m1 = m1->next) 1309: if (m1 == m0 || (m1->partial && m1->match == m0)) 1310: if (! (uid_luid[regno_first_uid[m1->regno]] > last 1311: || uid_luid[regno_last_uid[m1->regno]] < first)) 1312: goto overlap; 1313: 1314: /* No overlap: we can combine this with the others. */ 1315: m0->lifetime += m->lifetime; 1316: m0->savings += m->savings; 1317: m->done = 1; 1318: m->match = m0; 1319: 1320: overlap: ; 1321: } 1322: } 1323: } 1324: 1325: /* Return 1 if regs X and Y will become the same if moved. */ 1326: 1327: static int 1328: regs_match_p (x, y, movables) 1329: rtx x, y; 1330: struct movable *movables; 1331: { 1332: int xn = REGNO (x); 1333: int yn = REGNO (y); 1334: struct movable *mx, *my; 1335: 1336: for (mx = movables; mx; mx = mx->next) 1337: if (mx->regno == xn) 1338: break; 1339: 1340: for (my = movables; my; my = my->next) 1341: if (my->regno == yn) 1342: break; 1343: 1344: return (mx && my 1345: && ((mx->match == my->match && mx->match != 0) 1346: || mx->match == my 1347: || mx == my->match)); 1348: } 1349: 1350: /* Return 1 if X and Y are identical-looking rtx's. 1351: This is the Lisp function EQUAL for rtx arguments. 1352: 1353: If two registers are matching movables or a movable register and an 1354: equivalent constant, consider them equal. */ 1355: 1356: static int 1357: rtx_equal_for_loop_p (x, y, movables) 1358: rtx x, y; 1359: struct movable *movables; 1360: { 1361: register int i; 1362: register int j; 1363: register struct movable *m; 1364: register enum rtx_code code; 1365: register char *fmt; 1366: 1367: if (x == y) 1368: return 1; 1369: if (x == 0 || y == 0) 1370: return 0; 1371: 1372: code = GET_CODE (x); 1373: 1374: /* If we have a register and a constant, they may sometimes be 1375: equal. */ 1376: if (GET_CODE (x) == REG && n_times_set[REGNO (x)] == -2 1377: && CONSTANT_P (y)) 1378: for (m = movables; m; m = m->next) 1379: if (m->move_insn && m->regno == REGNO (x) 1380: && rtx_equal_p (m->set_src, y)) 1381: return 1; 1382: 1383: else if (GET_CODE (y) == REG && n_times_set[REGNO (y)] == -2 1384: && CONSTANT_P (x)) 1385: for (m = movables; m; m = m->next) 1386: if (m->move_insn && m->regno == REGNO (y) 1387: && rtx_equal_p (m->set_src, x)) 1388: return 1; 1389: 1390: /* Otherwise, rtx's of different codes cannot be equal. */ 1391: if (code != GET_CODE (y)) 1392: return 0; 1393: 1394: /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent. 1395: (REG:SI x) and (REG:HI x) are NOT equivalent. */ 1396: 1397: if (GET_MODE (x) != GET_MODE (y)) 1398: return 0; 1399: 1400: /* These three types of rtx's can be compared nonrecursively. */ 1401: if (code == REG) 1402: return (REGNO (x) == REGNO (y) || regs_match_p (x, y, movables)); 1403: 1404: if (code == LABEL_REF) 1405: return XEXP (x, 0) == XEXP (y, 0); 1406: if (code == SYMBOL_REF) 1407: return XSTR (x, 0) == XSTR (y, 0); 1408: 1409: /* Compare the elements. If any pair of corresponding elements 1410: fail to match, return 0 for the whole things. */ 1411: 1412: fmt = GET_RTX_FORMAT (code); 1413: for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) 1414: { 1415: switch (fmt[i]) 1416: { 1.1.1.4 ! root 1417: case 'w': ! 1418: if (XWINT (x, i) != XWINT (y, i)) ! 1419: return 0; ! 1420: break; ! 1421: 1.1 root 1422: case 'i': 1423: if (XINT (x, i) != XINT (y, i)) 1424: return 0; 1425: break; 1426: 1427: case 'E': 1428: /* Two vectors must have the same length. */ 1429: if (XVECLEN (x, i) != XVECLEN (y, i)) 1430: return 0; 1431: 1432: /* And the corresponding elements must match. */ 1433: for (j = 0; j < XVECLEN (x, i); j++) 1434: if (rtx_equal_for_loop_p (XVECEXP (x, i, j), XVECEXP (y, i, j), movables) == 0) 1435: return 0; 1436: break; 1437: 1438: case 'e': 1439: if (rtx_equal_for_loop_p (XEXP (x, i), XEXP (y, i), movables) == 0) 1440: return 0; 1441: break; 1442: 1443: case 's': 1444: if (strcmp (XSTR (x, i), XSTR (y, i))) 1445: return 0; 1446: break; 1447: 1448: case 'u': 1449: /* These are just backpointers, so they don't matter. */ 1450: break; 1451: 1452: case '0': 1453: break; 1454: 1455: /* It is believed that rtx's at this level will never 1456: contain anything but integers and other rtx's, 1457: except for within LABEL_REFs and SYMBOL_REFs. */ 1458: default: 1459: abort (); 1460: } 1461: } 1462: return 1; 1463: } 1464: 1.1.1.2 root 1465: /* If X contains any LABEL_REF's, add REG_LABEL notes for them to all 1466: insns in INSNS which use thet reference. */ 1467: 1468: static void 1469: add_label_notes (x, insns) 1470: rtx x; 1471: rtx insns; 1472: { 1473: enum rtx_code code = GET_CODE (x); 1.1.1.3 root 1474: int i, j; 1.1.1.2 root 1475: char *fmt; 1476: rtx insn; 1477: 1.1.1.4 ! root 1478: if (code == LABEL_REF && !LABEL_REF_NONLOCAL_P (x)) 1.1.1.2 root 1479: { 1480: for (insn = insns; insn; insn = NEXT_INSN (insn)) 1481: if (reg_mentioned_p (XEXP (x, 0), insn)) 1482: REG_NOTES (insn) = gen_rtx (EXPR_LIST, REG_LABEL, XEXP (x, 0), 1483: REG_NOTES (insn)); 1484: return; 1485: } 1486: 1487: fmt = GET_RTX_FORMAT (code); 1488: for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) 1.1.1.3 root 1489: { 1490: if (fmt[i] == 'e') 1491: add_label_notes (XEXP (x, i), insns); 1492: else if (fmt[i] == 'E') 1493: for (j = XVECLEN (x, i) - 1; j >= 0; j--) 1494: add_label_notes (XVECEXP (x, i, j), insns); 1495: } 1.1.1.2 root 1496: } 1497: 1.1 root 1498: /* Scan MOVABLES, and move the insns that deserve to be moved. 1499: If two matching movables are combined, replace one reg with the 1500: other throughout. */ 1501: 1502: static void 1503: move_movables (movables, threshold, insn_count, loop_start, end, nregs) 1504: struct movable *movables; 1505: int threshold; 1506: int insn_count; 1507: rtx loop_start; 1508: rtx end; 1509: int nregs; 1510: { 1511: rtx new_start = 0; 1512: register struct movable *m; 1513: register rtx p; 1514: /* Map of pseudo-register replacements to handle combining 1515: when we move several insns that load the same value 1516: into different pseudo-registers. */ 1517: rtx *reg_map = (rtx *) alloca (nregs * sizeof (rtx)); 1518: char *already_moved = (char *) alloca (nregs); 1519: 1520: bzero (already_moved, nregs); 1521: bzero (reg_map, nregs * sizeof (rtx)); 1522: 1523: num_movables = 0; 1524: 1525: for (m = movables; m; m = m->next) 1526: { 1527: /* Describe this movable insn. */ 1528: 1529: if (loop_dump_stream) 1530: { 1531: fprintf (loop_dump_stream, "Insn %d: regno %d (life %d), ", 1532: INSN_UID (m->insn), m->regno, m->lifetime); 1533: if (m->consec > 0) 1534: fprintf (loop_dump_stream, "consec %d, ", m->consec); 1535: if (m->cond) 1536: fprintf (loop_dump_stream, "cond "); 1537: if (m->force) 1538: fprintf (loop_dump_stream, "force "); 1539: if (m->global) 1540: fprintf (loop_dump_stream, "global "); 1541: if (m->done) 1542: fprintf (loop_dump_stream, "done "); 1543: if (m->move_insn) 1544: fprintf (loop_dump_stream, "move-insn "); 1545: if (m->match) 1546: fprintf (loop_dump_stream, "matches %d ", 1547: INSN_UID (m->match->insn)); 1548: if (m->forces) 1549: fprintf (loop_dump_stream, "forces %d ", 1550: INSN_UID (m->forces->insn)); 1551: } 1552: 1553: /* Count movables. Value used in heuristics in strength_reduce. */ 1554: num_movables++; 1555: 1556: /* Ignore the insn if it's already done (it matched something else). 1557: Otherwise, see if it is now safe to move. */ 1558: 1559: if (!m->done 1560: && (! m->cond 1561: || (1 == invariant_p (m->set_src) 1562: && (m->dependencies == 0 1563: || 1 == invariant_p (m->dependencies)) 1564: && (m->consec == 0 1565: || 1 == consec_sets_invariant_p (m->set_dest, 1566: m->consec + 1, 1567: m->insn)))) 1568: && (! m->forces || m->forces->done)) 1569: { 1570: register int regno; 1571: register rtx p; 1572: int savings = m->savings; 1573: 1574: /* We have an insn that is safe to move. 1575: Compute its desirability. */ 1576: 1577: p = m->insn; 1578: regno = m->regno; 1579: 1580: if (loop_dump_stream) 1581: fprintf (loop_dump_stream, "savings %d ", savings); 1582: 1583: if (moved_once[regno]) 1584: { 1585: insn_count *= 2; 1586: 1587: if (loop_dump_stream) 1588: fprintf (loop_dump_stream, "halved since already moved "); 1589: } 1590: 1591: /* An insn MUST be moved if we already moved something else 1592: which is safe only if this one is moved too: that is, 1593: if already_moved[REGNO] is nonzero. */ 1594: 1595: /* An insn is desirable to move if the new lifetime of the 1596: register is no more than THRESHOLD times the old lifetime. 1597: If it's not desirable, it means the loop is so big 1598: that moving won't speed things up much, 1599: and it is liable to make register usage worse. */ 1600: 1601: /* It is also desirable to move if it can be moved at no 1602: extra cost because something else was already moved. */ 1603: 1604: if (already_moved[regno] 1605: || (threshold * savings * m->lifetime) >= insn_count 1606: || (m->forces && m->forces->done 1607: && n_times_used[m->forces->regno] == 1)) 1608: { 1609: int count; 1610: register struct movable *m1; 1611: rtx first; 1612: 1613: /* Now move the insns that set the reg. */ 1614: 1615: if (m->partial && m->match) 1616: { 1617: rtx newpat, i1; 1618: rtx r1, r2; 1619: /* Find the end of this chain of matching regs. 1620: Thus, we load each reg in the chain from that one reg. 1621: And that reg is loaded with 0 directly, 1622: since it has ->match == 0. */ 1623: for (m1 = m; m1->match; m1 = m1->match); 1624: newpat = gen_move_insn (SET_DEST (PATTERN (m->insn)), 1625: SET_DEST (PATTERN (m1->insn))); 1626: i1 = emit_insn_before (newpat, loop_start); 1627: 1628: /* Mark the moved, invariant reg as being allowed to 1629: share a hard reg with the other matching invariant. */ 1630: REG_NOTES (i1) = REG_NOTES (m->insn); 1631: r1 = SET_DEST (PATTERN (m->insn)); 1632: r2 = SET_DEST (PATTERN (m1->insn)); 1633: regs_may_share = gen_rtx (EXPR_LIST, VOIDmode, r1, 1634: gen_rtx (EXPR_LIST, VOIDmode, r2, 1635: regs_may_share)); 1636: delete_insn (m->insn); 1637: 1638: if (new_start == 0) 1639: new_start = i1; 1640: 1641: if (loop_dump_stream) 1642: fprintf (loop_dump_stream, " moved to %d", INSN_UID (i1)); 1643: } 1644: /* If we are to re-generate the item being moved with a 1645: new move insn, first delete what we have and then emit 1646: the move insn before the loop. */ 1647: else if (m->move_insn) 1648: { 1649: rtx i1, temp; 1650: 1651: for (count = m->consec; count >= 0; count--) 1652: { 1653: /* If this is the first insn of a library call sequence, 1654: skip to the end. */ 1655: if (GET_CODE (p) != NOTE 1.1.1.4 ! root 1656: && (temp = find_reg_note (p, REG_LIBCALL, NULL_RTX))) 1.1 root 1657: p = XEXP (temp, 0); 1658: 1659: /* If this is the last insn of a libcall sequence, then 1660: delete every insn in the sequence except the last. 1661: The last insn is handled in the normal manner. */ 1662: if (GET_CODE (p) != NOTE 1.1.1.4 ! root 1663: && (temp = find_reg_note (p, REG_RETVAL, NULL_RTX))) 1.1 root 1664: { 1665: temp = XEXP (temp, 0); 1666: while (temp != p) 1667: temp = delete_insn (temp); 1668: } 1669: 1670: p = delete_insn (p); 1671: } 1672: 1673: start_sequence (); 1674: emit_move_insn (m->set_dest, m->set_src); 1.1.1.2 root 1675: temp = get_insns (); 1.1 root 1676: end_sequence (); 1677: 1.1.1.2 root 1678: add_label_notes (m->set_src, temp); 1679: 1680: i1 = emit_insns_before (temp, loop_start); 1.1.1.4 ! root 1681: if (! find_reg_note (i1, REG_EQUAL, NULL_RTX)) 1.1 root 1682: REG_NOTES (i1) 1683: = gen_rtx (EXPR_LIST, 1684: m->is_equiv ? REG_EQUIV : REG_EQUAL, 1685: m->set_src, REG_NOTES (i1)); 1686: 1687: if (loop_dump_stream) 1688: fprintf (loop_dump_stream, " moved to %d", INSN_UID (i1)); 1689: 1690: /* The more regs we move, the less we like moving them. */ 1691: threshold -= 3; 1692: } 1693: else 1694: { 1695: for (count = m->consec; count >= 0; count--) 1696: { 1697: rtx i1, temp; 1698: 1699: /* If first insn of libcall sequence, skip to end. */ 1700: /* Do this at start of loop, since p is guaranteed to 1701: be an insn here. */ 1702: if (GET_CODE (p) != NOTE 1.1.1.4 ! root 1703: && (temp = find_reg_note (p, REG_LIBCALL, NULL_RTX))) 1.1 root 1704: p = XEXP (temp, 0); 1705: 1706: /* If last insn of libcall sequence, move all 1707: insns except the last before the loop. The last 1708: insn is handled in the normal manner. */ 1709: if (GET_CODE (p) != NOTE 1.1.1.4 ! root 1710: && (temp = find_reg_note (p, REG_RETVAL, NULL_RTX))) 1.1 root 1711: { 1712: rtx fn_address = 0; 1713: rtx fn_reg = 0; 1714: rtx fn_address_insn = 0; 1715: 1716: first = 0; 1717: for (temp = XEXP (temp, 0); temp != p; 1718: temp = NEXT_INSN (temp)) 1719: { 1720: rtx body; 1721: rtx n; 1722: rtx next; 1723: 1724: if (GET_CODE (temp) == NOTE) 1725: continue; 1726: 1727: body = PATTERN (temp); 1728: 1729: /* Find the next insn after TEMP, 1730: not counting USE or NOTE insns. */ 1731: for (next = NEXT_INSN (temp); next != p; 1732: next = NEXT_INSN (next)) 1733: if (! (GET_CODE (next) == INSN 1734: && GET_CODE (PATTERN (next)) == USE) 1735: && GET_CODE (next) != NOTE) 1736: break; 1737: 1738: /* If that is the call, this may be the insn 1739: that loads the function address. 1740: 1741: Extract the function address from the insn 1742: that loads it into a register. 1743: If this insn was cse'd, we get incorrect code. 1744: 1745: So emit a new move insn that copies the 1746: function address into the register that the 1747: call insn will use. flow.c will delete any 1748: redundant stores that we have created. */ 1749: if (GET_CODE (next) == CALL_INSN 1750: && GET_CODE (body) == SET 1751: && GET_CODE (SET_DEST (body)) == REG 1.1.1.4 ! root 1752: && (n = find_reg_note (temp, REG_EQUAL, ! 1753: NULL_RTX))) 1.1 root 1754: { 1755: fn_reg = SET_SRC (body); 1756: if (GET_CODE (fn_reg) != REG) 1757: fn_reg = SET_DEST (body); 1758: fn_address = XEXP (n, 0); 1759: fn_address_insn = temp; 1760: } 1761: /* We have the call insn. 1762: If it uses the register we suspect it might, 1763: load it with the correct address directly. */ 1764: if (GET_CODE (temp) == CALL_INSN 1765: && fn_address != 0 1.1.1.4 ! root 1766: && reg_referenced_p (fn_reg, body)) 1.1 root 1767: emit_insn_after (gen_move_insn (fn_reg, 1768: fn_address), 1769: fn_address_insn); 1770: 1771: if (GET_CODE (temp) == CALL_INSN) 1772: i1 = emit_call_insn_before (body, loop_start); 1773: else 1774: i1 = emit_insn_before (body, loop_start); 1775: if (first == 0) 1776: first = i1; 1777: if (temp == fn_address_insn) 1778: fn_address_insn = i1; 1779: REG_NOTES (i1) = REG_NOTES (temp); 1780: delete_insn (temp); 1781: } 1782: } 1783: if (m->savemode != VOIDmode) 1784: { 1785: /* P sets REG to zero; but we should clear only 1786: the bits that are not covered by the mode 1787: m->savemode. */ 1788: rtx reg = m->set_dest; 1789: rtx sequence; 1790: rtx tem; 1791: 1792: start_sequence (); 1793: tem = expand_binop 1794: (GET_MODE (reg), and_optab, reg, 1.1.1.4 ! root 1795: GEN_INT ((((HOST_WIDE_INT) 1 ! 1796: << GET_MODE_BITSIZE (m->savemode))) 1.1 root 1797: - 1), 1798: reg, 1, OPTAB_LIB_WIDEN); 1799: if (tem == 0) 1800: abort (); 1801: if (tem != reg) 1802: emit_move_insn (reg, tem); 1803: sequence = gen_sequence (); 1804: end_sequence (); 1805: i1 = emit_insn_before (sequence, loop_start); 1806: } 1807: else if (GET_CODE (p) == CALL_INSN) 1808: i1 = emit_call_insn_before (PATTERN (p), loop_start); 1809: else 1810: i1 = emit_insn_before (PATTERN (p), loop_start); 1811: 1812: REG_NOTES (i1) = REG_NOTES (p); 1813: 1814: if (new_start == 0) 1815: new_start = i1; 1816: 1817: if (loop_dump_stream) 1818: fprintf (loop_dump_stream, " moved to %d", 1819: INSN_UID (i1)); 1820: 1821: #if 0 1822: /* This isn't needed because REG_NOTES is copied 1823: below and is wrong since P might be a PARALLEL. */ 1824: if (REG_NOTES (i1) == 0 1825: && ! m->partial /* But not if it's a zero-extend clr. */ 1826: && ! m->global /* and not if used outside the loop 1827: (since it might get set outside). */ 1828: && CONSTANT_P (SET_SRC (PATTERN (p)))) 1829: REG_NOTES (i1) 1830: = gen_rtx (EXPR_LIST, REG_EQUAL, 1831: SET_SRC (PATTERN (p)), REG_NOTES (i1)); 1832: #endif 1833: 1834: /* If library call, now fix the REG_NOTES that contain 1835: insn pointers, namely REG_LIBCALL on FIRST 1836: and REG_RETVAL on I1. */ 1.1.1.4 ! root 1837: if (temp = find_reg_note (i1, REG_RETVAL, NULL_RTX)) 1.1 root 1838: { 1839: XEXP (temp, 0) = first; 1.1.1.4 ! root 1840: temp = find_reg_note (first, REG_LIBCALL, NULL_RTX); 1.1 root 1841: XEXP (temp, 0) = i1; 1842: } 1843: 1844: delete_insn (p); 1845: do p = NEXT_INSN (p); 1846: while (p && GET_CODE (p) == NOTE); 1847: } 1848: 1849: /* The more regs we move, the less we like moving them. */ 1850: threshold -= 3; 1851: } 1852: 1853: /* Any other movable that loads the same register 1854: MUST be moved. */ 1855: already_moved[regno] = 1; 1856: 1857: /* This reg has been moved out of one loop. */ 1858: moved_once[regno] = 1; 1859: 1860: /* The reg set here is now invariant. */ 1861: if (! m->partial) 1862: n_times_set[regno] = 0; 1863: 1864: m->done = 1; 1865: 1866: /* Change the length-of-life info for the register 1867: to say it lives at least the full length of this loop. 1868: This will help guide optimizations in outer loops. */ 1869: 1870: if (uid_luid[regno_first_uid[regno]] > INSN_LUID (loop_start)) 1871: /* This is the old insn before all the moved insns. 1872: We can't use the moved insn because it is out of range 1873: in uid_luid. Only the old insns have luids. */ 1874: regno_first_uid[regno] = INSN_UID (loop_start); 1875: if (uid_luid[regno_last_uid[regno]] < INSN_LUID (end)) 1876: regno_last_uid[regno] = INSN_UID (end); 1877: 1878: /* Combine with this moved insn any other matching movables. */ 1879: 1880: if (! m->partial) 1881: for (m1 = movables; m1; m1 = m1->next) 1882: if (m1->match == m) 1883: { 1884: rtx temp; 1885: 1886: /* Schedule the reg loaded by M1 1887: for replacement so that shares the reg of M. 1888: If the modes differ (only possible in restricted 1889: circumstances, make a SUBREG. */ 1890: if (GET_MODE (m->set_dest) == GET_MODE (m1->set_dest)) 1891: reg_map[m1->regno] = m->set_dest; 1892: else 1893: reg_map[m1->regno] 1894: = gen_lowpart_common (GET_MODE (m1->set_dest), 1895: m->set_dest); 1896: 1897: /* Get rid of the matching insn 1898: and prevent further processing of it. */ 1899: m1->done = 1; 1900: 1901: /* if library call, delete all insn except last, which 1902: is deleted below */ 1.1.1.4 ! root 1903: if (temp = find_reg_note (m1->insn, REG_RETVAL, ! 1904: NULL_RTX)) 1.1 root 1905: { 1906: for (temp = XEXP (temp, 0); temp != m1->insn; 1907: temp = NEXT_INSN (temp)) 1908: delete_insn (temp); 1909: } 1910: delete_insn (m1->insn); 1911: 1912: /* Any other movable that loads the same register 1913: MUST be moved. */ 1914: already_moved[m1->regno] = 1; 1915: 1916: /* The reg merged here is now invariant, 1917: if the reg it matches is invariant. */ 1918: if (! m->partial) 1919: n_times_set[m1->regno] = 0; 1920: } 1921: } 1922: else if (loop_dump_stream) 1923: fprintf (loop_dump_stream, "not desirable"); 1924: } 1925: else if (loop_dump_stream && !m->match) 1926: fprintf (loop_dump_stream, "not safe"); 1927: 1928: if (loop_dump_stream) 1929: fprintf (loop_dump_stream, "\n"); 1930: } 1931: 1932: if (new_start == 0) 1933: new_start = loop_start; 1934: 1935: /* Go through all the instructions in the loop, making 1936: all the register substitutions scheduled in REG_MAP. */ 1937: for (p = new_start; p != end; p = NEXT_INSN (p)) 1938: if (GET_CODE (p) == INSN || GET_CODE (p) == JUMP_INSN 1939: || GET_CODE (p) == CALL_INSN) 1940: { 1941: replace_regs (PATTERN (p), reg_map, nregs, 0); 1942: replace_regs (REG_NOTES (p), reg_map, nregs, 0); 1943: } 1944: } 1945: 1946: #if 0 1947: /* Scan X and replace the address of any MEM in it with ADDR. 1948: REG is the address that MEM should have before the replacement. */ 1949: 1950: static void 1951: replace_call_address (x, reg, addr) 1952: rtx x, reg, addr; 1953: { 1954: register enum rtx_code code; 1955: register int i; 1956: register char *fmt; 1957: 1958: if (x == 0) 1959: return; 1960: code = GET_CODE (x); 1961: switch (code) 1962: { 1963: case PC: 1964: case CC0: 1965: case CONST_INT: 1966: case CONST_DOUBLE: 1967: case CONST: 1968: case SYMBOL_REF: 1969: case LABEL_REF: 1970: case REG: 1971: return; 1972: 1973: case SET: 1974: /* Short cut for very common case. */ 1975: replace_call_address (XEXP (x, 1), reg, addr); 1976: return; 1977: 1978: case CALL: 1979: /* Short cut for very common case. */ 1980: replace_call_address (XEXP (x, 0), reg, addr); 1981: return; 1982: 1983: case MEM: 1984: /* If this MEM uses a reg other than the one we expected, 1985: something is wrong. */ 1986: if (XEXP (x, 0) != reg) 1987: abort (); 1988: XEXP (x, 0) = addr; 1989: return; 1990: } 1991: 1992: fmt = GET_RTX_FORMAT (code); 1993: for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) 1994: { 1995: if (fmt[i] == 'e') 1996: replace_call_address (XEXP (x, i), reg, addr); 1997: if (fmt[i] == 'E') 1998: { 1999: register int j; 2000: for (j = 0; j < XVECLEN (x, i); j++) 2001: replace_call_address (XVECEXP (x, i, j), reg, addr); 2002: } 2003: } 2004: } 2005: #endif 2006: 2007: /* Return the number of memory refs to addresses that vary 2008: in the rtx X. */ 2009: 2010: static int 2011: count_nonfixed_reads (x) 2012: rtx x; 2013: { 2014: register enum rtx_code code; 2015: register int i; 2016: register char *fmt; 2017: int value; 2018: 2019: if (x == 0) 2020: return 0; 2021: 2022: code = GET_CODE (x); 2023: switch (code) 2024: { 2025: case PC: 2026: case CC0: 2027: case CONST_INT: 2028: case CONST_DOUBLE: 2029: case CONST: 2030: case SYMBOL_REF: 2031: case LABEL_REF: 2032: case REG: 2033: return 0; 2034: 2035: case MEM: 2036: return ((invariant_p (XEXP (x, 0)) != 1) 2037: + count_nonfixed_reads (XEXP (x, 0))); 2038: } 2039: 2040: value = 0; 2041: fmt = GET_RTX_FORMAT (code); 2042: for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) 2043: { 2044: if (fmt[i] == 'e') 2045: value += count_nonfixed_reads (XEXP (x, i)); 2046: if (fmt[i] == 'E') 2047: { 2048: register int j; 2049: for (j = 0; j < XVECLEN (x, i); j++) 2050: value += count_nonfixed_reads (XVECEXP (x, i, j)); 2051: } 2052: } 2053: return value; 2054: } 2055: 2056: 2057: #if 0 2058: /* P is an instruction that sets a register to the result of a ZERO_EXTEND. 2059: Replace it with an instruction to load just the low bytes 2060: if the machine supports such an instruction, 2061: and insert above LOOP_START an instruction to clear the register. */ 2062: 2063: static void 2064: constant_high_bytes (p, loop_start) 2065: rtx p, loop_start; 2066: { 2067: register rtx new; 2068: register int insn_code_number; 2069: 2070: /* Try to change (SET (REG ...) (ZERO_EXTEND (..:B ...))) 2071: to (SET (STRICT_LOW_PART (SUBREG:B (REG...))) ...). */ 2072: 2073: new = gen_rtx (SET, VOIDmode, 2074: gen_rtx (STRICT_LOW_PART, VOIDmode, 2075: gen_rtx (SUBREG, GET_MODE (XEXP (SET_SRC (PATTERN (p)), 0)), 2076: SET_DEST (PATTERN (p)), 2077: 0)), 2078: XEXP (SET_SRC (PATTERN (p)), 0)); 2079: insn_code_number = recog (new, p); 2080: 2081: if (insn_code_number) 2082: { 2083: register int i; 2084: 2085: /* Clear destination register before the loop. */ 2086: emit_insn_before (gen_rtx (SET, VOIDmode, 2087: SET_DEST (PATTERN (p)), 2088: const0_rtx), 2089: loop_start); 2090: 2091: /* Inside the loop, just load the low part. */ 2092: PATTERN (p) = new; 2093: } 2094: } 2095: #endif 2096: 2097: /* Scan a loop setting the variables `unknown_address_altered', 1.1.1.3 root 2098: `num_mem_sets', `loop_continue', loops_enclosed', `loop_has_call', 2099: and `loop_has_volatile'. 1.1 root 2100: Also, fill in the array `loop_store_mems'. */ 2101: 2102: static void 2103: prescan_loop (start, end) 2104: rtx start, end; 2105: { 2106: register int level = 1; 2107: register rtx insn; 2108: 2109: unknown_address_altered = 0; 2110: loop_has_call = 0; 1.1.1.3 root 2111: loop_has_volatile = 0; 1.1 root 2112: loop_store_mems_idx = 0; 2113: 2114: num_mem_sets = 0; 2115: loops_enclosed = 1; 2116: loop_continue = 0; 2117: 2118: for (insn = NEXT_INSN (start); insn != NEXT_INSN (end); 2119: insn = NEXT_INSN (insn)) 2120: { 2121: if (GET_CODE (insn) == NOTE) 2122: { 2123: if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG) 2124: { 2125: ++level; 2126: /* Count number of loops contained in this one. */ 2127: loops_enclosed++; 2128: } 2129: else if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END) 2130: { 2131: --level; 2132: if (level == 0) 2133: { 2134: end = insn; 2135: break; 2136: } 2137: } 2138: else if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_CONT) 2139: { 2140: if (level == 1) 2141: loop_continue = insn; 2142: } 2143: } 2144: else if (GET_CODE (insn) == CALL_INSN) 2145: { 2146: unknown_address_altered = 1; 2147: loop_has_call = 1; 2148: } 2149: else 2150: { 2151: if (GET_CODE (insn) == INSN || GET_CODE (insn) == JUMP_INSN) 1.1.1.3 root 2152: { 2153: if (volatile_refs_p (PATTERN (insn))) 2154: loop_has_volatile = 1; 2155: 2156: note_stores (PATTERN (insn), note_addr_stored); 2157: } 1.1 root 2158: } 2159: } 2160: } 2161: 2162: /* Scan the function looking for loops. Record the start and end of each loop. 2163: Also mark as invalid loops any loops that contain a setjmp or are branched 2164: to from outside the loop. */ 2165: 2166: static void 2167: find_and_verify_loops (f) 2168: rtx f; 2169: { 2170: rtx insn; 2171: int current_loop = -1; 2172: int next_loop = -1; 2173: int loop; 2174: 2175: /* If there are jumps to undefined labels, 2176: treat them as jumps out of any/all loops. 2177: This also avoids writing past end of tables when there are no loops. */ 2178: uid_loop_num[0] = -1; 2179: 2180: /* Find boundaries of loops, mark which loops are contained within 2181: loops, and invalidate loops that have setjmp. */ 2182: 2183: for (insn = f; insn; insn = NEXT_INSN (insn)) 2184: { 2185: if (GET_CODE (insn) == NOTE) 2186: switch (NOTE_LINE_NUMBER (insn)) 2187: { 2188: case NOTE_INSN_LOOP_BEG: 2189: loop_number_loop_starts[++next_loop] = insn; 2190: loop_number_loop_ends[next_loop] = 0; 2191: loop_outer_loop[next_loop] = current_loop; 2192: loop_invalid[next_loop] = 0; 2193: loop_number_exit_labels[next_loop] = 0; 2194: current_loop = next_loop; 2195: break; 2196: 2197: case NOTE_INSN_SETJMP: 2198: /* In this case, we must invalidate our current loop and any 2199: enclosing loop. */ 2200: for (loop = current_loop; loop != -1; loop = loop_outer_loop[loop]) 2201: { 2202: loop_invalid[loop] = 1; 2203: if (loop_dump_stream) 2204: fprintf (loop_dump_stream, 2205: "\nLoop at %d ignored due to setjmp.\n", 2206: INSN_UID (loop_number_loop_starts[loop])); 2207: } 2208: break; 2209: 2210: case NOTE_INSN_LOOP_END: 2211: if (current_loop == -1) 2212: abort (); 2213: 2214: loop_number_loop_ends[current_loop] = insn; 2215: current_loop = loop_outer_loop[current_loop]; 2216: break; 2217: 2218: } 2219: 2220: /* Note that this will mark the NOTE_INSN_LOOP_END note as being in the 2221: enclosing loop, but this doesn't matter. */ 2222: uid_loop_num[INSN_UID (insn)] = current_loop; 2223: } 2224: 2225: /* Now scan all JUMP_INSN's in the function. If any branches into a loop 2226: that it is not contained within, that loop is marked invalid. 2227: 2228: Also look for blocks of code ending in an unconditional branch that 2229: exits the loop. If such a block is surrounded by a conditional 2230: branch around the block, move the block elsewhere (see below) and 2231: invert the jump to point to the code block. This may eliminate a 2232: label in our loop and will simplify processing by both us and a 2233: possible second cse pass. */ 2234: 2235: for (insn = f; insn; insn = NEXT_INSN (insn)) 2236: if (GET_CODE (insn) == JUMP_INSN) 2237: { 2238: int this_loop_num = uid_loop_num[INSN_UID (insn)]; 2239: 2240: mark_loop_jump (PATTERN (insn), this_loop_num); 2241: 2242: /* See if this is an unconditional branch outside the loop. */ 2243: if (this_loop_num != -1 2244: && (GET_CODE (PATTERN (insn)) == RETURN 2245: || (simplejump_p (insn) 2246: && (uid_loop_num[INSN_UID (JUMP_LABEL (insn))] 1.1.1.4 ! root 2247: != this_loop_num))) ! 2248: && get_max_uid () < max_uid_for_loop) 1.1 root 2249: { 2250: rtx p; 2251: rtx our_next = next_real_insn (insn); 2252: 2253: /* Go backwards until we reach the start of the loop, a label, 2254: or a JUMP_INSN. */ 2255: for (p = PREV_INSN (insn); 2256: GET_CODE (p) != CODE_LABEL 2257: && ! (GET_CODE (p) == NOTE 2258: && NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_BEG) 2259: && GET_CODE (p) != JUMP_INSN; 2260: p = PREV_INSN (p)) 2261: ; 2262: 2263: /* If we stopped on a JUMP_INSN to the next insn after INSN, 2264: we have a block of code to try to move. 2265: 2266: We look backward and then forward from the target of INSN 2267: to find a BARRIER at the same loop depth as the target. 2268: If we find such a BARRIER, we make a new label for the start 2269: of the block, invert the jump in P and point it to that label, 2270: and move the block of code to the spot we found. */ 2271: 2272: if (GET_CODE (p) == JUMP_INSN 1.1.1.4 ! root 2273: && JUMP_LABEL (p) != 0 ! 2274: /* Just ignore jumps to labels that were never emitted. ! 2275: These always indicate compilation errors. */ ! 2276: && INSN_UID (JUMP_LABEL (p)) != 0 ! 2277: && condjump_p (p) ! 2278: && ! simplejump_p (p) ! 2279: && next_real_insn (JUMP_LABEL (p)) == our_next) 1.1 root 2280: { 2281: rtx target 2282: = JUMP_LABEL (insn) ? JUMP_LABEL (insn) : get_last_insn (); 2283: int target_loop_num = uid_loop_num[INSN_UID (target)]; 2284: rtx loc; 2285: 2286: for (loc = target; loc; loc = PREV_INSN (loc)) 2287: if (GET_CODE (loc) == BARRIER 2288: && uid_loop_num[INSN_UID (loc)] == target_loop_num) 2289: break; 2290: 2291: if (loc == 0) 2292: for (loc = target; loc; loc = NEXT_INSN (loc)) 2293: if (GET_CODE (loc) == BARRIER 2294: && uid_loop_num[INSN_UID (loc)] == target_loop_num) 2295: break; 2296: 2297: if (loc) 2298: { 2299: rtx cond_label = JUMP_LABEL (p); 2300: rtx new_label = get_label_after (p); 2301: 2302: /* Ensure our label doesn't go away. */ 2303: LABEL_NUSES (cond_label)++; 2304: 2305: /* Verify that uid_loop_num is large enough and that 2306: we can invert P. */ 1.1.1.4 ! root 2307: if (invert_jump (p, new_label)) 1.1 root 2308: { 2309: rtx q, r; 2310: 2311: /* Include the BARRIER after INSN and copy the 2312: block after LOC. */ 1.1.1.3 root 2313: new_label = squeeze_notes (new_label, NEXT_INSN (insn)); 1.1 root 2314: reorder_insns (new_label, NEXT_INSN (insn), loc); 2315: 2316: /* All those insns are now in TARGET_LOOP_NUM. */ 2317: for (q = new_label; q != NEXT_INSN (NEXT_INSN (insn)); 2318: q = NEXT_INSN (q)) 2319: uid_loop_num[INSN_UID (q)] = target_loop_num; 2320: 2321: /* The label jumped to by INSN is no longer a loop exit. 2322: Unless INSN does not have a label (e.g., it is a 2323: RETURN insn), search loop_number_exit_labels to find 2324: its label_ref, and remove it. Also turn off 2325: LABEL_OUTSIDE_LOOP_P bit. */ 2326: if (JUMP_LABEL (insn)) 2327: { 2328: for (q = 0, 2329: r = loop_number_exit_labels[this_loop_num]; 2330: r; q = r, r = LABEL_NEXTREF (r)) 2331: if (XEXP (r, 0) == JUMP_LABEL (insn)) 2332: { 2333: LABEL_OUTSIDE_LOOP_P (r) = 0; 2334: if (q) 2335: LABEL_NEXTREF (q) = LABEL_NEXTREF (r); 2336: else 2337: loop_number_exit_labels[this_loop_num] 2338: = LABEL_NEXTREF (r); 2339: break; 2340: } 2341: 2342: /* If we didn't find it, then something is wrong. */ 2343: if (! r) 2344: abort (); 2345: } 2346: 2347: /* P is now a jump outside the loop, so it must be put 2348: in loop_number_exit_labels, and marked as such. 2349: The easiest way to do this is to just call 2350: mark_loop_jump again for P. */ 2351: mark_loop_jump (PATTERN (p), this_loop_num); 2352: 2353: /* If INSN now jumps to the insn after it, 2354: delete INSN. */ 2355: if (JUMP_LABEL (insn) != 0 2356: && (next_real_insn (JUMP_LABEL (insn)) 2357: == next_real_insn (insn))) 2358: delete_insn (insn); 2359: } 2360: 2361: /* Continue the loop after where the conditional 2362: branch used to jump, since the only branch insn 2363: in the block (if it still remains) is an inter-loop 2364: branch and hence needs no processing. */ 2365: insn = NEXT_INSN (cond_label); 2366: 2367: if (--LABEL_NUSES (cond_label) == 0) 2368: delete_insn (cond_label); 2369: } 2370: } 2371: } 2372: } 2373: } 2374: 2375: /* If any label in X jumps to a loop different from LOOP_NUM and any of the 2376: loops it is contained in, mark the target loop invalid. 2377: 2378: For speed, we assume that X is part of a pattern of a JUMP_INSN. */ 2379: 2380: static void 2381: mark_loop_jump (x, loop_num) 2382: rtx x; 2383: int loop_num; 2384: { 2385: int dest_loop; 2386: int outer_loop; 2387: int i; 2388: 2389: switch (GET_CODE (x)) 2390: { 2391: case PC: 2392: case USE: 2393: case CLOBBER: 2394: case REG: 2395: case MEM: 2396: case CONST_INT: 2397: case CONST_DOUBLE: 2398: case RETURN: 2399: return; 2400: 2401: case CONST: 2402: /* There could be a label reference in here. */ 2403: mark_loop_jump (XEXP (x, 0), loop_num); 2404: return; 2405: 2406: case PLUS: 2407: case MINUS: 2408: case MULT: 2409: case LSHIFT: 2410: mark_loop_jump (XEXP (x, 0), loop_num); 2411: mark_loop_jump (XEXP (x, 1), loop_num); 2412: return; 2413: 2414: case SIGN_EXTEND: 2415: case ZERO_EXTEND: 2416: mark_loop_jump (XEXP (x, 0), loop_num); 2417: return; 2418: 2419: case LABEL_REF: 2420: dest_loop = uid_loop_num[INSN_UID (XEXP (x, 0))]; 2421: 2422: /* Link together all labels that branch outside the loop. This 2423: is used by final_[bg]iv_value and the loop unrolling code. Also 2424: mark this LABEL_REF so we know that this branch should predict 2425: false. */ 2426: 2427: if (dest_loop != loop_num && loop_num != -1) 2428: { 2429: LABEL_OUTSIDE_LOOP_P (x) = 1; 2430: LABEL_NEXTREF (x) = loop_number_exit_labels[loop_num]; 2431: loop_number_exit_labels[loop_num] = x; 2432: } 2433: 2434: /* If this is inside a loop, but not in the current loop or one enclosed 2435: by it, it invalidates at least one loop. */ 2436: 2437: if (dest_loop == -1) 2438: return; 2439: 2440: /* We must invalidate every nested loop containing the target of this 2441: label, except those that also contain the jump insn. */ 2442: 2443: for (; dest_loop != -1; dest_loop = loop_outer_loop[dest_loop]) 2444: { 2445: /* Stop when we reach a loop that also contains the jump insn. */ 2446: for (outer_loop = loop_num; outer_loop != -1; 2447: outer_loop = loop_outer_loop[outer_loop]) 2448: if (dest_loop == outer_loop) 2449: return; 2450: 2451: /* If we get here, we know we need to invalidate a loop. */ 2452: if (loop_dump_stream && ! loop_invalid[dest_loop]) 2453: fprintf (loop_dump_stream, 2454: "\nLoop at %d ignored due to multiple entry points.\n", 2455: INSN_UID (loop_number_loop_starts[dest_loop])); 2456: 2457: loop_invalid[dest_loop] = 1; 2458: } 2459: return; 2460: 2461: case SET: 2462: /* If this is not setting pc, ignore. */ 2463: if (SET_DEST (x) == pc_rtx) 2464: mark_loop_jump (SET_SRC (x), loop_num); 2465: return; 2466: 2467: case IF_THEN_ELSE: 2468: mark_loop_jump (XEXP (x, 1), loop_num); 2469: mark_loop_jump (XEXP (x, 2), loop_num); 2470: return; 2471: 2472: case PARALLEL: 2473: case ADDR_VEC: 2474: for (i = 0; i < XVECLEN (x, 0); i++) 2475: mark_loop_jump (XVECEXP (x, 0, i), loop_num); 2476: return; 2477: 2478: case ADDR_DIFF_VEC: 2479: for (i = 0; i < XVECLEN (x, 1); i++) 2480: mark_loop_jump (XVECEXP (x, 1, i), loop_num); 2481: return; 2482: 2483: default: 2484: /* Nothing else should occur in a JUMP_INSN. */ 2485: abort (); 2486: } 2487: } 2488: 2489: /* Return nonzero if there is a label in the range from 2490: insn INSN to and including the insn whose luid is END 2491: INSN must have an assigned luid (i.e., it must not have 2492: been previously created by loop.c). */ 2493: 2494: static int 2495: labels_in_range_p (insn, end) 2496: rtx insn; 2497: int end; 2498: { 2499: while (insn && INSN_LUID (insn) <= end) 2500: { 2501: if (GET_CODE (insn) == CODE_LABEL) 2502: return 1; 2503: insn = NEXT_INSN (insn); 2504: } 2505: 2506: return 0; 2507: } 2508: 2509: /* Record that a memory reference X is being set. */ 2510: 2511: static void 2512: note_addr_stored (x) 2513: rtx x; 2514: { 2515: register int i; 2516: 2517: if (x == 0 || GET_CODE (x) != MEM) 2518: return; 2519: 2520: /* Count number of memory writes. 2521: This affects heuristics in strength_reduce. */ 2522: num_mem_sets++; 2523: 2524: if (unknown_address_altered) 2525: return; 2526: 2527: for (i = 0; i < loop_store_mems_idx; i++) 2528: if (rtx_equal_p (XEXP (loop_store_mems[i], 0), XEXP (x, 0)) 2529: && MEM_IN_STRUCT_P (x) == MEM_IN_STRUCT_P (loop_store_mems[i])) 2530: { 2531: /* We are storing at the same address as previously noted. Save the 2532: wider reference, treating BLKmode as wider. */ 2533: if (GET_MODE (x) == BLKmode 2534: || (GET_MODE_SIZE (GET_MODE (x)) 2535: > GET_MODE_SIZE (GET_MODE (loop_store_mems[i])))) 2536: loop_store_mems[i] = x; 2537: break; 2538: } 2539: 2540: if (i == NUM_STORES) 2541: unknown_address_altered = 1; 2542: 2543: else if (i == loop_store_mems_idx) 2544: loop_store_mems[loop_store_mems_idx++] = x; 2545: } 2546: 2547: /* Return nonzero if the rtx X is invariant over the current loop. 2548: 2549: The value is 2 if we refer to something only conditionally invariant. 2550: 2551: If `unknown_address_altered' is nonzero, no memory ref is invariant. 2552: Otherwise, a memory ref is invariant if it does not conflict with 2553: anything stored in `loop_store_mems'. */ 2554: 2555: int 2556: invariant_p (x) 2557: register rtx x; 2558: { 2559: register int i; 2560: register enum rtx_code code; 2561: register char *fmt; 2562: int conditional = 0; 2563: 2564: if (x == 0) 2565: return 1; 2566: code = GET_CODE (x); 2567: switch (code) 2568: { 2569: case CONST_INT: 2570: case CONST_DOUBLE: 2571: case SYMBOL_REF: 2572: case CONST: 2573: return 1; 2574: 2575: case LABEL_REF: 2576: /* A LABEL_REF is normally invariant, however, if we are unrolling 2577: loops, and this label is inside the loop, then it isn't invariant. 2578: This is because each unrolled copy of the loop body will have 2579: a copy of this label. If this was invariant, then an insn loading 2580: the address of this label into a register might get moved outside 2581: the loop, and then each loop body would end up using the same label. 2582: 2583: We don't know the loop bounds here though, so just fail for all 2584: labels. */ 2585: if (flag_unroll_loops) 2586: return 0; 2587: else 2588: return 1; 2589: 2590: case PC: 2591: case CC0: 2592: case UNSPEC_VOLATILE: 2593: return 0; 2594: 2595: case REG: 2596: /* We used to check RTX_UNCHANGING_P (x) here, but that is invalid 2597: since the reg might be set by initialization within the loop. */ 2598: if (x == frame_pointer_rtx || x == arg_pointer_rtx) 2599: return 1; 2600: if (loop_has_call 2601: && REGNO (x) < FIRST_PSEUDO_REGISTER && call_used_regs[REGNO (x)]) 2602: return 0; 2603: if (n_times_set[REGNO (x)] < 0) 2604: return 2; 2605: return n_times_set[REGNO (x)] == 0; 2606: 2607: case MEM: 2608: /* Read-only items (such as constants in a constant pool) are 2609: invariant if their address is. */ 2610: if (RTX_UNCHANGING_P (x)) 2611: break; 2612: 2613: /* If we filled the table (or had a subroutine call), any location 2614: in memory could have been clobbered. */ 2615: if (unknown_address_altered 2616: /* Don't mess with volatile memory references. */ 2617: || MEM_VOLATILE_P (x)) 2618: return 0; 2619: 2620: /* See if there is any dependence between a store and this load. */ 2621: for (i = loop_store_mems_idx - 1; i >= 0; i--) 2622: if (true_dependence (loop_store_mems[i], x)) 2623: return 0; 2624: 2625: /* It's not invalidated by a store in memory 2626: but we must still verify the address is invariant. */ 2627: break; 2628: 2629: case ASM_OPERANDS: 2630: /* Don't mess with insns declared volatile. */ 2631: if (MEM_VOLATILE_P (x)) 2632: return 0; 2633: } 2634: 2635: fmt = GET_RTX_FORMAT (code); 2636: for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) 2637: { 2638: if (fmt[i] == 'e') 2639: { 2640: int tem = invariant_p (XEXP (x, i)); 2641: if (tem == 0) 2642: return 0; 2643: if (tem == 2) 2644: conditional = 1; 2645: } 2646: else if (fmt[i] == 'E') 2647: { 2648: register int j; 2649: for (j = 0; j < XVECLEN (x, i); j++) 2650: { 2651: int tem = invariant_p (XVECEXP (x, i, j)); 2652: if (tem == 0) 2653: return 0; 2654: if (tem == 2) 2655: conditional = 1; 2656: } 2657: 2658: } 2659: } 2660: 2661: return 1 + conditional; 2662: } 2663: 2664: /* Return 1 if OTHER (a mem ref) overlaps the area of memory 2665: which is SIZE bytes starting at BASE. */ 2666: 2667: int 2668: addr_overlap_p (other, base, size) 2669: rtx other; 2670: rtx base; 1.1.1.4 ! root 2671: HOST_WIDE_INT size; 1.1 root 2672: { 1.1.1.4 ! root 2673: HOST_WIDE_INT start = 0, end; 1.1 root 2674: 2675: if (GET_CODE (base) == CONST) 2676: base = XEXP (base, 0); 2677: if (GET_CODE (base) == PLUS 2678: && GET_CODE (XEXP (base, 1)) == CONST_INT) 2679: { 2680: start = INTVAL (XEXP (base, 1)); 2681: base = XEXP (base, 0); 2682: } 2683: 2684: end = start + size; 2685: return refers_to_mem_p (other, base, start, end); 2686: } 2687: 2688: /* Return nonzero if all the insns in the loop that set REG 2689: are INSN and the immediately following insns, 2690: and if each of those insns sets REG in an invariant way 2691: (not counting uses of REG in them). 2692: 2693: The value is 2 if some of these insns are only conditionally invariant. 2694: 2695: We assume that INSN itself is the first set of REG 2696: and that its source is invariant. */ 2697: 2698: static int 2699: consec_sets_invariant_p (reg, n_sets, insn) 2700: int n_sets; 2701: rtx reg, insn; 2702: { 2703: register rtx p = insn; 2704: register int regno = REGNO (reg); 2705: rtx temp; 2706: /* Number of sets we have to insist on finding after INSN. */ 2707: int count = n_sets - 1; 2708: int old = n_times_set[regno]; 2709: int value = 0; 2710: int this; 2711: 2712: /* If N_SETS hit the limit, we can't rely on its value. */ 2713: if (n_sets == 127) 2714: return 0; 2715: 2716: n_times_set[regno] = 0; 2717: 2718: while (count > 0) 2719: { 2720: register enum rtx_code code; 2721: rtx set; 2722: 2723: p = NEXT_INSN (p); 2724: code = GET_CODE (p); 2725: 2726: /* If library call, skip to end of of it. */ 1.1.1.4 ! root 2727: if (code == INSN && (temp = find_reg_note (p, REG_LIBCALL, NULL_RTX))) 1.1 root 2728: p = XEXP (temp, 0); 2729: 2730: this = 0; 2731: if (code == INSN 2732: && (set = single_set (p)) 2733: && GET_CODE (SET_DEST (set)) == REG 2734: && REGNO (SET_DEST (set)) == regno) 2735: { 2736: this = invariant_p (SET_SRC (set)); 2737: if (this != 0) 2738: value |= this; 1.1.1.4 ! root 2739: else if (temp = find_reg_note (p, REG_EQUAL, NULL_RTX)) 1.1 root 2740: { 2741: this = invariant_p (XEXP (temp, 0)); 2742: if (this != 0) 2743: value |= this; 2744: } 2745: } 2746: if (this != 0) 2747: count--; 2748: else if (code != NOTE) 2749: { 2750: n_times_set[regno] = old; 2751: return 0; 2752: } 2753: } 2754: 2755: n_times_set[regno] = old; 2756: /* If invariant_p ever returned 2, we return 2. */ 2757: return 1 + (value & 2); 2758: } 2759: 2760: #if 0 2761: /* I don't think this condition is sufficient to allow INSN 2762: to be moved, so we no longer test it. */ 2763: 2764: /* Return 1 if all insns in the basic block of INSN and following INSN 2765: that set REG are invariant according to TABLE. */ 2766: 2767: static int 2768: all_sets_invariant_p (reg, insn, table) 2769: rtx reg, insn; 2770: short *table; 2771: { 2772: register rtx p = insn; 2773: register int regno = REGNO (reg); 2774: 2775: while (1) 2776: { 2777: register enum rtx_code code; 2778: p = NEXT_INSN (p); 2779: code = GET_CODE (p); 2780: if (code == CODE_LABEL || code == JUMP_INSN) 2781: return 1; 2782: if (code == INSN && GET_CODE (PATTERN (p)) == SET 2783: && GET_CODE (SET_DEST (PATTERN (p))) == REG 2784: && REGNO (SET_DEST (PATTERN (p))) == regno) 2785: { 2786: if (!invariant_p (SET_SRC (PATTERN (p)), table)) 2787: return 0; 2788: } 2789: } 2790: } 2791: #endif /* 0 */ 2792: 2793: /* Look at all uses (not sets) of registers in X. For each, if it is 2794: the single use, set USAGE[REGNO] to INSN; if there was a previous use in 2795: a different insn, set USAGE[REGNO] to const0_rtx. */ 2796: 2797: static void 2798: find_single_use_in_loop (insn, x, usage) 2799: rtx insn; 2800: rtx x; 2801: rtx *usage; 2802: { 2803: enum rtx_code code = GET_CODE (x); 2804: char *fmt = GET_RTX_FORMAT (code); 2805: int i, j; 2806: 2807: if (code == REG) 2808: usage[REGNO (x)] 2809: = (usage[REGNO (x)] != 0 && usage[REGNO (x)] != insn) 2810: ? const0_rtx : insn; 2811: 2812: else if (code == SET) 2813: { 2814: /* Don't count SET_DEST if it is a REG; otherwise count things 2815: in SET_DEST because if a register is partially modified, it won't 2816: show up as a potential movable so we don't care how USAGE is set 2817: for it. */ 2818: if (GET_CODE (SET_DEST (x)) != REG) 2819: find_single_use_in_loop (insn, SET_DEST (x), usage); 2820: find_single_use_in_loop (insn, SET_SRC (x), usage); 2821: } 2822: else 2823: for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) 2824: { 2825: if (fmt[i] == 'e' && XEXP (x, i) != 0) 2826: find_single_use_in_loop (insn, XEXP (x, i), usage); 2827: else if (fmt[i] == 'E') 2828: for (j = XVECLEN (x, i) - 1; j >= 0; j--) 2829: find_single_use_in_loop (insn, XVECEXP (x, i, j), usage); 2830: } 2831: } 2832: 2833: /* Increment N_TIMES_SET at the index of each register 2834: that is modified by an insn between FROM and TO. 2835: If the value of an element of N_TIMES_SET becomes 127 or more, 2836: stop incrementing it, to avoid overflow. 2837: 2838: Store in SINGLE_USAGE[I] the single insn in which register I is 2839: used, if it is only used once. Otherwise, it is set to 0 (for no 2840: uses) or const0_rtx for more than one use. This parameter may be zero, 2841: in which case this processing is not done. 2842: 2843: Store in *COUNT_PTR the number of actual instruction 2844: in the loop. We use this to decide what is worth moving out. */ 2845: 2846: /* last_set[n] is nonzero iff reg n has been set in the current basic block. 2847: In that case, it is the insn that last set reg n. */ 2848: 2849: static void 2850: count_loop_regs_set (from, to, may_not_move, single_usage, count_ptr, nregs) 2851: register rtx from, to; 2852: char *may_not_move; 2853: rtx *single_usage; 2854: int *count_ptr; 2855: int nregs; 2856: { 2857: register rtx *last_set = (rtx *) alloca (nregs * sizeof (rtx)); 2858: register rtx insn; 2859: register int count = 0; 2860: register rtx dest; 2861: 2862: bzero (last_set, nregs * sizeof (rtx)); 2863: for (insn = from; insn != to; insn = NEXT_INSN (insn)) 2864: { 2865: if (GET_RTX_CLASS (GET_CODE (insn)) == 'i') 2866: { 2867: ++count; 2868: 2869: /* If requested, record registers that have exactly one use. */ 2870: if (single_usage) 2871: { 2872: find_single_use_in_loop (insn, PATTERN (insn), single_usage); 2873: 2874: /* Include uses in REG_EQUAL notes. */ 2875: if (REG_NOTES (insn)) 2876: find_single_use_in_loop (insn, REG_NOTES (insn), single_usage); 2877: } 2878: 2879: if (GET_CODE (PATTERN (insn)) == CLOBBER 2880: && GET_CODE (XEXP (PATTERN (insn), 0)) == REG) 2881: /* Don't move a reg that has an explicit clobber. 2882: We might do so sometimes, but it's not worth the pain. */ 2883: may_not_move[REGNO (XEXP (PATTERN (insn), 0))] = 1; 2884: 2885: if (GET_CODE (PATTERN (insn)) == SET 2886: || GET_CODE (PATTERN (insn)) == CLOBBER) 2887: { 2888: dest = SET_DEST (PATTERN (insn)); 2889: while (GET_CODE (dest) == SUBREG 2890: || GET_CODE (dest) == ZERO_EXTRACT 2891: || GET_CODE (dest) == SIGN_EXTRACT 2892: || GET_CODE (dest) == STRICT_LOW_PART) 2893: dest = XEXP (dest, 0); 2894: if (GET_CODE (dest) == REG) 2895: { 2896: register int regno = REGNO (dest); 2897: /* If this is the first setting of this reg 2898: in current basic block, and it was set before, 2899: it must be set in two basic blocks, so it cannot 2900: be moved out of the loop. */ 2901: if (n_times_set[regno] > 0 && last_set[regno] == 0) 2902: may_not_move[regno] = 1; 2903: /* If this is not first setting in current basic block, 2904: see if reg was used in between previous one and this. 2905: If so, neither one can be moved. */ 2906: if (last_set[regno] != 0 2907: && reg_used_between_p (dest, last_set[regno], insn)) 2908: may_not_move[regno] = 1; 2909: if (n_times_set[regno] < 127) 2910: ++n_times_set[regno]; 2911: last_set[regno] = insn; 2912: } 2913: } 2914: else if (GET_CODE (PATTERN (insn)) == PARALLEL) 2915: { 2916: register int i; 2917: for (i = XVECLEN (PATTERN (insn), 0) - 1; i >= 0; i--) 2918: { 2919: register rtx x = XVECEXP (PATTERN (insn), 0, i); 2920: if (GET_CODE (x) == CLOBBER && GET_CODE (XEXP (x, 0)) == REG) 2921: /* Don't move a reg that has an explicit clobber. 2922: It's not worth the pain to try to do it correctly. */ 2923: may_not_move[REGNO (XEXP (x, 0))] = 1; 2924: 2925: if (GET_CODE (x) == SET || GET_CODE (x) == CLOBBER) 2926: { 2927: dest = SET_DEST (x); 2928: while (GET_CODE (dest) == SUBREG 2929: || GET_CODE (dest) == ZERO_EXTRACT 2930: || GET_CODE (dest) == SIGN_EXTRACT 2931: || GET_CODE (dest) == STRICT_LOW_PART) 2932: dest = XEXP (dest, 0); 2933: if (GET_CODE (dest) == REG) 2934: { 2935: register int regno = REGNO (dest); 2936: if (n_times_set[regno] > 0 && last_set[regno] == 0) 2937: may_not_move[regno] = 1; 2938: if (last_set[regno] != 0 2939: && reg_used_between_p (dest, last_set[regno], insn)) 2940: may_not_move[regno] = 1; 2941: if (n_times_set[regno] < 127) 2942: ++n_times_set[regno]; 2943: last_set[regno] = insn; 2944: } 2945: } 2946: } 2947: } 2948: } 2949: if (GET_CODE (insn) == CODE_LABEL || GET_CODE (insn) == JUMP_INSN) 2950: bzero (last_set, nregs * sizeof (rtx)); 2951: } 2952: *count_ptr = count; 2953: } 2954: 2955: /* Given a loop that is bounded by LOOP_START and LOOP_END 2956: and that is entered at SCAN_START, 2957: return 1 if the register set in SET contained in insn INSN is used by 2958: any insn that precedes INSN in cyclic order starting 2959: from the loop entry point. 2960: 2961: We don't want to use INSN_LUID here because if we restrict INSN to those 2962: that have a valid INSN_LUID, it means we cannot move an invariant out 2963: from an inner loop past two loops. */ 2964: 2965: static int 2966: loop_reg_used_before_p (set, insn, loop_start, scan_start, loop_end) 2967: rtx set, insn, loop_start, scan_start, loop_end; 2968: { 2969: rtx reg = SET_DEST (set); 2970: rtx p; 2971: 2972: /* Scan forward checking for register usage. If we hit INSN, we 2973: are done. Otherwise, if we hit LOOP_END, wrap around to LOOP_START. */ 2974: for (p = scan_start; p != insn; p = NEXT_INSN (p)) 2975: { 2976: if (GET_RTX_CLASS (GET_CODE (p)) == 'i' 2977: && reg_overlap_mentioned_p (reg, PATTERN (p))) 2978: return 1; 2979: 2980: if (p == loop_end) 2981: p = loop_start; 2982: } 2983: 2984: return 0; 2985: } 2986: 2987: /* A "basic induction variable" or biv is a pseudo reg that is set 2988: (within this loop) only by incrementing or decrementing it. */ 2989: /* A "general induction variable" or giv is a pseudo reg whose 2990: value is a linear function of a biv. */ 2991: 2992: /* Bivs are recognized by `basic_induction_var'; 2993: Givs by `general_induct_var'. */ 2994: 2995: /* Indexed by register number, indicates whether or not register is an 2996: induction variable, and if so what type. */ 2997: 2998: enum iv_mode *reg_iv_type; 2999: 3000: /* Indexed by register number, contains pointer to `struct induction' 3001: if register is an induction variable. This holds general info for 3002: all induction variables. */ 3003: 3004: struct induction **reg_iv_info; 3005: 3006: /* Indexed by register number, contains pointer to `struct iv_class' 3007: if register is a basic induction variable. This holds info describing 3008: the class (a related group) of induction variables that the biv belongs 3009: to. */ 3010: 3011: struct iv_class **reg_biv_class; 3012: 3013: /* The head of a list which links together (via the next field) 3014: every iv class for the current loop. */ 3015: 3016: struct iv_class *loop_iv_list; 3017: 3018: /* Communication with routines called via `note_stores'. */ 3019: 3020: static rtx note_insn; 3021: 3022: /* Dummy register to have non-zero DEST_REG for DEST_ADDR type givs. */ 3023: 3024: static rtx addr_placeholder; 3025: 3026: /* ??? Unfinished optimizations, and possible future optimizations, 3027: for the strength reduction code. */ 3028: 3029: /* ??? There is one more optimization you might be interested in doing: to 3030: allocate pseudo registers for frequently-accessed memory locations. 3031: If the same memory location is referenced each time around, it might 3032: be possible to copy it into a register before and out after. 3033: This is especially useful when the memory location is a variable which 3034: is in a stack slot because somewhere its address is taken. If the 3035: loop doesn't contain a function call and the variable isn't volatile, 3036: it is safe to keep the value in a register for the duration of the 3037: loop. One tricky thing is that the copying of the value back from the 3038: register has to be done on all exits from the loop. You need to check that 3039: all the exits from the loop go to the same place. */ 3040: 3041: /* ??? The interaction of biv elimination, and recognition of 'constant' 3042: bivs, may cause problems. */ 3043: 3044: /* ??? Add heuristics so that DEST_ADDR strength reduction does not cause 3045: performance problems. 3046: 3047: Perhaps don't eliminate things that can be combined with an addressing 3048: mode. Find all givs that have the same biv, mult_val, and add_val; 3049: then for each giv, check to see if its only use dies in a following 3050: memory address. If so, generate a new memory address and check to see 3051: if it is valid. If it is valid, then store the modified memory address, 3052: otherwise, mark the giv as not done so that it will get its own iv. */ 3053: 3054: /* ??? Could try to optimize branches when it is known that a biv is always 3055: positive. */ 3056: 3057: /* ??? When replace a biv in a compare insn, we should replace with closest 3058: giv so that an optimized branch can still be recognized by the combiner, 3059: e.g. the VAX acb insn. */ 3060: 3061: /* ??? Many of the checks involving uid_luid could be simplified if regscan 3062: was rerun in loop_optimize whenever a register was added or moved. 3063: Also, some of the optimizations could be a little less conservative. */ 3064: 3065: /* Perform strength reduction and induction variable elimination. */ 3066: 3067: /* Pseudo registers created during this function will be beyond the last 3068: valid index in several tables including n_times_set and regno_last_uid. 3069: This does not cause a problem here, because the added registers cannot be 3070: givs outside of their loop, and hence will never be reconsidered. 3071: But scan_loop must check regnos to make sure they are in bounds. */ 3072: 3073: static void 3074: strength_reduce (scan_start, end, loop_top, insn_count, 3075: loop_start, loop_end) 3076: rtx scan_start; 3077: rtx end; 3078: rtx loop_top; 3079: int insn_count; 3080: rtx loop_start; 3081: rtx loop_end; 3082: { 3083: rtx p; 3084: rtx set; 3085: rtx inc_val; 3086: rtx mult_val; 3087: rtx dest_reg; 3088: /* This is 1 if current insn is not executed at least once for every loop 3089: iteration. */ 3090: int not_every_iteration = 0; 1.1.1.3 root 3091: /* This is 1 if current insn may be executed more than once for every 3092: loop iteration. */ 3093: int maybe_multiple = 0; 1.1 root 3094: /* Temporary list pointers for traversing loop_iv_list. */ 3095: struct iv_class *bl, **backbl; 3096: /* Ratio of extra register life span we can justify 3097: for saving an instruction. More if loop doesn't call subroutines 3098: since in that case saving an insn makes more difference 3099: and more registers are available. */ 3100: /* ??? could set this to last value of threshold in move_movables */ 3101: int threshold = (loop_has_call ? 1 : 2) * (3 + n_non_fixed_regs); 3102: /* Map of pseudo-register replacements. */ 3103: rtx *reg_map; 3104: int call_seen; 3105: rtx test; 3106: rtx end_insert_before; 3107: 3108: reg_iv_type = (enum iv_mode *) alloca (max_reg_before_loop 3109: * sizeof (enum iv_mode *)); 3110: bzero ((char *) reg_iv_type, max_reg_before_loop * sizeof (enum iv_mode *)); 3111: reg_iv_info = (struct induction **) 3112: alloca (max_reg_before_loop * sizeof (struct induction *)); 3113: bzero ((char *) reg_iv_info, (max_reg_before_loop 3114: * sizeof (struct induction *))); 3115: reg_biv_class = (struct iv_class **) 3116: alloca (max_reg_before_loop * sizeof (struct iv_class *)); 3117: bzero ((char *) reg_biv_class, (max_reg_before_loop 3118: * sizeof (struct iv_class *))); 3119: 3120: loop_iv_list = 0; 3121: addr_placeholder = gen_reg_rtx (Pmode); 3122: 3123: /* Save insn immediately after the loop_end. Insns inserted after loop_end 3124: must be put before this insn, so that they will appear in the right 3125: order (i.e. loop order). */ 3126: 3127: end_insert_before = NEXT_INSN (loop_end); 3128: 3129: /* Scan through loop to find all possible bivs. */ 3130: 3131: p = scan_start; 3132: while (1) 3133: { 3134: p = NEXT_INSN (p); 3135: /* At end of a straight-in loop, we are done. 3136: At end of a loop entered at the bottom, scan the top. */ 3137: if (p == scan_start) 3138: break; 3139: if (p == end) 3140: { 3141: if (loop_top != 0) 3142: p = NEXT_INSN (loop_top); 3143: else 3144: break; 3145: if (p == scan_start) 3146: break; 3147: } 3148: 3149: if (GET_CODE (p) == INSN 3150: && (set = single_set (p)) 3151: && GET_CODE (SET_DEST (set)) == REG) 3152: { 3153: dest_reg = SET_DEST (set); 3154: if (REGNO (dest_reg) < max_reg_before_loop 3155: && REGNO (dest_reg) >= FIRST_PSEUDO_REGISTER 3156: && reg_iv_type[REGNO (dest_reg)] != NOT_BASIC_INDUCT) 3157: { 1.1.1.4 ! root 3158: if (basic_induction_var (SET_SRC (set), dest_reg, p, 1.1 root 3159: &inc_val, &mult_val)) 3160: { 3161: /* It is a possible basic induction variable. 3162: Create and initialize an induction structure for it. */ 3163: 3164: struct induction *v 3165: = (struct induction *) alloca (sizeof (struct induction)); 3166: 3167: record_biv (v, p, dest_reg, inc_val, mult_val, 1.1.1.3 root 3168: not_every_iteration, maybe_multiple); 1.1 root 3169: reg_iv_type[REGNO (dest_reg)] = BASIC_INDUCT; 3170: } 3171: else if (REGNO (dest_reg) < max_reg_before_loop) 3172: reg_iv_type[REGNO (dest_reg)] = NOT_BASIC_INDUCT; 3173: } 3174: } 3175: 1.1.1.3 root 3176: /* Past CODE_LABEL, we get to insns that may be executed multiple 3177: times. The only way we can be sure that they can't is if every 3178: every jump insn between here and the end of the loop either 3179: returns, exits the loop, or is a forward jump. */ 3180: 3181: if (GET_CODE (p) == CODE_LABEL) 3182: { 3183: rtx insn = p; 3184: 3185: maybe_multiple = 0; 3186: 3187: while (1) 3188: { 3189: insn = NEXT_INSN (insn); 3190: if (insn == scan_start) 3191: break; 3192: if (insn == end) 3193: { 3194: if (loop_top != 0) 3195: insn = NEXT_INSN (loop_top); 3196: else 3197: break; 3198: if (insn == scan_start) 3199: break; 3200: } 3201: 3202: if (GET_CODE (insn) == JUMP_INSN 3203: && GET_CODE (PATTERN (insn)) != RETURN 3204: && (! condjump_p (insn) 3205: || (JUMP_LABEL (insn) != 0 3206: && (INSN_UID (JUMP_LABEL (insn)) >= max_uid_for_loop 3207: || INSN_UID (insn) >= max_uid_for_loop 3208: || (INSN_LUID (JUMP_LABEL (insn)) 3209: < INSN_LUID (insn)))))) 3210: { 3211: maybe_multiple = 1; 3212: break; 3213: } 3214: } 3215: } 3216: 1.1 root 3217: /* Past a label or a jump, we get to insns for which we can't count 3218: on whether or how many times they will be executed during each 3219: iteration. */ 3220: /* This code appears in three places, once in scan_loop, and twice 3221: in strength_reduce. */ 3222: if ((GET_CODE (p) == CODE_LABEL || GET_CODE (p) == JUMP_INSN) 3223: /* If we enter the loop in the middle, and scan around to the 3224: beginning, don't set not_every_iteration for that. 3225: This can be any kind of jump, since we want to know if insns 3226: will be executed if the loop is executed. */ 3227: && ! (GET_CODE (p) == JUMP_INSN && JUMP_LABEL (p) == loop_top 3228: && ((NEXT_INSN (NEXT_INSN (p)) == loop_end && simplejump_p (p)) 3229: || (NEXT_INSN (p) == loop_end && condjump_p (p))))) 3230: not_every_iteration = 1; 3231: 3232: /* At the virtual top of a converted loop, insns are again known to 3233: be executed each iteration: logically, the loop begins here 3234: even though the exit code has been duplicated. */ 3235: 3236: else if (GET_CODE (p) == NOTE 3237: && NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_VTOP) 3238: not_every_iteration = 0; 3239: 3240: /* Unlike in the code motion pass where MAYBE_NEVER indicates that 3241: an insn may never be executed, NOT_EVERY_ITERATION indicates whether 3242: or not an insn is known to be executed each iteration of the 3243: loop, whether or not any iterations are known to occur. 3244: 3245: Therefore, if we have just passed a label and have no more labels 3246: between here and the test insn of the loop, we know these insns 3247: will be executed each iteration. This can also happen if we 3248: have just passed a jump, for example, when there are nested loops. */ 3249: 3250: if (not_every_iteration && GET_CODE (p) == CODE_LABEL 3251: && no_labels_between_p (p, loop_end)) 3252: not_every_iteration = 0; 3253: } 3254: 3255: /* Scan loop_iv_list to remove all regs that proved not to be bivs. 3256: Make a sanity check against n_times_set. */ 3257: for (backbl = &loop_iv_list, bl = *backbl; bl; bl = bl->next) 3258: { 3259: if (reg_iv_type[bl->regno] != BASIC_INDUCT 3260: /* Above happens if register modified by subreg, etc. */ 3261: /* Make sure it is not recognized as a basic induction var: */ 3262: || n_times_set[bl->regno] != bl->biv_count 3263: /* If never incremented, it is invariant that we decided not to 3264: move. So leave it alone. */ 3265: || ! bl->incremented) 3266: { 3267: if (loop_dump_stream) 3268: fprintf (loop_dump_stream, "Reg %d: biv discarded, %s\n", 3269: bl->regno, 3270: (reg_iv_type[bl->regno] != BASIC_INDUCT 3271: ? "not induction variable" 3272: : (! bl->incremented ? "never incremented" 3273: : "count error"))); 3274: 3275: reg_iv_type[bl->regno] = NOT_BASIC_INDUCT; 3276: *backbl = bl->next; 3277: } 3278: else 3279: { 3280: backbl = &bl->next; 3281: 3282: if (loop_dump_stream) 3283: fprintf (loop_dump_stream, "Reg %d: biv verified\n", bl->regno); 3284: } 3285: } 3286: 3287: /* Exit if there are no bivs. */ 3288: if (! loop_iv_list) 3289: { 3290: /* Can still unroll the loop anyways, but indicate that there is no 3291: strength reduction info available. */ 3292: if (flag_unroll_loops) 3293: unroll_loop (loop_end, insn_count, loop_start, end_insert_before, 0); 3294: 3295: return; 3296: } 3297: 3298: /* Find initial value for each biv by searching backwards from loop_start, 3299: halting at first label. Also record any test condition. */ 3300: 3301: call_seen = 0; 3302: for (p = loop_start; p && GET_CODE (p) != CODE_LABEL; p = PREV_INSN (p)) 3303: { 3304: note_insn = p; 3305: 3306: if (GET_CODE (p) == CALL_INSN) 3307: call_seen = 1; 3308: 3309: if (GET_CODE (p) == INSN || GET_CODE (p) == JUMP_INSN 3310: || GET_CODE (p) == CALL_INSN) 3311: note_stores (PATTERN (p), record_initial); 3312: 3313: /* Record any test of a biv that branches around the loop if no store 3314: between it and the start of loop. We only care about tests with 3315: constants and registers and only certain of those. */ 3316: if (GET_CODE (p) == JUMP_INSN 3317: && JUMP_LABEL (p) != 0 3318: && next_real_insn (JUMP_LABEL (p)) == next_real_insn (loop_end) 3319: && (test = get_condition_for_loop (p)) != 0 3320: && GET_CODE (XEXP (test, 0)) == REG 3321: && REGNO (XEXP (test, 0)) < max_reg_before_loop 3322: && (bl = reg_biv_class[REGNO (XEXP (test, 0))]) != 0 3323: && valid_initial_value_p (XEXP (test, 1), p, call_seen, loop_start) 3324: && bl->init_insn == 0) 3325: { 3326: /* If an NE test, we have an initial value! */ 3327: if (GET_CODE (test) == NE) 3328: { 3329: bl->init_insn = p; 3330: bl->init_set = gen_rtx (SET, VOIDmode, 3331: XEXP (test, 0), XEXP (test, 1)); 3332: } 3333: else 3334: bl->initial_test = test; 3335: } 3336: } 3337: 3338: /* Look at the each biv and see if we can say anything better about its 3339: initial value from any initializing insns set up above. (This is done 3340: in two passes to avoid missing SETs in a PARALLEL.) */ 3341: for (bl = loop_iv_list; bl; bl = bl->next) 3342: { 3343: rtx src; 3344: 3345: if (! bl->init_insn) 3346: continue; 3347: 3348: src = SET_SRC (bl->init_set); 3349: 3350: if (loop_dump_stream) 3351: fprintf (loop_dump_stream, 3352: "Biv %d initialized at insn %d: initial value ", 3353: bl->regno, INSN_UID (bl->init_insn)); 3354: 3355: if (valid_initial_value_p (src, bl->init_insn, call_seen, loop_start)) 3356: { 3357: bl->initial_value = src; 3358: 3359: if (loop_dump_stream) 3360: { 3361: if (GET_CODE (src) == CONST_INT) 3362: fprintf (loop_dump_stream, "%d\n", INTVAL (src)); 3363: else 3364: { 3365: print_rtl (loop_dump_stream, src); 3366: fprintf (loop_dump_stream, "\n"); 3367: } 3368: } 3369: } 3370: else 3371: { 3372: /* Biv initial value is not simple move, 1.1.1.2 root 3373: so let it keep initial value of "itself". */ 1.1 root 3374: 3375: if (loop_dump_stream) 3376: fprintf (loop_dump_stream, "is complex\n"); 3377: } 3378: } 3379: 3380: /* Search the loop for general induction variables. */ 3381: 3382: /* A register is a giv if: it is only set once, it is a function of a 3383: biv and a constant (or invariant), and it is not a biv. */ 3384: 3385: not_every_iteration = 0; 3386: p = scan_start; 3387: while (1) 3388: { 3389: p = NEXT_INSN (p); 3390: /* At end of a straight-in loop, we are done. 3391: At end of a loop entered at the bottom, scan the top. */ 3392: if (p == scan_start) 3393: break; 3394: if (p == end) 3395: { 3396: if (loop_top != 0) 3397: p = NEXT_INSN (loop_top); 3398: else 3399: break; 3400: if (p == scan_start) 3401: break; 3402: } 3403: 3404: /* Look for a general induction variable in a register. */ 3405: if (GET_CODE (p) == INSN 3406: && (set = single_set (p)) 3407: && GET_CODE (SET_DEST (set)) == REG 3408: && ! may_not_optimize[REGNO (SET_DEST (set))]) 3409: { 3410: rtx src_reg; 3411: rtx add_val; 3412: rtx mult_val; 3413: int benefit; 3414: rtx regnote = 0; 3415: 3416: dest_reg = SET_DEST (set); 3417: if (REGNO (dest_reg) < FIRST_PSEUDO_REGISTER) 3418: continue; 3419: 3420: if (/* SET_SRC is a giv. */ 3421: ((benefit = general_induction_var (SET_SRC (set), 3422: &src_reg, &add_val, 3423: &mult_val)) 3424: /* Equivalent expression is a giv. */ 1.1.1.4 ! root 3425: || ((regnote = find_reg_note (p, REG_EQUAL, NULL_RTX)) 1.1 root 3426: && (benefit = general_induction_var (XEXP (regnote, 0), 3427: &src_reg, 3428: &add_val, &mult_val)))) 3429: /* Don't try to handle any regs made by loop optimization. 3430: We have nothing on them in regno_first_uid, etc. */ 3431: && REGNO (dest_reg) < max_reg_before_loop 3432: /* Don't recognize a BASIC_INDUCT_VAR here. */ 3433: && dest_reg != src_reg 3434: /* This must be the only place where the register is set. */ 3435: && (n_times_set[REGNO (dest_reg)] == 1 3436: /* or all sets must be consecutive and make a giv. */ 3437: || (benefit = consec_sets_giv (benefit, p, 3438: src_reg, dest_reg, 3439: &add_val, &mult_val)))) 3440: { 3441: int count; 3442: struct induction *v 3443: = (struct induction *) alloca (sizeof (struct induction)); 3444: rtx temp; 3445: 3446: /* If this is a library call, increase benefit. */ 1.1.1.4 ! root 3447: if (find_reg_note (p, REG_RETVAL, NULL_RTX)) 1.1 root 3448: benefit += libcall_benefit (p); 3449: 3450: /* Skip the consecutive insns, if there are any. */ 3451: for (count = n_times_set[REGNO (dest_reg)] - 1; 3452: count > 0; count--) 3453: { 3454: /* If first insn of libcall sequence, skip to end. 3455: Do this at start of loop, since INSN is guaranteed to 3456: be an insn here. */ 3457: if (GET_CODE (p) != NOTE 1.1.1.4 ! root 3458: && (temp = find_reg_note (p, REG_LIBCALL, NULL_RTX))) 1.1 root 3459: p = XEXP (temp, 0); 3460: 3461: do p = NEXT_INSN (p); 3462: while (GET_CODE (p) == NOTE); 3463: } 3464: 3465: record_giv (v, p, src_reg, dest_reg, mult_val, add_val, benefit, 1.1.1.4 ! root 3466: DEST_REG, not_every_iteration, NULL_PTR, loop_start, 1.1 root 3467: loop_end); 3468: 3469: } 3470: } 3471: 3472: #ifndef DONT_REDUCE_ADDR 3473: /* Look for givs which are memory addresses. */ 3474: /* This resulted in worse code on a VAX 8600. I wonder if it 3475: still does. */ 3476: if (GET_CODE (p) == INSN) 3477: find_mem_givs (PATTERN (p), p, not_every_iteration, loop_start, 3478: loop_end); 3479: #endif 3480: 3481: /* Update the status of whether giv can derive other givs. This can 3482: change when we pass a label or an insn that updates a biv. */ 1.1.1.3 root 3483: if (GET_CODE (p) == INSN || GET_CODE (p) == JUMP_INSN 3484: || GET_CODE (p) == CODE_LABEL) 1.1 root 3485: update_giv_derive (p); 3486: 3487: /* Past a label or a jump, we get to insns for which we can't count 3488: on whether or how many times they will be executed during each 3489: iteration. */ 3490: /* This code appears in three places, once in scan_loop, and twice 3491: in strength_reduce. */ 3492: if ((GET_CODE (p) == CODE_LABEL || GET_CODE (p) == JUMP_INSN) 3493: /* If we enter the loop in the middle, and scan around 3494: to the beginning, don't set not_every_iteration for that. 3495: This can be any kind of jump, since we want to know if insns 3496: will be executed if the loop is executed. */ 3497: && ! (GET_CODE (p) == JUMP_INSN && JUMP_LABEL (p) == loop_top 3498: && ((NEXT_INSN (NEXT_INSN (p)) == loop_end && simplejump_p (p)) 3499: || (NEXT_INSN (p) == loop_end && condjump_p (p))))) 3500: not_every_iteration = 1; 3501: 3502: /* At the virtual top of a converted loop, insns are again known to 3503: be executed each iteration: logically, the loop begins here 3504: even though the exit code has been duplicated. */ 3505: 3506: else if (GET_CODE (p) == NOTE 3507: && NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_VTOP) 3508: not_every_iteration = 0; 3509: 3510: /* Unlike in the code motion pass where MAYBE_NEVER indicates that 3511: an insn may never be executed, NOT_EVERY_ITERATION indicates whether 3512: or not an insn is known to be executed each iteration of the 3513: loop, whether or not any iterations are known to occur. 3514: 3515: Therefore, if we have just passed a label and have no more labels 3516: between here and the test insn of the loop, we know these insns 3517: will be executed each iteration. */ 3518: 3519: if (not_every_iteration && GET_CODE (p) == CODE_LABEL 3520: && no_labels_between_p (p, loop_end)) 3521: not_every_iteration = 0; 3522: } 3523: 3524: /* Try to calculate and save the number of loop iterations. This is 3525: set to zero if the actual number can not be calculated. This must 3526: be called after all giv's have been identified, since otherwise it may 3527: fail if the iteration variable is a giv. */ 3528: 3529: loop_n_iterations = loop_iterations (loop_start, loop_end); 3530: 3531: /* Now for each giv for which we still don't know whether or not it is 3532: replaceable, check to see if it is replaceable because its final value 3533: can be calculated. This must be done after loop_iterations is called, 3534: so that final_giv_value will work correctly. */ 3535: 3536: for (bl = loop_iv_list; bl; bl = bl->next) 3537: { 3538: struct induction *v; 3539: 3540: for (v = bl->giv; v; v = v->next_iv) 3541: if (! v->replaceable && ! v->not_replaceable) 3542: check_final_value (v, loop_start, loop_end); 3543: } 3544: 3545: /* Try to prove that the loop counter variable (if any) is always 3546: nonnegative; if so, record that fact with a REG_NONNEG note 3547: so that "decrement and branch until zero" insn can be used. */ 3548: check_dbra_loop (loop_end, insn_count, loop_start); 3549: 3550: /* Create reg_map to hold substitutions for replaceable giv regs. */ 3551: reg_map = (rtx *) alloca (max_reg_before_loop * sizeof (rtx)); 3552: bzero ((char *) reg_map, max_reg_before_loop * sizeof (rtx)); 3553: 3554: /* Examine each iv class for feasibility of strength reduction/induction 3555: variable elimination. */ 3556: 3557: for (bl = loop_iv_list; bl; bl = bl->next) 3558: { 3559: struct induction *v; 3560: int benefit; 3561: int all_reduced; 3562: rtx final_value = 0; 3563: 3564: /* Test whether it will be possible to eliminate this biv 3565: provided all givs are reduced. This is possible if either 3566: the reg is not used outside the loop, or we can compute 3567: what its final value will be. 3568: 3569: For architectures with a decrement_and_branch_until_zero insn, 3570: don't do this if we put a REG_NONNEG note on the endtest for 3571: this biv. */ 3572: 3573: /* Compare against bl->init_insn rather than loop_start. 3574: We aren't concerned with any uses of the biv between 3575: init_insn and loop_start since these won't be affected 3576: by the value of the biv elsewhere in the function, so 3577: long as init_insn doesn't use the biv itself. 3578: March 14, 1989 -- [email protected] */ 3579: 3580: if ((uid_luid[regno_last_uid[bl->regno]] < INSN_LUID (loop_end) 3581: && bl->init_insn 3582: && INSN_UID (bl->init_insn) < max_uid_for_loop 3583: && uid_luid[regno_first_uid[bl->regno]] >= INSN_LUID (bl->init_insn) 3584: #ifdef HAVE_decrement_and_branch_until_zero 3585: && ! bl->nonneg 3586: #endif 3587: && ! reg_mentioned_p (bl->biv->dest_reg, SET_SRC (bl->init_set))) 3588: || ((final_value = final_biv_value (bl, loop_start, loop_end)) 3589: #ifdef HAVE_decrement_and_branch_until_zero 3590: && ! bl->nonneg 3591: #endif 3592: )) 3593: bl->eliminable = maybe_eliminate_biv (bl, loop_start, end, 0, 3594: threshold, insn_count); 3595: else 3596: { 3597: if (loop_dump_stream) 3598: { 3599: fprintf (loop_dump_stream, 3600: "Cannot eliminate biv %d.\n", 3601: bl->regno); 3602: fprintf (loop_dump_stream, 3603: "First use: insn %d, last use: insn %d.\n", 3604: regno_first_uid[bl->regno], 3605: regno_last_uid[bl->regno]); 3606: } 3607: } 3608: 3609: /* Combine all giv's for this iv_class. */ 3610: combine_givs (bl); 3611: 3612: /* This will be true at the end, if all givs which depend on this 3613: biv have been strength reduced. 3614: We can't (currently) eliminate the biv unless this is so. */ 3615: all_reduced = 1; 3616: 3617: /* Check each giv in this class to see if we will benefit by reducing 3618: it. Skip giv's combined with others. */ 3619: for (v = bl->giv; v; v = v->next_iv) 3620: { 3621: struct induction *tv; 3622: 3623: if (v->ignore || v->same) 3624: continue; 3625: 3626: benefit = v->benefit; 3627: 3628: /* Reduce benefit if not replaceable, since we will insert 3629: a move-insn to replace the insn that calculates this giv. 3630: Don't do this unless the giv is a user variable, since it 3631: will often be marked non-replaceable because of the duplication 3632: of the exit code outside the loop. In such a case, the copies 3633: we insert are dead and will be deleted. So they don't have 3634: a cost. Similar situations exist. */ 3635: /* ??? The new final_[bg]iv_value code does a much better job 3636: of finding replaceable giv's, and hence this code may no longer 3637: be necessary. */ 3638: if (! v->replaceable && ! bl->eliminable 3639: && REG_USERVAR_P (v->dest_reg)) 3640: benefit -= copy_cost; 3641: 3642: /* Decrease the benefit to count the add-insns that we will 3643: insert to increment the reduced reg for the giv. */ 3644: benefit -= add_cost * bl->biv_count; 3645: 3646: /* Decide whether to strength-reduce this giv or to leave the code 3647: unchanged (recompute it from the biv each time it is used). 3648: This decision can be made independently for each giv. */ 3649: 3650: /* ??? Perhaps attempt to guess whether autoincrement will handle 3651: some of the new add insns; if so, can increase BENEFIT 3652: (undo the subtraction of add_cost that was done above). */ 3653: 3654: /* If an insn is not to be strength reduced, then set its ignore 3655: flag, and clear all_reduced. */ 3656: 3657: if (v->lifetime * threshold * benefit < insn_count) 3658: { 3659: if (loop_dump_stream) 3660: fprintf (loop_dump_stream, 3661: "giv of insn %d not worth while, %d vs %d.\n", 3662: INSN_UID (v->insn), 3663: v->lifetime * threshold * benefit, insn_count); 3664: v->ignore = 1; 3665: all_reduced = 0; 3666: } 3667: else 3668: { 3669: /* Check that we can increment the reduced giv without a 3670: multiply insn. If not, reject it. */ 3671: 3672: for (tv = bl->biv; tv; tv = tv->next_iv) 3673: if (tv->mult_val == const1_rtx 3674: && ! product_cheap_p (tv->add_val, v->mult_val)) 3675: { 3676: if (loop_dump_stream) 3677: fprintf (loop_dump_stream, 3678: "giv of insn %d: would need a multiply.\n", 3679: INSN_UID (v->insn)); 3680: v->ignore = 1; 3681: all_reduced = 0; 3682: break; 3683: } 3684: } 3685: } 3686: 3687: /* Reduce each giv that we decided to reduce. */ 3688: 3689: for (v = bl->giv; v; v = v->next_iv) 3690: { 3691: struct induction *tv; 3692: if (! v->ignore && v->same == 0) 3693: { 3694: v->new_reg = gen_reg_rtx (v->mode); 3695: 3696: /* For each place where the biv is incremented, 3697: add an insn to increment the new, reduced reg for the giv. */ 3698: for (tv = bl->biv; tv; tv = tv->next_iv) 3699: { 3700: if (tv->mult_val == const1_rtx) 3701: emit_iv_add_mult (tv->add_val, v->mult_val, 3702: v->new_reg, v->new_reg, tv->insn); 3703: else /* tv->mult_val == const0_rtx */ 3704: /* A multiply is acceptable here 3705: since this is presumed to be seldom executed. */ 3706: emit_iv_add_mult (tv->add_val, v->mult_val, 3707: v->add_val, v->new_reg, tv->insn); 3708: } 3709: 3710: /* Add code at loop start to initialize giv's reduced reg. */ 3711: 3712: emit_iv_add_mult (bl->initial_value, v->mult_val, 3713: v->add_val, v->new_reg, loop_start); 3714: } 3715: } 3716: 3717: /* Rescan all givs. If a giv is the same as a giv not reduced, mark it 3718: as not reduced. 3719: 3720: For each giv register that can be reduced now: if replaceable, 3721: substitute reduced reg wherever the old giv occurs; 3722: else add new move insn "giv_reg = reduced_reg". 3723: 3724: Also check for givs whose first use is their definition and whose 3725: last use is the definition of another giv. If so, it is likely 3726: dead and should not be used to eliminate a biv. */ 3727: for (v = bl->giv; v; v = v->next_iv) 3728: { 3729: if (v->same && v->same->ignore) 3730: v->ignore = 1; 3731: 3732: if (v->ignore) 3733: continue; 3734: 3735: if (v->giv_type == DEST_REG 3736: && regno_first_uid[REGNO (v->dest_reg)] == INSN_UID (v->insn)) 3737: { 3738: struct induction *v1; 3739: 3740: for (v1 = bl->giv; v1; v1 = v1->next_iv) 3741: if (regno_last_uid[REGNO (v->dest_reg)] == INSN_UID (v1->insn)) 3742: v->maybe_dead = 1; 3743: } 3744: 3745: /* Update expression if this was combined, in case other giv was 3746: replaced. */ 3747: if (v->same) 3748: v->new_reg = replace_rtx (v->new_reg, 3749: v->same->dest_reg, v->same->new_reg); 3750: 3751: if (v->giv_type == DEST_ADDR) 3752: /* Store reduced reg as the address in the memref where we found 3753: this giv. */ 3754: *v->location = v->new_reg; 3755: else if (v->replaceable) 3756: { 3757: reg_map[REGNO (v->dest_reg)] = v->new_reg; 3758: 3759: #if 0 3760: /* I can no longer duplicate the original problem. Perhaps 3761: this is unnecessary now? */ 3762: 3763: /* Replaceable; it isn't strictly necessary to delete the old 3764: insn and emit a new one, because v->dest_reg is now dead. 3765: 3766: However, especially when unrolling loops, the special 3767: handling for (set REG0 REG1) in the second cse pass may 3768: make v->dest_reg live again. To avoid this problem, emit 3769: an insn to set the original giv reg from the reduced giv. 3770: We can not delete the original insn, since it may be part 3771: of a LIBCALL, and the code in flow that eliminates dead 3772: libcalls will fail if it is deleted. */ 3773: emit_insn_after (gen_move_insn (v->dest_reg, v->new_reg), 3774: v->insn); 3775: #endif 3776: } 3777: else 3778: { 3779: /* Not replaceable; emit an insn to set the original giv reg from 3780: the reduced giv, same as above. */ 3781: emit_insn_after (gen_move_insn (v->dest_reg, v->new_reg), 3782: v->insn); 3783: } 3784: 3785: /* When a loop is reversed, givs which depend on the reversed 3786: biv, and which are live outside the loop, must be set to their 3787: correct final value. This insn is only needed if the giv is 3788: not replaceable. The correct final value is the same as the 3789: value that the giv starts the reversed loop with. */ 3790: if (bl->reversed && ! v->replaceable) 3791: emit_iv_add_mult (bl->initial_value, v->mult_val, 3792: v->add_val, v->dest_reg, end_insert_before); 3793: else if (v->final_value) 3794: { 3795: rtx insert_before; 3796: 3797: /* If the loop has multiple exits, emit the insn before the 3798: loop to ensure that it will always be executed no matter 3799: how the loop exits. Otherwise, emit the insn after the loop, 3800: since this is slightly more efficient. */ 3801: if (loop_number_exit_labels[uid_loop_num[INSN_UID (loop_start)]]) 3802: insert_before = loop_start; 3803: else 3804: insert_before = end_insert_before; 3805: emit_insn_before (gen_move_insn (v->dest_reg, v->final_value), 3806: insert_before); 3807: 3808: #if 0 3809: /* If the insn to set the final value of the giv was emitted 3810: before the loop, then we must delete the insn inside the loop 3811: that sets it. If this is a LIBCALL, then we must delete 3812: every insn in the libcall. Note, however, that 3813: final_giv_value will only succeed when there are multiple 3814: exits if the giv is dead at each exit, hence it does not 3815: matter that the original insn remains because it is dead 3816: anyways. */ 3817: /* Delete the insn inside the loop that sets the giv since 3818: the giv is now set before (or after) the loop. */ 3819: delete_insn (v->insn); 3820: #endif 3821: } 3822: 3823: if (loop_dump_stream) 3824: { 3825: fprintf (loop_dump_stream, "giv at %d reduced to ", 3826: INSN_UID (v->insn)); 3827: print_rtl (loop_dump_stream, v->new_reg); 3828: fprintf (loop_dump_stream, "\n"); 3829: } 3830: } 3831: 3832: /* All the givs based on the biv bl have been reduced if they 3833: merit it. */ 3834: 3835: /* For each giv not marked as maybe dead that has been combined with a 3836: second giv, clear any "maybe dead" mark on that second giv. 3837: v->new_reg will either be or refer to the register of the giv it 3838: combined with. 3839: 3840: Doing this clearing avoids problems in biv elimination where a 3841: giv's new_reg is a complex value that can't be put in the insn but 3842: the giv combined with (with a reg as new_reg) is marked maybe_dead. 3843: Since the register will be used in either case, we'd prefer it be 3844: used from the simpler giv. */ 3845: 3846: for (v = bl->giv; v; v = v->next_iv) 3847: if (! v->maybe_dead && v->same) 3848: v->same->maybe_dead = 0; 3849: 3850: /* Try to eliminate the biv, if it is a candidate. 3851: This won't work if ! all_reduced, 3852: since the givs we planned to use might not have been reduced. 3853: 1.1.1.2 root 3854: We have to be careful that we didn't initially think we could eliminate 1.1 root 3855: this biv because of a giv that we now think may be dead and shouldn't 3856: be used as a biv replacement. 3857: 3858: Also, there is the possibility that we may have a giv that looks 3859: like it can be used to eliminate a biv, but the resulting insn 3860: isn't valid. This can happen, for example, on the 88k, where a 3861: JUMP_INSN can compare a register only with zero. Attempts to 1.1.1.3 root 3862: replace it with a compare with a constant will fail. 1.1 root 3863: 3864: Note that in cases where this call fails, we may have replaced some 3865: of the occurrences of the biv with a giv, but no harm was done in 3866: doing so in the rare cases where it can occur. */ 3867: 3868: if (all_reduced == 1 && bl->eliminable 3869: && maybe_eliminate_biv (bl, loop_start, end, 1, 3870: threshold, insn_count)) 3871: 3872: { 3873: /* ?? If we created a new test to bypass the loop entirely, 3874: or otherwise drop straight in, based on this test, then 3875: we might want to rewrite it also. This way some later 3876: pass has more hope of removing the initialization of this 3877: biv entirely. */ 3878: 3879: /* If final_value != 0, then the biv may be used after loop end 3880: and we must emit an insn to set it just in case. 3881: 3882: Reversed bivs already have an insn after the loop setting their 3883: value, so we don't need another one. We can't calculate the 3884: proper final value for such a biv here anyways. */ 3885: if (final_value != 0 && ! bl->reversed) 3886: { 3887: rtx insert_before; 3888: 3889: /* If the loop has multiple exits, emit the insn before the 3890: loop to ensure that it will always be executed no matter 3891: how the loop exits. Otherwise, emit the insn after the 3892: loop, since this is slightly more efficient. */ 3893: if (loop_number_exit_labels[uid_loop_num[INSN_UID (loop_start)]]) 3894: insert_before = loop_start; 3895: else 3896: insert_before = end_insert_before; 3897: 3898: emit_insn_before (gen_move_insn (bl->biv->dest_reg, final_value), 3899: end_insert_before); 3900: } 3901: 3902: #if 0 3903: /* Delete all of the instructions inside the loop which set 3904: the biv, as they are all dead. If is safe to delete them, 3905: because an insn setting a biv will never be part of a libcall. */ 3906: /* However, deleting them will invalidate the regno_last_uid info, 3907: so keeping them around is more convenient. Final_biv_value 3908: will only succeed when there are multiple exits if the biv 3909: is dead at each exit, hence it does not matter that the original 3910: insn remains, because it is dead anyways. */ 3911: for (v = bl->biv; v; v = v->next_iv) 3912: delete_insn (v->insn); 3913: #endif 3914: 3915: if (loop_dump_stream) 3916: fprintf (loop_dump_stream, "Reg %d: biv eliminated\n", 3917: bl->regno); 3918: } 3919: } 3920: 3921: /* Go through all the instructions in the loop, making all the 3922: register substitutions scheduled in REG_MAP. */ 3923: 3924: for (p = loop_start; p != end; p = NEXT_INSN (p)) 3925: if (GET_CODE (p) == INSN || GET_CODE (p) == JUMP_INSN 3926: || GET_CODE (p) == CALL_INSN) 3927: { 3928: replace_regs (PATTERN (p), reg_map, max_reg_before_loop, 0); 3929: replace_regs (REG_NOTES (p), reg_map, max_reg_before_loop, 0); 3930: } 3931: 3932: /* Unroll loops from within strength reduction so that we can use the 3933: induction variable information that strength_reduce has already 3934: collected. */ 3935: 3936: if (flag_unroll_loops) 3937: unroll_loop (loop_end, insn_count, loop_start, end_insert_before, 1); 3938: 3939: if (loop_dump_stream) 3940: fprintf (loop_dump_stream, "\n"); 3941: } 3942: 3943: /* Return 1 if X is a valid source for an initial value (or as value being 3944: compared against in an initial test). 3945: 3946: X must be either a register or constant and must not be clobbered between 3947: the current insn and the start of the loop. 3948: 3949: INSN is the insn containing X. */ 3950: 3951: static int 3952: valid_initial_value_p (x, insn, call_seen, loop_start) 3953: rtx x; 3954: rtx insn; 3955: int call_seen; 3956: rtx loop_start; 3957: { 3958: if (CONSTANT_P (x)) 3959: return 1; 3960: 1.1.1.2 root 3961: /* Only consider pseudos we know about initialized in insns whose luids 1.1 root 3962: we know. */ 3963: if (GET_CODE (x) != REG 3964: || REGNO (x) >= max_reg_before_loop) 3965: return 0; 3966: 3967: /* Don't use call-clobbered registers across a call which clobbers it. On 3968: some machines, don't use any hard registers at all. */ 3969: if (REGNO (x) < FIRST_PSEUDO_REGISTER 3970: #ifndef SMALL_REGISTER_CLASSES 3971: && call_used_regs[REGNO (x)] && call_seen 3972: #endif 3973: ) 3974: return 0; 3975: 3976: /* Don't use registers that have been clobbered before the start of the 3977: loop. */ 3978: if (reg_set_between_p (x, insn, loop_start)) 3979: return 0; 3980: 3981: return 1; 3982: } 3983: 3984: /* Scan X for memory refs and check each memory address 3985: as a possible giv. INSN is the insn whose pattern X comes from. 3986: NOT_EVERY_ITERATION is 1 if the insn might not be executed during 3987: every loop iteration. */ 3988: 3989: static void 3990: find_mem_givs (x, insn, not_every_iteration, loop_start, loop_end) 3991: rtx x; 3992: rtx insn; 3993: int not_every_iteration; 3994: rtx loop_start, loop_end; 3995: { 3996: register int i, j; 3997: register enum rtx_code code; 3998: register char *fmt; 3999: 4000: if (x == 0) 4001: return; 4002: 4003: code = GET_CODE (x); 4004: switch (code) 4005: { 4006: case REG: 4007: case CONST_INT: 4008: case CONST: 4009: case CONST_DOUBLE: 4010: case SYMBOL_REF: 4011: case LABEL_REF: 4012: case PC: 4013: case CC0: 4014: case ADDR_VEC: 4015: case ADDR_DIFF_VEC: 4016: case USE: 4017: case CLOBBER: 4018: return; 4019: 4020: case MEM: 4021: { 4022: rtx src_reg; 4023: rtx add_val; 4024: rtx mult_val; 4025: int benefit; 4026: 4027: benefit = general_induction_var (XEXP (x, 0), 4028: &src_reg, &add_val, &mult_val); 4029: 4030: /* Don't make a DEST_ADDR giv with mult_val == 1 && add_val == 0. 4031: Such a giv isn't useful. */ 4032: if (benefit > 0 && (mult_val != const1_rtx || add_val != const0_rtx)) 4033: { 4034: /* Found one; record it. */ 4035: struct induction *v 4036: = (struct induction *) oballoc (sizeof (struct induction)); 4037: 4038: record_giv (v, insn, src_reg, addr_placeholder, mult_val, 4039: add_val, benefit, DEST_ADDR, not_every_iteration, 4040: &XEXP (x, 0), loop_start, loop_end); 4041: 4042: v->mem_mode = GET_MODE (x); 4043: } 4044: return; 4045: } 4046: } 4047: 4048: /* Recursively scan the subexpressions for other mem refs. */ 4049: 4050: fmt = GET_RTX_FORMAT (code); 4051: for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) 4052: if (fmt[i] == 'e') 4053: find_mem_givs (XEXP (x, i), insn, not_every_iteration, loop_start, 4054: loop_end); 4055: else if (fmt[i] == 'E') 4056: for (j = 0; j < XVECLEN (x, i); j++) 4057: find_mem_givs (XVECEXP (x, i, j), insn, not_every_iteration, 4058: loop_start, loop_end); 4059: } 4060: 4061: /* Fill in the data about one biv update. 4062: V is the `struct induction' in which we record the biv. (It is 4063: allocated by the caller, with alloca.) 4064: INSN is the insn that sets it. 4065: DEST_REG is the biv's reg. 4066: 4067: MULT_VAL is const1_rtx if the biv is being incremented here, in which case 4068: INC_VAL is the increment. Otherwise, MULT_VAL is const0_rtx and the biv is 1.1.1.3 root 4069: being set to INC_VAL. 4070: 4071: NOT_EVERY_ITERATION is nonzero if this biv update is not know to be 4072: executed every iteration; MAYBE_MULTIPLE is nonzero if this biv update 4073: can be executed more than once per iteration. If MAYBE_MULTIPLE 4074: and NOT_EVERY_ITERATION are both zero, we know that the biv update is 4075: executed exactly once per iteration. */ 1.1 root 4076: 4077: static void 1.1.1.3 root 4078: record_biv (v, insn, dest_reg, inc_val, mult_val, 4079: not_every_iteration, maybe_multiple) 1.1 root 4080: struct induction *v; 4081: rtx insn; 4082: rtx dest_reg; 4083: rtx inc_val; 4084: rtx mult_val; 4085: int not_every_iteration; 1.1.1.3 root 4086: int maybe_multiple; 1.1 root 4087: { 4088: struct iv_class *bl; 4089: 4090: v->insn = insn; 4091: v->src_reg = dest_reg; 4092: v->dest_reg = dest_reg; 4093: v->mult_val = mult_val; 4094: v->add_val = inc_val; 4095: v->mode = GET_MODE (dest_reg); 4096: v->always_computable = ! not_every_iteration; 1.1.1.3 root 4097: v->maybe_multiple = maybe_multiple; 1.1 root 4098: 4099: /* Add this to the reg's iv_class, creating a class 4100: if this is the first incrementation of the reg. */ 4101: 4102: bl = reg_biv_class[REGNO (dest_reg)]; 4103: if (bl == 0) 4104: { 4105: /* Create and initialize new iv_class. */ 4106: 4107: bl = (struct iv_class *) oballoc (sizeof (struct iv_class)); 4108: 4109: bl->regno = REGNO (dest_reg); 4110: bl->biv = 0; 4111: bl->giv = 0; 4112: bl->biv_count = 0; 4113: bl->giv_count = 0; 4114: 4115: /* Set initial value to the reg itself. */ 4116: bl->initial_value = dest_reg; 1.1.1.3 root 4117: /* We haven't seen the initializing insn yet */ 1.1 root 4118: bl->init_insn = 0; 4119: bl->init_set = 0; 4120: bl->initial_test = 0; 4121: bl->incremented = 0; 4122: bl->eliminable = 0; 4123: bl->nonneg = 0; 4124: bl->reversed = 0; 1.1.1.4 ! root 4125: bl->total_benefit = 0; 1.1 root 4126: 4127: /* Add this class to loop_iv_list. */ 4128: bl->next = loop_iv_list; 4129: loop_iv_list = bl; 4130: 4131: /* Put it in the array of biv register classes. */ 4132: reg_biv_class[REGNO (dest_reg)] = bl; 4133: } 4134: 4135: /* Update IV_CLASS entry for this biv. */ 4136: v->next_iv = bl->biv; 4137: bl->biv = v; 4138: bl->biv_count++; 4139: if (mult_val == const1_rtx) 4140: bl->incremented = 1; 4141: 4142: if (loop_dump_stream) 4143: { 4144: fprintf (loop_dump_stream, 4145: "Insn %d: possible biv, reg %d,", 4146: INSN_UID (insn), REGNO (dest_reg)); 4147: if (GET_CODE (inc_val) == CONST_INT) 4148: fprintf (loop_dump_stream, " const = %d\n", 4149: INTVAL (inc_val)); 4150: else 4151: { 4152: fprintf (loop_dump_stream, " const = "); 4153: print_rtl (loop_dump_stream, inc_val); 4154: fprintf (loop_dump_stream, "\n"); 4155: } 4156: } 4157: } 4158: 4159: /* Fill in the data about one giv. 4160: V is the `struct induction' in which we record the giv. (It is 4161: allocated by the caller, with alloca.) 4162: INSN is the insn that sets it. 4163: BENEFIT estimates the savings from deleting this insn. 4164: TYPE is DEST_REG or DEST_ADDR; it says whether the giv is computed 4165: into a register or is used as a memory address. 4166: 4167: SRC_REG is the biv reg which the giv is computed from. 4168: DEST_REG is the giv's reg (if the giv is stored in a reg). 4169: MULT_VAL and ADD_VAL are the coefficients used to compute the giv. 4170: LOCATION points to the place where this giv's value appears in INSN. */ 4171: 4172: static void 4173: record_giv (v, insn, src_reg, dest_reg, mult_val, add_val, benefit, 4174: type, not_every_iteration, location, loop_start, loop_end) 4175: struct induction *v; 4176: rtx insn; 4177: rtx src_reg; 4178: rtx dest_reg; 4179: rtx mult_val, add_val; 4180: int benefit; 4181: enum g_types type; 4182: int not_every_iteration; 4183: rtx *location; 4184: rtx loop_start, loop_end; 4185: { 4186: struct induction *b; 4187: struct iv_class *bl; 4188: rtx set = single_set (insn); 4189: rtx p; 4190: 4191: v->insn = insn; 4192: v->src_reg = src_reg; 4193: v->giv_type = type; 4194: v->dest_reg = dest_reg; 4195: v->mult_val = mult_val; 4196: v->add_val = add_val; 4197: v->benefit = benefit; 4198: v->location = location; 4199: v->cant_derive = 0; 4200: v->combined_with = 0; 1.1.1.3 root 4201: v->maybe_multiple = 0; 1.1 root 4202: v->maybe_dead = 0; 4203: v->derive_adjustment = 0; 4204: v->same = 0; 4205: v->ignore = 0; 4206: v->new_reg = 0; 4207: v->final_value = 0; 4208: 4209: /* The v->always_computable field is used in update_giv_derive, to 4210: determine whether a giv can be used to derive another giv. For a 4211: DEST_REG giv, INSN computes a new value for the giv, so its value 4212: isn't computable if INSN insn't executed every iteration. 4213: However, for a DEST_ADDR giv, INSN merely uses the value of the giv; 4214: it does not compute a new value. Hence the value is always computable 1.1.1.2 root 4215: regardless of whether INSN is executed each iteration. */ 1.1 root 4216: 4217: if (type == DEST_ADDR) 4218: v->always_computable = 1; 4219: else 4220: v->always_computable = ! not_every_iteration; 4221: 4222: if (type == DEST_ADDR) 4223: { 4224: v->mode = GET_MODE (*location); 4225: v->lifetime = 1; 4226: v->times_used = 1; 4227: } 4228: else /* type == DEST_REG */ 4229: { 4230: v->mode = GET_MODE (SET_DEST (set)); 4231: 4232: v->lifetime = (uid_luid[regno_last_uid[REGNO (dest_reg)]] 4233: - uid_luid[regno_first_uid[REGNO (dest_reg)]]); 4234: 4235: v->times_used = n_times_used[REGNO (dest_reg)]; 4236: 4237: /* If the lifetime is zero, it means that this register is 4238: really a dead store. So mark this as a giv that can be 4239: ignored. This will not prevent the biv from being eliminated. */ 4240: if (v->lifetime == 0) 4241: v->ignore = 1; 4242: 4243: reg_iv_type[REGNO (dest_reg)] = GENERAL_INDUCT; 4244: reg_iv_info[REGNO (dest_reg)] = v; 4245: } 4246: 4247: /* Add the giv to the class of givs computed from one biv. */ 4248: 4249: bl = reg_biv_class[REGNO (src_reg)]; 4250: if (bl) 4251: { 4252: v->next_iv = bl->giv; 4253: bl->giv = v; 4254: /* Don't count DEST_ADDR. This is supposed to count the number of 4255: insns that calculate givs. */ 4256: if (type == DEST_REG) 4257: bl->giv_count++; 4258: bl->total_benefit += benefit; 4259: } 4260: else 4261: /* Fatal error, biv missing for this giv? */ 4262: abort (); 4263: 4264: if (type == DEST_ADDR) 4265: v->replaceable = 1; 4266: else 4267: { 4268: /* The giv can be replaced outright by the reduced register only if all 4269: of the following conditions are true: 4270: - the insn that sets the giv is always executed on any iteration 4271: on which the giv is used at all 4272: (there are two ways to deduce this: 4273: either the insn is executed on every iteration, 4274: or all uses follow that insn in the same basic block), 4275: - the giv is not used outside the loop 4276: - no assignments to the biv occur during the giv's lifetime. */ 4277: 4278: if (regno_first_uid[REGNO (dest_reg)] == INSN_UID (insn) 4279: /* Previous line always fails if INSN was moved by loop opt. */ 4280: && uid_luid[regno_last_uid[REGNO (dest_reg)]] < INSN_LUID (loop_end) 4281: && (! not_every_iteration 4282: || last_use_this_basic_block (dest_reg, insn))) 4283: { 4284: /* Now check that there are no assignments to the biv within the 4285: giv's lifetime. This requires two separate checks. */ 4286: 4287: /* Check each biv update, and fail if any are between the first 4288: and last use of the giv. 4289: 4290: If this loop contains an inner loop that was unrolled, then 4291: the insn modifying the biv may have been emitted by the loop 4292: unrolling code, and hence does not have a valid luid. Just 4293: mark the biv as not replaceable in this case. It is not very 4294: useful as a biv, because it is used in two different loops. 4295: It is very unlikely that we would be able to optimize the giv 4296: using this biv anyways. */ 4297: 4298: v->replaceable = 1; 4299: for (b = bl->biv; b; b = b->next_iv) 4300: { 4301: if (INSN_UID (b->insn) >= max_uid_for_loop 4302: || ((uid_luid[INSN_UID (b->insn)] 4303: >= uid_luid[regno_first_uid[REGNO (dest_reg)]]) 4304: && (uid_luid[INSN_UID (b->insn)] 4305: <= uid_luid[regno_last_uid[REGNO (dest_reg)]]))) 4306: { 4307: v->replaceable = 0; 4308: v->not_replaceable = 1; 4309: break; 4310: } 4311: } 4312: 4313: /* Check each insn between the first and last use of the giv, 4314: and fail if any of them are branches that jump to a named label 4315: outside this range, but still inside the loop. This catches 4316: cases of spaghetti code where the execution order of insns 4317: is not linear, and hence the above test fails. For example, 4318: in the following code, j is not replaceable: 4319: for (i = 0; i < 100; ) { 4320: L0: j = 4*i; goto L1; 4321: L2: k = j; goto L3; 4322: L1: i++; goto L2; 4323: L3: ; } 4324: printf ("k = %d\n", k); } 4325: This test is conservative, but this test succeeds rarely enough 4326: that it isn't a problem. See also check_final_value below. */ 4327: 4328: if (v->replaceable) 4329: for (p = insn; 4330: INSN_UID (p) >= max_uid_for_loop 4331: || INSN_LUID (p) < uid_luid[regno_last_uid[REGNO (dest_reg)]]; 4332: p = NEXT_INSN (p)) 4333: { 4334: if (GET_CODE (p) == JUMP_INSN && JUMP_LABEL (p) 4335: && LABEL_NAME (JUMP_LABEL (p)) 4336: && ((INSN_LUID (JUMP_LABEL (p)) > INSN_LUID (loop_start) 4337: && (INSN_LUID (JUMP_LABEL (p)) 4338: < uid_luid[regno_first_uid[REGNO (dest_reg)]])) 4339: || (INSN_LUID (JUMP_LABEL (p)) < INSN_LUID (loop_end) 4340: && (INSN_LUID (JUMP_LABEL (p)) 4341: > uid_luid[regno_last_uid[REGNO (dest_reg)]])))) 4342: { 4343: v->replaceable = 0; 4344: v->not_replaceable = 1; 4345: 4346: if (loop_dump_stream) 4347: fprintf (loop_dump_stream, 4348: "Found branch outside giv lifetime.\n"); 4349: 4350: break; 4351: } 4352: } 4353: } 4354: else 4355: { 4356: /* May still be replaceable, we don't have enough info here to 4357: decide. */ 4358: v->replaceable = 0; 4359: v->not_replaceable = 0; 4360: } 4361: } 4362: 4363: if (loop_dump_stream) 4364: { 4365: if (type == DEST_REG) 4366: fprintf (loop_dump_stream, "Insn %d: giv reg %d", 4367: INSN_UID (insn), REGNO (dest_reg)); 4368: else 4369: fprintf (loop_dump_stream, "Insn %d: dest address", 4370: INSN_UID (insn)); 4371: 4372: fprintf (loop_dump_stream, " src reg %d benefit %d", 4373: REGNO (src_reg), v->benefit); 4374: fprintf (loop_dump_stream, " used %d lifetime %d", 4375: v->times_used, v->lifetime); 4376: 4377: if (v->replaceable) 4378: fprintf (loop_dump_stream, " replaceable"); 4379: 4380: if (GET_CODE (mult_val) == CONST_INT) 4381: fprintf (loop_dump_stream, " mult %d", 4382: INTVAL (mult_val)); 4383: else 4384: { 4385: fprintf (loop_dump_stream, " mult "); 4386: print_rtl (loop_dump_stream, mult_val); 4387: } 4388: 4389: if (GET_CODE (add_val) == CONST_INT) 4390: fprintf (loop_dump_stream, " add %d", 4391: INTVAL (add_val)); 4392: else 4393: { 4394: fprintf (loop_dump_stream, " add "); 4395: print_rtl (loop_dump_stream, add_val); 4396: } 4397: } 4398: 4399: if (loop_dump_stream) 4400: fprintf (loop_dump_stream, "\n"); 4401: 4402: } 4403: 4404: 4405: /* All this does is determine whether a giv can be made replaceable because 4406: its final value can be calculated. This code can not be part of record_giv 4407: above, because final_giv_value requires that the number of loop iterations 4408: be known, and that can not be accurately calculated until after all givs 4409: have been identified. */ 4410: 4411: static void 4412: check_final_value (v, loop_start, loop_end) 4413: struct induction *v; 4414: rtx loop_start, loop_end; 4415: { 4416: struct iv_class *bl; 4417: rtx final_value = 0; 4418: rtx tem; 4419: 4420: bl = reg_biv_class[REGNO (v->src_reg)]; 4421: 4422: /* DEST_ADDR givs will never reach here, because they are always marked 4423: replaceable above in record_giv. */ 4424: 4425: /* The giv can be replaced outright by the reduced register only if all 4426: of the following conditions are true: 4427: - the insn that sets the giv is always executed on any iteration 4428: on which the giv is used at all 4429: (there are two ways to deduce this: 4430: either the insn is executed on every iteration, 4431: or all uses follow that insn in the same basic block), 4432: - its final value can be calculated (this condition is different 4433: than the one above in record_giv) 4434: - no assignments to the biv occur during the giv's lifetime. */ 4435: 4436: #if 0 4437: /* This is only called now when replaceable is known to be false. */ 4438: /* Clear replaceable, so that it won't confuse final_giv_value. */ 4439: v->replaceable = 0; 4440: #endif 4441: 4442: if ((final_value = final_giv_value (v, loop_start, loop_end)) 4443: && (v->always_computable || last_use_this_basic_block (v->dest_reg, v->insn))) 4444: { 4445: int biv_increment_seen = 0; 4446: rtx p = v->insn; 4447: rtx last_giv_use; 4448: 4449: v->replaceable = 1; 4450: 4451: /* When trying to determine whether or not a biv increment occurs 4452: during the lifetime of the giv, we can ignore uses of the variable 4453: outside the loop because final_value is true. Hence we can not 4454: use regno_last_uid and regno_first_uid as above in record_giv. */ 4455: 4456: /* Search the loop to determine whether any assignments to the 4457: biv occur during the giv's lifetime. Start with the insn 4458: that sets the giv, and search around the loop until we come 4459: back to that insn again. 4460: 4461: Also fail if there is a jump within the giv's lifetime that jumps 4462: to somewhere outside the lifetime but still within the loop. This 4463: catches spaghetti code where the execution order is not linear, and 4464: hence the above test fails. Here we assume that the giv lifetime 4465: does not extend from one iteration of the loop to the next, so as 4466: to make the test easier. Since the lifetime isn't known yet, 4467: this requires two loops. See also record_giv above. */ 4468: 4469: last_giv_use = v->insn; 4470: 4471: while (1) 4472: { 4473: p = NEXT_INSN (p); 4474: if (p == loop_end) 4475: p = NEXT_INSN (loop_start); 4476: if (p == v->insn) 4477: break; 4478: 4479: if (GET_CODE (p) == INSN || GET_CODE (p) == JUMP_INSN 4480: || GET_CODE (p) == CALL_INSN) 4481: { 4482: if (biv_increment_seen) 4483: { 4484: if (reg_mentioned_p (v->dest_reg, PATTERN (p))) 4485: { 4486: v->replaceable = 0; 4487: v->not_replaceable = 1; 4488: break; 4489: } 4490: } 4491: else if (GET_CODE (PATTERN (p)) == SET 4492: && SET_DEST (PATTERN (p)) == v->src_reg) 4493: biv_increment_seen = 1; 4494: else if (reg_mentioned_p (v->dest_reg, PATTERN (p))) 4495: last_giv_use = p; 4496: } 4497: } 4498: 4499: /* Now that the lifetime of the giv is known, check for branches 4500: from within the lifetime to outside the lifetime if it is still 4501: replaceable. */ 4502: 4503: if (v->replaceable) 4504: { 4505: p = v->insn; 4506: while (1) 4507: { 4508: p = NEXT_INSN (p); 4509: if (p == loop_end) 4510: p = NEXT_INSN (loop_start); 4511: if (p == last_giv_use) 4512: break; 4513: 4514: if (GET_CODE (p) == JUMP_INSN && JUMP_LABEL (p) 4515: && LABEL_NAME (JUMP_LABEL (p)) 4516: && ((INSN_LUID (JUMP_LABEL (p)) < INSN_LUID (v->insn) 4517: && INSN_LUID (JUMP_LABEL (p)) > INSN_LUID (loop_start)) 4518: || (INSN_LUID (JUMP_LABEL (p)) > INSN_LUID (last_giv_use) 4519: && INSN_LUID (JUMP_LABEL (p)) < INSN_LUID (loop_end)))) 4520: { 4521: v->replaceable = 0; 4522: v->not_replaceable = 1; 4523: 4524: if (loop_dump_stream) 4525: fprintf (loop_dump_stream, 4526: "Found branch outside giv lifetime.\n"); 4527: 4528: break; 4529: } 4530: } 4531: } 4532: 4533: /* If it is replaceable, then save the final value. */ 4534: if (v->replaceable) 4535: v->final_value = final_value; 4536: } 4537: 4538: if (loop_dump_stream && v->replaceable) 4539: fprintf (loop_dump_stream, "Insn %d: giv reg %d final_value replaceable\n", 4540: INSN_UID (v->insn), REGNO (v->dest_reg)); 4541: } 4542: 4543: /* Update the status of whether a giv can derive other givs. 4544: 4545: We need to do something special if there is or may be an update to the biv 4546: between the time the giv is defined and the time it is used to derive 4547: another giv. 4548: 4549: In addition, a giv that is only conditionally set is not allowed to 4550: derive another giv once a label has been passed. 4551: 4552: The cases we look at are when a label or an update to a biv is passed. */ 4553: 4554: static void 4555: update_giv_derive (p) 4556: rtx p; 4557: { 4558: struct iv_class *bl; 4559: struct induction *biv, *giv; 4560: rtx tem; 4561: int dummy; 4562: 4563: /* Search all IV classes, then all bivs, and finally all givs. 4564: 1.1.1.3 root 4565: There are three cases we are concerned with. First we have the situation 1.1 root 4566: of a giv that is only updated conditionally. In that case, it may not 4567: derive any givs after a label is passed. 4568: 4569: The second case is when a biv update occurs, or may occur, after the 4570: definition of a giv. For certain biv updates (see below) that are 4571: known to occur between the giv definition and use, we can adjust the 4572: giv definition. For others, or when the biv update is conditional, 4573: we must prevent the giv from deriving any other givs. There are two 4574: sub-cases within this case. 4575: 4576: If this is a label, we are concerned with any biv update that is done 4577: conditionally, since it may be done after the giv is defined followed by 4578: a branch here (actually, we need to pass both a jump and a label, but 4579: this extra tracking doesn't seem worth it). 4580: 1.1.1.3 root 4581: If this is a jump, we are concerned about any biv update that may be 4582: executed multiple times. We are actually only concerned about 4583: backward jumps, but it is probably not worth performing the test 4584: on the jump again here. 4585: 4586: If this is a biv update, we must adjust the giv status to show that a 1.1 root 4587: subsequent biv update was performed. If this adjustment cannot be done, 4588: the giv cannot derive further givs. */ 4589: 4590: for (bl = loop_iv_list; bl; bl = bl->next) 4591: for (biv = bl->biv; biv; biv = biv->next_iv) 1.1.1.3 root 4592: if (GET_CODE (p) == CODE_LABEL || GET_CODE (p) == JUMP_INSN 4593: || biv->insn == p) 1.1 root 4594: { 4595: for (giv = bl->giv; giv; giv = giv->next_iv) 4596: { 4597: /* If cant_derive is already true, there is no point in 4598: checking all of these conditions again. */ 4599: if (giv->cant_derive) 4600: continue; 4601: 4602: /* If this giv is conditionally set and we have passed a label, 4603: it cannot derive anything. */ 4604: if (GET_CODE (p) == CODE_LABEL && ! giv->always_computable) 4605: giv->cant_derive = 1; 4606: 4607: /* Skip givs that have mult_val == 0, since 4608: they are really invariants. Also skip those that are 4609: replaceable, since we know their lifetime doesn't contain 4610: any biv update. */ 4611: else if (giv->mult_val == const0_rtx || giv->replaceable) 4612: continue; 4613: 4614: /* The only way we can allow this giv to derive another 4615: is if this is a biv increment and we can form the product 4616: of biv->add_val and giv->mult_val. In this case, we will 4617: be able to compute a compensation. */ 4618: else if (biv->insn == p) 4619: { 1.1.1.2 root 4620: tem = 0; 4621: 4622: if (biv->mult_val == const1_rtx) 4623: tem = simplify_giv_expr (gen_rtx (MULT, giv->mode, 4624: biv->add_val, 4625: giv->mult_val), 4626: &dummy); 4627: 4628: if (tem && giv->derive_adjustment) 4629: tem = simplify_giv_expr (gen_rtx (PLUS, giv->mode, tem, 4630: giv->derive_adjustment), 4631: &dummy); 4632: if (tem) 1.1 root 4633: giv->derive_adjustment = tem; 4634: else 4635: giv->cant_derive = 1; 4636: } 1.1.1.3 root 4637: else if ((GET_CODE (p) == CODE_LABEL && ! biv->always_computable) 4638: || (GET_CODE (p) == JUMP_INSN && biv->maybe_multiple)) 1.1 root 4639: giv->cant_derive = 1; 4640: } 4641: } 4642: } 4643: 4644: /* Check whether an insn is an increment legitimate for a basic induction var. 1.1.1.4 ! root 4645: X is the source of insn P. 1.1 root 4646: DEST_REG is the putative biv, also the destination of the insn. 4647: We accept patterns of these forms: 1.1.1.4 ! root 4648: REG = REG + INVARIANT (includes REG = REG - CONSTANT) 1.1 root 4649: REG = INVARIANT + REG 4650: 4651: If X is suitable, we return 1, set *MULT_VAL to CONST1_RTX, 4652: and store the additive term into *INC_VAL. 4653: 4654: If X is an assignment of an invariant into DEST_REG, we set 4655: *MULT_VAL to CONST0_RTX, and store the invariant into *INC_VAL. 4656: 1.1.1.4 ! root 4657: We also want to detect a BIV when it corresponds to a variable ! 4658: whose mode was promoted via PROMOTED_MODE. In that case, an increment ! 4659: of the variable may be a PLUS that adds a SUBREG of that variable to ! 4660: an invariant and then sign- or zero-extends the result of the PLUS ! 4661: into the variable. ! 4662: ! 4663: Most GIVs in such cases will be in the promoted mode, since that is the ! 4664: probably the natural computation mode (and almost certainly the mode ! 4665: used for addresses) on the machine. So we view the pseudo-reg containing ! 4666: the variable as the BIV, as if it were simply incremented. ! 4667: ! 4668: Note that treating the entire pseudo as a BIV will result in making ! 4669: simple increments to any GIVs based on it. However, if the variable ! 4670: overflows in its declared mode but not its promoted mode, the result will ! 4671: be incorrect. This is acceptable if the variable is signed, since ! 4672: overflows in such cases are undefined, but not if it is unsigned, since ! 4673: those overflows are defined. So we only check for SIGN_EXTEND and ! 4674: not ZERO_EXTEND. ! 4675: ! 4676: If we cannot find a biv, we return 0. */ 1.1 root 4677: 4678: static int 1.1.1.4 ! root 4679: basic_induction_var (x, dest_reg, p, inc_val, mult_val) 1.1 root 4680: register rtx x; 1.1.1.4 ! root 4681: rtx p; 1.1 root 4682: rtx dest_reg; 4683: rtx *inc_val; 4684: rtx *mult_val; 4685: { 4686: register enum rtx_code code; 4687: rtx arg; 1.1.1.4 ! root 4688: rtx insn, set = 0; 1.1 root 4689: 4690: code = GET_CODE (x); 4691: switch (code) 4692: { 4693: case PLUS: 1.1.1.4 ! root 4694: if (XEXP (x, 0) == dest_reg ! 4695: || (GET_CODE (XEXP (x, 0)) == SUBREG ! 4696: && SUBREG_PROMOTED_VAR_P (XEXP (x, 0)) ! 4697: && SUBREG_REG (XEXP (x, 0)) == dest_reg)) 1.1 root 4698: arg = XEXP (x, 1); 1.1.1.4 ! root 4699: else if (XEXP (x, 1) == dest_reg ! 4700: || (GET_CODE (XEXP (x, 1)) == SUBREG ! 4701: && SUBREG_PROMOTED_VAR_P (XEXP (x, 1)) ! 4702: && SUBREG_REG (XEXP (x, 1)) == dest_reg)) 1.1 root 4703: arg = XEXP (x, 0); 4704: else 4705: return 0; 4706: 4707: if (invariant_p (arg) != 1) 4708: return 0; 4709: 1.1.1.4 ! root 4710: *inc_val = convert_to_mode (GET_MODE (dest_reg), arg, 0);; 1.1 root 4711: *mult_val = const1_rtx; 4712: return 1; 4713: 1.1.1.4 ! root 4714: case SUBREG: ! 4715: /* If this is a SUBREG for a promoted variable, check the inner ! 4716: value. */ ! 4717: if (SUBREG_PROMOTED_VAR_P (x)) ! 4718: return basic_induction_var (SUBREG_REG (x), dest_reg, p, ! 4719: inc_val, mult_val); 1.1 root 4720: 1.1.1.4 ! root 4721: case REG: ! 4722: /* If this register is assigned in the previous insn, look at its ! 4723: source, but don't go outside the loop or past a label. */ ! 4724: ! 4725: for (insn = PREV_INSN (p); ! 4726: (insn && GET_CODE (insn) == NOTE ! 4727: && NOTE_LINE_NUMBER (insn) != NOTE_INSN_LOOP_BEG); ! 4728: insn = PREV_INSN (insn)) ! 4729: ; ! 4730: ! 4731: if (insn) ! 4732: set = single_set (insn); ! 4733: ! 4734: if (set != 0 && SET_DEST (set) == x) ! 4735: return basic_induction_var (SET_SRC (set), dest_reg, insn, ! 4736: inc_val, mult_val); ! 4737: /* ... fall through ... */ 1.1 root 4738: 4739: /* Can accept constant setting of biv only when inside inner most loop. 4740: Otherwise, a biv of an inner loop may be incorrectly recognized 4741: as a biv of the outer loop, 4742: causing code to be moved INTO the inner loop. */ 4743: case MEM: 4744: if (invariant_p (x) != 1) 4745: return 0; 4746: case CONST_INT: 4747: case SYMBOL_REF: 4748: case CONST: 4749: if (loops_enclosed == 1) 4750: { 1.1.1.4 ! root 4751: *inc_val = convert_to_mode (GET_MODE (dest_reg), x, 0);; 1.1 root 4752: *mult_val = const0_rtx; 4753: return 1; 4754: } 4755: else 4756: return 0; 4757: 1.1.1.4 ! root 4758: case SIGN_EXTEND: ! 4759: return basic_induction_var (XEXP (x, 0), dest_reg, p, ! 4760: inc_val, mult_val); ! 4761: case ASHIFTRT: ! 4762: /* Similar, since this can be a sign extension. */ ! 4763: for (insn = PREV_INSN (p); ! 4764: (insn && GET_CODE (insn) == NOTE ! 4765: && NOTE_LINE_NUMBER (insn) != NOTE_INSN_LOOP_BEG); ! 4766: insn = PREV_INSN (insn)) ! 4767: ; ! 4768: ! 4769: if (insn) ! 4770: set = single_set (insn); ! 4771: ! 4772: if (set && SET_DEST (set) == XEXP (x, 0) ! 4773: && GET_CODE (XEXP (x, 1)) == CONST_INT ! 4774: && INTVAL (XEXP (x, 1)) >= 0 ! 4775: && GET_CODE (SET_SRC (set)) == ASHIFT ! 4776: && XEXP (x, 1) == XEXP (SET_SRC (set), 1)) ! 4777: return basic_induction_var (XEXP (SET_SRC (set), 0), dest_reg, insn, ! 4778: inc_val, mult_val); ! 4779: return 0; ! 4780: 1.1 root 4781: default: 4782: return 0; 4783: } 4784: } 4785: 4786: /* A general induction variable (giv) is any quantity that is a linear 4787: function of a basic induction variable, 4788: i.e. giv = biv * mult_val + add_val. 4789: The coefficients can be any loop invariant quantity. 4790: A giv need not be computed directly from the biv; 4791: it can be computed by way of other givs. */ 4792: 4793: /* Determine whether X computes a giv. 4794: If it does, return a nonzero value 4795: which is the benefit from eliminating the computation of X; 4796: set *SRC_REG to the register of the biv that it is computed from; 4797: set *ADD_VAL and *MULT_VAL to the coefficients, 4798: such that the value of X is biv * mult + add; */ 4799: 4800: static int 4801: general_induction_var (x, src_reg, add_val, mult_val) 4802: rtx x; 4803: rtx *src_reg; 4804: rtx *add_val; 4805: rtx *mult_val; 4806: { 4807: rtx orig_x = x; 4808: int benefit = 0; 4809: char *storage; 4810: 4811: /* If this is an invariant, forget it, it isn't a giv. */ 4812: if (invariant_p (x) == 1) 4813: return 0; 4814: 4815: /* See if the expression could be a giv and get its form. 4816: Mark our place on the obstack in case we don't find a giv. */ 4817: storage = (char *) oballoc (0); 4818: x = simplify_giv_expr (x, &benefit); 4819: if (x == 0) 4820: { 4821: obfree (storage); 4822: return 0; 4823: } 4824: 4825: switch (GET_CODE (x)) 4826: { 4827: case USE: 4828: case CONST_INT: 4829: /* Since this is now an invariant and wasn't before, it must be a giv 4830: with MULT_VAL == 0. It doesn't matter which BIV we associate this 4831: with. */ 4832: *src_reg = loop_iv_list->biv->dest_reg; 4833: *mult_val = const0_rtx; 4834: *add_val = x; 4835: break; 4836: 4837: case REG: 4838: /* This is equivalent to a BIV. */ 4839: *src_reg = x; 4840: *mult_val = const1_rtx; 4841: *add_val = const0_rtx; 4842: break; 4843: 4844: case PLUS: 4845: /* Either (plus (biv) (invar)) or 4846: (plus (mult (biv) (invar_1)) (invar_2)). */ 4847: if (GET_CODE (XEXP (x, 0)) == MULT) 4848: { 4849: *src_reg = XEXP (XEXP (x, 0), 0); 4850: *mult_val = XEXP (XEXP (x, 0), 1); 4851: } 4852: else 4853: { 4854: *src_reg = XEXP (x, 0); 4855: *mult_val = const1_rtx; 4856: } 4857: *add_val = XEXP (x, 1); 4858: break; 4859: 4860: case MULT: 4861: /* ADD_VAL is zero. */ 4862: *src_reg = XEXP (x, 0); 4863: *mult_val = XEXP (x, 1); 4864: *add_val = const0_rtx; 4865: break; 4866: 4867: default: 4868: abort (); 4869: } 4870: 4871: /* Remove any enclosing USE from ADD_VAL and MULT_VAL (there will be 4872: unless they are CONST_INT). */ 4873: if (GET_CODE (*add_val) == USE) 4874: *add_val = XEXP (*add_val, 0); 4875: if (GET_CODE (*mult_val) == USE) 4876: *mult_val = XEXP (*mult_val, 0); 4877: 1.1.1.3 root 4878: benefit += rtx_cost (orig_x, SET); 1.1 root 4879: 4880: /* Always return some benefit if this is a giv so it will be detected 4881: as such. This allows elimination of bivs that might otherwise 4882: not be eliminated. */ 4883: return benefit == 0 ? 1 : benefit; 4884: } 4885: 4886: /* Given an expression, X, try to form it as a linear function of a biv. 4887: We will canonicalize it to be of the form 4888: (plus (mult (BIV) (invar_1)) 4889: (invar_2)) 1.1.1.3 root 4890: with possible degeneracies. 1.1 root 4891: 4892: The invariant expressions must each be of a form that can be used as a 4893: machine operand. We surround then with a USE rtx (a hack, but localized 4894: and certainly unambiguous!) if not a CONST_INT for simplicity in this 4895: routine; it is the caller's responsibility to strip them. 4896: 4897: If no such canonicalization is possible (i.e., two biv's are used or an 4898: expression that is neither invariant nor a biv or giv), this routine 4899: returns 0. 4900: 4901: For a non-zero return, the result will have a code of CONST_INT, USE, 4902: REG (for a BIV), PLUS, or MULT. No other codes will occur. 4903: 4904: *BENEFIT will be incremented by the benefit of any sub-giv encountered. */ 4905: 4906: static rtx 4907: simplify_giv_expr (x, benefit) 4908: rtx x; 4909: int *benefit; 4910: { 4911: enum machine_mode mode = GET_MODE (x); 4912: rtx arg0, arg1; 4913: rtx tem; 4914: 4915: /* If this is not an integer mode, or if we cannot do arithmetic in this 4916: mode, this can't be a giv. */ 4917: if (mode != VOIDmode 4918: && (GET_MODE_CLASS (mode) != MODE_INT 1.1.1.4 ! root 4919: || GET_MODE_BITSIZE (mode) > HOST_BITS_PER_WIDE_INT)) 1.1 root 4920: return 0; 4921: 4922: switch (GET_CODE (x)) 4923: { 4924: case PLUS: 4925: arg0 = simplify_giv_expr (XEXP (x, 0), benefit); 4926: arg1 = simplify_giv_expr (XEXP (x, 1), benefit); 4927: if (arg0 == 0 || arg1 == 0) 4928: return 0; 4929: 4930: /* Put constant last, CONST_INT last if both constant. */ 4931: if ((GET_CODE (arg0) == USE 4932: || GET_CODE (arg0) == CONST_INT) 4933: && GET_CODE (arg1) != CONST_INT) 4934: tem = arg0, arg0 = arg1, arg1 = tem; 4935: 4936: /* Handle addition of zero, then addition of an invariant. */ 4937: if (arg1 == const0_rtx) 4938: return arg0; 4939: else if (GET_CODE (arg1) == CONST_INT || GET_CODE (arg1) == USE) 4940: switch (GET_CODE (arg0)) 4941: { 4942: case CONST_INT: 4943: case USE: 4944: /* Both invariant. Only valid if sum is machine operand. 4945: First strip off possible USE on first operand. */ 4946: if (GET_CODE (arg0) == USE) 4947: arg0 = XEXP (arg0, 0); 4948: 4949: tem = 0; 4950: if (CONSTANT_P (arg0) && GET_CODE (arg1) == CONST_INT) 4951: { 4952: tem = plus_constant (arg0, INTVAL (arg1)); 4953: if (GET_CODE (tem) != CONST_INT) 4954: tem = gen_rtx (USE, mode, tem); 4955: } 4956: 4957: return tem; 4958: 4959: case REG: 4960: case MULT: 4961: /* biv + invar or mult + invar. Return sum. */ 4962: return gen_rtx (PLUS, mode, arg0, arg1); 4963: 4964: case PLUS: 4965: /* (a + invar_1) + invar_2. Associate. */ 4966: return simplify_giv_expr (gen_rtx (PLUS, mode, 4967: XEXP (arg0, 0), 4968: gen_rtx (PLUS, mode, 4969: XEXP (arg0, 1), arg1)), 4970: benefit); 4971: 4972: default: 4973: abort (); 4974: } 4975: 4976: /* Each argument must be either REG, PLUS, or MULT. Convert REG to 4977: MULT to reduce cases. */ 4978: if (GET_CODE (arg0) == REG) 4979: arg0 = gen_rtx (MULT, mode, arg0, const1_rtx); 4980: if (GET_CODE (arg1) == REG) 4981: arg1 = gen_rtx (MULT, mode, arg1, const1_rtx); 4982: 4983: /* Now have PLUS + PLUS, PLUS + MULT, MULT + PLUS, or MULT + MULT. 4984: Put a MULT first, leaving PLUS + PLUS, MULT + PLUS, or MULT + MULT. 4985: Recurse to associate the second PLUS. */ 4986: if (GET_CODE (arg1) == MULT) 4987: tem = arg0, arg0 = arg1, arg1 = tem; 4988: 4989: if (GET_CODE (arg1) == PLUS) 4990: return simplify_giv_expr (gen_rtx (PLUS, mode, 4991: gen_rtx (PLUS, mode, 4992: arg0, XEXP (arg1, 0)), 4993: XEXP (arg1, 1)), 4994: benefit); 4995: 4996: /* Now must have MULT + MULT. Distribute if same biv, else not giv. */ 4997: if (GET_CODE (arg0) != MULT || GET_CODE (arg1) != MULT) 4998: abort (); 4999: 5000: if (XEXP (arg0, 0) != XEXP (arg1, 0)) 5001: return 0; 5002: 5003: return simplify_giv_expr (gen_rtx (MULT, mode, 5004: XEXP (arg0, 0), 5005: gen_rtx (PLUS, mode, 5006: XEXP (arg0, 1), 5007: XEXP (arg1, 1))), 5008: benefit); 5009: 5010: case MINUS: 5011: /* Handle "a - b" as "a + b * (-1)". */ 5012: return simplify_giv_expr (gen_rtx (PLUS, mode, 5013: XEXP (x, 0), 5014: gen_rtx (MULT, mode, 1.1.1.4 ! root 5015: XEXP (x, 1), constm1_rtx)), 1.1 root 5016: benefit); 5017: 5018: case MULT: 5019: arg0 = simplify_giv_expr (XEXP (x, 0), benefit); 5020: arg1 = simplify_giv_expr (XEXP (x, 1), benefit); 5021: if (arg0 == 0 || arg1 == 0) 5022: return 0; 5023: 5024: /* Put constant last, CONST_INT last if both constant. */ 5025: if ((GET_CODE (arg0) == USE || GET_CODE (arg0) == CONST_INT) 5026: && GET_CODE (arg1) != CONST_INT) 5027: tem = arg0, arg0 = arg1, arg1 = tem; 5028: 5029: /* If second argument is not now constant, not giv. */ 5030: if (GET_CODE (arg1) != USE && GET_CODE (arg1) != CONST_INT) 5031: return 0; 5032: 5033: /* Handle multiply by 0 or 1. */ 5034: if (arg1 == const0_rtx) 5035: return const0_rtx; 5036: 5037: else if (arg1 == const1_rtx) 5038: return arg0; 5039: 5040: switch (GET_CODE (arg0)) 5041: { 5042: case REG: 5043: /* biv * invar. Done. */ 5044: return gen_rtx (MULT, mode, arg0, arg1); 5045: 5046: case CONST_INT: 5047: /* Product of two constants. */ 1.1.1.4 ! root 5048: return GEN_INT (INTVAL (arg0) * INTVAL (arg1)); 1.1 root 5049: 5050: case USE: 5051: /* invar * invar. Not giv. */ 5052: return 0; 5053: 5054: case MULT: 5055: /* (a * invar_1) * invar_2. Associate. */ 5056: return simplify_giv_expr (gen_rtx (MULT, mode, 5057: XEXP (arg0, 0), 5058: gen_rtx (MULT, mode, 5059: XEXP (arg0, 1), arg1)), 5060: benefit); 5061: 5062: case PLUS: 5063: /* (a + invar_1) * invar_2. Distribute. */ 5064: return simplify_giv_expr (gen_rtx (PLUS, mode, 5065: gen_rtx (MULT, mode, 5066: XEXP (arg0, 0), arg1), 5067: gen_rtx (MULT, mode, 5068: XEXP (arg0, 1), arg1)), 5069: benefit); 5070: 5071: default: 5072: abort (); 5073: } 5074: 5075: case ASHIFT: 5076: case LSHIFT: 5077: /* Shift by constant is multiply by power of two. */ 5078: if (GET_CODE (XEXP (x, 1)) != CONST_INT) 5079: return 0; 5080: 5081: return simplify_giv_expr (gen_rtx (MULT, mode, 5082: XEXP (x, 0), 1.1.1.4 ! root 5083: GEN_INT ((HOST_WIDE_INT) 1 ! 5084: << INTVAL (XEXP (x, 1)))), 1.1 root 5085: benefit); 5086: 5087: case NEG: 5088: /* "-a" is "a * (-1)" */ 1.1.1.4 ! root 5089: return simplify_giv_expr (gen_rtx (MULT, mode, XEXP (x, 0), constm1_rtx), 1.1 root 5090: benefit); 5091: 5092: case NOT: 5093: /* "~a" is "-a - 1". Silly, but easy. */ 5094: return simplify_giv_expr (gen_rtx (MINUS, mode, 5095: gen_rtx (NEG, mode, XEXP (x, 0)), 5096: const1_rtx), 5097: benefit); 5098: 5099: case USE: 5100: /* Already in proper form for invariant. */ 5101: return x; 5102: 5103: case REG: 5104: /* If this is a new register, we can't deal with it. */ 5105: if (REGNO (x) >= max_reg_before_loop) 5106: return 0; 5107: 5108: /* Check for biv or giv. */ 5109: switch (reg_iv_type[REGNO (x)]) 5110: { 5111: case BASIC_INDUCT: 5112: return x; 5113: case GENERAL_INDUCT: 5114: { 5115: struct induction *v = reg_iv_info[REGNO (x)]; 5116: 5117: /* Form expression from giv and add benefit. Ensure this giv 5118: can derive another and subtract any needed adjustment if so. */ 5119: *benefit += v->benefit; 5120: if (v->cant_derive) 5121: return 0; 5122: 5123: tem = gen_rtx (PLUS, mode, gen_rtx (MULT, mode, 5124: v->src_reg, v->mult_val), 5125: v->add_val); 5126: if (v->derive_adjustment) 5127: tem = gen_rtx (MINUS, mode, tem, v->derive_adjustment); 5128: return simplify_giv_expr (tem, benefit); 5129: } 5130: } 5131: 5132: /* Fall through to general case. */ 5133: default: 5134: /* If invariant, return as USE (unless CONST_INT). 5135: Otherwise, not giv. */ 5136: if (GET_CODE (x) == USE) 5137: x = XEXP (x, 0); 5138: 5139: if (invariant_p (x) == 1) 5140: { 5141: if (GET_CODE (x) == CONST_INT) 5142: return x; 5143: else 5144: return gen_rtx (USE, mode, x); 5145: } 5146: else 5147: return 0; 5148: } 5149: } 5150: 5151: /* Help detect a giv that is calculated by several consecutive insns; 5152: for example, 5153: giv = biv * M 5154: giv = giv + A 5155: The caller has already identified the first insn P as having a giv as dest; 5156: we check that all other insns that set the same register follow 5157: immediately after P, that they alter nothing else, 5158: and that the result of the last is still a giv. 5159: 5160: The value is 0 if the reg set in P is not really a giv. 5161: Otherwise, the value is the amount gained by eliminating 5162: all the consecutive insns that compute the value. 5163: 5164: FIRST_BENEFIT is the amount gained by eliminating the first insn, P. 5165: SRC_REG is the reg of the biv; DEST_REG is the reg of the giv. 5166: 5167: The coefficients of the ultimate giv value are stored in 5168: *MULT_VAL and *ADD_VAL. */ 5169: 5170: static int 5171: consec_sets_giv (first_benefit, p, src_reg, dest_reg, 5172: add_val, mult_val) 5173: int first_benefit; 5174: rtx p; 5175: rtx src_reg; 5176: rtx dest_reg; 5177: rtx *add_val; 5178: rtx *mult_val; 5179: { 5180: int count; 5181: enum rtx_code code; 5182: int benefit; 5183: rtx temp; 5184: rtx set; 5185: 5186: /* Indicate that this is a giv so that we can update the value produced in 5187: each insn of the multi-insn sequence. 5188: 5189: This induction structure will be used only by the call to 5190: general_induction_var below, so we can allocate it on our stack. 5191: If this is a giv, our caller will replace the induct var entry with 5192: a new induction structure. */ 5193: struct induction *v 5194: = (struct induction *) alloca (sizeof (struct induction)); 5195: v->src_reg = src_reg; 5196: v->mult_val = *mult_val; 5197: v->add_val = *add_val; 5198: v->benefit = first_benefit; 5199: v->cant_derive = 0; 5200: v->derive_adjustment = 0; 5201: 5202: reg_iv_type[REGNO (dest_reg)] = GENERAL_INDUCT; 5203: reg_iv_info[REGNO (dest_reg)] = v; 5204: 5205: count = n_times_set[REGNO (dest_reg)] - 1; 5206: 5207: while (count > 0) 5208: { 5209: p = NEXT_INSN (p); 5210: code = GET_CODE (p); 5211: 5212: /* If libcall, skip to end of call sequence. */ 1.1.1.4 ! root 5213: if (code == INSN && (temp = find_reg_note (p, REG_LIBCALL, NULL_RTX))) 1.1 root 5214: p = XEXP (temp, 0); 5215: 5216: if (code == INSN 5217: && (set = single_set (p)) 5218: && GET_CODE (SET_DEST (set)) == REG 5219: && SET_DEST (set) == dest_reg 5220: && ((benefit = general_induction_var (SET_SRC (set), &src_reg, 5221: add_val, mult_val)) 5222: /* Giv created by equivalent expression. */ 1.1.1.4 ! root 5223: || ((temp = find_reg_note (p, REG_EQUAL, NULL_RTX)) 1.1 root 5224: && (benefit = general_induction_var (XEXP (temp, 0), &src_reg, 5225: add_val, mult_val)))) 5226: && src_reg == v->src_reg) 5227: { 1.1.1.4 ! root 5228: if (find_reg_note (p, REG_RETVAL, NULL_RTX)) 1.1 root 5229: benefit += libcall_benefit (p); 5230: 5231: count--; 5232: v->mult_val = *mult_val; 5233: v->add_val = *add_val; 5234: v->benefit = benefit; 5235: } 5236: else if (code != NOTE) 5237: { 5238: /* Allow insns that set something other than this giv to a 5239: constant. Such insns are needed on machines which cannot 5240: include long constants and should not disqualify a giv. */ 5241: if (code == INSN 5242: && (set = single_set (p)) 5243: && SET_DEST (set) != dest_reg 5244: && CONSTANT_P (SET_SRC (set))) 5245: continue; 5246: 5247: reg_iv_type[REGNO (dest_reg)] = UNKNOWN_INDUCT; 5248: return 0; 5249: } 5250: } 5251: 5252: return v->benefit; 5253: } 5254: 5255: /* Return an rtx, if any, that expresses giv G2 as a function of the register 5256: represented by G1. If no such expression can be found, or it is clear that 5257: it cannot possibly be a valid address, 0 is returned. 5258: 5259: To perform the computation, we note that 5260: G1 = a * v + b and 5261: G2 = c * v + d 5262: where `v' is the biv. 5263: 5264: So G2 = (c/a) * G1 + (d - b*c/a) */ 5265: 5266: #ifdef ADDRESS_COST 5267: static rtx 5268: express_from (g1, g2) 5269: struct induction *g1, *g2; 5270: { 5271: rtx mult, add; 5272: 5273: /* The value that G1 will be multiplied by must be a constant integer. Also, 5274: the only chance we have of getting a valid address is if b*c/a (see above 5275: for notation) is also an integer. */ 5276: if (GET_CODE (g1->mult_val) != CONST_INT 5277: || GET_CODE (g2->mult_val) != CONST_INT 5278: || GET_CODE (g1->add_val) != CONST_INT 5279: || g1->mult_val == const0_rtx 5280: || INTVAL (g2->mult_val) % INTVAL (g1->mult_val) != 0) 5281: return 0; 5282: 1.1.1.4 ! root 5283: mult = GEN_INT (INTVAL (g2->mult_val) / INTVAL (g1->mult_val)); 1.1 root 5284: add = plus_constant (g2->add_val, - INTVAL (g1->add_val) * INTVAL (mult)); 5285: 5286: /* Form simplified final result. */ 5287: if (mult == const0_rtx) 5288: return add; 5289: else if (mult == const1_rtx) 5290: mult = g1->dest_reg; 5291: else 5292: mult = gen_rtx (MULT, g2->mode, g1->dest_reg, mult); 5293: 5294: if (add == const0_rtx) 5295: return mult; 5296: else 5297: return gen_rtx (PLUS, g2->mode, mult, add); 5298: } 5299: #endif 5300: 5301: /* Return 1 if giv G2 can be combined with G1. This means that G2 can use 5302: (either directly or via an address expression) a register used to represent 5303: G1. Set g2->new_reg to a represtation of G1 (normally just 5304: g1->dest_reg). */ 5305: 5306: static int 5307: combine_givs_p (g1, g2) 5308: struct induction *g1, *g2; 5309: { 5310: rtx tem; 5311: 5312: /* If these givs are identical, they can be combined. */ 5313: if (rtx_equal_p (g1->mult_val, g2->mult_val) 5314: && rtx_equal_p (g1->add_val, g2->add_val)) 5315: { 5316: g2->new_reg = g1->dest_reg; 5317: return 1; 5318: } 5319: 5320: #ifdef ADDRESS_COST 5321: /* If G2 can be expressed as a function of G1 and that function is valid 5322: as an address and no more expensive than using a register for G2, 5323: the expression of G2 in terms of G1 can be used. */ 5324: if (g2->giv_type == DEST_ADDR 5325: && (tem = express_from (g1, g2)) != 0 5326: && memory_address_p (g2->mem_mode, tem) 5327: && ADDRESS_COST (tem) <= ADDRESS_COST (*g2->location)) 5328: { 5329: g2->new_reg = tem; 5330: return 1; 5331: } 5332: #endif 5333: 5334: return 0; 5335: } 5336: 5337: /* Check all pairs of givs for iv_class BL and see if any can be combined with 5338: any other. If so, point SAME to the giv combined with and set NEW_REG to 5339: be an expression (in terms of the other giv's DEST_REG) equivalent to the 5340: giv. Also, update BENEFIT and related fields for cost/benefit analysis. */ 5341: 5342: static void 5343: combine_givs (bl) 5344: struct iv_class *bl; 5345: { 5346: struct induction *g1, *g2; 5347: int pass; 5348: 5349: for (g1 = bl->giv; g1; g1 = g1->next_iv) 5350: for (pass = 0; pass <= 1; pass++) 5351: for (g2 = bl->giv; g2; g2 = g2->next_iv) 5352: if (g1 != g2 5353: /* First try to combine with replaceable givs, then all givs. */ 5354: && (g1->replaceable || pass == 1) 5355: /* If either has already been combined or is to be ignored, can't 5356: combine. */ 5357: && ! g1->ignore && ! g2->ignore && ! g1->same && ! g2->same 5358: /* If something has been based on G2, G2 cannot itself be based 5359: on something else. */ 5360: && ! g2->combined_with 5361: && combine_givs_p (g1, g2)) 5362: { 5363: /* g2->new_reg set by `combine_givs_p' */ 5364: g2->same = g1; 5365: g1->combined_with = 1; 5366: g1->benefit += g2->benefit; 5367: /* ??? The new final_[bg]iv_value code does a much better job 5368: of finding replaceable giv's, and hence this code may no 5369: longer be necessary. */ 5370: if (! g2->replaceable && REG_USERVAR_P (g2->dest_reg)) 5371: g1->benefit -= copy_cost; 5372: g1->lifetime += g2->lifetime; 5373: g1->times_used += g2->times_used; 5374: 5375: if (loop_dump_stream) 5376: fprintf (loop_dump_stream, "giv at %d combined with giv at %d\n", 5377: INSN_UID (g2->insn), INSN_UID (g1->insn)); 5378: } 5379: } 5380: 5381: /* EMIT code before INSERT_BEFORE to set REG = B * M + A. */ 5382: 5383: void 5384: emit_iv_add_mult (b, m, a, reg, insert_before) 5385: rtx b; /* initial value of basic induction variable */ 5386: rtx m; /* multiplicative constant */ 5387: rtx a; /* additive constant */ 5388: rtx reg; /* destination register */ 5389: rtx insert_before; 5390: { 5391: rtx seq; 5392: rtx result; 5393: 5394: /* Prevent unexpected sharing of these rtx. */ 5395: a = copy_rtx (a); 5396: b = copy_rtx (b); 5397: 5398: /* Increase the lifetime of any invariants moved further in code. */ 5399: update_reg_last_use (a, insert_before); 5400: update_reg_last_use (b, insert_before); 5401: update_reg_last_use (m, insert_before); 5402: 5403: start_sequence (); 5404: result = expand_mult_add (b, reg, m, a, GET_MODE (reg), 0); 5405: if (reg != result) 5406: emit_move_insn (reg, result); 5407: seq = gen_sequence (); 5408: end_sequence (); 5409: 5410: emit_insn_before (seq, insert_before); 5411: } 5412: 5413: /* Test whether A * B can be computed without 5414: an actual multiply insn. Value is 1 if so. */ 5415: 5416: static int 5417: product_cheap_p (a, b) 5418: rtx a; 5419: rtx b; 5420: { 5421: int i; 5422: rtx tmp; 5423: struct obstack *old_rtl_obstack = rtl_obstack; 5424: char *storage = (char *) obstack_alloc (&temp_obstack, 0); 5425: int win = 1; 5426: 5427: /* If only one is constant, make it B. */ 5428: if (GET_CODE (a) == CONST_INT) 5429: tmp = a, a = b, b = tmp; 5430: 5431: /* If first constant, both constant, so don't need multiply. */ 5432: if (GET_CODE (a) == CONST_INT) 5433: return 1; 5434: 5435: /* If second not constant, neither is constant, so would need multiply. */ 5436: if (GET_CODE (b) != CONST_INT) 5437: return 0; 5438: 5439: /* One operand is constant, so might not need multiply insn. Generate the 5440: code for the multiply and see if a call or multiply, or long sequence 5441: of insns is generated. */ 5442: 5443: rtl_obstack = &temp_obstack; 5444: start_sequence (); 1.1.1.4 ! root 5445: expand_mult (GET_MODE (a), a, b, NULL_RTX, 0); 1.1 root 5446: tmp = gen_sequence (); 5447: end_sequence (); 5448: 5449: if (GET_CODE (tmp) == SEQUENCE) 5450: { 5451: if (XVEC (tmp, 0) == 0) 5452: win = 1; 5453: else if (XVECLEN (tmp, 0) > 3) 5454: win = 0; 5455: else 5456: for (i = 0; i < XVECLEN (tmp, 0); i++) 5457: { 5458: rtx insn = XVECEXP (tmp, 0, i); 5459: 5460: if (GET_CODE (insn) != INSN 5461: || (GET_CODE (PATTERN (insn)) == SET 5462: && GET_CODE (SET_SRC (PATTERN (insn))) == MULT) 5463: || (GET_CODE (PATTERN (insn)) == PARALLEL 5464: && GET_CODE (XVECEXP (PATTERN (insn), 0, 0)) == SET 5465: && GET_CODE (SET_SRC (XVECEXP (PATTERN (insn), 0, 0))) == MULT)) 5466: { 5467: win = 0; 5468: break; 5469: } 5470: } 5471: } 5472: else if (GET_CODE (tmp) == SET 5473: && GET_CODE (SET_SRC (tmp)) == MULT) 5474: win = 0; 5475: else if (GET_CODE (tmp) == PARALLEL 5476: && GET_CODE (XVECEXP (tmp, 0, 0)) == SET 5477: && GET_CODE (SET_SRC (XVECEXP (tmp, 0, 0))) == MULT) 5478: win = 0; 5479: 5480: /* Free any storage we obtained in generating this multiply and restore rtl 5481: allocation to its normal obstack. */ 5482: obstack_free (&temp_obstack, storage); 5483: rtl_obstack = old_rtl_obstack; 5484: 5485: return win; 5486: } 5487: 5488: /* Check to see if loop can be terminated by a "decrement and branch until 5489: zero" instruction. If so, add a REG_NONNEG note to the branch insn if so. 5490: Also try reversing an increment loop to a decrement loop 5491: to see if the optimization can be performed. 5492: Value is nonzero if optimization was performed. */ 5493: 5494: /* This is useful even if the architecture doesn't have such an insn, 5495: because it might change a loops which increments from 0 to n to a loop 5496: which decrements from n to 0. A loop that decrements to zero is usually 5497: faster than one that increments from zero. */ 5498: 5499: /* ??? This could be rewritten to use some of the loop unrolling procedures, 5500: such as approx_final_value, biv_total_increment, loop_iterations, and 5501: final_[bg]iv_value. */ 5502: 5503: static int 5504: check_dbra_loop (loop_end, insn_count, loop_start) 5505: rtx loop_end; 5506: int insn_count; 5507: rtx loop_start; 5508: { 5509: struct iv_class *bl; 5510: rtx reg; 5511: rtx jump_label; 5512: rtx final_value; 5513: rtx start_value; 5514: enum rtx_code branch_code; 5515: rtx new_add_val; 5516: rtx comparison; 5517: rtx before_comparison; 5518: rtx p; 5519: 5520: /* If last insn is a conditional branch, and the insn before tests a 5521: register value, try to optimize it. Otherwise, we can't do anything. */ 5522: 5523: comparison = get_condition_for_loop (PREV_INSN (loop_end)); 5524: if (comparison == 0) 5525: return 0; 5526: 5527: /* Check all of the bivs to see if the compare uses one of them. 5528: Skip biv's set more than once because we can't guarantee that 5529: it will be zero on the last iteration. Also skip if the biv is 5530: used between its update and the test insn. */ 5531: 5532: for (bl = loop_iv_list; bl; bl = bl->next) 5533: { 5534: if (bl->biv_count == 1 5535: && bl->biv->dest_reg == XEXP (comparison, 0) 5536: && ! reg_used_between_p (regno_reg_rtx[bl->regno], bl->biv->insn, 5537: PREV_INSN (PREV_INSN (loop_end)))) 5538: break; 5539: } 5540: 5541: if (! bl) 5542: return 0; 5543: 5544: /* Look for the case where the basic induction variable is always 5545: nonnegative, and equals zero on the last iteration. 5546: In this case, add a reg_note REG_NONNEG, which allows the 5547: m68k DBRA instruction to be used. */ 5548: 5549: if (((GET_CODE (comparison) == GT 5550: && GET_CODE (XEXP (comparison, 1)) == CONST_INT 5551: && INTVAL (XEXP (comparison, 1)) == -1) 5552: || (GET_CODE (comparison) == NE && XEXP (comparison, 1) == const0_rtx)) 5553: && GET_CODE (bl->biv->add_val) == CONST_INT 5554: && INTVAL (bl->biv->add_val) < 0) 5555: { 5556: /* Initial value must be greater than 0, 5557: init_val % -dec_value == 0 to ensure that it equals zero on 5558: the last iteration */ 5559: 5560: if (GET_CODE (bl->initial_value) == CONST_INT 5561: && INTVAL (bl->initial_value) > 0 5562: && (INTVAL (bl->initial_value) % 5563: (-INTVAL (bl->biv->add_val))) == 0) 5564: { 5565: /* register always nonnegative, add REG_NOTE to branch */ 5566: REG_NOTES (PREV_INSN (loop_end)) 1.1.1.4 ! root 5567: = gen_rtx (EXPR_LIST, REG_NONNEG, NULL_RTX, 1.1 root 5568: REG_NOTES (PREV_INSN (loop_end))); 5569: bl->nonneg = 1; 5570: 5571: return 1; 5572: } 5573: 5574: /* If the decrement is 1 and the value was tested as >= 0 before 5575: the loop, then we can safely optimize. */ 5576: for (p = loop_start; p; p = PREV_INSN (p)) 5577: { 5578: if (GET_CODE (p) == CODE_LABEL) 5579: break; 5580: if (GET_CODE (p) != JUMP_INSN) 5581: continue; 5582: 5583: before_comparison = get_condition_for_loop (p); 5584: if (before_comparison 5585: && XEXP (before_comparison, 0) == bl->biv->dest_reg 5586: && GET_CODE (before_comparison) == LT 5587: && XEXP (before_comparison, 1) == const0_rtx 5588: && ! reg_set_between_p (bl->biv->dest_reg, p, loop_start) 5589: && INTVAL (bl->biv->add_val) == -1) 5590: { 5591: REG_NOTES (PREV_INSN (loop_end)) 1.1.1.4 ! root 5592: = gen_rtx (EXPR_LIST, REG_NONNEG, NULL_RTX, 1.1 root 5593: REG_NOTES (PREV_INSN (loop_end))); 5594: bl->nonneg = 1; 5595: 5596: return 1; 5597: } 5598: } 5599: } 5600: else if (num_mem_sets <= 1) 5601: { 5602: /* Try to change inc to dec, so can apply above optimization. */ 5603: /* Can do this if: 5604: all registers modified are induction variables or invariant, 5605: all memory references have non-overlapping addresses 5606: (obviously true if only one write) 5607: allow 2 insns for the compare/jump at the end of the loop. */ 5608: int num_nonfixed_reads = 0; 5609: /* 1 if the iteration var is used only to count iterations. */ 5610: int no_use_except_counting = 0; 5611: 5612: for (p = loop_start; p != loop_end; p = NEXT_INSN (p)) 5613: if (GET_RTX_CLASS (GET_CODE (p)) == 'i') 5614: num_nonfixed_reads += count_nonfixed_reads (PATTERN (p)); 5615: 5616: if (bl->giv_count == 0 5617: && ! loop_number_exit_labels[uid_loop_num[INSN_UID (loop_start)]]) 5618: { 5619: rtx bivreg = regno_reg_rtx[bl->regno]; 5620: 5621: /* If there are no givs for this biv, and the only exit is the 5622: fall through at the end of the the loop, then 5623: see if perhaps there are no uses except to count. */ 5624: no_use_except_counting = 1; 5625: for (p = loop_start; p != loop_end; p = NEXT_INSN (p)) 5626: if (GET_RTX_CLASS (GET_CODE (p)) == 'i') 5627: { 5628: rtx set = single_set (p); 5629: 5630: if (set && GET_CODE (SET_DEST (set)) == REG 5631: && REGNO (SET_DEST (set)) == bl->regno) 5632: /* An insn that sets the biv is okay. */ 5633: ; 5634: else if (p == prev_nonnote_insn (prev_nonnote_insn (loop_end)) 5635: || p == prev_nonnote_insn (loop_end)) 5636: /* Don't bother about the end test. */ 5637: ; 5638: else if (reg_mentioned_p (bivreg, PATTERN (p))) 5639: /* Any other use of the biv is no good. */ 5640: { 5641: no_use_except_counting = 0; 5642: break; 5643: } 5644: } 5645: } 5646: 5647: /* This code only acts for innermost loops. Also it simplifies 5648: the memory address check by only reversing loops with 5649: zero or one memory access. 5650: Two memory accesses could involve parts of the same array, 5651: and that can't be reversed. */ 5652: 5653: if (num_nonfixed_reads <= 1 5654: && !loop_has_call 1.1.1.3 root 5655: && !loop_has_volatile 1.1 root 5656: && (no_use_except_counting 5657: || (bl->giv_count + bl->biv_count + num_mem_sets 5658: + num_movables + 2 == insn_count))) 5659: { 5660: rtx condition = get_condition_for_loop (PREV_INSN (loop_end)); 5661: int win; 5662: rtx tem; 5663: 5664: /* Loop can be reversed. */ 5665: if (loop_dump_stream) 5666: fprintf (loop_dump_stream, "Can reverse loop\n"); 5667: 5668: /* Now check other conditions: 5669: initial_value must be zero, 5670: final_value % add_val == 0, so that when reversed, the 5671: biv will be zero on the last iteration. 5672: 5673: This test can probably be improved since +/- 1 in the constant 5674: can be obtained by changing LT to LE and vice versa; this is 5675: confusing. */ 5676: 5677: if (comparison && bl->initial_value == const0_rtx 5678: && GET_CODE (XEXP (comparison, 1)) == CONST_INT 5679: /* LE gets turned into LT */ 5680: && GET_CODE (comparison) == LT 5681: && (INTVAL (XEXP (comparison, 1)) 5682: % INTVAL (bl->biv->add_val)) == 0) 5683: { 5684: /* Register will always be nonnegative, with value 5685: 0 on last iteration if loop reversed */ 5686: 5687: /* Save some info needed to produce the new insns. */ 5688: reg = bl->biv->dest_reg; 5689: jump_label = XEXP (SET_SRC (PATTERN (PREV_INSN (loop_end))), 1); 1.1.1.4 ! root 5690: new_add_val = GEN_INT (- INTVAL (bl->biv->add_val)); 1.1 root 5691: 5692: final_value = XEXP (comparison, 1); 1.1.1.4 ! root 5693: start_value = GEN_INT (INTVAL (XEXP (comparison, 1)) ! 5694: - INTVAL (bl->biv->add_val)); 1.1 root 5695: 5696: /* Initialize biv to start_value before loop start. 5697: The old initializing insn will be deleted as a 5698: dead store by flow.c. */ 5699: emit_insn_before (gen_move_insn (reg, start_value), loop_start); 5700: 5701: /* Add insn to decrement register, and delete insn 5702: that incremented the register. */ 5703: p = emit_insn_before (gen_add2_insn (reg, new_add_val), 5704: bl->biv->insn); 5705: delete_insn (bl->biv->insn); 5706: 5707: /* Update biv info to reflect its new status. */ 5708: bl->biv->insn = p; 5709: bl->initial_value = start_value; 5710: bl->biv->add_val = new_add_val; 5711: 5712: /* Inc LABEL_NUSES so that delete_insn will 5713: not delete the label. */ 5714: LABEL_NUSES (XEXP (jump_label, 0)) ++; 5715: 5716: /* Emit an insn after the end of the loop to set the biv's 5717: proper exit value if it is used anywhere outside the loop. */ 5718: if ((regno_last_uid[bl->regno] 5719: != INSN_UID (PREV_INSN (PREV_INSN (loop_end)))) 5720: || ! bl->init_insn 5721: || regno_first_uid[bl->regno] != INSN_UID (bl->init_insn)) 5722: emit_insn_after (gen_move_insn (reg, final_value), 5723: loop_end); 5724: 5725: /* Delete compare/branch at end of loop. */ 5726: delete_insn (PREV_INSN (loop_end)); 5727: delete_insn (PREV_INSN (loop_end)); 5728: 5729: /* Add new compare/branch insn at end of loop. */ 5730: start_sequence (); 1.1.1.4 ! root 5731: emit_cmp_insn (reg, const0_rtx, GE, NULL_RTX, ! 5732: GET_MODE (reg), 0, 0); 1.1 root 5733: emit_jump_insn (gen_bge (XEXP (jump_label, 0))); 5734: tem = gen_sequence (); 5735: end_sequence (); 5736: emit_jump_insn_before (tem, loop_end); 5737: 5738: for (tem = PREV_INSN (loop_end); 5739: tem && GET_CODE (tem) != JUMP_INSN; tem = PREV_INSN (tem)) 5740: ; 5741: if (tem) 5742: { 5743: JUMP_LABEL (tem) = XEXP (jump_label, 0); 5744: 5745: /* Increment of LABEL_NUSES done above. */ 5746: /* Register is now always nonnegative, 5747: so add REG_NONNEG note to the branch. */ 1.1.1.4 ! root 5748: REG_NOTES (tem) = gen_rtx (EXPR_LIST, REG_NONNEG, NULL_RTX, 1.1 root 5749: REG_NOTES (tem)); 5750: } 5751: 5752: bl->nonneg = 1; 5753: 5754: /* Mark that this biv has been reversed. Each giv which depends 5755: on this biv, and which is also live past the end of the loop 5756: will have to be fixed up. */ 5757: 5758: bl->reversed = 1; 5759: 5760: if (loop_dump_stream) 5761: fprintf (loop_dump_stream, 5762: "Reversed loop and added reg_nonneg\n"); 5763: 5764: return 1; 5765: } 5766: } 5767: } 5768: 5769: return 0; 5770: } 5771: 5772: /* Verify whether the biv BL appears to be eliminable, 5773: based on the insns in the loop that refer to it. 5774: LOOP_START is the first insn of the loop, and END is the end insn. 5775: 5776: If ELIMINATE_P is non-zero, actually do the elimination. 5777: 5778: THRESHOLD and INSN_COUNT are from loop_optimize and are used to 5779: determine whether invariant insns should be placed inside or at the 5780: start of the loop. */ 5781: 5782: static int 5783: maybe_eliminate_biv (bl, loop_start, end, eliminate_p, threshold, insn_count) 5784: struct iv_class *bl; 5785: rtx loop_start; 5786: rtx end; 5787: int eliminate_p; 5788: int threshold, insn_count; 5789: { 5790: rtx reg = bl->biv->dest_reg; 5791: rtx p, set; 5792: struct induction *v; 5793: 5794: /* Scan all insns in the loop, stopping if we find one that uses the 5795: biv in a way that we cannot eliminate. */ 5796: 5797: for (p = loop_start; p != end; p = NEXT_INSN (p)) 5798: { 5799: enum rtx_code code = GET_CODE (p); 5800: rtx where = threshold >= insn_count ? loop_start : p; 5801: 5802: if ((code == INSN || code == JUMP_INSN || code == CALL_INSN) 5803: && reg_mentioned_p (reg, PATTERN (p)) 5804: && ! maybe_eliminate_biv_1 (PATTERN (p), p, bl, eliminate_p, where)) 5805: { 5806: if (loop_dump_stream) 5807: fprintf (loop_dump_stream, 5808: "Cannot eliminate biv %d: biv used in insn %d.\n", 5809: bl->regno, INSN_UID (p)); 5810: break; 5811: } 5812: } 5813: 5814: if (p == end) 5815: { 5816: if (loop_dump_stream) 5817: fprintf (loop_dump_stream, "biv %d %s eliminated.\n", 5818: bl->regno, eliminate_p ? "was" : "can be"); 5819: return 1; 5820: } 5821: 5822: return 0; 5823: } 5824: 5825: /* If BL appears in X (part of the pattern of INSN), see if we can 5826: eliminate its use. If so, return 1. If not, return 0. 5827: 5828: If BIV does not appear in X, return 1. 5829: 5830: If ELIMINATE_P is non-zero, actually do the elimination. WHERE indicates 5831: where extra insns should be added. Depending on how many items have been 5832: moved out of the loop, it will either be before INSN or at the start of 5833: the loop. */ 5834: 5835: static int 5836: maybe_eliminate_biv_1 (x, insn, bl, eliminate_p, where) 5837: rtx x, insn; 5838: struct iv_class *bl; 5839: int eliminate_p; 5840: rtx where; 5841: { 5842: enum rtx_code code = GET_CODE (x); 5843: rtx reg = bl->biv->dest_reg; 5844: enum machine_mode mode = GET_MODE (reg); 5845: struct induction *v; 5846: rtx arg, new, tem; 5847: int arg_operand; 5848: char *fmt; 5849: int i, j; 5850: 5851: switch (code) 5852: { 5853: case REG: 5854: /* If we haven't already been able to do something with this BIV, 5855: we can't eliminate it. */ 5856: if (x == reg) 5857: return 0; 5858: return 1; 5859: 5860: case SET: 5861: /* If this sets the BIV, it is not a problem. */ 5862: if (SET_DEST (x) == reg) 5863: return 1; 5864: 5865: /* If this is an insn that defines a giv, it is also ok because 5866: it will go away when the giv is reduced. */ 5867: for (v = bl->giv; v; v = v->next_iv) 5868: if (v->giv_type == DEST_REG && SET_DEST (x) == v->dest_reg) 5869: return 1; 5870: 5871: #ifdef HAVE_cc0 5872: if (SET_DEST (x) == cc0_rtx && SET_SRC (x) == reg) 5873: { 5874: /* Can replace with any giv that was reduced and 5875: that has (MULT_VAL != 0) and (ADD_VAL == 0). 5876: Require a constant for MULT_VAL, so we know it's nonzero. */ 5877: 5878: for (v = bl->giv; v; v = v->next_iv) 5879: if (CONSTANT_P (v->mult_val) && v->mult_val != const0_rtx 5880: && v->add_val == const0_rtx 5881: && ! v->ignore && ! v->maybe_dead 5882: && v->mode == mode) 5883: { 5884: if (! eliminate_p) 5885: return 1; 5886: 5887: /* If the giv has the opposite direction of change, 5888: then reverse the comparison. */ 5889: if (INTVAL (v->mult_val) < 0) 5890: new = gen_rtx (COMPARE, GET_MODE (v->new_reg), 5891: const0_rtx, v->new_reg); 5892: else 5893: new = v->new_reg; 5894: 5895: /* We can probably test that giv's reduced reg. */ 5896: if (validate_change (insn, &SET_SRC (x), new, 0)) 5897: return 1; 5898: } 5899: 5900: /* Look for a giv with (MULT_VAL != 0) and (ADD_VAL != 0); 5901: replace test insn with a compare insn (cmp REDUCED_GIV ADD_VAL). 5902: Require a constant for MULT_VAL, so we know it's nonzero. */ 5903: 5904: for (v = bl->giv; v; v = v->next_iv) 5905: if (CONSTANT_P (v->mult_val) && v->mult_val != const0_rtx 5906: && ! v->ignore && ! v->maybe_dead 5907: && v->mode == mode) 5908: { 5909: if (! eliminate_p) 5910: return 1; 5911: 5912: /* If the giv has the opposite direction of change, 5913: then reverse the comparison. */ 5914: if (INTVAL (v->mult_val) < 0) 5915: new = gen_rtx (COMPARE, VOIDmode, copy_rtx (v->add_val), 5916: v->new_reg); 5917: else 5918: new = gen_rtx (COMPARE, VOIDmode, v->new_reg, 5919: copy_rtx (v->add_val)); 5920: 5921: /* Replace biv with the giv's reduced register. */ 5922: update_reg_last_use (v->add_val, insn); 5923: if (validate_change (insn, &SET_SRC (PATTERN (insn)), new, 0)) 5924: return 1; 5925: 5926: /* Insn doesn't support that constant or invariant. Copy it 5927: into a register (it will be a loop invariant.) */ 5928: tem = gen_reg_rtx (GET_MODE (v->new_reg)); 5929: 5930: emit_insn_before (gen_move_insn (tem, copy_rtx (v->add_val)), 5931: where); 5932: 5933: if (validate_change (insn, &SET_SRC (PATTERN (insn)), 5934: gen_rtx (COMPARE, VOIDmode, 5935: v->new_reg, tem), 0)) 5936: return 1; 5937: } 5938: } 5939: #endif 5940: break; 5941: 5942: case COMPARE: 5943: case EQ: case NE: 5944: case GT: case GE: case GTU: case GEU: 5945: case LT: case LE: case LTU: case LEU: 5946: /* See if either argument is the biv. */ 5947: if (XEXP (x, 0) == reg) 5948: arg = XEXP (x, 1), arg_operand = 1; 5949: else if (XEXP (x, 1) == reg) 5950: arg = XEXP (x, 0), arg_operand = 0; 5951: else 5952: break; 5953: 5954: if (CONSTANT_P (arg)) 5955: { 5956: /* First try to replace with any giv that has constant positive 5957: mult_val and constant add_val. We might be able to support 5958: negative mult_val, but it seems complex to do it in general. */ 5959: 5960: for (v = bl->giv; v; v = v->next_iv) 5961: if (CONSTANT_P (v->mult_val) && INTVAL (v->mult_val) > 0 5962: && CONSTANT_P (v->add_val) 5963: && ! v->ignore && ! v->maybe_dead 5964: && v->mode == mode) 5965: { 5966: if (! eliminate_p) 5967: return 1; 5968: 5969: /* Replace biv with the giv's reduced reg. */ 5970: XEXP (x, 1-arg_operand) = v->new_reg; 5971: 5972: /* If all constants are actually constant integers and 5973: the derived constant can be directly placed in the COMPARE, 5974: do so. */ 5975: if (GET_CODE (arg) == CONST_INT 5976: && GET_CODE (v->mult_val) == CONST_INT 5977: && GET_CODE (v->add_val) == CONST_INT 5978: && validate_change (insn, &XEXP (x, arg_operand), 1.1.1.4 ! root 5979: GEN_INT (INTVAL (arg) ! 5980: * INTVAL (v->mult_val) ! 5981: + INTVAL (v->add_val)), 0)) 1.1 root 5982: return 1; 5983: 5984: /* Otherwise, load it into a register. */ 5985: tem = gen_reg_rtx (mode); 5986: emit_iv_add_mult (arg, v->mult_val, v->add_val, tem, where); 5987: if (validate_change (insn, &XEXP (x, arg_operand), tem, 0)) 5988: return 1; 5989: 5990: /* If that failed, put back the change we made above. */ 5991: XEXP (x, 1-arg_operand) = reg; 5992: } 5993: 5994: /* Look for giv with positive constant mult_val and nonconst add_val. 5995: Insert insns to calculate new compare value. */ 5996: 5997: for (v = bl->giv; v; v = v->next_iv) 1.1.1.2 root 5998: if (CONSTANT_P (v->mult_val) && INTVAL (v->mult_val) > 0 1.1 root 5999: && ! v->ignore && ! v->maybe_dead 6000: && v->mode == mode) 6001: { 6002: rtx tem; 6003: 6004: if (! eliminate_p) 6005: return 1; 6006: 6007: tem = gen_reg_rtx (mode); 6008: 6009: /* Replace biv with giv's reduced register. */ 6010: validate_change (insn, &XEXP (x, 1 - arg_operand), 6011: v->new_reg, 1); 6012: 6013: /* Compute value to compare against. */ 6014: emit_iv_add_mult (arg, v->mult_val, v->add_val, tem, where); 6015: /* Use it in this insn. */ 6016: validate_change (insn, &XEXP (x, arg_operand), tem, 1); 6017: if (apply_change_group ()) 6018: return 1; 6019: } 6020: } 6021: else if (GET_CODE (arg) == REG || GET_CODE (arg) == MEM) 6022: { 6023: if (invariant_p (arg) == 1) 6024: { 6025: /* Look for giv with constant positive mult_val and nonconst 6026: add_val. Insert insns to compute new compare value. */ 6027: 6028: for (v = bl->giv; v; v = v->next_iv) 6029: if (CONSTANT_P (v->mult_val) && INTVAL (v->mult_val) > 0 6030: && ! v->ignore && ! v->maybe_dead 6031: && v->mode == mode) 6032: { 6033: rtx tem; 6034: 6035: if (! eliminate_p) 6036: return 1; 6037: 6038: tem = gen_reg_rtx (mode); 6039: 6040: /* Replace biv with giv's reduced register. */ 6041: validate_change (insn, &XEXP (x, 1 - arg_operand), 6042: v->new_reg, 1); 6043: 6044: /* Compute value to compare against. */ 6045: emit_iv_add_mult (arg, v->mult_val, v->add_val, 6046: tem, where); 6047: validate_change (insn, &XEXP (x, arg_operand), tem, 1); 6048: if (apply_change_group ()) 6049: return 1; 6050: } 6051: } 6052: 6053: /* This code has problems. Basically, you can't know when 6054: seeing if we will eliminate BL, whether a particular giv 6055: of ARG will be reduced. If it isn't going to be reduced, 6056: we can't eliminate BL. We can try forcing it to be reduced, 6057: but that can generate poor code. 6058: 6059: The problem is that the benefit of reducing TV, below should 6060: be increased if BL can actually be eliminated, but this means 6061: we might have to do a topological sort of the order in which 6062: we try to process biv. It doesn't seem worthwhile to do 6063: this sort of thing now. */ 6064: 6065: #if 0 6066: /* Otherwise the reg compared with had better be a biv. */ 6067: if (GET_CODE (arg) != REG 6068: || reg_iv_type[REGNO (arg)] != BASIC_INDUCT) 6069: return 0; 6070: 6071: /* Look for a pair of givs, one for each biv, 6072: with identical coefficients. */ 6073: for (v = bl->giv; v; v = v->next_iv) 6074: { 6075: struct induction *tv; 6076: 6077: if (v->ignore || v->maybe_dead || v->mode != mode) 6078: continue; 6079: 6080: for (tv = reg_biv_class[REGNO (arg)]->giv; tv; tv = tv->next_iv) 6081: if (! tv->ignore && ! tv->maybe_dead 6082: && rtx_equal_p (tv->mult_val, v->mult_val) 6083: && rtx_equal_p (tv->add_val, v->add_val) 6084: && tv->mode == mode) 6085: { 6086: if (! eliminate_p) 6087: return 1; 6088: 6089: /* Replace biv with its giv's reduced reg. */ 6090: XEXP (x, 1-arg_operand) = v->new_reg; 6091: /* Replace other operand with the other giv's 6092: reduced reg. */ 6093: XEXP (x, arg_operand) = tv->new_reg; 6094: return 1; 6095: } 6096: } 6097: #endif 6098: } 6099: 6100: /* If we get here, the biv can't be eliminated. */ 6101: return 0; 6102: 6103: case MEM: 6104: /* If this address is a DEST_ADDR giv, it doesn't matter if the 6105: biv is used in it, since it will be replaced. */ 6106: for (v = bl->giv; v; v = v->next_iv) 6107: if (v->giv_type == DEST_ADDR && v->location == &XEXP (x, 0)) 6108: return 1; 6109: break; 6110: } 6111: 6112: /* See if any subexpression fails elimination. */ 6113: fmt = GET_RTX_FORMAT (code); 6114: for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) 6115: { 6116: switch (fmt[i]) 6117: { 6118: case 'e': 6119: if (! maybe_eliminate_biv_1 (XEXP (x, i), insn, bl, 6120: eliminate_p, where)) 6121: return 0; 6122: break; 6123: 6124: case 'E': 6125: for (j = XVECLEN (x, i) - 1; j >= 0; j--) 6126: if (! maybe_eliminate_biv_1 (XVECEXP (x, i, j), insn, bl, 6127: eliminate_p, where)) 6128: return 0; 6129: break; 6130: } 6131: } 6132: 6133: return 1; 6134: } 6135: 6136: /* Return nonzero if the last use of REG 6137: is in an insn following INSN in the same basic block. */ 6138: 6139: static int 6140: last_use_this_basic_block (reg, insn) 6141: rtx reg; 6142: rtx insn; 6143: { 6144: rtx n; 6145: for (n = insn; 6146: n && GET_CODE (n) != CODE_LABEL && GET_CODE (n) != JUMP_INSN; 6147: n = NEXT_INSN (n)) 6148: { 6149: if (regno_last_uid[REGNO (reg)] == INSN_UID (n)) 6150: return 1; 6151: } 6152: return 0; 6153: } 6154: 6155: /* Called via `note_stores' to record the initial value of a biv. Here we 6156: just record the location of the set and process it later. */ 6157: 6158: static void 6159: record_initial (dest, set) 6160: rtx dest; 6161: rtx set; 6162: { 6163: struct iv_class *bl; 6164: 6165: if (GET_CODE (dest) != REG 6166: || REGNO (dest) >= max_reg_before_loop 6167: || reg_iv_type[REGNO (dest)] != BASIC_INDUCT) 6168: return; 6169: 6170: bl = reg_biv_class[REGNO (dest)]; 6171: 6172: /* If this is the first set found, record it. */ 6173: if (bl->init_insn == 0) 6174: { 6175: bl->init_insn = note_insn; 6176: bl->init_set = set; 6177: } 6178: } 6179: 6180: /* If any of the registers in X are "old" and currently have a last use earlier 6181: than INSN, update them to have a last use of INSN. Their actual last use 6182: will be the previous insn but it will not have a valid uid_luid so we can't 6183: use it. */ 6184: 6185: static void 6186: update_reg_last_use (x, insn) 6187: rtx x; 6188: rtx insn; 6189: { 6190: /* Check for the case where INSN does not have a valid luid. In this case, 6191: there is no need to modify the regno_last_uid, as this can only happen 6192: when code is inserted after the loop_end to set a pseudo's final value, 6193: and hence this insn will never be the last use of x. */ 6194: if (GET_CODE (x) == REG && REGNO (x) < max_reg_before_loop 6195: && INSN_UID (insn) < max_uid_for_loop 6196: && uid_luid[regno_last_uid[REGNO (x)]] < uid_luid[INSN_UID (insn)]) 6197: regno_last_uid[REGNO (x)] = INSN_UID (insn); 6198: else 6199: { 6200: register int i, j; 6201: register char *fmt = GET_RTX_FORMAT (GET_CODE (x)); 6202: for (i = GET_RTX_LENGTH (GET_CODE (x)) - 1; i >= 0; i--) 6203: { 6204: if (fmt[i] == 'e') 6205: update_reg_last_use (XEXP (x, i), insn); 6206: else if (fmt[i] == 'E') 6207: for (j = XVECLEN (x, i) - 1; j >= 0; j--) 6208: update_reg_last_use (XVECEXP (x, i, j), insn); 6209: } 6210: } 6211: } 6212: 6213: /* Given a jump insn JUMP, return the condition that will cause it to branch 6214: to its JUMP_LABEL. If the condition cannot be understood, or is an 6215: inequality floating-point comparison which needs to be reversed, 0 will 6216: be returned. 6217: 6218: If EARLIEST is non-zero, it is a pointer to a place where the earliest 6219: insn used in locating the condition was found. If a replacement test 6220: of the condition is desired, it should be placed in front of that 6221: insn and we will be sure that the inputs are still valid. 6222: 6223: The condition will be returned in a canonical form to simplify testing by 6224: callers. Specifically: 6225: 6226: (1) The code will always be a comparison operation (EQ, NE, GT, etc.). 6227: (2) Both operands will be machine operands; (cc0) will have been replaced. 6228: (3) If an operand is a constant, it will be the second operand. 6229: (4) (LE x const) will be replaced with (LT x <const+1>) and similarly 6230: for GE, GEU, and LEU. */ 6231: 6232: rtx 6233: get_condition (jump, earliest) 6234: rtx jump; 6235: rtx *earliest; 6236: { 6237: enum rtx_code code; 6238: rtx prev = jump; 6239: rtx set; 6240: rtx tem; 6241: rtx op0, op1; 6242: int reverse_code = 0; 6243: int did_reverse_condition = 0; 6244: 6245: /* If this is not a standard conditional jump, we can't parse it. */ 6246: if (GET_CODE (jump) != JUMP_INSN 6247: || ! condjump_p (jump) || simplejump_p (jump)) 6248: return 0; 6249: 6250: code = GET_CODE (XEXP (SET_SRC (PATTERN (jump)), 0)); 6251: op0 = XEXP (XEXP (SET_SRC (PATTERN (jump)), 0), 0); 6252: op1 = XEXP (XEXP (SET_SRC (PATTERN (jump)), 0), 1); 6253: 6254: if (earliest) 6255: *earliest = jump; 6256: 6257: /* If this branches to JUMP_LABEL when the condition is false, reverse 6258: the condition. */ 1.1.1.4 ! root 6259: if (GET_CODE (XEXP (SET_SRC (PATTERN (jump)), 2)) == LABEL_REF ! 6260: && XEXP (XEXP (SET_SRC (PATTERN (jump)), 2), 0) == JUMP_LABEL (jump)) 1.1 root 6261: code = reverse_condition (code), did_reverse_condition ^= 1; 6262: 6263: /* If we are comparing a register with zero, see if the register is set 6264: in the previous insn to a COMPARE or a comparison operation. Perform 6265: the same tests as a function of STORE_FLAG_VALUE as find_comparison_args 6266: in cse.c */ 6267: 6268: while (GET_RTX_CLASS (code) == '<' && op1 == const0_rtx) 6269: { 6270: /* Set non-zero when we find something of interest. */ 6271: rtx x = 0; 6272: 6273: #ifdef HAVE_cc0 6274: /* If comparison with cc0, import actual comparison from compare 6275: insn. */ 6276: if (op0 == cc0_rtx) 6277: { 6278: if ((prev = prev_nonnote_insn (prev)) == 0 6279: || GET_CODE (prev) != INSN 6280: || (set = single_set (prev)) == 0 6281: || SET_DEST (set) != cc0_rtx) 6282: return 0; 6283: 6284: op0 = SET_SRC (set); 6285: op1 = CONST0_RTX (GET_MODE (op0)); 6286: if (earliest) 6287: *earliest = prev; 6288: } 6289: #endif 6290: 6291: /* If this is a COMPARE, pick up the two things being compared. */ 6292: if (GET_CODE (op0) == COMPARE) 6293: { 6294: op1 = XEXP (op0, 1); 6295: op0 = XEXP (op0, 0); 6296: continue; 6297: } 6298: else if (GET_CODE (op0) != REG) 6299: break; 6300: 6301: /* Go back to the previous insn. Stop if it is not an INSN. We also 6302: stop if it isn't a single set or if it has a REG_INC note because 6303: we don't want to bother dealing with it. */ 6304: 6305: if ((prev = prev_nonnote_insn (prev)) == 0 6306: || GET_CODE (prev) != INSN 6307: || FIND_REG_INC_NOTE (prev, 0) 6308: || (set = single_set (prev)) == 0) 6309: break; 6310: 6311: /* If this is setting OP0, get what it sets it to if it looks 6312: relevant. */ 6313: if (SET_DEST (set) == op0) 6314: { 6315: enum machine_mode inner_mode = GET_MODE (SET_SRC (set)); 6316: 6317: if ((GET_CODE (SET_SRC (set)) == COMPARE 1.1.1.4 ! root 6318: || (((code == NE ! 6319: || (code == LT ! 6320: && GET_MODE_CLASS (inner_mode) == MODE_INT ! 6321: && (GET_MODE_BITSIZE (inner_mode) ! 6322: <= HOST_BITS_PER_WIDE_INT) ! 6323: && (STORE_FLAG_VALUE ! 6324: & ((HOST_WIDE_INT) 1 ! 6325: << (GET_MODE_BITSIZE (inner_mode) - 1)))) ! 6326: #ifdef FLOAT_STORE_FLAG_VALUE ! 6327: || (code == LT ! 6328: && GET_MODE_CLASS (inner_mode) == MODE_FLOAT ! 6329: && FLOAT_STORE_FLAG_VALUE < 0) ! 6330: #endif ! 6331: )) 1.1 root 6332: && GET_RTX_CLASS (GET_CODE (SET_SRC (set))) == '<'))) 6333: x = SET_SRC (set); 1.1.1.4 ! root 6334: else if (((code == EQ ! 6335: || (code == GE ! 6336: && (GET_MODE_BITSIZE (inner_mode) ! 6337: <= HOST_BITS_PER_WIDE_INT) ! 6338: && GET_MODE_CLASS (inner_mode) == MODE_INT ! 6339: && (STORE_FLAG_VALUE ! 6340: & ((HOST_WIDE_INT) 1 ! 6341: << (GET_MODE_BITSIZE (inner_mode) - 1)))) ! 6342: #ifdef FLOAT_STORE_FLAG_VALUE ! 6343: || (code == GE ! 6344: && GET_MODE_CLASS (inner_mode) == MODE_FLOAT ! 6345: && FLOAT_STORE_FLAG_VALUE < 0) ! 6346: #endif ! 6347: )) 1.1 root 6348: && GET_RTX_CLASS (GET_CODE (SET_SRC (set))) == '<') 6349: { 6350: /* We might have reversed a LT to get a GE here. But this wasn't 6351: actually the comparison of data, so we don't flag that we 6352: have had to reverse the condition. */ 6353: did_reverse_condition ^= 1; 6354: reverse_code = 1; 6355: x = SET_SRC (set); 6356: } 6357: } 6358: 6359: else if (reg_set_p (op0, prev)) 6360: /* If this sets OP0, but not directly, we have to give up. */ 6361: break; 6362: 6363: if (x) 6364: { 6365: if (GET_RTX_CLASS (GET_CODE (x)) == '<') 6366: code = GET_CODE (x); 6367: if (reverse_code) 6368: { 6369: code = reverse_condition (code); 6370: did_reverse_condition ^= 1; 6371: reverse_code = 0; 6372: } 6373: 6374: op0 = XEXP (x, 0), op1 = XEXP (x, 1); 6375: if (earliest) 6376: *earliest = prev; 6377: } 6378: } 6379: 6380: /* If constant is first, put it last. */ 6381: if (CONSTANT_P (op0)) 6382: code = swap_condition (code), tem = op0, op0 = op1, op1 = tem; 6383: 6384: /* If OP0 is the result of a comparison, we weren't able to find what 6385: was really being compared, so fail. */ 6386: if (GET_MODE_CLASS (GET_MODE (op0)) == MODE_CC) 6387: return 0; 6388: 1.1.1.4 ! root 6389: /* Canonicalize any ordered comparison with integers involving equality ! 6390: if we can do computations in the relevant mode and we do not ! 6391: overflow. */ ! 6392: ! 6393: if (GET_CODE (op1) == CONST_INT ! 6394: && GET_MODE (op0) != VOIDmode ! 6395: && GET_MODE_BITSIZE (GET_MODE (op0)) <= HOST_BITS_PER_WIDE_INT) ! 6396: { ! 6397: HOST_WIDE_INT const_val = INTVAL (op1); ! 6398: unsigned HOST_WIDE_INT uconst_val = const_val; ! 6399: unsigned HOST_WIDE_INT max_val ! 6400: = (unsigned HOST_WIDE_INT) GET_MODE_MASK (GET_MODE (op0)); 1.1 root 6401: 6402: switch (code) 1.1.1.4 ! root 6403: { ! 6404: case LE: ! 6405: if (const_val != max_val >> 1) ! 6406: code = LT, op1 = GEN_INT (const_val + 1); ! 6407: break; 1.1 root 6408: 1.1.1.4 ! root 6409: case GE: ! 6410: if (const_val ! 6411: != (((HOST_WIDE_INT) 1 ! 6412: << (GET_MODE_BITSIZE (GET_MODE (op0)) - 1)))) ! 6413: code = GT, op1 = GEN_INT (const_val - 1); ! 6414: break; 1.1 root 6415: 1.1.1.4 ! root 6416: case LEU: ! 6417: if (uconst_val != max_val) ! 6418: code = LTU, op1 = GEN_INT (uconst_val + 1); ! 6419: break; 1.1 root 6420: 1.1.1.4 ! root 6421: case GEU: ! 6422: if (uconst_val != 0) ! 6423: code = GTU, op1 = GEN_INT (uconst_val - 1); ! 6424: break; ! 6425: } 1.1 root 6426: } 6427: 6428: /* If this was floating-point and we reversed anything other than an 6429: EQ or NE, return zero. */ 6430: if (TARGET_FLOAT_FORMAT == IEEE_FLOAT_FORMAT 6431: && did_reverse_condition && code != NE && code != EQ 6432: && GET_MODE_CLASS (GET_MODE (op0)) == MODE_FLOAT) 6433: return 0; 6434: 6435: #ifdef HAVE_cc0 6436: /* Never return CC0; return zero instead. */ 6437: if (op0 == cc0_rtx) 6438: return 0; 6439: #endif 6440: 6441: return gen_rtx (code, VOIDmode, op0, op1); 6442: } 6443: 6444: /* Similar to above routine, except that we also put an invariant last 6445: unless both operands are invariants. */ 6446: 6447: rtx 6448: get_condition_for_loop (x) 6449: rtx x; 6450: { 1.1.1.4 ! root 6451: rtx comparison = get_condition (x, NULL_PTR); 1.1 root 6452: 6453: if (comparison == 0 6454: || ! invariant_p (XEXP (comparison, 0)) 6455: || invariant_p (XEXP (comparison, 1))) 6456: return comparison; 6457: 6458: return gen_rtx (swap_condition (GET_CODE (comparison)), VOIDmode, 6459: XEXP (comparison, 1), XEXP (comparison, 0)); 6460: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.