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