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