![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to loop.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [GCC 1.x] / gcc|
Return to loop.c CVS log | Up to [GCC 1.x] / gcc |
1.1 root 1: /* Move constant computations out of loops. 1.1.1.15! root 2: Copyright (C) 1987, 1988, 1989 Free Software Foundation, Inc. 1.1 root 3: 4: This file is part of GNU CC. 5: 1.1.1.13 root 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 1, or (at your option) 9: any later version. 10: 1.1 root 11: GNU CC is distributed in the hope that it will be useful, 1.1.1.13 root 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. */ 1.1 root 19: 20: 21: /* This is the loop optimization pass of the compiler. 22: It finds invariant computations within loops and moves them 1.1.1.8 root 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. 1.1 root 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: /* ??? verify_loop would run faster if we made one table 37: of the minimum and maximum luids from which each label is reached. 38: Also, it would be faster if loop_store_addrs were a hash table. */ 39: 40: #include "config.h" 41: #include "rtl.h" 1.1.1.10 root 42: #include "expr.h" 1.1 root 43: #include "insn-config.h" 44: #include "regs.h" 1.1.1.15! root 45: #include "hard-reg-set.h" 1.1 root 46: #include "recog.h" 1.1.1.8 root 47: #include "flags.h" 1.1.1.2 root 48: #include <stdio.h> 1.1 root 49: 50: /* Vector mapping INSN_UIDs to luids. 51: The luids are like uids but increase monononically always. 52: We use them to see whether a jump comes from outside a given loop. */ 53: 54: static short *uid_luid; 55: 56: /* Get the luid of an insn. */ 57: 58: #define INSN_LUID(INSN) (uid_luid[INSN_UID (INSN)]) 59: 60: /* 1 + largest uid of any insn. */ 61: 62: static int max_uid; 63: 64: /* 1 + luid of last insn. */ 65: 66: static int max_luid; 67: 68: /* Nonzero if somewhere in the current loop 69: there is either a subroutine call, 70: or a store into a memory address that is not fixed, 71: or a store in a BLKmode memory operand, 72: or too many different fixed addresses stored in 73: to record them all in `loop_store_addrs'. 74: 75: In any of these cases, no memory location can be regarded 76: as invariant. */ 77: 78: static int unknown_address_altered; 79: 80: /* Nonzero if somewhere in the current loop there is a store 81: into a memory address that is not fixed but is known to be 82: part of an aggregate. 83: 84: In this case, no memory reference in an aggregate may be 85: considered invariant. */ 86: 87: static int unknown_aggregate_altered; 88: 89: /* Nonzero if somewhere in the current loop there is a store 90: into a memory address other than a fixed address not in an aggregate. 91: 92: In this case, no memory reference in an aggregate at a varying address 93: may be considered invariant. */ 94: 95: static int fixed_aggregate_altered; 96: 97: /* Nonzero if there is a subroutine call in the current loop. 98: (unknown_address_altered is also nonzero in this case.) */ 99: 100: static int loop_has_call; 101: 1.1.1.14 root 102: /* Added loop_continue which is the NOTE_INSN_LOOP_CONT of the 103: current loop. A continue statement will generate a branch to 104: NEXT_INSN (loop_continue). */ 105: 106: static rtx loop_continue; 107: 1.1.1.8 root 108: /* Indexed by register number, contains the number of times the reg 1.1.1.10 root 109: is set during the loop being scanned. 110: During code motion, -1 indicates a reg that has been made a candidate. 111: After code motion, regs moved have 0 (which is accurate now) 112: while the failed candidates have the original number of times set. 113: 114: Therefore, at all times, 0 indicates an invariant register; 115: -1 a conditionally invariant one. */ 1.1.1.8 root 116: 117: static short *n_times_set; 118: 1.1.1.10 root 119: /* Original value of n_times_set; same except that this value 120: is not set to -1 for a reg whose sets have been made candidates 121: and not set to 0 for a reg that is moved. */ 1.1.1.8 root 122: 123: static short *n_times_used; 124: 1.1.1.12 root 125: /* Nonzero means reg N has already been moved out of one loop. 126: This reduces the desire to move it out of another. */ 127: 128: static char *moved_once; 129: 1.1 root 130: /* Array of fixed memory addresses that are stored in this loop. 131: If there are too many to fit here, 132: we just turn on unknown_address_altered. */ 133: 134: #define NUM_STORES 10 135: static rtx loop_store_addrs[NUM_STORES]; 136: static int loop_store_widths[NUM_STORES]; 137: 138: /* Index of first available slot in above array. */ 139: static int loop_store_addrs_idx; 140: 1.1.1.8 root 141: /* Count of movable (i.e. invariant) instructions discovered in the loop. */ 142: static int num_movables; 143: 144: /* Count of memory write instructions discovered in the loop. */ 145: static int num_mem_sets; 146: 147: /* Number of loops contained within the current one, including itself. */ 148: static int loops_enclosed; 149: 150: /* Bound on pseudo register number before loop optimization. 151: A pseudo has valid regscan info if its number is < old_max_reg. */ 152: static int old_max_reg; 153: 1.1 root 154: /* During the analysis of a loop, a chain of `struct movable's 155: is made to record all the movable insns found. 156: Then the entire chain can be scanned to decide which to move. */ 157: 158: struct movable 159: { 160: rtx insn; /* A movable insn */ 1.1.1.8 root 161: rtx set_src; /* The expression this reg is set from. 162: Either SET_SRC (body) or a REG_EQUAL. */ 1.1.1.2 root 163: int consec; /* Number of consecutive following insns 164: that must be moved with this one. */ 1.1 root 165: int regno; /* The register it sets */ 166: short lifetime; /* lifetime of that register; 167: may be adjusted when matching movables 168: that load the same value are found. */ 1.1.1.10 root 169: short savings; /* Number of insns we can move for this reg, 170: including other movables that force this 171: or match this one. */ 1.1 root 172: unsigned int cond : 1; /* 1 if only conditionally movable */ 173: unsigned int force : 1; /* 1 means MUST move this insn */ 174: unsigned int global : 1; /* 1 means reg is live outside this loop */ 1.1.1.15! root 175: /* If PARTIAL is 1, GLOBAL means something different: ! 176: that the reg is live outside the range from where it is set ! 177: to the following label. */ 1.1.1.2 root 178: unsigned int done : 1; /* 1 inhibits further processing of this */ 1.1.1.15! root 179: /* 1 in PARTIAL means this reg is used for zero-extending. ! 180: In particular, moving it does not make it invariant. */ ! 181: unsigned int partial : 1; 1.1.1.14 root 182: enum machine_mode savemode; /* Nonzero means it is a mode for a low part 183: that we should avoid changing when clearing 184: the rest of the reg. */ 1.1 root 185: struct movable *match; /* First entry for same value */ 186: struct movable *forces; /* An insn that must be moved if this is */ 187: struct movable *next; 188: }; 189: 1.1.1.2 root 190: static FILE *loop_dump_stream; 191: 1.1.1.15! root 192: /* Forward declarations. */ ! 193: ! 194: struct induction; ! 195: struct iv_class; ! 196: 1.1 root 197: static rtx verify_loop (); 198: static int invariant_p (); 1.1.1.4 root 199: static int consec_sets_invariant_p (); 1.1 root 200: static int can_jump_into_range_p (); 1.1.1.15! root 201: static int labels_in_range_p (); 1.1 root 202: static void count_loop_regs_set (); 203: static void note_addr_stored (); 204: static int loop_reg_used_before_p (); 205: static void constant_high_bytes (); 206: static void scan_loop (); 207: static rtx replace_regs (); 1.1.1.9 root 208: static void replace_call_address (); 1.1.1.15! root 209: static rtx skip_consec_insns (); ! 210: static void ignore_some_movables (); ! 211: static void force_movables (); ! 212: static void combine_movables (); ! 213: static int rtx_equal_for_loop_p (); 1.1.1.2 root 214: static void move_movables (); 1.1.1.8 root 215: static void strength_reduce (); 216: static void find_mem_givs (); 217: static void record_giv (); 218: static void delete_insn_forces (); 219: static int basic_induction_var (); 220: static int general_induction_var (); 221: static int consec_sets_giv (); 222: static int check_dbra_loop (); 223: static void emit_iv_init_code (); 224: static int product_cheap_p (); 225: static void emit_iv_inc (); 1.1.1.14 root 226: static void check_eliminate_biv (); 1.1.1.8 root 227: static int can_eliminate_biv_p (); 228: static void eliminate_biv (); 229: static rtx final_biv_value (); 1.1.1.11 root 230: static int last_use_this_basic_block (); 1.1 root 231: 232: /* Entry point of this file. Perform loop optimization 233: on the current function. F is the first insn of the function 1.1.1.13 root 234: and DUMPFILE is a stream for output of a trace of actions taken 235: (or 0 if none should be output). */ 1.1 root 236: 1.1.1.2 root 237: void 1.1.1.8 root 238: loop_optimize (f, dumpfile) 1.1 root 239: /* f is the first instruction of a chain of insns for one function */ 240: rtx f; 1.1.1.2 root 241: FILE *dumpfile; 1.1 root 242: { 243: register rtx insn; 244: register int i; 245: rtx end; 246: rtx last_insn; 247: 1.1.1.2 root 248: loop_dump_stream = dumpfile; 249: 1.1 root 250: init_recog (); 251: 1.1.1.10 root 252: old_max_reg = max_reg_num (); 1.1.1.8 root 253: 1.1.1.12 root 254: moved_once = (char *) alloca (old_max_reg); 255: bzero (moved_once, old_max_reg); 256: 1.1 root 257: /* First find the last real insn, and count the number of insns, 1.1.1.15! root 258: and assign insns their luids. */ 1.1 root 259: 260: for (insn = f, i = 0; insn; insn = NEXT_INSN (insn)) 261: if (INSN_UID (insn) > i) 262: i = INSN_UID (insn); 263: 264: max_uid = i + 1; 265: uid_luid = (short *) alloca ((i + 1) * sizeof (short)); 266: bzero (uid_luid, (i + 1) * sizeof (short)); 267: 268: /* Compute the mapping from uids to luids. 269: LUIDs are numbers assigned to insns, like uids, 1.1.1.15! root 270: except that luids increase monotonically through the code. ! 271: Don't assign luids to line-number NOTEs, so that the distance in luids ! 272: between two insns is not affected by -g. */ 1.1 root 273: 274: for (insn = f, i = 0; insn; insn = NEXT_INSN (insn)) 275: { 276: last_insn = insn; 1.1.1.15! root 277: if (GET_CODE (insn) != NOTE ! 278: || NOTE_LINE_NUMBER (insn) < 0) ! 279: INSN_LUID (insn) = ++i; ! 280: else ! 281: /* Give a line number note the same luid as preceding insn. */ ! 282: INSN_LUID (insn) = i; 1.1 root 283: } 284: 285: max_luid = i; 286: 287: /* Don't leave gaps in uid_luid for insns that have been 288: deleted. It is possible that the first or last insn 289: using some register has been deleted by cross-jumping. 290: Make sure that uid_luid for that former insn's uid 291: points to the general area where that insn used to be. */ 292: for (i = 0; i < max_uid; i++) 1.1.1.2 root 293: { 294: uid_luid[0] = uid_luid[i]; 295: if (uid_luid[0] != 0) 296: break; 297: } 298: for (i = 0; i < max_uid; i++) 1.1 root 299: if (uid_luid[i] == 0) 300: uid_luid[i] = uid_luid[i - 1]; 301: 302: /* Find and process each loop. 303: We scan from the end, and process each loop when its start is seen, 304: so we process innermost loops first. */ 305: 306: for (insn = last_insn; insn; insn = PREV_INSN (insn)) 307: if (GET_CODE (insn) == NOTE 1.1.1.4 root 308: && NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG) 309: { 1.1 root 310: /* Make sure it really is a loop -- no jumps in from outside. */ 1.1.1.4 root 311: end = verify_loop (f, insn); 312: if (end != 0) 313: /* If so, optimize this loop. */ 1.1.1.8 root 314: scan_loop (insn, end, max_reg_num ()); 1.1.1.4 root 315: else if (loop_dump_stream) 316: fprintf (loop_dump_stream, 317: "\nLoop at %d ignored due to multiple entry points.\n", 318: INSN_UID (insn)); 319: } 1.1 root 320: } 321: 322: /* Optimize one loop whose start is LOOP_START and end is END. 323: LOOP_START is the NOTE_INSN_LOOP_BEG and END is the matching 324: NOTE_INSN_LOOP_END. */ 325: 1.1.1.8 root 326: /* ??? can also move memory writes out of loop if destination 327: address is invariant? */ 328: 1.1 root 329: static void 330: scan_loop (loop_start, end, nregs) 331: rtx loop_start, end; 332: int nregs; 333: { 334: register int i; 335: register rtx p = NEXT_INSN (loop_start); 336: /* 1 if we are scanning insns that could be executed zero times. */ 337: int maybe_never = 0; 1.1.1.3 root 338: /* 1 if we are scanning insns that might never be executed 339: due to a subroutine call which might exit before they are reached. */ 340: int call_passed = 0; 1.1 root 341: /* For a rotated loop that is entered near the bottom, 342: this is the label at the top. Otherwise it is zero. */ 343: rtx loop_top = 0; 344: /* Jump insn that enters the loop, or 0 if control drops in. */ 345: rtx loop_entry_jump = 0; 346: /* Place in the loop where control enters. */ 347: rtx scan_start; 348: /* Number of insns in the loop. */ 349: int insn_count; 350: int tem; 1.1.1.8 root 351: rtx temp; 1.1 root 352: /* Indexed by register number, contains 1 for a register whose 353: assignments may not be moved out of the loop. */ 354: char *may_not_move; 355: /* Chain describing insns movable in current loop. */ 356: struct movable *movables = 0; 357: /* Last element in `movables' -- so we can add elements at the end. */ 358: struct movable *last_movable = 0; 359: /* Ratio of extra register life span we can justify 360: for saving an instruction. More if loop doesn't call subroutines 361: since in that case saving an insn makes more difference 362: and more registers are available. */ 1.1.1.10 root 363: int threshold = loop_has_call ? 15 : 30; 1.1.1.7 root 364: /* Nonzero if the insn that jumps into the real loop 365: is not the very first thing after the loop-beginning note. */ 366: int something_before_entry_jump = 0; 1.1 root 367: 368: n_times_set = (short *) alloca (nregs * sizeof (short)); 369: n_times_used = (short *) alloca (nregs * sizeof (short)); 370: may_not_move = (char *) alloca (nregs); 371: 372: /* Determine whether this loop starts with a jump down 373: to a test at the end. */ 374: while (p != end 375: && GET_CODE (p) != CODE_LABEL && GET_CODE (p) != JUMP_INSN) 1.1.1.7 root 376: { 377: if (GET_CODE (p) == CALL_INSN || GET_CODE (p) == INSN) 378: something_before_entry_jump = 1; 379: p = NEXT_INSN (p); 380: } 1.1 root 381: 382: /* "Loop" contains neither jumps nor labels; 383: it must have been a dummy. Think no more about it. */ 384: if (p == end) 385: return; 386: 1.1.1.2 root 387: scan_start = p; 388: 1.1 root 389: /* If loop has a jump before the first label, 390: the true entry is the target of that jump. 391: Start scan from there. 392: But record in LOOP_TOP the place where the end-test jumps 393: back to so we can scan that after the end of the loop. */ 394: if (GET_CODE (p) == JUMP_INSN) 395: { 396: loop_entry_jump = p; 397: loop_top = NEXT_INSN (p); 398: /* Loop entry will never be a conditional jump. 1.1.1.8 root 399: If we see one, this must not be a real loop. 400: Also, a return-insn isn't a jump to enter the loop. */ 401: if (GET_CODE (loop_top) != BARRIER 402: || GET_CODE (PATTERN (p)) != SET) 1.1 root 403: return; 1.1.1.5 root 404: /* Get the label at which the loop is entered. */ 405: p = XEXP (SET_SRC (PATTERN (p)), 0); 1.1 root 406: /* Check to see whether the jump actually 407: jumps out of the loop (meaning it's no loop). 408: This case can happen for things like 409: do {..} while (0). */ 1.1.1.2 root 410: if (p == 0 411: || INSN_LUID (p) < INSN_LUID (loop_start) 1.1 root 412: || INSN_LUID (p) >= INSN_LUID (end)) 1.1.1.2 root 413: { 414: if (loop_dump_stream) 415: fprintf (loop_dump_stream, "\nLoop from %d to %d is phony.\n\n", 416: INSN_UID (loop_start), INSN_UID (end)); 417: return; 418: } 419: 420: /* Find the first label after the entry-jump. */ 421: while (GET_CODE (loop_top) != CODE_LABEL) 422: { 423: loop_top = NEXT_INSN (loop_top); 424: if (loop_top == 0) 425: abort (); 426: } 427: 428: /* Maybe rearrange the loop to drop straight in 429: with a new test to jump around it entirely. 430: (The latter is considered outside the loop.) 431: If this is done, we no longer enter with a jump. */ 1.1.1.7 root 432: if (! something_before_entry_jump 433: && loop_skip_over (loop_start, end, loop_entry_jump)) 1.1.1.8 root 434: { 435: scan_start = loop_top; 436: loop_top = 0; 437: } 1.1.1.2 root 438: else 439: /* We really do enter with a jump; 440: scan the loop from the place where the jump jumps to. */ 441: scan_start = p; 1.1 root 442: } 443: 444: /* Count number of times each reg is set during this loop. 445: Set MAY_NOT_MOVE[I] if it is not safe to move out 446: the setting of register I. */ 447: 448: bzero (n_times_set, nregs * sizeof (short)); 449: bzero (may_not_move, nregs); 1.1.1.2 root 450: count_loop_regs_set (loop_top ? loop_top : loop_start, end, 1.1.1.8 root 451: may_not_move, &insn_count, nregs); 1.1 root 452: for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) 453: may_not_move[i] = 1, n_times_set[i] = 1; 454: bcopy (n_times_set, n_times_used, nregs * sizeof (short)); 455: 1.1.1.2 root 456: if (loop_dump_stream) 1.1.1.14 root 457: { 458: fprintf (loop_dump_stream, "\nLoop from %d to %d: %d real insns.\n", 459: INSN_UID (loop_start), INSN_UID (end), insn_count); 460: if (loop_continue) 461: fprintf (loop_dump_stream, "Continue at insn %d.\n", 462: INSN_UID (loop_continue)); 463: } 1.1.1.2 root 464: 1.1 root 465: /* Scan through the loop finding insns that are safe to move. 466: In each such insn, store QImode as the mode, to mark it. 467: Then set n_times_set to -1 for the reg being set, so that 468: this reg will be considered invariant for subsequent insns. 469: We consider whether subsequent insns use the reg 470: in deciding whether it is worth actually moving. 471: 472: MAYBE_NEVER is nonzero if we have passed a conditional jump insn 473: and therefore it is possible that the insns we are scanning 474: would never be executed. At such times, we must make sure 475: that it is safe to execute the insn once instead of zero times. 476: When MAYBE_NEVER is 0, all insns will be executed at least once 477: so that is not a problem. */ 478: 1.1.1.2 root 479: p = scan_start; 1.1 root 480: while (1) 481: { 482: p = NEXT_INSN (p); 483: /* At end of a straight-in loop, we are done. 484: At end of a loop entered at the bottom, scan the top. */ 485: if (p == scan_start) 486: break; 487: if (p == end) 488: { 489: if (loop_top != 0) 490: p = NEXT_INSN (loop_top); 491: else 492: break; 493: if (p == scan_start) 494: break; 495: } 496: if (GET_CODE (p) == INSN 497: && GET_CODE (PATTERN (p)) == SET 498: && GET_CODE (SET_DEST (PATTERN (p))) == REG 499: && ! may_not_move[REGNO (SET_DEST (PATTERN (p)))]) 500: { 1.1.1.4 root 501: int tem1 = 0; 1.1.1.11 root 502: /* Don't try to optimize a register that was made 503: by loop-optimization for an inner loop. 504: We don't know its life-span, so we can't compute the benefit. */ 505: if (REGNO (SET_DEST (PATTERN (p))) >= old_max_reg) 506: ; 1.1 root 507: /* If this register is used or set outside the loop, 508: then we can move it only if we know this insn is 509: executed exactly once per iteration, 510: and we can check all the insns executed before it 511: to make sure none of them used the value that 512: was lying around at entry to the loop. */ 1.1.1.11 root 513: else if ((uid_luid[regno_last_uid[REGNO (SET_DEST (PATTERN (p)))]] > INSN_LUID (end) 514: || uid_luid[regno_first_uid[REGNO (SET_DEST (PATTERN (p)))]] < INSN_LUID (loop_start)) 515: && (maybe_never 516: || loop_reg_used_before_p (p, loop_start, scan_start, end))) 1.1 root 517: ; 1.1.1.8 root 518: else if (((tem = invariant_p (SET_SRC (PATTERN (p)))) 519: || ((temp = find_reg_note (p, REG_EQUAL, 0)) 520: && (tem = invariant_p (XEXP (temp, 0))))) 1.1 root 521: && (n_times_set[REGNO (SET_DEST (PATTERN (p)))] == 1 1.1.1.4 root 522: || (tem1 523: = consec_sets_invariant_p (SET_DEST (PATTERN (p)), 524: n_times_set[REGNO (SET_DEST (PATTERN (p)))], 1.1.1.8 root 525: p))) 1.1.1.3 root 526: /* If the insn can cause a trap (such as divide by zero), 527: can't move it unless it's guaranteed to be executed 528: once loop is entered. Even a function call might 529: prevent the trap insn from being reached 530: (since it might exit!) */ 531: && ! ((maybe_never || call_passed) 1.1.1.8 root 532: && (may_trap_p (SET_SRC (PATTERN (p))) 533: || ((temp = find_reg_note (p, REG_EQUAL, 0)) 534: && may_trap_p (XEXP (temp, 0)))))) 1.1 root 535: { 536: register struct movable *m; 537: register int regno = REGNO (SET_DEST (PATTERN (p))); 1.1.1.2 root 538: int count; 1.1 root 539: m = (struct movable *) alloca (sizeof (struct movable)); 540: m->next = 0; 541: m->insn = p; 1.1.1.8 root 542: temp = find_reg_note (p, REG_EQUAL, 0); 543: if (temp) 544: m->set_src = XEXP (temp, 0); 545: else 546: m->set_src = SET_SRC (PATTERN (p)); 1.1 root 547: m->force = 0; 1.1.1.2 root 548: m->consec = n_times_set[REGNO (SET_DEST (PATTERN (p)))] - 1; 549: m->done = 0; 1.1 root 550: m->forces = 0; 1.1.1.2 root 551: m->partial = 0; 1.1.1.14 root 552: m->savemode = VOIDmode; 1.1 root 553: m->regno = regno; 1.1.1.4 root 554: /* Set M->cond if either invariant_p or consec_sets_invariant_p 555: returned 2 (only conditionally invariant). */ 556: m->cond = ((tem | tem1) > 1); 1.1 root 557: m->global = (uid_luid[regno_last_uid[regno]] > INSN_LUID (end) 558: || uid_luid[regno_first_uid[regno]] < INSN_LUID (loop_start)); 559: m->match = 0; 560: m->lifetime = (uid_luid[regno_last_uid[regno]] 561: - uid_luid[regno_first_uid[regno]]); 1.1.1.10 root 562: m->savings = n_times_used[regno]; 1.1 root 563: n_times_set[regno] = -1; 564: /* Add M to the end of the chain MOVABLES. */ 565: if (movables == 0) 566: movables = m; 567: else 568: last_movable->next = m; 569: last_movable = m; 1.1.1.15! root 570: if (m->consec > 0) 1.1.1.2 root 571: { 1.1.1.15! root 572: /* Skip this insn, not checking REG_LIBCALL notes. */ ! 573: p = NEXT_INSN (p); ! 574: /* Skip the consecutive insns, if there are any. */ ! 575: p = skip_consec_insns (p, m->consec); ! 576: /* Back up, so the main loop will advance to the right place. */ ! 577: p = PREV_INSN (p); 1.1.1.2 root 578: } 1.1 root 579: } 1.1.1.2 root 580: /* If this register is always set within a STRICT_LOW_PART 581: or set to zero, then its high bytes are constant. 1.1 root 582: So clear them outside the loop and within the loop 583: just load the low bytes. 584: We must check that the machine has an instruction to do so. 585: Also, if the value loaded into the register 586: depends on the same register, this cannot be done. */ 1.1.1.2 root 587: else if (SET_SRC (PATTERN (p)) == const0_rtx 588: && GET_CODE (NEXT_INSN (p)) == INSN 589: && GET_CODE (PATTERN (NEXT_INSN (p))) == SET 590: && (GET_CODE (SET_DEST (PATTERN (NEXT_INSN (p)))) 591: == STRICT_LOW_PART) 592: && (GET_CODE (XEXP (SET_DEST (PATTERN (NEXT_INSN (p))), 0)) 593: == SUBREG) 594: && (SUBREG_REG (XEXP (SET_DEST (PATTERN (NEXT_INSN (p))), 0)) 595: == SET_DEST (PATTERN (p))) 1.1 root 596: && !reg_mentioned_p (SET_DEST (PATTERN (p)), 1.1.1.2 root 597: SET_SRC (PATTERN (NEXT_INSN (p))))) 1.1 root 598: { 599: register int regno = REGNO (SET_DEST (PATTERN (p))); 1.1.1.2 root 600: if (n_times_set[regno] == 2) 601: { 602: register struct movable *m; 603: int count; 604: m = (struct movable *) alloca (sizeof (struct movable)); 605: m->next = 0; 606: m->insn = p; 607: m->force = 0; 608: m->consec = 0; 609: m->done = 0; 610: m->forces = 0; 611: m->partial = 1; 1.1.1.14 root 612: /* If the insn may not be executed on some cycles, 613: we can't clear the whole reg; clear just high part. 1.1.1.15! root 614: Not even if the reg is used only within this loop. 1.1.1.14 root 615: Consider this: 616: while (1) 1.1.1.15! root 617: while (s != t) { 1.1.1.14 root 618: if (foo ()) x = *s; 619: use (x); 620: } 621: Clearing x before the inner loop could clobber a value 1.1.1.15! root 622: being saved from the last time around the outer loop. ! 623: However, if the reg is not used outside this loop ! 624: and all uses of the register are in the same ! 625: basic block as the store, there is no problem. */ ! 626: m->global = (uid_luid[regno_last_uid[regno]] > INSN_LUID (end) ! 627: || uid_luid[regno_first_uid[regno]] < INSN_LUID (p) ! 628: || (labels_in_range_p ! 629: (p, uid_luid[regno_first_uid[regno]]))); ! 630: if (maybe_never && m->global) 1.1.1.14 root 631: m->savemode = GET_MODE (SET_SRC (PATTERN (NEXT_INSN (p)))); 632: else 633: m->savemode = VOIDmode; 1.1.1.2 root 634: m->regno = regno; 635: m->cond = 0; 636: m->match = 0; 637: m->lifetime = (uid_luid[regno_last_uid[regno]] 638: - uid_luid[regno_first_uid[regno]]); 1.1.1.10 root 639: m->savings = 1; 1.1.1.2 root 640: n_times_set[regno] = -1; 641: /* Add M to the end of the chain MOVABLES. */ 642: if (movables == 0) 643: movables = m; 644: else 645: last_movable->next = m; 646: last_movable = m; 647: } 1.1 root 648: } 649: } 1.1.1.3 root 650: /* Past a call insn, we get to insns which might not be executed 651: because the call might exit. This matters for insns that trap. */ 652: else if (GET_CODE (p) == CALL_INSN) 653: call_passed = 1; 1.1 root 654: /* Past a label or a jump, we get to insns for which we 655: can't count on whether or how many times they will be 656: executed during each iteration. Therefore, we can 657: only move out sets of trivial variables 658: (those not used after the loop). */ 1.1.1.15! root 659: else if ((GET_CODE (p) == CODE_LABEL || GET_CODE (p) == JUMP_INSN) ! 660: /* If we enter the loop in the middle, and scan around ! 661: to the beginning, don't set maybe_never for that. */ ! 662: && ! (NEXT_INSN (p) == end && GET_CODE (p) == JUMP_INSN ! 663: && simplejump_p (p))) 1.1 root 664: maybe_never = 1; 665: } 666: 1.1.1.15! root 667: /* If one movable subsumes another, ignore that other. */ ! 668: ! 669: ignore_some_movables (movables); ! 670: 1.1 root 671: /* For each movable insn, see if the reg that it loads 1.1.1.2 root 672: leads when it dies right into another conditionally movable insn. 673: If so, record that the second insn "forces" the first one, 674: since the second can be moved only if the first is. */ 675: 1.1.1.15! root 676: force_movables (movables); 1.1 root 677: 678: /* See if there are multiple movable insns that load the same value. 679: If there are, make all but the first point at the first one 680: through the `match' field, and add the priorities of them 681: all together as the priority of the first. */ 1.1.1.2 root 682: 1.1.1.15! root 683: combine_movables (movables, nregs); 1.1.1.2 root 684: 1.1.1.10 root 685: /* Now consider each movable insn to decide whether it is worth moving. 686: Store 0 in n_times_set for each reg that is moved. */ 1.1.1.2 root 687: 1.1.1.8 root 688: move_movables (movables, threshold, 1.1.1.2 root 689: insn_count, loop_start, end, nregs); 1.1.1.8 root 690: 1.1.1.10 root 691: /* Now candidates that still have -1 are those not moved. 692: Change n_times_set to indicate that those are not actually invariant. */ 693: for (i = 0; i < nregs; i++) 694: if (n_times_set[i] < 0) 695: n_times_set[i] = n_times_used[i]; 696: 1.1.1.8 root 697: if (flag_strength_reduce) 698: strength_reduce (scan_start, end, loop_top, 699: insn_count, loop_start, end, nregs); 1.1.1.2 root 700: } 701: 1.1.1.15! root 702: /* Skip COUNT insns from INSN, counting library calls as 1 insn. */ ! 703: ! 704: static rtx ! 705: skip_consec_insns (insn, count) ! 706: rtx insn; ! 707: int count; ! 708: { ! 709: for (; count > 0; count--) ! 710: { ! 711: if (GET_CODE (insn) == NOTE) ! 712: insn = NEXT_INSN (insn); ! 713: else if (GET_CODE (insn) == BARRIER || GET_CODE (insn) == CODE_LABEL) ! 714: abort (); ! 715: else ! 716: { ! 717: rtx i1, temp; ! 718: ! 719: /* If first insn of gnulib call sequence, skip to end. */ ! 720: /* Do this at start of loop, since INSN is guaranteed to ! 721: be an insn here. */ ! 722: if (temp = find_reg_note (insn, REG_LIBCALL, 0)) ! 723: insn = XEXP (temp, 0); ! 724: ! 725: do insn = NEXT_INSN (insn); ! 726: while (GET_CODE (insn) == NOTE); ! 727: } ! 728: } ! 729: ! 730: return insn; ! 731: } ! 732: ! 733: /* Ignore any movable whose insn falls within a libcall ! 734: which is part of another movable. ! 735: We make use of the fact that the movable for the libcall value ! 736: was made later and so appears later on the chain. */ ! 737: ! 738: static void ! 739: ignore_some_movables (movables) ! 740: struct movable *movables; ! 741: { ! 742: register struct movable *m, *m1; ! 743: ! 744: for (m = movables; m; m = m->next) ! 745: { ! 746: /* Is this a movable for the value of a libcall? */ ! 747: rtx note = find_reg_note (m->insn, REG_RETVAL, 0); ! 748: if (note) ! 749: { ! 750: /* Find the beginning of that libcall. */ ! 751: rtx first_insn = XEXP (note, 0); ! 752: /* Check for earlier movables inside that range, ! 753: and mark them invalid. */ ! 754: for (m1 = movables; m1 != m; m1 = m1->next) ! 755: if (INSN_LUID (m1->insn) >= INSN_LUID (first_insn) ! 756: && INSN_LUID (m1->insn) < INSN_LUID (m->insn)) ! 757: m1->done = 1; ! 758: } ! 759: } ! 760: } ! 761: ! 762: /* For each movable insn, see if the reg that it loads ! 763: leads when it dies right into another conditionally movable insn. ! 764: If so, record that the second insn "forces" the first one, ! 765: since the second can be moved only if the first is. */ ! 766: ! 767: static void ! 768: force_movables (movables) ! 769: struct movable *movables; ! 770: { ! 771: register struct movable *m, *m1; ! 772: for (m1 = movables; m1; m1 = m1->next) ! 773: /* Omit this if moving just the (SET (REG) 0) of a zero-extend. */ ! 774: if (!m1->partial && !m1->done) ! 775: { ! 776: int regno = m1->regno; ! 777: for (m = m1->next; m; m = m->next) ! 778: /* ??? Could this be a bug? What if CSE caused the ! 779: register of M1 to be used after this insn? ! 780: Since CSE does not update regno_last_uid, ! 781: this insn M->insn might not be where it dies. ! 782: But very likely this doesn't matter; what matters is ! 783: that M's reg is computed from M1's reg. */ ! 784: if (INSN_UID (m->insn) == regno_last_uid[regno] ! 785: && !m->done) ! 786: break; ! 787: if (m != 0 && m->set_src == SET_DEST (PATTERN (m1->insn))) ! 788: m = 0; ! 789: ! 790: /* Increase the priority of the moving the first insn ! 791: since it permits the second to be moved as well. */ ! 792: if (m != 0) ! 793: { ! 794: m->forces = m1; ! 795: m1->lifetime += m->lifetime; ! 796: m1->savings += m1->savings; ! 797: } ! 798: } ! 799: } ! 800: ! 801: /* Find invariant expressions that are equal and can be combined into ! 802: one register. */ ! 803: ! 804: static void ! 805: combine_movables (movables, nregs) ! 806: struct movable *movables; ! 807: int nregs; ! 808: { ! 809: register struct movable *m; ! 810: char *matched_regs = (char *) alloca (nregs); ! 811: enum machine_mode mode; ! 812: ! 813: /* Regs that are set more than once are not allowed to match ! 814: or be matched. I'm no longer sure why not. */ ! 815: /* Perhaps testing m->consec_sets would be more appropriate here? */ ! 816: ! 817: for (m = movables; m; m = m->next) ! 818: if (m->match == 0 && n_times_used[m->regno] == 1 && !m->partial) ! 819: { ! 820: register struct movable *m1; ! 821: int regno = m->regno; ! 822: ! 823: bzero (matched_regs, nregs); ! 824: matched_regs[regno] = 1; ! 825: ! 826: for (m1 = m->next; m1; m1 = m1->next) ! 827: if (m1->match == 0 && n_times_used[m1->regno] == 1 ! 828: /* A reg used outside the loop mustn't be eliminated. */ ! 829: && !m1->global ! 830: /* A reg used for zero-extending mustn't be eliminated. */ ! 831: && !m1->partial ! 832: && (matched_regs[m1->regno] ! 833: || ! 834: ( ! 835: /* Can't combine regs with different modes ! 836: even if loaded from the same constant. */ ! 837: (GET_MODE (SET_DEST (PATTERN (m->insn))) ! 838: == GET_MODE (SET_DEST (PATTERN (m1->insn)))) ! 839: /* See if the source of M1 says it matches M. */ ! 840: && ((GET_CODE (m1->set_src) == REG ! 841: && matched_regs[REGNO (m1->set_src)]) ! 842: || rtx_equal_for_loop_p (m->set_src, m1->set_src, ! 843: movables) ! 844: || (REG_NOTES (m->insn) && REG_NOTES (m1->insn) ! 845: && REG_NOTE_KIND (REG_NOTES (m->insn)) == REG_EQUIV ! 846: && REG_NOTE_KIND (REG_NOTES (m1->insn)) == REG_EQUIV ! 847: && rtx_equal_p (XEXP (REG_NOTES (m->insn), 0), ! 848: XEXP (REG_NOTES (m1->insn), 0))))))) ! 849: { ! 850: m->lifetime += m1->lifetime; ! 851: m->savings += m1->savings; ! 852: m1->match = m; ! 853: matched_regs[m1->regno] = 1; ! 854: } ! 855: } ! 856: ! 857: /* Now combine the regs used for zero-extension. ! 858: This can be done for those not marked `global' ! 859: provided their lives don't overlap. */ ! 860: ! 861: for (mode = VOIDmode; (int) mode < (int) MAX_MACHINE_MODE; ! 862: mode = (enum machine_mode) ((int) mode + 1)) ! 863: if (GET_MODE_CLASS (mode) == MODE_INT) ! 864: { ! 865: register struct movable *m0 = 0; ! 866: ! 867: /* Combine all the registers for extension from mode MODE. ! 868: Don't combine any that are used outside this loop. */ ! 869: for (m = movables; m; m = m->next) ! 870: if (m->partial && ! m->global ! 871: && mode == GET_MODE (SET_SRC (PATTERN (NEXT_INSN (m->insn))))) ! 872: { ! 873: register struct movable *m1; ! 874: int first = uid_luid[regno_first_uid[m->regno]]; ! 875: int last = uid_luid[regno_last_uid[m->regno]]; ! 876: ! 877: if (m0 == 0) ! 878: { ! 879: /* First one: don't check for overlap, just record it. */ ! 880: m0 = m; ! 881: continue; ! 882: } ! 883: ! 884: /* Make sure they extend to the same mode. ! 885: (Almost always true.) */ ! 886: if (GET_MODE (SET_DEST (PATTERN (m->insn))) ! 887: != GET_MODE (SET_DEST (PATTERN (m0->insn)))) ! 888: continue; ! 889: ! 890: /* We already have one: check for overlap with those ! 891: already combined together. */ ! 892: for (m1 = movables; m1 != m; m1 = m1->next) ! 893: if (m1 == m0 || (m1->partial && m1->match == m0)) ! 894: if (! (uid_luid[regno_first_uid[m1->regno]] > last ! 895: || uid_luid[regno_last_uid[m1->regno]] < first)) ! 896: goto overlap; ! 897: ! 898: /* No overlap: we can combine this with the others. */ ! 899: m0->lifetime += m->lifetime; ! 900: m0->savings += m->savings; ! 901: m->match = m0; ! 902: ! 903: overlap: ; ! 904: } ! 905: } ! 906: } ! 907: ! 908: /* Return 1 if regs X and Y will become the same if moved. */ ! 909: ! 910: static int ! 911: regs_match_p (x, y, movables) ! 912: rtx x, y; ! 913: struct movable *movables; ! 914: { ! 915: int xn = REGNO (x); ! 916: int yn = REGNO (y); ! 917: struct movable *mx, *my; ! 918: ! 919: for (mx = movables; mx; mx = mx->next) ! 920: if (mx->regno == xn) ! 921: break; ! 922: ! 923: for (my = movables; my; my = my->next) ! 924: if (my->regno == yn) ! 925: break; ! 926: ! 927: return (mx && my ! 928: && ((mx->match == my->match && mx->match != 0) ! 929: || mx->match == my ! 930: || mx == my->match)); ! 931: } ! 932: ! 933: /* Return 1 if X and Y are identical-looking rtx's. ! 934: This is the Lisp function EQUAL for rtx arguments. */ ! 935: ! 936: static int ! 937: rtx_equal_for_loop_p (x, y, movables) ! 938: rtx x, y; ! 939: struct movable *movables; ! 940: { ! 941: register int i; ! 942: register int j; ! 943: register enum rtx_code code; ! 944: register char *fmt; ! 945: ! 946: if (x == y) ! 947: return 1; ! 948: if (x == 0 || y == 0) ! 949: return 0; ! 950: ! 951: code = GET_CODE (x); ! 952: /* Rtx's of different codes cannot be equal. */ ! 953: if (code != GET_CODE (y)) ! 954: return 0; ! 955: ! 956: /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent. ! 957: (REG:SI x) and (REG:HI x) are NOT equivalent. */ ! 958: ! 959: if (GET_MODE (x) != GET_MODE (y)) ! 960: return 0; ! 961: ! 962: /* These three types of rtx's can be compared nonrecursively. */ ! 963: /* Until the end of reload, ! 964: don't consider the a reference to the return register of the current ! 965: function the same as the return from a called function. This eases ! 966: the job of function integration. Once the distinction no longer ! 967: matters, the insn will be deleted. */ ! 968: if (code == REG) ! 969: return ((REGNO (x) == REGNO (y) ! 970: && REG_FUNCTION_VALUE_P (x) == REG_FUNCTION_VALUE_P (y)) ! 971: || regs_match_p (x, y, movables)); ! 972: ! 973: if (code == LABEL_REF) ! 974: return XEXP (x, 0) == XEXP (y, 0); ! 975: if (code == SYMBOL_REF) ! 976: return XSTR (x, 0) == XSTR (y, 0); ! 977: ! 978: /* Compare the elements. If any pair of corresponding elements ! 979: fail to match, return 0 for the whole things. */ ! 980: ! 981: fmt = GET_RTX_FORMAT (code); ! 982: for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) ! 983: { ! 984: switch (fmt[i]) ! 985: { ! 986: case 'i': ! 987: if (XINT (x, i) != XINT (y, i)) ! 988: return 0; ! 989: break; ! 990: ! 991: case 'E': ! 992: /* Two vectors must have the same length. */ ! 993: if (XVECLEN (x, i) != XVECLEN (y, i)) ! 994: return 0; ! 995: ! 996: /* And the corresponding elements must match. */ ! 997: for (j = 0; j < XVECLEN (x, i); j++) ! 998: if (rtx_equal_for_loop_p (XVECEXP (x, i, j), XVECEXP (y, i, j), movables) == 0) ! 999: return 0; ! 1000: break; ! 1001: ! 1002: case 'e': ! 1003: if (rtx_equal_for_loop_p (XEXP (x, i), XEXP (y, i), movables) == 0) ! 1004: return 0; ! 1005: break; ! 1006: ! 1007: case 's': ! 1008: if (strcmp (XSTR (x, i), XSTR (y, i))) ! 1009: return 0; ! 1010: break; ! 1011: ! 1012: case 'u': ! 1013: /* These are just backpointers, so they don't matter. */ ! 1014: break; ! 1015: ! 1016: case '0': ! 1017: break; ! 1018: ! 1019: /* It is believed that rtx's at this level will never ! 1020: contain anything but integers and other rtx's, ! 1021: except for within LABEL_REFs and SYMBOL_REFs. */ ! 1022: default: ! 1023: abort (); ! 1024: } ! 1025: } ! 1026: return 1; ! 1027: } ! 1028: 1.1.1.2 root 1029: /* Scan MOVABLES, and move the insns that deserve to be moved. 1030: If two matching movables are combined, replace one reg with the 1031: other throughout. */ 1032: 1033: static void 1.1.1.8 root 1034: move_movables (movables, threshold, insn_count, loop_start, end, nregs) 1.1.1.2 root 1035: struct movable *movables; 1036: int threshold; 1037: int insn_count; 1038: rtx loop_start; 1039: rtx end; 1040: int nregs; 1041: { 1042: rtx new_start = 0; 1043: register struct movable *m; 1044: register rtx p; 1045: /* Map of pseudo-register replacements to handle combining 1046: when we move several insns that load the same value 1047: into different pseudo-registers. */ 1048: rtx *reg_map = (rtx *) alloca (nregs * sizeof (rtx)); 1049: char *already_moved = (char *) alloca (nregs); 1050: 1051: bzero (already_moved, nregs); 1052: bzero (reg_map, nregs * sizeof (rtx)); 1053: 1.1.1.8 root 1054: num_movables = 0; 1055: 1.1.1.2 root 1056: for (m = movables; m; m = m->next) 1057: { 1058: /* Describe this movable insn. */ 1059: 1060: if (loop_dump_stream) 1061: { 1062: fprintf (loop_dump_stream, "Insn %d: regno %d (life %d), ", 1063: INSN_UID (m->insn), m->regno, m->lifetime); 1064: if (m->consec > 0) 1065: fprintf (loop_dump_stream, "consec %d, ", m->consec); 1066: if (m->cond) 1067: fprintf (loop_dump_stream, "cond "); 1068: if (m->force) 1069: fprintf (loop_dump_stream, "force "); 1070: if (m->global) 1071: fprintf (loop_dump_stream, "global "); 1072: if (m->done) 1073: fprintf (loop_dump_stream, "done "); 1074: if (m->match) 1075: fprintf (loop_dump_stream, "matches %d ", 1076: INSN_UID (m->match->insn)); 1077: if (m->forces) 1078: fprintf (loop_dump_stream, "forces %d ", 1079: INSN_UID (m->forces->insn)); 1080: } 1081: 1.1.1.8 root 1082: /* Count movables. Value used in heuristics in strength_reduce. */ 1083: num_movables++; 1084: 1.1.1.2 root 1085: /* Ignore the insn if it's already done (it matched something else). 1086: Otherwise, see if it is now safe to move. */ 1087: 1088: if (!m->done 1089: && (! m->cond 1.1.1.8 root 1090: || (1 == invariant_p (m->set_src) 1.1.1.4 root 1091: && (m->consec == 0 1092: || 1 == consec_sets_invariant_p (SET_DEST (PATTERN (m->insn)), 1093: m->consec + 1, 1.1.1.8 root 1094: m->insn)))) 1.1.1.2 root 1095: && (! m->forces || m->forces->done)) 1096: { 1097: register int regno; 1098: register rtx p; 1.1.1.10 root 1099: int savings = m->savings; 1.1.1.2 root 1100: 1101: /* We have an insn that is safe to move. 1102: Compute its desirability. */ 1103: 1104: p = m->insn; 1105: regno = m->regno; 1106: 1107: if (loop_dump_stream) 1.1.1.10 root 1108: fprintf (loop_dump_stream, "savings %d ", savings); 1.1.1.2 root 1109: 1.1.1.12 root 1110: if (moved_once[regno]) 1111: { 1112: insn_count *= 2; 1113: 1114: if (loop_dump_stream) 1115: fprintf (loop_dump_stream, "halved since already moved "); 1116: } 1117: 1.1.1.2 root 1118: /* An insn MUST be moved if we already moved something else 1119: which is safe only if this one is moved too: that is, 1120: if already_moved[REGNO] is nonzero. */ 1121: 1122: /* An insn is desirable to move if the new lifetime of the 1123: register is no more than THRESHOLD times the old lifetime. 1124: If it's not desirable, it means the loop is so big 1125: that moving won't speed things up much, 1126: and it is liable to make register usage worse. */ 1127: 1128: /* It is also desirable to move if it can be moved at no 1129: extra cost because something else was already moved. */ 1130: 1131: if (already_moved[regno] 1.1.1.10 root 1132: || (threshold * savings * m->lifetime) >= insn_count 1.1.1.2 root 1133: || (m->forces && m->forces->done 1134: && n_times_used[m->forces->regno] == 1)) 1.1 root 1135: { 1.1.1.2 root 1136: int count; 1137: register struct movable *m1; 1.1.1.8 root 1138: rtx first; 1.1.1.2 root 1139: 1.1.1.14 root 1140: /* Now move the insns that set the reg. */ 1141: 1.1.1.2 root 1142: for (count = m->consec; count >= 0; count--) 1.1 root 1143: { 1.1.1.8 root 1144: rtx i1, temp; 1145: 1146: /* If first insn of gnulib call sequence, skip to end. */ 1147: /* Do this at start of loop, since p is guaranteed to 1148: be an insn here. */ 1149: if (temp = find_reg_note (p, REG_LIBCALL, 0)) 1150: p = XEXP (temp, 0); 1151: 1152: /* If last insn of gnulib call sequence, move all 1153: insns except the last before the loop. The last insn is 1154: handled in the normal manner. */ 1.1.1.15! root 1155: if (temp = find_reg_note (p, REG_RETVAL ! 1156: , 0)) 1.1.1.8 root 1157: { 1.1.1.9 root 1158: rtx fn_address = 0; 1159: rtx fn_reg = 0; 1.1.1.8 root 1160: first = 0; 1161: for (temp = XEXP (temp, 0); temp != p; 1162: temp = NEXT_INSN (temp)) 1163: { 1.1.1.9 root 1164: rtx body = PATTERN (temp); 1165: rtx n; 1166: /* Extract the function address from the insn 1167: that loads it into a register. 1168: If this insn was cse'd, we get incorrect code. 1169: So delete it and stick the fn address right 1170: into the call insn. Since the moved insns 1171: won't be cse'd, that does no harm. */ 1172: if (GET_CODE (NEXT_INSN (temp)) == CALL_INSN 1173: && GET_CODE (body) == SET 1174: && GET_CODE (SET_DEST (body)) == REG 1175: && (n = find_reg_note (temp, REG_EQUIV, 0))) 1176: { 1177: fn_reg = SET_SRC (body); 1178: if (GET_CODE (fn_reg) != REG) 1179: fn_reg = SET_DEST (body); 1180: fn_address = XEXP (n, 0); 1181: continue; 1182: } 1183: /* We have the call insn. 1184: Substitute the fn address for the reg 1185: that we believe this insn will use. */ 1186: if (GET_CODE (temp) == CALL_INSN 1187: && fn_address != 0) 1188: replace_call_address (body, fn_reg, fn_address); 1.1.1.10 root 1189: if (GET_CODE (temp) == CALL_INSN) 1190: i1 = emit_call_insn_before (body, loop_start); 1191: else 1192: i1 = emit_insn_before (body, loop_start); 1.1.1.8 root 1193: if (first == 0) 1194: first = i1; 1195: REG_NOTES (i1) = REG_NOTES (temp); 1196: delete_insn (temp); 1197: } 1198: } 1.1.1.14 root 1199: if (m->savemode != VOIDmode) 1200: { 1201: /* P sets REG to zero; but we should clear only the bits 1202: that are not covered by the mode m->savemode. */ 1203: rtx reg = SET_DEST (PATTERN (p)); 1204: i1 = emit_insn_before 1205: (gen_rtx (SET, VOIDmode, reg, 1206: gen_rtx (AND, GET_MODE (reg), 1207: reg, 1208: gen_rtx (CONST_INT, VOIDmode, 1209: (1 << GET_MODE_BITSIZE (m->savemode)) - 1))), 1210: loop_start); 1211: } 1212: else if (GET_CODE (PATTERN (p)) == CALL_INSN) 1.1.1.10 root 1213: i1 = emit_call_insn_before (PATTERN (p), loop_start); 1214: else 1215: i1 = emit_insn_before (PATTERN (p), loop_start); 1.1.1.8 root 1216: 1.1.1.2 root 1217: if (new_start == 0) 1218: new_start = i1; 1219: 1220: if (loop_dump_stream) 1.1.1.15! root 1221: fprintf (loop_dump_stream, " moved to %d", INSN_UID (i1)); 1.1.1.2 root 1222: 1223: /* Mark the moved, invariant reg as being equivalent to 1224: its constant value. */ 1225: REG_NOTES (i1) = REG_NOTES (p); 1226: if (REG_NOTES (i1) == 0 1.1.1.8 root 1227: && ! m->partial /* But not if it's a zero-extend clr. */ 1.1.1.2 root 1228: && ! m->global /* and not if used outside the loop 1229: (since it might get set outside). */ 1230: && CONSTANT_P (SET_SRC (PATTERN (p)))) 1231: REG_NOTES (i1) 1232: = gen_rtx (EXPR_LIST, REG_EQUIV, 1233: SET_SRC (PATTERN (p)), REG_NOTES (i1)); 1.1.1.8 root 1234: 1235: /* If library call, now fix the REG_NOTES that contain 1236: insn pointers, namely REG_LIBCALL on FIRST 1237: and REG_RETVAL on I1. */ 1238: if (temp = find_reg_note (i1, REG_RETVAL, 0)) 1239: { 1240: XEXP (temp, 0) = first; 1241: temp = find_reg_note (first, REG_LIBCALL, 0); 1242: XEXP (temp, 0) = i1; 1243: } 1244: 1.1.1.2 root 1245: delete_insn (p); 1246: do p = NEXT_INSN (p); 1247: while (GET_CODE (p) == NOTE); 1.1 root 1248: } 1.1.1.2 root 1249: 1.1.1.10 root 1250: /* The more regs we move, the less we like moving them. */ 1251: threshold -= 3; 1252: 1.1.1.2 root 1253: /* Any other movable that loads the same register 1254: MUST be moved. */ 1255: already_moved[regno] = 1; 1256: 1.1.1.12 root 1257: /* This reg has been moved out of one loop. */ 1258: moved_once[regno] = 1; 1259: 1.1.1.2 root 1260: /* The reg set here is now invariant. */ 1261: if (! m->partial) 1262: n_times_set[regno] = 0; 1263: 1264: m->done = 1; 1265: 1.1.1.10 root 1266: /* Change the length-of-life info for the register 1267: to say it lives at least the full length of this loop. 1268: This will help guide optimizations in outer loops. */ 1269: 1270: if (uid_luid[regno_first_uid[regno]] > INSN_LUID (loop_start)) 1271: /* This is the old insn before all the moved insns. 1272: We can't use the moved insn because it is out of range 1273: in uid_luid. Only the old insns have luids. */ 1274: regno_first_uid[regno] = INSN_UID (loop_start); 1275: if (uid_luid[regno_last_uid[regno]] < INSN_LUID (end)) 1276: regno_last_uid[regno] = INSN_UID (end); 1277: 1.1.1.2 root 1278: /* Combine with this moved insn any other matching movables. */ 1.1 root 1279: 1280: for (m1 = m->next; m1; m1 = m1->next) 1281: if (m1->match == m) 1282: { 1.1.1.8 root 1283: rtx temp; 1284: 1.1 root 1285: /* Schedule the reg loaded by M1 1286: for replacement so that shares the reg of M. */ 1287: reg_map[m1->regno] = SET_DEST (PATTERN (m->insn)); 1.1.1.2 root 1288: /* Get rid of the matching insn 1.1 root 1289: and prevent further processing of it. */ 1.1.1.2 root 1290: m1->done = 1; 1.1.1.8 root 1291: 1292: /* if library call, delete all insn except last, which 1293: is deleted below */ 1294: if (temp = find_reg_note (m1->insn, REG_RETVAL, 0)) 1295: { 1296: for (temp = XEXP (temp, 0); temp != m1->insn; 1297: temp = NEXT_INSN (temp)) 1298: delete_insn (temp); 1299: } 1.1 root 1300: delete_insn (m1->insn); 1.1.1.2 root 1301: 1302: /* Any other movable that loads the same register 1303: MUST be moved. */ 1304: already_moved[m1->regno] = 1; 1305: 1.1.1.13 root 1306: /* The reg merged here is now invariant, 1307: if the reg it matches is invariant. */ 1308: if (! m->partial) 1.1.1.2 root 1309: n_times_set[m1->regno] = 0; 1.1 root 1310: } 1311: } 1.1.1.2 root 1312: else if (loop_dump_stream) 1313: fprintf (loop_dump_stream, "not desirable"); 1.1 root 1314: } 1.1.1.2 root 1315: else if (loop_dump_stream && !m->match) 1316: fprintf (loop_dump_stream, "not safe"); 1.1 root 1317: 1.1.1.2 root 1318: if (loop_dump_stream) 1319: fprintf (loop_dump_stream, "\n"); 1320: } 1.1 root 1321: 1.1.1.2 root 1322: if (new_start == 0) 1323: new_start = loop_start; 1.1 root 1324: 1.1.1.2 root 1325: /* Go through all the instructions in the loop, making 1326: all the register substitutions scheduled in REG_MAP. */ 1327: for (p = new_start; p != end; p = NEXT_INSN (p)) 1328: if (GET_CODE (p) == INSN || GET_CODE (p) == JUMP_INSN 1329: || GET_CODE (p) == CALL_INSN) 1.1.1.8 root 1330: replace_regs (PATTERN (p), reg_map, nregs); 1.1.1.2 root 1331: } 1332: 1333: /* Optionally change a loop which enters just before the endtest 1334: to one which falls straight in 1335: after skipping around the entire loop if the endtest would drop out. 1336: Returns 1 if the change was made, 0 if the loop was not really suitable. */ 1337: 1338: int 1339: loop_skip_over (start, end, loop_entry_jump) 1340: rtx start; 1341: rtx end; 1342: rtx loop_entry_jump; 1343: { 1344: rtx endtestjump; 1345: register rtx p = JUMP_LABEL (loop_entry_jump); 1.1 root 1346: 1.1.1.2 root 1347: while (GET_CODE (p) != INSN && GET_CODE (p) != JUMP_INSN 1348: && GET_CODE (p) != CALL_INSN) 1349: p = NEXT_INSN (p); 1350: endtestjump = next_real_insn (p); 1351: 1352: /* Check that we (1) enter at a compare insn and (2) 1353: the insn (presumably a jump) following that compare 1354: is the last in the loop and jumps back to the loop beginning. */ 1355: 1.1.1.8 root 1356: if (sets_cc0_p (PATTERN (p)) > 0 1.1.1.2 root 1357: && endtestjump == prev_real_insn (end) 1358: && prev_real_insn (JUMP_LABEL (endtestjump)) == loop_entry_jump) 1.1 root 1359: { 1.1.1.2 root 1360: rtx newlab; 1361: /* This is the jump that we insert. */ 1362: rtx new_jump; 1363: 1364: /* Ok, duplicate that test before start of loop. */ 1365: emit_insn_before (copy_rtx (PATTERN (p)), start); 1366: /* Make a new entry-jump (before the original one) 1367: whose condition is opposite to the loop-around endtest 1.1.1.8 root 1368: and which jumps around the loop (to just after the ending NOTE). */ 1.1.1.2 root 1369: newlab = gen_label_rtx (); 1.1.1.8 root 1370: emit_label_after (newlab, end); 1.1.1.2 root 1371: emit_jump_insn_before (copy_rtx (PATTERN (endtestjump)), start); 1372: new_jump = PREV_INSN (start); 1373: JUMP_LABEL (new_jump) = JUMP_LABEL (endtestjump); 1374: LABEL_NUSES (JUMP_LABEL (endtestjump))++; 1375: invert_jump (new_jump, newlab); 1376: /* Delete the original entry-jump. */ 1377: delete_insn (loop_entry_jump); 1.1 root 1378: 1.1.1.2 root 1379: return 1; 1.1 root 1380: } 1.1.1.2 root 1381: 1382: return 0; 1.1 root 1383: } 1384: 1385: /* Throughout the rtx X, replace many registers according to REG_MAP. 1386: Return the replacement for X (which may be X with altered contents). 1.1.1.8 root 1387: REG_MAP[R] is the replacement for register R, or 0 for don't replace. 1388: NREGS is the length of REG_MAP; regs >= NREGS are not mapped. */ 1.1 root 1389: 1390: static rtx 1.1.1.8 root 1391: replace_regs (x, reg_map, nregs) 1.1 root 1392: rtx x; 1393: rtx *reg_map; 1.1.1.8 root 1394: int nregs; 1.1 root 1395: { 1.1.1.12 root 1396: register enum rtx_code code; 1.1 root 1397: register int i; 1398: register char *fmt; 1399: 1.1.1.12 root 1400: if (x == 0) 1401: return x; 1402: 1403: code = GET_CODE (x); 1.1 root 1404: switch (code) 1405: { 1406: case PC: 1407: case CC0: 1408: case CONST_INT: 1409: case CONST_DOUBLE: 1410: case CONST: 1411: case SYMBOL_REF: 1412: case LABEL_REF: 1413: return x; 1414: 1415: case REG: 1.1.1.8 root 1416: /* Verify that the register has an entry before trying to access it. */ 1417: if (REGNO (x) < nregs && reg_map[REGNO (x)] != 0) 1.1 root 1418: return reg_map[REGNO (x)]; 1419: return x; 1420: } 1421: 1422: fmt = GET_RTX_FORMAT (code); 1423: for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) 1424: { 1425: if (fmt[i] == 'e') 1.1.1.8 root 1426: XEXP (x, i) = replace_regs (XEXP (x, i), reg_map, nregs); 1.1 root 1427: if (fmt[i] == 'E') 1428: { 1429: register int j; 1430: for (j = 0; j < XVECLEN (x, i); j++) 1.1.1.8 root 1431: XVECEXP (x, i, j) = replace_regs (XVECEXP (x, i, j), reg_map, nregs); 1.1 root 1432: } 1433: } 1434: return x; 1435: } 1436: 1.1.1.9 root 1437: /* Scan X and replace the address of any MEM in it with ADDR. 1438: REG is the address that MEM should have before the replacement. */ 1439: 1440: static void 1441: replace_call_address (x, reg, addr) 1442: rtx x, reg, addr; 1443: { 1.1.1.12 root 1444: register enum rtx_code code; 1.1.1.9 root 1445: register int i; 1446: register char *fmt; 1447: 1.1.1.12 root 1448: if (x == 0) 1449: return; 1450: code = GET_CODE (x); 1.1.1.9 root 1451: switch (code) 1452: { 1453: case PC: 1454: case CC0: 1455: case CONST_INT: 1456: case CONST_DOUBLE: 1457: case CONST: 1458: case SYMBOL_REF: 1459: case LABEL_REF: 1460: case REG: 1461: return; 1462: 1463: case SET: 1464: /* Short cut for very common case. */ 1465: replace_call_address (XEXP (x, 1), reg, addr); 1466: return; 1467: 1468: case CALL: 1469: /* Short cut for very common case. */ 1470: replace_call_address (XEXP (x, 0), reg, addr); 1471: return; 1472: 1473: case MEM: 1474: /* If this MEM uses a reg other than the one we expected, 1475: something is wrong. */ 1476: if (XEXP (x, 0) != reg) 1477: abort (); 1478: XEXP (x, 0) = addr; 1479: return; 1480: } 1481: 1482: fmt = GET_RTX_FORMAT (code); 1483: for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) 1484: { 1485: if (fmt[i] == 'e') 1486: replace_call_address (XEXP (x, i), reg, addr); 1487: if (fmt[i] == 'E') 1488: { 1489: register int j; 1490: for (j = 0; j < XVECLEN (x, i); j++) 1491: replace_call_address (XVECEXP (x, i, j), reg, addr); 1492: } 1493: } 1494: } 1495: 1.1.1.15! root 1496: /* Return the number of memory refs to addresses that vary ! 1497: in the rtx X. */ ! 1498: ! 1499: static int ! 1500: count_nonfixed_reads (x) ! 1501: rtx x; ! 1502: { ! 1503: register enum rtx_code code; ! 1504: register int i; ! 1505: register char *fmt; ! 1506: int value; ! 1507: ! 1508: if (x == 0) ! 1509: return 0; ! 1510: ! 1511: code = GET_CODE (x); ! 1512: switch (code) ! 1513: { ! 1514: case PC: ! 1515: case CC0: ! 1516: case CONST_INT: ! 1517: case CONST_DOUBLE: ! 1518: case CONST: ! 1519: case SYMBOL_REF: ! 1520: case LABEL_REF: ! 1521: case REG: ! 1522: return 0; ! 1523: ! 1524: case MEM: ! 1525: return rtx_varies_p (XEXP (x, 0)) + count_nonfixed_reads (XEXP (x, 0)); ! 1526: } ! 1527: ! 1528: value = 0; ! 1529: fmt = GET_RTX_FORMAT (code); ! 1530: for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) ! 1531: { ! 1532: if (fmt[i] == 'e') ! 1533: value += count_nonfixed_reads (XEXP (x, i)); ! 1534: if (fmt[i] == 'E') ! 1535: { ! 1536: register int j; ! 1537: for (j = 0; j < XVECLEN (x, i); j++) ! 1538: value += count_nonfixed_reads (XVECEXP (x, i, j)); ! 1539: } ! 1540: } ! 1541: return value; ! 1542: } ! 1543: ! 1544: 1.1.1.4 root 1545: #if 0 1.1 root 1546: /* P is an instruction that sets a register to the result of a ZERO_EXTEND. 1547: Replace it with an instruction to load just the low bytes 1548: if the machine supports such an instruction, 1549: and insert above LOOP_START an instruction to clear the register. */ 1550: 1551: static void 1552: constant_high_bytes (p, loop_start) 1553: rtx p, loop_start; 1554: { 1555: register rtx new; 1556: register int insn_code_number; 1557: 1558: /* Try to change (SET (REG ...) (ZERO_EXTEND (..:B ...))) 1559: to (SET (STRICT_LOW_PART (SUBREG:B (REG...))) ...). */ 1560: 1561: new = gen_rtx (SET, VOIDmode, 1562: gen_rtx (STRICT_LOW_PART, VOIDmode, 1563: gen_rtx (SUBREG, GET_MODE (XEXP (SET_SRC (PATTERN (p)), 0)), 1564: SET_DEST (PATTERN (p)), 1565: 0)), 1566: XEXP (SET_SRC (PATTERN (p)), 0)); 1567: insn_code_number = recog (new, p); 1568: 1569: if (insn_code_number) 1570: { 1571: register int i; 1572: 1573: /* Clear destination register before the loop. */ 1574: emit_insn_before (gen_rtx (SET, VOIDmode, 1575: SET_DEST (PATTERN (p)), 1576: const0_rtx), 1577: loop_start); 1578: 1579: /* Inside the loop, just load the low part. */ 1580: PATTERN (p) = new; 1581: } 1582: } 1.1.1.4 root 1583: #endif 1.1 root 1584: 1585: /* Verify that the ostensible loop starting at START 1586: really is a loop: nothing jumps into it from outside. 1587: Return the marker for the end of the loop, or zero if not a real loop. 1588: 1589: Also set the variables `unknown_*_altered' and `loop_has_call', 1590: and fill in the array `loop_store_addrs'. */ 1591: 1592: static rtx 1593: verify_loop (f, start) 1594: rtx f, start; 1595: { 1596: register int level = 1; 1597: register rtx insn, end; 1598: 1599: /* First find the LOOP_END that matches. 1600: Also check each insn for storing in memory and record where. */ 1601: 1602: unknown_address_altered = 0; 1603: unknown_aggregate_altered = 0; 1604: fixed_aggregate_altered = 0; 1605: loop_has_call = 0; 1606: loop_store_addrs_idx = 0; 1607: 1.1.1.8 root 1608: num_mem_sets = 0; 1609: loops_enclosed = 1; 1.1.1.14 root 1610: loop_continue = 0; 1.1.1.8 root 1611: 1.1 root 1612: for (insn = NEXT_INSN (start); level > 0; insn = NEXT_INSN (insn)) 1613: { 1614: if (insn == 0) 1.1.1.2 root 1615: /* Parse errors can cause a loop-beg with no loop-end. */ 1616: return 0; 1.1 root 1617: if (GET_CODE (insn) == NOTE) 1618: { 1619: if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG) 1.1.1.8 root 1620: { 1621: ++level; 1622: /* Count number of loops contained in this one. */ 1623: loops_enclosed++; 1624: } 1.1 root 1625: else if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END) 1.1.1.2 root 1626: { 1627: --level; 1628: if (level == 0) 1629: { 1630: end = insn; 1631: break; 1632: } 1633: } 1.1.1.14 root 1634: else if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_CONT) 1635: { 1636: if (level == 1) 1637: loop_continue = insn; 1638: } 1639: 1.1.1.11 root 1640: /* Don't optimize loops containing setjmps. 1641: On some machines, longjmp does not restore the reg 1642: values as of the time of the setjmp. */ 1643: else if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_SETJMP) 1644: return 0; 1.1 root 1645: } 1646: else if (GET_CODE (insn) == CALL_INSN) 1647: { 1648: unknown_address_altered = 1; 1649: loop_has_call = 1; 1650: } 1.1.1.8 root 1651: /* ??? 1652: else if (! unknown_address_altered) */ 1653: else 1.1 root 1654: { 1655: if (GET_CODE (insn) == INSN || GET_CODE (insn) == JUMP_INSN) 1656: note_stores (PATTERN (insn), note_addr_stored); 1657: } 1658: } 1659: 1660: /* Now scan all jumps in the function and see if any of them can 1661: reach a label within the range of the loop. */ 1662: 1663: for (insn = f; insn; insn = NEXT_INSN (insn)) 1664: if (GET_CODE (insn) == JUMP_INSN 1665: /* Don't get fooled by jumps inserted by loop-optimize. 1666: They don't have valid LUIDs, and they never jump into loops. */ 1667: && INSN_UID (insn) < max_uid 1668: && (INSN_LUID (insn) < INSN_LUID (start) 1669: || INSN_LUID (insn) > INSN_LUID (end)) 1670: /* We have a jump that is outside the loop. 1671: Does it jump into the loop? */ 1672: && can_jump_into_range_p (PATTERN (insn), 1673: INSN_LUID (start), INSN_LUID (end))) 1674: return 0; 1675: 1676: #if 0 1677: /* Now scan all labels between them and check for any jumps from outside. 1678: This uses the ref-chains set up by find_basic_blocks. 1679: This code is not used because it's more convenient for other reasons 1680: to do the loop optimization before find_basic_blocks. */ 1681: 1682: for (insn = start; insn != end; insn = NEXT_INSN (insn)) 1683: if (GET_CODE (insn) == CODE_LABEL) 1684: { 1685: register rtx y; 1686: for (y = LABEL_REFS (insn); y != insn; y = LABEL_NEXTREF (y)) 1687: if (INSN_LUID (CONTAINING_INSN (y)) < INSN_LUID (start) 1688: || INSN_LUID (CONTAINING_INSN (y)) > INSN_LUID (end)) 1689: return 0; 1690: } 1691: #endif 1692: 1693: return end; 1694: } 1695: 1696: /* Return 1 if somewhere in X is a LABEL_REF to a label 1697: located between BEG and END. */ 1698: 1699: static int 1700: can_jump_into_range_p (x, beg, end) 1701: rtx x; 1702: int beg, end; 1703: { 1.1.1.12 root 1704: register enum rtx_code code = GET_CODE (x); 1.1 root 1705: register int i; 1706: register char *fmt; 1707: 1708: if (code == LABEL_REF) 1709: { 1710: register int luid = INSN_LUID (XEXP (x, 0)); 1711: return luid > beg && luid < end; 1712: } 1713: 1714: fmt = GET_RTX_FORMAT (code); 1715: for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) 1716: { 1717: if (fmt[i] == 'e') 1718: { 1719: if (can_jump_into_range_p (XEXP (x, i), beg, end)) 1720: return 1; 1721: } 1722: else if (fmt[i] == 'E') 1723: { 1724: register int j; 1725: for (j = 0; j < XVECLEN (x, i); j++) 1726: if (can_jump_into_range_p (XVECEXP (x, i, j), beg, end)) 1727: return 1; 1728: } 1729: } 1730: 1731: return 0; 1732: } 1733: 1.1.1.15! root 1734: /* Return nonzero if there is a label in the range from ! 1735: insn INSN to the insn whose luid is END. */ ! 1736: ! 1737: static int ! 1738: labels_in_range_p (insn, end) ! 1739: rtx insn; ! 1740: int end; ! 1741: { ! 1742: while (insn && INSN_LUID (insn) <= end) ! 1743: { ! 1744: if (GET_CODE (insn) == CODE_LABEL) ! 1745: return 0; ! 1746: insn = NEXT_INSN (insn); ! 1747: } ! 1748: ! 1749: return 0; ! 1750: } ! 1751: 1.1 root 1752: /* Record that a memory reference X is being set. */ 1753: 1754: static void 1755: note_addr_stored (x) 1756: rtx x; 1757: { 1758: if (x == 0 || GET_CODE (x) != MEM) 1759: return; 1.1.1.8 root 1760: 1761: /* Count number of memory writes. 1762: This affects heuristics in strength_reduce. */ 1763: num_mem_sets++; 1764: if (unknown_address_altered) 1765: return; 1766: 1.1.1.2 root 1767: if (GET_MODE (x) == BLKmode) 1768: unknown_address_altered = 1; 1769: else if (rtx_addr_varies_p (x)) 1.1 root 1770: { 1771: if (GET_CODE (XEXP (x, 0)) == PLUS) 1772: unknown_aggregate_altered = 1; 1773: else 1774: unknown_address_altered = 1; 1775: } 1776: else 1777: { 1778: register int i; 1779: register rtx addr = XEXP (x, 0); 1780: 1.1.1.8 root 1781: if (MEM_IN_STRUCT_P (x)) 1.1 root 1782: fixed_aggregate_altered = 1; 1783: for (i = 0; i < loop_store_addrs_idx; i++) 1784: if (rtx_equal_p (loop_store_addrs[i], addr)) 1785: { 1786: if (loop_store_widths[i] < GET_MODE_SIZE (GET_MODE (x))) 1787: loop_store_widths[i] = GET_MODE_SIZE (GET_MODE (x)); 1788: break; 1789: } 1790: if (i == NUM_STORES) 1791: unknown_address_altered = 1; 1792: else if (i == loop_store_addrs_idx) 1793: { 1.1.1.2 root 1794: loop_store_widths[i] = GET_MODE_SIZE (GET_MODE (x)); 1.1 root 1795: loop_store_addrs[loop_store_addrs_idx++] = addr; 1796: } 1797: } 1798: } 1799: 1800: /* Return nonzero if the rtx X is invariant over the current loop. 1801: 1802: The value is 2 if we refer to something only conditionally invariant. 1803: 1804: If `unknown_address_altered' is nonzero, no memory ref is invariant. 1805: Otherwise if `unknown_aggregate_altered' is nonzero, 1806: a memory ref is invariant if it is not part of an aggregate 1807: and its address is fixed and not in `loop_store_addrs'. 1808: Otherwise if `fixed_aggregate_altered' is nonzero, 1809: a memory ref is invariant 1810: if its address is fixed and not in `loop_store_addrs'. 1811: Otherwise, a memory ref is invariant if its address is fixed and not in 1812: `loop_store_addrs' or if it is not an aggregate. */ 1813: 1814: static int 1.1.1.8 root 1815: invariant_p (x) 1.1 root 1816: register rtx x; 1817: { 1818: register int i; 1.1.1.12 root 1819: register enum rtx_code code; 1.1 root 1820: register char *fmt; 1821: int conditional = 0; 1822: 1.1.1.12 root 1823: if (x == 0) 1824: return 1; 1825: code = GET_CODE (x); 1.1 root 1826: switch (code) 1827: { 1828: case CONST_INT: 1829: case CONST_DOUBLE: 1830: case SYMBOL_REF: 1831: case LABEL_REF: 1832: case CONST: 1833: return 1; 1834: 1835: case PC: 1836: case CC0: 1837: return 0; 1838: 1839: case REG: 1.1.1.8 root 1840: /* We used to check RTX_UNCHANGING_P (x) here, but that is invalid 1.1.1.6 root 1841: since the reg might be set by initialization within the loop. */ 1842: if (x == frame_pointer_rtx || x == arg_pointer_rtx) 1.1.1.2 root 1843: return 1; 1.1 root 1844: if (n_times_set[REGNO (x)] == -1) 1845: return 2; 1846: return n_times_set[REGNO (x)] == 0; 1847: 1848: case MEM: 1.1.1.14 root 1849: /* Constants in the constant pool are invariant. 1850: ?? Really we should detect any constant address in the 1851: text section. */ 1852: if (GET_CODE (XEXP (x, 0)) == SYMBOL_REF 1853: && CONSTANT_POOL_ADDRESS_P (XEXP (x, 0))) 1854: return 1; 1.1 root 1855: /* A store in a varying-address scalar (or a subroutine call) 1856: could clobber anything in memory. */ 1857: if (unknown_address_altered) 1858: return 0; 1.1.1.2 root 1859: /* Don't mess with volatile memory references. */ 1.1.1.8 root 1860: if (MEM_VOLATILE_P (x)) 1.1.1.2 root 1861: return 0; 1.1.1.6 root 1862: #if 0 1.1.1.2 root 1863: /* If it's declared read-only, it is invariant 1864: if its address is invariant. */ 1.1.1.8 root 1865: if (RTX_UNCHANGING_P (x)) 1866: return invariant_p (XEXP (x, 0)); 1.1.1.6 root 1867: #endif 1.1 root 1868: /* A store in a varying-address aggregate component 1869: could clobber anything except a scalar with a fixed address. */ 1870: if (unknown_aggregate_altered 1.1.1.8 root 1871: && ((MEM_IN_STRUCT_P (x) || GET_CODE (XEXP (x, 0)) == PLUS) 1.1 root 1872: || rtx_addr_varies_p (x))) 1873: return 0; 1874: /* A store in a fixed-address aggregate component 1875: could clobber anything whose address is not fixed, 1876: even an aggregate component. */ 1877: if (fixed_aggregate_altered 1878: && rtx_addr_varies_p (x)) 1879: return 0; 1880: /* Any store could clobber a varying-address scalar. */ 1881: if (loop_store_addrs_idx 1.1.1.8 root 1882: && !(MEM_IN_STRUCT_P (x) || GET_CODE (XEXP (x, 0)) == PLUS) 1.1 root 1883: && rtx_addr_varies_p (x)) 1884: return 0; 1885: /* A store in a fixed address clobbers overlapping references. */ 1886: for (i = loop_store_addrs_idx - 1; i >= 0; i--) 1.1.1.2 root 1887: if (addr_overlap_p (x, loop_store_addrs[i], loop_store_widths[i])) 1.1 root 1888: return 0; 1889: /* It's not invalidated by a store in memory 1890: but we must still verify the address is invariant. */ 1.1.1.2 root 1891: break; 1892: 1893: case ASM_OPERANDS: 1894: /* Don't mess with insns declared volatile. */ 1.1.1.8 root 1895: if (MEM_VOLATILE_P (x)) 1.1.1.2 root 1896: return 0; 1.1 root 1897: } 1898: 1899: fmt = GET_RTX_FORMAT (code); 1900: for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) 1901: { 1902: if (fmt[i] == 'e') 1903: { 1.1.1.8 root 1904: int tem = invariant_p (XEXP (x, i)); 1.1 root 1905: if (tem == 0) 1906: return 0; 1907: if (tem == 2) 1908: conditional = 1; 1909: } 1.1.1.2 root 1910: else if (fmt[i] == 'E') 1911: { 1912: register int j; 1913: for (j = 0; j < XVECLEN (x, i); j++) 1914: { 1.1.1.8 root 1915: int tem = invariant_p (XVECEXP (x, i, j)); 1.1.1.2 root 1916: if (tem == 0) 1917: return 0; 1918: if (tem == 2) 1919: conditional = 1; 1920: } 1921: 1922: } 1.1 root 1923: } 1924: 1925: return 1 + conditional; 1926: } 1927: 1928: /* Return 1 if OTHER (a mem ref) overlaps the area of memory 1929: which is SIZE bytes starting at BASE. */ 1930: 1931: int 1932: addr_overlap_p (other, base, size) 1933: rtx other; 1934: rtx base; 1935: int size; 1936: { 1937: int start = 0, end; 1938: 1939: if (GET_CODE (base) == CONST) 1940: base = XEXP (base, 0); 1941: if (GET_CODE (base) == PLUS 1942: && GET_CODE (XEXP (base, 1)) == CONST_INT) 1943: { 1944: start = INTVAL (XEXP (base, 1)); 1945: base = XEXP (base, 0); 1946: } 1947: 1948: end = start + size; 1949: return refers_to_mem_p (other, base, start, end); 1950: } 1.1.1.2 root 1951: 1.1.1.4 root 1952: /* Return nonzero if all the insns in the loop that set REG 1.1.1.2 root 1953: are INSN and the immediately following insns, 1954: and if each of those insns sets REG in an invariant way 1.1.1.8 root 1955: (not counting uses of REG in them). 1.1.1.2 root 1956: 1.1.1.4 root 1957: The value is 2 if some of these insns are only conditionally invariant. 1958: 1.1.1.2 root 1959: We assume that INSN itself is the first set of REG 1960: and that its source is invariant. */ 1961: 1962: static int 1.1.1.8 root 1963: consec_sets_invariant_p (reg, n_sets, insn) 1.1.1.4 root 1964: int n_sets; 1.1.1.2 root 1965: rtx reg, insn; 1966: { 1967: register rtx p = insn; 1968: register int regno = REGNO (reg); 1.1.1.8 root 1969: rtx temp; 1.1.1.2 root 1970: /* Number of sets we have to insist on finding after INSN. */ 1.1.1.4 root 1971: int count = n_sets - 1; 1.1.1.8 root 1972: int old = n_times_set[regno]; 1.1.1.15! root 1973: int value = 0; ! 1974: int this; 1.1.1.2 root 1975: 1.1.1.8 root 1976: /* If N_SETS hit the limit, we can't rely on its value. */ 1977: if (n_sets == 127) 1978: return 0; 1979: 1980: n_times_set[regno] = 0; 1.1.1.2 root 1981: 1982: while (count > 0) 1983: { 1984: register enum rtx_code code; 1985: p = NEXT_INSN (p); 1986: code = GET_CODE (p); 1.1.1.8 root 1987: 1988: /* If library call, skip to end of of it. */ 1989: if (code == INSN && (temp = find_reg_note (p, REG_LIBCALL, 0))) 1990: p = XEXP (temp, 0); 1991: 1.1.1.15! root 1992: this = 0; 1.1.1.2 root 1993: if (code == INSN && GET_CODE (PATTERN (p)) == SET 1994: && GET_CODE (SET_DEST (PATTERN (p))) == REG 1.1.1.15! root 1995: && REGNO (SET_DEST (PATTERN (p))) == regno) ! 1996: { ! 1997: this = invariant_p (SET_SRC (PATTERN (p))); ! 1998: if (this != 0) ! 1999: value |= this; ! 2000: else if (temp = find_reg_note (p, REG_EQUAL, 0)) ! 2001: { ! 2002: this = invariant_p (XEXP (temp, 0)); ! 2003: if (this != 0) ! 2004: value |= this; ! 2005: } ! 2006: } ! 2007: if (this != 0) 1.1.1.2 root 2008: count--; 2009: else if (code != NOTE) 2010: { 1.1.1.8 root 2011: n_times_set[regno] = old; 1.1.1.2 root 2012: return 0; 2013: } 2014: } 2015: 1.1.1.8 root 2016: n_times_set[regno] = old; 1.1.1.4 root 2017: /* If invariant_p ever returned 2, we return 2. */ 1.1.1.15! root 2018: return 1 + (value & 2); 1.1.1.2 root 2019: } 2020: 2021: #if 0 2022: /* I don't think this condition is sufficient to allow INSN 2023: to be moved, so we no longer test it. */ 1.1 root 2024: 2025: /* Return 1 if all insns in the basic block of INSN and following INSN 2026: that set REG are invariant according to TABLE. */ 2027: 2028: static int 2029: all_sets_invariant_p (reg, insn, table) 2030: rtx reg, insn; 1.1.1.2 root 2031: short *table; 1.1 root 2032: { 2033: register rtx p = insn; 2034: register int regno = REGNO (reg); 2035: 2036: while (1) 2037: { 2038: register enum rtx_code code; 2039: p = NEXT_INSN (p); 2040: code = GET_CODE (p); 2041: if (code == CODE_LABEL || code == JUMP_INSN) 2042: return 1; 2043: if (code == INSN && GET_CODE (PATTERN (p)) == SET 2044: && GET_CODE (SET_DEST (PATTERN (p))) == REG 2045: && REGNO (SET_DEST (PATTERN (p))) == regno) 2046: { 2047: if (!invariant_p (SET_SRC (PATTERN (p)), table)) 2048: return 0; 2049: } 2050: } 2051: } 1.1.1.2 root 2052: #endif /* 0 */ 1.1 root 2053: 2054: /* Increment N_TIMES_SET at the index of each register 2055: that is modified by an insn between FROM and TO. 1.1.1.8 root 2056: If the value of an element of N_TIMES_SET becomes 127 or more, 2057: stop incrementing it, to avoid overflow. 1.1 root 2058: 2059: Store in *COUNT_PTR the number of actual instruction 2060: in the loop. We use this to decide what is worth moving out. */ 2061: 2062: /* last_set[n] is nonzero iff reg n has been set in the current basic block. 2063: In that case, it is the insn that last set reg n. */ 2064: 2065: static void 1.1.1.8 root 2066: count_loop_regs_set (from, to, may_not_move, count_ptr, nregs) 1.1 root 2067: register rtx from, to; 2068: char *may_not_move; 2069: int *count_ptr; 2070: int nregs; 2071: { 2072: register rtx *last_set = (rtx *) alloca (nregs * sizeof (rtx)); 2073: register rtx insn; 2074: register int count = 0; 2075: register rtx dest; 2076: 2077: bzero (last_set, nregs * sizeof (rtx)); 2078: for (insn = from; insn != to; insn = NEXT_INSN (insn)) 2079: { 1.1.1.2 root 2080: if (GET_CODE (insn) == CALL_INSN) 2081: { 2082: /* If a register is used as a subroutine address, 2083: don't allow this register's setting to be moved out of the loop. 2084: This condition is not at all logically correct 2085: but it averts a very common lossage pattern 2086: and creates lossage much less often. */ 2087: if (GET_CODE (PATTERN (insn)) == CALL 2088: && GET_CODE (XEXP (PATTERN (insn), 0)) == MEM 2089: && GET_CODE (XEXP (XEXP (PATTERN (insn), 0), 0)) == REG) 2090: { 2091: register int regno 2092: = REGNO (XEXP (XEXP (PATTERN (insn), 0), 0)); 2093: may_not_move[regno] = 1; 2094: } 2095: else if (GET_CODE (PATTERN (insn)) == SET 2096: && GET_CODE (SET_SRC (PATTERN (insn))) == CALL 2097: && GET_CODE (XEXP (SET_SRC (PATTERN (insn)), 0)) == MEM 2098: && GET_CODE (XEXP (XEXP (SET_SRC (PATTERN (insn)), 0), 0)) == REG) 2099: { 2100: register int regno 2101: = REGNO (XEXP (XEXP (SET_SRC (PATTERN (insn)), 0), 0)); 2102: may_not_move[regno] = 1; 2103: /* The call insn itself sets a reg, which cannot be moved. */ 2104: may_not_move[REGNO (SET_DEST (PATTERN (insn)))] = 1; 1.1.1.8 root 2105: if (n_times_set[REGNO (SET_DEST (PATTERN (insn)))] < 127) 2106: n_times_set[REGNO (SET_DEST (PATTERN (insn)))]++; 1.1.1.2 root 2107: } 2108: } 2109: if (GET_CODE (insn) == INSN || GET_CODE (insn) == JUMP_INSN) 1.1 root 2110: { 2111: ++count; 1.1.1.2 root 2112: if (GET_CODE (PATTERN (insn)) == CLOBBER 2113: && GET_CODE (XEXP (PATTERN (insn), 0)) == REG) 2114: /* Don't move a reg that has an explicit clobber. 2115: We might do so sometimes, but it's not worth the pain. */ 2116: may_not_move[REGNO (XEXP (PATTERN (insn), 0))] = 1; 2117: else if (GET_CODE (PATTERN (insn)) == SET) 1.1 root 2118: { 2119: dest = SET_DEST (PATTERN (insn)); 2120: while (GET_CODE (dest) == SUBREG 2121: || GET_CODE (dest) == ZERO_EXTRACT 2122: || GET_CODE (dest) == SIGN_EXTRACT 2123: || GET_CODE (dest) == STRICT_LOW_PART) 2124: dest = XEXP (dest, 0); 2125: if (GET_CODE (dest) == REG) 2126: { 2127: register int regno = REGNO (dest); 2128: /* If this is the first setting of this reg 2129: in current basic block, and it was set before, 2130: it must be set in two basic blocks, so it cannot 2131: be moved out of the loop. */ 2132: if (n_times_set[regno] > 0 && last_set[regno] == 0) 2133: may_not_move[regno] = 1; 2134: /* If this is not first setting in current basic block, 2135: see if reg was used in between previous one and this. 2136: If so, neither one can be moved. */ 2137: if (last_set[regno] != 0 2138: && reg_used_between_p (dest, last_set[regno], insn)) 2139: may_not_move[regno] = 1; 1.1.1.8 root 2140: if (n_times_set[regno] < 127) 2141: ++n_times_set[regno]; 1.1 root 2142: last_set[regno] = insn; 2143: } 2144: } 2145: else if (GET_CODE (PATTERN (insn)) == PARALLEL) 2146: { 2147: register int i; 2148: for (i = XVECLEN (PATTERN (insn), 0) - 1; i >= 0; i--) 2149: { 2150: register rtx x = XVECEXP (PATTERN (insn), 0, i); 1.1.1.2 root 2151: if (GET_CODE (x) == CLOBBER && GET_CODE (XEXP (x, 0)) == REG) 2152: /* Don't move a reg that has an explicit clobber. 2153: It's not worth the pain to try to do it correctly. */ 2154: may_not_move[REGNO (XEXP (x, 0))] = 1; 1.1 root 2155: if (GET_CODE (x) == SET) 2156: { 2157: dest = SET_DEST (x); 2158: while (GET_CODE (dest) == SUBREG 2159: || GET_CODE (dest) == ZERO_EXTRACT 2160: || GET_CODE (dest) == SIGN_EXTRACT 2161: || GET_CODE (dest) == STRICT_LOW_PART) 2162: dest = XEXP (dest, 0); 2163: if (GET_CODE (dest) == REG) 2164: { 2165: register int regno = REGNO (dest); 1.1.1.8 root 2166: if (n_times_set[regno] < 127) 2167: ++n_times_set[regno]; 1.1 root 2168: may_not_move[regno] = 1; 2169: last_set[regno] = insn; 2170: } 2171: } 2172: } 2173: } 2174: } 2175: if (GET_CODE (insn) == CODE_LABEL || GET_CODE (insn) == JUMP_INSN) 2176: bzero (last_set, nregs * sizeof (rtx)); 2177: } 2178: *count_ptr = count; 2179: } 2180: 2181: /* Given a loop that is bounded by LOOP_START and LOOP_END 2182: and that is entered at SCAN_START, 2183: return 1 if the register set by insn INSN is used by 2184: any insn that precedes INSN in cyclic order starting 2185: from the loop entry point. */ 2186: 2187: static int 2188: loop_reg_used_before_p (insn, loop_start, scan_start, loop_end) 2189: rtx insn, loop_start, scan_start, loop_end; 2190: { 2191: rtx reg = SET_DEST (PATTERN (insn)); 2192: if (INSN_LUID (scan_start) > INSN_LUID (insn)) 2193: return (reg_used_between_p (reg, scan_start, loop_end) 2194: || reg_used_between_p (reg, loop_start, insn)); 2195: else 2196: return reg_used_between_p (reg, scan_start, insn); 2197: } 1.1.1.8 root 2198: 2199: /* A "basic induction variable" or biv is a pseudo reg that is set 2200: (within this loop) only by incrementing or decrementing it. */ 2201: /* A "general induction variable" or giv is a pseudo reg whose 2202: value is a linear function of a biv. */ 2203: 2204: /* Bivs are recognized by `basic_induction_var'; 2205: Givs by `general_induct_var'. */ 2206: 2207: /* An enum for the two different types of givs, those that are used 2208: as memory addresses and those that are calculated into registers. */ 2209: enum g_types { DEST_ADDR, DEST_REG }; 2210: 2211: /* A `struct induction' is created for every instruction that sets 2212: an induction variable (either a biv or a giv). */ 2213: 2214: struct induction 2215: { 2216: rtx insn; /* The insn that sets a biv or giv */ 2217: rtx new_reg; /* New register, containing strength reduced 2218: version of this giv. */ 2219: int src_regno; /* Biv from which this giv is computed. 2220: (If this is a biv, then this is the biv.) */ 2221: enum g_types giv_type; /* Indicate whether DEST_ADDR or DEST_REG giv */ 2222: int dest_regno; /* Destination register for insn: this is the 2223: register which was the biv or giv. 2224: For a biv, this equals src_reg. 2225: For a DEST_ADDR type giv, this is 0. */ 2226: rtx *location; /* Place in the insn where this giv occurs. 2227: If GIV_TYPE is DEST_REG, this is 0. */ 1.1.1.14 root 2228: enum machine_mode mode; /* The mode of this biv or giv */ 1.1.1.8 root 2229: rtx mult_val; /* Multiplicative factor for src_reg. */ 2230: rtx add_val; /* Additive constant for that product. */ 2231: int benefit; /* Gain from eliminating this insn. */ 2232: int consec; /* The number of consecutive insn that set this 2233: register; they are all eliminated if this 2234: one is. */ 2235: char replaceable; /* 1 if we can substitute the strength-reduced 2236: variable for the original variable. 2237: 0 means they must be kept separate and the 2238: new one must be copied into the old pseudo 2239: reg each time the old one is set. */ 2240: char ignore; /* 1 prohibits further processing of this giv */ 2241: int lifetime; /* Length of life of this giv */ 2242: int times_used; /* # times this giv is used. */ 2243: struct induction *family; /* Links together all induction variables that 2244: have the same src register. */ 2245: struct induction *forces; /* Points to an induction variable insn which 2246: is used only once, to compute this giv, 2247: and hence can be deleted if this insn is 2248: strength reduced. */ 2249: struct induction *forces2; /* Likewise. */ 2250: struct induction *same; /* Links together all induction variables that 2251: have the same tuple (src, mult, add). */ 2252: }; 2253: 2254: /* A `struct iv_class' is created for each biv. */ 2255: 2256: struct iv_class { 2257: int regno; /* Pseudo reg which is the biv. */ 2258: int biv_count; /* Number of insns setting this reg. */ 2259: struct induction *biv; /* List of all insns that set this reg. */ 1.1.1.14 root 2260: int giv_count; /* Number of DEST_REG givs computed from this 2261: biv. The resulting count is only used in 2262: check_dbra_loop. */ 1.1.1.8 root 2263: struct induction *giv; /* List of all insns that compute a giv 2264: from this reg. */ 2265: int total_benefit; /* Sum of BENEFITs of all those givs */ 2266: rtx initial_value; /* Value of reg at loop start */ 2267: struct iv_class *next; /* Links all class structures together */ 1.1.1.14 root 2268: rtx init_insn; /* insn which intializes biv, 0 if none seen. */ 1.1.1.8 root 2269: char eliminable; /* 1 if plausible candidate for elimination. */ 2270: char nonneg; /* 1 if we added a REG_NONNEG note for this. */ 2271: }; 2272: 2273: /* Definitions used by the basic induction variable discovery code. */ 2274: enum iv_mode { UNKNOWN_INDUCT, BASIC_INDUCT, NOT_BASIC_INDUCT, 2275: GENERAL_INDUCT }; 2276: 2277: /* Relative gain of eliminating various kinds of operations. */ 2278: #define NO_BENEFIT 0 2279: #define ADD_BENEFIT 1 2280: #define SHIFT_BENEFIT 2 2281: #define MULT_BENEFIT 4 2282: #define LIBCALL_BENEFIT 15 2283: /* Benefit penalty, if a giv is not replaceable, i.e. must emit an insn to 2284: copy the value of the strength reduced giv to its original register. */ 2285: #define COPY_PENALTY 2 2286: 2287: /* Indexed by register number, indicates whether or not register is an 2288: induction variable, and if so what type. */ 2289: 2290: static enum iv_mode *induct_var; 2291: 2292: /* Indexed by register number, contains pointer to `struct induction' 2293: if register is a general induction variable. */ 2294: 2295: static struct induction **induct_struct; 2296: 2297: /* Indexed by register number, contains pointer to `struct iv_class' 2298: if register is a basic induction variable. */ 2299: 2300: static struct iv_class **class_struct; 2301: 2302: /*********************************/ 2303: 2304: /* ??? Unfinished optimizations, [email protected] */ 2305: 2306: /* strength reduce addresses found in sources (set () (mem ())*/ 2307: 2308: /* There is one more optimization you might be interested in doing: to 2309: allocate pseudo registers for frequently-accessed memory locations. 2310: If the same memory location is referenced each time around, it might 2311: be possible to copy it into a register before and out after. 2312: This is especially useful when the memory location is a variable which 2313: is in a stack slot because somewhere its address is taken. If the 2314: loop doesn't contain a function call and the variable isn't volatile, 2315: it is safe to keep the value in a register for the duration of the 2316: loop. One tricky thing is that the copying of the value back from the 2317: register has to be done on all exits from the loop. You need to check that 2318: all the exits from the loop go to the same place. */ 2319: 2320: /* WARNING: the interaction of biv elimination, and recognizing 'constant' 2321: bivs may cause problems */ 2322: 2323: /* add heuristic so that DEST_ADDR strength reduction does not cause 2324: performance problems */ 2325: 2326: /* don't eliminate things that can be combined with an addressing mode? 2327: find all giv that have same biv and mult_val (now must also have 2328: same add_val), then for each giv, check to see if its only use 2329: dies in a following memory address, generate a new memory address 2330: and check to see if valid, if valid then store modified mem addr, 2331: else if not valid addr mark giv as not done so that it will get its 2332: own iv */ 2333: 2334: /* consec_sets_giv does not calculate replaceable and forces correctly, 2335: forces should be a more general linked list instead of two entries */ 2336: 2337: /* try to optimize branches when it is known that a biv is always positive */ 2338: 2339: /* when replace biv in compare insn, should replace with closest giv so that 2340: an optimized branch can still be recognized by combiner, i.e. VAXen acb */ 2341: 2342: /* should merge final_value calculation in check_dbra_loop with the 2343: new final_biv_value function */ 2344: 2345: /* many of the checks involving uid_luid could be simplified if regscan 2346: was rerun in loop_optimize() whenever a register was added or moved, 2347: also some of the optimizations could be a little less conservative */ 2348: 2349: /* Perform strength reduction and induction variable elimination. */ 2350: 2351: /* Pseudo registers created during this function will be beyond the last 2352: valid index in several tables including n_times_set and regno_last_uid. 2353: This does not cause a problem here, because the added registers cannot be 2354: givs outside of their loop, and hence will never be reconsidered. 2355: But scan_loop must check regnos to make sure they are in bounds. */ 2356: 2357: static void 2358: strength_reduce (scan_start, end, loop_top, insn_count, 2359: loop_start, loop_end, nregs) 2360: rtx scan_start; 2361: rtx end; 2362: rtx loop_top; 2363: int insn_count; 2364: rtx loop_start; 2365: rtx loop_end; 2366: int nregs; 2367: { 2368: rtx p; 2369: rtx inc_val; 2370: rtx mult_val; 2371: int dest_regno; 2372: int biv_found; 2373: /* This is 1 if current insn could be executed zero times in the loop. */ 2374: int maybe_never = 0; 2375: /* List of all possible basic induction variables. */ 2376: struct iv_class *iv_list = 0; 2377: /* Temporary list pointers for traversing iv_list. */ 2378: struct iv_class *bl, *backbl; 2379: /* Ratio of extra register life span we can justify 2380: for saving an instruction. More if loop doesn't call subroutines 2381: since in that case saving an insn makes more difference 2382: and more registers are available. */ 2383: /* ??? could set this to last value of threshold in move_movables */ 2384: int threshold = loop_has_call ? 17 : 34; 2385: /* Map of pseudo-register replacements. */ 2386: rtx *reg_map; 1.1.1.15! root 2387: int call_seen; 1.1.1.8 root 2388: 2389: induct_var = (enum iv_mode *) alloca (nregs * sizeof (induct_var[0])); 2390: bzero ((char *)induct_var, nregs * sizeof (induct_var[0])); 2391: induct_struct = (struct induction **) 2392: alloca (nregs * sizeof (struct induction *)); 2393: bzero ((char *)induct_struct, nregs * sizeof (struct induction *)); 2394: class_struct = (struct iv_class **) 2395: alloca (nregs * sizeof (struct iv_class *)); 2396: bzero ((char *)class_struct, nregs * sizeof (struct iv_class *)); 2397: 2398: /* Scan through loop to find all possible bivs. */ 2399: 2400: for (p = NEXT_INSN (loop_start); p != end; p = NEXT_INSN (p)) 2401: { 2402: if (GET_CODE (p) == INSN 2403: && GET_CODE (PATTERN (p)) == SET 2404: && GET_CODE (SET_DEST (PATTERN (p))) == REG) 2405: { 2406: dest_regno = REGNO (SET_DEST (PATTERN (p))); 1.1.1.15! root 2407: if (induct_var[dest_regno] != NOT_BASIC_INDUCT ! 2408: && dest_regno >= FIRST_PSEUDO_REGISTER) 1.1.1.8 root 2409: { 2410: if (basic_induction_var (SET_SRC (PATTERN (p)), dest_regno, 2411: &inc_val, &mult_val)) 2412: { 2413: /* It is a possible basic induction variable. 2414: Create and initialize an induction structure for it. */ 2415: 2416: struct induction *v = 2417: (struct induction *) alloca (sizeof (struct induction)); 2418: 2419: v->insn = p; 2420: v->src_regno = dest_regno; 2421: v->dest_regno = dest_regno; 2422: v->mult_val = mult_val; 2423: v->add_val = inc_val; 1.1.1.14 root 2424: v->mode = GET_MODE (SET_DEST (PATTERN (p))); 1.1.1.8 root 2425: 2426: /* Add this to the reg's iv_class, creating a class 2427: if this is the first incrementation of the reg. */ 2428: 2429: bl = class_struct[dest_regno]; 2430: if (bl) 2431: { 2432: v->family = bl->biv; 2433: bl->biv = v; 2434: bl->biv_count++; 2435: } 2436: else 2437: { 2438: /* Create and initialize new iv_class. */ 2439: 2440: bl = (struct iv_class *) alloca (sizeof (struct iv_class)); 2441: 2442: bl->regno = dest_regno; 2443: bl->biv = v; 2444: v->family = 0; 2445: bl->giv = 0; 2446: bl->biv_count = 1; 2447: bl->giv_count = 0; 2448: 2449: /* Set initial value to the reg itself. */ 2450: bl->initial_value = SET_DEST (PATTERN (p)); 1.1.1.14 root 2451: /* We haven't seen the intializing insn yet */ 2452: bl->init_insn = 0; 1.1.1.8 root 2453: bl->eliminable = 0; 2454: bl->nonneg = 0; 2455: 2456: /* Add this insn to iv_list. */ 2457: bl->next = iv_list; 2458: iv_list = bl; 2459: 2460: /* Put it in the array of iv_lists. */ 2461: class_struct[dest_regno] = bl; 2462: } 2463: 2464: induct_var[dest_regno] = BASIC_INDUCT; 2465: 2466: if (loop_dump_stream) 2467: { 2468: fprintf (loop_dump_stream, 2469: "Insn %d: possible biv, reg %d,", 2470: INSN_UID (p), dest_regno); 2471: if (GET_CODE (inc_val) == CONST_INT) 2472: fprintf (loop_dump_stream, " const = %d\n", 2473: INTVAL (inc_val)); 2474: else 2475: { 2476: fprintf (loop_dump_stream, " const = "); 2477: print_rtl (loop_dump_stream, inc_val); 2478: fprintf (loop_dump_stream, "\n"); 2479: } 2480: } 2481: } 2482: else 2483: induct_var[dest_regno] = NOT_BASIC_INDUCT; 2484: } 2485: } 2486: } 2487: 2488: /* Scan iv_list to remove all regs that proved not to be bivs. 2489: Make a sanity check against n_times_set. */ 2490: 2491: biv_found = 0; 2492: 2493: for (backbl = bl = iv_list; bl; backbl = bl, bl = bl->next) 2494: { 2495: if (induct_var[bl->regno] != BASIC_INDUCT) 2496: { 2497: /* Not a basic induction variable, remove this iv_class. */ 2498: 2499: if (backbl == bl) 2500: iv_list = bl->next; 2501: else 2502: backbl->next = bl->next; 2503: 2504: if (loop_dump_stream) 2505: fprintf (loop_dump_stream, "Reg %d: biv discarded, not induct\n", 2506: bl->regno); 2507: } 2508: else if (n_times_set[bl->regno] != bl->biv_count) 2509: { 2510: /* This happens if register modified by subreg, etc. */ 2511: /* Make sure it is not recognized as a basic induction var: */ 2512: /* remove this iv_class from iv_list. */ 2513: 2514: induct_var[bl->regno] = NOT_BASIC_INDUCT; 2515: 2516: if (backbl == bl) 2517: iv_list = bl->next; 2518: else 2519: backbl->next = bl->next; 2520: 2521: if (loop_dump_stream) 2522: fprintf (loop_dump_stream, "Reg %d: biv discarded, count error\n", 2523: bl->regno); 2524: } 2525: else 2526: { 2527: /* This is a valid basic induction variable. */ 2528: 2529: biv_found++; 2530: 2531: if (loop_dump_stream) 2532: fprintf (loop_dump_stream, "Reg %d: biv verified\n", bl->regno); 2533: } 2534: } 2535: 2536: /* Exit if there are no bivs. */ 2537: if (!iv_list) 2538: return; 2539: 2540: /* Find initial value for each biv. */ 2541: /* Search backwards from loop_start, halting at first label 2542: or when all bivs have been seen. */ 2543: 1.1.1.15! root 2544: call_seen = 0; 1.1.1.8 root 2545: p = loop_start; 2546: while (biv_found) 2547: { 2548: p = PREV_INSN (p); 2549: if (p == 0) 2550: break; 2551: 1.1.1.15! root 2552: if (GET_CODE (p) == CALL_INSN) ! 2553: call_seen = 1; ! 2554: 1.1.1.8 root 2555: if (GET_CODE (p) == INSN 2556: && GET_CODE (PATTERN (p)) == SET 2557: && GET_CODE (SET_DEST (PATTERN (p))) == REG) 2558: { 2559: int dest_regno = REGNO (SET_DEST (PATTERN (p))); 2560: 2561: if (induct_var[dest_regno] == BASIC_INDUCT 1.1.1.14 root 2562: && class_struct[dest_regno]->init_insn == 0) 1.1.1.8 root 2563: { 2564: /* This is the first modification found for this reg. */ 2565: 1.1.1.15! root 2566: rtx src = SET_SRC (PATTERN (p)); ! 2567: 1.1.1.14 root 2568: /* Record the intializing INSN */ 2569: 2570: class_struct[dest_regno]->init_insn = p; 2571: 2572: if (loop_dump_stream) 2573: fprintf (loop_dump_stream, "Biv %d initialized at insn %d: ", 2574: dest_regno, INSN_UID (p)); 2575: 1.1.1.8 root 2576: /* Save value if it is a constant or register. */ 1.1.1.15! root 2577: if (CONSTANT_P (src) ! 2578: || (GET_CODE (src) == REG ! 2579: /* Don't try to use a value in a hard reg ! 2580: across a call which clobbers it. */ ! 2581: && ! (REGNO (src) < FIRST_PSEUDO_REGISTER ! 2582: && call_used_regs[REGNO (src)] ! 2583: && call_seen) ! 2584: && ! reg_set_between_p (src, p, loop_start))) 1.1.1.8 root 2585: { 1.1.1.15! root 2586: class_struct[dest_regno]->initial_value = src; 1.1.1.8 root 2587: 2588: if (loop_dump_stream) 1.1.1.14 root 2589: fprintf (loop_dump_stream, "initial value "); 1.1.1.8 root 2590: if (loop_dump_stream) 2591: { 1.1.1.15! root 2592: if (GET_CODE (src) == CONST_INT) ! 2593: fprintf (loop_dump_stream, "%d\n", INTVAL (src)); 1.1.1.8 root 2594: else 1.1.1.14 root 2595: { 1.1.1.15! root 2596: print_rtl (loop_dump_stream, src); 1.1.1.14 root 2597: fprintf (loop_dump_stream, "\n"); 2598: } 1.1.1.8 root 2599: } 2600: } 2601: else 2602: { 2603: /* Biv initial value is not simple move, 2604: so let it keep intial value of "itself". */ 2605: 2606: if (loop_dump_stream) 1.1.1.14 root 2607: fprintf (loop_dump_stream, "complex initial value\n"); 1.1.1.8 root 2608: } 2609: 2610: biv_found--; 2611: } 2612: } 2613: else if (GET_CODE (p) == CODE_LABEL) 2614: break; 2615: } 2616: 2617: /* Search the loop for general induction variables. */ 2618: 2619: /* A register is a giv if: it is only set once, it is a function of a 2620: biv and a constant (or invariant), and it is not a biv. */ 2621: 2622: p = scan_start; 2623: while (1) 2624: { 2625: p = NEXT_INSN (p); 2626: /* At end of a straight-in loop, we are done. 2627: At end of a loop entered at the bottom, scan the top. */ 2628: if (p == scan_start) 2629: break; 2630: if (p == end) 2631: { 2632: if (loop_top != 0) 2633: p = NEXT_INSN (loop_top); 2634: else 2635: break; 2636: if (p == scan_start) 2637: break; 2638: } 2639: 2640: /* Look for a general induction variable in a register. */ 2641: if (GET_CODE (p) == INSN 2642: && GET_CODE (PATTERN (p)) == SET 2643: && GET_CODE (SET_DEST (PATTERN (p))) == REG) 2644: { 2645: int src_regno; 2646: rtx add_val; 2647: rtx mult_val; 2648: int benefit; 2649: rtx regnote = 0; 2650: struct induction *forces = 0; 2651: struct induction *forces2 = 0; 2652: 2653: dest_regno = REGNO (SET_DEST (PATTERN (p))); 1.1.1.15! root 2654: if (dest_regno < FIRST_PSEUDO_REGISTER) ! 2655: continue; 1.1.1.8 root 2656: 2657: if (/* Normal giv. */ 2658: ((benefit = general_induction_var (SET_SRC (PATTERN (p)), 2659: &src_regno, &add_val, 2660: &mult_val, 2661: &forces, &forces2)) 2662: /* Giv set with call to a library routine. */ 2663: || ((regnote = find_reg_note (p, REG_EQUAL, 0)) 2664: && 2665: (benefit = general_induction_var (XEXP (regnote, 0), 2666: &src_regno, 2667: &add_val, &mult_val, 2668: &forces, &forces2)))) 1.1.1.11 root 2669: /* Don't try to handle any regs made by loop optimization. 2670: We have nothing on them in regno_first_uid, etc. */ 2671: && dest_regno < old_max_reg 1.1.1.8 root 2672: /* Don't recognize a BASIC_INDUCT_VAR here. */ 2673: && dest_regno != src_regno 2674: /* This must be the only place where the register is set. */ 2675: && (n_times_set[dest_regno] == 1 2676: || (benefit = consec_sets_giv (benefit, p, 2677: src_regno, dest_regno, 2678: &add_val, &mult_val)))) 2679: { 2680: int count; 2681: struct induction *v = 2682: (struct induction *) alloca (sizeof (struct induction)); 2683: rtx temp; 2684: 2685: record_giv (v, p, src_regno, dest_regno, mult_val, add_val, benefit, 1.1.1.14 root 2686: forces, forces2, DEST_REG, maybe_never, 0, loop_end); 1.1.1.8 root 2687: 2688: /* Skip the consecutive insns, if there are any. */ 2689: for (count = v->consec - 1; count >= 0; count--) 2690: { 2691: /* If first insn of libcall sequence, skip to end. */ 2692: /* Do this at start of loop, since INSN is guaranteed to 2693: be an insn here. */ 2694: if (temp = find_reg_note (p, REG_LIBCALL, 0)) 2695: { 2696: /* Eliminating a libcall does more good than 2697: eliminating a single insn to do the same job. */ 2698: benefit += LIBCALL_BENEFIT; 2699: p = XEXP (temp, 0); 2700: } 2701: 2702: do p = NEXT_INSN (p); 2703: while (GET_CODE (p) == NOTE); 2704: } 2705: } 2706: } 2707: 2708: #ifndef DONT_REDUCE_ADDR 2709: /* Look for givs which are memory addresses. */ 2710: /* This resulted in worse code on a VAX 8600. I wonder if it 2711: still does. */ 2712: if (GET_CODE (p) == INSN) 1.1.1.14 root 2713: find_mem_givs (PATTERN (p), p, maybe_never, loop_end); 1.1.1.8 root 2714: #endif 2715: 2716: /* Past a label or a jump, we get to insns for which we can't count 2717: on whether or how many times they will be executed during each 2718: iteration. Givs found afterwards cannot be marked replaceable. */ 2719: if (GET_CODE (p) == CODE_LABEL || GET_CODE (p) == JUMP_INSN) 2720: maybe_never = 1; 2721: } 2722: 2723: /* Try to prove that the loop counter variable (if any) is always 2724: nonnegative; if so, record that fact with a REG_NONNEG note 2725: so that "decrement and branch until zero" insn can be used. */ 2726: check_dbra_loop (loop_end, iv_list, insn_count, loop_start); 2727: 2728: /* Create reg_map to hold substitutions for replaceable giv regs. */ 2729: reg_map = (rtx *) alloca (nregs * sizeof (rtx)); 2730: bzero ((char *)reg_map, nregs * sizeof (rtx)); 2731: 2732: /* Examine each iv class for feasibility of strength reduction/induction 2733: variable elimination. */ 2734: 2735: for (bl = iv_list; bl; bl = bl->next) 2736: { 2737: struct induction *v; 2738: int benefit; 2739: int replaceable; 2740: int all_reduced; 2741: rtx final_value = 0; 2742: 2743: /* Test whether it will be possible to eliminate this biv 1.1.1.10 root 2744: provided all givs are reduced. This is possible if either 2745: the reg is not used outside the loop, or we can compute 2746: what its final value will be. 1.1.1.8 root 2747: 2748: Don't try if we put a REG_NONNEG note on the endtest for this biv. 2749: ??? That should be only on machines that have dbra insns. */ 2750: 1.1.1.14 root 2751: /* Compare against bl->init_insn rather than loop_start. 2752: We aren't concerned with any uses of the biv between 2753: init_insn and loop_start since these won't be affected 2754: by the value of the biv elsewhere in the function, so 2755: long as init_insn doesn't use the biv itself. 2756: March 14, 1989 -- [email protected] */ 2757: 1.1.1.8 root 2758: if ((uid_luid[regno_last_uid[bl->regno]] < INSN_LUID (loop_end) 1.1.1.14 root 2759: && bl->init_insn 2760: && uid_luid[regno_first_uid[bl->regno]] >= INSN_LUID (bl->init_insn) 2761: && ! reg_mentioned_p (SET_DEST (PATTERN (bl->biv->insn)), 2762: SET_SRC (PATTERN (bl->init_insn))) 2763: && ! bl->nonneg) 1.1.1.8 root 2764: || (final_value = final_biv_value (bl, loop_end))) 1.1.1.15! root 2765: check_eliminate_biv (bl, loop_start, end); 1.1.1.8 root 2766: else 2767: { 2768: if (loop_dump_stream) 1.1.1.14 root 2769: { 2770: fprintf (loop_dump_stream, 2771: "Cannot eliminate biv %d.\n", 2772: bl->regno); 2773: fprintf (loop_dump_stream, 2774: "First use: insn %d, last use: insn %d.\n", 2775: regno_first_uid[bl->regno], 2776: regno_last_uid[bl->regno]); 2777: } 1.1.1.8 root 2778: } 2779: 2780: /* This will be true at the end, if all givs which depend on this 2781: biv have been strength reduced. 2782: We can't (currently) eliminate the biv unless this is so. */ 2783: all_reduced = 1; 2784: 2785: /* Check each giv in this class. */ 2786: 2787: for (v = bl->giv; v; v = v->family) 2788: { 2789: struct induction *tv; 2790: 2791: if (v->ignore) 2792: continue; 2793: 2794: benefit = v->benefit; 2795: replaceable = v->replaceable; 2796: 2797: /* Reduce benefit if not replaceable, since we will insert 2798: a move-insn to replace the insn that calculates this giv. */ 2799: if (!replaceable && ! bl->eliminable) 2800: benefit -= COPY_PENALTY; 2801: 2802: /* Decrease the benefit to count the add-insns that we will 2803: insert to increment the reduced reg for the giv. */ 2804: benefit -= ADD_BENEFIT * bl->biv_count; 2805: 2806: /* Find all equivalent givs (that bear same relation to the biv). 2807: Link them via the `same' field and add their benefits together. 2808: They can be replaced with a single register. */ 2809: 2810: for (tv = v->family; tv; tv = tv->family) 2811: { 2812: if (tv->ignore == 0 2813: && tv->src_regno == v->src_regno 2814: && rtx_equal_p (tv->mult_val, v->mult_val) 2815: && rtx_equal_p (tv->add_val, v->add_val)) 2816: { 2817: benefit += tv->benefit; 2818: if (! tv->replaceable) 2819: benefit -= COPY_PENALTY; 2820: v->lifetime += tv->lifetime; 2821: v->times_used += tv->times_used; 2822: tv->ignore = 1; 2823: 2824: /* Link them together via `same' field. */ 2825: tv->same = v->same; 2826: v->same = tv; 2827: 2828: if (loop_dump_stream) 2829: fprintf (loop_dump_stream, 2830: "giv of insn %d combined with that of %d.\n", 2831: INSN_UID (v->insn), INSN_UID (tv->insn)); 2832: } 2833: } 2834: 2835: /* Decide whether to strength-reduce this giv 2836: or to leave the code unchanged 2837: (recompute it from the biv each time it is used). 2838: This decision can be made independently for each giv. */ 2839: 2840: /* ??? Perhaps attempt to guess whether autoincrement will handle 2841: some of the new add insns; if so, can increase BENEFIT 2842: (undo the subtraction of ADD_BENEFIT that was done above). */ 2843: 1.1.1.14 root 2844: /* If an insn is not to be strength reduced, then set its ignore 2845: flag, and clear all_reduced. */ 2846: 1.1.1.8 root 2847: /* Is it right to consider times_used? */ 2848: 1.1.1.14 root 2849: /* ??? What about the insns that are 'forced' by this one? 2850: Although this insn is not worthwhile to reduce, it may be 2851: worthwhile to reduce the simpler givs used to compute this 2852: complex giv. */ 2853: 2854: /* ??? Hey! If a giv has its forces field set, then that means 2855: it is not computed directly from the biv, it is instead computed 2856: from a simpler giv. If we define UNFORCE_INSNS, then the simpler 2857: giv will be considered for strength reduction, and this giv should 2858: not cause all_reduced to be cleared because it DOESN'T use the 2859: biv!!! If the simpler giv can not be reduced, then that simpler 2860: biv will still cause all_reduced to be cleared. */ 2861: 1.1.1.8 root 2862: if (benefit <= 0) 2863: { 2864: if (loop_dump_stream) 2865: fprintf (loop_dump_stream, "giv of insn %d, no benefit\n", 2866: INSN_UID (v->insn)); 2867: v->ignore = 1; 1.1.1.14 root 2868: all_reduced = 0; 1.1.1.8 root 2869: } 2870: 2871: if (v->lifetime * threshold * benefit < insn_count) 2872: { 2873: if (loop_dump_stream) 2874: fprintf (loop_dump_stream, 2875: "giv of insn %d not worth while, %d vs %d.\n", 2876: INSN_UID (v->insn), 2877: v->lifetime * threshold * benefit, insn_count); 2878: v->ignore = 1; 1.1.1.14 root 2879: all_reduced = 0; 1.1.1.8 root 2880: } 2881: 2882: /* Now check that we can increment the reduced giv 2883: without needing a multiply insn. If not, reject it. */ 2884: 2885: if (! v->ignore) 2886: { 2887: int success = 1; 2888: 2889: for (tv = bl->biv; tv; tv = tv->family) 2890: if (tv->mult_val == const1_rtx) 2891: success &= product_cheap_p (tv->add_val, v->mult_val); 2892: 2893: if (! success) 2894: { 2895: if (loop_dump_stream) 2896: fprintf (loop_dump_stream, 2897: "giv of insn %d: would need a multiply.\n", 2898: INSN_UID (v->insn)); 2899: v->ignore = 1; 1.1.1.14 root 2900: all_reduced = 0; 1.1.1.8 root 2901: } 2902: } 2903: } 2904: 2905: /* Reduce each giv that we decided to reduce. */ 2906: 2907: for (v = bl->giv; v; v = v->family) 2908: { 2909: struct induction *tv; 2910: if (! v->ignore) 2911: { 1.1.1.11 root 2912: rtx new_reg; 2913: 2914: /* Note Iris compiler dies if ?: is used inside gen_reg_rtx. */ 2915: if (v->giv_type == DEST_ADDR) 2916: new_reg = gen_reg_rtx (Pmode); 2917: else 2918: new_reg = gen_reg_rtx (GET_MODE (SET_DEST (PATTERN (v->insn)))); 1.1.1.8 root 2919: 2920: /* For each place where the biv is incremented, 2921: add an insn to increment the new, reduced reg for the giv. 2922: Insert it before the insn that sets the biv, 2923: so that the biv increment remains last before the endtest, 2924: so that dbra will still be recognized. */ 2925: 2926: for (tv = bl->biv; tv; tv = tv->family) 2927: { 1.1.1.14 root 2928: struct induction *iv; 2929: rtx before_insn = tv->insn; 2930: 2931: /* If this increment is between the setting of the giv and 2932: its use, don't increment until after the use. */ 2933: for (iv = v; iv; iv = iv->same) 2934: { 2935: if (INSN_LUID (tv->insn) <= INSN_LUID (iv->insn) 2936: && ((iv->forces 2937: && (INSN_LUID (tv->insn) 2938: >= INSN_LUID (iv->forces->insn)) 2939: || (iv->forces2 2940: && (INSN_LUID (tv->insn) 2941: >= INSN_LUID (iv->forces2->insn)))))) 2942: { 2943: before_insn = NEXT_INSN (iv->insn); 2944: break; 2945: } 2946: } 2947: 1.1.1.8 root 2948: if (tv->mult_val == const1_rtx) 2949: emit_iv_inc (tv->add_val, v->mult_val, 1.1.1.14 root 2950: new_reg, before_insn); 1.1.1.8 root 2951: else /* tv->mult_val == const0_rtx */ 2952: /* A multiply is acceptable here 2953: since this is presumed to be seldom executed. */ 2954: emit_iv_init_code (tv->add_val, v->mult_val, 1.1.1.14 root 2955: v->add_val, new_reg, before_insn); 1.1.1.8 root 2956: } 2957: 2958: /* Add code at loop start to initialize giv's reduced reg. */ 2959: 2960: emit_iv_init_code (bl->initial_value, v->mult_val, 2961: v->add_val, new_reg, loop_start); 2962: 2963: /* For each giv register that can be reduced now: 2964: delete old insn that modifies the giv, 2965: if replaceable, substitute reduced reg 2966: wherever the old giv occurs; 2967: else add new move insn "giv_reg = reduced_reg". */ 2968: 2969: for (tv = v; tv; tv = tv->same) 2970: { 2971: /* Record the identity of the reduced reg. */ 2972: tv->new_reg = new_reg; 2973: 2974: if (tv->giv_type == DEST_ADDR) 2975: { 2976: /* Store reduced reg as the address in the memref 2977: where we found this giv. */ 2978: * tv->location = new_reg; 2979: } 2980: else if (tv->replaceable) 2981: { 2982: reg_map[tv->dest_regno] = new_reg; 2983: /* If giv lives after end of loop, 2984: emit insn to copy reduced reg into old reg, 1.1.1.14 root 2985: at the end of the loop. 2986: ?? insufficient; used before loop could 2987: mean live after loop, due to surrounding loop. */ 2988: /* Currently a giv used outside 2989: the loop will not be marked replaceable, 2990: so these deficiencies don't really hurt. */ 1.1.1.8 root 2991: if (uid_luid[regno_last_uid[tv->dest_regno]] 2992: > uid_luid[INSN_UID (loop_end)]) 1.1.1.14 root 2993: { 2994: /* ?? This won't work. We need to do this at 2995: ALL exits. */ 2996: emit_insn_after (gen_rtx (SET, VOIDmode, 2997: SET_DEST (PATTERN (tv->insn)), 2998: new_reg), 2999: loop_end); 3000: abort (); 3001: } 1.1.1.8 root 3002: } 3003: else 3004: { 1.1.1.14 root 3005: /* Not replaceable; emit an insn to set the 3006: original giv reg from the reduced giv. */ 3007: 3008: int count; 3009: rtx after_insn = tv->insn; 3010: 3011: for (count = tv->consec; count > 0; count--) 3012: after_insn = next_real_insn (after_insn); 3013: 1.1.1.11 root 3014: /* Put new insn after, not before, in case 1.1.1.14 root 3015: after_insn is the end of a libcall. */ 1.1.1.11 root 3016: emit_insn_after (gen_rtx (SET, VOIDmode, 1.1.1.8 root 3017: SET_DEST (PATTERN (tv->insn)), 3018: new_reg), 1.1.1.14 root 3019: after_insn); 1.1.1.8 root 3020: } 3021: 3022: /* Delete the insn that used to set the old giv reg, 3023: unless we modified an address in it. 3024: In any case, delete the other insns used for this one. */ 3025: delete_insn_forces (tv, tv->giv_type != DEST_ADDR); 3026: 3027: if (loop_dump_stream) 3028: fprintf (loop_dump_stream, "giv at %d reduced to reg %d\n", 3029: INSN_UID (tv->insn), REGNO (new_reg)); 3030: } 3031: /* One set of equivalent givs has been strength-reduced. */ 3032: } 1.1.1.14 root 3033: #if 0 1.1.1.8 root 3034: else if (v->new_reg == 0) 3035: { 3036: /* This giv wasn't reduced and is not worth reducing. */ 3037: 3038: for (tv = v; tv; tv = tv->same) 3039: if (loop_dump_stream) 3040: fprintf (loop_dump_stream, "giv at %d not reduced\n", 3041: INSN_UID (tv->insn)); 3042: 3043: all_reduced = 0; 3044: } 1.1.1.14 root 3045: #endif 1.1.1.8 root 3046: } 3047: 3048: /* All the givs in this family have been reduced if they merit it. */ 3049: 3050: /* Try to eliminate the biv, if it is a candidate. 3051: This won't work if ! all_reduced, 3052: since the givs we planned to use might not have been reduced. */ 3053: 3054: if (all_reduced == 1 && bl->eliminable) 3055: { 3056: /* Get the REG rtx for the biv. */ 3057: rtx reg = SET_DEST (PATTERN (bl->biv->insn)); 3058: 3059: for (p = loop_start; p != end; p = NEXT_INSN (p)) 3060: { 3061: enum rtx_code code = GET_CODE (p); 3062: if ((code == INSN || code == JUMP_INSN || code == CALL_INSN) 3063: && reg_mentioned_p (reg, PATTERN (p)) 3064: && SET_DEST (PATTERN (p)) == cc0_rtx) 3065: /* Found a compare instruction using this biv; 3066: rewrite it to use a related giv. */ 3067: eliminate_biv (p, bl, loop_start); 3068: } 3069: 3070: /* Biv is no longer really needed inside the loop, 3071: so delete all insns that set the biv. */ 3072: 3073: for (v = bl->biv; v; v = v->family) 3074: delete_insn (v->insn); 3075: 1.1.1.14 root 3076: /* ?? If we created a new test to bypass the loop entirely, 3077: or otherwise drop straight in, based on this test, then 3078: we might want to rewrite it also. This way some later 3079: pass has more hope of removing the intialization of this 3080: biv entirely. */ 3081: 1.1.1.8 root 3082: /* If final_value != 0, then biv may be used after loop end 3083: and we must emit an insn to set it just in case. */ 3084: if (final_value != 0) 3085: emit_insn_after (gen_rtx (SET, VOIDmode, reg, final_value), 3086: loop_end); 3087: 3088: if (loop_dump_stream) 3089: fprintf (loop_dump_stream, "Reg %d: biv eliminated\n", 3090: bl->regno); 3091: } 3092: } 3093: 3094: /* Go through all the instructions in the loop, making all the 3095: register substitutions scheduled in REG_MAP. */ 3096: 3097: for (p = loop_start; p != end; p = NEXT_INSN (p)) 3098: if (GET_CODE (p) == INSN || GET_CODE (p) == JUMP_INSN 3099: || GET_CODE (p) == CALL_INSN) 3100: replace_regs (PATTERN (p), reg_map, nregs); 1.1.1.14 root 3101: 3102: if (loop_dump_stream) 3103: fprintf (loop_dump_stream, "\n"); 3104: } 3105: 3106: /* Nonzero if register REG appears somewhere within IN, except in 3107: subexpressions EQ to EXPR. This is a modification of reg_mentioned_p. */ 3108: 3109: int 3110: only_reg_use_p (reg, expr, in) 3111: register rtx reg, expr, in; 3112: { 3113: register char *fmt; 3114: register int i; 3115: register enum rtx_code code; 3116: 3117: if (in == 0) 3118: return 0; 3119: 3120: if (reg == expr) 3121: return 0; 3122: 3123: if (reg == in) 3124: return 1; 3125: 3126: code = GET_CODE (in); 3127: 3128: switch (code) 3129: { 3130: /* Compare registers by number. */ 3131: case REG: 3132: return GET_CODE (reg) == REG && REGNO (in) == REGNO (reg); 3133: 3134: /* These codes have no constituent expressions 3135: and are unique. */ 3136: case CC0: 3137: case PC: 3138: case CONST_INT: 3139: case CONST_DOUBLE: 3140: case SYMBOL_REF: 3141: case CODE_LABEL: 3142: return 0; 3143: } 3144: 3145: fmt = GET_RTX_FORMAT (code); 3146: 3147: for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) 3148: { 3149: if (fmt[i] == 'E') 3150: { 3151: register int j; 3152: for (j = XVECLEN (in, i) - 1; j >= 0; j--) 3153: if (only_reg_use_p (reg, expr, XVECEXP (in, i, j))) 3154: return 1; 3155: } 3156: else if (fmt[i] == 'e' 3157: && only_reg_use_p (reg, expr, XEXP (in, i))) 3158: return 1; 3159: } 3160: return 0; 1.1.1.8 root 3161: } 3162: 3163: /* Scan X for memory refs and check each memory address 3164: as a possible giv. INSN is the insn whose pattern X comes from. 3165: MAYBE_NEVER is 1 if the loop might execute INSN zero times. */ 3166: 3167: static void 1.1.1.14 root 3168: find_mem_givs (x, insn, maybe_never, loop_end) 1.1.1.8 root 3169: rtx x; 3170: rtx insn; 3171: int maybe_never; 1.1.1.14 root 3172: rtx loop_end; 1.1.1.8 root 3173: { 3174: register int i, j; 3175: register enum rtx_code code; 3176: register char *fmt; 3177: 3178: if (x == 0) 3179: return; 3180: 3181: code = GET_CODE (x); 3182: switch (code) 3183: { 3184: case REG: 3185: case CONST_INT: 3186: case CONST: 3187: case CONST_DOUBLE: 3188: case SYMBOL_REF: 3189: case LABEL_REF: 3190: case PC: 3191: case CC0: 3192: case ADDR_VEC: 3193: case ADDR_DIFF_VEC: 3194: case USE: 3195: case CLOBBER: 3196: return; 3197: 3198: case MEM: 3199: { 3200: int src_regno; 3201: rtx add_val; 3202: rtx mult_val; 3203: int benefit; 3204: struct induction *forces = 0; 3205: struct induction *forces2 = 0; 3206: 3207: benefit = general_induction_var (XEXP (x, 0), 3208: &src_regno, &add_val, &mult_val, 3209: &forces, &forces2); 3210: if (benefit > 0) 3211: { 3212: /* Found one; record it. */ 3213: struct induction *v = 3214: (struct induction *) oballoc (sizeof (struct induction)); 3215: 3216: record_giv (v, insn, src_regno, 0, mult_val, add_val, benefit, 1.1.1.14 root 3217: forces, forces2, DEST_ADDR, maybe_never, &XEXP (x, 0), 3218: loop_end); 1.1.1.8 root 3219: } 3220: return; 3221: } 3222: } 3223: 3224: /* Recursively scan the subexpressions for other mem refs. */ 3225: 3226: fmt = GET_RTX_FORMAT (code); 3227: for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) 3228: if (fmt[i] == 'e') 1.1.1.14 root 3229: find_mem_givs (XEXP (x, i), insn, maybe_never, loop_end); 1.1.1.8 root 3230: else if (fmt[i] == 'E') 3231: for (j = 0; j < XVECLEN (x, i); j++) 1.1.1.14 root 3232: find_mem_givs (XVECEXP (x, i, j), insn, maybe_never, loop_end); 1.1.1.8 root 3233: } 3234: 3235: /* Fill in the data about one giv. 3236: V is the `struct induction' in which we record the giv. (It is 3237: allocated by the caller, with alloca.) 3238: INSN is the insn that sets it. 3239: BENEFIT estimates the savings from deleting this insn. 3240: TYPE is DEST_REG or DEST_ADDR; it says whether the giv is computed 3241: into a register or is used as a memory address. 3242: 3243: SRC_REGNO is the biv reg number which the giv is computed from. 3244: DEST_REGNO is the giv's reg number (if the giv is stored in a reg). 3245: MULT_VAL and ADD_VAL are the coefficients used to compute the giv. 3246: FORCES and FORCES2, if nonzero, are other `struct induction's for 3247: other givs which are used to compute this giv indirectly. 3248: LOCATION points to the place where this giv's value appears in INSN. */ 3249: 3250: static void 3251: record_giv (v, insn, src_regno, dest_regno, mult_val, add_val, benefit, 1.1.1.14 root 3252: forces, forces2, type, maybe_never, location, loop_end) 1.1.1.8 root 3253: struct induction *v; 3254: rtx insn; 3255: int src_regno, dest_regno; 3256: rtx mult_val, add_val; 3257: int benefit; 3258: struct induction *forces, *forces2; 3259: enum g_types type; 3260: int maybe_never; 3261: rtx *location; 1.1.1.14 root 3262: rtx loop_end; 1.1.1.8 root 3263: { 3264: struct induction *b; 3265: struct iv_class *bl; 3266: 3267: v->insn = insn; 3268: v->src_regno = src_regno; 3269: v->giv_type = type; 3270: v->dest_regno = dest_regno; 3271: v->mult_val = mult_val; 3272: v->add_val = add_val; 3273: v->benefit = benefit; 3274: v->location = location; 3275: 3276: if (type == DEST_ADDR) 3277: { 1.1.1.14 root 3278: v->mode = GET_MODE (*location); 1.1.1.8 root 3279: v->consec = 0; 3280: v->lifetime = 1; 3281: v->times_used = 1; 3282: } 1.1.1.14 root 3283: else /* type == DEST_REG */ 1.1.1.8 root 3284: { 1.1.1.14 root 3285: v->mode = GET_MODE (SET_DEST (PATTERN (insn))); 1.1.1.8 root 3286: v->consec = n_times_set[dest_regno] - 1; 3287: v->lifetime = (uid_luid[regno_last_uid[dest_regno]] 3288: - uid_luid[regno_first_uid[dest_regno]]); 3289: v->times_used = n_times_used[dest_regno]; 3290: } 3291: 3292: v->same = 0; 3293: v->forces = 0; 3294: v->forces2 = 0; 3295: v->ignore = 0; 3296: v->new_reg = 0; 3297: 3298: /* Mark giv as forced if it is only used to compute another giv. */ 3299: 3300: /* This check is not sufficient as INSN may have been moved giving 3301: it a new uid, so make another check by calculating lifetimes. 3302: This is overconservative but seems to be correct. */ 3303: 3304: if (forces) 3305: { 3306: v->benefit += forces->benefit; 3307: if ((regno_last_uid[forces->dest_regno] == INSN_UID (insn) 3308: || 3309: ((uid_luid[regno_last_uid[forces->dest_regno]] 3310: - uid_luid[regno_first_uid[forces->dest_regno]]) 1.1.1.15! root 3311: == (INSN_LUID (insn) - INSN_LUID (forces->insn)))) 1.1.1.8 root 3312: && !reg_used_between_p (SET_DEST (PATTERN (forces->insn)), 3313: forces->insn, insn)) 3314: { 3315: v->forces = forces; 3316: forces->ignore = 1; 3317: } 3318: } 3319: 3320: if (forces2) 3321: { 3322: v->benefit += forces2->benefit; 3323: if ((regno_last_uid[forces2->dest_regno] == INSN_UID (insn) 3324: || 3325: ((uid_luid[regno_last_uid[forces2->dest_regno]] 3326: - uid_luid[regno_first_uid[forces2->dest_regno]]) 1.1.1.15! root 3327: == (INSN_LUID (insn) - INSN_LUID (forces2->insn)))) 1.1.1.8 root 3328: && !reg_used_between_p (SET_DEST (PATTERN (forces2->insn)), 3329: forces2->insn, insn)) 3330: { 3331: if (v->forces) 3332: v->forces2 = forces2; 3333: else 3334: v->forces = forces2; 3335: forces2->ignore = 1; 3336: } 3337: } 3338: 3339: if (type == DEST_REG) 3340: { 3341: induct_var[dest_regno] = GENERAL_INDUCT; 3342: induct_struct[dest_regno] = v; 3343: } 3344: 3345: /* Add the giv to the class of givs computed from one biv. */ 3346: 3347: bl = class_struct[src_regno]; 3348: if (bl) 3349: { 3350: v->family = bl->giv; 3351: bl->giv = v; 1.1.1.14 root 3352: /* Don't count DEST_ADDR. This is supposed to count the number of 3353: insns that calculate givs. */ 3354: if (type == DEST_REG) 3355: bl->giv_count++; 1.1.1.8 root 3356: bl->total_benefit += benefit; 3357: } 3358: else 1.1.1.15! root 3359: /* Fatal error, biv missing for this giv? */ ! 3360: abort (); 1.1.1.8 root 3361: 3362: if (type == DEST_ADDR) 3363: v->replaceable = 1; 3364: else 3365: { 3366: /* The giv can be replaced outright by the reduced register if 1.1.1.11 root 3367: - the insn that sets the giv is always executed on any iteration 3368: on which the giv is used at all 3369: (there are two ways to deduce this: 3370: either the insn is executed on every iteration, 3371: or all uses follow that insn in the same basic block), 1.1.1.8 root 3372: - the giv is not used before the insn that sets it, 3373: i.e. no definition outside loop reaches into loop 3374: - no assignments to the biv occur during the giv's lifetime. */ 3375: 1.1.1.14 root 3376: /* Is this right? Don't we need to make sure the giv is not used 3377: outside the loop. Someday we will know where all the loop exits 3378: are so we can do better, but until then.... 3379: March 18, 1989 -- [email protected] */ 3380: 1.1.1.11 root 3381: if (regno_first_uid[dest_regno] == INSN_UID (insn) 3382: /* Previous line always fails if INSN was moved by loop opt. */ 1.1.1.14 root 3383: && uid_luid[regno_last_uid[dest_regno]] < INSN_LUID (loop_end) 1.1.1.11 root 3384: && (!maybe_never || last_use_this_basic_block (dest_regno, insn))) 1.1.1.8 root 3385: { 3386: v->replaceable = 1; 3387: for (b = bl->biv; b; b = b->family) 3388: { 3389: if ((uid_luid[INSN_UID (b->insn)] >= uid_luid[regno_first_uid[dest_regno]]) 3390: && 3391: (uid_luid[INSN_UID (b->insn)] 3392: <= uid_luid[regno_last_uid[dest_regno]])) 3393: { 3394: v->replaceable = 0; 3395: break; 3396: } 3397: } 3398: } 3399: else 3400: v->replaceable = 0; 3401: } 3402: 3403: if (loop_dump_stream) 3404: { 3405: if (type == DEST_REG) 3406: fprintf (loop_dump_stream, "Insn %d: giv reg %d", 3407: INSN_UID (insn), dest_regno); 3408: else 3409: fprintf (loop_dump_stream, "Insn %d: dest address", 3410: INSN_UID (insn)); 3411: 3412: fprintf (loop_dump_stream, " src reg %d benefit %d", 3413: src_regno, v->benefit); 3414: fprintf (loop_dump_stream, " used %d lifetime %d", 3415: v->times_used, v->lifetime); 3416: 3417: if (v->replaceable) 3418: fprintf (loop_dump_stream, " replaceable"); 3419: 3420: if (GET_CODE (mult_val) == CONST_INT) 3421: fprintf (loop_dump_stream, " mult %d", 3422: INTVAL (mult_val)); 3423: else 3424: { 3425: fprintf (loop_dump_stream, " mult "); 3426: print_rtl (loop_dump_stream, mult_val); 3427: } 3428: 3429: if (GET_CODE (add_val) == CONST_INT) 3430: fprintf (loop_dump_stream, " add %d", 3431: INTVAL (add_val)); 3432: else 3433: { 3434: fprintf (loop_dump_stream, " add "); 3435: print_rtl (loop_dump_stream, add_val); 3436: } 3437: } 3438: 3439: if (loop_dump_stream && v->forces) 3440: fprintf (loop_dump_stream, " forces insn %d", INSN_UID (v->forces->insn)); 3441: if (loop_dump_stream && v->forces2) 3442: fprintf (loop_dump_stream, " forces insn %d", INSN_UID (v->forces2->insn)); 3443: if (loop_dump_stream && v->consec) 3444: fprintf (loop_dump_stream, " consec %d", v->consec); 3445: if (loop_dump_stream) 3446: fprintf (loop_dump_stream, "\n"); 3447: } 3448: 3449: /* Delete the insns forced by the insn described by V. 3450: If THIS_TOO is nonzero, delete that insn itself as well. */ 3451: 3452: static void 3453: delete_insn_forces (v, this_too) 3454: struct induction *v; 3455: int this_too; 3456: { 3457: rtx x, p; 3458: int count; 3459: rtx insn; 3460: 3461: if (this_too) 3462: { 3463: insn = v->insn; 3464: for (count = v->consec; count >= 0; count--) 3465: { 3466: /* If first insn of libcall sequence, skip to end. */ 3467: /* Do this at start of loop, since p is guaranteed to 3468: be an insn here. */ 3469: if (x = find_reg_note (insn, REG_LIBCALL, 0)) 3470: insn = XEXP (x, 0); 3471: 1.1.1.13 root 3472: if (x = find_reg_note (insn, REG_RETVAL, 0)) 1.1.1.8 root 3473: { 3474: /* This is a library call; delete all insns backward until get to 3475: first insn in this group. */ 1.1.1.13 root 3476: rtx first = XEXP (x, 0); 1.1.1.8 root 3477: for (p = insn; p != first; p = PREV_INSN (p)) 3478: delete_insn (p); 3479: /* Delete first insn also. */ 3480: delete_insn (p); 3481: } 3482: else 3483: delete_insn (insn); 3484: 3485: do insn = NEXT_INSN (insn); 3486: while (GET_CODE (insn) == NOTE); 3487: } 3488: } 3489: 3490: if (v->forces) 3491: delete_insn_forces (v->forces, 1); 3492: if (v->forces2) 3493: delete_insn_forces (v->forces2, 1); 3494: } 3495: 3496: /* Check whether an insn is an increment legitimate for a basic induction var. 3497: X is the source of the insn. 3498: DEST_REG is the putative biv, also the destination of the insn. 3499: We accept patterns of these forms: 3500: REG = REG + INVARIANT 3501: REG = INVARIANT + REG 3502: REG = REG - CONSTANT 3503: 3504: If X is suitable, we return 1, 3505: and store the factor multiplying REF in X into *MULT_VAL 3506: and the additive term into *INC_VAL. 3507: Otherwise we return 0. */ 3508: 3509: static int 3510: basic_induction_var (x, dest_regno, inc_val, mult_val) 3511: register rtx x; 3512: int dest_regno; 3513: rtx *inc_val; 3514: rtx *mult_val; 3515: { 1.1.1.12 root 3516: register enum rtx_code code; 1.1.1.8 root 3517: rtx arg; 3518: 1.1.1.12 root 3519: if (x == 0) 3520: return 0; 3521: code = GET_CODE (x); 1.1.1.8 root 3522: switch (code) 3523: { 3524: case PLUS: 3525: if (GET_CODE (XEXP (x, 0)) == REG 3526: && REGNO (XEXP (x, 0)) == dest_regno) 3527: arg = XEXP (x, 1); 3528: else if (GET_CODE (XEXP (x, 1)) == REG 3529: && REGNO (XEXP (x, 1)) == dest_regno) 3530: arg = XEXP (x, 0); 3531: else 3532: return 0; 3533: 3534: if (invariant_p (arg) == 1) 3535: *inc_val = arg; 3536: else 3537: return 0; 3538: 3539: *mult_val = const1_rtx; 3540: return 1; 3541: 3542: case MINUS: 3543: if (GET_CODE (XEXP (x, 0)) == REG 3544: && REGNO (XEXP (x, 0)) == dest_regno 3545: && GET_CODE (XEXP (x, 1)) == CONST_INT) 3546: *inc_val = gen_rtx (CONST_INT, VOIDmode, 3547: - INTVAL (XEXP (x, 1))); 3548: else 3549: return 0; 3550: *mult_val = const1_rtx; 3551: return 1; 3552: 3553: /* Can accept constant setting of biv only when inside inner most loop. 3554: Otherwise, a biv of an inner loop may be incorrectly recognized 3555: as a biv of the outer loop, 3556: causing code to be moved INTO the inner loop. */ 3557: case REG: 3558: if (!invariant_p (x)) 3559: return 0; 3560: case CONST_INT: 3561: case SYMBOL_REF: 3562: case CONST: 3563: if (loops_enclosed == 1) 3564: { 3565: *inc_val = x; 3566: *mult_val = const0_rtx; 3567: return 1; 3568: } 3569: else 3570: return 0; 3571: 3572: default: 3573: return 0; 3574: } 3575: } 3576: 3577: /* A general induction variable (giv) is any quantity that is a linear function 3578: of a basic induction variable, i.e. giv = biv * mult_val + add_val. 3579: The coefficients can be any loop invariant quantity. 3580: A giv need not be computed directly from the biv; 3581: it can be computed by way of other givs. */ 3582: 3583: /* Determine whether X computes a giv. 3584: If it does, return a nonzero value 3585: which is the benefit from eliminating the computation of X; 3586: set *SRC_REGNO to the register number of the biv that it is computed from; 3587: set *ADD_VAL and *MULT_VAL to the coefficients, 3588: such that the value of X is biv * mult + add; 3589: set forces (and forces2) to identify any other givs that are used 3590: solely to compute this one. */ 3591: 3592: /* This routine recognizes four types of patterns that generate givs: 3593: - giv = biv op invariant v = 0, g = 0 3594: - giv1 = giv2 op invariant v = 0, g = giv2 3595: where giv1 and giv2 are functions of the same biv 3596: - giv1 = biv op giv2 v = giv2, g = 0 3597: where giv2 is a function of biv 3598: - giv1 = giv2 op giv3 v = giv3, g = giv2 3599: where giv2 and giv3 are functions of the save biv */ 3600: 3601: static int 3602: general_induction_var (x, src_regno, add_val, mult_val, forces, forces2) 3603: rtx x; 3604: int *src_regno; 3605: rtx *add_val; 3606: rtx *mult_val; 3607: struct induction **forces; 3608: struct induction **forces2; 3609: { 1.1.1.12 root 3610: register enum rtx_code code; 1.1.1.8 root 3611: rtx arg; 3612: struct induction *g = 0; 3613: struct induction *v = 0; 3614: int subexp = 0; 3615: int tem; 3616: 1.1.1.12 root 3617: if (x == 0) 3618: return 0; 3619: 3620: code = GET_CODE (x); 1.1.1.8 root 3621: switch (code) 3622: { 3623: case NEG: 3624: /* This can generate givs also, but it is not handled. */ 3625: return 0; 3626: 3627: case PLUS: 3628: case MINUS: 3629: case MULT: 3630: case UMULT: 3631: /* Result is linear in both operands. */ 3632: /* Determine which operand is the biv, and put the other in ARG. */ 3633: if (GET_CODE (XEXP (x, 0)) == REG 3634: && induct_var[REGNO (XEXP (x, 0))] == BASIC_INDUCT) 3635: { 3636: *src_regno = REGNO (XEXP (x, 0)); 3637: arg = XEXP (x, 1); 3638: 3639: } 3640: else if (GET_CODE (XEXP (x, 1)) == REG 3641: && induct_var[REGNO (XEXP (x, 1))] == BASIC_INDUCT) 3642: { 3643: *src_regno = REGNO (XEXP (x, 1)); 3644: arg = XEXP (x, 0); 3645: 3646: } 3647: /* Check for an rtl subexpression that is a giv. Memory address 3648: givs often look like (plus (reg) (mult (biv) (const))). */ 3649: /* Do this before checking for a giv operand, as this function will 3650: fail if this special operand is not recognized. */ 3651: #ifndef DONT_REDUCE_ADDR 3652: else if (tem = general_induction_var (XEXP (x, 1), src_regno, 3653: add_val, mult_val, 1.1.1.15! root 3654: forces, forces2) ! 3655: && code != MINUS) 1.1.1.8 root 3656: { 3657: /* Set subexp true so that this can be handled a little 3658: differently from the normal case of g set. */ 3659: /* Note that SRC_REGNO is already set. */ 3660: subexp = TRUE; 3661: g = (struct induction *) alloca (sizeof (struct induction)); 3662: g->mult_val = *mult_val; 3663: g->add_val = *add_val; 1.1.1.15! root 3664: /* Fake out the test below. */ ! 3665: g->replaceable = 1; 1.1.1.8 root 3666: /* Count this multiply as a shift, since that's what it 3667: really will do. */ 3668: if (tem == MULT_BENEFIT) 3669: g->benefit = SHIFT_BENEFIT; 3670: else 3671: g->benefit = tem; 3672: arg = XEXP (x, 0); 3673: } 3674: #endif 3675: /* Also allow general induction variables. 3676: Could have a mult followed by an add (i.e. an address calculation), 3677: thereby generating two related general induction variables 3678: of which only the second is actually used. */ 3679: /* Do this after checking both args for basic induction variables. */ 3680: else if (GET_CODE (XEXP (x, 0)) == REG 3681: && induct_var[REGNO (XEXP (x, 0))] == GENERAL_INDUCT) 3682: { 3683: g = induct_struct[REGNO (XEXP (x, 0))]; 3684: *src_regno = g->src_regno; 3685: arg = XEXP (x, 1); 3686: } 3687: else if (GET_CODE (XEXP (x, 1)) == REG 1.1.1.15! root 3688: && induct_var[REGNO (XEXP (x, 1))] == GENERAL_INDUCT ! 3689: && code != MINUS) 1.1.1.8 root 3690: { 3691: g = induct_struct[REGNO (XEXP (x, 1))]; 3692: *src_regno = g->src_regno; 3693: arg = XEXP (x, 0); 3694: } 3695: else 3696: return 0; 3697: 3698: /* Overall form of expression looks good. */ 3699: break; 3700: 3701: /* Could handle these also. */ 3702: case DIV: 3703: case UDIV: 3704: /* For a 68020 could handle these? */ 3705: case LSHIFT: 3706: case ASHIFT: 3707: case ASHIFTRT: 3708: case LSHIFTRT: 3709: /* These operations are linear only in first operand. 3710: Check for a biv or giv there; if found, put other operand in ARG. */ 3711: if (GET_CODE (XEXP (x, 0)) == REG 3712: && induct_var[REGNO (XEXP (x, 0))] == BASIC_INDUCT) 3713: { 3714: *src_regno = REGNO (XEXP (x, 0)); 3715: arg = XEXP (x, 1); 3716: } 3717: /* Also allow general induction variable. */ 3718: else if (GET_CODE (XEXP (x, 0)) == REG 3719: && induct_var[REGNO (XEXP (x, 0))] == GENERAL_INDUCT) 3720: { 3721: g = induct_struct[REGNO (XEXP (x, 0))]; 3722: *src_regno = g->src_regno; 3723: arg = XEXP (x, 1); 3724: } 3725: else 3726: return 0; 3727: 3728: /* Overall form of expression looks good. */ 3729: break; 3730: 3731: default: 3732: return 0; 3733: } 3734: 3735: /* ARG is the operand that is NOT a biv or giv. 3736: Test it for superficial validity. */ 3737: 3738: /* This is just a special case of invariant values, 3739: it is not really needed, but it's a shortcut. */ 3740: if (GET_CODE (arg) == CONST_INT) 3741: ; 3742: 3743: /* Depends on previous general induction variable, which has 3744: the same basic induction variable */ 3745: /* This code detects mults that have been generated as shift and add. */ 3746: else if (GET_CODE (arg) == REG 3747: && induct_var[REGNO (arg)] == GENERAL_INDUCT 3748: && induct_struct[REGNO (arg)]->src_regno == *src_regno) 3749: { 3750: v = induct_struct[REGNO (arg)]; 3751: /* Dependence indicated by forces, sort of kludgey. */ 3752: } 3753: 3754: /* Invariant expression, could be a constant-valued register. */ 3755: else if (invariant_p (arg) == 1) 3756: ; 3757: 3758: /* Failure */ 3759: else 3760: return 0; 1.1.1.15! root 3761: ! 3762: /* Until we can do the correct thing, suppress use of nonreplaceable givs ! 3763: as sources for other givs. */ ! 3764: if ((g && ! g->replaceable) ! 3765: || (v && ! v->replaceable)) ! 3766: return 0; 1.1.1.8 root 3767: 3768: /* Now we know looks like a giv; extract the coefficients. 3769: We can still fail if the coefficients are not what we can handle. */ 3770: 3771: /* Only succeed if result mult_val and add_val are only one level of rtl, 3772: for example, (NEG:SI (REG:SI 34)) is not accepted. 3773: This mainly causes problems with the MINUS code. */ 3774: 3775: switch (code) 3776: { 3777: case PLUS: 3778: if (v && g) 3779: { 3780: if (GET_CODE (g->mult_val) == CONST_INT) 3781: { 3782: if (g->mult_val == const0_rtx) 3783: *mult_val = v->mult_val; 3784: else if (GET_CODE (v->mult_val) == CONST_INT) 3785: *mult_val = gen_rtx (CONST_INT, VOIDmode, 3786: INTVAL (g->mult_val) 3787: + INTVAL (v->mult_val)); 3788: else 3789: return 0; 3790: } 3791: else if (v->mult_val == const0_rtx) 3792: *mult_val = g->mult_val; 3793: else 3794: return 0; 3795: 3796: if (GET_CODE (g->add_val) == CONST_INT) 3797: { 3798: if (g->add_val == const0_rtx) 3799: *add_val = v->add_val; 3800: else if (GET_CODE (v->add_val) == CONST_INT) 3801: *add_val = gen_rtx (CONST_INT, VOIDmode, 3802: INTVAL (g->add_val) 3803: + INTVAL (v->add_val)); 3804: else 3805: return 0; 3806: } 3807: else if (v->add_val == const0_rtx) 3808: *add_val = g->add_val; 3809: else 3810: return 0; 3811: 3812: if (subexp) 3813: { 3814: /* g deleted when return, can't return pointer to it */ 3815: if (*forces2 == 0) 3816: *forces2 = v; 3817: return ADD_BENEFIT + g->benefit; 3818: } 3819: else 3820: { 3821: *forces = g; 3822: *forces2 = v; 3823: return ADD_BENEFIT; 3824: } 3825: } 3826: else if (v) 3827: { 3828: if (GET_CODE (v->mult_val) == CONST_INT) 3829: *mult_val = gen_rtx (CONST_INT, VOIDmode, 3830: INTVAL (v->mult_val) + 1); 3831: else 3832: return 0; 3833: *add_val = v->add_val; 3834: *forces = v; 3835: return ADD_BENEFIT; 3836: } 3837: else if (g) 3838: { 3839: *mult_val = g->mult_val; 3840: if (GET_CODE (g->add_val) == CONST_INT) 3841: { 3842: if (g->add_val == const0_rtx) 3843: *add_val = arg; 3844: else if (GET_CODE (arg) == CONST_INT) 3845: *add_val = gen_rtx (CONST_INT, VOIDmode, 3846: INTVAL (g->add_val) + INTVAL (arg)); 3847: else 3848: return 0; 3849: } 3850: else 3851: /* Could succeed if arg == 0, but that will never occur. */ 3852: return 0; 3853: 3854: if (subexp) 3855: /* g deleted when return, can't return pointer to it */ 3856: return ADD_BENEFIT + g->benefit; 3857: else 3858: { 3859: *forces = g; 3860: return ADD_BENEFIT; 3861: } 3862: } 3863: else 3864: { 3865: *mult_val = const1_rtx; 3866: *add_val = arg; 3867: return ADD_BENEFIT; 3868: } 3869: 3870: /* Takes a lot of code and will rarely succeed. */ 3871: case MINUS: 3872: if (v && g) 3873: { 3874: /* G is the first argument of MINUS. */ 3875: 3876: if (GET_CODE (g->mult_val) == CONST_INT) 3877: { 3878: if (g->mult_val == const0_rtx) 3879: #if 0 /* Should not have to fail here */ 3880: *mult_val = gen_rtx (NEG, SImode, v->mult_val); 3881: #endif 3882: return 0; 3883: else if (GET_CODE (v->mult_val) == CONST_INT) 3884: *mult_val = gen_rtx (CONST_INT, VOIDmode, 3885: INTVAL (g->mult_val) 3886: - INTVAL (v->mult_val)); 3887: else 3888: return 0; 3889: } 3890: else if (v->mult_val == const0_rtx) 3891: *mult_val = g->mult_val; 3892: else 3893: return 0; 3894: 3895: if (GET_CODE (g->add_val) == CONST_INT) 3896: { 3897: if (g->add_val == const0_rtx) 3898: #if 0 /* should not have to fail here */ 3899: *add_val = v->add_val; 3900: #endif 3901: return 0; 3902: else if (GET_CODE (v->add_val) == CONST_INT) 3903: *add_val = gen_rtx (CONST_INT, VOIDmode, 3904: INTVAL (g->add_val) 3905: - INTVAL (v->add_val)); 3906: else 3907: return 0; 3908: } 3909: else if (v->add_val == const0_rtx) 3910: *add_val = g->add_val; 3911: else 3912: return 0; 3913: 3914: if (subexp) 3915: { 3916: /* G deleted when return, can't return pointer to it */ 3917: if (*forces2 == 0) 3918: *forces2 = v; 3919: return ADD_BENEFIT + g->benefit; 3920: } 3921: else 3922: { 3923: *forces = g; 3924: *forces2 = v; 3925: return ADD_BENEFIT; 3926: } 3927: } 3928: else if (v) 3929: { 3930: if (GET_CODE (v->mult_val) != CONST_INT) 3931: return 0; 3932: if (arg == XEXP (x, 0)) /* giv1 = giv2 - biv */ 3933: { 3934: *mult_val = gen_rtx (CONST_INT, VOIDmode, 3935: INTVAL (v->mult_val) - 1); 3936: *add_val = v->add_val; 3937: } 3938: else /* giv1 = biv - giv2 */ 3939: { 3940: *mult_val = gen_rtx (CONST_INT, VOIDmode, 3941: 1 - INTVAL (v->mult_val)); 3942: if (GET_CODE (v->add_val) == CONST_INT) 3943: *add_val = gen_rtx (CONST_INT, VOIDmode, 3944: - INTVAL (v->add_val)); 3945: else 3946: return 0; 3947: } 3948: *forces = v; 3949: return ADD_BENEFIT; 3950: } 3951: else if (g) 3952: { 3953: if (arg == XEXP (x, 1)) 3954: *mult_val = g->mult_val; 3955: else 3956: { 3957: if (GET_CODE (g->mult_val) == CONST_INT) 3958: *mult_val = gen_rtx (CONST_INT, VOIDmode, 3959: - INTVAL (g->mult_val)); 3960: else 3961: return 0; 3962: } 3963: if (GET_CODE (g->add_val) == CONST_INT) 3964: { 3965: if (g->add_val == const0_rtx) 3966: { 3967: if (arg == XEXP (x, 1)) /* giv1 = giv2 - arg */ 3968: { 3969: /* Fail unless arg is a constant. */ 3970: if (GET_CODE (arg) == CONST_INT) 3971: *add_val = gen_rtx (CONST_INT, VOIDmode, 3972: -INTVAL (arg)); 3973: else 3974: return 0; 3975: } 3976: else /* giv1 = arg - giv2 */ 3977: *add_val = arg; 3978: } 3979: else if (GET_CODE (arg) == CONST_INT) 3980: { 3981: if (arg == XEXP (x, 1)) /* giv1 = giv2 - arg */ 3982: *add_val = gen_rtx (CONST_INT, VOIDmode, 3983: INTVAL (g->add_val) 3984: - INTVAL (arg)); 3985: else /* giv1 = arg - giv2 */ 3986: *add_val = gen_rtx (CONST_INT, VOIDmode, 3987: INTVAL (arg), 3988: - INTVAL (g->add_val)); 3989: } 3990: else 3991: return 0; 3992: } 3993: else 3994: /* Could succeed if arg == 0, but that will never occur. */ 3995: return 0; 3996: 3997: if (subexp) 3998: /* G deleted when return, can't return pointer to it. */ 3999: return ADD_BENEFIT + g->benefit; 4000: else 4001: { 4002: *forces = g; 4003: return ADD_BENEFIT; 4004: } 4005: } 4006: else if (GET_CODE (arg) == CONST_INT) 4007: { 4008: if (arg == XEXP (x, 1)) 4009: { 4010: *add_val = gen_rtx (CONST_INT, VOIDmode, - INTVAL (arg)); 4011: *mult_val = const1_rtx; 4012: } 4013: else 4014: { 4015: *add_val = arg; 4016: *mult_val = gen_rtx (CONST_INT, VOIDmode, -1); 4017: } 4018: return ADD_BENEFIT; 4019: } 4020: else 4021: return 0; 4022: 4023: /* UMULT can be handled like MULT since C ignores overflows. */ 4024: case MULT: 4025: case UMULT: 4026: if (v && g) 4027: { 4028: /* Quadratic term, just fail. */ 4029: return 0; 4030: } 4031: else if (v) 4032: { 4033: /* Quadratic term, just fail. */ 4034: return 0; 4035: } 4036: else if (g) 4037: { 4038: /* Takes a lot of code and will rarely succeed. */ 4039: /* dest = m * arg * b + a * arg */ 4040: if (GET_CODE (g->mult_val) == CONST_INT) 4041: { 4042: if (g->mult_val == const0_rtx) 4043: *mult_val = const0_rtx; 4044: else if (g->mult_val == const1_rtx) 4045: *mult_val = arg; 4046: else if (GET_CODE (arg) == CONST_INT) 4047: *mult_val = gen_rtx (CONST_INT, VOIDmode, 4048: INTVAL (g->mult_val) * INTVAL (arg)); 4049: else 4050: return 0; 4051: } 4052: else 4053: /* Could suceed if arg == 1 or 0, but this will never occur. */ 4054: return 0; 4055: 4056: if (GET_CODE (g->add_val) == CONST_INT) 4057: { 4058: if (g->add_val == const0_rtx) 4059: *add_val = const0_rtx; 4060: else if (g->add_val == const1_rtx) 4061: *add_val = arg; 4062: else if (GET_CODE (arg) == CONST_INT) 4063: *add_val = gen_rtx (CONST_INT, VOIDmode, 4064: INTVAL (g->add_val) * INTVAL (arg)); 4065: else 4066: return 0; 4067: } 4068: else 4069: /* Could suceed if arg == 1 or 0, but this will never occur. */ 4070: return 0; 4071: 4072: if (subexp) 4073: /* G deleted when return, can't return pointer to it. */ 4074: return MULT_BENEFIT + g->benefit; 4075: else 4076: { 4077: *forces = g; 4078: return MULT_BENEFIT; 4079: } 4080: } 4081: else 4082: { 4083: *mult_val = arg; 4084: *add_val = const0_rtx; 4085: return MULT_BENEFIT; 4086: } 4087: 4088: /* These are not worth the trouble. */ 4089: case DIV: 4090: case UDIV: 4091: return 0; 4092: 4093: /* Handle these, but only for left shift. */ 4094: case LSHIFT: 4095: case ASHIFT: 4096: if (v && g) 4097: { 4098: /* Quadratic term, just fail. */ 4099: return 0; 4100: } 4101: else if (v) 4102: { 4103: /* Quadratic term, just fail. */ 4104: return 0; 4105: } 4106: else if (g) 4107: { 4108: /* Takes a lot of code and will rarely succeed. */ 4109: /* dest = ((m * b) << arg) + (a << arg) */ 4110: if (GET_CODE (g->mult_val) == CONST_INT) 4111: { 4112: if (g->mult_val == const0_rtx) 4113: *mult_val = const0_rtx; 4114: else if (GET_CODE (arg) == CONST_INT && INTVAL (arg) >= 0) 4115: *mult_val = gen_rtx (CONST_INT, VOIDmode, 4116: INTVAL (g->mult_val) 4117: * (1 << INTVAL (arg))); 4118: else 4119: return 0; 4120: } 4121: else 4122: /* Could suceed if arg == 0, but this will never occur. */ 4123: return 0; 4124: 4125: if (GET_CODE (g->add_val) == CONST_INT) 4126: { 4127: if (g->add_val == const0_rtx) 4128: *add_val = const0_rtx; 4129: else if (GET_CODE (arg) == CONST_INT) 4130: *add_val = gen_rtx (CONST_INT, VOIDmode, 4131: INTVAL (g->add_val) 4132: * (1 << INTVAL (arg))); 4133: else 4134: return 0; 4135: } 4136: else 4137: /* Could suceed if arg == 0, but this will never occur. */ 4138: return 0; 4139: 4140: if (subexp) 4141: /* G deleted when return, can't return pointer to it. */ 4142: return SHIFT_BENEFIT + g->benefit; 4143: else 4144: { 4145: *forces = g; 4146: return SHIFT_BENEFIT; 4147: } 4148: } 4149: 4150: if (GET_CODE (arg) == CONST_INT && INTVAL (arg) >= 0) 4151: *mult_val = gen_rtx (CONST_INT, VOIDmode, 1 << INTVAL (arg)); 4152: else 4153: return 0; 4154: *add_val = const0_rtx; 4155: return SHIFT_BENEFIT; 4156: 4157: /* These are not worth the trouble. */ 4158: case ASHIFTRT: 4159: case LSHIFTRT: 4160: return 0; 4161: 4162: /* should never reach here */ 4163: default: 4164: abort (); 4165: return 0; 4166: } 4167: } 4168: 4169: /* Help detect a giv that is calculated by several consecutive insns; 4170: for example, 4171: giv = biv * M 4172: giv = giv + A 4173: The caller has already identified the first insn P as having a giv as dest; 4174: we check that all other insns that set the same register follow 4175: immediately after P, that they alter nothing else, 4176: and that the result of the last is still a giv. 4177: 4178: The value is 0 if the reg set in P is not really a giv. 4179: Otherwise, the value is the amount gained by eliminating 4180: all the consecutive insns that compute the value. 4181: 4182: FIRST_BENEFIT is the amount gained by eliminating the first insn, P. 4183: SRC_REGNO is the regno of the biv; DEST_REGNO is that of the giv. 4184: 4185: The coefficients of the ultimate giv value are stored in 4186: *MULT_VAL and *ADD_VAL. */ 4187: 4188: static int 4189: consec_sets_giv (first_benefit, p, src_regno, dest_regno, 4190: add_val, mult_val) 4191: int first_benefit; 4192: rtx p; 4193: int src_regno; 4194: int dest_regno; 4195: rtx *add_val; 4196: rtx *mult_val; 4197: { 4198: int count; 4199: int benefit = first_benefit; 4200: enum rtx_code code; 1.1.1.15! root 4201: struct induction forces, forces2; 1.1.1.8 root 4202: rtx temp; 4203: int tem; 4204: 4205: /* Initialize info used by general_induction_var. */ 4206: struct induction *v = 4207: (struct induction *) oballoc (sizeof (struct induction)); 4208: v->src_regno = src_regno; 4209: v->mult_val = *mult_val; 4210: v->add_val = *add_val; 4211: 4212: induct_var[dest_regno] = GENERAL_INDUCT; 4213: induct_struct[dest_regno] = v; 4214: 4215: count = n_times_set[dest_regno] - 1; 4216: 4217: while (count > 0) 4218: { 4219: p = NEXT_INSN (p); 4220: code = GET_CODE (p); 4221: 4222: /* If libcall, skip to end of call sequence. */ 4223: if (code == INSN && (temp = find_reg_note (p, REG_LIBCALL, 0))) 4224: p = XEXP (temp, 0); 4225: 4226: if (code == INSN && GET_CODE (PATTERN (p)) == SET 4227: && GET_CODE (SET_DEST (PATTERN (p))) == REG 4228: && REGNO (SET_DEST (PATTERN (p))) == dest_regno 4229: && ((tem = general_induction_var (SET_SRC (PATTERN (p)), &src_regno, 4230: add_val, mult_val, 4231: &forces, &forces2)) 4232: /* Giv created by call to library routine. */ 4233: || ((temp = find_reg_note (p, REG_EQUAL, 0)) && 4234: (tem = general_induction_var (XEXP (temp, 0), &src_regno, 4235: add_val, mult_val, 4236: &forces, &forces2)))) 4237: && src_regno == v->src_regno) 4238: { 4239: count--; 4240: benefit += tem; 4241: v->mult_val = *mult_val; 4242: v->add_val = *add_val; 4243: } 4244: else if (code != NOTE) 4245: { 4246: induct_var[dest_regno] = UNKNOWN_INDUCT; 4247: return 0; 4248: } 4249: } 4250: 4251: return benefit; 4252: } 4253: 4254: /* Generate a SEQUENCE to multiply OP0 and OP1 with result in TARGET. 4255: Use expand_mult to "optimally" do the multiply. 1.1.1.10 root 4256: This also works for machines that do not have multiply insns. 4257: If one of the operands is a constant, it must be the second. */ 1.1.1.8 root 4258: 4259: static rtx 4260: gen_iv_mult (mode, op0, op1, target) 4261: enum machine_mode mode; 4262: register rtx op0, op1, target; 4263: { 4264: extern rtx gen_sequence (); 4265: extern rtx start_sequence (); 1.1.1.10 root 4266: rtx saved, result, temp; 1.1.1.8 root 4267: 4268: saved = start_sequence (); 4269: 1.1.1.10 root 4270: /* ??? It is very unmodular to use expand_mult here! 4271: This should be redesigned. */ 4272: 1.1.1.8 root 4273: /* UNSIGNEDP arg can be zero since operands/target always same width. */ 1.1.1.10 root 4274: temp = expand_mult (mode, op0, op1, target, 0); 4275: 4276: /* Move to target register, if expand_mult did not put it there. */ 4277: if (target != 0 && temp != target) 4278: emit_move_insn (target, temp); 1.1.1.8 root 4279: 4280: result = gen_sequence (); 4281: end_sequence (saved); 4282: 4283: return result; 4284: } 4285: 4286: /* Emit code to initialize an induction variable created by strength 1.1.1.15! root 4287: reduction. ! 4288: More precisely, emit code before INSERT_BEFORE ! 4289: to set REG = B * M + A. */ 1.1.1.14 root 4290: 1.1.1.8 root 4291: static void 1.1.1.15! root 4292: emit_iv_init_code (b, m, a, reg, insert_before) 1.1.1.8 root 4293: rtx b; /* initial value of basic induction variable */ 4294: rtx m; /* multiplicative constant */ 4295: rtx a; /* additive constant */ 4296: rtx reg; /* destination register */ 1.1.1.15! root 4297: rtx insert_before; 1.1.1.8 root 4298: { 1.1.1.15! root 4299: rtx seq; ! 4300: rtx result; 1.1.1.8 root 4301: 1.1.1.15! root 4302: /* Prevent unexpected sharing of these rtx. */ ! 4303: a = copy_rtx (a); ! 4304: b = copy_rtx (b); ! 4305: ! 4306: start_sequence (); ! 4307: result = expand_mult_add (b, m, a, GET_MODE (reg), 0); ! 4308: if (reg != result) ! 4309: emit_move_insn (reg, result); ! 4310: seq = gen_sequence (); ! 4311: end_sequence (); 1.1.1.8 root 4312: 1.1.1.15! root 4313: emit_insn_before (seq, insert_before); ! 4314: } 1.1.1.8 root 4315: 1.1.1.15! root 4316: /* Emit code to increment the induction variable inside the loop. ! 4317: Try to emit optimal code for the expression ! 4318: REG = REG + BIV_ADD * GIV_MULT. */ 1.1.1.8 root 4319: 1.1.1.15! root 4320: static void ! 4321: emit_iv_inc (biv_add, giv_mult, reg, insn) ! 4322: rtx biv_add; /* increment value for biv */ ! 4323: rtx giv_mult; /* multiply value of giv */ ! 4324: rtx reg; /* create insn to set this reg */ ! 4325: rtx insn; /* where to insert the new insn */ ! 4326: { ! 4327: emit_iv_init_code (biv_add, giv_mult, reg, reg, insn); 1.1.1.8 root 4328: } 4329: 4330: /* Test whethen BIV_ADD * GIV_MULT can be computed without 4331: an actual multiply insn. Value is 1 if so. */ 4332: 4333: static int 4334: product_cheap_p (biv_add, giv_mult) 4335: rtx biv_add; 4336: rtx giv_mult; 4337: { 4338: /* Indicates which of MULT/ADD are constants. */ 4339: int status = 0; 4340: int const_val; 4341: rtx tmp; 4342: 4343: if (GET_CODE (biv_add) == CONST_INT) 4344: status |= 0x1; 4345: if (GET_CODE (giv_mult) == CONST_INT) 4346: status |= 0x2; 4347: 4348: switch (status) 4349: { 4350: case 0: 4351: /* Neither is constant: would need a multiply insn, so fail. */ 4352: return 0; 4353: 4354: case 1: 4355: /* BIV_ADD value is constant */ 4356: /* Equivalent to state 2, just switch values of BIV_ADD and GIV_MULT 4357: and fall through. */ 4358: tmp = biv_add; 4359: biv_add = giv_mult; 4360: giv_mult = tmp; 4361: 4362: case 2: 4363: /* GIV_MULT value is constant. 4364: If it is 1, 0 or -1 then we win. */ 4365: const_val = INTVAL (giv_mult); 4366: if (const_val < -1 || const_val > 1) 4367: { 4368: tmp = gen_iv_mult (GET_MODE (biv_add), biv_add, giv_mult, 0); 4369: /* Don't emit a multiply insn, just fail instead. */ 4370: if ((GET_CODE (tmp) == SET && GET_CODE (SET_SRC (tmp)) == MULT) 4371: /* Also fail if library call (which generates more 4372: then two insn) is needed. */ 4373: || (GET_CODE (tmp) == SEQUENCE && XVECLEN (tmp, 0) > 2)) 4374: return 0; 4375: } 4376: return 1; 4377: 4378: case 3: 4379: /* Both BIV_ADD and GIV_MULT are constant; 4380: can compute the product at compile time. */ 4381: return 1; 4382: 4383: default: 4384: abort (); 4385: } 4386: } 4387: 4388: 4389: /* Check to see if loop can be terminated by a "decrement and branch until 4390: zero" instruction. If so, add a REG_NONNEG note to the branch insn if so. 4391: Also try reversing an increment loop to a decrement loop 4392: to see if the optimization can be performed. 4393: Value is nonzero if optimization was performed. */ 4394: 4395: static int 4396: check_dbra_loop (loop_end, iv_list, insn_count, loop_start) 4397: rtx loop_end; 4398: struct iv_class *iv_list; 4399: int insn_count; 4400: rtx loop_start; 4401: { 4402: struct iv_class *bl; 4403: rtx reg; 4404: rtx jump_label; 4405: rtx final_value; 4406: rtx start_value; 4407: enum rtx_code branch_code; 4408: rtx new_add_val; 4409: rtx tested_before_loop = 0; 4410: rtx p; 4411: 4412: /* See if the loop is contained in `if (X >= 0)' for some reg X. 4413: If so, then we know X is initially nonnegative even though 4414: we don't know its initial value. 4415: Record X in TESTED_BEFORE_LOOP. */ 4416: 4417: for (p = loop_start; p != 0; p = PREV_INSN (p)) 4418: if (GET_CODE (p) != NOTE) 4419: break; 4420: 4421: /* See if a conditional branch preceeds the loop. 4422: There may be no other insns or labels between it and 4423: the beginning of the loop. */ 4424: if (p != 0 && GET_CODE (p) == JUMP_INSN && condjump_p (p) 4425: && SET_SRC (PATTERN (p)) != pc_rtx 4426: && ((GET_CODE (XEXP (SET_SRC (PATTERN (p)), 0)) == LT 4427: && XEXP (SET_SRC (PATTERN (p)), 2) == pc_rtx) 4428: || 4429: (GET_CODE (XEXP (SET_SRC (PATTERN (p)), 0)) == GE 4430: && XEXP (SET_SRC (PATTERN (p)), 1) == pc_rtx)) 4431: && next_real_insn (JUMP_LABEL (p)) == next_real_insn (loop_end)) 4432: { 4433: /* Before the branch should be a test or compare. 4434: See if we are comparing something against zero. */ 4435: p = PREV_INSN (p); 4436: if (GET_CODE (p) == INSN && GET_CODE (PATTERN (p)) == SET 4437: && SET_DEST (PATTERN (p)) == cc0_rtx) 4438: { 4439: if (GET_CODE (SET_SRC (PATTERN (p))) == REG) 4440: tested_before_loop = SET_SRC (PATTERN (p)); 1.1.1.14 root 4441: else if (GET_CODE (SET_SRC (PATTERN (p))) == COMPARE 4442: && GET_CODE (XEXP (SET_SRC (PATTERN (p)), 0)) == REG 1.1.1.8 root 4443: && XEXP (SET_SRC (PATTERN (p)), 1) == const0_rtx) 4444: tested_before_loop = XEXP (SET_SRC (PATTERN (p)), 0); 1.1.1.14 root 4445: else if (GET_CODE (SET_SRC (PATTERN (p))) == COMPARE 4446: && GET_CODE (XEXP (SET_SRC (PATTERN (p)), 1)) == REG 4447: && XEXP (SET_SRC (PATTERN (p)), 0) == const0_rtx) 4448: tested_before_loop = XEXP (SET_SRC (PATTERN (p)), 1); 1.1.1.8 root 4449: } 4450: } 4451: 4452: /* If last insn is a conditional branch, and the insn before tests a register 4453: value, then try to optimize it. */ 4454: 4455: if (GET_CODE (PREV_INSN (loop_end)) == JUMP_INSN 4456: && GET_CODE (PATTERN (PREV_INSN (loop_end))) == SET 4457: && GET_CODE (SET_SRC (PATTERN (PREV_INSN (loop_end)))) == IF_THEN_ELSE 4458: && GET_CODE (PREV_INSN (PREV_INSN (loop_end))) == INSN 4459: && GET_CODE (PATTERN (PREV_INSN (PREV_INSN (loop_end)))) == SET 4460: && (GET_CODE (SET_DEST (PATTERN (PREV_INSN (PREV_INSN (loop_end))))) == 4461: CC0)) 4462: { 4463: /* Check all of the bivs to see if the compare uses one of them. */ 4464: 4465: for (bl = iv_list; bl; bl = bl->next) 4466: { 4467: if (reg_mentioned_p (SET_DEST (PATTERN (bl->biv->insn)), 4468: PREV_INSN (PREV_INSN (loop_end)))) 4469: break; 4470: } 4471: 4472: /* If biv set more than once, then give up. 1.1.1.15! root 4473: We can't guarantee that it will be zero on the last iteration. ! 4474: Also give up if the biv is used between its update and the test ! 4475: insn. */ ! 4476: if (bl && bl->biv_count == 1 ! 4477: && ! reg_used_between_p (regno_reg_rtx[bl->regno], bl->biv->insn, ! 4478: PREV_INSN (PREV_INSN (loop_end)))) 1.1.1.8 root 4479: { 4480: /* Look for the case where the basic induction variable is always 4481: nonnegative, and equals zero on the last iteration. 4482: In this case, add a reg_note REG_NONNEG, which allows the 4483: m68k DBRA instruction to be used. */ 4484: 4485: /* the decrement case */ 4486: 4487: if (GET_CODE (bl->biv->add_val) == CONST_INT 4488: && INTVAL (bl->biv->add_val) < 0) 4489: { 4490: /* Initial value must be greater than 0, 4491: init_val % -dec_value == 0 to ensure that it equals zero on 4492: the last iteration */ 4493: 4494: if (GET_CODE (bl->initial_value) == CONST_INT 4495: && INTVAL (bl->initial_value) > 0 4496: && (INTVAL (bl->initial_value) % 4497: (-INTVAL (bl->biv->add_val))) == 0) 4498: { 4499: /* register always nonnegative, add REG_NOTE to branch */ 4500: REG_NOTES (PREV_INSN (loop_end)) 4501: = gen_rtx (EXPR_LIST, REG_NONNEG, 0, 4502: REG_NOTES (PREV_INSN (loop_end))); 4503: bl->nonneg = 1; 4504: 4505: return 1; 4506: } 4507: 4508: /* If the decrement is 1 and the value was tested as >= 0 before 4509: the loop, then we can safely optimize. */ 4510: if (SET_DEST (PATTERN (bl->biv->insn)) == tested_before_loop 4511: && INTVAL (bl->biv->add_val) == -1) 4512: { 4513: REG_NOTES (PREV_INSN (loop_end)) 4514: = gen_rtx (EXPR_LIST, REG_NONNEG, 0, 4515: REG_NOTES (PREV_INSN (loop_end))); 4516: bl->nonneg = 1; 4517: 4518: return 1; 4519: } 4520: } 1.1.1.15! root 4521: else if (num_mem_sets <= 1) 1.1.1.8 root 4522: { 4523: /* Try to change inc to dec, so can apply above optimization. */ 4524: /* Can do this if: 4525: all registers modified are induction variables or invariant, 4526: all memory references have non-overlapping addresses 4527: (obviously true if only one write) 4528: allow 2 insns for the compare/jump at the end of the loop. */ 1.1.1.15! root 4529: int num_nonfixed_reads = 0; ! 4530: rtx p; ! 4531: ! 4532: for (p = loop_start; p != loop_end; p = NEXT_INSN (p)) ! 4533: if (GET_CODE (p) == INSN || GET_CODE (p) == CALL_INSN ! 4534: || GET_CODE (p) == JUMP_INSN) ! 4535: num_nonfixed_reads += count_nonfixed_reads (PATTERN (p)); 1.1.1.8 root 4536: 4537: /* This code only acts for innermost loops. Also it simplifies 4538: the memory address check by only reversing loops with 1.1.1.15! root 4539: zero or one memory access. ! 4540: Two memory accesses could involve parts of the same array, ! 4541: and that can't be reversed. */ 1.1.1.8 root 4542: 1.1.1.15! root 4543: if (num_nonfixed_reads <= 1 1.1.1.8 root 4544: && !loop_has_call 4545: && (bl->giv_count + bl->biv_count + num_mem_sets 4546: + num_movables + 2 == insn_count)) 4547: { 4548: rtx src_two_before_end; 1.1.1.15! root 4549: int constant; ! 4550: int win; 1.1.1.8 root 4551: 4552: /* Loop can be reversed. */ 4553: if (loop_dump_stream) 4554: fprintf (loop_dump_stream, "Can reverse loop\n"); 4555: 4556: /* Now check other conditions: 4557: initial_value must be zero, 4558: final_value % add_val == 0, so that when reversed, the 4559: biv will be zero on the last iteration. */ 4560: 4561: /* Calculating the final value non trivial. 4562: If branch is (LT (CC0) (CONST 0), 4563: then value in compare is final value. 4564: If branch is (LE (CC0) (CONST 0), 4565: then value in compare is final_value - add_val */ 4566: 4567: branch_code 4568: = GET_CODE (XEXP (SET_SRC (PATTERN (PREV_INSN (loop_end))), 0)); 4569: src_two_before_end 1.1.1.14 root 4570: = SET_SRC (PATTERN (PREV_INSN (PREV_INSN (loop_end)))); 1.1.1.8 root 4571: 1.1.1.15! root 4572: win = 1; ! 4573: if (GET_CODE (src_two_before_end) == REG) ! 4574: constant = 0; ! 4575: else if (GET_CODE (src_two_before_end) == COMPARE ! 4576: && GET_CODE (XEXP (src_two_before_end, 1)) == CONST_INT) ! 4577: constant = INTVAL (XEXP (src_two_before_end, 1)); ! 4578: else ! 4579: win = 0; ! 4580: ! 4581: if (win && bl->initial_value == const0_rtx 1.1.1.8 root 4582: && (branch_code == LT || branch_code == LE) 4583: && XEXP (XEXP (SET_SRC (PATTERN (PREV_INSN (loop_end))), 0), 1) == const0_rtx 1.1.1.15! root 4584: && (constant % INTVAL (bl->biv->add_val)) == 0) 1.1.1.8 root 4585: { 4586: /* Register will always be nonnegative, with value 4587: 0 on last iteration if loop reversed */ 4588: 4589: /* Save some info needed to produce the new insns. */ 4590: reg = SET_DEST (PATTERN (bl->biv->insn)); 4591: jump_label = XEXP (SET_SRC (PATTERN (PREV_INSN (loop_end))), 1); 4592: new_add_val = gen_rtx (CONST_INT, VOIDmode, 4593: - INTVAL (bl->biv->add_val)); 4594: 4595: 4596: if (branch_code == LT) 4597: { 1.1.1.15! root 4598: final_value ! 4599: = gen_rtx (CONST_INT, VOIDmode, constant); 1.1.1.8 root 4600: start_value 4601: = gen_rtx (CONST_INT, VOIDmode, 1.1.1.15! root 4602: (constant - INTVAL (bl->biv->add_val))); 1.1.1.8 root 4603: } 4604: else /* branch_code == LE */ 4605: { 1.1.1.15! root 4606: start_value ! 4607: = gen_rtx (CONST_INT, VOIDmode, constant); 1.1.1.8 root 4608: final_value 4609: = gen_rtx (CONST_INT, VOIDmode, 1.1.1.15! root 4610: (constant + INTVAL (bl->biv->add_val))); 1.1.1.8 root 4611: } 4612: 4613: /* Initialize biv to start_value before loop start. 4614: The old initializing insn will be deleted as a 4615: dead store by flow.c. */ 4616: emit_insn_before (gen_rtx (SET, VOIDmode, reg, 4617: start_value), 4618: loop_start); 4619: 4620: /* Add insn to decrement register, and delete insn 4621: that incremented the register. */ 4622: emit_insn_before (gen_rtx (SET, VOIDmode, reg, 4623: gen_rtx (PLUS, GET_MODE (reg), reg, 4624: new_add_val)), 4625: bl->biv->insn); 4626: /* Update biv info to reflect its new status. */ 4627: bl->biv->insn = PREV_INSN (bl->biv->insn); 4628: delete_insn (NEXT_INSN (bl->biv->insn)); 4629: 1.1.1.15! root 4630: /* Inc LABEL_NUSES so that delete_insn will 1.1.1.8 root 4631: not delete the label. */ 1.1.1.15! root 4632: LABEL_NUSES (XEXP (jump_label, 0)) ++; 1.1.1.8 root 4633: 4634: if (regno_last_uid[bl->regno] != INSN_UID (PREV_INSN (loop_end))) 4635: emit_insn_after (gen_rtx (SET, VOIDmode, reg, 4636: final_value), 4637: loop_end); 4638: 4639: /* Delete compare/branch at end of loop. */ 4640: delete_insn (PREV_INSN (loop_end)); 4641: delete_insn (PREV_INSN (loop_end)); 4642: 4643: /* Add new compare/branch insn at end of loop. */ 4644: emit_insn_before (gen_rtx (SET, VOIDmode, cc0_rtx, reg), 4645: loop_end); 4646: emit_jump_insn_before (gen_rtx (SET, VOIDmode, pc_rtx, 4647: gen_rtx (IF_THEN_ELSE, VOIDmode, 4648: gen_rtx (GE, VOIDmode, cc0_rtx, 4649: const0_rtx), 4650: jump_label, 4651: pc_rtx)), 4652: loop_end); 4653: 1.1.1.15! root 4654: JUMP_LABEL (PREV_INSN (loop_end)) = XEXP (jump_label, 0); ! 4655: /* Increment of LABEL_NUSES done above. */ ! 4656: 1.1.1.8 root 4657: /* Register is now always nonnegative, 4658: so add REG_NONNEG note to the branch. */ 4659: REG_NOTES (PREV_INSN (loop_end)) 4660: = gen_rtx (EXPR_LIST, REG_NONNEG, 0, 4661: REG_NOTES (PREV_INSN (loop_end))); 4662: bl->nonneg = 1; 4663: 4664: /* Update rest of biv info. */ 4665: bl->initial_value = start_value; 4666: bl->biv->add_val = new_add_val; 4667: 4668: if (loop_dump_stream) 4669: fprintf (loop_dump_stream, "Reversed loop and added reg_nonneg\n"); 4670: 4671: return 1; 4672: } 4673: } 4674: } 4675: } 4676: } 4677: return 0; 4678: } 4679: 1.1.1.14 root 4680: /* Verify whether the biv BL appears to be eliminable, 4681: based on the insns in the loop that refer to it. 4682: LOOP_START is the first insn of the loop, and END is the end insn. */ 4683: 4684: static void 4685: check_eliminate_biv (bl, loop_start, end) 4686: struct iv_class *bl; 4687: rtx loop_start; 4688: rtx end; 4689: { 4690: /* Get the REG rtx for the biv. */ 4691: rtx reg = SET_DEST (PATTERN (bl->biv->insn)); 4692: rtx p; 4693: struct induction *v; 4694: 4695: bl->eliminable = 0; 4696: 4697: for (p = loop_start; p != end; p = NEXT_INSN (p)) 4698: { 4699: enum rtx_code code = GET_CODE (p); 4700: if ((code == INSN || code == JUMP_INSN || code == CALL_INSN) 4701: && reg_mentioned_p (reg, PATTERN (p))) 4702: { 4703: /* This insn uses the biv. If we can't understand it, 4704: then we can't eliminate the biv. */ 4705: if (GET_CODE (PATTERN (p)) != SET) 4706: { 4707: if (loop_dump_stream) 4708: fprintf (loop_dump_stream, 4709: "Cannot eliminate biv %d: cannot understand insn %d.\n", 4710: bl->regno, INSN_UID (p)); 4711: break; 4712: } 4713: 4714: /* The insns that increment the biv are no problem. */ 4715: if (SET_DEST (PATTERN (p)) == reg) 4716: continue; 4717: 4718: /* If this is an insn which uses the biv ONLY in the 4719: calculation of a giv which is in the family of this 4720: biv, it's ok becuase it will go away when the giv is 4721: reduced. March 14, 1989 -- [email protected] */ 4722: for (v = bl->giv; v; v = v->family) 4723: if (v->insn == p) 4724: { 4725: if (v->giv_type == DEST_REG 4726: || (v->giv_type == DEST_ADDR 4727: && ! only_reg_use_p (reg, *(v->location), 4728: PATTERN (p)))) 4729: break; 4730: } 4731: if (v) 4732: continue; 4733: 4734: /* If can rewrite this insn not to use the biv, it's ok. */ 4735: if (can_eliminate_biv_p (p, bl)) 4736: continue; 4737: 4738: /* Biv is used in a way we cannot eliminate. */ 4739: if (loop_dump_stream) 4740: fprintf (loop_dump_stream, 4741: "Cannot eliminate biv %d: biv used in insn %d.\n", 4742: bl->regno, INSN_UID (p)); 4743: break; 4744: } 4745: } 4746: 4747: if (p == end) 4748: { 4749: bl->eliminable = 1; 4750: if (loop_dump_stream) 4751: fprintf (loop_dump_stream, "Can eliminate biv %d.\n", 4752: bl->regno); 4753: } 4754: } 4755: 1.1.1.8 root 4756: /* Return 1 if INSN, a compare insn which tests the biv described by BL, 4757: can be rewritten to use instead some reduced giv related to that biv. 4758: Does not change the rtl. 4759: 4760: We make the assumption that all the givs depending on this biv 4761: will be reduced, since only in that case will an attempt to eliminate 4762: the biv actually be made. 4763: 4764: The following function is very parallel to this one. */ 4765: 4766: static int 4767: can_eliminate_biv_p (insn, bl) 4768: rtx insn; 4769: struct iv_class *bl; 4770: { 4771: rtx src; 4772: enum rtx_code code; 4773: struct induction *v, *tv; 4774: rtx arg; 4775: int arg_operand; 4776: /* Mode of this biv. */ 1.1.1.14 root 4777: enum machine_mode mode = bl->biv->mode; 1.1.1.8 root 4778: 4779: if (SET_DEST (PATTERN (insn)) != cc0_rtx) 4780: return 0; 4781: 4782: src = SET_SRC (PATTERN (insn)); 4783: code = GET_CODE (src); 4784: 4785: switch (code) 4786: { 4787: /* a test insn */ 4788: case REG: 4789: /* Can replace with any giv that has (MULT_VAL != 0) and (ADD_VAL == 0) 1.1.1.14 root 4790: Require a constant integer for MULT_VAL, so we know it's nonzero. */ 1.1.1.8 root 4791: 4792: for (v = bl->giv; v; v = v->family) 1.1.1.14 root 4793: if (GET_CODE (v->mult_val) == CONST_INT && v->mult_val != const0_rtx 4794: && v->add_val == const0_rtx 4795: && ! v->ignore 4796: && v->mode == mode) 1.1.1.8 root 4797: return 1; 4798: 4799: /* Look for a giv with (MULT_VAL != 0) and (ADD_VAL != 0); 1.1.1.14 root 4800: replace test insn with a compare insn (cmp REDUCED_GIV ADD_VAL). 4801: Require a constant integer for MULT_VAL, so we know it's nonzero. */ 1.1.1.8 root 4802: 4803: for (v = bl->giv; v; v = v->family) 1.1.1.14 root 4804: if (GET_CODE (v->mult_val) == CONST_INT && v->mult_val != const0_rtx 4805: && ! v->ignore 4806: && v->mode == mode) 1.1.1.8 root 4807: return 1; 1.1.1.14 root 4808: 4809: if (loop_dump_stream) 4810: fprintf (loop_dump_stream, "Cannot eliminate biv %d in test insn %d: no appropriate giv.\n", 4811: bl->regno, INSN_UID (insn)); 4812: 1.1.1.8 root 4813: return 0; 4814: 4815: /* a compare insn */ 1.1.1.13 root 4816: case COMPARE: 1.1.1.8 root 4817: /* Figure out which operand is the biv. */ 4818: if ((GET_CODE (XEXP (src, 0)) == REG) 4819: && (REGNO (XEXP (src, 0)) == bl->regno)) 4820: { 4821: arg = XEXP (src, 1); 4822: arg_operand = 1; 4823: } 4824: else 4825: { 4826: arg = XEXP (src, 0); 4827: arg_operand = 0; 4828: } 4829: 4830: if (GET_CODE (arg) == CONST_INT) 4831: { 4832: /* Can replace with any giv that has constant coefficients. */ 4833: 4834: for (v = bl->giv; v; v = v->family) 4835: if (GET_CODE (v->mult_val) == CONST_INT 4836: && GET_CODE (v->add_val) == CONST_INT 1.1.1.14 root 4837: && ! v->ignore 4838: && v->mode == mode) 1.1.1.8 root 4839: return 1; 4840: 4841: /* Look for giv with constant mult_val and nonconst add_val, 4842: since we can insert add insn before loop 4843: to calculate new compare value. */ 4844: 4845: for (v = bl->giv; v; v = v->family) 4846: if (GET_CODE (v->mult_val) == CONST_INT 1.1.1.14 root 4847: && ! v->ignore 4848: && v->mode == mode) 1.1.1.8 root 4849: return 1; 4850: } 4851: else if (GET_CODE (arg) == REG || GET_CODE (arg) == MEM) 4852: { 4853: /* Comparing against invariant register or memref can be handled. */ 4854: 4855: if (invariant_p (arg)) 4856: { 4857: /* Look for giv with constant mult_val and nonconst add_val. 4858: Insert add-insn before loop to compute new compare value. */ 4859: 4860: for (v = bl->giv; v; v = v->family) 4861: if ((GET_CODE (v->mult_val) == CONST_INT) 1.1.1.14 root 4862: && ! v->ignore 4863: && v->mode == mode) 1.1.1.8 root 4864: return 1; 4865: } 4866: 4867: /* Otherwise, only comparing against a biv can be handled. */ 4868: if (GET_CODE (arg) != REG 4869: || induct_var[REGNO (arg)] != BASIC_INDUCT) 4870: return 0; 4871: 4872: /* Look for a giv for each biv that have identical 4873: values for mult_val and add_val. */ 4874: for (v = bl->giv; v; v = v->family) 1.1.1.14 root 4875: if (v->mode == mode 4876: && ! v->ignore) 1.1.1.8 root 4877: { 4878: for (tv = class_struct[REGNO (arg)]->giv; tv; tv = tv->family) 4879: if ((tv->new_reg != 0) 4880: && rtx_equal_p (tv->mult_val, v->mult_val) 4881: && rtx_equal_p (tv->mult_val, v->mult_val) 1.1.1.14 root 4882: && ! tv->ignore 4883: && tv->mode == mode) 1.1.1.8 root 4884: return 1; 4885: } 4886: } 4887: return 0; 4888: 4889: default: 4890: return 0; 4891: } 4892: } 4893: 4894: /* Rewrite a compare insn INSN which uses the biv described by BL 4895: so that it doesn't use that biv any more. 4896: Instead it will use some reduced giv related to that biv. 4897: 4898: The preceding function is very parallel to this one. */ 4899: 4900: static void 4901: eliminate_biv (insn, bl, loop_start) 4902: rtx insn; 4903: struct iv_class *bl; 4904: rtx loop_start; 4905: { 4906: rtx src = SET_SRC (PATTERN (insn)); 4907: enum rtx_code code = GET_CODE (src); 4908: struct induction *v, *tv; 4909: rtx arg; 4910: int arg_operand; 4911: /* Mode of this biv. */ 1.1.1.14 root 4912: enum machine_mode mode = bl->biv->mode; 1.1.1.8 root 4913: 4914: switch (code) 4915: { 4916: /* a test insn */ 4917: case REG: 1.1.1.14 root 4918: /* Can replace with any giv that was reduced and 4919: that has (MULT_VAL != 0) and (ADD_VAL == 0). 4920: Require a constant integer for MULT_VAL, so we know it's nonzero. */ 1.1.1.8 root 4921: 4922: for (v = bl->giv; v; v = v->family) 1.1.1.14 root 4923: if (GET_CODE (v->mult_val) == CONST_INT && v->mult_val != const0_rtx 4924: && v->add_val == const0_rtx 1.1.1.8 root 4925: && v->new_reg != 0 1.1.1.14 root 4926: && v->mode == mode) 1.1.1.8 root 4927: break; 4928: if (v) 4929: { 4930: /* We can test the sign of that giv's reduced reg. */ 4931: SET_SRC (PATTERN (insn)) = v->new_reg; 4932: return; 4933: } 4934: 4935: /* Look for a giv with (MULT_VAL != 0) and (ADD_VAL != 0); 1.1.1.14 root 4936: replace test insn with a compare insn (cmp REDUCED_GIV ADD_VAL). 4937: Require a constant integer for MULT_VAL, so we know it's nonzero. */ 1.1.1.8 root 4938: 4939: for (v = bl->giv; v; v = v->family) 1.1.1.14 root 4940: if (GET_CODE (v->mult_val) == CONST_INT && v->mult_val != const0_rtx 4941: && v->new_reg != 0 4942: && v->mode == mode) 1.1.1.8 root 4943: break; 4944: if (v) 4945: { 4946: /* Replace biv with the giv's reduced register. */ 1.1.1.14 root 4947: SET_SRC (PATTERN (insn)) = gen_rtx (COMPARE, GET_MODE (v->new_reg), 1.1.1.15! root 4948: v->new_reg, ! 4949: copy_rtx (v->add_val)); 1.1.1.8 root 4950: 4951: #if 0 4952: /* add_val must be invariant, so don't bother storing in a register */ 4953: /* calculate the appropriate constant to compare against */ 4954: emit_insn_before (gen_rtx (SET, VOIDmode, compare_value, 1.1.1.15! root 4955: copy_rtx (v->add_val)), 1.1.1.8 root 4956: loop_start); 4957: #endif 4958: return; 4959: } 4960: abort (); 4961: break; 4962: 4963: /* a compare insn */ 1.1.1.13 root 4964: case COMPARE: 1.1.1.8 root 4965: /* Figure out which operand is the biv. */ 1.1.1.13 root 4966: if (GET_CODE (XEXP (src, 0)) == REG 4967: && REGNO (XEXP (src, 0)) == bl->regno) 1.1.1.8 root 4968: { 4969: arg = XEXP (src, 1); 4970: arg_operand = 1; 4971: } 4972: else 4973: { 4974: arg = XEXP (src, 0); 4975: arg_operand = 0; 4976: } 4977: 4978: if (GET_CODE (arg) == CONST_INT) 4979: { 4980: /* Can replace with any giv that has constant mult_val and add_val. 4981: Make sure it was strength reduced by checking new_reg != 0. */ 4982: 4983: for (v = bl->giv; v; v = v->family) 4984: if (GET_CODE (v->mult_val) == CONST_INT 4985: && GET_CODE (v->add_val) == CONST_INT 4986: && v->new_reg 1.1.1.14 root 4987: && v->mode == mode) 1.1.1.8 root 4988: break; 4989: if (v) 4990: { 1.1.1.15! root 4991: rtx newval; 1.1.1.8 root 4992: /* Replace biv with the giv's reduced reg. */ 4993: XEXP (src, 1-arg_operand) = v->new_reg; 4994: /* Calculate the appropriate constant to compare against. */ 1.1.1.15! root 4995: newval = gen_rtx (CONST_INT, VOIDmode, ! 4996: (INTVAL (arg) * INTVAL (v->mult_val) ! 4997: + INTVAL (v->add_val))); ! 4998: XEXP (src, arg_operand) = newval; ! 4999: /* If that constant is no good in a compare, ! 5000: put it in a register. */ ! 5001: if (recog (PATTERN (insn), insn) < 0) ! 5002: { ! 5003: rtx temp = gen_reg_rtx (mode); ! 5004: emit_iv_init_code (arg, v->mult_val, v->add_val, ! 5005: temp, loop_start); ! 5006: XEXP (src, arg_operand) = temp; ! 5007: } 1.1.1.8 root 5008: return; 5009: } 5010: 5011: /* Look for giv with constant mult_val and nonconst add_val. 5012: Insert add insn before loop to calculate new compare value. */ 5013: 5014: for (v = bl->giv; v; v = v->family) 5015: if (GET_CODE (v->mult_val) == CONST_INT 5016: && v->new_reg 1.1.1.14 root 5017: && v->mode == mode) 1.1.1.8 root 5018: break; 5019: if (v) 5020: { 5021: rtx compare_value = gen_reg_rtx (mode); 5022: 5023: /* Replace biv with giv's reduced register. */ 5024: XEXP (src, 1-arg_operand) = v->new_reg; 5025: 5026: /* At start of loop, compute value to compare against. */ 1.1.1.15! root 5027: emit_iv_init_code (arg, v->mult_val, v->add_val, ! 5028: compare_value, loop_start); ! 5029: /* Use it in this insn. */ 1.1.1.8 root 5030: XEXP (src, arg_operand) = compare_value; 5031: return; 5032: } 5033: abort (); 5034: } 5035: else if (GET_CODE (arg) == REG || GET_CODE (arg) == MEM) 5036: { 5037: if (invariant_p (arg)) 5038: { 5039: /* Look for giv with constant mult_val and nonconst add_val. 5040: Insert add-insn before loop to compute new compare value. */ 5041: 5042: for (v = bl->giv; v; v = v->family) 5043: if (GET_CODE (v->mult_val) == CONST_INT 5044: && v->new_reg 1.1.1.14 root 5045: && v->mode == mode) 1.1.1.8 root 5046: break; 5047: if (v) 5048: { 5049: rtx compare_value = gen_reg_rtx (mode); 5050: 5051: /* Replace biv with giv's reduced register. */ 5052: XEXP (src, 1-arg_operand) = v->new_reg; 5053: 1.1.1.15! root 5054: /* At start of loop, compute value to compare against. */ ! 5055: emit_iv_init_code (arg, v->mult_val, v->add_val, ! 5056: compare_value, loop_start); 1.1.1.8 root 5057: XEXP (src, arg_operand) = compare_value; 5058: return; 5059: } 5060: } 5061: 5062: /* Otherwise the reg compared with had better be a biv. */ 5063: if (GET_CODE (arg) != REG 5064: || induct_var[REGNO (arg)] != BASIC_INDUCT) 5065: abort (); 5066: 5067: /* Look for a pair of givs, one for each biv, 5068: with identical coefficients. */ 5069: for (v = bl->giv; v; v = v->family) 5070: { 1.1.1.14 root 5071: if (!v->new_reg && v->mode == mode) 1.1.1.8 root 5072: continue; 5073: for (tv = class_struct[REGNO (arg)]->giv; tv; tv = tv->family) 5074: if ((tv->new_reg != 0) 5075: && rtx_equal_p (tv->mult_val, v->mult_val) 5076: && rtx_equal_p (tv->mult_val, v->mult_val) 1.1.1.14 root 5077: && tv->mode == mode) 1.1.1.8 root 5078: break; 5079: if (tv) 5080: break; 5081: } 5082: if (v) 5083: { 5084: /* Replace biv with its giv's reduced reg. */ 5085: XEXP (src, 1-arg_operand) = v->new_reg; 5086: /* Replace other operand with the other giv's reduced reg. */ 5087: XEXP (src, arg_operand) = tv->new_reg; 5088: return; 5089: } 5090: } 5091: abort (); 5092: 5093: default: 5094: abort (); 5095: } 5096: } 5097: 5098: /* Try to calculate the final value of the biv, 5099: the value it will have at the end of the loop. 5100: If we can do it, return that value. */ 5101: 1.1.1.10 root 5102: /* ??? One case that should be simple to handle 5103: is when the biv is incremented by an invariant 5104: exactly once each time around the loop, 5105: and when the number of iterations can be determined 5106: (as the value of some invariant). 5107: Then the final value would be BIV + (INCREMENT * NUM_ITERATIONS). 5108: 5109: Once that case is handled, it would become desirable to detect empty 5110: loops and delete them, since this optimization could make empty loops. */ 5111: 1.1.1.8 root 5112: static rtx 5113: final_biv_value (bl, loop_end) 5114: struct iv_class *bl; 5115: rtx loop_end; 5116: { 5117: /* wimpy, but guaranteed to work */ 5118: return 0; 5119: } 1.1.1.11 root 5120: 5121: /* Return nonzero if the last use of reg REGNO 5122: is in an insn following INSN in the same basic block. */ 5123: 5124: static int 5125: last_use_this_basic_block (regno, insn) 5126: int regno; 5127: rtx insn; 5128: { 5129: rtx n; 5130: for (n = insn; 5131: n && GET_CODE (n) != CODE_LABEL && GET_CODE (n) != JUMP_INSN; 5132: n = NEXT_INSN (n)) 5133: { 5134: if (regno_last_uid[regno] == INSN_UID (n)) 5135: return 1; 5136: } 5137: return 0; 5138: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.