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