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