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